Fix a long-standing bug in the computation of the live environments for bailouts. When visiting a l…

frog/leg/ssa/bailout.dart

Index: frog/leg/ssa/bailout.dart
===================================================================
--- frog/leg/ssa/bailout.dart	(revision 5281)
+++ frog/leg/ssa/bailout.dart	(working copy)
@@ -14,10 +14,17 @@
  */
 class Environment {
   final Set<HInstruction> lives;
-  Environment() : lives = new Set<HInstruction>();
+  final Set<HBasicBlock> loopMarkers;
+  Environment() : lives = new Set<HInstruction>(),
+                  loopMarkers = new Set<HBasicBlock>();
   Environment.from(Environment other)
-    : lives = new Set<HInstruction>.from(other.lives);
+    : lives = new Set<HInstruction>.from(other.lives),
+      loopMarkers = new Set<HBasicBlock>.from(other.loopMarkers);
 
+  Environment.forLoop(Environment other)

[floitsch, 2012/03/12 11:35:10]

forLoopBody

[ngeoffray, 2012/03/12 11:53:24]

Done.

+    : lives = new Set<HInstruction>(),
+      loopMarkers = new Set<HBasicBlock>.from(other.loopMarkers);
+
   void remove(HInstruction instruction) {
     lives.remove(instruction);
   }
@@ -32,8 +39,17 @@
     }
   }
 
+  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);
   }
 
   List<HInstruction> buildAndSetLast(HInstruction instruction) {
@@ -46,6 +62,7 @@
 
   bool isEmpty() => lives.isEmpty();
   bool contains(HInstruction instruction) => lives.contains(instruction);
+  bool containsLoopMarker(HBasicBlock block) => loopMarkers.contains(block);
   void clear() => lives.clear();
 }
 
@@ -60,15 +77,28 @@
   Environment environment;
   SubGraph subGraph;
 
-  SsaEnvironmentBuilder(Compiler this.compiler);
+  final Map<HInstruction, Environment> capturedEnvironments;
 
+  SsaEnvironmentBuilder(Compiler this.compiler)
+    : capturedEnvironments = new Map<HInstruction, Environment>();
+
   void visitGraph(HGraph graph) {
     subGraph = new SubGraph(graph.entry, graph.exit);
     environment = new Environment();
     visitBasicBlock(graph.entry);
     assert(environment.isEmpty());
+    insertCapturedEnvironments();
   }
 
+  abstract void insertCapturedEnvironments();
+  abstract bool shouldCaptureEnvironment(HInstruction instruction);
+
+  void maybeCaptureEnvironment(HInstruction instruction) {
+    if (shouldCaptureEnvironment(instruction)) {
+      capturedEnvironments[instruction] = new Environment.from(environment);
+    }
+  }
+
   void visitSubGraph(SubGraph newSubGraph) {
     SubGraph oldSubGraph = subGraph;
     subGraph = newSubGraph;
@@ -90,9 +120,20 @@
     for (HPhi phi = block.phis.first; phi != null; phi = phi.next) {
       phi.accept(this);
     }
+
+    if (block.isLoopHeader()) {

[floitsch, 2012/03/12 11:35:10]

Add a comment, maybe even with an example.

[ngeoffray, 2012/03/12 11:53:24]

Done.

+      environment.removeLoopMarker(block);
+      capturedEnvironments.forEach((instruction, env) {
+        if (env.containsLoopMarker(block)) {
+          env.removeLoopMarker(block);
+          env.addAll(environment);
+        }
+      });
+    }
   }
 
   void visitPhi(HPhi phi) {
+    maybeCaptureEnvironment(phi);
     environment.remove(phi);
     // If the block is a loop header, we insert the incoming values of
     // the phis, and remove the loop values.
@@ -107,6 +148,7 @@
   }
 
   void visitInstruction(HInstruction instruction) {
+    maybeCaptureEnvironment(instruction);
     environment.remove(instruction);
     for (int i = 0, len = instruction.inputs.length; i < len; i++) {
       environment.add(instruction.inputs[i]);
@@ -193,21 +235,34 @@
 
     // Visit the code after the loop.
     visitBasicBlock(block.successors[1]);
-    // TODO(ngeoffray): Remove the instructions of the loop-exit from
-    // the environment.
 
+    Environment joinEnvironment = environment;
+
+    // When visiting the loop body, we don't require the live
+    // instructions after the loop body to be in the environment. They
+    // will be either recomputed in the loop header, or inserted
+    // with the loop marker.

[floitsch, 2012/03/12 11:35:10]

However we need the current environment to transfer already existing loop
markers.

[ngeoffray, 2012/03/12 11:53:24]

Done.

+    environment = new Environment.forLoop(environment);
+
+    // Put the loop phis in the environment.
     HBasicBlock header = block.isLoopHeader() ? block : block.parentLoopHeader;
-    // Put the loop phis in the environment.
     for (HPhi phi = header.phis.first; phi != null; phi = phi.next) {
       for (int i = 1, len = phi.inputs.length; i < len; i++) {
         environment.add(phi.inputs[i]);
       }
     }
 
+    // Add the loop marker
+    environment.addLoopMarker(header);
+
     if (!branch.isDoWhile()) {
       assert(block.successors[0] == block.dominatedBlocks[0]);
       visitBasicBlock(block.successors[0]);
     }
+
+    // We merge the environment required by the code after the loop,
+    // and the code inside the loop.
+    environment.addAll(joinEnvironment);
   }
 
   // Deal with all kinds of control flow instructions. In case we add
@@ -240,34 +295,25 @@
 
   SsaTypeGuardBuilder(Compiler compiler) : super(compiler);
 
-  void tryInsertTypeGuard(HInstruction instruction,
-                          HInstruction insertionPoint) {
-    // If we found a type for the instruction, but the instruction
-    // does not know if it produces that type, add a type guard.
-    if (instruction.type.isKnown() && !instruction.hasExpectedType()) {
-      // The type guard expects the guarded instruction to be at the
-      // end of the inputs.
-      List<HInstruction> inputs = environment.buildAndSetLast(instruction);
+  bool shouldCaptureEnvironment(HInstruction instruction) {
+    return instruction.type.isKnown() && !instruction.hasExpectedType();
+  }
+
+  void insertCapturedEnvironments() {
+    capturedEnvironments.forEach((HInstruction instruction, Environment env) {
+      List<HInstruction> inputs = env.buildAndSetLast(instruction);
       HTypeGuard guard =
           new HTypeGuard(instruction.type, inputs, instruction.id);
       // Remove the instruction's type, the guard is now holding that
       // type.
       instruction.type = HType.UNKNOWN;
       instruction.block.rewrite(instruction, guard);
+      HInstruction insertionPoint = (instruction is HPhi)
+          ? phi.block.first
+          : instruction.next;
       insertionPoint.block.addBefore(insertionPoint, guard);
-    }
+    });
   }
-
-
-  void visitInstruction(HInstruction instruction) {
-    tryInsertTypeGuard(instruction, instruction.next);
-    super.visitInstruction(instruction);
-  }
-
-  void visitPhi(HPhi phi) {
-    tryInsertTypeGuard(phi, phi.block.first);
-    super.visitPhi(phi);
-  }
 }
 
 /*
@@ -280,24 +326,21 @@
 
   SsaBailoutBuilder(Compiler compiler, this.bailouts) : super(compiler);
 
-  void checkBailout(HInstruction instruction, HInstruction insertionPoint) {
-    BailoutInfo info = bailouts[instruction.id];
-    if (info != null) {
-      List<HInstruction> inputs = environment.buildAndSetLast(instruction);
+  bool shouldCaptureEnvironment(HInstruction instruction) {
+    return bailouts[instruction.id] != null;
+  }
+
+  void insertCapturedEnvironments() {
+    capturedEnvironments.forEach((HInstruction instruction, Environment env) {
+      BailoutInfo info = bailouts[instruction.id];
+      List<HInstruction> inputs = env.buildAndSetLast(instruction);
       HBailoutTarget bailout = new HBailoutTarget(info.bailoutId, inputs);
+      HInstruction insertionPoint = (instruction is HPhi)
+          ? phi.block.first
+          : instruction.next;
       instruction.block.addBefore(insertionPoint, bailout);
-    }
+    });
   }
-
-  void visitInstruction(HInstruction instruction) {
-    checkBailout(instruction, instruction.next);
-    super.visitInstruction(instruction);
-  }
-
-  void visitPhi(HPhi phi) {
-    checkBailout(phi, phi.block.first);
-    super.visitPhi(phi);
-  }
 }
 
 /**