Version 1.6.52

Cherry-pick: Improve handling of register allocation for intervals
             same start.
CL: https://r8-review.googlesource.com/c/r8/+/45627

Bug: 142682636
Change-Id: Ib854a49cc1f849d660b3186d88c081f485616438
diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index e9ad7d9..004eb44 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.6.51";
+  public static final String LABEL = "1.6.52";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java b/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
index ec6710b..93fc650 100644
--- a/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
@@ -229,8 +229,7 @@
       // Find a free register that is not used by an inactive interval that overlaps with
       // unhandledInterval.
       if (tryHint(unhandledInterval)) {
-        assignRegisterToUnhandledInterval(
-            unhandledInterval, unhandledInterval.getHint().getRegister());
+        assignRegisterToUnhandledInterval(unhandledInterval, unhandledInterval.getHint());
       } else {
         boolean wide = unhandledInterval.getType().isWide();
         int register;
@@ -304,9 +303,9 @@
   private void updateHints(LiveIntervals intervals) {
     for (Phi phi : intervals.getValue().uniquePhiUsers()) {
       if (!phi.isValueOnStack()) {
-        phi.getLiveIntervals().setHint(intervals);
+        phi.getLiveIntervals().setHint(intervals, unhandled);
         for (Value value : phi.getOperands()) {
-          value.getLiveIntervals().setHint(intervals);
+          value.getLiveIntervals().setHint(intervals, unhandled);
         }
       }
     }
@@ -317,7 +316,7 @@
       return false;
     }
     boolean isWide = unhandled.getType().isWide();
-    int hintRegister = unhandled.getHint().getRegister();
+    int hintRegister = unhandled.getHint();
     if (freeRegisters.contains(hintRegister)
         && (!isWide || freeRegisters.contains(hintRegister + 1))) {
       for (LiveIntervals inactive : inactive) {
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 8456912..c30e9d1 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
@@ -1056,7 +1056,7 @@
       if (checkcastInput.getLiveIntervals() != null &&
           !checkcastInput.getLiveIntervals().overlaps(unhandledInterval) &&
           checkcastInput.getLocalInfo() == unhandledInterval.getValue().definition.getLocalInfo()) {
-        unhandledInterval.setHint(checkcastInput.getLiveIntervals());
+        unhandledInterval.setHint(checkcastInput.getLiveIntervals(), unhandled);
       }
     }
   }
@@ -1074,13 +1074,13 @@
       assert left != null;
       if (left.getLiveIntervals() != null &&
           !left.getLiveIntervals().overlaps(unhandledInterval)) {
-        unhandledInterval.setHint(left.getLiveIntervals());
+        unhandledInterval.setHint(left.getLiveIntervals(), unhandled);
       } else {
         Value right = binOp.rightValue();
         assert right != null;
         if (binOp.isCommutative() && right.getLiveIntervals() != null &&
             !right.getLiveIntervals().overlaps(unhandledInterval)) {
-          unhandledInterval.setHint(right.getLiveIntervals());
+          unhandledInterval.setHint(right.getLiveIntervals(), unhandled);
         }
       }
     }
@@ -1209,7 +1209,7 @@
       if (!value.isPhi() && value.definition.isMove()) {
         Move move = value.definition.asMove();
         LiveIntervals intervals = move.src().getLiveIntervals();
-        intervals.setHint(current);
+        intervals.setHint(current, unhandled);
       }
       if (current != unhandledInterval) {
         // Only the start of unhandledInterval has been reached at this point. All other live
@@ -1777,11 +1777,9 @@
     // spilling. For phis we also use the hint before looking at the operand registers. The
     // phi could have a hint from an argument moves which it seems more important to honor in
     // practice.
-    LiveIntervals hint = unhandledInterval.getHint();
+    Integer hint = unhandledInterval.getHint();
     if (hint != null) {
-      int register = hint.getRegister();
-      if (tryHint(unhandledInterval, registerConstraint, freePositions, needsRegisterPair,
-          register)) {
+      if (tryHint(unhandledInterval, registerConstraint, freePositions, needsRegisterPair, hint)) {
         return true;
       }
     }
@@ -1862,13 +1860,14 @@
     for (Phi phi : value.uniquePhiUsers()) {
       LiveIntervals phiIntervals = phi.getLiveIntervals();
       if (phiIntervals.getHint() == null) {
+        phiIntervals.setHint(intervals, unhandled);
         for (int i = 0; i < phi.getOperands().size(); i++) {
           Value operand = phi.getOperand(i);
           LiveIntervals operandIntervals = operand.getLiveIntervals();
           BasicBlock pred = phi.getBlock().getPredecessors().get(i);
           operandIntervals = operandIntervals.getSplitCovering(pred.exit().getNumber());
           if (operandIntervals.getHint() == null) {
-            operandIntervals.setHint(intervals);
+            operandIntervals.setHint(intervals, unhandled);
           }
         }
       }
@@ -1885,7 +1884,7 @@
         BasicBlock pred = block.getPredecessors().get(i);
         LiveIntervals operandIntervals =
             operand.getLiveIntervals().getSplitCovering(pred.exit().getNumber());
-        operandIntervals.setHint(intervals);
+        operandIntervals.setHint(intervals, unhandled);
       }
     }
   }
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 0251687..9cb4c09 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
@@ -17,6 +17,7 @@
 import java.util.Comparator;
 import java.util.Iterator;
 import java.util.List;
+import java.util.PriorityQueue;
 import java.util.TreeSet;
 import java.util.function.IntConsumer;
 
@@ -36,7 +37,7 @@
   private final TreeSet<LiveIntervalsUse> uses = new TreeSet<>();
   private int numberOfConsecutiveRegisters = -1;
   private int register = NO_REGISTER;
-  private LiveIntervals hint;
+  private Integer hint;
   private boolean spilled = false;
   private boolean usedInMonitorOperations = false;
 
@@ -82,11 +83,20 @@
     return getType().requiredRegisters();
   }
 
-  public void setHint(LiveIntervals intervals) {
-    hint = intervals;
+  public void setHint(LiveIntervals intervals, PriorityQueue<LiveIntervals> unhandled) {
+    // Do not set hints if they cannot be used anyway.
+    if (!overlaps(intervals)) {
+      // The hint is used in sorting the unhandled intervals. Therefore, if the hint changes
+      // we have to remove and reinsert the interval to get the sorting updated.
+      boolean removed = unhandled.remove(this);
+      hint = intervals.getRegister();
+      if (removed) {
+        unhandled.add(this);
+      }
+    }
   }
 
-  public LiveIntervals getHint() {
+  public Integer getHint() {
     return hint;
   }
 
@@ -537,8 +547,23 @@
 
   @Override
   public int compareTo(LiveIntervals other) {
+    // Sort by interval start instruction number.
     int startDiff = getStart() - other.getStart();
-    return startDiff != 0 ? startDiff : (value.getNumber() - other.value.getNumber());
+    if (startDiff != 0) return startDiff;
+    // Then sort by register number of hints to make sure that a phi
+    // does not take a low register that is the hint for another phi.
+    if (hint != null && other.hint != null) {
+      int registerDiff = hint - other.hint;
+      if (registerDiff != 0) return registerDiff;
+    }
+    // Intervals with hints go first so intervals without hints
+    // do not take registers from intervals with hints.
+    if (hint != null && other.hint == null) return -1;
+    if (hint == null && other.hint != null) return 1;
+    // Tie-breaker: no values have equal numbers.
+    int result = value.getNumber() - other.value.getNumber();
+    assert result != 0;
+    return result;
   }
 
   @Override
diff --git a/src/test/java/com/android/tools/r8/regress/b142682636/Regress142682636.java b/src/test/java/com/android/tools/r8/regress/b142682636/Regress142682636.java
new file mode 100644
index 0000000..2bef90c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/regress/b142682636/Regress142682636.java
@@ -0,0 +1,20 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.regress.b142682636;
+
+class Regress142682636 {
+  static void foo(long v, byte[] a, int s, int b) {
+    for (int i = s; i < s + b; i++) {
+      a[i] = (byte) v;
+      v = v >> 8;
+    }
+  }
+
+  static void bar(int s, long v, byte[] a, int b) {
+    for (int i = s; i < s + b; i++) {
+      a[i] = (byte) v;
+      v = v >> 8;
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/regress/b142682636/Regress142682636Runner.java b/src/test/java/com/android/tools/r8/regress/b142682636/Regress142682636Runner.java
new file mode 100644
index 0000000..c1a3d6c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/regress/b142682636/Regress142682636Runner.java
@@ -0,0 +1,40 @@
+package com.android.tools.r8.regress.b142682636;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.code.MoveWide;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import java.util.Arrays;
+import org.junit.Test;
+
+public class Regress142682636Runner extends TestBase {
+  private final Class<?> testClass = Regress142682636.class;
+
+  @Test
+  public void test() throws Exception {
+    CodeInspector inspector = testForD8()
+        .addProgramClasses(testClass)
+        .release()
+        .compile()
+        .inspector();
+    ClassSubject clazz = inspector.clazz(testClass);
+    assertThat(clazz, isPresent());
+    MethodSubject foo = clazz.uniqueMethodWithName("foo");
+    assertThat(foo, isPresent());
+    checkNoMoveWide(foo);
+    MethodSubject bar = clazz.uniqueMethodWithName("bar");
+    assertThat(bar, isPresent());
+    checkNoMoveWide(bar);
+  }
+
+  private void checkNoMoveWide(MethodSubject m) {
+    assertTrue(Arrays.stream(m.getMethod().getCode().asDexCode().instructions)
+        .noneMatch(i -> i instanceof MoveWide));
+  }
+
+}