diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index e743d8e..8950635 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -88,23 +88,36 @@
 
   // Visit this block's list of phis.
   for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+    HInstruction* current = it.Current();
     // Ensure this block's list of phis contains only phis.
-    if (!it.Current()->IsPhi()) {
+    if (!current->IsPhi()) {
       AddError(StringPrintf("Block %d has a non-phi in its phi list.",
                             current_block_->GetBlockId()));
     }
-    it.Current()->Accept(this);
+    if (current->GetNext() == nullptr && current != block->GetLastPhi()) {
+      AddError(StringPrintf("The recorded last phi of block %d does not match "
+                            "the actual last phi %d.",
+                            current_block_->GetBlockId(),
+                            current->GetId()));
+    }
+    current->Accept(this);
   }
 
   // Visit this block's list of instructions.
-  for (HInstructionIterator it(block->GetInstructions()); !it.Done();
-       it.Advance()) {
+  for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+    HInstruction* current = it.Current();
     // Ensure this block's list of instructions does not contains phis.
-    if (it.Current()->IsPhi()) {
+    if (current->IsPhi()) {
       AddError(StringPrintf("Block %d has a phi in its non-phi list.",
                             current_block_->GetBlockId()));
     }
-    it.Current()->Accept(this);
+    if (current->GetNext() == nullptr && current != block->GetLastInstruction()) {
+      AddError(StringPrintf("The recorded last instruction of block %d does not match "
+                            "the actual last instruction %d.",
+                            current_block_->GetBlockId(),
+                            current->GetId()));
+    }
+    current->Accept(this);
   }
 }
 
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 4b9d4fc..bef5896 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -416,26 +416,6 @@
   DCHECK(!instruction->HasEnvironment());
 }
 
-void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) {
-  DCHECK(!cursor->IsPhi());
-  DCHECK(!instruction->IsPhi());
-  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());
-  UpdateInputsUsers(instruction);
-}
-
 void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial,
                                                   HInstruction* replacement) {
   DCHECK(initial->GetBlock() == this);
@@ -463,23 +443,27 @@
   Add(&phis_, this, phi);
 }
 
+void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) {
+  DCHECK(!cursor->IsPhi());
+  DCHECK(!instruction->IsPhi());
+  DCHECK_EQ(instruction->GetId(), -1);
+  DCHECK_NE(cursor->GetId(), -1);
+  DCHECK_EQ(cursor->GetBlock(), this);
+  DCHECK(!instruction->IsControlFlow());
+  instruction->SetBlock(this);
+  instruction->SetId(GetGraph()->GetNextInstructionId());
+  UpdateInputsUsers(instruction);
+  instructions_.InsertInstructionBefore(instruction, cursor);
+}
+
 void HBasicBlock::InsertPhiAfter(HPhi* phi, HPhi* cursor) {
   DCHECK_EQ(phi->GetId(), -1);
   DCHECK_NE(cursor->GetId(), -1);
   DCHECK_EQ(cursor->GetBlock(), this);
-  if (cursor->next_ == nullptr) {
-    cursor->next_ = phi;
-    phi->previous_ = cursor;
-    DCHECK(phi->next_ == nullptr);
-  } else {
-    phi->next_ = cursor->next_;
-    phi->previous_ = cursor;
-    cursor->next_ = phi;
-    phi->next_->previous_ = phi;
-  }
   phi->SetBlock(this);
   phi->SetId(GetGraph()->GetNextInstructionId());
   UpdateInputsUsers(phi);
+  phis_.InsertInstructionAfter(phi, cursor);
 }
 
 static void Remove(HInstructionList* instruction_list,
@@ -546,6 +530,34 @@
   }
 }
 
+void HInstructionList::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) {
+  DCHECK(Contains(cursor));
+  if (cursor == first_instruction_) {
+    cursor->previous_ = instruction;
+    instruction->next_ = cursor;
+    first_instruction_ = instruction;
+  } else {
+    instruction->previous_ = cursor->previous_;
+    instruction->next_ = cursor;
+    cursor->previous_ = instruction;
+    instruction->previous_->next_ = instruction;
+  }
+}
+
+void HInstructionList::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) {
+  DCHECK(Contains(cursor));
+  if (cursor == last_instruction_) {
+    cursor->next_ = instruction;
+    instruction->previous_ = cursor;
+    last_instruction_ = instruction;
+  } else {
+    instruction->next_ = cursor->next_;
+    instruction->previous_ = cursor;
+    cursor->next_ = instruction;
+    instruction->next_->previous_ = instruction;
+  }
+}
+
 void HInstructionList::RemoveInstruction(HInstruction* instruction) {
   if (instruction->previous_ != nullptr) {
     instruction->previous_->next_ = instruction->next_;
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 08fcdbb..1a24cb5 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -75,6 +75,10 @@
   void AddInstruction(HInstruction* instruction);
   void RemoveInstruction(HInstruction* instruction);
 
+  // Insert `instruction` before/after an existing instruction `cursor`.
+  void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor);
+  void InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor);
+
   // Return true if this list contains `instruction`.
   bool Contains(HInstruction* instruction) const;
 
@@ -467,8 +471,9 @@
   HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; }
   HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; }
   const HInstructionList& GetInstructions() const { return instructions_; }
-  const HInstructionList& GetPhis() const { return phis_; }
   HInstruction* GetFirstPhi() const { return phis_.first_instruction_; }
+  HInstruction* GetLastPhi() const { return phis_.last_instruction_; }
+  const HInstructionList& GetPhis() const { return phis_; }
 
   void AddSuccessor(HBasicBlock* block) {
     successors_.Add(block);