001/*
002 * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.phases.graph;
024
025import com.oracle.graal.compiler.common.type.*;
026import com.oracle.graal.graph.*;
027import com.oracle.graal.nodes.*;
028
029public class InferStamps {
030
031    /**
032     * Infer the stamps for all Object nodes in the graph, to make the stamps as precise as
033     * possible. For example, this propagates the word-type through phi functions. To handle phi
034     * functions at loop headers, the stamp inference is called until a fix point is reached.
035     * <p>
036     * This method can be used when it is needed that stamps are inferred before the first run of
037     * the canonicalizer. For example, word type rewriting must run before the first run of the
038     * canonicalizer because many nodes are not prepared to see the word type during
039     * canonicalization.
040     */
041    public static void inferStamps(StructuredGraph graph) {
042        /*
043         * We want to make the stamps more precise. For cyclic phi functions, this means we have to
044         * ignore the initial stamp because the imprecise stamp would always propagate around the
045         * cycle. We therefore set the stamp to an illegal stamp, which is automatically ignored
046         * when the phi function performs the "meet" operator on its input stamps.
047         */
048        for (Node n : graph.getNodes()) {
049            if (n instanceof ValuePhiNode) {
050                ValueNode node = (ValueNode) n;
051                if (node.stamp() instanceof ObjectStamp) {
052                    assert node.stamp().hasValues() : "We assume all Phi and Proxy stamps are legal before the analysis";
053                    node.setStamp(node.stamp().empty());
054                }
055            }
056        }
057
058        boolean stampChanged;
059        // The algorithm is not guaranteed to reach a stable state.
060        int z = 0;
061        do {
062            stampChanged = false;
063            /*
064             * We could use GraphOrder.forwardGraph() to process the nodes in a defined order and
065             * propagate long def-use chains in fewer iterations. However, measurements showed that
066             * we have few iterations anyway, and the overhead of computing the order is much higher
067             * than the benefit.
068             */
069            for (Node n : graph.getNodes()) {
070                if (n instanceof ValueNode) {
071                    ValueNode node = (ValueNode) n;
072                    if (node.stamp() instanceof ObjectStamp) {
073                        stampChanged |= node.inferStamp();
074                    }
075                }
076            }
077            ++z;
078        } while (stampChanged && z < 10000);
079
080        /*
081         * Check that all the illegal stamps we introduced above are correctly replaced with real
082         * stamps again.
083         */
084        assert checkNoEmptyStamp(graph);
085    }
086
087    private static boolean checkNoEmptyStamp(StructuredGraph graph) {
088        for (Node n : graph.getNodes()) {
089            if (n instanceof ValuePhiNode) {
090                ValueNode node = (ValueNode) n;
091                assert node.stamp().hasValues() : "Stamp is empty after analysis. This is not necessarily an error, but a condition that we want to investigate (and then maybe relax or remove the assertion).";
092            }
093        }
094        return true;
095    }
096}