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.graph; 26 27 import java.util.ArrayDeque; 28 import java.util.ArrayList; 29 import java.util.Deque; 30 import java.util.List; 31 32 import jdk.internal.vm.compiler.collections.EconomicMap; 33 import jdk.internal.vm.compiler.collections.Equivalence; 34 import org.graalvm.compiler.graph.Node; 35 import org.graalvm.compiler.graph.NodeBitMap; 36 import org.graalvm.compiler.nodes.AbstractBeginNode; 37 import org.graalvm.compiler.nodes.AbstractMergeNode; 38 import org.graalvm.compiler.nodes.ControlSinkNode; 39 import org.graalvm.compiler.nodes.ControlSplitNode; 40 import org.graalvm.compiler.nodes.EndNode; 41 import org.graalvm.compiler.nodes.FixedNode; 42 import org.graalvm.compiler.nodes.FixedWithNextNode; 43 import org.graalvm.compiler.nodes.Invoke; 44 import org.graalvm.compiler.nodes.InvokeWithExceptionNode; 45 import org.graalvm.compiler.nodes.LoopBeginNode; 46 import org.graalvm.compiler.nodes.LoopEndNode; 47 import org.graalvm.compiler.nodes.StartNode; 48 import org.graalvm.compiler.nodes.StructuredGraph; 49 50 /** 51 * A SinglePassNodeIterator iterates the fixed nodes of the graph in post order starting from its 52 * start node. Unlike in iterative dataflow analysis, a single pass is performed, which allows 53 * keeping a smaller working set of pending {@link MergeableState}. This iteration scheme requires: 54 * <ul> 55 * <li>{@link MergeableState#merge(AbstractMergeNode, List)} to always return <code>true</code> (an 56 * assertion checks this)</li> 57 * <li>{@link #controlSplit(ControlSplitNode)} to always return all successors (otherwise, not all 58 * associated {@link EndNode} will be visited. In turn, visiting all the end nodes for a given 59 * {@link AbstractMergeNode} is a precondition before that merge node can be visited)</li> 60 * </ul> 61 * 62 * <p> 63 * For this iterator the CFG is defined by the classical CFG nodes ( 64 * {@link org.graalvm.compiler.nodes.ControlSplitNode}, 65 * {@link org.graalvm.compiler.nodes.AbstractMergeNode} ...) and the 66 * {@link org.graalvm.compiler.nodes.FixedWithNextNode#next() next} pointers of 67 * {@link org.graalvm.compiler.nodes.FixedWithNextNode}. 68 * </p> 69 * 70 * <p> 71 * The lifecycle that single-pass node iterators go through is described in {@link #apply()} 72 * </p> 73 * 74 * @param <T> the type of {@link MergeableState} handled by this SinglePassNodeIterator 75 */ 76 public abstract class SinglePassNodeIterator<T extends MergeableState<T>> { 77 78 private final NodeBitMap visitedEnds; 79 80 /** 81 * @see SinglePassNodeIterator.PathStart 82 */ 83 private final Deque<PathStart<T>> nodeQueue; 84 85 /** 86 * The keys in this map may be: 87 * <ul> 88 * <li>loop-begins and loop-ends, see {@link #finishLoopEnds(LoopEndNode)}</li> 89 * <li>forward-ends of merge-nodes, see {@link #queueMerge(EndNode)}</li> 90 * </ul> 91 * 92 * <p> 93 * It's tricky to answer whether the state an entry contains is the pre-state or the post-state 94 * for the key in question, because states are mutable. Thus an entry may be created to contain 95 * a pre-state (at the time, as done for a loop-begin in {@link #apply()}) only to make it a 96 * post-state soon after (continuing with the loop-begin example, also in {@link #apply()}). In 97 * any case, given that keys are limited to the nodes mentioned in the previous paragraph, in 98 * all cases an entry can be considered to hold a post-state by the time such entry is 99 * retrieved. 100 * </p> 101 * 102 * <p> 103 * The only method that makes this map grow is {@link #keepForLater(FixedNode, MergeableState)} 104 * and the only one that shrinks it is {@link #pruneEntry(FixedNode)}. To make sure no entry is 105 * left behind inadvertently, asserts in {@link #finished()} are in place. 106 * </p> 107 */ 108 private final EconomicMap<FixedNode, T> nodeStates; 109 110 private final StartNode start; 111 112 protected T state; 113 114 /** 115 * An item queued in {@link #nodeQueue} can be used to continue with the single-pass visit after 116 * the previous path can't be followed anymore. Such items are: 117 * <ul> 118 * <li>de-queued via {@link #nextQueuedNode()}</li> 119 * <li>en-queued via {@link #queueMerge(EndNode)} and {@link #queueSuccessors(FixedNode)}</li> 120 * </ul> 121 * 122 * <p> 123 * Correspondingly each item may stand for: 124 * <ul> 125 * <li>a {@link AbstractMergeNode} whose pre-state results from merging those of its 126 * forward-ends, see {@link #nextQueuedNode()}</li> 127 * <li>a successor of a control-split node, in which case the state on entry to it (the 128 * successor) is also stored in the item, see {@link #nextQueuedNode()}</li> 129 * </ul> 130 * </p> 131 */ 132 private static final class PathStart<U> { 133 private final AbstractBeginNode node; 134 private final U stateOnEntry; 135 PathStart(AbstractBeginNode node, U stateOnEntry)136 private PathStart(AbstractBeginNode node, U stateOnEntry) { 137 this.node = node; 138 this.stateOnEntry = stateOnEntry; 139 assert repOK(); 140 } 141 142 /** 143 * @return true iff this instance is internally consistent (ie, its "representation is OK") 144 */ repOK()145 private boolean repOK() { 146 if (node == null) { 147 return false; 148 } 149 if (node instanceof AbstractMergeNode) { 150 return stateOnEntry == null; 151 } 152 return (stateOnEntry != null); 153 } 154 } 155 SinglePassNodeIterator(StartNode start, T initialState)156 public SinglePassNodeIterator(StartNode start, T initialState) { 157 StructuredGraph graph = start.graph(); 158 visitedEnds = graph.createNodeBitMap(); 159 nodeQueue = new ArrayDeque<>(); 160 nodeStates = EconomicMap.create(Equivalence.IDENTITY); 161 this.start = start; 162 this.state = initialState; 163 } 164 165 /** 166 * Performs a single-pass iteration. 167 * 168 * <p> 169 * After this method has been invoked, the {@link SinglePassNodeIterator} instance can't be used 170 * again. This saves clearing up fields in {@link #finished()}, the assumption being that this 171 * instance will be garbage-collected soon afterwards. 172 * </p> 173 */ apply()174 public void apply() { 175 FixedNode current = start; 176 177 do { 178 if (current instanceof InvokeWithExceptionNode) { 179 invoke((Invoke) current); 180 queueSuccessors(current); 181 current = nextQueuedNode(); 182 } else if (current instanceof LoopBeginNode) { 183 state.loopBegin((LoopBeginNode) current); 184 keepForLater(current, state); 185 state = state.clone(); 186 loopBegin((LoopBeginNode) current); 187 current = ((LoopBeginNode) current).next(); 188 assert current != null; 189 } else if (current instanceof LoopEndNode) { 190 loopEnd((LoopEndNode) current); 191 finishLoopEnds((LoopEndNode) current); 192 current = nextQueuedNode(); 193 } else if (current instanceof AbstractMergeNode) { 194 merge((AbstractMergeNode) current); 195 current = ((AbstractMergeNode) current).next(); 196 assert current != null; 197 } else if (current instanceof FixedWithNextNode) { 198 FixedNode next = ((FixedWithNextNode) current).next(); 199 assert next != null : current; 200 node(current); 201 current = next; 202 } else if (current instanceof EndNode) { 203 end((EndNode) current); 204 queueMerge((EndNode) current); 205 current = nextQueuedNode(); 206 } else if (current instanceof ControlSinkNode) { 207 node(current); 208 current = nextQueuedNode(); 209 } else if (current instanceof ControlSplitNode) { 210 controlSplit((ControlSplitNode) current); 211 queueSuccessors(current); 212 current = nextQueuedNode(); 213 } else { 214 assert false : current; 215 } 216 } while (current != null); 217 finished(); 218 } 219 220 /** 221 * Two methods enqueue items in {@link #nodeQueue}. Of them, only this method enqueues items 222 * with non-null state (the other method being {@link #queueMerge(EndNode)}). 223 * 224 * <p> 225 * A space optimization is made: the state is cloned for all successors except the first. Given 226 * that right after invoking this method, {@link #nextQueuedNode()} is invoked, that single 227 * non-cloned state instance is in effect "handed over" to its next owner (thus realizing an 228 * owner-is-mutator access protocol). 229 * </p> 230 */ queueSuccessors(FixedNode x)231 private void queueSuccessors(FixedNode x) { 232 T startState = state; 233 T curState = startState; 234 for (Node succ : x.successors()) { 235 if (succ != null) { 236 if (curState == null) { 237 // the current state isn't cloned for the first successor 238 // conceptually, the state is handed over to it 239 curState = startState.clone(); 240 } 241 AbstractBeginNode begin = (AbstractBeginNode) succ; 242 nodeQueue.addFirst(new PathStart<>(begin, curState)); 243 } 244 } 245 } 246 247 /** 248 * This method is invoked upon not having a (single) next {@link FixedNode} to visit. This 249 * method picks such next-node-to-visit from {@link #nodeQueue} and updates {@link #state} with 250 * the pre-state for that node. 251 * 252 * <p> 253 * Upon reaching a {@link AbstractMergeNode}, some entries are pruned from {@link #nodeStates} 254 * (ie, the entries associated to forward-ends for that merge-node). 255 * </p> 256 */ nextQueuedNode()257 private FixedNode nextQueuedNode() { 258 if (nodeQueue.isEmpty()) { 259 return null; 260 } 261 PathStart<T> elem = nodeQueue.removeFirst(); 262 if (elem.node instanceof AbstractMergeNode) { 263 AbstractMergeNode merge = (AbstractMergeNode) elem.node; 264 state = pruneEntry(merge.forwardEndAt(0)); 265 ArrayList<T> states = new ArrayList<>(merge.forwardEndCount() - 1); 266 for (int i = 1; i < merge.forwardEndCount(); i++) { 267 T other = pruneEntry(merge.forwardEndAt(i)); 268 states.add(other); 269 } 270 boolean ready = state.merge(merge, states); 271 assert ready : "Not a single-pass iterator after all"; 272 return merge; 273 } else { 274 AbstractBeginNode begin = elem.node; 275 assert begin.predecessor() != null; 276 state = elem.stateOnEntry; 277 state.afterSplit(begin); 278 return begin; 279 } 280 } 281 282 /** 283 * Once all loop-end-nodes for a given loop-node have been visited. 284 * <ul> 285 * <li>the state for that loop-node is updated based on the states of the loop-end-nodes</li> 286 * <li>entries in {@link #nodeStates} are pruned for the loop (they aren't going to be looked up 287 * again, anyway)</li> 288 * </ul> 289 * 290 * <p> 291 * The entries removed by this method were inserted: 292 * <ul> 293 * <li>for the loop-begin, by {@link #apply()}</li> 294 * <li>for loop-ends, by (previous) invocations of this method</li> 295 * </ul> 296 * </p> 297 */ finishLoopEnds(LoopEndNode end)298 private void finishLoopEnds(LoopEndNode end) { 299 assert !visitedEnds.isMarked(end); 300 visitedEnds.mark(end); 301 keepForLater(end, state); 302 LoopBeginNode begin = end.loopBegin(); 303 boolean endsVisited = true; 304 for (LoopEndNode le : begin.loopEnds()) { 305 if (!visitedEnds.isMarked(le)) { 306 endsVisited = false; 307 break; 308 } 309 } 310 if (endsVisited) { 311 ArrayList<T> states = new ArrayList<>(begin.loopEnds().count()); 312 for (LoopEndNode le : begin.orderedLoopEnds()) { 313 T leState = pruneEntry(le); 314 states.add(leState); 315 } 316 T loopBeginState = pruneEntry(begin); 317 loopBeginState.loopEnds(begin, states); 318 } 319 } 320 321 /** 322 * Once all end-nodes for a given merge-node have been visited, that merge-node is added to the 323 * {@link #nodeQueue} 324 * 325 * <p> 326 * {@link #nextQueuedNode()} is in charge of pruning entries (held by {@link #nodeStates}) for 327 * the forward-ends inserted by this method. 328 * </p> 329 */ queueMerge(EndNode end)330 private void queueMerge(EndNode end) { 331 assert !visitedEnds.isMarked(end); 332 visitedEnds.mark(end); 333 keepForLater(end, state); 334 AbstractMergeNode merge = end.merge(); 335 boolean endsVisited = true; 336 for (int i = 0; i < merge.forwardEndCount(); i++) { 337 if (!visitedEnds.isMarked(merge.forwardEndAt(i))) { 338 endsVisited = false; 339 break; 340 } 341 } 342 if (endsVisited) { 343 nodeQueue.add(new PathStart<>(merge, null)); 344 } 345 } 346 node(FixedNode node)347 protected abstract void node(FixedNode node); 348 end(EndNode endNode)349 protected void end(EndNode endNode) { 350 node(endNode); 351 } 352 merge(AbstractMergeNode merge)353 protected void merge(AbstractMergeNode merge) { 354 node(merge); 355 } 356 loopBegin(LoopBeginNode loopBegin)357 protected void loopBegin(LoopBeginNode loopBegin) { 358 node(loopBegin); 359 } 360 loopEnd(LoopEndNode loopEnd)361 protected void loopEnd(LoopEndNode loopEnd) { 362 node(loopEnd); 363 } 364 controlSplit(ControlSplitNode controlSplit)365 protected void controlSplit(ControlSplitNode controlSplit) { 366 node(controlSplit); 367 } 368 invoke(Invoke invoke)369 protected void invoke(Invoke invoke) { 370 node(invoke.asNode()); 371 } 372 373 /** 374 * The lifecycle that single-pass node iterators go through is described in {@link #apply()} 375 * 376 * <p> 377 * When overriding this method don't forget to invoke this implementation, otherwise the 378 * assertions will be skipped. 379 * </p> 380 */ finished()381 protected void finished() { 382 assert nodeQueue.isEmpty(); 383 assert nodeStates.isEmpty(); 384 } 385 keepForLater(FixedNode x, T s)386 private void keepForLater(FixedNode x, T s) { 387 assert !nodeStates.containsKey(x); 388 assert (x instanceof LoopBeginNode) || (x instanceof LoopEndNode) || (x instanceof EndNode); 389 assert s != null; 390 nodeStates.put(x, s); 391 } 392 pruneEntry(FixedNode x)393 private T pruneEntry(FixedNode x) { 394 T result = nodeStates.removeKey(x); 395 assert result != null; 396 return result; 397 } 398 } 399