From 8e3964b766652a0478e8e0e303e8556c997675f1 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Fri, 17 Oct 2014 11:06:38 +0100 Subject: [PATCH] Remove the notion of dies at entry. - Instead, explicitly say that the output does not overlap. - Inputs that must be in a fixed register do die at entry, as we know they have a location that others can not take. - There is also no need to differentiate between an input move and a connecting sibling move - those can be put in the same parallel move instruction. Change-Id: I1b2b2827906601f822b59fb9d6a21d48e43bae27 --- compiler/optimizing/code_generator_arm.cc | 67 +++++++++++++--------------- compiler/optimizing/code_generator_x86.cc | 43 ++++++++---------- compiler/optimizing/code_generator_x86_64.cc | 41 +++++++++-------- compiler/optimizing/live_ranges_test.cc | 14 +++--- compiler/optimizing/locations.cc | 4 +- compiler/optimizing/locations.h | 25 +++++++---- compiler/optimizing/register_allocator.cc | 26 +++-------- compiler/optimizing/ssa_liveness_analysis.h | 8 +++- 8 files changed, 108 insertions(+), 120 deletions(-) diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc index a2cf670b0..5ff486307 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -656,7 +656,7 @@ void LocationsBuilderARM::VisitIf(HIf* if_instr) { new (GetGraph()->GetArena()) LocationSummary(if_instr, LocationSummary::kNoCall); HInstruction* cond = if_instr->InputAt(0); if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) { - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); + locations->SetInAt(0, Location::RequiresRegister()); } } @@ -715,10 +715,10 @@ void InstructionCodeGeneratorARM::VisitIf(HIf* if_instr) { void LocationsBuilderARM::VisitCondition(HCondition* comp) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(comp, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetInAt(1, Location::RegisterOrConstant(comp->InputAt(1)), Location::kDiesAtEntry); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RegisterOrConstant(comp->InputAt(1))); if (comp->NeedsMaterialization()) { - locations->SetOut(Location::RequiresRegister()); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } } @@ -1022,10 +1022,10 @@ void LocationsBuilderARM::VisitAdd(HAdd* add) { switch (add->GetResultType()) { case Primitive::kPrimInt: case Primitive::kPrimLong: { - bool dies_at_entry = add->GetResultType() != Primitive::kPrimLong; - locations->SetInAt(0, Location::RequiresRegister(), dies_at_entry); - locations->SetInAt(1, Location::RegisterOrConstant(add->InputAt(1)), dies_at_entry); - locations->SetOut(Location::RequiresRegister()); + bool output_overlaps = (add->GetResultType() == Primitive::kPrimLong); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RegisterOrConstant(add->InputAt(1))); + locations->SetOut(Location::RequiresRegister(), output_overlaps); break; } @@ -1088,10 +1088,10 @@ void LocationsBuilderARM::VisitSub(HSub* sub) { switch (sub->GetResultType()) { case Primitive::kPrimInt: case Primitive::kPrimLong: { - bool dies_at_entry = sub->GetResultType() != Primitive::kPrimLong; - locations->SetInAt(0, Location::RequiresRegister(), dies_at_entry); - locations->SetInAt(1, Location::RegisterOrConstant(sub->InputAt(1)), dies_at_entry); - locations->SetOut(Location::RequiresRegister()); + bool output_overlaps = (sub->GetResultType() == Primitive::kPrimLong); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RegisterOrConstant(sub->InputAt(1))); + locations->SetOut(Location::RequiresRegister(), output_overlaps); break; } @@ -1150,9 +1150,9 @@ void LocationsBuilderARM::VisitMul(HMul* mul) { switch (mul->GetResultType()) { case Primitive::kPrimInt: case Primitive::kPrimLong: { - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetInAt(1, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RequiresRegister()); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); break; } @@ -1261,8 +1261,8 @@ void InstructionCodeGeneratorARM::VisitParameterValue(HParameterValue* instructi void LocationsBuilderARM::VisitNot(HNot* instruction) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } void InstructionCodeGeneratorARM::VisitNot(HNot* instruction) { @@ -1274,9 +1274,9 @@ void InstructionCodeGeneratorARM::VisitNot(HNot* instruction) { void LocationsBuilderARM::VisitCompare(HCompare* compare) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(compare, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetInAt(1, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RequiresRegister()); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } void InstructionCodeGeneratorARM::VisitCompare(HCompare* compare) { @@ -1332,9 +1332,8 @@ void LocationsBuilderARM::VisitInstanceFieldSet(HInstanceFieldSet* instruction) LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); bool is_object_type = instruction->GetFieldType() == Primitive::kPrimNot; - bool dies_at_entry = !is_object_type; - locations->SetInAt(0, Location::RequiresRegister(), dies_at_entry); - locations->SetInAt(1, Location::RequiresRegister(), dies_at_entry); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RequiresRegister()); // Temporary registers for the write barrier. if (is_object_type) { locations->AddTemp(Location::RequiresRegister()); @@ -1394,8 +1393,8 @@ void InstructionCodeGeneratorARM::VisitInstanceFieldSet(HInstanceFieldSet* instr void LocationsBuilderARM::VisitInstanceFieldGet(HInstanceFieldGet* instruction) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } void InstructionCodeGeneratorARM::VisitInstanceFieldGet(HInstanceFieldGet* instruction) { @@ -1481,10 +1480,9 @@ void InstructionCodeGeneratorARM::VisitNullCheck(HNullCheck* instruction) { void LocationsBuilderARM::VisitArrayGet(HArrayGet* instruction) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetInAt( - 1, Location::RegisterOrConstant(instruction->InputAt(1)), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RegisterOrConstant(instruction->InputAt(1))); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } void InstructionCodeGeneratorARM::VisitArrayGet(HArrayGet* instruction) { @@ -1594,10 +1592,9 @@ void LocationsBuilderARM::VisitArraySet(HArraySet* instruction) { locations->SetInAt(1, Location::RegisterLocation(calling_convention.GetRegisterAt(1))); locations->SetInAt(2, Location::RegisterLocation(calling_convention.GetRegisterAt(2))); } else { - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetInAt( - 1, Location::RegisterOrConstant(instruction->InputAt(1)), Location::kDiesAtEntry); - locations->SetInAt(2, Location::RequiresRegister(), Location::kDiesAtEntry); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RegisterOrConstant(instruction->InputAt(1))); + locations->SetInAt(2, Location::RequiresRegister()); } } @@ -1684,8 +1681,8 @@ void InstructionCodeGeneratorARM::VisitArraySet(HArraySet* instruction) { void LocationsBuilderARM::VisitArrayLength(HArrayLength* instruction) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } void InstructionCodeGeneratorARM::VisitArrayLength(HArrayLength* instruction) { diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index 041acdf91..679763c3c 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -588,7 +588,7 @@ void LocationsBuilderX86::VisitIf(HIf* if_instr) { new (GetGraph()->GetArena()) LocationSummary(if_instr, LocationSummary::kNoCall); HInstruction* cond = if_instr->InputAt(0); if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) { - locations->SetInAt(0, Location::Any(), Location::kDiesAtEntry); + locations->SetInAt(0, Location::Any()); } } @@ -699,8 +699,8 @@ void InstructionCodeGeneratorX86::VisitStoreLocal(HStoreLocal* store) { void LocationsBuilderX86::VisitCondition(HCondition* comp) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(comp, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetInAt(1, Location::Any(), Location::kDiesAtEntry); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::Any()); if (comp->NeedsMaterialization()) { locations->SetOut(Location::RequiresRegister()); } @@ -1279,9 +1279,9 @@ void InstructionCodeGeneratorX86::VisitNot(HNot* instruction) { void LocationsBuilderX86::VisitCompare(HCompare* compare) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(compare, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetInAt(1, Location::Any(), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::Any()); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } void InstructionCodeGeneratorX86::VisitCompare(HCompare* compare) { @@ -1350,12 +1350,11 @@ void LocationsBuilderX86::VisitInstanceFieldSet(HInstanceFieldSet* instruction) || (field_type == Primitive::kPrimByte); // The register allocator does not support multiple // inputs that die at entry with one in a specific register. - bool dies_at_entry = !is_object_type && !is_byte_type; if (is_byte_type) { // Ensure the value is in a byte register. - locations->SetInAt(1, Location::RegisterLocation(EAX), dies_at_entry); + locations->SetInAt(1, Location::RegisterLocation(EAX)); } else { - locations->SetInAt(1, Location::RequiresRegister(), dies_at_entry); + locations->SetInAt(1, Location::RequiresRegister()); } // Temporary registers for the write barrier. if (is_object_type) { @@ -1431,8 +1430,8 @@ void CodeGeneratorX86::MarkGCCard(Register temp, Register card, Register object, void LocationsBuilderX86::VisitInstanceFieldGet(HInstanceFieldGet* instruction) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } void InstructionCodeGeneratorX86::VisitInstanceFieldGet(HInstanceFieldGet* instruction) { @@ -1521,10 +1520,9 @@ void InstructionCodeGeneratorX86::VisitNullCheck(HNullCheck* instruction) { void LocationsBuilderX86::VisitArrayGet(HArrayGet* instruction) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetInAt( - 1, Location::RegisterOrConstant(instruction->InputAt(1)), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RegisterOrConstant(instruction->InputAt(1))); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } void InstructionCodeGeneratorX86::VisitArrayGet(HArrayGet* instruction) { @@ -1637,16 +1635,13 @@ void LocationsBuilderX86::VisitArraySet(HArraySet* instruction) { // We need the inputs to be different than the output in case of long operation. // In case of a byte operation, the register allocator does not support multiple // inputs that die at entry with one in a specific register. - bool dies_at_entry = value_type != Primitive::kPrimLong && !is_byte_type; - locations->SetInAt(0, Location::RequiresRegister(), dies_at_entry); - locations->SetInAt( - 1, Location::RegisterOrConstant(instruction->InputAt(1)), dies_at_entry); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RegisterOrConstant(instruction->InputAt(1))); if (is_byte_type) { // Ensure the value is in a byte register. - locations->SetInAt(2, Location::ByteRegisterOrConstant( - EAX, instruction->InputAt(2)), dies_at_entry); + locations->SetInAt(2, Location::ByteRegisterOrConstant(EAX, instruction->InputAt(2))); } else { - locations->SetInAt(2, Location::RegisterOrConstant(instruction->InputAt(2)), dies_at_entry); + locations->SetInAt(2, Location::RegisterOrConstant(instruction->InputAt(2))); } } } @@ -1776,8 +1771,8 @@ void InstructionCodeGeneratorX86::VisitArraySet(HArraySet* instruction) { void LocationsBuilderX86::VisitArrayLength(HArrayLength* instruction) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); instruction->SetLocations(locations); } diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc index 5fa930512..4a379c124 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -489,7 +489,7 @@ void LocationsBuilderX86_64::VisitIf(HIf* if_instr) { new (GetGraph()->GetArena()) LocationSummary(if_instr, LocationSummary::kNoCall); HInstruction* cond = if_instr->InputAt(0); if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) { - locations->SetInAt(0, Location::Any(), Location::kDiesAtEntry); + locations->SetInAt(0, Location::Any()); } } @@ -598,8 +598,8 @@ void InstructionCodeGeneratorX86_64::VisitStoreLocal(HStoreLocal* store) { void LocationsBuilderX86_64::VisitCondition(HCondition* comp) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(comp, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetInAt(1, Location::Any(), Location::kDiesAtEntry); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::Any()); if (comp->NeedsMaterialization()) { locations->SetOut(Location::RequiresRegister()); } @@ -676,9 +676,9 @@ void InstructionCodeGeneratorX86_64::VisitGreaterThanOrEqual(HGreaterThanOrEqual void LocationsBuilderX86_64::VisitCompare(HCompare* compare) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(compare, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetInAt(1, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RequiresRegister()); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } void InstructionCodeGeneratorX86_64::VisitCompare(HCompare* compare) { @@ -1213,9 +1213,8 @@ void LocationsBuilderX86_64::VisitInstanceFieldSet(HInstanceFieldSet* instructio new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); Primitive::Type field_type = instruction->GetFieldType(); bool is_object_type = field_type == Primitive::kPrimNot; - bool dies_at_entry = !is_object_type; - locations->SetInAt(0, Location::RequiresRegister(), dies_at_entry); - locations->SetInAt(1, Location::RequiresRegister(), dies_at_entry); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetInAt(1, Location::RequiresRegister()); if (is_object_type) { // Temporary registers for the write barrier. locations->AddTemp(Location::RequiresRegister()); @@ -1272,8 +1271,8 @@ void InstructionCodeGeneratorX86_64::VisitInstanceFieldSet(HInstanceFieldSet* in void LocationsBuilderX86_64::VisitInstanceFieldGet(HInstanceFieldGet* instruction) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } void InstructionCodeGeneratorX86_64::VisitInstanceFieldGet(HInstanceFieldGet* instruction) { @@ -1356,10 +1355,10 @@ void InstructionCodeGeneratorX86_64::VisitNullCheck(HNullCheck* instruction) { void LocationsBuilderX86_64::VisitArrayGet(HArrayGet* instruction) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); + locations->SetInAt(0, Location::RequiresRegister()); locations->SetInAt( - 1, Location::RegisterOrConstant(instruction->InputAt(1)), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + 1, Location::RegisterOrConstant(instruction->InputAt(1))); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } void InstructionCodeGeneratorX86_64::VisitArrayGet(HArrayGet* instruction) { @@ -1463,14 +1462,14 @@ void LocationsBuilderX86_64::VisitArraySet(HArraySet* instruction) { locations->SetInAt(1, Location::RegisterLocation(calling_convention.GetRegisterAt(1))); locations->SetInAt(2, Location::RegisterLocation(calling_convention.GetRegisterAt(2))); } else { - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); + locations->SetInAt(0, Location::RequiresRegister()); locations->SetInAt( - 1, Location::RegisterOrConstant(instruction->InputAt(1)), Location::kDiesAtEntry); - locations->SetInAt(2, Location::RequiresRegister(), Location::kDiesAtEntry); + 1, Location::RegisterOrConstant(instruction->InputAt(1))); + locations->SetInAt(2, Location::RequiresRegister()); if (value_type == Primitive::kPrimLong) { - locations->SetInAt(2, Location::RequiresRegister(), Location::kDiesAtEntry); + locations->SetInAt(2, Location::RequiresRegister()); } else { - locations->SetInAt(2, Location::RegisterOrConstant(instruction->InputAt(2)), Location::kDiesAtEntry); + locations->SetInAt(2, Location::RegisterOrConstant(instruction->InputAt(2))); } } } @@ -1582,8 +1581,8 @@ void InstructionCodeGeneratorX86_64::VisitArraySet(HArraySet* instruction) { void LocationsBuilderX86_64::VisitArrayLength(HArrayLength* instruction) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); - locations->SetInAt(0, Location::RequiresRegister(), Location::kDiesAtEntry); - locations->SetOut(Location::RequiresRegister()); + locations->SetInAt(0, Location::RequiresRegister()); + locations->SetOut(Location::RequiresRegister(), Location::kNoOutputOverlap); } void InstructionCodeGeneratorX86_64::VisitArrayLength(HArrayLength* instruction) { diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc index d5f4f902c..89c949563 100644 --- a/compiler/optimizing/live_ranges_test.cc +++ b/compiler/optimizing/live_ranges_test.cc @@ -73,7 +73,7 @@ TEST(LiveRangesTest, CFG1) { LiveRange* range = interval->GetFirstRange(); ASSERT_EQ(2u, range->GetStart()); // Last use is the return instruction. - ASSERT_EQ(9u, range->GetEnd()); + ASSERT_EQ(8u, range->GetEnd()); HBasicBlock* block = graph->GetBlocks().Get(1); ASSERT_TRUE(block->GetLastInstruction()->IsReturn()); ASSERT_EQ(8u, block->GetLastInstruction()->GetLifetimePosition()); @@ -119,7 +119,7 @@ TEST(LiveRangesTest, CFG2) { LiveRange* range = interval->GetFirstRange(); ASSERT_EQ(2u, range->GetStart()); // Last use is the return instruction. - ASSERT_EQ(23u, range->GetEnd()); + ASSERT_EQ(22u, range->GetEnd()); HBasicBlock* block = graph->GetBlocks().Get(3); ASSERT_TRUE(block->GetLastInstruction()->IsReturn()); ASSERT_EQ(22u, block->GetLastInstruction()->GetLifetimePosition()); @@ -193,7 +193,7 @@ TEST(LiveRangesTest, CFG3) { range = interval->GetFirstRange(); ASSERT_EQ(22u, liveness.GetInstructionFromSsaIndex(2)->GetLifetimePosition()); ASSERT_EQ(22u, range->GetStart()); - ASSERT_EQ(25u, range->GetEnd()); + ASSERT_EQ(24u, range->GetEnd()); ASSERT_TRUE(range->GetNext() == nullptr); } @@ -263,7 +263,7 @@ TEST(LiveRangesTest, Loop1) { range = interval->GetFirstRange(); // The instruction is live until the return instruction after the loop. ASSERT_EQ(6u, range->GetStart()); - ASSERT_EQ(27u, range->GetEnd()); + ASSERT_EQ(26u, range->GetEnd()); ASSERT_TRUE(range->GetNext() == nullptr); // Test for the phi. @@ -271,7 +271,7 @@ TEST(LiveRangesTest, Loop1) { 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); } @@ -338,7 +338,7 @@ TEST(LiveRangesTest, Loop2) { range = range->GetNext(); ASSERT_TRUE(range != nullptr); ASSERT_EQ(24u, range->GetStart()); - ASSERT_EQ(27u, range->GetEnd()); + ASSERT_EQ(26u, range->GetEnd()); // Test for the add instruction. HAdd* add = liveness.GetInstructionFromSsaIndex(2)->AsAdd(); @@ -410,7 +410,7 @@ TEST(LiveRangesTest, CFG4) { interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval(); range = interval->GetFirstRange(); ASSERT_EQ(4u, range->GetStart()); - ASSERT_EQ(29u, range->GetEnd()); + ASSERT_EQ(28u, range->GetEnd()); ASSERT_TRUE(range->GetNext() == nullptr); // Test for the first add. diff --git a/compiler/optimizing/locations.cc b/compiler/optimizing/locations.cc index 163748479..ed5e260a5 100644 --- a/compiler/optimizing/locations.cc +++ b/compiler/optimizing/locations.cc @@ -25,16 +25,14 @@ LocationSummary::LocationSummary(HInstruction* instruction, CallKind call_kind) temps_(instruction->GetBlock()->GetGraph()->GetArena(), 0), environment_(instruction->GetBlock()->GetGraph()->GetArena(), instruction->EnvironmentSize()), - dies_at_entry_(instruction->GetBlock()->GetGraph()->GetArena(), instruction->InputCount()), + output_overlaps_(true), call_kind_(call_kind), stack_mask_(nullptr), register_mask_(0), live_registers_() { inputs_.SetSize(instruction->InputCount()); - dies_at_entry_.SetSize(instruction->InputCount()); for (size_t i = 0; i < instruction->InputCount(); ++i) { inputs_.Put(i, Location()); - dies_at_entry_.Put(i, false); } environment_.SetSize(instruction->EnvironmentSize()); for (size_t i = 0; i < instruction->EnvironmentSize(); ++i) { diff --git a/compiler/optimizing/locations.h b/compiler/optimizing/locations.h index dcf70f27b..11bcd7852 100644 --- a/compiler/optimizing/locations.h +++ b/compiler/optimizing/locations.h @@ -34,7 +34,7 @@ class HInstruction; */ class Location : public ValueObject { public: - static constexpr bool kDiesAtEntry = true; + static constexpr bool kNoOutputOverlap = false; enum Kind { kInvalid = 0, @@ -373,8 +373,7 @@ class LocationSummary : public ArenaObject { LocationSummary(HInstruction* instruction, CallKind call_kind = kNoCall); - void SetInAt(uint32_t at, Location location, bool dies_at_entry = false) { - dies_at_entry_.Put(at, dies_at_entry); + void SetInAt(uint32_t at, Location location) { inputs_.Put(at, location); } @@ -386,7 +385,8 @@ class LocationSummary : public ArenaObject { return inputs_.Size(); } - void SetOut(Location location) { + void SetOut(Location location, bool overlaps = true) { + output_overlaps_ = overlaps; output_ = Location(location); } @@ -449,23 +449,30 @@ class LocationSummary : public ArenaObject { return &live_registers_; } - bool InputOverlapsWithOutputOrTemp(uint32_t input, bool is_environment) const { + bool InputOverlapsWithOutputOrTemp(uint32_t input_index, bool is_environment) const { if (is_environment) return true; - Location location = Out(); - if (input == 0 && location.IsUnallocated() && location.GetPolicy() == Location::kSameAsFirstInput) { + if ((input_index == 0) + && output_.IsUnallocated() + && (output_.GetPolicy() == Location::kSameAsFirstInput)) { return false; } - if (dies_at_entry_.Get(input)) { + if (inputs_.Get(input_index).IsRegister() || inputs_.Get(input_index).IsFpuRegister()) { return false; } return true; } + bool OutputOverlapsWithInputs() const { + return output_overlaps_; + } + private: GrowableArray inputs_; GrowableArray temps_; GrowableArray environment_; - GrowableArray dies_at_entry_; + // Whether the output overlaps with any of the inputs. If it overlaps, then it cannot + // share the same register as the inputs. + bool output_overlaps_; Location output_; const CallKind call_kind_; diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc index 5055a7610..719c06972 100644 --- a/compiler/optimizing/register_allocator.cc +++ b/compiler/optimizing/register_allocator.cc @@ -218,6 +218,9 @@ void RegisterAllocator::ProcessInstruction(HInstruction* instruction) { current->SetFrom(position + 1); current->SetRegister(output.reg()); BlockRegister(output, position, position + 1, instruction->GetType()); + } else if (!locations->OutputOverlapsWithInputs()) { + // Shift the interval's start by one to not interfere with the inputs. + current->SetFrom(position + 1); } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { current->SetSpillSlot(output.GetStackIndex()); } @@ -723,15 +726,6 @@ void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { parent->SetSpillSlot((slot + reserved_out_slots_) * kVRegSize); } -// 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 -// have been executed. -static constexpr size_t kInputMoveLifetimePosition = 0; -static bool IsInputMove(HInstruction* instruction) { - return instruction->GetLifetimePosition() == kInputMoveLifetimePosition; -} - static bool IsValidDestination(Location destination) { return destination.IsRegister() || destination.IsStackSlot() || destination.IsDoubleStackSlot(); } @@ -748,14 +742,14 @@ void RegisterAllocator::AddInputMoveFor(HInstruction* user, HParallelMove* move = nullptr; if (previous == nullptr || !previous->IsParallelMove() - || !IsInputMove(previous)) { + || previous->GetLifetimePosition() < user->GetLifetimePosition()) { move = new (allocator_) HParallelMove(allocator_); - move->SetLifetimePosition(kInputMoveLifetimePosition); + move->SetLifetimePosition(user->GetLifetimePosition()); user->GetBlock()->InsertInstructionBefore(move, user); } else { move = previous->AsParallelMove(); } - DCHECK(IsInputMove(move)); + DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition()); move->AddMove(new (allocator_) MoveOperands(source, destination, nullptr)); } @@ -778,7 +772,7 @@ void RegisterAllocator::InsertParallelMoveAt(size_t position, move = at->GetNext()->AsParallelMove(); // This is a parallel move for connecting siblings in a same block. We need to // differentiate it with moves for connecting blocks, and input moves. - if (move == nullptr || IsInputMove(move) || move->GetLifetimePosition() > position) { + if (move == nullptr || move->GetLifetimePosition() > position) { move = new (allocator_) HParallelMove(allocator_); move->SetLifetimePosition(position); at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); @@ -786,12 +780,6 @@ void RegisterAllocator::InsertParallelMoveAt(size_t position, } else { // Move must happen before the instruction. HInstruction* previous = at->GetPrevious(); - if (previous != nullptr && previous->IsParallelMove() && IsInputMove(previous)) { - // This is a parallel move for connecting siblings in a same block. We need to - // differentiate it with input moves. - at = previous; - previous = previous->GetPrevious(); - } if (previous == nullptr || !previous->IsParallelMove() || previous->GetLifetimePosition() != position) { diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h index e9bd30338..d3e1c0e81 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -188,10 +188,14 @@ class LiveInterval : public ArenaObject { && (first_use_->GetPosition() < position)) { // The user uses the instruction multiple times, and one use dies before the other. // We update the use list so that the latter is first. + UsePosition* cursor = first_use_; + while ((cursor->GetNext() != nullptr) && (cursor->GetNext()->GetPosition() < position)) { + cursor = cursor->GetNext(); + } DCHECK(first_use_->GetPosition() + 1 == position); UsePosition* new_use = new (allocator_) UsePosition( - instruction, input_index, is_environment, position, first_use_->GetNext()); - first_use_->SetNext(new_use); + instruction, input_index, is_environment, position, cursor->GetNext()); + cursor->SetNext(new_use); if (first_range_->GetEnd() == first_use_->GetPosition()) { first_range_->end_ = position; } -- 2.11.0