1 /*
2 * Copyright (c) 2011, 2016, 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.nodes.cfg;
24
25 import java.util.ArrayList;
26 import java.util.Arrays;
27 import java.util.Collections;
28 import java.util.List;
29
30 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
31 import org.graalvm.compiler.core.common.cfg.CFGVerifier;
32 import org.graalvm.compiler.core.common.cfg.Loop;
33 import org.graalvm.compiler.debug.Debug;
34 import org.graalvm.compiler.debug.GraalError;
35 import org.graalvm.compiler.graph.Node;
36 import org.graalvm.compiler.graph.NodeMap;
37 import org.graalvm.compiler.nodes.AbstractBeginNode;
38 import org.graalvm.compiler.nodes.AbstractEndNode;
39 import org.graalvm.compiler.nodes.ControlSplitNode;
40 import org.graalvm.compiler.nodes.EndNode;
41 import org.graalvm.compiler.nodes.FixedNode;
42 import org.graalvm.compiler.nodes.FixedWithNextNode;
43 import org.graalvm.compiler.nodes.IfNode;
44 import org.graalvm.compiler.nodes.LoopBeginNode;
45 import org.graalvm.compiler.nodes.LoopEndNode;
46 import org.graalvm.compiler.nodes.LoopExitNode;
47 import org.graalvm.compiler.nodes.MergeNode;
48 import org.graalvm.compiler.nodes.StructuredGraph;
49 import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
50
51 public final class ControlFlowGraph implements AbstractControlFlowGraph<Block> {
52 /**
53 * Don't allow probability values to be become too small or too high as this makes frequency
54 * calculations over- or underflow the range of a double. This commonly happens with infinite
55 * loops within infinite loops. The value is chosen a bit lower than half the maximum exponent
56 * supported by double. That way we can never overflow to infinity when multiplying two
57 * probability values.
58 */
59 public static final double MIN_PROBABILITY = 0x1.0p-500;
60 public static final double MAX_PROBABILITY = 1 / MIN_PROBABILITY;
61
62 public final StructuredGraph graph;
63
64 private NodeMap<Block> nodeToBlock;
65 private Block[] reversePostOrder;
66 private List<Loop<Block>> loops;
67
68 public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) {
69 ControlFlowGraph cfg = new ControlFlowGraph(graph);
70 cfg.identifyBlocks();
71 cfg.computeProbabilities();
72
73 if (computeLoops) {
74 cfg.computeLoopInformation();
75 }
76 if (computeDominators) {
77 cfg.computeDominators();
78 }
79 if (computePostdominators) {
80 cfg.computePostdominators();
81 }
82 // there's not much to verify when connectBlocks == false
83 assert !(connectBlocks || computeLoops || computeDominators || computePostdominators) || CFGVerifier.verify(cfg);
84 return cfg;
85 }
86
87 private ControlFlowGraph(StructuredGraph graph) {
88 this.graph = graph;
89 this.nodeToBlock = graph.createNodeMap();
90 }
91
92 private void computeDominators() {
93 assert reversePostOrder[0].getPredecessorCount() == 0 : "start block has no predecessor and therefore no dominator";
94 Block[] blocks = reversePostOrder;
95 for (int i = 1; i < blocks.length; i++) {
96 Block block = blocks[i];
97 assert block.getPredecessorCount() > 0;
98 Block dominator = null;
99 for (Block pred : block.getPredecessors()) {
100 if (!pred.isLoopEnd()) {
101 dominator = ((dominator == null) ? pred : commonDominatorRaw(dominator, pred));
102 }
103 }
104 // set dominator
105 block.setDominator(dominator);
106 if (dominator.getDominated().equals(Collections.emptyList())) {
107 dominator.setDominated(new ArrayList<>());
108 }
109 dominator.getDominated().add(block);
110 }
111 calcDominatorRanges(getStartBlock(), reversePostOrder.length);
112 }
113
114 private static void calcDominatorRanges(Block block, int size) {
115 Block[] stack = new Block[size];
116 stack[0] = block;
117 int tos = 0;
118 int myNumber = 0;
119
120 do {
121 Block cur = stack[tos];
122 List<Block> dominated = cur.getDominated();
123
124 if (cur.getDominatorNumber() == -1) {
125 cur.setDominatorNumber(myNumber);
126 if (dominated.size() > 0) {
127 // Push children onto stack.
128 for (Block b : dominated) {
129 stack[++tos] = b;
130 }
131 } else {
132 cur.setMaxChildDomNumber(myNumber);
133 --tos;
134 }
135 ++myNumber;
136 } else {
137 cur.setMaxChildDomNumber(dominated.get(0).getMaxChildDominatorNumber());
138 --tos;
139 }
140 } while (tos >= 0);
141 }
142
143 private static Block commonDominatorRaw(Block a, Block b) {
144 int aDomDepth = a.getDominatorDepth();
145 int bDomDepth = b.getDominatorDepth();
146 if (aDomDepth > bDomDepth) {
147 return commonDominatorRawSameDepth(a.getDominator(aDomDepth - bDomDepth), b);
148 } else {
149 return commonDominatorRawSameDepth(a, b.getDominator(bDomDepth - aDomDepth));
150 }
151 }
152
153 private static Block commonDominatorRawSameDepth(Block a, Block b) {
154 Block iterA = a;
155 Block iterB = b;
156 while (iterA != iterB) {
157 iterA = iterA.getDominator();
238 EndNode endNode = (EndNode) last;
239 Block suxBlock = nodeMap.get(endNode.merge());
240 if (suxBlock.getId() == BLOCK_ID_INITIAL) {
241 stack[++tos] = suxBlock;
242 }
243 block.setSuccessors(new Block[]{suxBlock});
244 } else if (last instanceof IfNode) {
245 IfNode ifNode = (IfNode) last;
246 Block trueSucc = nodeMap.get(ifNode.trueSuccessor());
247 stack[++tos] = trueSucc;
248 Block falseSucc = nodeMap.get(ifNode.falseSuccessor());
249 stack[++tos] = falseSucc;
250 block.setSuccessors(new Block[]{trueSucc, falseSucc});
251 Block[] ifPred = new Block[]{block};
252 trueSucc.setPredecessors(ifPred);
253 falseSucc.setPredecessors(ifPred);
254 } else if (last instanceof LoopEndNode) {
255 LoopEndNode loopEndNode = (LoopEndNode) last;
256 block.setSuccessors(new Block[]{nodeMap.get(loopEndNode.loopBegin())});
257 // Nothing to do push onto the stack.
258 } else {
259 assert !(last instanceof AbstractEndNode) : "Algorithm only supports EndNode and LoopEndNode.";
260 int startTos = tos;
261 Block[] ifPred = new Block[]{block};
262 for (Node suxNode : last.successors()) {
263 Block sux = nodeMap.get(suxNode);
264 stack[++tos] = sux;
265 sux.setPredecessors(ifPred);
266 }
267 int suxCount = tos - startTos;
268 Block[] successors = new Block[suxCount];
269 System.arraycopy(stack, startTos + 1, successors, 0, suxCount);
270 block.setSuccessors(successors);
271 }
272 block.setId(BLOCK_ID_VISITED);
273 AbstractBeginNode beginNode = block.getBeginNode();
274 if (beginNode instanceof LoopBeginNode) {
275 computeLoopPredecessors(nodeMap, block, (LoopBeginNode) beginNode);
276 } else if (beginNode instanceof MergeNode) {
277 MergeNode mergeNode = (MergeNode) beginNode;
325 } else if (predecessors.length == 1) {
326 Block pred = predecessors[0];
327 probability = pred.probability;
328 if (pred.getSuccessorCount() > 1) {
329 assert pred.getEndNode() instanceof ControlSplitNode;
330 ControlSplitNode controlSplit = (ControlSplitNode) pred.getEndNode();
331 probability *= controlSplit.probability(block.getBeginNode());
332 }
333 } else {
334 probability = predecessors[0].probability;
335 for (int i = 1; i < predecessors.length; ++i) {
336 probability += predecessors[i].probability;
337 }
338
339 if (block.getBeginNode() instanceof LoopBeginNode) {
340 LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode();
341 probability *= loopBegin.loopFrequency();
342 }
343 }
344 if (probability < MIN_PROBABILITY) {
345 block.setProbability(MIN_PROBABILITY);
346 } else if (probability > MAX_PROBABILITY) {
347 block.setProbability(MAX_PROBABILITY);
348 } else {
349 block.setProbability(probability);
350 }
351 }
352
353 }
354
355 private void computeLoopInformation() {
356 loops = new ArrayList<>();
357 if (graph.hasLoops()) {
358 Block[] stack = new Block[this.reversePostOrder.length];
359 for (Block block : reversePostOrder) {
360 AbstractBeginNode beginNode = block.getBeginNode();
361 if (beginNode instanceof LoopBeginNode) {
362 Loop<Block> loop = new HIRLoop(block.getLoop(), loops.size(), block);
363 loops.add(loop);
364 block.loop = loop;
365 loop.getBlocks().add(block);
366
367 LoopBeginNode loopBegin = (LoopBeginNode) beginNode;
368 for (LoopEndNode end : loopBegin.loopEnds()) {
369 Block endBlock = nodeToBlock.get(end);
370 computeLoopBlocks(endBlock, loop, stack, true);
454 loop.getBlocks().add(start);
455 int tos = 0;
456 do {
457 Block block = stack[tos--];
458
459 // Add predecessors or successors to the loop.
460 for (Block b : (usePred ? block.getPredecessors() : block.getSuccessors())) {
461 if (b.loop != loop) {
462 stack[++tos] = b;
463 b.loop = loop;
464 loop.getBlocks().add(b);
465 }
466 }
467 } while (tos >= 0);
468 }
469 }
470
471 public void computePostdominators() {
472
473 Block[] reversePostOrderTmp = this.reversePostOrder;
474
475 outer: for (int j = reversePostOrderTmp.length - 1; j >= 0; --j) {
476 Block block = reversePostOrderTmp[j];
477 if (block.isLoopEnd()) {
478 // We do not want the loop header registered as the postdominator of the loop end.
479 continue;
480 }
481 if (block.getSuccessorCount() == 0) {
482 // No successors => no postdominator.
483 continue;
484 }
485 Block firstSucc = block.getSuccessors()[0];
486 if (block.getSuccessorCount() == 1) {
487 block.postdominator = firstSucc;
488 continue;
489 }
490 Block postdominator = firstSucc;
491 for (Block sux : block.getSuccessors()) {
492 postdominator = commonPostdominator(postdominator, sux);
493 if (postdominator == null) {
494 // There is a dead end => no postdominator available.
495 continue outer;
496 }
497 }
498 assert !Arrays.asList(block.getSuccessors()).contains(postdominator) : "Block " + block + " has a wrong post dominator: " + postdominator;
499 block.postdominator = postdominator;
500 }
501 }
502
503 private static Block commonPostdominator(Block a, Block b) {
504 Block iterA = a;
505 Block iterB = b;
506 while (iterA != iterB) {
507 if (iterA.getId() < iterB.getId()) {
508 iterA = iterA.getPostdominator();
509 if (iterA == null) {
510 return null;
511 }
512 } else {
513 assert iterB.getId() < iterA.getId();
514 iterB = iterB.getPostdominator();
515 if (iterB == null) {
516 return null;
517 }
518 }
519 }
|
1 /*
2 * Copyright (c) 2011, 2017, 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.nodes.cfg;
24
25 import java.util.ArrayList;
26 import java.util.Arrays;
27 import java.util.BitSet;
28 import java.util.List;
29
30 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
31 import org.graalvm.compiler.core.common.cfg.CFGVerifier;
32 import org.graalvm.compiler.core.common.cfg.Loop;
33 import org.graalvm.compiler.debug.Debug;
34 import org.graalvm.compiler.debug.GraalError;
35 import org.graalvm.compiler.graph.Node;
36 import org.graalvm.compiler.graph.NodeMap;
37 import org.graalvm.compiler.nodes.AbstractBeginNode;
38 import org.graalvm.compiler.nodes.AbstractEndNode;
39 import org.graalvm.compiler.nodes.ControlSinkNode;
40 import org.graalvm.compiler.nodes.ControlSplitNode;
41 import org.graalvm.compiler.nodes.EndNode;
42 import org.graalvm.compiler.nodes.FixedNode;
43 import org.graalvm.compiler.nodes.FixedWithNextNode;
44 import org.graalvm.compiler.nodes.IfNode;
45 import org.graalvm.compiler.nodes.LoopBeginNode;
46 import org.graalvm.compiler.nodes.LoopEndNode;
47 import org.graalvm.compiler.nodes.LoopExitNode;
48 import org.graalvm.compiler.nodes.MergeNode;
49 import org.graalvm.compiler.nodes.StructuredGraph;
50 import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
51
52 public final class ControlFlowGraph implements AbstractControlFlowGraph<Block> {
53 /**
54 * Don't allow probability values to be become too small or too high as this makes frequency
55 * calculations over- or underflow the range of a double. This commonly happens with infinite
56 * loops within infinite loops. The value is chosen a bit lower than half the maximum exponent
57 * supported by double. That way we can never overflow to infinity when multiplying two
58 * probability values.
59 */
60 public static final double MIN_PROBABILITY = 0x1.0p-500;
61 public static final double MAX_PROBABILITY = 1 / MIN_PROBABILITY;
62
63 public final StructuredGraph graph;
64
65 private NodeMap<Block> nodeToBlock;
66 private Block[] reversePostOrder;
67 private List<Loop<Block>> loops;
68 private int maxDominatorDepth;
69
70 public interface RecursiveVisitor<V> {
71 V enter(Block b);
72
73 void exit(Block b, V value);
74 }
75
76 public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) {
77 ControlFlowGraph cfg = new ControlFlowGraph(graph);
78 cfg.identifyBlocks();
79 cfg.computeProbabilities();
80
81 if (computeLoops) {
82 cfg.computeLoopInformation();
83 }
84 if (computeDominators) {
85 cfg.computeDominators();
86 }
87 if (computePostdominators) {
88 cfg.computePostdominators();
89 }
90
91 // there's not much to verify when connectBlocks == false
92 assert !(connectBlocks || computeLoops || computeDominators || computePostdominators) || CFGVerifier.verify(cfg);
93 return cfg;
94 }
95
96 public String dominatorTreeString() {
97 return dominatorTreeString(getStartBlock());
98 }
99
100 private static String dominatorTreeString(Block b) {
101 StringBuilder sb = new StringBuilder();
102 sb.append(b);
103 sb.append("(");
104 Block firstDominated = b.getFirstDominated();
105 while (firstDominated != null) {
106 if (firstDominated.getDominator().getPostdominator() == firstDominated) {
107 sb.append("!");
108 }
109 sb.append(dominatorTreeString(firstDominated));
110 firstDominated = firstDominated.getDominatedSibling();
111 }
112 sb.append(") ");
113 return sb.toString();
114 }
115
116 @SuppressWarnings("unchecked")
117 public <V> void visitDominatorTreeDefault(RecursiveVisitor<V> visitor) {
118
119 Block[] stack = new Block[maxDominatorDepth + 1];
120 Block current = getStartBlock();
121 int tos = 0;
122 Object[] values = null;
123 int valuesTOS = 0;
124
125 while (tos >= 0) {
126 Block state = stack[tos];
127 if (state == null || state.getDominator() == null || state.getDominator().getPostdominator() != state) {
128 if (state == null) {
129 // We enter this block for the first time.
130 V value = visitor.enter(current);
131 if (value != null || values != null) {
132 if (values == null) {
133 values = new Object[maxDominatorDepth + 1];
134 }
135 values[valuesTOS++] = value;
136 }
137
138 Block dominated = skipPostDom(current.getFirstDominated());
139 if (dominated != null) {
140 // Descend into dominated.
141 stack[tos] = dominated;
142 current = dominated;
143 stack[++tos] = null;
144 continue;
145 }
146 } else {
147 Block next = skipPostDom(state.getDominatedSibling());
148 if (next != null) {
149 // Descend into dominated.
150 stack[tos] = next;
151 current = next;
152 stack[++tos] = null;
153 continue;
154 }
155 }
156
157 // Finished processing all normal dominators.
158 Block postDom = current.getPostdominator();
159 if (postDom != null && postDom.getDominator() == current) {
160 // Descend into post dominator.
161 stack[tos] = postDom;
162 current = postDom;
163 stack[++tos] = null;
164 continue;
165 }
166 }
167
168 // Finished processing this node, exit and pop from stack.
169 V value = null;
170 if (values != null && valuesTOS > 0) {
171 value = (V) values[--valuesTOS];
172 }
173 visitor.exit(current, value);
174 current = current.getDominator();
175 --tos;
176 }
177 }
178
179 private static Block skipPostDom(Block block) {
180 if (block != null && block.getDominator().getPostdominator() == block) {
181 // This is an always reached block.
182 return block.getDominatedSibling();
183 }
184 return block;
185 }
186
187 private static final class DeferredExit {
188
189 private DeferredExit(Block block, DeferredExit next) {
190 this.block = block;
191 this.next = next;
192 }
193
194 private final Block block;
195 private final DeferredExit next;
196 }
197
198 private static void addDeferredExit(DeferredExit[] deferredExits, Block b) {
199 Loop<Block> outermostExited = b.getDominator().getLoop();
200 Loop<Block> exitBlockLoop = b.getLoop();
201 assert outermostExited != null;
202 while (outermostExited.getParent() != null && outermostExited.getParent() != exitBlockLoop) {
203 outermostExited = outermostExited.getParent();
204 }
205 int loopIndex = outermostExited.getIndex();
206 deferredExits[loopIndex] = new DeferredExit(b, deferredExits[loopIndex]);
207 }
208
209 @SuppressWarnings({"unchecked"})
210 public <V> void visitDominatorTreeDeferLoopExits(RecursiveVisitor<V> visitor) {
211 Block[] stack = new Block[getBlocks().length];
212 int tos = 0;
213 BitSet visited = new BitSet(getBlocks().length);
214 int loopCount = getLoops().size();
215 DeferredExit[] deferredExits = new DeferredExit[loopCount];
216 Object[] values = null;
217 int valuesTOS = 0;
218 stack[0] = getStartBlock();
219
220 while (tos >= 0) {
221 Block cur = stack[tos];
222 int curId = cur.getId();
223 if (visited.get(curId)) {
224 V value = null;
225 if (values != null && valuesTOS > 0) {
226 value = (V) values[--valuesTOS];
227 }
228 visitor.exit(cur, value);
229 --tos;
230 if (cur.isLoopHeader()) {
231 int loopIndex = cur.getLoop().getIndex();
232 DeferredExit deferredExit = deferredExits[loopIndex];
233 if (deferredExit != null) {
234 while (deferredExit != null) {
235 stack[++tos] = deferredExit.block;
236 deferredExit = deferredExit.next;
237 }
238 deferredExits[loopIndex] = null;
239 }
240 }
241 } else {
242 visited.set(curId);
243 V value = visitor.enter(cur);
244 if (value != null || values != null) {
245 if (values == null) {
246 values = new Object[maxDominatorDepth + 1];
247 }
248 values[valuesTOS++] = value;
249 }
250
251 Block alwaysReached = cur.getPostdominator();
252 if (alwaysReached != null) {
253 if (alwaysReached.getDominator() != cur) {
254 alwaysReached = null;
255 } else if (isDominatorTreeLoopExit(alwaysReached)) {
256 addDeferredExit(deferredExits, alwaysReached);
257 } else {
258 stack[++tos] = alwaysReached;
259 }
260 }
261
262 Block b = cur.getFirstDominated();
263 while (b != null) {
264 if (b != alwaysReached) {
265 if (isDominatorTreeLoopExit(b)) {
266 addDeferredExit(deferredExits, b);
267 } else {
268 stack[++tos] = b;
269 }
270 }
271 b = b.getDominatedSibling();
272 }
273 }
274 }
275 }
276
277 public <V> void visitDominatorTree(RecursiveVisitor<V> visitor, boolean deferLoopExits) {
278 if (deferLoopExits && this.getLoops().size() > 0) {
279 visitDominatorTreeDeferLoopExits(visitor);
280 } else {
281 visitDominatorTreeDefault(visitor);
282 }
283 }
284
285 private static boolean isDominatorTreeLoopExit(Block b) {
286 Block dominator = b.getDominator();
287 return dominator != null && b.getLoop() != dominator.getLoop() && (!b.isLoopHeader() || dominator.getLoopDepth() >= b.getLoopDepth());
288 }
289
290 private ControlFlowGraph(StructuredGraph graph) {
291 this.graph = graph;
292 this.nodeToBlock = graph.createNodeMap();
293 }
294
295 private void computeDominators() {
296 assert reversePostOrder[0].getPredecessorCount() == 0 : "start block has no predecessor and therefore no dominator";
297 Block[] blocks = reversePostOrder;
298 int curMaxDominatorDepth = 0;
299 for (int i = 1; i < blocks.length; i++) {
300 Block block = blocks[i];
301 assert block.getPredecessorCount() > 0;
302 Block dominator = null;
303 for (Block pred : block.getPredecessors()) {
304 if (!pred.isLoopEnd()) {
305 dominator = ((dominator == null) ? pred : commonDominatorRaw(dominator, pred));
306 }
307 }
308
309 // Set dominator.
310 block.setDominator(dominator);
311
312 // Keep dominated linked list sorted by block ID such that predecessor blocks are always
313 // before successor blocks.
314 Block currentDominated = dominator.getFirstDominated();
315 if (currentDominated != null && currentDominated.getId() < block.getId()) {
316 while (currentDominated.getDominatedSibling() != null && currentDominated.getDominatedSibling().getId() < block.getId()) {
317 currentDominated = currentDominated.getDominatedSibling();
318 }
319 block.setDominatedSibling(currentDominated.getDominatedSibling());
320 currentDominated.setDominatedSibling(block);
321 } else {
322 block.setDominatedSibling(dominator.getFirstDominated());
323 dominator.setFirstDominated(block);
324 }
325
326 curMaxDominatorDepth = Math.max(curMaxDominatorDepth, block.getDominatorDepth());
327 }
328 this.maxDominatorDepth = curMaxDominatorDepth;
329 calcDominatorRanges(getStartBlock(), reversePostOrder.length);
330 }
331
332 private static void calcDominatorRanges(Block block, int size) {
333 Block[] stack = new Block[size];
334 stack[0] = block;
335 int tos = 0;
336 int myNumber = 0;
337
338 do {
339 Block cur = stack[tos];
340 Block dominated = cur.getFirstDominated();
341
342 if (cur.getDominatorNumber() == -1) {
343 cur.setDominatorNumber(myNumber);
344 if (dominated != null) {
345 // Push children onto stack.
346 do {
347 stack[++tos] = dominated;
348 dominated = dominated.getDominatedSibling();
349 } while (dominated != null);
350 } else {
351 cur.setMaxChildDomNumber(myNumber);
352 --tos;
353 }
354 ++myNumber;
355 } else {
356 cur.setMaxChildDomNumber(dominated.getMaxChildDominatorNumber());
357 --tos;
358 }
359 } while (tos >= 0);
360 }
361
362 private static Block commonDominatorRaw(Block a, Block b) {
363 int aDomDepth = a.getDominatorDepth();
364 int bDomDepth = b.getDominatorDepth();
365 if (aDomDepth > bDomDepth) {
366 return commonDominatorRawSameDepth(a.getDominator(aDomDepth - bDomDepth), b);
367 } else {
368 return commonDominatorRawSameDepth(a, b.getDominator(bDomDepth - aDomDepth));
369 }
370 }
371
372 private static Block commonDominatorRawSameDepth(Block a, Block b) {
373 Block iterA = a;
374 Block iterB = b;
375 while (iterA != iterB) {
376 iterA = iterA.getDominator();
457 EndNode endNode = (EndNode) last;
458 Block suxBlock = nodeMap.get(endNode.merge());
459 if (suxBlock.getId() == BLOCK_ID_INITIAL) {
460 stack[++tos] = suxBlock;
461 }
462 block.setSuccessors(new Block[]{suxBlock});
463 } else if (last instanceof IfNode) {
464 IfNode ifNode = (IfNode) last;
465 Block trueSucc = nodeMap.get(ifNode.trueSuccessor());
466 stack[++tos] = trueSucc;
467 Block falseSucc = nodeMap.get(ifNode.falseSuccessor());
468 stack[++tos] = falseSucc;
469 block.setSuccessors(new Block[]{trueSucc, falseSucc});
470 Block[] ifPred = new Block[]{block};
471 trueSucc.setPredecessors(ifPred);
472 falseSucc.setPredecessors(ifPred);
473 } else if (last instanceof LoopEndNode) {
474 LoopEndNode loopEndNode = (LoopEndNode) last;
475 block.setSuccessors(new Block[]{nodeMap.get(loopEndNode.loopBegin())});
476 // Nothing to do push onto the stack.
477 } else if (last instanceof ControlSinkNode) {
478 block.setSuccessors(Block.EMPTY_ARRAY);
479 } else {
480 assert !(last instanceof AbstractEndNode) : "Algorithm only supports EndNode and LoopEndNode.";
481 int startTos = tos;
482 Block[] ifPred = new Block[]{block};
483 for (Node suxNode : last.successors()) {
484 Block sux = nodeMap.get(suxNode);
485 stack[++tos] = sux;
486 sux.setPredecessors(ifPred);
487 }
488 int suxCount = tos - startTos;
489 Block[] successors = new Block[suxCount];
490 System.arraycopy(stack, startTos + 1, successors, 0, suxCount);
491 block.setSuccessors(successors);
492 }
493 block.setId(BLOCK_ID_VISITED);
494 AbstractBeginNode beginNode = block.getBeginNode();
495 if (beginNode instanceof LoopBeginNode) {
496 computeLoopPredecessors(nodeMap, block, (LoopBeginNode) beginNode);
497 } else if (beginNode instanceof MergeNode) {
498 MergeNode mergeNode = (MergeNode) beginNode;
546 } else if (predecessors.length == 1) {
547 Block pred = predecessors[0];
548 probability = pred.probability;
549 if (pred.getSuccessorCount() > 1) {
550 assert pred.getEndNode() instanceof ControlSplitNode;
551 ControlSplitNode controlSplit = (ControlSplitNode) pred.getEndNode();
552 probability *= controlSplit.probability(block.getBeginNode());
553 }
554 } else {
555 probability = predecessors[0].probability;
556 for (int i = 1; i < predecessors.length; ++i) {
557 probability += predecessors[i].probability;
558 }
559
560 if (block.getBeginNode() instanceof LoopBeginNode) {
561 LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode();
562 probability *= loopBegin.loopFrequency();
563 }
564 }
565 if (probability < MIN_PROBABILITY) {
566 probability = MIN_PROBABILITY;
567 } else if (probability > MAX_PROBABILITY) {
568 probability = MAX_PROBABILITY;
569 }
570 block.setProbability(probability);
571 }
572
573 }
574
575 private void computeLoopInformation() {
576 loops = new ArrayList<>();
577 if (graph.hasLoops()) {
578 Block[] stack = new Block[this.reversePostOrder.length];
579 for (Block block : reversePostOrder) {
580 AbstractBeginNode beginNode = block.getBeginNode();
581 if (beginNode instanceof LoopBeginNode) {
582 Loop<Block> loop = new HIRLoop(block.getLoop(), loops.size(), block);
583 loops.add(loop);
584 block.loop = loop;
585 loop.getBlocks().add(block);
586
587 LoopBeginNode loopBegin = (LoopBeginNode) beginNode;
588 for (LoopEndNode end : loopBegin.loopEnds()) {
589 Block endBlock = nodeToBlock.get(end);
590 computeLoopBlocks(endBlock, loop, stack, true);
674 loop.getBlocks().add(start);
675 int tos = 0;
676 do {
677 Block block = stack[tos--];
678
679 // Add predecessors or successors to the loop.
680 for (Block b : (usePred ? block.getPredecessors() : block.getSuccessors())) {
681 if (b.loop != loop) {
682 stack[++tos] = b;
683 b.loop = loop;
684 loop.getBlocks().add(b);
685 }
686 }
687 } while (tos >= 0);
688 }
689 }
690
691 public void computePostdominators() {
692
693 Block[] reversePostOrderTmp = this.reversePostOrder;
694 outer: for (int j = reversePostOrderTmp.length - 1; j >= 0; --j) {
695 Block block = reversePostOrderTmp[j];
696 if (block.isLoopEnd()) {
697 // We do not want the loop header registered as the postdominator of the loop end.
698 continue;
699 }
700 if (block.getSuccessorCount() == 0) {
701 // No successors => no postdominator.
702 continue;
703 }
704 Block firstSucc = block.getSuccessors()[0];
705 if (block.getSuccessorCount() == 1) {
706 block.postdominator = firstSucc;
707 continue;
708 }
709 Block postdominator = firstSucc;
710 for (Block sux : block.getSuccessors()) {
711 postdominator = commonPostdominator(postdominator, sux);
712 if (postdominator == null) {
713 // There is a dead end => no postdominator available.
714 continue outer;
715 }
716 }
717 assert !Arrays.asList(block.getSuccessors()).contains(postdominator) : "Block " + block + " has a wrong post dominator: " + postdominator;
718 block.setPostDominator(postdominator);
719 }
720 }
721
722 private static Block commonPostdominator(Block a, Block b) {
723 Block iterA = a;
724 Block iterB = b;
725 while (iterA != iterB) {
726 if (iterA.getId() < iterB.getId()) {
727 iterA = iterA.getPostdominator();
728 if (iterA == null) {
729 return null;
730 }
731 } else {
732 assert iterB.getId() < iterA.getId();
733 iterB = iterB.getPostdominator();
734 if (iterB == null) {
735 return null;
736 }
737 }
738 }
|