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

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

Issue 10735071: Introduce Goto instructions to the flow graph. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Rewrite a comment that was word salad. 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
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 714 matching lines...) Expand 10 before | Expand all | Expand 10 after
907 if (node->false_branch() != NULL) node->false_branch()->Visit(&for_false); 922 if (node->false_branch() != NULL) node->false_branch()->Visit(&for_false);
908 Join(for_test, for_true, for_false); 923 Join(for_test, for_true, for_false);
909 } 924 }
910 925
911 926
912 void EffectGraphVisitor::VisitSwitchNode(SwitchNode* node) { 927 void EffectGraphVisitor::VisitSwitchNode(SwitchNode* node) {
913 EffectGraphVisitor switch_body(owner(), temp_index()); 928 EffectGraphVisitor switch_body(owner(), temp_index());
914 node->body()->Visit(&switch_body); 929 node->body()->Visit(&switch_body);
915 Append(switch_body); 930 Append(switch_body);
916 if ((node->label() != NULL) && (node->label()->join_for_break() != NULL)) { 931 if ((node->label() != NULL) && (node->label()->join_for_break() != NULL)) {
917 if (is_open()) { 932 if (is_open()) Goto(node->label()->join_for_break());
918 AddInstruction(node->label()->join_for_break()); 933 exit_ = node->label()->join_for_break();
919 } else {
920 exit_ = node->label()->join_for_break();
921 }
922 } 934 }
923 // No continue label allowed. 935 // No continue label allowed.
924 ASSERT((node->label() == NULL) || 936 ASSERT((node->label() == NULL) ||
925 (node->label()->join_for_continue() == NULL)); 937 (node->label()->join_for_continue() == NULL));
926 } 938 }
927 939
928 940
929 // A case node contains zero or more case expressions, can contain default 941 // A case node contains zero or more case expressions, can contain default
930 // and a case statement body. 942 // and a case statement body.
931 // Compose fragment as follows: 943 // Compose fragment as follows:
(...skipping 11 matching lines...) Expand all
943 // g) case-statements-join 955 // g) case-statements-join
944 // h) [ case-statements ] -> exit-join 956 // h) [ case-statements ] -> exit-join
945 // i) exit-target -> exit-join 957 // i) exit-target -> exit-join
946 // j) exit-join 958 // j) exit-join
947 // 959 //
948 // Note: The specification of switch/case is under discussion and may change 960 // Note: The specification of switch/case is under discussion and may change
949 // drastically. 961 // drastically.
950 void EffectGraphVisitor::VisitCaseNode(CaseNode* node) { 962 void EffectGraphVisitor::VisitCaseNode(CaseNode* node) {
951 const intptr_t len = node->case_expressions()->length(); 963 const intptr_t len = node->case_expressions()->length();
952 // Create case statements instructions. 964 // Create case statements instructions.
953 const bool needs_join_at_statement_entry =
954 (len > 1) || ((len > 0) && (node->contains_default()));
955 EffectGraphVisitor for_case_statements(owner(), temp_index()); 965 EffectGraphVisitor for_case_statements(owner(), temp_index());
956 // Compute start of statements fragment. 966 // Compute start of statements fragment.
957 BlockEntryInstr* statement_start = NULL; 967 JoinEntryInstr* statement_start = NULL;
958 if ((node->label() != NULL) && (node->label()->is_continue_target())) { 968 if ((node->label() != NULL) && node->label()->is_continue_target()) {
959 // Since a labeled jump continue statement occur in a different case node, 969 // Since a labeled jump continue statement occur in a different case node,
960 // allocate JoinNode here and use it as statement start. 970 // allocate JoinNode here and use it as statement start.
961 if (node->label()->join_for_continue() == NULL) { 971 statement_start = node->label()->join_for_continue();
962 node->label()->set_join_for_continue(new JoinEntryInstr()); 972 if (statement_start == NULL) {
973 statement_start = new JoinEntryInstr();
974 node->label()->set_join_for_continue(statement_start);
963 } 975 }
964 statement_start = node->label()->join_for_continue(); 976 } else {
965 } else if (needs_join_at_statement_entry) {
966 statement_start = new JoinEntryInstr(); 977 statement_start = new JoinEntryInstr();
967 } else {
968 statement_start = new TargetEntryInstr();
969 } 978 }
970 for_case_statements.AddInstruction(statement_start);
971 node->statements()->Visit(&for_case_statements); 979 node->statements()->Visit(&for_case_statements);
980 Instruction* statement_exit =
981 AppendFragment(statement_start, for_case_statements);
972 if (is_open() && (len == 0)) { 982 if (is_open() && (len == 0)) {
973 ASSERT(node->contains_default()); 983 ASSERT(node->contains_default());
974 // Default only case node. 984 // Default only case node.
975 Append(for_case_statements); 985 Goto(statement_start);
986 exit_ = statement_exit;
976 return; 987 return;
977 } 988 }
978 989
979 // Generate instructions for all case expressions and collect data to 990 // Generate instructions for all case expressions.
980 // connect them. 991 TargetEntryInstr** previous_false_address = NULL;
Kevin Millikin (Google) 2012/07/12 11:51:28 I refactored this code to wire up the case compari
981 GrowableArray<TargetEntryInstr**> case_true_addresses;
982 GrowableArray<TargetEntryInstr**> case_false_addresses;
983 GrowableArray<TargetEntryInstr*> case_entries;
984 for (intptr_t i = 0; i < len; i++) { 992 for (intptr_t i = 0; i < len; i++) {
985 AstNode* case_expr = node->case_expressions()->NodeAt(i); 993 AstNode* case_expr = node->case_expressions()->NodeAt(i);
986 TestGraphVisitor for_case_expression(owner(), 994 TestGraphVisitor for_case_expression(owner(),
987 temp_index(), 995 temp_index(),
988 case_expr->token_pos()); 996 case_expr->token_pos());
997 case_expr->Visit(&for_case_expression);
989 if (i == 0) { 998 if (i == 0) {
990 case_entries.Add(NULL); // Not to be used
991 case_expr->Visit(&for_case_expression);
992 // Append only the first one, everything else is connected from it. 999 // Append only the first one, everything else is connected from it.
993 Append(for_case_expression); 1000 Append(for_case_expression);
994 } else { 1001 } else {
995 TargetEntryInstr* case_entry_target = new TargetEntryInstr(); 1002 TargetEntryInstr* case_entry_target = new TargetEntryInstr();
996 case_entries.Add(case_entry_target); 1003 AppendFragment(case_entry_target, for_case_expression);
997 for_case_expression.AddInstruction(case_entry_target); 1004 *previous_false_address = case_entry_target;
998 case_expr->Visit(&for_case_expression);
999 } 1005 }
1000 case_true_addresses.Add(for_case_expression.true_successor_address()); 1006 TargetEntryInstr* true_target = new TargetEntryInstr();
1001 case_false_addresses.Add(for_case_expression.false_successor_address()); 1007 *for_case_expression.true_successor_address() = true_target;
1008 true_target->Goto(statement_start);
1009 previous_false_address = for_case_expression.false_successor_address();
1002 } 1010 }
1003 1011
1004 // Once a test fragment has been added, this fragment is closed. 1012 // Once a test fragment has been added, this fragment is closed.
1005 ASSERT(!is_open()); 1013 ASSERT(!is_open());
1006 1014
1007 // Connect all test cases except the last one. 1015 Instruction* exit_instruction = NULL;
1008 for (intptr_t i = 0; i < (len - 1); i++) {
1009 ASSERT(needs_join_at_statement_entry);
1010 *case_false_addresses[i] = case_entries[i + 1];
1011 TargetEntryInstr* true_target = new TargetEntryInstr();
1012 *case_true_addresses[i] = true_target;
1013 true_target->set_next(statement_start);
1014 }
1015
1016 BlockEntryInstr* exit_instruction = NULL;
1017 // Handle last (or only) case: false goes to exit or to statement if this 1016 // Handle last (or only) case: false goes to exit or to statement if this
1018 // node contains default. 1017 // node contains default.
1019 if (len > 0) { 1018 if (len > 0) {
1020 if (statement_start->IsTargetEntry()) {
1021 *case_true_addresses[len - 1] = statement_start->AsTargetEntry();
1022 } else {
1023 TargetEntryInstr* true_target = new TargetEntryInstr();
1024 *case_true_addresses[len - 1] = true_target;
1025 true_target->set_next(statement_start);
1026 }
1027 TargetEntryInstr* false_target = new TargetEntryInstr(); 1019 TargetEntryInstr* false_target = new TargetEntryInstr();
1028 *case_false_addresses[len - 1] = false_target; 1020 *previous_false_address = false_target;
1029 if (node->contains_default()) { 1021 if (node->contains_default()) {
1030 // True and false go to statement start. 1022 // True and false go to statement start.
1031 false_target->set_next(statement_start); 1023 false_target->Goto(statement_start);
1032 if (for_case_statements.is_open()) { 1024 exit_instruction = statement_exit;
1033 exit_instruction = new TargetEntryInstr(); 1025 } else {
1034 for_case_statements.exit()->set_next(exit_instruction); 1026 if (statement_exit != NULL) {
1027 JoinEntryInstr* join = new JoinEntryInstr();
1028 statement_exit->Goto(join);
1029 false_target->Goto(join);
1030 exit_instruction = join;
1031 } else {
1032 exit_instruction = false_target;
1035 } 1033 }
1036 } else {
1037 if (for_case_statements.is_open()) {
1038 exit_instruction = new JoinEntryInstr();
1039 for_case_statements.exit()->set_next(exit_instruction);
1040 } else {
1041 exit_instruction = new TargetEntryInstr();
1042 }
1043 false_target->set_next(exit_instruction);
1044 } 1034 }
1045 } else { 1035 } else {
1046 // A CaseNode without case expressions must contain default. 1036 // A CaseNode without case expressions must contain default.
1047 ASSERT(node->contains_default()); 1037 ASSERT(node->contains_default());
1048 AddInstruction(statement_start); 1038 Goto(statement_start);
1039 exit_instruction = statement_exit;
1049 } 1040 }
1050 1041
1051 ASSERT(!is_open()); 1042 ASSERT(!is_open());
1052 exit_ = exit_instruction; 1043 exit_ = exit_instruction;
1053 } 1044 }
1054 1045
1055 1046
1056 // <Statement> ::= While { label: SourceLabel 1047 // <Statement> ::= While { label: SourceLabel
1057 // condition: <Expression> 1048 // condition: <Expression>
1058 // body: <Sequence> } 1049 // body: <Sequence> }
(...skipping 13 matching lines...) Expand all
1072 ASSERT(!for_test.is_empty()); // Language spec. 1063 ASSERT(!for_test.is_empty()); // Language spec.
1073 1064
1074 EffectGraphVisitor for_body(owner(), temp_index()); 1065 EffectGraphVisitor for_body(owner(), temp_index());
1075 for_body.Do( 1066 for_body.Do(
1076 new CheckStackOverflowComp(node->token_pos(), owner()->try_index())); 1067 new CheckStackOverflowComp(node->token_pos(), owner()->try_index()));
1077 node->body()->Visit(&for_body); 1068 node->body()->Visit(&for_body);
1078 1069
1079 // Labels are set after body traversal. 1070 // Labels are set after body traversal.
1080 SourceLabel* lbl = node->label(); 1071 SourceLabel* lbl = node->label();
1081 ASSERT(lbl != NULL); 1072 ASSERT(lbl != NULL);
1082 if (lbl->join_for_continue() != NULL) { 1073 JoinEntryInstr* join = lbl->join_for_continue();
1083 AddInstruction(lbl->join_for_continue()); 1074 if (join != NULL) {
1075 Goto(join);
1076 exit_ = join;
1084 } 1077 }
1085 TieLoop(for_test, for_body); 1078 TieLoop(for_test, for_body);
1086 if (lbl->join_for_break() != NULL) { 1079 join = lbl->join_for_break();
1087 AddInstruction(lbl->join_for_break()); 1080 if (join != NULL) {
1081 Goto(join);
1082 exit_ = join;
1088 } 1083 }
1089 } 1084 }
1090 1085
1091 1086
1092 // The fragment is composed as follows: 1087 // The fragment is composed as follows:
1093 // a) body-entry-join 1088 // a) body-entry-join
1094 // b) [ body ] 1089 // b) [ body ]
1095 // c) test-entry (continue-join or body-exit-target) 1090 // c) test-entry (continue-join or body-exit-target)
1096 // d) [ test-entry ] -> (back-target, loop-exit-target) 1091 // d) [ test-entry ] -> (back-target, loop-exit-target)
1097 // e) back-target -> (body-entry-join) 1092 // e) back-target -> (body-entry-join)
1098 // f) loop-exit-target 1093 // f) loop-exit-target
1099 // g) break-join 1094 // g) break-join
1100 void EffectGraphVisitor::VisitDoWhileNode(DoWhileNode* node) { 1095 void EffectGraphVisitor::VisitDoWhileNode(DoWhileNode* node) {
1101 // Traverse body first in order to generate continue and break labels. 1096 // Traverse body first in order to generate continue and break labels.
1102 EffectGraphVisitor for_body(owner(), temp_index()); 1097 EffectGraphVisitor for_body(owner(), temp_index());
1103 for_body.Do( 1098 for_body.Do(
1104 new CheckStackOverflowComp(node->token_pos(), owner()->try_index())); 1099 new CheckStackOverflowComp(node->token_pos(), owner()->try_index()));
1105 node->body()->Visit(&for_body); 1100 node->body()->Visit(&for_body);
1106 1101
1107 TestGraphVisitor for_test(owner(), 1102 TestGraphVisitor for_test(owner(),
1108 temp_index(), 1103 temp_index(),
1109 node->condition()->token_pos()); 1104 node->condition()->token_pos());
1110 node->condition()->Visit(&for_test); 1105 node->condition()->Visit(&for_test);
1111 ASSERT(is_open()); 1106 ASSERT(is_open());
1112 1107
1113 // Tie do-while loop (test is after the body). 1108 // Tie do-while loop (test is after the body).
1114 JoinEntryInstr* body_entry_join = new JoinEntryInstr(); 1109 JoinEntryInstr* body_entry_join = new JoinEntryInstr();
1115 AddInstruction(body_entry_join); 1110 Goto(body_entry_join);
1116 Instruction* body_exit = AppendFragment(body_entry_join, for_body); 1111 Instruction* body_exit = AppendFragment(body_entry_join, for_body);
1117 1112
1118 if (for_body.is_open() || (node->label()->join_for_continue() != NULL)) { 1113 JoinEntryInstr* join = node->label()->join_for_continue();
1119 BlockEntryInstr* test_entry = NULL; 1114 if ((body_exit != NULL) || (join != NULL)) {
1120 if (node->label()->join_for_continue() == NULL) { 1115 if (join == NULL) join = new JoinEntryInstr();
1121 test_entry = new TargetEntryInstr(); 1116 join->set_next(for_test.entry());
1122 } else {
1123 test_entry = node->label()->join_for_continue();
1124 }
1125 test_entry->set_next(for_test.entry());
1126 if (body_exit != NULL) { 1117 if (body_exit != NULL) {
1127 body_exit->set_next(test_entry); 1118 body_exit->Goto(join);
1128 } 1119 }
1129 } 1120 }
1130 1121
1131 TargetEntryInstr* back_target_entry = new TargetEntryInstr(); 1122 TargetEntryInstr* back_target_entry = new TargetEntryInstr();
1132 *for_test.true_successor_address() = back_target_entry; 1123 *for_test.true_successor_address() = back_target_entry;
1133 back_target_entry->set_next(body_entry_join); 1124 back_target_entry->Goto(body_entry_join);
1134 TargetEntryInstr* loop_exit_target = new TargetEntryInstr(); 1125 TargetEntryInstr* loop_exit_target = new TargetEntryInstr();
1135 *for_test.false_successor_address() = loop_exit_target; 1126 *for_test.false_successor_address() = loop_exit_target;
1136 if (node->label()->join_for_break() == NULL) { 1127 if (node->label()->join_for_break() == NULL) {
1137 exit_ = loop_exit_target; 1128 exit_ = loop_exit_target;
1138 } else { 1129 } else {
1139 loop_exit_target->set_next(node->label()->join_for_break()); 1130 loop_exit_target->Goto(node->label()->join_for_break());
1140 exit_ = node->label()->join_for_break(); 1131 exit_ = node->label()->join_for_break();
1141 } 1132 }
1142 } 1133 }
1143 1134
1144 1135
1145 // A ForNode can contain break and continue jumps. 'break' joins to 1136 // A ForNode can contain break and continue jumps. 'break' joins to
1146 // ForNode exit, 'continue' joins at increment entry. The fragment is composed 1137 // ForNode exit, 'continue' joins at increment entry. The fragment is composed
1147 // as follows: 1138 // as follows:
1148 // a) [ initializer ] 1139 // a) [ initializer ]
1149 // b) loop-join 1140 // b) loop-join
1150 // c) [ test ] -> (body-entry-target, loop-exit-target) 1141 // c) [ test ] -> (body-entry-target, loop-exit-target)
1151 // d) body-entry-target 1142 // d) body-entry-target
1152 // e) [ body ] 1143 // e) [ body ]
1153 // f) continue-join (optional) 1144 // f) continue-join (optional)
1154 // g) [ increment ] -> (loop-join) 1145 // g) [ increment ] -> (loop-join)
1155 // h) loop-exit-target 1146 // h) loop-exit-target
1156 // i) break-join 1147 // i) break-join
1157 void EffectGraphVisitor::VisitForNode(ForNode* node) { 1148 void EffectGraphVisitor::VisitForNode(ForNode* node) {
1158 EffectGraphVisitor for_initializer(owner(), temp_index()); 1149 EffectGraphVisitor for_initializer(owner(), temp_index());
1159 node->initializer()->Visit(&for_initializer); 1150 node->initializer()->Visit(&for_initializer);
1160 Append(for_initializer); 1151 Append(for_initializer);
1161 ASSERT(is_open()); 1152 ASSERT(is_open());
1162 1153
1163 // Compose body to set any jump labels. 1154 // Compose body to set any jump labels.
1164 EffectGraphVisitor for_body(owner(), temp_index()); 1155 EffectGraphVisitor for_body(owner(), temp_index());
1165 TargetEntryInstr* body_entry = new TargetEntryInstr();
1166 for_body.AddInstruction(body_entry);
1167 for_body.Do( 1156 for_body.Do(
1168 new CheckStackOverflowComp(node->token_pos(), owner()->try_index())); 1157 new CheckStackOverflowComp(node->token_pos(), owner()->try_index()));
1169 node->body()->Visit(&for_body); 1158 node->body()->Visit(&for_body);
1170 1159
1171 // Join loop body, increment and compute their end instruction. 1160 // Join loop body, increment and compute their end instruction.
1172 ASSERT(!for_body.is_empty()); 1161 ASSERT(!for_body.is_empty());
1173 Instruction* loop_increment_end = NULL; 1162 Instruction* loop_increment_end = NULL;
1174 EffectGraphVisitor for_increment(owner(), temp_index()); 1163 EffectGraphVisitor for_increment(owner(), temp_index());
1175 if ((node->label()->join_for_continue() == NULL) && for_body.is_open()) { 1164 node->increment()->Visit(&for_increment);
1165 JoinEntryInstr* join = node->label()->join_for_continue();
1166 if (join != NULL) {
1167 // Insert the join between the body and increment.
1168 if (for_body.is_open()) for_body.Goto(join);
1169 loop_increment_end = AppendFragment(join, for_increment);
1170 ASSERT(loop_increment_end != NULL);
1171 } else if (for_body.is_open()) {
1176 // Do not insert an extra basic block. 1172 // Do not insert an extra basic block.
1177 node->increment()->Visit(&for_increment);
1178 for_body.Append(for_increment); 1173 for_body.Append(for_increment);
1179 loop_increment_end = for_body.exit(); 1174 loop_increment_end = for_body.exit();
1180 // 'for_body' contains at least the TargetInstruction 'body_entry'. 1175 // 'for_body' contains at least the stack check.
1181 ASSERT(loop_increment_end != NULL);
1182 } else if (node->label()->join_for_continue() != NULL) {
1183 // Insert join between body and increment.
1184 if (for_body.is_open()) {
1185 for_body.exit()->set_next(node->label()->join_for_continue());
1186 }
1187 for_increment.AddInstruction(node->label()->join_for_continue());
1188 node->increment()->Visit(&for_increment);
1189 loop_increment_end = for_increment.exit();
1190 ASSERT(loop_increment_end != NULL); 1176 ASSERT(loop_increment_end != NULL);
1191 } else { 1177 } else {
1192 loop_increment_end = NULL; 1178 loop_increment_end = NULL;
1193 ASSERT(!for_body.is_open() && node->label()->join_for_continue() == NULL);
1194 } 1179 }
1195 1180
1196 // 'loop_increment_end' is NULL only if there is no join for continue and the 1181 // 'loop_increment_end' is NULL only if there is no join for continue and the
1197 // body is not open, i.e., no backward branch exists. 1182 // body is not open, i.e., no backward branch exists.
1198 if (loop_increment_end != NULL) { 1183 if (loop_increment_end != NULL) {
1199 JoinEntryInstr* loop_start = new JoinEntryInstr(); 1184 JoinEntryInstr* loop_start = new JoinEntryInstr();
1200 AddInstruction(loop_start); 1185 Goto(loop_start);
1201 loop_increment_end->set_next(loop_start); 1186 loop_increment_end->Goto(loop_start);
1187 exit_ = loop_start;
1202 } 1188 }
1203 1189
1204 if (node->condition() == NULL) { 1190 if (node->condition() == NULL) {
1205 // Endless loop, no test. 1191 // Endless loop, no test.
1206 Append(for_body); 1192 JoinEntryInstr* body_entry = new JoinEntryInstr();
1207 if (node->label()->join_for_break() == NULL) { 1193 AppendFragment(body_entry, for_body);
1208 CloseFragment(); 1194 Goto(body_entry);
1209 } else { 1195 if (node->label()->join_for_break() != NULL) {
1210 // Control flow of ForLoop continues into join_for_break. 1196 // Control flow of ForLoop continues into join_for_break.
1211 exit_ = node->label()->join_for_break(); 1197 exit_ = node->label()->join_for_break();
1212 } 1198 }
1213 } else { 1199 } else {
1214 TargetEntryInstr* loop_exit = new TargetEntryInstr(); 1200 TargetEntryInstr* loop_exit = new TargetEntryInstr();
1215 TestGraphVisitor for_test(owner(), 1201 TestGraphVisitor for_test(owner(),
1216 temp_index(), 1202 temp_index(),
1217 node->condition()->token_pos()); 1203 node->condition()->token_pos());
1218 node->condition()->Visit(&for_test); 1204 node->condition()->Visit(&for_test);
1219 Append(for_test); 1205 Append(for_test);
1206 TargetEntryInstr* body_entry = new TargetEntryInstr();
1207 AppendFragment(body_entry, for_body);
1220 *for_test.true_successor_address() = body_entry; 1208 *for_test.true_successor_address() = body_entry;
1221 *for_test.false_successor_address() = loop_exit; 1209 *for_test.false_successor_address() = loop_exit;
1222 if (node->label()->join_for_break() == NULL) { 1210 if (node->label()->join_for_break() == NULL) {
1223 exit_ = loop_exit; 1211 exit_ = loop_exit;
1224 } else { 1212 } else {
1225 loop_exit->set_next(node->label()->join_for_break()); 1213 loop_exit->Goto(node->label()->join_for_break());
1226 exit_ = node->label()->join_for_break(); 1214 exit_ = node->label()->join_for_break();
1227 } 1215 }
1228 } 1216 }
1229 } 1217 }
1230 1218
1231 1219
1232 void EffectGraphVisitor::VisitJumpNode(JumpNode* node) { 1220 void EffectGraphVisitor::VisitJumpNode(JumpNode* node) {
1233 for (intptr_t i = 0; i < node->inlined_finally_list_length(); i++) { 1221 for (intptr_t i = 0; i < node->inlined_finally_list_length(); i++) {
1234 EffectGraphVisitor for_effect(owner(), temp_index()); 1222 EffectGraphVisitor for_effect(owner(), temp_index());
1235 node->InlinedFinallyNodeAt(i)->Visit(&for_effect); 1223 node->InlinedFinallyNodeAt(i)->Visit(&for_effect);
(...skipping 22 matching lines...) Expand all
1258 target_context_level = target_scope->context_level(); 1246 target_context_level = target_scope->context_level();
1259 } 1247 }
1260 } 1248 }
1261 ASSERT(target_context_level >= 0); 1249 ASSERT(target_context_level >= 0);
1262 intptr_t current_context_level = owner()->context_level(); 1250 intptr_t current_context_level = owner()->context_level();
1263 ASSERT(current_context_level >= target_context_level); 1251 ASSERT(current_context_level >= target_context_level);
1264 while (current_context_level-- > target_context_level) { 1252 while (current_context_level-- > target_context_level) {
1265 UnchainContext(); 1253 UnchainContext();
1266 } 1254 }
1267 1255
1268 Instruction* jump_target = NULL; 1256 JoinEntryInstr* jump_target = NULL;
1269 if (node->kind() == Token::kBREAK) { 1257 if (node->kind() == Token::kBREAK) {
1270 if (node->label()->join_for_break() == NULL) { 1258 if (node->label()->join_for_break() == NULL) {
1271 node->label()->set_join_for_break(new JoinEntryInstr()); 1259 node->label()->set_join_for_break(new JoinEntryInstr());
1272 } 1260 }
1273 jump_target = node->label()->join_for_break(); 1261 jump_target = node->label()->join_for_break();
1274 } else { 1262 } else {
1275 if (node->label()->join_for_continue() == NULL) { 1263 if (node->label()->join_for_continue() == NULL) {
1276 node->label()->set_join_for_continue(new JoinEntryInstr()); 1264 node->label()->set_join_for_continue(new JoinEntryInstr());
1277 } 1265 }
1278 jump_target = node->label()->join_for_continue(); 1266 jump_target = node->label()->join_for_continue();
1279 } 1267 }
1280 AddInstruction(jump_target); 1268 Goto(jump_target);
1281 CloseFragment();
1282 } 1269 }
1283 1270
1284 1271
1285 void EffectGraphVisitor::VisitArgumentListNode(ArgumentListNode* node) { 1272 void EffectGraphVisitor::VisitArgumentListNode(ArgumentListNode* node) {
1286 UNREACHABLE(); 1273 UNREACHABLE();
1287 } 1274 }
1288 1275
1289 1276
1290 void EffectGraphVisitor::VisitArrayNode(ArrayNode* node) { 1277 void EffectGraphVisitor::VisitArrayNode(ArrayNode* node) {
1291 // Translate the array elements and collect their values. 1278 // Translate the array elements and collect their values.
(...skipping 802 matching lines...) Expand 10 before | Expand all | Expand 10 after
2094 } 2081 }
2095 } 2082 }
2096 2083
2097 // No continue on sequence allowed. 2084 // No continue on sequence allowed.
2098 ASSERT((node->label() == NULL) || 2085 ASSERT((node->label() == NULL) ||
2099 (node->label()->join_for_continue() == NULL)); 2086 (node->label()->join_for_continue() == NULL));
2100 // If this node sequence is labeled, a break out of the sequence will have 2087 // If this node sequence is labeled, a break out of the sequence will have
2101 // taken care of unchaining the context. 2088 // taken care of unchaining the context.
2102 if ((node->label() != NULL) && 2089 if ((node->label() != NULL) &&
2103 (node->label()->join_for_break() != NULL)) { 2090 (node->label()->join_for_break() != NULL)) {
2104 if (is_open()) { 2091 if (is_open()) Goto(node->label()->join_for_break());
2105 AddInstruction(node->label()->join_for_break()); 2092 exit_ = node->label()->join_for_break();
2106 } else {
2107 exit_ = node->label()->join_for_break();
2108 }
2109 } 2093 }
2110 2094
2111 // The outermost function sequence cannot contain a label. 2095 // The outermost function sequence cannot contain a label.
2112 ASSERT((node->label() == NULL) || 2096 ASSERT((node->label() == NULL) ||
2113 (node != owner()->parsed_function().node_sequence())); 2097 (node != owner()->parsed_function().node_sequence()));
2114 owner()->set_context_level(previous_context_level); 2098 owner()->set_context_level(previous_context_level);
2115 } 2099 }
2116 2100
2117 2101
2118 void EffectGraphVisitor::VisitCatchClauseNode(CatchClauseNode* node) { 2102 void EffectGraphVisitor::VisitCatchClauseNode(CatchClauseNode* node) {
(...skipping 24 matching lines...) Expand all
2143 // We are done generating code for the try block. 2127 // We are done generating code for the try block.
2144 owner()->set_try_index(old_try_index); 2128 owner()->set_try_index(old_try_index);
2145 2129
2146 CatchClauseNode* catch_block = node->catch_block(); 2130 CatchClauseNode* catch_block = node->catch_block();
2147 if (catch_block != NULL) { 2131 if (catch_block != NULL) {
2148 // Set the corresponding try index for this catch block so 2132 // Set the corresponding try index for this catch block so
2149 // that we can set the appropriate handler pc when we generate 2133 // that we can set the appropriate handler pc when we generate
2150 // code for this catch block. 2134 // code for this catch block.
2151 catch_block->set_try_index(try_index); 2135 catch_block->set_try_index(try_index);
2152 EffectGraphVisitor for_catch_block(owner(), temp_index()); 2136 EffectGraphVisitor for_catch_block(owner(), temp_index());
2137 catch_block->Visit(&for_catch_block);
2153 TargetEntryInstr* catch_entry = new TargetEntryInstr(try_index); 2138 TargetEntryInstr* catch_entry = new TargetEntryInstr(try_index);
2154 for_catch_block.AddInstruction(catch_entry);
2155 catch_block->Visit(&for_catch_block);
2156 owner()->AddCatchEntry(catch_entry); 2139 owner()->AddCatchEntry(catch_entry);
2157 ASSERT(!for_catch_block.is_open()); 2140 ASSERT(!for_catch_block.is_open());
2158 if ((node->end_catch_label() != NULL) && 2141 AppendFragment(catch_entry, for_catch_block);
2159 (node->end_catch_label()->join_for_continue() != NULL)) { 2142 if (node->end_catch_label() != NULL) {
2160 if (is_open()) { 2143 JoinEntryInstr* join = node->end_catch_label()->join_for_continue();
2161 AddInstruction(node->end_catch_label()->join_for_continue()); 2144 if (join != NULL) {
2162 } else { 2145 if (is_open()) Goto(join);
2163 exit_ = node->end_catch_label()->join_for_continue(); 2146 exit_ = join;
2164 } 2147 }
2165 } 2148 }
2166 } 2149 }
2167 2150
2168 // Generate code for the finally block if one exists. 2151 // Generate code for the finally block if one exists.
2169 if ((node->finally_block() != NULL) && is_open()) { 2152 if ((node->finally_block() != NULL) && is_open()) {
2170 EffectGraphVisitor for_finally_block(owner(), temp_index()); 2153 EffectGraphVisitor for_finally_block(owner(), temp_index());
2171 node->finally_block()->Visit(&for_finally_block); 2154 node->finally_block()->Visit(&for_finally_block);
2172 Append(for_finally_block); 2155 Append(for_finally_block);
2173 } 2156 }
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after
2232 void FlowGraphBuilder::BuildGraph(bool for_optimized, bool use_ssa) { 2215 void FlowGraphBuilder::BuildGraph(bool for_optimized, bool use_ssa) {
2233 if (FLAG_print_ast) { 2216 if (FLAG_print_ast) {
2234 // Print the function ast before IL generation. 2217 // Print the function ast before IL generation.
2235 AstPrinter::PrintFunctionNodes(parsed_function()); 2218 AstPrinter::PrintFunctionNodes(parsed_function());
2236 } 2219 }
2237 // Compilation can be nested, preserve the computation-id. 2220 // Compilation can be nested, preserve the computation-id.
2238 const Function& function = parsed_function().function(); 2221 const Function& function = parsed_function().function();
2239 TargetEntryInstr* normal_entry = new TargetEntryInstr(); 2222 TargetEntryInstr* normal_entry = new TargetEntryInstr();
2240 graph_entry_ = new GraphEntryInstr(normal_entry); 2223 graph_entry_ = new GraphEntryInstr(normal_entry);
2241 EffectGraphVisitor for_effect(this, 0); 2224 EffectGraphVisitor for_effect(this, 0);
2242 for_effect.AddInstruction(normal_entry);
2243 parsed_function().node_sequence()->Visit(&for_effect); 2225 parsed_function().node_sequence()->Visit(&for_effect);
2226 AppendFragment(normal_entry, for_effect);
2244 // Check that the graph is properly terminated. 2227 // Check that the graph is properly terminated.
2245 ASSERT(!for_effect.is_open()); 2228 ASSERT(!for_effect.is_open());
2246 GrowableArray<intptr_t> parent; 2229 GrowableArray<intptr_t> parent;
2247 GrowableArray<BitVector*> assigned_vars; 2230 GrowableArray<BitVector*> assigned_vars;
2248 intptr_t variable_count = parsed_function_.function().num_fixed_parameters() + 2231 intptr_t variable_count = parsed_function_.function().num_fixed_parameters() +
2249 parsed_function_.copied_parameter_count() + 2232 parsed_function_.copied_parameter_count() +
2250 parsed_function_.stack_local_count(); 2233 parsed_function_.stack_local_count();
2251 // Perform a depth-first traversal of the graph to build preorder and 2234 // Perform a depth-first traversal of the graph to build preorder and
2252 // postorder block orders. 2235 // postorder block orders.
2253 graph_entry_->DiscoverBlocks(NULL, // Entry block predecessor. 2236 graph_entry_->DiscoverBlocks(NULL, // Entry block predecessor.
(...skipping 411 matching lines...) Expand 10 before | Expand all | Expand 10 after
2665 char* chars = reinterpret_cast<char*>( 2648 char* chars = reinterpret_cast<char*>(
2666 Isolate::Current()->current_zone()->Allocate(len)); 2649 Isolate::Current()->current_zone()->Allocate(len));
2667 OS::SNPrint(chars, len, kFormat, function_name, reason); 2650 OS::SNPrint(chars, len, kFormat, function_name, reason);
2668 const Error& error = Error::Handle( 2651 const Error& error = Error::Handle(
2669 LanguageError::New(String::Handle(String::New(chars)))); 2652 LanguageError::New(String::Handle(String::New(chars))));
2670 Isolate::Current()->long_jump_base()->Jump(1, error); 2653 Isolate::Current()->long_jump_base()->Jump(1, error);
2671 } 2654 }
2672 2655
2673 2656
2674 } // namespace dart 2657 } // namespace dart
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698