Fix variable allocator in the presence of HCheck instructions.

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

Index: sdk/lib/_internal/compiler/implementation/ssa/variable_allocator.dart
===================================================================
--- sdk/lib/_internal/compiler/implementation/ssa/variable_allocator.dart	(revision 21537)
+++ sdk/lib/_internal/compiler/implementation/ssa/variable_allocator.dart	(working copy)
@@ -29,6 +29,8 @@
   int start;
   final List<LiveRange> ranges;
   LiveInterval() : ranges = <LiveRange>[];
+  LiveInterval.forCheck(this.start, LiveInterval checkedInterval)
+      : ranges = checkedInterval.ranges;
 
   /**
    * Update all ranges that are contained in [from, to[ to
@@ -114,24 +116,13 @@
    * range: [id, / id contained in [liveInstructions] /].
    */
   void remove(HInstruction instruction, int id) {
-    // Special case the HCheck instruction to have the same live
-    // interval as the instruction it is checking.
-    if (instruction is HCheck) {
-      var input = instruction.checkedInput;
-      while (input is HCheck) input = input.checkedInput;
-      liveIntervals.putIfAbsent(input, () => new LiveInterval());
-      // Unconditionally force the live interval of the HCheck to
-      // be the live interval of the instruction it is checking.
-      liveIntervals[instruction] = liveIntervals[input];
-    } else {
-      LiveInterval range = liveIntervals.putIfAbsent(
-          instruction, () => new LiveInterval());
-      int lastId = liveInstructions[instruction];
-      // If [lastId] is null, then this instruction is not being used.
-      range.add(new LiveRange(id, lastId == null ? id : lastId));
-      // The instruction is defined at [id].
-      range.start = id;
-    }
+    LiveInterval interval = liveIntervals.putIfAbsent(
+        instruction, () => new LiveInterval());
+    int lastId = liveInstructions[instruction];
+    // If [lastId] is null, then this instruction is not being used.
+    interval.add(new LiveRange(id, lastId == null ? id : lastId));
+    // The instruction is defined at [id].
+    interval.start = id;
     liveInstructions.remove(instruction);
   }
 
@@ -143,13 +134,6 @@
     // Note that we are visiting the graph in post-dominator order, so
     // the first time we see a variable is when it dies.
     liveInstructions.putIfAbsent(instruction, () => userId);
-    if (instruction is HCheck) {
-      // Special case the HCheck instruction to mark the actual
-      // checked instruction live.
-      var input = instruction.checkedInput;
-      while (input is HCheck) input = input.checkedInput;
-      liveInstructions.putIfAbsent(input, () => userId);
-    }
   }
 
   /**
@@ -234,16 +218,50 @@
     }
   }
 
+  HInstruction unwrap(instruction) {
+    do {
+      instruction = instruction.checkedInput;
+    } while (instruction is HCheck);
+    return instruction;
+  }
+
   void markAsLiveInEnvironment(HInstruction instruction,
                                LiveEnvironment environment) {
-    if (environment.contains(instruction)) return;

[ngeoffray, 2013/04/16 14:58:02]

The contains check here and the code line 151 were the root cause of the bug:
line 151 was adding an instruction to the live environment, and when we started
analyzing that instruction we would not run the code below. The code below
setups ranges for the inputs of an instruction.

-    environment.add(instruction, instructionId);
-    // HPhis are treated specially.
+    // The inputs of a [HPhi] are being handled at the entry of a
+    // block.
     if (generateAtUseSite.contains(instruction) && instruction is !HPhi) {
       markInputsAsLiveInEnvironment(instruction, environment);
+    } else {
+      environment.add(instruction, instructionId);
+      // Special case the HCheck instruction to mark the actual
+      // checked instruction live. The checked instruction and the
+      // [HCheck] will share the same live ranges.
+      if (instruction is HCheck) {
+        HInstruction checked = unwrap(instruction);
+        if (!generateAtUseSite.contains(checked)) {
+          environment.add(checked, instructionId);
+        }
+      }
     }
   }
 
+  void removeFromEnvironment(HInstruction instruction,
+                             LiveEnvironment environment) {
+    environment.remove(instruction, instructionId);
+    // Special case the HCheck instruction to have the same live
+    // interval as the instruction it is checking.
+    if (instruction is HCheck) {
+      HInstruction checked = unwrap(instruction);
+      if (!generateAtUseSite.contains(checked)) {
+        liveIntervals.putIfAbsent(checked, () => new LiveInterval());
+        // Unconditionally force the live ranges of the HCheck to
+        // be the live ranges of the instruction it is checking.
+        liveIntervals[instruction] =
+            new LiveInterval.forCheck(instructionId, liveIntervals[checked]);
+      }
+    }
+  }
+
   void visitBasicBlock(HBasicBlock block) {
     LiveEnvironment environment =
         new LiveEnvironment(liveIntervals, instructionId);
@@ -269,10 +287,12 @@
     // environment and add its inputs.
     HInstruction instruction = block.last;
     while (instruction != null) {
-      environment.remove(instruction, instructionId);
-      markInputsAsLiveInEnvironment(instruction, environment);
+      if (!generateAtUseSite.contains(instruction)) {
+        removeFromEnvironment(instruction, environment);
+        markInputsAsLiveInEnvironment(instruction, environment);
+      }
+      instructionId--;
       instruction = instruction.previous;
-      instructionId--;
     }
 
     // We just remove the phis from the environment. The inputs of the
@@ -599,7 +619,7 @@
 
   /**
    * Returns whether [instruction] needs a name. Instructions that
-   * have no users or that are generated at use site does not need a name.
+   * have no users or that are generated at use site do not need a name.
    */
   bool needsName(HInstruction instruction) {
     if (instruction is HThis) return false;
@@ -607,7 +627,7 @@
     if (instruction.usedBy.isEmpty) return false;
     if (generateAtUseSite.contains(instruction)) return false;
     // A [HCheck] instruction that has control flow needs a name only if its
-    // checked input needs a name (e.g. a check [HConstant] does not
+    // checked input needs a name (for example, a checked [HConstant] does not
     // need a name).
     if (instruction is HCheck && instruction.isControlFlow()) {
       HCheck check = instruction;
@@ -629,15 +649,6 @@
   void freeUsedNamesAt(HInstruction instruction,
                        HInstruction at,
                        VariableNamer namer) {
-    // TODO(ager): We cannot perform this check to free names for
-    // HCheck instructions because they are special cased to have the
-    // same live intervals as the instruction they are checking. This
-    // includes sharing the start id with the checked
-    // input. Therefore, for HCheck(checkedInput, otherInput) we would
-    // end up checking that otherInput dies not here, but at the
-    // location of checkedInput. We should preserve the start id for
-    // the check instruction.
-    if (at is HCheck) return;
     if (needsName(instruction)) {
       if (diesAt(instruction, at)) {
         namer.freeName(instruction);
@@ -653,6 +664,11 @@
   }
 
   void handleInstruction(HInstruction instruction, VariableNamer namer) {
+    if (generateAtUseSite.contains(instruction)) {
+      assert(!liveIntervals.containsKey(instruction));
+      return;
+    }
+
     for (int i = 0, len = instruction.inputs.length; i < len; i++) {
       HInstruction input = instruction.inputs[i];
       freeUsedNamesAt(input, instruction, namer);