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

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 3146 matching lines @@
   for (intptr_t j = 0; j < header->PredecessorCount(); ++j) {
     BlockEntryInstr* candidate = header->PredecessorAt(j);
     if (header->dominator() == candidate) {
       return candidate;
     }
   }
   return NULL;
 }
 
 
 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());
 }
 
 
 void LICM::Hoist(ForwardInstructionIterator* it,
                  BlockEntryInstr* pre_header,
                  Instruction* current) {
   // TODO(fschneider): Avoid repeated deoptimization when
   // speculatively hoisting checks.
   if (FLAG_trace_optimization) {
     OS::Print("Hoisting instruction %s:%"Pd" from B%"Pd" to B%"Pd"\n",
@@ skipping 99 matching lines @@
                 &it, header, pre_header, current->AsCheckSmi());
           }
         }
       }
     }
   }
 }
 
 
 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();
 }
 
 
 // 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 52 matching lines @@
     kCurrentContextAlias = -1,
     kIndexesAlias = 0,
     kFirstFieldAlias = kIndexesAlias + 1,
     kAliasBase = kCurrentContextAlias
   };
 
   const intptr_t alias_;
 };
 
 
-// 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()) {
       // We are assuming that LoadField is never used to load the first word.
       return Alias::Indexes();
     }
 
     LoadFieldInstr* load_field = defn->AsLoadField();
     if (load_field != NULL) {
       if (load_field->field() != NULL) {
@@ skipping 50 matching lines @@
   bool Contains(const Alias alias) {
     const intptr_t idx = alias.ToIndex();
     return (idx < sets_.length()) && (sets_[idx] != NULL);
   }
 
   BitVector* Get(const Alias alias) {
     ASSERT(Contains(alias));
     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) {
       sets_.Add(NULL);
     }
 
     if (sets_[idx] == NULL) {
       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; }
 
+  BitVector* aliased_by_effects() const { return aliased_by_effects_; }
+
  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_;
-
   // 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) {
     intptr_t id = field_ids_.Lookup(FieldIdPair::Key(instance_id, &field));
     if (id == 0) {
       id = ++max_field_id_;
       field_ids_.Insert(FieldIdPair(FieldIdPair::Key(instance_id, &field), id));
     }
     return id;
   }
@@ skipping 43 matching lines @@
            use = use->next_use()) {
         Instruction* instr = use->instruction();
         if (instr->IsPushArgument() ||
             (instr->IsStoreVMField() && (use->use_index() != 0)) ||
             (instr->IsStoreInstanceField() && (use->use_index() != 0)) ||
             (instr->IsStoreStaticField()) ||
             (instr->IsPhi())) {
           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 {
       Key(intptr_t instance_id, const Field* field)
           : instance_id_(instance_id), field_(field) { }
 
       intptr_t instance_id_;
       const Field* field_;
     };
 
@@ skipping 17 matching lines @@
     static inline bool IsKeyEqual(Pair kv, Key key) {
       return (KeyOf(kv).field_->raw() == key.field_->raw()) &&
           (KeyOf(kv).instance_id_ == key.instance_id_);
     }
 
    private:
     Key key_;
     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.
+  intptr_t max_field_id_;
   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) {
@@ skipping 146 matching lines @@
       } else {
         defn->set_expr_id(result->expr_id());
       }
     }
   }
 
   // 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];
-    aliased_set->Add(aliased_set->ComputeAliasForLoad(defn), defn->expr_id());
+    aliased_set->AddRepresentative(defn);
   }
   return aliased_set;
 }
 
 
 class LoadOptimizer : public ValueObject {
  public:
   LoadOptimizer(FlowGraph* graph,
                 AliasedSet* aliased_set,
                 DirectChainedHashMap<LoadKeyValueTrait>* map)
@@ skipping 15 matching lines @@
       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);
     }
   }
 
+  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();
     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()) {
@@ skipping 37 matching lines @@
                 if (out_values == NULL) out_values = CreateBlockOutValues();
                 (*out_values)[load->expr_id()] = GetStoredValue(instr);
               }
             }
           }
           ASSERT(!instr->IsDefinition() ||
                  !IsLoadEliminationCandidate(instr->AsDefinition()));
           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;
+        }
+
         const intptr_t expr_id = defn->expr_id();
         if (gen->Contains(expr_id)) {
           // This is a locally redundant load.
           ASSERT((out_values != NULL) && ((*out_values)[expr_id] != NULL));
 
           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(),
@@ skipping 380 matching lines @@
   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;
-    }
+    changed = LoadOptimizer::OptimizeGraph(graph) || changed;
   }
 
   CSEInstructionMap map;
   changed = OptimizeRecursive(graph, graph->graph_entry(), &map) || changed;
 
   return changed;
 }
 
 
 bool DominatorBasedCSE::OptimizeRecursive(
@@ skipping 759 matching lines @@
   SetValue(instr, instr->value());
 }
 
 
 void ConstantPropagator::VisitConstraint(ConstraintInstr* instr) {
   // Should not be used outside of range analysis.
   UNREACHABLE();
 }
 
 
+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();
   const Object& right = instr->right()->definition()->constant_value();
   if (IsNonConstant(left) || IsNonConstant(right)) {
     SetValue(instr, non_constant_);
   } else if (IsConstant(left) && IsConstant(right)) {
     // TODO(kmillikin): Handle binary operation.
     SetValue(instr, non_constant_);
   }
@@ skipping 725 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);
   }
 }
 
 
+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