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;
       }