Inlining of calls with optional parameters.

runtime/vm/flow_graph_inliner.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_inliner.h"
 
 #include "vm/compiler.h"
 #include "vm/flags.h"
 #include "vm/flow_graph.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 13 matching lines @@
     "Inline only functions with up to threshold instructions (default 50)");
 // TODO(srdjan): set to 3 once crash in apidoc.dart is resolved.
 DEFINE_FLAG(int, inlining_depth_threshold, 3,
     "Inline recursively up to threshold depth (default 3)");
 DEFINE_FLAG(bool, inline_control_flow, true,
     "Inline functions with control flow.");
 DECLARE_FLAG(bool, print_flow_graph);
 DECLARE_FLAG(int, deoptimization_counter_threshold);
 DECLARE_FLAG(bool, verify_compiler);
 DECLARE_FLAG(bool, compiler_stats);
+DECLARE_FLAG(bool, reject_named_argument_as_positional);

[srdjan, 2012/10/23 16:00:52]

Remove?

[srdjan, 2012/10/23 16:02:37]

Actually not yet :-)... sorry

 
 #define TRACE_INLINING(statement)                                              \
   do {                                                                         \
     if (FLAG_trace_inlining) statement;                                        \
   } while (false)
 
 
 // Test if a call is recursive by looking in the deoptimization environment.
 static bool IsCallRecursive(const Function& function, Definition* call) {
   Environment* env = call->env();
   while (env != NULL) {
     if (function.raw() == env->function().raw()) return true;
     env = env->outer();
   }
   return false;
 }
 
 
-// TODO(zerny): Remove the following classes once we have moved the label/join
-// map for control flow out of the AST an into the flow graph builder.
+// TODO(zerny): Remove the ChildrenVisitor and SourceLabelResetter once we have
+// moved the label/join map for control flow out of the AST an into the flow
+// graph builder.
 
 // Default visitor to traverse child nodes.
 class ChildrenVisitor : public AstNodeVisitor {
  public:
   ChildrenVisitor() { }
 #define DEFINE_VISIT(type, name)                                               \
   virtual void Visit##type(type* node) { node->VisitChildren(this); }
   NODE_LIST(DEFINE_VISIT);
 #undef DEFINE_VISIT
 };
@@ skipping 26 matching lines @@
   }
   void Reset(AstNode* node, SourceLabel* lbl) {
     node->VisitChildren(this);
     if (lbl == NULL) return;
     lbl->join_for_break_ = NULL;
     lbl->join_for_continue_ = NULL;
   }
 };
 
 
+// Helper to create a parameter stub from an actual argument.
+static Definition* CreateParameterStub(intptr_t i,
+                                       Value* argument,
+                                       FlowGraph* graph) {
+  ConstantInstr* constant = argument->definition()->AsConstant();
+  if (constant != NULL) {
+    return new ConstantInstr(constant->value());
+  } else {
+    return new ParameterInstr(i, graph->graph_entry());
+  }
+}
+
+
+// Helper to get the default value of a formal parameter.
+static ConstantInstr* GetDefaultValue(intptr_t i,
+                                      const ParsedFunction& parsed_function) {
+  return new ConstantInstr(Object::ZoneHandle(
+      parsed_function.default_parameter_values().At(i)));
+}
+
+
+// Pair of an argument name and its value.
+struct NamedArgument : ZoneAllocated {

[Kevin Millikin (Google), 2012/10/23 11:34:42]

It should work to make this ValueObject.

[zerny-google, 2012/10/23 13:03:42]

Done.

+ public:
+  String* name;
+  Value* value;
+  NamedArgument(String* name, Value* value)
+    : name(name), value(value) { }
+};
+
+
 // A collection of call sites to consider for inlining.
 class CallSites : public FlowGraphVisitor {
  public:
   explicit CallSites(FlowGraph* flow_graph)
       : FlowGraphVisitor(flow_graph->postorder()),  // We don't use this order.
         static_calls_(),
         closure_calls_(),
         instance_calls_() { }
 
   GrowableArray<StaticCallInstr*>* static_calls() {
@@ skipping 97 matching lines @@
 
   bool inlined() const { return inlined_; }
 
   double GrowthFactor() const {
     return static_cast<double>(inlined_size_) /
         static_cast<double>(initial_size_);
   }
 
  private:
   bool TryInlining(const Function& function,
+                   const Array& argument_names,
                    GrowableArray<Value*>* arguments,
                    Definition* call) {
     TRACE_INLINING(OS::Print("  => %s (deopt count %d)\n",
                              function.ToCString(),
                              function.deoptimization_counter()));
 
     // Abort if the inlinable bit on the function is low.
     if (!function.IsInlineable()) {
       TRACE_INLINING(OS::Print("     Bailout: not inlinable\n"));
       return false;
     }
 
-    // Abort if the callee has optional parameters.
-    if (function.HasOptionalParameters()) {
-      TRACE_INLINING(OS::Print("     Bailout: optional parameters\n"));
-      return false;
-    }
-
-    // Assuming no optional parameters the actual/formal count should match.
-    ASSERT(arguments->length() == function.num_fixed_parameters());
-
     // Abort if this function has deoptimized too much.
     if (function.deoptimization_counter() >=
         FLAG_deoptimization_counter_threshold) {
       function.set_is_inlinable(false);
       TRACE_INLINING(OS::Print("     Bailout: deoptimization threshold\n"));
       return false;
     }
 
     // Abort if this is a recursive occurrence.
     if (IsCallRecursive(function, call)) {
       function.set_is_inlinable(false);
       TRACE_INLINING(OS::Print("     Bailout: recursive function\n"));
       return false;
     }
 
     // Abort if the callee has an intrinsic translation.
     if (Intrinsifier::CanIntrinsify(function)) {
       function.set_is_inlinable(false);
       TRACE_INLINING(OS::Print("     Bailout: can intrinsify\n"));
       return false;
     }
 
+    // Abort if we are running legacy support for optional parameters.
+    if (!FLAG_reject_named_argument_as_positional &&
+        function.HasOptionalPositionalParameters() &&
+        (!argument_names.IsNull() && (argument_names.Length() > 0))) {
+      function.set_is_inlinable(false);
+      TRACE_INLINING(OS::Print(
+          "     Bailout: named optional positional parameter\n"));
+      return false;
+    }
+
     Isolate* isolate = Isolate::Current();
     // Save and clear IC data.
     const Array& prev_ic_data = Array::Handle(isolate->ic_data_array());
     isolate->set_ic_data_array(Array::null());
     // Save and clear deopt id.
     const intptr_t prev_deopt_id = isolate->deopt_id();
     isolate->set_deopt_id(0);
     // Install bailout jump.
     LongJump* base = isolate->long_jump_base();
     LongJump jump;
@@ skipping 30 matching lines @@
       // Abort if the callee graph contains control flow.
       if (!FLAG_inline_control_flow &&
           (callee_graph->preorder().length() != 2)) {
         function.set_is_inlinable(false);
         isolate->set_long_jump_base(base);
         isolate->set_ic_data_array(prev_ic_data.raw());
         TRACE_INLINING(OS::Print("     Bailout: control flow\n"));
         return false;
       }
 
+      // 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.
+      GrowableArray<Definition*> param_stubs(function.NumParameters());
+
+      // 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));
+      }
+
+      // 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(OS::Print("     adjusting for optional parameters\n"));
+        AdjustForOptionalParameters(*parsed_function,
+                                    argument_names,
+                                    arguments,
+                                    &param_stubs,
+                                    callee_graph);
+        // Add a bogus parameter at the end for the (unused) argument descriptor
+        // slot. The parser allocates an extra slot between locals and
+        // parameters to hold the argument descriptor in case it escapes.  We
+        // currently bailout if there are argument test expressions or escaping
+        // variables so this parameter and the stack slot are not used.
+        if (parsed_function->GetSavedArgumentsDescriptorVar() != NULL) {
+          param_stubs.Add(new ParameterInstr(
+              function.NumParameters(), callee_graph->graph_entry()));
+        }
+      }
+
+      // After treating optional parameters the actual/formal count must match.
+      ASSERT(arguments->length() == function.NumParameters());
+      ASSERT(param_stubs.length() == callee_graph->parameter_count());
+
       {
         TimerScope timer(FLAG_compiler_stats,
                          &CompilerStats::graphinliner_ssa_timer,
                          isolate);
         // Compute SSA on the callee graph, catching bailouts.
-        callee_graph->ComputeSSA(next_ssa_temp_index_);
+        callee_graph->ComputeSSA(next_ssa_temp_index_, &param_stubs);
         callee_graph->ComputeUseLists();
       }
 
       {
         TimerScope timer(FLAG_compiler_stats,
                          &CompilerStats::graphinliner_opt_timer,
                          isolate);
         // TODO(zerny): Do more optimization passes on the callee graph.
         FlowGraphOptimizer optimizer(callee_graph);
         optimizer.ApplyICData();
@@ skipping 33 matching lines @@
         caller_graph_->InlineCall(call, callee_graph);
         next_ssa_temp_index_ = caller_graph_->max_virtual_register_number();
 
         // Remove push arguments of the call.
         for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {
           PushArgumentInstr* push = call->ArgumentAt(i);
           push->ReplaceUsesWith(push->value()->definition());
           push->RemoveFromGraph();
         }
 
-        // Replace formal parameters with actuals.
-        intptr_t arg_index = 0;
+        // Replace each stub with the actual argument or the caller's constant.
+        // Nulls denote optional parameters for which no actual was given.
+        for (intptr_t i = 0; i < arguments->length(); ++i) {
+          Definition* stub = param_stubs[i];
+          Value* actual = (*arguments)[i];
+          if (actual != NULL) stub->ReplaceUsesWith(actual->definition());
+        }
+
+        // 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) {
-          ParameterInstr* param = (*defns)[i]->AsParameter();
-          if (param != NULL) {
-            param->ReplaceUsesWith((*arguments)[arg_index++]->definition());
+          ConstantInstr* constant = (*defns)[i]->AsConstant();
+          if (constant == NULL ||
+              ((constant->input_use_list() == NULL) &&
+               (constant->env_use_list() == NULL))) {
+            continue;
           }
+          constant->ReplaceUsesWith(
+            caller_graph_->AddConstantToInitialDefinitions(constant->value()));
         }
-        ASSERT(arg_index == arguments->length());
-
-        // Replace callee's null constant with caller's null constant.
-        callee_graph->graph_entry()->constant_null()->ReplaceUsesWith(
-            caller_graph_->graph_entry()->constant_null());
       }
 
       TRACE_INLINING(OS::Print("     Success\n"));
 
       // Add the function to the cache.
       if (!in_cache) function_cache.Add(parsed_function);
 
       // Check that inlining maintains use lists.
       DEBUG_ASSERT(!FLAG_verify_compiler || caller_graph_->ValidateUseLists());
 
       // Build succeeded so we restore the bailout jump.
       inlined_ = true;
       inlined_size_ += size;
       isolate->set_long_jump_base(base);
       isolate->set_deopt_id(prev_deopt_id);
       isolate->set_ic_data_array(prev_ic_data.raw());
       return true;
     } else {
       Error& error = Error::Handle();
       error = isolate->object_store()->sticky_error();
       isolate->object_store()->clear_sticky_error();
       isolate->set_long_jump_base(base);
       isolate->set_deopt_id(prev_deopt_id);
       isolate->set_ic_data_array(prev_ic_data.raw());
       TRACE_INLINING(OS::Print("     Bailout: %s\n", error.ToErrorCString()));
       return false;
     }
   }
 
-  // Parse a function reusing the cache if possible. Returns true if the
-  // function was in the cache.
+  // Parse a function reusing the cache if possible.
   ParsedFunction* ParseFunction(const Function& function, bool* in_cache) {
     // TODO(zerny): Use a hash map for the cache.
     for (intptr_t i = 0; i < function_cache.length(); ++i) {
       ParsedFunction* parsed_function = function_cache[i];
       if (parsed_function->function().raw() == function.raw()) {
         *in_cache = true;
         SourceLabelResetter reset;
         parsed_function->node_sequence()->Visit(&reset);
         return parsed_function;
       }
     }
     *in_cache = false;
     ParsedFunction* parsed_function = new ParsedFunction(function);
     Parser::ParseFunction(parsed_function);
     parsed_function->AllocateVariables();
     return parsed_function;
   }
 
   void InlineStaticCalls() {
     const GrowableArray<StaticCallInstr*>& calls =
         *inlining_call_sites_->static_calls();
     TRACE_INLINING(OS::Print("  Static Calls (%d)\n", calls.length()));
     for (intptr_t i = 0; i < calls.length(); ++i) {
       StaticCallInstr* call = calls[i];
       GrowableArray<Value*> arguments(call->ArgumentCount());
       for (int i = 0; i < call->ArgumentCount(); ++i) {
         arguments.Add(call->ArgumentAt(i)->value());
       }
-      TryInlining(call->function(), &arguments, call);
+      TryInlining(call->function(), call->argument_names(), &arguments, call);
     }
   }
 
   void InlineClosureCalls() {
     const GrowableArray<ClosureCallInstr*>& calls =
         *inlining_call_sites_->closure_calls();
     TRACE_INLINING(OS::Print("  Closure Calls (%d)\n", calls.length()));
     for (intptr_t i = 0; i < calls.length(); ++i) {
       ClosureCallInstr* call = calls[i];
       // Find the closure of the callee.
       ASSERT(call->ArgumentCount() > 0);
       const CreateClosureInstr* closure =
           call->ArgumentAt(0)->value()->definition()->AsCreateClosure();
       if (closure == NULL) {
         TRACE_INLINING(OS::Print("     Bailout: non-closure operator\n"));
         continue;
       }
       GrowableArray<Value*> arguments(call->ArgumentCount() - 1);
       for (int i = 1; i < call->ArgumentCount(); ++i) {
         arguments.Add(call->ArgumentAt(i)->value());
       }
-      TryInlining(closure->function(), &arguments, call);
+      TryInlining(closure->function(),
+                  call->argument_names(),
+                  &arguments,
+                  call);
     }
   }
 
   void InlineInstanceCalls() {
     const GrowableArray<PolymorphicInstanceCallInstr*>& calls =
         *inlining_call_sites_->instance_calls();
     TRACE_INLINING(OS::Print("  Polymorphic Instance Calls (%d)\n",
                              calls.length()));
     for (intptr_t i = 0; i < calls.length(); ++i) {
       PolymorphicInstanceCallInstr* instr = calls[i];
       const ICData& ic_data = instr->ic_data();
       const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0));
       if (instr->with_checks()) {
         TRACE_INLINING(OS::Print(
           "  => %s (deopt count %d)\n     Bailout: %"Pd" checks\n",
           target.ToCString(),
           target.deoptimization_counter(),
           ic_data.NumberOfChecks()));
         continue;
       }
       GrowableArray<Value*> arguments(instr->ArgumentCount());
       for (int i = 0; i < instr->ArgumentCount(); ++i) {
         arguments.Add(instr->ArgumentAt(i)->value());
       }
-      TryInlining(target, &arguments, instr);
+      TryInlining(target,
+                  instr->instance_call()->argument_names(),
+                  &arguments,
+                  instr);
     }
   }
 
+  void AdjustForOptionalParameters(const ParsedFunction& parsed_function,
+                                   const Array& argument_names,
+                                   GrowableArray<Value*>* arguments,
+                                   GrowableArray<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());
+
+    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);
+
+    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) {
+        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 - fixed_param_count;

[Kevin Millikin (Google), 2012/10/23 11:34:42]

I think it's a bit weird to adjust the initial value and limit like this.  It
seems more logical (follows on from the previous loop) if it is:

for (intptr_t i = arg_count; i < param_count; ++i) {
  ...values().At(i - fixed_param_count);
  ...
}

[zerny-google, 2012/10/23 13:03:42]

Done.

+           i < param_count - fixed_param_count;
+           ++i) {
+        const Object& object =
+            Object::ZoneHandle(
+                parsed_function.default_parameter_values().At(i));
+        ConstantInstr* constant = new ConstantInstr(object);
+        arguments->Add(NULL);
+        param_stubs->Add(constant);
+      }
+      return;
+    }
+
+    ASSERT(function.HasOptionalNamedParameters());
+
+    // Passed arguments 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));
+
+    // 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;
+    }
+
+    // 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(Isolate::Current());
+      arg_name ^= argument_names.At(i);
+      named_args.Add(
+          new NamedArgument(&arg_name, (*arguments)[i + fixed_param_count]));
+    }
+
+    // Truncate the arguments array to just fixed parameters.
+    arguments->TruncateTo(fixed_param_count);
+
+    // For each optional named parameter, add the actual argument or its
+    // default if no argument is passed.
+    for (intptr_t i = fixed_param_count; i < param_count; i++) {

[Kevin Millikin (Google), 2012/10/23 11:34:42]

There's a mix of ++i and i++ in loops in this function.  Stick with one or the
other.

[zerny-google, 2012/10/23 13:03:42]

Done.

+      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;
+          break;
+        }
+      }
+      arguments->Add(arg);
+      // Create a stub parameter for the named argument or its default.
+      if (arg != NULL) {
+        param_stubs->Add(CreateParameterStub(i, arg, callee_graph));
+      } else {
+        param_stubs->Add(
+            GetDefaultValue(i - fixed_param_count, parsed_function));
+      }
+    }
+  }
+
+
   FlowGraph* caller_graph_;
   intptr_t next_ssa_temp_index_;
   bool inlined_;
   intptr_t initial_size_;
   intptr_t inlined_size_;
   intptr_t inlining_depth_;
   CallSites* collected_call_sites_;
   CallSites* inlining_call_sites_;
   GrowableArray<ParsedFunction*> function_cache;
 
@@ skipping 31 matching lines @@
         OS::Print("After Inlining of %s\n", flow_graph_->
                   parsed_function().function().ToFullyQualifiedCString());
         FlowGraphPrinter printer(*flow_graph_);
         printer.PrintBlocks();
       }
     }
   }
 }
 
 }  // namespace dart