Teach LoadOptimizer to interblock multi-indirection redundancies in one 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/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 5598 matching lines @@
   GrowableArray<ZoneGrowableArray<Move>* > moves_;
 };
 
 
 // A map from aliases to a set of places sharing the alias. Additionally
 // carries a set of places that can be aliased by side-effects, essentially
 // those that are affected by calls.
 class AliasedSet : public ZoneAllocated {
  public:
   AliasedSet(Isolate* isolate,
+             DirectChainedHashMap<PointerKeyValueTrait<Place> >* places_map,
              ZoneGrowableArray<Place*>* places,
              PhiPlaceMoves* phi_moves)
       : isolate_(isolate),
+        places_map_(places_map),
         places_(*places),
         phi_moves_(phi_moves),
         aliases_(5),
         aliases_map_(),
         representatives_(),
         killed_(),
         aliased_by_effects_(new(isolate) BitVector(isolate, places->length())) {
     InsertAlias(Place::CreateAnyInstanceAnyIndexAlias(isolate_,
         kAnyInstanceAnyIndexAlias));
     for (intptr_t i = 0; i < places_.length(); i++) {
       AddRepresentative(places_[i]);
     }
     ComputeKillSets();
   }
 
   intptr_t LookupAliasId(const Place& alias) {
     const Place* result = aliases_map_.Lookup(&alias);
     return (result != NULL) ? result->id() : static_cast<intptr_t>(kNoAlias);
   }
 
   bool IsStore(Instruction* instr, BitVector** killed) {

[Florian Schneider, 2014/11/17 12:46:02]

The name is a little misleading since this method has multiple side-effects:

For stores it updates the killed bit-vector, for loads it may re-number the
place-id.

Or maybe pass a Place computed outside in and have a AliasedSet::HandleStore and
and HandleLoad method?

     bool is_load = false, is_store = false;
     Place place(instr, &is_load, &is_store);
     if (is_store && (place.kind() != Place::kNone)) {
       const intptr_t alias_id = LookupAliasId(place.ToAlias());
       if (alias_id != kNoAlias) {
         *killed = GetKilledSet(alias_id);
       } else if (!place.IsFinalField()) {
         // We encountered unknown alias: this means intrablock load forwarding
         // refined parameter of this store, for example
         //
         //     o   <- alloc()
         //     a.f <- o
         //     u   <- a.f
         //     u.x <- null ;; this store alias is *.x
         //
         // after intrablock load forwarding
         //
         //     o   <- alloc()
         //     a.f <- o
         //     o.x <- null ;; this store alias is o.x
         //
         // In this case we fallback to using place id recorded in the
         // instruction that still points to the old place with a more generic
         // alias.
         *killed = GetKilledSet(
             LookupAliasId(places_[instr->place_id()]->ToAlias()));
       }
+    } else if (is_load && (place.kind() != Place::kNone)) {
+      const Place* canonical = LookupCanonical(&place);
+      if ((canonical != NULL) &&
+          (canonical->id() != instr->AsDefinition()->place_id())) {
+        instr->AsDefinition()->set_place_id(canonical->id());
+      }
     }
     return is_store;
   }
 
   BitVector* GetKilledSet(intptr_t alias) {
     return (alias < killed_.length()) ? killed_[alias] : NULL;
   }
 
   intptr_t max_place_id() const { return places().length(); }
   bool IsEmpty() const { return max_place_id() == 0; }
 
   BitVector* aliased_by_effects() const { return aliased_by_effects_; }
 
   const ZoneGrowableArray<Place*>& places() const {
     return places_;
   }
 
+  Place* LookupCanonical(Place* place) const {
+    return places_map_->Lookup(place);
+  }
+
   void PrintSet(BitVector* set) {
     bool comma = false;
     for (BitVector::Iterator it(set);
          !it.Done();
          it.Advance()) {
       if (comma) {
         OS::Print(", ");
       }
       OS::Print("%s", places_[it.Current()]->ToCString());
       comma = true;
@@ skipping 351 matching lines @@
       // If the allocation site is marked as aliased conservatively mark
       // any values stored into the object aliased too.
       if (defn->Identity().IsAliased()) {
         MarkStoredValuesEscaping(defn);
       }
     }
   }
 
   Isolate* isolate_;
 
+  DirectChainedHashMap<PointerKeyValueTrait<Place> >* places_map_;
+
   const ZoneGrowableArray<Place*>& places_;
 
   const PhiPlaceMoves* phi_moves_;
 
   // A list of all seen aliases and a map that allows looking up canonical
   // alias object.
   GrowableArray<const Place*> aliases_;
   DirectChainedHashMap<PointerKeyValueTrait<const Place> > aliases_map_;
 
   // Maps alias id to set of ids of places representing the alias.
@@ skipping 149 matching lines @@
   if ((mode == kOptimizeLoads) && !has_loads) {
     return NULL;
   }
   if ((mode == kOptimizeStores) && !has_stores) {
     return NULL;
   }
 
   PhiPlaceMoves* phi_moves = ComputePhiMoves(map, places);
 
   // Build aliasing sets mapping aliases to loads.
-  return new(isolate) AliasedSet(isolate, places, phi_moves);
+  return new(isolate) AliasedSet(isolate, map, places, phi_moves);
 }
 
 
 class LoadOptimizer : public ValueObject {
  public:
-  LoadOptimizer(FlowGraph* graph,
-                AliasedSet* aliased_set,
-                DirectChainedHashMap<PointerKeyValueTrait<Place> >* map)
+  LoadOptimizer(FlowGraph* graph, AliasedSet* aliased_set)
       : graph_(graph),
-        map_(map),
         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),
         congruency_worklist_(6),
@@ skipping 25 matching lines @@
 
     DirectChainedHashMap<PointerKeyValueTrait<Place> > map;
     AliasedSet* aliased_set = NumberPlaces(graph, &map, kOptimizeLoads);
     if ((aliased_set != NULL) && !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);
+      LoadOptimizer load_optimizer(graph, aliased_set);
       return load_optimizer.Optimize();
     }
     return false;
   }
 
  private:
   bool Optimize() {
     ComputeInitialSets();
     ComputeOutSets();
     ComputeOutValues();
@@ skipping 49 matching lines @@
           // 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) ||
               (array_store->class_id() == kTypedDataFloat32ArrayCid) ||
               (array_store->class_id() == kTypedDataFloat32x4ArrayCid)) {
             bool is_load = false, is_store = false;
             Place store_place(instr, &is_load, &is_store);
             ASSERT(!is_load && is_store);
-            Place* place = map_->Lookup(&store_place);
+            Place* place = aliased_set_->LookupCanonical(&store_place);
             if (place != NULL) {
               // Store has a corresponding numbered place that might have a
               // load. Try forwarding stored value to it.
               gen->Add(place->id());
               if (out_values == NULL) out_values = CreateBlockOutValues();
               (*out_values)[place->id()] = GetStoredValue(instr);
             }
           }
 
           ASSERT(!instr->IsDefinition() ||
@@ skipping 3649 matching lines @@
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits_collector_.exits().length(); i++) {
     CreateMaterializationAt(
         exits_collector_.exits()[i], alloc, *slots);
   }
 }
 
 
 }  // namespace dart