Merge "Temporarily disable -adaptresourcefilecontents in gmscore tests"
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 df30c18..0976087 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
@@ -77,6 +77,7 @@
public static final int REGISTER_CANDIDATE_NOT_FOUND = -1;
public static final int MIN_CONSTANT_FREE_FOR_POSITIONS = 5;
+ public static final int EXCEPTION_INTERVALS_OVERLAP_CUTOFF = 500;
private enum ArgumentReuseMode {
ALLOW_ARGUMENT_REUSE,
@@ -1357,7 +1358,7 @@
// If there are that many move exception intervals we don't spent the time
// going through them all. In that case it is unlikely that we can reuse the move exception
// register in any case.
- if (moveExceptionIntervals.size() > 1000) {
+ if (moveExceptionIntervals.size() > EXCEPTION_INTERVALS_OVERLAP_CUTOFF) {
return true;
}
for (LiveIntervals moveExceptionInterval : moveExceptionIntervals) {
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 74600f4..c8e6e4c 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
@@ -11,7 +11,10 @@
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.code.ValueType;
import com.android.tools.r8.utils.CfgPrinter;
+import it.unimi.dsi.fastutil.ints.IntArrayList;
import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.TreeSet;
@@ -20,12 +23,15 @@
public class LiveIntervals implements Comparable<LiveIntervals> {
public static final int NO_REGISTER = Integer.MIN_VALUE;
+ public static final int CHILDREN_SORTING_CUTOFF = 100;
private final Value value;
private LiveIntervals nextConsecutive;
private LiveIntervals previousConsecutive;
private final LiveIntervals splitParent;
private final List<LiveIntervals> splitChildren = new ArrayList<>();
+ private final IntArrayList sortedSplitChildrenEnds = new IntArrayList();
+ private boolean sortedChildren = false;
private List<LiveRange> ranges = new ArrayList<>();
private final TreeSet<LiveIntervalsUse> uses = new TreeSet<>();
private int numberOfConsecutiveRegisters = -1;
@@ -189,6 +195,26 @@
return splitChildren.size() != 0;
}
+ private void sortSplitChildrenIfNeeded() {
+ if (!sortedChildren) {
+ splitChildren.sort(Comparator.comparingInt(LiveIntervals::getEnd));
+ sortedSplitChildrenEnds.clear();
+ for (LiveIntervals splitChild : splitChildren) {
+ sortedSplitChildrenEnds.add(splitChild.getEnd());
+ }
+ assert sortedChildrenConsistent();
+ sortedChildren = true;
+ }
+ }
+
+ private boolean sortedChildrenConsistent() {
+ for (int i = 0; i < splitChildren.size(); i++) {
+ assert splitChildren.get(i).getEnd() == sortedSplitChildrenEnds.getInt(i);
+ assert i == 0 || sortedSplitChildrenEnds.getInt(i - 1) <= sortedSplitChildrenEnds.getInt(i);
+ }
+ return true;
+ }
+
public List<LiveIntervals> getSplitChildren() {
return splitChildren;
}
@@ -404,6 +430,7 @@
start = toGapPosition(start);
LiveIntervals splitChild = new LiveIntervals(splitParent);
splitParent.splitChildren.add(splitChild);
+ splitParent.sortedChildren = false;
List<LiveRange> beforeSplit = new ArrayList<>();
List<LiveRange> afterSplit = new ArrayList<>();
if (start == getEnd()) {
@@ -460,7 +487,19 @@
// whose end is the instruction number. This is needed when transitioning values across
// control-flow boundaries.
LiveIntervals matchingEnd = getEnd() == instructionNumber ? this : null;
- for (LiveIntervals splitChild : splitChildren) {
+ // When there are many children, avoid looking at the ones for which the end is before
+ // the instruction number by doing a binary search for the first candidate whose end is after
+ // the instruction number.
+ int firstCandidate = 0;
+ if (splitChildren.size() > CHILDREN_SORTING_CUTOFF) {
+ sortSplitChildrenIfNeeded();
+ firstCandidate = Collections.binarySearch(sortedSplitChildrenEnds, instructionNumber);
+ if (firstCandidate < 0) {
+ firstCandidate = -(firstCandidate + 1);
+ }
+ }
+ for (int i = firstCandidate; i < splitChildren.size(); i++) {
+ LiveIntervals splitChild = splitChildren.get(i);
if (splitChild.getStart() <= instructionNumber && splitChild.getEnd() > instructionNumber) {
return splitChild;
}
