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 10 matching lines @@
 
 DECLARE_FLAG(bool, eliminate_type_checks);
 DECLARE_FLAG(bool, enable_type_checks);
 DEFINE_FLAG(bool, trace_optimization, false, "Print optimization details.");
 DECLARE_FLAG(bool, trace_type_check_elimination);
 DEFINE_FLAG(bool, use_cha, true, "Use class hierarchy analysis.");
 DEFINE_FLAG(bool, load_cse, true, "Use redundant load elimination.");
 DEFINE_FLAG(bool, trace_range_analysis, false, "Trace range analysis progress");
 DEFINE_FLAG(bool, trace_constant_propagation, false,
             "Print constant propagation and useless code elimination.");
+DEFINE_FLAG(bool, array_bounds_check_elimination, true,
+            "Eliminate redundant bounds checks.");
 
 
 void FlowGraphOptimizer::ApplyICData() {
   VisitBlocks();
 }
 
 
 // Attempts to convert an instance call (IC call) using propagated class-ids,
 // e.g., receiver class id.
 void FlowGraphOptimizer::ApplyClassIds() {
@@ skipping 867 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 (FLAG_array_bounds_check_elimination &&
+               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