Add a value range analysis phase to remove bounds checks.

lib/compiler/implementation/ssa/value_range_analyzer.dart

Index: lib/compiler/implementation/ssa/value_range_analyzer.dart
===================================================================
--- lib/compiler/implementation/ssa/value_range_analyzer.dart	(revision 0)
+++ lib/compiler/implementation/ssa/value_range_analyzer.dart	(revision 0)
@@ -0,0 +1,616 @@
+// 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.
+
+/**
+ * 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 {
+  const Value();
+
+  Value operator +(Value other);
+  Value operator -(Value other);
+  Value operator &(Value other);
+
+  Value min(Value other) {
+    if (this == other) return this;
+    if (other == const MinValue()) return other;
+    if (other == const MaxValue()) 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 MinValue()) return this;
+    if (other == const MaxValue()) return other;
+    Value value = this - other;
+    if (value.isPositive()) return this;
+    if (value.isNegative()) return other;
+    return const UnknownValue();
+  }
+
+  bool isNegative() => false;
+  bool isPositive() => false;
+  bool isZero() => false;
+}
+
+/**
+ * An [IntValue] contains a constant integer value.
+ */
+class IntValue extends Value {
+  final int value;
+  const IntValue(this.value);
+
+  Value operator +(other) {
+    if (other is !IntValue) return other + this;
+    return new IntValue(value + other.value);
+  }
+
+  Value operator -(other) {
+    if (other is !IntValue) return other - this;
+    return new IntValue(value - other.value);
+  }
+
+  Value operator &(other) {
+    if (other is !IntValue) return this;
+    return new IntValue(value & other.value);
+  }
+
+  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;
+  }
+
+  String toString() => 'IntValue $value';
+  bool isNegative() => value < 0;
+  bool isPositive() => value >= 0;
+  bool isZero() => value == 0;
+}
+
+/**
+ * The [MaxValue] represents the maximum value an integer can have,
+ * which is currently +infinity.
+ */
+class MaxValue extends Value {

[Søren Gjesse, 2012/09/26 09:08:24]

Should this maybe be called MaxIntValue and extend IntValue instead (then it
should implement isZero)?

[ngeoffray, 2012/09/26 09:33:26]

Renaming is fine, but if it extends IntValue what value would you put in the
[value] field? Also, all values here a re "int" values, so would you prefer if
IntValue was renamed to ConcreteIntValue?

[Søren Gjesse, 2012/09/26 14:00:15]

Another alternative is to have AbstractIntValue with subclasses IntValue,
MaxIntValue and MinIntValue. But then AbstractIntValue does not add much.

Thinking about it maybe the comments for MaxValue and MinValue should just be
changed to not mention integer. As far as I can see they could be used with
doubles as well if we where to start tracking double value ranges.

Then IntValue should be abstract then without the value field with 

[ngeoffray, 2012/09/27 13:22:02]

Let's rename MaxValue and MinValue to MaxIntValue and MinIntValue for now. I'd
prefer not to take decisions on what things we might implement in the future.

+  const MaxValue();
+  Value operator +(Value other) => this;
+  Value operator -(Value other) => this;
+  Value operator &(Value other) {
+    if (other.isPositive()) return other;
+    if (other.isNegative()) return const IntValue(0);
+    return this;
+  }
+  Value min(Value other) => other;
+  Value max(Value other) => this;
+  String toString() => 'Max';
+  bool isNegative() => false;
+  bool isPositive() => true;
+}
+
+/**
+ * The [MinValue] represents the minimum value an integer can have,
+ * which is currently -infinity.
+ */
+class MinValue extends Value {

[Søren Gjesse, 2012/09/26 09:08:24]

MinIntValue?

+  const MinValue();
+  Value operator +(Value other) => this;
+  Value operator -(Value other) => this;
+  Value operator &(Value other) {
+    if (other.isPositive()) return const IntValue(0);
+    if (other.isNegative()) return other;
+    return this;
+  }
+  Value min(Value other) => this;
+  Value max(Value other) => other;
+  String toString() => 'Min';
+  bool isNegative() => true;
+  bool 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();
+  Value operator +(Value other) => const UnknownValue();
+  Value operator -(Value other) => const UnknownValue();
+  Value operator &(Value other) => const UnknownValue();
+  Value min(Value other) => const UnknownValue();
+  Value max(Value other) => const UnknownValue();
+  bool isNegative() => false;
+  bool isPositive() => false;
+  String toString() => 'Unknown';
+}
+
+/**
+ * A symbolic value representing an [HInstruction].
+ */
+class InstructionValue extends Value {
+  final HInstruction instruction;
+  InstructionValue(this.instruction);
+
+  bool operator ==(other) {
+    if (other is !InstructionValue) return false;
+    return this.instruction == other.instruction;
+  }
+
+  Value operator +(Value other) {
+    if (other.isZero()) return this;
+    return new OperationValue(this, other, const AddOperation());
+  }
+
+  Value operator -(Value other) {
+    if (other.isZero()) return this;
+    if (this == other) return const IntValue(0);
+    return new OperationValue(this, other, const SubtractOperation());
+  }
+
+  Value operator &(Value other) {
+    if (other is IntValue) return other & this;
+    return this;
+  }
+
+  bool isNegative() => false;
+  bool isPositive() => false;
+
+  String toString() => 'Instruction: $instruction';
+}
+
+/**
+ * Special value for instructions that represent the length of an
+ * array. The difference with an [InstructionValue] is that we know
+ * the value is positive.
+ */
+class LengthValue extends InstructionValue {
+  LengthValue(HInstruction instruction) : super(instruction);
+  bool isPositive() => true;
+  String toString() => 'Length: $instruction';
+}
+
+/**
+ * Represents a binary operation on two [Value], where the operation
+ * did not yield a canonical value.
+ */
+class OperationValue extends Value {
+  final Value left;
+  final Value right;
+  final Operation operation;
+  OperationValue(this.left, this.right, this.operation);
+
+  bool operator ==(other) {
+    if (other is !OperationValue) return false;
+    return left == other.left
+        && right == other.right
+        && operation == other.operation;
+  }
+
+  Value operator +(Value other) => const UnknownValue();
+  Value operator &(Value other) => const UnknownValue();
+
+  Value operator -(Value other) {

[Søren Gjesse, 2012/09/26 09:08:24]

Could you please explain how this works?

[ngeoffray, 2012/09/26 09:33:26]

Done.

+    Value value = left - other;
+    if (value != const UnknownValue() && value is! OperationValue) {
+      return operation.apply(value, right);
+    }
+    value = right - other;
+    if (value != const UnknownValue() && value is! OperationValue) {
+      return operation.apply(left, value);
+    }
+    return const UnknownValue();
+  }
+
+  bool isNegative() => false;
+  bool isPositive() => false;
+  String toString() => '$left ${operation.name} $right';
+}
+
+/**
+ * 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;
+  const Range([this.lower = const MinValue(), this.upper = const MaxValue()]);
+
+  /**
+   * Checks if the range has UnknownValue as bounds, and returns a
+   * range that does not have any.
+   */
+  Range normalize() {
+    if (lower != const UnknownValue() && upper != const UnknownValue()) {
+      return this;
+    }
+    Value low = lower == const UnknownValue() ? const MinValue() : lower;
+    Value up = upper == const UnknownValue() ? const MaxValue() : upper;
+    return new Range(low, up);
+  }
+
+  Range union(Range other) {
+    Range range = new Range(lower.min(other.lower), upper.max(other.upper));

[Søren Gjesse, 2012/09/26 09:08:24]

Maybe add Range.normalize constructor.

[ngeoffray, 2012/09/26 09:33:26]

Good point. Done.

+    return range.normalize();
+  }
+
+  intersection(Range other) {
+    Range range = new Range(lower.max(other.lower), upper.min(other.upper));
+    return range.normalize();
+  }
+
+  Range operator +(Range other) {
+    Range range = new Range(lower + other.lower, upper + other.upper);
+    return range.normalize();
+  }
+
+  Range operator -(Range other) {
+    Range range = new Range(lower - other.lower, upper - other.upper);
+    return range.normalize();
+  }
+
+  Range operator &(Range other) {
+    Range range = new Range(lower & other.lower, upper & other.upper);
+    return range.normalize();
+  }
+
+  bool operator ==(other) {
+    if (other is! Range) return false;
+    return other.lower == lower && other.upper == upper;
+  }
+
+  bool isLessThan(Range other) {
+    return upper != other.lower && upper.min(other.lower) == upper;
+  }
+
+  bool isNegative() => upper.isNegative();
+  bool isPositive() => lower.isPositive();
+
+  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 ConstantSystem constantSystem;
+  final HTypeMap types;
+  WorkItem work;
+  HGraph graph;
+
+  SsaValueRangeAnalyzer(this.constantSystem, this.types, WorkItem this.work);
+
+  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();
+  }
+
+  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(types)) {
+        assert(range != null);
+        ranges[instruction] = range;
+      }
+    }
+
+    block.forEachPhi(visit);
+    block.forEachInstruction(visit);
+  }
+
+  Range visitInstruction(HInstruction instruction) {
+    return const Range(const MinValue(), const MaxValue());

[Søren Gjesse, 2012/09/26 09:08:24]

What is the difference between returning null and returning an unbounded range?

[ngeoffray, 2012/09/26 09:33:26]

It's to make sure an instruction that has type int gets a range. See assert line
335. I agree it doesn't look nice, so maybe I could just get rid of that assert
and create a [min,max] range if range is null. WDYT?

[Søren Gjesse, 2012/09/26 14:00:15]

I think returning the [min,max] range instead of null will look better. Another
option will be to return null here if the instruction does not have type
integer.

+  }
+
+  Range visitParameterValue(HParameterValue parameter) {
+    if (!parameter.isInteger(types)) return null;
+    Value value = new InstructionValue(parameter);
+    return new Range(value, value);
+  }
+
+  Range visitPhi(HPhi phi) {
+    if (!phi.isInteger(types)) return null;
+    if (phi.block.isLoopHeader()) {
+      Range range = tryInferLoopPhiRange(phi);
+      if (range == null) return visitInstruction(phi);
+      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, types));
+  }
+
+  Range visitConstant(HConstant constant) {
+    if (!constant.isInteger(types)) return null;
+    Value value = new IntValue(constant.constant.value);
+    return new Range(value, value);
+  }
+
+  Range visitInvokeInterceptor(HInvokeInterceptor interceptor) {
+    if (!interceptor.isInteger(types)) return null;
+    if (!interceptor.isLengthGetterOnStringOrArray(types)) {
+      return visitInstruction(interceptor);
+    }
+    LengthValue value = new LengthValue(interceptor);
+    return new Range(value, value);
+  }
+
+  bool handleBoundsCheck(HBoundsCheck check) {
+    Range indexRange = ranges[check.index];
+    Range lengthRange = ranges[check.length];
+    Value maxIndex = lengthRange.upper - const IntValue(1);
+    bool belowLength = maxIndex != const MaxValue()
+        && indexRange.upper.min(maxIndex) == indexRange.upper;
+    if (indexRange.isPositive() && belowLength) {
+      check.block.rewrite(check, check.index);
+      check.block.remove(check);
+      return true;
+    } else if (indexRange.isNegative() || lengthRange.isLessThan(indexRange)) {
+      check.staticChecks = HBoundsCheck.ALWAYS_FALSE;
+    } else if (indexRange.isPositive()) {
+      check.staticChecks = HBoundsCheck.ALWAYS_ABOVE_ZERO;
+    } else if (belowLength) {
+      check.staticChecks = HBoundsCheck.ALWAYS_BELOW_LENGTH;
+    }
+    return false;
+  }
+
+  Range visitBoundsCheck(HBoundsCheck check) {
+    HInstruction next = check.next;
+    Range indexRange = ranges[check.index];
+    Range lengthRange = ranges[check.length];
+    if (handleBoundsCheck(check)) return indexRange;
+    // Update the range of the index.
+    Range newIndexRange = indexRange.intersection(lengthRange);
+    if (indexRange == newIndexRange) return indexRange;
+    HInstruction instruction = createRangeConversion(check.next, check.index);
+    ranges[instruction] = newIndexRange;
+    return newIndexRange;
+  }
+
+  Range visitLess(HLess less) {
+    HInstruction right = less.right;
+    HInstruction left = less.left;
+    if (!left.isInteger(types)) return null;
+    if (!right.isInteger(types)) return null;
+    if (ranges[left].isLessThan(ranges[right])) {
+      less.block.rewrite(less, graph.addConstantBool(true, constantSystem));
+      less.block.remove(less);
+      return null;
+    }
+    if (ranges[right].isLessThan(ranges[left])) {
+      less.block.rewrite(less, graph.addConstantBool(false, constantSystem));
+      less.block.remove(less);
+      return null;
+    }

[Søren Gjesse, 2012/09/26 09:08:24]

Missing explicit return.

[ngeoffray, 2012/09/26 09:33:26]

Done.

+  }
+
+  Range handleBinaryOperation(HBinaryArithmetic instruction) {
+    if (!instruction.isInteger(types)) return null;
+    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(types)) return null;
+    HInstruction right = node.right;
+    HInstruction left = node.left;
+    if (left.isInteger(types) && right.isInteger(types)) {
+      return ranges[left] & ranges[right];
+    }
+
+    Range tryComputeRange(HInstruction instruction) {
+      Range range = ranges[instruction];
+      if (range.isPositive()) {
+        return new Range(const IntValue(0), range.upper);
+      } else if (range.isNegative()) {
+        return new Range(range.lower, const IntValue(0));
+      }
+      return visitInstruction(node);
+    }
+
+    if (left.isInteger(types)) {
+      return tryComputeRange(left);
+    } else if (right.isInteger(types)) {
+      return tryComputeRange(right);
+    }
+    return visitInstruction(node);
+  }
+
+  Range visitCheck(HCheck instruction) {
+    if (ranges[instruction.checkedInput] == null) {
+      return visitInstruction(instruction);
+    }
+    return ranges[instruction.checkedInput];
+  }
+
+  HInstruction createRangeConversion(HInstruction cursor,
+                                     HInstruction instruction) {
+    HRangeConversion newInstruction = new HRangeConversion(instruction);
+    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.
+    Set<HInstruction> dominatedUsers = instruction.dominatedUsers(cursor);
+    for (HInstruction user in dominatedUsers) {
+      user.changeUse(instruction, newInstruction);
+    }
+    return newInstruction;
+  }
+
+  Range visitConditionalBranch(HConditionalBranch branch) {
+    var condition = branch.condition;
+    // TODO(ngeoffray): Handle more condition kinds.
+    if (condition is !HLess) return null;
+    HInstruction right = condition.right;
+    HInstruction left = condition.left;
+    if (!left.isInteger(types)) return null;
+    if (!right.isInteger(types)) return null;
+
+    // Update the true branch to use a narrower range for [left].
+    // TODO(ngeoffray): Also do it for [right].
+    HInstruction instruction =
+        createRangeConversion(branch.trueBranch.first, left);
+    Range range = new Range(
+        const MinValue(), ranges[right].upper - const IntValue(1));
+    range = range.intersection(ranges[left]);
+    ranges[instruction] = range;
+
+    // Update the false branch to use a narrower range for [left].
+    // TODO(ngeoffray): Also do it for [right].
+    instruction = createRangeConversion(branch.falseBranch.first, left);
+    range = new Range(ranges[right].lower, const MaxValue());
+    range = range.intersection(ranges[left]);
+    ranges[instruction] = range;
+
+    return null;
+  }
+
+  Range visitRangeConversion(HRangeConversion conversion) {
+    return ranges[conversion];
+  }
+}
+
+/**
+ * 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 HTypeMap types;
+  LoopUpdateRecognizer(this.loopPhi, this.ranges, this.types);
+
+  Range visitAdd(HAdd operation) {
+    Range range = getRangeForRecognizableOperation(operation);
+    if (range == null) return null;
+    Range initial = ranges[loopPhi.inputs[0]];
+    if (range.isPositive()) {
+      return new Range(initial.lower, const MaxValue());
+    } else if (range.isNegative()) {
+      return new Range(const MinValue(), initial.upper);
+    }

[Søren Gjesse, 2012/09/26 09:08:24]

Missing explicit "return null" here.

[ngeoffray, 2012/09/26 09:33:26]

Done.

+  }
+
+  Range visitSubtract(HSubtract operation) {
+    Range range = getRangeForRecognizableOperation(operation);
+    if (range == null) return null;
+    Range initial = ranges[loopPhi.inputs[0]];
+    if (range.isPositive()) {
+      return new Range(const MinValue(), initial.upper);
+    } else if (range.isNegative()) {
+      return new Range(initial.lower, const MaxValue());
+    }
+    return null;
+  }
+
+  Range visitPhi(HPhi phi) {
+    // If one of the inputs is the loop phi, then we're only
+    // interested in the other input: a loop phi feeding itself means
+    // it is not being updated.
+    if (unwrap(phi.inputs[0]) == loopPhi) return phi.inputs[1].accept(this);
+    if (unwrap(phi.inputs[1]) == loopPhi) return phi.inputs[0].accept(this);
+    assert(phi.inputs.length == 2);

[Søren Gjesse, 2012/09/26 09:08:24]

Ditto.

[ngeoffray, 2012/09/26 09:33:26]

Done.

+  }
+
+  Range getRangeForRecognizableOperation(HBinaryArithmetic operation) {
+    if (!operation.left.isInteger(types)) return null;
+    if (!operation.right.isInteger(types)) 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 = new IntValue(other.constant.value);
+      return new Range(value, value);
+    }
+    return null;
+  }
+
+  /**
+   * [HCheck] instructions may check the loop phi. Since we only
+   * recognize updated on the loop phi, we must [unwrap] the [HCheck]

[Søren Gjesse, 2012/09/26 09:08:24]

updated -> updates

[ngeoffray, 2012/09/26 09:33:26]

Done.

+   * 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;
+  }
+}