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.Map;
29 import java.util.Set;
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.StructuredGraph;
45
46 /**
47 * A PostOrderNodeIterator iterates the fixed nodes of the graph in post order starting from a
48 * specified fixed node.
49 * <p>
50 * For this iterator the CFG is defined by the classical CFG nodes ({@link ControlSplitNode},
51 * {@link AbstractMergeNode}...) and the {@link FixedWithNextNode#next() next} pointers of
52 * {@link FixedWithNextNode}.
53 * <p>
54 * While iterating it maintains a user-defined state by calling the methods available in
55 * {@link MergeableState}.
56 *
57 * @param <T> the type of {@link MergeableState} handled by this PostOrderNodeIterator
58 */
59 public abstract class PostOrderNodeIterator<T extends MergeableState<T>> {
60
61 private final NodeBitMap visitedEnds;
62 private final Deque<AbstractBeginNode> nodeQueue;
63 private final Map<FixedNode, T> nodeStates;
64 private final FixedNode start;
65
66 protected T state;
67
68 public PostOrderNodeIterator(FixedNode start, T initialState) {
69 StructuredGraph graph = start.graph();
70 visitedEnds = graph.createNodeBitMap();
71 nodeQueue = new ArrayDeque<>();
72 nodeStates = Node.newIdentityMap();
73 this.start = start;
74 this.state = initialState;
75 }
76
77 public void apply() {
78 FixedNode current = start;
79
80 do {
81 if (current instanceof InvokeWithExceptionNode) {
82 invoke((Invoke) current);
83 queueSuccessors(current, null);
84 current = nextQueuedNode();
85 } else if (current instanceof LoopBeginNode) {
86 state.loopBegin((LoopBeginNode) current);
87 nodeStates.put(current, state);
88 state = state.clone();
89 loopBegin((LoopBeginNode) current);
90 current = ((LoopBeginNode) current).next();
91 assert current != null;
92 } else if (current instanceof LoopEndNode) {
93 loopEnd((LoopEndNode) current);
94 finishLoopEnds((LoopEndNode) current);
95 current = nextQueuedNode();
96 } else if (current instanceof AbstractMergeNode) {
97 merge((AbstractMergeNode) current);
98 current = ((AbstractMergeNode) current).next();
99 assert current != null;
100 } else if (current instanceof FixedWithNextNode) {
101 FixedNode next = ((FixedWithNextNode) current).next();
102 assert next != null : current;
103 node(current);
104 current = next;
105 } else if (current instanceof EndNode) {
106 end((EndNode) current);
107 queueMerge((EndNode) current);
108 current = nextQueuedNode();
109 } else if (current instanceof ControlSinkNode) {
110 node(current);
111 current = nextQueuedNode();
112 } else if (current instanceof ControlSplitNode) {
113 Set<Node> successors = controlSplit((ControlSplitNode) current);
114 queueSuccessors(current, successors);
115 current = nextQueuedNode();
116 } else {
117 assert false : current;
118 }
119 } while (current != null);
120 finished();
121 }
122
123 private void queueSuccessors(FixedNode x, Set<Node> successors) {
124 nodeStates.put(x, state);
125 if (successors != null) {
126 for (Node node : successors) {
127 if (node != null) {
128 nodeStates.put((FixedNode) node.predecessor(), state);
129 nodeQueue.addFirst((AbstractBeginNode) node);
130 }
131 }
132 } else {
133 for (Node node : x.successors()) {
134 if (node != null) {
135 nodeQueue.addFirst((AbstractBeginNode) node);
136 }
137 }
138 }
139 }
140
141 private FixedNode nextQueuedNode() {
142 int maxIterations = nodeQueue.size();
143 while (maxIterations-- > 0) {
144 AbstractBeginNode node = nodeQueue.removeFirst();
145 if (node instanceof AbstractMergeNode) {
146 AbstractMergeNode merge = (AbstractMergeNode) node;
147 state = nodeStates.get(merge.forwardEndAt(0)).clone();
148 ArrayList<T> states = new ArrayList<>(merge.forwardEndCount() - 1);
149 for (int i = 1; i < merge.forwardEndCount(); i++) {
150 T other = nodeStates.get(merge.forwardEndAt(i));
151 assert other != null;
152 states.add(other);
153 }
154 boolean ready = state.merge(merge, states);
155 if (ready) {
156 return merge;
157 } else {
158 nodeQueue.addLast(merge);
159 }
160 } else {
161 assert node.predecessor() != null;
162 state = nodeStates.get(node.predecessor()).clone();
163 state.afterSplit(node);
164 return node;
165 }
166 }
167 return null;
168 }
169
170 private void finishLoopEnds(LoopEndNode end) {
171 assert !visitedEnds.isMarked(end);
172 assert !nodeStates.containsKey(end);
173 nodeStates.put(end, state);
174 visitedEnds.mark(end);
175 LoopBeginNode begin = end.loopBegin();
176 boolean endsVisited = true;
177 for (LoopEndNode le : begin.loopEnds()) {
178 if (!visitedEnds.isMarked(le)) {
179 endsVisited = false;
180 break;
181 }
182 }
183 if (endsVisited) {
184 ArrayList<T> states = new ArrayList<>(begin.loopEnds().count());
185 for (LoopEndNode le : begin.orderedLoopEnds()) {
186 states.add(nodeStates.get(le));
187 }
188 T loopBeginState = nodeStates.get(begin);
189 if (loopBeginState != null) {
190 loopBeginState.loopEnds(begin, states);
191 }
192 }
193 }
194
195 private void queueMerge(EndNode end) {
196 assert !visitedEnds.isMarked(end);
197 assert !nodeStates.containsKey(end);
198 nodeStates.put(end, state);
199 visitedEnds.mark(end);
200 AbstractMergeNode merge = end.merge();
201 boolean endsVisited = true;
202 for (int i = 0; i < merge.forwardEndCount(); i++) {
203 if (!visitedEnds.isMarked(merge.forwardEndAt(i))) {
204 endsVisited = false;
205 break;
206 }
207 }
208 if (endsVisited) {
209 nodeQueue.add(merge);
210 }
211 }
212
213 protected abstract void node(FixedNode node);
214
215 protected void end(EndNode endNode) {
216 node(endNode);
217 }
218
219 protected void merge(AbstractMergeNode merge) {
220 node(merge);
221 }
222
223 protected void loopBegin(LoopBeginNode loopBegin) {
224 node(loopBegin);
225 }
226
227 protected void loopEnd(LoopEndNode loopEnd) {
228 node(loopEnd);
229 }
230
231 protected Set<Node> controlSplit(ControlSplitNode controlSplit) {
232 node(controlSplit);
233 return null;
234 }
235
236 protected void invoke(Invoke invoke) {
237 node(invoke.asNode());
238 }
239
240 protected void finished() {
241 // nothing to do
242 }
243 }