Move dart2js from sdk/lib/_internal/compiler to pkg/compiler

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

Index: sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart
diff --git a/sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart b/sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart
deleted file mode 100644
index 3b7f3dc312c674a86e8e61218a977153f8980484..0000000000000000000000000000000000000000
--- a/sdk/lib/_internal/compiler/implementation/ssa/value_range_analyzer.dart
+++ /dev/null
@@ -1,1075 +0,0 @@
-// 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;
-
-  IntValue intZero;
-  IntValue intOne;
-
-  ValueRangeInfo(this.constantSystem) {
-    intZero = newIntValue(0);
-    intOne = newIntValue(1);
-  }
-
-  Value newIntValue(int value) {
-    return new IntValue(value, this);
-  }
-
-  Value newInstructionValue(HInstruction instruction) {
-    return new InstructionValue(instruction, this);
-  }
-
-  Value newPositiveValue(HInstruction instruction) {
-    return new PositiveValue(instruction, this);
-  }
-
-  Value newAddValue(Value left, Value right) {
-    return new AddValue(left, right, this);
-  }
-
-  Value newSubtractValue(Value left, Value right) {
-    return new SubtractValue(left, right, this);
-  }
-
-  Value newNegateValue(Value value) {
-    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);
-
-  Value operator +(Value other) => const UnknownValue();
-  Value operator -(Value other) => const UnknownValue();
-  Value operator -()  => const UnknownValue();
-  Value operator &(Value other) => const UnknownValue();
-
-  Value min(Value other) {
-    if (this == other) return this;
-    if (other == const MinIntValue()) return other;
-    if (other == const MaxIntValue()) return this;
-    Value value = this - other;
-    if (value.isPositive) return other;
-    if (value.isNegative) return this;
-    return const UnknownValue();
-  }
-
-  Value max(Value other) {
-    if (this == other) return this;
-    if (other == const MinIntValue()) return this;
-    if (other == const MaxIntValue()) return other;
-    Value value = this - other;
-    if (value.isPositive) return this;
-    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;
-    ConstantSystem constantSystem = info.constantSystem;
-    var constant = constantSystem.add.fold(
-        constantSystem.createInt(value), constantSystem.createInt(other.value));
-    if (!constant.isInt) return const UnknownValue();
-    return info.newIntValue(constant.primitiveValue);
-  }
-
-  Value operator -(other) {
-    if (other.isZero) return this;
-    if (other is !IntValue) return -other + this;
-    ConstantSystem constantSystem = info.constantSystem;
-    var constant = constantSystem.subtract.fold(
-        constantSystem.createInt(value), constantSystem.createInt(other.value));
-    if (!constant.isInt) return const UnknownValue();
-    return info.newIntValue(constant.primitiveValue);
-  }
-
-  Value operator -() {
-    if (isZero) return this;
-    ConstantSystem constantSystem = info.constantSystem;
-    var constant = constantSystem.negate.fold(
-        constantSystem.createInt(value));
-    if (!constant.isInt) return const UnknownValue();
-    return info.newIntValue(constant.primitiveValue);
-  }
-
-  Value operator &(other) {
-    if (other is !IntValue) return const UnknownValue();
-    ConstantSystem constantSystem = info.constantSystem;
-    var constant = constantSystem.bitAnd.fold(
-        constantSystem.createInt(value), constantSystem.createInt(other.value));
-    return info.newIntValue(constant.primitiveValue);
-  }
-
-  Value min(other) {
-    if (other is !IntValue) return other.min(this);
-    return this.value < other.value ? this : other;
-  }
-
-  Value max(other) {
-    if (other is !IntValue) return other.max(this);
-    return this.value < other.value ? other : this;
-  }
-
-  bool operator ==(other) {
-    if (other is !IntValue) return false;
-    return this.value == other.value;
-  }
-
-  int get hashCode => throw new UnsupportedError('IntValue.hashCode');
-
-  String toString() => 'IntValue $value';
-  bool get isNegative => value < 0;
-  bool get isPositive => value >= 0;
-  bool get isZero => value == 0;
-}
-
-/**
- * The [MaxIntValue] represents the maximum value an integer can have,
- * which is currently +infinity.
- */
-class MaxIntValue extends Value {
-  const MaxIntValue() : super(null);
-  Value operator +(Value other) => this;
-  Value operator -(Value other) => this;
-  Value operator -() => const MinIntValue();
-  Value min(Value other) => other;
-  Value max(Value other) => this;
-  String toString() => 'Max';
-  bool get isNegative => false;
-  bool get isPositive => true;
-}
-
-/**
- * The [MinIntValue] represents the minimum value an integer can have,
- * which is currently -infinity.
- */
-class MinIntValue extends Value {
-  const MinIntValue() : super(null);
-  Value operator +(Value other) => this;
-  Value operator -(Value other) => this;
-  Value operator -() => const MaxIntValue();
-  Value min(Value other) => this;
-  Value max(Value other) => other;
-  String toString() => 'Min';
-  bool get isNegative => true;
-  bool get isPositive => false;
-}
-
-/**
- * The [UnknownValue] is the sentinel in our analysis to mark an
- * operation that could not be done because of too much complexity.
- */
-class UnknownValue extends Value {
-  const UnknownValue() : super(null);
-  Value operator +(Value other) => const UnknownValue();
-  Value operator -(Value other) => const UnknownValue();
-  Value operator -() => const UnknownValue();
-  Value min(Value other) => const UnknownValue();
-  Value max(Value other) => const UnknownValue();
-  bool get isNegative => false;
-  bool get isPositive => false;
-  String toString() => 'Unknown';
-}
-
-/**
- * A symbolic value representing an [HInstruction].
- */
-class InstructionValue extends Value {
-  final HInstruction instruction;
-  InstructionValue(this.instruction, info) : super(info);
-
-  bool operator ==(other) {
-    if (other is !InstructionValue) return false;
-    return this.instruction == other.instruction;
-  }
-
-  int get hashCode => throw new UnsupportedError('InstructionValue.hashCode');
-
-  Value operator +(Value other) {
-    if (other.isZero) return this;
-    if (other is IntValue) {
-      if (other.isNegative) {
-        return info.newSubtractValue(this, -other);
-      }
-      return info.newAddValue(this, other);
-    }
-    if (other is InstructionValue) {
-      return info.newAddValue(this, other);
-    }
-    return other + this;
-  }
-
-  Value operator -(Value other) {
-    if (other.isZero) return this;
-    if (this == other) return info.intZero;
-    if (other is IntValue) {
-      if (other.isNegative) {
-        return info.newAddValue(this, -other);
-      }
-      return info.newSubtractValue(this, other);
-    }
-    if (other is InstructionValue) {
-      return info.newSubtractValue(this, other);
-    }
-    return -other + this;
-  }
-
-  Value operator -() {
-    return info.newNegateValue(this);
-  }
-
-  bool get isNegative => false;
-  bool get isPositive => false;
-
-  String toString() => 'Instruction: $instruction';
-}
-
-/**
- * Special value for instructions whose type is a positive integer.
- */
-class PositiveValue extends InstructionValue {
-  PositiveValue(HInstruction instruction, info) : super(instruction, info);
-  bool get isPositive => true;
-}
-
-/**
- * Represents a binary operation on two [Value], where the operation
- * did not yield a canonical value.
- */
-class BinaryOperationValue extends Value {
-  final Value left;
-  final Value right;
-  BinaryOperationValue(this.left, this.right, info) : super(info);
-}
-
-class AddValue extends BinaryOperationValue {
-  AddValue(left, right, info) : super(left, right, info);
-
-  bool operator ==(other) {
-    if (other is !AddValue) return false;
-    return (left == other.left && right == other.right)
-      || (left == other.right && right == other.left);
-  }
-
-  int get hashCode => throw new UnsupportedError('AddValue.hashCode');
-
-  Value operator -() => -left - right;
-
-  Value operator +(Value other) {
-    if (other.isZero) return this;
-    Value value = left + other;
-    if (value != const UnknownValue() && value is! BinaryOperationValue) {
-      return value + right;
-    }
-    // If the result is not simple enough, we try the same approach
-    // with [right].
-    value = right + other;
-    if (value != const UnknownValue() && value is! BinaryOperationValue) {
-      return left + value;
-    }
-    return const UnknownValue();
-  }
-
-  Value operator -(Value other) {
-    if (other.isZero) return this;
-    Value value = left - other;
-    if (value != const UnknownValue() && value is! BinaryOperationValue) {
-      return value + right;
-    }
-    // If the result is not simple enough, we try the same approach
-    // with [right].
-    value = right - other;
-    if (value != const UnknownValue() && value is! BinaryOperationValue) {
-      return left + value;
-    }
-    return const UnknownValue();
-  }
-
-  bool get isNegative => left.isNegative && right.isNegative;
-  bool get isPositive => left.isPositive && right.isPositive;
-  String toString() => '$left + $right';
-}
-
-class SubtractValue extends BinaryOperationValue {
-  SubtractValue(left, right, info) : super(left, right, info);
-
-  bool operator ==(other) {
-    if (other is !SubtractValue) return false;
-    return left == other.left && right == other.right;
-  }
-
-  int get hashCode => throw new UnsupportedError('SubtractValue.hashCode');
-
-  Value operator -() => right - left;
-
-  Value operator +(Value other) {
-    if (other.isZero) return this;
-    Value value = left + other;
-    if (value != const UnknownValue() && value is! BinaryOperationValue) {
-      return value - right;
-    }
-    // If the result is not simple enough, we try the same approach
-    // with [right].
-    value = other - right;
-    if (value != const UnknownValue() && value is! BinaryOperationValue) {
-      return left + value;
-    }
-    return const UnknownValue();
-  }
-
-  Value operator -(Value other) {
-    if (other.isZero) return this;
-    Value value = left - other;
-    if (value != const UnknownValue() && value is! BinaryOperationValue) {
-      return value - right;
-    }
-    // If the result is not simple enough, we try the same approach
-    // with [right].
-    value = right + other;
-    if (value != const UnknownValue() && value is! BinaryOperationValue) {
-      return left - value;
-    }
-    return const UnknownValue();
-  }
-
-  bool get isNegative => left.isNegative && right.isPositive;
-  bool get isPositive => left.isPositive && right.isNegative;
-  String toString() => '$left - $right';
-}
-
-class NegateValue extends Value {
-  final Value value;
-  NegateValue(this.value, info) : super(info);
-
-  bool operator ==(other) {
-    if (other is !NegateValue) return false;
-    return value == other.value;
-  }
-
-  int get hashCode => throw new UnsupportedError('Negate.hashCode');
-
-  Value operator +(other) {
-    if (other.isZero) return this;
-    if (other == value) return info.intZero;
-    if (other is NegateValue) return this - other.value;
-    if (other is IntValue) {
-      if (other.isNegative) {
-        return info.newSubtractValue(this, -other);
-      }
-      return info.newSubtractValue(other, value);
-    }
-    if (other is InstructionValue) {
-      return info.newSubtractValue(other, value);
-    }
-    return other - value;
-  }
-
-  Value operator &(Value other) => const UnknownValue();
-
-  Value operator -(other) {
-    if (other.isZero) return this;
-    if (other is IntValue) {
-      if (other.isNegative) {
-        return info.newSubtractValue(-other, value);
-      }
-      return info.newSubtractValue(this, other);
-    }
-    if (other is InstructionValue) {
-      return info.newSubtractValue(this, other);
-    }
-    if (other is NegateValue) return this + other.value;
-    return -other - value;
-  }
-
-  Value operator -() => value;
-
-  bool get isNegative => value.isPositive;
-  bool get isPositive => value.isNegative;
-  String toString() => '-$value';
-}
-
-/**
- * A [Range] represents the possible integer values an instruction
- * can have, from its [lower] bound to its [upper] bound, both
- * included.
- */
-class Range {
-  final Value lower;
-  final Value upper;
-  final ValueRangeInfo info;
-  Range(this.lower, this.upper, this.info) {
-    assert(lower != const UnknownValue());
-    assert(upper != const UnknownValue());
-  }
-
-  Range.unbound(info) : this(const MinIntValue(), const MaxIntValue(), info);
-
-  /**
-   * Checks if the given values are unknown, and creates a
-   * range that does not have any unknown values.
-   */
-  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) {
-    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()) {
-      if (upper is IntValue) up = upper;
-      else if (other.upper is IntValue) up = other.upper;
-      else up = upper;
-    }
-    return info.newNormalizedRange(low, up);
-  }
-
-  Range operator +(Range other) {
-    return info.newNormalizedRange(lower + other.lower, upper + other.upper);
-  }
-
-  Range operator -(Range other) {
-    return info.newNormalizedRange(lower - other.upper, upper - other.lower);
-  }
-
-  Range operator -() {
-    return info.newNormalizedRange(-upper, -lower);
-  }
-
-  Range operator &(Range other) {
-    if (isSingleValue
-        && other.isSingleValue
-        && lower is IntValue
-        && other.lower is IntValue) {
-      return info.newNormalizedRange(lower & other.lower, upper & other.upper);
-    }
-    if (isPositive && other.isPositive) {
-      Value up = upper.min(other.upper);
-      if (up == const UnknownValue()) {
-        // If we could not find a trivial bound, just try to use the
-        // one that is an int.
-        up = upper is IntValue ? upper : other.upper;
-        // Make sure we get the same upper bound, whether it's a & b
-        // or b & a.
-        if (up is! IntValue && upper != other.upper) up = const MaxIntValue();
-      }
-      return info.newNormalizedRange(info.intZero, up);
-    } else if (isPositive) {
-      return info.newNormalizedRange(info.intZero, upper);
-    } else if (other.isPositive) {
-      return info.newNormalizedRange(info.intZero, other.upper);
-    } else {
-      return info.newUnboundRange();
-    }
-  }
-
-  bool operator ==(other) {
-    if (other is! Range) return false;
-    return other.lower == lower && other.upper == upper;
-  }
-
-  int get hashCode => throw new UnsupportedError('Range.hashCode');
-
-  bool operator <(Range other) {
-    return upper != other.lower && upper.min(other.lower) == upper;
-  }
-
-  bool operator >(Range other) {
-    return lower != other.upper && lower.max(other.upper) == lower;
-  }
-
-  bool operator <=(Range other) {
-    return upper.min(other.lower) == upper;
-  }
-
-  bool operator >=(Range other) {
-    return lower.max(other.upper) == lower;
-  }
-
-  bool get isNegative => upper.isNegative;
-  bool get isPositive => lower.isPositive;
-  bool get isSingleValue => lower == upper;
-
-  String toString() => '[$lower, $upper]';
-}
-
-/**
- * Visits the graph in dominator order, and computes value ranges for
- * integer instructions. While visiting the graph, this phase also
- * removes unnecessary bounds checks, and comparisons that are proven
- * to be true or false.
- */
-class SsaValueRangeAnalyzer extends HBaseVisitor implements OptimizationPhase {
-  String get name => 'SSA value range builder';
-
-  /**
-   * List of [HRangeConversion] instructions created by the phase. We
-   * save them here in order to remove them once the phase is done.
-   */
-  final List<HRangeConversion> conversions = <HRangeConversion>[];
-
-  /**
-   * Value ranges for integer instructions. This map gets populated by
-   * the dominator tree visit.
-   */
-  final Map<HInstruction, Range> ranges = new Map<HInstruction, Range>();
-
-  final Compiler compiler;
-  final ConstantSystem constantSystem;
-  final ValueRangeInfo info;
-
-  CodegenWorkItem work;
-  HGraph graph;
-
-  SsaValueRangeAnalyzer(this.compiler, constantSystem, this.work)
-      : info = new ValueRangeInfo(constantSystem),
-        this.constantSystem = constantSystem;
-
-  void visitGraph(HGraph graph) {
-    this.graph = graph;
-    visitDominatorTree(graph);
-    // We remove the range conversions after visiting the graph so
-    // that the graph does not get polluted with these instructions
-    // only necessary for this phase.
-    removeRangeConversion();
-    JavaScriptBackend backend = compiler.backend;
-    // TODO(herhut): Find a cleaner way to pass around ranges.
-    backend.optimizer.ranges = ranges;
-  }
-
-  void removeRangeConversion() {
-    conversions.forEach((HRangeConversion instruction) {
-      instruction.block.rewrite(instruction, instruction.inputs[0]);;
-      instruction.block.remove(instruction);
-    });
-  }
-
-  void visitBasicBlock(HBasicBlock block) {
-
-    void visit(HInstruction instruction) {
-      Range range = instruction.accept(this);
-      if (instruction.isInteger(compiler)) {
-        assert(range != null);
-        ranges[instruction] = range;
-      }
-    }
-
-    block.forEachPhi(visit);
-    block.forEachInstruction(visit);
-  }
-
-  Range visitInstruction(HInstruction instruction) {
-    if (instruction.isPositiveInteger(compiler)) {
-      return info.newNormalizedRange(
-          info.intZero, info.newPositiveValue(instruction));
-    } else if (instruction.isInteger(compiler)) {
-      InstructionValue value = info.newInstructionValue(instruction);
-      return info.newNormalizedRange(value, value);
-    } else {
-      return info.newUnboundRange();
-    }
-  }
-
-  Range visitPhi(HPhi phi) {
-    if (!phi.isInteger(compiler)) 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(compiler))) {
-      return info.newUnboundRange();
-    }
-    if (phi.block.isLoopHeader()) {
-      Range range = new LoopUpdateRecognizer(compiler, ranges, info).run(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 visitConstant(HConstant hConstant) {
-    if (!hConstant.isInteger(compiler)) return info.newUnboundRange();
-    ConstantValue constant = hConstant.constant;
-    NumConstantValue constantNum;
-    if (constant is DeferredConstantValue) {
-      constantNum = constant.referenced;
-    } else {
-      constantNum = constant;
-    }
-    if (constantNum.isMinusZero) constantNum = new IntConstantValue(0);
-    Value value = info.newIntValue(constantNum.primitiveValue);
-    return info.newNormalizedRange(value, value);
-  }
-
-  Range visitFieldGet(HFieldGet fieldGet) {
-    if (!fieldGet.isInteger(compiler)) return info.newUnboundRange();
-    if (!fieldGet.receiver.isIndexablePrimitive(compiler)) {
-      return visitInstruction(fieldGet);
-    }
-    JavaScriptBackend backend = compiler.backend;
-    assert(fieldGet.element == backend.jsIndexableLength);
-    PositiveValue value = info.newPositiveValue(fieldGet);
-    // We know this range is above zero. To simplify the analysis, we
-    // put the zero value as the lower bound of this range. This
-    // allows to easily remove the second bound check in the following
-    // expression: a[1] + a[0].
-    return info.newNormalizedRange(info.intZero, value);
-  }
-
-  Range visitBoundsCheck(HBoundsCheck check) {
-    // Save the next instruction, in case the check gets removed.
-    HInstruction next = check.next;
-    Range indexRange = ranges[check.index];
-    Range lengthRange = ranges[check.length];
-    if (indexRange == null) {
-      indexRange = info.newUnboundRange();
-      assert(!check.index.isInteger(compiler));
-    }
-    assert(check.length.isInteger(compiler));
-
-    // Check if the index is strictly below the upper bound of the length
-    // range.
-    Value maxIndex = lengthRange.upper - info.intOne;
-    bool belowLength = maxIndex != const MaxIntValue()
-        && indexRange.upper.min(maxIndex) == indexRange.upper;
-
-    // Check if the index is strictly below the lower bound of the length
-    // range.
-    belowLength = belowLength
-        || (indexRange.upper != lengthRange.lower
-            && indexRange.upper.min(lengthRange.lower) == indexRange.upper);
-    if (indexRange.isPositive && belowLength) {
-      check.block.rewrite(check, check.index);
-      check.block.remove(check);
-    } else if (indexRange.isNegative || lengthRange < indexRange) {
-      check.staticChecks = HBoundsCheck.ALWAYS_FALSE;
-      // The check is always false, and whatever instruction it
-      // dominates is dead code.
-      return indexRange;
-    } else if (indexRange.isPositive) {
-      check.staticChecks = HBoundsCheck.ALWAYS_ABOVE_ZERO;
-    } else if (belowLength) {
-      check.staticChecks = HBoundsCheck.ALWAYS_BELOW_LENGTH;
-    }
-
-    if (indexRange.isPositive) {
-      // If the test passes, we know the lower bound of the length is
-      // greater or equal than the lower bound of the index.
-      Value low = lengthRange.lower.max(indexRange.lower);
-      if (low != const UnknownValue()) {
-        HInstruction instruction =
-            createRangeConversion(next, check.length);
-        ranges[instruction] = info.newNormalizedRange(low, lengthRange.upper);
-      }
-    }
-
-    // Update the range of the index if using the maximum index
-    // narrows it. Use that new range for this instruction as well.
-    Range newIndexRange = indexRange.intersection(
-        info.newNormalizedRange(info.intZero, maxIndex));
-    if (indexRange == newIndexRange) return indexRange;
-    // Explicitly attach the range information to the index instruction,
-    // which may be used by other instructions.  Returning the new range will
-    // attach it to this instruction.
-    HInstruction instruction = createRangeConversion(next, check.index);
-    ranges[instruction] = newIndexRange;
-    return newIndexRange;
-  }
-
-  Range visitRelational(HRelational relational) {
-    HInstruction right = relational.right;
-    HInstruction left = relational.left;
-    if (!left.isInteger(compiler)) return info.newUnboundRange();
-    if (!right.isInteger(compiler)) return info.newUnboundRange();
-    BinaryOperation operation = relational.operation(constantSystem);
-    Range rightRange = ranges[relational.right];
-    Range leftRange = ranges[relational.left];
-
-    if (relational is HIdentity) {
-      handleEqualityCheck(relational);
-    } else if (operation.apply(leftRange, rightRange)) {
-      relational.block.rewrite(
-          relational, graph.addConstantBool(true, compiler));
-      relational.block.remove(relational);
-    } else if (negateOperation(operation).apply(leftRange, rightRange)) {
-      relational.block.rewrite(
-          relational, graph.addConstantBool(false, compiler));
-      relational.block.remove(relational);
-    }
-    return info.newUnboundRange();
-  }
-
-  void handleEqualityCheck(HRelational node) {
-    Range right = ranges[node.right];
-    Range left = ranges[node.left];
-    if (left.isSingleValue && right.isSingleValue && left == right) {
-      node.block.rewrite(
-          node, graph.addConstantBool(true, compiler));
-      node.block.remove(node);
-    }
-  }
-
-  Range handleInvokeModulo(HInvokeDynamicMethod invoke) {
-    HInstruction left = invoke.inputs[1];
-    HInstruction right = invoke.inputs[2];
-    Range divisor = ranges[right];
-    if (divisor != null) {
-      // For Integer values we can be precise in the upper bound,
-      // so special case those.
-      if (left.isInteger(compiler) && right.isInteger(compiler)) {
-        if (divisor.isPositive) {
-          return info.newNormalizedRange(info.intZero, divisor.upper -
-              info.intOne);
-        } else if (divisor.isNegative) {
-          return info.newNormalizedRange(info.intZero, info.newNegateValue(
-              divisor.lower) - info.intOne);
-        }
-      } else if (left.isNumber(compiler) && right.isNumber(compiler)) {
-        if (divisor.isPositive) {
-          return info.newNormalizedRange(info.intZero, divisor.upper);
-        } else if (divisor.isNegative) {
-          return info.newNormalizedRange(info.intZero, info.newNegateValue(
-              divisor.lower));
-        }
-      }
-    }
-    return info.newUnboundRange();
-  }
-
-  Range visitInvokeDynamicMethod(HInvokeDynamicMethod invoke) {
-    if ((invoke.inputs.length == 3) && (invoke.selector.name == "%"))
-      return handleInvokeModulo(invoke);
-    return super.visitInvokeDynamicMethod(invoke);
-  }
-
-  Range handleBinaryOperation(HBinaryArithmetic instruction) {
-    if (!instruction.isInteger(compiler)) return info.newUnboundRange();
-    return instruction.operation(constantSystem).apply(
-        ranges[instruction.left], ranges[instruction.right]);
-  }
-
-  Range visitAdd(HAdd add) {
-    return handleBinaryOperation(add);
-  }
-
-  Range visitSubtract(HSubtract sub) {
-    return handleBinaryOperation(sub);
-  }
-
-  Range visitBitAnd(HBitAnd node) {
-    if (!node.isInteger(compiler)) return info.newUnboundRange();
-    HInstruction right = node.right;
-    HInstruction left = node.left;
-    if (left.isInteger(compiler) && right.isInteger(compiler)) {
-      return ranges[left] & ranges[right];
-    }
-
-    Range tryComputeRange(HInstruction instruction) {
-      Range range = ranges[instruction];
-      if (range.isPositive) {
-        return info.newNormalizedRange(info.intZero, range.upper);
-      } else if (range.isNegative) {
-        return info.newNormalizedRange(range.lower, info.intZero);
-      }
-      return info.newUnboundRange();
-    }
-
-    if (left.isInteger(compiler)) {
-      return tryComputeRange(left);
-    } else if (right.isInteger(compiler)) {
-      return tryComputeRange(right);
-    }
-    return info.newUnboundRange();
-  }
-
-  Range visitCheck(HCheck instruction) {
-    if (ranges[instruction.checkedInput] == null) {
-      return visitInstruction(instruction);
-    }
-    return ranges[instruction.checkedInput];
-  }
-
-  HInstruction createRangeConversion(HInstruction cursor,
-                                     HInstruction instruction) {
-    JavaScriptBackend backend = compiler.backend;
-    HRangeConversion newInstruction =
-        new HRangeConversion(instruction, backend.intType);
-    conversions.add(newInstruction);
-    cursor.block.addBefore(cursor, newInstruction);
-    // Update the users of the instruction dominated by [cursor] to
-    // use the new instruction, that has an narrower range.
-    instruction.replaceAllUsersDominatedBy(cursor, newInstruction);
-    return newInstruction;
-  }
-
-  static BinaryOperation negateOperation(BinaryOperation operation) {
-    if (operation == const LessOperation()) {
-      return const GreaterEqualOperation();
-    } else if (operation == const LessEqualOperation()) {
-      return const GreaterOperation();
-    } else if (operation == const GreaterOperation()) {
-      return const LessEqualOperation();
-    } else if (operation == const GreaterEqualOperation()) {
-      return const LessOperation();
-    } else {
-      return null;
-    }
-  }
-
-  static BinaryOperation flipOperation(BinaryOperation operation) {
-    if (operation == const LessOperation()) {
-      return const GreaterOperation();
-    } else if (operation == const LessEqualOperation()) {
-      return const GreaterEqualOperation();
-    } else if (operation == const GreaterOperation()) {
-      return const LessOperation();
-    } else if (operation == const GreaterEqualOperation()) {
-      return const LessEqualOperation();
-    } else {
-      return null;
-    }
-  }
-
-  Range computeConstrainedRange(BinaryOperation operation,
-                                Range leftRange,
-                                Range rightRange) {
-    Range range;
-    if (operation == const LessOperation()) {
-      range = info.newNormalizedRange(
-          const MinIntValue(), rightRange.upper - info.intOne);
-    } else if (operation == const LessEqualOperation()) {
-      range = info.newNormalizedRange(const MinIntValue(), rightRange.upper);
-    } else if (operation == const GreaterOperation()) {
-      range = info.newNormalizedRange(
-          rightRange.lower + info.intOne, const MaxIntValue());
-    } else if (operation == const GreaterEqualOperation()) {
-      range = info.newNormalizedRange(rightRange.lower, const MaxIntValue());
-    } else {
-      range = info.newUnboundRange();
-    }
-    return range.intersection(leftRange);
-  }
-
-  Range visitConditionalBranch(HConditionalBranch branch) {
-    var condition = branch.condition;
-    // TODO(ngeoffray): Handle complex conditions.
-    if (condition is !HRelational) return info.newUnboundRange();
-    if (condition is HIdentity) return info.newUnboundRange();
-    HInstruction right = condition.right;
-    HInstruction left = condition.left;
-    if (!left.isInteger(compiler)) return info.newUnboundRange();
-    if (!right.isInteger(compiler)) return info.newUnboundRange();
-
-    Range rightRange = ranges[right];
-    Range leftRange = ranges[left];
-    Operation operation = condition.operation(constantSystem);
-    Operation mirrorOp = flipOperation(operation);
-    // Only update the true branch if this block is the only
-    // predecessor.
-    if (branch.trueBranch.predecessors.length == 1) {
-      assert(branch.trueBranch.predecessors[0] == branch.block);
-      // Update the true branch to use narrower ranges for [left] and
-      // [right].
-      Range range = computeConstrainedRange(operation, leftRange, rightRange);
-      if (leftRange != range) {
-        HInstruction instruction =
-            createRangeConversion(branch.trueBranch.first, left);
-        ranges[instruction] = range;
-      }
-
-      range = computeConstrainedRange(mirrorOp, rightRange, leftRange);
-      if (rightRange != range) {
-        HInstruction instruction =
-            createRangeConversion(branch.trueBranch.first, right);
-        ranges[instruction] = range;
-      }
-    }
-
-    // Only update the false branch if this block is the only
-    // predecessor.
-    if (branch.falseBranch.predecessors.length == 1) {
-      assert(branch.falseBranch.predecessors[0] == branch.block);
-      Operation reverse = negateOperation(operation);
-      Operation reversedMirror = flipOperation(reverse);
-      // Update the false branch to use narrower ranges for [left] and
-      // [right].
-      Range range = computeConstrainedRange(reverse, leftRange, rightRange);
-      if (leftRange != range) {
-        HInstruction instruction =
-            createRangeConversion(branch.falseBranch.first, left);
-        ranges[instruction] = range;
-      }
-
-      range = computeConstrainedRange(reversedMirror, rightRange, leftRange);
-      if (rightRange != range) {
-        HInstruction instruction =
-            createRangeConversion(branch.falseBranch.first, right);
-        ranges[instruction] = range;
-      }
-    }
-
-    return info.newUnboundRange();
-  }
-
-  Range visitRangeConversion(HRangeConversion conversion) {
-    return ranges[conversion];
-  }
-}
-
-/**
- * Tries to find a range for the update instruction of a loop phi.
- */
-class LoopUpdateRecognizer extends HBaseVisitor {
-  final Compiler compiler;
-  final Map<HInstruction, Range> ranges;
-  final ValueRangeInfo info;
-  LoopUpdateRecognizer(this.compiler, 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]];
-    // If the lower (respectively upper) value is the marker, we know
-    // the loop does not change it, so we can just use the
-    // [startRange]'s lower (upper) value. Otherwise the lower (upper) value
-    // is the minimum of the [startRange]'s lower (upper) and the
-    // [updateRange]'s lower (upper).
-    Value low = updateRange.lower is MarkerValue
-        ? startRange.lower
-        : updateRange.lower.min(startRange.lower);
-    Value up = updateRange.upper is MarkerValue
-        ? startRange.upper
-        : updateRange.upper.max(startRange.upper);
-    return info.newNormalizedRange(low, up);
-  }
-
-  Range visit(HInstruction instruction) {
-    if (!instruction.isInteger(compiler)) return null;
-    if (ranges[instruction] != null) return ranges[instruction];
-    return instruction.accept(this);
-  }
-
-  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);
-      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);
-  }
-
-  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);
-  }
-}