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

8 files changed, 108 insertions, 120 deletions

diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index a2cf670..5ff4863 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 041acdf..679763c 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 5fa9305..4a379c1 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 d5f4f90..89c9495 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 1637484..ed5e260 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 dcf70f2..11bcd78 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<Location> inputs_;
   GrowableArray<Location> temps_;
   GrowableArray<Location> environment_;
-  GrowableArray<bool> 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 5055a76..719c069 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 e9bd303..d3e1c0e 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;
       }