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();
158 iterB = iterB.getDominator();
159 }
160 return iterA;
161 }
162
163 @Override
164 public Block[] getBlocks() {
165 return reversePostOrder;
166 }
167
168 @Override
169 public Block getStartBlock() {
170 return reversePostOrder[0];
171 }
172
173 public Block[] reversePostOrder() {
174 return reversePostOrder;
175 }
176
177 public NodeMap<Block> getNodeToBlock() {
178 return nodeToBlock;
179 }
180
181 public Block blockFor(Node node) {
182 return nodeToBlock.get(node);
183 }
184
185 @Override
186 public List<Loop<Block>> getLoops() {
187 return loops;
188 }
189
190 private void identifyBlock(Block block) {
191 FixedWithNextNode cur = block.getBeginNode();
192 while (true) {
193 assert !cur.isDeleted();
194 assert nodeToBlock.get(cur) == null;
195 nodeToBlock.set(cur, block);
196 FixedNode next = cur.next();
197 if (next instanceof AbstractBeginNode) {
198 block.endNode = cur;
199 return;
200 } else if (next instanceof FixedWithNextNode) {
201 cur = (FixedWithNextNode) next;
202 } else {
203 nodeToBlock.set(next, block);
204 block.endNode = next;
205 return;
206 }
207 }
208 }
209
210 /**
211 * Identify and connect blocks (including loop backward edges). Predecessors need to be in the
212 * order expected when iterating phi inputs.
213 */
214 private void identifyBlocks() {
215 // Find all block headers.
216 int numBlocks = 0;
217 for (AbstractBeginNode begin : graph.getNodes(AbstractBeginNode.TYPE)) {
218 Block block = new Block(begin);
219 identifyBlock(block);
220 numBlocks++;
221 }
222
223 // Compute reverse post order.
224 int count = 0;
225 NodeMap<Block> nodeMap = this.nodeToBlock;
226 Block[] stack = new Block[numBlocks];
227 int tos = 0;
228 Block startBlock = blockFor(graph.start());
229 stack[0] = startBlock;
230 startBlock.setPredecessors(Block.EMPTY_ARRAY);
231 do {
232 Block block = stack[tos];
233 int id = block.getId();
234 if (id == BLOCK_ID_INITIAL) {
235 // First time we see this block: push all successors.
236 FixedNode last = block.getEndNode();
237 if (last instanceof EndNode) {
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;
278 int forwardEndCount = mergeNode.forwardEndCount();
279 Block[] predecessors = new Block[forwardEndCount];
280 for (int i = 0; i < forwardEndCount; ++i) {
281 predecessors[i] = nodeMap.get(mergeNode.forwardEndAt(i));
282 }
283 block.setPredecessors(predecessors);
284 }
285
286 } else if (id == BLOCK_ID_VISITED) {
287 // Second time we see this block: All successors have been processed, so add block
288 // to result list. Can safely reuse the stack for this.
289 --tos;
290 count++;
291 int index = numBlocks - count;
292 stack[index] = block;
293 block.setId(index);
294 } else {
295 throw GraalError.shouldNotReachHere();
296 }
297 } while (tos >= 0);
298
299 // Compute reverse postorder and number blocks.
300 assert count == numBlocks : "all blocks must be reachable";
301 this.reversePostOrder = stack;
302 }
303
304 private static void computeLoopPredecessors(NodeMap<Block> nodeMap, Block block, LoopBeginNode loopBeginNode) {
305 int forwardEndCount = loopBeginNode.forwardEndCount();
306 LoopEndNode[] loopEnds = loopBeginNode.orderedLoopEnds();
307 Block[] predecessors = new Block[forwardEndCount + loopEnds.length];
308 for (int i = 0; i < forwardEndCount; ++i) {
309 predecessors[i] = nodeMap.get(loopBeginNode.forwardEndAt(i));
310 }
311 for (int i = 0; i < loopEnds.length; ++i) {
312 predecessors[i + forwardEndCount] = nodeMap.get(loopEnds[i]);
313 }
314 block.setPredecessors(predecessors);
315 }
316
317 private void computeProbabilities() {
318
319 for (Block block : reversePostOrder) {
320 Block[] predecessors = block.getPredecessors();
321
322 double probability;
323 if (predecessors.length == 0) {
324 probability = 1D;
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);
371 }
372
373 if (graph.getGuardsStage() != GuardsStage.AFTER_FSA) {
374 for (LoopExitNode exit : loopBegin.loopExits()) {
375 Block exitBlock = nodeToBlock.get(exit);
376 assert exitBlock.getPredecessorCount() == 1;
377 computeLoopBlocks(exitBlock.getFirstPredecessor(), loop, stack, true);
378 loop.getExits().add(exitBlock);
379 }
380
381 // The following loop can add new blocks to the end of the loop's block
382 // list.
383 int size = loop.getBlocks().size();
384 for (int i = 0; i < size; ++i) {
385 Block b = loop.getBlocks().get(i);
386 for (Block sux : b.getSuccessors()) {
387 if (sux.loop != loop) {
388 AbstractBeginNode begin = sux.getBeginNode();
389 if (!(begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == loopBegin)) {
390 Debug.log(Debug.VERBOSE_LOG_LEVEL, "Unexpected loop exit with %s, including whole branch in the loop", sux);
391 computeLoopBlocks(sux, loop, stack, false);
392 }
393 }
394 }
395 }
396 }
397 }
398 }
399 }
400
401 /*
402 * Compute the loop exit blocks after FSA.
403 */
404 if (graph.getGuardsStage() == GuardsStage.AFTER_FSA) {
405 for (Block b : reversePostOrder) {
406 if (b.getLoop() != null) {
407 for (Block succ : b.getSuccessors()) {
408 // if the loop of the succ is a different one (or none)
409 if (b.getLoop() != succ.getLoop()) {
410 // and the succ loop is not a child loop of the curr one
411 if (succ.getLoop() == null) {
412 // we might exit multiple loops if b.loops is not a loop at depth 0
413 Loop<Block> curr = b.getLoop();
414 while (curr != null) {
415 curr.getExits().add(succ);
416 curr = curr.getParent();
417 }
418 } else {
419 /*
420 * succ also has a loop, might be a child loop
421 *
422 * if it is a child loop we do not exit a loop. if it is a loop
423 * different than b.loop and not a child loop it must be a parent
424 * loop, thus we exit all loops between b.loop and succ.loop
425 *
426 * if we exit multiple loops immediately after each other the
427 * bytecode parser might generate loop exit nodes after another and
428 * the CFG will identify them as separate blocks, we just take the
429 * first one and exit all loops at this one
430 */
431 if (succ.getLoop().getParent() != b.getLoop()) {
432 assert succ.getLoop().getDepth() < b.getLoop().getDepth();
433 // b.loop must not be a transitive parent of succ.loop
434 assert !Loop.transitiveParentLoop(succ.getLoop(), b.getLoop());
435 Loop<Block> curr = b.getLoop();
436 while (curr != null && curr != succ.getLoop()) {
437 curr.getExits().add(succ);
438 curr = curr.getParent();
439 }
440 }
441 }
442 }
443 }
444 }
445 }
446 }
447
448 }
449
450 private static void computeLoopBlocks(Block start, Loop<Block> loop, Block[] stack, boolean usePred) {
451 if (start.loop != loop) {
452 start.loop = loop;
453 stack[0] = start;
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 }
520 return iterA;
521 }
522
523 public void setNodeToBlock(NodeMap<Block> nodeMap) {
524 this.nodeToBlock = nodeMap;
525 }
526 }