< prev index next >

src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.nodes/src/org/graalvm/compiler/nodes/cfg/ControlFlowGraph.java

Print this page
rev 52509 : [mq]: graal


  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 }
< prev index next >