| 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/ast_printer.h" | 7 #include "vm/ast_printer.h" |
| 8 #include "vm/bit_vector.h" | 8 #include "vm/bit_vector.h" |
| 9 #include "vm/code_descriptors.h" | 9 #include "vm/code_descriptors.h" |
| 10 #include "vm/dart_entry.h" | 10 #include "vm/dart_entry.h" |
| (...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 88 } else { | 88 } else { |
| 89 exit()->set_next(do_instr); | 89 exit()->set_next(do_instr); |
| 90 } | 90 } |
| 91 exit_ = do_instr; | 91 exit_ = do_instr; |
| 92 } | 92 } |
| 93 | 93 |
| 94 | 94 |
| 95 void EffectGraphVisitor::AddInstruction(Instruction* instruction) { | 95 void EffectGraphVisitor::AddInstruction(Instruction* instruction) { |
| 96 ASSERT(is_open()); | 96 ASSERT(is_open()); |
| 97 ASSERT(!instruction->IsDefinition()); | 97 ASSERT(!instruction->IsDefinition()); |
| 98 ASSERT(!instruction->IsBlockEntry()); |
| 98 DeallocateTempIndex(instruction->InputCount()); | 99 DeallocateTempIndex(instruction->InputCount()); |
| 99 if (instruction->IsDefinition()) { | |
| 100 instruction->AsDefinition()->set_temp_index(AllocateTempIndex()); | |
| 101 } | |
| 102 if (is_empty()) { | 100 if (is_empty()) { |
| 103 entry_ = exit_ = instruction; | 101 entry_ = exit_ = instruction; |
| 104 } else { | 102 } else { |
| 105 exit()->set_next(instruction); | 103 exit()->set_next(instruction); |
| 106 exit_ = instruction; | 104 exit_ = instruction; |
| 107 } | 105 } |
| 108 } | 106 } |
| 109 | 107 |
| 110 | 108 |
| 111 // Appends a graph fragment to a block entry instruction and returns the exit | 109 void EffectGraphVisitor::Goto(JoinEntryInstr* join) { |
| 112 // of the resulting graph fragment. | 110 ASSERT(is_open()); |
| 111 if (is_empty()) { |
| 112 entry_ = new GotoInstr(join); |
| 113 } else { |
| 114 exit()->Goto(join); |
| 115 } |
| 116 exit_ = NULL; |
| 117 } |
| 118 |
| 119 |
| 120 // Appends a graph fragment to a block entry instruction. Returns the entry |
| 121 // instruction if the fragment was empty or else the exit of the fragment if |
| 122 // it was non-empty (so NULL if the fragment is closed). |
| 123 // |
| 124 // Note that the fragment is no longer a valid fragment after calling this |
| 125 // function -- the fragment is closed at its entry because the entry has a |
| 126 // predecessor in the graph. |
| 113 static Instruction* AppendFragment(BlockEntryInstr* entry, | 127 static Instruction* AppendFragment(BlockEntryInstr* entry, |
| 114 const EffectGraphVisitor& fragment) { | 128 const EffectGraphVisitor& fragment) { |
| 115 if (fragment.is_empty()) return entry; | 129 if (fragment.is_empty()) return entry; |
| 116 entry->set_next(fragment.entry()); | 130 entry->set_next(fragment.entry()); |
| 117 return fragment.exit(); | 131 return fragment.exit(); |
| 118 } | 132 } |
| 119 | 133 |
| 120 | 134 |
| 121 void EffectGraphVisitor::Join(const TestGraphVisitor& test_fragment, | 135 void EffectGraphVisitor::Join(const TestGraphVisitor& test_fragment, |
| 122 const EffectGraphVisitor& true_fragment, | 136 const EffectGraphVisitor& true_fragment, |
| (...skipping 18 matching lines...) Expand all Loading... |
| 141 Instruction* false_exit = AppendFragment(false_entry, false_fragment); | 155 Instruction* false_exit = AppendFragment(false_entry, false_fragment); |
| 142 | 156 |
| 143 // 3. Add a join or select one (or neither) of the arms as exit. | 157 // 3. Add a join or select one (or neither) of the arms as exit. |
| 144 if (true_exit == NULL) { | 158 if (true_exit == NULL) { |
| 145 exit_ = false_exit; // May be NULL. | 159 exit_ = false_exit; // May be NULL. |
| 146 if (false_exit != NULL) temp_index_ = false_fragment.temp_index(); | 160 if (false_exit != NULL) temp_index_ = false_fragment.temp_index(); |
| 147 } else if (false_exit == NULL) { | 161 } else if (false_exit == NULL) { |
| 148 exit_ = true_exit; | 162 exit_ = true_exit; |
| 149 temp_index_ = true_fragment.temp_index(); | 163 temp_index_ = true_fragment.temp_index(); |
| 150 } else { | 164 } else { |
| 151 exit_ = new JoinEntryInstr(); | 165 JoinEntryInstr* join = new JoinEntryInstr(); |
| 152 true_exit->set_next(exit_); | 166 true_exit->Goto(join); |
| 153 false_exit->set_next(exit_); | 167 false_exit->Goto(join); |
| 168 exit_ = join; |
| 154 ASSERT(true_fragment.temp_index() == false_fragment.temp_index()); | 169 ASSERT(true_fragment.temp_index() == false_fragment.temp_index()); |
| 155 temp_index_ = true_fragment.temp_index(); | 170 temp_index_ = true_fragment.temp_index(); |
| 156 } | 171 } |
| 157 } | 172 } |
| 158 | 173 |
| 159 | 174 |
| 160 void EffectGraphVisitor::TieLoop(const TestGraphVisitor& test_fragment, | 175 void EffectGraphVisitor::TieLoop(const TestGraphVisitor& test_fragment, |
| 161 const EffectGraphVisitor& body_fragment) { | 176 const EffectGraphVisitor& body_fragment) { |
| 162 // We have: a test graph fragment with zero, one, or two available exits; | 177 // We have: a test graph fragment with zero, one, or two available exits; |
| 163 // and an effect graph fragment with zero or one available exits. We want | 178 // and an effect graph fragment with zero or one available exits. We want |
| 164 // to append the 'while loop' consisting of the test graph fragment as | 179 // to append the 'while loop' consisting of the test graph fragment as |
| 165 // condition and the effect graph fragment as body. | 180 // condition and the effect graph fragment as body. |
| 166 ASSERT(is_open()); | 181 ASSERT(is_open()); |
| 167 | 182 |
| 168 // 1. Connect the body to the test if it is reachable, and if so record | 183 // 1. Connect the body to the test if it is reachable, and if so record |
| 169 // its exit (if any). | 184 // its exit (if any). |
| 170 TargetEntryInstr* body_entry = new TargetEntryInstr(); | 185 TargetEntryInstr* body_entry = new TargetEntryInstr(); |
| 171 *test_fragment.true_successor_address() = body_entry; | 186 *test_fragment.true_successor_address() = body_entry; |
| 172 Instruction* body_exit = AppendFragment(body_entry, body_fragment); | 187 Instruction* body_exit = AppendFragment(body_entry, body_fragment); |
| 173 | 188 |
| 174 // 2. Connect the test to this graph, including the body if reachable and | 189 // 2. Connect the test to this graph, including the body if reachable and |
| 175 // using a fresh join node if the body is reachable and has an open exit. | 190 // using a fresh join node if the body is reachable and has an open exit. |
| 176 if (body_exit == NULL) { | 191 if (body_exit == NULL) { |
| 177 Append(test_fragment); | 192 Append(test_fragment); |
| 178 } else { | 193 } else { |
| 179 JoinEntryInstr* join = new JoinEntryInstr(); | 194 JoinEntryInstr* join = new JoinEntryInstr(); |
| 180 AddInstruction(join); | |
| 181 join->set_next(test_fragment.entry()); | 195 join->set_next(test_fragment.entry()); |
| 182 body_exit->set_next(join); | 196 Goto(join); |
| 197 body_exit->Goto(join); |
| 183 } | 198 } |
| 184 | 199 |
| 185 // 3. Set the exit to the graph to be the false successor of the test, a | 200 // 3. Set the exit to the graph to be the false successor of the test, a |
| 186 // fresh target node | 201 // fresh target node |
| 187 exit_ = *test_fragment.false_successor_address() = new TargetEntryInstr(); | 202 exit_ = *test_fragment.false_successor_address() = new TargetEntryInstr(); |
| 188 } | 203 } |
| 189 | 204 |
| 190 | 205 |
| 191 Computation* EffectGraphVisitor::BuildStoreLocal( | 206 Computation* EffectGraphVisitor::BuildStoreLocal( |
| 192 const LocalVariable& local, Value* value) { | 207 const LocalVariable& local, Value* value) { |
| (...skipping 720 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 913 if (node->false_branch() != NULL) node->false_branch()->Visit(&for_false); | 928 if (node->false_branch() != NULL) node->false_branch()->Visit(&for_false); |
| 914 Join(for_test, for_true, for_false); | 929 Join(for_test, for_true, for_false); |
| 915 } | 930 } |
| 916 | 931 |
| 917 | 932 |
| 918 void EffectGraphVisitor::VisitSwitchNode(SwitchNode* node) { | 933 void EffectGraphVisitor::VisitSwitchNode(SwitchNode* node) { |
| 919 EffectGraphVisitor switch_body(owner(), temp_index()); | 934 EffectGraphVisitor switch_body(owner(), temp_index()); |
| 920 node->body()->Visit(&switch_body); | 935 node->body()->Visit(&switch_body); |
| 921 Append(switch_body); | 936 Append(switch_body); |
| 922 if ((node->label() != NULL) && (node->label()->join_for_break() != NULL)) { | 937 if ((node->label() != NULL) && (node->label()->join_for_break() != NULL)) { |
| 923 if (is_open()) { | 938 if (is_open()) Goto(node->label()->join_for_break()); |
| 924 AddInstruction(node->label()->join_for_break()); | 939 exit_ = node->label()->join_for_break(); |
| 925 } else { | |
| 926 exit_ = node->label()->join_for_break(); | |
| 927 } | |
| 928 } | 940 } |
| 929 // No continue label allowed. | 941 // No continue label allowed. |
| 930 ASSERT((node->label() == NULL) || | 942 ASSERT((node->label() == NULL) || |
| 931 (node->label()->join_for_continue() == NULL)); | 943 (node->label()->join_for_continue() == NULL)); |
| 932 } | 944 } |
| 933 | 945 |
| 934 | 946 |
| 935 // A case node contains zero or more case expressions, can contain default | 947 // A case node contains zero or more case expressions, can contain default |
| 936 // and a case statement body. | 948 // and a case statement body. |
| 937 // Compose fragment as follows: | 949 // Compose fragment as follows: |
| (...skipping 11 matching lines...) Expand all Loading... |
| 949 // g) case-statements-join | 961 // g) case-statements-join |
| 950 // h) [ case-statements ] -> exit-join | 962 // h) [ case-statements ] -> exit-join |
| 951 // i) exit-target -> exit-join | 963 // i) exit-target -> exit-join |
| 952 // j) exit-join | 964 // j) exit-join |
| 953 // | 965 // |
| 954 // Note: The specification of switch/case is under discussion and may change | 966 // Note: The specification of switch/case is under discussion and may change |
| 955 // drastically. | 967 // drastically. |
| 956 void EffectGraphVisitor::VisitCaseNode(CaseNode* node) { | 968 void EffectGraphVisitor::VisitCaseNode(CaseNode* node) { |
| 957 const intptr_t len = node->case_expressions()->length(); | 969 const intptr_t len = node->case_expressions()->length(); |
| 958 // Create case statements instructions. | 970 // Create case statements instructions. |
| 959 const bool needs_join_at_statement_entry = | |
| 960 (len > 1) || ((len > 0) && (node->contains_default())); | |
| 961 EffectGraphVisitor for_case_statements(owner(), temp_index()); | 971 EffectGraphVisitor for_case_statements(owner(), temp_index()); |
| 962 // Compute start of statements fragment. | 972 // Compute start of statements fragment. |
| 963 BlockEntryInstr* statement_start = NULL; | 973 JoinEntryInstr* statement_start = NULL; |
| 964 if ((node->label() != NULL) && (node->label()->is_continue_target())) { | 974 if ((node->label() != NULL) && node->label()->is_continue_target()) { |
| 965 // Since a labeled jump continue statement occur in a different case node, | 975 // Since a labeled jump continue statement occur in a different case node, |
| 966 // allocate JoinNode here and use it as statement start. | 976 // allocate JoinNode here and use it as statement start. |
| 967 if (node->label()->join_for_continue() == NULL) { | 977 statement_start = node->label()->join_for_continue(); |
| 968 node->label()->set_join_for_continue(new JoinEntryInstr()); | 978 if (statement_start == NULL) { |
| 979 statement_start = new JoinEntryInstr(); |
| 980 node->label()->set_join_for_continue(statement_start); |
| 969 } | 981 } |
| 970 statement_start = node->label()->join_for_continue(); | 982 } else { |
| 971 } else if (needs_join_at_statement_entry) { | |
| 972 statement_start = new JoinEntryInstr(); | 983 statement_start = new JoinEntryInstr(); |
| 973 } else { | |
| 974 statement_start = new TargetEntryInstr(); | |
| 975 } | 984 } |
| 976 for_case_statements.AddInstruction(statement_start); | |
| 977 node->statements()->Visit(&for_case_statements); | 985 node->statements()->Visit(&for_case_statements); |
| 986 Instruction* statement_exit = |
| 987 AppendFragment(statement_start, for_case_statements); |
| 978 if (is_open() && (len == 0)) { | 988 if (is_open() && (len == 0)) { |
| 979 ASSERT(node->contains_default()); | 989 ASSERT(node->contains_default()); |
| 980 // Default only case node. | 990 // Default only case node. |
| 981 Append(for_case_statements); | 991 Goto(statement_start); |
| 992 exit_ = statement_exit; |
| 982 return; | 993 return; |
| 983 } | 994 } |
| 984 | 995 |
| 985 // Generate instructions for all case expressions and collect data to | 996 // Generate instructions for all case expressions. |
| 986 // connect them. | 997 TargetEntryInstr** previous_false_address = NULL; |
| 987 GrowableArray<TargetEntryInstr**> case_true_addresses; | |
| 988 GrowableArray<TargetEntryInstr**> case_false_addresses; | |
| 989 GrowableArray<TargetEntryInstr*> case_entries; | |
| 990 for (intptr_t i = 0; i < len; i++) { | 998 for (intptr_t i = 0; i < len; i++) { |
| 991 AstNode* case_expr = node->case_expressions()->NodeAt(i); | 999 AstNode* case_expr = node->case_expressions()->NodeAt(i); |
| 992 TestGraphVisitor for_case_expression(owner(), | 1000 TestGraphVisitor for_case_expression(owner(), |
| 993 temp_index(), | 1001 temp_index(), |
| 994 case_expr->token_pos()); | 1002 case_expr->token_pos()); |
| 1003 case_expr->Visit(&for_case_expression); |
| 995 if (i == 0) { | 1004 if (i == 0) { |
| 996 case_entries.Add(NULL); // Not to be used | |
| 997 case_expr->Visit(&for_case_expression); | |
| 998 // Append only the first one, everything else is connected from it. | 1005 // Append only the first one, everything else is connected from it. |
| 999 Append(for_case_expression); | 1006 Append(for_case_expression); |
| 1000 } else { | 1007 } else { |
| 1001 TargetEntryInstr* case_entry_target = new TargetEntryInstr(); | 1008 TargetEntryInstr* case_entry_target = new TargetEntryInstr(); |
| 1002 case_entries.Add(case_entry_target); | 1009 AppendFragment(case_entry_target, for_case_expression); |
| 1003 for_case_expression.AddInstruction(case_entry_target); | 1010 *previous_false_address = case_entry_target; |
| 1004 case_expr->Visit(&for_case_expression); | |
| 1005 } | 1011 } |
| 1006 case_true_addresses.Add(for_case_expression.true_successor_address()); | 1012 TargetEntryInstr* true_target = new TargetEntryInstr(); |
| 1007 case_false_addresses.Add(for_case_expression.false_successor_address()); | 1013 *for_case_expression.true_successor_address() = true_target; |
| 1014 true_target->Goto(statement_start); |
| 1015 previous_false_address = for_case_expression.false_successor_address(); |
| 1008 } | 1016 } |
| 1009 | 1017 |
| 1010 // Once a test fragment has been added, this fragment is closed. | 1018 // Once a test fragment has been added, this fragment is closed. |
| 1011 ASSERT(!is_open()); | 1019 ASSERT(!is_open()); |
| 1012 | 1020 |
| 1013 // Connect all test cases except the last one. | 1021 Instruction* exit_instruction = NULL; |
| 1014 for (intptr_t i = 0; i < (len - 1); i++) { | |
| 1015 ASSERT(needs_join_at_statement_entry); | |
| 1016 *case_false_addresses[i] = case_entries[i + 1]; | |
| 1017 TargetEntryInstr* true_target = new TargetEntryInstr(); | |
| 1018 *case_true_addresses[i] = true_target; | |
| 1019 true_target->set_next(statement_start); | |
| 1020 } | |
| 1021 | |
| 1022 BlockEntryInstr* exit_instruction = NULL; | |
| 1023 // Handle last (or only) case: false goes to exit or to statement if this | 1022 // Handle last (or only) case: false goes to exit or to statement if this |
| 1024 // node contains default. | 1023 // node contains default. |
| 1025 if (len > 0) { | 1024 if (len > 0) { |
| 1026 if (statement_start->IsTargetEntry()) { | |
| 1027 *case_true_addresses[len - 1] = statement_start->AsTargetEntry(); | |
| 1028 } else { | |
| 1029 TargetEntryInstr* true_target = new TargetEntryInstr(); | |
| 1030 *case_true_addresses[len - 1] = true_target; | |
| 1031 true_target->set_next(statement_start); | |
| 1032 } | |
| 1033 TargetEntryInstr* false_target = new TargetEntryInstr(); | 1025 TargetEntryInstr* false_target = new TargetEntryInstr(); |
| 1034 *case_false_addresses[len - 1] = false_target; | 1026 *previous_false_address = false_target; |
| 1035 if (node->contains_default()) { | 1027 if (node->contains_default()) { |
| 1036 // True and false go to statement start. | 1028 // True and false go to statement start. |
| 1037 false_target->set_next(statement_start); | 1029 false_target->Goto(statement_start); |
| 1038 if (for_case_statements.is_open()) { | 1030 exit_instruction = statement_exit; |
| 1039 exit_instruction = new TargetEntryInstr(); | 1031 } else { |
| 1040 for_case_statements.exit()->set_next(exit_instruction); | 1032 if (statement_exit != NULL) { |
| 1033 JoinEntryInstr* join = new JoinEntryInstr(); |
| 1034 statement_exit->Goto(join); |
| 1035 false_target->Goto(join); |
| 1036 exit_instruction = join; |
| 1037 } else { |
| 1038 exit_instruction = false_target; |
| 1041 } | 1039 } |
| 1042 } else { | |
| 1043 if (for_case_statements.is_open()) { | |
| 1044 exit_instruction = new JoinEntryInstr(); | |
| 1045 for_case_statements.exit()->set_next(exit_instruction); | |
| 1046 } else { | |
| 1047 exit_instruction = new TargetEntryInstr(); | |
| 1048 } | |
| 1049 false_target->set_next(exit_instruction); | |
| 1050 } | 1040 } |
| 1051 } else { | 1041 } else { |
| 1052 // A CaseNode without case expressions must contain default. | 1042 // A CaseNode without case expressions must contain default. |
| 1053 ASSERT(node->contains_default()); | 1043 ASSERT(node->contains_default()); |
| 1054 AddInstruction(statement_start); | 1044 Goto(statement_start); |
| 1045 exit_instruction = statement_exit; |
| 1055 } | 1046 } |
| 1056 | 1047 |
| 1057 ASSERT(!is_open()); | 1048 ASSERT(!is_open()); |
| 1058 exit_ = exit_instruction; | 1049 exit_ = exit_instruction; |
| 1059 } | 1050 } |
| 1060 | 1051 |
| 1061 | 1052 |
| 1062 // <Statement> ::= While { label: SourceLabel | 1053 // <Statement> ::= While { label: SourceLabel |
| 1063 // condition: <Expression> | 1054 // condition: <Expression> |
| 1064 // body: <Sequence> } | 1055 // body: <Sequence> } |
| (...skipping 13 matching lines...) Expand all Loading... |
| 1078 ASSERT(!for_test.is_empty()); // Language spec. | 1069 ASSERT(!for_test.is_empty()); // Language spec. |
| 1079 | 1070 |
| 1080 EffectGraphVisitor for_body(owner(), temp_index()); | 1071 EffectGraphVisitor for_body(owner(), temp_index()); |
| 1081 for_body.Do( | 1072 for_body.Do( |
| 1082 new CheckStackOverflowComp(node->token_pos(), owner()->try_index())); | 1073 new CheckStackOverflowComp(node->token_pos(), owner()->try_index())); |
| 1083 node->body()->Visit(&for_body); | 1074 node->body()->Visit(&for_body); |
| 1084 | 1075 |
| 1085 // Labels are set after body traversal. | 1076 // Labels are set after body traversal. |
| 1086 SourceLabel* lbl = node->label(); | 1077 SourceLabel* lbl = node->label(); |
| 1087 ASSERT(lbl != NULL); | 1078 ASSERT(lbl != NULL); |
| 1088 if (lbl->join_for_continue() != NULL) { | 1079 JoinEntryInstr* join = lbl->join_for_continue(); |
| 1089 AddInstruction(lbl->join_for_continue()); | 1080 if (join != NULL) { |
| 1081 Goto(join); |
| 1082 exit_ = join; |
| 1090 } | 1083 } |
| 1091 TieLoop(for_test, for_body); | 1084 TieLoop(for_test, for_body); |
| 1092 if (lbl->join_for_break() != NULL) { | 1085 join = lbl->join_for_break(); |
| 1093 AddInstruction(lbl->join_for_break()); | 1086 if (join != NULL) { |
| 1087 Goto(join); |
| 1088 exit_ = join; |
| 1094 } | 1089 } |
| 1095 } | 1090 } |
| 1096 | 1091 |
| 1097 | 1092 |
| 1098 // The fragment is composed as follows: | 1093 // The fragment is composed as follows: |
| 1099 // a) body-entry-join | 1094 // a) body-entry-join |
| 1100 // b) [ body ] | 1095 // b) [ body ] |
| 1101 // c) test-entry (continue-join or body-exit-target) | 1096 // c) test-entry (continue-join or body-exit-target) |
| 1102 // d) [ test-entry ] -> (back-target, loop-exit-target) | 1097 // d) [ test-entry ] -> (back-target, loop-exit-target) |
| 1103 // e) back-target -> (body-entry-join) | 1098 // e) back-target -> (body-entry-join) |
| 1104 // f) loop-exit-target | 1099 // f) loop-exit-target |
| 1105 // g) break-join | 1100 // g) break-join |
| 1106 void EffectGraphVisitor::VisitDoWhileNode(DoWhileNode* node) { | 1101 void EffectGraphVisitor::VisitDoWhileNode(DoWhileNode* node) { |
| 1107 // Traverse body first in order to generate continue and break labels. | 1102 // Traverse body first in order to generate continue and break labels. |
| 1108 EffectGraphVisitor for_body(owner(), temp_index()); | 1103 EffectGraphVisitor for_body(owner(), temp_index()); |
| 1109 for_body.Do( | 1104 for_body.Do( |
| 1110 new CheckStackOverflowComp(node->token_pos(), owner()->try_index())); | 1105 new CheckStackOverflowComp(node->token_pos(), owner()->try_index())); |
| 1111 node->body()->Visit(&for_body); | 1106 node->body()->Visit(&for_body); |
| 1112 | 1107 |
| 1113 TestGraphVisitor for_test(owner(), | 1108 TestGraphVisitor for_test(owner(), |
| 1114 temp_index(), | 1109 temp_index(), |
| 1115 node->condition()->token_pos()); | 1110 node->condition()->token_pos()); |
| 1116 node->condition()->Visit(&for_test); | 1111 node->condition()->Visit(&for_test); |
| 1117 ASSERT(is_open()); | 1112 ASSERT(is_open()); |
| 1118 | 1113 |
| 1119 // Tie do-while loop (test is after the body). | 1114 // Tie do-while loop (test is after the body). |
| 1120 JoinEntryInstr* body_entry_join = new JoinEntryInstr(); | 1115 JoinEntryInstr* body_entry_join = new JoinEntryInstr(); |
| 1121 AddInstruction(body_entry_join); | 1116 Goto(body_entry_join); |
| 1122 Instruction* body_exit = AppendFragment(body_entry_join, for_body); | 1117 Instruction* body_exit = AppendFragment(body_entry_join, for_body); |
| 1123 | 1118 |
| 1124 if (for_body.is_open() || (node->label()->join_for_continue() != NULL)) { | 1119 JoinEntryInstr* join = node->label()->join_for_continue(); |
| 1125 BlockEntryInstr* test_entry = NULL; | 1120 if ((body_exit != NULL) || (join != NULL)) { |
| 1126 if (node->label()->join_for_continue() == NULL) { | 1121 if (join == NULL) join = new JoinEntryInstr(); |
| 1127 test_entry = new TargetEntryInstr(); | 1122 join->set_next(for_test.entry()); |
| 1128 } else { | |
| 1129 test_entry = node->label()->join_for_continue(); | |
| 1130 } | |
| 1131 test_entry->set_next(for_test.entry()); | |
| 1132 if (body_exit != NULL) { | 1123 if (body_exit != NULL) { |
| 1133 body_exit->set_next(test_entry); | 1124 body_exit->Goto(join); |
| 1134 } | 1125 } |
| 1135 } | 1126 } |
| 1136 | 1127 |
| 1137 TargetEntryInstr* back_target_entry = new TargetEntryInstr(); | 1128 TargetEntryInstr* back_target_entry = new TargetEntryInstr(); |
| 1138 *for_test.true_successor_address() = back_target_entry; | 1129 *for_test.true_successor_address() = back_target_entry; |
| 1139 back_target_entry->set_next(body_entry_join); | 1130 back_target_entry->Goto(body_entry_join); |
| 1140 TargetEntryInstr* loop_exit_target = new TargetEntryInstr(); | 1131 TargetEntryInstr* loop_exit_target = new TargetEntryInstr(); |
| 1141 *for_test.false_successor_address() = loop_exit_target; | 1132 *for_test.false_successor_address() = loop_exit_target; |
| 1142 if (node->label()->join_for_break() == NULL) { | 1133 if (node->label()->join_for_break() == NULL) { |
| 1143 exit_ = loop_exit_target; | 1134 exit_ = loop_exit_target; |
| 1144 } else { | 1135 } else { |
| 1145 loop_exit_target->set_next(node->label()->join_for_break()); | 1136 loop_exit_target->Goto(node->label()->join_for_break()); |
| 1146 exit_ = node->label()->join_for_break(); | 1137 exit_ = node->label()->join_for_break(); |
| 1147 } | 1138 } |
| 1148 } | 1139 } |
| 1149 | 1140 |
| 1150 | 1141 |
| 1151 // A ForNode can contain break and continue jumps. 'break' joins to | 1142 // A ForNode can contain break and continue jumps. 'break' joins to |
| 1152 // ForNode exit, 'continue' joins at increment entry. The fragment is composed | 1143 // ForNode exit, 'continue' joins at increment entry. The fragment is composed |
| 1153 // as follows: | 1144 // as follows: |
| 1154 // a) [ initializer ] | 1145 // a) [ initializer ] |
| 1155 // b) loop-join | 1146 // b) loop-join |
| 1156 // c) [ test ] -> (body-entry-target, loop-exit-target) | 1147 // c) [ test ] -> (body-entry-target, loop-exit-target) |
| 1157 // d) body-entry-target | 1148 // d) body-entry-target |
| 1158 // e) [ body ] | 1149 // e) [ body ] |
| 1159 // f) continue-join (optional) | 1150 // f) continue-join (optional) |
| 1160 // g) [ increment ] -> (loop-join) | 1151 // g) [ increment ] -> (loop-join) |
| 1161 // h) loop-exit-target | 1152 // h) loop-exit-target |
| 1162 // i) break-join | 1153 // i) break-join |
| 1163 void EffectGraphVisitor::VisitForNode(ForNode* node) { | 1154 void EffectGraphVisitor::VisitForNode(ForNode* node) { |
| 1164 EffectGraphVisitor for_initializer(owner(), temp_index()); | 1155 EffectGraphVisitor for_initializer(owner(), temp_index()); |
| 1165 node->initializer()->Visit(&for_initializer); | 1156 node->initializer()->Visit(&for_initializer); |
| 1166 Append(for_initializer); | 1157 Append(for_initializer); |
| 1167 ASSERT(is_open()); | 1158 ASSERT(is_open()); |
| 1168 | 1159 |
| 1169 // Compose body to set any jump labels. | 1160 // Compose body to set any jump labels. |
| 1170 EffectGraphVisitor for_body(owner(), temp_index()); | 1161 EffectGraphVisitor for_body(owner(), temp_index()); |
| 1171 TargetEntryInstr* body_entry = new TargetEntryInstr(); | |
| 1172 for_body.AddInstruction(body_entry); | |
| 1173 for_body.Do( | 1162 for_body.Do( |
| 1174 new CheckStackOverflowComp(node->token_pos(), owner()->try_index())); | 1163 new CheckStackOverflowComp(node->token_pos(), owner()->try_index())); |
| 1175 node->body()->Visit(&for_body); | 1164 node->body()->Visit(&for_body); |
| 1176 | 1165 |
| 1177 // Join loop body, increment and compute their end instruction. | 1166 // Join loop body, increment and compute their end instruction. |
| 1178 ASSERT(!for_body.is_empty()); | 1167 ASSERT(!for_body.is_empty()); |
| 1179 Instruction* loop_increment_end = NULL; | 1168 Instruction* loop_increment_end = NULL; |
| 1180 EffectGraphVisitor for_increment(owner(), temp_index()); | 1169 EffectGraphVisitor for_increment(owner(), temp_index()); |
| 1181 if ((node->label()->join_for_continue() == NULL) && for_body.is_open()) { | 1170 node->increment()->Visit(&for_increment); |
| 1171 JoinEntryInstr* join = node->label()->join_for_continue(); |
| 1172 if (join != NULL) { |
| 1173 // Insert the join between the body and increment. |
| 1174 if (for_body.is_open()) for_body.Goto(join); |
| 1175 loop_increment_end = AppendFragment(join, for_increment); |
| 1176 ASSERT(loop_increment_end != NULL); |
| 1177 } else if (for_body.is_open()) { |
| 1182 // Do not insert an extra basic block. | 1178 // Do not insert an extra basic block. |
| 1183 node->increment()->Visit(&for_increment); | |
| 1184 for_body.Append(for_increment); | 1179 for_body.Append(for_increment); |
| 1185 loop_increment_end = for_body.exit(); | 1180 loop_increment_end = for_body.exit(); |
| 1186 // 'for_body' contains at least the TargetInstruction 'body_entry'. | 1181 // 'for_body' contains at least the stack check. |
| 1187 ASSERT(loop_increment_end != NULL); | |
| 1188 } else if (node->label()->join_for_continue() != NULL) { | |
| 1189 // Insert join between body and increment. | |
| 1190 if (for_body.is_open()) { | |
| 1191 for_body.exit()->set_next(node->label()->join_for_continue()); | |
| 1192 } | |
| 1193 for_increment.AddInstruction(node->label()->join_for_continue()); | |
| 1194 node->increment()->Visit(&for_increment); | |
| 1195 loop_increment_end = for_increment.exit(); | |
| 1196 ASSERT(loop_increment_end != NULL); | 1182 ASSERT(loop_increment_end != NULL); |
| 1197 } else { | 1183 } else { |
| 1198 loop_increment_end = NULL; | 1184 loop_increment_end = NULL; |
| 1199 ASSERT(!for_body.is_open() && node->label()->join_for_continue() == NULL); | |
| 1200 } | 1185 } |
| 1201 | 1186 |
| 1202 // 'loop_increment_end' is NULL only if there is no join for continue and the | 1187 // 'loop_increment_end' is NULL only if there is no join for continue and the |
| 1203 // body is not open, i.e., no backward branch exists. | 1188 // body is not open, i.e., no backward branch exists. |
| 1204 if (loop_increment_end != NULL) { | 1189 if (loop_increment_end != NULL) { |
| 1205 JoinEntryInstr* loop_start = new JoinEntryInstr(); | 1190 JoinEntryInstr* loop_start = new JoinEntryInstr(); |
| 1206 AddInstruction(loop_start); | 1191 Goto(loop_start); |
| 1207 loop_increment_end->set_next(loop_start); | 1192 loop_increment_end->Goto(loop_start); |
| 1193 exit_ = loop_start; |
| 1208 } | 1194 } |
| 1209 | 1195 |
| 1210 if (node->condition() == NULL) { | 1196 if (node->condition() == NULL) { |
| 1211 // Endless loop, no test. | 1197 // Endless loop, no test. |
| 1212 Append(for_body); | 1198 JoinEntryInstr* body_entry = new JoinEntryInstr(); |
| 1213 if (node->label()->join_for_break() == NULL) { | 1199 AppendFragment(body_entry, for_body); |
| 1214 CloseFragment(); | 1200 Goto(body_entry); |
| 1215 } else { | 1201 if (node->label()->join_for_break() != NULL) { |
| 1216 // Control flow of ForLoop continues into join_for_break. | 1202 // Control flow of ForLoop continues into join_for_break. |
| 1217 exit_ = node->label()->join_for_break(); | 1203 exit_ = node->label()->join_for_break(); |
| 1218 } | 1204 } |
| 1219 } else { | 1205 } else { |
| 1220 TargetEntryInstr* loop_exit = new TargetEntryInstr(); | 1206 TargetEntryInstr* loop_exit = new TargetEntryInstr(); |
| 1221 TestGraphVisitor for_test(owner(), | 1207 TestGraphVisitor for_test(owner(), |
| 1222 temp_index(), | 1208 temp_index(), |
| 1223 node->condition()->token_pos()); | 1209 node->condition()->token_pos()); |
| 1224 node->condition()->Visit(&for_test); | 1210 node->condition()->Visit(&for_test); |
| 1225 Append(for_test); | 1211 Append(for_test); |
| 1212 TargetEntryInstr* body_entry = new TargetEntryInstr(); |
| 1213 AppendFragment(body_entry, for_body); |
| 1226 *for_test.true_successor_address() = body_entry; | 1214 *for_test.true_successor_address() = body_entry; |
| 1227 *for_test.false_successor_address() = loop_exit; | 1215 *for_test.false_successor_address() = loop_exit; |
| 1228 if (node->label()->join_for_break() == NULL) { | 1216 if (node->label()->join_for_break() == NULL) { |
| 1229 exit_ = loop_exit; | 1217 exit_ = loop_exit; |
| 1230 } else { | 1218 } else { |
| 1231 loop_exit->set_next(node->label()->join_for_break()); | 1219 loop_exit->Goto(node->label()->join_for_break()); |
| 1232 exit_ = node->label()->join_for_break(); | 1220 exit_ = node->label()->join_for_break(); |
| 1233 } | 1221 } |
| 1234 } | 1222 } |
| 1235 } | 1223 } |
| 1236 | 1224 |
| 1237 | 1225 |
| 1238 void EffectGraphVisitor::VisitJumpNode(JumpNode* node) { | 1226 void EffectGraphVisitor::VisitJumpNode(JumpNode* node) { |
| 1239 for (intptr_t i = 0; i < node->inlined_finally_list_length(); i++) { | 1227 for (intptr_t i = 0; i < node->inlined_finally_list_length(); i++) { |
| 1240 EffectGraphVisitor for_effect(owner(), temp_index()); | 1228 EffectGraphVisitor for_effect(owner(), temp_index()); |
| 1241 node->InlinedFinallyNodeAt(i)->Visit(&for_effect); | 1229 node->InlinedFinallyNodeAt(i)->Visit(&for_effect); |
| (...skipping 22 matching lines...) Expand all Loading... |
| 1264 target_context_level = target_scope->context_level(); | 1252 target_context_level = target_scope->context_level(); |
| 1265 } | 1253 } |
| 1266 } | 1254 } |
| 1267 ASSERT(target_context_level >= 0); | 1255 ASSERT(target_context_level >= 0); |
| 1268 intptr_t current_context_level = owner()->context_level(); | 1256 intptr_t current_context_level = owner()->context_level(); |
| 1269 ASSERT(current_context_level >= target_context_level); | 1257 ASSERT(current_context_level >= target_context_level); |
| 1270 while (current_context_level-- > target_context_level) { | 1258 while (current_context_level-- > target_context_level) { |
| 1271 UnchainContext(); | 1259 UnchainContext(); |
| 1272 } | 1260 } |
| 1273 | 1261 |
| 1274 Instruction* jump_target = NULL; | 1262 JoinEntryInstr* jump_target = NULL; |
| 1275 if (node->kind() == Token::kBREAK) { | 1263 if (node->kind() == Token::kBREAK) { |
| 1276 if (node->label()->join_for_break() == NULL) { | 1264 if (node->label()->join_for_break() == NULL) { |
| 1277 node->label()->set_join_for_break(new JoinEntryInstr()); | 1265 node->label()->set_join_for_break(new JoinEntryInstr()); |
| 1278 } | 1266 } |
| 1279 jump_target = node->label()->join_for_break(); | 1267 jump_target = node->label()->join_for_break(); |
| 1280 } else { | 1268 } else { |
| 1281 if (node->label()->join_for_continue() == NULL) { | 1269 if (node->label()->join_for_continue() == NULL) { |
| 1282 node->label()->set_join_for_continue(new JoinEntryInstr()); | 1270 node->label()->set_join_for_continue(new JoinEntryInstr()); |
| 1283 } | 1271 } |
| 1284 jump_target = node->label()->join_for_continue(); | 1272 jump_target = node->label()->join_for_continue(); |
| 1285 } | 1273 } |
| 1286 AddInstruction(jump_target); | 1274 Goto(jump_target); |
| 1287 CloseFragment(); | |
| 1288 } | 1275 } |
| 1289 | 1276 |
| 1290 | 1277 |
| 1291 void EffectGraphVisitor::VisitArgumentListNode(ArgumentListNode* node) { | 1278 void EffectGraphVisitor::VisitArgumentListNode(ArgumentListNode* node) { |
| 1292 UNREACHABLE(); | 1279 UNREACHABLE(); |
| 1293 } | 1280 } |
| 1294 | 1281 |
| 1295 | 1282 |
| 1296 void EffectGraphVisitor::VisitArrayNode(ArrayNode* node) { | 1283 void EffectGraphVisitor::VisitArrayNode(ArrayNode* node) { |
| 1297 // Translate the array elements and collect their values. | 1284 // Translate the array elements and collect their values. |
| (...skipping 802 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2100 } | 2087 } |
| 2101 } | 2088 } |
| 2102 | 2089 |
| 2103 // No continue on sequence allowed. | 2090 // No continue on sequence allowed. |
| 2104 ASSERT((node->label() == NULL) || | 2091 ASSERT((node->label() == NULL) || |
| 2105 (node->label()->join_for_continue() == NULL)); | 2092 (node->label()->join_for_continue() == NULL)); |
| 2106 // If this node sequence is labeled, a break out of the sequence will have | 2093 // If this node sequence is labeled, a break out of the sequence will have |
| 2107 // taken care of unchaining the context. | 2094 // taken care of unchaining the context. |
| 2108 if ((node->label() != NULL) && | 2095 if ((node->label() != NULL) && |
| 2109 (node->label()->join_for_break() != NULL)) { | 2096 (node->label()->join_for_break() != NULL)) { |
| 2110 if (is_open()) { | 2097 if (is_open()) Goto(node->label()->join_for_break()); |
| 2111 AddInstruction(node->label()->join_for_break()); | 2098 exit_ = node->label()->join_for_break(); |
| 2112 } else { | |
| 2113 exit_ = node->label()->join_for_break(); | |
| 2114 } | |
| 2115 } | 2099 } |
| 2116 | 2100 |
| 2117 // The outermost function sequence cannot contain a label. | 2101 // The outermost function sequence cannot contain a label. |
| 2118 ASSERT((node->label() == NULL) || | 2102 ASSERT((node->label() == NULL) || |
| 2119 (node != owner()->parsed_function().node_sequence())); | 2103 (node != owner()->parsed_function().node_sequence())); |
| 2120 owner()->set_context_level(previous_context_level); | 2104 owner()->set_context_level(previous_context_level); |
| 2121 } | 2105 } |
| 2122 | 2106 |
| 2123 | 2107 |
| 2124 void EffectGraphVisitor::VisitCatchClauseNode(CatchClauseNode* node) { | 2108 void EffectGraphVisitor::VisitCatchClauseNode(CatchClauseNode* node) { |
| (...skipping 24 matching lines...) Expand all Loading... |
| 2149 // We are done generating code for the try block. | 2133 // We are done generating code for the try block. |
| 2150 owner()->set_try_index(old_try_index); | 2134 owner()->set_try_index(old_try_index); |
| 2151 | 2135 |
| 2152 CatchClauseNode* catch_block = node->catch_block(); | 2136 CatchClauseNode* catch_block = node->catch_block(); |
| 2153 if (catch_block != NULL) { | 2137 if (catch_block != NULL) { |
| 2154 // Set the corresponding try index for this catch block so | 2138 // Set the corresponding try index for this catch block so |
| 2155 // that we can set the appropriate handler pc when we generate | 2139 // that we can set the appropriate handler pc when we generate |
| 2156 // code for this catch block. | 2140 // code for this catch block. |
| 2157 catch_block->set_try_index(try_index); | 2141 catch_block->set_try_index(try_index); |
| 2158 EffectGraphVisitor for_catch_block(owner(), temp_index()); | 2142 EffectGraphVisitor for_catch_block(owner(), temp_index()); |
| 2143 catch_block->Visit(&for_catch_block); |
| 2159 TargetEntryInstr* catch_entry = new TargetEntryInstr(try_index); | 2144 TargetEntryInstr* catch_entry = new TargetEntryInstr(try_index); |
| 2160 for_catch_block.AddInstruction(catch_entry); | |
| 2161 catch_block->Visit(&for_catch_block); | |
| 2162 owner()->AddCatchEntry(catch_entry); | 2145 owner()->AddCatchEntry(catch_entry); |
| 2163 ASSERT(!for_catch_block.is_open()); | 2146 ASSERT(!for_catch_block.is_open()); |
| 2164 if ((node->end_catch_label() != NULL) && | 2147 AppendFragment(catch_entry, for_catch_block); |
| 2165 (node->end_catch_label()->join_for_continue() != NULL)) { | 2148 if (node->end_catch_label() != NULL) { |
| 2166 if (is_open()) { | 2149 JoinEntryInstr* join = node->end_catch_label()->join_for_continue(); |
| 2167 AddInstruction(node->end_catch_label()->join_for_continue()); | 2150 if (join != NULL) { |
| 2168 } else { | 2151 if (is_open()) Goto(join); |
| 2169 exit_ = node->end_catch_label()->join_for_continue(); | 2152 exit_ = join; |
| 2170 } | 2153 } |
| 2171 } | 2154 } |
| 2172 } | 2155 } |
| 2173 | 2156 |
| 2174 // Generate code for the finally block if one exists. | 2157 // Generate code for the finally block if one exists. |
| 2175 if ((node->finally_block() != NULL) && is_open()) { | 2158 if ((node->finally_block() != NULL) && is_open()) { |
| 2176 EffectGraphVisitor for_finally_block(owner(), temp_index()); | 2159 EffectGraphVisitor for_finally_block(owner(), temp_index()); |
| 2177 node->finally_block()->Visit(&for_finally_block); | 2160 node->finally_block()->Visit(&for_finally_block); |
| 2178 Append(for_finally_block); | 2161 Append(for_finally_block); |
| 2179 } | 2162 } |
| (...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2238 void FlowGraphBuilder::BuildGraph(bool for_optimized, bool use_ssa) { | 2221 void FlowGraphBuilder::BuildGraph(bool for_optimized, bool use_ssa) { |
| 2239 if (FLAG_print_ast) { | 2222 if (FLAG_print_ast) { |
| 2240 // Print the function ast before IL generation. | 2223 // Print the function ast before IL generation. |
| 2241 AstPrinter::PrintFunctionNodes(parsed_function()); | 2224 AstPrinter::PrintFunctionNodes(parsed_function()); |
| 2242 } | 2225 } |
| 2243 // Compilation can be nested, preserve the computation-id. | 2226 // Compilation can be nested, preserve the computation-id. |
| 2244 const Function& function = parsed_function().function(); | 2227 const Function& function = parsed_function().function(); |
| 2245 TargetEntryInstr* normal_entry = new TargetEntryInstr(); | 2228 TargetEntryInstr* normal_entry = new TargetEntryInstr(); |
| 2246 graph_entry_ = new GraphEntryInstr(normal_entry); | 2229 graph_entry_ = new GraphEntryInstr(normal_entry); |
| 2247 EffectGraphVisitor for_effect(this, 0); | 2230 EffectGraphVisitor for_effect(this, 0); |
| 2248 for_effect.AddInstruction(normal_entry); | |
| 2249 parsed_function().node_sequence()->Visit(&for_effect); | 2231 parsed_function().node_sequence()->Visit(&for_effect); |
| 2232 AppendFragment(normal_entry, for_effect); |
| 2250 // Check that the graph is properly terminated. | 2233 // Check that the graph is properly terminated. |
| 2251 ASSERT(!for_effect.is_open()); | 2234 ASSERT(!for_effect.is_open()); |
| 2252 GrowableArray<intptr_t> parent; | 2235 GrowableArray<intptr_t> parent; |
| 2253 GrowableArray<BitVector*> assigned_vars; | 2236 GrowableArray<BitVector*> assigned_vars; |
| 2254 intptr_t variable_count = parsed_function_.function().num_fixed_parameters() + | 2237 intptr_t variable_count = parsed_function_.function().num_fixed_parameters() + |
| 2255 parsed_function_.copied_parameter_count() + | 2238 parsed_function_.copied_parameter_count() + |
| 2256 parsed_function_.stack_local_count(); | 2239 parsed_function_.stack_local_count(); |
| 2257 // Perform a depth-first traversal of the graph to build preorder and | 2240 // Perform a depth-first traversal of the graph to build preorder and |
| 2258 // postorder block orders. | 2241 // postorder block orders. |
| 2259 graph_entry_->DiscoverBlocks(NULL, // Entry block predecessor. | 2242 graph_entry_->DiscoverBlocks(NULL, // Entry block predecessor. |
| (...skipping 411 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2671 char* chars = reinterpret_cast<char*>( | 2654 char* chars = reinterpret_cast<char*>( |
| 2672 Isolate::Current()->current_zone()->Allocate(len)); | 2655 Isolate::Current()->current_zone()->Allocate(len)); |
| 2673 OS::SNPrint(chars, len, kFormat, function_name, reason); | 2656 OS::SNPrint(chars, len, kFormat, function_name, reason); |
| 2674 const Error& error = Error::Handle( | 2657 const Error& error = Error::Handle( |
| 2675 LanguageError::New(String::Handle(String::New(chars)))); | 2658 LanguageError::New(String::Handle(String::New(chars)))); |
| 2676 Isolate::Current()->long_jump_base()->Jump(1, error); | 2659 Isolate::Current()->long_jump_base()->Jump(1, error); |
| 2677 } | 2660 } |
| 2678 | 2661 |
| 2679 | 2662 |
| 2680 } // namespace dart | 2663 } // namespace dart |
| OLD | NEW |