36 import org.graalvm.compiler.debug.GraalError;
37 import org.graalvm.compiler.graph.Node;
38 import org.graalvm.compiler.graph.NodeMap;
39 import org.graalvm.compiler.nodes.AbstractBeginNode;
40 import org.graalvm.compiler.nodes.AbstractEndNode;
41 import org.graalvm.compiler.nodes.ControlSinkNode;
42 import org.graalvm.compiler.nodes.ControlSplitNode;
43 import org.graalvm.compiler.nodes.EndNode;
44 import org.graalvm.compiler.nodes.FixedNode;
45 import org.graalvm.compiler.nodes.FixedWithNextNode;
46 import org.graalvm.compiler.nodes.IfNode;
47 import org.graalvm.compiler.nodes.LoopBeginNode;
48 import org.graalvm.compiler.nodes.LoopEndNode;
49 import org.graalvm.compiler.nodes.LoopExitNode;
50 import org.graalvm.compiler.nodes.MergeNode;
51 import org.graalvm.compiler.nodes.StructuredGraph;
52 import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
53
54 public final class ControlFlowGraph implements AbstractControlFlowGraph<Block> {
55 /**
56 * Don't allow probability values to be become too small or too high as this makes frequency
57 * calculations over- or underflow the range of a double. This commonly happens with infinite
58 * loops within infinite loops. The value is chosen a bit lower than half the maximum exponent
59 * supported by double. That way we can never overflow to infinity when multiplying two
60 * probability values.
61 */
62 public static final double MIN_PROBABILITY = 0x1.0p-500;
63 public static final double MAX_PROBABILITY = 1 / MIN_PROBABILITY;
64
65 public final StructuredGraph graph;
66
67 private NodeMap<Block> nodeToBlock;
68 private Block[] reversePostOrder;
69 private List<Loop<Block>> loops;
70 private int maxDominatorDepth;
71
72 public interface RecursiveVisitor<V> {
73 V enter(Block b);
74
75 void exit(Block b, V value);
76 }
77
78 public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) {
79 ControlFlowGraph cfg = new ControlFlowGraph(graph);
80 cfg.identifyBlocks();
81 cfg.computeProbabilities();
82
83 if (computeLoops) {
84 cfg.computeLoopInformation();
85 }
86 if (computeDominators) {
87 cfg.computeDominators();
88 }
89 if (computePostdominators) {
90 cfg.computePostdominators();
91 }
92
93 // there's not much to verify when connectBlocks == false
94 assert !(connectBlocks || computeLoops || computeDominators || computePostdominators) || CFGVerifier.verify(cfg);
95 return cfg;
96 }
97
98 public String dominatorTreeString() {
99 return dominatorTreeString(getStartBlock());
100 }
101
407 public NodeMap<Block> getNodeToBlock() {
408 return nodeToBlock;
409 }
410
411 public Block blockFor(Node node) {
412 return nodeToBlock.get(node);
413 }
414
415 @Override
416 public List<Loop<Block>> getLoops() {
417 return loops;
418 }
419
420 public int getMaxDominatorDepth() {
421 return maxDominatorDepth;
422 }
423
424 private void identifyBlock(Block block) {
425 FixedWithNextNode cur = block.getBeginNode();
426 while (true) {
427 assert !cur.isDeleted();
428 assert nodeToBlock.get(cur) == null;
429 nodeToBlock.set(cur, block);
430 FixedNode next = cur.next();
431 if (next instanceof AbstractBeginNode) {
432 block.endNode = cur;
433 return;
434 } else if (next instanceof FixedWithNextNode) {
435 cur = (FixedWithNextNode) next;
436 } else {
437 nodeToBlock.set(next, block);
438 block.endNode = next;
439 return;
440 }
441 }
442 }
443
444 /**
445 * Identify and connect blocks (including loop backward edges). Predecessors need to be in the
446 * order expected when iterating phi inputs.
447 */
533 } while (tos >= 0);
534
535 // Compute reverse postorder and number blocks.
536 assert count == numBlocks : "all blocks must be reachable";
537 this.reversePostOrder = stack;
538 }
539
540 private static void computeLoopPredecessors(NodeMap<Block> nodeMap, Block block, LoopBeginNode loopBeginNode) {
541 int forwardEndCount = loopBeginNode.forwardEndCount();
542 LoopEndNode[] loopEnds = loopBeginNode.orderedLoopEnds();
543 Block[] predecessors = new Block[forwardEndCount + loopEnds.length];
544 for (int i = 0; i < forwardEndCount; ++i) {
545 predecessors[i] = nodeMap.get(loopBeginNode.forwardEndAt(i));
546 }
547 for (int i = 0; i < loopEnds.length; ++i) {
548 predecessors[i + forwardEndCount] = nodeMap.get(loopEnds[i]);
549 }
550 block.setPredecessors(predecessors);
551 }
552
553 private void computeProbabilities() {
554
555 for (Block block : reversePostOrder) {
556 Block[] predecessors = block.getPredecessors();
557
558 double probability;
559 if (predecessors.length == 0) {
560 probability = 1D;
561 } else if (predecessors.length == 1) {
562 Block pred = predecessors[0];
563 probability = pred.probability;
564 if (pred.getSuccessorCount() > 1) {
565 assert pred.getEndNode() instanceof ControlSplitNode;
566 ControlSplitNode controlSplit = (ControlSplitNode) pred.getEndNode();
567 probability = multiplyProbabilities(probability, controlSplit.probability(block.getBeginNode()));
568 }
569 } else {
570 probability = predecessors[0].probability;
571 for (int i = 1; i < predecessors.length; ++i) {
572 probability += predecessors[i].probability;
573 }
574
575 if (block.getBeginNode() instanceof LoopBeginNode) {
576 LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode();
577 probability = multiplyProbabilities(probability, loopBegin.loopFrequency());
578 }
579 }
580 if (probability < MIN_PROBABILITY) {
581 probability = MIN_PROBABILITY;
582 } else if (probability > MAX_PROBABILITY) {
583 probability = MAX_PROBABILITY;
584 }
585 block.setProbability(probability);
586 }
587
588 }
589
590 private void computeLoopInformation() {
591 loops = new ArrayList<>();
592 if (graph.hasLoops()) {
593 Block[] stack = new Block[this.reversePostOrder.length];
594 for (Block block : reversePostOrder) {
595 AbstractBeginNode beginNode = block.getBeginNode();
596 if (beginNode instanceof LoopBeginNode) {
597 Loop<Block> parent = block.getLoop();
598 Loop<Block> loop = new HIRLoop(parent, loops.size(), block);
599 if (parent != null) {
600 parent.getChildren().add(loop);
601 }
602 loops.add(loop);
603 block.setLoop(loop);
604 loop.getBlocks().add(block);
605
746 iterA = iterA.getPostdominator();
747 if (iterA == null) {
748 return null;
749 }
750 } else {
751 assert iterB.getId() < iterA.getId();
752 iterB = iterB.getPostdominator();
753 if (iterB == null) {
754 return null;
755 }
756 }
757 }
758 return iterA;
759 }
760
761 public void setNodeToBlock(NodeMap<Block> nodeMap) {
762 this.nodeToBlock = nodeMap;
763 }
764
765 /**
766 * Multiplies a and b and clamps the between {@link ControlFlowGraph#MIN_PROBABILITY} and
767 * {@link ControlFlowGraph#MAX_PROBABILITY}.
768 */
769 public static double multiplyProbabilities(double a, double b) {
770 assert !Double.isNaN(a) && !Double.isNaN(b) && Double.isFinite(a) && Double.isFinite(b) : a + " " + b;
771 double r = a * b;
772 if (r > MAX_PROBABILITY) {
773 return MAX_PROBABILITY;
774 }
775 if (r < MIN_PROBABILITY) {
776 return MIN_PROBABILITY;
777 }
778 return r;
779 }
780 }
|
36 import org.graalvm.compiler.debug.GraalError;
37 import org.graalvm.compiler.graph.Node;
38 import org.graalvm.compiler.graph.NodeMap;
39 import org.graalvm.compiler.nodes.AbstractBeginNode;
40 import org.graalvm.compiler.nodes.AbstractEndNode;
41 import org.graalvm.compiler.nodes.ControlSinkNode;
42 import org.graalvm.compiler.nodes.ControlSplitNode;
43 import org.graalvm.compiler.nodes.EndNode;
44 import org.graalvm.compiler.nodes.FixedNode;
45 import org.graalvm.compiler.nodes.FixedWithNextNode;
46 import org.graalvm.compiler.nodes.IfNode;
47 import org.graalvm.compiler.nodes.LoopBeginNode;
48 import org.graalvm.compiler.nodes.LoopEndNode;
49 import org.graalvm.compiler.nodes.LoopExitNode;
50 import org.graalvm.compiler.nodes.MergeNode;
51 import org.graalvm.compiler.nodes.StructuredGraph;
52 import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
53
54 public final class ControlFlowGraph implements AbstractControlFlowGraph<Block> {
55 /**
56 * Don't allow relative frequency values to be become too small or too high as this makes
57 * frequency calculations over- or underflow the range of a double. This commonly happens with
58 * infinite loops within infinite loops. The value is chosen a bit lower than half the maximum
59 * exponent supported by double. That way we can never overflow to infinity when multiplying two
60 * relative frequency values.
61 */
62 public static final double MIN_RELATIVE_FREQUENCY = 0x1.0p-500;
63 public static final double MAX_RELATIVE_FREQUENCY = 1 / MIN_RELATIVE_FREQUENCY;
64
65 public final StructuredGraph graph;
66
67 private NodeMap<Block> nodeToBlock;
68 private Block[] reversePostOrder;
69 private List<Loop<Block>> loops;
70 private int maxDominatorDepth;
71
72 public interface RecursiveVisitor<V> {
73 V enter(Block b);
74
75 void exit(Block b, V value);
76 }
77
78 public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) {
79 ControlFlowGraph cfg = new ControlFlowGraph(graph);
80 cfg.identifyBlocks();
81 cfg.computeFrequencies();
82
83 if (computeLoops) {
84 cfg.computeLoopInformation();
85 }
86 if (computeDominators) {
87 cfg.computeDominators();
88 }
89 if (computePostdominators) {
90 cfg.computePostdominators();
91 }
92
93 // there's not much to verify when connectBlocks == false
94 assert !(connectBlocks || computeLoops || computeDominators || computePostdominators) || CFGVerifier.verify(cfg);
95 return cfg;
96 }
97
98 public String dominatorTreeString() {
99 return dominatorTreeString(getStartBlock());
100 }
101
407 public NodeMap<Block> getNodeToBlock() {
408 return nodeToBlock;
409 }
410
411 public Block blockFor(Node node) {
412 return nodeToBlock.get(node);
413 }
414
415 @Override
416 public List<Loop<Block>> getLoops() {
417 return loops;
418 }
419
420 public int getMaxDominatorDepth() {
421 return maxDominatorDepth;
422 }
423
424 private void identifyBlock(Block block) {
425 FixedWithNextNode cur = block.getBeginNode();
426 while (true) {
427 assert cur.isAlive() : cur;
428 assert nodeToBlock.get(cur) == null;
429 nodeToBlock.set(cur, block);
430 FixedNode next = cur.next();
431 if (next instanceof AbstractBeginNode) {
432 block.endNode = cur;
433 return;
434 } else if (next instanceof FixedWithNextNode) {
435 cur = (FixedWithNextNode) next;
436 } else {
437 nodeToBlock.set(next, block);
438 block.endNode = next;
439 return;
440 }
441 }
442 }
443
444 /**
445 * Identify and connect blocks (including loop backward edges). Predecessors need to be in the
446 * order expected when iterating phi inputs.
447 */
533 } while (tos >= 0);
534
535 // Compute reverse postorder and number blocks.
536 assert count == numBlocks : "all blocks must be reachable";
537 this.reversePostOrder = stack;
538 }
539
540 private static void computeLoopPredecessors(NodeMap<Block> nodeMap, Block block, LoopBeginNode loopBeginNode) {
541 int forwardEndCount = loopBeginNode.forwardEndCount();
542 LoopEndNode[] loopEnds = loopBeginNode.orderedLoopEnds();
543 Block[] predecessors = new Block[forwardEndCount + loopEnds.length];
544 for (int i = 0; i < forwardEndCount; ++i) {
545 predecessors[i] = nodeMap.get(loopBeginNode.forwardEndAt(i));
546 }
547 for (int i = 0; i < loopEnds.length; ++i) {
548 predecessors[i + forwardEndCount] = nodeMap.get(loopEnds[i]);
549 }
550 block.setPredecessors(predecessors);
551 }
552
553 /**
554 * Computes the frequencies of all blocks relative to the start block. It uses the probability
555 * information attached to control flow splits to calculate the frequency of a block based on
556 * the frequency of its predecessor and the probability of its incoming control flow branch.
557 */
558 private void computeFrequencies() {
559
560 for (Block block : reversePostOrder) {
561 Block[] predecessors = block.getPredecessors();
562
563 double relativeFrequency;
564 if (predecessors.length == 0) {
565 relativeFrequency = 1D;
566 } else if (predecessors.length == 1) {
567 Block pred = predecessors[0];
568 relativeFrequency = pred.relativeFrequency;
569 if (pred.getSuccessorCount() > 1) {
570 assert pred.getEndNode() instanceof ControlSplitNode;
571 ControlSplitNode controlSplit = (ControlSplitNode) pred.getEndNode();
572 relativeFrequency = multiplyRelativeFrequencies(relativeFrequency, controlSplit.probability(block.getBeginNode()));
573 }
574 } else {
575 relativeFrequency = predecessors[0].relativeFrequency;
576 for (int i = 1; i < predecessors.length; ++i) {
577 relativeFrequency += predecessors[i].relativeFrequency;
578 }
579
580 if (block.getBeginNode() instanceof LoopBeginNode) {
581 LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode();
582 relativeFrequency = multiplyRelativeFrequencies(relativeFrequency, loopBegin.loopFrequency());
583 }
584 }
585 if (relativeFrequency < MIN_RELATIVE_FREQUENCY) {
586 relativeFrequency = MIN_RELATIVE_FREQUENCY;
587 } else if (relativeFrequency > MAX_RELATIVE_FREQUENCY) {
588 relativeFrequency = MAX_RELATIVE_FREQUENCY;
589 }
590 block.setRelativeFrequency(relativeFrequency);
591 }
592
593 }
594
595 private void computeLoopInformation() {
596 loops = new ArrayList<>();
597 if (graph.hasLoops()) {
598 Block[] stack = new Block[this.reversePostOrder.length];
599 for (Block block : reversePostOrder) {
600 AbstractBeginNode beginNode = block.getBeginNode();
601 if (beginNode instanceof LoopBeginNode) {
602 Loop<Block> parent = block.getLoop();
603 Loop<Block> loop = new HIRLoop(parent, loops.size(), block);
604 if (parent != null) {
605 parent.getChildren().add(loop);
606 }
607 loops.add(loop);
608 block.setLoop(loop);
609 loop.getBlocks().add(block);
610
751 iterA = iterA.getPostdominator();
752 if (iterA == null) {
753 return null;
754 }
755 } else {
756 assert iterB.getId() < iterA.getId();
757 iterB = iterB.getPostdominator();
758 if (iterB == null) {
759 return null;
760 }
761 }
762 }
763 return iterA;
764 }
765
766 public void setNodeToBlock(NodeMap<Block> nodeMap) {
767 this.nodeToBlock = nodeMap;
768 }
769
770 /**
771 * Multiplies a and b and clamps the between {@link ControlFlowGraph#MIN_RELATIVE_FREQUENCY} and
772 * {@link ControlFlowGraph#MAX_RELATIVE_FREQUENCY}.
773 */
774 public static double multiplyRelativeFrequencies(double a, double b) {
775 assert !Double.isNaN(a) && !Double.isNaN(b) && Double.isFinite(a) && Double.isFinite(b) : a + " " + b;
776 double r = a * b;
777 if (r > MAX_RELATIVE_FREQUENCY) {
778 return MAX_RELATIVE_FREQUENCY;
779 }
780 if (r < MIN_RELATIVE_FREQUENCY) {
781 return MIN_RELATIVE_FREQUENCY;
782 }
783 return r;
784 }
785 }
|