Opt compiler: Implement parallel move resolver without using swap.
The algorithm of ParallelMoveResolverNoSwap() is almost the same with
ParallelMoveResolverWithSwap(), except the way we resolve the circular
dependency. NoSwap() uses additional scratch register to resolve the
circular dependency. For example, (0->1) (1->2) (2->0) will be performed
as (2->scratch) (1->2) (0->1) (scratch->0).
On architectures without swap register support, NoSwap() can reduce the
number of moves from 3x(N-1) to (N+1) when there is circular dependency
with N moves.
And also, NoSwap() algorithm does not depend on architecture register
layout information, which means it can support register pairs on arm32
and X/W, D/S registers on arm64 without additional modification.
Change-Id: Idf56bd5469bb78c0e339e43ab16387428a082318
diff --git a/compiler/optimizing/locations.h b/compiler/optimizing/locations.h
index de876be..c3a9915 100644
--- a/compiler/optimizing/locations.h
+++ b/compiler/optimizing/locations.h
@@ -285,17 +285,26 @@
bool Contains(Location other) const {
if (Equals(other)) {
return true;
- } else if (IsFpuRegisterPair() && other.IsFpuRegister()) {
- return other.reg() == low() || other.reg() == high();
- } else if (IsRegisterPair() && other.IsRegister()) {
- return other.reg() == low() || other.reg() == high();
- } else if (IsDoubleStackSlot() && other.IsStackSlot()) {
- return (GetStackIndex() == other.GetStackIndex())
- || (GetStackIndex() + 4 == other.GetStackIndex());
+ } else if (IsPair() || IsDoubleStackSlot()) {
+ return ToLow().Equals(other) || ToHigh().Equals(other);
}
return false;
}
+ bool OverlapsWith(Location other) const {
+ // Only check the overlapping case that can happen with our register allocation algorithm.
+ bool overlap = Contains(other) || other.Contains(*this);
+ if (kIsDebugBuild && !overlap) {
+ // Note: These are also overlapping cases. But we are not able to handle them in
+ // ParallelMoveResolverWithSwap. Make sure that we do not meet such case with our compiler.
+ if ((IsPair() && other.IsPair()) || (IsDoubleStackSlot() && other.IsDoubleStackSlot())) {
+ DCHECK(!Contains(other.ToLow()));
+ DCHECK(!Contains(other.ToHigh()));
+ }
+ }
+ return overlap;
+ }
+
const char* DebugString() const {
switch (GetKind()) {
case kInvalid: return "I";