Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(316)

Side by Side Diff: runtime/vm/flow_graph_inliner.cc

Issue 11228022: Cache parsed functions when inlining. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 8 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « no previous file | runtime/vm/parser.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2 // for details. All rights reserved. Use of this source code is governed by a 2 // for details. All rights reserved. Use of this source code is governed by a
3 // BSD-style license that can be found in the LICENSE file. 3 // BSD-style license that can be found in the LICENSE file.
4 4
5 #include "vm/flow_graph_inliner.h" 5 #include "vm/flow_graph_inliner.h"
6 6
7 #include "vm/compiler.h" 7 #include "vm/compiler.h"
8 #include "vm/flags.h" 8 #include "vm/flags.h"
9 #include "vm/flow_graph.h" 9 #include "vm/flow_graph.h"
10 #include "vm/flow_graph_builder.h" 10 #include "vm/flow_graph_builder.h"
(...skipping 28 matching lines...) Expand all
39 // Test if a call is recursive by looking in the deoptimization environment. 39 // Test if a call is recursive by looking in the deoptimization environment.
40 static bool IsCallRecursive(const Function& function, Definition* call) { 40 static bool IsCallRecursive(const Function& function, Definition* call) {
41 Environment* env = call->env(); 41 Environment* env = call->env();
42 while (env != NULL) { 42 while (env != NULL) {
43 if (function.raw() == env->function().raw()) return true; 43 if (function.raw() == env->function().raw()) return true;
44 env = env->outer(); 44 env = env->outer();
45 } 45 }
46 return false; 46 return false;
47 } 47 }
48 48
49 // Cached function structure to reuse parsed ASTs for multiple inlining sites.
50 class CachedFunction : public ZoneAllocated {
Kevin Millikin (Google) 2012/10/22 10:52:16 This seems unnecessary. Couldn't we just make Par
51 public:
52 explicit CachedFunction(const ParsedFunction& parsed_function)
53 : function_(Function::ZoneHandle(parsed_function.function().raw())),
54 node_sequence_(parsed_function.node_sequence()),
55 instantiator_(parsed_function.instantiator()),
56 default_parameter_values_(Array::ZoneHandle(
57 parsed_function.default_parameter_values().raw())),
58 expression_temp_var_(parsed_function.has_expression_temp_var()
59 ? parsed_function.expression_temp_var()
60 : NULL),
61 first_parameter_index_(parsed_function.first_parameter_index()),
62 first_stack_local_index_(parsed_function.first_stack_local_index()),
63 num_copied_params_(parsed_function.num_copied_params()),
64 num_stack_locals_(parsed_function.num_stack_locals()) { }
65
66 void ParseFunction(ParsedFunction* parsed_function) {
67 ASSERT(parsed_function->function().raw() == function_.raw());
68 parsed_function->SetNodeSequence(node_sequence_);
69 parsed_function->set_instantiator(instantiator_);
70 parsed_function->set_default_parameter_values(default_parameter_values_);
71 if (expression_temp_var_ != NULL) {
72 parsed_function->set_expression_temp_var(expression_temp_var_);
73 }
74 parsed_function->first_parameter_index_ = first_parameter_index_;
75 parsed_function->first_stack_local_index_ = first_stack_local_index_;
76 parsed_function->num_copied_params_ = num_copied_params_;
77 parsed_function->num_stack_locals_ = num_stack_locals_;
78 // Reset all source labels to null.
79 SourceLabelResetter reset;
80 node_sequence_->Visit(&reset);
81 }
82
83 bool Equals(const Function& function) {
84 return function_.raw() == function.raw();
85 }
86
87 private:
88 // TODO(zerny): Remove the following classes once we have moved the label/join
89 // map for control flow out of the AST an into the flow graph builder.
90
91 // Default visitor to traverse child nodes.
92 class ChildrenVisitor : public AstNodeVisitor {
93 public:
94 ChildrenVisitor() { }
95 #define DEFINE_VISIT(type, name) \
96 virtual void Visit##type(type* node) { node->VisitChildren(this); }
97 NODE_LIST(DEFINE_VISIT);
98 #undef DEFINE_VISIT
99 };
100
101 // Visitor to clear each AST node containing source labels.
102 class SourceLabelResetter : public ChildrenVisitor {
103 public:
104 SourceLabelResetter() { }
105 void VisitSequenceNode(SequenceNode* node) { Reset(node, node->label()); }
106 void VisitCaseNode(CaseNode* node) { Reset(node, node->label()); }
107 void VisitSwitchNode(SwitchNode* node) { Reset(node, node->label()); }
108 void VisitWhileNode(WhileNode* node) { Reset(node, node->label()); }
109 void VisitDoWhileNode(DoWhileNode* node) { Reset(node, node->label()); }
110 void VisitForNode(ForNode* node) { Reset(node, node->label()); }
111 void VisitJumpNode(JumpNode* node) { Reset(node, node->label()); }
112 void Reset(AstNode* node, SourceLabel* lbl) {
113 node->VisitChildren(this);
114 if (lbl == NULL) return;
115 lbl->join_for_break_ = NULL;
116 lbl->join_for_continue_ = NULL;
117 }
118 };
119
120 const Function& function_;
121 SequenceNode* node_sequence_;
122 AstNode* instantiator_;
123 Array& default_parameter_values_;
124 LocalVariable* saved_context_var_;
125 LocalVariable* expression_temp_var_;
126 int first_parameter_index_;
127 int first_stack_local_index_;
128 int num_copied_params_;
129 int num_stack_locals_;
130
131 DISALLOW_COPY_AND_ASSIGN(CachedFunction);
132 };
49 133
50 // A collection of call sites to consider for inlining. 134 // A collection of call sites to consider for inlining.
51 class CallSites : public FlowGraphVisitor { 135 class CallSites : public FlowGraphVisitor {
52 public: 136 public:
53 explicit CallSites(FlowGraph* flow_graph) 137 explicit CallSites(FlowGraph* flow_graph)
54 : FlowGraphVisitor(flow_graph->postorder()), // We don't use this order. 138 : FlowGraphVisitor(flow_graph->postorder()), // We don't use this order.
55 static_calls_(), 139 static_calls_(),
56 closure_calls_(), 140 closure_calls_(),
57 instance_calls_() { } 141 instance_calls_() { }
58 142
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after
116 class CallSiteInliner : public ValueObject { 200 class CallSiteInliner : public ValueObject {
117 public: 201 public:
118 explicit CallSiteInliner(FlowGraph* flow_graph) 202 explicit CallSiteInliner(FlowGraph* flow_graph)
119 : caller_graph_(flow_graph), 203 : caller_graph_(flow_graph),
120 next_ssa_temp_index_(flow_graph->max_virtual_register_number()), 204 next_ssa_temp_index_(flow_graph->max_virtual_register_number()),
121 inlined_(false), 205 inlined_(false),
122 initial_size_(flow_graph->InstructionCount()), 206 initial_size_(flow_graph->InstructionCount()),
123 inlined_size_(0), 207 inlined_size_(0),
124 inlining_depth_(1), 208 inlining_depth_(1),
125 collected_call_sites_(NULL), 209 collected_call_sites_(NULL),
126 inlining_call_sites_(NULL) { } 210 inlining_call_sites_(NULL),
211 function_cache() { }
127 212
128 void InlineCalls() { 213 void InlineCalls() {
129 // If inlining depth is less then one abort. 214 // If inlining depth is less then one abort.
130 if (FLAG_inlining_depth_threshold < 1) return; 215 if (FLAG_inlining_depth_threshold < 1) return;
131 // Create two call site collections to swap between. 216 // Create two call site collections to swap between.
132 CallSites sites1(caller_graph_); 217 CallSites sites1(caller_graph_);
133 CallSites sites2(caller_graph_); 218 CallSites sites2(caller_graph_);
134 CallSites* call_sites_temp = NULL; 219 CallSites* call_sites_temp = NULL;
135 collected_call_sites_ = &sites1; 220 collected_call_sites_ = &sites1;
136 inlining_call_sites_ = &sites2; 221 inlining_call_sites_ = &sites2;
(...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after
213 // Save and clear deopt id. 298 // Save and clear deopt id.
214 const intptr_t prev_deopt_id = isolate->deopt_id(); 299 const intptr_t prev_deopt_id = isolate->deopt_id();
215 isolate->set_deopt_id(0); 300 isolate->set_deopt_id(0);
216 // Install bailout jump. 301 // Install bailout jump.
217 LongJump* base = isolate->long_jump_base(); 302 LongJump* base = isolate->long_jump_base();
218 LongJump jump; 303 LongJump jump;
219 isolate->set_long_jump_base(&jump); 304 isolate->set_long_jump_base(&jump);
220 if (setjmp(*jump.Set()) == 0) { 305 if (setjmp(*jump.Set()) == 0) {
221 // Parse the callee function. 306 // Parse the callee function.
222 ParsedFunction parsed_function(function); 307 ParsedFunction parsed_function(function);
223 Parser::ParseFunction(&parsed_function); 308 bool in_cache = ParseFunction(&parsed_function);
224 parsed_function.AllocateVariables();
225 309
226 // Load IC data for the callee. 310 // Load IC data for the callee.
227 if (function.HasCode()) { 311 if (function.HasCode()) {
228 const Code& unoptimized_code = 312 const Code& unoptimized_code =
229 Code::Handle(function.unoptimized_code()); 313 Code::Handle(function.unoptimized_code());
230 isolate->set_ic_data_array(unoptimized_code.ExtractTypeFeedbackArray()); 314 isolate->set_ic_data_array(unoptimized_code.ExtractTypeFeedbackArray());
231 } 315 }
232 316
233 // Build the callee graph. 317 // Build the callee graph.
234 FlowGraphBuilder builder(parsed_function); 318 FlowGraphBuilder builder(parsed_function);
(...skipping 15 matching lines...) Expand all
250 callee_graph->ComputeSSA(next_ssa_temp_index_); 334 callee_graph->ComputeSSA(next_ssa_temp_index_);
251 callee_graph->ComputeUseLists(); 335 callee_graph->ComputeUseLists();
252 336
253 // TODO(zerny): Do more optimization passes on the callee graph. 337 // TODO(zerny): Do more optimization passes on the callee graph.
254 FlowGraphOptimizer optimizer(callee_graph); 338 FlowGraphOptimizer optimizer(callee_graph);
255 optimizer.ApplyICData(); 339 optimizer.ApplyICData();
256 callee_graph->ComputeUseLists(); 340 callee_graph->ComputeUseLists();
257 341
258 if (FLAG_trace_inlining && FLAG_print_flow_graph) { 342 if (FLAG_trace_inlining && FLAG_print_flow_graph) {
259 OS::Print("Callee graph for inlining %s\n", 343 OS::Print("Callee graph for inlining %s\n",
260 parsed_function.function().ToFullyQualifiedCString()); 344 function.ToFullyQualifiedCString());
261 FlowGraphPrinter printer(*callee_graph); 345 FlowGraphPrinter printer(*callee_graph);
262 printer.PrintBlocks(); 346 printer.PrintBlocks();
263 } 347 }
264 348
265 // If result is more than size threshold then abort. 349 // If result is more than size threshold then abort.
266 // TODO(zerny): Do this after CP and dead code elimination. 350 // TODO(zerny): Do this after CP and dead code elimination.
267 intptr_t size = callee_graph->InstructionCount(); 351 intptr_t size = callee_graph->InstructionCount();
268 if (size > FLAG_inlining_size_threshold) { 352 if (size > FLAG_inlining_size_threshold) {
269 function.set_is_inlinable(false); 353 function.set_is_inlinable(false);
270 isolate->set_long_jump_base(base); 354 isolate->set_long_jump_base(base);
(...skipping 30 matching lines...) Expand all
301 } 385 }
302 } 386 }
303 ASSERT(arg_index == arguments->length()); 387 ASSERT(arg_index == arguments->length());
304 388
305 // Replace callee's null constant with caller's null constant. 389 // Replace callee's null constant with caller's null constant.
306 callee_graph->graph_entry()->constant_null()->ReplaceUsesWith( 390 callee_graph->graph_entry()->constant_null()->ReplaceUsesWith(
307 caller_graph_->graph_entry()->constant_null()); 391 caller_graph_->graph_entry()->constant_null());
308 392
309 TRACE_INLINING(OS::Print(" Success\n")); 393 TRACE_INLINING(OS::Print(" Success\n"));
310 394
395 // Add the function to the cache.
396 if (!in_cache) function_cache.Add(new CachedFunction(parsed_function));
397
311 // Check that inlining maintains use lists. 398 // Check that inlining maintains use lists.
312 DEBUG_ASSERT(!FLAG_verify_compiler || caller_graph_->ValidateUseLists()); 399 DEBUG_ASSERT(!FLAG_verify_compiler || caller_graph_->ValidateUseLists());
313 400
314 // Build succeeded so we restore the bailout jump. 401 // Build succeeded so we restore the bailout jump.
315 inlined_ = true; 402 inlined_ = true;
316 inlined_size_ += size; 403 inlined_size_ += size;
317 isolate->set_long_jump_base(base); 404 isolate->set_long_jump_base(base);
318 isolate->set_deopt_id(prev_deopt_id); 405 isolate->set_deopt_id(prev_deopt_id);
319 isolate->set_ic_data_array(prev_ic_data.raw()); 406 isolate->set_ic_data_array(prev_ic_data.raw());
320 return true; 407 return true;
321 } else { 408 } else {
322 Error& error = Error::Handle(); 409 Error& error = Error::Handle();
323 error = isolate->object_store()->sticky_error(); 410 error = isolate->object_store()->sticky_error();
324 isolate->object_store()->clear_sticky_error(); 411 isolate->object_store()->clear_sticky_error();
325 isolate->set_long_jump_base(base); 412 isolate->set_long_jump_base(base);
326 isolate->set_deopt_id(prev_deopt_id); 413 isolate->set_deopt_id(prev_deopt_id);
327 isolate->set_ic_data_array(prev_ic_data.raw()); 414 isolate->set_ic_data_array(prev_ic_data.raw());
328 TRACE_INLINING(OS::Print(" Bailout: %s\n", error.ToErrorCString())); 415 TRACE_INLINING(OS::Print(" Bailout: %s\n", error.ToErrorCString()));
329 return false; 416 return false;
330 } 417 }
331 } 418 }
332 419
420 // Parse a function reusing the cache if possible. Returns true if the
421 // function was in the cache.
422 bool ParseFunction(ParsedFunction* parsed_function) {
423 // TODO(zerny): Use a hash map for the cache.
424 for (intptr_t i = 0; i < function_cache.length(); ++i) {
425 if (function_cache[i]->Equals(parsed_function->function())) {
426 function_cache[i]->ParseFunction(parsed_function);
427 return true;
428 }
429 }
430 Parser::ParseFunction(parsed_function);
431 parsed_function->AllocateVariables();
432 return false;
433 }
434
333 void InlineStaticCalls() { 435 void InlineStaticCalls() {
334 const GrowableArray<StaticCallInstr*>& calls = 436 const GrowableArray<StaticCallInstr*>& calls =
335 *inlining_call_sites_->static_calls(); 437 *inlining_call_sites_->static_calls();
336 TRACE_INLINING(OS::Print(" Static Calls (%d)\n", calls.length())); 438 TRACE_INLINING(OS::Print(" Static Calls (%d)\n", calls.length()));
337 for (intptr_t i = 0; i < calls.length(); ++i) { 439 for (intptr_t i = 0; i < calls.length(); ++i) {
338 StaticCallInstr* call = calls[i]; 440 StaticCallInstr* call = calls[i];
339 GrowableArray<Value*> arguments(call->ArgumentCount()); 441 GrowableArray<Value*> arguments(call->ArgumentCount());
340 for (int i = 0; i < call->ArgumentCount(); ++i) { 442 for (int i = 0; i < call->ArgumentCount(); ++i) {
341 arguments.Add(call->ArgumentAt(i)->value()); 443 arguments.Add(call->ArgumentAt(i)->value());
342 } 444 }
(...skipping 26 matching lines...) Expand all
369 void InlineInstanceCalls() { 471 void InlineInstanceCalls() {
370 const GrowableArray<PolymorphicInstanceCallInstr*>& calls = 472 const GrowableArray<PolymorphicInstanceCallInstr*>& calls =
371 *inlining_call_sites_->instance_calls(); 473 *inlining_call_sites_->instance_calls();
372 TRACE_INLINING(OS::Print(" Polymorphic Instance Calls (%d)\n", 474 TRACE_INLINING(OS::Print(" Polymorphic Instance Calls (%d)\n",
373 calls.length())); 475 calls.length()));
374 for (intptr_t i = 0; i < calls.length(); ++i) { 476 for (intptr_t i = 0; i < calls.length(); ++i) {
375 PolymorphicInstanceCallInstr* instr = calls[i]; 477 PolymorphicInstanceCallInstr* instr = calls[i];
376 const ICData& ic_data = instr->ic_data(); 478 const ICData& ic_data = instr->ic_data();
377 const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0)); 479 const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0));
378 if (instr->with_checks()) { 480 if (instr->with_checks()) {
379 TRACE_INLINING(OS::Print(" Bailout: %"Pd" checks target '%s'\n", 481 TRACE_INLINING(OS::Print(
380 ic_data.NumberOfChecks(), 482 " => %s (deopt count %d)\n Bailout: %"Pd" checks\n",
381 target.ToCString())); 483 target.ToCString(),
484 target.deoptimization_counter(),
485 ic_data.NumberOfChecks()));
382 continue; 486 continue;
383 } 487 }
384 GrowableArray<Value*> arguments(instr->ArgumentCount()); 488 GrowableArray<Value*> arguments(instr->ArgumentCount());
385 for (int i = 0; i < instr->ArgumentCount(); ++i) { 489 for (int i = 0; i < instr->ArgumentCount(); ++i) {
386 arguments.Add(instr->ArgumentAt(i)->value()); 490 arguments.Add(instr->ArgumentAt(i)->value());
387 } 491 }
388 TryInlining(target, &arguments, instr); 492 TryInlining(target, &arguments, instr);
389 } 493 }
390 } 494 }
391 495
392 FlowGraph* caller_graph_; 496 FlowGraph* caller_graph_;
393 intptr_t next_ssa_temp_index_; 497 intptr_t next_ssa_temp_index_;
394 bool inlined_; 498 bool inlined_;
395 intptr_t initial_size_; 499 intptr_t initial_size_;
396 intptr_t inlined_size_; 500 intptr_t inlined_size_;
397 intptr_t inlining_depth_; 501 intptr_t inlining_depth_;
398 CallSites* collected_call_sites_; 502 CallSites* collected_call_sites_;
399 CallSites* inlining_call_sites_; 503 CallSites* inlining_call_sites_;
504 GrowableArray<CachedFunction*> function_cache;
400 505
401 DISALLOW_COPY_AND_ASSIGN(CallSiteInliner); 506 DISALLOW_COPY_AND_ASSIGN(CallSiteInliner);
402 }; 507 };
403 508
404 509
405 void FlowGraphInliner::Inline() { 510 void FlowGraphInliner::Inline() {
406 if ((FLAG_inlining_filter != NULL) && 511 if ((FLAG_inlining_filter != NULL) &&
407 (strstr(flow_graph_-> 512 (strstr(flow_graph_->
408 parsed_function().function().ToFullyQualifiedCString(), 513 parsed_function().function().ToFullyQualifiedCString(),
409 FLAG_inlining_filter) == NULL)) { 514 FLAG_inlining_filter) == NULL)) {
(...skipping 21 matching lines...) Expand all
431 OS::Print("After Inlining of %s\n", flow_graph_-> 536 OS::Print("After Inlining of %s\n", flow_graph_->
432 parsed_function().function().ToFullyQualifiedCString()); 537 parsed_function().function().ToFullyQualifiedCString());
433 FlowGraphPrinter printer(*flow_graph_); 538 FlowGraphPrinter printer(*flow_graph_);
434 printer.PrintBlocks(); 539 printer.PrintBlocks();
435 } 540 }
436 } 541 }
437 } 542 }
438 } 543 }
439 544
440 } // namespace dart 545 } // namespace dart
OLDNEW
« no previous file with comments | « no previous file | runtime/vm/parser.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698