Simple array bounds check elimination on top of range analysis framework.

runtime/vm/flow_graph_optimizer.cc

 // 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.
 
 #include "vm/flow_graph_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 897 matching lines @@
       call->ArgumentAt(0)->value(),
       field.Offset(),
       AbstractType::ZoneHandle(field.type()));
   call->ReplaceWith(load, current_iterator());
   RemovePushArguments(call);
 }
 
 
 void FlowGraphOptimizer::InlineArrayLengthGetter(InstanceCallInstr* call,
                                                  intptr_t length_offset,
-                                                 bool is_immutable) {
+                                                 bool is_immutable,
+                                                 MethodRecognizer::Kind kind) {
   // Check receiver class.
   AddCheckClass(call, call->ArgumentAt(0)->value()->Copy());
 
   LoadFieldInstr* load = new LoadFieldInstr(
       call->ArgumentAt(0)->value(),
       length_offset,
       Type::ZoneHandle(Type::SmiType()),
       is_immutable);
   load->set_result_cid(kSmiCid);
+  load->set_recognized_kind(kind);
   call->ReplaceWith(load, current_iterator());
   RemovePushArguments(call);
 }
 
 
 void FlowGraphOptimizer::InlineGArrayCapacityGetter(InstanceCallInstr* call) {
   // Check receiver class.
   AddCheckClass(call, call->ArgumentAt(0)->value()->Copy());
 
   // TODO(srdjan): type of load should be GrowableObjectArrayType.
   LoadFieldInstr* data_load = new LoadFieldInstr(
       call->ArgumentAt(0)->value(),
       Array::data_offset(),
       Type::ZoneHandle(Type::DynamicType()));
   data_load->set_result_cid(kArrayCid);
   InsertBefore(call, data_load, NULL, Definition::kValue);
 
   LoadFieldInstr* length_load = new LoadFieldInstr(
       new Value(data_load),
       Array::length_offset(),
       Type::ZoneHandle(Type::SmiType()));
   length_load->set_result_cid(kSmiCid);
+  length_load->set_recognized_kind(MethodRecognizer::kObjectArrayLength);
 
   call->ReplaceWith(length_load, current_iterator());
   RemovePushArguments(call);
 }
 
 
 static LoadFieldInstr* BuildLoadStringLength(Value* str) {
   const bool is_immutable = true;  // String length is immutable.
   LoadFieldInstr* load = new LoadFieldInstr(
       str,
@@ skipping 60 matching lines @@
   if ((recognized_kind == MethodRecognizer::kObjectArrayLength) ||
       (recognized_kind == MethodRecognizer::kImmutableArrayLength) ||
       (recognized_kind == MethodRecognizer::kGrowableArrayLength)) {
     if (!ic_data.HasOneTarget()) {
       // TODO(srdjan): Implement for mutiple targets.
       return false;
     }
     switch (recognized_kind) {
       case MethodRecognizer::kObjectArrayLength:
       case MethodRecognizer::kImmutableArrayLength:
-        InlineArrayLengthGetter(call, Array::length_offset(), true);
+        InlineArrayLengthGetter(call,
+                                Array::length_offset(),
+                                true,
+                                recognized_kind);
         break;
       case MethodRecognizer::kGrowableArrayLength:
         InlineArrayLengthGetter(call,
                                 GrowableObjectArray::length_offset(),
-                                false);
+                                false,
+                                recognized_kind);
         break;
       default:
         UNREACHABLE();
     }
     return true;
   }
 
   if (recognized_kind == MethodRecognizer::kGrowableArrayCapacity) {
     InlineGArrayCapacityGetter(call);
     return true;
@@ skipping 1047 matching lines @@
             continue;
           }
         }
 
         phi->InferRange();
       }
     }
   }
 
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
-    Definition* defn = it.Current()->AsDefinition();
+    Instruction* current = it.Current();
+
+    Definition* defn = current->AsDefinition();
     if ((defn != NULL) &&
         (defn->ssa_temp_index() != -1) &&
         smi_definitions_->Contains(defn->ssa_temp_index())) {
       defn->InferRange();
+    } else if (current->IsCheckArrayBound() &&
+               current->AsCheckArrayBound()->IsRedundant()) {
+      it.RemoveCurrentFromGraph();
     }
   }
 
   for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) {
     InferRangesRecursive(block->dominated_blocks()[i]);
   }
 }
 
 
 void RangeAnalysis::InferRanges() {
@@ skipping 1421 matching lines @@
 
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== After constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart