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