More code generation for the optimizing compiler.

- Add HReturn instruction
- Generate code for locals/if/return
- Setup infrastructure for register allocation. Currently
  emulate a stack.

Change-Id: Ib28c2dba80f6c526177ed9a7b09c0689ac8122fb

12 files changed, 584 insertions, 66 deletions

diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index 190c925..8c6a8cb 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -28,19 +28,25 @@ void HGraphBuilder::InitializeLocals(int count) {
   for (int i = 0; i < count; i++) {
     HLocal* local = new (arena_) HLocal(i);
     entry_block_->AddInstruction(local);
-    locals_.Put(0, local);
+    locals_.Put(i, local);
   }
 }
 
 static bool CanHandleCodeItem(const DexFile::CodeItem& code_item) {
-  if (code_item.tries_size_ > 0) return false;
-  if (code_item.outs_size_ > 0) return false;
-  if (code_item.ins_size_ > 0) return false;
+  if (code_item.tries_size_ > 0) {
+    return false;
+  } else if (code_item.outs_size_ > 0) {
+    return false;
+  } else if (code_item.ins_size_ > 0) {
+    return false;
+  }
   return true;
 }
 
 HGraph* HGraphBuilder::BuildGraph(const DexFile::CodeItem& code_item) {
-  if (!CanHandleCodeItem(code_item)) return nullptr;
+  if (!CanHandleCodeItem(code_item)) {
+    return nullptr;
+  }
 
   const uint16_t* code_ptr = code_item.insns_;
   const uint16_t* code_end = code_item.insns_ + code_item.insns_size_in_code_units_;
@@ -78,7 +84,9 @@ HGraph* HGraphBuilder::BuildGraph(const DexFile::CodeItem& code_item) {
 
 void HGraphBuilder::MaybeUpdateCurrentBlock(size_t index) {
   HBasicBlock* block = FindBlockStartingAt(index);
-  if (block == nullptr) return;
+  if (block == nullptr) {
+    return;
+  }
 
   if (current_block_ != nullptr) {
     // Branching instructions clear current_block, so we know
@@ -131,7 +139,9 @@ HBasicBlock* HGraphBuilder::FindBlockStartingAt(int32_t index) const {
 }
 
 bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, int32_t dex_offset) {
-  if (current_block_ == nullptr) return true;  // Dead code
+  if (current_block_ == nullptr) {
+    return true;  // Dead code
+  }
 
   switch (instruction.Opcode()) {
     case Instruction::CONST_4: {
@@ -140,11 +150,14 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, int32_
       UpdateLocal(register_index, constant);
       break;
     }
-    case Instruction::RETURN_VOID:
+
+    case Instruction::RETURN_VOID: {
       current_block_->AddInstruction(new (arena_) HReturnVoid());
       current_block_->AddSuccessor(exit_block_);
       current_block_ = nullptr;
       break;
+    }
+
     case Instruction::IF_EQ: {
       HInstruction* first = LoadLocal(instruction.VRegA());
       HInstruction* second = LoadLocal(instruction.VRegB());
@@ -159,6 +172,7 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, int32_
       current_block_ = nullptr;
       break;
     }
+
     case Instruction::GOTO:
     case Instruction::GOTO_16:
     case Instruction::GOTO_32: {
@@ -169,8 +183,18 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, int32_
       current_block_ = nullptr;
       break;
     }
+
+    case Instruction::RETURN: {
+      HInstruction* value = LoadLocal(instruction.VRegA());
+      current_block_->AddInstruction(new (arena_) HReturn(value));
+      current_block_->AddSuccessor(exit_block_);
+      current_block_ = nullptr;
+      break;
+    }
+
     case Instruction::NOP:
       break;
+
     default:
       return false;
   }
@@ -178,15 +202,27 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, int32_
 }
 
 HIntConstant* HGraphBuilder::GetConstant0() {
-  if (constant0_ != nullptr) return constant0_;
-  HIntConstant* constant = new(arena_) HIntConstant(0);
-  entry_block_->AddInstruction(constant);
-  return constant;
+  if (constant0_ != nullptr) {
+    return constant0_;
+  }
+  constant0_ = new(arena_) HIntConstant(0);
+  entry_block_->AddInstruction(constant0_);
+  return constant0_;
+}
+
+HIntConstant* HGraphBuilder::GetConstant1() {
+  if (constant1_ != nullptr) {
+    return constant1_;
+  }
+  constant1_ = new(arena_) HIntConstant(1);
+  entry_block_->AddInstruction(constant1_);
+  return constant1_;
 }
 
 HIntConstant* HGraphBuilder::GetConstant(int constant) {
   switch (constant) {
     case 0: return GetConstant0();
+    case 1: return GetConstant1();
     default: {
       HIntConstant* instruction = new (arena_) HIntConstant(constant);
       entry_block_->AddInstruction(instruction);
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index 399dd63..fff83a1 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -41,7 +41,8 @@ class HGraphBuilder : public ValueObject {
         exit_block_(nullptr),
         current_block_(nullptr),
         graph_(nullptr),
-        constant0_(nullptr) { }
+        constant0_(nullptr),
+        constant1_(nullptr) { }
 
   HGraph* BuildGraph(const DexFile::CodeItem& code);
 
@@ -58,6 +59,7 @@ class HGraphBuilder : public ValueObject {
   HBasicBlock* FindBlockStartingAt(int32_t index) const;
 
   HIntConstant* GetConstant0();
+  HIntConstant* GetConstant1();
   HIntConstant* GetConstant(int constant);
   void InitializeLocals(int count);
   HLocal* GetLocalAt(int register_index) const;
@@ -79,6 +81,7 @@ class HGraphBuilder : public ValueObject {
   HGraph* graph_;
 
   HIntConstant* constant0_;
+  HIntConstant* constant1_;
 
   DISALLOW_COPY_AND_ASSIGN(HGraphBuilder);
 };
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index 01fc23b..56342aa 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -26,9 +26,11 @@
 namespace art {
 
 void CodeGenerator::Compile(CodeAllocator* allocator) {
-  GenerateFrameEntry();
   const GrowableArray<HBasicBlock*>* blocks = graph()->blocks();
-  for (size_t i = 0; i < blocks->Size(); i++) {
+  DCHECK(blocks->Get(0) == graph()->entry_block());
+  DCHECK(GoesToNextBlock(graph()->entry_block(), blocks->Get(1)));
+  CompileEntryBlock();
+  for (size_t i = 1; i < blocks->Size(); i++) {
     CompileBlock(blocks->Get(i));
   }
   size_t code_size = assembler_->CodeSize();
@@ -37,17 +39,54 @@ void CodeGenerator::Compile(CodeAllocator* allocator) {
   assembler_->FinalizeInstructions(code);
 }
 
+void CodeGenerator::CompileEntryBlock() {
+  HGraphVisitor* location_builder = GetLocationBuilder();
+  // The entry block contains all locals for this method. By visiting the entry block,
+  // we're computing the required frame size.
+  for (HInstructionIterator it(graph()->entry_block()); !it.Done(); it.Advance()) {
+    HInstruction* current = it.Current();
+    // Instructions in the entry block should not generate code.
+    if (kIsDebugBuild) {
+      current->Accept(location_builder);
+      DCHECK(current->locations() == nullptr);
+    }
+    current->Accept(this);
+  }
+  GenerateFrameEntry();
+}
+
 void CodeGenerator::CompileBlock(HBasicBlock* block) {
   Bind(GetLabelOf(block));
+  HGraphVisitor* location_builder = GetLocationBuilder();
   for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
-    it.Current()->Accept(this);
+    // For each instruction, we emulate a stack-based machine, where the inputs are popped from
+    // the runtime stack, and the result is pushed on the stack. We currently can do this because
+    // we do not perform any code motion, and the Dex format does not reference individual
+    // instructions but uses registers instead (our equivalent of HLocal).
+    HInstruction* current = it.Current();
+    current->Accept(location_builder);
+    InitLocations(current);
+    current->Accept(this);
+    if (current->locations() != nullptr && current->locations()->Out().IsValid()) {
+      Push(current, current->locations()->Out());
+    }
+  }
+}
+
+void CodeGenerator::InitLocations(HInstruction* instruction) {
+  if (instruction->locations() == nullptr) return;
+  for (int i = 0; i < instruction->InputCount(); i++) {
+    Location location = instruction->locations()->InAt(i);
+    if (location.IsValid()) {
+      // Move the input to the desired location.
+      Move(instruction->InputAt(i), location);
+    }
   }
 }
 
-bool CodeGenerator::GoesToNextBlock(HGoto* goto_instruction) const {
-  HBasicBlock* successor = goto_instruction->GetSuccessor();
+bool CodeGenerator::GoesToNextBlock(HBasicBlock* current, HBasicBlock* next) const {
   // We currently iterate over the block in insertion order.
-  return goto_instruction->block()->block_id() + 1 == successor->block_id();
+  return current->block_id() + 1 == next->block_id();
 }
 
 Label* CodeGenerator::GetLabelOf(HBasicBlock* block) const {
diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h
index 2a5ae7d..c406378 100644
--- a/compiler/optimizing/code_generator.h
+++ b/compiler/optimizing/code_generator.h
@@ -17,6 +17,7 @@
 #ifndef ART_COMPILER_OPTIMIZING_CODE_GENERATOR_H_
 #define ART_COMPILER_OPTIMIZING_CODE_GENERATOR_H_
 
+#include "globals.h"
 #include "instruction_set.h"
 #include "memory_region.h"
 #include "nodes.h"
@@ -35,12 +36,82 @@ class CodeAllocator {
   DISALLOW_COPY_AND_ASSIGN(CodeAllocator);
 };
 
+/**
+ * A Location is an abstraction over the potential location
+ * of an instruction. It could be in register or stack.
+ */
+class Location : public ValueObject {
+ public:
+  template<typename T>
+  T reg() const { return static_cast<T>(reg_); }
+
+  Location() : reg_(kInvalid) { }
+  explicit Location(uword reg) : reg_(reg) { }
+
+  static Location RegisterLocation(uword reg) {
+    return Location(reg);
+  }
+
+  bool IsValid() const { return reg_ != kInvalid; }
+
+  Location(const Location& other) : reg_(other.reg_) { }
+
+  Location& operator=(const Location& other) {
+    reg_ = other.reg_;
+    return *this;
+  }
+
+ private:
+  // The target register for that location.
+  // TODO: Support stack location.
+  uword reg_;
+  static const uword kInvalid = -1;
+};
+
+/**
+ * The code generator computes LocationSummary for each instruction so that
+ * the instruction itself knows what code to generate: where to find the inputs
+ * and where to place the result.
+ *
+ * The intent is to have the code for generating the instruction independent of
+ * register allocation. A register allocator just has to provide a LocationSummary.
+ */
+class LocationSummary : public ArenaObject {
+ public:
+  explicit LocationSummary(HInstruction* instruction)
+      : inputs(instruction->block()->graph()->arena(), instruction->InputCount()) {
+    inputs.SetSize(instruction->InputCount());
+    for (int i = 0; i < instruction->InputCount(); i++) {
+      inputs.Put(i, Location());
+    }
+  }
+
+  void SetInAt(uint32_t at, Location location) {
+    inputs.Put(at, location);
+  }
+
+  Location InAt(uint32_t at) const {
+    return inputs.Get(at);
+  }
+
+  void SetOut(Location location) {
+    output = Location(location);
+  }
+
+  Location Out() const { return output; }
+
+ private:
+  GrowableArray<Location> inputs;
+  Location output;
+
+  DISALLOW_COPY_AND_ASSIGN(LocationSummary);
+};
+
 class CodeGenerator : public HGraphVisitor {
  public:
   // Compiles the graph to executable instructions. Returns whether the compilation
   // succeeded.
-  static bool CompileGraph(
-      HGraph* graph, InstructionSet instruction_set, CodeAllocator* allocator);
+  static bool CompileGraph(HGraph* graph, InstructionSet instruction_set, CodeAllocator* allocator);
 
   Assembler* assembler() const { return assembler_; }
 
@@ -54,20 +125,31 @@ class CodeGenerator : public HGraphVisitor {
 
  protected:
   CodeGenerator(Assembler* assembler, HGraph* graph)
-      : HGraphVisitor(graph), assembler_(assembler), block_labels_(graph->arena(), 0) {
+      : HGraphVisitor(graph),
+        frame_size_(0),
+        assembler_(assembler),
+        block_labels_(graph->arena(), 0) {
     block_labels_.SetSize(graph->blocks()->Size());
   }
 
   Label* GetLabelOf(HBasicBlock* block) const;
-  bool GoesToNextBlock(HGoto* got) const;
+  bool GoesToNextBlock(HBasicBlock* current, HBasicBlock* next) const;
+
+  // Frame size required for this method.
+  uint32_t frame_size_;
 
- private:
   virtual void GenerateFrameEntry() = 0;
   virtual void GenerateFrameExit() = 0;
   virtual void Bind(Label* label) = 0;
+  virtual void Move(HInstruction* instruction, Location location) = 0;
+  virtual void Push(HInstruction* instruction, Location location) = 0;
+  virtual HGraphVisitor* GetLocationBuilder() = 0;
 
+ private:
+  void InitLocations(HInstruction* instruction);
   void Compile(CodeAllocator* allocator);
   void CompileBlock(HBasicBlock* block);
+  void CompileEntryBlock();
 
   Assembler* const assembler_;
 
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 356e909..62bf7ba 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -24,28 +24,52 @@ namespace art {
 namespace arm {
 
 void CodeGeneratorARM::GenerateFrameEntry() {
-  RegList registers = (1 << LR) | (1 << FP);
-  __ PushList(registers);
+  __ PushList((1 << FP) | (1 << LR));
+  __ mov(FP, ShifterOperand(SP));
+  if (frame_size_ != 0) {
+    __ AddConstant(SP, -frame_size_);
+  }
 }
 
 void CodeGeneratorARM::GenerateFrameExit() {
-  RegList registers = (1 << PC) | (1 << FP);
-  __ PopList(registers);
+  __ mov(SP, ShifterOperand(FP));
+  __ PopList((1 << FP) | (1 << PC));
 }
 
 void CodeGeneratorARM::Bind(Label* label) {
   __ Bind(label);
 }
 
+void CodeGeneratorARM::Push(HInstruction* instruction, Location location) {
+  __ Push(location.reg<Register>());
+}
+
+void CodeGeneratorARM::Move(HInstruction* instruction, Location location) {
+  HIntConstant* constant = instruction->AsIntConstant();
+  if (constant != nullptr) {
+    __ LoadImmediate(location.reg<Register>(), constant->value());
+  } else {
+    __ Pop(location.reg<Register>());
+  }
+}
+
+void LocationsBuilderARM::VisitGoto(HGoto* got) {
+  got->set_locations(nullptr);
+}
+
 void CodeGeneratorARM::VisitGoto(HGoto* got) {
   HBasicBlock* successor = got->GetSuccessor();
   if (graph()->exit_block() == successor) {
     GenerateFrameExit();
-  } else if (!GoesToNextBlock(got)) {
+  } else if (!GoesToNextBlock(got->block(), successor)) {
     __ b(GetLabelOf(successor));
   }
 }
 
+void LocationsBuilderARM::VisitExit(HExit* exit) {
+  exit->set_locations(nullptr);
+}
+
 void CodeGeneratorARM::VisitExit(HExit* exit) {
   if (kIsDebugBuild) {
     __ Comment("Unreachable");
@@ -53,33 +77,101 @@ void CodeGeneratorARM::VisitExit(HExit* exit) {
   }
 }
 
+void LocationsBuilderARM::VisitIf(HIf* if_instr) {
+  LocationSummary* locations = new (graph()->arena()) LocationSummary(if_instr);
+  locations->SetInAt(0, Location(R0));
+  if_instr->set_locations(locations);
+}
+
 void CodeGeneratorARM::VisitIf(HIf* if_instr) {
-  LOG(FATAL) << "UNIMPLEMENTED";
+  // TODO: Generate the input as a condition, instead of materializing in a register.
+  __ cmp(if_instr->locations()->InAt(0).reg<Register>(), ShifterOperand(0));
+  __ b(GetLabelOf(if_instr->IfFalseSuccessor()), EQ);
+  if (!GoesToNextBlock(if_instr->block(), if_instr->IfTrueSuccessor())) {
+    __ b(GetLabelOf(if_instr->IfTrueSuccessor()));
+  }
+}
+
+void LocationsBuilderARM::VisitEqual(HEqual* equal) {
+  LocationSummary* locations = new (graph()->arena()) LocationSummary(equal);
+  locations->SetInAt(0, Location(R0));
+  locations->SetInAt(1, Location(R1));
+  locations->SetOut(Location(R0));
+  equal->set_locations(locations);
 }
 
 void CodeGeneratorARM::VisitEqual(HEqual* equal) {
-  LOG(FATAL) << "UNIMPLEMENTED";
+  LocationSummary* locations = equal->locations();
+  __ teq(locations->InAt(0).reg<Register>(),
+         ShifterOperand(locations->InAt(1).reg<Register>()));
+  __ mov(locations->Out().reg<Register>(), ShifterOperand(1), EQ);
+  __ mov(locations->Out().reg<Register>(), ShifterOperand(0), NE);
+}
+
+void LocationsBuilderARM::VisitLocal(HLocal* local) {
+  local->set_locations(nullptr);
 }
 
 void CodeGeneratorARM::VisitLocal(HLocal* local) {
-  LOG(FATAL) << "UNIMPLEMENTED";
+  DCHECK_EQ(local->block(), graph()->entry_block());
+  frame_size_ += kWordSize;
+}
+
+void LocationsBuilderARM::VisitLoadLocal(HLoadLocal* load) {
+  LocationSummary* locations = new (graph()->arena()) LocationSummary(load);
+  locations->SetOut(Location(R0));
+  load->set_locations(locations);
+}
+
+static int32_t GetStackSlot(HLocal* local) {
+  // We are currently using FP to access locals, so the offset must be negative.
+  return (local->reg_number() + 1) * -kWordSize;
+}
+
+void CodeGeneratorARM::VisitLoadLocal(HLoadLocal* load) {
+  LocationSummary* locations = load->locations();
+  __ LoadFromOffset(kLoadWord, locations->Out().reg<Register>(),
+                    FP, GetStackSlot(load->GetLocal()));
+}
+
+void LocationsBuilderARM::VisitStoreLocal(HStoreLocal* store) {
+  LocationSummary* locations = new (graph()->arena()) LocationSummary(store);
+  locations->SetInAt(1, Location(R0));
+  store->set_locations(locations);
 }
 
-void CodeGeneratorARM::VisitLoadLocal(HLoadLocal* local) {
-  LOG(FATAL) << "UNIMPLEMENTED";
+void CodeGeneratorARM::VisitStoreLocal(HStoreLocal* store) {
+  LocationSummary* locations = store->locations();
+  __ StoreToOffset(kStoreWord, locations->InAt(1).reg<Register>(),
+                   FP, GetStackSlot(store->GetLocal()));
 }
 
-void CodeGeneratorARM::VisitStoreLocal(HStoreLocal* local) {
-  LOG(FATAL) << "UNIMPLEMENTED";
+void LocationsBuilderARM::VisitIntConstant(HIntConstant* constant) {
+  constant->set_locations(nullptr);
 }
 
 void CodeGeneratorARM::VisitIntConstant(HIntConstant* constant) {
-  LOG(FATAL) << "UNIMPLEMENTED";
+  // Will be generated at use site.
+}
+
+void LocationsBuilderARM::VisitReturnVoid(HReturnVoid* ret) {
+  ret->set_locations(nullptr);
 }
 
 void CodeGeneratorARM::VisitReturnVoid(HReturnVoid* ret) {
   GenerateFrameExit();
 }
 
+void LocationsBuilderARM::VisitReturn(HReturn* ret) {
+  LocationSummary* locations = new (graph()->arena()) LocationSummary(ret);
+  locations->SetInAt(0, Location(R0));
+  ret->set_locations(locations);
+}
+
+void CodeGeneratorARM::VisitReturn(HReturn* ret) {
+  DCHECK_EQ(ret->locations()->InAt(0).reg<Register>(), R0);
+  GenerateFrameExit();
+}
+
 }  // namespace arm
 }  // namespace art
diff --git a/compiler/optimizing/code_generator_arm.h b/compiler/optimizing/code_generator_arm.h
index 27a83b8..33d8e62 100644
--- a/compiler/optimizing/code_generator_arm.h
+++ b/compiler/optimizing/code_generator_arm.h
@@ -27,10 +27,25 @@ class Label;
 
 namespace arm {
 
+class LocationsBuilderARM : public HGraphVisitor {
+ public:
+  explicit LocationsBuilderARM(HGraph* graph) : HGraphVisitor(graph) { }
+
+#define DECLARE_VISIT_INSTRUCTION(name)     \
+  virtual void Visit##name(H##name* instr);
+
+  FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
+
+#undef DECLARE_VISIT_INSTRUCTION
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(LocationsBuilderARM);
+};
+
 class CodeGeneratorARM : public CodeGenerator {
  public:
   CodeGeneratorARM(Assembler* assembler, HGraph* graph)
-      : CodeGenerator(assembler, graph) { }
+      : CodeGenerator(assembler, graph), location_builder_(graph) { }
 
   // Visit functions for instruction classes.
 #define DECLARE_VISIT_INSTRUCTION(name)     \
@@ -40,10 +55,19 @@ class CodeGeneratorARM : public CodeGenerator {
 
 #undef DECLARE_VISIT_INSTRUCTION
 
+ protected:
+  virtual void GenerateFrameEntry() OVERRIDE;
+  virtual void GenerateFrameExit() OVERRIDE;
+  virtual void Bind(Label* label) OVERRIDE;
+  virtual void Move(HInstruction* instruction, Location location) OVERRIDE;
+  virtual void Push(HInstruction* instruction, Location location) OVERRIDE;
+
+  virtual HGraphVisitor* GetLocationBuilder() OVERRIDE {
+    return &location_builder_;
+  }
+
  private:
-  virtual void GenerateFrameEntry();
-  virtual void GenerateFrameExit();
-  virtual void Bind(Label* label);
+  LocationsBuilderARM location_builder_;
 
   DISALLOW_COPY_AND_ASSIGN(CodeGeneratorARM);
 };
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index ab34599..81ada4d 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -26,6 +26,10 @@ namespace x86 {
 void CodeGeneratorX86::GenerateFrameEntry() {
   __ pushl(EBP);
   __ movl(EBP, ESP);
+
+  if (frame_size_ != 0) {
+    __ subl(ESP, Immediate(frame_size_));
+  }
 }
 
 void CodeGeneratorX86::GenerateFrameExit() {
@@ -37,15 +41,36 @@ void CodeGeneratorX86::Bind(Label* label) {
   __ Bind(label);
 }
 
+void CodeGeneratorX86::Push(HInstruction* instruction, Location location) {
+  __ pushl(location.reg<Register>());
+}
+
+void CodeGeneratorX86::Move(HInstruction* instruction, Location location) {
+  HIntConstant* constant = instruction->AsIntConstant();
+  if (constant != nullptr) {
+    __ movl(location.reg<Register>(), Immediate(constant->value()));
+  } else {
+    __ popl(location.reg<Register>());
+  }
+}
+
+void LocationsBuilderX86::VisitGoto(HGoto* got) {
+  got->set_locations(nullptr);
+}
+
 void CodeGeneratorX86::VisitGoto(HGoto* got) {
   HBasicBlock* successor = got->GetSuccessor();
   if (graph()->exit_block() == successor) {
     GenerateFrameExit();
-  } else if (!GoesToNextBlock(got)) {
+  } else if (!GoesToNextBlock(got->block(), successor)) {
     __ jmp(GetLabelOf(successor));
   }
 }
 
+void LocationsBuilderX86::VisitExit(HExit* exit) {
+  exit->set_locations(nullptr);
+}
+
 void CodeGeneratorX86::VisitExit(HExit* exit) {
   if (kIsDebugBuild) {
     __ Comment("Unreachable");
@@ -53,28 +78,81 @@ void CodeGeneratorX86::VisitExit(HExit* exit) {
   }
 }
 
+void LocationsBuilderX86::VisitIf(HIf* if_instr) {
+  LocationSummary* locations = new (graph()->arena()) LocationSummary(if_instr);
+  locations->SetInAt(0, Location(EAX));
+  if_instr->set_locations(locations);
+}
+
 void CodeGeneratorX86::VisitIf(HIf* if_instr) {
-  LOG(FATAL) << "UNIMPLEMENTED";
+  // TODO: Generate the input as a condition, instead of materializing in a register.
+  __ cmpl(if_instr->locations()->InAt(0).reg<Register>(), Immediate(0));
+  __ j(kEqual, GetLabelOf(if_instr->IfFalseSuccessor()));
+  if (!GoesToNextBlock(if_instr->block(), if_instr->IfTrueSuccessor())) {
+    __ jmp(GetLabelOf(if_instr->IfTrueSuccessor()));
+  }
+}
+
+void LocationsBuilderX86::VisitLocal(HLocal* local) {
+  local->set_locations(nullptr);
 }
 
 void CodeGeneratorX86::VisitLocal(HLocal* local) {
-  LOG(FATAL) << "UNIMPLEMENTED";
+  DCHECK_EQ(local->block(), graph()->entry_block());
+  frame_size_ += kWordSize;
+}
+
+void LocationsBuilderX86::VisitLoadLocal(HLoadLocal* local) {
+  LocationSummary* locations = new (graph()->arena()) LocationSummary(local);
+  locations->SetOut(Location(EAX));
+  local->set_locations(locations);
+}
+
+static int32_t GetStackSlot(HLocal* local) {
+  // We are currently using EBP to access locals, so the offset must be negative.
+  return (local->reg_number() + 1) * -kWordSize;
+}
+
+void CodeGeneratorX86::VisitLoadLocal(HLoadLocal* load) {
+  __ movl(load->locations()->Out().reg<Register>(),
+          Address(EBP, GetStackSlot(load->GetLocal())));
 }
 
-void CodeGeneratorX86::VisitLoadLocal(HLoadLocal* local) {
-  LOG(FATAL) << "UNIMPLEMENTED";
+void LocationsBuilderX86::VisitStoreLocal(HStoreLocal* local) {
+  LocationSummary* locations = new (graph()->arena()) LocationSummary(local);
+  locations->SetInAt(1, Location(EAX));
+  local->set_locations(locations);
 }
 
-void CodeGeneratorX86::VisitStoreLocal(HStoreLocal* local) {
-  LOG(FATAL) << "UNIMPLEMENTED";
+void CodeGeneratorX86::VisitStoreLocal(HStoreLocal* store) {
+  __ movl(Address(EBP, GetStackSlot(store->GetLocal())),
+          store->locations()->InAt(1).reg<Register>());
+}
+
+void LocationsBuilderX86::VisitEqual(HEqual* equal) {
+  LocationSummary* locations = new (graph()->arena()) LocationSummary(equal);
+  locations->SetInAt(0, Location(EAX));
+  locations->SetInAt(1, Location(ECX));
+  locations->SetOut(Location(EAX));
+  equal->set_locations(locations);
 }
 
 void CodeGeneratorX86::VisitEqual(HEqual* equal) {
-  LOG(FATAL) << "UNIMPLEMENTED";
+  __ cmpl(equal->locations()->InAt(0).reg<Register>(),
+          equal->locations()->InAt(1).reg<Register>());
+  __ setb(kEqual, equal->locations()->Out().reg<Register>());
+}
+
+void LocationsBuilderX86::VisitIntConstant(HIntConstant* constant) {
+  constant->set_locations(nullptr);
 }
 
 void CodeGeneratorX86::VisitIntConstant(HIntConstant* constant) {
-  LOG(FATAL) << "UNIMPLEMENTED";
+  // Will be generated at use site.
+}
+
+void LocationsBuilderX86::VisitReturnVoid(HReturnVoid* ret) {
+  ret->set_locations(nullptr);
 }
 
 void CodeGeneratorX86::VisitReturnVoid(HReturnVoid* ret) {
@@ -82,5 +160,17 @@ void CodeGeneratorX86::VisitReturnVoid(HReturnVoid* ret) {
   __ ret();
 }
 
+void LocationsBuilderX86::VisitReturn(HReturn* ret) {
+  LocationSummary* locations = new (graph()->arena()) LocationSummary(ret);
+  locations->SetInAt(0, Location(EAX));
+  ret->set_locations(locations);
+}
+
+void CodeGeneratorX86::VisitReturn(HReturn* ret) {
+  DCHECK_EQ(ret->locations()->InAt(0).reg<Register>(), EAX);
+  GenerateFrameExit();
+  __ ret();
+}
+
 }  // namespace x86
 }  // namespace art
diff --git a/compiler/optimizing/code_generator_x86.h b/compiler/optimizing/code_generator_x86.h
index 7dae2ab..dd146b8 100644
--- a/compiler/optimizing/code_generator_x86.h
+++ b/compiler/optimizing/code_generator_x86.h
@@ -27,12 +27,26 @@ class Label;
 
 namespace x86 {
 
+class LocationsBuilderX86 : public HGraphVisitor {
+ public:
+  explicit LocationsBuilderX86(HGraph* graph) : HGraphVisitor(graph) { }
+
+#define DECLARE_VISIT_INSTRUCTION(name)     \
+  virtual void Visit##name(H##name* instr);
+
+  FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
+
+#undef DECLARE_VISIT_INSTRUCTION
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(LocationsBuilderX86);
+};
+
 class CodeGeneratorX86 : public CodeGenerator {
  public:
   CodeGeneratorX86(Assembler* assembler, HGraph* graph)
-      : CodeGenerator(assembler, graph) { }
+      : CodeGenerator(assembler, graph), location_builder_(graph) { }
 
-  // Visit functions for instruction classes.
 #define DECLARE_VISIT_INSTRUCTION(name)     \
   virtual void Visit##name(H##name* instr);
 
@@ -40,10 +54,19 @@ class CodeGeneratorX86 : public CodeGenerator {
 
 #undef DECLARE_VISIT_INSTRUCTION
 
+ protected:
+  virtual void GenerateFrameEntry() OVERRIDE;
+  virtual void GenerateFrameExit() OVERRIDE;
+  virtual void Bind(Label* label) OVERRIDE;
+  virtual void Move(HInstruction* instruction, Location location) OVERRIDE;
+  virtual void Push(HInstruction* instruction, Location location) OVERRIDE;
+
+  virtual HGraphVisitor* GetLocationBuilder() OVERRIDE {
+    return &location_builder_;
+  }
+
  private:
-  virtual void GenerateFrameEntry();
-  virtual void GenerateFrameExit();
-  virtual void Bind(Label* label);
+  LocationsBuilderX86 location_builder_;
 
   DISALLOW_COPY_AND_ASSIGN(CodeGeneratorX86);
 };
diff --git a/compiler/optimizing/codegen_test.cc b/compiler/optimizing/codegen_test.cc
index 6d4588d..a6ecdfb 100644
--- a/compiler/optimizing/codegen_test.cc
+++ b/compiler/optimizing/codegen_test.cc
@@ -45,7 +45,7 @@ class ExecutableMemoryAllocator : public CodeAllocator {
   DISALLOW_COPY_AND_ASSIGN(ExecutableMemoryAllocator);
 };
 
-static void TestCode(const uint16_t* data) {
+static void TestCode(const uint16_t* data, bool has_result = false, int32_t expected = 0) {
   ArenaPool pool;
   ArenaAllocator arena(&pool);
   HGraphBuilder builder(&arena);
@@ -54,14 +54,17 @@ static void TestCode(const uint16_t* data) {
   ASSERT_NE(graph, nullptr);
   ExecutableMemoryAllocator allocator;
   CHECK(CodeGenerator::CompileGraph(graph, kX86, &allocator));
-  typedef void (*fptr)();
+  typedef int32_t (*fptr)();
 #if defined(__i386__)
-  reinterpret_cast<fptr>(allocator.memory())();
+  int32_t result = reinterpret_cast<fptr>(allocator.memory())();
 #endif
   CHECK(CodeGenerator::CompileGraph(graph, kArm, &allocator));
 #if defined(__arm__)
-  reinterpret_cast<fptr>(allocator.memory())();
+  int32_t result = reinterpret_cast<fptr>(allocator.memory())();
 #endif
+  if (has_result) {
+    CHECK_EQ(result, expected);
+  }
 }
 
 TEST(CodegenTest, ReturnVoid) {
@@ -69,7 +72,7 @@ TEST(CodegenTest, ReturnVoid) {
   TestCode(data);
 }
 
-TEST(PrettyPrinterTest, CFG1) {
+TEST(CodegenTest, CFG1) {
   const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
     Instruction::GOTO | 0x100,
     Instruction::RETURN_VOID);
@@ -77,7 +80,7 @@ TEST(PrettyPrinterTest, CFG1) {
   TestCode(data);
 }
 
-TEST(PrettyPrinterTest, CFG2) {
+TEST(CodegenTest, CFG2) {
   const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
     Instruction::GOTO | 0x100,
     Instruction::GOTO | 0x100,
@@ -86,7 +89,7 @@ TEST(PrettyPrinterTest, CFG2) {
   TestCode(data);
 }
 
-TEST(PrettyPrinterTest, CFG3) {
+TEST(CodegenTest, CFG3) {
   const uint16_t data1[] = ZERO_REGISTER_CODE_ITEM(
     Instruction::GOTO | 0x200,
     Instruction::RETURN_VOID,
@@ -109,7 +112,7 @@ TEST(PrettyPrinterTest, CFG3) {
   TestCode(data3);
 }
 
-TEST(PrettyPrinterTest, CFG4) {
+TEST(CodegenTest, CFG4) {
   const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
     Instruction::RETURN_VOID,
     Instruction::GOTO | 0x100,
@@ -118,4 +121,70 @@ TEST(PrettyPrinterTest, CFG4) {
   TestCode(data);
 }
 
+TEST(CodegenTest, CFG5) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0x100,
+    Instruction::RETURN_VOID);
+
+  TestCode(data);
+}
+
+TEST(CodegenTest, IntConstant) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::RETURN_VOID);
+
+  TestCode(data);
+}
+
+TEST(CodegenTest, Return1) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::RETURN | 0);
+
+  TestCode(data, true, 0);
+}
+
+TEST(CodegenTest, Return2) {
+  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::CONST_4 | 0 | 1 << 8,
+    Instruction::RETURN | 1 << 8);
+
+  TestCode(data, true, 0);
+}
+
+TEST(CodegenTest, Return3) {
+  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::CONST_4 | 1 << 8 | 1 << 12,
+    Instruction::RETURN | 1 << 8);
+
+  TestCode(data, true, 1);
+}
+
+TEST(CodegenTest, ReturnIf1) {
+  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::CONST_4 | 1 << 8 | 1 << 12,
+    Instruction::IF_EQ, 3,
+    Instruction::RETURN | 0 << 8,
+    Instruction::RETURN | 1 << 8);
+
+  TestCode(data, true, 1);
+}
+
+TEST(CodegenTest, ReturnIf2) {
+  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::CONST_4 | 1 << 8 | 1 << 12,
+    Instruction::IF_EQ | 0 << 4 | 1 << 8, 3,
+    Instruction::RETURN | 0 << 8,
+    Instruction::RETURN | 1 << 8);
+
+  TestCode(data, true, 0);
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 16dfb94..a6f3f5a 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -121,6 +121,7 @@ void HGraph::VisitBlockForDominatorTree(HBasicBlock* block,
 }
 
 void HBasicBlock::AddInstruction(HInstruction* instruction) {
+  DCHECK(instruction->block() == nullptr);
   instruction->set_block(this);
   instruction->set_id(graph()->GetNextInstructionId());
   if (first_instruction_ == nullptr) {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index bb08bd0..9418599 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -27,6 +27,7 @@ class HBasicBlock;
 class HInstruction;
 class HIntConstant;
 class HGraphVisitor;
+class LocationSummary;
 
 static const int kDefaultNumberOfBlocks = 8;
 static const int kDefaultNumberOfSuccessors = 2;
@@ -186,12 +187,18 @@ class HBasicBlock : public ArenaObject {
   M(IntConstant)                                           \
   M(LoadLocal)                                             \
   M(Local)                                                 \
+  M(Return)                                                \
   M(ReturnVoid)                                            \
   M(StoreLocal)                                            \
 
+#define FORWARD_DECLARATION(type) class H##type;
+FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
+#undef FORWARD_DECLARATION
+
 #define DECLARE_INSTRUCTION(type)                          \
   virtual void Accept(HGraphVisitor* visitor);             \
   virtual const char* DebugName() const { return #type; }  \
+  virtual H##type* As##type() { return this; }             \
 
 class HUseListNode : public ArenaObject {
  public:
@@ -210,7 +217,14 @@ class HUseListNode : public ArenaObject {
 
 class HInstruction : public ArenaObject {
  public:
-  HInstruction() : previous_(nullptr), next_(nullptr), block_(nullptr), id_(-1), uses_(nullptr) { }
+  HInstruction()
+      : previous_(nullptr),
+        next_(nullptr),
+        block_(nullptr),
+        id_(-1),
+        uses_(nullptr),
+        locations_(nullptr) { }
+
   virtual ~HInstruction() { }
 
   HInstruction* next() const { return next_; }
@@ -236,6 +250,15 @@ class HInstruction : public ArenaObject {
   int id() const { return id_; }
   void set_id(int id) { id_ = id; }
 
+  LocationSummary* locations() const { return locations_; }
+  void set_locations(LocationSummary* locations) { locations_ = locations; }
+
+#define INSTRUCTION_TYPE_CHECK(type)                                           \
+  virtual H##type* As##type() { return nullptr; }
+
+  FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
+#undef INSTRUCTION_TYPE_CHECK
+
  private:
   HInstruction* previous_;
   HInstruction* next_;
@@ -248,6 +271,9 @@ class HInstruction : public ArenaObject {
 
   HUseListNode* uses_;
 
+  // Set by the code generator.
+  LocationSummary* locations_;
+
   friend class HBasicBlock;
 
   DISALLOW_COPY_AND_ASSIGN(HInstruction);
@@ -386,6 +412,20 @@ class HReturnVoid : public HTemplateInstruction<0> {
   DISALLOW_COPY_AND_ASSIGN(HReturnVoid);
 };
 
+// Represents dex's RETURN opcodes. A HReturn is a control flow
+// instruction that branches to the exit block.
+class HReturn : public HTemplateInstruction<1> {
+ public:
+  explicit HReturn(HInstruction* value) {
+    SetRawInputAt(0, value);
+  }
+
+  DECLARE_INSTRUCTION(Return)
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HReturn);
+};
+
 // The exit instruction is the only instruction of the exit block.
 // Instructions aborting the method (HTrow and HReturn) must branch to the
 // exit block.
@@ -422,6 +462,14 @@ class HIf : public HTemplateInstruction<1> {
     SetRawInputAt(0, input);
   }
 
+  HBasicBlock* IfTrueSuccessor() const {
+    return block()->successors()->Get(0);
+  }
+
+  HBasicBlock* IfFalseSuccessor() const {
+    return block()->successors()->Get(1);
+  }
+
   DECLARE_INSTRUCTION(If)
 
  private:
@@ -449,9 +497,11 @@ class HLocal : public HTemplateInstruction<0> {
 
   DECLARE_INSTRUCTION(Local)
 
+  uint16_t reg_number() const { return reg_number_; }
+
  private:
-  // The register number in Dex.
-  uint16_t reg_number_;
+  // The Dex register number.
+  const uint16_t reg_number_;
 
   DISALLOW_COPY_AND_ASSIGN(HLocal);
 };
@@ -463,6 +513,8 @@ class HLoadLocal : public HTemplateInstruction<1> {
     SetRawInputAt(0, local);
   }
 
+  HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
+
   DECLARE_INSTRUCTION(LoadLocal)
 
  private:
@@ -478,6 +530,8 @@ class HStoreLocal : public HTemplateInstruction<2> {
     SetRawInputAt(1, value);
   }
 
+  HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
+
   DECLARE_INSTRUCTION(StoreLocal)
 
  private:
@@ -490,6 +544,8 @@ class HIntConstant : public HTemplateInstruction<0> {
  public:
   explicit HIntConstant(int32_t value) : value_(value) { }
 
+  int32_t value() const { return value_; }
+
   DECLARE_INSTRUCTION(IntConstant)
 
  private:
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index bf13a41..67c4850 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -26,4 +26,7 @@
 #define ONE_REGISTER_CODE_ITEM(...)                                        \
     { 1, 0, 0, 0, 0, 0, NUM_INSTRUCTIONS(__VA_ARGS__), 0, __VA_ARGS__ }
 
+#define TWO_REGISTERS_CODE_ITEM(...)                                       \
+    { 2, 0, 0, 0, 0, 0, NUM_INSTRUCTIONS(__VA_ARGS__), 0, __VA_ARGS__ }
+
 #endif  // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_