Change register allocator to deal better with unconstrained uses.

When low on registers, if the interval we are currently attempting
to allocate a register for has an unconstrained first use, split
the current interval instead of finding another interval to split.

In addition, make the determination of when to split argument
values right after their definition more precise.

These changes shouldn't matter much at this point. However,
zerny@ is working on changes to debug information handling
that will make this occur a lot more for arguments. For such
cases this is needed and generates better code than we currently
do.

R=zerny@google.com

Change-Id: I6d83b91a15486d294c2c66f68b17cb871c0cbae1

3 files changed, 50 insertions, 16 deletions

diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
index 33dc79a97..a30f57440 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
@@ -567,18 +567,18 @@ public class LinearScanRegisterAllocator implements RegisterAllocator {
         active.add(argumentInterval);
       } else {
         // Treat the argument interval as spilled which will require a load to a different
-        // register for all usages.
+        // register for all register-constrained usages.
         if (argumentInterval.getUses().size() > 1) {
           LiveIntervalsUse use = argumentInterval.firstUseWithConstraint();
           if (use != null) {
             LiveIntervals split;
-            if (argumentInterval.getUses().size() == 2) {
-              // If there is only one real use (definition plus one real use), split before
+            if (argumentInterval.numberOfUsesWithConstraint() == 1) {
+              // If there is only one register-constrained use, split before
               // that one use.
               split = argumentInterval.splitBefore(use.getPosition());
             } else {
-              // If there are multiple real users, split right after the definition to make it
-              // more likely that arguments get in usable registers from the start.
+              // If there are multiple register-constrained users, split right after the definition
+              // to make it more likely that arguments get in usable registers from the start.
               split = argumentInterval
                   .splitBefore(argumentInterval.getValue().definition.getNumber() + 1);
             }
@@ -1004,7 +1004,24 @@ public class LinearScanRegisterAllocator implements RegisterAllocator {
         // argument reuse disallowed.
         return false;
       }
-      allocateBlockedRegister(unhandledInterval);
+      // If the first use for these intervals is unconstrained, just spill this interval instead
+      // of finding another candidate to spill via allocateBlockedRegister.
+      if (!unhandledInterval.getUses().first().hasConstraint()) {
+        int nextConstrainedPosition = unhandledInterval.firstUseWithConstraint().getPosition();
+        int register;
+        // Arguments are always in the argument registers, so for arguments just use that register
+        // for the unconstrained prefix. For everything else, get a spill register.
+        if (unhandledInterval.isArgumentInterval()) {
+          register = unhandledInterval.getSplitParent().getRegister();
+        } else {
+          register = getSpillRegister(unhandledInterval);
+        }
+        LiveIntervals split = unhandledInterval.splitBefore(nextConstrainedPosition);
+        assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, register);
+        unhandled.add(split);
+      } else {
+        allocateBlockedRegister(unhandledInterval);
+      }
     } else if (largestFreePosition >= unhandledInterval.getEnd()) {
       // Free for the entire interval. Allocate the register.
       assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, candidate);
@@ -1016,8 +1033,7 @@ public class LinearScanRegisterAllocator implements RegisterAllocator {
       }
       // The candidate is free for the beginning of an interval. We split the interval
       // and use the register for as long as we can.
-      int splitPosition = largestFreePosition;
-      LiveIntervals split = unhandledInterval.splitBefore(splitPosition);
+      LiveIntervals split = unhandledInterval.splitBefore(largestFreePosition);
       assert split != unhandledInterval;
       assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, candidate);
       unhandled.add(split);
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java b/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java
index cf44137fd..f01ed3adf 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.regalloc;
 
+import static com.android.tools.r8.dex.Constants.U16BIT_MAX;
 import static com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator.NO_REGISTER;
 
 import com.android.tools.r8.dex.Constants;
@@ -29,7 +30,7 @@ public class LiveIntervals {
   private boolean spilled = false;
 
   // Only registers up to and including the registerLimit are allowed for this interval.
-  private int registerLimit = Constants.U16BIT_MAX;
+  private int registerLimit = U16BIT_MAX;
 
   // Max register used for any of the non-spilled splits for these live intervals or for any of the
   // live intervals that this live interval is connected to by phi moves. This is used to
@@ -331,7 +332,7 @@ public class LiveIntervals {
 
   public LiveIntervalsUse firstUseWithConstraint() {
     for (LiveIntervalsUse use : uses) {
-      if (use.getLimit() < Constants.U16BIT_MAX) {
+      if (use.hasConstraint()) {
         return use;
       }
     }
@@ -386,13 +387,14 @@ public class LiveIntervals {
   }
 
   private void recomputeLimit() {
-    registerLimit = Constants.U16BIT_MAX;
+    registerLimit = U16BIT_MAX;
     for (LiveIntervalsUse use : uses) {
       updateRegisterConstraint(use.getLimit());
     }
   }
 
   public LiveIntervals getSplitCovering(int instructionNumber) {
+    assert getSplitParent() == this;
     // Check if this interval itself is covering the instruction.
     if (getStart() <= instructionNumber && getEnd() > instructionNumber) {
       return this;
@@ -417,6 +419,20 @@ public class LiveIntervals {
     return null;
   }
 
+  public boolean isConstantNumberInterval() {
+    return value.definition != null && value.definition.isConstNumber();
+  }
+
+  public int numberOfUsesWithConstraint() {
+    int count = 0;
+    for (LiveIntervalsUse use : getUses()) {
+      if (use.hasConstraint()) {
+        count++;
+      }
+    }
+    return count;
+  }
+
   @Override
   public String toString() {
     StringBuilder builder = new StringBuilder();
@@ -468,8 +484,4 @@ public class LiveIntervals {
       splitChild.print(printer, number + delta, number);
     }
   }
-
-  public boolean isConstantNumberInterval() {
-    return value.definition != null && value.definition.isConstNumber();
-  }
-}
\ No newline at end of file
+}
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervalsUse.java b/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervalsUse.java
index fd37af8f3..a60213453 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervalsUse.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervalsUse.java
@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.regalloc;
 
+import static com.android.tools.r8.dex.Constants.U16BIT_MAX;
+
 public class LiveIntervalsUse implements Comparable<LiveIntervalsUse> {
   private int position;
   private int limit;
@@ -41,4 +43,8 @@ public class LiveIntervalsUse implements Comparable<LiveIntervalsUse> {
     }
     return limit - o.limit;
   }
+
+  public boolean hasConstraint() {
+    return limit < U16BIT_MAX;
+  }
 }