| 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" | |
| 8 #include "vm/flags.h" | 7 #include "vm/flags.h" |
| 9 #include "vm/flow_graph.h" | 8 #include "vm/flow_graph.h" |
| 10 #include "vm/flow_graph_builder.h" | 9 #include "vm/flow_graph_builder.h" |
| 11 #include "vm/flow_graph_optimizer.h" | |
| 12 #include "vm/il_printer.h" | 10 #include "vm/il_printer.h" |
| 13 #include "vm/intrinsifier.h" | |
| 14 #include "vm/longjump.h" | 11 #include "vm/longjump.h" |
| 15 #include "vm/object.h" | 12 #include "vm/object.h" |
| 16 #include "vm/object_store.h" | 13 #include "vm/object_store.h" |
| 17 | 14 |
| 18 namespace dart { | 15 namespace dart { |
| 19 | 16 |
| 20 DEFINE_FLAG(bool, trace_inlining, false, "Trace inlining"); | 17 DEFINE_FLAG(bool, trace_inlining, false, "Trace inlining"); |
| 21 DEFINE_FLAG(charp, inlining_filter, NULL, "Inline only in named function"); | 18 DEFINE_FLAG(charp, inlining_filter, NULL, "Inline only in named function"); |
| 22 DECLARE_FLAG(bool, print_flow_graph); | 19 DECLARE_FLAG(bool, print_flow_graph); |
| 23 DECLARE_FLAG(bool, deoptimization_counter_threshold); | |
| 24 | 20 |
| 25 #define TRACE_INLINING(statement) \ | 21 #define TRACE_INLINING(statement) \ |
| 26 do { \ | 22 do { \ |
| 27 if (FLAG_trace_inlining) statement; \ | 23 if (FLAG_trace_inlining) statement; \ |
| 28 } while (false) | 24 } while (false) |
| 29 | 25 |
| 30 | 26 |
| 31 class CallSiteInliner : public FlowGraphVisitor { | 27 class CallSiteInliner : public FlowGraphVisitor { |
| 32 public: | 28 public: |
| 33 explicit CallSiteInliner(FlowGraph* flow_graph) | 29 explicit CallSiteInliner(FlowGraph* flow_graph) |
| 34 : FlowGraphVisitor(flow_graph->postorder()), | 30 : FlowGraphVisitor(flow_graph->postorder()), |
| 35 caller_graph_(flow_graph), | 31 caller_graph_(flow_graph), |
| 36 next_ssa_temp_index_(flow_graph->max_virtual_register_number()), | 32 next_ssa_temp_index_(flow_graph->max_virtual_register_number()), |
| 37 inlined_(false) { } | 33 inlined_(false) { } |
| 38 | 34 |
| 39 bool TryInlining(const Function& function, | 35 bool TryInlining(const Function& function, |
| 40 GrowableArray<Value*>* arguments, | 36 GrowableArray<Value*>* arguments, |
| 41 Definition* call) { | 37 Definition* call) { |
| 42 TRACE_INLINING(OS::Print(" => %s\n", function.ToCString())); | 38 TRACE_INLINING(OS::Print(" => %s\n", function.ToCString())); |
| 43 | 39 |
| 44 // Abort if the callee has optional parameters. | 40 // Abort if the callee has optional parameters. |
| 45 if (function.HasOptionalParameters()) { | 41 if (function.HasOptionalParameters()) { |
| 46 TRACE_INLINING(OS::Print(" Bailout: optional parameters\n")); | 42 TRACE_INLINING(OS::Print(" Bailout: optional parameters\n")); |
| 47 return false; | 43 return false; |
| 48 } | 44 } |
| 49 | 45 |
| 50 // Assuming no optional parameters the actual/formal count should match. | 46 // Assuming no optional parameters the actual/formal count should match. |
| 51 ASSERT(arguments->length() == function.num_fixed_parameters()); | 47 ASSERT(arguments->length() == function.num_fixed_parameters()); |
| 52 | 48 |
| 53 // Abort if the callee has an intrinsic translation. | |
| 54 if (Intrinsifier::CanIntrinsify(function)) { | |
| 55 TRACE_INLINING(OS::Print(" Bailout: can intrinsify\n")); | |
| 56 return false; | |
| 57 } | |
| 58 | |
| 59 Isolate* isolate = Isolate::Current(); | 49 Isolate* isolate = Isolate::Current(); |
| 60 // Save and clear IC data. | 50 // Save and clear IC data. |
| 61 const Array& prev_ic_data = Array::Handle(isolate->ic_data_array()); | 51 const Array& old_ic_data = Array::Handle(isolate->ic_data_array()); |
| 62 isolate->set_ic_data_array(Array::null()); | 52 isolate->set_ic_data_array(Array::null()); |
| 63 // Save and clear deopt id. | |
| 64 const intptr_t prev_deopt_id = isolate->deopt_id(); | |
| 65 isolate->set_deopt_id(0); | |
| 66 // Install bailout jump. | 53 // Install bailout jump. |
| 67 LongJump* base = isolate->long_jump_base(); | 54 LongJump* base = isolate->long_jump_base(); |
| 68 LongJump jump; | 55 LongJump jump; |
| 69 isolate->set_long_jump_base(&jump); | 56 isolate->set_long_jump_base(&jump); |
| 70 if (setjmp(*jump.Set()) == 0) { | 57 if (setjmp(*jump.Set()) == 0) { |
| 71 // Parse the callee function. | 58 // Parse the callee function. |
| 72 ParsedFunction parsed_function(function); | 59 ParsedFunction parsed_function(function); |
| 73 Parser::ParseFunction(&parsed_function); | 60 Parser::ParseFunction(&parsed_function); |
| 74 parsed_function.AllocateVariables(); | 61 parsed_function.AllocateVariables(); |
| 75 | 62 FlowGraphBuilder builder(parsed_function); |
| 76 // Load IC data for the callee. | |
| 77 if ((function.deoptimization_counter() < | |
| 78 FLAG_deoptimization_counter_threshold) && | |
| 79 function.HasCode()) { | |
| 80 const Code& unoptimized_code = | |
| 81 Code::Handle(function.unoptimized_code()); | |
| 82 isolate->set_ic_data_array(unoptimized_code.ExtractTypeFeedbackArray()); | |
| 83 } | |
| 84 | 63 |
| 85 // Build the callee graph. | 64 // Build the callee graph. |
| 86 FlowGraphBuilder builder(parsed_function); | |
| 87 FlowGraph* callee_graph = | 65 FlowGraph* callee_graph = |
| 88 builder.BuildGraph(FlowGraphBuilder::kValueContext); | 66 builder.BuildGraph(FlowGraphBuilder::kValueContext); |
| 89 | 67 |
| 90 // Abort if the callee graph contains control flow. | 68 // Abort if the callee graph contains control flow. |
| 91 if (callee_graph->preorder().length() != 2) { | 69 if (callee_graph->preorder().length() != 2) { |
| 92 isolate->set_long_jump_base(base); | 70 isolate->set_long_jump_base(base); |
| 93 isolate->set_ic_data_array(prev_ic_data.raw()); | 71 isolate->set_ic_data_array(old_ic_data.raw()); |
| 94 TRACE_INLINING(OS::Print(" Bailout: control flow\n")); | 72 TRACE_INLINING(OS::Print(" Bailout: control flow\n")); |
| 95 return false; | 73 return false; |
| 96 } | 74 } |
| 97 | 75 |
| 98 // Compute SSA on the callee graph, catching bailouts. | |
| 99 callee_graph->ComputeSSA(next_ssa_temp_index_); | |
| 100 callee_graph->ComputeUseLists(); | |
| 101 | |
| 102 // TODO(zerny): Do more optimization passes on the callee graph. | |
| 103 FlowGraphOptimizer optimizer(callee_graph); | |
| 104 optimizer.ApplyICData(); | |
| 105 callee_graph->ComputeUseLists(); | |
| 106 | |
| 107 if (FLAG_trace_inlining && FLAG_print_flow_graph) { | 76 if (FLAG_trace_inlining && FLAG_print_flow_graph) { |
| 108 OS::Print("Callee graph for inlining %s\n", | 77 OS::Print("Callee graph before SSA %s\n", |
| 109 parsed_function.function().ToFullyQualifiedCString()); | 78 parsed_function.function().ToFullyQualifiedCString()); |
| 110 FlowGraphPrinter printer(*callee_graph); | 79 FlowGraphPrinter printer(*callee_graph); |
| 111 printer.PrintBlocks(); | 80 printer.PrintBlocks(); |
| 112 } | 81 } |
| 113 | 82 |
| 83 // Compute SSA on the callee graph. (catching bailouts) |
| 84 callee_graph->ComputeSSA(next_ssa_temp_index_); |
| 85 |
| 86 if (FLAG_trace_inlining && FLAG_print_flow_graph) { |
| 87 OS::Print("Callee graph after SSA %s\n", |
| 88 parsed_function.function().ToFullyQualifiedCString()); |
| 89 FlowGraphPrinter printer(*callee_graph); |
| 90 printer.PrintBlocks(); |
| 91 } |
| 92 |
| 93 callee_graph->ComputeUseLists(); |
| 94 |
| 95 // TODO(zerny): Do optimization passes on the callee graph. |
| 96 |
| 114 // TODO(zerny): If result is more than size threshold then abort. | 97 // TODO(zerny): If result is more than size threshold then abort. |
| 115 | 98 |
| 116 // TODO(zerny): If effort is less than threshold then inline recursively. | 99 // TODO(zerny): If effort is less than threshold then inline recursively. |
| 117 | 100 |
| 118 // Plug result in the caller graph. | 101 // Plug result in the caller graph. |
| 119 caller_graph_->InlineCall(call, callee_graph); | 102 caller_graph_->InlineCall(call, callee_graph); |
| 120 next_ssa_temp_index_ = caller_graph_->max_virtual_register_number(); | 103 next_ssa_temp_index_ = caller_graph_->max_virtual_register_number(); |
| 121 | 104 |
| 122 // Check that inlining maintains use lists. | 105 // Remove (all) push arguments of the call. |
| 123 DEBUG_ASSERT(caller_graph_->ValidateUseLists()); | |
| 124 | |
| 125 // Remove push arguments of the call. | |
| 126 for (intptr_t i = 0; i < call->ArgumentCount(); ++i) { | 106 for (intptr_t i = 0; i < call->ArgumentCount(); ++i) { |
| 127 PushArgumentInstr* push = call->ArgumentAt(i); | 107 PushArgumentInstr* push = call->ArgumentAt(i); |
| 128 push->ReplaceUsesWith(push->value()->definition()); | 108 push->ReplaceUsesWith(push->value()->definition()); |
| 129 push->RemoveFromGraph(); | 109 push->RemoveFromGraph(); |
| 130 } | 110 } |
| 131 | 111 |
| 132 // Replace formal parameters with actuals. | 112 // Replace all the formal parameters with the actuals. |
| 133 for (intptr_t i = 0; i < arguments->length(); ++i) { | 113 for (intptr_t i = 0; i < arguments->length(); ++i) { |
| 134 Value* val = callee_graph->graph_entry()->start_env()->ValueAt(i); | 114 Value* val = callee_graph->graph_entry()->start_env()->ValueAt(i); |
| 135 ParameterInstr* param = val->definition()->AsParameter(); | 115 ParameterInstr* param = val->definition()->AsParameter(); |
| 136 ASSERT(param != NULL); | 116 ASSERT(param != NULL); |
| 137 param->ReplaceUsesWith((*arguments)[i]->definition()); | 117 param->ReplaceUsesWith((*arguments)[i]->definition()); |
| 138 } | 118 } |
| 139 | 119 |
| 140 // Replace callee's null constant with caller's null constant. | 120 // Replace callee's null constant with caller's null constant. |
| 141 callee_graph->graph_entry()->constant_null()->ReplaceUsesWith( | 121 callee_graph->graph_entry()->constant_null()->ReplaceUsesWith( |
| 142 caller_graph_->graph_entry()->constant_null()); | 122 caller_graph_->graph_entry()->constant_null()); |
| 143 | 123 |
| 144 TRACE_INLINING(OS::Print(" Success\n")); | 124 TRACE_INLINING(OS::Print(" Success\n")); |
| 145 | 125 |
| 146 // Build succeeded so we restore the bailout jump. | 126 // Build succeeded so we restore the bailout jump. |
| 147 inlined_ = true; | 127 inlined_ = true; |
| 148 isolate->set_long_jump_base(base); | 128 isolate->set_long_jump_base(base); |
| 149 isolate->set_deopt_id(prev_deopt_id); | 129 isolate->set_ic_data_array(old_ic_data.raw()); |
| 150 isolate->set_ic_data_array(prev_ic_data.raw()); | |
| 151 return true; | 130 return true; |
| 152 } else { | 131 } else { |
| 153 Error& error = Error::Handle(); | 132 Error& error = Error::Handle(); |
| 154 error = isolate->object_store()->sticky_error(); | 133 error = isolate->object_store()->sticky_error(); |
| 155 isolate->object_store()->clear_sticky_error(); | 134 isolate->object_store()->clear_sticky_error(); |
| 156 isolate->set_long_jump_base(base); | 135 isolate->set_long_jump_base(base); |
| 157 isolate->set_deopt_id(prev_deopt_id); | 136 isolate->set_ic_data_array(old_ic_data.raw()); |
| 158 isolate->set_ic_data_array(prev_ic_data.raw()); | |
| 159 TRACE_INLINING(OS::Print(" Bailout: %s\n", error.ToErrorCString())); | 137 TRACE_INLINING(OS::Print(" Bailout: %s\n", error.ToErrorCString())); |
| 160 return false; | 138 return false; |
| 161 } | 139 } |
| 162 } | 140 } |
| 163 | 141 |
| 164 void VisitClosureCall(ClosureCallInstr* call) { | 142 void VisitClosureCall(ClosureCallInstr* call) { |
| 165 TRACE_INLINING(OS::Print(" ClosureCall\n")); | 143 TRACE_INLINING(OS::Print(" ClosureCall\n")); |
| 166 // Find the closure of the callee. | 144 // Find the closure of the callee. |
| 167 ASSERT(call->ArgumentCount() > 0); | 145 ASSERT(call->ArgumentCount() > 0); |
| 168 const CreateClosureInstr* closure = | 146 const CreateClosureInstr* closure = |
| (...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 214 | 192 |
| 215 | 193 |
| 216 void FlowGraphInliner::Inline() { | 194 void FlowGraphInliner::Inline() { |
| 217 if ((FLAG_inlining_filter != NULL) && | 195 if ((FLAG_inlining_filter != NULL) && |
| 218 (strstr(flow_graph_-> | 196 (strstr(flow_graph_-> |
| 219 parsed_function().function().ToFullyQualifiedCString(), | 197 parsed_function().function().ToFullyQualifiedCString(), |
| 220 FLAG_inlining_filter) == NULL)) { | 198 FLAG_inlining_filter) == NULL)) { |
| 221 return; | 199 return; |
| 222 } | 200 } |
| 223 | 201 |
| 224 TRACE_INLINING(OS::Print( | |
| 225 "Inlining calls in %s\n", | |
| 226 flow_graph_->parsed_function().function().ToCString())); | |
| 227 | |
| 228 if (FLAG_trace_inlining && FLAG_print_flow_graph) { | 202 if (FLAG_trace_inlining && FLAG_print_flow_graph) { |
| 229 OS::Print("Before Inlining of %s\n", flow_graph_-> | 203 OS::Print("Before Inlining of %s\n", flow_graph_-> |
| 230 parsed_function().function().ToFullyQualifiedCString()); | 204 parsed_function().function().ToFullyQualifiedCString()); |
| 231 FlowGraphPrinter printer(*flow_graph_); | 205 FlowGraphPrinter printer(*flow_graph_); |
| 232 printer.PrintBlocks(); | 206 printer.PrintBlocks(); |
| 233 } | 207 } |
| 234 | 208 |
| 209 TRACE_INLINING(OS::Print( |
| 210 "Inlining calls in %s\n", |
| 211 flow_graph_->parsed_function().function().ToCString())); |
| 235 CallSiteInliner inliner(flow_graph_); | 212 CallSiteInliner inliner(flow_graph_); |
| 236 inliner.VisitBlocks(); | 213 inliner.VisitBlocks(); |
| 237 | 214 |
| 238 if (inliner.inlined()) { | 215 if (inliner.inlined()) { |
| 239 if (FLAG_trace_inlining && FLAG_print_flow_graph) { | 216 if (FLAG_trace_inlining && FLAG_print_flow_graph) { |
| 240 OS::Print("After Inlining of %s\n", flow_graph_-> | 217 OS::Print("After Inlining of %s\n", flow_graph_-> |
| 241 parsed_function().function().ToFullyQualifiedCString()); | 218 parsed_function().function().ToFullyQualifiedCString()); |
| 242 FlowGraphPrinter printer(*flow_graph_); | 219 FlowGraphPrinter printer(*flow_graph_); |
| 243 printer.PrintBlocks(); | 220 printer.PrintBlocks(); |
| 244 } | 221 } |
| 245 } | 222 } |
| 246 } | 223 } |
| 247 | 224 |
| 248 } // namespace dart | 225 } // namespace dart |
| OLD | NEW |