Implement simple dead store elimination.

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"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
 #include "vm/hash_map.h"
 #include "vm/il_printer.h"
 #include "vm/intermediate_language.h"
 #include "vm/object_store.h"
 #include "vm/parser.h"
 #include "vm/resolver.h"
 #include "vm/scopes.h"
 #include "vm/stack_frame.h"
 #include "vm/symbols.h"
 
 namespace dart {
 
 DEFINE_FLAG(bool, array_bounds_check_elimination, true,
     "Eliminate redundant bounds checks.");
 DEFINE_FLAG(int, getter_setter_ratio, 13,
     "Ratio of getter/setter usage used for double field unboxing heuristics");
 DEFINE_FLAG(bool, load_cse, true, "Use redundant load elimination.");
+DEFINE_FLAG(bool, dead_store_elimination, true, "Eliminate dead stores");
 DEFINE_FLAG(int, max_polymorphic_checks, 4,
     "Maximum number of polymorphic check, otherwise it is megamorphic.");
 DEFINE_FLAG(int, max_equality_polymorphic_checks, 32,
     "Maximum number of polymorphic checks in equality operator,"
     " otherwise use megamorphic dispatch.");
 DEFINE_FLAG(bool, remove_redundant_phis, true, "Remove redundant phis.");
 DEFINE_FLAG(bool, trace_constant_propagation, false,
     "Print constant propagation and useless code elimination.");
 DEFINE_FLAG(bool, trace_load_optimization, false,
     "Print live sets for load optimization pass.");
@@ skipping 4051 matching lines @@
     } else {
       call_with_checks = true;
     }
     PolymorphicInstanceCallInstr* call =
         new PolymorphicInstanceCallInstr(instr, unary_checks,
                                          call_with_checks);
     instr->ReplaceWith(call, current_iterator());
   }
 }
 
+
 void FlowGraphOptimizer::VisitStaticCall(StaticCallInstr* call) {
   MethodRecognizer::Kind recognized_kind =
       MethodRecognizer::RecognizeKind(call->function());
   MathUnaryInstr::MathUnaryKind unary_kind;
   switch (recognized_kind) {
     case MethodRecognizer::kMathSqrt:
       unary_kind = MathUnaryInstr::kSqrt;
       break;
     case MethodRecognizer::kMathSin:
       unary_kind = MathUnaryInstr::kSin;
@@ skipping 983 matching lines @@
   Hoist(it, pre_header, current);
 
   // Replace value we are checking with phi's input.
   current->value()->BindTo(phi->InputAt(non_smi_input)->definition());
 
   phi->UpdateType(CompileType::FromCid(kSmiCid));
 }
 
 
 // Load instructions handled by load elimination.
-static bool IsCandidateLoad(Instruction* instr) {
+static bool IsLoadEliminationCandidate(Instruction* instr) {
   return instr->IsLoadField()
       || instr->IsLoadIndexed()
       || instr->IsLoadStaticField()
       || instr->IsCurrentContext();
 }
 
 
 static bool IsLoopInvariantLoad(ZoneGrowableArray<BitVector*>* sets,
                                 intptr_t loop_header_index,
                                 Instruction* instr) {
-  return IsCandidateLoad(instr) &&
+  return IsLoadEliminationCandidate(instr) &&
       (sets != NULL) &&
       instr->HasPlaceId() &&
       ((*sets)[loop_header_index] != NULL) &&
       (*sets)[loop_header_index]->Contains(instr->place_id());
 }
 
 
 void LICM::Optimize() {
   if (!flow_graph()->parsed_function().function().
           allows_hoisting_check_class()) {
@@ skipping 45 matching lines @@
             TryHoistCheckSmiThroughPhi(
                 &it, header, pre_header, current->AsCheckSmi());
           }
         }
       }
     }
   }
 }
 
 
-static bool IsLoadEliminationCandidate(Definition* def) {
-  return def->IsLoadField()
-      || def->IsLoadIndexed()
-      || def->IsLoadStaticField()
-      || def->IsCurrentContext();
-}
-
-
 // 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.
@@ skipping 109 matching lines @@
       : ValueObject(),
         kind_(other.kind_),
         representation_(other.representation_),
         instance_(other.instance_),
         raw_selector_(other.raw_selector_),
         id_(other.id_) {
   }
 
   // Construct a place from instruction if instruction accesses any place.
   // Otherwise constructs kNone place.
-  Place(Instruction* instr, bool* is_load)
+  Place(Instruction* instr, bool* is_load, bool* is_store)
       : kind_(kNone),
         representation_(kNoRepresentation),
         instance_(NULL),
         raw_selector_(0),
         id_(0) {
     switch (instr->tag()) {
       case Instruction::kLoadField: {
         LoadFieldInstr* load_field = instr->AsLoadField();
         representation_ = load_field->representation();
         instance_ = load_field->instance()->definition()->OriginalDefinition();
@@ skipping 14 matching lines @@
         representation_ = store->RequiredInputRepresentation(
             StoreInstanceFieldInstr::kValuePos);
         instance_ = store->instance()->definition()->OriginalDefinition();
         if (!store->field().IsNull()) {
           kind_ = kField;
           field_ = &store->field();
         } else {
           kind_ = kVMField;
           offset_in_bytes_ = store->offset_in_bytes();
         }
+        *is_store = true;
         break;
       }
 
       case Instruction::kLoadStaticField:
         kind_ = kField;
         representation_ = instr->AsLoadStaticField()->representation();
         field_ = &instr->AsLoadStaticField()->StaticField();
         *is_load = true;
         break;
 
       case Instruction::kStoreStaticField:
         kind_ = kField;
         representation_ = instr->AsStoreStaticField()->
             RequiredInputRepresentation(StoreStaticFieldInstr::kValuePos);
         field_ = &instr->AsStoreStaticField()->field();
+        *is_store = true;
         break;
 
       case Instruction::kLoadIndexed: {
         LoadIndexedInstr* load_indexed = instr->AsLoadIndexed();
         kind_ = kIndexed;
         representation_ = load_indexed->representation();
         instance_ = load_indexed->array()->definition()->OriginalDefinition();
         index_ = load_indexed->index()->definition();
         *is_load = true;
         break;
       }
 
       case Instruction::kStoreIndexed: {
         StoreIndexedInstr* store_indexed = instr->AsStoreIndexed();
         kind_ = kIndexed;
         representation_ = store_indexed->
             RequiredInputRepresentation(StoreIndexedInstr::kValuePos);
         instance_ = store_indexed->array()->definition()->OriginalDefinition();
         index_ = store_indexed->index()->definition();
+        *is_store = true;
         break;
       }
 
       case Instruction::kCurrentContext:
         kind_ = kContext;
         ASSERT(instr->AsCurrentContext()->representation() == kTagged);
         representation_ = kTagged;
         *is_load = true;
         break;
 
       case Instruction::kStoreContext:
         kind_ = kContext;
         ASSERT(instr->AsStoreContext()->RequiredInputRepresentation(
             StoreContextInstr::kValuePos) == kTagged);
         representation_ = kTagged;
+        *is_store = true;
         break;
 
       default:
         break;
     }
   }
 
   intptr_t id() const { return id_; }
   void set_id(intptr_t id) { id_ = id; }
 
@@ skipping 753 matching lines @@
         phi_moves->CreateOutgoingMove(block->PredecessorAt(j),
                                       result->id(),
                                       place->id());
       }
     }
   }
 
   return phi_moves;
 }
 
+
+enum CSEMode {
+  kOptimizeLoads,
+  kOptimizeStores
+};
+
+
 static AliasedSet* NumberPlaces(
     FlowGraph* graph,
-    DirectChainedHashMap<PointerKeyValueTrait<Place> >* map) {
+    DirectChainedHashMap<PointerKeyValueTrait<Place> >* map,
+    CSEMode mode) {
   // Loads representing different expression ids will be collected and
   // used to build per offset kill sets.
   ZoneGrowableArray<Place*>* places = new ZoneGrowableArray<Place*>(10);
 
   bool has_loads = false;
+  bool has_stores = false;
   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()) {
       Instruction* instr = instr_it.Current();
-
-      Place place(instr, &has_loads);
+      Place place(instr, &has_loads, &has_stores);
       if (place.kind() == Place::kNone) {
         continue;
       }
 
       Place* result = map->Lookup(&place);
       if (result == NULL) {
         place.set_id(places->length());
         result = Place::Wrap(place);
         map->Insert(result);
         places->Add(result);
 
         if (FLAG_trace_optimization) {
           OS::Print("numbering %s as %" Pd "\n",
                     result->ToCString(),
                     result->id());
         }
       }
 
       instr->set_place_id(result->id());
     }
   }
 
-  if (!has_loads) {
+  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.
   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);
@@ skipping 35 matching lines @@
     }
   }
 
   static bool OptimizeGraph(FlowGraph* graph) {
     ASSERT(FLAG_load_cse);
     if (FLAG_trace_load_optimization) {
       FlowGraphPrinter::PrintGraph("Before LoadOptimizer", graph);
     }
 
     DirectChainedHashMap<PointerKeyValueTrait<Place> > map;
-    AliasedSet* aliased_set = NumberPlaces(graph, &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);
       return load_optimizer.Optimize();
     }
@@ skipping 57 matching lines @@
 
           // Only forward stores to normal arrays, float64, and simd 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) ||
               (array_store->class_id() == kTypedDataFloat32ArrayCid) ||
               (array_store->class_id() == kTypedDataFloat32x4ArrayCid)) {
-            bool is_load = false;
-            Place store_place(instr, &is_load);
-            ASSERT(!is_load);
+            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);
             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);
             }
           }
 
@@ skipping 679 matching lines @@
   GrowableArray<PhiInstr*> worklist_;
   BitVector* in_worklist_;
 
   // True if any load was eliminated.
   bool forwarded_;
 
   DISALLOW_COPY_AND_ASSIGN(LoadOptimizer);
 };
 
 
+class StoreOptimizer : public LivenessAnalysis {
+ public:
+  StoreOptimizer(FlowGraph* graph,
+                 AliasedSet* aliased_set,
+                 DirectChainedHashMap<PointerKeyValueTrait<Place> >* map)
+      : LivenessAnalysis(aliased_set->max_place_id(), graph->postorder()),
+        graph_(graph),
+        map_(map),
+        aliased_set_(aliased_set),
+        exposed_stores_(graph_->postorder().length()) {
+    const intptr_t num_blocks = graph_->postorder().length();
+    for (intptr_t i = 0; i < num_blocks; i++) {
+      exposed_stores_.Add(NULL);
+    }
+  }
+
+  static void OptimizeGraph(FlowGraph* graph) {
+    ASSERT(FLAG_load_cse);
+    if (FLAG_trace_load_optimization) {
+      FlowGraphPrinter::PrintGraph("Before StoreOptimizer", graph);
+    }
+
+    DirectChainedHashMap<PointerKeyValueTrait<Place> > map;
+    AliasedSet* aliased_set = NumberPlaces(graph, &map, kOptimizeStores);
+    if ((aliased_set != NULL) && !aliased_set->IsEmpty()) {
+      StoreOptimizer store_optimizer(graph, aliased_set, &map);
+      store_optimizer.Optimize();
+    }
+  }
+
+ private:
+  void Optimize() {
+    Analyze();
+    if (FLAG_trace_load_optimization) {
+      Dump();
+    }
+    EliminateDeadStores();
+    if (FLAG_trace_load_optimization) {
+      FlowGraphPrinter::PrintGraph("After StoreOptimizer", graph_);
+    }
+  }
+
+  bool CanEliminateStore(Instruction* instr) {
+    switch (instr->tag()) {
+      case Instruction::kStoreInstanceField:
+        if (instr->AsStoreInstanceField()->is_initialization()) {
+          // Can't eliminate stores that initialized unboxed fields.
+          return false;
+        }
+      case Instruction::kStoreContext:
+      case Instruction::kStoreIndexed:
+      case Instruction::kStoreStaticField:
+        return true;
+      default:
+        UNREACHABLE();
+        return false;
+    }
+  }
+
+  virtual void ComputeInitialSets() {
+    BitVector* all_places = new BitVector(aliased_set_->max_place_id());
+    all_places->SetAll();
+    for (BlockIterator block_it = graph_->postorder_iterator();
+         !block_it.Done();
+         block_it.Advance()) {
+      BlockEntryInstr* block = block_it.Current();
+      const intptr_t postorder_number = block->postorder_number();
+
+      BitVector* kill = kill_[postorder_number];
+      BitVector* live_in = live_in_[postorder_number];
+      BitVector* live_out = live_out_[postorder_number];
+
+      ZoneGrowableArray<Instruction*>* exposed_stores = NULL;
+
+      // Iterate backwards starting at the last instruction.
+      for (BackwardInstructionIterator instr_it(block);
+           !instr_it.Done();
+           instr_it.Advance()) {
+        Instruction* instr = instr_it.Current();
+
+        bool is_load = false;
+        bool is_store = false;
+        Place place(instr, &is_load, &is_store);
+        if (place.IsFinalField()) {
+          // Loads/stores of final fields do not participate.
+          continue;
+        }
+
+        // Handle stores.
+        if (is_store) {
+          if (kill->Contains(instr->place_id())) {
+            if (!live_in->Contains(instr->place_id()) &&
+                CanEliminateStore(instr)) {
+              if (FLAG_trace_optimization) {
+                OS::Print(
+                    "Removing dead store to place %" Pd " in block B%" Pd "\n",
+                    instr->place_id(), block->block_id());
+              }
+              instr_it.RemoveCurrentFromGraph();
+            }
+          } else if (!live_in->Contains(instr->place_id())) {
+            // Mark this store as down-ward exposed: They are the only
+            // candidates for the global store elimination.
+            if (exposed_stores == NULL) {
+              const intptr_t kMaxExposedStoresInitialSize = 5;
+              exposed_stores = new ZoneGrowableArray<Instruction*>(
+                  Utils::Minimum(kMaxExposedStoresInitialSize,
+                                 aliased_set_->max_place_id()));
+            }
+            exposed_stores->Add(instr);
+          }
+          // Interfering stores kill only loads from the same place.
+          kill->Add(instr->place_id());
+          live_in->Remove(instr->place_id());
+          continue;
+        }
+
+        // Handle side effects, deoptimization and function return.
+        if (!instr->Effects().IsNone() ||
+            instr->CanDeoptimize() ||
+            instr->IsThrow() ||
+            instr->IsReThrow() ||
+            instr->IsReturn()) {
+          // Instructions that return from the function, instructions with side
+          // effects and instructions that can deoptimize are considered as
+          // loads from all places.
+          live_in->CopyFrom(all_places);
+          if (instr->IsThrow() || instr->IsReThrow() || instr->IsReturn()) {
+            // Initialize live-out for exit blocks since it won't be computed
+            // otherwise during the fixed point iteration.
+            live_out->CopyFrom(all_places);
+          }
+          continue;
+        }
+
+        // Handle loads.
+        Definition* defn = instr->AsDefinition();
+        if ((defn != NULL) && IsLoadEliminationCandidate(defn)) {
+          const Alias alias = aliased_set_->ComputeAlias(&place);
+          live_in->AddAll(aliased_set_->Get(alias));
+          continue;
+        }
+      }
+      exposed_stores_[postorder_number] = exposed_stores;
+    }
+    if (FLAG_trace_load_optimization) {
+      Dump();
+      OS::Print("---\n");
+    }
+  }
+
+  void EliminateDeadStores() {
+    // Iteration order does not matter here.
+    for (BlockIterator block_it = graph_->postorder_iterator();
+         !block_it.Done();
+         block_it.Advance()) {
+      BlockEntryInstr* block = block_it.Current();
+      const intptr_t postorder_number = block->postorder_number();
+
+      BitVector* live_out = live_out_[postorder_number];
+
+      ZoneGrowableArray<Instruction*>* exposed_stores =
+        exposed_stores_[postorder_number];
+      if (exposed_stores == NULL) continue;  // No exposed stores.
+
+      // Iterate over candidate stores.
+      for (intptr_t i = 0; i < exposed_stores->length(); ++i) {
+        Instruction* instr = (*exposed_stores)[i];
+        bool is_load = false;
+        bool is_store = false;
+        Place place(instr, &is_load, &is_store);
+        ASSERT(!is_load && is_store);
+        if (place.IsFinalField()) {
+          // Final field do not participate in dead store elimination.
+          continue;
+        }
+        // Eliminate a downward exposed store if the corresponding place is not
+        // in live-out.
+        if (!live_out->Contains(instr->place_id()) &&
+            CanEliminateStore(instr)) {
+          if (FLAG_trace_optimization) {
+            OS::Print("Removing dead store to place %"Pd" in block B%"Pd"\n",
+                      instr->place_id(), block->block_id());
+          }
+          instr->RemoveFromGraph(/* ignored */ false);
+        }
+      }
+    }
+  }
+
+  FlowGraph* graph_;
+  DirectChainedHashMap<PointerKeyValueTrait<Place> >* map_;
+
+  // Mapping between field offsets in words and expression ids of loads from
+  // that offset.
+  AliasedSet* aliased_set_;
+
+  // Per block list of downward exposed stores.
+  GrowableArray<ZoneGrowableArray<Instruction*>*> exposed_stores_;
+
+  DISALLOW_COPY_AND_ASSIGN(StoreOptimizer);
+};
+
+
+void DeadStoreElimination::Optimize(FlowGraph* graph) {
+  if (FLAG_dead_store_elimination) {
+    StoreOptimizer::OptimizeGraph(graph);
+  }
+}
+
+
 class CSEInstructionMap : public ValueObject {
  public:
   // Right now CSE and LICM track a single effect: possible externalization of
   // strings.
   // Other effects like modifications of fields are tracked in a separate load
   // forwarding pass via Alias structure.
   COMPILE_ASSERT(EffectSet::kLastEffect == 1, single_effect_is_tracked);
 
   CSEInstructionMap() : independent_(), dependent_() { }
   explicit CSEInstructionMap(const CSEInstructionMap& other)
@@ skipping 2237 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