Add alias identity information to array allocations.

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
===================================================================
--- runtime/vm/flow_graph_optimizer.cc	(revision 33493)
+++ runtime/vm/flow_graph_optimizer.cc	(working copy)
@@ -4996,8 +4996,8 @@
   // 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) {
@@ -5053,7 +5053,7 @@
   enum Kind {
     kNoneAlias = -1,
     kCurrentContextAlias = 0,
-    kIndexesAlias = 1,
+    kUnknownIndexAlias = 1,
     kFieldAlias = 2,
     kVMFieldAlias = 3,
     kConstantIndex = 4,
@@ -5391,6 +5391,8 @@
         field_ids_(),
         max_index_id_(0),
         index_ids_(),
+        max_unknown_index_id_(0),
+        unknown_index_ids_(),
         max_vm_field_id_(0),
         vm_field_ids_() { }
 
@@ -5400,16 +5402,18 @@
         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:
@@ -5423,14 +5427,16 @@
   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 =
@@ -5442,7 +5448,8 @@
             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()) {
@@ -5472,27 +5479,32 @@
     }
   }
 
-  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);
+        }
       }
     }
   }
@@ -5538,8 +5550,12 @@
   // 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;
@@ -5559,11 +5575,10 @@
         }
       }
 
-      alloc->set_identity(escapes ? AllocateObjectInstr::kAliased
-                                  : AllocateObjectInstr::kNotAliased);
+      alloc->SetIdentity(escapes ? kIdentityAliased : kIdentityNotAliased);
     }
 
-    return alloc->identity() != AllocateObjectInstr::kNotAliased;
+    return alloc->Identity() != kIdentityNotAliased;
   }
 
  private:
@@ -5578,12 +5593,14 @@
     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;
   }
@@ -5617,15 +5634,17 @@
     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));
@@ -5637,6 +5656,44 @@
     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());
@@ -5710,27 +5767,63 @@
     Value value_;
   };
 
-  class IndexIdPair {
+  class ConstantIndexIdPair {
    public:
+    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 ConstantIndexIdPair Pair;
+
+    ConstantIndexIdPair(Key key, Value value) : key_(key), value_(value) { }
+
+    static Key KeyOf(ConstantIndexIdPair kv) {
+      return kv.key_;
+    }
+
+    static Value ValueOf(ConstantIndexIdPair kv) {
+      return kv.value_;
+    }
+
+    static intptr_t Hashcode(Key key) {
+      return (key.instance_id_ + 1) * 1024 + key.index_;
+    }
+
+    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 IndexIdPair Pair;
+    typedef UnknownIndexIdPair Pair;
 
-    IndexIdPair(Key key, Value value) : key_(key), value_(value) { }
+    UnknownIndexIdPair(Key key, Value value) : key_(key), value_(value) { }
 
-    static Key KeyOf(IndexIdPair kv) {
+    static Key KeyOf(UnknownIndexIdPair kv) {
       return kv.key_;
     }
 
-    static Value ValueOf(IndexIdPair kv) {
+    static Value ValueOf(UnknownIndexIdPair kv) {
       return kv.value_;
     }
 
     static intptr_t Hashcode(Key key) {
-      return key;
+      return key + 1;
     }
 
-    static inline bool IsKeyEqual(IndexIdPair kv, Key key) {
+    static inline bool IsKeyEqual(UnknownIndexIdPair kv, Key key) {
       return KeyOf(kv) == key;
     }
 
@@ -5791,8 +5884,11 @@
   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_;
 };
@@ -5929,7 +6025,7 @@
     aliased_set->AddRepresentative(place);
   }
 
-  aliased_set->EnsureAliasingForIndexes();
+  aliased_set->EnsureAliasingForUnknownIndices();
 
   return aliased_set;
 }
@@ -8721,7 +8817,7 @@
         }
 
         // All sinking candidate are known to be not aliased.
-        alloc->set_identity(AllocateObjectInstr::kNotAliased);
+        alloc->SetIdentity(kIdentityNotAliased);
 
         candidates.Add(alloc);
       }