| 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_allocator.h" | 5 #include "vm/flow_graph_allocator.h" |
| 6 | 6 |
| 7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
| 8 #include "vm/intermediate_language.h" | 8 #include "vm/intermediate_language.h" |
| 9 #include "vm/flow_graph_compiler.h" | 9 #include "vm/flow_graph_compiler.h" |
| 10 | 10 |
| (...skipping 11 matching lines...) Expand all Loading... |
| 22 postorder_(postorder), | 22 postorder_(postorder), |
| 23 vreg_count_(max_ssa_temp_index) { | 23 vreg_count_(max_ssa_temp_index) { |
| 24 } | 24 } |
| 25 | 25 |
| 26 | 26 |
| 27 void FlowGraphAllocator::ResolveConstraints() { | 27 void FlowGraphAllocator::ResolveConstraints() { |
| 28 // TODO(fschneider): Resolve register constraints. | 28 // TODO(fschneider): Resolve register constraints. |
| 29 } | 29 } |
| 30 | 30 |
| 31 | 31 |
| 32 static intptr_t ToVirtualRegister(Instruction* instr) { | |
| 33 const Definition* def = instr->AsDefinition(); | |
| 34 return (def == NULL) ? -1 : def->ssa_temp_index(); | |
| 35 } | |
| 36 | |
| 37 | |
| 38 void FlowGraphAllocator::ComputeInitialSets() { | 32 void FlowGraphAllocator::ComputeInitialSets() { |
| 39 const intptr_t block_count = postorder_.length(); | 33 const intptr_t block_count = postorder_.length(); |
| 40 for (intptr_t i = 0; i < block_count; i++) { | 34 for (intptr_t i = 0; i < block_count; i++) { |
| 41 BlockEntryInstr* block = postorder_[i]; | 35 BlockEntryInstr* block = postorder_[i]; |
| 42 | 36 |
| 43 BitVector* kill = kill_[i]; | 37 BitVector* kill = kill_[i]; |
| 44 BitVector* live_in = live_in_[i]; | 38 BitVector* live_in = live_in_[i]; |
| 45 | 39 |
| 46 if (block->IsJoinEntry()) { | 40 if (block->IsJoinEntry()) { |
| 47 JoinEntryInstr* join = block->AsJoinEntry(); | 41 JoinEntryInstr* join = block->AsJoinEntry(); |
| 48 if (join->phis() != NULL) { | 42 if (join->phis() != NULL) { |
| 49 for (intptr_t j = 0; j < join->phis()->length(); j++) { | 43 for (intptr_t j = 0; j < join->phis()->length(); j++) { |
| 50 PhiInstr* phi = (*join->phis())[j]; | 44 PhiInstr* phi = (*join->phis())[j]; |
| 51 if (phi == NULL) continue; | 45 if (phi == NULL) continue; |
| 52 | 46 kill->Add(phi->ssa_temp_index()); |
| 53 const intptr_t def = ToVirtualRegister(phi); | |
| 54 if (def >= 0) kill->Add(def); | |
| 55 | 47 |
| 56 for (intptr_t k = 0; k < phi->InputCount(); k++) { | 48 for (intptr_t k = 0; k < phi->InputCount(); k++) { |
| 57 Value* val = phi->InputAt(k); | 49 Value* val = phi->InputAt(k); |
| 58 if (!val->IsUse()) continue; | 50 if (val->IsUse()) { |
| 59 const intptr_t use = ToVirtualRegister(val->AsUse()->definition()); | |
| 60 if (use >= 0) { | |
| 61 BlockEntryInstr* pred = block->PredecessorAt(k); | 51 BlockEntryInstr* pred = block->PredecessorAt(k); |
| 52 const intptr_t use = val->AsUse()->definition()->ssa_temp_index(); |
| 62 live_out_[pred->postorder_number()]->Add(use); | 53 live_out_[pred->postorder_number()]->Add(use); |
| 63 } | 54 } |
| 64 } | 55 } |
| 65 } | 56 } |
| 66 } | 57 } |
| 67 } | 58 } |
| 68 | 59 |
| 69 // TODO(vegorov): iterate backwards. | 60 // TODO(vegorov): iterate backwards. |
| 70 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | 61 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
| 71 Instruction* current = it.Current(); | 62 Instruction* current = it.Current(); |
| 72 for (intptr_t j = 0; j < current->InputCount(); j++) { | 63 for (intptr_t j = 0; j < current->InputCount(); j++) { |
| 73 Value* input = current->InputAt(j); | 64 Value* input = current->InputAt(j); |
| 74 if (!input->IsUse()) continue; | 65 if (input->IsUse()) { |
| 75 const intptr_t use = ToVirtualRegister(input->AsUse()->definition()); | 66 const intptr_t use = input->AsUse()->definition()->ssa_temp_index(); |
| 76 if ((use >= 0) && !kill->Contains(use)) live_in->Add(use); | 67 if (!kill->Contains(use)) live_in->Add(use); |
| 68 } |
| 77 } | 69 } |
| 78 | 70 |
| 79 const intptr_t def = ToVirtualRegister(current); | 71 Definition* current_def = current->AsDefinition(); |
| 80 if (def >= 0) kill->Add(def); | 72 if ((current_def != NULL) && (current_def->ssa_temp_index() >= 0)) { |
| 73 kill->Add(current_def->ssa_temp_index()); |
| 74 } |
| 81 } | 75 } |
| 82 } | 76 } |
| 83 | 77 |
| 84 // Update initial live_in sets to match live_out sets. Has to be | 78 // Update initial live_in sets to match live_out sets. Has to be |
| 85 // done in a separate path because of backwards branches. | 79 // done in a separate path because of backwards branches. |
| 86 for (intptr_t i = 0; i < block_count; i++) { | 80 for (intptr_t i = 0; i < block_count; i++) { |
| 87 UpdateLiveIn(postorder_[i]); | 81 UpdateLiveIn(postorder_[i]); |
| 88 } | 82 } |
| 89 } | 83 } |
| 90 | 84 |
| (...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 174 OS::Print("\n"); | 168 OS::Print("\n"); |
| 175 | 169 |
| 176 PrintBitVector(" live out", live_out_[i]); | 170 PrintBitVector(" live out", live_out_[i]); |
| 177 PrintBitVector(" kill", kill_[i]); | 171 PrintBitVector(" kill", kill_[i]); |
| 178 PrintBitVector(" live in", live_in_[i]); | 172 PrintBitVector(" live in", live_in_[i]); |
| 179 } | 173 } |
| 180 } | 174 } |
| 181 | 175 |
| 182 | 176 |
| 183 } // namespace dart | 177 } // namespace dart |
| OLD | NEW |