Fix IndexOutOfBoundsException in register allocation

Bug: b/545349635
Change-Id: I14809cac6950f6f9ba50b927abaf1a776a2412c7

src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java

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 6c8906a..347077c 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
@@ -2130,7 +2130,9 @@
           assignFreeRegisterToUnhandledInterval(unhandledInterval, register);
         }
       } else {
-        allocateBlockedRegister(unhandledInterval, registerConstraint);
+        if (!allocateBlockedRegister(unhandledInterval, registerConstraint)) {
+          return false;
+        }
       }
     } else {
       // We will use the candidate register(s) for unhandledInterval, and therefore potentially
@@ -2717,7 +2719,7 @@
     return candidate;
   }
 
-  private void allocateBlockedRegister(LiveIntervals unhandledInterval, int registerConstraint) {
+  private boolean allocateBlockedRegister(LiveIntervals unhandledInterval, int registerConstraint) {
     // Initialize all candidate registers to Integer.MAX_VALUE.
     RegisterPositions usePositions = new RegisterPositionsImpl(registerConstraint + 1);
     RegisterPositions blockedPositions = new RegisterPositionsImpl(registerConstraint + 1);
@@ -2828,20 +2830,40 @@
               RegisterType.MONITOR);
     }
 
+    if (candidate == REGISTER_CANDIDATE_NOT_FOUND) {
+      if (toInstructionPosition(unhandledInterval.getFirstUse())
+          > toInstructionPosition(unhandledInterval.getStart())) {
+        // All active and inactive intervals are used before current. Therefore, it is best to spill
+        // current itself.
+        spillCurrentInterval(unhandledInterval);
+        return true;
+      }
+      LiveIntervalsUse firstUse = unhandledInterval.getUses().first();
+      LiveIntervalsUse nextStricterUse = null;
+      for (LiveIntervalsUse use : unhandledInterval.getUses()) {
+        if (use.getLimit() < firstUse.getLimit()) {
+          nextStricterUse = use;
+          break;
+        }
+      }
+      if (nextStricterUse != null
+          && toInstructionPosition(nextStricterUse.getPosition())
+              > toInstructionPosition(unhandledInterval.getStart())) {
+        LiveIntervals split = unhandledInterval.splitBefore(nextStricterUse.getPosition(), mode);
+        assert split != unhandledInterval;
+        unhandled.add(split);
+        return allocateSingleInterval(unhandledInterval);
+      }
+      return false;
+    }
+
     int largestUsePosition = getLargestPosition(usePositions, candidate, needsRegisterPair);
     int blockedPosition = getLargestPosition(blockedPositions, candidate, needsRegisterPair);
 
     if (largestUsePosition < unhandledInterval.getFirstUse()) {
       // All active and inactive intervals are used before current. Therefore, it is best to spill
       // current itself.
-      int splitPosition = unhandledInterval.getFirstUse();
-      LiveIntervals split = unhandledInterval.splitBefore(splitPosition, mode);
-      assert split != unhandledInterval;
-      // Experiments show that it has a positive impact on code size to use a fresh register here.
-      int registerNumber = getNewSpillRegister(unhandledInterval);
-      assignFreeRegisterToUnhandledInterval(unhandledInterval, registerNumber);
-      unhandledInterval.setSpilled(true);
-      unhandled.add(split);
+      spillCurrentInterval(unhandledInterval);
     } else {
       // We will use the candidate register(s) for unhandledInterval, and therefore potentially
       // need to adjust maxRegisterNumber.
@@ -2860,6 +2882,18 @@
         assignRegisterAndSpill(unhandledInterval, candidate);
       }
     }
+    return true;
+  }
+
+  private void spillCurrentInterval(LiveIntervals unhandledInterval) {
+    int splitPosition = unhandledInterval.getFirstUse();
+    LiveIntervals split = unhandledInterval.splitBefore(splitPosition, mode);
+    assert split != unhandledInterval;
+    // Experiments show that it has a positive impact on code size to use a fresh register here.
+    int registerNumber = getNewSpillRegister(unhandledInterval);
+    assignFreeRegisterToUnhandledInterval(unhandledInterval, registerNumber);
+    unhandledInterval.setSpilled(true);
+    unhandled.add(split);
   }
 
   private int getLargestPosition(

src/test/java8/ir/com/android/tools/r8/ir/regalloc/SpillIntervalWithMultipleDifferentConstrainedUsesTest.java

diff --git a/src/test/java8/ir/com/android/tools/r8/ir/regalloc/SpillIntervalWithMultipleDifferentConstrainedUsesTest.java b/src/test/java8/ir/com/android/tools/r8/ir/regalloc/SpillIntervalWithMultipleDifferentConstrainedUsesTest.java
index 28762e7..061ad5c 100644
--- a/src/test/java8/ir/com/android/tools/r8/ir/regalloc/SpillIntervalWithMultipleDifferentConstrainedUsesTest.java
+++ b/src/test/java8/ir/com/android/tools/r8/ir/regalloc/SpillIntervalWithMultipleDifferentConstrainedUsesTest.java
@@ -3,12 +3,10 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.regalloc;
 
-import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
-import com.android.tools.r8.utils.codeinspector.AssertUtils;
 import java.io.File;
 import java.io.IOException;
 import org.junit.Test;
@@ -17,6 +15,7 @@
 import org.junit.runners.Parameterized.Parameter;
 import org.junit.runners.Parameterized.Parameters;
 
+// Regression test for IndexOutOfBoundsException in debug mode: b/545349635.
 @RunWith(Parameterized.class)
 public class SpillIntervalWithMultipleDifferentConstrainedUsesTest extends TestBase {
 
@@ -30,9 +29,7 @@
 
   @Test
   public void testD8Debug() throws Exception {
-    AssertUtils.assertFailsCompilation(
-        () -> testForD8(parameters).addInnerClasses(getClass()).compile(),
-        e -> assertTrue(e.getCause() instanceof IndexOutOfBoundsException));
+    testForD8(parameters).addInnerClasses(getClass()).compile();
   }
 
   @Test