Plug code generator into liveness analysis.
Also implement spill slot support.
Change-Id: If5e28811e9fbbf3842a258772c633318a2f4fafc
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index c367611..50ea00f 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -15,6 +15,8 @@
*/
#include "ssa_liveness_analysis.h"
+
+#include "code_generator.h"
#include "nodes.h"
namespace art {
@@ -80,38 +82,6 @@
order->Add(block);
}
-class HLinearOrderIterator : public ValueObject {
- public:
- explicit HLinearOrderIterator(const GrowableArray<HBasicBlock*>& post_order)
- : post_order_(post_order), index_(post_order.Size()) {}
-
- bool Done() const { return index_ == 0; }
- HBasicBlock* Current() const { return post_order_.Get(index_ -1); }
- void Advance() { --index_; DCHECK_GE(index_, 0U); }
-
- private:
- const GrowableArray<HBasicBlock*>& post_order_;
- size_t index_;
-
- DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator);
-};
-
-class HLinearPostOrderIterator : public ValueObject {
- public:
- explicit HLinearPostOrderIterator(const GrowableArray<HBasicBlock*>& post_order)
- : post_order_(post_order), index_(0) {}
-
- bool Done() const { return index_ == post_order_.Size(); }
- HBasicBlock* Current() const { return post_order_.Get(index_); }
- void Advance() { ++index_; }
-
- private:
- const GrowableArray<HBasicBlock*>& post_order_;
- size_t index_;
-
- DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator);
-};
-
void SsaLivenessAnalysis::LinearizeGraph() {
// For simplicity of the implementation, we create post linear order. The order for
// computing live ranges is the reverse of that order.
@@ -131,30 +101,38 @@
// to differentiate between the start and end of an instruction. Adding 2 to
// the lifetime position for each instruction ensures the start of an
// instruction is different than the end of the previous instruction.
- for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
+ for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
block->SetLifetimeStart(lifetime_position);
for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
- if (current->HasUses()) {
+ current->Accept(codegen_->GetLocationBuilder());
+ LocationSummary* locations = current->GetLocations();
+ if (locations != nullptr && locations->Out().IsValid()) {
instructions_from_ssa_index_.Add(current);
current->SetSsaIndex(ssa_index++);
current->SetLiveInterval(
- new (graph_.GetArena()) LiveInterval(graph_.GetArena(), current->GetType()));
+ new (graph_.GetArena()) LiveInterval(graph_.GetArena(), current->GetType(), current));
}
current->SetLifetimePosition(lifetime_position);
}
lifetime_position += 2;
+ // Add a null marker to notify we are starting a block.
+ instructions_from_lifetime_position_.Add(nullptr);
+
for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
- if (current->HasUses()) {
+ current->Accept(codegen_->GetLocationBuilder());
+ LocationSummary* locations = current->GetLocations();
+ if (locations != nullptr && locations->Out().IsValid()) {
instructions_from_ssa_index_.Add(current);
current->SetSsaIndex(ssa_index++);
current->SetLiveInterval(
- new (graph_.GetArena()) LiveInterval(graph_.GetArena(), current->GetType()));
+ new (graph_.GetArena()) LiveInterval(graph_.GetArena(), current->GetType(), current));
}
+ instructions_from_lifetime_position_.Add(current);
current->SetLifetimePosition(lifetime_position);
lifetime_position += 2;
}
@@ -165,7 +143,7 @@
}
void SsaLivenessAnalysis::ComputeLiveness() {
- for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
+ for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
block_infos_.Put(
block->GetBlockId(),
@@ -186,7 +164,7 @@
void SsaLivenessAnalysis::ComputeLiveRanges() {
// Do a post order visit, adding inputs of instructions live in the block where
// that instruction is defined, and killing instructions that are being visited.
- for (HLinearPostOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
+ for (HLinearPostOrderIterator it(*this); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
BitVector* kill = GetKillSet(*block);
@@ -201,7 +179,7 @@
for (HInstructionIterator it(successor->GetPhis()); !it.Done(); it.Advance()) {
HInstruction* phi = it.Current();
HInstruction* input = phi->InputAt(phi_input_index);
- input->GetLiveInterval()->AddPhiUse(phi, block);
+ input->GetLiveInterval()->AddPhiUse(phi, phi_input_index, block);
// A phi input whose last user is the phi dies at the end of the predecessor block,
// and not at the phi's lifetime position.
live_in->SetBit(input->GetSsaIndex());
@@ -228,7 +206,7 @@
HInstruction* input = current->InputAt(i);
DCHECK(input->HasSsaIndex());
live_in->SetBit(input->GetSsaIndex());
- input->GetLiveInterval()->AddUse(current);
+ input->GetLiveInterval()->AddUse(current, i, false);
}
if (current->HasEnvironment()) {
@@ -239,7 +217,7 @@
if (instruction != nullptr) {
DCHECK(instruction->HasSsaIndex());
live_in->SetBit(instruction->GetSsaIndex());
- instruction->GetLiveInterval()->AddUse(current);
+ instruction->GetLiveInterval()->AddUse(current, i, true);
}
}
}
@@ -251,6 +229,10 @@
if (current->HasSsaIndex()) {
kill->SetBit(current->GetSsaIndex());
live_in->ClearBit(current->GetSsaIndex());
+ LiveInterval* interval = current->GetLiveInterval();
+ DCHECK((interval->GetFirstRange() == nullptr)
+ || (interval->GetStart() == current->GetLifetimePosition()));
+ interval->SetFrom(current->GetLifetimePosition());
}
}