Fix bad assumption of environment builder when it comes to nested loops: blocks inside a loop would…

sdk/lib/_internal/compiler/implementation/ssa/bailout.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 BailoutInfo {
   int instructionId;
   int bailoutId;
   BailoutInfo(this.instructionId, this.bailoutId);
 }
 
 /**
  * Keeps track of the execution environment for instructions. An
  * execution environment contains the SSA instructions that are live.
  */
 class Environment {
   final Set<HInstruction> lives;
-  final Set<HBasicBlock> loopMarkers;
+  final List<HBasicBlock> loopMarkers;
   Environment() : lives = new Set<HInstruction>(),
-                  loopMarkers = new Set<HBasicBlock>();
+                  loopMarkers = new List<HBasicBlock>();
   Environment.from(Environment other)
     : lives = new Set<HInstruction>.from(other.lives),
-      loopMarkers = new Set<HBasicBlock>.from(other.loopMarkers);
+      loopMarkers = new List<HBasicBlock>.from(other.loopMarkers);
 
   void remove(HInstruction instruction) {
     lives.remove(instruction);
   }
 
   void add(HInstruction instruction) {
     // If the instruction is a check, we add its checked input
     // instead. This allows sharing the same environment between
     // different type guards.
     //
     // Also, we don't need to add code motion invariant instructions
     // in the live set (because we generate them at use-site), except
     // for parameters that are not 'this', which is always passed as
     // the receiver.
     if (instruction is HCheck) {
       add(instruction.checkedInput);
     } else if (!instruction.isCodeMotionInvariant()
                || (instruction is HParameterValue && instruction is !HThis)) {
       lives.add(instruction);
     } else {
       for (int i = 0, len = instruction.inputs.length; i < len; i++) {
         add(instruction.inputs[i]);
       }
     }
   }
 
-  void addLoopMarker(HBasicBlock block) {
-    loopMarkers.add(block);
-  }
-
-  void removeLoopMarker(HBasicBlock block) {
-    loopMarkers.remove(block);
-  }
-
   void addAll(Environment other) {
     lives.addAll(other.lives);
-    loopMarkers.addAll(other.loopMarkers);
   }
 
   bool get isEmpty => lives.isEmpty && loopMarkers.isEmpty;
+
+  String toString() => '${loopMarkers.length}';

[floitsch, 2012/11/20 15:39:31]

Remove or make it at least mention "Environment".

[ngeoffray, 2012/11/20 16:40:37]

Removed.

 }
 
 
 /**
  * Visits the graph in dominator order and inserts TypeGuards in places where
  * we consider the guard to be of value.
  *
  * Might modify the [types] in an inconsistent way. No further analysis should
  * rely on them.
  */
@@ skipping 175 matching lines @@
  *
  * At the end of the computation, insert type guards in the graph.
  */
 class SsaEnvironmentBuilder extends HBaseVisitor implements OptimizationPhase {
   final Compiler compiler;
   final String name = 'SsaEnvironmentBuilder';
 
   final Map<HBailoutTarget, Environment> capturedEnvironments;
   final Map<HBasicBlock, Environment> liveInstructions;
   Environment environment;
+  List<HBasicBlock> loopMarkers;

[floitsch, 2012/11/20 15:39:31]

Add comment explaining what these contain.

[ngeoffray, 2012/11/20 16:40:37]

Done.

 
   SsaEnvironmentBuilder(Compiler this.compiler)
     : capturedEnvironments = new Map<HBailoutTarget, Environment>(),
-      liveInstructions = new Map<HBasicBlock, Environment>();
+      liveInstructions = new Map<HBasicBlock, Environment>(),
+      loopMarkers = <HBasicBlock>[];
 
 
   void visitGraph(HGraph graph) {
     visitPostDominatorTree(graph);
     if (!liveInstructions[graph.entry].isEmpty) {
       compiler.internalError('Bailout environment computation',
           node: compiler.currentElement.parseNode(compiler));
     }
     updateLoopMarkers();
     insertCapturedEnvironments();
   }
 
   void updateLoopMarkers() {
     // If the block is a loop header, we need to merge the loop
     // header's live instructions into every environment that contains
     // the loop marker.
     // For example with the following loop (read the example in
     // reverse):
     //
     // while (true) { <-- (4) update the marker with the environment
     //   use(x);      <-- (3) environment = {x}
     //   bailout;     <-- (2) has the marker when computed
     // }              <-- (1) create a loop marker
     //
     // The bailout instruction first captures the marker, but it
     // will be replaced by the live environment at the loop entry,
     // in this case {x}.
     capturedEnvironments.forEach((ignoredInstruction, env) {
       env.loopMarkers.forEach((HBasicBlock header) {
-        env.removeLoopMarker(header);
         env.addAll(liveInstructions[header]);
       });
+      env.loopMarkers.clear();
     });
   }
 
   void visitBasicBlock(HBasicBlock block) {
     environment = new Environment();
 
     // Add to the environment the live instructions of its successor, as well as
     // the inputs of the phis of the successor that flow from this block.
     for (int i = 0; i < block.successors.length; i++) {
       HBasicBlock successor = block.successors[i];
       Environment successorEnv = liveInstructions[successor];
       if (successorEnv != null) {
         environment.addAll(successorEnv);
       } else {
         // If we haven't computed the liveInstructions of that successor, we
         // know it must be a loop header.
         assert(successor.isLoopHeader());
-        environment.addLoopMarker(successor);
+        assert(!block.isLoopHeader());
+        loopMarkers.add(successor);
       }
 
       int index = successor.predecessors.indexOf(block);
       for (HPhi phi = successor.phis.first; phi != null; phi = phi.next) {
         environment.add(phi.inputs[index]);
       }
     }
 
+    // If the block is a loop header, we can remove the loop marker,

[floitsch, 2012/11/20 15:39:31]

This sounds too much like an optimization.
In fact without this if the 'loopMarkers' list would never shrink.

[ngeoffray, 2012/11/20 16:40:37]

Improved comment.

+    // because it will just recompute the loop phis.
+    if (block.isLoopHeader()) {
+      loopMarkers.removeLast();

[floitsch, 2012/11/20 15:39:31]

assert that it is the same as block?

[ngeoffray, 2012/11/20 16:40:37]

Done.

[ngeoffray, 2012/11/20 17:30:45]

Actually, I had to change the data structure to be a set, because the last may
not be the current loop header in case of labeled loops.

+    }
+
+    environment.loopMarkers.addAll(loopMarkers);
+
     // Iterate over all instructions to remove an instruction from the
     // environment and add its inputs.
     HInstruction instruction = block.last;
     while (instruction != null) {
       instruction.accept(this);
       instruction = instruction.previous;
     }
 
     // We just remove the phis from the environment. The inputs of the
     // phis will be put in the environment of the predecessors.
     for (HPhi phi = block.phis.first; phi != null; phi = phi.next) {
       environment.remove(phi);
     }
 
-    // If the block is a loop header, we can remove the loop marker,
-    // because it will just recompute the loop phis.
-    if (block.isLoopHeader()) {
-      environment.removeLoopMarker(block);
-    }
-
     // Finally save the liveInstructions of that block.
     liveInstructions[block] = environment;
   }
 
   void visitBailoutTarget(HBailoutTarget target) {
     visitInstruction(target);
     capturedEnvironments[target] = new Environment.from(environment);
   }
 
   void visitInstruction(HInstruction instruction) {
@@ skipping 187 matching lines @@
         hasComplexBailoutTargets = true;
       }
     } else {
       hasComplexBailoutTargets = true;
       blocks.forEach((HBasicBlock block) {
         block.bailoutTargets.add(target);
       });
     }
   }
 }