| // 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_inliner.h" |
| |
| #include "vm/compiler.h" |
| #include "vm/flags.h" |
| #include "vm/flow_graph.h" |
| #include "vm/flow_graph_builder.h" |
| #include "vm/flow_graph_optimizer.h" |
| #include "vm/il_printer.h" |
| #include "vm/intrinsifier.h" |
| #include "vm/longjump.h" |
| #include "vm/object.h" |
| #include "vm/object_store.h" |
| #include "vm/timer.h" |
| |
| namespace dart { |
| |
| DEFINE_FLAG(bool, trace_inlining, false, "Trace inlining"); |
| DEFINE_FLAG(charp, inlining_filter, NULL, "Inline only in named function"); |
| |
| // Flags for inlining heuristics. |
| DEFINE_FLAG(int, inlining_depth_threshold, 3, |
| "Inline function calls up to threshold nesting depth"); |
| DEFINE_FLAG(int, inlining_size_threshold, 20, |
| "Always inline functions that have threshold or fewer instructions"); |
| DEFINE_FLAG(int, inlining_callee_call_sites_threshold, 1, |
| "Always inline functions containing threshold or fewer calls."); |
| DEFINE_FLAG(int, inlining_constant_arguments_count, 1, |
| "Inline function calls with sufficient constant arguments " |
| "and up to the increased threshold on instructions"); |
| DEFINE_FLAG(int, inlining_constant_arguments_size_threshold, 60, |
| "Inline function calls with sufficient constant arguments " |
| "and up to the increased threshold on instructions"); |
| DEFINE_FLAG(int, inlining_hotness, 10, |
| "Inline only hotter calls, in percents (0 .. 100); " |
| "default 10%: calls above-equal 10% of max-count are inlined."); |
| DEFINE_FLAG(bool, inline_recursive, true, |
| "Inline recursive calls."); |
| |
| DECLARE_FLAG(bool, print_flow_graph); |
| DECLARE_FLAG(bool, print_flow_graph_optimized); |
| DECLARE_FLAG(int, deoptimization_counter_threshold); |
| DECLARE_FLAG(bool, verify_compiler); |
| DECLARE_FLAG(bool, compiler_stats); |
| |
| #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 ChildrenVisitor and SourceLabelResetter once we have |
| // moved the label/join map for control flow out of the AST and 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 |
| }; |
| |
| |
| // Visitor to clear each AST node containing source labels. |
| class SourceLabelResetter : public ChildrenVisitor { |
| public: |
| SourceLabelResetter() { } |
| virtual void VisitSequenceNode(SequenceNode* node) { |
| Reset(node, node->label()); |
| } |
| virtual void VisitCaseNode(CaseNode* node) { |
| Reset(node, node->label()); |
| } |
| virtual void VisitSwitchNode(SwitchNode* node) { |
| Reset(node, node->label()); |
| } |
| virtual void VisitWhileNode(WhileNode* node) { |
| Reset(node, node->label()); |
| } |
| virtual void VisitDoWhileNode(DoWhileNode* node) { |
| Reset(node, node->label()); |
| } |
| virtual void VisitForNode(ForNode* node) { |
| Reset(node, node->label()); |
| } |
| virtual void VisitJumpNode(JumpNode* node) { |
| Reset(node, node->label()); |
| } |
| 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 { |
| public: |
| String* name; |
| Value* value; |
| NamedArgument(String* name, Value* value) |
| : name(name), value(value) { } |
| }; |
| |
| |
| // Helper to collect information about a callee graph when considering it for |
| // inlining. |
| class GraphInfoCollector : public ValueObject { |
| public: |
| GraphInfoCollector() |
| : call_site_count_(0), |
| instruction_count_(0) { } |
| |
| void Collect(const FlowGraph& graph) { |
| call_site_count_ = 0; |
| instruction_count_ = 0; |
| for (BlockIterator block_it = graph.postorder_iterator(); |
| !block_it.Done(); |
| block_it.Advance()) { |
| for (ForwardInstructionIterator it(block_it.Current()); |
| !it.Done(); |
| it.Advance()) { |
| ++instruction_count_; |
| if (it.Current()->IsStaticCall() || |
| it.Current()->IsClosureCall() || |
| it.Current()->IsPolymorphicInstanceCall()) { |
| ++call_site_count_; |
| } |
| } |
| } |
| } |
| |
| intptr_t call_site_count() const { return call_site_count_; } |
| intptr_t instruction_count() const { return instruction_count_; } |
| |
| private: |
| intptr_t call_site_count_; |
| intptr_t instruction_count_; |
| }; |
| |
| |
| // 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_(), |
| skip_static_call_deopt_ids_() { } |
| |
| const GrowableArray<StaticCallInstr*>& static_calls() const { |
| return static_calls_; |
| } |
| |
| const GrowableArray<ClosureCallInstr*>& closure_calls() const { |
| return closure_calls_; |
| } |
| |
| struct InstanceCallInfo { |
| PolymorphicInstanceCallInstr* call; |
| double ratio; |
| explicit InstanceCallInfo(PolymorphicInstanceCallInstr* call_arg) |
| : call(call_arg), ratio(0.0) {} |
| }; |
| |
| const GrowableArray<InstanceCallInfo>& instance_calls() const { |
| return instance_calls_; |
| } |
| |
| bool HasCalls() const { |
| return !(static_calls_.is_empty() && |
| closure_calls_.is_empty() && |
| instance_calls_.is_empty()); |
| } |
| |
| void Clear() { |
| static_calls_.Clear(); |
| closure_calls_.Clear(); |
| instance_calls_.Clear(); |
| skip_static_call_deopt_ids_.Clear(); |
| } |
| |
| void FindCallSites(FlowGraph* graph) { |
| ASSERT(graph != NULL); |
| const Function& function = graph->parsed_function().function(); |
| ASSERT(function.HasCode()); |
| const Code& code = Code::Handle(function.unoptimized_code()); |
| |
| skip_static_call_deopt_ids_.Clear(); |
| code.ExtractUncalledStaticCallDeoptIds(&skip_static_call_deopt_ids_); |
| |
| const intptr_t instance_call_start_ix = instance_calls_.length(); |
| for (BlockIterator block_it = graph->postorder_iterator(); |
| !block_it.Done(); |
| block_it.Advance()) { |
| for (ForwardInstructionIterator it(block_it.Current()); |
| !it.Done(); |
| it.Advance()) { |
| it.Current()->Accept(this); |
| } |
| } |
| // Compute instance call site ratio. |
| const intptr_t num_instance_calls = |
| instance_calls_.length() - instance_call_start_ix; |
| intptr_t max_count = 0; |
| GrowableArray<intptr_t> call_counts(num_instance_calls); |
| for (intptr_t i = 0; i < num_instance_calls; ++i) { |
| const intptr_t aggregate_count = |
| instance_calls_[i + instance_call_start_ix]. |
| call->ic_data().AggregateCount(); |
| call_counts.Add(aggregate_count); |
| if (aggregate_count > max_count) max_count = aggregate_count; |
| } |
| |
| |
| for (intptr_t i = 0; i < num_instance_calls; ++i) { |
| const double ratio = static_cast<double>(call_counts[i]) / max_count; |
| instance_calls_[i + instance_call_start_ix].ratio = ratio; |
| } |
| } |
| |
| void VisitClosureCall(ClosureCallInstr* call) { |
| closure_calls_.Add(call); |
| } |
| |
| void VisitPolymorphicInstanceCall(PolymorphicInstanceCallInstr* call) { |
| instance_calls_.Add(InstanceCallInfo(call)); |
| } |
| |
| void VisitStaticCall(StaticCallInstr* call) { |
| if (!call->function().IsInlineable()) return; |
| const intptr_t call_deopt_id = call->deopt_id(); |
| for (intptr_t i = 0; i < skip_static_call_deopt_ids_.length(); i++) { |
| if (call_deopt_id == skip_static_call_deopt_ids_[i]) { |
| // Do not inline this call. |
| return; |
| } |
| } |
| static_calls_.Add(call); |
| } |
| |
| private: |
| GrowableArray<StaticCallInstr*> static_calls_; |
| GrowableArray<ClosureCallInstr*> closure_calls_; |
| GrowableArray<InstanceCallInfo> instance_calls_; |
| GrowableArray<intptr_t> skip_static_call_deopt_ids_; |
| |
| DISALLOW_COPY_AND_ASSIGN(CallSites); |
| }; |
| |
| |
| class CallSiteInliner : public ValueObject { |
| public: |
| CallSiteInliner(FlowGraph* flow_graph, GrowableArray<Field*>* guarded_fields) |
| : caller_graph_(flow_graph), |
| inlined_(false), |
| initial_size_(flow_graph->InstructionCount()), |
| inlined_size_(0), |
| inlining_depth_(1), |
| collected_call_sites_(NULL), |
| inlining_call_sites_(NULL), |
| function_cache_(), |
| guarded_fields_(guarded_fields) { } |
| |
| // Inlining heuristics based on Cooper et al. 2008. |
| bool ShouldWeInline(intptr_t instr_count, |
| intptr_t call_site_count, |
| intptr_t const_arg_count) { |
| if (instr_count <= FLAG_inlining_size_threshold) { |
| return true; |
| } |
| if (call_site_count <= FLAG_inlining_callee_call_sites_threshold) { |
| return true; |
| } |
| if ((const_arg_count >= FLAG_inlining_constant_arguments_count) && |
| (instr_count <= FLAG_inlining_constant_arguments_size_threshold)) { |
| return true; |
| } |
| return false; |
| } |
| |
| // TODO(srdjan): Handle large 'skip_static_call_deopt_ids'. Currently |
| // max. size observed is 11 (dart2js). |
| void InlineCalls() { |
| // If inlining depth is less then one abort. |
| if (FLAG_inlining_depth_threshold < 1) return; |
| // Create two call site collections to swap between. |
| CallSites sites1(caller_graph_); |
| CallSites sites2(caller_graph_); |
| CallSites* call_sites_temp = NULL; |
| collected_call_sites_ = &sites1; |
| inlining_call_sites_ = &sites2; |
| // Collect initial call sites. |
| collected_call_sites_->FindCallSites(caller_graph_); |
| while (collected_call_sites_->HasCalls()) { |
| TRACE_INLINING(OS::Print(" Depth %"Pd" ----------\n", inlining_depth_)); |
| // Swap collected and inlining arrays and clear the new collecting array. |
| call_sites_temp = collected_call_sites_; |
| collected_call_sites_ = inlining_call_sites_; |
| inlining_call_sites_ = call_sites_temp; |
| collected_call_sites_->Clear(); |
| // Inline call sites at the current depth. |
| InlineStaticCalls(); |
| InlineClosureCalls(); |
| InlineInstanceCalls(); |
| // Increment the inlining depth. Checked before recursive inlining. |
| ++inlining_depth_; |
| } |
| collected_call_sites_ = NULL; |
| inlining_call_sites_ = NULL; |
| } |
| |
| bool inlined() const { return inlined_; } |
| |
| double GrowthFactor() const { |
| return static_cast<double>(inlined_size_) / |
| static_cast<double>(initial_size_); |
| } |
| |
| private: |
| struct InlinedCallData { |
| public: |
| InlinedCallData(Definition* call, GrowableArray<Value*>* arguments) |
| : call(call), |
| arguments(arguments), |
| callee_graph(NULL), |
| parameter_stubs(NULL), |
| exit_collector(NULL) { } |
| |
| Definition* call; |
| GrowableArray<Value*>* arguments; |
| FlowGraph* callee_graph; |
| ZoneGrowableArray<Definition*>* parameter_stubs; |
| InlineExitCollector* exit_collector; |
| }; |
| |
| bool TryInlining(const Function& function, |
| const Array& argument_names, |
| InlinedCallData* call_data) { |
| 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 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; |
| } |
| |
| GrowableArray<Value*>* arguments = call_data->arguments; |
| const intptr_t constant_arguments = CountConstants(*arguments); |
| if (!ShouldWeInline(function.optimized_instruction_count(), |
| function.optimized_call_site_count(), |
| constant_arguments)) { |
| TRACE_INLINING(OS::Print(" Bailout: early heuristics with " |
| "code size: %"Pd", " |
| "call sites: %"Pd", " |
| "const args: %"Pd"\n", |
| function.optimized_instruction_count(), |
| function.optimized_call_site_count(), |
| constant_arguments)); |
| return false; |
| } |
| |
| // Abort if this is a recursive occurrence. |
| Definition* call = call_data->call; |
| if (!FLAG_inline_recursive && 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; |
| } |
| |
| 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; |
| isolate->set_long_jump_base(&jump); |
| if (setjmp(*jump.Set()) == 0) { |
| // Parse the callee function. |
| bool in_cache; |
| ParsedFunction* parsed_function; |
| { |
| TimerScope timer(FLAG_compiler_stats, |
| &CompilerStats::graphinliner_parse_timer, |
| isolate); |
| parsed_function = GetParsedFunction(function, &in_cache); |
| } |
| |
| // Load IC data for the callee. |
| if (function.HasCode()) { |
| const Code& unoptimized_code = |
| Code::Handle(function.unoptimized_code()); |
| isolate->set_ic_data_array(unoptimized_code.ExtractTypeFeedbackArray()); |
| } |
| |
| // Build the callee graph. |
| InlineExitCollector* exit_collector = |
| new InlineExitCollector(caller_graph_, call); |
| FlowGraphBuilder builder(*parsed_function, exit_collector); |
| builder.SetInitialBlockId(caller_graph_->max_block_id()); |
| FlowGraph* callee_graph; |
| { |
| TimerScope timer(FLAG_compiler_stats, |
| &CompilerStats::graphinliner_build_timer, |
| isolate); |
| callee_graph = builder.BuildGraph(); |
| } |
| |
| // 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. |
| ZoneGrowableArray<Definition*>* param_stubs = |
| new ZoneGrowableArray<Definition*>(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) arguments |
| // descriptor slot. The parser allocates an extra slot between |
| // locals and parameters to hold the arguments 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(caller_graph_->max_virtual_register_number(), |
| param_stubs); |
| DEBUG_ASSERT(callee_graph->VerifyUseLists()); |
| } |
| |
| { |
| TimerScope timer(FLAG_compiler_stats, |
| &CompilerStats::graphinliner_opt_timer, |
| isolate); |
| // TODO(zerny): Do more optimization passes on the callee graph. |
| FlowGraphOptimizer optimizer(callee_graph, guarded_fields_); |
| optimizer.ApplyICData(); |
| DEBUG_ASSERT(callee_graph->VerifyUseLists()); |
| } |
| |
| if (FLAG_trace_inlining && |
| (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized)) { |
| OS::Print("Callee graph for inlining %s\n", |
| function.ToFullyQualifiedCString()); |
| FlowGraphPrinter printer(*callee_graph); |
| printer.PrintBlocks(); |
| } |
| |
| // Collect information about the call site and caller graph. |
| // TODO(zerny): Do this after CP and dead code elimination. |
| intptr_t constants_count = 0; |
| for (intptr_t i = 0; i < param_stubs->length(); ++i) { |
| if ((*param_stubs)[i]->IsConstant()) ++constants_count; |
| } |
| GraphInfoCollector info; |
| info.Collect(*callee_graph); |
| const intptr_t size = info.instruction_count(); |
| |
| function.set_optimized_instruction_count(size); |
| function.set_optimized_call_site_count(info.call_site_count()); |
| |
| // Use heuristics do decide if this call should be inlined. |
| if (!ShouldWeInline(size, |
| info.call_site_count(), |
| constants_count)) { |
| // If size is larger than all thresholds, don't consider it again. |
| if ((size > FLAG_inlining_size_threshold) && |
| (size > FLAG_inlining_callee_call_sites_threshold) && |
| (size > FLAG_inlining_constant_arguments_size_threshold)) { |
| function.set_is_inlinable(false); |
| } |
| 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: heuristics with " |
| "code size: %"Pd", " |
| "call sites: %"Pd", " |
| "const args: %"Pd"\n", |
| size, |
| info.call_site_count(), |
| constants_count)); |
| return false; |
| } |
| |
| // If depth is less or equal to threshold recursively add call sites. |
| if (inlining_depth_ < FLAG_inlining_depth_threshold) { |
| collected_call_sites_->FindCallSites(callee_graph); |
| } |
| |
| // Add the function to the cache. |
| if (!in_cache) function_cache_.Add(parsed_function); |
| |
| // 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()); |
| |
| call_data->callee_graph = callee_graph; |
| call_data->parameter_stubs = param_stubs; |
| call_data->exit_collector = exit_collector; |
| TRACE_INLINING(OS::Print(" Success\n")); |
| 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; |
| } |
| } |
| |
| void InlineCall(InlinedCallData* call_data) { |
| TimerScope timer(FLAG_compiler_stats, |
| &CompilerStats::graphinliner_subst_timer, |
| Isolate::Current()); |
| |
| // Plug result in the caller graph. |
| FlowGraph* callee_graph = call_data->callee_graph; |
| InlineExitCollector* exit_collector = call_data->exit_collector; |
| exit_collector->PrepareGraphs(callee_graph); |
| exit_collector->ReplaceCall(callee_graph->graph_entry()->normal_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_->AddConstantToInitialDefinitions( |
| constant->value())); |
| } |
| } |
| |
| // 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++) { |
| if (arguments[i]->BindsToConstant()) count++; |
| } |
| return count; |
| } |
| |
| // Parse a function reusing the cache if possible. |
| ParsedFunction* GetParsedFunction(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; |
| } |
| |
| // Include special handling for List. factory: inlining it is not helpful |
| // if the incoming argument is a non-constant value. |
| // TODO(srdjan): Fix inlining of List. factory. |
| 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]; |
| if (call->function().name() == Symbols::ListFactory().raw()) { |
| // Inline only if no arguments or a constant was passed. |
| ASSERT(call->function().NumImplicitParameters() == 1); |
| ASSERT(call->ArgumentCount() <= 2); |
| // Arg 0: Instantiator type arguments. |
| // Arg 1: Length (optional). |
| if ((call->ArgumentCount() == 2) && |
| (!call->PushArgumentAt(1)->value()->BindsToConstant())) { |
| // Do not inline since a non-constant argument was passed. |
| 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); |
| if (TryInlining(call->function(), call->argument_names(), &call_data)) { |
| InlineCall(&call_data); |
| } |
| } |
| } |
| |
| 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)->AsCreateClosure(); |
| if (closure == NULL) { |
| TRACE_INLINING(OS::Print(" Bailout: non-closure operator\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); |
| if (TryInlining(closure->function(), |
| call->argument_names(), |
| &call_data)) { |
| InlineCall(&call_data); |
| } |
| } |
| } |
| |
| void InlineInstanceCalls() { |
| const GrowableArray<CallSites::InstanceCallInfo>& call_info = |
| inlining_call_sites_->instance_calls(); |
| TRACE_INLINING(OS::Print(" Polymorphic Instance Calls (%d)\n", |
| call_info.length())); |
| for (intptr_t i = 0; i < call_info.length(); ++i) { |
| PolymorphicInstanceCallInstr* call = call_info[i].call; |
| const ICData& ic_data = call->ic_data(); |
| const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0)); |
| if (call->with_checks()) { |
| TRACE_INLINING(OS::Print( |
| " => %s (deopt count %d)\n Bailout: %"Pd" checks\n", |
| target.ToCString(), |
| target.deoptimization_counter(), |
| ic_data.NumberOfChecks())); |
| continue; |
| } |
| if ((call_info[i].ratio * 100) < FLAG_inlining_hotness) { |
| TRACE_INLINING(OS::Print( |
| " => %s (deopt count %d)\n Bailout: cold %f\n", |
| target.ToCString(), |
| target.deoptimization_counter(), |
| call_info[i].ratio)); |
| continue; |
| } |
| GrowableArray<Value*> arguments(call->ArgumentCount()); |
| for (int arg_i = 0; arg_i < call->ArgumentCount(); ++arg_i) { |
| arguments.Add(call->PushArgumentAt(arg_i)->value()); |
| } |
| InlinedCallData call_data(call, &arguments); |
| if (TryInlining(target, |
| call->instance_call()->argument_names(), |
| &call_data)) { |
| InlineCall(&call_data); |
| } |
| } |
| } |
| |
| void AdjustForOptionalParameters(const ParsedFunction& parsed_function, |
| 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()); |
| |
| 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; i < param_count; ++i) { |
| const Object& object = |
| Object::ZoneHandle( |
| parsed_function.default_parameter_values().At( |
| i - fixed_param_count)); |
| 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( |
| 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) { |
| 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 for the argument or use the parameter's default value. |
| 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_; |
| 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_; |
| GrowableArray<Field*>* guarded_fields_; |
| |
| DISALLOW_COPY_AND_ASSIGN(CallSiteInliner); |
| }; |
| |
| |
| void FlowGraphInliner::CollectGraphInfo(FlowGraph* flow_graph) { |
| GraphInfoCollector info; |
| info.Collect(*flow_graph); |
| const Function& function = flow_graph->parsed_function().function(); |
| function.set_optimized_instruction_count( |
| static_cast<uint16_t>(info.instruction_count())); |
| function.set_optimized_call_site_count( |
| static_cast<uint16_t>(info.call_site_count())); |
| } |
| |
| |
| void FlowGraphInliner::Inline() { |
| // Collect graph info and store it on the function. |
| // We might later use it for an early bailout from the inlining. |
| CollectGraphInfo(flow_graph_); |
| |
| if ((FLAG_inlining_filter != NULL) && |
| (strstr(flow_graph_-> |
| parsed_function().function().ToFullyQualifiedCString(), |
| FLAG_inlining_filter) == NULL)) { |
| return; |
| } |
| |
| TRACE_INLINING(OS::Print( |
| "Inlining calls in %s\n", |
| flow_graph_->parsed_function().function().ToCString())); |
| |
| if (FLAG_trace_inlining && |
| (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized)) { |
| OS::Print("Before Inlining of %s\n", flow_graph_-> |
| parsed_function().function().ToFullyQualifiedCString()); |
| FlowGraphPrinter printer(*flow_graph_); |
| printer.PrintBlocks(); |
| } |
| |
| CallSiteInliner inliner(flow_graph_, guarded_fields_); |
| inliner.InlineCalls(); |
| |
| if (inliner.inlined()) { |
| flow_graph_->DiscoverBlocks(); |
| if (FLAG_trace_inlining) { |
| OS::Print("Inlining growth factor: %f\n", inliner.GrowthFactor()); |
| if (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) { |
| OS::Print("After Inlining of %s\n", flow_graph_-> |
| parsed_function().function().ToFullyQualifiedCString()); |
| FlowGraphPrinter printer(*flow_graph_); |
| printer.PrintBlocks(); |
| } |
| } |
| } |
| } |
| |
| } // namespace dart |
