Implement a variation of scalar replacement for non-escaping allocations.

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
diff --git a/runtime/vm/flow_graph_optimizer.cc b/runtime/vm/flow_graph_optimizer.cc
index 67d2d3c2bde9eda8b0697203f2fa403ad6b787c6..d049b8db6867a41aa5167c4fb9b2c85767bcc930 100644
--- a/runtime/vm/flow_graph_optimizer.cc
+++ b/runtime/vm/flow_graph_optimizer.cc
@@ -3165,6 +3165,7 @@ static BlockEntryInstr* FindPreHeader(BlockEntryInstr* header) {
 
 
 LICM::LICM(FlowGraph* flow_graph) : flow_graph_(flow_graph) {

[srdjan, 2013/05/07 23:11:45]

, materializations_()

[Vyacheslav Egorov (Google), 2013/05/07 23:28:21]

Added this to DeoptInfoBuilder, LICM does not have such field.

+  ASSERT(flow_graph->is_licm_allowed());
 }
 
 
@@ -3284,10 +3285,7 @@ void LICM::Optimize() {
 
 
 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->Dependencies().IsNone())
+  return def->IsLoadField()
       || def->IsLoadIndexed()
       || def->IsLoadStaticField()
       || def->IsCurrentContext();
@@ -3360,14 +3358,19 @@ class Alias : public ValueObject {
 };
 
 
-// Set mapping alias to a list of loads sharing this alias.
+// Set mapping alias to a list of loads sharing this alias. Additionally
+// carries a set of loads that can be aliased by side-effects, essentially
+// those that are affected by calls.
 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) { }
+        // BitVector constructor throws if requested length is 0.
+        aliased_by_effects_(max_expr_id > 0 ? new BitVector(max_expr_id)
+                                            : NULL),
+        max_field_id_(0),
+        field_ids_() { }
 
   Alias ComputeAliasForLoad(Definition* defn) {
     if (defn->IsLoadIndexed()) {
@@ -3438,7 +3441,14 @@ class AliasedSet : public ZoneAllocated {
     return sets_[alias.ToIndex()];
   }
 
-  void Add(const Alias alias, intptr_t ssa_index) {
+  void AddRepresentative(Definition* defn) {
+    AddIdForAlias(ComputeAliasForLoad(defn), defn->expr_id());
+    if (!IsIndependentFromEffects(defn)) {
+      aliased_by_effects_->Add(defn->expr_id());
+    }
+  }
+
+  void AddIdForAlias(const Alias alias, intptr_t expr_id) {
     const intptr_t idx = alias.ToIndex();
 
     while (sets_.length() <= idx) {
@@ -3449,19 +3459,15 @@ class AliasedSet : public ZoneAllocated {
       sets_[idx] = new BitVector(max_expr_id_);
     }
 
-    sets_[idx]->Add(ssa_index);
+    sets_[idx]->Add(expr_id);
   }
 
   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_;
-
-  // Maps alias index to a set of ssa indexes corresponding to loads with the
-  // given alias.
-  GrowableArray<BitVector*> sets_;
+  BitVector* aliased_by_effects() const { return aliased_by_effects_; }
 
+ private:
   // Get id assigned to the given field. Assign a new id if the field is seen
   // for the first time.
   intptr_t GetFieldId(intptr_t instance_id, const Field& field) {
@@ -3525,15 +3531,51 @@ class AliasedSet : public ZoneAllocated {
           escapes = true;
           break;
         }
-
-        alloc->set_identity(escapes ? AllocateObjectInstr::kAliased
-                                    : AllocateObjectInstr::kNotAliased);
       }
+
+      alloc->set_identity(escapes ? AllocateObjectInstr::kAliased
+                                  : AllocateObjectInstr::kNotAliased);
     }
 
     return alloc->identity() != AllocateObjectInstr::kNotAliased;
   }
 
+  // Returns true if the given load is unaffected by external side-effects.
+  // This essentially means that no stores to the same location can
+  // occur in other functions.
+  bool IsIndependentFromEffects(Definition* defn) {
+    LoadFieldInstr* load_field = defn->AsLoadField();
+    if (load_field != NULL) {
+      // Note that we can't use LoadField's is_immutable attribute here because
+      // some VM-fields (those that have no corresponding Field object and
+      // accessed through offset alone) can share offset but have different
+      // immutability properties.
+      // One example is length property of growable and fixed size list. If
+      // loads of these two properties occur in the same function for the same
+      // receiver then they will recieve the same expression number. However

[srdjan, 2013/05/07 23:11:45]

s/recieve/receive/

[Vyacheslav Egorov (Google), 2013/05/07 23:28:21]

Done.

+      // immutability of the length of fixed size list does not mean that
+      // growable list also has immutable property. Thus we will make a
+      // conservative assumption for the VM-properties.
+      // TODO(vegorov): disambiguate immutable and non-immutable VM-fields with
+      // the same offset e.g. through recognized kind.
+      if ((load_field->field() != NULL) &&
+          (load_field->field()->is_final())) {
+        return true;
+      }
+
+      AllocateObjectInstr* alloc =
+          load_field->instance()->definition()->AsAllocateObject();
+      return (alloc != NULL) && !CanBeAliased(alloc);
+    }
+
+    LoadStaticFieldInstr* load_static_field = defn->AsLoadStaticField();
+    if (load_static_field != NULL) {
+      return load_static_field->field().is_final();
+    }
+
+    return false;
+  }
+
   class FieldIdPair {
    public:
     struct Key {
@@ -3571,9 +3613,17 @@ class AliasedSet : public ZoneAllocated {
     Value value_;
   };
 
+  const intptr_t max_expr_id_;
+
+  // 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.
-  DirectChainedHashMap<FieldIdPair> field_ids_;
   intptr_t max_field_id_;
+  DirectChainedHashMap<FieldIdPair> field_ids_;
 };
 
 
@@ -3740,7 +3790,7 @@ static AliasedSet* NumberLoadExpressions(
   AliasedSet* aliased_set = new AliasedSet(expr_id);
   for (intptr_t i = 0; i < loads.length(); i++) {
     Definition* defn = loads[i];
-    aliased_set->Add(aliased_set->ComputeAliasForLoad(defn), defn->expr_id());
+    aliased_set->AddRepresentative(defn);
   }
   return aliased_set;
 }
@@ -3776,6 +3826,25 @@ class LoadOptimizer : public ValueObject {
     }
   }
 
+  static bool OptimizeGraph(FlowGraph* graph) {
+    ASSERT(FLAG_load_cse);
+
+    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);
+      return load_optimizer.Optimize();
+    }
+    return false;
+  }
+
+ private:
   bool Optimize() {
     ComputeInitialSets();
     ComputeOutValues();
@@ -3784,7 +3853,6 @@ class LoadOptimizer : public ValueObject {
     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
@@ -3842,18 +3910,59 @@ class LoadOptimizer : public ValueObject {
           continue;
         }
 
-        // Other instructions with side effects kill all loads.
+        // If instruction has effects then kill all loads affected.
         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
+          kill->AddAll(aliased_set_->aliased_by_effects());
+          // There is no need to clear out_values when removing values from GEN
+          // set because only those values that are in the GEN set
           // will ever be used.
-          gen->Clear();
+          gen->RemoveAll(aliased_set_->aliased_by_effects());
           continue;
         }
 
         Definition* defn = instr->AsDefinition();
-        if ((defn == NULL) || !IsLoadEliminationCandidate(defn)) {
+        if (defn == NULL) {
+          continue;
+        }
+
+        // For object allocation forward initial values of the fields to
+        // subsequent loads.
+        // For simplicity we ignore escaping objects and objects that have
+        // type arguments.
+        // The reason to ignore escaping objects is that final fields are
+        // initialized in constructor that potentially can be not inlined into
+        // the function that we are currently optimizing. However at the same
+        // time we assume that values of the final fields can be forwarded
+        // across side-effects. If we add 'null' as the know values for these

[srdjan, 2013/05/07 23:11:45]

s/know/known/

[Vyacheslav Egorov (Google), 2013/05/07 23:28:21]

Done.

+        // fields here we will incorrectly propagate this null across
+        // constructor invocation.
+        // TODO(vegorov): record null-values at least for not final fields of
+        // escaping object.
+        // TODO(vegorov): enable forwarding of type arguments.
+        AllocateObjectInstr* alloc = instr->AsAllocateObject();
+        if ((alloc != NULL) &&
+            (alloc->identity() == AllocateObjectInstr::kNotAliased) &&
+            (alloc->ArgumentCount() == 0)) {
+          for (Value* use = alloc->input_use_list();
+               use != NULL;
+               use = use->next_use()) {
+            // Look for all immediate loads from this object.
+            if (use->use_index() != 0) {
+              continue;
+            }
+
+            LoadFieldInstr* load = use->instruction()->AsLoadField();
+            if (load != NULL) {
+              // Found a load. Initialize current value of the field to null.
+              gen->Add(load->expr_id());
+              if (out_values == NULL) out_values = CreateBlockOutValues();
+              (*out_values)[load->expr_id()] = graph_->constant_null();
+            }
+          }
+          continue;
+        }
+
+        if (!IsLoadEliminationCandidate(defn)) {
           continue;
         }
 
@@ -4257,19 +4366,7 @@ class CSEInstructionMap : public ValueObject {
 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;
-    }
+    changed = LoadOptimizer::OptimizeGraph(graph) || changed;
   }
 
   CSEInstructionMap map;
@@ -5049,6 +5146,12 @@ void ConstantPropagator::VisitConstraint(ConstraintInstr* instr) {
 }
 
 
+void ConstantPropagator::VisitMaterializeObject(MaterializeObjectInstr* instr) {
+  // Should not be used outside of allocation elimination pass.
+  UNREACHABLE();
+}
+
+
 void ConstantPropagator::VisitBinaryDoubleOp(
     BinaryDoubleOpInstr* instr) {
   const Object& left = instr->left()->definition()->constant_value();
@@ -5794,4 +5897,240 @@ void IfConverter::Simplify(FlowGraph* flow_graph) {
 }
 
 
+void FlowGraphOptimizer::EliminateEnvironments() {
+  // After this pass we can no longer perform LICM and hoist instructions
+  // that can deoptimize.
+
+  flow_graph_->disallow_licm();
+  for (intptr_t i = 0; i < block_order_.length(); ++i) {
+    BlockEntryInstr* block = block_order_[i];
+    block->RemoveEnvironment();
+    for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+      Instruction* current = it.Current();
+      if (!current->CanDeoptimize()) current->RemoveEnvironment();
+    }
+  }
+}
+
+
+// Right now we are attempting to sink allocation only into
+// deoptimization exit. So candidate should only be used in StoreInstanceField
+// instructions that write into fields of the allocated object.
+// We do not support materialization of the object that has type arguments.
+static bool IsAllocationSinkingCandidate(AllocateObjectInstr* alloc) {
+  // TODO(vegorov): support AllocateObject with type arguments.
+  if (alloc->ArgumentCount() > 0) {
+    return false;
+  }
+
+  for (Value* use = alloc->input_use_list();
+       use != NULL;
+       use = use->next_use()) {
+    if (!(use->instruction()->IsStoreInstanceField() &&
+          use->use_index() == 0)) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
+
+// Remove the given allocation from the graph. It is not observable.
+// If deoptimization occurs the object will be materialized.
+static void EliminateAllocation(AllocateObjectInstr* alloc) {
+  ASSERT(IsAllocationSinkingCandidate(alloc));
+
+  if (FLAG_trace_optimization) {
+    OS::Print("removing allocation from the graph: v%"Pd"\n",
+              alloc->ssa_temp_index());
+  }
+
+  // As an allocation sinking candidate it is only used in stores to its own
+  // fields. Remove these stores.
+  for (Value* use = alloc->input_use_list();
+       use != NULL;
+       use = alloc->input_use_list()) {
+    use->instruction()->RemoveFromGraph();
+  }
+
+  // There should be no environment uses. The pass replaced them with
+  // MaterializeObject instructions.
+  ASSERT(alloc->env_use_list() == NULL);
+  ASSERT(alloc->input_use_list() == NULL);
+  alloc->RemoveFromGraph();
+}
+
+
+void AllocationSinking::Optimize() {
+  GrowableArray<AllocateObjectInstr*> candidates(5);
+
+  // Collect sinking candidates.
+  const GrowableArray<BlockEntryInstr*>& postorder = flow_graph_->postorder();
+  for (BlockIterator block_it(postorder);
+       !block_it.Done();
+       block_it.Advance()) {
+    BlockEntryInstr* block = block_it.Current();
+    for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+      AllocateObjectInstr* alloc = it.Current()->AsAllocateObject();
+      if ((alloc != NULL) && IsAllocationSinkingCandidate(alloc)) {
+        if (FLAG_trace_optimization) {
+          OS::Print("discovered allocation sinking candidate: v%"Pd"\n",
+                    alloc->ssa_temp_index());
+        }
+        candidates.Add(alloc);
+      }
+    }
+  }
+
+  // Insert MaterializeObject instructions that will describe the state of the
+  // object at all deoptimization points. Each inserted materialization looks
+  // like this (where v_0 is allocation that we are going to eliminate):
+  //   v_1     <- LoadField(v_0, field_1)
+  //           ...
+  //   v_N     <- LoadField(v_0, field_N)
+  //   v_{N+1} <- MaterializeObject(field_1 = v_1, ..., field_N = v_{N})
+  for (intptr_t i = 0; i < candidates.length(); i++) {
+    InsertMaterializations(candidates[i]);
+  }
+
+  // Run load forwarding to eliminate LoadField instructions inserted above.
+  // All loads will be successfully eliminated because:
+  //   a) they use fields (not offsets) and thus provide precise aliasing
+  //      information
+  //   b) candidate does not escape and thus its fields is not affected by
+  //      external effects from calls.
+  LoadOptimizer::OptimizeGraph(flow_graph_);
+
+  // At this point we have computed the state of object at each deoptimization
+  // point and we can eliminate it. Loads inserted above were forwarded so there
+  // are no uses of the allocation just as in the begging of the pass.
+  for (intptr_t i = 0; i < candidates.length(); i++) {
+    EliminateAllocation(candidates[i]);
+  }
+
+  // Process materializations and unbox their arguments: materializations
+  // are part of the environment and can materialize boxes for double/mint/simd
+  // values when needed.
+  // TODO(vegorov): handle all box types here.
+  for (intptr_t i = 0; i < materializations_.length(); i++) {
+    MaterializeObjectInstr* mat = materializations_[i];
+    for (intptr_t j = 0; j < mat->InputCount(); j++) {
+      Definition* defn = mat->InputAt(j)->definition();
+      if (defn->IsBoxDouble()) {
+        mat->InputAt(j)->BindTo(defn->InputAt(0)->definition());
+      }
+    }
+  }
+}
+
+
+// Remove materializations from the graph. Register allocator will treat them
+// as part of the environment not as a real instruction.
+void AllocationSinking::DetachMaterializations() {
+  for (intptr_t i = 0; i < materializations_.length(); i++) {
+    ASSERT(materializations_[i]->input_use_list() == NULL);
+    materializations_[i]->previous()->LinkTo(materializations_[i]->next());
+  }
+}
+
+
+// Add the given field to the list of fields if it is not yet present there.
+static void AddField(ZoneGrowableArray<const Field*>* fields,
+                     const Field& field) {
+  for (intptr_t i = 0; i < fields->length(); i++) {
+    if ((*fields)[i]->raw() == field.raw()) {
+      return;
+    }
+  }
+  fields->Add(&field);
+}
+
+
+// Add given instruction to the list of the instructions if it is not yet
+// present there.
+static void AddInstruction(GrowableArray<Instruction*>* exits,
+                           Instruction* exit) {
+  for (intptr_t i = 0; i < exits->length(); i++) {
+    if ((*exits)[i] == exit) {
+      return;
+    }
+  }

[srdjan, 2013/05/07 23:11:45]

Maybe we should add AddUnique to GrowableArray. I believe we are using it in
other places as well.

[Vyacheslav Egorov (Google), 2013/05/07 23:28:21]

Yes, we should. Unfortunately it would not help for AddField like things.

+  exits->Add(exit);
+}
+
+
+// Insert MaterializeObject instruction for the given allocation before
+// the given instruction that can deoptimize.
+void AllocationSinking::CreateMaterializationAt(
+    Instruction* exit,
+    AllocateObjectInstr* alloc,
+    const Class& cls,
+    const ZoneGrowableArray<const Field*>& fields) {
+  ZoneGrowableArray<Value*>* values =
+      new ZoneGrowableArray<Value*>(fields.length());
+
+  // Insert load instruction for every field.
+  for (intptr_t i = 0; i < fields.length(); i++) {
+    const Field* field = fields[i];
+    LoadFieldInstr* load = new LoadFieldInstr(new Value(alloc),
+                                              field->Offset(),
+                                              AbstractType::ZoneHandle());
+    load->set_field(field);
+    flow_graph_->InsertBefore(
+        exit, load, NULL, Definition::kValue);
+    values->Add(new Value(load));
+  }
+
+  MaterializeObjectInstr* mat = new MaterializeObjectInstr(cls, fields, values);
+  flow_graph_->InsertBefore(exit, mat, NULL, Definition::kValue);
+
+  // Replace all mentions of this allocation with a newly inserted
+  // MaterializeObject instruction.
+  // We must preserve the identity: all mentions are replaced by the same
+  // materialization.
+  for (Environment::DeepIterator env_it(exit->env());
+       !env_it.Done();
+       env_it.Advance()) {
+    Value* use = env_it.CurrentValue();
+    if (use->definition() == alloc) {
+      use->RemoveFromUseList();
+      use->set_definition(mat);
+      mat->AddEnvUse(use);
+    }
+  }
+
+  // Record inserted materialization.
+  materializations_.Add(mat);
+}
+
+
+void AllocationSinking::InsertMaterializations(AllocateObjectInstr* alloc) {
+  // Collect all fields that are written for this instance.
+  ZoneGrowableArray<const Field*>* fields =
+      new ZoneGrowableArray<const Field*>(5);
+
+  for (Value* use = alloc->input_use_list();
+       use != NULL;
+       use = use->next_use()) {
+    ASSERT(use->instruction()->IsStoreInstanceField());
+    AddField(fields, use->instruction()->AsStoreInstanceField()->field());
+  }
+
+  // Collect all instructions that mention this object in the environment.
+  GrowableArray<Instruction*> exits(10);
+  for (Value* use = alloc->env_use_list();
+       use != NULL;
+       use = use->next_use()) {
+    AddInstruction(&exits, use->instruction());
+  }
+
+  // Insert materializations at environment uses.
+  const Class& cls = Class::Handle(alloc->constructor().Owner());
+  for (intptr_t i = 0; i < exits.length(); i++) {
+    CreateMaterializationAt(exits[i], alloc, cls, *fields);
+  }
+}
+
+
 }  // namespace dart