diff --git a/src/main/java/com/android/tools/r8/graph/DexCallSite.java b/src/main/java/com/android/tools/r8/graph/DexCallSite.java
index e690317..11bca5a 100644
--- a/src/main/java/com/android/tools/r8/graph/DexCallSite.java
+++ b/src/main/java/com/android/tools/r8/graph/DexCallSite.java
@@ -118,10 +118,14 @@
   public void collectIndexedItems(IndexedItemCollection indexedItems,
       DexMethod method, int instructionOffset) {
     assert method != null;
+    // Since collectIndexedItems() is called in transactions that may be rolled back, we may end up
+    // setting this.method and this.instructionOffset more than once. If we do set them more than
+    // once, then we must have the same values for method and instructionOffset every time.
+    assert this.method == null || this.method == method;
+    assert this.instructionOffset == 0 || this.instructionOffset == instructionOffset;
+    this.method = method;
+    this.instructionOffset = instructionOffset;
     if (indexedItems.addCallSite(this)) {
-      assert this.method == null;
-      this.method = method;
-      this.instructionOffset = instructionOffset;
       methodName.collectIndexedItems(indexedItems, method, instructionOffset);
       methodProto.collectIndexedItems(indexedItems, method, instructionOffset);
       bootstrapMethod.collectIndexedItems(indexedItems, method, instructionOffset);
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;
       }
diff --git a/third_party/gmscore/gmscore_v10.tar.gz.sha1 b/third_party/gmscore/gmscore_v10.tar.gz.sha1
index 15cab81..535f285 100644
--- a/third_party/gmscore/gmscore_v10.tar.gz.sha1
+++ b/third_party/gmscore/gmscore_v10.tar.gz.sha1
@@ -1 +1 @@
-43838ee1687ff48e866396dfd4b99415662fbea6
\ No newline at end of file
+fd2bc157ba2d61a19804107df47e0f87926b210d
\ No newline at end of file
diff --git a/third_party/gmscore/gmscore_v9.tar.gz.sha1 b/third_party/gmscore/gmscore_v9.tar.gz.sha1
index 5983b5b..0ff5779 100644
--- a/third_party/gmscore/gmscore_v9.tar.gz.sha1
+++ b/third_party/gmscore/gmscore_v9.tar.gz.sha1
@@ -1 +1 @@
-0066065faeb293c5a850d3319f2cb8a48d1e760d
\ No newline at end of file
+4bfdee0d2287b061164f984dfa4ad6ec8617effa
\ No newline at end of file
diff --git a/tools/upload_to_x20.py b/tools/upload_to_x20.py
index 08e48d9..1efacf5 100755
--- a/tools/upload_to_x20.py
+++ b/tools/upload_to_x20.py
@@ -39,7 +39,7 @@
   dest = os.path.join(GMSCORE_DEPS, sha1)
   print 'Uploading to %s' % dest
   shutil.copyfile(filename, dest)
-  os.chmod(dest, stat.S_IRWXU | stat.S_IROTH | stat.S_IXOTH | stat.S_IRWXG)
+  subprocess.check_call(['chmod', '664', dest])
   sha1_file = '%s.sha1' % filename
   with open(sha1_file, 'w') as output:
     output.write(sha1)