Index: runtime/vm/flow_graph_allocator.cc |
diff --git a/runtime/vm/flow_graph_allocator.cc b/runtime/vm/flow_graph_allocator.cc |
index 553e8866891ae0fab1f67f671c5f1bedf73d88c2..3b5446c2d3f376b4f4afba5f9a8bf705f9c745c8 100644 |
--- a/runtime/vm/flow_graph_allocator.cc |
+++ b/runtime/vm/flow_graph_allocator.cc |
@@ -4,12 +4,174 @@ |
#include "vm/flow_graph_allocator.h" |
+#include "vm/bit_vector.h" |
#include "vm/intermediate_language.h" |
+#include "vm/flow_graph_compiler.h" |
namespace dart { |
+DEFINE_FLAG(bool, print_ssa_liveness, false, |
+ "Print liveness for ssa variables."); |
+ |
+FlowGraphAllocator::FlowGraphAllocator( |
+ const GrowableArray<BlockEntryInstr*>& postorder, |
+ intptr_t max_ssa_temp_index) |
+ : live_out_(postorder.length()), |
+ kill_(postorder.length()), |
+ gen_(postorder.length()), |
+ live_in_(postorder.length()), |
+ postorder_(postorder), |
+ vreg_count_(max_ssa_temp_index) { |
+} |
+ |
+ |
void FlowGraphAllocator::ResolveConstraints() { |
// TODO(fschneider): Resolve register constraints. |
} |
+ |
+static intptr_t ToVirtualRegister(Instruction* instr) { |
+ const Definition* def = instr->AsDefinition(); |
+ if (def == 0) return -1; |
Florian Schneider
2012/06/25 14:38:29
Better def == NULL?
Vyacheslav Egorov (Google)
2012/06/25 16:58:26
Done.
|
+ return def->ssa_temp_index(); |
+} |
srdjan
2012/06/25 17:30:05
return (def == NULL) ? -1 : def->ssa_temp_index();
|
+ |
+ |
+void FlowGraphAllocator::ComputeKillAndGenSets() { |
+ const intptr_t block_count = postorder_.length(); |
+ for (intptr_t i = 0; i < block_count; i++) { |
+ BlockEntryInstr* block = postorder_[i]; |
+ |
+ BitVector* kill = kill_[i]; |
+ BitVector* gen = gen_[i]; |
srdjan
2012/06/25 17:30:05
ASSERT kill and gen are not NULL.
|
+ |
+ if (block->IsJoinEntry()) { |
+ JoinEntryInstr* join = block->AsJoinEntry(); |
+ for (intptr_t j = 0; j < join->phis()->length(); j++) { |
Florian Schneider
2012/06/25 14:38:29
Missing NULL check: join->phis() can be NULL for j
Vyacheslav Egorov (Google)
2012/06/25 16:58:26
Done.
|
+ PhiInstr* phi = (*join->phis())[j]; |
+ if (phi == NULL) continue; |
+ |
+ const intptr_t def = ToVirtualRegister(phi); |
+ if (def >= 0) kill->Add(def); |
+ |
+ for (intptr_t k = 0; k < phi->InputCount(); k++) { |
+ Value* val = phi->InputAt(k); |
+ if (!val->IsUse()) continue; |
+ const intptr_t use = ToVirtualRegister(val->AsUse()->definition()); |
+ if (use >= 0) { |
+ BlockEntryInstr* pred = block->PredecessorAt(k); |
+ live_out_[pred->postorder_number()]->Add(use); |
+ } |
+ } |
+ } |
+ } |
+ |
+ Instruction* current = block->StraightLineSuccessor(); |
+ // TODO(vegorov): iterate backwards. |
+ while ((current != NULL) && !current->IsBlockEntry()) { |
+ for (intptr_t j = 0; j < current->InputCount(); j++) { |
+ Value* input = current->InputAt(j); |
+ if (!input->IsUse()) continue; |
+ const intptr_t use = ToVirtualRegister(input->AsUse()->definition()); |
+ if (use >= 0 && !kill->Contains(use)) gen->Add(use); |
+ } |
+ |
+ const intptr_t def = ToVirtualRegister(current); |
+ if (def >= 0) kill->Add(def); |
+ |
+ current = current->StraightLineSuccessor(); |
+ } |
+ |
+ live_in_[i]->AddAll(gen); |
+ UpdateLiveIn(block); |
+ } |
+} |
+ |
+ |
+bool FlowGraphAllocator::UpdateLiveOut(BlockEntryInstr* instr) { |
+ BitVector* live_out = live_out_[instr->postorder_number()]; |
+ bool changed = false; |
+ Instruction* last = instr->last_instruction(); |
srdjan
2012/06/25 17:30:05
ASSERT (last != NULL, live_out != NULL) ?
Vyacheslav Egorov (Google)
2012/06/25 17:42:23
live_out_ != NULL is a fundamental property of ini
srdjan
2012/06/25 17:51:44
Agree with the fundamental property. SIGSEGV is mu
|
+ for (intptr_t i = 0; i < last->SuccessorCount(); i++) { |
srdjan
2012/06/25 17:30:05
SuccessotCount can be 0 or 1, is a loop necessary?
Vyacheslav Egorov (Google)
2012/06/25 17:42:23
it can be 0, 1 (implicit goto), 2 (branch), 1 + #c
srdjan
2012/06/25 17:51:44
Mea culpa.
|
+ BlockEntryInstr* succ = last->SuccessorAt(i); |
srdjan
2012/06/25 17:30:05
ASSERT(succ != NULL) ?
|
+ if (live_out->AddAll(live_in_[succ->postorder_number()])) { |
+ changed = true; |
+ } |
+ } |
+ return changed; |
+} |
+ |
+ |
+bool FlowGraphAllocator::UpdateLiveIn(BlockEntryInstr* instr) { |
+ BitVector* live_out = live_out_[instr->postorder_number()]; |
+ BitVector* kill = kill_[instr->postorder_number()]; |
+ BitVector* live_in = live_in_[instr->postorder_number()]; |
+ return live_in->KillAndAdd(kill, live_out); |
+} |
+ |
+ |
+void FlowGraphAllocator::ComputeLiveInAndLiveOutSets() { |
+ const intptr_t block_count = postorder_.length(); |
+ bool changed; |
srdjan
2012/06/25 17:30:05
bool changed = false;
|
+ do { |
+ changed = false; |
srdjan
2012/06/25 17:30:05
Remove this line.
Vyacheslav Egorov (Google)
2012/06/25 17:42:23
I need to reset changed to false after each iterat
srdjan
2012/06/25 17:51:44
I negated the condition while reading. Mea Culpa
|
+ |
+ for (intptr_t i = 0; i < block_count; i++) { |
+ BlockEntryInstr* block = postorder_[i]; |
srdjan
2012/06/25 17:30:05
Maybe add comments that you do not need to update
|
+ if (UpdateLiveOut(block) && UpdateLiveIn(block)) { |
+ changed = true; |
+ } |
+ } |
+ } while (changed); |
+} |
+ |
+ |
+void FlowGraphAllocator::AnalyzeLiveness() { |
+ const intptr_t block_count = postorder_.length(); |
+ for (intptr_t i = 0; i < block_count; i++) { |
+ live_out_.Add(new BitVector(vreg_count_)); |
+ kill_.Add(new BitVector(vreg_count_)); |
+ gen_.Add(new BitVector(vreg_count_)); |
+ live_in_.Add(new BitVector(vreg_count_)); |
+ } |
+ |
+ ComputeKillAndGenSets(); |
+ ComputeLiveInAndLiveOutSets(); |
+ |
+ if (FLAG_print_ssa_liveness) { |
+ DumpLiveness(); |
+ } |
+} |
+ |
+ |
+static void PrintBitVector(const char* tag, BitVector* v) { |
+ printf("%s:", tag); |
Florian Schneider
2012/06/25 14:38:29
Use OS::Print instead.
Vyacheslav Egorov (Google)
2012/06/25 16:58:26
Done.
|
+ for (BitVector::Iterator it(v); !it.Done(); it.Advance()) { |
+ printf(" %d", it.Current()); |
Florian Schneider
2012/06/25 14:38:29
OS::Print
Vyacheslav Egorov (Google)
2012/06/25 16:58:26
Done.
|
+ } |
+ printf("\n"); |
Florian Schneider
2012/06/25 14:38:29
OS::Print
Vyacheslav Egorov (Google)
2012/06/25 16:58:26
Done.
|
+} |
+ |
+ |
+void FlowGraphAllocator::DumpLiveness() { |
+ const intptr_t block_count = postorder_.length(); |
+ for (intptr_t i = 0; i < block_count; i++) { |
+ BlockEntryInstr* block = postorder_[i]; |
+ printf("block @%d -> ", block->block_id()); |
srdjan
2012/06/25 17:30:05
OS::Print here as well.
|
+ |
+ Instruction* last = block->last_instruction(); |
+ for (intptr_t j = 0; j < last->SuccessorCount(); j++) { |
+ BlockEntryInstr* succ = last->SuccessorAt(j); |
+ printf(" @%d", succ->block_id()); |
+ } |
+ printf("\n"); |
+ |
+ PrintBitVector(" live out", live_out_[i]); |
+ PrintBitVector(" kill", kill_[i]); |
+ PrintBitVector(" gen", gen_[i]); |
+ PrintBitVector(" live in", live_in_[i]); |
Florian Schneider
2012/06/25 14:38:29
Maybe print in a different order? e.g. live_in, ge
Vyacheslav Egorov (Google)
2012/06/25 16:58:26
We print blocks in post order so printing live out
|
+ } |
+} |
+ |
+ |
} // namespace dart |