Optimize static field and context load/stores as part of CSE pass.

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 3045 matching lines @@
     }
   }
 }
 
 
 static bool IsLoadEliminationCandidate(Definition* def) {
   // Immutable loads (not affected by side effects) are handled
   // in the DominatorBasedCSE pass.
   // TODO(fschneider): Extend to other load instructions.
   return (def->IsLoadField() && def->AffectedBySideEffect())
-      || def->IsLoadIndexed();
+      || def->IsLoadIndexed()
+      || def->IsLoadStaticField()
+      || def->IsCurrentContext();
 }
 
 
-static intptr_t ComputeLoadOffsetInWords(Definition* defn) {
-  if (defn->IsLoadIndexed()) {
-    // We are assuming that LoadField is never used to load the first word.
-    return 0;
-  }
-
-  LoadFieldInstr* load_field = defn->AsLoadField();
-  if (load_field != NULL) {
-    const intptr_t idx = load_field->offset_in_bytes() / kWordSize;
-    ASSERT(idx > 0);
-    return idx;
-  }
-
-  UNREACHABLE();
-  return 0;
-}
-
-
-static bool IsInterferingStore(Instruction* instr,
-                               intptr_t* offset_in_words) {
-  if (instr->IsStoreIndexed()) {
-    // We are assuming that LoadField is never used to load the first word.
-    *offset_in_words = 0;
-    return true;
-  }
-
-  StoreInstanceFieldInstr* store_instance_field = instr->AsStoreInstanceField();
-  if (store_instance_field != NULL) {
-    ASSERT(store_instance_field->field().Offset() != 0);
-    *offset_in_words = store_instance_field->field().Offset() / kWordSize;
-    return true;
-  }
-
-  StoreVMFieldInstr* store_vm_field = instr->AsStoreVMField();
-  if (store_vm_field != NULL) {
-    ASSERT(store_vm_field->offset_in_bytes() != 0);
-    *offset_in_words = store_vm_field->offset_in_bytes() / kWordSize;
-    return true;
-  }
-
-  return false;
-}
+// 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.

[srdjan, 2013/04/22 22:00:05]

Optional: There are various TODO-s which probably will require Alias to become
ZoneAllocated, we could do it now.

[Vyacheslav Egorov (Google), 2013/04/23 11:00:06]

I'll keep it ValueObject for now. I don't think it'll becoeme ZoneObject right
away.

+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.

[srdjan, 2013/04/22 22:00:05]

You could (as TODO) also incorporate the index ranges.

[Vyacheslav Egorov (Google), 2013/04/23 11:00:06]

I have doubts that it's common to have disjoint ranges.

Most ranges would be [0, N] and thus intersect.

+  static Alias Indices() {

[srdjan, 2013/04/22 22:00:05]

We are using indexes instead of indeces in the VM.

[Vyacheslav Egorov (Google), 2013/04/23 11:00:06]

Done.

+    return Alias(kIndicesAlias);
+  }
+
+  // Field load/stores alias each other when field offset matches.
+  // TODO(vegorov): use field information to disambiguate load/stores into
+  // different fields that by accident share offset.
+  static Alias Field(intptr_t offset_in_bytes) {
+    const intptr_t idx = offset_in_bytes / kWordSize;
+    ASSERT(idx >= kFirstFieldAlias);
+    return Alias(idx * 2);
+  }
+
+  // Static field load/stores alias each other.
+  // AliasedSet assigns ids to static fields during optimization phase.
+  static Alias StaticField(intptr_t id) {
+    ASSERT(id >= kFirstFieldAlias);
+    return Alias(id * 2 + 1);
+  }
+
+  // Current context load/stores alias each other.
+  static Alias CurrentContext() {
+    return Alias(kCurrentContextAlias);
+  }
+
+  // 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;
+  }
+
+ private:
+  explicit Alias(intptr_t alias) : alias_(alias) { }
+
+  enum {
+    kNoneAlias = -2,
+    kCurrentContextAlias = -1,
+    kIndicesAlias = 0,
+    kFirstFieldAlias = kIndicesAlias + 1,
+    kAliasBase = kCurrentContextAlias
+  };
+
+  intptr_t alias_;

[srdjan, 2013/04/22 22:00:05]

const

[Vyacheslav Egorov (Google), 2013/04/23 11:00:06]

Done.

+};
+
+
+// Set mapping alias to a list of loads sharing this alias.
+class AliasedSet : public ZoneAllocated {
+ public:
+  explicit AliasedSet(intptr_t max_expr_id)
+      : max_expr_id_(max_expr_id),
+        sets_(),
+        field_ids_(),
+        max_field_id_(0) { }
+
+  Alias ComputeAliasForLoad(Definition* defn) {
+    if (defn->IsLoadIndexed()) {
+      // We are assuming that LoadField is never used to load the first word.
+      return Alias::Indices();
+    }
+
+    LoadFieldInstr* load_field = defn->AsLoadField();
+    if (load_field != NULL) {
+      return Alias::Field(load_field->offset_in_bytes());
+    }
+
+    if (defn->IsCurrentContext()) {
+      return Alias::CurrentContext();
+    }
+
+    LoadStaticFieldInstr* load_static_field = defn->AsLoadStaticField();
+    if (load_static_field != NULL) {
+      return Alias::StaticField(GetFieldId(load_static_field->field()));
+    }
+
+    UNREACHABLE();
+    return Alias::None();
+  }
+
+  Alias ComputeAliasForStore(Instruction* instr) {
+    if (instr->IsStoreIndexed()) {
+      return Alias::Indices();
+    }
+
+    StoreInstanceFieldInstr* store_instance_field =
+        instr->AsStoreInstanceField();
+    if (store_instance_field != NULL) {
+      return Alias::Field(store_instance_field->field().Offset());
+    }
+
+    StoreVMFieldInstr* store_vm_field = instr->AsStoreVMField();
+    if (store_vm_field != NULL) {
+      return Alias::Field(store_vm_field->offset_in_bytes());
+    }
+
+    if (instr->IsStoreContext() || instr->IsChainContext()) {
+      return Alias::CurrentContext();
+    }
+
+    StoreStaticFieldInstr* store_static_field = instr->AsStoreStaticField();
+    if (store_static_field != NULL) {
+      return Alias::StaticField(GetFieldId(store_static_field->field()));
+    }
+
+    return Alias::None();
+  }
+
+  bool Contains(Alias alias) {

[srdjan, 2013/04/22 22:00:05]

const

[Vyacheslav Egorov (Google), 2013/04/23 11:00:06]

Done.

+    const intptr_t idx = alias.ToIndex();
+    return (idx < sets_.length()) && (sets_[idx] != NULL);
+  }
+
+  BitVector* Get(Alias alias) {

[srdjan, 2013/04/22 22:00:05]

const

[Vyacheslav Egorov (Google), 2013/04/23 11:00:06]

Done.

+    ASSERT(Contains(alias));
+    return sets_[alias.ToIndex()];
+  }
+
+  void Add(Alias alias, intptr_t ssa_index) {
+    const intptr_t idx = alias.ToIndex();
+
+    while (sets_.length() <= idx) {
+     sets_.Add(NULL);

[srdjan, 2013/04/22 22:00:05]

indent

[Vyacheslav Egorov (Google), 2013/04/23 11:00:06]

Done.

+    }
+
+    if (sets_[idx] == NULL) {
+      sets_[idx] = new BitVector(max_expr_id_);
+    }
+
+    sets_[idx]->Add(ssa_index);
+  }
+
+  intptr_t max_expr_id() const { return max_expr_id_; }
+  bool IsEmpty() const { return max_expr_id_ == 0; }
+
+ private:
+  const intptr_t max_expr_id_;
+  GrowableArray<BitVector*> sets_;

[srdjan, 2013/04/22 22:00:05]

Add comment what sets_ represents.

[Vyacheslav Egorov (Google), 2013/04/23 11:00:06]

Done.

+
+  // Get id assigned to the given field. Assign a new id if the field is seen
+  // for the first time.
+  intptr_t GetFieldId(const Field& field) {
+    intptr_t id = field_ids_.Lookup(&field);
+    if (id == 0) {
+      id = ++max_field_id_;
+      field_ids_.Insert(FieldIdPair(&field, id));
+    }
+    return id;
+  }
+
+  class FieldIdPair {
+   public:
+    typedef const Field* Key;
+    typedef intptr_t Value;
+    typedef FieldIdPair Pair;
+
+    FieldIdPair(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 inline intptr_t Hashcode(Key key) {

[srdjan, 2013/04/22 22:00:05]

Why the inline? The code in the body is not that lightweight, it seems to me.

[Vyacheslav Egorov (Google), 2013/04/23 11:00:06]

Done.

+      return String::Handle(key->name()).Hash();
+    }
+
+    static inline bool IsKeyEqual(Pair kv, Key key) {
+      return KeyOf(kv)->raw() == key->raw();
+    }
+
+   private:
+    Key key_;
+    Value value_;
+  };
+
+  // Table mapping static field to their id used during optimization pass.
+  DirectChainedHashMap<FieldIdPair> field_ids_;
+  intptr_t max_field_id_;
+};
 
 
 static Definition* GetStoredValue(Instruction* instr) {
   if (instr->IsStoreIndexed()) {
     return instr->AsStoreIndexed()->value()->definition();
   }
 
   StoreInstanceFieldInstr* store_instance_field = instr->AsStoreInstanceField();
   if (store_instance_field != NULL) {
     return store_instance_field->value()->definition();
   }
 
   StoreVMFieldInstr* store_vm_field = instr->AsStoreVMField();
   if (store_vm_field != NULL) {
     return store_vm_field->value()->definition();
   }
 
+  StoreStaticFieldInstr* store_static_field = instr->AsStoreStaticField();
+  if (store_static_field != NULL) {
+    return store_static_field->value()->definition();
+  }
+
+  if (instr->IsStoreContext() || instr->IsChainContext()) {
+    return instr->InputAt(0)->definition();
+  }
+
   UNREACHABLE();  // Should only be called for supported store instructions.
   return NULL;
 }
 
 
 // KeyValueTrait used for numbering of loads. Allows to lookup loads
 // corresponding to stores.
 class LoadKeyValueTrait {
  public:
   typedef Definition* Value;
-  typedef Definition* Key;
+  typedef Instruction* Key;
   typedef Definition* Pair;
 
   static Key KeyOf(Pair kv) {
     return kv;
   }
 
   static Value ValueOf(Pair kv) {
     return kv;
   }
 
@@ skipping 14 matching lines @@
       object = load_field->value()->definition()->ssa_temp_index();
       location = load_field->offset_in_bytes();
     } else if (key->IsStoreInstanceField()) {
       StoreInstanceFieldInstr* store_field = key->AsStoreInstanceField();
       object = store_field->instance()->definition()->ssa_temp_index();
       location = store_field->field().Offset();
     } else if (key->IsStoreVMField()) {
       StoreVMFieldInstr* store_field = key->AsStoreVMField();
       object = store_field->dest()->definition()->ssa_temp_index();
       location = store_field->offset_in_bytes();
+    } else if (key->IsLoadStaticField()) {
+      LoadStaticFieldInstr* load_static_field = key->AsLoadStaticField();
+      object = String::Handle(load_static_field->field().name()).Hash();
+    } else if (key->IsStoreStaticField()) {
+      StoreStaticFieldInstr* store_static_field = key->AsStoreStaticField();
+      object = String::Handle(store_static_field->field().name()).Hash();
+    } else {
+      ASSERT(key->IsStoreContext() ||
+             key->IsCurrentContext() ||
+             key->IsChainContext());
     }
 
     return object * 31 + location;
   }
 
   static inline bool IsKeyEqual(Pair kv, Key key) {
     if (kv->Equals(key)) return true;
 
     if (kv->IsLoadIndexed()) {
       if (key->IsStoreIndexed()) {
         LoadIndexedInstr* load_indexed = kv->AsLoadIndexed();
         StoreIndexedInstr* store_indexed = key->AsStoreIndexed();
         return load_indexed->array()->Equals(store_indexed->array()) &&
                load_indexed->index()->Equals(store_indexed->index());
       }
       return false;
     }
 
+    if (kv->IsLoadStaticField()) {
+      if (key->IsStoreStaticField()) {
+        LoadStaticFieldInstr* load_static_field = kv->AsLoadStaticField();
+        StoreStaticFieldInstr* store_static_field = key->AsStoreStaticField();
+        return load_static_field->field().raw() ==
+            store_static_field->field().raw();
+      }
+      return false;
+    }
+
+    if (kv->IsCurrentContext()) {
+      return key->IsStoreContext() || key->IsChainContext();
+    }
+
     ASSERT(kv->IsLoadField());
     LoadFieldInstr* load_field = kv->AsLoadField();
     if (key->IsStoreVMField()) {
       StoreVMFieldInstr* store_field = key->AsStoreVMField();
       return load_field->value()->Equals(store_field->dest()) &&
              (load_field->offset_in_bytes() == store_field->offset_in_bytes());
     } else if (key->IsStoreInstanceField()) {
       StoreInstanceFieldInstr* store_field = key->AsStoreInstanceField();
       return load_field->value()->Equals(store_field->instance()) &&
              (load_field->offset_in_bytes() == store_field->field().Offset());
     }
 
     return false;
   }
 };
 
 
-static intptr_t NumberLoadExpressions(
+static AliasedSet* NumberLoadExpressions(
     FlowGraph* graph,
-    DirectChainedHashMap<LoadKeyValueTrait>* map,
-    GrowableArray<BitVector*>* kill_by_offs) {
+    DirectChainedHashMap<LoadKeyValueTrait>* map) {
   intptr_t expr_id = 0;
 
   // Loads representing different expression ids will be collected and
   // used to build per offset kill sets.
   GrowableArray<Definition*> loads(10);
 
   for (BlockIterator it = graph->reverse_postorder_iterator();
        !it.Done();
        it.Advance()) {
     BlockEntryInstr* block = it.Current();
     for (ForwardInstructionIterator instr_it(block);
          !instr_it.Done();
          instr_it.Advance()) {
       Definition* defn = instr_it.Current()->AsDefinition();
       if ((defn == NULL) || !IsLoadEliminationCandidate(defn)) {
         continue;
       }
       Definition* result = map->Lookup(defn);
       if (result == NULL) {
         map->Insert(defn);
         defn->set_expr_id(expr_id++);
         loads.Add(defn);
       } else {
         defn->set_expr_id(result->expr_id());
       }
     }
   }
 
-  // Build per offset kill sets. Any store interferes only with loads from
-  // the same offset.
+  // Build aliasing sets mapping aliases to loads.
+  AliasedSet* aliased_set = new AliasedSet(expr_id);
   for (intptr_t i = 0; i < loads.length(); i++) {
     Definition* defn = loads[i];
-
-    const intptr_t offset_in_words = ComputeLoadOffsetInWords(defn);
-    while (kill_by_offs->length() <= offset_in_words) {
-      kill_by_offs->Add(NULL);
-    }
-    if ((*kill_by_offs)[offset_in_words] == NULL) {
-      (*kill_by_offs)[offset_in_words] = new BitVector(expr_id);
-    }
-    (*kill_by_offs)[offset_in_words]->Add(defn->expr_id());
+    aliased_set->Add(aliased_set->ComputeAliasForLoad(defn), defn->expr_id());
   }
-
-  return expr_id;
+  return aliased_set;
 }
 
 
 class LoadOptimizer : public ValueObject {
  public:
   LoadOptimizer(FlowGraph* graph,
-                intptr_t max_expr_id,
-                DirectChainedHashMap<LoadKeyValueTrait>* map,
-                const GrowableArray<BitVector*>& kill_by_offset)
+                AliasedSet* aliased_set,
+                DirectChainedHashMap<LoadKeyValueTrait>* map)
       : graph_(graph),
         map_(map),
-        max_expr_id_(max_expr_id),
-        kill_by_offset_(kill_by_offset),
+        aliased_set_(aliased_set),
         in_(graph_->preorder().length()),
         out_(graph_->preorder().length()),
         gen_(graph_->preorder().length()),
         kill_(graph_->preorder().length()),
         exposed_values_(graph_->preorder().length()),
         out_values_(graph_->preorder().length()),
         phis_(5),
         worklist_(5),
-        in_worklist_(NULL) {
+        in_worklist_(NULL),
+        forwarded_(false) {
     const intptr_t num_blocks = graph_->preorder().length();
     for (intptr_t i = 0; i < num_blocks; i++) {
-      out_.Add(new BitVector(max_expr_id_));
-      gen_.Add(new BitVector(max_expr_id_));
-      kill_.Add(new BitVector(max_expr_id_));
-      in_.Add(new BitVector(max_expr_id_));
+      out_.Add(new BitVector(aliased_set_->max_expr_id()));
+      gen_.Add(new BitVector(aliased_set_->max_expr_id()));
+      kill_.Add(new BitVector(aliased_set_->max_expr_id()));
+      in_.Add(new BitVector(aliased_set_->max_expr_id()));
 
       exposed_values_.Add(NULL);
       out_values_.Add(NULL);
     }
   }
 
-  void Optimize() {
+  bool Optimize() {
     ComputeInitialSets();
     ComputeOutValues();
     ForwardLoads();
     EmitPhis();
+    return forwarded_;
   }
 
  private:
   // Compute sets of loads generated and killed by each block.
   // Additionally compute upwards exposed and generated loads for each block.
   // Exposed loads are those that can be replaced if a corresponding
   // reaching load will be found.
   // Loads that are locally redundant will be replaced as we go through
   // instructions.
   void ComputeInitialSets() {
     for (BlockIterator block_it = graph_->reverse_postorder_iterator();
          !block_it.Done();
          block_it.Advance()) {
       BlockEntryInstr* block = block_it.Current();
       const intptr_t preorder_number = block->preorder_number();
 
       BitVector* kill = kill_[preorder_number];
       BitVector* gen = gen_[preorder_number];
 
       ZoneGrowableArray<Definition*>* exposed_values = NULL;
       ZoneGrowableArray<Definition*>* out_values = NULL;
 
       for (ForwardInstructionIterator instr_it(block);
            !instr_it.Done();
            instr_it.Advance()) {
         Instruction* instr = instr_it.Current();
 
-        intptr_t offset_in_words = 0;
-        if (IsInterferingStore(instr, &offset_in_words)) {
+        const Alias alias = aliased_set_->ComputeAliasForStore(instr);
+        if (!alias.IsNone()) {
           // Interfering stores kill only loads from the same offset.
-          if ((offset_in_words < kill_by_offset_.length()) &&
-              (kill_by_offset_[offset_in_words] != NULL)) {
-            kill->AddAll(kill_by_offset_[offset_in_words]);
+          if (aliased_set_->Contains(alias)) {
+            BitVector* killed = aliased_set_->Get(alias);
+            kill->AddAll(killed);
             // There is no need to clear out_values when clearing GEN set
             // because only those values that are in the GEN set
             // will ever be used.
-            gen->RemoveAll(kill_by_offset_[offset_in_words]);
+            gen->RemoveAll(killed);
 
             // Only forward stores to normal arrays and float64 arrays
             // to loads because other array stores (intXX/uintXX/float32)
             // may implicitly convert the value stored.
             StoreIndexedInstr* array_store = instr->AsStoreIndexed();
             if (array_store == NULL ||
                 array_store->class_id() == kArrayCid ||
                 array_store->class_id() == kTypedDataFloat64ArrayCid) {
-              Definition* load = map_->Lookup(instr->AsDefinition());
+              Definition* load = map_->Lookup(instr);
               if (load != NULL) {
                 // Store has a corresponding numbered load. Try forwarding
                 // stored value to it.
                 gen->Add(load->expr_id());
                 if (out_values == NULL) out_values = CreateBlockOutValues();
                 (*out_values)[load->expr_id()] = GetStoredValue(instr);
               }
             }
           }
-          ASSERT(instr->IsDefinition() &&
+          ASSERT(!instr->IsDefinition() ||
                  !IsLoadEliminationCandidate(instr->AsDefinition()));
           continue;
         }
 
         // Other instructions with side effects kill all loads.
         if (instr->HasSideEffect()) {
           kill->SetAll();
           // There is no need to clear out_values when clearing GEN set
           // because only those values that are in the GEN set
           // will ever be used.
@@ skipping 14 matching lines @@
           Definition* replacement = (*out_values)[expr_id];
           EnsureSSATempIndex(graph_, defn, replacement);
           if (FLAG_trace_optimization) {
             OS::Print("Replacing load v%"Pd" with v%"Pd"\n",
                       defn->ssa_temp_index(),
                       replacement->ssa_temp_index());
           }
 
           defn->ReplaceUsesWith(replacement);
           instr_it.RemoveCurrentFromGraph();
+          forwarded_ = true;
           continue;
         } else if (!kill->Contains(expr_id)) {
           // This is an exposed load: it is the first representative of a
           // given expression id and it is not killed on the path from
           // the block entry.
           if (exposed_values == NULL) {
             static const intptr_t kMaxExposedValuesInitialSize = 5;
             exposed_values = new ZoneGrowableArray<Definition*>(
-                Utils::Minimum(kMaxExposedValuesInitialSize, max_expr_id_));
+                Utils::Minimum(kMaxExposedValuesInitialSize,
+                               aliased_set_->max_expr_id()));
           }
 
           exposed_values->Add(defn);
         }
 
         gen->Add(expr_id);
 
         if (out_values == NULL) out_values = CreateBlockOutValues();
         (*out_values)[expr_id] = defn;
       }
 
       out_[preorder_number]->CopyFrom(gen);
       exposed_values_[preorder_number] = exposed_values;
       out_values_[preorder_number] = out_values;
     }
   }
 
   // Compute OUT sets and corresponding out_values mappings by propagating them
   // iteratively until fix point is reached.
   // No replacement is done at this point and thus any out_value[expr_id] is
   // changed at most once: from NULL to an actual value.
   // When merging incoming loads we might need to create a phi.
   // These phis are not inserted at the graph immediately because some of them
   // might become redundant after load forwarding is done.
   void ComputeOutValues() {
-    BitVector* temp = new BitVector(max_expr_id_);
+    BitVector* temp = new BitVector(aliased_set_->max_expr_id());
 
     bool changed = true;
     while (changed) {
       changed = false;
 
       for (BlockIterator block_it = graph_->reverse_postorder_iterator();
            !block_it.Done();
            block_it.Advance()) {
         BlockEntryInstr* block = block_it.Current();
 
@@ skipping 153 matching lines @@
 
           if (FLAG_trace_optimization) {
             OS::Print("Replacing load v%"Pd" with v%"Pd"\n",
                       load->ssa_temp_index(),
                       replacement->ssa_temp_index());
           }
 
           load->ReplaceUsesWith(replacement);
           load->RemoveFromGraph();
           load->SetReplacement(replacement);
+          forwarded_ = true;
         }
       }
     }
   }
 
   // Check if the given phi take the same value on all code paths.
   // Eliminate it as redundant if this is the case.
   // When analyzing phi operands assumes that only generated during
   // this load phase can be redundant. They can be distinguished because
   // they are not marked alive.
@@ skipping 57 matching lines @@
       } else {
         for (intptr_t j = phi->InputCount() - 1; j >= 0; --j) {
           phi->InputAt(j)->RemoveFromUseList();
         }
       }
     }
   }
 
   ZoneGrowableArray<Definition*>* CreateBlockOutValues() {
     ZoneGrowableArray<Definition*>* out =
-        new ZoneGrowableArray<Definition*>(max_expr_id_);
-    for (intptr_t i = 0; i < max_expr_id_; i++) {
+        new ZoneGrowableArray<Definition*>(aliased_set_->max_expr_id());
+    for (intptr_t i = 0; i < aliased_set_->max_expr_id(); i++) {
       out->Add(NULL);
     }
     return out;
   }
 
   FlowGraph* graph_;
   DirectChainedHashMap<LoadKeyValueTrait>* map_;
-  const intptr_t max_expr_id_;
 
   // Mapping between field offsets in words and expression ids of loads from
   // that offset.
-  const GrowableArray<BitVector*>& kill_by_offset_;
+  AliasedSet* aliased_set_;
 
   // Per block sets of expression ids for loads that are: incoming (available
   // on the entry), outgoing (available on the exit), generated and killed.
   GrowableArray<BitVector*> in_;
   GrowableArray<BitVector*> out_;
   GrowableArray<BitVector*> gen_;
   GrowableArray<BitVector*> kill_;
 
   // Per block list of upwards exposed loads.
   GrowableArray<ZoneGrowableArray<Definition*>*> exposed_values_;
 
   // Per block mappings between expression ids and outgoing definitions that
   // represent those ids.
   GrowableArray<ZoneGrowableArray<Definition*>*> out_values_;
 
   // List of phis generated during ComputeOutValues and ForwardLoads.
   // Some of these phis might be redundant and thus a separate pass is
   // needed to emit only non-redundant ones.
   GrowableArray<PhiInstr*> phis_;
 
   // Auxiliary worklist used by redundant phi elimination.
   GrowableArray<PhiInstr*> worklist_;
   BitVector* in_worklist_;
 
+  // True if any load was eliminated.
+  bool forwarded_;
+
   DISALLOW_COPY_AND_ASSIGN(LoadOptimizer);
 };
 
 
 bool DominatorBasedCSE::Optimize(FlowGraph* graph) {
   bool changed = false;
   if (FLAG_load_cse) {
     GrowableArray<BitVector*> kill_by_offs(10);
     DirectChainedHashMap<LoadKeyValueTrait> map;
-    const intptr_t max_expr_id =
-        NumberLoadExpressions(graph, &map, &kill_by_offs);
-    if (max_expr_id > 0) {
-      LoadOptimizer load_optimizer(graph, max_expr_id, &map, kill_by_offs);
-      load_optimizer.Optimize();
+    AliasedSet* aliased_set = NumberLoadExpressions(graph, &map);
+    if (!aliased_set->IsEmpty()) {
+      // If any loads were forwarded return true from Optimize to run load
+      // forwarding again. This will allow to forward chains of loads.
+      // This is especially important for context variables as they are built
+      // as loads from loaded context.
+      // TODO(vegorov): renumber newly discovered congruences during the
+      // forwarding to forward chains without running whole pass twice.
+      LoadOptimizer load_optimizer(graph, aliased_set, &map);
+      changed = load_optimizer.Optimize() || changed;
     }
   }
 
   DirectChainedHashMap<PointerKeyValueTrait<Instruction> > map;
   changed = OptimizeRecursive(graph, graph->graph_entry(), &map) || changed;
 
   return changed;
 }
 
 
@@ skipping 1386 matching lines @@
   if (changed) {
     // We may have changed the block order and the dominator tree.
     flow_graph->DiscoverBlocks();
     GrowableArray<BitVector*> dominance_frontier;
     flow_graph->ComputeDominators(&dominance_frontier);
   }
 }
 
 
 }  // namespace dart