Add a value range analysis phase to remove bounds checks.

lib/compiler/implementation/ssa/nodes.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.
 
 abstract class HVisitor<R> {
   R visitAdd(HAdd node);
   R visitBailoutTarget(HBailoutTarget node);
   R visitBitAnd(HBitAnd node);
   R visitBitNot(HBitNot node);
   R visitBitOr(HBitOr node);
@@ skipping 33 matching lines @@
   R visitLocalGet(HLocalGet node);
   R visitLocalSet(HLocalSet node);
   R visitLocalValue(HLocalValue node);
   R visitLoopBranch(HLoopBranch node);
   R visitModulo(HModulo node);
   R visitMultiply(HMultiply node);
   R visitNegate(HNegate node);
   R visitNot(HNot node);
   R visitParameterValue(HParameterValue node);
   R visitPhi(HPhi node);
+  R visitRangeConversion(HRangeConversion node);
   R visitReturn(HReturn node);
   R visitShiftLeft(HShiftLeft node);
   R visitShiftRight(HShiftRight node);
   R visitStatic(HStatic node);
   R visitStaticStore(HStaticStore node);
   R visitStringConcat(HStringConcat node);
   R visitSubtract(HSubtract node);
   R visitSwitch(HSwitch node);
   R visitThis(HThis node);
   R visitThrow(HThrow node);
@@ skipping 244 matching lines @@
   visitLocalGet(HLocalGet node) => visitFieldGet(node);
   visitLocalSet(HLocalSet node) => visitFieldSet(node);
   visitLocalValue(HLocalValue node) => visitInstruction(node);
   visitLoopBranch(HLoopBranch node) => visitConditionalBranch(node);
   visitModulo(HModulo node) => visitBinaryArithmetic(node);
   visitNegate(HNegate node) => visitInvokeUnary(node);
   visitNot(HNot node) => visitInstruction(node);
   visitPhi(HPhi node) => visitInstruction(node);
   visitMultiply(HMultiply node) => visitBinaryArithmetic(node);
   visitParameterValue(HParameterValue node) => visitLocalValue(node);
+  visitRangeConversion(HRangeConversion node) => visitCheck(node);
   visitReturn(HReturn node) => visitControlFlow(node);
   visitShiftRight(HShiftRight node) => visitBinaryBitOp(node);
   visitShiftLeft(HShiftLeft node) => visitBinaryBitOp(node);
   visitSubtract(HSubtract node) => visitBinaryArithmetic(node);
   visitSwitch(HSwitch node) => visitControlFlow(node);
   visitStatic(HStatic node) => visitInstruction(node);
   visitStaticStore(HStaticStore node) => visitInstruction(node);
   visitStringConcat(HStringConcat node) => visitInstruction(node);
   visitThis(HThis node) => visitParameterValue(node);
   visitThrow(HThrow node) => visitControlFlow(node);
@@ skipping 372 matching lines @@
       if (dominator !== block0) {
         dominator.removeDominatedBlock(this);
         block0.addDominatedBlock(this);
       }
     }
   }
 
   void forEachPhi(void f(HPhi phi)) {
     HPhi current = phis.first;
     while (current !== null) {
+      HInstruction saved = current.next;
       f(current);
-      current = current.next;
+      current = saved;
     }
   }
 
   void forEachInstruction(void f(HInstruction instruction)) {
     HInstruction current = first;
     while (current !== null) {
+      HInstruction saved = current.next;
       f(current);
-      current = current.next;
+      current = saved;
     }
   }
 
   bool isValid() {
     assert(isClosed());
     HValidator validator = new HValidator();
     validator.visitBasicBlock(this);
     return validator.isValid;
   }
 
@@ skipping 455 matching lines @@
   accept(HVisitor visitor) => visitor.visitTypeGuard(this);
   int typeCode() => HInstruction.TYPE_GUARD_TYPECODE;
   bool typeEquals(other) => other is HTypeGuard;
   bool dataEquals(HTypeGuard other) => guardedType == other.guardedType;
 }
 
 class HBoundsCheck extends HCheck {
   static const int ALWAYS_FALSE = 0;
   static const int FULL_CHECK = 1;
   static const int ALWAYS_ABOVE_ZERO = 2;
-  static const int ALWAYS_TRUE = 3;
+  static const int ALWAYS_BELOW_LENGTH = 3;
+  static const int ALWAYS_TRUE = 4;
   /**
    * Details which tests have been done statically during compilation.
    * Default is that all checks must be performed dynamically.
    */
   int staticChecks = FULL_CHECK;
 
   HBoundsCheck(length, index) : super(<HInstruction>[length, index]);
 
   HInstruction get length => inputs[1];
   HInstruction get index => inputs[0];
@@ skipping 1353 matching lines @@
   bool isJsStatement(HTypeMap types) => kind == ARGUMENT_TYPE_CHECK;
   bool isControlFlow() => kind == ARGUMENT_TYPE_CHECK;
 
   int typeCode() => HInstruction.TYPE_CONVERSION_TYPECODE;
   bool typeEquals(HInstruction other) => other is HTypeConversion;
   bool dataEquals(HTypeConversion other) {
     return type == other.type && kind == other.kind;
   }
 }
 
+class HRangeConversion extends HCheck {
+  HRangeConversion(HInstruction input) : super(<HInstruction>[input]) {
+    sourceElement = input.sourceElement;
+  }
+  accept(HVisitor visitor) => visitor.visitRangeConversion(this);

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

Maybe add a comment that we only do range analysis for integers.

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

Done.

+  HType get guaranteedType => HType.INTEGER;
+}
+
 class HStringConcat extends HInstruction {
   final Node node;
   HStringConcat(HInstruction left, HInstruction right, this.node)
       : super(<HInstruction>[left, right]);
   HType get guaranteedType => HType.STRING;
 
   HInstruction get left => inputs[0];
   HInstruction get right => inputs[1];
 
   accept(HVisitor visitor) => visitor.visitStringConcat(this);
@@ skipping 325 matching lines @@
   HBasicBlock get start => expression.start;
   HBasicBlock get end {
     // We don't create a switch block if there are no cases.
     assert(!statements.isEmpty());
     return statements.last().end;
   }
 
   bool accept(HStatementInformationVisitor visitor) =>
       visitor.visitSwitchInfo(this);
 }