Fix some bugs in graph construction/simplification methods.

Also fix a brano during SSA construction. The code should
not have been commented out. Added a test to cover what the code
intends.

Change-Id: Ia00ae79dcf75eb0d412f07649d73e7f94dbfb6f0

8 files changed, 420 insertions, 35 deletions

diff --git a/compiler/optimizing/graph_test.cc b/compiler/optimizing/graph_test.cc
new file mode 100644
index 0000000..371478c
--- /dev/null
+++ b/compiler/optimizing/graph_test.cc
@@ -0,0 +1,322 @@
+/*
+ * 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 "nodes.h"
+#include "optimizing_unit_test.h"
+#include "pretty_printer.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static HBasicBlock* createIfBlock(HGraph* graph, ArenaAllocator* allocator) {
+  HBasicBlock* if_block = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(if_block);
+  HInstruction* instr = new (allocator) HIntConstant(4);
+  if_block->AddInstruction(instr);
+  instr = new (allocator) HIf(instr);
+  if_block->AddInstruction(instr);
+  return if_block;
+}
+
+static HBasicBlock* createGotoBlock(HGraph* graph, ArenaAllocator* allocator) {
+  HBasicBlock* block = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  HInstruction* got = new (allocator) HGoto();
+  block->AddInstruction(got);
+  return block;
+}
+
+static HBasicBlock* createReturnBlock(HGraph* graph, ArenaAllocator* allocator) {
+  HBasicBlock* block = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  HInstruction* return_instr = new (allocator) HReturnVoid();
+  block->AddInstruction(return_instr);
+  return block;
+}
+
+static HBasicBlock* createExitBlock(HGraph* graph, ArenaAllocator* allocator) {
+  HBasicBlock* block = new (allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  HInstruction* exit_instr = new (allocator) HExit();
+  block->AddInstruction(exit_instr);
+  return block;
+}
+
+
+// Test that the successors of an if block stay consistent after a SimplifyCFG.
+// This test sets the false block to be the return block.
+TEST(GraphTest, IfSuccessorSimpleJoinBlock1) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* if_true = createGotoBlock(graph, &allocator);
+  HBasicBlock* return_block = createReturnBlock(graph, &allocator);
+  HBasicBlock* exit_block = createExitBlock(graph, &allocator);
+
+  entry_block->AddSuccessor(if_block);
+  if_block->AddSuccessor(if_true);
+  if_true->AddSuccessor(return_block);
+  if_block->AddSuccessor(return_block);
+  return_block->AddSuccessor(exit_block);
+
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true);
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
+
+  graph->SimplifyCFG();
+
+  // Ensure we still have the same if true block.
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true);
+
+  // Ensure the critical edge has been removed.
+  HBasicBlock* false_block = if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor();
+  ASSERT_NE(false_block, return_block);
+
+  // Ensure the new block branches to the join block.
+  ASSERT_EQ(false_block->GetSuccessors().Get(0), return_block);
+}
+
+// Test that the successors of an if block stay consistent after a SimplifyCFG.
+// This test sets the true block to be the return block.
+TEST(GraphTest, IfSuccessorSimpleJoinBlock2) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* if_false = createGotoBlock(graph, &allocator);
+  HBasicBlock* return_block = createReturnBlock(graph, &allocator);
+  HBasicBlock* exit_block = createExitBlock(graph, &allocator);
+
+  entry_block->AddSuccessor(if_block);
+  if_block->AddSuccessor(return_block);
+  if_false->AddSuccessor(return_block);
+  if_block->AddSuccessor(if_false);
+  return_block->AddSuccessor(exit_block);
+
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false);
+
+  graph->SimplifyCFG();
+
+  // Ensure we still have the same if true block.
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false);
+
+  // Ensure the critical edge has been removed.
+  HBasicBlock* true_block = if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor();
+  ASSERT_NE(true_block, return_block);
+
+  // Ensure the new block branches to the join block.
+  ASSERT_EQ(true_block->GetSuccessors().Get(0), return_block);
+}
+
+// Test that the successors of an if block stay consistent after a SimplifyCFG.
+// This test sets the true block to be the loop header.
+TEST(GraphTest, IfSuccessorMultipleBackEdges1) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* return_block = createReturnBlock(graph, &allocator);
+  HBasicBlock* exit_block = createExitBlock(graph, &allocator);
+
+  graph->SetEntryBlock(entry_block);
+  entry_block->AddSuccessor(if_block);
+  if_block->AddSuccessor(if_block);
+  if_block->AddSuccessor(return_block);
+  return_block->AddSuccessor(exit_block);
+
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_block);
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
+
+  graph->BuildDominatorTree();
+
+  // Ensure we still have the same if false block.
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
+
+  // Ensure there is only one back edge.
+  ASSERT_EQ(if_block->GetPredecessors().Size(), 2u);
+  ASSERT_EQ(if_block->GetPredecessors().Get(0), entry_block);
+  ASSERT_NE(if_block->GetPredecessors().Get(1), if_block);
+
+  // Ensure the new block is the back edge.
+  ASSERT_EQ(if_block->GetPredecessors().Get(1),
+            if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor());
+}
+
+// Test that the successors of an if block stay consistent after a SimplifyCFG.
+// This test sets the false block to be the loop header.
+TEST(GraphTest, IfSuccessorMultipleBackEdges2) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* return_block = createReturnBlock(graph, &allocator);
+  HBasicBlock* exit_block = createExitBlock(graph, &allocator);
+
+  graph->SetEntryBlock(entry_block);
+  entry_block->AddSuccessor(if_block);
+  if_block->AddSuccessor(return_block);
+  if_block->AddSuccessor(if_block);
+  return_block->AddSuccessor(exit_block);
+
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_block);
+
+  graph->BuildDominatorTree();
+
+  // Ensure we still have the same if true block.
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
+
+  // Ensure there is only one back edge.
+  ASSERT_EQ(if_block->GetPredecessors().Size(), 2u);
+  ASSERT_EQ(if_block->GetPredecessors().Get(0), entry_block);
+  ASSERT_NE(if_block->GetPredecessors().Get(1), if_block);
+
+  // Ensure the new block is the back edge.
+  ASSERT_EQ(if_block->GetPredecessors().Get(1),
+            if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor());
+}
+
+// Test that the successors of an if block stay consistent after a SimplifyCFG.
+// This test sets the true block to be a loop header with multiple pre headers.
+TEST(GraphTest, IfSuccessorMultiplePreHeaders1) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* first_if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* loop_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* return_block = createReturnBlock(graph, &allocator);
+
+  graph->SetEntryBlock(entry_block);
+  entry_block->AddSuccessor(first_if_block);
+  first_if_block->AddSuccessor(if_block);
+  first_if_block->AddSuccessor(loop_block);
+  loop_block->AddSuccessor(loop_block);
+  if_block->AddSuccessor(loop_block);
+  if_block->AddSuccessor(return_block);
+
+
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), loop_block);
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block);
+
+  graph->BuildDominatorTree();
+
+  HIf* if_instr = if_block->GetLastInstruction()->AsIf();
+  // Ensure we still have the same if false block.
+  ASSERT_EQ(if_instr->IfFalseSuccessor(), return_block);
+
+  // Ensure there is only one pre header..
+  ASSERT_EQ(loop_block->GetPredecessors().Size(), 2u);
+
+  // Ensure the new block is the successor of the true block.
+  ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().Size(), 1u);
+  ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().Get(0),
+            loop_block->GetLoopInformation()->GetPreHeader());
+}
+
+// Test that the successors of an if block stay consistent after a SimplifyCFG.
+// This test sets the false block to be a loop header with multiple pre headers.
+TEST(GraphTest, IfSuccessorMultiplePreHeaders2) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* first_if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* if_block = createIfBlock(graph, &allocator);
+  HBasicBlock* loop_block = createGotoBlock(graph, &allocator);
+  HBasicBlock* return_block = createReturnBlock(graph, &allocator);
+
+  graph->SetEntryBlock(entry_block);
+  entry_block->AddSuccessor(first_if_block);
+  first_if_block->AddSuccessor(if_block);
+  first_if_block->AddSuccessor(loop_block);
+  loop_block->AddSuccessor(loop_block);
+  if_block->AddSuccessor(return_block);
+  if_block->AddSuccessor(loop_block);
+
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block);
+  ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), loop_block);
+
+  graph->BuildDominatorTree();
+
+  HIf* if_instr = if_block->GetLastInstruction()->AsIf();
+  // Ensure we still have the same if true block.
+  ASSERT_EQ(if_instr->IfTrueSuccessor(), return_block);
+
+  // Ensure there is only one pre header..
+  ASSERT_EQ(loop_block->GetPredecessors().Size(), 2u);
+
+  // Ensure the new block is the successor of the false block.
+  ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().Size(), 1u);
+  ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().Get(0),
+            loop_block->GetLoopInformation()->GetPreHeader());
+}
+
+TEST(GraphTest, InsertInstructionBefore) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* block = createGotoBlock(graph, &allocator);
+  HInstruction* got = block->GetLastInstruction();
+  ASSERT_TRUE(got->IsControlFlow());
+
+  // Test at the beginning of the block.
+  HInstruction* first_instruction = new (&allocator) HIntConstant(4);
+  block->InsertInstructionBefore(first_instruction, got);
+
+  ASSERT_NE(first_instruction->GetId(), -1);
+  ASSERT_EQ(first_instruction->GetBlock(), block);
+  ASSERT_EQ(block->GetFirstInstruction(), first_instruction);
+  ASSERT_EQ(block->GetLastInstruction(), got);
+  ASSERT_EQ(first_instruction->GetNext(), got);
+  ASSERT_EQ(first_instruction->GetPrevious(), nullptr);
+  ASSERT_EQ(got->GetNext(), nullptr);
+  ASSERT_EQ(got->GetPrevious(), first_instruction);
+
+  // Test in the middle of the block.
+  HInstruction* second_instruction = new (&allocator) HIntConstant(4);
+  block->InsertInstructionBefore(second_instruction, got);
+
+  ASSERT_NE(second_instruction->GetId(), -1);
+  ASSERT_EQ(second_instruction->GetBlock(), block);
+  ASSERT_EQ(block->GetFirstInstruction(), first_instruction);
+  ASSERT_EQ(block->GetLastInstruction(), got);
+  ASSERT_EQ(first_instruction->GetNext(), second_instruction);
+  ASSERT_EQ(first_instruction->GetPrevious(), nullptr);
+  ASSERT_EQ(second_instruction->GetNext(), got);
+  ASSERT_EQ(second_instruction->GetPrevious(), first_instruction);
+  ASSERT_EQ(got->GetNext(), nullptr);
+  ASSERT_EQ(got->GetPrevious(), second_instruction);
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
index c797497..017117a 100644
--- a/compiler/optimizing/live_ranges_test.cc
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -152,22 +152,22 @@ TEST(LiveRangesTest, CFG3) {
   SsaLivenessAnalysis liveness(*graph);
   liveness.Analyze();
 
-  // Test for the 0 constant.
-  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
+  // Test for the 4 constant.
+  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
   LiveRange* range = interval->GetFirstRange();
-  ASSERT_EQ(2u, range->GetStart());
+  ASSERT_EQ(4u, range->GetStart());
   // Last use is the phi at the return block so instruction is live until
   // the end of the then block.
   ASSERT_EQ(18u, range->GetEnd());
   ASSERT_TRUE(range->GetNext() == nullptr);
 
-  // Test for the 4 constant.
-  interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
+  // Test for the 0 constant.
+  interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
   // The then branch is a hole for this constant, therefore its interval has 2 ranges.
   // First range starts from the definition and ends at the if block.
   range = interval->GetFirstRange();
-  ASSERT_EQ(4u, range->GetStart());
-  // 9 is the end of the if block.
+  ASSERT_EQ(2u, range->GetStart());
+  // 14 is the end of the if block.
   ASSERT_EQ(14u, range->GetEnd());
   // Second range is the else block.
   range = range->GetNext();
@@ -179,6 +179,7 @@ TEST(LiveRangesTest, CFG3) {
   // Test for the phi.
   interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
   range = interval->GetFirstRange();
+  ASSERT_EQ(22u, liveness.GetInstructionFromSsaIndex(3)->GetLifetimePosition());
   ASSERT_EQ(22u, range->GetStart());
   ASSERT_EQ(24u, range->GetEnd());
   ASSERT_TRUE(range->GetNext() == nullptr);
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 752466b..2a97fad 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -35,7 +35,7 @@ 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, false);
+        block->GetSuccessors().Get(j)->RemovePredecessor(block);
       }
       for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
         block->RemovePhi(it.Current()->AsPhi());
@@ -143,8 +143,7 @@ void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) {
   HBasicBlock* new_block = new (arena_) HBasicBlock(this);
   AddBlock(new_block);
   new_block->AddInstruction(new (arena_) HGoto());
-  block->RemoveSuccessor(successor);
-  block->AddSuccessor(new_block);
+  block->ReplaceSuccessor(successor, new_block);
   new_block->AddSuccessor(successor);
   if (successor->IsLoopHeader()) {
     // If we split at a back edge boundary, make the new block the back edge.
@@ -168,8 +167,7 @@ void HGraph::SimplifyLoop(HBasicBlock* header) {
     new_back_edge->AddInstruction(new (arena_) HGoto());
     for (size_t pred = 0, e = info->GetBackEdges().Size(); pred < e; ++pred) {
       HBasicBlock* back_edge = info->GetBackEdges().Get(pred);
-      header->RemovePredecessor(back_edge);
-      back_edge->AddSuccessor(new_back_edge);
+      back_edge->ReplaceSuccessor(header, new_back_edge);
     }
     info->ClearBackEdges();
     info->AddBackEdge(new_back_edge);
@@ -190,9 +188,8 @@ void HGraph::SimplifyLoop(HBasicBlock* header) {
     for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) {
       HBasicBlock* predecessor = header->GetPredecessors().Get(pred);
       if (predecessor != back_edge) {
-        header->RemovePredecessor(predecessor);
+        predecessor->ReplaceSuccessor(header, pre_header);
         pred--;
-        predecessor->AddSuccessor(pre_header);
       }
     }
     pre_header->AddSuccessor(header);
@@ -294,12 +291,20 @@ bool HBasicBlock::Dominates(HBasicBlock* other) const {
 void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) {
   DCHECK(cursor->AsPhi() == nullptr);
   DCHECK(instruction->AsPhi() == nullptr);
+  DCHECK_EQ(instruction->GetId(), -1);
+  DCHECK_NE(cursor->GetId(), -1);
+  DCHECK_EQ(cursor->GetBlock(), this);
+  DCHECK(!instruction->IsControlFlow());
   instruction->next_ = cursor;
   instruction->previous_ = cursor->previous_;
   cursor->previous_ = instruction;
   if (GetFirstInstruction() == cursor) {
     instructions_.first_instruction_ = instruction;
+  } else {
+    instruction->previous_->next_ = instruction;
   }
+  instruction->SetBlock(this);
+  instruction->SetId(GetGraph()->GetNextInstructionId());
 }
 
 static void Add(HInstructionList* instruction_list,
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index b1c8016..68848de 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -283,18 +283,16 @@ class HBasicBlock : public ArenaObject {
     block->predecessors_.Add(this);
   }
 
-  void RemovePredecessor(HBasicBlock* block, bool remove_in_successor = true) {
-    predecessors_.Delete(block);
-    if (remove_in_successor) {
-      block->successors_.Delete(this);
-    }
+  void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) {
+    size_t successor_index = GetSuccessorIndexOf(existing);
+    DCHECK_NE(successor_index, static_cast<size_t>(-1));
+    existing->RemovePredecessor(this);
+    new_block->predecessors_.Add(this);
+    successors_.Put(successor_index, new_block);
   }
 
-  void RemoveSuccessor(HBasicBlock* block, bool remove_in_predecessor = true) {
-    successors_.Delete(block);
-    if (remove_in_predecessor) {
-      block->predecessors_.Delete(this);
-    }
+  void RemovePredecessor(HBasicBlock* block) {
+    predecessors_.Delete(block);
   }
 
   void ClearAllPredecessors() {
@@ -315,6 +313,15 @@ class HBasicBlock : public ArenaObject {
     return -1;
   }
 
+  size_t GetSuccessorIndexOf(HBasicBlock* successor) {
+    for (size_t i = 0, e = successors_.Size(); i < e; ++i) {
+      if (successors_.Get(i) == successor) {
+        return i;
+      }
+    }
+    return -1;
+  }
+
   void AddInstruction(HInstruction* instruction);
   void RemoveInstruction(HInstruction* instruction);
   void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor);
@@ -455,6 +462,7 @@ class HInstruction : public ArenaObject {
   virtual void SetRawInputAt(size_t index, HInstruction* input) = 0;
 
   virtual bool NeedsEnvironment() const { return false; }
+  virtual bool IsControlFlow() const { return false; }
 
   void AddUseAt(HInstruction* user, size_t index) {
     uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_);
@@ -733,7 +741,9 @@ class HTemplateInstruction: public HInstruction {
 // instruction that branches to the exit block.
 class HReturnVoid : public HTemplateInstruction<0> {
  public:
-  HReturnVoid() { }
+  HReturnVoid() {}
+
+  virtual bool IsControlFlow() const { return true; }
 
   DECLARE_INSTRUCTION(ReturnVoid);
 
@@ -749,6 +759,8 @@ class HReturn : public HTemplateInstruction<1> {
     SetRawInputAt(0, value);
   }
 
+  virtual bool IsControlFlow() const { return true; }
+
   DECLARE_INSTRUCTION(Return);
 
  private:
@@ -760,7 +772,9 @@ class HReturn : public HTemplateInstruction<1> {
 // exit block.
 class HExit : public HTemplateInstruction<0> {
  public:
-  HExit() { }
+  HExit() {}
+
+  virtual bool IsControlFlow() const { return true; }
 
   DECLARE_INSTRUCTION(Exit);
 
@@ -771,12 +785,14 @@ class HExit : public HTemplateInstruction<0> {
 // Jumps from one block to another.
 class HGoto : public HTemplateInstruction<0> {
  public:
-  HGoto() { }
+  HGoto() {}
 
   HBasicBlock* GetSuccessor() const {
     return GetBlock()->GetSuccessors().Get(0);
   }
 
+  virtual bool IsControlFlow() const { return true; }
+
   DECLARE_INSTRUCTION(Goto);
 
  private:
@@ -799,6 +815,8 @@ class HIf : public HTemplateInstruction<1> {
     return GetBlock()->GetSuccessors().Get(1);
   }
 
+  virtual bool IsControlFlow() const { return true; }
+
   DECLARE_INSTRUCTION(If);
 
  private:
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 1284a97..54c3c5d 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -102,8 +102,8 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
       for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
         HInstruction* current = ValueOfLocal(block->GetPredecessors().Get(i), local);
         if (current == nullptr) {
-//          one_predecessor_has_no_value = true;
-//          break;
+          one_predecessor_has_no_value = true;
+          break;
         } else if (current != value) {
           is_different = true;
         }
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index dc4b2e5..c367611 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -134,7 +134,6 @@ void SsaLivenessAnalysis::NumberInstructions() {
   for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     block->SetLifetimeStart(lifetime_position);
-    lifetime_position += 2;
 
     for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
       HInstruction* current = it.Current();
@@ -146,6 +145,7 @@ void SsaLivenessAnalysis::NumberInstructions() {
       }
       current->SetLifetimePosition(lifetime_position);
     }
+    lifetime_position += 2;
 
     for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
       HInstruction* current = it.Current();
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 4d56e1f..733535e 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -99,7 +99,7 @@ class UsePosition : public ArenaObject {
 
   HInstruction* GetUser() const { return user_; }
 
-  void Dump(std::ostream& stream) {
+  void Dump(std::ostream& stream) const {
     stream << position_;
   }
 
diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
index 485ea27..3b354f1 100644
--- a/compiler/optimizing/ssa_test.cc
+++ b/compiler/optimizing/ssa_test.cc
@@ -99,7 +99,7 @@ TEST(SsaTest, CFG1) {
     "BasicBlock 0, succ: 1\n"
     "  0: IntConstant 0 [2, 2]\n"
     "  1: Goto\n"
-    "BasicBlock 1, pred: 0, succ: 2, 5\n"
+    "BasicBlock 1, pred: 0, succ: 5, 2\n"
     "  2: Equal(0, 0) [3]\n"
     "  3: If(2)\n"
     "BasicBlock 2, pred: 1, succ: 3\n"
@@ -129,7 +129,7 @@ TEST(SsaTest, CFG2) {
     "  0: IntConstant 0 [6, 3, 3]\n"
     "  1: IntConstant 4 [6]\n"
     "  2: Goto\n"
-    "BasicBlock 1, pred: 0, succ: 2, 5\n"
+    "BasicBlock 1, pred: 0, succ: 5, 2\n"
     "  3: Equal(0, 0) [4]\n"
     "  4: If(3)\n"
     "BasicBlock 2, pred: 1, succ: 3\n"
@@ -409,7 +409,7 @@ TEST(SsaTest, Loop7) {
     "  3: Goto\n"
     "BasicBlock 1, pred: 0, succ: 2\n"
     "  4: Goto\n"
-    "BasicBlock 2, pred: 1, 5, succ: 3, 8\n"
+    "BasicBlock 2, pred: 1, 5, succ: 8, 3\n"
     "  5: Phi(0, 1) [12, 6, 6]\n"
     "  6: Equal(5, 5) [7]\n"
     "  7: If(6)\n"
@@ -467,7 +467,7 @@ TEST(SsaTest, LocalInIf) {
     "  0: IntConstant 0 [3, 3]\n"
     "  1: IntConstant 4\n"
     "  2: Goto\n"
-    "BasicBlock 1, pred: 0, succ: 2, 5\n"
+    "BasicBlock 1, pred: 0, succ: 5, 2\n"
     "  3: Equal(0, 0) [4]\n"
     "  4: If(3)\n"
     "BasicBlock 2, pred: 1, succ: 3\n"
@@ -489,4 +489,43 @@ TEST(SsaTest, LocalInIf) {
   TestCode(data, expected);
 }
 
+TEST(SsaTest, MultiplePredecessors) {
+  // Test that we do not create a phi when one predecessor
+  // does not update the local.
+  const char* expected =
+    "BasicBlock 0, succ: 1\n"
+    "  0: IntConstant 0 [4, 8, 6, 6, 2, 2, 8, 4]\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: 5\n"
+    "  4: Add(0, 0)\n"
+    "  5: Goto\n"
+    "BasicBlock 3, pred: 1, succ: 7, 4\n"
+    "  6: Equal(0, 0) [7]\n"
+    "  7: If(6)\n"
+    "BasicBlock 4, pred: 3, succ: 5\n"
+    "  8: Add(0, 0)\n"
+    "  9: Goto\n"
+    // This block should not get a phi for local 1.
+    "BasicBlock 5, pred: 2, 4, 7, succ: 6\n"
+    "  10: ReturnVoid\n"
+    "BasicBlock 6, pred: 5\n"
+    "  11: Exit\n"
+    "BasicBlock 7, pred: 3, succ: 5\n"
+    "  12: Goto\n";
+
+  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 5,
+    Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8,
+    Instruction::GOTO | 0x0500,
+    Instruction::IF_EQ, 4,
+    Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8,
+    Instruction::RETURN_VOID);
+
+  TestCode(data, expected);
+}
+
 }  // namespace art