Fix a bug in the insertion of parallel move.
To make sure we do not connect interval siblings in the
same parallel move, I added a new field in MoveOperands
that tells for which instruction this move is for.
A parallel move should not contains moves for the same instructions.
The checks revealed a bug when connecting siblings, where
we would choose the wrong parallel move.
Change-Id: I70f27ec120886745c187071453c78da4c47c1dd2
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();