1 /*
2 * Copyright (c) 2013, 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.Deque;
27
28 import org.graalvm.compiler.graph.Node;
29 import org.graalvm.compiler.graph.NodeBitMap;
30 import org.graalvm.compiler.graph.iterators.NodeIterable;
31 import org.graalvm.compiler.nodes.AbstractEndNode;
32 import org.graalvm.compiler.nodes.AbstractMergeNode;
33 import org.graalvm.compiler.nodes.ControlSinkNode;
34 import org.graalvm.compiler.nodes.ControlSplitNode;
35 import org.graalvm.compiler.nodes.EndNode;
36 import org.graalvm.compiler.nodes.FixedNode;
37 import org.graalvm.compiler.nodes.FixedWithNextNode;
38 import org.graalvm.compiler.nodes.Invoke;
39 import org.graalvm.compiler.nodes.LoopBeginNode;
40 import org.graalvm.compiler.nodes.LoopEndNode;
41 import org.graalvm.compiler.nodes.LoopExitNode;
42 import org.graalvm.compiler.nodes.StructuredGraph;
43
44 public abstract class ScopedPostOrderNodeIterator {
45
46 private final Deque<FixedNode> nodeQueue;
47 private final NodeBitMap queuedNodes;
48 private final Deque<FixedNode> scopes;
49
50 protected FixedNode currentScopeStart;
51
52 public ScopedPostOrderNodeIterator(StructuredGraph graph) {
53 this.queuedNodes = graph.createNodeBitMap();
54 this.nodeQueue = new ArrayDeque<>();
55 this.scopes = getScopes(graph);
56 }
57
58 public void apply() {
59 while (!scopes.isEmpty()) {
60 queuedNodes.clearAll();
61 this.currentScopeStart = scopes.pop();
62 initializeScope();
63 processScope();
64 }
65 }
66
67 public void processScope() {
68 FixedNode current;
69 queue(currentScopeStart);
70
71 while ((current = nextQueuedNode()) != null) {
72 assert current.isAlive();
73
74 if (current instanceof Invoke) {
75 invoke((Invoke) current);
76 queueSuccessors(current);
77 } else if (current instanceof LoopBeginNode) {
78 queueLoopBeginSuccessors((LoopBeginNode) current);
79 } else if (current instanceof LoopExitNode) {
80 queueLoopExitSuccessors((LoopExitNode) current);
81 } else if (current instanceof LoopEndNode) {
82 // nothing todo
83 } else if (current instanceof AbstractMergeNode) {
84 queueSuccessors(current);
85 } else if (current instanceof FixedWithNextNode) {
86 queueSuccessors(current);
87 } else if (current instanceof EndNode) {
88 queueMerge((EndNode) current);
89 } else if (current instanceof ControlSinkNode) {
90 // nothing todo
91 } else if (current instanceof ControlSplitNode) {
92 queueSuccessors(current);
93 } else {
94 assert false : current;
95 }
96 }
97 }
98
99 protected void queueLoopBeginSuccessors(LoopBeginNode node) {
100 if (currentScopeStart == node) {
101 queue(node.next());
102 } else if (currentScopeStart instanceof LoopBeginNode) {
103 // so we are currently processing loop A and found another loop B
104 // -> queue all loop exits of B except those that also exit loop A
105 for (LoopExitNode loopExit : node.loopExits()) {
106 if (!((LoopBeginNode) currentScopeStart).loopExits().contains(loopExit)) {
107 queue(loopExit);
108 }
109 }
110 } else {
111 queue(node.loopExits());
112 }
113 }
114
115 protected void queueLoopExitSuccessors(LoopExitNode node) {
116 if (!(currentScopeStart instanceof LoopBeginNode) || !((LoopBeginNode) currentScopeStart).loopExits().contains(node)) {
117 queueSuccessors(node);
118 }
119 }
120
121 protected Deque<FixedNode> getScopes(StructuredGraph graph) {
122 Deque<FixedNode> result = new ArrayDeque<>();
123 result.push(graph.start());
124 for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) {
125 result.push(loopBegin);
126 }
127 return result;
128 }
129
130 private void queueSuccessors(FixedNode x) {
131 queue(x.successors());
132 }
133
134 private void queue(NodeIterable<? extends Node> iter) {
135 for (Node node : iter) {
136 queue(node);
137 }
138 }
139
140 private void queue(Node node) {
141 if (node != null && !queuedNodes.isMarked(node)) {
142 queuedNodes.mark(node);
143 nodeQueue.addFirst((FixedNode) node);
144 }
145 }
146
147 private FixedNode nextQueuedNode() {
148 if (nodeQueue.isEmpty()) {
149 return null;
150 }
151
152 FixedNode result = nodeQueue.removeFirst();
153 assert queuedNodes.isMarked(result);
154 return result;
155 }
156
157 private void queueMerge(AbstractEndNode end) {
158 AbstractMergeNode merge = end.merge();
159 if (!queuedNodes.isMarked(merge) && visitedAllEnds(merge)) {
160 queue(merge);
161 }
162 }
163
164 private boolean visitedAllEnds(AbstractMergeNode merge) {
165 for (int i = 0; i < merge.forwardEndCount(); i++) {
166 if (!queuedNodes.isMarked(merge.forwardEndAt(i))) {
167 return false;
168 }
169 }
170 return true;
171 }
172
173 protected abstract void initializeScope();
174
175 protected abstract void invoke(Invoke invoke);
176 }