Chromium Code Reviews| 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.h" | 5 #include "vm/flow_graph.h" |
| 6 | 6 |
| 7 #include "vm/assert.h" | |
| 8 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
| 9 #include "vm/flow_graph_builder.h" | 8 #include "vm/flow_graph_builder.h" |
| 10 #include "vm/intermediate_language.h" | 9 #include "vm/intermediate_language.h" |
| 11 #include "vm/longjump.h" | 10 #include "vm/longjump.h" |
| 12 #include "vm/growable_array.h" | 11 #include "vm/growable_array.h" |
| 13 | 12 |
| 14 namespace dart { | 13 namespace dart { |
| 15 | 14 |
| 16 DECLARE_FLAG(bool, trace_optimization); | 15 DECLARE_FLAG(bool, trace_optimization); |
| 16 DECLARE_FLAG(bool, verify_compiler); | |
| 17 | 17 |
| 18 FlowGraph::FlowGraph(const FlowGraphBuilder& builder, | 18 FlowGraph::FlowGraph(const FlowGraphBuilder& builder, |
| 19 GraphEntryInstr* graph_entry, | 19 GraphEntryInstr* graph_entry, |
| 20 intptr_t max_block_id) | 20 intptr_t max_block_id) |
| 21 : parent_(), | 21 : parent_(), |
| 22 assigned_vars_(), | 22 assigned_vars_(), |
| 23 current_ssa_temp_index_(0), | 23 current_ssa_temp_index_(0), |
| 24 max_block_id_(max_block_id), | 24 max_block_id_(max_block_id), |
| 25 parsed_function_(builder.parsed_function()), | 25 parsed_function_(builder.parsed_function()), |
| 26 num_copied_params_(builder.num_copied_params()), | 26 num_copied_params_(builder.num_copied_params()), |
| (...skipping 91 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 118 return true; // Return true so we can ASSERT the reset code. | 118 return true; // Return true so we can ASSERT the reset code. |
| 119 } | 119 } |
| 120 | 120 |
| 121 | 121 |
| 122 static void ValidateUseListsInInstruction(Instruction* instr) { | 122 static void ValidateUseListsInInstruction(Instruction* instr) { |
| 123 ASSERT(instr != NULL); | 123 ASSERT(instr != NULL); |
| 124 ASSERT(!instr->IsJoinEntry()); | 124 ASSERT(!instr->IsJoinEntry()); |
| 125 for (intptr_t i = 0; i < instr->InputCount(); ++i) { | 125 for (intptr_t i = 0; i < instr->InputCount(); ++i) { |
| 126 Value* use = instr->InputAt(i); | 126 Value* use = instr->InputAt(i); |
| 127 ASSERT(use->use_index() == i); | 127 ASSERT(use->use_index() == i); |
| 128 SLOW_ASSERT(1 == MembershipCount(use, use->definition()->input_use_list())); | 128 ASSERT(!FLAG_verify_compiler || |
| 129 (1 == MembershipCount(use, use->definition()->input_use_list()))); | |
|
srdjan
2012/10/09 16:28:52
Would it make sense to do verification in release
zerny-google
2012/10/10 07:44:54
We could, but currently all of the verification co
| |
| 129 } | 130 } |
| 130 if (instr->env() != NULL) { | 131 if (instr->env() != NULL) { |
| 131 intptr_t use_index = 0; | 132 intptr_t use_index = 0; |
| 132 for (Environment::DeepIterator it(instr->env()); !it.Done(); it.Advance()) { | 133 for (Environment::DeepIterator it(instr->env()); !it.Done(); it.Advance()) { |
| 133 Value* use = it.CurrentValue(); | 134 Value* use = it.CurrentValue(); |
| 134 ASSERT(use->use_index() == use_index++); | 135 ASSERT(use->use_index() == use_index++); |
| 135 SLOW_ASSERT(1 == MembershipCount(use, use->definition()->env_use_list())); | 136 ASSERT(!FLAG_verify_compiler || |
| 137 (1 == MembershipCount(use, use->definition()->env_use_list()))); | |
| 136 } | 138 } |
| 137 } | 139 } |
| 138 Definition* defn = instr->AsDefinition(); | 140 Definition* defn = instr->AsDefinition(); |
| 139 if (defn != NULL) { | 141 if (defn != NULL) { |
| 140 for (Value* use = defn->input_use_list(); | 142 for (Value* use = defn->input_use_list(); |
| 141 use != NULL; | 143 use != NULL; |
| 142 use = use->next_use()) { | 144 use = use->next_use()) { |
| 143 ASSERT(defn == use->definition()); | 145 ASSERT(defn == use->definition()); |
| 144 ASSERT(use == use->instruction()->InputAt(use->use_index())); | 146 ASSERT(use == use->instruction()->InputAt(use->use_index())); |
| 145 } | 147 } |
| (...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 188 } | 190 } |
| 189 | 191 |
| 190 | 192 |
| 191 static void RecordInputUses(Instruction* instr) { | 193 static void RecordInputUses(Instruction* instr) { |
| 192 ASSERT(instr != NULL); | 194 ASSERT(instr != NULL); |
| 193 for (intptr_t i = 0; i < instr->InputCount(); ++i) { | 195 for (intptr_t i = 0; i < instr->InputCount(); ++i) { |
| 194 Value* use = instr->InputAt(i); | 196 Value* use = instr->InputAt(i); |
| 195 ASSERT(use->instruction() == NULL); | 197 ASSERT(use->instruction() == NULL); |
| 196 ASSERT(use->use_index() == -1); | 198 ASSERT(use->use_index() == -1); |
| 197 ASSERT(use->next_use() == NULL); | 199 ASSERT(use->next_use() == NULL); |
| 198 SLOW_ASSERT(0 == MembershipCount(use, use->definition()->input_use_list())); | 200 DEBUG_ASSERT(!FLAG_verify_compiler || |
|
srdjan
2012/10/09 16:28:52
Why DEBUG_ASSERT instead of ASSERT? All identifier
zerny-google
2012/10/10 07:44:54
No, the verification code (including MembershipCou
| |
| 201 (0 == MembershipCount(use, use->definition()->input_use_list()))); | |
| 199 use->set_instruction(instr); | 202 use->set_instruction(instr); |
| 200 use->set_use_index(i); | 203 use->set_use_index(i); |
| 201 use->AddToInputUseList(); | 204 use->AddToInputUseList(); |
| 202 } | 205 } |
| 203 } | 206 } |
| 204 | 207 |
| 205 | 208 |
| 206 static void RecordEnvUses(Instruction* instr) { | 209 static void RecordEnvUses(Instruction* instr) { |
| 207 ASSERT(instr != NULL); | 210 ASSERT(instr != NULL); |
| 208 if (instr->env() == NULL) return; | 211 if (instr->env() == NULL) return; |
| 209 intptr_t use_index = 0; | 212 intptr_t use_index = 0; |
| 210 for (Environment::DeepIterator it(instr->env()); !it.Done(); it.Advance()) { | 213 for (Environment::DeepIterator it(instr->env()); !it.Done(); it.Advance()) { |
| 211 Value* use = it.CurrentValue(); | 214 Value* use = it.CurrentValue(); |
| 212 ASSERT(use->instruction() == NULL); | 215 ASSERT(use->instruction() == NULL); |
| 213 ASSERT(use->use_index() == -1); | 216 ASSERT(use->use_index() == -1); |
| 214 ASSERT(use->next_use() == NULL); | 217 ASSERT(use->next_use() == NULL); |
| 215 SLOW_ASSERT(0 == MembershipCount(use, use->definition()->env_use_list())); | 218 DEBUG_ASSERT(!FLAG_verify_compiler || |
| 219 (0 == MembershipCount(use, use->definition()->env_use_list()))); | |
| 216 use->set_instruction(instr); | 220 use->set_instruction(instr); |
| 217 use->set_use_index(use_index++); | 221 use->set_use_index(use_index++); |
| 218 use->AddToEnvUseList(); | 222 use->AddToEnvUseList(); |
| 219 } | 223 } |
| 220 } | 224 } |
| 221 | 225 |
| 222 | 226 |
| 223 static void ComputeUseListsRecursive(BlockEntryInstr* block) { | 227 static void ComputeUseListsRecursive(BlockEntryInstr* block) { |
| 224 // Clear phi definitions. | 228 // Clear phi definitions. |
| 225 JoinEntryInstr* join = block->AsJoinEntry(); | 229 JoinEntryInstr* join = block->AsJoinEntry(); |
| (...skipping 22 matching lines...) Expand all Loading... | |
| 248 intptr_t pred_index = join->IndexOfPredecessor(block); | 252 intptr_t pred_index = join->IndexOfPredecessor(block); |
| 249 ASSERT(pred_index >= 0); | 253 ASSERT(pred_index >= 0); |
| 250 if (join->phis() != NULL) { | 254 if (join->phis() != NULL) { |
| 251 for (intptr_t i = 0; i < join->phis()->length(); ++i) { | 255 for (intptr_t i = 0; i < join->phis()->length(); ++i) { |
| 252 PhiInstr* phi = (*join->phis())[i]; | 256 PhiInstr* phi = (*join->phis())[i]; |
| 253 if (phi == NULL) continue; | 257 if (phi == NULL) continue; |
| 254 Value* use = phi->InputAt(pred_index); | 258 Value* use = phi->InputAt(pred_index); |
| 255 ASSERT(use->instruction() == NULL); | 259 ASSERT(use->instruction() == NULL); |
| 256 ASSERT(use->use_index() == -1); | 260 ASSERT(use->use_index() == -1); |
| 257 ASSERT(use->next_use() == NULL); | 261 ASSERT(use->next_use() == NULL); |
| 258 SLOW_ASSERT(0 == MembershipCount(use, | 262 DEBUG_ASSERT(!FLAG_verify_compiler || |
| 259 use->definition()->input_use_list())); | 263 (0 == MembershipCount(use, use->definition()->input_use_list()))); |
| 260 use->set_instruction(phi); | 264 use->set_instruction(phi); |
| 261 use->set_use_index(pred_index); | 265 use->set_use_index(pred_index); |
| 262 use->AddToInputUseList(); | 266 use->AddToInputUseList(); |
| 263 } | 267 } |
| 264 } | 268 } |
| 265 } | 269 } |
| 266 } | 270 } |
| 267 | 271 |
| 268 | 272 |
| 269 void FlowGraph::ComputeUseLists() { | 273 void FlowGraph::ComputeUseLists() { |
| 270 DEBUG_ASSERT(ResetUseLists()); | 274 DEBUG_ASSERT(ResetUseLists()); |
| 271 // Clear initial definitions. | 275 // Clear initial definitions. |
| 272 for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); ++i) { | 276 for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); ++i) { |
| 273 ClearUseLists((*graph_entry_->initial_definitions())[i]); | 277 ClearUseLists((*graph_entry_->initial_definitions())[i]); |
| 274 } | 278 } |
| 275 ComputeUseListsRecursive(graph_entry_); | 279 ComputeUseListsRecursive(graph_entry_); |
| 276 SLOW_ASSERT(ValidateUseLists()); | 280 DEBUG_ASSERT(!FLAG_verify_compiler || ValidateUseLists()); |
| 277 } | 281 } |
| 278 | 282 |
| 279 | 283 |
| 280 void FlowGraph::ComputeSSA(intptr_t next_virtual_register_number) { | 284 void FlowGraph::ComputeSSA(intptr_t next_virtual_register_number) { |
| 281 current_ssa_temp_index_ = next_virtual_register_number; | 285 current_ssa_temp_index_ = next_virtual_register_number; |
| 282 GrowableArray<BitVector*> dominance_frontier; | 286 GrowableArray<BitVector*> dominance_frontier; |
| 283 ComputeDominators(&dominance_frontier); | 287 ComputeDominators(&dominance_frontier); |
| 284 InsertPhis(preorder_, assigned_vars_, dominance_frontier); | 288 InsertPhis(preorder_, assigned_vars_, dominance_frontier); |
| 285 GrowableArray<PhiInstr*> live_phis; | 289 GrowableArray<PhiInstr*> live_phis; |
| 286 // Rename uses to reference inserted phis where appropriate. | 290 // Rename uses to reference inserted phis where appropriate. |
| (...skipping 617 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 904 !it.Done(); | 908 !it.Done(); |
| 905 it.Advance()) { | 909 it.Advance()) { |
| 906 ++size; | 910 ++size; |
| 907 } | 911 } |
| 908 } | 912 } |
| 909 return size; | 913 return size; |
| 910 } | 914 } |
| 911 | 915 |
| 912 | 916 |
| 913 } // namespace dart | 917 } // namespace dart |
| OLD | NEW |