diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index a01e19d..d116905 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -657,18 +657,14 @@
   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 @@
   } 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 @@
       }
     }
     __ 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 1c4b400..328fc93 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -595,22 +595,18 @@
   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 @@
     }
     __ 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 @@
     } 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 cbf0630..5d04ca6 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -483,21 +483,17 @@
   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 @@
     }
     __ 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 @@
     } 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 a0de73d..2d9e35c 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -38,4 +38,21 @@
   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 b2f3f52..d74b624 100644
--- a/compiler/optimizing/instruction_simplifier.h
+++ b/compiler/optimizing/instruction_simplifier.h
@@ -32,6 +32,7 @@
 
  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 013ab72..3ee1afe 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -150,8 +150,7 @@
     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 @@
     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 @@
   }
 }
 
-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 @@
     }
   }
 
-  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 @@
   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 @@
       move = previous->AsParallelMove();
     }
   }
+  DCHECK_EQ(move->GetLifetimePosition(), position);
   move->AddMove(new (allocator_) MoveOperands(source, destination, instruction));
 }
 
@@ -901,7 +885,7 @@
     // 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 @@
   // 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 @@
     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,27 +1009,17 @@
   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));
+                                source->ToLocation(),
+                                destination->ToLocation());
   }
 }
 
-// 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);
-  }
-  return ConvertToLocation(current);
-}
-
 void RegisterAllocator::Resolve() {
   codegen_->ComputeFrameSize(
       spill_slots_.Size(), maximum_number_of_live_registers_, reserved_out_slots_);
@@ -1072,7 +1046,7 @@
       }
     }
 
-    Location source = ConvertToLocation(current);
+    Location source = current->ToLocation();
 
     if (location.IsUnallocated()) {
       if (location.GetPolicy() == Location::kSameAsFirstInput) {
@@ -1112,9 +1086,9 @@
         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 @@
   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 535a768..b7d56e6 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 @@
   // 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 @@
   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 cd13d81..1de90b4 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -297,4 +297,136 @@
   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 c62e61b..e9bd303 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -23,6 +23,8 @@
 
 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 @@
     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 @@
 
   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 @@
     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;
   }