Add a value range analysis phase to remove bounds checks.

lib/compiler/implementation/ssa/optimize.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 OptimizationPhase {
   String get name;
   void visitGraph(HGraph graph);
 }
 
 class SsaOptimizerTask extends CompilerTask {
@@ skipping 23 matching lines @@
       List<OptimizationPhase> phases = <OptimizationPhase>[
           // Run trivial constant folding first to optimize
           // some patterns useful for type conversion.
           new SsaConstantFolder(constantSystem, backend, work, types),
           new SsaTypeConversionInserter(compiler),
           new SsaTypePropagator(compiler, types),
           new SsaCheckInserter(backend, types, context.boundsChecked),
           new SsaConstantFolder(constantSystem, backend, work, types),
           new SsaRedundantPhiEliminator(),
           new SsaDeadPhiEliminator(),
+          new SsaConstantFolder(constantSystem, backend, work, types),
           new SsaGlobalValueNumberer(compiler, types),
           new SsaCodeMotion(),
+          new SsaValueRangeAnalyzer(constantSystem, types, work),
           // Previous optimizations may have generated new
           // opportunities for constant folding.
           new SsaConstantFolder(constantSystem, backend, work, types),
           new SsaDeadCodeEliminator(types),
           new SsaRegisterRecompilationCandidates(backend, work, types)];
       runPhases(graph, phases);
     });
   }
 
   bool trySpeculativeOptimizations(WorkItem work, HGraph graph) {
@@ skipping 133 matching lines @@
     HInstruction operand = node.operand;
     if (operand is HConstant) {
       UnaryOperation operation = node.operation(constantSystem);
       HConstant receiver = operand;
       Constant folded = operation.fold(receiver.constant);
       if (folded !== null) return graph.addConstant(folded);
     }
     return node;
   }
 
   HInstruction visitInvokeInterceptor(HInvokeInterceptor node) {

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

Add a comment on the pattern recognized here.

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

Done.

+    if (node.isLengthGetter() && node.inputs[1] is HInvokeStatic) {
+      HInvokeStatic call = node.inputs[1];
+      Element element = call.inputs[0].element;
+      if (element.isConstructor() &&
+          element.enclosingElement == compiler.listClass.defaultClass.element) {
+        if (call.inputs.length == 2 && call.inputs[1].isInteger(types)) {
+          return call.inputs[1];
+        }
+      }
+    }
     HInstruction input = node.inputs[1];
     if (node.isLengthGetter()) {
       if (input.isConstantString()) {
         HConstant constantInput = input;
         StringConstant constant = constantInput.constant;
         return graph.addConstantInt(constant.length, constantSystem);
       } else if (input.isConstantList()) {
         HConstant constantInput = input;
         ListConstant constant = constantInput.constant;
         return graph.addConstantInt(constant.length, constantSystem);
@@ skipping 53 matching lines @@
     HInvokeDynamicMethod result = new HInvokeDynamicMethod(
         selector,
         node.inputs.getRange(1, node.inputs.length - 1));
     if (type.isExact()) {
       HBoundedType concrete = type;
       result.element = concrete.lookupMember(selector.name);
     }
     return result;
   }
 
-  HInstruction visitBoundsCheck(HBoundsCheck node) {
-    int tryGetIntConstantValue(HInstruction instruction, String errorMessage) {
-      // Tests whether an [HInstruction] is a constant.
-      // If it is a constant, and not an int constant, it fails.
-      // If it's an int constant it returns the value.
-      // Otherwise it's not a constant, and this function returns null.
-      if (!instruction.isConstant()) return null;
-      HConstant constantInstruction = instruction;
-      Constant constant = constantInstruction.constant;
-      if (!constant.isInt()) {
-        compiler.internalError(errorMessage, instruction: instruction);
-      }
-      IntConstant intConstant = constant;
-      return intConstant.value;
-    }
-    int index = tryGetIntConstantValue(node.index,
-                                       'String or List index not a number');
-    if (index !== null) {
-      if (index < 0) {
-        node.staticChecks = HBoundsCheck.ALWAYS_FALSE;
-        return node;
-      }
-      int length = tryGetIntConstantValue(node.length,
-                                          'String or List length not a number');
-      if (length !== null) {
-        if (index >= length) {
-          node.staticChecks = HBoundsCheck.ALWAYS_FALSE;
-        } else {
-          // Could have set the staticChecks to ALWAYS_TRUE instead.
-          return node.index;
-        }
-        return node;
-      }
-      node.staticChecks = HBoundsCheck.ALWAYS_ABOVE_ZERO;
-    }
-    return node;
-  }
-
   HInstruction visitIntegerCheck(HIntegerCheck node) {
     HInstruction value = node.value;
     if (value.isInteger(types)) return value;
     if (value.isConstant()) {
       HConstant constantInstruction = value;
       assert(!constantInstruction.constant.isInt());
       if (!constantSystem.isInt(constantInstruction.constant)) {
         // -0.0 is a double but will pass the runtime integer check.
         node.alwaysFalse = true;
       }
@@ skipping 400 matching lines @@
 
   void visitIndex(HIndex node) {
     if (!node.receiver.isIndexablePrimitive(types)) return;
     if (boundsChecked.contains(node)) return;
     HInstruction index = node.index;
     if (!node.index.isInteger(types)) {
       index = insertIntegerCheck(node, index);
     }
     index = insertBoundsCheck(node, node.receiver, index);
     node.changeUse(node.index, index);
+    assert(node.isBuiltin(types));
   }
 
   void visitIndexAssign(HIndexAssign node) {
     if (!node.receiver.isMutableArray(types)) return;
     if (boundsChecked.contains(node)) return;
     HInstruction index = node.index;
     if (!node.index.isInteger(types)) {
       index = insertIntegerCheck(node, index);
     }
     index = insertBoundsCheck(node, node.receiver, index);
     node.changeUse(node.index, index);
+    assert(node.isBuiltin(types));
   }
 
   void visitInvokeInterceptor(HInvokeInterceptor node) {
     if (!node.isPopCall(types)) return;
     if (boundsChecked.contains(node)) return;
     HInstruction receiver = node.inputs[1];
     insertBoundsCheck(node, receiver, graph.addConstantInt(0, constantSystem));
   }
 }
 
@@ skipping 617 matching lines @@
       // this type for the field is still a strong signal
       // indicating the expected type of the field.
       types[field] = type;
     } else {
       // If there are no invoked setters we know the type of
       // this field for sure.
       field.guaranteedType = type;
     }
   }
 }