Final CL to enable register allocation on x86.

This CL implements:
1) Resolution after allocation: connecting the locations
   allocated to an interval within a block and between blocks.
2) Handling of fixed registers: some instructions require
   inputs/output to be at a specific location, and the allocator
   needs to deal with them in a special way.
3) ParallelMoveResolver::EmitNativeCode for x86.

Change-Id: I0da6bd7eb66877987148b87c3be6a983b4e3f858

21 files changed, 1103 insertions, 160 deletions

diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index beafbcc386..f05cb66aba 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -29,30 +29,60 @@
 
 namespace art {
 
-void CodeGenerator::Compile(CodeAllocator* allocator) {
+void CodeGenerator::CompileBaseline(CodeAllocator* allocator) {
   const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
   DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
   DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
+  block_labels_.SetSize(blocks.Size());
+
+  DCHECK_EQ(frame_size_, kUninitializedFrameSize);
+  ComputeFrameSize(GetGraph()->GetMaximumNumberOfOutVRegs()
+                   + GetGraph()->GetNumberOfVRegs()
+                   + 1 /* filler */);
   GenerateFrameEntry();
+
   for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
-    CompileBlock(blocks.Get(i));
+    HBasicBlock* block = blocks.Get(i);
+    Bind(GetLabelOf(block));
+    HGraphVisitor* location_builder = GetLocationBuilder();
+    HGraphVisitor* instruction_visitor = GetInstructionVisitor();
+    for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+      HInstruction* current = it.Current();
+      current->Accept(location_builder);
+      InitLocations(current);
+      current->Accept(instruction_visitor);
+    }
   }
+
   size_t code_size = GetAssembler()->CodeSize();
   uint8_t* buffer = allocator->Allocate(code_size);
   MemoryRegion code(buffer, code_size);
   GetAssembler()->FinalizeInstructions(code);
 }
 
-void CodeGenerator::CompileBlock(HBasicBlock* block) {
-  Bind(GetLabelOf(block));
-  HGraphVisitor* location_builder = GetLocationBuilder();
-  HGraphVisitor* instruction_visitor = GetInstructionVisitor();
-  for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
-    HInstruction* current = it.Current();
-    current->Accept(location_builder);
-    InitLocations(current);
-    current->Accept(instruction_visitor);
+void CodeGenerator::CompileOptimized(CodeAllocator* allocator) {
+  // The frame size has already been computed during register allocation.
+  DCHECK_NE(frame_size_, kUninitializedFrameSize);
+  const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
+  DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
+  DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
+  block_labels_.SetSize(blocks.Size());
+
+  GenerateFrameEntry();
+  for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
+    HBasicBlock* block = blocks.Get(i);
+    Bind(GetLabelOf(block));
+    HGraphVisitor* instruction_visitor = GetInstructionVisitor();
+    for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+      HInstruction* current = it.Current();
+      current->Accept(instruction_visitor);
+    }
   }
+
+  size_t code_size = GetAssembler()->CodeSize();
+  uint8_t* buffer = allocator->Allocate(code_size);
+  MemoryRegion code(buffer, code_size);
+  GetAssembler()->FinalizeInstructions(code);
 }
 
 size_t CodeGenerator::AllocateFreeRegisterInternal(
diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h
index e197ccd517..82fa6393e0 100644
--- a/compiler/optimizing/code_generator.h
+++ b/compiler/optimizing/code_generator.h
@@ -28,6 +28,7 @@
 namespace art {
 
 static size_t constexpr kVRegSize = 4;
+static size_t constexpr kUninitializedFrameSize = 0;
 
 class DexCompilationUnit;
 
@@ -51,7 +52,8 @@ class CodeGenerator : public ArenaObject {
  public:
   // Compiles the graph to executable instructions. Returns whether the compilation
   // succeeded.
-  void Compile(CodeAllocator* allocator);
+  void CompileBaseline(CodeAllocator* allocator);
+  void CompileOptimized(CodeAllocator* allocator);
   static CodeGenerator* Create(ArenaAllocator* allocator,
                                HGraph* graph,
                                InstructionSet instruction_set);
@@ -61,6 +63,14 @@ class CodeGenerator : public ArenaObject {
   Label* GetLabelOf(HBasicBlock* block) const;
   bool GoesToNextBlock(HBasicBlock* current, HBasicBlock* next) const;
 
+  size_t GetStackSlotOfParameter(HParameterValue* parameter) const {
+    // Note that this follows the current calling convention.
+    return GetFrameSize()
+        + kVRegSize  // Art method
+        + (parameter->GetIndex() - graph_->GetNumberOfVRegs() + graph_->GetNumberOfInVRegs())
+          * kVRegSize;
+  }
+
   virtual void GenerateFrameEntry() = 0;
   virtual void GenerateFrameExit() = 0;
   virtual void Bind(Label* label) = 0;
@@ -69,6 +79,7 @@ class CodeGenerator : public ArenaObject {
   virtual HGraphVisitor* GetInstructionVisitor() = 0;
   virtual Assembler* GetAssembler() = 0;
   virtual size_t GetWordSize() const = 0;
+  virtual void ComputeFrameSize(size_t number_of_spill_slots) = 0;
 
   uint32_t GetFrameSize() const { return frame_size_; }
   void SetFrameSize(uint32_t size) { frame_size_ = size; }
@@ -95,14 +106,12 @@ class CodeGenerator : public ArenaObject {
 
  protected:
   CodeGenerator(HGraph* graph, size_t number_of_registers)
-      : frame_size_(0),
+      : frame_size_(kUninitializedFrameSize),
         graph_(graph),
         block_labels_(graph->GetArena(), 0),
         pc_infos_(graph->GetArena(), 32),
-        blocked_registers_(graph->GetArena()->AllocArray<bool>(number_of_registers)) {
-    block_labels_.SetSize(graph->GetBlocks().Size());
-  }
-  ~CodeGenerator() { }
+        blocked_registers_(graph->GetArena()->AllocArray<bool>(number_of_registers)) {}
+  ~CodeGenerator() {}
 
   // Register allocation logic.
   void AllocateRegistersLocally(HInstruction* instruction) const;
@@ -123,7 +132,6 @@ class CodeGenerator : public ArenaObject {
 
  private:
   void InitLocations(HInstruction* instruction);
-  void CompileBlock(HBasicBlock* block);
 
   HGraph* const graph_;
 
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index e888cc1d6e..d61df36ca9 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -129,16 +129,18 @@ InstructionCodeGeneratorARM::InstructionCodeGeneratorARM(HGraph* graph, CodeGene
         assembler_(codegen->GetAssembler()),
         codegen_(codegen) {}
 
+void CodeGeneratorARM::ComputeFrameSize(size_t number_of_spill_slots) {
+  SetFrameSize(RoundUp(
+      number_of_spill_slots * kVRegSize
+      + kVRegSize  // Art method
+      + kNumberOfPushedRegistersAtEntry * kArmWordSize,
+      kStackAlignment));
+}
+
 void CodeGeneratorARM::GenerateFrameEntry() {
   core_spill_mask_ |= (1 << LR);
   __ PushList((1 << LR));
 
-  SetFrameSize(RoundUp(
-      (GetGraph()->GetMaximumNumberOfOutVRegs() + GetGraph()->GetNumberOfVRegs()) * kVRegSize
-      + kVRegSize  // filler
-      + kArmWordSize  // Art method
-      + kNumberOfPushedRegistersAtEntry * kArmWordSize,
-      kStackAlignment));
   // The return PC has already been pushed on the stack.
   __ AddConstant(SP, -(GetFrameSize() - kNumberOfPushedRegistersAtEntry * kArmWordSize));
   __ str(R0, Address(SP, 0));
diff --git a/compiler/optimizing/code_generator_arm.h b/compiler/optimizing/code_generator_arm.h
index c945a06d47..ac5ef212ba 100644
--- a/compiler/optimizing/code_generator_arm.h
+++ b/compiler/optimizing/code_generator_arm.h
@@ -104,6 +104,7 @@ class CodeGeneratorARM : public CodeGenerator {
   explicit CodeGeneratorARM(HGraph* graph);
   virtual ~CodeGeneratorARM() { }
 
+  virtual void ComputeFrameSize(size_t number_of_spill_slots) OVERRIDE;
   virtual void GenerateFrameEntry() OVERRIDE;
   virtual void GenerateFrameExit() OVERRIDE;
   virtual void Bind(Label* label) OVERRIDE;
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 72c697ffee..c7dca86dab 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -48,7 +48,16 @@ void CodeGeneratorX86::DumpFloatingPointRegister(std::ostream& stream, int reg)
 CodeGeneratorX86::CodeGeneratorX86(HGraph* graph)
     : CodeGenerator(graph, kNumberOfRegIds),
       location_builder_(graph, this),
-      instruction_visitor_(graph, this) {}
+      instruction_visitor_(graph, this),
+      move_resolver_(graph->GetArena(), this) {}
+
+void CodeGeneratorX86::ComputeFrameSize(size_t number_of_spill_slots) {
+  SetFrameSize(RoundUp(
+      number_of_spill_slots * kVRegSize
+      + kVRegSize  // Art method
+      + kNumberOfPushedRegistersAtEntry * kX86WordSize,
+      kStackAlignment));
+}
 
 static bool* GetBlockedRegisterPairs(bool* blocked_registers) {
   return blocked_registers + kNumberOfAllocIds;
@@ -125,13 +134,6 @@ void CodeGeneratorX86::GenerateFrameEntry() {
   static const int kFakeReturnRegister = 8;
   core_spill_mask_ |= (1 << kFakeReturnRegister);
 
-  SetFrameSize(RoundUp(
-      (GetGraph()->GetMaximumNumberOfOutVRegs() + GetGraph()->GetNumberOfVRegs()) * kVRegSize
-      + kVRegSize  // filler
-      + kX86WordSize  // Art method
-      + kNumberOfPushedRegistersAtEntry * kX86WordSize,
-      kStackAlignment));
-
   // The return PC has already been pushed on the stack.
   __ subl(ESP, Immediate(GetFrameSize() - kNumberOfPushedRegistersAtEntry * kX86WordSize));
   __ movl(Address(ESP, kCurrentMethodStackOffset), EAX);
@@ -264,8 +266,8 @@ void CodeGeneratorX86::Move32(Location destination, Location source) {
       __ movl(Address(ESP, destination.GetStackIndex()), source.AsX86().AsCpuRegister());
     } else {
       DCHECK(source.IsStackSlot());
-      __ movl(EAX, Address(ESP, source.GetStackIndex()));
-      __ movl(Address(ESP, destination.GetStackIndex()), EAX);
+      __ pushl(Address(ESP, source.GetStackIndex()));
+      __ popl(Address(ESP, destination.GetStackIndex()));
     }
   }
 }
@@ -302,8 +304,8 @@ void CodeGeneratorX86::Move64(Location destination, Location source) {
       DCHECK(source.IsDoubleStackSlot());
       __ movl(calling_convention.GetRegisterAt(argument_index),
               Address(ESP, source.GetStackIndex()));
-      __ movl(EAX, Address(ESP, source.GetHighStackIndex(kX86WordSize)));
-      __ movl(Address(ESP, calling_convention.GetStackOffsetOf(argument_index + 1, kX86WordSize)), EAX);
+      __ pushl(Address(ESP, source.GetHighStackIndex(kX86WordSize)));
+      __ popl(Address(ESP, calling_convention.GetStackOffsetOf(argument_index + 1, kX86WordSize)));
     }
   } else {
     if (source.IsRegister()) {
@@ -315,15 +317,15 @@ void CodeGeneratorX86::Move64(Location destination, Location source) {
       uint32_t argument_index = source.GetQuickParameterIndex();
       __ movl(Address(ESP, destination.GetStackIndex()),
               calling_convention.GetRegisterAt(argument_index));
-      __ movl(EAX, Address(ESP,
+      __ pushl(Address(ESP,
           calling_convention.GetStackOffsetOf(argument_index + 1, kX86WordSize) + GetFrameSize()));
-      __ movl(Address(ESP, destination.GetHighStackIndex(kX86WordSize)), EAX);
+      __ popl(Address(ESP, destination.GetHighStackIndex(kX86WordSize)));
     } else {
       DCHECK(source.IsDoubleStackSlot());
-      __ movl(EAX, Address(ESP, source.GetStackIndex()));
-      __ movl(Address(ESP, destination.GetStackIndex()), EAX);
-      __ movl(EAX, Address(ESP, source.GetHighStackIndex(kX86WordSize)));
-      __ movl(Address(ESP, destination.GetHighStackIndex(kX86WordSize)), EAX);
+      __ pushl(Address(ESP, source.GetStackIndex()));
+      __ popl(Address(ESP, destination.GetStackIndex()));
+      __ pushl(Address(ESP, source.GetHighStackIndex(kX86WordSize)));
+      __ popl(Address(ESP, destination.GetHighStackIndex(kX86WordSize)));
     }
   }
 }
@@ -501,7 +503,7 @@ void LocationsBuilderX86::VisitIntConstant(HIntConstant* constant) {
 }
 
 void InstructionCodeGeneratorX86::VisitIntConstant(HIntConstant* constant) {
-  // Will be generated at use site.
+  codegen_->Move(constant, constant->GetLocations()->Out(), nullptr);
 }
 
 void LocationsBuilderX86::VisitLongConstant(HLongConstant* constant) {
@@ -573,7 +575,7 @@ void InstructionCodeGeneratorX86::VisitReturn(HReturn* ret) {
 
 void LocationsBuilderX86::VisitInvokeStatic(HInvokeStatic* invoke) {
   LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(invoke);
-  locations->AddTemp(Location::RequiresRegister());
+  locations->AddTemp(X86CpuLocation(EAX));
 
   InvokeDexCallingConventionVisitor calling_convention_visitor;
   for (size_t i = 0; i < invoke->InputCount(); i++) {
@@ -802,7 +804,6 @@ void LocationsBuilderX86::VisitParameterValue(HParameterValue* instruction) {
 }
 
 void InstructionCodeGeneratorX86::VisitParameterValue(HParameterValue* instruction) {
-  // Nothing to do, the parameter is already at its location.
 }
 
 void LocationsBuilderX86::VisitNot(HNot* instruction) {
@@ -829,15 +830,100 @@ void LocationsBuilderX86::VisitPhi(HPhi* instruction) {
 }
 
 void InstructionCodeGeneratorX86::VisitPhi(HPhi* instruction) {
-  LOG(FATAL) << "Unimplemented";
+  LOG(FATAL) << "Unreachable";
 }
 
 void LocationsBuilderX86::VisitParallelMove(HParallelMove* instruction) {
-  LOG(FATAL) << "Unimplemented";
+  LOG(FATAL) << "Unreachable";
 }
 
 void InstructionCodeGeneratorX86::VisitParallelMove(HParallelMove* instruction) {
-  LOG(FATAL) << "Unimplemented";
+  codegen_->GetMoveResolver()->EmitNativeCode(instruction);
+}
+
+X86Assembler* ParallelMoveResolverX86::GetAssembler() const {
+  return codegen_->GetAssembler();
+}
+
+void ParallelMoveResolverX86::MoveMemoryToMemory(int dst, int src) {
+  ScratchRegisterScope ensure_scratch(
+      this, kNoRegister, codegen_->GetNumberOfCoreRegisters());
+  int stack_offset = ensure_scratch.IsSpilled() ? kX86WordSize : 0;
+  __ movl(static_cast<Register>(ensure_scratch.GetRegister()), Address(ESP, src + stack_offset));
+  __ movl(Address(ESP, dst + stack_offset), static_cast<Register>(ensure_scratch.GetRegister()));
+}
+
+void ParallelMoveResolverX86::EmitMove(size_t index) {
+  MoveOperands* move = moves_.Get(index);
+  Location source = move->GetSource();
+  Location destination = move->GetDestination();
+
+  if (source.IsRegister()) {
+    if (destination.IsRegister()) {
+      __ movl(destination.AsX86().AsCpuRegister(), source.AsX86().AsCpuRegister());
+    } else {
+      DCHECK(destination.IsStackSlot());
+      __ movl(Address(ESP, destination.GetStackIndex()), source.AsX86().AsCpuRegister());
+    }
+  } else if (source.IsStackSlot()) {
+    if (destination.IsRegister()) {
+      __ movl(destination.AsX86().AsCpuRegister(), Address(ESP, source.GetStackIndex()));
+    } else {
+      DCHECK(destination.IsStackSlot());
+      MoveMemoryToMemory(destination.GetStackIndex(),
+                         source.GetStackIndex());
+    }
+  } else {
+    LOG(FATAL) << "Unimplemented";
+  }
+}
+
+void ParallelMoveResolverX86::Exchange(Register reg, int mem) {
+  ScratchRegisterScope ensure_scratch(this, reg, codegen_->GetNumberOfCoreRegisters());
+  int stack_offset = ensure_scratch.IsSpilled() ? kX86WordSize : 0;
+  __ movl(static_cast<Register>(ensure_scratch.GetRegister()), Address(ESP, mem + stack_offset));
+  __ movl(Address(ESP, mem + stack_offset), reg);
+  __ movl(reg, static_cast<Register>(ensure_scratch.GetRegister()));
+}
+
+
+void ParallelMoveResolverX86::Exchange(int mem1, int mem2) {
+  ScratchRegisterScope ensure_scratch1(
+      this, kNoRegister, codegen_->GetNumberOfCoreRegisters());
+  ScratchRegisterScope ensure_scratch2(
+      this, ensure_scratch1.GetRegister(), codegen_->GetNumberOfCoreRegisters());
+  int stack_offset = ensure_scratch1.IsSpilled() ? kX86WordSize : 0;
+  stack_offset += ensure_scratch2.IsSpilled() ? kX86WordSize : 0;
+  __ movl(static_cast<Register>(ensure_scratch1.GetRegister()), Address(ESP, mem1 + stack_offset));
+  __ movl(static_cast<Register>(ensure_scratch2.GetRegister()), Address(ESP, mem2 + stack_offset));
+  __ movl(Address(ESP, mem2 + stack_offset), static_cast<Register>(ensure_scratch1.GetRegister()));
+  __ movl(Address(ESP, mem1 + stack_offset), static_cast<Register>(ensure_scratch2.GetRegister()));
+}
+
+void ParallelMoveResolverX86::EmitSwap(size_t index) {
+  MoveOperands* move = moves_.Get(index);
+  Location source = move->GetSource();
+  Location destination = move->GetDestination();
+
+  if (source.IsRegister() && destination.IsRegister()) {
+    __ xchgl(destination.AsX86().AsCpuRegister(), source.AsX86().AsCpuRegister());
+  } else if (source.IsRegister() && destination.IsStackSlot()) {
+    Exchange(source.AsX86().AsCpuRegister(), destination.GetStackIndex());
+  } else if (source.IsStackSlot() && destination.IsRegister()) {
+    Exchange(destination.AsX86().AsCpuRegister(), source.GetStackIndex());
+  } else if (source.IsStackSlot() && destination.IsStackSlot()) {
+    Exchange(destination.GetStackIndex(), source.GetStackIndex());
+  } else {
+    LOG(FATAL) << "Unimplemented";
+  }
+}
+
+void ParallelMoveResolverX86::SpillScratch(int reg) {
+  __ pushl(static_cast<Register>(reg));
+}
+
+void ParallelMoveResolverX86::RestoreScratch(int reg) {
+  __ popl(static_cast<Register>(reg));
 }
 
 }  // namespace x86
diff --git a/compiler/optimizing/code_generator_x86.h b/compiler/optimizing/code_generator_x86.h
index 4a706363b2..acc670e09b 100644
--- a/compiler/optimizing/code_generator_x86.h
+++ b/compiler/optimizing/code_generator_x86.h
@@ -19,6 +19,7 @@
 
 #include "code_generator.h"
 #include "nodes.h"
+#include "parallel_move_resolver.h"
 #include "utils/x86/assembler_x86.h"
 
 namespace art {
@@ -59,6 +60,28 @@ class InvokeDexCallingConventionVisitor {
   DISALLOW_COPY_AND_ASSIGN(InvokeDexCallingConventionVisitor);
 };
 
+class ParallelMoveResolverX86 : public ParallelMoveResolver {
+ public:
+  ParallelMoveResolverX86(ArenaAllocator* allocator, CodeGeneratorX86* codegen)
+      : ParallelMoveResolver(allocator), codegen_(codegen) {}
+
+  virtual void EmitMove(size_t index) OVERRIDE;
+  virtual void EmitSwap(size_t index) OVERRIDE;
+  virtual void SpillScratch(int reg) OVERRIDE;
+  virtual void RestoreScratch(int reg) OVERRIDE;
+
+  X86Assembler* GetAssembler() const;
+
+ private:
+  void Exchange(Register reg, int mem);
+  void Exchange(int mem1, int mem2);
+  void MoveMemoryToMemory(int dst, int src);
+
+  CodeGeneratorX86* const codegen_;
+
+  DISALLOW_COPY_AND_ASSIGN(ParallelMoveResolverX86);
+};
+
 class LocationsBuilderX86 : public HGraphVisitor {
  public:
   LocationsBuilderX86(HGraph* graph, CodeGeneratorX86* codegen)
@@ -105,6 +128,7 @@ class CodeGeneratorX86 : public CodeGenerator {
   explicit CodeGeneratorX86(HGraph* graph);
   virtual ~CodeGeneratorX86() { }
 
+  virtual void ComputeFrameSize(size_t number_of_spill_slots) OVERRIDE;
   virtual void GenerateFrameEntry() OVERRIDE;
   virtual void GenerateFrameExit() OVERRIDE;
   virtual void Bind(Label* label) OVERRIDE;
@@ -145,6 +169,10 @@ class CodeGeneratorX86 : public CodeGenerator {
   virtual void DumpCoreRegister(std::ostream& stream, int reg) const OVERRIDE;
   virtual void DumpFloatingPointRegister(std::ostream& stream, int reg) const OVERRIDE;
 
+  ParallelMoveResolverX86* GetMoveResolver() {
+    return &move_resolver_;
+  }
+
  private:
   // Helper method to move a 32bits value between two locations.
   void Move32(Location destination, Location source);
@@ -153,6 +181,7 @@ class CodeGeneratorX86 : public CodeGenerator {
 
   LocationsBuilderX86 location_builder_;
   InstructionCodeGeneratorX86 instruction_visitor_;
+  ParallelMoveResolverX86 move_resolver_;
   X86Assembler assembler_;
 
   DISALLOW_COPY_AND_ASSIGN(CodeGeneratorX86);
diff --git a/compiler/optimizing/codegen_test.cc b/compiler/optimizing/codegen_test.cc
index 7684bb189d..8ee775cbe1 100644
--- a/compiler/optimizing/codegen_test.cc
+++ b/compiler/optimizing/codegen_test.cc
@@ -56,7 +56,7 @@ static void TestCode(const uint16_t* data, bool has_result = false, int32_t expe
   ASSERT_NE(graph, nullptr);
   InternalCodeAllocator allocator;
   CodeGenerator* codegen = CodeGenerator::Create(&arena, graph, kX86);
-  codegen->Compile(&allocator);
+  codegen->CompileBaseline(&allocator);
   typedef int32_t (*fptr)();
 #if defined(__i386__)
   CommonCompilerTest::MakeExecutable(allocator.GetMemory(), allocator.GetSize());
@@ -66,7 +66,7 @@ static void TestCode(const uint16_t* data, bool has_result = false, int32_t expe
   }
 #endif
   codegen = CodeGenerator::Create(&arena, graph, kArm);
-  codegen->Compile(&allocator);
+  codegen->CompileBaseline(&allocator);
 #if defined(__arm__)
   CommonCompilerTest::MakeExecutable(allocator.GetMemory(), allocator.GetSize());
   int32_t result = reinterpret_cast<fptr>(allocator.GetMemory())();
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 5c5042e20f..a49ce64a2d 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -28,8 +28,15 @@ namespace art {
  */
 class HGraphVisualizerPrinter : public HGraphVisitor {
  public:
-  HGraphVisualizerPrinter(HGraph* graph, std::ostream& output, const CodeGenerator& codegen)
-      : HGraphVisitor(graph), output_(output), codegen_(codegen), indent_(0) {}
+  HGraphVisualizerPrinter(HGraph* graph,
+                          std::ostream& output,
+                          const char* pass_name,
+                          const CodeGenerator& codegen)
+      : HGraphVisitor(graph),
+        output_(output),
+        pass_name_(pass_name),
+        codegen_(codegen),
+        indent_(0) {}
 
   void StartTag(const char* name) {
     AddIndent();
@@ -94,6 +101,33 @@ class HGraphVisualizerPrinter : public HGraphVisitor {
     output_<< std::endl;
   }
 
+  void DumpLocation(Location location, Primitive::Type type) {
+    if (location.IsRegister()) {
+      if (type == Primitive::kPrimDouble || type == Primitive::kPrimFloat) {
+        codegen_.DumpFloatingPointRegister(output_, location.reg().RegId());
+      } else {
+        codegen_.DumpCoreRegister(output_, location.reg().RegId());
+      }
+    } else {
+      DCHECK(location.IsStackSlot());
+      output_ << location.GetStackIndex() << "(sp)";
+    }
+  }
+
+  void VisitParallelMove(HParallelMove* instruction) {
+    output_ << instruction->DebugName();
+    output_ << " (";
+    for (size_t i = 0, e = instruction->NumMoves(); i < e; ++i) {
+      MoveOperands* move = instruction->MoveOperandsAt(i);
+      DumpLocation(move->GetSource(), Primitive::kPrimInt);
+      output_ << " -> ";
+      DumpLocation(move->GetDestination(), Primitive::kPrimInt);
+      if (i + 1 != e) {
+        output_ << ", ";
+      }
+    }
+    output_ << ")";
+  }
 
   void VisitInstruction(HInstruction* instruction) {
     output_ << instruction->DebugName();
@@ -104,24 +138,28 @@ class HGraphVisualizerPrinter : public HGraphVisitor {
       }
       output_ << "]";
     }
-    if (instruction->GetLifetimePosition() != kNoLifetime) {
+    if (pass_name_ == kLivenessPassName && instruction->GetLifetimePosition() != kNoLifetime) {
       output_ << " (liveness: " << instruction->GetLifetimePosition();
       if (instruction->HasLiveInterval()) {
         output_ << " ";
         const LiveInterval& interval = *instruction->GetLiveInterval();
         interval.Dump(output_);
-        if (interval.HasRegister()) {
-          int reg = interval.GetRegister();
+      }
+      output_ << ")";
+    } else if (pass_name_ == kRegisterAllocatorPassName) {
+      LocationSummary* locations = instruction->GetLocations();
+      if (locations != nullptr) {
+        output_ << " ( ";
+        for (size_t i = 0; i < instruction->InputCount(); ++i) {
+          DumpLocation(locations->InAt(i), instruction->InputAt(i)->GetType());
           output_ << " ";
-          if (instruction->GetType() == Primitive::kPrimFloat
-              || instruction->GetType() == Primitive::kPrimDouble) {
-            codegen_.DumpFloatingPointRegister(output_, reg);
-          } else {
-            codegen_.DumpCoreRegister(output_, reg);
-          }
+        }
+        output_ << ")";
+        if (locations->Out().IsValid()) {
+          output_ << " -> ";
+          DumpLocation(locations->Out(), instruction->GetType());
         }
       }
-      output_ << ")";
     }
   }
 
@@ -137,9 +175,9 @@ class HGraphVisualizerPrinter : public HGraphVisitor {
     }
   }
 
-  void Run(const char* pass_name) {
+  void Run() {
     StartTag("cfg");
-    PrintProperty("name", pass_name);
+    PrintProperty("name", pass_name_);
     VisitInsertionOrder();
     EndTag("cfg");
   }
@@ -188,6 +226,7 @@ class HGraphVisualizerPrinter : public HGraphVisitor {
 
  private:
   std::ostream& output_;
+  const char* pass_name_;
   const CodeGenerator& codegen_;
   size_t indent_;
 
@@ -209,7 +248,7 @@ HGraphVisualizer::HGraphVisualizer(std::ostream* output,
   }
 
   is_enabled_ = true;
-  HGraphVisualizerPrinter printer(graph, *output_, codegen_);
+  HGraphVisualizerPrinter printer(graph, *output_, "", codegen_);
   printer.StartTag("compilation");
   printer.PrintProperty("name", pretty_name.c_str());
   printer.PrintProperty("method", pretty_name.c_str());
@@ -227,7 +266,7 @@ HGraphVisualizer::HGraphVisualizer(std::ostream* output,
   }
 
   is_enabled_ = true;
-  HGraphVisualizerPrinter printer(graph, *output_, codegen_);
+  HGraphVisualizerPrinter printer(graph, *output_, "", codegen_);
   printer.StartTag("compilation");
   printer.PrintProperty("name", name);
   printer.PrintProperty("method", name);
@@ -239,8 +278,8 @@ void HGraphVisualizer::DumpGraph(const char* pass_name) {
   if (!is_enabled_) {
     return;
   }
-  HGraphVisualizerPrinter printer(graph_, *output_, codegen_);
-  printer.Run(pass_name);
+  HGraphVisualizerPrinter printer(graph_, *output_, pass_name, codegen_);
+  printer.Run();
 }
 
 }  // namespace art
diff --git a/compiler/optimizing/graph_visualizer.h b/compiler/optimizing/graph_visualizer.h
index 2638cf504d..7cd74e9b7a 100644
--- a/compiler/optimizing/graph_visualizer.h
+++ b/compiler/optimizing/graph_visualizer.h
@@ -25,6 +25,9 @@ class CodeGenerator;
 class DexCompilationUnit;
 class HGraph;
 
+static const char* kLivenessPassName = "liveness";
+static const char* kRegisterAllocatorPassName = "register";
+
 /**
  * If enabled, emits compilation information suitable for the c1visualizer tool
  * and IRHydra.
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 68848de636..143d5c9e6f 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -508,6 +508,7 @@ class HInstruction : public ArenaObject {
   void ReplaceWith(HInstruction* instruction);
 
 #define INSTRUCTION_TYPE_CHECK(type)                                           \
+  bool Is##type() { return (As##type() != nullptr); }                          \
   virtual H##type* As##type() { return nullptr; }
 
   FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 3dc0928d6d..ccacbef401 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -85,6 +85,8 @@ CompiledMethod* OptimizingCompiler::TryCompile(const DexFile::CodeItem* code_ite
   // For testing purposes, we put a special marker on method names that should be compiled
   // with this compiler. This makes sure we're not regressing.
   bool shouldCompile = dex_compilation_unit.GetSymbol().find("00024opt_00024") != std::string::npos;
+  bool shouldOptimize =
+      dex_compilation_unit.GetSymbol().find("00024reg_00024") != std::string::npos;
 
   ArenaPool pool;
   ArenaAllocator arena(&pool);
@@ -116,7 +118,36 @@ CompiledMethod* OptimizingCompiler::TryCompile(const DexFile::CodeItem* code_ite
   visualizer.DumpGraph("builder");
 
   CodeVectorAllocator allocator;
-  codegen->Compile(&allocator);
+
+  if (RegisterAllocator::CanAllocateRegistersFor(*graph, instruction_set)) {
+    graph->BuildDominatorTree();
+    graph->TransformToSSA();
+    visualizer.DumpGraph("ssa");
+
+    graph->FindNaturalLoops();
+    SsaLivenessAnalysis liveness(*graph, codegen);
+    liveness.Analyze();
+    visualizer.DumpGraph(kLivenessPassName);
+
+    RegisterAllocator register_allocator(graph->GetArena(), codegen, liveness);
+    register_allocator.AllocateRegisters();
+
+    visualizer.DumpGraph(kRegisterAllocatorPassName);
+    codegen->CompileOptimized(&allocator);
+  } else if (shouldOptimize && RegisterAllocator::Supports(instruction_set)) {
+    LOG(FATAL) << "Could not allocate registers in optimizing compiler";
+  } else {
+    codegen->CompileBaseline(&allocator);
+
+    // Run these phases to get some test coverage.
+    graph->BuildDominatorTree();
+    graph->TransformToSSA();
+    visualizer.DumpGraph("ssa");
+    graph->FindNaturalLoops();
+    SsaLivenessAnalysis liveness(*graph, codegen);
+    liveness.Analyze();
+    visualizer.DumpGraph(kLivenessPassName);
+  }
 
   std::vector<uint8_t> mapping_table;
   codegen->BuildMappingTable(&mapping_table);
@@ -125,19 +156,6 @@ CompiledMethod* OptimizingCompiler::TryCompile(const DexFile::CodeItem* code_ite
   std::vector<uint8_t> gc_map;
   codegen->BuildNativeGCMap(&gc_map, dex_compilation_unit);
 
-  // Run these phases to get some test coverage.
-  graph->BuildDominatorTree();
-  graph->TransformToSSA();
-  visualizer.DumpGraph("ssa");
-
-  graph->FindNaturalLoops();
-  SsaLivenessAnalysis liveness(*graph, codegen);
-  liveness.Analyze();
-  visualizer.DumpGraph("liveness");
-
-  RegisterAllocator(graph->GetArena(), *codegen).AllocateRegisters(liveness);
-  visualizer.DumpGraph("register");
-
   return new CompiledMethod(GetCompilerDriver(),
                             instruction_set,
                             allocator.GetMemory(),
diff --git a/compiler/optimizing/parallel_move_resolver.cc b/compiler/optimizing/parallel_move_resolver.cc
index 3d2d136ec3..4a1b6ce446 100644
--- a/compiler/optimizing/parallel_move_resolver.cc
+++ b/compiler/optimizing/parallel_move_resolver.cc
@@ -147,4 +147,64 @@ void ParallelMoveResolver::PerformMove(size_t index) {
   }
 }
 
+bool ParallelMoveResolver::IsScratchLocation(Location loc) {
+  for (size_t i = 0; i < moves_.Size(); ++i) {
+    if (moves_.Get(i)->Blocks(loc)) {
+      return false;
+    }
+  }
+
+  for (size_t i = 0; i < moves_.Size(); ++i) {
+    if (moves_.Get(i)->GetDestination().Equals(loc)) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
+int ParallelMoveResolver::AllocateScratchRegister(int blocked, int register_count, bool* spilled) {
+  int scratch = -1;
+  for (int reg = 0; reg < register_count; ++reg) {
+    if ((blocked != reg) &&
+        IsScratchLocation(Location::RegisterLocation(ManagedRegister(reg)))) {
+      scratch = reg;
+      break;
+    }
+  }
+
+  if (scratch == -1) {
+    *spilled = true;
+    for (int reg = 0; reg < register_count; ++reg) {
+      if (blocked != reg) {
+        scratch = reg;
+      }
+    }
+  } else {
+    *spilled = false;
+  }
+
+  return scratch;
+}
+
+
+ParallelMoveResolver::ScratchRegisterScope::ScratchRegisterScope(
+    ParallelMoveResolver* resolver, int blocked, int number_of_registers)
+    : resolver_(resolver),
+      reg_(kNoRegister),
+      spilled_(false) {
+  reg_ = resolver_->AllocateScratchRegister(blocked, number_of_registers, &spilled_);
+
+  if (spilled_) {
+    resolver->SpillScratch(reg_);
+  }
+}
+
+
+ParallelMoveResolver::ScratchRegisterScope::~ScratchRegisterScope() {
+  if (spilled_) {
+    resolver_->RestoreScratch(reg_);
+  }
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/parallel_move_resolver.h b/compiler/optimizing/parallel_move_resolver.h
index ff20cb0bc6..e1189d8520 100644
--- a/compiler/optimizing/parallel_move_resolver.h
+++ b/compiler/optimizing/parallel_move_resolver.h
@@ -23,6 +23,7 @@
 namespace art {
 
 class HParallelMove;
+class Location;
 class MoveOperands;
 
 /**
@@ -39,15 +40,37 @@ class ParallelMoveResolver : public ValueObject {
   void EmitNativeCode(HParallelMove* parallel_move);
 
  protected:
+  class ScratchRegisterScope : public ValueObject {
+   public:
+    ScratchRegisterScope(ParallelMoveResolver* resolver, int blocked, int number_of_registers);
+    ~ScratchRegisterScope();
+
+    int GetRegister() const { return reg_; }
+    bool IsSpilled() const { return spilled_; }
+
+   private:
+    ParallelMoveResolver* resolver_;
+    int reg_;
+    bool spilled_;
+  };
+
+  bool IsScratchLocation(Location loc);
+  int AllocateScratchRegister(int blocked, int register_count, bool* spilled);
+
   // Emit a move.
   virtual void EmitMove(size_t index) = 0;
 
   // Execute a move by emitting a swap of two operands.
   virtual void EmitSwap(size_t index) = 0;
 
+  virtual void SpillScratch(int reg) = 0;
+  virtual void RestoreScratch(int reg) = 0;
+
   // List of moves not yet resolved.
   GrowableArray<MoveOperands*> moves_;
 
+  static constexpr int kNoRegister = -1;
+
  private:
   // Build the initial list of moves.
   void BuildInitialMoveList(HParallelMove* parallel_move);
diff --git a/compiler/optimizing/parallel_move_test.cc b/compiler/optimizing/parallel_move_test.cc
index 88df24d9ac..093856d497 100644
--- a/compiler/optimizing/parallel_move_test.cc
+++ b/compiler/optimizing/parallel_move_test.cc
@@ -50,6 +50,9 @@ class TestParallelMoveResolver : public ParallelMoveResolver {
              << ")";
   }
 
+  virtual void SpillScratch(int reg) {}
+  virtual void RestoreScratch(int reg) {}
+
   std::string GetMessage() const {
     return  message_.str();
   }
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 8c6eb2a174..c2a47697de 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -24,64 +24,151 @@ namespace art {
 static constexpr size_t kMaxLifetimePosition = -1;
 static constexpr size_t kDefaultNumberOfSpillSlots = 4;
 
-RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, const CodeGenerator& codegen)
+RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator,
+                                     CodeGenerator* codegen,
+                                     const SsaLivenessAnalysis& liveness)
       : allocator_(allocator),
         codegen_(codegen),
+        liveness_(liveness),
         unhandled_(allocator, 0),
         handled_(allocator, 0),
         active_(allocator, 0),
         inactive_(allocator, 0),
+        physical_register_intervals_(allocator, codegen->GetNumberOfRegisters()),
         spill_slots_(allocator, kDefaultNumberOfSpillSlots),
         processing_core_registers_(false),
         number_of_registers_(-1),
         registers_array_(nullptr),
-        blocked_registers_(allocator->AllocArray<bool>(codegen.GetNumberOfRegisters())) {
-  codegen.SetupBlockedRegisters(blocked_registers_);
+        blocked_registers_(allocator->AllocArray<bool>(codegen->GetNumberOfRegisters())) {
+  codegen->SetupBlockedRegisters(blocked_registers_);
+  physical_register_intervals_.SetSize(codegen->GetNumberOfRegisters());
 }
 
-static bool ShouldProcess(bool processing_core_registers, HInstruction* instruction) {
-  bool is_core_register = (instruction->GetType() != Primitive::kPrimDouble)
-      && (instruction->GetType() != Primitive::kPrimFloat);
+bool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph,
+                                                InstructionSet instruction_set) {
+  if (!Supports(instruction_set)) {
+    return false;
+  }
+  for (size_t i = 0, e = graph.GetBlocks().Size(); i < e; ++i) {
+    for (HInstructionIterator it(graph.GetBlocks().Get(i)->GetInstructions());
+         !it.Done();
+         it.Advance()) {
+      HInstruction* current = it.Current();
+      if (current->NeedsEnvironment()) return false;
+      if (current->GetType() == Primitive::kPrimLong) return false;
+      if (current->GetType() == Primitive::kPrimFloat) return false;
+      if (current->GetType() == Primitive::kPrimDouble) return false;
+    }
+  }
+  return true;
+}
+
+static bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) {
+  bool is_core_register = (interval->GetType() != Primitive::kPrimDouble)
+      && (interval->GetType() != Primitive::kPrimFloat);
   return processing_core_registers == is_core_register;
 }
 
-void RegisterAllocator::AllocateRegistersInternal(const SsaLivenessAnalysis& liveness) {
+void RegisterAllocator::AllocateRegisters() {
+  processing_core_registers_ = true;
+  AllocateRegistersInternal();
+  processing_core_registers_ = false;
+  AllocateRegistersInternal();
+
+  Resolve();
+
+  if (kIsDebugBuild) {
+    processing_core_registers_ = true;
+    ValidateInternal(true);
+    processing_core_registers_ = false;
+    ValidateInternal(true);
+  }
+}
+
+void RegisterAllocator::BlockRegister(Location location,
+                                      size_t start,
+                                      size_t end,
+                                      Primitive::Type type) {
+  int reg = location.reg().RegId();
+  LiveInterval* interval = physical_register_intervals_.Get(reg);
+  if (interval == nullptr) {
+    interval = LiveInterval::MakeFixedInterval(allocator_, reg, type);
+    physical_register_intervals_.Put(reg, interval);
+    inactive_.Add(interval);
+  }
+  DCHECK(interval->GetRegister() == reg);
+  interval->AddRange(start, end);
+}
+
+void RegisterAllocator::AllocateRegistersInternal() {
   number_of_registers_ = processing_core_registers_
-      ? codegen_.GetNumberOfCoreRegisters()
-      : codegen_.GetNumberOfFloatingPointRegisters();
+      ? codegen_->GetNumberOfCoreRegisters()
+      : codegen_->GetNumberOfFloatingPointRegisters();
 
   registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_);
 
   // Iterate post-order, to ensure the list is sorted, and the last added interval
   // is the one with the lowest start position.
-  for (size_t i = liveness.GetNumberOfSsaValues(); i > 0; --i) {
-    HInstruction* instruction = liveness.GetInstructionFromSsaIndex(i - 1);
-    if (ShouldProcess(processing_core_registers_, instruction)) {
-      LiveInterval* current = instruction->GetLiveInterval();
+  for (size_t i = liveness_.GetNumberOfSsaValues(); i > 0; --i) {
+    HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i - 1);
+    LiveInterval* current = instruction->GetLiveInterval();
+    if (ShouldProcess(processing_core_registers_, current)) {
       DCHECK(unhandled_.IsEmpty() || current->StartsBefore(unhandled_.Peek()));
-      unhandled_.Add(current);
-    }
-  }
 
-  LinearScan();
-  if (kIsDebugBuild) {
-    ValidateInternal(liveness, true);
-  }
-}
+      LocationSummary* locations = instruction->GetLocations();
+      if (locations->GetTempCount() != 0) {
+        // Note that we already filtered out instructions requiring temporaries in
+        // RegisterAllocator::CanAllocateRegistersFor.
+        LOG(FATAL) << "Unimplemented";
+      }
 
-bool RegisterAllocator::ValidateInternal(const SsaLivenessAnalysis& liveness,
-                                         bool log_fatal_on_failure) const {
-  // To simplify unit testing, we eagerly create the array of intervals, and
-  // call the helper method.
-  GrowableArray<LiveInterval*> intervals(allocator_, 0);
-  for (size_t i = 0; i < liveness.GetNumberOfSsaValues(); ++i) {
-    HInstruction* instruction = liveness.GetInstructionFromSsaIndex(i);
-    if (ShouldProcess(processing_core_registers_, instruction)) {
-      intervals.Add(instruction->GetLiveInterval());
+      // Some instructions define their output in fixed register/stack slot. We need
+      // to ensure we know these locations before doing register allocation. For a
+      // given register, we create an interval that covers these locations. The register
+      // will be unavailable at these locations when trying to allocate one for an
+      // interval.
+      //
+      // The backwards walking ensures the ranges are ordered on increasing start positions.
+      Location output = locations->Out();
+      size_t position = instruction->GetLifetimePosition();
+      if (output.IsRegister()) {
+        // Shift the interval's start by one to account for the blocked register.
+        current->SetFrom(position + 1);
+        current->SetRegister(output.reg().RegId());
+        BlockRegister(output, position, position + 1, instruction->GetType());
+      } else if (output.IsStackSlot()) {
+        current->SetSpillSlot(output.GetStackIndex());
+      }
+      for (size_t i = 0; i < instruction->InputCount(); ++i) {
+        Location input = locations->InAt(i);
+        if (input.IsRegister()) {
+          BlockRegister(input, position, position + 1, instruction->InputAt(i)->GetType());
+        }
+      }
+
+      // Add the interval to the correct list.
+      if (current->HasRegister()) {
+        DCHECK(instruction->IsParameterValue());
+        inactive_.Add(current);
+      } else if (current->HasSpillSlot()) {
+        DCHECK(instruction->IsParameterValue());
+        // Split before first register use.
+        size_t first_register_use = current->FirstRegisterUse();
+        if (first_register_use != kNoLifetime) {
+          LiveInterval* split = Split(current, first_register_use - 1);
+          // The new interval may start at a late
+          AddToUnhandled(split);
+        } else {
+          // Nothing to do, we won't allocate a register for this value.
+        }
+      } else {
+        DCHECK(unhandled_.IsEmpty() || current->StartsBefore(unhandled_.Peek()));
+        unhandled_.Add(current);
+      }
     }
   }
-  return ValidateIntervals(intervals, spill_slots_.Size(), codegen_, allocator_,
-                           processing_core_registers_, log_fatal_on_failure);
+
+  LinearScan();
 }
 
 class AllRangesIterator : public ValueObject {
@@ -111,6 +198,28 @@ class AllRangesIterator : public ValueObject {
   DISALLOW_COPY_AND_ASSIGN(AllRangesIterator);
 };
 
+bool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const {
+  // To simplify unit testing, we eagerly create the array of intervals, and
+  // call the helper method.
+  GrowableArray<LiveInterval*> intervals(allocator_, 0);
+  for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) {
+    HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i);
+    if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) {
+      intervals.Add(instruction->GetLiveInterval());
+    }
+  }
+
+  for (size_t i = 0, e = physical_register_intervals_.Size(); i < e; ++i) {
+    LiveInterval* fixed = physical_register_intervals_.Get(i);
+    if (fixed != nullptr && ShouldProcess(processing_core_registers_, fixed)) {
+      intervals.Add(fixed);
+    }
+  }
+
+  return ValidateIntervals(intervals, spill_slots_.Size(), *codegen_, allocator_,
+                           processing_core_registers_, log_fatal_on_failure);
+}
+
 bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals,
                                           size_t number_of_spill_slots,
                                           const CodeGenerator& codegen,
@@ -132,7 +241,10 @@ bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& in
   for (size_t i = 0, e = intervals.Size(); i < e; ++i) {
     for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) {
       LiveInterval* current = it.CurrentInterval();
-      if (current->GetParent()->HasSpillSlot()) {
+      HInstruction* defined_by = current->GetParent()->GetDefinedBy();
+      if (current->GetParent()->HasSpillSlot()
+           // Parameters have their own stack slot.
+           && !(defined_by != nullptr && defined_by->IsParameterValue())) {
         BitVector* liveness_of_spill_slot = liveness_of_values.Get(
             number_of_registers + current->GetParent()->GetSpillSlot() / kVRegSize);
         for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) {
@@ -176,14 +288,14 @@ bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& in
   return true;
 }
 
-void RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) {
+void RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const {
   interval->Dump(stream);
   stream << ": ";
   if (interval->HasRegister()) {
     if (processing_core_registers_) {
-      codegen_.DumpCoreRegister(stream, interval->GetRegister());
+      codegen_->DumpCoreRegister(stream, interval->GetRegister());
     } else {
-      codegen_.DumpFloatingPointRegister(stream, interval->GetRegister());
+      codegen_->DumpFloatingPointRegister(stream, interval->GetRegister());
     }
   } else {
     stream << "spilled";
@@ -196,6 +308,7 @@ void RegisterAllocator::LinearScan() {
   while (!unhandled_.IsEmpty()) {
     // (1) Remove interval with the lowest start position from unhandled.
     LiveInterval* current = unhandled_.Pop();
+    DCHECK(!current->IsFixed() && !current->HasRegister() && !current->HasSpillSlot());
     size_t position = current->GetStart();
 
     // (2) Remove currently active intervals that are dead at this position.
@@ -255,13 +368,6 @@ bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) {
     free_until[i] = kMaxLifetimePosition;
   }
 
-  // For each active interval, set its register to not free.
-  for (size_t i = 0, e = active_.Size(); i < e; ++i) {
-    LiveInterval* interval = active_.Get(i);
-    DCHECK(interval->HasRegister());
-    free_until[interval->GetRegister()] = 0;
-  }
-
   // For each inactive interval, set its register to be free until
   // the next intersection with `current`.
   // Thanks to SSA, this should only be needed for intervals
@@ -275,6 +381,13 @@ bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) {
     }
   }
 
+  // For each active interval, set its register to not free.
+  for (size_t i = 0, e = active_.Size(); i < e; ++i) {
+    LiveInterval* interval = active_.Get(i);
+    DCHECK(interval->HasRegister());
+    free_until[interval->GetRegister()] = 0;
+  }
+
   // Pick the register that is free the longest.
   int reg = -1;
   for (size_t i = 0; i < number_of_registers_; ++i) {
@@ -330,9 +443,13 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
   for (size_t i = 0, e = active_.Size(); i < e; ++i) {
     LiveInterval* active = active_.Get(i);
     DCHECK(active->HasRegister());
-    size_t use = active->FirstRegisterUseAfter(current->GetStart());
-    if (use != kNoLifetime) {
-      next_use[active->GetRegister()] = use;
+    if (active->IsFixed()) {
+      next_use[active->GetRegister()] = current->GetStart();
+    } else {
+      size_t use = active->FirstRegisterUseAfter(current->GetStart());
+      if (use != kNoLifetime) {
+        next_use[active->GetRegister()] = use;
+      }
     }
   }
 
@@ -343,9 +460,17 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
   for (size_t i = 0, e = inactive_.Size(); i < e; ++i) {
     LiveInterval* inactive = inactive_.Get(i);
     DCHECK(inactive->HasRegister());
-    size_t use = inactive->FirstRegisterUseAfter(current->GetStart());
-    if (use != kNoLifetime) {
-      next_use[inactive->GetRegister()] = use;
+    size_t next_intersection = inactive->FirstIntersectionWith(current);
+    if (next_intersection != kNoLifetime) {
+      if (inactive->IsFixed()) {
+        next_use[inactive->GetRegister()] =
+            std::min(next_intersection, next_use[inactive->GetRegister()]);
+      } else {
+        size_t use = inactive->FirstRegisterUseAfter(current->GetStart());
+        if (use != kNoLifetime) {
+          next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]);
+        }
+      }
     }
   }
 
@@ -374,6 +499,7 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
     for (size_t i = 0, e = active_.Size(); i < e; ++i) {
       LiveInterval* active = active_.Get(i);
       if (active->GetRegister() == reg) {
+        DCHECK(!active->IsFixed());
         LiveInterval* split = Split(active, current->GetStart());
         active_.DeleteAt(i);
         handled_.Add(active);
@@ -385,11 +511,19 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
     for (size_t i = 0; i < inactive_.Size(); ++i) {
       LiveInterval* inactive = inactive_.Get(i);
       if (inactive->GetRegister() == reg) {
-        LiveInterval* split = Split(inactive, current->GetStart());
-        inactive_.DeleteAt(i);
-        handled_.Add(inactive);
-        AddToUnhandled(split);
-        --i;
+        size_t next_intersection = inactive->FirstIntersectionWith(current);
+        if (next_intersection != kNoLifetime) {
+          if (inactive->IsFixed()) {
+            LiveInterval* split = Split(current, next_intersection);
+            AddToUnhandled(split);
+          } else {
+            LiveInterval* split = Split(inactive, current->GetStart());
+            inactive_.DeleteAt(i);
+            handled_.Add(inactive);
+            AddToUnhandled(split);
+            --i;
+          }
+        }
       }
     }
 
@@ -398,13 +532,15 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
 }
 
 void RegisterAllocator::AddToUnhandled(LiveInterval* interval) {
+  size_t insert_at = 0;
   for (size_t i = unhandled_.Size(); i > 0; --i) {
     LiveInterval* current = unhandled_.Get(i - 1);
     if (current->StartsAfter(interval)) {
-      unhandled_.InsertAt(i, interval);
+      insert_at = i;
       break;
     }
   }
+  unhandled_.InsertAt(insert_at, interval);
 }
 
 LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) {
@@ -429,7 +565,13 @@ void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) {
     return;
   }
 
-  // Find when this instruction dies.
+  HInstruction* defined_by = parent->GetDefinedBy();
+  if (defined_by->IsParameterValue()) {
+    // Parameters have their own stack slot.
+    parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue()));
+    return;
+  }
+
   LiveInterval* last_sibling = interval;
   while (last_sibling->GetNextSibling() != nullptr) {
     last_sibling = last_sibling->GetNextSibling();
@@ -451,7 +593,315 @@ void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) {
     spill_slots_.Put(slot, end);
   }
 
-  interval->GetParent()->SetSpillSlot(slot * kVRegSize);
+  parent->SetSpillSlot(slot * kVRegSize);
+}
+
+static Location ConvertToLocation(LiveInterval* interval) {
+  if (interval->HasRegister()) {
+    return Location::RegisterLocation(ManagedRegister(interval->GetRegister()));
+  } else {
+    DCHECK(interval->GetParent()->HasSpillSlot());
+    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
+// have been executed.
+static constexpr size_t kInputMoveLifetimePosition = 0;
+static bool IsInputMove(HInstruction* instruction) {
+  return instruction->GetLifetimePosition() == kInputMoveLifetimePosition;
+}
+
+void RegisterAllocator::AddInputMoveFor(HInstruction* instruction,
+                                        Location source,
+                                        Location destination) const {
+  if (source.Equals(destination)) return;
+
+  DCHECK(instruction->AsPhi() == nullptr);
+
+  HInstruction* previous = instruction->GetPrevious();
+  HParallelMove* move = nullptr;
+  if (previous == nullptr
+      || previous->AsParallelMove() == nullptr
+      || !IsInputMove(previous)) {
+    move = new (allocator_) HParallelMove(allocator_);
+    move->SetLifetimePosition(kInputMoveLifetimePosition);
+    instruction->GetBlock()->InsertInstructionBefore(move, instruction);
+  } else {
+    move = previous->AsParallelMove();
+  }
+  DCHECK(IsInputMove(move));
+  move->AddMove(new (allocator_) MoveOperands(source, destination));
+}
+
+void RegisterAllocator::InsertParallelMoveAt(size_t position,
+                                             Location source,
+                                             Location destination) const {
+  if (source.Equals(destination)) return;
+
+  HInstruction* at = liveness_.GetInstructionFromPosition(position / 2);
+  if (at == nullptr) {
+    // Block boundary, don't no anything the connection of split siblings will handle it.
+    return;
+  }
+  HParallelMove* move;
+  if ((position & 1) == 1) {
+    // Move must happen after the instruction.
+    DCHECK(!at->IsControlFlow());
+    move = at->GetNext()->AsParallelMove();
+    if (move == nullptr || IsInputMove(move)) {
+      move = new (allocator_) HParallelMove(allocator_);
+      move->SetLifetimePosition(position);
+      at->GetBlock()->InsertInstructionBefore(move, at->GetNext());
+    }
+  } else {
+    // Move must happen before the instruction.
+    HInstruction* previous = at->GetPrevious();
+    if (previous != nullptr && previous->AsParallelMove() != nullptr) {
+      if (IsInputMove(previous)) {
+        previous = previous->GetPrevious();
+      }
+    }
+    if (previous == nullptr || previous->AsParallelMove() == nullptr) {
+      move = new (allocator_) HParallelMove(allocator_);
+      move->SetLifetimePosition(position);
+      at->GetBlock()->InsertInstructionBefore(move, at);
+    } else {
+      move = previous->AsParallelMove();
+    }
+  }
+  move->AddMove(new (allocator_) MoveOperands(source, destination));
+}
+
+void RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block,
+                                                   Location source,
+                                                   Location destination) const {
+  if (source.Equals(destination)) return;
+
+  DCHECK_EQ(block->GetSuccessors().Size(), 1u);
+  HInstruction* last = block->GetLastInstruction();
+  HInstruction* previous = last->GetPrevious();
+  HParallelMove* move;
+  if (previous == nullptr || previous->AsParallelMove() == nullptr) {
+    move = new (allocator_) HParallelMove(allocator_);
+    block->InsertInstructionBefore(move, last);
+  } else {
+    move = previous->AsParallelMove();
+  }
+  move->AddMove(new (allocator_) MoveOperands(source, destination));
+}
+
+void RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block,
+                                                    Location source,
+                                                    Location destination) const {
+  if (source.Equals(destination)) return;
+
+  HInstruction* first = block->GetFirstInstruction();
+  HParallelMove* move = first->AsParallelMove();
+  if (move == nullptr || IsInputMove(move)) {
+    move = new (allocator_) HParallelMove(allocator_);
+    move->SetLifetimePosition(block->GetLifetimeStart());
+    block->InsertInstructionBefore(move, first);
+  }
+  move->AddMove(new (allocator_) MoveOperands(source, destination));
+}
+
+void RegisterAllocator::InsertMoveAfter(HInstruction* instruction,
+                                        Location source,
+                                        Location destination) const {
+  if (source.Equals(destination)) return;
+
+  if (instruction->AsPhi() != nullptr) {
+    InsertParallelMoveAtEntryOf(instruction->GetBlock(), source, destination);
+    return;
+  }
+
+  HParallelMove* move = instruction->GetNext()->AsParallelMove();
+  if (move == nullptr || IsInputMove(move)) {
+    move = new (allocator_) HParallelMove(allocator_);
+    instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext());
+  }
+  move->AddMove(new (allocator_) MoveOperands(source, destination));
+}
+
+void RegisterAllocator::ConnectSiblings(LiveInterval* interval) {
+  LiveInterval* current = interval;
+  if (current->HasSpillSlot() && current->HasRegister()) {
+    // We spill eagerly, so move must be at definition.
+    InsertMoveAfter(interval->GetDefinedBy(),
+                    Location::RegisterLocation(ManagedRegister(interval->GetRegister())),
+                    Location::StackSlot(interval->GetParent()->GetSpillSlot()));
+  }
+  UsePosition* use = current->GetFirstUse();
+
+  // Walk over all siblings, updating locations of use positions, and
+  // connecting them when they are adjacent.
+  do {
+    Location source = ConvertToLocation(current);
+
+    // Walk over all uses covered by this interval, and update the location
+    // information.
+    while (use != nullptr && use->GetPosition() <= current->GetEnd()) {
+      if (!use->GetIsEnvironment()) {
+        LocationSummary* locations = use->GetUser()->GetLocations();
+        Location expected_location = locations->InAt(use->GetInputIndex());
+        if (expected_location.IsUnallocated()) {
+          locations->SetInAt(use->GetInputIndex(), source);
+        } else {
+          AddInputMoveFor(use->GetUser(), source, expected_location);
+        }
+      }
+      use = use->GetNext();
+    }
+
+    // If the next interval starts just after this one, and has a register,
+    // insert a move.
+    LiveInterval* next_sibling = current->GetNextSibling();
+    if (next_sibling != nullptr
+        && next_sibling->HasRegister()
+        && current->GetEnd() == next_sibling->GetStart()) {
+      Location destination = ConvertToLocation(next_sibling);
+      InsertParallelMoveAt(current->GetEnd(), source, destination);
+    }
+    current = next_sibling;
+  } while (current != nullptr);
+  DCHECK(use == nullptr);
+}
+
+void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval,
+                                             HBasicBlock* from,
+                                             HBasicBlock* to) const {
+  if (interval->GetNextSibling() == nullptr) {
+    // Nothing to connect. The whole range was allocated to the same location.
+    return;
+  }
+
+  size_t from_position = from->GetLifetimeEnd() - 1;
+  size_t to_position = to->GetLifetimeStart();
+
+  LiveInterval* destination = nullptr;
+  LiveInterval* source = nullptr;
+
+  LiveInterval* current = interval;
+
+  // Check the intervals that cover `from` and `to`.
+  while ((current != nullptr) && (source == nullptr || destination == nullptr)) {
+    if (current->Covers(from_position)) {
+      DCHECK(source == nullptr);
+      source = current;
+    }
+    if (current->Covers(to_position)) {
+      DCHECK(destination == nullptr);
+      destination = current;
+    }
+
+    current = current->GetNextSibling();
+  }
+
+  if (destination == source) {
+    // Interval was not split.
+    return;
+  }
+
+  if (!destination->HasRegister()) {
+    // Values are eagerly spilled. Spill slot already contains appropriate value.
+    return;
+  }
+
+  // If `from` has only one successor, we can put the moves at the exit of it. Otherwise
+  // we need to put the moves at the entry of `to`.
+  if (from->GetSuccessors().Size() == 1) {
+    InsertParallelMoveAtExitOf(from, ConvertToLocation(source), ConvertToLocation(destination));
+  } else {
+    DCHECK_EQ(to->GetPredecessors().Size(), 1u);
+    InsertParallelMoveAtEntryOf(to, ConvertToLocation(source), ConvertToLocation(destination));
+  }
+}
+
+// Returns the location of `interval`, or siblings of `interval`, at `position`.
+static Location FindLocationAt(LiveInterval* interval, size_t position) {
+  LiveInterval* current = interval;
+  while (!current->Covers(position)) {
+    current = current->GetNextSibling();
+    DCHECK(current != nullptr);
+  }
+  return ConvertToLocation(current);
+}
+
+void RegisterAllocator::Resolve() {
+  codegen_->ComputeFrameSize(spill_slots_.Size());
+
+  // Adjust the Out Location of instructions.
+  // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration.
+  for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) {
+    HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i);
+    LiveInterval* current = instruction->GetLiveInterval();
+    LocationSummary* locations = instruction->GetLocations();
+    Location location = locations->Out();
+    if (instruction->AsParameterValue() != nullptr) {
+      // Now that we know the frame size, adjust the parameter's location.
+      if (location.IsStackSlot()) {
+        location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize());
+        current->SetSpillSlot(location.GetStackIndex());
+        locations->SetOut(location);
+      } else if (location.IsDoubleStackSlot()) {
+        location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize());
+        current->SetSpillSlot(location.GetStackIndex());
+        locations->SetOut(location);
+      } else if (current->HasSpillSlot()) {
+        current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize());
+      }
+    }
+
+    Location source = ConvertToLocation(current);
+
+    if (location.IsUnallocated()) {
+      if (location.GetPolicy() == Location::kSameAsFirstInput) {
+        locations->SetInAt(0, source);
+      }
+      locations->SetOut(source);
+    } else {
+      DCHECK(source.Equals(location));
+    }
+  }
+
+  // Connect siblings.
+  for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) {
+    HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i);
+    ConnectSiblings(instruction->GetLiveInterval());
+  }
+
+  // Resolve non-linear control flow across branches. Order does not matter.
+  for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+    BitVector* live = liveness_.GetLiveInSet(*block);
+    for (uint32_t idx : live->Indexes()) {
+      HInstruction* current = liveness_.GetInstructionFromSsaIndex(idx);
+      LiveInterval* interval = current->GetLiveInterval();
+      for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
+        ConnectSplitSiblings(interval, block->GetPredecessors().Get(i), block);
+      }
+    }
+  }
+
+  // Resolve phi inputs. Order does not matter.
+  for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) {
+    HBasicBlock* current = it.Current();
+    for (HInstructionIterator it(current->GetPhis()); !it.Done(); it.Advance()) {
+      HInstruction* phi = it.Current();
+      for (size_t i = 0, e = current->GetPredecessors().Size(); i < e; ++i) {
+        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());
+        InsertParallelMoveAtExitOf(predecessor, source, destination);
+      }
+    }
+  }
 }
 
 }  // namespace art
diff --git a/compiler/optimizing/register_allocator.h b/compiler/optimizing/register_allocator.h
index 3393a04d77..1b5585f36c 100644
--- a/compiler/optimizing/register_allocator.h
+++ b/compiler/optimizing/register_allocator.h
@@ -23,7 +23,12 @@
 namespace art {
 
 class CodeGenerator;
+class HBasicBlock;
+class HGraph;
+class HInstruction;
+class HParallelMove;
 class LiveInterval;
+class Location;
 class SsaLivenessAnalysis;
 
 /**
@@ -31,26 +36,23 @@ class SsaLivenessAnalysis;
  */
 class RegisterAllocator {
  public:
-  RegisterAllocator(ArenaAllocator* allocator, const CodeGenerator& codegen);
+  RegisterAllocator(ArenaAllocator* allocator,
+                    CodeGenerator* codegen,
+                    const SsaLivenessAnalysis& analysis);
 
   // Main entry point for the register allocator. Given the liveness analysis,
   // allocates registers to live intervals.
-  void AllocateRegisters(const SsaLivenessAnalysis& liveness) {
-    processing_core_registers_ = true;
-    AllocateRegistersInternal(liveness);
-    processing_core_registers_ = false;
-    AllocateRegistersInternal(liveness);
-  }
+  void AllocateRegisters();
 
   // Validate that the register allocator did not allocate the same register to
   // intervals that intersect each other. Returns false if it did not.
-  bool Validate(const SsaLivenessAnalysis& liveness, bool log_fatal_on_failure) {
+  bool Validate(bool log_fatal_on_failure) {
     processing_core_registers_ = true;
-    if (!ValidateInternal(liveness, log_fatal_on_failure)) {
+    if (!ValidateInternal(log_fatal_on_failure)) {
       return false;
     }
     processing_core_registers_ = false;
-    return ValidateInternal(liveness, log_fatal_on_failure);
+    return ValidateInternal(log_fatal_on_failure);
   }
 
   // Helper method for validation. Used by unit testing.
@@ -61,11 +63,21 @@ class RegisterAllocator {
                                 bool processing_core_registers,
                                 bool log_fatal_on_failure);
 
+  static bool CanAllocateRegistersFor(const HGraph& graph, InstructionSet instruction_set);
+  static bool Supports(InstructionSet instruction_set) {
+    return instruction_set == kX86;
+  }
+
+  size_t GetNumberOfSpillSlots() const {
+    return spill_slots_.Size();
+  }
+
  private:
   // Main methods of the allocator.
   void LinearScan();
   bool TryAllocateFreeReg(LiveInterval* interval);
   bool AllocateBlockedReg(LiveInterval* interval);
+  void Resolve();
 
   // Add `interval` in the sorted list of unhandled intervals.
   void AddToUnhandled(LiveInterval* interval);
@@ -76,16 +88,33 @@ class RegisterAllocator {
   // Returns whether `reg` is blocked by the code generator.
   bool IsBlocked(int reg) const;
 
+  // Update the interval for the register in `location` to cover [start, end).
+  void BlockRegister(Location location, size_t start, size_t end, Primitive::Type type);
+
   // Allocate a spill slot for the given interval.
   void AllocateSpillSlotFor(LiveInterval* interval);
 
+  // Connect adjacent siblings within blocks.
+  void ConnectSiblings(LiveInterval* interval);
+
+  // Connect siblings between block entries and exits.
+  void ConnectSplitSiblings(LiveInterval* interval, HBasicBlock* from, HBasicBlock* to) const;
+
+  // Helper methods to insert parallel moves in the graph.
+  void InsertParallelMoveAtExitOf(HBasicBlock* block, Location source, Location destination) const;
+  void InsertParallelMoveAtEntryOf(HBasicBlock* block, Location source, Location destination) const;
+  void InsertMoveAfter(HInstruction* instruction, Location source, Location destination) const;
+  void AddInputMoveFor(HInstruction* instruction, Location source, Location destination) const;
+  void InsertParallelMoveAt(size_t position, Location source, Location destination) const;
+
   // Helper methods.
-  void AllocateRegistersInternal(const SsaLivenessAnalysis& liveness);
-  bool ValidateInternal(const SsaLivenessAnalysis& liveness, bool log_fatal_on_failure) const;
-  void DumpInterval(std::ostream& stream, LiveInterval* interval);
+  void AllocateRegistersInternal();
+  bool ValidateInternal(bool log_fatal_on_failure) const;
+  void DumpInterval(std::ostream& stream, LiveInterval* interval) const;
 
   ArenaAllocator* const allocator_;
-  const CodeGenerator& codegen_;
+  CodeGenerator* const codegen_;
+  const SsaLivenessAnalysis& liveness_;
 
   // List of intervals that must be processed, ordered by start position. Last entry
   // is the interval that has the lowest start position.
@@ -102,6 +131,10 @@ class RegisterAllocator {
   // That is, they have a lifetime hole that spans the start of the new interval.
   GrowableArray<LiveInterval*> inactive_;
 
+  // Fixed intervals for physical registers. Such an interval covers the positions
+  // where an instruction requires a specific register.
+  GrowableArray<LiveInterval*> physical_register_intervals_;
+
   // The spill slots allocated for live intervals.
   GrowableArray<size_t> spill_slots_;
 
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index ff9b9beefc..bfabc5ad27 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -43,9 +43,9 @@ static bool Check(const uint16_t* data) {
   CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86);
   SsaLivenessAnalysis liveness(*graph, codegen);
   liveness.Analyze();
-  RegisterAllocator register_allocator(&allocator, *codegen);
-  register_allocator.AllocateRegisters(liveness);
-  return register_allocator.Validate(liveness, false);
+  RegisterAllocator register_allocator(&allocator, codegen, liveness);
+  register_allocator.AllocateRegisters();
+  return register_allocator.Validate(false);
 }
 
 /**
@@ -300,9 +300,9 @@ TEST(RegisterAllocatorTest, Loop3) {
   CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86);
   SsaLivenessAnalysis liveness(*graph, codegen);
   liveness.Analyze();
-  RegisterAllocator register_allocator(&allocator, *codegen);
-  register_allocator.AllocateRegisters(liveness);
-  ASSERT_TRUE(register_allocator.Validate(liveness, false));
+  RegisterAllocator register_allocator(&allocator, codegen, liveness);
+  register_allocator.AllocateRegisters();
+  ASSERT_TRUE(register_allocator.Validate(false));
 
   HBasicBlock* loop_header = graph->GetBlocks().Get(2);
   HPhi* phi = loop_header->GetFirstPhi()->AsPhi();
@@ -314,7 +314,7 @@ TEST(RegisterAllocatorTest, Loop3) {
   ASSERT_NE(phi_interval->GetRegister(), loop_update->GetRegister());
 
   HBasicBlock* return_block = graph->GetBlocks().Get(3);
-  HReturn* ret = return_block->GetFirstInstruction()->AsReturn();
+  HReturn* ret = return_block->GetLastInstruction()->AsReturn();
   ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister());
 }
 
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 7903ad6cff..fc3eb660d5 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -172,6 +172,7 @@ class LiveInterval : public ArenaObject {
       // Last use is in the following block.
       first_range_->start_ = start_block_position;
     } else {
+      DCHECK(first_range_->GetStart() > position);
       // There is a hole in the interval. Create a new range.
       first_range_ = new (allocator_) LiveRange(start_block_position, position, first_range_);
     }
@@ -192,6 +193,7 @@ class LiveInterval : public ArenaObject {
       // There is a use in the following block.
       first_range_->start_ = start;
     } else {
+      DCHECK(first_range_->GetStart() > end);
       // There is a hole in the interval. Create a new range.
       first_range_ = new (allocator_) LiveRange(start, end, first_range_);
     }
diff --git a/test/404-optimizing-allocator/expected.txt b/test/404-optimizing-allocator/expected.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/404-optimizing-allocator/expected.txt
diff --git a/test/404-optimizing-allocator/info.txt b/test/404-optimizing-allocator/info.txt
new file mode 100644
index 0000000000..930d42f3f1
--- /dev/null
+++ b/test/404-optimizing-allocator/info.txt
@@ -0,0 +1 @@
+Initial tests for testing the optimizing compiler's register allocator.
diff --git a/test/404-optimizing-allocator/src/Main.java b/test/404-optimizing-allocator/src/Main.java
new file mode 100644
index 0000000000..60477f9d8e
--- /dev/null
+++ b/test/404-optimizing-allocator/src/Main.java
@@ -0,0 +1,154 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Note that $opt$reg$ is a marker for the optimizing compiler to ensure
+// it does use its register allocator.
+
+public class Main {
+  public static void main(String[] args) {
+
+    expectEquals(4, $opt$reg$TestLostCopy());
+    expectEquals(-10, $opt$reg$TestTwoLive());
+    expectEquals(-20, $opt$reg$TestThreeLive());
+    expectEquals(5, $opt$reg$TestFourLive());
+    expectEquals(10, $opt$reg$TestMultipleLive());
+    expectEquals(1, $opt$reg$TestWithBreakAndContinue());
+    expectEquals(-15, $opt$reg$testSpillInIf(5, 6, 7));
+    expectEquals(-567, $opt$reg$TestAgressiveLive(1, 2, 3, 4, 5, 6, 7));
+  }
+
+  public static int $opt$reg$TestLostCopy() {
+    int a = 0;
+    int b = 0;
+    do {
+      b = a;
+      a++;
+    } while (a != 5);
+    return b;
+  }
+
+  public static int $opt$reg$TestTwoLive() {
+    int a = 0;
+    int b = 0;
+    do {
+      a++;
+      b += 3;
+    } while (a != 5);
+    return a - b;
+  }
+
+  public static int $opt$reg$TestThreeLive() {
+    int a = 0;
+    int b = 0;
+    int c = 0;
+    do {
+      a++;
+      b += 3;
+      c += 2;
+    } while (a != 5);
+    return a - b - c;
+  }
+
+  public static int $opt$reg$TestFourLive() {
+    int a = 0;
+    int b = 0;
+    int c = 0;
+    int d = 0;
+    do {
+      a++;
+      b += 3;
+      c += 2;
+      d++;
+    } while (a != 5);
+    return d;
+  }
+
+  public static int $opt$reg$TestMultipleLive() {
+    int a = 0;
+    int b = 0;
+    int c = 0;
+    int d = 0;
+    int e = 0;
+    int f = 0;
+    int g = 0;
+    do {
+      a++;
+      b++;
+      c++;
+      d++;
+      e += 3;
+      f += 2;
+      g += 2;
+    } while (a != 5);
+    return f;
+  }
+
+  public static int $opt$reg$TestWithBreakAndContinue() {
+    int a = 0;
+    int b = 0;
+    do {
+      a++;
+      if (a == 2) {
+        continue;
+      }
+      b++;
+      if (a == 5) {
+        break;
+      }
+    } while (true);
+    return a - b;
+  }
+
+  public static int $opt$reg$testSpillInIf(int a, int b, int c) {
+    int d = 0;
+    int e = 0;
+    if (a == 5) {
+      b++;
+      c++;
+      d += 2;
+      e += 3;
+    }
+
+    return a - b - c - d - e;
+  }
+
+  public static int $opt$reg$TestAgressiveLive(int a, int b, int c, int d, int e, int f, int g) {
+    int h = a - b;
+    int i = c - d;
+    int j = e - f;
+    int k = 42 + g - a;
+    do {
+      b++;
+      while (k != 1) {
+        --k;
+        ++i;
+        if (i == 9) {
+          ++i;
+        }
+        j += 5;
+      }
+      k = 9;
+      h++;
+    } while (h != 5);
+    return a - b - c - d - e - f - g - h - i - j - k;
+  }
+
+  public static void expectEquals(int expected, int value) {
+    if (expected != value) {
+      throw new Error("Expected: " + expected + ", got: " + value);
+    }
+  }
+}