Revert r27232: some checked mode tests fail.

sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.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 ValueRangeInfo {
   final ConstantSystem constantSystem;
 
@@ skipping 29 matching lines @@
     return new NegateValue(value, this);
   }
 
   Range newUnboundRange() {
     return new Range.unbound(this);
   }
 
   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);
-  }
 }
 
 /**
  * A [Value] represents both symbolic values like the value of a
  * parameter, or the length of an array, and concrete values, like
  * constants.
  */
 abstract class Value {
   final ValueRangeInfo info;
   const Value(this.info);
@@ skipping 22 matching lines @@
     if (value.isNegative) return other;
     return const UnknownValue();
   }
 
   bool get isNegative => false;
   bool get isPositive => false;
   bool get isZero => false;
 }
 
 /**
- * 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 {
   final int value;
 
   const IntValue(this.value, info) : super(info);
 
   Value operator +(other) {
     if (other.isZero) return this;
     if (other is !IntValue) return other + this;
@@ skipping 345 matching lines @@
   Range.normalize(Value low, Value up, info) : this(
       low == const UnknownValue() ? const MinIntValue() : low,
       up == const UnknownValue() ? const MaxIntValue() : up,
       info);
 
   Range union(Range other) {
     return info.newNormalizedRange(
         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
     // ranges, with priority to [IntValue]s because they are simpler.
     if (low == const UnknownValue()) {
       if (lower is IntValue) low = lower;
       else if (other.lower is IntValue) low = other.lower;
       else low = lower;
     }
     if (up == const UnknownValue()) {
@@ skipping 146 matching lines @@
   }
 
   Range visitPhi(HPhi phi) {
     if (!phi.isInteger()) return info.newUnboundRange();
     // Some phases may replace instructions that change the inputs of
     // this phi. Only the [SsaTypesPropagation] phase will update the
     // phi type. Play it safe by assuming the [SsaTypesPropagation]
     // 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;
     }
 
     Range range = ranges[phi.inputs[0]];
     for (int i = 1; i < phi.inputs.length; i++) {
       range = range.union(ranges[phi.inputs[i]]);
     }
     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;
     Value value = info.newIntValue(constantInt.value);
     return info.newNormalizedRange(value, value);
   }
 
   Range visitFieldGet(HFieldGet fieldGet) {
     if (!fieldGet.isInteger()) return info.newUnboundRange();
     if (!fieldGet.receiver.isIndexable(compiler)) {
@@ skipping 250 matching lines @@
 
     return info.newUnboundRange();
   }
 
   Range visitRangeConversion(HRangeConversion conversion) {
     return ranges[conversion];
   }
 }
 
 /**
- * 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;
       } else {
         phiRange = phiRange.union(inputRange);
       }
     }
     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;
+
+    var other = isLeftLoopPhi ? right : left;
+    // If the analysis already computed range for the update, use it.
+    if (ranges[other] != null) return ranges[other];
+
+    // 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 visitAdd(HAdd operation) {
-    return handleBinaryOperation(operation);
-  }
-
-  Range visitSubtract(HSubtract operation) {
-    return handleBinaryOperation(operation);
-  }
-
-  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;
   }
 }