1 /*
   2  * Copyright (c) 2011, 2018, 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 
  24 
  25 package org.graalvm.compiler.phases.util;
  26 
  27 import java.util.ArrayList;
  28 import java.util.List;
  29 
  30 import jdk.internal.vm.compiler.collections.EconomicMap;
  31 import jdk.internal.vm.compiler.collections.Equivalence;
  32 import org.graalvm.compiler.core.common.cfg.Loop;
  33 import org.graalvm.compiler.debug.GraalError;
  34 import org.graalvm.compiler.graph.GraalGraphError;
  35 import org.graalvm.compiler.graph.Node;
  36 import org.graalvm.compiler.graph.NodeBitMap;
  37 import org.graalvm.compiler.nodes.AbstractEndNode;
  38 import org.graalvm.compiler.nodes.AbstractMergeNode;
  39 import org.graalvm.compiler.nodes.ConstantNode;
  40 import org.graalvm.compiler.nodes.EndNode;
  41 import org.graalvm.compiler.nodes.FixedNode;
  42 import org.graalvm.compiler.nodes.FrameState;
  43 import org.graalvm.compiler.nodes.FullInfopointNode;
  44 import org.graalvm.compiler.nodes.LoopBeginNode;
  45 import org.graalvm.compiler.nodes.LoopExitNode;
  46 import org.graalvm.compiler.nodes.PhiNode;
  47 import org.graalvm.compiler.nodes.ProxyNode;
  48 import org.graalvm.compiler.nodes.StateSplit;
  49 import org.graalvm.compiler.nodes.StructuredGraph;
  50 import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
  51 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
  52 import org.graalvm.compiler.nodes.ValueNode;
  53 import org.graalvm.compiler.nodes.VirtualState;
  54 import org.graalvm.compiler.nodes.VirtualState.NodeClosure;
  55 import org.graalvm.compiler.nodes.cfg.Block;
  56 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
  57 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator;
  58 import org.graalvm.compiler.phases.graph.ReentrantBlockIterator.BlockIteratorClosure;
  59 import org.graalvm.compiler.phases.graph.StatelessPostOrderNodeIterator;
  60 import org.graalvm.compiler.phases.schedule.SchedulePhase;
  61 import org.graalvm.compiler.phases.schedule.SchedulePhase.SchedulingStrategy;
  62 
  63 public final class GraphOrder {
  64 
  65     private GraphOrder() {
  66     }
  67 
  68     /**
  69      * Quick (and imprecise) assertion that there are no (invalid) cycles in the given graph. First,
  70      * an ordered list of all nodes in the graph (a total ordering) is created. A second run over
  71      * this list checks whether inputs are scheduled before their usages.
  72      *
  73      * @param graph the graph to be checked.
  74      * @throws AssertionError if a cycle was detected.
  75      */
  76     public static boolean assertNonCyclicGraph(StructuredGraph graph) {
  77         List<Node> order = createOrder(graph);
  78         NodeBitMap visited = graph.createNodeBitMap();
  79         visited.clearAll();
  80         for (Node node : order) {
  81             if (node instanceof PhiNode && ((PhiNode) node).merge() instanceof LoopBeginNode) {
  82                 assert visited.isMarked(((PhiNode) node).valueAt(0));
  83                 // nothing to do
  84             } else {
  85                 for (Node input : node.inputs()) {
  86                     if (!visited.isMarked(input)) {
  87                         if (input instanceof FrameState) {
  88                             // nothing to do - frame states are known, allowed cycles
  89                         } else {
  90                             assert false : "unexpected cycle detected at input " + node + " -> " + input;
  91                         }
  92                     }
  93                 }
  94             }
  95             visited.mark(node);
  96         }
  97         return true;
  98     }
  99 
 100     private static List<Node> createOrder(StructuredGraph graph) {
 101         final ArrayList<Node> nodes = new ArrayList<>();
 102         final NodeBitMap visited = graph.createNodeBitMap();
 103 
 104         new StatelessPostOrderNodeIterator(graph.start()) {
 105             @Override
 106             protected void node(FixedNode node) {
 107                 visitForward(nodes, visited, node, false);
 108             }
 109         }.apply();
 110         return nodes;
 111     }
 112 
 113     private static void visitForward(ArrayList<Node> nodes, NodeBitMap visited, Node node, boolean floatingOnly) {
 114         try {
 115             assert node == null || node.isAlive() : node + " not alive";
 116             if (node != null && !visited.isMarked(node)) {
 117                 if (floatingOnly && node instanceof FixedNode) {
 118                     throw new GraalError("unexpected reference to fixed node: %s (this indicates an unexpected cycle)", node);
 119                 }
 120                 visited.mark(node);
 121                 FrameState stateAfter = null;
 122                 if (node instanceof StateSplit) {
 123                     stateAfter = ((StateSplit) node).stateAfter();
 124                 }
 125                 for (Node input : node.inputs()) {
 126                     if (input != stateAfter) {
 127                         visitForward(nodes, visited, input, true);
 128                     }
 129                 }
 130                 if (node instanceof EndNode) {
 131                     EndNode end = (EndNode) node;
 132                     for (PhiNode phi : end.merge().phis()) {
 133                         visitForward(nodes, visited, phi.valueAt(end), true);
 134                     }
 135                 }
 136                 nodes.add(node);
 137                 if (node instanceof AbstractMergeNode) {
 138                     for (PhiNode phi : ((AbstractMergeNode) node).phis()) {
 139                         visited.mark(phi);
 140                         nodes.add(phi);
 141                     }
 142                 }
 143                 if (stateAfter != null) {
 144                     visitForward(nodes, visited, stateAfter, true);
 145                 }
 146             }
 147         } catch (GraalError e) {
 148             throw GraalGraphError.transformAndAddContext(e, node);
 149         }
 150     }
 151 
 152     /**
 153      * This method schedules the graph and makes sure that, for every node, all inputs are available
 154      * at the position where it is scheduled. This is a very expensive assertion.
 155      */
 156     public static boolean assertSchedulableGraph(final StructuredGraph graph) {
 157         assert graph.getGuardsStage() != GuardsStage.AFTER_FSA : "Cannot use the BlockIteratorClosure after FrameState Assignment, HIR Loop Data Structures are no longer valid.";
 158         try {
 159             final SchedulePhase schedulePhase = new SchedulePhase(SchedulingStrategy.LATEST_OUT_OF_LOOPS, true);
 160             final EconomicMap<LoopBeginNode, NodeBitMap> loopEntryStates = EconomicMap.create(Equivalence.IDENTITY);
 161             schedulePhase.apply(graph, false);
 162             final ScheduleResult schedule = graph.getLastSchedule();
 163 
 164             BlockIteratorClosure<NodeBitMap> closure = new BlockIteratorClosure<NodeBitMap>() {
 165 
 166                 @Override
 167                 protected List<NodeBitMap> processLoop(Loop<Block> loop, NodeBitMap initialState) {
 168                     return ReentrantBlockIterator.processLoop(this, loop, initialState).exitStates;
 169                 }
 170 
 171                 @Override
 172                 protected NodeBitMap processBlock(final Block block, final NodeBitMap currentState) {
 173                     final List<Node> list = graph.getLastSchedule().getBlockToNodesMap().get(block);
 174 
 175                     /*
 176                      * A stateAfter is not valid directly after its associated state split, but
 177                      * right before the next fixed node. Therefore a pending stateAfter is kept that
 178                      * will be checked at the correct position.
 179                      */
 180                     FrameState pendingStateAfter = null;
 181                     for (final Node node : list) {
 182                         if (node instanceof ValueNode) {
 183                             FrameState stateAfter = node instanceof StateSplit ? ((StateSplit) node).stateAfter() : null;
 184                             if (node instanceof FullInfopointNode) {
 185                                 stateAfter = ((FullInfopointNode) node).getState();
 186                             }
 187 
 188                             if (pendingStateAfter != null && node instanceof FixedNode) {
 189                                 pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() {
 190                                     @Override
 191                                     public void apply(Node usage, Node nonVirtualNode) {
 192                                         assert currentState.isMarked(nonVirtualNode) || nonVirtualNode instanceof VirtualObjectNode || nonVirtualNode instanceof ConstantNode : nonVirtualNode +
 193                                                         " not available at virtualstate " + usage + " before " + node + " in block " + block + " \n" + list;
 194                                     }
 195                                 });
 196                                 pendingStateAfter = null;
 197                             }
 198 
 199                             if (node instanceof AbstractMergeNode) {
 200                                 // phis aren't scheduled, so they need to be added explicitly
 201                                 currentState.markAll(((AbstractMergeNode) node).phis());
 202                                 if (node instanceof LoopBeginNode) {
 203                                     // remember the state at the loop entry, it's restored at exits
 204                                     loopEntryStates.put((LoopBeginNode) node, currentState.copy());
 205                                 }
 206                             } else if (node instanceof ProxyNode) {
 207                                 assert false : "proxy nodes should not be in the schedule";
 208                             } else if (node instanceof LoopExitNode) {
 209                                 if (graph.hasValueProxies()) {
 210                                     for (ProxyNode proxy : ((LoopExitNode) node).proxies()) {
 211                                         for (Node input : proxy.inputs()) {
 212                                             if (input != proxy.proxyPoint()) {
 213                                                 assert currentState.isMarked(input) : input + " not available at " + proxy + " in block " + block + "\n" + list;
 214                                             }
 215                                         }
 216                                     }
 217 
 218                                     // loop contents are only accessible via proxies at the exit
 219                                     currentState.clearAll();
 220                                     currentState.markAll(loopEntryStates.get(((LoopExitNode) node).loopBegin()));
 221                                 }
 222                                 // Loop proxies aren't scheduled, so they need to be added
 223                                 // explicitly
 224                                 currentState.markAll(((LoopExitNode) node).proxies());
 225                             } else {
 226                                 for (Node input : node.inputs()) {
 227                                     if (input != stateAfter) {
 228                                         if (input instanceof FrameState) {
 229                                             ((FrameState) input).applyToNonVirtual(new VirtualState.NodeClosure<Node>() {
 230                                                 @Override
 231                                                 public void apply(Node usage, Node nonVirtual) {
 232                                                     assert currentState.isMarked(nonVirtual) : nonVirtual + " not available at " + node + " in block " + block + "\n" + list;
 233                                                 }
 234                                             });
 235                                         } else {
 236                                             assert currentState.isMarked(input) || input instanceof VirtualObjectNode || input instanceof ConstantNode : input + " not available at " + node +
 237                                                             " in block " + block + "\n" + list;
 238                                         }
 239                                     }
 240                                 }
 241                             }
 242                             if (node instanceof AbstractEndNode) {
 243                                 AbstractMergeNode merge = ((AbstractEndNode) node).merge();
 244                                 for (PhiNode phi : merge.phis()) {
 245                                     ValueNode phiValue = phi.valueAt((AbstractEndNode) node);
 246                                     assert phiValue == null || currentState.isMarked(phiValue) || phiValue instanceof ConstantNode : phiValue + " not available at phi " + phi + " / end " + node +
 247                                                     " in block " + block;
 248                                 }
 249                             }
 250                             if (stateAfter != null) {
 251                                 assert pendingStateAfter == null;
 252                                 pendingStateAfter = stateAfter;
 253                             }
 254                             currentState.mark(node);
 255                         }
 256                     }
 257                     if (pendingStateAfter != null) {
 258                         pendingStateAfter.applyToNonVirtual(new NodeClosure<Node>() {
 259                             @Override
 260                             public void apply(Node usage, Node nonVirtualNode) {
 261                                 assert currentState.isMarked(nonVirtualNode) || nonVirtualNode instanceof VirtualObjectNode || nonVirtualNode instanceof ConstantNode : nonVirtualNode +
 262                                                 " not available at virtualstate " + usage + " at end of block " + block + " \n" + list;
 263                             }
 264                         });
 265                     }
 266                     return currentState;
 267                 }
 268 
 269                 @Override
 270                 protected NodeBitMap merge(Block merge, List<NodeBitMap> states) {
 271                     NodeBitMap result = states.get(0);
 272                     for (int i = 1; i < states.size(); i++) {
 273                         result.intersect(states.get(i));
 274                     }
 275                     return result;
 276                 }
 277 
 278                 @Override
 279                 protected NodeBitMap getInitialState() {
 280                     NodeBitMap ret = graph.createNodeBitMap();
 281                     ret.markAll(graph.getNodes().filter(ConstantNode.class));
 282                     return ret;
 283                 }
 284 
 285                 @Override
 286                 protected NodeBitMap cloneState(NodeBitMap oldState) {
 287                     return oldState.copy();
 288                 }
 289             };
 290 
 291             ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock());
 292 
 293         } catch (Throwable t) {
 294             graph.getDebug().handle(t);
 295         }
 296         return true;
 297     }
 298 }