summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--compiler/optimizing/code_generator_arm.cc12
-rw-r--r--compiler/optimizing/code_generator_x86.cc18
-rw-r--r--compiler/optimizing/code_generator_x86_64.cc16
-rw-r--r--compiler/optimizing/instruction_simplifier.cc17
-rw-r--r--compiler/optimizing/instruction_simplifier.h1
-rw-r--r--compiler/optimizing/register_allocator.cc85
-rw-r--r--compiler/optimizing/register_allocator_test.cc253
-rw-r--r--compiler/optimizing/ssa_liveness_analysis.cc132
-rw-r--r--compiler/optimizing/ssa_liveness_analysis.h39
9 files changed, 482 insertions, 91 deletions
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index a01e19d33f..d116905903 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -657,18 +657,14 @@ void LocationsBuilderARM::VisitIf(HIf* if_instr) {
LocationSummary* locations =
new (GetGraph()->GetArena()) LocationSummary(if_instr, LocationSummary::kNoCall);
HInstruction* cond = if_instr->InputAt(0);
- DCHECK(cond->IsCondition());
- HCondition* condition = cond->AsCondition();
- if (condition->NeedsMaterialization()) {
+ if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry);
}
}
void InstructionCodeGeneratorARM::VisitIf(HIf* if_instr) {
HInstruction* cond = if_instr->InputAt(0);
- DCHECK(cond->IsCondition());
- HCondition* condition = cond->AsCondition();
- if (condition->NeedsMaterialization()) {
+ if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
// Condition has been materialized, compare the output to 0
DCHECK(if_instr->GetLocations()->InAt(0).IsRegister());
__ cmp(if_instr->GetLocations()->InAt(0).AsArm().AsCoreRegister(),
@@ -677,7 +673,7 @@ void InstructionCodeGeneratorARM::VisitIf(HIf* if_instr) {
} else {
// Condition has not been materialized, use its inputs as the comparison and its
// condition as the branch condition.
- LocationSummary* locations = condition->GetLocations();
+ LocationSummary* locations = cond->GetLocations();
if (locations->InAt(1).IsRegister()) {
__ cmp(locations->InAt(0).AsArm().AsCoreRegister(),
ShifterOperand(locations->InAt(1).AsArm().AsCoreRegister()));
@@ -694,7 +690,7 @@ void InstructionCodeGeneratorARM::VisitIf(HIf* if_instr) {
}
}
__ b(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()),
- ARMCondition(condition->GetCondition()));
+ ARMCondition(cond->AsCondition()->GetCondition()));
}
if (!codegen_->GoesToNextBlock(if_instr->GetBlock(), if_instr->IfFalseSuccessor())) {
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 1c4b40038d..328fc93ca8 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -595,22 +595,18 @@ void LocationsBuilderX86::VisitIf(HIf* if_instr) {
LocationSummary* locations =
new (GetGraph()->GetArena()) LocationSummary(if_instr, LocationSummary::kNoCall);
HInstruction* cond = if_instr->InputAt(0);
- DCHECK(cond->IsCondition());
- HCondition* condition = cond->AsCondition();
- if (condition->NeedsMaterialization()) {
+ if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
locations->SetInAt(0, Location::Any(), Location::kDiesAtEntry);
}
}
void InstructionCodeGeneratorX86::VisitIf(HIf* if_instr) {
HInstruction* cond = if_instr->InputAt(0);
- DCHECK(cond->IsCondition());
- HCondition* condition = cond->AsCondition();
- if (condition->NeedsMaterialization()) {
+ if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
// Moves do not affect the eflags register, so if the condition is evaluated
// just before the if, we don't need to evaluate it again.
- if (!condition->IsBeforeWhenDisregardMoves(if_instr)) {
- // Materialized condition, compare against 0
+ if (!cond->IsCondition() || !cond->AsCondition()->IsBeforeWhenDisregardMoves(if_instr)) {
+ // Materialized condition, compare against 0.
Location lhs = if_instr->GetLocations()->InAt(0);
if (lhs.IsRegister()) {
__ cmpl(lhs.AsX86().AsCpuRegister(), Immediate(0));
@@ -620,8 +616,8 @@ void InstructionCodeGeneratorX86::VisitIf(HIf* if_instr) {
}
__ j(kNotEqual, codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
} else {
- Location lhs = condition->GetLocations()->InAt(0);
- Location rhs = condition->GetLocations()->InAt(1);
+ Location lhs = cond->GetLocations()->InAt(0);
+ Location rhs = cond->GetLocations()->InAt(1);
// LHS is guaranteed to be in a register (see LocationsBuilderX86::VisitCondition).
if (rhs.IsRegister()) {
__ cmpl(lhs.AsX86().AsCpuRegister(), rhs.AsX86().AsCpuRegister());
@@ -632,7 +628,7 @@ void InstructionCodeGeneratorX86::VisitIf(HIf* if_instr) {
} else {
__ cmpl(lhs.AsX86().AsCpuRegister(), Address(ESP, rhs.GetStackIndex()));
}
- __ j(X86Condition(condition->GetCondition()),
+ __ j(X86Condition(cond->AsCondition()->GetCondition()),
codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
}
if (!codegen_->GoesToNextBlock(if_instr->GetBlock(), if_instr->IfFalseSuccessor())) {
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index cbf0630a3c..5d04ca688f 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -483,21 +483,17 @@ void LocationsBuilderX86_64::VisitIf(HIf* if_instr) {
LocationSummary* locations =
new (GetGraph()->GetArena()) LocationSummary(if_instr, LocationSummary::kNoCall);
HInstruction* cond = if_instr->InputAt(0);
- DCHECK(cond->IsCondition());
- HCondition* condition = cond->AsCondition();
- if (condition->NeedsMaterialization()) {
+ if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
locations->SetInAt(0, Location::Any(), Location::kDiesAtEntry);
}
}
void InstructionCodeGeneratorX86_64::VisitIf(HIf* if_instr) {
HInstruction* cond = if_instr->InputAt(0);
- DCHECK(cond->IsCondition());
- HCondition* condition = cond->AsCondition();
- if (condition->NeedsMaterialization()) {
+ if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
// Moves do not affect the eflags register, so if the condition is evaluated
// just before the if, we don't need to evaluate it again.
- if (!condition->IsBeforeWhenDisregardMoves(if_instr)) {
+ if (!cond->IsCondition() || !cond->AsCondition()->IsBeforeWhenDisregardMoves(if_instr)) {
// Materialized condition, compare against 0.
Location lhs = if_instr->GetLocations()->InAt(0);
if (lhs.IsRegister()) {
@@ -508,8 +504,8 @@ void InstructionCodeGeneratorX86_64::VisitIf(HIf* if_instr) {
}
__ j(kNotEqual, codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
} else {
- Location lhs = condition->GetLocations()->InAt(0);
- Location rhs = condition->GetLocations()->InAt(1);
+ Location lhs = cond->GetLocations()->InAt(0);
+ Location rhs = cond->GetLocations()->InAt(1);
if (rhs.IsRegister()) {
__ cmpl(lhs.AsX86_64().AsCpuRegister(), rhs.AsX86_64().AsCpuRegister());
} else if (rhs.IsConstant()) {
@@ -518,7 +514,7 @@ void InstructionCodeGeneratorX86_64::VisitIf(HIf* if_instr) {
} else {
__ cmpl(lhs.AsX86_64().AsCpuRegister(), Address(CpuRegister(RSP), rhs.GetStackIndex()));
}
- __ j(X86_64Condition(condition->GetCondition()),
+ __ j(X86_64Condition(cond->AsCondition()->GetCondition()),
codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
}
if (!codegen_->GoesToNextBlock(if_instr->GetBlock(), if_instr->IfFalseSuccessor())) {
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index a0de73da32..2d9e35c3b6 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -38,4 +38,21 @@ void InstructionSimplifier::VisitSuspendCheck(HSuspendCheck* check) {
block->RemoveInstruction(check);
}
+void InstructionSimplifier::VisitEqual(HEqual* equal) {
+ HInstruction* input1 = equal->InputAt(0);
+ HInstruction* input2 = equal->InputAt(1);
+ if (input1->GetType() == Primitive::kPrimBoolean && input2->IsIntConstant()) {
+ if (input2->AsIntConstant()->GetValue() == 1) {
+ // Replace (bool_value == 1) with bool_value
+ equal->ReplaceWith(equal->InputAt(0));
+ equal->GetBlock()->RemoveInstruction(equal);
+ } else {
+ // Replace (bool_value == 0) with !bool_value
+ DCHECK_EQ(input2->AsIntConstant()->GetValue(), 0);
+ equal->GetBlock()->ReplaceAndRemoveInstructionWith(
+ equal, new (GetGraph()->GetArena()) HNot(input1));
+ }
+ }
+}
+
} // namespace art
diff --git a/compiler/optimizing/instruction_simplifier.h b/compiler/optimizing/instruction_simplifier.h
index b2f3f521ae..d74b624518 100644
--- a/compiler/optimizing/instruction_simplifier.h
+++ b/compiler/optimizing/instruction_simplifier.h
@@ -32,6 +32,7 @@ class InstructionSimplifier : public HGraphVisitor {
private:
virtual void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE;
+ virtual void VisitEqual(HEqual* equal) OVERRIDE;
};
} // namespace art
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 013ab72c59..3ee1afe7ad 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -150,8 +150,7 @@ void RegisterAllocator::ProcessInstruction(HInstruction* instruction) {
if (temp.IsRegister()) {
BlockRegister(temp, position, position + 1, Primitive::kPrimInt);
} else {
- LiveInterval* interval =
- LiveInterval::MakeTempInterval(allocator_, instruction, Primitive::kPrimInt);
+ LiveInterval* interval = LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt);
temp_intervals_.Add(interval);
interval->AddRange(position, position + 1);
unhandled_core_intervals_.Add(interval);
@@ -486,12 +485,18 @@ bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) {
reg = current->GetRegister();
DCHECK_NE(free_until[reg], 0u);
} else {
- // Pick the register that is free the longest.
- for (size_t i = 0; i < number_of_registers_; ++i) {
- if (IsBlocked(i)) continue;
- if (reg == -1 || free_until[i] > free_until[reg]) {
- reg = i;
- if (free_until[i] == kMaxLifetimePosition) break;
+ int hint = current->FindFirstRegisterHint(free_until);
+ if (hint != kNoRegister) {
+ DCHECK(!IsBlocked(hint));
+ reg = hint;
+ } else {
+ // Pick the register that is free the longest.
+ for (size_t i = 0; i < number_of_registers_; ++i) {
+ if (IsBlocked(i)) continue;
+ if (reg == -1 || free_until[i] > free_until[reg]) {
+ reg = i;
+ if (free_until[i] == kMaxLifetimePosition) break;
+ }
}
}
}
@@ -654,10 +659,6 @@ LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position)
}
}
-static bool NeedTwoSpillSlot(Primitive::Type type) {
- return type == Primitive::kPrimLong || type == Primitive::kPrimDouble;
-}
-
void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) {
LiveInterval* parent = interval->GetParent();
@@ -698,7 +699,7 @@ void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) {
}
}
- if (NeedTwoSpillSlot(parent->GetType())) {
+ if (parent->NeedsTwoSpillSlots()) {
if (slot == spill_slots_.Size()) {
// We need a new spill slot.
spill_slots_.Add(end);
@@ -722,24 +723,6 @@ void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) {
parent->SetSpillSlot((slot + reserved_out_slots_) * kVRegSize);
}
-static Location ConvertToLocation(LiveInterval* interval) {
- if (interval->HasRegister()) {
- return Location::RegisterLocation(ManagedRegister(interval->GetRegister()));
- } else {
- HInstruction* defined_by = interval->GetParent()->GetDefinedBy();
- if (defined_by->IsConstant()) {
- return defined_by->GetLocations()->Out();
- } else {
- DCHECK(interval->GetParent()->HasSpillSlot());
- if (NeedTwoSpillSlot(interval->GetType())) {
- return Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot());
- } else {
- return Location::StackSlot(interval->GetParent()->GetSpillSlot());
- }
- }
- }
-}
-
// We create a special marker for inputs moves to differentiate them from
// moves created during resolution. They must be different instructions
// because the input moves work on the assumption that the interval moves
@@ -825,6 +808,7 @@ void RegisterAllocator::InsertParallelMoveAt(size_t position,
move = previous->AsParallelMove();
}
}
+ DCHECK_EQ(move->GetLifetimePosition(), position);
move->AddMove(new (allocator_) MoveOperands(source, destination, instruction));
}
@@ -901,7 +885,7 @@ void RegisterAllocator::ConnectSiblings(LiveInterval* interval) {
// We spill eagerly, so move must be at definition.
InsertMoveAfter(interval->GetDefinedBy(),
Location::RegisterLocation(ManagedRegister(interval->GetRegister())),
- NeedTwoSpillSlot(interval->GetType())
+ interval->NeedsTwoSpillSlots()
? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot())
: Location::StackSlot(interval->GetParent()->GetSpillSlot()));
}
@@ -910,7 +894,7 @@ void RegisterAllocator::ConnectSiblings(LiveInterval* interval) {
// Walk over all siblings, updating locations of use positions, and
// connecting them when they are adjacent.
do {
- Location source = ConvertToLocation(current);
+ Location source = current->ToLocation();
// Walk over all uses covered by this interval, and update the location
// information.
@@ -935,7 +919,7 @@ void RegisterAllocator::ConnectSiblings(LiveInterval* interval) {
if (next_sibling != nullptr
&& next_sibling->HasRegister()
&& current->GetEnd() == next_sibling->GetStart()) {
- Location destination = ConvertToLocation(next_sibling);
+ Location destination = next_sibling->ToLocation();
InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination);
}
@@ -1025,25 +1009,15 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval,
if (from->GetSuccessors().Size() == 1) {
InsertParallelMoveAtExitOf(from,
interval->GetParent()->GetDefinedBy(),
- ConvertToLocation(source),
- ConvertToLocation(destination));
+ source->ToLocation(),
+ destination->ToLocation());
} else {
DCHECK_EQ(to->GetPredecessors().Size(), 1u);
InsertParallelMoveAtEntryOf(to,
interval->GetParent()->GetDefinedBy(),
- ConvertToLocation(source),
- ConvertToLocation(destination));
- }
-}
-
-// Returns the location of `interval`, or siblings of `interval`, at `position`.
-static Location FindLocationAt(LiveInterval* interval, size_t position) {
- LiveInterval* current = interval;
- while (!current->Covers(position)) {
- current = current->GetNextSibling();
- DCHECK(current != nullptr);
+ source->ToLocation(),
+ destination->ToLocation());
}
- return ConvertToLocation(current);
}
void RegisterAllocator::Resolve() {
@@ -1072,7 +1046,7 @@ void RegisterAllocator::Resolve() {
}
}
- Location source = ConvertToLocation(current);
+ Location source = current->ToLocation();
if (location.IsUnallocated()) {
if (location.GetPolicy() == Location::kSameAsFirstInput) {
@@ -1112,9 +1086,9 @@ void RegisterAllocator::Resolve() {
HBasicBlock* predecessor = current->GetPredecessors().Get(i);
DCHECK_EQ(predecessor->GetSuccessors().Size(), 1u);
HInstruction* input = phi->InputAt(i);
- Location source = FindLocationAt(input->GetLiveInterval(),
- predecessor->GetLastInstruction()->GetLifetimePosition());
- Location destination = ConvertToLocation(phi->GetLiveInterval());
+ Location source = input->GetLiveInterval()->GetLocationAt(
+ predecessor->GetLifetimeEnd() - 1);
+ Location destination = phi->GetLiveInterval()->ToLocation();
InsertParallelMoveAtExitOf(predecessor, nullptr, source, destination);
}
}
@@ -1125,11 +1099,12 @@ void RegisterAllocator::Resolve() {
size_t temp_index = 0;
for (size_t i = 0; i < temp_intervals_.Size(); ++i) {
LiveInterval* temp = temp_intervals_.Get(i);
- if (temp->GetDefinedBy() != current) {
+ HInstruction* at = liveness_.GetTempUser(temp);
+ if (at != current) {
temp_index = 0;
- current = temp->GetDefinedBy();
+ current = at;
}
- LocationSummary* locations = current->GetLocations();
+ LocationSummary* locations = at->GetLocations();
locations->SetTempAt(
temp_index++, Location::RegisterLocation(ManagedRegister(temp->GetRegister())));
}
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index 535a768ea1..b7d56e6571 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -25,6 +25,7 @@
#include "ssa_liveness_analysis.h"
#include "ssa_phi_elimination.h"
#include "utils/arena_allocator.h"
+#include "utils/managed_register.h"
#include "gtest/gtest.h"
@@ -418,17 +419,17 @@ TEST(RegisterAllocatorTest, FreeUntil) {
// Add three temps holding the same register, and starting at different positions.
// Put the one that should be picked in the middle of the inactive list to ensure
// we do not depend on an order.
- LiveInterval* interval = LiveInterval::MakeTempInterval(&allocator, nullptr, Primitive::kPrimInt);
+ LiveInterval* interval = LiveInterval::MakeTempInterval(&allocator, Primitive::kPrimInt);
interval->SetRegister(0);
interval->AddRange(40, 50);
register_allocator.inactive_.Add(interval);
- interval = LiveInterval::MakeTempInterval(&allocator, nullptr, Primitive::kPrimInt);
+ interval = LiveInterval::MakeTempInterval(&allocator, Primitive::kPrimInt);
interval->SetRegister(0);
interval->AddRange(20, 30);
register_allocator.inactive_.Add(interval);
- interval = LiveInterval::MakeTempInterval(&allocator, nullptr, Primitive::kPrimInt);
+ interval = LiveInterval::MakeTempInterval(&allocator, Primitive::kPrimInt);
interval->SetRegister(0);
interval->AddRange(60, 70);
register_allocator.inactive_.Add(interval);
@@ -447,4 +448,250 @@ TEST(RegisterAllocatorTest, FreeUntil) {
ASSERT_EQ(20u, register_allocator.unhandled_->Get(0)->GetStart());
}
+static HGraph* BuildIfElseWithPhi(ArenaAllocator* allocator,
+ HPhi** phi,
+ HInstruction** input1,
+ HInstruction** input2) {
+ HGraph* graph = new (allocator) HGraph(allocator);
+ HBasicBlock* entry = new (allocator) HBasicBlock(graph);
+ graph->AddBlock(entry);
+ graph->SetEntryBlock(entry);
+ HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot);
+ entry->AddInstruction(parameter);
+
+ HBasicBlock* block = new (allocator) HBasicBlock(graph);
+ graph->AddBlock(block);
+ entry->AddSuccessor(block);
+
+ HInstruction* test = new (allocator) HInstanceFieldGet(
+ parameter, Primitive::kPrimBoolean, MemberOffset(22));
+ block->AddInstruction(test);
+ block->AddInstruction(new (allocator) HIf(test));
+ HBasicBlock* then = new (allocator) HBasicBlock(graph);
+ HBasicBlock* else_ = new (allocator) HBasicBlock(graph);
+ HBasicBlock* join = new (allocator) HBasicBlock(graph);
+ graph->AddBlock(then);
+ graph->AddBlock(else_);
+ graph->AddBlock(join);
+
+ block->AddSuccessor(then);
+ block->AddSuccessor(else_);
+ then->AddSuccessor(join);
+ else_->AddSuccessor(join);
+ then->AddInstruction(new (allocator) HGoto());
+ else_->AddInstruction(new (allocator) HGoto());
+
+ *phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
+ join->AddPhi(*phi);
+ *input1 = new (allocator) HInstanceFieldGet(parameter, Primitive::kPrimInt, MemberOffset(42));
+ *input2 = new (allocator) HInstanceFieldGet(parameter, Primitive::kPrimInt, MemberOffset(42));
+ then->AddInstruction(*input1);
+ else_->AddInstruction(*input2);
+ join->AddInstruction(new (allocator) HExit());
+ (*phi)->AddInput(*input1);
+ (*phi)->AddInput(*input2);
+
+ graph->BuildDominatorTree();
+ graph->FindNaturalLoops();
+ return graph;
+}
+
+TEST(RegisterAllocatorTest, PhiHint) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HPhi *phi;
+ HInstruction *input1, *input2;
+
+ {
+ HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
+ x86::CodeGeneratorX86 codegen(graph);
+ SsaLivenessAnalysis liveness(*graph, &codegen);
+ liveness.Analyze();
+
+ // Check that the register allocator is deterministic.
+ RegisterAllocator register_allocator(&allocator, &codegen, liveness);
+ register_allocator.AllocateRegisters();
+
+ ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 0);
+ ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 0);
+ ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 0);
+ }
+
+ {
+ HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
+ x86::CodeGeneratorX86 codegen(graph);
+ SsaLivenessAnalysis liveness(*graph, &codegen);
+ liveness.Analyze();
+
+ // Set the phi to a specific register, and check that the inputs get allocated
+ // the same register.
+ phi->GetLocations()->SetOut(Location::RegisterLocation(ManagedRegister(2)));
+ RegisterAllocator register_allocator(&allocator, &codegen, liveness);
+ register_allocator.AllocateRegisters();
+
+ ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
+ ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
+ ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
+ }
+
+ {
+ HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
+ x86::CodeGeneratorX86 codegen(graph);
+ SsaLivenessAnalysis liveness(*graph, &codegen);
+ liveness.Analyze();
+
+ // Set input1 to a specific register, and check that the phi and other input get allocated
+ // the same register.
+ input1->GetLocations()->SetOut(Location::RegisterLocation(ManagedRegister(2)));
+ RegisterAllocator register_allocator(&allocator, &codegen, liveness);
+ register_allocator.AllocateRegisters();
+
+ ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
+ ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
+ ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
+ }
+
+ {
+ HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
+ x86::CodeGeneratorX86 codegen(graph);
+ SsaLivenessAnalysis liveness(*graph, &codegen);
+ liveness.Analyze();
+
+ // Set input2 to a specific register, and check that the phi and other input get allocated
+ // the same register.
+ input2->GetLocations()->SetOut(Location::RegisterLocation(ManagedRegister(2)));
+ RegisterAllocator register_allocator(&allocator, &codegen, liveness);
+ register_allocator.AllocateRegisters();
+
+ ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
+ ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
+ ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
+ }
+}
+
+static HGraph* BuildFieldReturn(ArenaAllocator* allocator,
+ HInstruction** field,
+ HInstruction** ret) {
+ HGraph* graph = new (allocator) HGraph(allocator);
+ HBasicBlock* entry = new (allocator) HBasicBlock(graph);
+ graph->AddBlock(entry);
+ graph->SetEntryBlock(entry);
+ HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot);
+ entry->AddInstruction(parameter);
+
+ HBasicBlock* block = new (allocator) HBasicBlock(graph);
+ graph->AddBlock(block);
+ entry->AddSuccessor(block);
+
+ *field = new (allocator) HInstanceFieldGet(parameter, Primitive::kPrimInt, MemberOffset(42));
+ block->AddInstruction(*field);
+ *ret = new (allocator) HReturn(*field);
+ block->AddInstruction(*ret);
+
+ HBasicBlock* exit = new (allocator) HBasicBlock(graph);
+ graph->AddBlock(exit);
+ block->AddSuccessor(exit);
+ exit->AddInstruction(new (allocator) HExit());
+ return graph;
+}
+
+TEST(RegisterAllocatorTest, ExpectedInRegisterHint) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HInstruction *field, *ret;
+
+ {
+ HGraph* graph = BuildFieldReturn(&allocator, &field, &ret);
+ x86::CodeGeneratorX86 codegen(graph);
+ SsaLivenessAnalysis liveness(*graph, &codegen);
+ liveness.Analyze();
+
+ RegisterAllocator register_allocator(&allocator, &codegen, liveness);
+ register_allocator.AllocateRegisters();
+
+ // Sanity check that in normal conditions, the register should be hinted to 0 (EAX).
+ ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 0);
+ }
+
+ {
+ HGraph* graph = BuildFieldReturn(&allocator, &field, &ret);
+ x86::CodeGeneratorX86 codegen(graph);
+ SsaLivenessAnalysis liveness(*graph, &codegen);
+ liveness.Analyze();
+
+ // Check that the field gets put in the register expected by its use.
+ ret->GetLocations()->SetInAt(0, Location::RegisterLocation(ManagedRegister(2)));
+
+ RegisterAllocator register_allocator(&allocator, &codegen, liveness);
+ register_allocator.AllocateRegisters();
+
+ ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 2);
+ }
+}
+
+static HGraph* BuildTwoAdds(ArenaAllocator* allocator,
+ HInstruction** first_add,
+ HInstruction** second_add) {
+ HGraph* graph = new (allocator) HGraph(allocator);
+ HBasicBlock* entry = new (allocator) HBasicBlock(graph);
+ graph->AddBlock(entry);
+ graph->SetEntryBlock(entry);
+ HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimInt);
+ HInstruction* constant1 = new (allocator) HIntConstant(0);
+ HInstruction* constant2 = new (allocator) HIntConstant(0);
+ entry->AddInstruction(parameter);
+ entry->AddInstruction(constant1);
+ entry->AddInstruction(constant2);
+
+ HBasicBlock* block = new (allocator) HBasicBlock(graph);
+ graph->AddBlock(block);
+ entry->AddSuccessor(block);
+
+ *first_add = new (allocator) HAdd(Primitive::kPrimInt, parameter, constant1);
+ block->AddInstruction(*first_add);
+ *second_add = new (allocator) HAdd(Primitive::kPrimInt, *first_add, constant2);
+ block->AddInstruction(*second_add);
+
+ block->AddInstruction(new (allocator) HExit());
+ return graph;
+}
+
+TEST(RegisterAllocatorTest, SameAsFirstInputHint) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HInstruction *first_add, *second_add;
+
+ {
+ HGraph* graph = BuildTwoAdds(&allocator, &first_add, &second_add);
+ x86::CodeGeneratorX86 codegen(graph);
+ SsaLivenessAnalysis liveness(*graph, &codegen);
+ liveness.Analyze();
+
+ RegisterAllocator register_allocator(&allocator, &codegen, liveness);
+ register_allocator.AllocateRegisters();
+
+ // Sanity check that in normal conditions, the registers are the same.
+ ASSERT_EQ(first_add->GetLiveInterval()->GetRegister(), 1);
+ ASSERT_EQ(second_add->GetLiveInterval()->GetRegister(), 1);
+ }
+
+ {
+ HGraph* graph = BuildTwoAdds(&allocator, &first_add, &second_add);
+ x86::CodeGeneratorX86 codegen(graph);
+ SsaLivenessAnalysis liveness(*graph, &codegen);
+ liveness.Analyze();
+
+ // check that both adds get the same register.
+ first_add->InputAt(0)->GetLocations()->SetOut(Location::RegisterLocation(ManagedRegister(2)));
+ ASSERT_EQ(first_add->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
+ ASSERT_EQ(second_add->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
+
+ RegisterAllocator register_allocator(&allocator, &codegen, liveness);
+ register_allocator.AllocateRegisters();
+
+ ASSERT_EQ(first_add->GetLiveInterval()->GetRegister(), 2);
+ ASSERT_EQ(second_add->GetLiveInterval()->GetRegister(), 2);
+ }
+}
+
} // namespace art
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index cd13d81a36..1de90b4fd2 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -297,4 +297,136 @@ bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) {
return live_in->UnionIfNotIn(live_out, kill);
}
+int LiveInterval::FindFirstRegisterHint(size_t* free_until) const {
+ if (GetParent() == this && defined_by_ != nullptr) {
+ // This is the first interval for the instruction. Try to find
+ // a register based on its definition.
+ DCHECK_EQ(defined_by_->GetLiveInterval(), this);
+ int hint = FindHintAtDefinition();
+ if (hint != kNoRegister && free_until[hint] > GetStart()) {
+ return hint;
+ }
+ }
+
+ UsePosition* use = first_use_;
+ size_t start = GetStart();
+ size_t end = GetEnd();
+ while (use != nullptr && use->GetPosition() <= end) {
+ size_t use_position = use->GetPosition();
+ if (use_position >= start && !use->GetIsEnvironment()) {
+ HInstruction* user = use->GetUser();
+ size_t input_index = use->GetInputIndex();
+ if (user->IsPhi()) {
+ // If the phi has a register, try to use the same.
+ Location phi_location = user->GetLiveInterval()->ToLocation();
+ if (phi_location.IsRegister() && free_until[phi_location.reg().RegId()] >= use_position) {
+ return phi_location.reg().RegId();
+ }
+ const GrowableArray<HBasicBlock*>& predecessors = user->GetBlock()->GetPredecessors();
+ // If the instruction dies at the phi assignment, we can try having the
+ // same register.
+ if (end == predecessors.Get(input_index)->GetLifetimeEnd()) {
+ for (size_t i = 0, e = user->InputCount(); i < e; ++i) {
+ if (i == input_index) {
+ continue;
+ }
+ HInstruction* input = user->InputAt(i);
+ Location location = input->GetLiveInterval()->GetLocationAt(
+ predecessors.Get(i)->GetLifetimeEnd() - 1);
+ if (location.IsRegister() && free_until[location.reg().RegId()] >= use_position) {
+ return location.reg().RegId();
+ }
+ }
+ }
+ } else {
+ // If the instruction is expected in a register, try to use it.
+ LocationSummary* locations = user->GetLocations();
+ Location expected = locations->InAt(use->GetInputIndex());
+ // We use the user's lifetime position - 1 (and not `use_position`) because the
+ // register is blocked at the beginning of the user.
+ size_t position = user->GetLifetimePosition() - 1;
+ if (expected.IsRegister() && free_until[expected.reg().RegId()] >= position) {
+ return expected.reg().RegId();
+ }
+ }
+ }
+ use = use->GetNext();
+ }
+
+ return kNoRegister;
+}
+
+int LiveInterval::FindHintAtDefinition() const {
+ if (defined_by_->IsPhi()) {
+ // Try to use the same register as one of the inputs.
+ const GrowableArray<HBasicBlock*>& predecessors = defined_by_->GetBlock()->GetPredecessors();
+ for (size_t i = 0, e = defined_by_->InputCount(); i < e; ++i) {
+ HInstruction* input = defined_by_->InputAt(i);
+ size_t end = predecessors.Get(i)->GetLifetimeEnd();
+ const LiveInterval& input_interval = input->GetLiveInterval()->GetIntervalAt(end - 1);
+ if (input_interval.GetEnd() == end) {
+ // If the input dies at the end of the predecessor, we know its register can
+ // be reused.
+ Location input_location = input_interval.ToLocation();
+ if (input_location.IsRegister()) {
+ return input_location.reg().RegId();
+ }
+ }
+ }
+ } else {
+ LocationSummary* locations = GetDefinedBy()->GetLocations();
+ Location out = locations->Out();
+ if (out.IsUnallocated() && out.GetPolicy() == Location::kSameAsFirstInput) {
+ // Try to use the same register as the first input.
+ const LiveInterval& input_interval =
+ GetDefinedBy()->InputAt(0)->GetLiveInterval()->GetIntervalAt(GetStart() - 1);
+ if (input_interval.GetEnd() == GetStart()) {
+ // If the input dies at the start of this instruction, we know its register can
+ // be reused.
+ Location location = input_interval.ToLocation();
+ if (location.IsRegister()) {
+ return location.reg().RegId();
+ }
+ }
+ }
+ }
+ return kNoRegister;
+}
+
+bool LiveInterval::NeedsTwoSpillSlots() const {
+ return type_ == Primitive::kPrimLong || type_ == Primitive::kPrimDouble;
+}
+
+Location LiveInterval::ToLocation() const {
+ if (HasRegister()) {
+ return Location::RegisterLocation(ManagedRegister(GetRegister()));
+ } else {
+ HInstruction* defined_by = GetParent()->GetDefinedBy();
+ if (defined_by->IsConstant()) {
+ return defined_by->GetLocations()->Out();
+ } else if (GetParent()->HasSpillSlot()) {
+ if (NeedsTwoSpillSlots()) {
+ return Location::DoubleStackSlot(GetParent()->GetSpillSlot());
+ } else {
+ return Location::StackSlot(GetParent()->GetSpillSlot());
+ }
+ } else {
+ return Location();
+ }
+ }
+}
+
+Location LiveInterval::GetLocationAt(size_t position) const {
+ return GetIntervalAt(position).ToLocation();
+}
+
+const LiveInterval& LiveInterval::GetIntervalAt(size_t position) const {
+ const LiveInterval* current = this;
+ while (!current->Covers(position)) {
+ current = current->GetNextSibling();
+ DCHECK(current != nullptr);
+ }
+ return *current;
+}
+
} // namespace art
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index c62e61b2cd..e9bd30338d 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -23,6 +23,8 @@ namespace art {
class CodeGenerator;
+static constexpr int kNoRegister = -1;
+
class BlockInfo : public ArenaObject {
public:
BlockInfo(ArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values)
@@ -166,10 +168,8 @@ class LiveInterval : public ArenaObject {
return new (allocator) LiveInterval(allocator, type, nullptr, true, reg, false);
}
- static LiveInterval* MakeTempInterval(ArenaAllocator* allocator,
- HInstruction* defined_by,
- Primitive::Type type) {
- return new (allocator) LiveInterval(allocator, type, defined_by, false, kNoRegister, true);
+ static LiveInterval* MakeTempInterval(ArenaAllocator* allocator, Primitive::Type type) {
+ return new (allocator) LiveInterval(allocator, type, nullptr, false, kNoRegister, true);
}
bool IsFixed() const { return is_fixed_; }
@@ -484,6 +484,31 @@ class LiveInterval : public ArenaObject {
LiveInterval* GetNextSibling() const { return next_sibling_; }
+ // Returns the first register hint that is at least free before
+ // the value contained in `free_until`. If none is found, returns
+ // `kNoRegister`.
+ int FindFirstRegisterHint(size_t* free_until) const;
+
+ // If there is enough at the definition site to find a register (for example
+ // it uses the same input as the first input), returns the register as a hint.
+ // Returns kNoRegister otherwise.
+ int FindHintAtDefinition() const;
+
+ // Returns whether the interval needs two (Dex virtual register size `kVRegSize`)
+ // slots for spilling.
+ bool NeedsTwoSpillSlots() const;
+
+ // Converts the location of the interval to a `Location` object.
+ Location ToLocation() const;
+
+ // Returns the location of the interval following its siblings at `position`.
+ Location GetLocationAt(size_t position) const;
+
+ // Finds the interval that covers `position`.
+ const LiveInterval& GetIntervalAt(size_t position) const;
+
+ bool IsTemp() const { return is_temp_; }
+
private:
ArenaAllocator* const allocator_;
@@ -567,6 +592,12 @@ class SsaLivenessAnalysis : public ValueObject {
return instructions_from_lifetime_position_.Get(index);
}
+ HInstruction* GetTempUser(LiveInterval* temp) const {
+ // A temporary shares the same lifetime start as the instruction that requires it.
+ DCHECK(temp->IsTemp());
+ return GetInstructionFromPosition(temp->GetStart() / 2);
+ }
+
size_t GetMaxLifetimePosition() const {
return instructions_from_lifetime_position_.Size() * 2 - 1;
}
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2026-01-01 11:47:30 +0000