Merge "Add a Transform to SSA phase to the optimizing compiler."

13 files changed, 1039 insertions, 46 deletions

diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 12af0c4..2358391 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -78,6 +78,7 @@ COMPILER_GTEST_COMMON_SRC_FILES := \
 	compiler/optimizing/codegen_test.cc \
 	compiler/optimizing/dominator_test.cc \
 	compiler/optimizing/pretty_printer_test.cc \
+	compiler/optimizing/ssa_test.cc \
 	compiler/output_stream_test.cc \
 	compiler/utils/arena_allocator_test.cc \
 	compiler/utils/dedupe_set_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 6d656e6..e3201e7 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -78,6 +78,7 @@ LIBART_COMPILER_SRC_FILES := \
 	optimizing/code_generator_x86.cc \
 	optimizing/nodes.cc \
 	optimizing/optimizing_compiler.cc \
+	optimizing/ssa_builder.cc \
 	trampolines/trampoline_compiler.cc \
 	utils/arena_allocator.cc \
 	utils/arena_bit_vector.cc \
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index 7e63c69..babb1f5 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -47,7 +47,7 @@ void CodeGenerator::CompileBlock(HBasicBlock* block) {
   Bind(GetLabelOf(block));
   HGraphVisitor* location_builder = GetLocationBuilder();
   HGraphVisitor* instruction_visitor = GetInstructionVisitor();
-  for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
+  for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
     HInstruction* current = it.Current();
     current->Accept(location_builder);
     InitLocations(current);
@@ -57,7 +57,7 @@ void CodeGenerator::CompileBlock(HBasicBlock* block) {
 
 void CodeGenerator::InitLocations(HInstruction* instruction) {
   if (instruction->GetLocations() == nullptr) return;
-  for (int i = 0; i < instruction->InputCount(); i++) {
+  for (size_t i = 0; i < instruction->InputCount(); i++) {
     Location location = instruction->GetLocations()->InAt(i);
     if (location.IsValid()) {
       // Move the input to the desired location.
diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h
index 5c7cac1..54f9e70 100644
--- a/compiler/optimizing/code_generator.h
+++ b/compiler/optimizing/code_generator.h
@@ -211,7 +211,7 @@ class LocationSummary : public ArenaObject {
       : inputs(instruction->GetBlock()->GetGraph()->GetArena(), instruction->InputCount()),
         temps(instruction->GetBlock()->GetGraph()->GetArena(), 0) {
     inputs.SetSize(instruction->InputCount());
-    for (int i = 0; i < instruction->InputCount(); i++) {
+    for (size_t i = 0; i < instruction->InputCount(); i++) {
       inputs.Put(i, Location());
     }
   }
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 27691ac..6e528f9 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -447,7 +447,7 @@ void LocationsBuilderARM::VisitInvokeStatic(HInvokeStatic* invoke) {
   locations->AddTemp(ArmCoreLocation(R0));
 
   InvokeDexCallingConventionVisitor calling_convention_visitor;
-  for (int i = 0; i < invoke->InputCount(); i++) {
+  for (size_t i = 0; i < invoke->InputCount(); i++) {
     HInstruction* input = invoke->InputAt(i);
     locations->SetInAt(i, calling_convention_visitor.GetNextLocation(input->GetType()));
   }
@@ -694,5 +694,13 @@ void InstructionCodeGeneratorARM::VisitNot(HNot* instruction) {
          locations->InAt(0).AsArm().AsCoreRegister(), ShifterOperand(1));
 }
 
+void LocationsBuilderARM::VisitPhi(HPhi* instruction) {
+  LOG(FATAL) << "Unimplemented";
+}
+
+void InstructionCodeGeneratorARM::VisitPhi(HPhi* instruction) {
+  LOG(FATAL) << "Unimplemented";
+}
+
 }  // namespace arm
 }  // namespace art
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 1142631..dc10830 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -456,7 +456,7 @@ void LocationsBuilderX86::VisitInvokeStatic(HInvokeStatic* invoke) {
   locations->AddTemp(X86CpuLocation(EAX));
 
   InvokeDexCallingConventionVisitor calling_convention_visitor;
-  for (int i = 0; i < invoke->InputCount(); i++) {
+  for (size_t i = 0; i < invoke->InputCount(); i++) {
     HInstruction* input = invoke->InputAt(i);
     locations->SetInAt(i, calling_convention_visitor.GetNextLocation(input->GetType()));
   }
@@ -687,5 +687,13 @@ void InstructionCodeGeneratorX86::VisitNot(HNot* instruction) {
   __ xorl(locations->Out().AsX86().AsCpuRegister(), Immediate(1));
 }
 
+void LocationsBuilderX86::VisitPhi(HPhi* instruction) {
+  LOG(FATAL) << "Unimplemented";
+}
+
+void InstructionCodeGeneratorX86::VisitPhi(HPhi* instruction) {
+  LOG(FATAL) << "Unimplemented";
+}
+
 }  // namespace x86
 }  // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 498deba..3d6aeb7 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -15,6 +15,7 @@
  */
 
 #include "nodes.h"
+#include "ssa_builder.h"
 #include "utils/growable_array.h"
 
 namespace art {
@@ -34,7 +35,13 @@ void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const {
     if (!visited.IsBitSet(i)) {
       HBasicBlock* block = blocks_.Get(i);
       for (size_t j = 0; j < block->GetSuccessors()->Size(); j++) {
-        block->GetSuccessors()->Get(j)->RemovePredecessor(block);
+        block->GetSuccessors()->Get(j)->RemovePredecessor(block, false);
+      }
+      for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+        block->RemovePhi(it.Current()->AsPhi());
+      }
+      for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
+        block->RemoveInstruction(it.Current());
       }
     }
   }
@@ -120,11 +127,112 @@ void HGraph::VisitBlockForDominatorTree(HBasicBlock* block,
   }
 }
 
-void HBasicBlock::AddInstruction(HInstruction* instruction) {
+void HGraph::TransformToSSA() {
+  DCHECK(!dominator_order_.IsEmpty());
+  SimplifyCFG();
+  SsaBuilder ssa_builder(this);
+  ssa_builder.BuildSsa();
+}
+
+void HGraph::SimplifyCFG() {
+  for (size_t i = 0; i < dominator_order_.Size(); i++) {
+    HBasicBlock* current = dominator_order_.Get(i);
+    if (current->IsLoopHeader()) {
+      // Make sure the loop has only one pre header. This simplifies SSA building by having
+      // to just look at the pre header to know which locals are initialized at entry of the
+      // loop.
+      HLoopInformation* info = current->GetLoopInformation();
+      size_t number_of_incomings = current->GetPredecessors()->Size() - info->NumberOfBackEdges();
+      if (number_of_incomings != 1) {
+        HBasicBlock* pre_header = new (arena_) HBasicBlock(this);
+        AddBlock(pre_header);
+        pre_header->AddInstruction(new (arena_) HGoto());
+        pre_header->SetDominator(current->GetDominator());
+        current->SetDominator(pre_header);
+        dominator_order_.InsertAt(i, pre_header);
+        i++;
+
+        ArenaBitVector back_edges(arena_, GetBlocks()->Size(), false);
+        for (size_t pred = 0; pred < info->GetBackEdges()->Size(); pred++) {
+          back_edges.SetBit(info->GetBackEdges()->Get(pred)->GetBlockId());
+        }
+        for (size_t pred = 0; pred < current->GetPredecessors()->Size(); pred++) {
+          HBasicBlock* predecessor = current->GetPredecessors()->Get(pred);
+          if (!back_edges.IsBitSet(predecessor->GetBlockId())) {
+            current->RemovePredecessor(predecessor);
+            pred--;
+            predecessor->AddSuccessor(pre_header);
+          }
+        }
+        pre_header->AddSuccessor(current);
+      }
+      info->SetPreHeader(current->GetDominator());
+    }
+  }
+}
+
+void HLoopInformation::SetPreHeader(HBasicBlock* block) {
+  DCHECK_EQ(header_->GetDominator(), block);
+  pre_header_ = block;
+}
+
+static void Add(HInstructionList* instruction_list,
+                HBasicBlock* block,
+                HInstruction* instruction) {
   DCHECK(instruction->GetBlock() == nullptr);
   DCHECK_EQ(instruction->GetId(), -1);
-  instruction->SetBlock(this);
-  instruction->SetId(GetGraph()->GetNextInstructionId());
+  instruction->SetBlock(block);
+  instruction->SetId(block->GetGraph()->GetNextInstructionId());
+  instruction_list->AddInstruction(instruction);
+}
+
+void HBasicBlock::AddInstruction(HInstruction* instruction) {
+  Add(&instructions_, this, instruction);
+}
+
+void HBasicBlock::AddPhi(HPhi* phi) {
+  Add(&phis_, this, phi);
+}
+
+static void Remove(HInstructionList* instruction_list,
+                   HBasicBlock* block,
+                   HInstruction* instruction) {
+  DCHECK_EQ(block, instruction->GetBlock());
+  DCHECK(instruction->GetUses() == nullptr);
+  DCHECK(instruction->GetEnvUses() == nullptr);
+  instruction->SetBlock(nullptr);
+  instruction_list->RemoveInstruction(instruction);
+
+  for (size_t i = 0; i < instruction->InputCount(); i++) {
+    instruction->InputAt(i)->RemoveUser(instruction, i);
+  }
+}
+
+void HBasicBlock::RemoveInstruction(HInstruction* instruction) {
+  Remove(&instructions_, this, instruction);
+}
+
+void HBasicBlock::RemovePhi(HPhi* phi) {
+  Remove(&phis_, this, phi);
+}
+
+void HInstruction::RemoveUser(HInstruction* user, size_t input_index) {
+  HUseListNode<HInstruction>* previous = nullptr;
+  HUseListNode<HInstruction>* current = uses_;
+  while (current != nullptr) {
+    if (current->GetUser() == user && current->GetIndex() == input_index) {
+      if (previous == NULL) {
+        uses_ = current->GetTail();
+      } else {
+        previous->SetTail(current->GetTail());
+      }
+    }
+    previous = current;
+    current = current->GetTail();
+  }
+}
+
+void HInstructionList::AddInstruction(HInstruction* instruction) {
   if (first_instruction_ == nullptr) {
     DCHECK(last_instruction_ == nullptr);
     first_instruction_ = last_instruction_ = instruction;
@@ -133,9 +241,51 @@ void HBasicBlock::AddInstruction(HInstruction* instruction) {
     instruction->previous_ = last_instruction_;
     last_instruction_ = instruction;
   }
-  for (int i = 0; i < instruction->InputCount(); i++) {
-    instruction->InputAt(i)->AddUse(instruction);
+  for (size_t i = 0; i < instruction->InputCount(); i++) {
+    instruction->InputAt(i)->AddUseAt(instruction, i);
+  }
+}
+
+void HInstructionList::RemoveInstruction(HInstruction* instruction) {
+  if (instruction->previous_ != nullptr) {
+    instruction->previous_->next_ = instruction->next_;
+  }
+  if (instruction->next_ != nullptr) {
+    instruction->next_->previous_ = instruction->previous_;
   }
+  if (instruction == first_instruction_) {
+    first_instruction_ = instruction->next_;
+  }
+  if (instruction == last_instruction_) {
+    last_instruction_ = instruction->previous_;
+  }
+}
+
+void HInstruction::ReplaceWith(HInstruction* other) {
+  for (HUseIterator<HInstruction> it(GetUses()); !it.Done(); it.Advance()) {
+    HUseListNode<HInstruction>* current = it.Current();
+    HInstruction* user = current->GetUser();
+    size_t input_index = current->GetIndex();
+    user->SetRawInputAt(input_index, other);
+    other->AddUseAt(user, input_index);
+  }
+
+  for (HUseIterator<HEnvironment> it(GetEnvUses()); !it.Done(); it.Advance()) {
+    HUseListNode<HEnvironment>* current = it.Current();
+    HEnvironment* user = current->GetUser();
+    size_t input_index = current->GetIndex();
+    user->SetRawEnvAt(input_index, other);
+    other->AddEnvUseAt(user, input_index);
+  }
+
+  uses_ = nullptr;
+  env_uses_ = nullptr;
+}
+
+void HPhi::AddInput(HInstruction* input) {
+  DCHECK(input->GetBlock() != nullptr);
+  inputs_.Add(input);
+  input->AddUseAt(this, inputs_.Size() - 1);
 }
 
 #define DEFINE_ACCEPT(name)                                                    \
@@ -155,7 +305,10 @@ void HGraphVisitor::VisitInsertionOrder() {
 }
 
 void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) {
-  for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
+  for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+    it.Current()->Accept(this);
+  }
+  for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
     it.Current()->Accept(this);
   }
 }
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 3da9ed9..581c1d5 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -24,9 +24,11 @@
 namespace art {
 
 class HBasicBlock;
+class HEnvironment;
 class HInstruction;
 class HIntConstant;
 class HGraphVisitor;
+class HPhi;
 class LocationSummary;
 
 static const int kDefaultNumberOfBlocks = 8;
@@ -34,6 +36,23 @@ static const int kDefaultNumberOfSuccessors = 2;
 static const int kDefaultNumberOfPredecessors = 2;
 static const int kDefaultNumberOfBackEdges = 1;
 
+class HInstructionList {
+ public:
+  HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {}
+
+  void AddInstruction(HInstruction* instruction);
+  void RemoveInstruction(HInstruction* instruction);
+
+ private:
+  HInstruction* first_instruction_;
+  HInstruction* last_instruction_;
+
+  friend class HBasicBlock;
+  friend class HInstructionIterator;
+
+  DISALLOW_COPY_AND_ASSIGN(HInstructionList);
+};
+
 // Control-flow graph of a method. Contains a list of basic blocks.
 class HGraph : public ArenaObject {
  public:
@@ -56,7 +75,10 @@ class HGraph : public ArenaObject {
   void SetExitBlock(HBasicBlock* block) { exit_block_ = block; }
 
   void AddBlock(HBasicBlock* block);
+
   void BuildDominatorTree();
+  void TransformToSSA();
+  void SimplifyCFG();
 
   int GetNextInstructionId() {
     return current_instruction_id_++;
@@ -86,6 +108,9 @@ class HGraph : public ArenaObject {
     return number_of_in_vregs_;
   }
 
+  GrowableArray<HBasicBlock*>* GetDominatorOrder() {
+    return &dominator_order_;
+  }
 
  private:
   HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
@@ -138,7 +163,18 @@ class HLoopInformation : public ArenaObject {
     return back_edges_.Size();
   }
 
+  void SetPreHeader(HBasicBlock* block);
+
+  HBasicBlock* GetPreHeader() const {
+    return pre_header_;
+  }
+
+  const GrowableArray<HBasicBlock*>* GetBackEdges() const {
+    return &back_edges_;
+  }
+
  private:
+  HBasicBlock* pre_header_;
   HBasicBlock* header_;
   GrowableArray<HBasicBlock*> back_edges_;
 
@@ -154,8 +190,6 @@ class HBasicBlock : public ArenaObject {
       : graph_(graph),
         predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors),
         successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
-        first_instruction_(nullptr),
-        last_instruction_(nullptr),
         loop_information_(nullptr),
         dominator_(nullptr),
         block_id_(-1) { }
@@ -189,26 +223,42 @@ class HBasicBlock : public ArenaObject {
         : loop_information_->NumberOfBackEdges();
   }
 
-  HInstruction* GetFirstInstruction() const { return first_instruction_; }
-  HInstruction* GetLastInstruction() const { return last_instruction_; }
+  HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; }
+  HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; }
+  HInstructionList const* GetInstructions() const { return &instructions_; }
+  HInstructionList const* GetPhis() const { return &phis_; }
 
   void AddSuccessor(HBasicBlock* block) {
     successors_.Add(block);
     block->predecessors_.Add(this);
   }
 
-  void RemovePredecessor(HBasicBlock* block) {
+  void RemovePredecessor(HBasicBlock* block, bool remove_in_successor = true) {
     predecessors_.Delete(block);
+    if (remove_in_successor) {
+      block->successors_.Delete(this);
+    }
   }
 
   void AddInstruction(HInstruction* instruction);
+  void RemoveInstruction(HInstruction* instruction);
+  void AddPhi(HPhi* phi);
+  void RemovePhi(HPhi* phi);
+
+  bool IsLoopHeader() const {
+    return loop_information_ != nullptr;
+  }
+
+  HLoopInformation* GetLoopInformation() const {
+    return loop_information_;
+  }
 
  private:
   HGraph* const graph_;
   GrowableArray<HBasicBlock*> predecessors_;
   GrowableArray<HBasicBlock*> successors_;
-  HInstruction* first_instruction_;
-  HInstruction* last_instruction_;
+  HInstructionList instructions_;
+  HInstructionList phis_;
   HLoopInformation* loop_information_;
   HBasicBlock* dominator_;
   int block_id_;
@@ -230,6 +280,7 @@ class HBasicBlock : public ArenaObject {
   M(NewInstance)                                           \
   M(Not)                                                   \
   M(ParameterValue)                                        \
+  M(Phi)                                                   \
   M(Return)                                                \
   M(ReturnVoid)                                            \
   M(StoreLocal)                                            \
@@ -244,17 +295,22 @@ FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
   virtual const char* DebugName() const { return #type; }  \
   virtual H##type* As##type() { return this; }             \
 
+template <typename T>
 class HUseListNode : public ArenaObject {
  public:
-  HUseListNode(HInstruction* instruction, HUseListNode* tail)
-      : instruction_(instruction), tail_(tail) { }
+  HUseListNode(T* user, size_t index, HUseListNode* tail)
+      : user_(user), index_(index), tail_(tail) { }
 
   HUseListNode* GetTail() const { return tail_; }
-  HInstruction* GetInstruction() const { return instruction_; }
+  T* GetUser() const { return user_; }
+  size_t GetIndex() const { return index_; }
+
+  void SetTail(HUseListNode<T>* node) { tail_ = node; }
 
  private:
-  HInstruction* const instruction_;
-  HUseListNode* const tail_;
+  T* const user_;
+  const size_t index_;
+  HUseListNode<T>* tail_;
 
   DISALLOW_COPY_AND_ASSIGN(HUseListNode);
 };
@@ -267,6 +323,8 @@ class HInstruction : public ArenaObject {
         block_(nullptr),
         id_(-1),
         uses_(nullptr),
+        env_uses_(nullptr),
+        environment_(nullptr),
         locations_(nullptr) { }
 
   virtual ~HInstruction() { }
@@ -277,28 +335,43 @@ class HInstruction : public ArenaObject {
   HBasicBlock* GetBlock() const { return block_; }
   void SetBlock(HBasicBlock* block) { block_ = block; }
 
-  virtual intptr_t InputCount() const  = 0;
-  virtual HInstruction* InputAt(intptr_t i) const = 0;
+  virtual size_t InputCount() const  = 0;
+  virtual HInstruction* InputAt(size_t i) const = 0;
 
   virtual void Accept(HGraphVisitor* visitor) = 0;
   virtual const char* DebugName() const = 0;
 
   virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; }
+  virtual void SetRawInputAt(size_t index, HInstruction* input) = 0;
+
+  virtual bool NeedsEnvironment() const { return false; }
 
-  void AddUse(HInstruction* user) {
-    uses_ = new (block_->GetGraph()->GetArena()) HUseListNode(user, uses_);
+  void AddUseAt(HInstruction* user, size_t index) {
+    uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_);
   }
 
-  HUseListNode* GetUses() const { return uses_; }
+  void AddEnvUseAt(HEnvironment* user, size_t index) {
+    env_uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HEnvironment>(
+        user, index, env_uses_);
+  }
+
+  void RemoveUser(HInstruction* user, size_t index);
+
+  HUseListNode<HInstruction>* GetUses() const { return uses_; }
+  HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; }
 
   bool HasUses() const { return uses_ != nullptr; }
 
   int GetId() const { return id_; }
   void SetId(int id) { id_ = id; }
 
+  void SetEnvironment(HEnvironment* environment) { environment_ = environment; }
+
   LocationSummary* GetLocations() const { return locations_; }
   void SetLocations(LocationSummary* locations) { locations_ = locations; }
 
+  void ReplaceWith(HInstruction* instruction);
+
 #define INSTRUCTION_TYPE_CHECK(type)                                           \
   virtual H##type* As##type() { return nullptr; }
 
@@ -315,19 +388,27 @@ class HInstruction : public ArenaObject {
   // has not beed added to the graph.
   int id_;
 
-  HUseListNode* uses_;
+  // List of instructions that have this instruction as input.
+  HUseListNode<HInstruction>* uses_;
+
+  // List of environments that contain this instruction.
+  HUseListNode<HEnvironment>* env_uses_;
+
+  HEnvironment* environment_;
 
   // Set by the code generator.
   LocationSummary* locations_;
 
   friend class HBasicBlock;
+  friend class HInstructionList;
 
   DISALLOW_COPY_AND_ASSIGN(HInstruction);
 };
 
+template<typename T>
 class HUseIterator : public ValueObject {
  public:
-  explicit HUseIterator(HInstruction* instruction) : current_(instruction->GetUses()) { }
+  explicit HUseIterator(HUseListNode<T>* uses) : current_(uses) {}
 
   bool Done() const { return current_ == nullptr; }
 
@@ -336,17 +417,51 @@ class HUseIterator : public ValueObject {
     current_ = current_->GetTail();
   }
 
-  HInstruction* Current() const {
+  HUseListNode<T>* Current() const {
     DCHECK(!Done());
-    return current_->GetInstruction();
+    return current_;
   }
 
  private:
-  HUseListNode* current_;
+  HUseListNode<T>* current_;
 
   friend class HValue;
 };
 
+// A HEnvironment object contains the values of virtual registers at a given location.
+class HEnvironment : public ArenaObject {
+ public:
+  HEnvironment(ArenaAllocator* arena, size_t number_of_vregs) : vregs_(arena, number_of_vregs) {
+    vregs_.SetSize(number_of_vregs);
+    for (size_t i = 0; i < number_of_vregs; i++) {
+      vregs_.Put(i, nullptr);
+    }
+  }
+
+  void Populate(const GrowableArray<HInstruction*>& env) {
+    for (size_t i = 0; i < env.Size(); i++) {
+      HInstruction* instruction = env.Get(i);
+      vregs_.Put(i, instruction);
+      if (instruction != nullptr) {
+        instruction->AddEnvUseAt(this, i);
+      }
+    }
+  }
+
+  void SetRawEnvAt(size_t index, HInstruction* instruction) {
+    vregs_.Put(index, instruction);
+  }
+
+  GrowableArray<HInstruction*>* GetVRegs() {
+    return &vregs_;
+  }
+
+ private:
+  GrowableArray<HInstruction*> vregs_;
+
+  DISALLOW_COPY_AND_ASSIGN(HEnvironment);
+};
+
 class HInputIterator : public ValueObject {
  public:
   explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) { }
@@ -357,15 +472,15 @@ class HInputIterator : public ValueObject {
 
  private:
   HInstruction* instruction_;
-  int index_;
+  size_t index_;
 
   DISALLOW_COPY_AND_ASSIGN(HInputIterator);
 };
 
 class HInstructionIterator : public ValueObject {
  public:
-  explicit HInstructionIterator(HBasicBlock* block)
-      : instruction_(block->GetFirstInstruction()) {
+  explicit HInstructionIterator(const HInstructionList& instructions)
+      : instruction_(instructions.first_instruction_) {
     next_ = Done() ? nullptr : instruction_->GetNext();
   }
 
@@ -434,16 +549,18 @@ class HTemplateInstruction: public HInstruction {
   HTemplateInstruction<N>() : inputs_() { }
   virtual ~HTemplateInstruction() { }
 
-  virtual intptr_t InputCount() const { return N; }
-  virtual HInstruction* InputAt(intptr_t i) const { return inputs_[i]; }
+  virtual size_t InputCount() const { return N; }
+  virtual HInstruction* InputAt(size_t i) const { return inputs_[i]; }
 
  protected:
-  void SetRawInputAt(intptr_t i, HInstruction* instruction) {
+  virtual void SetRawInputAt(size_t i, HInstruction* instruction) {
     inputs_[i] = instruction;
   }
 
  private:
   EmbeddedArray<HInstruction*, N> inputs_;
+
+  friend class SsaBuilder;
 };
 
 // Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow
@@ -658,11 +775,19 @@ class HInvoke : public HInstruction {
     inputs_.SetSize(number_of_arguments);
   }
 
-  virtual intptr_t InputCount() const { return inputs_.Size(); }
-  virtual HInstruction* InputAt(intptr_t i) const { return inputs_.Get(i); }
+  virtual size_t InputCount() const { return inputs_.Size(); }
+  virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); }
+
+  // Runtime needs to walk the stack, so Dex -> Dex calls need to
+  // know their environment.
+  virtual bool NeedsEnvironment() const { return true; }
 
   void SetArgumentAt(size_t index, HInstruction* argument) {
-    inputs_.Put(index, argument);
+    SetRawInputAt(index, argument);
+  }
+
+  virtual void SetRawInputAt(size_t index, HInstruction* input) {
+    inputs_.Put(index, input);
   }
 
   virtual Primitive::Type GetType() const { return return_type_; }
@@ -707,6 +832,9 @@ class HNewInstance : public HTemplateInstruction<0> {
 
   virtual Primitive::Type GetType() const { return Primitive::kPrimNot; }
 
+  // Calls runtime so needs an environment.
+  virtual bool NeedsEnvironment() const { return true; }
+
   DECLARE_INSTRUCTION(NewInstance)
 
  private:
@@ -779,6 +907,39 @@ class HNot : public HTemplateInstruction<1> {
   DISALLOW_COPY_AND_ASSIGN(HNot);
 };
 
+class HPhi : public HInstruction {
+ public:
+  HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type)
+      : inputs_(arena, number_of_inputs),
+        reg_number_(reg_number),
+        type_(type) {
+    inputs_.SetSize(number_of_inputs);
+  }
+
+  virtual size_t InputCount() const { return inputs_.Size(); }
+  virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); }
+
+  virtual void SetRawInputAt(size_t index, HInstruction* input) {
+    inputs_.Put(index, input);
+  }
+
+  void AddInput(HInstruction* input);
+
+  virtual Primitive::Type GetType() const { return type_; }
+
+  uint32_t GetRegNumber() const { return reg_number_; }
+
+  DECLARE_INSTRUCTION(Phi)
+
+ protected:
+  GrowableArray<HInstruction*> inputs_;
+  const uint32_t reg_number_;
+  const Primitive::Type type_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HPhi);
+};
+
 class HGraphVisitor : public ValueObject {
  public:
   explicit HGraphVisitor(HGraph* graph) : graph_(graph) { }
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index d19c40c..9438890 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -100,6 +100,10 @@ CompiledMethod* OptimizingCompiler::TryCompile(CompilerDriver& driver,
   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();
+
   return new CompiledMethod(driver,
                             instruction_set,
                             allocator.GetMemory(),
diff --git a/compiler/optimizing/pretty_printer.h b/compiler/optimizing/pretty_printer.h
index 606c915..c82d0cc 100644
--- a/compiler/optimizing/pretty_printer.h
+++ b/compiler/optimizing/pretty_printer.h
@@ -25,11 +25,19 @@ class HPrettyPrinter : public HGraphVisitor {
  public:
   explicit HPrettyPrinter(HGraph* graph) : HGraphVisitor(graph) { }
 
-  virtual void VisitInstruction(HInstruction* instruction) {
+  void PrintPreInstruction(HInstruction* instruction) {
     PrintString("  ");
     PrintInt(instruction->GetId());
     PrintString(": ");
+  }
+
+  virtual void VisitInstruction(HInstruction* instruction) {
+    PrintPreInstruction(instruction);
     PrintString(instruction->DebugName());
+    PrintPostInstruction(instruction);
+  }
+
+  void PrintPostInstruction(HInstruction* instruction) {
     if (instruction->InputCount() != 0) {
       PrintString("(");
       bool first = true;
@@ -46,13 +54,13 @@ class HPrettyPrinter : public HGraphVisitor {
     if (instruction->HasUses()) {
       PrintString(" [");
       bool first = true;
-      for (HUseIterator it(instruction); !it.Done(); it.Advance()) {
+      for (HUseIterator<HInstruction> it(instruction->GetUses()); !it.Done(); it.Advance()) {
         if (first) {
           first = false;
         } else {
           PrintString(", ");
         }
-        PrintInt(it.Current()->GetId());
+        PrintInt(it.Current()->GetUser()->GetId());
       }
       PrintString("]");
     }
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
new file mode 100644
index 0000000..bfb4f38
--- /dev/null
+++ b/compiler/optimizing/ssa_builder.cc
@@ -0,0 +1,134 @@
+/*
+ * 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.
+ */
+
+#include "ssa_builder.h"
+#include "nodes.h"
+
+namespace art {
+
+void SsaBuilder::BuildSsa() {
+  // 1) Visit in dominator order. We need to have all predecessors of a block visited
+  // (with the exception of loops) in order to create the right environment for that
+  // block. For loops, we create phis whose inputs will be set in 2).
+  for (size_t i = 0; i < GetGraph()->GetDominatorOrder()->Size(); i++) {
+    VisitBasicBlock(GetGraph()->GetDominatorOrder()->Get(i));
+  }
+
+  // 2) Set inputs of loop phis.
+  for (size_t i = 0; i < loop_headers_.Size(); i++) {
+    HBasicBlock* block = loop_headers_.Get(i);
+    for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+      HPhi* phi = it.Current()->AsPhi();
+      for (size_t pred = 0; pred < block->GetPredecessors()->Size(); pred++) {
+        phi->AddInput(ValueOfLocal(block->GetPredecessors()->Get(pred), phi->GetRegNumber()));
+      }
+    }
+  }
+
+  // 3) Clear locals.
+  // TODO: Move this to a dead code eliminator phase.
+  for (HInstructionIterator it(*GetGraph()->GetEntryBlock()->GetInstructions());
+       !it.Done();
+       it.Advance()) {
+    HInstruction* current = it.Current();
+    if (current->AsLocal() != nullptr) {
+      current->GetBlock()->RemoveInstruction(current);
+    }
+  }
+}
+
+HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) {
+  return GetLocalsFor(block)->Get(local);
+}
+
+void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
+  current_locals_ = GetLocalsFor(block);
+
+  if (block->IsLoopHeader()) {
+    // If the block is a loop header, we know we only have visited the pre header
+    // because we are visiting in dominator order. We create phis for all initialized
+    // locals from the pre header. Their inputs will be populated at the end of
+    // the analysis.
+    for (size_t local = 0; local < current_locals_->Size(); local++) {
+      HInstruction* incoming = ValueOfLocal(block->GetLoopInformation()->GetPreHeader(), local);
+      if (incoming != nullptr) {
+        // TODO: Compute union type.
+        HPhi* phi = new (GetGraph()->GetArena()) HPhi(
+            GetGraph()->GetArena(), local, 0, Primitive::kPrimVoid);
+        block->AddPhi(phi);
+        current_locals_->Put(local, phi);
+      }
+    }
+    // Save the loop header so that the last phase of the analysis knows which
+    // blocks need to be updated.
+    loop_headers_.Add(block);
+  } else if (block->GetPredecessors()->Size() > 0) {
+    // All predecessors have already been visited because we are visiting in dominator order.
+    // We merge the values of all locals, creating phis if those values differ.
+    for (size_t local = 0; local < current_locals_->Size(); local++) {
+      bool is_different = false;
+      HInstruction* value = ValueOfLocal(block->GetPredecessors()->Get(0), local);
+      for (size_t i = 1; i < block->GetPredecessors()->Size(); i++) {
+        if (ValueOfLocal(block->GetPredecessors()->Get(i), local) != value) {
+          is_different = true;
+          break;
+        }
+      }
+      if (is_different) {
+        // TODO: Compute union type.
+        HPhi* phi = new (GetGraph()->GetArena()) HPhi(
+            GetGraph()->GetArena(), local, block->GetPredecessors()->Size(), Primitive::kPrimVoid);
+        for (size_t i = 0; i < block->GetPredecessors()->Size(); i++) {
+          phi->SetRawInputAt(i, ValueOfLocal(block->GetPredecessors()->Get(i), local));
+        }
+        block->AddPhi(phi);
+        value = phi;
+      }
+      current_locals_->Put(local, value);
+    }
+  }
+
+  // Visit all instructions. The instructions of interest are:
+  // - HLoadLocal: replace them with the current value of the local.
+  // - HStoreLocal: update current value of the local and remove the instruction.
+  // - Instructions that require an environment: populate their environment
+  //   with the current values of the locals.
+  for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
+    it.Current()->Accept(this);
+  }
+}
+
+void SsaBuilder::VisitLoadLocal(HLoadLocal* load) {
+  load->ReplaceWith(current_locals_->Get(load->GetLocal()->GetRegNumber()));
+  load->GetBlock()->RemoveInstruction(load);
+}
+
+void SsaBuilder::VisitStoreLocal(HStoreLocal* store) {
+  current_locals_->Put(store->GetLocal()->GetRegNumber(), store->InputAt(1));
+  store->GetBlock()->RemoveInstruction(store);
+}
+
+void SsaBuilder::VisitInstruction(HInstruction* instruction) {
+  if (!instruction->NeedsEnvironment()) {
+    return;
+  }
+  HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment(
+      GetGraph()->GetArena(), current_locals_->Size());
+  environment->Populate(*current_locals_);
+  instruction->SetEnvironment(environment);
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
new file mode 100644
index 0000000..b6c6c0b
--- /dev/null
+++ b/compiler/optimizing/ssa_builder.h
@@ -0,0 +1,71 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_
+#define ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_
+
+#include "nodes.h"
+
+namespace art {
+
+static constexpr int kDefaultNumberOfLoops = 2;
+
+class SsaBuilder : public HGraphVisitor {
+ public:
+  explicit SsaBuilder(HGraph* graph)
+      : HGraphVisitor(graph),
+        current_locals_(nullptr),
+        loop_headers_(graph->GetArena(), kDefaultNumberOfLoops),
+        locals_for_(graph->GetArena(), graph->GetBlocks()->Size()) {
+    locals_for_.SetSize(graph->GetBlocks()->Size());
+  }
+
+  void BuildSsa();
+
+  GrowableArray<HInstruction*>* GetLocalsFor(HBasicBlock* block) {
+    HEnvironment* env = locals_for_.Get(block->GetBlockId());
+    if (env == nullptr) {
+      env = new (GetGraph()->GetArena()) HEnvironment(
+          GetGraph()->GetArena(), GetGraph()->GetNumberOfVRegs());
+      locals_for_.Put(block->GetBlockId(), env);
+    }
+    return env->GetVRegs();
+  }
+
+  HInstruction* ValueOfLocal(HBasicBlock* block, size_t local);
+
+  void VisitBasicBlock(HBasicBlock* block);
+  void VisitLoadLocal(HLoadLocal* load);
+  void VisitStoreLocal(HStoreLocal* store);
+  void VisitInstruction(HInstruction* instruction);
+
+ private:
+  // Locals for the current block being visited.
+  GrowableArray<HInstruction*>* current_locals_;
+
+  // Keep track of loop headers found. The last phase of the analysis iterates
+  // over these blocks to set the inputs of their phis.
+  GrowableArray<HBasicBlock*> loop_headers_;
+
+  // HEnvironment for each block.
+  GrowableArray<HEnvironment*> locals_for_;
+
+  DISALLOW_COPY_AND_ASSIGN(SsaBuilder);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_SSA_BUILDER_H_
diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
new file mode 100644
index 0000000..7c3633b
--- /dev/null
+++ b/compiler/optimizing/ssa_test.cc
@@ -0,0 +1,444 @@
+/*
+ * 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.
+ */
+
+#include "base/stringprintf.h"
+#include "builder.h"
+#include "dex_file.h"
+#include "dex_instruction.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "pretty_printer.h"
+#include "ssa_builder.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+class StringPrettyPrinter : public HPrettyPrinter {
+ public:
+  explicit StringPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {}
+
+  virtual void PrintInt(int value) {
+    str_ += StringPrintf("%d", value);
+  }
+
+  virtual void PrintString(const char* value) {
+    str_ += value;
+  }
+
+  virtual void PrintNewLine() {
+    str_ += '\n';
+  }
+
+  void Clear() { str_.clear(); }
+
+  std::string str() const { return str_; }
+
+  virtual void VisitIntConstant(HIntConstant* constant) {
+    PrintPreInstruction(constant);
+    str_ += constant->DebugName();
+    str_ += " ";
+    PrintInt(constant->GetValue());
+    PrintPostInstruction(constant);
+  }
+
+ private:
+  std::string str_;
+
+  DISALLOW_COPY_AND_ASSIGN(StringPrettyPrinter);
+};
+
+static void ReNumberInstructions(HGraph* graph) {
+  int id = 0;
+  for (size_t i = 0; i < graph->GetBlocks()->Size(); i++) {
+    HBasicBlock* block = graph->GetBlocks()->Get(i);
+    for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+      it.Current()->SetId(id++);
+    }
+    for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
+      it.Current()->SetId(id++);
+    }
+  }
+}
+
+static void TestCode(const uint16_t* data, const char* expected) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraphBuilder builder(&allocator);
+  const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
+  HGraph* graph = builder.BuildGraph(*item);
+  ASSERT_NE(graph, nullptr);
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+  ReNumberInstructions(graph);
+
+  StringPrettyPrinter printer(graph);
+  printer.VisitInsertionOrder();
+
+  ASSERT_STREQ(expected, printer.str().c_str());
+}
+
+TEST(SsaTest, CFG1) {
+  // Test that we get rid of loads and stores.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [2, 2]\n"
+    "  1: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "  2: Equal(0, 0) [3]\n"
+    "  3: If(2)\n"
+    "BasicBlock 2, pred: 1, succ: 3\n"
+    "  4: Goto\n"
+    "BasicBlock 3, pred: 1, 2, succ: 4\n"
+    "  5: ReturnVoid\n"
+    "BasicBlock 4, pred: 3\n"
+    "  6: Exit\n";
+
+  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, expected);
+}
+
+TEST(SsaTest, CFG2) {
+  // Test that we create a phi for the join block of an if control flow instruction
+  // when there is only code in the else branch.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [6, 3, 3]\n"
+    "  1: IntConstant 4 [6]\n"
+    "  2: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "  3: Equal(0, 0) [4]\n"
+    "  4: If(3)\n"
+    "BasicBlock 2, pred: 1, succ: 3\n"
+    "  5: Goto\n"
+    "BasicBlock 3, pred: 1, 2, succ: 4\n"
+    "  6: Phi(0, 1) [7]\n"
+    "  7: Return(6)\n"
+    "BasicBlock 4, pred: 3\n"
+    "  8: Exit\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(SsaTest, CFG3) {
+  // Test that we create a phi for the join block of an if control flow instruction
+  // when there both branches update a local.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [4, 4]\n"
+    "  1: IntConstant 4 [8]\n"
+    "  2: IntConstant 5 [8]\n"
+    "  3: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "  4: Equal(0, 0) [5]\n"
+    "  5: If(4)\n"
+    "BasicBlock 2, pred: 1, succ: 4\n"
+    "  6: Goto\n"
+    "BasicBlock 3, pred: 1, succ: 4\n"
+    "  7: Goto\n"
+    "BasicBlock 4, pred: 2, 3, succ: 5\n"
+    "  8: Phi(1, 2) [9]\n"
+    "  9: Return(8)\n"
+    "BasicBlock 5, pred: 4\n"
+    "  10: Exit\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0x200,
+    Instruction::CONST_4 | 5 << 12 | 0,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop1) {
+  // Test that we create a phi for an initialized local at entry of a loop.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [6, 4, 2, 2]\n"
+    "  1: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "  2: Equal(0, 0) [3]\n"
+    "  3: If(2)\n"
+    "BasicBlock 2, pred: 1, 3, succ: 3\n"
+    "  4: Phi(0, 6) [6]\n"
+    "  5: Goto\n"
+    "BasicBlock 3, pred: 1, 2, succ: 2\n"
+    "  6: Phi(0, 4) [4]\n"
+    "  7: Goto\n"
+    "BasicBlock 4\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0x100,
+    Instruction::GOTO | 0xFF00);
+
+  TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop2) {
+  // Simple loop with one preheader and one back edge.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [4]\n"
+    "  1: IntConstant 4 [4]\n"
+    "  2: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  3: Goto\n"
+    "BasicBlock 2, pred: 1, 3, succ: 4, 3\n"
+    "  4: Phi(0, 1) [5, 5]\n"
+    "  5: Equal(4, 4) [6]\n"
+    "  6: If(5)\n"
+    "BasicBlock 3, pred: 2, succ: 2\n"
+    "  7: Goto\n"
+    "BasicBlock 4, pred: 2, succ: 5\n"
+    "  8: ReturnVoid\n"
+    "BasicBlock 5, pred: 4\n"
+    "  9: Exit\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0xFD00,
+    Instruction::RETURN_VOID);
+
+  TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop3) {
+  // Test that a local not yet defined at the entry of a loop is handled properly.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [5]\n"
+    "  1: IntConstant 4 [5]\n"
+    "  2: IntConstant 5 [9]\n"
+    "  3: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  4: Goto\n"
+    "BasicBlock 2, pred: 1, 3, succ: 4, 3\n"
+    "  5: Phi(0, 1) [6, 6]\n"
+    "  6: Equal(5, 5) [7]\n"
+    "  7: If(6)\n"
+    "BasicBlock 3, pred: 2, succ: 2\n"
+    "  8: Goto\n"
+    "BasicBlock 4, pred: 2, succ: 5\n"
+    "  9: Return(2)\n"
+    "BasicBlock 5, pred: 4\n"
+    "  10: Exit\n";
+
+  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0xFD00,
+    Instruction::CONST_4 | 5 << 12 | 1 << 8,
+    Instruction::RETURN | 1 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop4) {
+  // Make sure we support a preheader of a loop not being the first predecessor
+  // in the predecessor list of the header.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [4]\n"
+    "  1: IntConstant 4 [4]\n"
+    "  2: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 4\n"
+    "  3: Goto\n"
+    "BasicBlock 2, pred: 3, 4, succ: 5, 3\n"
+    "  4: Phi(1, 0) [9, 5, 5]\n"
+    "  5: Equal(4, 4) [6]\n"
+    "  6: If(5)\n"
+    "BasicBlock 3, pred: 2, succ: 2\n"
+    "  7: Goto\n"
+    "BasicBlock 4, pred: 1, succ: 2\n"
+    "  8: Goto\n"
+    "BasicBlock 5, pred: 2, succ: 6\n"
+    "  9: Return(4)\n"
+    "BasicBlock 6, pred: 5\n"
+    "  10: Exit\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::GOTO | 0x500,
+    Instruction::IF_EQ, 5,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0xFD00,
+    Instruction::GOTO | 0xFC00,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop5) {
+  // Make sure we create a preheader of a loop when a header originally has two
+  // incoming blocks and one back edge.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [4, 4]\n"
+    "  1: IntConstant 4 [14]\n"
+    "  2: IntConstant 5 [14]\n"
+    "  3: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 3, 2\n"
+    "  4: Equal(0, 0) [5]\n"
+    "  5: If(4)\n"
+    "BasicBlock 2, pred: 1, succ: 8\n"
+    "  6: Goto\n"
+    "BasicBlock 3, pred: 1, succ: 8\n"
+    "  7: Goto\n"
+    "BasicBlock 4, pred: 5, 8, succ: 6, 5\n"
+    "  8: Phi(8, 14) [8, 12, 9, 9]\n"
+    "  9: Equal(8, 8) [10]\n"
+    "  10: If(9)\n"
+    "BasicBlock 5, pred: 4, succ: 4\n"
+    "  11: Goto\n"
+    "BasicBlock 6, pred: 4, succ: 7\n"
+    "  12: Return(8)\n"
+    "BasicBlock 7, pred: 6\n"
+    "  13: Exit\n"
+    "BasicBlock 8, pred: 2, 3, succ: 4\n"
+    "  14: Phi(1, 2) [8]\n"
+    "  15: Goto\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::GOTO | 0x200,
+    Instruction::CONST_4 | 5 << 12 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0xFE00,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop6) {
+  // Test a loop with one preheader and two back edges (e.g. continue).
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [5]\n"
+    "  1: IntConstant 4 [5, 8, 8]\n"
+    "  2: IntConstant 5 [5]\n"
+    "  3: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  4: Goto\n"
+    "BasicBlock 2, pred: 1, 4, 5, succ: 6, 3\n"
+    "  5: Phi(0, 2, 1) [12, 6, 6]\n"
+    "  6: Equal(5, 5) [7]\n"
+    "  7: If(6)\n"
+    "BasicBlock 3, pred: 2, succ: 5, 4\n"
+    "  8: Equal(1, 1) [9]\n"
+    "  9: If(8)\n"
+    "BasicBlock 4, pred: 3, succ: 2\n"
+    "  10: Goto\n"
+    "BasicBlock 5, pred: 3, succ: 2\n"
+    "  11: Goto\n"
+    "BasicBlock 6, pred: 2, succ: 7\n"
+    "  12: Return(5)\n"
+    "BasicBlock 7, pred: 6\n"
+    "  13: Exit\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 8,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 5 << 12 | 0,
+    Instruction::GOTO | 0xFA00,
+    Instruction::GOTO | 0xF900,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(SsaTest, Loop7) {
+  // Test a loop with one preheader, one back edge, and two exit edges (e.g. break).
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [5]\n"
+    "  1: IntConstant 4 [5, 8, 8]\n"
+    "  2: IntConstant 5 [12]\n"
+    "  3: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  4: Goto\n"
+    "BasicBlock 2, pred: 1, 5, succ: 6, 3\n"
+    "  5: Phi(0, 1) [12, 6, 6]\n"
+    "  6: Equal(5, 5) [7]\n"
+    "  7: If(6)\n"
+    "BasicBlock 3, pred: 2, succ: 5, 4\n"
+    "  8: Equal(1, 1) [9]\n"
+    "  9: If(8)\n"
+    "BasicBlock 4, pred: 3, succ: 6\n"
+    "  10: Goto\n"
+    "BasicBlock 5, pred: 3, succ: 2\n"
+    "  11: Goto\n"
+    "BasicBlock 6, pred: 2, 4, succ: 7\n"
+    "  12: Phi(5, 2) [13]\n"
+    "  13: Return(12)\n"
+    "BasicBlock 7, pred: 6\n"
+    "  14: Exit\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 8,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::IF_EQ, 4,
+    Instruction::CONST_4 | 5 << 12 | 0,
+    Instruction::GOTO | 0x0200,
+    Instruction::GOTO | 0xF900,
+    Instruction::RETURN | 0 << 8);
+
+  TestCode(data, expected);
+}
+
+TEST(SsaTest, DeadLocal) {
+  // Test that we correctly handle a local not being used.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0\n"
+    "  1: Goto\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  2: ReturnVoid\n"
+    "BasicBlock 2, pred: 1\n"
+    "  3: Exit\n";
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::RETURN_VOID);
+
+  TestCode(data, expected);
+}
+
+}  // namespace art