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

runtime/vm/flow_graph.cc

 // Copyright (c) 2012, 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.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 662 matching lines @@
 
     return assigned_vars_;
   }
 
   // Returns true if the value set by the given store reaches any load from the
   // same local variable.
   bool IsStoreAlive(BlockEntryInstr* block, StoreLocalInstr* store) {
     if (store->local().Equals(*flow_graph_->CurrentContextVar())) {
       return true;
     }
+    if ((flow_graph_->FunctionTypeArgsVar() != NULL) &&

[Vyacheslav Egorov (Google), 2017/05/22 11:23:21]

Is this a mutable variable? 

I thought it's just an incoming argument which can't be mutated. 

[regis, 2017/05/22 17:51:08]

It is invariable with one exception: if the generic function is nested in a
parent generic function, the type argument vector of the parent is prepended to
the passed-in type argument vector. This is done only once on entry. I plan to
do this by a runtime call. Would this prevent using a
SpecialParameterInstr(kind) as you suggest below? 

[regis, 2017/05/22 18:02:42]

I suppose I could use the SpecialParameterInstr only if the generic function
does not have a generic parent. And I could bail out of inlining it if it has
one.

[Vyacheslav Egorov (Google), 2017/05/22 18:39:43]

I think there is no problem. I think the best way to express the second case
(when you need to prepend something) is by emitting explicit store-local - then
a lot of things will work out of the box, e.g.

1) First case: no nesting.

Unopt Graph:
// no special code in the graph itself.
// function entry point handles copying of type arguments from 
// stack slot before the receiver into :function_type_args variable
// (just what we do with context). All uses just load this variable
LoadLocal(:function_type_args)
USE(...)

Opt Graph:
// no special code in the graph, 
// initial declarations in B0 contain special instruction
// SpecialParameterInstr(kTypeArgs). 
// SSA renaming handles the rest.
B0 {
  v42 <- SpecialParameter(kTypeArgs)
}
...
USE(v42)

2) Second case: function is nested, requires prepending on entry.

Unopt Graph:
// function entry point handles copying of type arguments from 
// stack slot before the receiver into :function_type_args variable
// (just what we do with context). Then there is code in B1 doing 
// prepending - then result is stored in the local
B1: 
  LoadLocal(:function_type_args)
  PushArgument()
  StaticCall(Object._prependTypeArguments, ...)
  StoreLocal(:function_type_args)
  ... somewhere later ...
  LoadLocal(:function_type_args)
  USE(...)

Optimized Graph:
// SSA renaming will handle everything.
B0 {
  v42 <- SpecialParameter(kTypeArgs)
}
B1:
  PushArgument(v42)
  v43 <- StaticCall(Object._prependTypeArguments, v42)
...
  USE(v43)  // SSA renaming handled it

+        store->local().Equals(*flow_graph_->FunctionTypeArgsVar())) {
+      return true;
+    }
 
     if (store->is_dead()) {
       return false;
     }
     if (store->is_last()) {
       const intptr_t index = store->local().BitIndexIn(num_non_copied_params_);
       return GetLiveOutSet(block)->Contains(index);
     }
 
     return true;
   }
 
   // Returns true if the given load is the last for the local and the value
   // of the local will not flow into another one.
   bool IsLastLoad(BlockEntryInstr* block, LoadLocalInstr* load) {
     if (load->local().Equals(*flow_graph_->CurrentContextVar())) {
       return false;
     }
+    if ((flow_graph_->FunctionTypeArgsVar() != NULL) &&
+        load->local().Equals(*flow_graph_->FunctionTypeArgsVar())) {
+      return false;
+    }
     const intptr_t index = load->local().BitIndexIn(num_non_copied_params_);
     return load->is_last() && !GetLiveOutSet(block)->Contains(index);
   }
 
  private:
   virtual void ComputeInitialSets();
 
   const FlowGraph* flow_graph_;
   const intptr_t num_non_copied_params_;
   GrowableArray<BitVector*> assigned_vars_;
@@ skipping 54 matching lines @@
           kill->Add(index);
         }
         live_in->Remove(index);
         continue;
       }
     }
   }
 }
 
 
-void FlowGraph::ComputeSSA(
-    intptr_t next_virtual_register_number,
-    ZoneGrowableArray<Definition*>* inlining_parameters) {
+void FlowGraph::ComputeSSA(intptr_t next_virtual_register_number,
+                           ZoneGrowableArray<Definition*>* inlining_parameters,
+                           Definition* inlining_type_args) {
   ASSERT((next_virtual_register_number == 0) || (inlining_parameters != NULL));
   current_ssa_temp_index_ = next_virtual_register_number;
   GrowableArray<BitVector*> dominance_frontier;
   ComputeDominators(&dominance_frontier);
 
   VariableLivenessAnalysis variable_liveness(this);
   variable_liveness.Analyze();
 
   GrowableArray<PhiInstr*> live_phis;
 
   InsertPhis(preorder_, variable_liveness.ComputeAssignedVars(),
              dominance_frontier, &live_phis);
 
 
   // Rename uses to reference inserted phis where appropriate.
   // Collect phis that reach a non-environment use.
-  Rename(&live_phis, &variable_liveness, inlining_parameters);
+  Rename(&live_phis, &variable_liveness, inlining_parameters,
+         inlining_type_args);
 
   // Propagate alive mark transitively from alive phis and then remove
   // non-live ones.
   RemoveDeadPhis(&live_phis);
 }
 
 
 // Compute immediate dominators and the dominance frontier for each basic
 // block.  As a side effect of the algorithm, sets the immediate dominator
 // of each basic block.
@@ skipping 167 matching lines @@
           }
         }
       }
     }
   }
 }
 
 
 void FlowGraph::Rename(GrowableArray<PhiInstr*>* live_phis,
                        VariableLivenessAnalysis* variable_liveness,
-                       ZoneGrowableArray<Definition*>* inlining_parameters) {
+                       ZoneGrowableArray<Definition*>* inlining_parameters,
+                       Definition* inlining_type_args) {
   GraphEntryInstr* entry = graph_entry();
 
   // Initial renaming environment.
   GrowableArray<Definition*> env(variable_count());
 
   // Add global constants to the initial definitions.
   constant_null_ = GetConstant(Object::ZoneHandle());
   constant_dead_ = GetConstant(Symbols::OptimizedOut());
   constant_empty_context_ = GetConstant(Object::empty_context());
 
@@ skipping 15 matching lines @@
       ParameterInstr* param = new (zone()) ParameterInstr(i, entry);
       param->set_ssa_temp_index(alloc_ssa_temp_index());  // New SSA temp.
       AddToInitialDefinitions(param);
       env.Add(param);
     }
   }
 
   // Initialize all locals in the renaming environment  For OSR, the locals have
   // already been handled as parameters.
   if (!IsCompiledForOsr()) {
+    const intptr_t type_args_env_index =
+        (FunctionTypeArgsVar() != NULL) ? FunctionTypeArgsEnvIndex() : -1;
     for (intptr_t i = parameter_count(); i < variable_count(); ++i) {
-      if (i == CurrentContextEnvIndex()) {
+      if (i == type_args_env_index) {

[Vyacheslav Egorov (Google), 2017/05/22 11:23:21]

I think a better way would be to mimic what we do for incomming closure context
and use a special marker in the environment.

For closure context we use CurrentContextInstr (which is confusingly named for
historical reasons) - and register allocator / inliner hooks it up with a
correct value. 

Maybe what we should do is rename CurrentContextInstr to SpecialParameter(kind)
and have

SpecialParameter(kContext) for context
SpecialParameter(kTypeArguments) for arguments

then we can handle both type arguments and context here uniformly and you will
not need to thread inlining_type_args into here. Instead you hook it up in the
inliner itself: search for AsCurrentContext to see how the context is hooked up.

[regis, 2017/05/22 17:51:08]

Thank you for the suggestion. Let me try that.

+        if (inlining_type_args != NULL) {
+          AllocateSSAIndexes(inlining_type_args);
+          AddToInitialDefinitions(inlining_type_args);
+          env.Add(inlining_type_args);
+        } else {
+          // TODO(regis): For now, initialize local variable to null.
+          // Where do we check for a passed type args? If not passed in, must
+          // set to vector of dynamic of the proper length.
+          // Do we need a FunctionTypeArgsInstr?
+          env.Add(constant_null());
+        }
+      } else if (i == CurrentContextEnvIndex()) {
         if (function().IsClosureFunction()) {
           CurrentContextInstr* context = new CurrentContextInstr();
           context->set_ssa_temp_index(alloc_ssa_temp_index());  // New SSA temp.
           AddToInitialDefinitions(context);
           env.Add(context);
         } else {
           env.Add(constant_empty_context());
         }
       } else {
         env.Add(constant_null());
@@ skipping 1282 matching lines @@
                                                 Representation rep,
                                                 intptr_t cid) {
   ExtractNthOutputInstr* extract =
       new (Z) ExtractNthOutputInstr(new (Z) Value(instr), index, rep, cid);
   instr->ReplaceUsesWith(extract);
   InsertAfter(instr, extract, NULL, FlowGraph::kValue);
 }
 
 
 }  // namespace dart