OLD | NEW |
---|---|
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 |
OLD | NEW |