Separate the array/string .length load from the bounds check.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2013, 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 533 matching lines @@
     ConstantInstr* array_def = (*array)->definition()->AsConstant();
     const ImmutableArray& constant_array =
         ImmutableArray::Cast(array_def->value());
     ConstantInstr* index_def = (*index)->definition()->AsConstant();
     if (index_def->value().IsSmi()) {
       intptr_t constant_index = Smi::Cast(index_def->value()).Value();
       skip_check = (constant_index < constant_array.Length());
     }
   }
   if (!skip_check) {
-    // Insert array bounds check.
+    // Insert array length load and bounds check.
+    const bool is_immutable = (class_id != kGrowableObjectArrayCid);

[srdjan, 2013/02/01 19:01:28]

It may be better to compute is_immutable by checking what class_id IS and not
what it IS NOT, since that could cause problems when adding new types in
TryReplaceWithStoreIndexed.

[Florian Schneider, 2013/02/06 13:08:19]

Agree. I'll change it.

+    LoadFieldInstr* length = new LoadFieldInstr(
+        (*array)->Copy(),
+        CheckArrayBoundInstr::LengthOffsetFor(class_id),
+        Type::ZoneHandle(Type::SmiType()),
+        is_immutable);
+    length->set_result_cid(kSmiCid);
+    length->set_recognized_kind(
+        LoadFieldInstr::RecognizedKindFromArrayCid(class_id));
+    InsertBefore(call, length, NULL, Definition::kValue);
     InsertBefore(call,
-                 new CheckArrayBoundInstr((*array)->Copy(),
+                 new CheckArrayBoundInstr(new Value(length),
                                           (*index)->Copy(),
                                           class_id,
                                           call),
                  call->env(),
                  Definition::kEffect);
   }
   if (class_id == kGrowableObjectArrayCid) {
     // Insert data elements load.
     LoadFieldInstr* elements =
         new LoadFieldInstr((*array)->Copy(),
@@ skipping 725 matching lines @@
     const String& constant_string =
         String::Cast(string_def->value());
     ConstantInstr* index_def = index->definition()->AsConstant();
     if (index_def->value().IsSmi()) {
       intptr_t constant_index = Smi::Cast(index_def->value()).Value();
       skip_check = (constant_index < constant_string.Length());
     }
   }
   if (!skip_check) {
     // Insert bounds check.
+    const bool is_immutable = true;
+    LoadFieldInstr* length = new LoadFieldInstr(
+        str->Copy(),
+        CheckArrayBoundInstr::LengthOffsetFor(cid),
+        Type::ZoneHandle(Type::SmiType()),
+        is_immutable);
+    length->set_result_cid(kSmiCid);
+    length->set_recognized_kind(MethodRecognizer::kStringBaseLength);
+    InsertBefore(call, length, NULL, Definition::kValue);
     InsertBefore(call,
-                 new CheckArrayBoundInstr(str->Copy(),
+                 new CheckArrayBoundInstr(new Value(length),
                                           index->Copy(),
                                           cid,
                                           call),
                  call->env(),
                  Definition::kEffect);
   }
   return new LoadIndexedInstr(str, index, cid, Isolate::kNoDeoptId);
 }
 
 
@@ skipping 724 matching lines @@
 
   // Create a constraint for defn, insert it after given instruction and
   // rename all uses that are dominated by it.
   ConstraintInstr* InsertConstraintFor(Definition* defn,
                                        Range* constraint,
                                        Instruction* after);
 
   void ConstrainValueAfterBranch(Definition* defn, Value* use);
   void ConstrainValueAfterCheckArrayBound(Definition* defn,
                                           CheckArrayBoundInstr* check);
-  Definition* LoadArrayLength(CheckArrayBoundInstr* check);
 
   // Replace uses of the definition def that are dominated by instruction dom
   // with uses of other definition.
   void RenameDominatedUses(Definition* def,
                            Instruction* dom,
                            Definition* other);
 
 
   // Walk the dominator tree and infer ranges for smi values.
   void InferRanges();
@@ skipping 39 matching lines @@
   // as smi values.
   GrowableArray<ConstraintInstr*> constraints_;
 
   // Bitvector for a quick filtering of known smi values.
   BitVector* smi_definitions_;
 
   // Worklist for induction variables analysis.
   GrowableArray<Definition*> worklist_;
   BitVector* marked_defns_;
 
-  class ArrayLengthData : public ValueObject {
-   public:
-    ArrayLengthData(Definition* array, Definition* array_length)
-        : array_(array), array_length_(array_length) { }
-
-    ArrayLengthData(const ArrayLengthData& other)
-        : ValueObject(),
-          array_(other.array_),
-          array_length_(other.array_length_) { }
-
-    ArrayLengthData& operator=(const ArrayLengthData& other) {
-      array_ = other.array_;
-      array_length_ = other.array_length_;
-      return *this;
-    }
-
-    Definition* array() const { return array_; }
-    Definition* array_length() const { return array_length_; }
-
-    typedef Definition* Value;
-    typedef Definition* Key;
-    typedef class ArrayLengthData Pair;
-
-    // KeyValueTrait members.
-    static Key KeyOf(const ArrayLengthData& data) {
-      return data.array();
-    }
-
-    static Value ValueOf(const ArrayLengthData& data) {
-      return data.array_length();
-    }
-
-    static inline intptr_t Hashcode(Key key) {
-      return reinterpret_cast<intptr_t>(key);
-    }
-
-    static inline bool IsKeyEqual(const ArrayLengthData& kv, Key key) {
-      return kv.array() == key;
-    }
-
-   private:
-    Definition* array_;
-    Definition* array_length_;
-  };
-
-  DirectChainedHashMap<ArrayLengthData> array_lengths_;
-
   DISALLOW_COPY_AND_ASSIGN(RangeAnalysis);
 };
 
 
 void RangeAnalysis::Analyze() {
   CollectSmiValues();
   InsertConstraints();
   InferRanges();
   RemoveConstraints();
 }
@@ skipping 213 matching lines @@
       ConstrainValueAfterBranch(defn, use);
     } else if (use->instruction()->IsCheckArrayBound()) {
       ConstrainValueAfterCheckArrayBound(
           defn,
           use->instruction()->AsCheckArrayBound());
     }
   }
 }
 
 
-Definition* RangeAnalysis::LoadArrayLength(CheckArrayBoundInstr* check) {
-  Definition* array = check->array()->definition();
-
-  Definition* length = array_lengths_.Lookup(array);
-  if (length != NULL) return length;
-
-  StaticCallInstr* allocation = array->AsStaticCall();
-  if ((allocation != NULL) &&
-      allocation->is_known_constructor() &&
-      (allocation->ResultCid() == kArrayCid)) {
-    // For fixed length arrays check if array is the result of a constructor
-    // call. In this case we can use the length passed to the constructor
-    // instead of loading it from array itself.
-    length = allocation->ArgumentAt(1)->value()->definition();
-  } else {
-    // Load length from the array. Do not insert instruction into the graph.
-    // It will only be used in range boundaries.
-    LoadFieldInstr* length_load = new LoadFieldInstr(
-        check->array()->Copy(),
-        CheckArrayBoundInstr::LengthOffsetFor(check->array_type()),
-        Type::ZoneHandle(Type::SmiType()),
-        true);  // Immutable.
-    length_load->set_recognized_kind(MethodRecognizer::kObjectArrayLength);
-    length_load->set_result_cid(kSmiCid);
-    length_load->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index());
-    length = length_load;
-  }
-
-  ASSERT(length != NULL);
-  array_lengths_.Insert(ArrayLengthData(array, length));
-  return length;
-}
-
-
 void RangeAnalysis::ConstrainValueAfterCheckArrayBound(
     Definition* defn, CheckArrayBoundInstr* check) {
   if (!CheckArrayBoundInstr::IsFixedLengthArrayType(check->array_type())) {
     return;
   }
 
-  Definition* length = LoadArrayLength(check);
+  Definition* length = check->length()->definition();
 
   Range* constraint_range = new Range(
       RangeBoundary::FromConstant(0),
       RangeBoundary::FromDefinition(length, -1));
   InsertConstraintFor(defn, constraint_range, check);
 }
 
 
 void RangeAnalysis::InsertConstraints() {
   for (intptr_t i = 0; i < smi_checks_.length(); i++) {
@@ skipping 176 matching lines @@
 
     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()) {
       CheckArrayBoundInstr* check = current->AsCheckArrayBound();
       RangeBoundary array_length =
-          RangeBoundary::FromDefinition(LoadArrayLength(check));
+          RangeBoundary::FromDefinition(check->length()->definition());
       if (check->IsRedundant(array_length)) it.RemoveCurrentFromGraph();
     }
   }
 
   for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) {
     InferRangesRecursive(block->dominated_blocks()[i]);
   }
 }
 
 
@@ skipping 1569 matching lines @@
 }
 
 
 void ConstantPropagator::VisitLoadField(LoadFieldInstr* instr) {
   if ((instr->recognized_kind() == MethodRecognizer::kObjectArrayLength) &&
       (instr->value()->definition()->IsCreateArray())) {
     const intptr_t length =
         instr->value()->definition()->AsCreateArray()->ArgumentCount();
     const Object& result = Smi::ZoneHandle(Smi::New(length));
     SetValue(instr, result);
-  } else {
-    SetValue(instr, non_constant_);
+    return;
   }
+
+  if (instr->IsImmutableLengthLoad()) {
+    ConstantInstr* constant = instr->value()->definition()->AsConstant();
+    if (constant != NULL) {
+      if (constant->value().IsString()) {
+        SetValue(instr, Smi::ZoneHandle(
+            Smi::New(String::Cast(constant->value()).Length())));
+        return;
+      }
+      if (constant->value().IsArray()) {
+        SetValue(instr, Smi::ZoneHandle(
+            Smi::New(Array::Cast(constant->value()).Length())));
+        return;
+      }
+    }
+  }
+  SetValue(instr, non_constant_);
 }
 
 
 void ConstantPropagator::VisitStoreVMField(StoreVMFieldInstr* instr) {
   SetValue(instr, instr->value()->definition()->constant_value());
 }
 
 
 void ConstantPropagator::VisitInstantiateTypeArguments(
     InstantiateTypeArgumentsInstr* instr) {
@@ skipping 377 matching lines @@
 
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== After constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart