Allocation sinking for contexts.

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 5469 matching lines @@
     return (kind_ == other->kind_) &&
         (representation_ == other->representation_) &&
         (instance_ == other->instance_) &&
         SameField(other);
   }
 
   // Create a zone allocated copy of this place and assign given id to it.
   static Place* Wrap(Isolate* isolate, const Place& place, intptr_t id);
 
   static bool IsAllocation(Definition* defn) {
-    // TODO(vegorov): add CreateContext to this list.
     return (defn != NULL) &&
         (defn->IsAllocateObject() ||
          defn->IsCreateArray() ||
+         defn->IsAllocateUninitializedContext() ||
          (defn->IsStaticCall() &&
           defn->AsStaticCall()->IsRecognizedFactory()));
   }
 
  private:
   Place(Kind kind, Definition* instance, intptr_t selector)
       : kind_(kind),
         representation_(kNoRepresentation),
         instance_(instance),
         raw_selector_(selector),
@@ skipping 410 matching lines @@
       // the same offset e.g. through recognized kind.
       return true;
     }
 
     return ((place->kind() == Place::kField) ||
          (place->kind() == Place::kVMField)) &&
         !CanBeAliased(place->instance());
   }
 
   // Returns true if there are direct loads from the given place.
   bool HasLoadsFromPlace(Definition* defn, const Place* place) {

[Vyacheslav Egorov (Google), 2014/11/13 13:01:42]

It would be good if we could assert somehow that *top-level* invocation of
HasLoadsFromPlace(defn, place) is always happening for defn that *is*
allocation.

The same for AnyUseCreatesAlias and MarkStoredValuesEscaping.

[Florian Schneider, 2014/11/13 13:38:53]

Done.

     ASSERT((place->kind() == Place::kField) ||
            (place->kind() == Place::kVMField));
-    ASSERT(place->instance() == defn);
 
     for (Value* use = defn->input_use_list();
          use != NULL;
          use = use->next_use()) {
+      Instruction* instr = use->instruction();
+      if ((instr->IsRedefinition() ||
+           instr->IsAssertAssignable()) &&
+          HasLoadsFromPlace(instr->AsDefinition(), place)) {
+        return true;
+      }
       bool is_load = false, is_store;
-      Place load_place(use->instruction(), &is_load, &is_store);
+      Place load_place(instr, &is_load, &is_store);
 
       if (is_load && load_place.Equals(place)) {
         return true;
       }
     }
 
     return false;
   }
 
   // Check if any use of the definition can create an alias.
   // Can add more objects into aliasing_worklist_.
   bool AnyUseCreatesAlias(Definition* defn) {
     for (Value* use = defn->input_use_list();
          use != NULL;
          use = use->next_use()) {
       Instruction* instr = use->instruction();
       if (instr->IsPushArgument() ||
           (instr->IsStoreIndexed()
            && (use->use_index() == StoreIndexedInstr::kValuePos)) ||
           instr->IsStoreStaticField() ||
-          instr->IsPhi() ||
-          instr->IsAssertAssignable() ||
-          instr->IsRedefinition()) {
+          instr->IsPhi()) {
+        return true;
+      } else if ((instr->IsAssertAssignable() || instr->IsRedefinition()) &&
+                 AnyUseCreatesAlias(instr->AsDefinition())) {
         return true;
       } else if ((instr->IsStoreInstanceField()
            && (use->use_index() != StoreInstanceFieldInstr::kInstancePos))) {
         ASSERT(use->use_index() == StoreInstanceFieldInstr::kValuePos);
         // If we store this value into an object that is not aliased itself
         // and we never load again then the store does not create an alias.
         StoreInstanceFieldInstr* store = instr->AsStoreInstanceField();
-        Definition* instance = store->instance()->definition();
-        if (instance->IsAllocateObject() && !instance->Identity().IsAliased()) {
+        Definition* instance =
+            store->instance()->definition()->OriginalDefinition();
+        if (Place::IsAllocation(instance) &&
+            !instance->Identity().IsAliased()) {
           bool is_load, is_store;
           Place store_place(instr, &is_load, &is_store);
 
           if (!HasLoadsFromPlace(instance, &store_place)) {
             // No loads found that match this store. If it is yet unknown if
             // the object is not aliased then optimistically assume this but
             // add it to the worklist to check its uses transitively.
             if (instance->Identity().IsUnknown()) {
               instance->SetIdentity(AliasIdentity::NotAliased());
               aliasing_worklist_.Add(instance);
             }
             continue;
           }
         }
-
         return true;
       }
     }
     return false;
   }
 
   // Mark any value stored into the given object as potentially aliased.
   void MarkStoredValuesEscaping(Definition* defn) {
-    if (!defn->IsAllocateObject()) {
-      return;
-    }
-
     // Find all stores into this object.
     for (Value* use = defn->input_use_list();
          use != NULL;
          use = use->next_use()) {
+      if (use->instruction()->IsRedefinition() ||
+          use->instruction()->IsAssertAssignable()) {
+        MarkStoredValuesEscaping(use->instruction()->AsDefinition());
+        continue;
+      }
       if ((use->use_index() == StoreInstanceFieldInstr::kInstancePos) &&
           use->instruction()->IsStoreInstanceField()) {
         StoreInstanceFieldInstr* store =
             use->instruction()->AsStoreInstanceField();
-        Definition* value = store->value()->definition();
+        Definition* value = store->value()->definition()->OriginalDefinition();
         if (value->Identity().IsNotAliased()) {
           value->SetIdentity(AliasIdentity::Aliased());
           identity_rollback_.Add(value);
 
           // Add to worklist to propagate the mark transitively.
           aliasing_worklist_.Add(value);
         }
       }
     }
   }
@@ skipping 3423 matching lines @@
   }
 
   return false;
 }
 
 
 // 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,
+static bool IsAllocationSinkingCandidate(Definition* alloc,
                                          SafeUseCheck check_type) {
   for (Value* use = alloc->input_use_list();
        use != NULL;
        use = use->next_use()) {
     if (!IsSafeUse(use, check_type)) {
       if (FLAG_trace_optimization) {
         OS::Print("use of %s at %s is unsafe for allocation sinking\n",
                   alloc->ToCString(),
                   use->instruction()->ToCString());
       }
@@ skipping 12 matching lines @@
   if (store != NULL) {
     return store->instance()->definition();
   }
 
   return NULL;
 }
 
 
 // Remove the given allocation from the graph. It is not observable.
 // If deoptimization occurs the object will be materialized.
-void AllocationSinking::EliminateAllocation(AllocateObjectInstr* alloc) {
+void AllocationSinking::EliminateAllocation(Definition* alloc) {
   ASSERT(IsAllocationSinkingCandidate(alloc, kStrictCheck));
 
   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();
@@ skipping 25 matching lines @@
 // Find allocation instructions that can be potentially eliminated and
 // rematerialized at deoptimization exits if needed. See IsSafeUse
 // for the description of algorithm used below.
 void AllocationSinking::CollectCandidates() {
   // Optimistically collect all potential candidates.
   for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator();
        !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, kOptimisticCheck)) {
-        alloc->SetIdentity(AliasIdentity::AllocationSinkingCandidate());
-        candidates_.Add(alloc);
+      { AllocateObjectInstr* alloc = it.Current()->AsAllocateObject();
+        if ((alloc != NULL) &&
+            IsAllocationSinkingCandidate(alloc, kOptimisticCheck)) {
+          alloc->SetIdentity(AliasIdentity::AllocationSinkingCandidate());
+          candidates_.Add(alloc);
+        }
+      }
+      { AllocateUninitializedContextInstr* alloc =
+            it.Current()->AsAllocateUninitializedContext();
+        if ((alloc != NULL) &&
+            IsAllocationSinkingCandidate(alloc, kOptimisticCheck)) {
+          alloc->SetIdentity(AliasIdentity::AllocationSinkingCandidate());
+          candidates_.Add(alloc);
+        }
       }
     }
   }
 
   // Transitively unmark all candidates that are not strictly valid.
   bool changed;
   do {
     changed = false;
     for (intptr_t i = 0; i < candidates_.length(); i++) {
-      AllocateObjectInstr* alloc = candidates_[i];
+      Definition* alloc = candidates_[i];
       if (alloc->Identity().IsAllocationSinkingCandidate()) {
         if (!IsAllocationSinkingCandidate(alloc, kStrictCheck)) {
           alloc->SetIdentity(AliasIdentity::Unknown());
           changed = true;
         }
       }
     }
   } while (changed);
 
   // Shrink the list of candidates removing all unmarked ones.
   intptr_t j = 0;
   for (intptr_t i = 0; i < candidates_.length(); i++) {
-    AllocateObjectInstr* alloc = candidates_[i];
+    Definition* alloc = candidates_[i];
     if (alloc->Identity().IsAllocationSinkingCandidate()) {
       if (FLAG_trace_optimization) {
         OS::Print("discovered allocation sinking candidate: v%" Pd "\n",
                   alloc->ssa_temp_index());
       }
 
       if (j != i) {
         candidates_[j] = alloc;
       }
       j++;
@@ skipping 61 matching lines @@
 // the load forwarding because they flow into phis that load forwarding
 // inserts. Discover such allocations and remove them from the list
 // of allocation sinking candidates undoing all changes that we did
 // in preparation for sinking these allocations.
 void AllocationSinking::DiscoverFailedCandidates() {
   // Transitively unmark all candidates that are not strictly valid.
   bool changed;
   do {
     changed = false;
     for (intptr_t i = 0; i < candidates_.length(); i++) {
-      AllocateObjectInstr* alloc = candidates_[i];
+      Definition* alloc = candidates_[i];
       if (alloc->Identity().IsAllocationSinkingCandidate()) {
         if (!IsAllocationSinkingCandidate(alloc, kStrictCheck)) {
           alloc->SetIdentity(AliasIdentity::Unknown());
           changed = true;
         }
       }
     }
   } while (changed);
 
   // Remove all failed candidates from the candidates list.
   intptr_t j = 0;
   for (intptr_t i = 0; i < candidates_.length(); i++) {
-    AllocateObjectInstr* alloc = candidates_[i];
+    Definition* alloc = candidates_[i];
     if (!alloc->Identity().IsAllocationSinkingCandidate()) {
       if (FLAG_trace_optimization) {
         OS::Print("allocation v%" Pd " can't be eliminated\n",
                   alloc->ssa_temp_index());
       }
 
 #ifdef DEBUG
       for (Value* use = alloc->env_use_list();
            use != NULL;
            use = use->next_use()) {
@@ skipping 163 matching lines @@
   }
 
   return NULL;
 }
 
 
 // Insert MaterializeObject instruction for the given allocation before
 // the given instruction that can deoptimize.
 void AllocationSinking::CreateMaterializationAt(
     Instruction* exit,
-    AllocateObjectInstr* alloc,
-    const Class& cls,
+    Definition* alloc,
     const ZoneGrowableArray<const Object*>& slots) {
   ZoneGrowableArray<Value*>* values =
       new(I) ZoneGrowableArray<Value*>(slots.length());
 
   // All loads should be inserted before the first materialization so that
   // IR follows the following pattern: loads, materializations, deoptimizing
   // instruction.
   Instruction* load_point = FirstMaterializationAt(exit);
 
   // Insert load instruction for every field.
   for (intptr_t i = 0; i < slots.length(); i++) {
     LoadFieldInstr* load = slots[i]->IsField()
         ? new(I) LoadFieldInstr(
             new(I) Value(alloc),
             &Field::Cast(*slots[i]),
             AbstractType::ZoneHandle(I),
             alloc->token_pos())
         : new(I) LoadFieldInstr(
             new(I) Value(alloc),
             Smi::Cast(*slots[i]).Value(),
             AbstractType::ZoneHandle(I),
             alloc->token_pos());
     flow_graph_->InsertBefore(
         load_point, load, NULL, FlowGraph::kValue);
     values->Add(new(I) Value(load));
   }
 
-  MaterializeObjectInstr* mat =
-      new(I) MaterializeObjectInstr(alloc, cls, slots, values);
+  MaterializeObjectInstr* mat = NULL;
+  if (alloc->IsAllocateObject()) {
+    mat = new(I) MaterializeObjectInstr(
+        alloc->AsAllocateObject(), slots, values);
+  } else {
+    ASSERT(alloc->IsAllocateUninitializedContext());
+    mat = new(I) MaterializeObjectInstr(
+        alloc->AsAllocateUninitializedContext(), slots, values);
+  }
+
   flow_graph_->InsertBefore(exit, mat, NULL, FlowGraph::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();
@@ skipping 72 matching lines @@
   // We are not removing allocations from the worklist not to waste space on
   // the side maintaining BitVector of already processed allocations: worklist
   // is expected to be very small thus linear search in it is just as effecient
   // as a bitvector.
   for (intptr_t i = 0; i < worklist_.length(); i++) {
     Collect(worklist_[i]);
   }
 }
 
 
-void AllocationSinking::InsertMaterializations(AllocateObjectInstr* alloc) {
+void AllocationSinking::InsertMaterializations(Definition* alloc) {
   // Collect all fields that are written for this instance.
   ZoneGrowableArray<const Object*>* slots =
       new(I) ZoneGrowableArray<const Object*>(5);
 
   for (Value* use = alloc->input_use_list();
        use != NULL;
        use = use->next_use()) {
     StoreInstanceFieldInstr* store = use->instruction()->AsStoreInstanceField();
     if ((store != NULL) && (store->instance()->definition() == alloc)) {
       if (!store->field().IsNull()) {
         AddSlot(slots, store->field());
       } else {
         AddSlot(slots, Smi::ZoneHandle(I, Smi::New(store->offset_in_bytes())));
       }
     }
   }
 
   if (alloc->ArgumentCount() > 0) {
-    ASSERT(alloc->ArgumentCount() == 1);
-    intptr_t type_args_offset = alloc->cls().type_arguments_field_offset();
+    AllocateObjectInstr* alloc_object = alloc->AsAllocateObject();
+    ASSERT(alloc_object->ArgumentCount() == 1);
+    intptr_t type_args_offset =
+        alloc_object->cls().type_arguments_field_offset();
     AddSlot(slots, Smi::ZoneHandle(I, Smi::New(type_args_offset)));
   }
 
   // Collect all instructions that mention this object in the environment.
   exits_collector_.CollectTransitively(alloc);
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits_collector_.exits().length(); i++) {
     CreateMaterializationAt(
-        exits_collector_.exits()[i], alloc, alloc->cls(), *slots);
+        exits_collector_.exits()[i], alloc, *slots);
   }
 }
 
 
 }  // namespace dart