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.List;
29 import java.util.Map;
30 import java.util.function.Predicate;
31
32 import org.graalvm.compiler.common.RetryableBailoutException;
33 import org.graalvm.compiler.core.common.cfg.Loop;
34 import org.graalvm.compiler.core.common.util.CompilationAlarm;
35 import org.graalvm.compiler.graph.Node;
36 import org.graalvm.compiler.nodes.AbstractEndNode;
37 import org.graalvm.compiler.nodes.AbstractMergeNode;
38 import org.graalvm.compiler.nodes.FixedNode;
39 import org.graalvm.compiler.nodes.LoopBeginNode;
40 import org.graalvm.compiler.nodes.cfg.Block;
41
42 public final class ReentrantBlockIterator {
43
44 public static class LoopInfo<StateT> {
45
46 public final List<StateT> endStates;
47 public final List<StateT> exitStates;
48
49 public LoopInfo(int endCount, int exitCount) {
50 endStates = new ArrayList<>(endCount);
51 exitStates = new ArrayList<>(exitCount);
52 }
53 }
54
55 public abstract static class BlockIteratorClosure<StateT> {
56
57 protected abstract StateT getInitialState();
58
59 protected abstract StateT processBlock(Block block, StateT currentState);
60
61 protected abstract StateT merge(Block merge, List<StateT> states);
62
63 protected abstract StateT cloneState(StateT oldState);
64
65 protected abstract List<StateT> processLoop(Loop<Block> loop, StateT initialState);
66 }
67
68 private ReentrantBlockIterator() {
69 // no instances allowed
70 }
71
72 public static <StateT> LoopInfo<StateT> processLoop(BlockIteratorClosure<StateT> closure, Loop<Block> loop, StateT initialState) {
73 Map<FixedNode, StateT> blockEndStates = apply(closure, loop.getHeader(), initialState, block -> !(block.getLoop() == loop || block.isLoopHeader()));
74
75 Block[] predecessors = loop.getHeader().getPredecessors();
76 LoopInfo<StateT> info = new LoopInfo<>(predecessors.length - 1, loop.getExits().size());
77 for (int i = 1; i < predecessors.length; i++) {
78 StateT endState = blockEndStates.get(predecessors[i].getEndNode());
79 // make sure all end states are unique objects
80 info.endStates.add(closure.cloneState(endState));
81 }
82 for (Block loopExit : loop.getExits()) {
83 assert loopExit.getPredecessorCount() == 1;
84 assert blockEndStates.containsKey(loopExit.getBeginNode()) : loopExit.getBeginNode() + " " + blockEndStates;
85 StateT exitState = blockEndStates.get(loopExit.getBeginNode());
86 // make sure all exit states are unique objects
87 info.exitStates.add(closure.cloneState(exitState));
88 }
89 return info;
90 }
91
92 public static <StateT> void apply(BlockIteratorClosure<StateT> closure, Block start) {
93 apply(closure, start, closure.getInitialState(), null);
94 }
95
96 public static <StateT> Map<FixedNode, StateT> apply(BlockIteratorClosure<StateT> closure, Block start, StateT initialState, Predicate<Block> stopAtBlock) {
97 Deque<Block> blockQueue = new ArrayDeque<>();
98 /*
99 * States are stored on EndNodes before merges, and on BeginNodes after ControlSplitNodes.
100 */
101 Map<FixedNode, StateT> states = Node.newIdentityMap();
102
103 StateT state = initialState;
104 Block current = start;
105
106 while (true) {
107 if (CompilationAlarm.hasExpired()) {
108 throw new RetryableBailoutException("Compilation exceeded %d seconds during CFG traversal", CompilationAlarm.Options.CompilationExpirationPeriod.getValue());
109 }
110 Block next = null;
111 if (stopAtBlock != null && stopAtBlock.test(current)) {
112 states.put(current.getBeginNode(), state);
113 } else {
114 state = closure.processBlock(current, state);
115
116 Block[] successors = current.getSuccessors();
117 if (successors.length == 0) {
118 // nothing to do...
119 } else if (successors.length == 1) {
120 Block successor = successors[0];
121 if (successor.isLoopHeader()) {
122 if (current.isLoopEnd()) {
123 // nothing to do... loop ends only lead to loop begins we've already
124 // visited
125 states.put(current.getEndNode(), state);
126 } else {
127 recurseIntoLoop(closure, blockQueue, states, state, successor);
128 }
129 } else if (current.getEndNode() instanceof AbstractEndNode) {
130 AbstractEndNode end = (AbstractEndNode) current.getEndNode();
131
132 // add the end node and see if the merge is ready for processing
133 AbstractMergeNode merge = end.merge();
134 if (allEndsVisited(states, current, merge)) {
135 ArrayList<StateT> mergedStates = mergeStates(states, state, current, successor, merge);
136 state = closure.merge(successor, mergedStates);
137 next = successor;
138 } else {
139 assert !states.containsKey(end);
140 states.put(end, state);
141 }
142 } else {
143 next = successor;
144 }
145 } else {
146 next = processMultipleSuccessors(closure, blockQueue, states, state, successors);
147 }
148 }
149
150 // get next queued block
151 if (next != null) {
152 current = next;
153 } else if (blockQueue.isEmpty()) {
154 return states;
155 } else {
156 current = blockQueue.removeFirst();
157 assert current.getPredecessorCount() == 1;
158 assert states.containsKey(current.getBeginNode());
159 state = states.remove(current.getBeginNode());
160 }
161 }
162 }
163
164 private static <StateT> boolean allEndsVisited(Map<FixedNode, StateT> states, Block current, AbstractMergeNode merge) {
165 for (AbstractEndNode forwardEnd : merge.forwardEnds()) {
166 if (forwardEnd != current.getEndNode() && !states.containsKey(forwardEnd)) {
167 return false;
168 }
169 }
170 return true;
171 }
172
173 private static <StateT> Block processMultipleSuccessors(BlockIteratorClosure<StateT> closure, Deque<Block> blockQueue, Map<FixedNode, StateT> states, StateT state, Block[] successors) {
174 assert successors.length > 1;
175 for (int i = 1; i < successors.length; i++) {
176 Block successor = successors[i];
177 blockQueue.addFirst(successor);
178 states.put(successor.getBeginNode(), closure.cloneState(state));
179 }
180 return successors[0];
181 }
182
183 private static <StateT> ArrayList<StateT> mergeStates(Map<FixedNode, StateT> states, StateT state, Block current, Block successor, AbstractMergeNode merge) {
184 ArrayList<StateT> mergedStates = new ArrayList<>(merge.forwardEndCount());
185 for (Block predecessor : successor.getPredecessors()) {
186 assert predecessor == current || states.containsKey(predecessor.getEndNode());
187 StateT endState = predecessor == current ? state : states.remove(predecessor.getEndNode());
188 mergedStates.add(endState);
189 }
190 return mergedStates;
191 }
192
193 private static <StateT> void recurseIntoLoop(BlockIteratorClosure<StateT> closure, Deque<Block> blockQueue, Map<FixedNode, StateT> states, StateT state, Block successor) {
194 // recurse into the loop
195 Loop<Block> loop = successor.getLoop();
196 LoopBeginNode loopBegin = (LoopBeginNode) loop.getHeader().getBeginNode();
197 assert successor.getBeginNode() == loopBegin;
198
199 List<StateT> exitStates = closure.processLoop(loop, state);
200
201 int i = 0;
202 assert loop.getExits().size() == exitStates.size();
203 for (Block exit : loop.getExits()) {
204 states.put(exit.getBeginNode(), exitStates.get(i++));
205 blockQueue.addFirst(exit);
206 }
207 }
208 }