1 /*
   2  * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.graalvm.compiler.phases.graph;
  24 
  25 import org.graalvm.compiler.core.common.type.ObjectStamp;
  26 import org.graalvm.compiler.graph.Node;
  27 import org.graalvm.compiler.nodes.StructuredGraph;
  28 import org.graalvm.compiler.nodes.ValueNode;
  29 import org.graalvm.compiler.nodes.ValuePhiNode;
  30 
  31 public class InferStamps {
  32 
  33     /**
  34      * Infer the stamps for all Object nodes in the graph, to make the stamps as precise as
  35      * possible. For example, this propagates the word-type through phi functions. To handle phi
  36      * functions at loop headers, the stamp inference is called until a fix point is reached.
  37      * <p>
  38      * This method can be used when it is needed that stamps are inferred before the first run of
  39      * the canonicalizer. For example, word type rewriting must run before the first run of the
  40      * canonicalizer because many nodes are not prepared to see the word type during
  41      * canonicalization.
  42      */
  43     public static void inferStamps(StructuredGraph graph) {
  44         /*
  45          * We want to make the stamps more precise. For cyclic phi functions, this means we have to
  46          * ignore the initial stamp because the imprecise stamp would always propagate around the
  47          * cycle. We therefore set the stamp to an illegal stamp, which is automatically ignored
  48          * when the phi function performs the "meet" operator on its input stamps.
  49          */
  50         for (Node n : graph.getNodes()) {
  51             if (n instanceof ValuePhiNode) {
  52                 ValueNode node = (ValueNode) n;
  53                 if (node.stamp() instanceof ObjectStamp) {
  54                     assert node.stamp().hasValues() : "We assume all Phi and Proxy stamps are legal before the analysis";
  55                     node.setStamp(node.stamp().empty());
  56                 }
  57             }
  58         }
  59 
  60         boolean stampChanged;
  61         // The algorithm is not guaranteed to reach a stable state.
  62         int z = 0;
  63         do {
  64             stampChanged = false;
  65             /*
  66              * We could use GraphOrder.forwardGraph() to process the nodes in a defined order and
  67              * propagate long def-use chains in fewer iterations. However, measurements showed that
  68              * we have few iterations anyway, and the overhead of computing the order is much higher
  69              * than the benefit.
  70              */
  71             for (Node n : graph.getNodes()) {
  72                 if (n instanceof ValueNode) {
  73                     ValueNode node = (ValueNode) n;
  74                     if (node.stamp() instanceof ObjectStamp) {
  75                         stampChanged |= node.inferStamp();
  76                     }
  77                 }
  78             }
  79             ++z;
  80         } while (stampChanged && z < 10000);
  81 
  82         /*
  83          * Check that all the illegal stamps we introduced above are correctly replaced with real
  84          * stamps again.
  85          */
  86         assert checkNoEmptyStamp(graph);
  87     }
  88 
  89     private static boolean checkNoEmptyStamp(StructuredGraph graph) {
  90         for (Node n : graph.getNodes()) {
  91             if (n instanceof ValuePhiNode) {
  92                 ValueNode node = (ValueNode) n;
  93                 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).";
  94             }
  95         }
  96         return true;
  97     }
  98 }