Support inlining of calls where type arguments are passed to generic functions.

runtime/vm/flow_graph_inliner.cc

Index: runtime/vm/flow_graph_inliner.cc
diff --git a/runtime/vm/flow_graph_inliner.cc b/runtime/vm/flow_graph_inliner.cc
index 65c37415495fe331a2acc600cf65aca6347e4dc5..3831f51b8b058887b25dff631eb56ef9efa339da 100644
--- a/runtime/vm/flow_graph_inliner.cc
+++ b/runtime/vm/flow_graph_inliner.cc
@@ -432,24 +432,27 @@ class CallSites : public ValueObject {
 
 struct InlinedCallData {
   InlinedCallData(Definition* call,
+                  intptr_t first_param_index,  // 1 if type args are passed.
                   GrowableArray<Value*>* arguments,
                   const Function& caller,
                   intptr_t caller_inlining_id)
       : call(call),
+        first_param_index(first_param_index),
         arguments(arguments),
         callee_graph(NULL),
         parameter_stubs(NULL),
         exit_collector(NULL),
         caller(caller),
-        caller_inlining_id_(caller_inlining_id) {}
+        caller_inlining_id(caller_inlining_id) {}
 
   Definition* call;
+  const intptr_t first_param_index;
   GrowableArray<Value*>* arguments;
   FlowGraph* callee_graph;
   ZoneGrowableArray<Definition*>* parameter_stubs;
   InlineExitCollector* exit_collector;
   const Function& caller;
-  const intptr_t caller_inlining_id_;
+  const intptr_t caller_inlining_id;
 };
 
 
@@ -514,6 +517,108 @@ static bool HasAnnotation(const Function& function, const char* annotation) {
 }
 
 
+static void InlineCall(Zone* zone,
+                       FlowGraph* caller_graph,
+                       InlinedCallData* call_data,
+                       const TargetInfo* target_info) {
+  CSTAT_TIMER_SCOPE(Thread::Current(), graphinliner_subst_timer);
+  const bool is_polymorphic = call_data->call->IsPolymorphicInstanceCall();
+  ASSERT(is_polymorphic == (target_info != NULL));
+  FlowGraph* callee_graph = call_data->callee_graph;
+  TargetEntryInstr* callee_entry = callee_graph->graph_entry()->normal_entry();
+  if (!is_polymorphic) {
+    // Plug result in the caller graph.
+    InlineExitCollector* exit_collector = call_data->exit_collector;
+    exit_collector->PrepareGraphs(callee_graph);
+    exit_collector->ReplaceCall(callee_entry);
+  }
+
+  // Replace each stub with the actual argument or the caller's constant.
+  // Nulls denote optional parameters for which no actual was given.
+  const intptr_t first_param_index = call_data->first_param_index;
+  // When first_param_index > 0, the stub and actual argument processed in the
+  // first loop iteration represent a passed-in type argument vector.
+  GrowableArray<Value*>* arguments = call_data->arguments;
+  intptr_t first_arg_stub_index = 0;
+  if (arguments->length() != call_data->parameter_stubs->length()) {
+    ASSERT(arguments->length() == call_data->parameter_stubs->length() - 1);
+    ASSERT(first_param_index == 0);
+    // The first parameter stub accepts an optional type argument vector, but
+    // none was provided in arguments.
+    first_arg_stub_index = 1;
+  }
+  for (intptr_t i = 0; i < arguments->length(); ++i) {
+    Value* actual = (*arguments)[i];
+    if (is_polymorphic && (i == first_param_index)) {
+      // Replace the receiver argument with a redefinition to prevent code from
+      // the inlined body from being hoisted above the inlined entry.
+      RedefinitionInstr* redefinition =
+          new (zone) RedefinitionInstr(actual->Copy(zone));
+      redefinition->set_ssa_temp_index(caller_graph->alloc_ssa_temp_index());
+      if (target_info->IsSingleCid()) {
+        redefinition->UpdateType(CompileType::FromCid(target_info->cid_start));
+      }
+      redefinition->InsertAfter(callee_entry);
+      Definition* stub = (*call_data->parameter_stubs)[first_arg_stub_index];

[Vyacheslav Egorov (Google), 2017/07/03 16:15:43]

I think this is the problematic place. This should probably be
first_arg_stub_index + i 

Consider refactoring code to remove the duplication of the last two lines:

Definition* defn = NULL;
if (is_polymorphic && (i == ...)) {
  ...
  defn = redefinition;
} else if (value != NULL) {
  defn = value->definition();
}

if (defn != NULL) {
  call_data->parameter_stubs->At(first_arg_stub_index + i)->ReplaceUsesWith(...)
}

[regis, 2017/07/05 18:41:29]

Good catch! If first_arg_stub_index is 1, i has to be 0 (+i makes no
difference), but first_arg_stub_index can be 0 while i is 1 (bug!!).

I refactored the code as suggested.

+      stub->ReplaceUsesWith(redefinition);
+    } else if (actual != NULL) {
+      Definition* stub =
+          (*call_data->parameter_stubs)[first_arg_stub_index + i];
+      stub->ReplaceUsesWith(actual->definition());
+    }
+  }
+
+  if (!is_polymorphic) {
+    // Remove push arguments of the call.
+    Definition* call = call_data->call;
+    for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {
+      PushArgumentInstr* push = call->PushArgumentAt(i);
+      push->ReplaceUsesWith(push->value()->definition());
+      push->RemoveFromGraph();
+    }
+  }
+
+  // Replace remaining constants with uses by constants in the caller's
+  // initial definitions.
+  GrowableArray<Definition*>* defns =
+      callee_graph->graph_entry()->initial_definitions();
+  for (intptr_t i = 0; i < defns->length(); ++i) {
+    ConstantInstr* constant = (*defns)[i]->AsConstant();
+    if ((constant != NULL) && constant->HasUses()) {
+      constant->ReplaceUsesWith(caller_graph->GetConstant(constant->value()));
+    }
+    SpecialParameterInstr* param = (*defns)[i]->AsSpecialParameter();
+    if ((param != NULL) && param->HasUses()) {
+      if (param->kind() == SpecialParameterInstr::kContext) {
+        ASSERT(!is_polymorphic);

[Vyacheslav Egorov (Google), 2017/07/03 16:15:43]

maybe leave a comment here that we currently don't support polymorphic inlining
of closure calls (we used to support that back in the days when there was a
class per closure, that's why inliner contained some code to deal with it)

[regis, 2017/07/05 18:41:29]

Done.

+        ASSERT(call_data->call->IsClosureCall());
+        LoadFieldInstr* context_load = new (zone) LoadFieldInstr(
+            new Value((*arguments)[first_param_index]->definition()),
+            Closure::context_offset(),
+            AbstractType::ZoneHandle(zone, AbstractType::null()),
+            call_data->call->token_pos());
+        context_load->set_is_immutable(true);
+        context_load->set_ssa_temp_index(caller_graph->alloc_ssa_temp_index());
+        context_load->InsertBefore(callee_entry->next());
+        param->ReplaceUsesWith(context_load);
+      } else {
+        ASSERT(param->kind() == SpecialParameterInstr::kTypeArgs);
+        Definition* type_args;
+        if (first_param_index > 0) {
+          type_args = (*arguments)[0]->definition();
+        } else {
+          type_args = callee_graph->constant_null();
+        }
+        param->ReplaceUsesWith(type_args);
+      }
+    }
+  }
+
+  // Check that inlining maintains use lists.
+  DEBUG_ASSERT(!FLAG_verify_compiler || caller_graph->VerifyUseLists());
+}
+
+
 class CallSiteInliner : public ValueObject {
  public:
   explicit CallSiteInliner(FlowGraphInliner* inliner, intptr_t threshold)
@@ -573,7 +678,7 @@ class CallSiteInliner : public ValueObject {
   }
 
   void InlineCalls() {
-    // If inlining depth is less then one abort.
+    // If inlining depth is less than one abort.
     if (inlining_depth_threshold_ < 1) return;
     if (caller_graph_->function().deoptimization_counter() >=
         FLAG_deoptimization_counter_inlining_threshold) {
@@ -829,13 +934,28 @@ class CallSiteInliner : public ValueObject {
         // concrete information about the values, for example constant values,
         // without linking between the caller and callee graphs.
         // TODO(zerny): Put more information in the stubs, eg, type information.
+        const intptr_t first_actual_param_index = call_data->first_param_index;
+        const intptr_t inlined_type_args_param =
+            (FLAG_reify_generic_functions && function.IsGeneric()) ? 1 : 0;
+        const intptr_t num_inlined_params =
+            inlined_type_args_param + function.NumParameters();
         ZoneGrowableArray<Definition*>* param_stubs =
-            new (Z) ZoneGrowableArray<Definition*>(function.NumParameters());
+            new (Z) ZoneGrowableArray<Definition*>(num_inlined_params);
 
+        // Create a ConstantInstr as Definition for the type arguments, if any.
+        if (first_actual_param_index > 0) {
+          // A type argument vector is explicitly passed.
+          param_stubs->Add(
+              CreateParameterStub(-1, (*arguments)[0], callee_graph));
+        } else if (inlined_type_args_param > 0) {
+          // No type argument vector is passed to the generic function,
+          // pass a null vector, which is the same as a vector of dynamic types.
+          param_stubs->Add(callee_graph->GetConstant(Object::ZoneHandle()));
+        }
         // Create a parameter stub for each fixed positional parameter.
         for (intptr_t i = 0; i < function.num_fixed_parameters(); ++i) {
-          param_stubs->Add(
-              CreateParameterStub(i, (*arguments)[i], callee_graph));
+          param_stubs->Add(CreateParameterStub(
+              i, (*arguments)[first_actual_param_index + i], callee_graph));
         }
 
         // If the callee has optional parameters, rebuild the argument and stub
@@ -843,9 +963,9 @@ class CallSiteInliner : public ValueObject {
         // parameters.
         if (function.HasOptionalParameters()) {
           TRACE_INLINING(THR_Print("     adjusting for optional parameters\n"));
-          if (!AdjustForOptionalParameters(*parsed_function, argument_names,
-                                           arguments, param_stubs,
-                                           callee_graph)) {
+          if (!AdjustForOptionalParameters(
+                  *parsed_function, first_actual_param_index, argument_names,
+                  arguments, param_stubs, callee_graph)) {
             function.set_is_inlinable(false);
             TRACE_INLINING(THR_Print("     Bailout: optional arg mismatch\n"));
             PRINT_INLINING_TREE("Optional arg mismatch", &call_data->caller,
@@ -856,17 +976,10 @@ class CallSiteInliner : public ValueObject {
 
         // After treating optional parameters the actual/formal count must
         // match.
-        // TODO(regis): Consider type arguments in arguments.
-        if (arguments->length() != function.NumParameters()) {
-          ASSERT(function.IsGeneric());
-          ASSERT(arguments->length() == function.NumParameters() + 1);
-          TRACE_INLINING(
-              THR_Print("     Bailout: unsupported type arguments\n"));
-          PRINT_INLINING_TREE("Unsupported type arguments", &call_data->caller,
-                              &function, call_data->call);
-          return false;
-        }
-        ASSERT(param_stubs->length() == callee_graph->parameter_count());
+        ASSERT(arguments->length() ==
+               first_actual_param_index + function.NumParameters());
+        ASSERT(param_stubs->length() ==
+               inlined_type_args_param + callee_graph->parameter_count());
 
         // Update try-index of the callee graph.
         BlockEntryInstr* call_block = call_data->call->GetBlock();
@@ -1020,7 +1133,7 @@ class CallSiteInliner : public ValueObject {
             callee_graph,
             inliner_->NextInlineId(callee_graph->function(),
                                    call_data->call->token_pos(),
-                                   call_data->caller_inlining_id_));
+                                   call_data->caller_inlining_id));
         TRACE_INLINING(THR_Print("     Success\n"));
         TRACE_INLINING(THR_Print("       with size %" Pd "\n",
                                  function.optimized_instruction_count()));
@@ -1121,61 +1234,6 @@ class CallSiteInliner : public ValueObject {
     }
   }
 
-  void InlineCall(InlinedCallData* call_data) {
-    CSTAT_TIMER_SCOPE(Thread::Current(), graphinliner_subst_timer);
-    FlowGraph* callee_graph = call_data->callee_graph;
-    TargetEntryInstr* callee_entry =
-        callee_graph->graph_entry()->normal_entry();
-    // Plug result in the caller graph.
-    InlineExitCollector* exit_collector = call_data->exit_collector;
-    exit_collector->PrepareGraphs(callee_graph);
-    exit_collector->ReplaceCall(callee_entry);
-
-    // Replace each stub with the actual argument or the caller's constant.
-    // Nulls denote optional parameters for which no actual was given.
-    GrowableArray<Value*>* arguments = call_data->arguments;
-    for (intptr_t i = 0; i < arguments->length(); ++i) {
-      Definition* stub = (*call_data->parameter_stubs)[i];
-      Value* actual = (*arguments)[i];
-      if (actual != NULL) stub->ReplaceUsesWith(actual->definition());
-    }
-
-    // Remove push arguments of the call.
-    Definition* call = call_data->call;
-    for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {
-      PushArgumentInstr* push = call->PushArgumentAt(i);
-      push->ReplaceUsesWith(push->value()->definition());
-      push->RemoveFromGraph();
-    }
-
-    // Replace remaining constants with uses by constants in the caller's
-    // initial definitions.
-    GrowableArray<Definition*>* defns =
-        callee_graph->graph_entry()->initial_definitions();
-    for (intptr_t i = 0; i < defns->length(); ++i) {
-      ConstantInstr* constant = (*defns)[i]->AsConstant();
-      if ((constant != NULL) && constant->HasUses()) {
-        constant->ReplaceUsesWith(
-            caller_graph_->GetConstant(constant->value()));
-      }
-      CurrentContextInstr* context = (*defns)[i]->AsCurrentContext();
-      if ((context != NULL) && context->HasUses()) {
-        ASSERT(call->IsClosureCall());
-        LoadFieldInstr* context_load = new (Z) LoadFieldInstr(
-            new Value((*arguments)[0]->definition()), Closure::context_offset(),
-            AbstractType::ZoneHandle(zone(), AbstractType::null()),
-            call_data->call->token_pos());
-        context_load->set_is_immutable(true);
-        context_load->set_ssa_temp_index(caller_graph_->alloc_ssa_temp_index());
-        context_load->InsertBefore(callee_entry->next());
-        context->ReplaceUsesWith(context_load);
-      }
-    }
-
-    // Check that inlining maintains use lists.
-    DEBUG_ASSERT(!FLAG_verify_compiler || caller_graph_->VerifyUseLists());
-  }
-
   static intptr_t CountConstants(const GrowableArray<Value*>& arguments) {
     intptr_t count = 0;
     for (intptr_t i = 0; i < arguments.length(); i++) {
@@ -1228,10 +1286,11 @@ class CallSiteInliner : public ValueObject {
         arguments.Add(call->PushArgumentAt(i)->value());
       }
       InlinedCallData call_data(
-          call, &arguments, call_info[call_idx].caller(),
+          call, call->FirstParamIndex(), &arguments,
+          call_info[call_idx].caller(),
           call_info[call_idx].caller_graph->inlining_id());
       if (TryInlining(call->function(), call->argument_names(), &call_data)) {
-        InlineCall(&call_data);
+        InlineCall(zone(), caller_graph_, &call_data, NULL);
       }
     }
   }
@@ -1274,10 +1333,11 @@ class CallSiteInliner : public ValueObject {
         arguments.Add(call->PushArgumentAt(i)->value());
       }
       InlinedCallData call_data(
-          call, &arguments, call_info[call_idx].caller(),
+          call, call->FirstParamIndex(), &arguments,
+          call_info[call_idx].caller(),
           call_info[call_idx].caller_graph->inlining_id());
       if (TryInlining(target, call->argument_names(), &call_data)) {
-        InlineCall(&call_data);
+        InlineCall(zone(), caller_graph_, &call_data, NULL);
       }
     }
   }
@@ -1305,6 +1365,7 @@ class CallSiteInliner : public ValueObject {
   }
 
   bool AdjustForOptionalParameters(const ParsedFunction& parsed_function,
+                                   intptr_t first_param_index,
                                    const Array& argument_names,
                                    GrowableArray<Value*>* arguments,
                                    ZoneGrowableArray<Definition*>* param_stubs,
@@ -1315,23 +1376,23 @@ class CallSiteInliner : public ValueObject {
     ASSERT(!function.HasOptionalPositionalParameters() ||
            !function.HasOptionalNamedParameters());
 
-    // TODO(regis): Consider type arguments in arguments.
     intptr_t arg_count = arguments->length();
     intptr_t param_count = function.NumParameters();
     intptr_t fixed_param_count = function.num_fixed_parameters();
-    ASSERT(fixed_param_count <= arg_count);
-    ASSERT(arg_count <= param_count);
+    ASSERT(fixed_param_count <= arg_count - first_param_index);
+    ASSERT(arg_count - first_param_index <= param_count);
 
     if (function.HasOptionalPositionalParameters()) {
       // Create a stub for each optional positional parameters with an actual.
-      for (intptr_t i = fixed_param_count; i < arg_count; ++i) {
+      for (intptr_t i = first_param_index + fixed_param_count; i < arg_count;
+           ++i) {
         param_stubs->Add(CreateParameterStub(i, (*arguments)[i], callee_graph));
       }
       ASSERT(function.NumOptionalPositionalParameters() ==
              (param_count - fixed_param_count));
       // For each optional positional parameter without an actual, add its
       // default value.
-      for (intptr_t i = arg_count; i < param_count; ++i) {
+      for (intptr_t i = arg_count - first_param_index; i < param_count; ++i) {
         const Instance& object =
             parsed_function.DefaultParameterValueAt(i - fixed_param_count);
         ConstantInstr* constant = new (Z) ConstantInstr(object);
@@ -1343,10 +1404,12 @@ class CallSiteInliner : public ValueObject {
 
     ASSERT(function.HasOptionalNamedParameters());
 
-    // Passed arguments must match fixed parameters plus named arguments.
+    // Passed arguments (not counting optional type args) must match fixed
+    // parameters plus named arguments.
     intptr_t argument_names_count =
         (argument_names.IsNull()) ? 0 : argument_names.Length();
-    ASSERT(arg_count == (fixed_param_count + argument_names_count));
+    ASSERT((arg_count - first_param_index) ==
+           (fixed_param_count + argument_names_count));
 
     // Fast path when no optional named parameters are given.
     if (argument_names_count == 0) {
@@ -1362,12 +1425,12 @@ class CallSiteInliner : public ValueObject {
     for (intptr_t i = 0; i < argument_names.Length(); ++i) {
       String& arg_name = String::Handle(caller_graph_->zone());
       arg_name ^= argument_names.At(i);
-      named_args.Add(
-          NamedArgument(&arg_name, (*arguments)[i + fixed_param_count]));
+      named_args.Add(NamedArgument(
+          &arg_name, (*arguments)[first_param_index + fixed_param_count + i]));
     }
 
-    // Truncate the arguments array to just fixed parameters.
-    arguments->TruncateTo(fixed_param_count);
+    // Truncate the arguments array to just type args and fixed parameters.
+    arguments->TruncateTo(first_param_index + fixed_param_count);
 
     // For each optional named parameter, add the actual argument or its
     // default if no argument is passed.
@@ -1386,7 +1449,8 @@ class CallSiteInliner : public ValueObject {
       arguments->Add(arg);
       // Create a stub for the argument or use the parameter's default value.
       if (arg != NULL) {
-        param_stubs->Add(CreateParameterStub(i, arg, callee_graph));
+        param_stubs->Add(
+            CreateParameterStub(first_param_index + i, arg, callee_graph));
       } else {
         param_stubs->Add(
             GetDefaultValue(i - fixed_param_count, parsed_function));
@@ -1529,8 +1593,8 @@ bool PolymorphicInliner::TryInliningPoly(const TargetInfo& target_info) {
   for (int i = 0; i < call_->ArgumentCount(); ++i) {
     arguments.Add(call_->PushArgumentAt(i)->value());
   }
-  InlinedCallData call_data(call_, &arguments, caller_function_,
-                            caller_inlining_id_);
+  InlinedCallData call_data(call_, call_->instance_call()->FirstParamIndex(),
+                            &arguments, caller_function_, caller_inlining_id_);
   Function& target = Function::ZoneHandle(zone(), target_info.target->raw());
   if (!owner_->TryInlining(target, call_->instance_call()->argument_names(),
                            &call_data)) {
@@ -1542,50 +1606,7 @@ bool PolymorphicInliner::TryInliningPoly(const TargetInfo& target_info) {
   inlined_entries_.Add(callee_graph->graph_entry());
   exit_collector_->Union(call_data.exit_collector);
 
-  // Replace parameter stubs and constants.  Replace the receiver argument
-  // with a redefinition to prevent code from the inlined body from being
-  // hoisted above the inlined entry.
-  ASSERT(arguments.length() > 0);
-  Value* actual = arguments[0];
-  RedefinitionInstr* redefinition = new (Z) RedefinitionInstr(actual->Copy(Z));
-  redefinition->set_ssa_temp_index(
-      owner_->caller_graph()->alloc_ssa_temp_index());
-  if (target_info.IsSingleCid()) {
-    redefinition->UpdateType(CompileType::FromCid(target_info.cid_start));
-  }
-  redefinition->InsertAfter(callee_graph->graph_entry()->normal_entry());
-  Definition* stub = (*call_data.parameter_stubs)[0];
-  stub->ReplaceUsesWith(redefinition);
-
-  for (intptr_t i = 1; i < arguments.length(); ++i) {
-    actual = arguments[i];
-    if (actual != NULL) {
-      stub = (*call_data.parameter_stubs)[i];
-      stub->ReplaceUsesWith(actual->definition());
-    }
-  }
-  GrowableArray<Definition*>* defns =
-      callee_graph->graph_entry()->initial_definitions();
-  for (intptr_t i = 0; i < defns->length(); ++i) {
-    ConstantInstr* constant = (*defns)[i]->AsConstant();
-    if ((constant != NULL) && constant->HasUses()) {
-      constant->ReplaceUsesWith(
-          owner_->caller_graph()->GetConstant(constant->value()));
-    }
-    CurrentContextInstr* context = (*defns)[i]->AsCurrentContext();
-    if ((context != NULL) && context->HasUses()) {
-      ASSERT(call_data.call->IsClosureCall());
-      LoadFieldInstr* context_load = new (Z)
-          LoadFieldInstr(new Value(redefinition), Closure::context_offset(),
-                         AbstractType::ZoneHandle(zone(), AbstractType::null()),
-                         call_data.call->token_pos());
-      context_load->set_is_immutable(true);
-      context_load->set_ssa_temp_index(
-          owner_->caller_graph()->alloc_ssa_temp_index());
-      context_load->InsertAfter(redefinition);
-      context->ReplaceUsesWith(context_load);
-    }
-  }
+  InlineCall(zone(), owner_->caller_graph(), &call_data, &target_info);
   return true;
 }