Support type arguments for allocation sinking in certain conditions.

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 4079 matching lines @@
   // 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->AddRepresentative(defn);
   }
   return aliased_set;
 }
 
 
+static bool HasSupportedArguments(AllocateObjectInstr* alloc) {

[Vyacheslav Egorov (Google), 2013/06/12 13:26:17]

The name is a bit confusing. Maybe AllocationHasSimpleTypeArguments?

[Florian Schneider, 2013/06/13 14:38:39]

Done.

+  if (alloc->ArgumentCount() == 0) return true;

[srdjan, 2013/06/12 16:22:07]

What Slava said and maybe add an itty-bitty comment  about argument count  and
result. 

+  ASSERT(alloc->ArgumentCount() == 2);
+  Value* arg1 = alloc->PushArgumentAt(1)->value();
+  if (!arg1->BindsToConstant()) return false;
+
+  const Object& obj = arg1->BoundConstant();
+  return obj.IsSmi()
+      && (Smi::Cast(obj).Value() == StubCode::kNoInstantiator);
+}
+
+
 class LoadOptimizer : public ValueObject {
  public:
   LoadOptimizer(FlowGraph* graph,
                 AliasedSet* aliased_set,
                 DirectChainedHashMap<LoadKeyValueTrait>* map)
       : graph_(graph),
         map_(map),
         aliased_set_(aliased_set),
         in_(graph_->preorder().length()),
         out_(graph_->preorder().length()),
@@ skipping 125 matching lines @@
         // 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 known values for these
         // 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)) {
+            HasSupportedArguments(alloc)) {
           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.
+              // Found a load. Initialize current value of the field to null for
+              // normal fields, or with type arguments.
               gen->Add(load->expr_id());
               if (out_values == NULL) out_values = CreateBlockOutValues();
+
+              if (alloc->ArgumentCount() > 0) {

[Vyacheslav Egorov (Google), 2013/06/12 13:26:17]

ASSERT(alloc->ArgumentCount() == 2);

[Florian Schneider, 2013/06/13 14:38:39]

Done.

+                const Class& cls = Class::Handle(alloc->constructor().Owner());

[srdjan, 2013/06/12 16:22:07]

We have alloc->ArgumentCount() > 0 (or its variation) in many places. How about
adding a tester HasArguments to AllocateObjectInstr? Constructor of
AllocateObjectInstr has an assert that the count is eithr 0 or two. I winder if
we should replicate asserts everywhere or not?

[Florian Schneider, 2013/06/20 14:06:26]

Done. I guess it does not hurt to have more asserts, than just in the
constructor. For now I'll leave them in those places.

+                intptr_t type_args_offset = cls.type_arguments_field_offset();
+                if (load->offset_in_bytes() == type_args_offset) {
+                  (*out_values)[load->expr_id()] =
+                      alloc->PushArgumentAt(0)->value()->definition();
+                  continue;
+                }
+              }
               (*out_values)[load->expr_id()] = graph_->constant_null();
             }
           }
           continue;
         }
 
         if (!IsLoadEliminationCandidate(defn)) {
           continue;
         }
 
@@ skipping 2097 matching lines @@
     }
   }
 }
 
 
 // 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;
-  }
+  if (!HasSupportedArguments(alloc)) 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;
     }
   }
 
@@ skipping 17 matching lines @@
        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();
+  if (alloc->ArgumentCount() > 0) {
+    ASSERT(alloc->ArgumentCount() == 2);
+    for (intptr_t i = 0; i < alloc->ArgumentCount(); ++i) {
+      alloc->PushArgumentAt(i)->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();
@@ skipping 23 matching lines @@
   }
 
   // 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_);
 
+  if (FLAG_trace_optimization) {
+    FlowGraphPrinter::PrintGraph("Sinking", 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.
@@ skipping 95 matching lines @@
   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());
   }
 
+  if (alloc->ArgumentCount() > 0) {
+    const String& name = String::Handle(Symbols::New(":type_args"));
+    const Field& type_args_field =
+        Field::ZoneHandle(Field::New(
+            name,
+            false,  // !static
+            false,  // !final
+            false,  // !const
+            Class::Handle(alloc->constructor().Owner()),
+            0));  // No token position.
+    const Class& cls = Class::Handle(alloc->constructor().Owner());
+    type_args_field.SetOffset(cls.type_arguments_field_offset());
+    AddField(fields, type_args_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