| 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_builder.h" | 5 #include "vm/flow_graph_builder.h" |
| 6 | 6 |
| 7 #include "vm/flags.h" | 7 #include "vm/flags.h" |
| 8 #include "vm/intermediate_language.h" | 8 #include "vm/intermediate_language.h" |
| 9 #include "vm/longjump.h" |
| 9 #include "vm/os.h" | 10 #include "vm/os.h" |
| 10 #include "vm/parser.h" | 11 #include "vm/parser.h" |
| 11 | 12 |
| 12 namespace dart { | 13 namespace dart { |
| 13 | 14 |
| 14 DEFINE_FLAG(bool, trace_bailout, false, "Print bailout from graph builder."); | |
| 15 DEFINE_FLAG(bool, print_flow_graph, false, "Print the IR flow graph."); | 15 DEFINE_FLAG(bool, print_flow_graph, false, "Print the IR flow graph."); |
| 16 DECLARE_FLAG(bool, enable_type_checks); | 16 DECLARE_FLAG(bool, enable_type_checks); |
| 17 | 17 |
| 18 void EffectGraphVisitor::Append(const EffectGraphVisitor& other_fragment) { | 18 void EffectGraphVisitor::Append(const EffectGraphVisitor& other_fragment) { |
| 19 ASSERT(is_open()); | 19 ASSERT(is_open()); |
| 20 if (other_fragment.is_empty()) return; | 20 if (other_fragment.is_empty()) return; |
| 21 if (is_empty()) { | 21 if (is_empty()) { |
| 22 entry_ = other_fragment.entry(); | 22 entry_ = other_fragment.entry(); |
| 23 exit_ = other_fragment.exit(); | 23 exit_ = other_fragment.exit(); |
| 24 } else { | 24 } else { |
| (...skipping 91 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 116 void TestGraphVisitor::BranchOnValue(Value* value) { | 116 void TestGraphVisitor::BranchOnValue(Value* value) { |
| 117 BranchInstr* branch = new BranchInstr(value); | 117 BranchInstr* branch = new BranchInstr(value); |
| 118 AddInstruction(branch); | 118 AddInstruction(branch); |
| 119 CloseFragment(); | 119 CloseFragment(); |
| 120 true_successor_address_ = branch->true_successor_address(); | 120 true_successor_address_ = branch->true_successor_address(); |
| 121 false_successor_address_ = branch->false_successor_address(); | 121 false_successor_address_ = branch->false_successor_address(); |
| 122 } | 122 } |
| 123 | 123 |
| 124 | 124 |
| 125 void EffectGraphVisitor::Bailout(const char* reason) { | 125 void EffectGraphVisitor::Bailout(const char* reason) { |
| 126 if (FLAG_trace_bailout) { | |
| 127 OS::Print("Flow Graph Bailout: %s\n", reason); | |
| 128 } | |
| 129 owner()->Bailout(reason); | 126 owner()->Bailout(reason); |
| 130 } | 127 } |
| 131 | 128 |
| 132 | 129 |
| 133 // 'bailout' is a statement (without a semicolon), typically a return. | 130 // 'bailout' is a statement (without a semicolon), typically a return. |
| 134 #define CHECK_ALIVE(bailout) \ | 131 #define CHECK_ALIVE(bailout) \ |
| 135 do { \ | 132 do { \ |
| 136 if (owner()->HasBailedOut() || !is_open()) { \ | 133 if (!is_open()) { \ |
| 137 bailout; \ | 134 bailout; \ |
| 138 } \ | 135 } \ |
| 139 } while (false) | 136 } while (false) |
| 140 | 137 |
| 141 | 138 |
| 142 // <Statement> ::= Return { value: <Expression> | 139 // <Statement> ::= Return { value: <Expression> |
| 143 // inlined_finally_list: <InlinedFinally>* } | 140 // inlined_finally_list: <InlinedFinally>* } |
| 144 void EffectGraphVisitor::VisitReturnNode(ReturnNode* node) { | 141 void EffectGraphVisitor::VisitReturnNode(ReturnNode* node) { |
| 145 ValueGraphVisitor for_value(owner(), temp_index()); | 142 ValueGraphVisitor for_value(owner(), temp_index()); |
| 146 node->value()->Visit(&for_value); | 143 node->value()->Visit(&for_value); |
| (...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 230 CHECK_ALIVE(return); | 227 CHECK_ALIVE(return); |
| 231 BranchOnValueOf(assert); | 228 BranchOnValueOf(assert); |
| 232 } | 229 } |
| 233 | 230 |
| 234 | 231 |
| 235 // <Expression> :: BinaryOp { kind: Token::Kind | 232 // <Expression> :: BinaryOp { kind: Token::Kind |
| 236 // left: <Expression> | 233 // left: <Expression> |
| 237 // right: <Expression> } | 234 // right: <Expression> } |
| 238 InstanceCallComp* EffectGraphVisitor::TranslateBinaryOp( | 235 InstanceCallComp* EffectGraphVisitor::TranslateBinaryOp( |
| 239 const BinaryOpNode& node) { | 236 const BinaryOpNode& node) { |
| 237 // Operators "&&" and "||" cannot be overloaded therefore do not call |
| 238 // operator. |
| 240 if ((node.kind() == Token::kAND) || (node.kind() == Token::kOR)) { | 239 if ((node.kind() == Token::kAND) || (node.kind() == Token::kOR)) { |
| 241 Bailout("EffectGraphVisitor::VisitBinaryOpNode"); | 240 Bailout("EffectGraphVisitor::VisitBinaryOpNode AND/OR"); |
| 242 return NULL; | |
| 243 } | 241 } |
| 244 ValueGraphVisitor for_left_value(owner(), temp_index()); | 242 ValueGraphVisitor for_left_value(owner(), temp_index()); |
| 245 node.left()->Visit(&for_left_value); | 243 node.left()->Visit(&for_left_value); |
| 246 Append(for_left_value); | 244 Append(for_left_value); |
| 247 CHECK_ALIVE(return NULL); | 245 CHECK_ALIVE(return NULL); |
| 248 ValueGraphVisitor for_right_value(owner(), for_left_value.temp_index()); | 246 ValueGraphVisitor for_right_value(owner(), for_left_value.temp_index()); |
| 249 node.right()->Visit(&for_right_value); | 247 node.right()->Visit(&for_right_value); |
| 250 Append(for_right_value); | 248 Append(for_right_value); |
| 251 CHECK_ALIVE(return NULL); | 249 CHECK_ALIVE(return NULL); |
| 252 ZoneGrowableArray<Value*>* arguments = new ZoneGrowableArray<Value*>(2); | 250 ZoneGrowableArray<Value*>* arguments = new ZoneGrowableArray<Value*>(2); |
| (...skipping 68 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 321 ReturnValueOf(call); | 319 ReturnValueOf(call); |
| 322 } | 320 } |
| 323 | 321 |
| 324 void TestGraphVisitor::VisitComparisonNode(ComparisonNode* node) { | 322 void TestGraphVisitor::VisitComparisonNode(ComparisonNode* node) { |
| 325 InstanceCallComp* call = TranslateComparison(*node); | 323 InstanceCallComp* call = TranslateComparison(*node); |
| 326 CHECK_ALIVE(return); | 324 CHECK_ALIVE(return); |
| 327 BranchOnValueOf(call); | 325 BranchOnValueOf(call); |
| 328 } | 326 } |
| 329 | 327 |
| 330 | 328 |
| 329 |
| 330 InstanceCallComp* EffectGraphVisitor::TranslateUnaryOp( |
| 331 const UnaryOpNode& node) { |
| 332 // "!" cannot be overloaded, therefore do not call operator. |
| 333 if (node.kind() == Token::kNOT) { |
| 334 Bailout("EffectGraphVisitor::VisitUnaryOpNode NOT"); |
| 335 } |
| 336 ValueGraphVisitor for_value(owner(), temp_index()); |
| 337 node.operand()->Visit(&for_value); |
| 338 Append(for_value); |
| 339 ZoneGrowableArray<Value*>* argument = new ZoneGrowableArray<Value*>(1); |
| 340 argument->Add(for_value.value()); |
| 341 return new InstanceCallComp(node.Name(), argument); |
| 342 } |
| 343 |
| 344 |
| 331 void EffectGraphVisitor::VisitUnaryOpNode(UnaryOpNode* node) { | 345 void EffectGraphVisitor::VisitUnaryOpNode(UnaryOpNode* node) { |
| 332 Bailout("EffectGraphVisitor::VisitUnaryOpNode"); | 346 InstanceCallComp* call = TranslateUnaryOp(*node); |
| 347 DoComputation(call); |
| 333 } | 348 } |
| 334 void ValueGraphVisitor::VisitUnaryOpNode(UnaryOpNode* node) { | 349 void ValueGraphVisitor::VisitUnaryOpNode(UnaryOpNode* node) { |
| 335 Bailout("ValueGraphVisitor::VisitUnaryOpNode"); | 350 InstanceCallComp* call = TranslateUnaryOp(*node); |
| 351 ReturnValueOf(call); |
| 336 } | 352 } |
| 337 void TestGraphVisitor::VisitUnaryOpNode(UnaryOpNode* node) { | 353 void TestGraphVisitor::VisitUnaryOpNode(UnaryOpNode* node) { |
| 338 Bailout("TestGraphVisitor::VisitUnaryOpNode"); | 354 InstanceCallComp* call = TranslateUnaryOp(*node); |
| 355 BranchOnValueOf(call); |
| 339 } | 356 } |
| 340 | 357 |
| 341 | 358 |
| 342 void EffectGraphVisitor::VisitIncrOpLocalNode(IncrOpLocalNode* node) { | 359 void EffectGraphVisitor::VisitIncrOpLocalNode(IncrOpLocalNode* node) { |
| 343 Bailout("EffectGraphVisitor::VisitIncrOpLocalNode"); | 360 Bailout("EffectGraphVisitor::VisitIncrOpLocalNode"); |
| 344 } | 361 } |
| 345 void ValueGraphVisitor::VisitIncrOpLocalNode(IncrOpLocalNode* node) { | 362 void ValueGraphVisitor::VisitIncrOpLocalNode(IncrOpLocalNode* node) { |
| 346 Bailout("ValueGraphVisitor::VisitIncrOpLocalNode"); | 363 Bailout("ValueGraphVisitor::VisitIncrOpLocalNode"); |
| 347 } | 364 } |
| 348 void TestGraphVisitor::VisitIncrOpLocalNode(IncrOpLocalNode* node) { | 365 void TestGraphVisitor::VisitIncrOpLocalNode(IncrOpLocalNode* node) { |
| (...skipping 500 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 849 Bailout("EffectGraphVisitor::VisitInlinedFinallyNode"); | 866 Bailout("EffectGraphVisitor::VisitInlinedFinallyNode"); |
| 850 } | 867 } |
| 851 void ValueGraphVisitor::VisitInlinedFinallyNode(InlinedFinallyNode* node) { | 868 void ValueGraphVisitor::VisitInlinedFinallyNode(InlinedFinallyNode* node) { |
| 852 Bailout("ValueGraphVisitor::VisitInlinedFinallyNode"); | 869 Bailout("ValueGraphVisitor::VisitInlinedFinallyNode"); |
| 853 } | 870 } |
| 854 void TestGraphVisitor::VisitInlinedFinallyNode(InlinedFinallyNode* node) { | 871 void TestGraphVisitor::VisitInlinedFinallyNode(InlinedFinallyNode* node) { |
| 855 Bailout("TestGraphVisitor::VisitInlinedFinallyNode"); | 872 Bailout("TestGraphVisitor::VisitInlinedFinallyNode"); |
| 856 } | 873 } |
| 857 | 874 |
| 858 | 875 |
| 859 void FlowGraphBuilder::TraceBailout() const { | |
| 860 if (FLAG_trace_bailout && HasBailedOut()) { | |
| 861 OS::Print("Failed: %s in %s\n", | |
| 862 bailout_reason_, | |
| 863 parsed_function().function().ToFullyQualifiedCString()); | |
| 864 } | |
| 865 } | |
| 866 | |
| 867 | |
| 868 void FlowGraphBuilder::PrintGraph() const { | 876 void FlowGraphBuilder::PrintGraph() const { |
| 869 if (!FLAG_print_flow_graph || HasBailedOut()) return; | |
| 870 | |
| 871 OS::Print("==== %s\n", | 877 OS::Print("==== %s\n", |
| 872 parsed_function().function().ToFullyQualifiedCString()); | 878 parsed_function().function().ToFullyQualifiedCString()); |
| 873 | 879 |
| 874 for (intptr_t i = postorder_block_entries_.length() - 1; i >= 0; --i) { | 880 for (intptr_t i = postorder_block_entries_.length() - 1; i >= 0; --i) { |
| 875 // Print the block entry. | 881 // Print the block entry. |
| 876 Instruction* current = postorder_block_entries_[i]->Print(); | 882 Instruction* current = postorder_block_entries_[i]->Print(); |
| 877 // And all the successors until an exit, branch, or a block entry. | 883 // And all the successors until an exit, branch, or a block entry. |
| 878 while ((current != NULL) && !current->IsBlockEntry()) { | 884 while ((current != NULL) && !current->IsBlockEntry()) { |
| 879 OS::Print("\n"); | 885 OS::Print("\n"); |
| 880 current = current->Print(); | 886 current = current->Print(); |
| 881 } | 887 } |
| 882 if (current != NULL && current->IsBlockEntry()) { | 888 if (current != NULL && current->IsBlockEntry()) { |
| 883 OS::Print(" goto %d", current->GetBlockNumber()); | 889 OS::Print(" goto %d", current->GetBlockNumber()); |
| 884 } | 890 } |
| 885 OS::Print("\n"); | 891 OS::Print("\n"); |
| 886 } | 892 } |
| 887 } | 893 } |
| 888 | 894 |
| 889 | 895 |
| 890 void FlowGraphBuilder::BuildGraph() { | 896 void FlowGraphBuilder::BuildGraph() { |
| 891 EffectGraphVisitor for_effect(this, 0); | 897 EffectGraphVisitor for_effect(this, 0); |
| 892 for_effect.AddInstruction(new TargetEntryInstr()); | 898 for_effect.AddInstruction(new TargetEntryInstr()); |
| 893 parsed_function().node_sequence()->Visit(&for_effect); | 899 parsed_function().node_sequence()->Visit(&for_effect); |
| 894 TraceBailout(); | 900 if (for_effect.entry() != NULL) { |
| 895 if (!HasBailedOut() && (for_effect.entry() != NULL)) { | |
| 896 // Accumulate basic block entries via postorder traversal. | 901 // Accumulate basic block entries via postorder traversal. |
| 897 for_effect.entry()->Postorder(&postorder_block_entries_); | 902 for_effect.entry()->Postorder(&postorder_block_entries_); |
| 898 // Number the blocks in reverse postorder starting with 0. | 903 // Number the blocks in reverse postorder starting with 0. |
| 899 intptr_t last_index = postorder_block_entries_.length() - 1; | 904 intptr_t last_index = postorder_block_entries_.length() - 1; |
| 900 for (intptr_t i = last_index; i >= 0; --i) { | 905 for (intptr_t i = last_index; i >= 0; --i) { |
| 901 postorder_block_entries_[i]->SetBlockNumber(last_index - i); | 906 postorder_block_entries_[i]->SetBlockNumber(last_index - i); |
| 902 } | 907 } |
| 903 } | 908 } |
| 904 PrintGraph(); | 909 if (FLAG_print_flow_graph) { |
| 910 PrintGraph(); |
| 911 } |
| 905 } | 912 } |
| 906 | 913 |
| 914 |
| 915 void FlowGraphBuilder::Bailout(const char* reason) { |
| 916 const char* kFormat = "FlowGraphBuilder Bailout: %s"; |
| 917 intptr_t len = OS::SNPrint(NULL, 0, kFormat, reason) + 1; |
| 918 char* chars = reinterpret_cast<char*>( |
| 919 Isolate::Current()->current_zone()->Allocate(len)); |
| 920 OS::SNPrint(chars, len, kFormat, reason); |
| 921 const Error& error = Error::Handle( |
| 922 LanguageError::New(String::Handle(String::New(chars)))); |
| 923 Isolate::Current()->long_jump_base()->Jump(1, error); |
| 924 } |
| 925 |
| 926 |
| 907 } // namespace dart | 927 } // namespace dart |
| OLD | NEW |