Fix variable allocator in the presence of HCheck instructions.

sdk/lib/_internal/compiler/implementation/ssa/variable_allocator.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;
 
 /**
  * The [LiveRange] class covers a range where an instruction is live.
  */
 class LiveRange {
@@ skipping 11 matching lines @@
  * The [LiveInterval] class contains the list of ranges where an
  * instruction is live.
  */
 class LiveInterval {
   /**
    * The id where the instruction is defined.
    */
   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
    * die at [to].
    */
   void loopUpdate(int from, int to) {
     for (LiveRange range in ranges) {
       if (from <= range.start && range.end < to) {
         range.end = to;
       }
@@ skipping 65 matching lines @@
   LiveEnvironment(this.liveIntervals, this.endId)
     : liveInstructions = new Map<HInstruction, int>(),
       loopMarkers = new Map<HBasicBlock, int>();
 
   /**
    * Remove an instruction from the liveIn set. This method also
    * updates the live interval of [instruction] to contain the new
    * 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);
   }
 
   /**
    * Add [instruction] to the liveIn set. If the instruction is not
    * already in the set, we save the id where it dies.
    */
   void add(HInstruction instruction, int userId) {
     // 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);
-    }
   }
 
   /**
    * Merge this environment with [other]. Update the end id of
    * instructions in case they are different between this and [other].
    */
   void mergeWith(LiveEnvironment other) {
     other.liveInstructions.forEach((HInstruction instruction, int existingId) {
       // If both environments have the same instruction id of where
       // [instruction] dies, there is no need to update the live
@@ skipping 64 matching lines @@
     }
   }
 
   void markInputsAsLiveInEnvironment(HInstruction instruction,
                                      LiveEnvironment environment) {
     for (int i = 0, len = instruction.inputs.length; i < len; i++) {
       markAsLiveInEnvironment(instruction.inputs[i], environment);
     }
   }
 
+  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);
 
     // Add to the environment the liveIn 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];
       LiveEnvironment successorEnv = liveInstructions[successor];
       if (successorEnv != null) {
         environment.mergeWith(successorEnv);
       } else {
         environment.addLoopMarker(successor, instructionId);
       }
 
       int index = successor.predecessors.indexOf(block);
       for (HPhi phi = successor.phis.first; phi != null; phi = phi.next) {
         markAsLiveInEnvironment(phi.inputs[index], environment);
       }
     }
 
     // Iterate over all instructions to remove an instruction from the
     // 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
     // phis will be put in the environment of the predecessors.
     for (HPhi phi = block.phis.first; phi != null; phi = phi.next) {
       environment.remove(phi, instructionId);
     }
 
     // Save the liveInstructions of that block.
     environment.startId = instructionId + 1;
@@ skipping 306 matching lines @@
       handlePhi(phi, namer);
     });
 
     block.forEachInstruction((HInstruction instruction) {
       handleInstruction(instruction, namer);
     });
   }
 
   /**
    * 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;
     if (instruction is HParameterValue) return true;
     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;
       return needsName(instruction.checkedInput);
     }
     return true;
   }
 
   /**
    * Returns whether [instruction] dies at the instruction [at].
    */
   bool diesAt(HInstruction instruction, HInstruction at) {
     LiveInterval atInterval = liveIntervals[at];
     LiveInterval instructionInterval = liveIntervals[instruction];
     int start = atInterval.start;
     return instructionInterval.diesAt(start);
   }
 
   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);
       }
     } else if (generateAtUseSite.contains(instruction)) {
       // If the instruction is generated at use site, then all its
       // inputs may also die at [at].
       for (int i = 0, len = instruction.inputs.length; i < len; i++) {
         HInstruction input = instruction.inputs[i];
         freeUsedNamesAt(input, at, namer);
       }
     }
   }
 
   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);
     }
 
     if (needsName(instruction)) {
       namer.allocateName(instruction);
     }
   }
 
   void handlePhi(HPhi phi, VariableNamer namer) {
     if (!needsName(phi)) return;
 
     for (int i = 0; i < phi.inputs.length; i++) {
       HInstruction input = phi.inputs[i];
       HBasicBlock predecessor = phi.block.predecessors[i];
       if (!needsName(input)) {
         names.addAssignment(predecessor, input, phi);
       } else {
         names.addCopy(predecessor, input, phi);
       }
     }
 
     namer.allocateName(phi);
   }
 }