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

runtime/vm/flow_graph_inliner.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.
 #if !defined(DART_PRECOMPILED_RUNTIME)
 #include "vm/flow_graph_inliner.h"
 
 #include "vm/aot_optimizer.h"
 #include "vm/precompiler.h"
 #include "vm/block_scheduler.h"
 #include "vm/branch_optimizer.h"
@@ skipping 414 matching lines @@
   GrowableArray<StaticCallInfo> static_calls_;
   GrowableArray<ClosureCallInfo> closure_calls_;
   GrowableArray<InstanceCallInfo> instance_calls_;
 
   DISALLOW_COPY_AND_ASSIGN(CallSites);
 };
 
 
 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;
 };
 
 
 class CallSiteInliner;
 
 class PolymorphicInliner : public ValueObject {
  public:
   PolymorphicInliner(CallSiteInliner* owner,
                      PolymorphicInstanceCallInstr* call,
                      const Function& caller_function,
@@ skipping 103 matching lines @@
       return true;
     }
     if ((const_arg_count >= FLAG_inlining_constant_arguments_count) &&
         (instr_count <= FLAG_inlining_constant_arguments_min_size_threshold)) {
       return true;
     }
     return false;
   }
 
   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) {
       return;
     }
     // Create two call site collections to swap between.
     CallSites sites1(caller_graph_, inlining_depth_threshold_);
     CallSites sites2(caller_graph_, inlining_depth_threshold_);
     CallSites* call_sites_temp = NULL;
     collected_call_sites_ = &sites1;
@@ skipping 235 matching lines @@
             inliner_->precompiler_->TryApplyFeedback(
                 parsed_function->function(), callee_graph);
           }
         }
 #endif
 
         // The parameter stubs are a copy of the actual arguments providing
         // 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
         // arrays so that actual arguments are in one-to-one with the formal
         // 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,
                                 &function, call_data->call);
             return false;
           }
         }
 
         // 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();
         if (call_block->InsideTryBlock()) {
           intptr_t try_index = call_block->try_index();
           for (BlockIterator it = callee_graph->reverse_postorder_iterator();
                !it.Done(); it.Advance()) {
             BlockEntryInstr* block = it.Current();
             block->set_try_index(try_index);
           }
@@ skipping 133 matching lines @@
         }
         // When inlined, we add the deferred prefixes of the callee to the
         // caller's list of deferred prefixes.
         caller_graph()->AddToDeferredPrefixes(
             callee_graph->deferred_prefixes());
 
         FlowGraphInliner::SetInliningId(
             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()));
         PRINT_INLINING_TREE(NULL, &call_data->caller, &function, call);
         return true;
       } else {
         error = thread()->sticky_error();
         thread()->clear_sticky_error();
 
         if (error.IsLanguageError() &&
@@ skipping 92 matching lines @@
     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.
+    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) {
-      Definition* stub = (*call_data->parameter_stubs)[i];
+      Definition* stub =
+          (*call_data->parameter_stubs)[first_arg_stub_index + i];
       Value* actual = (*arguments)[i];
-      if (actual != NULL) stub->ReplaceUsesWith(actual->definition());
+      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);
+      SpecialParameterInstr* param = (*defns)[i]->AsSpecialParameter();
+      if ((param != NULL) && param->HasUses()) {
+        if (param->kind() == SpecialParameterInstr::kContext) {
+          ASSERT(call->IsClosureCall());
+          LoadFieldInstr* context_load = new (Z) 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());
   }
 
   static intptr_t CountConstants(const GrowableArray<Value*>& arguments) {
     intptr_t count = 0;
     for (intptr_t i = 0; i < arguments.length(); i++) {
@@ skipping 39 matching lines @@
         }
         PRINT_INLINING_TREE("Too cold", &call_info[call_idx].caller(),
                             &call->function(), call);
         continue;
       }
       GrowableArray<Value*> arguments(call->ArgumentCount());
       for (int i = 0; i < call->ArgumentCount(); ++i) {
         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);
       }
     }
   }
 
   void InlineClosureCalls() {
     const GrowableArray<CallSites::ClosureCallInfo>& call_info =
         inlining_call_sites_->closure_calls();
@@ skipping 25 matching lines @@
           call->ArgumentCount() < target.num_fixed_parameters()) {
         TRACE_INLINING(THR_Print("     Bailout: wrong parameter count\n"));
         continue;
       }
 
       GrowableArray<Value*> arguments(call->ArgumentCount());
       for (int i = 0; i < call->ArgumentCount(); ++i) {
         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);
       }
     }
   }
 
   void InlineInstanceCalls() {
     const GrowableArray<CallSites::InstanceCallInfo>& call_info =
         inlining_call_sites_->instance_calls();
@@ skipping 10 matching lines @@
       }
       const Function& cl = call_info[call_idx].caller();
       intptr_t caller_inlining_id =
           call_info[call_idx].caller_graph->inlining_id();
       PolymorphicInliner inliner(this, call, cl, caller_inlining_id);
       inliner.Inline();
     }
   }
 
   bool AdjustForOptionalParameters(const ParsedFunction& parsed_function,
+                                   intptr_t first_param_index,
                                    const Array& argument_names,
                                    GrowableArray<Value*>* arguments,
                                    ZoneGrowableArray<Definition*>* param_stubs,
                                    FlowGraph* callee_graph) {
     const Function& function = parsed_function.function();
     // The language and this code does not support both optional positional
     // and optional named parameters for the same function.
     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);
         arguments->Add(NULL);
         param_stubs->Add(constant);
       }
       return true;
     }
 
     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) {
       for (intptr_t i = 0; i < param_count - fixed_param_count; ++i) {
         arguments->Add(NULL);
         param_stubs->Add(GetDefaultValue(i, parsed_function));
       }
       return true;
     }
 
     // Otherwise, build a collection of name/argument pairs.
     GrowableArray<NamedArgument> named_args(argument_names_count);
     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.
     intptr_t match_count = 0;
     for (intptr_t i = fixed_param_count; i < param_count; ++i) {
       String& param_name = String::Handle(function.ParameterNameAt(i));
       // Search for and add the named argument.
       Value* arg = NULL;
       for (intptr_t j = 0; j < named_args.length(); ++j) {
         if (param_name.Equals(*named_args[j].name)) {
           arg = named_args[j].value;
           match_count++;
           break;
         }
       }
       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));
       }
     }
     return argument_names_count == match_count;
   }
 
   FlowGraphInliner* inliner_;
   FlowGraph* caller_graph_;
@@ skipping 122 matching lines @@
       target_info.IsSingleCid() &&
       TryInlineRecognizedMethod(target_info.cid_start, *target_info.target)) {
     owner_->inlined_ = true;
     return true;
   }
 
   GrowableArray<Value*> arguments(call_->ArgumentCount());
   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)) {
     return false;
   }
 
   FlowGraph* callee_graph = call_data.callee_graph;
   call_data.exit_collector->PrepareGraphs(callee_graph);
   inlined_entries_.Add(callee_graph->graph_entry());
   exit_collector_->Union(call_data.exit_collector);
 
   // Replace parameter stubs and constants.  Replace the receiver argument

[Vyacheslav Egorov (Google), 2017/06/28 14:56:02]

I think that parameter stubs replacement that happens here needs to match the
logic in the InlineCall on line 1147.

Ideally we want to move this logic into a shared function if possible. I don't
think it is very different. I can see a lot of duplicated code between here and
monomorphic InlineCall(...).

[regis, 2017/06/28 21:03:59]

That was it! Thanks!
I moved this code into a shared function as you suggested. 

   // 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);
+    SpecialParameterInstr* param = (*defns)[i]->AsSpecialParameter();
+    if ((param != NULL) && param->HasUses()) {
+      if (param->kind() == SpecialParameterInstr::kContext) {
+        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);
+        param->ReplaceUsesWith(context_load);
+      } else {
+        ASSERT(param->kind() == SpecialParameterInstr::kTypeArgs);
+        UNIMPLEMENTED();  // TODO(regis): Why am I not hitting this? No uses?
+      }
     }
   }
   return true;
 }
 
 
 static Instruction* AppendInstruction(Instruction* first, Instruction* second) {
   for (intptr_t i = second->InputCount() - 1; i >= 0; --i) {
     Value* input = second->InputAt(i);
     input->definition()->AddInputUse(input);
@@ skipping 2170 matching lines @@
     }
 
     default:
       return false;
   }
 }
 
 
 }  // namespace dart
 #endif  // !defined(DART_PRECOMPILED_RUNTIME)