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

Side by Side Diff: runtime/vm/flow_graph_builder.cc

Issue 10805008: Revert "Revert "Introduce Goto instructions to the flow graph."" (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 8 years, 5 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/flow_graph_builder.h ('k') | runtime/vm/flow_graph_compiler.cc » ('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_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
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
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
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
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
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
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
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
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
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
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
OLDNEW
« no previous file with comments | « runtime/vm/flow_graph_builder.h ('k') | runtime/vm/flow_graph_compiler.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698