Avoid critical edge for loop-exits.

sdk/lib/_internal/compiler/implementation/ssa/builder.dart

Index: sdk/lib/_internal/compiler/implementation/ssa/builder.dart
diff --git a/sdk/lib/_internal/compiler/implementation/ssa/builder.dart b/sdk/lib/_internal/compiler/implementation/ssa/builder.dart
index 3d0d55f77904bf55a88f8f82d76d7b7a1ad2fc4c..895e42ad24400c76cecea4d707c8186e59824e74 100644
--- a/sdk/lib/_internal/compiler/implementation/ssa/builder.dart
+++ b/sdk/lib/_internal/compiler/implementation/ssa/builder.dart
@@ -2397,34 +2397,36 @@ class SsaBuilder extends ResolvedVisitor {
 
   /**
    * Ends the loop:
-   * - creates a new block and adds it as successor to the [branchBlock] and
+   * - creates a new block and adds it as successor to the [branchExitBlock] and
    *   any blocks that end in break.
    * - opens the new block (setting as [current]).
    * - notifies the locals handler that we're exiting a loop.
    * [savedLocals] are the locals from the end of the loop condition.
-   * [branchBlock] is the exit (branching) block of the condition.  For the
-   * while and for loops this is at the top of the loop.  For do-while it is
-   * the end of the body.  It is null for degenerate do-while loops that have
+   * [branchExitBlock] is the exit (branching) block of the condition. Generally
+   * this is not the top of the loop, since this would lead to critical edges.
+   * It is null for degenerate do-while loops that have
    * no back edge because they abort (throw/return/break in the body and have
    * no continues).
    */
   void endLoop(HBasicBlock loopEntry,
-               HBasicBlock branchBlock,
+               HBasicBlock branchExitBlock,
                JumpHandler jumpHandler,
                LocalsHandler savedLocals) {
     HBasicBlock loopExitBlock = addNewBlock();
+
     List<LocalsHandler> breakHandlers = <LocalsHandler>[];
     // Collect data for the successors and the phis at each break.
     jumpHandler.forEachBreak((HBreak breakInstruction, LocalsHandler locals) {
       breakInstruction.block.addSuccessor(loopExitBlock);
       breakHandlers.add(locals);
     });
+
     // The exit block is a successor of the loop condition if it is reached.
     // We don't add the successor in the case of a while/for loop that aborts
     // because the caller of endLoop will be wiring up a special empty else
     // block instead.
-    if (branchBlock != null) {
-      branchBlock.addSuccessor(loopExitBlock);
+    if (branchExitBlock != null) {
+      branchExitBlock.addSuccessor(loopExitBlock);
     }
     // Update the phis at the loop entry with the current values of locals.
     localsHandler.endLoop(loopEntry);
@@ -2434,7 +2436,7 @@ class SsaBuilder extends ResolvedVisitor {
 
     // Create a new localsHandler for the loopExitBlock with the correct phis.
     if (!breakHandlers.isEmpty) {
-      if (branchBlock != null) {
+      if (branchExitBlock != null) {
         // Add the values of the locals at the end of the condition block to
         // the phis.  These are the values that flow to the exit if the
         // condition fails.
@@ -2494,10 +2496,10 @@ class SsaBuilder extends ResolvedVisitor {
     if (startBlock == null) startBlock = conditionBlock;
 
     HInstruction conditionInstruction = condition();
-    HBasicBlock conditionExitBlock =
+    HBasicBlock conditionEndBlock =
         close(new HLoopBranch(conditionInstruction));
     SubExpression conditionExpression =
-        new SubExpression(conditionBlock, conditionExitBlock);
+        new SubExpression(conditionBlock, conditionEndBlock);
 
     // Save the values of the local variables at the end of the condition
     // block.  These are the values that will flow to the loop exit if the
@@ -2506,7 +2508,7 @@ class SsaBuilder extends ResolvedVisitor {
 
     // The body.
     HBasicBlock beginBodyBlock = addNewBlock();
-    conditionExitBlock.addSuccessor(beginBodyBlock);
+    conditionEndBlock.addSuccessor(beginBodyBlock);
     open(beginBodyBlock);
 
     localsHandler.enterLoopBody(loop);
@@ -2571,6 +2573,12 @@ class SsaBuilder extends ResolvedVisitor {
       updateEndBlock.addSuccessor(conditionBlock);
       updateGraph = new SubExpression(updateBlock, updateEndBlock);
 
+      // Avoid a critical edge from the condition to the loop-exit body.

[ngeoffray, 2014/06/24 12:39:13]

Unconditionally? Isn't it when there can be multiple break/return blocks? Can we
detect that beforehand?

[floitsch, 2014/06/24 14:44:38]

Yes. We could try to avoid them (and I started this way), but then we would need
to special case in the codegen too.
I don't expect an empty basic-block to have a huge impact.

+      HBasicBlock conditionExitBlock = addNewBlock();
+      open(conditionExitBlock);
+      close(new HGoto());
+      conditionEndBlock.addSuccessor(conditionExitBlock);
+
       endLoop(conditionBlock, conditionExitBlock, jumpHandler, savedLocals);
 
       conditionBlock.postProcessLoopHeader();
@@ -2612,19 +2620,19 @@ class SsaBuilder extends ResolvedVisitor {
 
       // Remove the [HLoopBranch] instruction and replace it with
       // [HIf].
-      HInstruction condition = conditionExitBlock.last.inputs[0];
-      conditionExitBlock.addAtExit(new HIf(condition));
-      conditionExitBlock.addSuccessor(elseBlock);
-      conditionExitBlock.remove(conditionExitBlock.last);
+      HInstruction condition = conditionEndBlock.last.inputs[0];
+      conditionEndBlock.addAtExit(new HIf(condition));
+      conditionEndBlock.addSuccessor(elseBlock);
+      conditionEndBlock.remove(conditionEndBlock.last);
       HIfBlockInformation info =
           new HIfBlockInformation(
               wrapExpressionGraph(conditionExpression),
               wrapStatementGraph(bodyGraph),
               wrapStatementGraph(elseGraph));
 
-      conditionExitBlock.setBlockFlow(info, current);
-      HIf ifBlock = conditionExitBlock.last;
-      ifBlock.blockInformation = conditionExitBlock.blockFlow;
+      conditionEndBlock.setBlockFlow(info, current);
+      HIf ifBlock = conditionEndBlock.last;
+      ifBlock.blockInformation = conditionEndBlock.blockFlow;
 
       // If the body has any break, attach a synthesized label to the
       // if block.
@@ -2784,7 +2792,13 @@ class SsaBuilder extends ResolvedVisitor {
       conditionExpression =
           new SubExpression(conditionBlock, conditionEndBlock);
 
-      endLoop(loopEntryBlock, conditionEndBlock, jumpHandler, localsHandler);
+      // Avoid a critical edge from the condition to the loop-exit body.

[ngeoffray, 2014/06/24 12:39:13]

ditto

[floitsch, 2014/06/24 14:44:38]

ditto.

+      HBasicBlock conditionExitBlock = addNewBlock();
+      open(conditionExitBlock);
+      close(new HGoto());
+      conditionEndBlock.addSuccessor(conditionExitBlock);
+
+      endLoop(loopEntryBlock, conditionExitBlock, jumpHandler, localsHandler);
 
       loopEntryBlock.postProcessLoopHeader();
       SubGraph bodyGraph = new SubGraph(loopEntryBlock, bodyExitBlock);