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

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: Zone allocated ParsedFunction 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 | « runtime/vm/compiler.cc ('k') | 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 // TODO(zerny): Remove the following classes once we have moved the label/join
50 // map for control flow out of the AST an into the flow graph builder.
51
52 // Default visitor to traverse child nodes.
53 class ChildrenVisitor : public AstNodeVisitor {
54 public:
55 ChildrenVisitor() { }
56 #define DEFINE_VISIT(type, name) \
57 virtual void Visit##type(type* node) { node->VisitChildren(this); }
58 NODE_LIST(DEFINE_VISIT);
59 #undef DEFINE_VISIT
60 };
61
62 // Visitor to clear each AST node containing source labels.
63 class SourceLabelResetter : public ChildrenVisitor {
64 public:
65 SourceLabelResetter() { }
66 void VisitSequenceNode(SequenceNode* node) { Reset(node, node->label()); }
Kevin Millikin (Google) 2012/10/22 13:56:29 I guess these Visit functions should all be virtua
67 void VisitCaseNode(CaseNode* node) { Reset(node, node->label()); }
68 void VisitSwitchNode(SwitchNode* node) { Reset(node, node->label()); }
69 void VisitWhileNode(WhileNode* node) { Reset(node, node->label()); }
70 void VisitDoWhileNode(DoWhileNode* node) { Reset(node, node->label()); }
71 void VisitForNode(ForNode* node) { Reset(node, node->label()); }
72 void VisitJumpNode(JumpNode* node) { Reset(node, node->label()); }
73 void Reset(AstNode* node, SourceLabel* lbl) {
74 node->VisitChildren(this);
75 if (lbl == NULL) return;
76 lbl->join_for_break_ = NULL;
77 lbl->join_for_continue_ = NULL;
78 }
79 };
49 80
50 // A collection of call sites to consider for inlining. 81 // A collection of call sites to consider for inlining.
51 class CallSites : public FlowGraphVisitor { 82 class CallSites : public FlowGraphVisitor {
52 public: 83 public:
53 explicit CallSites(FlowGraph* flow_graph) 84 explicit CallSites(FlowGraph* flow_graph)
54 : FlowGraphVisitor(flow_graph->postorder()), // We don't use this order. 85 : FlowGraphVisitor(flow_graph->postorder()), // We don't use this order.
55 static_calls_(), 86 static_calls_(),
56 closure_calls_(), 87 closure_calls_(),
57 instance_calls_() { } 88 instance_calls_() { }
58 89
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after
116 class CallSiteInliner : public ValueObject { 147 class CallSiteInliner : public ValueObject {
117 public: 148 public:
118 explicit CallSiteInliner(FlowGraph* flow_graph) 149 explicit CallSiteInliner(FlowGraph* flow_graph)
119 : caller_graph_(flow_graph), 150 : caller_graph_(flow_graph),
120 next_ssa_temp_index_(flow_graph->max_virtual_register_number()), 151 next_ssa_temp_index_(flow_graph->max_virtual_register_number()),
121 inlined_(false), 152 inlined_(false),
122 initial_size_(flow_graph->InstructionCount()), 153 initial_size_(flow_graph->InstructionCount()),
123 inlined_size_(0), 154 inlined_size_(0),
124 inlining_depth_(1), 155 inlining_depth_(1),
125 collected_call_sites_(NULL), 156 collected_call_sites_(NULL),
126 inlining_call_sites_(NULL) { } 157 inlining_call_sites_(NULL),
158 function_cache() { }
127 159
128 void InlineCalls() { 160 void InlineCalls() {
129 // If inlining depth is less then one abort. 161 // If inlining depth is less then one abort.
130 if (FLAG_inlining_depth_threshold < 1) return; 162 if (FLAG_inlining_depth_threshold < 1) return;
131 // Create two call site collections to swap between. 163 // Create two call site collections to swap between.
132 CallSites sites1(caller_graph_); 164 CallSites sites1(caller_graph_);
133 CallSites sites2(caller_graph_); 165 CallSites sites2(caller_graph_);
134 CallSites* call_sites_temp = NULL; 166 CallSites* call_sites_temp = NULL;
135 collected_call_sites_ = &sites1; 167 collected_call_sites_ = &sites1;
136 inlining_call_sites_ = &sites2; 168 inlining_call_sites_ = &sites2;
(...skipping 75 matching lines...) Expand 10 before | Expand all | Expand 10 after
212 isolate->set_ic_data_array(Array::null()); 244 isolate->set_ic_data_array(Array::null());
213 // Save and clear deopt id. 245 // Save and clear deopt id.
214 const intptr_t prev_deopt_id = isolate->deopt_id(); 246 const intptr_t prev_deopt_id = isolate->deopt_id();
215 isolate->set_deopt_id(0); 247 isolate->set_deopt_id(0);
216 // Install bailout jump. 248 // Install bailout jump.
217 LongJump* base = isolate->long_jump_base(); 249 LongJump* base = isolate->long_jump_base();
218 LongJump jump; 250 LongJump jump;
219 isolate->set_long_jump_base(&jump); 251 isolate->set_long_jump_base(&jump);
220 if (setjmp(*jump.Set()) == 0) { 252 if (setjmp(*jump.Set()) == 0) {
221 // Parse the callee function. 253 // Parse the callee function.
222 ParsedFunction parsed_function(function); 254 bool in_cache;
223 Parser::ParseFunction(&parsed_function); 255 ParsedFunction* parsed_function = ParseFunction(function, &in_cache);
224 parsed_function.AllocateVariables();
225 256
226 // Load IC data for the callee. 257 // Load IC data for the callee.
227 if (function.HasCode()) { 258 if (function.HasCode()) {
228 const Code& unoptimized_code = 259 const Code& unoptimized_code =
229 Code::Handle(function.unoptimized_code()); 260 Code::Handle(function.unoptimized_code());
230 isolate->set_ic_data_array(unoptimized_code.ExtractTypeFeedbackArray()); 261 isolate->set_ic_data_array(unoptimized_code.ExtractTypeFeedbackArray());
231 } 262 }
232 263
233 // Build the callee graph. 264 // Build the callee graph.
234 FlowGraphBuilder builder(parsed_function); 265 FlowGraphBuilder builder(*parsed_function);
235 builder.SetInitialBlockId(caller_graph_->max_block_id()); 266 builder.SetInitialBlockId(caller_graph_->max_block_id());
236 FlowGraph* callee_graph = 267 FlowGraph* callee_graph =
237 builder.BuildGraph(FlowGraphBuilder::kValueContext); 268 builder.BuildGraph(FlowGraphBuilder::kValueContext);
238 269
239 // Abort if the callee graph contains control flow. 270 // Abort if the callee graph contains control flow.
240 if (!FLAG_inline_control_flow && 271 if (!FLAG_inline_control_flow &&
241 (callee_graph->preorder().length() != 2)) { 272 (callee_graph->preorder().length() != 2)) {
242 function.set_is_inlinable(false); 273 function.set_is_inlinable(false);
243 isolate->set_long_jump_base(base); 274 isolate->set_long_jump_base(base);
244 isolate->set_ic_data_array(prev_ic_data.raw()); 275 isolate->set_ic_data_array(prev_ic_data.raw());
245 TRACE_INLINING(OS::Print(" Bailout: control flow\n")); 276 TRACE_INLINING(OS::Print(" Bailout: control flow\n"));
246 return false; 277 return false;
247 } 278 }
248 279
249 // Compute SSA on the callee graph, catching bailouts. 280 // Compute SSA on the callee graph, catching bailouts.
250 callee_graph->ComputeSSA(next_ssa_temp_index_); 281 callee_graph->ComputeSSA(next_ssa_temp_index_);
251 callee_graph->ComputeUseLists(); 282 callee_graph->ComputeUseLists();
252 283
253 // TODO(zerny): Do more optimization passes on the callee graph. 284 // TODO(zerny): Do more optimization passes on the callee graph.
254 FlowGraphOptimizer optimizer(callee_graph); 285 FlowGraphOptimizer optimizer(callee_graph);
255 optimizer.ApplyICData(); 286 optimizer.ApplyICData();
256 callee_graph->ComputeUseLists(); 287 callee_graph->ComputeUseLists();
257 288
258 if (FLAG_trace_inlining && FLAG_print_flow_graph) { 289 if (FLAG_trace_inlining && FLAG_print_flow_graph) {
259 OS::Print("Callee graph for inlining %s\n", 290 OS::Print("Callee graph for inlining %s\n",
260 parsed_function.function().ToFullyQualifiedCString()); 291 function.ToFullyQualifiedCString());
261 FlowGraphPrinter printer(*callee_graph); 292 FlowGraphPrinter printer(*callee_graph);
262 printer.PrintBlocks(); 293 printer.PrintBlocks();
263 } 294 }
264 295
265 // If result is more than size threshold then abort. 296 // If result is more than size threshold then abort.
266 // TODO(zerny): Do this after CP and dead code elimination. 297 // TODO(zerny): Do this after CP and dead code elimination.
267 intptr_t size = callee_graph->InstructionCount(); 298 intptr_t size = callee_graph->InstructionCount();
268 if (size > FLAG_inlining_size_threshold) { 299 if (size > FLAG_inlining_size_threshold) {
269 function.set_is_inlinable(false); 300 function.set_is_inlinable(false);
270 isolate->set_long_jump_base(base); 301 isolate->set_long_jump_base(base);
(...skipping 30 matching lines...) Expand all
301 } 332 }
302 } 333 }
303 ASSERT(arg_index == arguments->length()); 334 ASSERT(arg_index == arguments->length());
304 335
305 // Replace callee's null constant with caller's null constant. 336 // Replace callee's null constant with caller's null constant.
306 callee_graph->graph_entry()->constant_null()->ReplaceUsesWith( 337 callee_graph->graph_entry()->constant_null()->ReplaceUsesWith(
307 caller_graph_->graph_entry()->constant_null()); 338 caller_graph_->graph_entry()->constant_null());
308 339
309 TRACE_INLINING(OS::Print(" Success\n")); 340 TRACE_INLINING(OS::Print(" Success\n"));
310 341
342 // Add the function to the cache.
343 if (!in_cache) function_cache.Add(parsed_function);
344
311 // Check that inlining maintains use lists. 345 // Check that inlining maintains use lists.
312 DEBUG_ASSERT(!FLAG_verify_compiler || caller_graph_->ValidateUseLists()); 346 DEBUG_ASSERT(!FLAG_verify_compiler || caller_graph_->ValidateUseLists());
313 347
314 // Build succeeded so we restore the bailout jump. 348 // Build succeeded so we restore the bailout jump.
315 inlined_ = true; 349 inlined_ = true;
316 inlined_size_ += size; 350 inlined_size_ += size;
317 isolate->set_long_jump_base(base); 351 isolate->set_long_jump_base(base);
318 isolate->set_deopt_id(prev_deopt_id); 352 isolate->set_deopt_id(prev_deopt_id);
319 isolate->set_ic_data_array(prev_ic_data.raw()); 353 isolate->set_ic_data_array(prev_ic_data.raw());
320 return true; 354 return true;
321 } else { 355 } else {
322 Error& error = Error::Handle(); 356 Error& error = Error::Handle();
323 error = isolate->object_store()->sticky_error(); 357 error = isolate->object_store()->sticky_error();
324 isolate->object_store()->clear_sticky_error(); 358 isolate->object_store()->clear_sticky_error();
325 isolate->set_long_jump_base(base); 359 isolate->set_long_jump_base(base);
326 isolate->set_deopt_id(prev_deopt_id); 360 isolate->set_deopt_id(prev_deopt_id);
327 isolate->set_ic_data_array(prev_ic_data.raw()); 361 isolate->set_ic_data_array(prev_ic_data.raw());
328 TRACE_INLINING(OS::Print(" Bailout: %s\n", error.ToErrorCString())); 362 TRACE_INLINING(OS::Print(" Bailout: %s\n", error.ToErrorCString()));
329 return false; 363 return false;
330 } 364 }
331 } 365 }
332 366
367 // Parse a function reusing the cache if possible. Returns true if the
368 // function was in the cache.
369 ParsedFunction* ParseFunction(const Function& function, bool* in_cache) {
370 // TODO(zerny): Use a hash map for the cache.
371 for (intptr_t i = 0; i < function_cache.length(); ++i) {
372 ParsedFunction* parsed_function = function_cache[i];
373 if (parsed_function->function().raw() == function.raw()) {
374 *in_cache = true;
375 SourceLabelResetter reset;
376 parsed_function->node_sequence()->Visit(&reset);
377 return parsed_function;
378 }
379 }
380 *in_cache = false;
381 ParsedFunction* parsed_function = new ParsedFunction(function);
382 Parser::ParseFunction(parsed_function);
383 parsed_function->AllocateVariables();
384 return parsed_function;
385 }
386
333 void InlineStaticCalls() { 387 void InlineStaticCalls() {
334 const GrowableArray<StaticCallInstr*>& calls = 388 const GrowableArray<StaticCallInstr*>& calls =
335 *inlining_call_sites_->static_calls(); 389 *inlining_call_sites_->static_calls();
336 TRACE_INLINING(OS::Print(" Static Calls (%d)\n", calls.length())); 390 TRACE_INLINING(OS::Print(" Static Calls (%d)\n", calls.length()));
337 for (intptr_t i = 0; i < calls.length(); ++i) { 391 for (intptr_t i = 0; i < calls.length(); ++i) {
338 StaticCallInstr* call = calls[i]; 392 StaticCallInstr* call = calls[i];
339 GrowableArray<Value*> arguments(call->ArgumentCount()); 393 GrowableArray<Value*> arguments(call->ArgumentCount());
340 for (int i = 0; i < call->ArgumentCount(); ++i) { 394 for (int i = 0; i < call->ArgumentCount(); ++i) {
341 arguments.Add(call->ArgumentAt(i)->value()); 395 arguments.Add(call->ArgumentAt(i)->value());
342 } 396 }
(...skipping 26 matching lines...) Expand all
369 void InlineInstanceCalls() { 423 void InlineInstanceCalls() {
370 const GrowableArray<PolymorphicInstanceCallInstr*>& calls = 424 const GrowableArray<PolymorphicInstanceCallInstr*>& calls =
371 *inlining_call_sites_->instance_calls(); 425 *inlining_call_sites_->instance_calls();
372 TRACE_INLINING(OS::Print(" Polymorphic Instance Calls (%d)\n", 426 TRACE_INLINING(OS::Print(" Polymorphic Instance Calls (%d)\n",
373 calls.length())); 427 calls.length()));
374 for (intptr_t i = 0; i < calls.length(); ++i) { 428 for (intptr_t i = 0; i < calls.length(); ++i) {
375 PolymorphicInstanceCallInstr* instr = calls[i]; 429 PolymorphicInstanceCallInstr* instr = calls[i];
376 const ICData& ic_data = instr->ic_data(); 430 const ICData& ic_data = instr->ic_data();
377 const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0)); 431 const Function& target = Function::ZoneHandle(ic_data.GetTargetAt(0));
378 if (instr->with_checks()) { 432 if (instr->with_checks()) {
379 TRACE_INLINING(OS::Print(" Bailout: %"Pd" checks target '%s'\n", 433 TRACE_INLINING(OS::Print(
380 ic_data.NumberOfChecks(), 434 " => %s (deopt count %d)\n Bailout: %"Pd" checks\n",
381 target.ToCString())); 435 target.ToCString(),
436 target.deoptimization_counter(),
437 ic_data.NumberOfChecks()));
382 continue; 438 continue;
383 } 439 }
384 GrowableArray<Value*> arguments(instr->ArgumentCount()); 440 GrowableArray<Value*> arguments(instr->ArgumentCount());
385 for (int i = 0; i < instr->ArgumentCount(); ++i) { 441 for (int i = 0; i < instr->ArgumentCount(); ++i) {
386 arguments.Add(instr->ArgumentAt(i)->value()); 442 arguments.Add(instr->ArgumentAt(i)->value());
387 } 443 }
388 TryInlining(target, &arguments, instr); 444 TryInlining(target, &arguments, instr);
389 } 445 }
390 } 446 }
391 447
392 FlowGraph* caller_graph_; 448 FlowGraph* caller_graph_;
393 intptr_t next_ssa_temp_index_; 449 intptr_t next_ssa_temp_index_;
394 bool inlined_; 450 bool inlined_;
395 intptr_t initial_size_; 451 intptr_t initial_size_;
396 intptr_t inlined_size_; 452 intptr_t inlined_size_;
397 intptr_t inlining_depth_; 453 intptr_t inlining_depth_;
398 CallSites* collected_call_sites_; 454 CallSites* collected_call_sites_;
399 CallSites* inlining_call_sites_; 455 CallSites* inlining_call_sites_;
456 GrowableArray<ParsedFunction*> function_cache;
400 457
401 DISALLOW_COPY_AND_ASSIGN(CallSiteInliner); 458 DISALLOW_COPY_AND_ASSIGN(CallSiteInliner);
402 }; 459 };
403 460
404 461
405 void FlowGraphInliner::Inline() { 462 void FlowGraphInliner::Inline() {
406 if ((FLAG_inlining_filter != NULL) && 463 if ((FLAG_inlining_filter != NULL) &&
407 (strstr(flow_graph_-> 464 (strstr(flow_graph_->
408 parsed_function().function().ToFullyQualifiedCString(), 465 parsed_function().function().ToFullyQualifiedCString(),
409 FLAG_inlining_filter) == NULL)) { 466 FLAG_inlining_filter) == NULL)) {
(...skipping 21 matching lines...) Expand all
431 OS::Print("After Inlining of %s\n", flow_graph_-> 488 OS::Print("After Inlining of %s\n", flow_graph_->
432 parsed_function().function().ToFullyQualifiedCString()); 489 parsed_function().function().ToFullyQualifiedCString());
433 FlowGraphPrinter printer(*flow_graph_); 490 FlowGraphPrinter printer(*flow_graph_);
434 printer.PrintBlocks(); 491 printer.PrintBlocks();
435 } 492 }
436 } 493 }
437 } 494 }
438 } 495 }
439 496
440 } // namespace dart 497 } // namespace dart
OLDNEW
« no previous file with comments | « runtime/vm/compiler.cc ('k') | runtime/vm/parser.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698