001/*
002 * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.phases.graph;
024
025import java.util.*;
026
027import com.oracle.graal.graph.*;
028import com.oracle.graal.nodes.*;
029
030/**
031 * A SinglePassNodeIterator iterates the fixed nodes of the graph in post order starting from its
032 * start node. Unlike in iterative dataflow analysis, a single pass is performed, which allows
033 * keeping a smaller working set of pending {@link MergeableState}. This iteration scheme requires:
034 * <ul>
035 * <li>{@link MergeableState#merge(AbstractMergeNode, List)} to always return <code>true</code> (an
036 * assertion checks this)</li>
037 * <li>{@link #controlSplit(ControlSplitNode)} to always return all successors (otherwise, not all
038 * associated {@link EndNode} will be visited. In turn, visiting all the end nodes for a given
039 * {@link AbstractMergeNode} is a precondition before that merge node can be visited)</li>
040 * </ul>
041 *
042 * <p>
043 * For this iterator the CFG is defined by the classical CFG nodes (
044 * {@link com.oracle.graal.nodes.ControlSplitNode}, {@link com.oracle.graal.nodes.AbstractMergeNode}
045 * ...) and the {@link com.oracle.graal.nodes.FixedWithNextNode#next() next} pointers of
046 * {@link com.oracle.graal.nodes.FixedWithNextNode}.
047 * </p>
048 *
049 * <p>
050 * The lifecycle that single-pass node iterators go through is described in {@link #apply()}
051 * </p>
052 *
053 * @param <T> the type of {@link MergeableState} handled by this SinglePassNodeIterator
054 */
055public abstract class SinglePassNodeIterator<T extends MergeableState<T>> {
056
057    private final NodeBitMap visitedEnds;
058
059    /**
060     * @see SinglePassNodeIterator.PathStart
061     */
062    private final Deque<PathStart<T>> nodeQueue;
063
064    /**
065     * The keys in this map may be:
066     * <ul>
067     * <li>loop-begins and loop-ends, see {@link #finishLoopEnds(LoopEndNode)}</li>
068     * <li>forward-ends of merge-nodes, see {@link #queueMerge(EndNode)}</li>
069     * </ul>
070     *
071     * <p>
072     * It's tricky to answer whether the state an entry contains is the pre-state or the post-state
073     * for the key in question, because states are mutable. Thus an entry may be created to contain
074     * a pre-state (at the time, as done for a loop-begin in {@link #apply()}) only to make it a
075     * post-state soon after (continuing with the loop-begin example, also in {@link #apply()}). In
076     * any case, given that keys are limited to the nodes mentioned in the previous paragraph, in
077     * all cases an entry can be considered to hold a post-state by the time such entry is
078     * retrieved.
079     * </p>
080     *
081     * <p>
082     * The only method that makes this map grow is {@link #keepForLater(FixedNode, MergeableState)}
083     * and the only one that shrinks it is {@link #pruneEntry(FixedNode)}. To make sure no entry is
084     * left behind inadvertently, asserts in {@link #finished()} are in place.
085     * </p>
086     */
087    private final Map<FixedNode, T> nodeStates;
088
089    private final StartNode start;
090
091    protected T state;
092
093    /**
094     * An item queued in {@link #nodeQueue} can be used to continue with the single-pass visit after
095     * the previous path can't be followed anymore. Such items are:
096     * <ul>
097     * <li>de-queued via {@link #nextQueuedNode()}</li>
098     * <li>en-queued via {@link #queueMerge(EndNode)} and {@link #queueSuccessors(FixedNode)}</li>
099     * </ul>
100     *
101     * <p>
102     * Correspondingly each item may stand for:
103     * <ul>
104     * <li>a {@link AbstractMergeNode} whose pre-state results from merging those of its
105     * forward-ends, see {@link #nextQueuedNode()}</li>
106     * <li>a successor of a control-split node, in which case the state on entry to it (the
107     * successor) is also stored in the item, see {@link #nextQueuedNode()}</li>
108     * </ul>
109     * </p>
110     */
111    private static final class PathStart<U> {
112        private final AbstractBeginNode node;
113        private final U stateOnEntry;
114
115        private PathStart(AbstractBeginNode node, U stateOnEntry) {
116            this.node = node;
117            this.stateOnEntry = stateOnEntry;
118            assert repOK();
119        }
120
121        /**
122         * @return true iff this instance is internally consistent (ie, its "representation is OK")
123         */
124        private boolean repOK() {
125            if (node == null) {
126                return false;
127            }
128            if (node instanceof AbstractMergeNode) {
129                return stateOnEntry == null;
130            }
131            return (stateOnEntry != null);
132        }
133    }
134
135    public SinglePassNodeIterator(StartNode start, T initialState) {
136        StructuredGraph graph = start.graph();
137        visitedEnds = graph.createNodeBitMap();
138        nodeQueue = new ArrayDeque<>();
139        nodeStates = Node.newIdentityMap();
140        this.start = start;
141        this.state = initialState;
142    }
143
144    /**
145     * Performs a single-pass iteration.
146     *
147     * <p>
148     * After this method has been invoked, the {@link SinglePassNodeIterator} instance can't be used
149     * again. This saves clearing up fields in {@link #finished()}, the assumption being that this
150     * instance will be garbage-collected soon afterwards.
151     * </p>
152     */
153    public void apply() {
154        FixedNode current = start;
155
156        do {
157            if (current instanceof InvokeWithExceptionNode) {
158                invoke((Invoke) current);
159                queueSuccessors(current);
160                current = nextQueuedNode();
161            } else if (current instanceof LoopBeginNode) {
162                state.loopBegin((LoopBeginNode) current);
163                keepForLater(current, state);
164                state = state.clone();
165                loopBegin((LoopBeginNode) current);
166                current = ((LoopBeginNode) current).next();
167                assert current != null;
168            } else if (current instanceof LoopEndNode) {
169                loopEnd((LoopEndNode) current);
170                finishLoopEnds((LoopEndNode) current);
171                current = nextQueuedNode();
172            } else if (current instanceof AbstractMergeNode) {
173                merge((AbstractMergeNode) current);
174                current = ((AbstractMergeNode) current).next();
175                assert current != null;
176            } else if (current instanceof FixedWithNextNode) {
177                FixedNode next = ((FixedWithNextNode) current).next();
178                assert next != null : current;
179                node(current);
180                current = next;
181            } else if (current instanceof EndNode) {
182                end((EndNode) current);
183                queueMerge((EndNode) current);
184                current = nextQueuedNode();
185            } else if (current instanceof ControlSinkNode) {
186                node(current);
187                current = nextQueuedNode();
188            } else if (current instanceof ControlSplitNode) {
189                controlSplit((ControlSplitNode) current);
190                queueSuccessors(current);
191                current = nextQueuedNode();
192            } else {
193                assert false : current;
194            }
195        } while (current != null);
196        finished();
197    }
198
199    /**
200     * Two methods enqueue items in {@link #nodeQueue}. Of them, only this method enqueues items
201     * with non-null state (the other method being {@link #queueMerge(EndNode)}).
202     *
203     * <p>
204     * A space optimization is made: the state is cloned for all successors except the first. Given
205     * that right after invoking this method, {@link #nextQueuedNode()} is invoked, that single
206     * non-cloned state instance is in effect "handed over" to its next owner (thus realizing an
207     * owner-is-mutator access protocol).
208     * </p>
209     */
210    private void queueSuccessors(FixedNode x) {
211        Iterator<Node> iter = x.successors().nonNull().iterator();
212        if (iter.hasNext()) {
213            AbstractBeginNode begin = (AbstractBeginNode) iter.next();
214            // the current state isn't cloned for the first successor
215            // conceptually, the state is handed over to it
216            nodeQueue.addFirst(new PathStart<>(begin, state));
217        }
218        while (iter.hasNext()) {
219            AbstractBeginNode begin = (AbstractBeginNode) iter.next();
220            // for all other successors it is cloned
221            nodeQueue.addFirst(new PathStart<>(begin, state.clone()));
222        }
223    }
224
225    /**
226     * This method is invoked upon not having a (single) next {@link FixedNode} to visit. This
227     * method picks such next-node-to-visit from {@link #nodeQueue} and updates {@link #state} with
228     * the pre-state for that node.
229     *
230     * <p>
231     * Upon reaching a {@link AbstractMergeNode}, some entries are pruned from {@link #nodeStates}
232     * (ie, the entries associated to forward-ends for that merge-node).
233     * </p>
234     */
235    private FixedNode nextQueuedNode() {
236        if (nodeQueue.isEmpty()) {
237            return null;
238        }
239        PathStart<T> elem = nodeQueue.removeFirst();
240        if (elem.node instanceof AbstractMergeNode) {
241            AbstractMergeNode merge = (AbstractMergeNode) elem.node;
242            state = pruneEntry(merge.forwardEndAt(0));
243            ArrayList<T> states = new ArrayList<>(merge.forwardEndCount() - 1);
244            for (int i = 1; i < merge.forwardEndCount(); i++) {
245                T other = pruneEntry(merge.forwardEndAt(i));
246                states.add(other);
247            }
248            boolean ready = state.merge(merge, states);
249            assert ready : "Not a single-pass iterator after all";
250            return merge;
251        } else {
252            AbstractBeginNode begin = elem.node;
253            assert begin.predecessor() != null;
254            state = elem.stateOnEntry;
255            state.afterSplit(begin);
256            return begin;
257        }
258    }
259
260    /**
261     * Once all loop-end-nodes for a given loop-node have been visited.
262     * <ul>
263     * <li>the state for that loop-node is updated based on the states of the loop-end-nodes</li>
264     * <li>entries in {@link #nodeStates} are pruned for the loop (they aren't going to be looked up
265     * again, anyway)</li>
266     * </ul>
267     *
268     * <p>
269     * The entries removed by this method were inserted:
270     * <ul>
271     * <li>for the loop-begin, by {@link #apply()}</li>
272     * <li>for loop-ends, by (previous) invocations of this method</li>
273     * </ul>
274     * </p>
275     */
276    private void finishLoopEnds(LoopEndNode end) {
277        assert !visitedEnds.isMarked(end);
278        visitedEnds.mark(end);
279        keepForLater(end, state);
280        LoopBeginNode begin = end.loopBegin();
281        boolean endsVisited = true;
282        for (LoopEndNode le : begin.loopEnds()) {
283            if (!visitedEnds.isMarked(le)) {
284                endsVisited = false;
285                break;
286            }
287        }
288        if (endsVisited) {
289            ArrayList<T> states = new ArrayList<>(begin.loopEnds().count());
290            for (LoopEndNode le : begin.orderedLoopEnds()) {
291                T leState = pruneEntry(le);
292                states.add(leState);
293            }
294            T loopBeginState = pruneEntry(begin);
295            loopBeginState.loopEnds(begin, states);
296        }
297    }
298
299    /**
300     * Once all end-nodes for a given merge-node have been visited, that merge-node is added to the
301     * {@link #nodeQueue}
302     *
303     * <p>
304     * {@link #nextQueuedNode()} is in charge of pruning entries (held by {@link #nodeStates}) for
305     * the forward-ends inserted by this method.
306     * </p>
307     */
308    private void queueMerge(EndNode end) {
309        assert !visitedEnds.isMarked(end);
310        visitedEnds.mark(end);
311        keepForLater(end, state);
312        AbstractMergeNode merge = end.merge();
313        boolean endsVisited = true;
314        for (int i = 0; i < merge.forwardEndCount(); i++) {
315            if (!visitedEnds.isMarked(merge.forwardEndAt(i))) {
316                endsVisited = false;
317                break;
318            }
319        }
320        if (endsVisited) {
321            nodeQueue.add(new PathStart<>(merge, null));
322        }
323    }
324
325    protected abstract void node(FixedNode node);
326
327    protected void end(EndNode endNode) {
328        node(endNode);
329    }
330
331    protected void merge(AbstractMergeNode merge) {
332        node(merge);
333    }
334
335    protected void loopBegin(LoopBeginNode loopBegin) {
336        node(loopBegin);
337    }
338
339    protected void loopEnd(LoopEndNode loopEnd) {
340        node(loopEnd);
341    }
342
343    protected void controlSplit(ControlSplitNode controlSplit) {
344        node(controlSplit);
345    }
346
347    protected void invoke(Invoke invoke) {
348        node(invoke.asNode());
349    }
350
351    /**
352     * The lifecycle that single-pass node iterators go through is described in {@link #apply()}
353     *
354     * <p>
355     * When overriding this method don't forget to invoke this implementation, otherwise the
356     * assertions will be skipped.
357     * </p>
358     */
359    protected void finished() {
360        assert nodeQueue.isEmpty();
361        assert nodeStates.isEmpty();
362    }
363
364    private void keepForLater(FixedNode x, T s) {
365        assert !nodeStates.containsKey(x);
366        assert (x instanceof LoopBeginNode) || (x instanceof LoopEndNode) || (x instanceof EndNode);
367        assert s != null;
368        nodeStates.put(x, s);
369    }
370
371    private T pruneEntry(FixedNode x) {
372        T result = nodeStates.remove(x);
373        assert result != null;
374        return result;
375    }
376}