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