Avoid critical edge for loop-exits.

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

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 part of ssa;
 
 /**
  * A special element for the extra parameter taken by intercepted
  * methods. We need to implement [TypedElement.type] because our
  * optimizers may look at its declared type.
@@ skipping 2379 matching lines @@
         jumpHandler.labels());
     previousBlock.addSuccessor(loopEntry);
     open(loopEntry);
 
     localsHandler.beginLoopHeader(loopEntry);
     return jumpHandler;
   }
 
   /**
    * 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);
 
     // Start generating code for the exit block.
     open(loopExitBlock);
 
     // 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.
         breakHandlers.add(savedLocals);
       }
       localsHandler = savedLocals.mergeMultiple(breakHandlers, loopExitBlock);
     } else {
       localsHandler = savedLocals;
     }
   }
@@ skipping 39 matching lines @@
           new SubExpression(initializerBlock, current);
     }
 
     loopNesting++;
     JumpHandler jumpHandler = beginLoopHeader(loop);
     HLoopInformation loopInfo = current.loopInformation;
     HBasicBlock conditionBlock = current;
     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
     // condition fails.
     LocalsHandler savedLocals = new LocalsHandler.from(localsHandler);
 
     // The body.
     HBasicBlock beginBodyBlock = addNewBlock();
-    conditionExitBlock.addSuccessor(beginBodyBlock);
+    conditionEndBlock.addSuccessor(beginBodyBlock);
     open(beginBodyBlock);
 
     localsHandler.enterLoopBody(loop);
     body();
 
     SubGraph bodyGraph = new SubGraph(beginBodyBlock, lastOpenedBlock);
     HBasicBlock bodyBlock = current;
     if (current != null) close(new HGoto());
 
     SubExpression updateGraph;
@@ skipping 44 matching lines @@
 
       localsHandler.enterLoopUpdates(loop);
 
       update();
 
       HBasicBlock updateEndBlock = close(new HGoto());
       // The back-edge completing the cycle.
       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();
       HLoopBlockInformation info =
           new HLoopBlockInformation(
               HLoopBlockInformation.loopType(loop),
               wrapExpressionGraph(initializerGraph),
               wrapExpressionGraph(conditionExpression),
               wrapStatementGraph(bodyGraph),
               wrapExpressionGraph(updateGraph),
@@ skipping 21 matching lines @@
       // Pass the elseBlock as the branchBlock, because that's the block we go
       // to just before leaving the 'loop'.
       endLoop(conditionBlock, elseBlock, jumpHandler, savedLocals);
 
       SubGraph elseGraph = new SubGraph(elseBlock, elseBlock);
       // Remove the loop information attached to the header.
       conditionBlock.loopInformation = null;
 
       // 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.
       if (jumpHandler.hasAnyBreak()) {
         TargetElement target = elements[loop];
         LabelElement label = target.addLabel(null, 'loop');
         label.setBreakTarget();
         SubGraph labelGraph = new SubGraph(conditionBlock, current);
         HLabeledBlockInformation labelInfo = new HLabeledBlockInformation(
                 new HSubGraphBlockInformation(labelGraph),
@@ skipping 139 matching lines @@
 
       HBasicBlock avoidCriticalEdge = addNewBlock();
       conditionEndBlock.addSuccessor(avoidCriticalEdge);
       open(avoidCriticalEdge);
       close(new HGoto());
       avoidCriticalEdge.addSuccessor(loopEntryBlock); // The back-edge.
 
       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);
       HLoopBlockInformation loopBlockInfo =
           new HLoopBlockInformation(
               HLoopBlockInformation.DO_WHILE_LOOP,
               null,
               wrapExpressionGraph(conditionExpression),
               wrapStatementGraph(bodyGraph),
               null,
@@ skipping 3567 matching lines @@
     DartType unaliased = type.unalias(builder.compiler);
     if (unaliased is TypedefType) throw 'unable to unalias $type';
     unaliased.accept(this, builder);
   }
 
   void visitDynamicType(DynamicType type, SsaBuilder builder) {
     ClassElement cls = builder.compiler.findHelper('DynamicRuntimeType');
     builder.push(new HDynamicType(type, new TypeMask.exact(cls)));
   }
 }