Plug code generator into liveness analysis.
Also implement spill slot support.
Change-Id: If5e28811e9fbbf3842a258772c633318a2f4fafc
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index ed3f43c..e888cc1 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -484,7 +484,10 @@
}
void LocationsBuilderARM::VisitIntConstant(HIntConstant* constant) {
- constant->SetLocations(nullptr);
+ // TODO: Support constant locations.
+ LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(constant);
+ locations->SetOut(Location::RequiresRegister());
+ constant->SetLocations(locations);
}
void InstructionCodeGeneratorARM::VisitIntConstant(HIntConstant* constant) {
@@ -492,7 +495,10 @@
}
void LocationsBuilderARM::VisitLongConstant(HLongConstant* constant) {
- constant->SetLocations(nullptr);
+ // TODO: Support constant locations.
+ LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(constant);
+ locations->SetOut(Location::RequiresRegister());
+ constant->SetLocations(locations);
}
void InstructionCodeGeneratorARM::VisitLongConstant(HLongConstant* constant) {
@@ -794,7 +800,12 @@
}
void LocationsBuilderARM::VisitPhi(HPhi* instruction) {
- LOG(FATAL) << "Unimplemented";
+ LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
+ for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
+ locations->SetInAt(i, Location::Any());
+ }
+ locations->SetOut(Location::Any());
+ instruction->SetLocations(locations);
}
void InstructionCodeGeneratorARM::VisitPhi(HPhi* instruction) {
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 8bfd8d6..72c697f 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -494,7 +494,10 @@
}
void LocationsBuilderX86::VisitIntConstant(HIntConstant* constant) {
- constant->SetLocations(nullptr);
+ // TODO: Support constant locations.
+ LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(constant);
+ locations->SetOut(Location::RequiresRegister());
+ constant->SetLocations(locations);
}
void InstructionCodeGeneratorX86::VisitIntConstant(HIntConstant* constant) {
@@ -502,7 +505,10 @@
}
void LocationsBuilderX86::VisitLongConstant(HLongConstant* constant) {
- constant->SetLocations(nullptr);
+ // TODO: Support constant locations.
+ LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(constant);
+ locations->SetOut(Location::RequiresRegister());
+ constant->SetLocations(locations);
}
void InstructionCodeGeneratorX86::VisitLongConstant(HLongConstant* constant) {
@@ -814,7 +820,12 @@
}
void LocationsBuilderX86::VisitPhi(HPhi* instruction) {
- LOG(FATAL) << "Unimplemented";
+ LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction);
+ for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
+ locations->SetInAt(i, Location::Any());
+ }
+ locations->SetOut(Location::Any());
+ instruction->SetLocations(locations);
}
void InstructionCodeGeneratorX86::VisitPhi(HPhi* instruction) {
diff --git a/compiler/optimizing/linearize_test.cc b/compiler/optimizing/linearize_test.cc
index f9ae529..e4f9371 100644
--- a/compiler/optimizing/linearize_test.cc
+++ b/compiler/optimizing/linearize_test.cc
@@ -18,6 +18,7 @@
#include "base/stringprintf.h"
#include "builder.h"
+#include "code_generator.h"
#include "dex_file.h"
#include "dex_instruction.h"
#include "graph_visualizer.h"
@@ -41,8 +42,11 @@
ASSERT_NE(graph, nullptr);
graph->BuildDominatorTree();
+ graph->TransformToSSA();
graph->FindNaturalLoops();
- SsaLivenessAnalysis liveness(*graph);
+
+ CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86);
+ SsaLivenessAnalysis liveness(*graph, codegen);
liveness.Analyze();
ASSERT_EQ(liveness.GetLinearPostOrder().Size(), number_of_blocks);
diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
index 017117a..987c5f2 100644
--- a/compiler/optimizing/live_ranges_test.cc
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -15,6 +15,7 @@
*/
#include "builder.h"
+#include "code_generator.h"
#include "dex_file.h"
#include "dex_instruction.h"
#include "nodes.h"
@@ -56,14 +57,16 @@
ArenaPool pool;
ArenaAllocator allocator(&pool);
HGraph* graph = BuildGraph(data, &allocator);
- SsaLivenessAnalysis liveness(*graph);
+
+ CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86);
+ SsaLivenessAnalysis liveness(*graph, codegen);
liveness.Analyze();
LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
LiveRange* range = interval->GetFirstRange();
ASSERT_EQ(2u, range->GetStart());
// Last use is the return instruction.
- ASSERT_EQ(8u, range->GetEnd());
+ ASSERT_EQ(9u, range->GetEnd());
HBasicBlock* block = graph->GetBlocks().Get(1);
ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr);
ASSERT_EQ(8u, block->GetLastInstruction()->GetLifetimePosition());
@@ -101,14 +104,15 @@
ArenaPool pool;
ArenaAllocator allocator(&pool);
HGraph* graph = BuildGraph(data, &allocator);
- SsaLivenessAnalysis liveness(*graph);
+ CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86);
+ SsaLivenessAnalysis liveness(*graph, codegen);
liveness.Analyze();
LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
LiveRange* range = interval->GetFirstRange();
ASSERT_EQ(2u, range->GetStart());
// Last use is the return instruction.
- ASSERT_EQ(22u, range->GetEnd());
+ ASSERT_EQ(23u, range->GetEnd());
HBasicBlock* block = graph->GetBlocks().Get(3);
ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr);
ASSERT_EQ(22u, block->GetLastInstruction()->GetLifetimePosition());
@@ -149,7 +153,8 @@
ArenaPool pool;
ArenaAllocator allocator(&pool);
HGraph* graph = BuildGraph(data, &allocator);
- SsaLivenessAnalysis liveness(*graph);
+ CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86);
+ SsaLivenessAnalysis liveness(*graph, codegen);
liveness.Analyze();
// Test for the 4 constant.
@@ -181,7 +186,7 @@
range = interval->GetFirstRange();
ASSERT_EQ(22u, liveness.GetInstructionFromSsaIndex(3)->GetLifetimePosition());
ASSERT_EQ(22u, range->GetStart());
- ASSERT_EQ(24u, range->GetEnd());
+ ASSERT_EQ(25u, range->GetEnd());
ASSERT_TRUE(range->GetNext() == nullptr);
}
@@ -224,7 +229,8 @@
ArenaPool pool;
ArenaAllocator allocator(&pool);
HGraph* graph = BuildGraph(data, &allocator);
- SsaLivenessAnalysis liveness(*graph);
+ CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86);
+ SsaLivenessAnalysis liveness(*graph, codegen);
liveness.Analyze();
// Test for the 0 constant.
@@ -249,7 +255,7 @@
range = interval->GetFirstRange();
// The instruction is live until the return instruction after the loop.
ASSERT_EQ(6u, range->GetStart());
- ASSERT_EQ(26u, range->GetEnd());
+ ASSERT_EQ(27u, range->GetEnd());
ASSERT_TRUE(range->GetNext() == nullptr);
// Test for the phi.
@@ -257,7 +263,7 @@
range = interval->GetFirstRange();
// Instruction is consumed by the if.
ASSERT_EQ(14u, range->GetStart());
- ASSERT_EQ(16u, range->GetEnd());
+ ASSERT_EQ(17u, range->GetEnd());
ASSERT_TRUE(range->GetNext() == nullptr);
}
diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc
index 7a33620..2d0bc39 100644
--- a/compiler/optimizing/liveness_test.cc
+++ b/compiler/optimizing/liveness_test.cc
@@ -15,6 +15,7 @@
*/
#include "builder.h"
+#include "code_generator.h"
#include "dex_file.h"
#include "dex_instruction.h"
#include "nodes.h"
@@ -48,7 +49,8 @@
graph->BuildDominatorTree();
graph->TransformToSSA();
graph->FindNaturalLoops();
- SsaLivenessAnalysis liveness(*graph);
+ CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86);
+ SsaLivenessAnalysis liveness(*graph, codegen);
liveness.Analyze();
std::ostringstream buffer;
@@ -69,17 +71,17 @@
TEST(LivenessTest, CFG1) {
const char* expected =
"Block 0\n"
- " live in: ()\n"
- " live out: ()\n"
- " kill: ()\n"
+ " live in: (0)\n"
+ " live out: (0)\n"
+ " kill: (1)\n"
"Block 1\n"
- " live in: ()\n"
- " live out: ()\n"
- " kill: ()\n"
+ " live in: (0)\n"
+ " live out: (0)\n"
+ " kill: (0)\n"
"Block 2\n"
- " live in: ()\n"
- " live out: ()\n"
- " kill: ()\n";
+ " live in: (0)\n"
+ " live out: (0)\n"
+ " kill: (0)\n";
// Constant is not used.
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index dfbb488..3dc0928 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -131,7 +131,7 @@
visualizer.DumpGraph("ssa");
graph->FindNaturalLoops();
- SsaLivenessAnalysis liveness(*graph);
+ SsaLivenessAnalysis liveness(*graph, codegen);
liveness.Analyze();
visualizer.DumpGraph("liveness");
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index dd175d2..8c6eb2a 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -22,6 +22,7 @@
namespace art {
static constexpr size_t kMaxLifetimePosition = -1;
+static constexpr size_t kDefaultNumberOfSpillSlots = 4;
RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, const CodeGenerator& codegen)
: allocator_(allocator),
@@ -30,6 +31,7 @@
handled_(allocator, 0),
active_(allocator, 0),
inactive_(allocator, 0),
+ spill_slots_(allocator, kDefaultNumberOfSpillSlots),
processing_core_registers_(false),
number_of_registers_(-1),
registers_array_(nullptr),
@@ -78,11 +80,39 @@
intervals.Add(instruction->GetLiveInterval());
}
}
- return ValidateIntervals(intervals, codegen_, allocator_, processing_core_registers_,
- log_fatal_on_failure);
+ return ValidateIntervals(intervals, spill_slots_.Size(), codegen_, allocator_,
+ processing_core_registers_, log_fatal_on_failure);
}
-bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& ranges,
+class AllRangesIterator : public ValueObject {
+ public:
+ explicit AllRangesIterator(LiveInterval* interval)
+ : current_interval_(interval),
+ current_range_(interval->GetFirstRange()) {}
+
+ bool Done() const { return current_interval_ == nullptr; }
+ LiveRange* CurrentRange() const { return current_range_; }
+ LiveInterval* CurrentInterval() const { return current_interval_; }
+
+ void Advance() {
+ current_range_ = current_range_->GetNext();
+ if (current_range_ == nullptr) {
+ current_interval_ = current_interval_->GetNextSibling();
+ if (current_interval_ != nullptr) {
+ current_range_ = current_interval_->GetFirstRange();
+ }
+ }
+ }
+
+ private:
+ LiveInterval* current_interval_;
+ LiveRange* current_range_;
+
+ DISALLOW_COPY_AND_ASSIGN(AllRangesIterator);
+};
+
+bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals,
+ size_t number_of_spill_slots,
const CodeGenerator& codegen,
ArenaAllocator* allocator,
bool processing_core_registers,
@@ -90,25 +120,40 @@
size_t number_of_registers = processing_core_registers
? codegen.GetNumberOfCoreRegisters()
: codegen.GetNumberOfFloatingPointRegisters();
- GrowableArray<ArenaBitVector*> bit_vectors(allocator, number_of_registers);
+ GrowableArray<ArenaBitVector*> liveness_of_values(
+ allocator, number_of_registers + number_of_spill_slots);
// Allocate a bit vector per register. A live interval that has a register
// allocated will populate the associated bit vector based on its live ranges.
- for (size_t i = 0; i < number_of_registers; i++) {
- bit_vectors.Add(new (allocator) ArenaBitVector(allocator, 0, true));
+ for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) {
+ liveness_of_values.Add(new (allocator) ArenaBitVector(allocator, 0, true));
}
- for (size_t i = 0, e = ranges.Size(); i < e; ++i) {
- LiveInterval* current = ranges.Get(i);
- do {
- if (!current->HasRegister()) {
- continue;
+ for (size_t i = 0, e = intervals.Size(); i < e; ++i) {
+ for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) {
+ LiveInterval* current = it.CurrentInterval();
+ if (current->GetParent()->HasSpillSlot()) {
+ BitVector* liveness_of_spill_slot = liveness_of_values.Get(
+ number_of_registers + current->GetParent()->GetSpillSlot() / kVRegSize);
+ for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) {
+ if (liveness_of_spill_slot->IsBitSet(j)) {
+ if (log_fatal_on_failure) {
+ std::ostringstream message;
+ message << "Spill slot conflict at " << j;
+ LOG(FATAL) << message.str();
+ } else {
+ return false;
+ }
+ } else {
+ liveness_of_spill_slot->SetBit(j);
+ }
+ }
}
- BitVector* vector = bit_vectors.Get(current->GetRegister());
- LiveRange* range = current->GetFirstRange();
- do {
- for (size_t j = range->GetStart(); j < range->GetEnd(); ++j) {
- if (vector->IsBitSet(j)) {
+
+ if (current->HasRegister()) {
+ BitVector* liveness_of_register = liveness_of_values.Get(current->GetRegister());
+ for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) {
+ if (liveness_of_register->IsBitSet(j)) {
if (log_fatal_on_failure) {
std::ostringstream message;
message << "Register conflict at " << j << " for ";
@@ -122,11 +167,11 @@
return false;
}
} else {
- vector->SetBit(j);
+ liveness_of_register->SetBit(j);
}
}
- } while ((range = range->GetNext()) != nullptr);
- } while ((current = current->GetNextSibling()) != nullptr);
+ }
+ }
}
return true;
}
@@ -270,7 +315,7 @@
bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
size_t first_register_use = current->FirstRegisterUse();
if (current->FirstRegisterUse() == kNoLifetime) {
- // TODO: Allocate spill slot for `current`.
+ AllocateSpillSlotFor(current);
return false;
}
@@ -317,6 +362,7 @@
if (first_register_use >= next_use[reg]) {
// If the first use of that instruction is after the last use of the found
// register, we split this interval just before its first register use.
+ AllocateSpillSlotFor(current);
LiveInterval* split = Split(current, first_register_use - 1);
AddToUnhandled(split);
return false;
@@ -370,9 +416,42 @@
return interval;
} else {
LiveInterval* new_interval = interval->SplitAt(position);
- // TODO: Allocate spill slot for `interval`.
return new_interval;
}
}
+void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) {
+ LiveInterval* parent = interval->GetParent();
+
+ // An instruction gets a spill slot for its entire lifetime. If the parent
+ // of this interval already has a spill slot, there is nothing to do.
+ if (parent->HasSpillSlot()) {
+ return;
+ }
+
+ // Find when this instruction dies.
+ LiveInterval* last_sibling = interval;
+ while (last_sibling->GetNextSibling() != nullptr) {
+ last_sibling = last_sibling->GetNextSibling();
+ }
+ size_t end = last_sibling->GetEnd();
+
+ // Find an available spill slot.
+ size_t slot = 0;
+ for (size_t e = spill_slots_.Size(); slot < e; ++slot) {
+ if (spill_slots_.Get(slot) <= parent->GetStart()) {
+ break;
+ }
+ }
+
+ if (slot == spill_slots_.Size()) {
+ // We need a new spill slot.
+ spill_slots_.Add(end);
+ } else {
+ spill_slots_.Put(slot, end);
+ }
+
+ interval->GetParent()->SetSpillSlot(slot * kVRegSize);
+}
+
} // namespace art
diff --git a/compiler/optimizing/register_allocator.h b/compiler/optimizing/register_allocator.h
index e575b96..3393a04 100644
--- a/compiler/optimizing/register_allocator.h
+++ b/compiler/optimizing/register_allocator.h
@@ -55,6 +55,7 @@
// Helper method for validation. Used by unit testing.
static bool ValidateIntervals(const GrowableArray<LiveInterval*>& intervals,
+ size_t number_of_spill_slots,
const CodeGenerator& codegen,
ArenaAllocator* allocator,
bool processing_core_registers,
@@ -75,6 +76,9 @@
// Returns whether `reg` is blocked by the code generator.
bool IsBlocked(int reg) const;
+ // Allocate a spill slot for the given interval.
+ void AllocateSpillSlotFor(LiveInterval* interval);
+
// Helper methods.
void AllocateRegistersInternal(const SsaLivenessAnalysis& liveness);
bool ValidateInternal(const SsaLivenessAnalysis& liveness, bool log_fatal_on_failure) const;
@@ -98,6 +102,9 @@
// That is, they have a lifetime hole that spans the start of the new interval.
GrowableArray<LiveInterval*> inactive_;
+ // The spill slots allocated for live intervals.
+ GrowableArray<size_t> spill_slots_;
+
// True if processing core registers. False if processing floating
// point registers.
bool processing_core_registers_;
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index 019d0f8..ff9b9be 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -40,9 +40,9 @@
graph->BuildDominatorTree();
graph->TransformToSSA();
graph->FindNaturalLoops();
- SsaLivenessAnalysis liveness(*graph);
- liveness.Analyze();
CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86);
+ SsaLivenessAnalysis liveness(*graph, codegen);
+ liveness.Analyze();
RegisterAllocator register_allocator(&allocator, *codegen);
register_allocator.AllocateRegisters(liveness);
return register_allocator.Validate(liveness, false);
@@ -64,10 +64,12 @@
static constexpr size_t ranges[][2] = {{0, 42}};
intervals.Add(BuildInterval(ranges, arraysize(ranges), &allocator, 0));
intervals.Add(BuildInterval(ranges, arraysize(ranges), &allocator, 1));
- ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false));
+ ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
+ intervals, 0, *codegen, &allocator, true, false));
intervals.Get(1)->SetRegister(0);
- ASSERT_FALSE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false));
+ ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
+ intervals, 0, *codegen, &allocator, true, false));
intervals.Reset();
}
@@ -77,10 +79,12 @@
intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
static constexpr size_t ranges2[][2] = {{42, 43}};
intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
- ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false));
+ ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
+ intervals, 0, *codegen, &allocator, true, false));
intervals.Get(1)->SetRegister(0);
- ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false));
+ ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
+ intervals, 0, *codegen, &allocator, true, false));
intervals.Reset();
}
@@ -90,10 +94,12 @@
intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
static constexpr size_t ranges2[][2] = {{42, 43}};
intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
- ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false));
+ ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
+ intervals, 0, *codegen, &allocator, true, false));
intervals.Get(1)->SetRegister(0);
- ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false));
+ ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
+ intervals, 0, *codegen, &allocator, true, false));
intervals.Reset();
}
@@ -103,10 +109,12 @@
intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
static constexpr size_t ranges2[][2] = {{42, 47}};
intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
- ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false));
+ ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
+ intervals, 0, *codegen, &allocator, true, false));
intervals.Get(1)->SetRegister(0);
- ASSERT_FALSE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false));
+ ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
+ intervals, 0, *codegen, &allocator, true, false));
intervals.Reset();
}
@@ -117,14 +125,17 @@
intervals.Get(0)->SplitAt(43);
static constexpr size_t ranges2[][2] = {{42, 47}};
intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
- ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false));
+ ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
+ intervals, 0, *codegen, &allocator, true, false));
intervals.Get(1)->SetRegister(0);
// Sibling of the first interval has no register allocated to it.
- ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false));
+ ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
+ intervals, 0, *codegen, &allocator, true, false));
intervals.Get(0)->GetNextSibling()->SetRegister(0);
- ASSERT_FALSE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false));
+ ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
+ intervals, 0, *codegen, &allocator, true, false));
}
}
@@ -286,9 +297,9 @@
ArenaPool pool;
ArenaAllocator allocator(&pool);
HGraph* graph = BuildSSAGraph(data, &allocator);
- SsaLivenessAnalysis liveness(*graph);
- liveness.Analyze();
CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86);
+ SsaLivenessAnalysis liveness(*graph, codegen);
+ liveness.Analyze();
RegisterAllocator register_allocator(&allocator, *codegen);
register_allocator.AllocateRegisters(liveness);
ASSERT_TRUE(register_allocator.Validate(liveness, false));
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());
}
}
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 733535e..7903ad6 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -21,6 +21,8 @@
namespace art {
+class CodeGenerator;
+
class BlockInfo : public ArenaObject {
public:
BlockInfo(ArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values)
@@ -87,9 +89,17 @@
*/
class UsePosition : public ArenaObject {
public:
- UsePosition(HInstruction* user, size_t position, UsePosition* next)
- : user_(user), position_(position), next_(next) {
- DCHECK(user->AsPhi() != nullptr || GetPosition() == user->GetLifetimePosition());
+ UsePosition(HInstruction* user,
+ size_t input_index,
+ bool is_environment,
+ size_t position,
+ UsePosition* next)
+ : user_(user),
+ input_index_(input_index),
+ is_environment_(is_environment),
+ position_(position),
+ next_(next) {
+ DCHECK(user->AsPhi() != nullptr || GetPosition() == user->GetLifetimePosition() + 1);
DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
}
@@ -99,12 +109,18 @@
HInstruction* GetUser() const { return user_; }
+ bool GetIsEnvironment() const { return is_environment_; }
+
+ size_t GetInputIndex() const { return input_index_; }
+
void Dump(std::ostream& stream) const {
stream << position_;
}
private:
HInstruction* const user_;
+ const size_t input_index_;
+ const bool is_environment_;
const size_t position_;
UsePosition* const next_;
@@ -117,17 +133,33 @@
*/
class LiveInterval : public ArenaObject {
public:
- LiveInterval(ArenaAllocator* allocator, Primitive::Type type)
+ LiveInterval(ArenaAllocator* allocator, Primitive::Type type, HInstruction* defined_by = nullptr)
: allocator_(allocator),
first_range_(nullptr),
last_range_(nullptr),
first_use_(nullptr),
type_(type),
next_sibling_(nullptr),
- register_(kNoRegister) {}
+ parent_(this),
+ register_(kNoRegister),
+ spill_slot_(kNoSpillSlot),
+ is_fixed_(false),
+ defined_by_(defined_by) {}
- void AddUse(HInstruction* instruction) {
- size_t position = instruction->GetLifetimePosition();
+ static LiveInterval* MakeFixedInterval(ArenaAllocator* allocator, int reg, Primitive::Type type) {
+ LiveInterval* interval = new (allocator) LiveInterval(allocator, type);
+ interval->SetRegister(reg);
+ interval->is_fixed_ = true;
+ return interval;
+ }
+
+ bool IsFixed() const { return is_fixed_; }
+
+ void AddUse(HInstruction* instruction, size_t input_index, bool is_environment) {
+ // Set the use within the instruction.
+ // TODO: Use the instruction's location to know whether the instruction can die
+ // at entry, or needs to say alive within the user.
+ size_t position = instruction->GetLifetimePosition() + 1;
size_t start_block_position = instruction->GetBlock()->GetLifetimeStart();
size_t end_block_position = instruction->GetBlock()->GetLifetimeEnd();
if (first_range_ == nullptr) {
@@ -143,12 +175,14 @@
// There is a hole in the interval. Create a new range.
first_range_ = new (allocator_) LiveRange(start_block_position, position, first_range_);
}
- first_use_ = new (allocator_) UsePosition(instruction, position, first_use_);
+ first_use_ = new (allocator_) UsePosition(
+ instruction, input_index, is_environment, position, first_use_);
}
- void AddPhiUse(HInstruction* instruction, HBasicBlock* block) {
+ void AddPhiUse(HInstruction* instruction, size_t input_index, HBasicBlock* block) {
DCHECK(instruction->AsPhi() != nullptr);
- first_use_ = new (allocator_) UsePosition(instruction, block->GetLifetimeEnd(), first_use_);
+ first_use_ = new (allocator_) UsePosition(
+ instruction, input_index, false, block->GetLifetimeEnd(), first_use_);
}
void AddRange(size_t start, size_t end) {
@@ -178,11 +212,23 @@
}
}
+ bool HasSpillSlot() const { return spill_slot_ != kNoSpillSlot; }
+ void SetSpillSlot(int slot) { spill_slot_ = slot; }
+ int GetSpillSlot() const { return spill_slot_; }
+
void SetFrom(size_t from) {
- DCHECK(first_range_ != nullptr);
- first_range_->start_ = from;
+ if (first_range_ != nullptr) {
+ first_range_->start_ = from;
+ } else {
+ // Instruction without uses.
+ DCHECK(!defined_by_->HasUses());
+ DCHECK(from == defined_by_->GetLifetimePosition());
+ first_range_ = last_range_ = new (allocator_) LiveRange(from, from + 2, nullptr);
+ }
}
+ LiveInterval* GetParent() const { return parent_; }
+
LiveRange* GetFirstRange() const { return first_range_; }
int GetRegister() const { return register_; }
@@ -190,11 +236,11 @@
void ClearRegister() { register_ = kNoRegister; }
bool HasRegister() const { return register_ != kNoRegister; }
- bool IsDeadAt(size_t position) {
+ bool IsDeadAt(size_t position) const {
return last_range_->GetEnd() <= position;
}
- bool Covers(size_t position) {
+ bool Covers(size_t position) const {
LiveRange* current = first_range_;
while (current != nullptr) {
if (position >= current->GetStart() && position < current->GetEnd()) {
@@ -208,27 +254,10 @@
/**
* Returns the first intersection of this interval with `other`.
*/
- size_t FirstIntersectionWith(LiveInterval* other) {
- // We only call this method if there is a lifetime hole in this interval
- // at the start of `other`.
- DCHECK(!Covers(other->GetStart()));
- DCHECK_LE(GetStart(), other->GetStart());
- // Move to the range in this interval that starts after the other interval.
- size_t other_start = other->GetStart();
- LiveRange* my_range = first_range_;
- while (my_range != nullptr) {
- if (my_range->GetStart() >= other_start) {
- break;
- } else {
- my_range = my_range->GetNext();
- }
- }
- if (my_range == nullptr) {
- return kNoLifetime;
- }
-
+ size_t FirstIntersectionWith(LiveInterval* other) const {
// Advance both intervals and find the first matching range start in
// this interval.
+ LiveRange* my_range = first_range_;
LiveRange* other_range = other->first_range_;
do {
if (my_range->IntersectsWith(*other_range)) {
@@ -252,16 +281,33 @@
return first_range_->GetStart();
}
+ size_t GetEnd() const {
+ return last_range_->GetEnd();
+ }
+
size_t FirstRegisterUseAfter(size_t position) const {
+ if (position == GetStart() && defined_by_ != nullptr) {
+ Location location = defined_by_->GetLocations()->Out();
+ // This interval is the first interval of the instruction. If the output
+ // of the instruction requires a register, we return the position of that instruction
+ // as the first register use.
+ if (location.IsUnallocated()) {
+ if ((location.GetPolicy() == Location::kRequiresRegister)
+ || (location.GetPolicy() == Location::kSameAsFirstInput
+ && defined_by_->GetLocations()->InAt(0).GetPolicy() == Location::kRequiresRegister)) {
+ return position;
+ }
+ }
+ }
+
UsePosition* use = first_use_;
while (use != nullptr) {
size_t use_position = use->GetPosition();
- // TODO: Once we plug the Locations builder of the code generator
- // to the register allocator, this method must be adjusted. We
- // test if there is an environment, because these are currently the only
- // instructions that could have more uses than the number of registers.
- if (use_position >= position && !use->GetUser()->NeedsEnvironment()) {
- return use_position;
+ if (use_position >= position && !use->GetIsEnvironment()) {
+ Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex());
+ if (location.IsUnallocated() && location.GetPolicy() == Location::kRequiresRegister) {
+ return use_position;
+ }
}
use = use->GetNext();
}
@@ -272,10 +318,18 @@
return FirstRegisterUseAfter(GetStart());
}
+ UsePosition* GetFirstUse() const {
+ return first_use_;
+ }
+
Primitive::Type GetType() const {
return type_;
}
+ HInstruction* GetDefinedBy() const {
+ return defined_by_;
+ }
+
/**
* Split this interval at `position`. This interval is changed to:
* [start ... position).
@@ -284,7 +338,7 @@
* [position ... end)
*/
LiveInterval* SplitAt(size_t position) {
- DCHECK(next_sibling_ == nullptr);
+ DCHECK(!is_fixed_);
DCHECK_GT(position, GetStart());
if (last_range_->GetEnd() <= position) {
@@ -293,7 +347,9 @@
}
LiveInterval* new_interval = new (allocator_) LiveInterval(allocator_, type_);
+ new_interval->next_sibling_ = next_sibling_;
next_sibling_ = new_interval;
+ new_interval->parent_ = parent_;
new_interval->first_use_ = first_use_;
LiveRange* current = first_range_;
@@ -383,21 +439,36 @@
// Live interval that is the result of a split.
LiveInterval* next_sibling_;
+ // The first interval from which split intervals come from.
+ LiveInterval* parent_;
+
// The register allocated to this interval.
int register_;
+ // The spill slot allocated to this interval.
+ int spill_slot_;
+
+ // Whether the interval is for a fixed register.
+ bool is_fixed_;
+
+ // The instruction represented by this interval.
+ HInstruction* const defined_by_;
+
static constexpr int kNoRegister = -1;
+ static constexpr int kNoSpillSlot = -1;
DISALLOW_COPY_AND_ASSIGN(LiveInterval);
};
class SsaLivenessAnalysis : public ValueObject {
public:
- explicit SsaLivenessAnalysis(const HGraph& graph)
+ SsaLivenessAnalysis(const HGraph& graph, CodeGenerator* codegen)
: graph_(graph),
+ codegen_(codegen),
linear_post_order_(graph.GetArena(), graph.GetBlocks().Size()),
block_infos_(graph.GetArena(), graph.GetBlocks().Size()),
instructions_from_ssa_index_(graph.GetArena(), 0),
+ instructions_from_lifetime_position_(graph.GetArena(), 0),
number_of_ssa_values_(0) {
block_infos_.SetSize(graph.GetBlocks().Size());
}
@@ -424,6 +495,14 @@
return instructions_from_ssa_index_.Get(index);
}
+ HInstruction* GetInstructionFromPosition(size_t index) const {
+ return instructions_from_lifetime_position_.Get(index);
+ }
+
+ size_t GetMaxLifetimePosition() const {
+ return instructions_from_lifetime_position_.Size() * 2 - 1;
+ }
+
size_t GetNumberOfSsaValues() const {
return number_of_ssa_values_;
}
@@ -458,14 +537,52 @@
bool UpdateLiveOut(const HBasicBlock& block);
const HGraph& graph_;
+ CodeGenerator* const codegen_;
GrowableArray<HBasicBlock*> linear_post_order_;
GrowableArray<BlockInfo*> block_infos_;
+
+ // Temporary array used when computing live_in, live_out, and kill sets.
GrowableArray<HInstruction*> instructions_from_ssa_index_;
+
+ // Temporary array used when inserting moves in the graph.
+ GrowableArray<HInstruction*> instructions_from_lifetime_position_;
size_t number_of_ssa_values_;
DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);
};
+class HLinearOrderIterator : public ValueObject {
+ public:
+ explicit HLinearOrderIterator(const SsaLivenessAnalysis& liveness)
+ : post_order_(liveness.GetLinearPostOrder()), index_(liveness.GetLinearPostOrder().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 SsaLivenessAnalysis& liveness)
+ : post_order_(liveness.GetLinearPostOrder()), 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);
+};
+
} // namespace art
#endif // ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_