Improve aliasing info for load elimination of array loads.

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/dart_entry.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 279 matching lines @@
 
 
 
 // Used by TryMergeDivMod.
 // Inserts a load-indexed instruction between a TRUNCDIV or MOD instruction,
 // and the using instruction. This is an intermediate step before merging.
 void FlowGraphOptimizer::AppendLoadIndexedForMerged(Definition* instr,
                                                     intptr_t ix,
                                                     intptr_t cid) {
   const intptr_t index_scale = FlowGraphCompiler::ElementSizeFor(cid);
-  ConstantInstr* index_instr = new ConstantInstr(Smi::Handle(Smi::New(ix)));
-  flow_graph()->InsertAfter(instr, index_instr, NULL, Definition::kValue);
+  ConstantInstr* index_instr =
+      flow_graph()->GetConstant(Smi::Handle(Smi::New(ix)));

[Florian Schneider, 2014/01/23 13:02:29]

Unrelated cleanup to use constant pool here.

   LoadIndexedInstr* load = new LoadIndexedInstr(new Value(instr),
                                                 new Value(index_instr),
                                                 index_scale,
                                                 cid,
                                                 Isolate::kNoDeoptId);
   instr->ReplaceUsesWith(load);
-  flow_graph()->InsertAfter(index_instr, load, NULL, Definition::kValue);
+  flow_graph()->InsertAfter(instr, load, NULL, Definition::kValue);
 }
 
 
 // Dart:
 //  var x = d % 10;
 //  var y = d ~/ 10;
 //  var z = x + y;
 //
 // IL:
 //  v4 <- %(v2, v3)
@@ skipping 4298 matching lines @@
 // 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);
+    return Alias(kIndexesAlias, 0);
+  }
+
+  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.
   static Alias Field(intptr_t id) {
-    ASSERT(id >= kFirstFieldAlias);
-    return Alias(id * 2 + 1);
+    ASSERT(id != 0);
+    return Alias(kFieldAlias, id);
   }
 
   // VMField load/stores alias each other when field offset matches.
   // TODO(vegorov) storing a context variable does not alias loading array
   // length.
   static Alias VMField(intptr_t offset_in_bytes) {
+    ASSERT(offset_in_byes >= 0);
     const intptr_t idx = offset_in_bytes / kWordSize;
-    ASSERT(idx >= kFirstFieldAlias);
-    return Alias(idx * 2);
+    return Alias(kVMFieldAlias, idx);
   }
 
   // Current context load/stores alias each other.
   static Alias CurrentContext() {
-    return Alias(kCurrentContextAlias);
+    return Alias(kCurrentContextAlias, 0);
   }
 
   // Operation does not alias anything.
   static Alias None() {
     return Alias(kNoneAlias);
   }
 
   bool IsNone() const {
     return alias_ == kNoneAlias;
   }
 
   // Convert this alias to a positive array index.
   intptr_t ToIndex() const {
     ASSERT(!IsNone());
-    return alias_ - kAliasBase;
+    return alias_;
   }
 
  private:
+  enum {
+    // 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,
+    kFieldAlias = 2,
+    kVMFieldAlias = 3,
+    kConstantIndex = 4,
+    kNumKinds = kConstantIndex + 1
+  };
+  COMPILE_ASSERT(kNumKinds < ((1 << kBitsForKind) - 1), InvalidBitFieldSize);
+
   explicit Alias(intptr_t alias) : alias_(alias) { }
 
-  enum {
-    kNoneAlias = -2,
-    kCurrentContextAlias = -1,
-    kIndexesAlias = 0,
-    kFirstFieldAlias = kIndexesAlias + 1,
-    kAliasBase = kCurrentContextAlias
-  };
+  Alias(Kind kind, uword payload)
+      : alias_(KindField::encode(kind) | PayloadField::encode(payload)) { }
+
+  uword payload() const {
+    return PayloadField::decode(alias_);
+  }
+
+  Kind kind() const {
+    return IsNone() ? kNoneAlias : KindField::decode(alias_);
+  }
+
+  typedef BitField<Kind, 0, kBitsForKind> KindField;
+  typedef BitField<uword, kBitsForKind, kBitsForPayload> PayloadField;

[Florian Schneider, 2014/01/23 13:02:29]

Instead of encoding as the ids as odd/even positive/negative integers, I changed
the encoding to use the BitField class similar to how we encode Location in the
code generator.

 
   const intptr_t alias_;
 };
 
 
 // Place describes an abstract location (e.g. field) that IR can load
 // from or store to.
 class Place : public ValueObject {
  public:
   enum Kind {
@@ skipping 298 matching lines @@
 // those that are affected by calls.
 class AliasedSet : public ZoneAllocated {
  public:
   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_() { }
+        field_ids_(),
+        max_index_id_(0),
+        index_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::Indexes();
       case Place::kField:
         return Alias::Field(
             GetInstanceFieldId(place->instance(), place->field()));
       case Place::kVMField:
         return Alias::VMField(place->offset_in_bytes());
       case Place::kContext:
         return Alias::CurrentContext();
       case Place::kNone:
         UNREACHABLE();
     }
 
     UNREACHABLE();
     return Alias::None();
   }
 
   Alias ComputeAliasForStore(Instruction* instr) {
-    if (instr->IsStoreIndexed()) {
+    StoreIndexedInstr* store_indexed = instr->AsStoreIndexed();
+    if (store_indexed != NULL) {
+      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::Indexes();
     }
 
     StoreInstanceFieldInstr* store_instance_field =
         instr->AsStoreInstanceField();
     if (store_instance_field != NULL) {
       Definition* instance = store_instance_field->instance()->definition();
       return Alias::Field(GetInstanceFieldId(instance,
                                              store_instance_field->field()));
     }
@@ skipping 10 matching lines @@
     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();
-    return (idx < sets_.length()) ? sets_[idx] : NULL;
+    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;
+    }
+
+    // Constant indexes alias all non-constant indexes. 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);
+      }
+    }
+
+    // Non-constant indexes alias all constant indexes.

[Cutch, 2014/01/24 23:07:15]

Can these two loops not be merged? 

[Florian Schneider, 2014/01/27 14:29:00]

No, at first I thought they can, but Slava pointed out that the ordering matters
here.

+    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);
+      }
+    }
+  }
+
   void AddIdForAlias(const Alias alias, intptr_t place_id) {
     const intptr_t idx = alias.ToIndex();
-
     while (sets_.length() <= idx) {
       sets_.Add(NULL);
     }
 
     if (sets_[idx] == NULL) {
       sets_[idx] = new BitVector(max_place_id());
     }
 
     sets_[idx]->Add(place_id);
   }
@@ skipping 59 matching lines @@
   // 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);
+    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));
+    }
+    return id;
+  }
+
   enum {
     kAnyInstance = -1
   };
 
   // Get or create an identifier for an instance field belonging to the
   // given instance.
   // The space of identifiers assigned to instance fields is split into
   // parts based on the instance that contains the field.
   // If compiler can prove that instance has a single SSA name in the compiled
   // function then we use that SSA name to distinguish fields of this object
@@ skipping 82 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 {
+   public:
+    typedef intptr_t Key;
+    typedef intptr_t Value;
+    typedef IndexIdPair Pair;

[Cutch, 2014/01/24 23:07:15]

Why not just pick one name for this class: Pair or IndexIdPair.

[Florian Schneider, 2014/01/27 14:29:00]

Done. I can replace Pair below with IndexIdPair, but still need the typedef
because the hash map implementation requires the type parameter to have a type
Pair defined.

+
+    IndexIdPair(Key key, Value value) : key_(key), value_(value) { }
+
+    static Key KeyOf(Pair kv) {
+      return kv.key_;
+    }
+
+    static Value ValueOf(Pair kv) {
+      return kv.value_;
+    }
+
+    static intptr_t Hashcode(Key key) {
+      return key;
+    }
+
+    static inline bool IsKeyEqual(Pair kv, Key key) {
+      return KeyOf(kv) == key;
+    }
+
+   private:
+    Key key_;
+    Value value_;
+  };
+
   const ZoneGrowableArray<Place*>& places_;
 
   const PhiPlaceMoves* phi_moves_;
 
   // Maps alias index to a set of ssa indexes corresponding to loads with the
   // 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_;
 };
 
 
 static Definition* GetStoredValue(Instruction* instr) {
   if (instr->IsStoreIndexed()) {
     return instr->AsStoreIndexed()->value()->definition();
   }
 
   StoreInstanceFieldInstr* store_instance_field = instr->AsStoreInstanceField();
   if (store_instance_field != NULL) {
@@ skipping 120 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();
+
   return aliased_set;
 }
 
 
 static bool HasSimpleTypeArguments(AllocateObjectInstr* alloc) {
   if (alloc->ArgumentCount() == 0) return true;
   ASSERT(alloc->ArgumentCount() == 2);
   Value* arg1 = alloc->PushArgumentAt(1)->value();
   if (!arg1->BindsToConstant()) return false;
 
@@ skipping 2921 matching lines @@
   }
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, alloc->cls(), *fields);
   }
 }
 
 
 }  // namespace dart