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