Add alias identity information to array allocations.

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/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 4978 matching lines @@
 // Alias represents a family of locations. It is used to capture aliasing
 // between stores and loads. Store can alias another load or store if and only
 // if they have the same alias.
 class Alias : public ValueObject {
  public:
   Alias(const Alias& other) : ValueObject(), alias_(other.alias_) { }
 
   // All indexed load/stores alias each other.
   // TODO(vegorov): incorporate type of array into alias to disambiguate
   // different typed data and normal arrays.
-  static Alias Indexes() {
-    return Alias(kIndexesAlias, 0);
+  static Alias UnknownIndex(intptr_t id) {
+    return Alias(kUnknownIndexAlias, id);
   }
 
   static Alias ConstantIndex(intptr_t id) {
     ASSERT(id != 0);
     return Alias(kConstantIndex, id);
   }
 
   // Field load/stores alias each other only when they access the same field.
   // AliasedSet assigns ids to a combination of instance and field during
   // the optimization phase.
@@ skipping 35 matching lines @@
     // Number of bits required to encode Kind value.
     // The payload occupies the rest of the bits, but leaves the MSB (sign bit)
     // empty so that the resulting encoded value is always a positive integer.
     kBitsForKind = 3,
     kBitsForPayload = kWordSize * kBitsPerByte - kBitsForKind - 1,
   };
 
   enum Kind {
     kNoneAlias = -1,
     kCurrentContextAlias = 0,
-    kIndexesAlias = 1,
+    kUnknownIndexAlias = 1,
     kFieldAlias = 2,
     kVMFieldAlias = 3,
     kConstantIndex = 4,
     kNumKinds = kConstantIndex + 1
   };
   COMPILE_ASSERT(kNumKinds < ((1 << kBitsForKind) - 1), InvalidBitFieldSize);
 
   explicit Alias(intptr_t alias) : alias_(alias) { }
 
   Alias(Kind kind, uword payload)
@@ skipping 317 matching lines @@
   explicit AliasedSet(ZoneGrowableArray<Place*>* places,
                       PhiPlaceMoves* phi_moves)
       : places_(*places),
         phi_moves_(phi_moves),
         sets_(),
         aliased_by_effects_(new BitVector(places->length())),
         max_field_id_(0),
         field_ids_(),
         max_index_id_(0),
         index_ids_(),
+        max_unknown_index_id_(0),
+        unknown_index_ids_(),
         max_vm_field_id_(0),
         vm_field_ids_() { }
 
   Alias ComputeAlias(Place* place) {
     switch (place->kind()) {
       case Place::kIndexed:
         if (place->index()->IsConstant()) {
           const Object& index = place->index()->AsConstant()->value();
           if (index.IsSmi()) {
-            return Alias::ConstantIndex(GetIndexId(Smi::Cast(index).Value()));
+            return Alias::ConstantIndex(
+                GetInstanceIndexId(place->instance(),
+                                   Smi::Cast(index).Value()));
           }
         }
-        return Alias::Indexes();
+        return Alias::UnknownIndex(GetUnknownIndexId(place->instance()));
       case Place::kField:
         return Alias::Field(
             GetInstanceFieldId(place->instance(), place->field()));
       case Place::kVMField:
         return Alias::VMField(
-            GetVMFieldId(place->instance(), place->offset_in_bytes()));
+            GetInstanceVMFieldId(place->instance(), place->offset_in_bytes()));
       case Place::kContext:
         return Alias::CurrentContext();
       case Place::kNone:
         UNREACHABLE();
     }
 
     UNREACHABLE();
     return Alias::None();
   }
 
   Alias ComputeAliasForStore(Instruction* instr) {
     StoreIndexedInstr* store_indexed = instr->AsStoreIndexed();
     if (store_indexed != NULL) {
+      Definition* instance = store_indexed->array()->definition();
       if (store_indexed->index()->definition()->IsConstant()) {
         const Object& index =
             store_indexed->index()->definition()->AsConstant()->value();
         if (index.IsSmi()) {
-          return Alias::ConstantIndex(GetIndexId(Smi::Cast(index).Value()));
+          return Alias::ConstantIndex(
+              GetInstanceIndexId(instance, Smi::Cast(index).Value()));
         }
       }
-      return Alias::Indexes();
+      return Alias::UnknownIndex(GetUnknownIndexId(instance));
     }
 
     StoreInstanceFieldInstr* store_instance_field =
         instr->AsStoreInstanceField();
     if (store_instance_field != NULL) {
       Definition* instance = store_instance_field->instance()->definition();
       if (!store_instance_field->field().IsNull()) {
         return Alias::Field(
             GetInstanceFieldId(instance, store_instance_field->field()));
       }
       return Alias::VMField(
-          GetVMFieldId(instance, store_instance_field->offset_in_bytes()));
+          GetInstanceVMFieldId(instance,
+                               store_instance_field->offset_in_bytes()));
     }
 
     if (instr->IsStoreContext()) {
       return Alias::CurrentContext();
     }
 
     StoreStaticFieldInstr* store_static_field = instr->AsStoreStaticField();
     if (store_static_field != NULL) {
       return Alias::Field(GetStaticFieldId(store_static_field->field()));
     }
 
     return Alias::None();
   }
 
   BitVector* Get(const Alias alias) {
     const intptr_t idx = alias.ToIndex();
     BitVector* ret = (idx < sets_.length()) ? sets_[idx] : NULL;
     return ret;
   }
 
   void AddRepresentative(Place* place) {
     if (!place->IsFinalField()) {
       AddIdForAlias(ComputeAlias(place), place->id());
       if (!IsIndependentFromEffects(place)) {
         aliased_by_effects_->Add(place->id());
       }
     }
   }
 
-  void EnsureAliasingForIndexes() {
-    BitVector* indexes = Get(Alias::Indexes());
-    if (indexes == NULL) {
-      return;
-    }
+  void EnsureAliasingForUnknownIndices() {
+    // Ids start at 1 because the hash-map uses 0 for element not found.
+    for (intptr_t unknown_index_id = 1;
+         unknown_index_id <= max_unknown_index_id_;
+         unknown_index_id++) {
+      BitVector* unknown_index = Get(Alias::UnknownIndex(unknown_index_id));
+      if (unknown_index == NULL) {
+        return;
+      }
 
-    // Constant indexes alias all non-constant indexes.
-    // Non-constant indexes alias all constant indexes.
-    // First update alias set for const-indices, then
-    // update set for all indices. Ids start at 1.
-    for (intptr_t id = 1; id <= max_index_id_; id++) {
-      BitVector* const_indexes = Get(Alias::ConstantIndex(id));
-      if (const_indexes != NULL) {
-        const_indexes->AddAll(indexes);
+      // Constant indexes alias all non-constant indexes.
+      // Non-constant indexes alias all constant indexes.
+      // First update alias set for const-indices, then
+      // update set for all indices. Ids start at 1.
+      for (intptr_t id = 1; id <= max_index_id_; id++) {
+        BitVector* const_indexes = Get(Alias::ConstantIndex(id));
+        if (const_indexes != NULL) {
+          const_indexes->AddAll(unknown_index);
+        }
       }
-    }
 
-    for (intptr_t id = 1; id <= max_index_id_; id++) {
-      BitVector* const_indexes = Get(Alias::ConstantIndex(id));
-      if (const_indexes != NULL) {
-        indexes->AddAll(const_indexes);
+      for (intptr_t id = 1; id <= max_index_id_; id++) {
+        BitVector* const_indexes = Get(Alias::ConstantIndex(id));
+        if (const_indexes != NULL) {
+          unknown_index->AddAll(const_indexes);
+        }
       }
     }
   }
 
   void AddIdForAlias(const Alias alias, intptr_t place_id) {
     const intptr_t idx = alias.ToIndex();
     while (sets_.length() <= idx) {
       sets_.Add(NULL);
     }
 
@@ skipping 25 matching lines @@
       comma = true;
     }
   }
 
   const PhiPlaceMoves* phi_moves() const { return phi_moves_; }
 
   // Returns true if the result of an allocation instruction can be aliased by
   // some other SSA variable and false otherwise. Currently simply checks if
   // this value is stored in a field, escapes to another function or
   // participates in a phi.
-  static bool CanBeAliased(AllocateObjectInstr* alloc) {
-    if (alloc->identity() == AllocateObjectInstr::kUnknown) {
+  static bool CanBeAliased(Definition* alloc) {
+    ASSERT(alloc->IsAllocateObject() ||
+           alloc->IsCreateArray() ||
+           (alloc->IsStaticCall() &&
+            alloc->AsStaticCall()->is_known_list_constructor()));
+    if (alloc->Identity() == kIdentityUnknown) {
       bool escapes = false;
       for (Value* use = alloc->input_use_list();
            use != NULL;
            use = use->next_use()) {
         Instruction* instr = use->instruction();
         if (instr->IsPushArgument() ||
             (instr->IsStoreInstanceField()
              && (use->use_index() != StoreInstanceFieldInstr::kInstancePos)) ||
             (instr->IsStoreIndexed()
              && (use->use_index() == StoreIndexedInstr::kValuePos)) ||
             instr->IsStoreStaticField() ||
             instr->IsPhi() ||
             instr->IsAssertAssignable() ||
             instr->IsRedefinition()) {
           escapes = true;
           break;
         }
       }
 
-      alloc->set_identity(escapes ? AllocateObjectInstr::kAliased
-                                  : AllocateObjectInstr::kNotAliased);
+      alloc->SetIdentity(escapes ? kIdentityAliased : kIdentityNotAliased);
     }
 
-    return alloc->identity() != AllocateObjectInstr::kNotAliased;
+    return alloc->Identity() != kIdentityNotAliased;
   }
 
  private:
   // Get id assigned to the given field. Assign a new id if the field is seen
   // for the first time.
   intptr_t GetFieldId(intptr_t instance_id, const Field& field) {
     intptr_t id = field_ids_.Lookup(FieldIdPair::Key(instance_id, &field));
     if (id == 0) {
       id = ++max_field_id_;
       field_ids_.Insert(FieldIdPair(FieldIdPair::Key(instance_id, &field), id));
     }
     return id;
   }
 
-  intptr_t GetIndexId(intptr_t index) {
-    intptr_t id = index_ids_.Lookup(index);
+  intptr_t GetIndexId(intptr_t instance_id, intptr_t index) {
+    intptr_t id = index_ids_.Lookup(
+        ConstantIndexIdPair::Key(instance_id, index));
     if (id == 0) {
       // Zero is used to indicate element not found. The first id is one.
       id = ++max_index_id_;
-      index_ids_.Insert(IndexIdPair(index, id));
+      index_ids_.Insert(ConstantIndexIdPair(
+          ConstantIndexIdPair::Key(instance_id, index), id));
     }
     return id;
   }
 
   enum {
     kAnyInstance = -1
   };
 
   // Get or create an identifier for an instance field belonging to the
   // given instance.
@@ skipping 13 matching lines @@
       AllocateObjectInstr* alloc = defn->AsAllocateObject();
       if ((alloc != NULL) && !CanBeAliased(alloc)) {
         instance_id = alloc->ssa_temp_index();
         ASSERT(instance_id != kAnyInstance);
       }
     }
 
     return GetFieldId(instance_id, field);
   }
 
-  intptr_t GetVMFieldId(Definition* defn, intptr_t offset) {
+  intptr_t GetInstanceVMFieldId(Definition* defn, intptr_t offset) {
     intptr_t instance_id = kAnyInstance;
 
-    if (defn != NULL) {
-      AllocateObjectInstr* alloc = defn->AsAllocateObject();
-      if ((alloc != NULL) && !CanBeAliased(alloc)) {
-        instance_id = alloc->ssa_temp_index();
-        ASSERT(instance_id != kAnyInstance);
-      }
+    ASSERT(defn != NULL);
+    if ((defn->IsAllocateObject() ||
+         defn->IsCreateArray() ||
+         (defn->IsStaticCall() &&
+          defn->AsStaticCall()->is_known_list_constructor())) &&
+        !CanBeAliased(defn)) {
+      instance_id = defn->ssa_temp_index();
+      ASSERT(instance_id != kAnyInstance);
     }
 
     intptr_t id = vm_field_ids_.Lookup(VMFieldIdPair::Key(instance_id, offset));
     if (id == 0) {
       id = ++max_vm_field_id_;
       vm_field_ids_.Insert(
           VMFieldIdPair(VMFieldIdPair::Key(instance_id, offset), id));
     }
     return id;
   }
 
+  intptr_t GetInstanceIndexId(Definition* defn, intptr_t index) {
+    intptr_t instance_id = kAnyInstance;
+
+    ASSERT(defn != NULL);
+    if ((defn->IsCreateArray() ||
+         (defn->IsStaticCall() &&
+          defn->AsStaticCall()->is_known_list_constructor())) &&
+        !CanBeAliased(defn)) {
+      instance_id = defn->ssa_temp_index();
+      ASSERT(instance_id != kAnyInstance);
+    }
+
+    return GetIndexId(instance_id, index);
+  }
+
+  intptr_t GetUnknownIndexId(Definition* defn) {
+    intptr_t instance_id = kAnyInstance;
+
+    ASSERT(defn != NULL);
+    if ((defn->IsCreateArray() ||
+         (defn->IsStaticCall() &&
+          defn->AsStaticCall()->is_known_list_constructor())) &&
+        !CanBeAliased(defn)) {
+      instance_id = defn->ssa_temp_index();
+      ASSERT(instance_id != kAnyInstance);
+    }
+
+    intptr_t id = unknown_index_ids_.Lookup(
+        UnknownIndexIdPair::Key(instance_id));
+    if (id == 0) {
+      // Zero is used to indicate element not found. The first id is one.
+      id = ++max_unknown_index_id_;
+      unknown_index_ids_.Insert(
+          UnknownIndexIdPair(UnknownIndexIdPair::Key(instance_id), id));
+    }
+    return id;
+  }
+
   // Get or create an identifier for a static field.
   intptr_t GetStaticFieldId(const Field& field) {
     ASSERT(field.is_static());
     return GetFieldId(kAnyInstance, field);
   }
 
   // Returns true if the given load is unaffected by external side-effects.
   // This essentially means that no stores to the same location can
   // occur in other functions.
   bool IsIndependentFromEffects(Place* place) {
@@ skipping 53 matching lines @@
     static inline bool IsKeyEqual(Pair kv, Key key) {
       return (KeyOf(kv).field_->raw() == key.field_->raw()) &&
           (KeyOf(kv).instance_id_ == key.instance_id_);
     }
 
    private:
     Key key_;
     Value value_;
   };
 
-  class IndexIdPair {
+  class ConstantIndexIdPair {
    public:
-    typedef intptr_t Key;
+    struct Key {
+      Key(intptr_t instance_id, intptr_t index)
+          : instance_id_(instance_id), index_(index) { }
+
+      intptr_t instance_id_;
+      intptr_t index_;
+    };
     typedef intptr_t Value;
-    typedef IndexIdPair Pair;
+    typedef ConstantIndexIdPair Pair;
 
-    IndexIdPair(Key key, Value value) : key_(key), value_(value) { }
+    ConstantIndexIdPair(Key key, Value value) : key_(key), value_(value) { }
 
-    static Key KeyOf(IndexIdPair kv) {
+    static Key KeyOf(ConstantIndexIdPair kv) {
       return kv.key_;
     }
 
-    static Value ValueOf(IndexIdPair kv) {
+    static Value ValueOf(ConstantIndexIdPair kv) {
       return kv.value_;
     }
 
     static intptr_t Hashcode(Key key) {
-      return key;
+      return (key.instance_id_ + 1) * 1024 + key.index_;
     }
 
-    static inline bool IsKeyEqual(IndexIdPair kv, Key key) {
+    static inline bool IsKeyEqual(ConstantIndexIdPair kv, Key key) {
+      return (KeyOf(kv).index_ == key.index_)
+          && (KeyOf(kv).instance_id_ == key.instance_id_);
+    }
+
+   private:
+    Key key_;
+    Value value_;
+  };
+
+  class UnknownIndexIdPair {
+   public:
+    typedef intptr_t Key;
+    typedef intptr_t Value;
+    typedef UnknownIndexIdPair Pair;
+
+    UnknownIndexIdPair(Key key, Value value) : key_(key), value_(value) { }
+
+    static Key KeyOf(UnknownIndexIdPair kv) {
+      return kv.key_;
+    }
+
+    static Value ValueOf(UnknownIndexIdPair kv) {
+      return kv.value_;
+    }
+
+    static intptr_t Hashcode(Key key) {
+      return key + 1;
+    }
+
+    static inline bool IsKeyEqual(UnknownIndexIdPair kv, Key key) {
       return KeyOf(kv) == key;
     }
 
    private:
     Key key_;
     Value value_;
   };
 
   class VMFieldIdPair {
    public:
@@ skipping 40 matching lines @@
   // given alias.
   GrowableArray<BitVector*> sets_;
 
   BitVector* aliased_by_effects_;
 
   // Table mapping static field to their id used during optimization pass.
   intptr_t max_field_id_;
   DirectChainedHashMap<FieldIdPair> field_ids_;
 
   intptr_t max_index_id_;
-  DirectChainedHashMap<IndexIdPair> index_ids_;
+  DirectChainedHashMap<ConstantIndexIdPair> index_ids_;
+
+  intptr_t max_unknown_index_id_;
+  DirectChainedHashMap<UnknownIndexIdPair> unknown_index_ids_;
 
   intptr_t max_vm_field_id_;
   DirectChainedHashMap<VMFieldIdPair> vm_field_ids_;
 };
 
 
 static Definition* GetStoredValue(Instruction* instr) {
   if (instr->IsStoreIndexed()) {
     return instr->AsStoreIndexed()->value()->definition();
   }
@@ skipping 117 matching lines @@
 
   PhiPlaceMoves* phi_moves = ComputePhiMoves(map, places);
 
   // Build aliasing sets mapping aliases to loads.
   AliasedSet* aliased_set = new AliasedSet(places, phi_moves);
   for (intptr_t i = 0; i < places->length(); i++) {
     Place* place = (*places)[i];
     aliased_set->AddRepresentative(place);
   }
 
-  aliased_set->EnsureAliasingForIndexes();
+  aliased_set->EnsureAliasingForUnknownIndices();
 
   return aliased_set;
 }
 
 
 class LoadOptimizer : public ValueObject {
  public:
   LoadOptimizer(FlowGraph* graph,
                 AliasedSet* aliased_set,
                 DirectChainedHashMap<PointerKeyValueTrait<Place> >* map)
@@ skipping 2771 matching lines @@
     BlockEntryInstr* block = block_it.Current();
     for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
       AllocateObjectInstr* alloc = it.Current()->AsAllocateObject();
       if ((alloc != NULL) && IsAllocationSinkingCandidate(alloc)) {
         if (FLAG_trace_optimization) {
           OS::Print("discovered allocation sinking candidate: v%" Pd "\n",
                     alloc->ssa_temp_index());
         }
 
         // All sinking candidate are known to be not aliased.
-        alloc->set_identity(AllocateObjectInstr::kNotAliased);
+        alloc->SetIdentity(kIdentityNotAliased);
 
         candidates.Add(alloc);
       }
     }
   }
 
   // Insert MaterializeObject instructions that will describe the state of the
   // object at all deoptimization points. Each inserted materialization looks
   // like this (where v_0 is allocation that we are going to eliminate):
   //   v_1     <- LoadField(v_0, field_1)
@@ skipping 155 matching lines @@
   }
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, alloc->cls(), *slots);
   }
 }
 
 
 }  // namespace dart