diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 944e803..3d65366 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1814,8 +1814,8 @@
 
 class MoveOperands : public ArenaObject {
  public:
-  MoveOperands(Location source, Location destination)
-      : source_(source), destination_(destination) {}
+  MoveOperands(Location source, Location destination, HInstruction* instruction)
+      : source_(source), destination_(destination), instruction_(instruction) {}
 
   Location GetSource() const { return source_; }
   Location GetDestination() const { return destination_; }
@@ -1863,9 +1863,16 @@
     return source_.IsInvalid();
   }
 
+  HInstruction* GetInstruction() const { return instruction_; }
+
  private:
   Location source_;
   Location destination_;
+  // The instruction this move is assocatied with. Null when this move is
+  // for moving an input in the expected locations of user (including a phi user).
+  // This is only used in debug mode, to ensure we do not connect interval siblings
+  // in the same parallel move.
+  HInstruction* instruction_;
 
   DISALLOW_COPY_AND_ASSIGN(MoveOperands);
 };
@@ -1878,6 +1885,12 @@
       : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {}
 
   void AddMove(MoveOperands* move) {
+    if (kIsDebugBuild && move->GetInstruction() != nullptr) {
+      for (size_t i = 0, e = moves_.Size(); i < e; ++i) {
+        DCHECK_NE(moves_.Get(i)->GetInstruction(), move->GetInstruction())
+          << "Doing parallel moves for the same instruction.";
+      }
+    }
     moves_.Add(move);
   }
 
diff --git a/compiler/optimizing/parallel_move_test.cc b/compiler/optimizing/parallel_move_test.cc
index 093856d..863e107 100644
--- a/compiler/optimizing/parallel_move_test.cc
+++ b/compiler/optimizing/parallel_move_test.cc
@@ -71,7 +71,8 @@
   for (size_t i = 0; i < number_of_moves; ++i) {
     moves->AddMove(new (allocator) MoveOperands(
         Location::RegisterLocation(ManagedRegister(operands[i][0])),
-        Location::RegisterLocation(ManagedRegister(operands[i][1]))));
+        Location::RegisterLocation(ManagedRegister(operands[i][1])),
+        nullptr));
   }
   return moves;
 }
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 4b45f43..f4fb336 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -753,30 +753,31 @@
   return destination.IsRegister() || destination.IsStackSlot() || destination.IsDoubleStackSlot();
 }
 
-void RegisterAllocator::AddInputMoveFor(HInstruction* instruction,
+void RegisterAllocator::AddInputMoveFor(HInstruction* user,
                                         Location source,
                                         Location destination) const {
   DCHECK(IsValidDestination(destination));
   if (source.Equals(destination)) return;
 
-  DCHECK(instruction->AsPhi() == nullptr);
+  DCHECK(user->AsPhi() == nullptr);
 
-  HInstruction* previous = instruction->GetPrevious();
+  HInstruction* previous = user->GetPrevious();
   HParallelMove* move = nullptr;
   if (previous == nullptr
       || previous->AsParallelMove() == nullptr
       || !IsInputMove(previous)) {
     move = new (allocator_) HParallelMove(allocator_);
     move->SetLifetimePosition(kInputMoveLifetimePosition);
-    instruction->GetBlock()->InsertInstructionBefore(move, instruction);
+    user->GetBlock()->InsertInstructionBefore(move, user);
   } else {
     move = previous->AsParallelMove();
   }
   DCHECK(IsInputMove(move));
-  move->AddMove(new (allocator_) MoveOperands(source, destination));
+  move->AddMove(new (allocator_) MoveOperands(source, destination, nullptr));
 }
 
 void RegisterAllocator::InsertParallelMoveAt(size_t position,
+                                             HInstruction* instruction,
                                              Location source,
                                              Location destination) const {
   DCHECK(IsValidDestination(destination));
@@ -802,7 +803,7 @@
   } else {
     // Move must happen before the instruction.
     HInstruction* previous = at->GetPrevious();
-    if (previous != nullptr && previous->AsParallelMove() != nullptr) {
+    if (previous != nullptr && previous->IsParallelMove()) {
       // This is a parallel move for connecting siblings in a same block. We need to
       // differentiate it with moves for connecting blocks, and input moves.
       if (previous->GetLifetimePosition() != position) {
@@ -813,7 +814,15 @@
         previous = previous->GetPrevious();
       }
     }
-    if (previous == nullptr || previous->AsParallelMove() == nullptr) {
+    if (previous == nullptr
+        || !previous->IsParallelMove()
+        || previous->GetLifetimePosition() != position) {
+      // If the previous is a parallel move, then its position must be lower
+      // than the given `position`: it was added just after the non-parallel
+      // move instruction that precedes `instruction`.
+      DCHECK(previous == nullptr
+             || !previous->IsParallelMove()
+             || previous->GetLifetimePosition() < position);
       move = new (allocator_) HParallelMove(allocator_);
       move->SetLifetimePosition(position);
       at->GetBlock()->InsertInstructionBefore(move, at);
@@ -821,10 +830,11 @@
       move = previous->AsParallelMove();
     }
   }
-  move->AddMove(new (allocator_) MoveOperands(source, destination));
+  move->AddMove(new (allocator_) MoveOperands(source, destination, instruction));
 }
 
 void RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block,
+                                                   HInstruction* instruction,
                                                    Location source,
                                                    Location destination) const {
   DCHECK(IsValidDestination(destination));
@@ -836,7 +846,7 @@
   HParallelMove* move;
   // This is a parallel move for connecting blocks. We need to differentiate
   // it with moves for connecting siblings in a same block, and output moves.
-  if (previous == nullptr || previous->AsParallelMove() == nullptr
+  if (previous == nullptr || !previous->IsParallelMove()
       || previous->AsParallelMove()->GetLifetimePosition() != block->GetLifetimeEnd()) {
     move = new (allocator_) HParallelMove(allocator_);
     move->SetLifetimePosition(block->GetLifetimeEnd());
@@ -844,10 +854,11 @@
   } else {
     move = previous->AsParallelMove();
   }
-  move->AddMove(new (allocator_) MoveOperands(source, destination));
+  move->AddMove(new (allocator_) MoveOperands(source, destination, instruction));
 }
 
 void RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block,
+                                                    HInstruction* instruction,
                                                     Location source,
                                                     Location destination) const {
   DCHECK(IsValidDestination(destination));
@@ -862,7 +873,7 @@
     move->SetLifetimePosition(block->GetLifetimeStart());
     block->InsertInstructionBefore(move, first);
   }
-  move->AddMove(new (allocator_) MoveOperands(source, destination));
+  move->AddMove(new (allocator_) MoveOperands(source, destination, instruction));
 }
 
 void RegisterAllocator::InsertMoveAfter(HInstruction* instruction,
@@ -872,7 +883,7 @@
   if (source.Equals(destination)) return;
 
   if (instruction->AsPhi() != nullptr) {
-    InsertParallelMoveAtEntryOf(instruction->GetBlock(), source, destination);
+    InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination);
     return;
   }
 
@@ -886,7 +897,7 @@
     move->SetLifetimePosition(position);
     instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext());
   }
-  move->AddMove(new (allocator_) MoveOperands(source, destination));
+  move->AddMove(new (allocator_) MoveOperands(source, destination, instruction));
 }
 
 void RegisterAllocator::ConnectSiblings(LiveInterval* interval) {
@@ -930,7 +941,7 @@
         && next_sibling->HasRegister()
         && current->GetEnd() == next_sibling->GetStart()) {
       Location destination = ConvertToLocation(next_sibling);
-      InsertParallelMoveAt(current->GetEnd(), source, destination);
+      InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination);
     }
 
     // At each safepoint, we record stack and register information.
@@ -1015,10 +1026,16 @@
   // If `from` has only one successor, we can put the moves at the exit of it. Otherwise
   // we need to put the moves at the entry of `to`.
   if (from->GetSuccessors().Size() == 1) {
-    InsertParallelMoveAtExitOf(from, ConvertToLocation(source), ConvertToLocation(destination));
+    InsertParallelMoveAtExitOf(from,
+                               interval->GetParent()->GetDefinedBy(),
+                               ConvertToLocation(source),
+                               ConvertToLocation(destination));
   } else {
     DCHECK_EQ(to->GetPredecessors().Size(), 1u);
-    InsertParallelMoveAtEntryOf(to, ConvertToLocation(source), ConvertToLocation(destination));
+    InsertParallelMoveAtEntryOf(to,
+                                interval->GetParent()->GetDefinedBy(),
+                                ConvertToLocation(source),
+                                ConvertToLocation(destination));
   }
 }
 
@@ -1101,7 +1118,7 @@
         Location source = FindLocationAt(input->GetLiveInterval(),
                                          predecessor->GetLastInstruction()->GetLifetimePosition());
         Location destination = ConvertToLocation(phi->GetLiveInterval());
-        InsertParallelMoveAtExitOf(predecessor, source, destination);
+        InsertParallelMoveAtExitOf(predecessor, nullptr, source, destination);
       }
     }
   }
diff --git a/compiler/optimizing/register_allocator.h b/compiler/optimizing/register_allocator.h
index b97b6fc..d4c233a 100644
--- a/compiler/optimizing/register_allocator.h
+++ b/compiler/optimizing/register_allocator.h
@@ -108,11 +108,20 @@
   void ConnectSplitSiblings(LiveInterval* interval, HBasicBlock* from, HBasicBlock* to) const;
 
   // Helper methods to insert parallel moves in the graph.
-  void InsertParallelMoveAtExitOf(HBasicBlock* block, Location source, Location destination) const;
-  void InsertParallelMoveAtEntryOf(HBasicBlock* block, Location source, Location destination) const;
+  void InsertParallelMoveAtExitOf(HBasicBlock* block,
+                                  HInstruction* instruction,
+                                  Location source,
+                                  Location destination) const;
+  void InsertParallelMoveAtEntryOf(HBasicBlock* block,
+                                   HInstruction* instruction,
+                                   Location source,
+                                   Location destination) const;
   void InsertMoveAfter(HInstruction* instruction, Location source, Location destination) const;
-  void AddInputMoveFor(HInstruction* instruction, Location source, Location destination) const;
-  void InsertParallelMoveAt(size_t position, Location source, Location destination) const;
+  void AddInputMoveFor(HInstruction* user, Location source, Location destination) const;
+  void InsertParallelMoveAt(size_t position,
+                            HInstruction* instruction,
+                            Location source,
+                            Location destination) const;
 
   // Helper methods.
   void AllocateRegistersInternal();