1 /*
2 * Copyright (c) 2011, 2012, 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.Iterator;
29 import java.util.List;
30 import java.util.Map;
31
32 import org.graalvm.compiler.graph.Node;
33 import org.graalvm.compiler.nodes.AbstractBeginNode;
34 import org.graalvm.compiler.nodes.AbstractEndNode;
35 import org.graalvm.compiler.nodes.AbstractMergeNode;
36 import org.graalvm.compiler.nodes.EndNode;
37 import org.graalvm.compiler.nodes.FixedNode;
38 import org.graalvm.compiler.nodes.FixedWithNextNode;
39 import org.graalvm.compiler.nodes.LoopBeginNode;
40 import org.graalvm.compiler.nodes.LoopEndNode;
41 import org.graalvm.compiler.nodes.LoopExitNode;
42
43 public final class ReentrantNodeIterator {
44
45 public static class LoopInfo<StateT> {
46
47 public final Map<LoopEndNode, StateT> endStates;
48 public final Map<LoopExitNode, StateT> exitStates;
49
50 public LoopInfo(int endCount, int exitCount) {
51 endStates = Node.newIdentityMap(endCount);
52 exitStates = Node.newIdentityMap(exitCount);
53 }
54 }
55
56 public abstract static class NodeIteratorClosure<StateT> {
57
58 protected abstract StateT processNode(FixedNode node, StateT currentState);
59
60 protected abstract StateT merge(AbstractMergeNode merge, List<StateT> states);
61
62 protected abstract StateT afterSplit(AbstractBeginNode node, StateT oldState);
63
64 protected abstract Map<LoopExitNode, StateT> processLoop(LoopBeginNode loop, StateT initialState);
65
66 /**
67 * Determine whether iteration should continue in the current state.
68 *
69 * @param currentState
70 */
71 protected boolean continueIteration(StateT currentState) {
72 return true;
73 }
74 }
75
76 private ReentrantNodeIterator() {
77 // no instances allowed
78 }
79
80 public static <StateT> LoopInfo<StateT> processLoop(NodeIteratorClosure<StateT> closure, LoopBeginNode loop, StateT initialState) {
81 Map<FixedNode, StateT> blockEndStates = apply(closure, loop, initialState, loop);
82
83 LoopInfo<StateT> info = new LoopInfo<>(loop.loopEnds().count(), loop.loopExits().count());
84 for (LoopEndNode end : loop.loopEnds()) {
85 if (blockEndStates.containsKey(end)) {
86 info.endStates.put(end, blockEndStates.get(end));
87 }
88 }
89 for (LoopExitNode exit : loop.loopExits()) {
90 if (blockEndStates.containsKey(exit)) {
91 info.exitStates.put(exit, blockEndStates.get(exit));
92 }
93 }
94 return info;
95 }
96
97 public static <StateT> void apply(NodeIteratorClosure<StateT> closure, FixedNode start, StateT initialState) {
98 apply(closure, start, initialState, null);
99 }
100
101 private static <StateT> Map<FixedNode, StateT> apply(NodeIteratorClosure<StateT> closure, FixedNode start, StateT initialState, LoopBeginNode boundary) {
102 assert start != null;
103 Deque<AbstractBeginNode> nodeQueue = new ArrayDeque<>();
104 Map<FixedNode, StateT> blockEndStates = Node.newIdentityMap();
105
106 StateT state = initialState;
107 FixedNode current = start;
108 do {
109 while (current instanceof FixedWithNextNode) {
110 if (boundary != null && current instanceof LoopExitNode && ((LoopExitNode) current).loopBegin() == boundary) {
111 blockEndStates.put(current, state);
112 current = null;
113 } else {
114 FixedNode next = ((FixedWithNextNode) current).next();
115 state = closure.processNode(current, state);
116 current = closure.continueIteration(state) ? next : null;
117 }
118 }
119
120 if (current != null) {
121 state = closure.processNode(current, state);
122
123 if (closure.continueIteration(state)) {
124 Iterator<Node> successors = current.successors().iterator();
125 if (!successors.hasNext()) {
126 if (current instanceof LoopEndNode) {
127 blockEndStates.put(current, state);
128 } else if (current instanceof EndNode) {
129 // add the end node and see if the merge is ready for processing
130 AbstractMergeNode merge = ((EndNode) current).merge();
131 if (merge instanceof LoopBeginNode) {
132 Map<LoopExitNode, StateT> loopExitState = closure.processLoop((LoopBeginNode) merge, state);
133 for (Map.Entry<LoopExitNode, StateT> entry : loopExitState.entrySet()) {
134 blockEndStates.put(entry.getKey(), entry.getValue());
135 nodeQueue.add(entry.getKey());
136 }
137 } else {
138 boolean endsVisited = true;
139 for (AbstractEndNode forwardEnd : merge.forwardEnds()) {
140 if (forwardEnd != current && !blockEndStates.containsKey(forwardEnd)) {
141 endsVisited = false;
142 break;
143 }
144 }
145 if (endsVisited) {
146 ArrayList<StateT> states = new ArrayList<>(merge.forwardEndCount());
147 for (int i = 0; i < merge.forwardEndCount(); i++) {
148 AbstractEndNode forwardEnd = merge.forwardEndAt(i);
149 assert forwardEnd == current || blockEndStates.containsKey(forwardEnd);
150 StateT other = forwardEnd == current ? state : blockEndStates.remove(forwardEnd);
151 states.add(other);
152 }
153 state = closure.merge(merge, states);
154 current = closure.continueIteration(state) ? merge : null;
155 continue;
156 } else {
157 assert !blockEndStates.containsKey(current);
158 blockEndStates.put(current, state);
159 }
160 }
161 }
162 } else {
163 FixedNode firstSuccessor = (FixedNode) successors.next();
164 if (!successors.hasNext()) {
165 current = firstSuccessor;
166 continue;
167 } else {
168 do {
169 AbstractBeginNode successor = (AbstractBeginNode) successors.next();
170 StateT successorState = closure.afterSplit(successor, state);
171 if (closure.continueIteration(successorState)) {
172 blockEndStates.put(successor, successorState);
173 nodeQueue.add(successor);
174 }
175 } while (successors.hasNext());
176
177 state = closure.afterSplit((AbstractBeginNode) firstSuccessor, state);
178 current = closure.continueIteration(state) ? firstSuccessor : null;
179 continue;
180 }
181 }
182 }
183 }
184
185 // get next queued block
186 if (nodeQueue.isEmpty()) {
187 return blockEndStates;
188 } else {
189 current = nodeQueue.removeFirst();
190 assert blockEndStates.containsKey(current);
191 state = blockEndStates.remove(current);
192 assert !(current instanceof AbstractMergeNode) && current instanceof AbstractBeginNode;
193 }
194 } while (true);
195 }
196 }