Avoid critical edge for loop-exits.

sdk/lib/_internal/compiler/implementation/ssa/codegen.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;
 
 class SsaCodeGeneratorTask extends CompilerTask {
 
   final JavaScriptBackend backend;
 
@@ skipping 737 matching lines @@
       currentBlockInformation = oldInfo;
     } else {
       generateStatements(info.body);
     }
   }
 
   bool visitLoopInfo(HLoopBlockInformation info) {
     HExpressionInformation condition = info.condition;
     bool isConditionExpression = isJSCondition(condition);
 
+    // Assert that the block we inserted to avoid critical edges satisfies
+    // basic assumptions.
+    assert(!condition.end.successors.last.isEmpty);
+    assert(condition.end.successors.last.first is HGoto);
+    assert(condition.end.successors.last.first.next == null);

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

Should that be in validator.dart instead?

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

Done.

+
     js.Loop loop;
 
     switch (info.kind) {
       // Treate all three "test-first" loops the same way.
       case HLoopBlockInformation.FOR_LOOP:
       case HLoopBlockInformation.WHILE_LOOP:
       case HLoopBlockInformation.FOR_IN_LOOP:
       case HLoopBlockInformation.SWITCH_CONTINUE_LOOP:
         HBlockInformation initialization = info.initializer;
         int initializationType = TYPE_STATEMENT;
         if (initialization != null) {
           initializationType = expressionType(initialization);
           if (initializationType == TYPE_STATEMENT) {
             generateStatements(initialization);
             initialization = null;
           }
         }
+
+        // We inserted a basic block to avoid critical edges. This block is
+        // part of the LoopBlockInformation and must therefore be handled here.
+        js.Block oldContainer = currentContainer;
+        js.Block avoidContainer = new js.Block.empty();
+        currentContainer = avoidContainer;
+        assignPhisOfSuccessors(condition.end.successors.last);
+        bool hasPhiUpdates = !avoidContainer.statements.isEmpty;
+        currentContainer = oldContainer;
+
         if (isConditionExpression &&
+            !hasPhiUpdates &&
             info.updates != null && isJSExpression(info.updates)) {
           // If we have an updates graph, and it's expressible as an
           // expression, generate a for-loop.
           js.Expression jsInitialization = null;
           if (initialization != null) {
             int delayedVariablesCount = collectedVariableDeclarations.length;
             jsInitialization = generateExpression(initialization);
             if (!shouldGroupVarDeclarations &&
                 delayedVariablesCount < collectedVariableDeclarations.length) {
               // We just added a new delayed variable-declaration. See if we can
@@ skipping 35 matching lines @@
                 jsInitialization = new js.VariableDeclarationList(inits);
               }
             }
           }
           js.Expression jsCondition = generateExpression(condition);
           js.Expression jsUpdates = generateExpression(info.updates);
           // The body might be labeled. Ignore this when recursing on the
           // subgraph.
           // TODO(lrn): Remove this extra labeling when handling all loops
           // using subgraphs.
-          js.Block oldContainer = currentContainer;
+          oldContainer = currentContainer;
           js.Statement body = new js.Block.empty();
           currentContainer = body;
           visitBodyIgnoreLabels(info);
           currentContainer = oldContainer;
           body = unwrapStatement(body);
           loop = new js.For(jsInitialization, jsCondition, jsUpdates, body);
         } else {
           // We have either no update graph, or it's too complex to
           // put in an expression.
           if (initialization != null) {
             generateStatements(initialization);
           }
           js.Expression jsCondition;
           js.Block oldContainer = currentContainer;
           js.Statement body = new js.Block.empty();
-          if (isConditionExpression) {
+          if (isConditionExpression && !hasPhiUpdates) {
             jsCondition = generateExpression(condition);
             currentContainer = body;
           } else {
             jsCondition = newLiteralBool(true);
             currentContainer = body;
             generateStatements(condition);
             use(condition.conditionExpression);
             js.Expression ifTest = new js.Prefix("!", pop());
-            js.Break jsBreak = new js.Break(null);
-            pushStatement(new js.If.noElse(ifTest, jsBreak));
+            js.Statement jsBreak = new js.Break(null);
+            js.Statement exitLoop;
+            if (avoidContainer.statements.isEmpty) {
+              exitLoop = jsBreak;
+            } else {
+              avoidContainer.statements.add(jsBreak);
+              exitLoop = avoidContainer;
+            }
+            pushStatement(new js.If.noElse(ifTest, exitLoop));
           }
           if (info.updates != null) {
             wrapLoopBodyForContinue(info);
             generateStatements(info.updates);
           } else {
             visitBodyIgnoreLabels(info);
           }
           currentContainer = oldContainer;
           body = unwrapStatement(body);
           loop = new js.While(jsCondition, body);
         }
         break;
       case HLoopBlockInformation.DO_WHILE_LOOP:
         if (info.initializer != null) {
           generateStatements(info.initializer);
         }
+        // We inserted a basic block to avoid critical edges. This block is
+        // part of the LoopBlockInformation and must therefore be handled here.
         js.Block oldContainer = currentContainer;
+        js.Block exitAvoidContainer = new js.Block.empty();
+        currentContainer = exitAvoidContainer;
+        assignPhisOfSuccessors(condition.end.successors.last);
+        bool hasExitPhiUpdates = !exitAvoidContainer.statements.isEmpty;
+        currentContainer = oldContainer;
+
+
+        oldContainer = currentContainer;
         js.Block body = new js.Block.empty();
         // If there are phi copies in the block that jumps to the
         // loop entry, we must emit the condition like this:
         // do {
         //   body;
         //   if (condition) {
         //     phi updates;
         //     continue;
         //   } else {
         //     break;
@@ skipping 15 matching lines @@
           generateStatements(condition);
           use(condition.conditionExpression);
         }
         js.Expression jsCondition = pop();
         if (jsCondition == null) {
           // If the condition is dead code, we turn the do-while into
           // a simpler while because we will never reach the condition
           // at the end of the loop anyway.
           loop = new js.While(newLiteralBool(true), unwrapStatement(body));
         } else {
-          if (hasPhiUpdates) {
+          if (hasPhiUpdates || hasExitPhiUpdates) {
             updateBody.statements.add(new js.Continue(null));
+            js.Statement jsBreak = new js.Break(null);
+            js.Statement exitLoop;
+            if (exitAvoidContainer.statements.isEmpty) {
+              exitLoop = jsBreak;
+            } else {
+              exitAvoidContainer.statements.add(jsBreak);
+              exitLoop = exitAvoidContainer;
+            }
             body.statements.add(
-                new js.If(jsCondition, updateBody, new js.Break(null)));
+                new js.If(jsCondition, updateBody, exitLoop));
             jsCondition = newLiteralBool(true);
           }
           loop = new js.Do(unwrapStatement(body), jsCondition);
         }
         currentContainer = oldContainer;
         break;
       default:
         compiler.internalError(condition.conditionExpression,
             'Unexpected loop kind: ${info.kind}.');
     }
@@ skipping 1751 matching lines @@
   js.PropertyAccess accessHelper(String name) {
     Element helper = compiler.findHelper(name);
     if (helper == null) {
       // For mocked-up tests.
       return js.js('(void 0).$name');
     }
     registry.registerStaticUse(helper);
     return backend.namer.elementAccess(helper);
   }
 }