Revert r27232: some checked mode tests fail.

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

Index: sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart
===================================================================
--- sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart	(revision 27236)
+++ sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart	(working copy)
@@ -47,12 +47,6 @@
   Range newNormalizedRange(Value low, Value up) {
     return new Range.normalize(low, up, this);
   }
-
-  Range newMarkerRange() {
-    return new Range(new MarkerValue(false, this),
-                     new MarkerValue(true, this),
-                     this);
-  }
 }
 
 /**
@@ -95,33 +89,6 @@
 }
 
 /**
- * The [MarkerValue] class is used to recognize ranges of loop
- * updates.
- */
-class MarkerValue extends Value {
-  /// If [positive] is true (respectively false), the marker goes
-  /// to [MaxIntValue] (respectively [MinIntValue]) when being added
-  /// to a positive (respectively negative) value.
-  final bool positive;
-
-  const MarkerValue(this.positive, info) : super(info);
-
-  Value operator +(Value other) {
-    if (other.isPositive && positive) return const MaxIntValue();
-    if (other.isNegative && !positive) return const MinIntValue();
-    if (other is IntValue) return this;
-    return const UnknownValue();
-  }
-
-  Value operator -(Value other) {
-    if (other.isPositive && !positive) return const MinIntValue();
-    if (other.isNegative && positive) return const MaxIntValue();
-    if (other is IntValue) return this;
-    return const UnknownValue();
-  }
-}
-
-/**
  * An [IntValue] contains a constant integer value.
  */
 class IntValue extends Value {
@@ -487,7 +454,7 @@
         lower.min(other.lower), upper.max(other.upper));
   }
 
-  Range intersection(Range other) {
+  intersection(Range other) {
     Value low = lower.max(other.lower);
     Value up = upper.min(other.upper);
     // If we could not compute max or min, pick a value in the two
@@ -654,7 +621,7 @@
     // phase is not necessarily run before the [ValueRangeAnalyzer].
     if (phi.inputs.any((i) => !i.isInteger())) return info.newUnboundRange();
     if (phi.block.isLoopHeader()) {
-      Range range = new LoopUpdateRecognizer(ranges, info).run(phi);
+      Range range = tryInferLoopPhiRange(phi);
       if (range == null) return info.newUnboundRange();
       return range;
     }
@@ -666,6 +633,11 @@
     return range;
   }
 
+  Range tryInferLoopPhiRange(HPhi phi) {
+    HInstruction update = phi.inputs[1];
+    return update.accept(new LoopUpdateRecognizer(phi, ranges, info));
+  }
+
   Range visitConstant(HConstant constant) {
     if (!constant.isInteger()) return info.newUnboundRange();
     IntConstant constantInt = constant.constant;
@@ -936,43 +908,52 @@
 }
 
 /**
- * Tries to find a range for the update instruction of a loop phi.
+ * Recognizes a number of patterns in a loop update instruction and
+ * tries to infer a range for the loop phi.
  */
 class LoopUpdateRecognizer extends HBaseVisitor {
+  final HPhi loopPhi;
   final Map<HInstruction, Range> ranges;
   final ValueRangeInfo info;
-  LoopUpdateRecognizer(this.ranges, this.info);
+  LoopUpdateRecognizer(this.loopPhi, this.ranges, this.info);
 
-  Range run(HPhi loopPhi) {
-    // Create a marker range for the loop phi, so that if the update
-    // uses the loop phi, it has a range to use.
-    ranges[loopPhi] = info.newMarkerRange();
-    Range updateRange = visit(loopPhi.inputs[1]);
-    ranges[loopPhi] = null;
-    if (updateRange == null) return null;
-    Range startRange = ranges[loopPhi.inputs[0]];
-    Value low = updateRange.lower is MarkerValue
-        ? startRange.lower
-        : updateRange.lower;
-    Value up = updateRange.upper is MarkerValue
-        ? startRange.upper
-        : updateRange.upper;
-    return info.newNormalizedRange(low, up);
+  Range visitAdd(HAdd operation) {
+    Range range = getRangeForRecognizableOperation(operation);
+    if (range == null) return info.newUnboundRange();
+    Range initial = ranges[loopPhi.inputs[0]];
+    if (range.isPositive) {
+      return info.newNormalizedRange(initial.lower, const MaxIntValue());
+    } else if (range.isNegative) {
+      return info.newNormalizedRange(const MinIntValue(), initial.upper);
+    }
+    return info.newUnboundRange();
   }
 
-  Range visit(HInstruction instruction) {
-    if (!instruction.isInteger()) return null;
-    if (ranges[instruction] != null) return ranges[instruction];
-    return instruction.accept(this);
+  Range visitSubtract(HSubtract operation) {
+    Range range = getRangeForRecognizableOperation(operation);
+    if (range == null) return info.newUnboundRange();
+    Range initial = ranges[loopPhi.inputs[0]];
+    if (range.isPositive) {
+      return info.newNormalizedRange(const MinIntValue(), initial.upper);
+    } else if (range.isNegative) {
+      return info.newNormalizedRange(initial.lower, const MaxIntValue());
+    }
+    return info.newUnboundRange();
   }
 
   Range visitPhi(HPhi phi) {
-    // If the update of a loop phi involves another loop phi, we give
-    // up.
-    if (phi.block.isLoopHeader()) return null;
     Range phiRange;
     for (HInstruction input in phi.inputs) {
-      Range inputRange = visit(input);
+      HInstruction instruction = unwrap(input);
+      // If one of the inputs is the loop phi, then we're only
+      // interested in the other inputs: a loop phi feeding itself means
+      // it is not being updated.
+      if (instruction == loopPhi) continue;
+
+      // If another loop phi is involved, it's too complex to analyze.
+      if (instruction is HPhi && instruction.block.isLoopHeader()) return null;
+
+      Range inputRange = instruction.accept(this);
       if (inputRange == null) return null;
       if (phiRange == null) {
         phiRange = inputRange;
@@ -983,23 +964,49 @@
     return phiRange;
   }
 
-  Range visitCheck(HCheck instruction) {
-    return visit(instruction.checkedInput);
-  }
+  /**
+   * If [operation] is recognizable, returns the inferred range.
+   * Otherwise returns [null].
+   */
+  Range getRangeForRecognizableOperation(HBinaryArithmetic operation) {
+    if (!operation.left.isInteger()) return null;
+    if (!operation.right.isInteger()) return null;
+    HInstruction left = unwrap(operation.left);
+    HInstruction right = unwrap(operation.right);
+    // We only recognize operations that operate on the loop phi.
+    bool isLeftLoopPhi = (left == loopPhi);
+    bool isRightLoopPhi = (right == loopPhi);
+    if (!isLeftLoopPhi && !isRightLoopPhi) return null;
 
-  Range visitAdd(HAdd operation) {
-    return handleBinaryOperation(operation);
-  }
+    var other = isLeftLoopPhi ? right : left;
+    // If the analysis already computed range for the update, use it.
+    if (ranges[other] != null) return ranges[other];
 
-  Range visitSubtract(HSubtract operation) {
-    return handleBinaryOperation(operation);
+    // We currently only handle constants in updates if the
+    // update does not have a range.
+    if (other.isConstant()) {
+      Value value = info.newIntValue(other.constant.value);
+      return info.newNormalizedRange(value, value);
+    }
+    return null;
   }
 
-  Range handleBinaryOperation(HBinaryArithmetic instruction) {
-    Range leftRange = visit(instruction.left);
-    Range rightRange = visit(instruction.right);
-    if (leftRange == null || rightRange == null) return null;
-    BinaryOperation operation = instruction.operation(info.constantSystem);
-    return operation.apply(leftRange, rightRange);
+  /**
+   * [HCheck] instructions may check the loop phi. Since we only
+   * recognize updates on the loop phi, we must [unwrap] the [HCheck]
+   * instruction to check if it references the loop phi.
+   */
+  HInstruction unwrap(instruction) {
+    if (instruction is HCheck) return unwrap(instruction.checkedInput);
+    // [HPhi] might have two different [HCheck] instructions as
+    // inputs, checking the same instruction.
+    if (instruction is HPhi && !instruction.block.isLoopHeader()) {
+      HInstruction result = unwrap(instruction.inputs[0]);
+      for (int i = 1; i < instruction.inputs.length; i++) {
+        if (result != unwrap(instruction.inputs[i])) return instruction;
+      }
+      return result;
+    }
+    return instruction;
   }
 }