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