Track side-effect free paths in the graph to allow CSE and LICM for instructions that depend on som…

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 3057 matching lines @@
     if (pre_header == NULL) continue;
 
     for (BitVector::Iterator loop_it(header->loop_info());
          !loop_it.Done();
          loop_it.Advance()) {
       BlockEntryInstr* block = flow_graph()->preorder()[loop_it.Current()];
       for (ForwardInstructionIterator it(block);
            !it.Done();
            it.Advance()) {
         Instruction* current = it.Current();
-        if (!current->IsPushArgument() && !current->AffectedBySideEffect()) {
+        if (!current->IsPushArgument() &&
+            current->AllowsCSE() &&
+            flow_graph()->block_effects()->CanBeMovedTo(current, pre_header)) {
           bool inputs_loop_invariant = true;
           for (int i = 0; i < current->InputCount(); ++i) {
             Definition* input_def = current->InputAt(i)->definition();
             if (!input_def->GetBlock()->Dominates(pre_header)) {
               inputs_loop_invariant = false;
               break;
             }
           }
           if (inputs_loop_invariant &&
               !current->IsAssertAssignable() &&
@@ skipping 10 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())
+  return (def->IsLoadField() && !def->Dependencies().IsNone())
       || 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 {
@@ skipping 458 matching lines @@
                 (*out_values)[load->expr_id()] = GetStoredValue(instr);
               }
             }
           }
           ASSERT(!instr->IsDefinition() ||
                  !IsLoadEliminationCandidate(instr->AsDefinition()));
           continue;
         }
 
         // Other instructions with side effects kill all loads.
-        if (instr->HasSideEffect()) {
+        if (!instr->Effects().IsNone()) {
           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.
           gen->Clear();
           continue;
         }
 
         Definition* defn = instr->AsDefinition();
         if ((defn == NULL) || !IsLoadEliminationCandidate(defn)) {
@@ skipping 340 matching lines @@
   GrowableArray<PhiInstr*> worklist_;
   BitVector* in_worklist_;
 
   // True if any load was eliminated.
   bool forwarded_;
 
   DISALLOW_COPY_AND_ASSIGN(LoadOptimizer);
 };
 
 
+class CSEInstructionMap {

[srdjan, 2013/04/29 17:16:26]

: public ValueObject

[Vyacheslav Egorov (Google), 2013/04/30 14:01:33]

Done.

+ 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_() { }
+  CSEInstructionMap(const CSEInstructionMap& other)

[srdjan, 2013/04/29 17:16:26]

explicit

[Vyacheslav Egorov (Google), 2013/04/30 14:01:33]

Done.

+      : independent_(other.independent_), dependent_(other.dependent_) { }
+
+  void RemoveAffected(EffectSet effects) {
+    if (!effects.IsNone()) {
+      dependent_.Clear();
+    }
+  }
+
+  Instruction* Lookup(Instruction* other) const {
+    return GetMapFor(other)->Lookup(other);
+  }
+
+  void Insert(Instruction* instr) {
+    return GetMapFor(instr)->Insert(instr);
+  }
+
+ private:
+  typedef DirectChainedHashMap<PointerKeyValueTrait<Instruction> >  Map;
+
+  Map* GetMapFor(Instruction* instr) {
+    return instr->Dependencies().IsNone() ? &independent_ : &dependent_;
+  }
+
+  const Map* GetMapFor(Instruction* instr) const {
+    return instr->Dependencies().IsNone() ? &independent_ : &dependent_;
+  }
+
+  // All computations that are not affected by any side-effect.
+  // Majority of computations are not affected by anything and will be in
+  // this map.
+  Map independent_;
+
+  // All computations that are affected by side effect.
+  Map dependent_;
+};
+
+
 bool DominatorBasedCSE::Optimize(FlowGraph* graph) {
   bool changed = false;
   if (FLAG_load_cse) {
     GrowableArray<BitVector*> kill_by_offs(10);
     DirectChainedHashMap<LoadKeyValueTrait> map;
     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;
+  CSEInstructionMap map;
   changed = OptimizeRecursive(graph, graph->graph_entry(), &map) || changed;
 
   return changed;
 }
 
 
 bool DominatorBasedCSE::OptimizeRecursive(
     FlowGraph* graph,
     BlockEntryInstr* block,
-    DirectChainedHashMap<PointerKeyValueTrait<Instruction> >* map) {
+    CSEInstructionMap* map) {
   bool changed = false;
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     Instruction* current = it.Current();
-    if (current->AffectedBySideEffect()) continue;
-    Instruction* replacement = map->Lookup(current);
-    if (replacement == NULL) {
+    if (current->AllowsCSE()) {
+      Instruction* replacement = map->Lookup(current);
+      if ((replacement != NULL) &&
+          graph->block_effects()->IsAvailableAt(replacement, block)) {
+        // Replace current with lookup result.
+        ReplaceCurrentInstruction(&it, current, replacement, graph);
+        changed = true;
+        continue;
+      }
+
+      // For simplicity we assume that instruction either does not depend on
+      // anything or does not affect anything. If this is not the case then
+      // we should first remove affected instructions from the map and
+      // then add instruction to the map so that it does not kill itself.
+      ASSERT(current->Effects().IsNone() || current->Dependencies().IsNone());
       map->Insert(current);
-      continue;
     }
-    // Replace current with lookup result.
-    ReplaceCurrentInstruction(&it, current, replacement, graph);
-    changed = true;
+
+    map->RemoveAffected(current->Effects());
   }
 
   // Process children in the dominator tree recursively.
   intptr_t num_children = block->dominated_blocks().length();
   for (intptr_t i = 0; i < num_children; ++i) {
     BlockEntryInstr* child = block->dominated_blocks()[i];
     if (i  < num_children - 1) {
       // Copy map.
-      DirectChainedHashMap<PointerKeyValueTrait<Instruction> > child_map(*map);
+      CSEInstructionMap child_map(*map);
       changed = OptimizeRecursive(graph, child, &child_map) || changed;
     } else {
       // Reuse map for the last child.
       changed = OptimizeRecursive(graph, child, map) || changed;
     }
   }
   return changed;
 }
 
 
@@ skipping 1374 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