diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index ebfc337..84a48dd 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -2075,11 +2075,10 @@
       return;
     }
 
-    int color = code.reserveMarkingColor();
     ListIterator<BasicBlock> blockIterator = code.listIterator();
     while (blockIterator.hasNext()) {
       BasicBlock block = blockIterator.next();
-      if (block.isMarked(color)) {
+      if (block.getNumber() != 0 && block.getPredecessors().isEmpty()) {
         continue;
       }
       InstructionListIterator insnIterator = block.listIterator();
@@ -2096,19 +2095,13 @@
         }
 
         // Split the block.
-        BasicBlock newBlock = insnIterator.split(code, blockIterator);
-        assert !insnIterator.hasNext(); // must be pointing *after* inserted GoTo.
-        // Move block iterator back so current block is 'newBlock'.
-        blockIterator.previous();
+        {
+          BasicBlock newBlock = insnIterator.split(code, blockIterator);
+          assert !insnIterator.hasNext(); // must be pointing *after* inserted GoTo.
+          // Move block iterator back so current block is 'newBlock'.
+          blockIterator.previous();
 
-        // Unlink the next block representing all the instructions of the original
-        // block after the invocation which never returns normally. Mark all the
-        // removed blocks for deletion.
-        List<BasicBlock> removedBlocks = block.unlink(newBlock, new DominatorTree(code));
-        for (BasicBlock removedBlock : removedBlocks) {
-          if (!removedBlock.isMarked(color)) {
-            removedBlock.mark(color);
-          }
+          newBlock.unlinkSinglePredecessorSiblingsAllowed();
         }
 
         // We want to follow the invoke instruction with 'throw null', which should
@@ -2137,8 +2130,7 @@
         notReachableThrow.forceSetPosition(insn.getPosition());
       }
     }
-    code.removeMarkedBlocks(color);
-    code.returnMarkingColor(color);
+    code.removeUnreachableBlocks();
     assert code.isConsistentSSA();
   }
 
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 abc4730..1c0e761 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
@@ -140,6 +140,7 @@
   protected PriorityQueue<LiveIntervals> unhandled = new PriorityQueue<>();
 
   // List of intervals for the result of move-exception instructions.
+  // Always empty in mode ALLOW_ARGUMENT_REUSE.
   private List<LiveIntervals> moveExceptionIntervals = new ArrayList<>();
 
   // The first register used for parallel moves. After register allocation the parallel move
@@ -152,16 +153,17 @@
 
   // Whether or not the code has a move exception instruction. Used to pin the move exception
   // register.
-  private boolean hasDedicatedMoveExceptionRegister = false;
-
-  // We allocate a dedicated move exception register right after the arguments.
-  private int getMoveExceptionRegister() {
-    assert hasDedicatedMoveExceptionRegister;
-    return numberOfArgumentRegisters;
+  private boolean hasDedicatedMoveExceptionRegister() {
+    return !moveExceptionIntervals.isEmpty();
   }
 
-  private int getNextUnusedRegisterNumber() {
-    return maxRegisterNumber + 1;
+  // We allocate a dedicated move exception register right after the arguments.
+  // TODO(christofferqa): The move-exception instruction only requires its destination register to
+  // fit in 8 bits. In some situations, it might be better to use a register which is >= 16 if we
+  // end up using that many registers.
+  private int getMoveExceptionRegister() {
+    assert hasDedicatedMoveExceptionRegister();
+    return numberOfArgumentRegisters;
   }
 
   public LinearScanRegisterAllocator(IRCode code, InternalOptions options) {
@@ -740,6 +742,8 @@
       } else {
         // Treat the argument interval as spilled which will require a load to a different
         // register for all register-constrained usages.
+        inactive.add(argumentInterval);
+        // Split argument live interval at its first constrained use.
         if (argumentInterval.getUses().size() > 1) {
           LiveIntervalsUse use = argumentInterval.firstUseWithConstraint();
           if (use != null) {
@@ -751,12 +755,17 @@
             } else {
               // If there are multiple register-constrained users, split right after the definition
               // to make it more likely that arguments get in usable registers from the start.
+              // TODO(christofferqa): This is not great if there are many arguments with multiple
+              // constrained uses, since we fill up all the low registers immediately, making it
+              // likely that we will have to kick them back out before they are actually used.
               split = argumentInterval
                   .splitBefore(argumentInterval.getValue().definition.getNumber() + 1);
             }
             unhandled.add(split);
           }
         }
+        // Since we are not activating the argument live intervals, we need to free their registers.
+        freeOccupiedRegistersForIntervals(argumentInterval);
       }
       argumentValue = argumentValue.getNextConsecutive();
     }
@@ -769,40 +778,33 @@
     // When we allow argument reuse we do not allow any splitting, therefore we cannot get into
     // trouble with move exception registers. When argument reuse is disallowed we block a fixed
     // register to be used only by move exception instructions.
-    if (mode != ArgumentReuseMode.ALLOW_ARGUMENT_REUSE) {
+    if (mode == ArgumentReuseMode.DISALLOW_ARGUMENT_REUSE) {
       // Force all move exception ranges to start out with the exception in a fixed register. Split
       // their live ranges which will force another register if used.
-      int moveExceptionRegister = NO_REGISTER;
       boolean overlappingMoveExceptionIntervals = false;
       for (BasicBlock block : code.blocks) {
-        for (Instruction instruction : block.getInstructions()) {
-          if (instruction.isMoveException()) {
-            hasDedicatedMoveExceptionRegister = true;
-            Value exceptionValue = instruction.outValue();
-            LiveIntervals intervals = exceptionValue.getLiveIntervals();
-            unhandled.remove(intervals);
-            moveExceptionIntervals.add(intervals);
-            if (moveExceptionRegister == NO_REGISTER) {
-              moveExceptionRegister = getFreeConsecutiveRegisters(1);
-              assert moveExceptionRegister == getMoveExceptionRegister();
-              assert !freeRegisters.contains(moveExceptionRegister);
-            }
-            intervals.setRegister(moveExceptionRegister);
-            if (!overlappingMoveExceptionIntervals) {
-              for (LiveIntervals other : moveExceptionIntervals) {
-                overlappingMoveExceptionIntervals |= other.overlaps(intervals);
-              }
+        Instruction instruction = block.entry();
+        if (instruction.isMoveException()) {
+          LiveIntervals intervals = instruction.outValue().getLiveIntervals();
+          unhandled.remove(intervals);
+          moveExceptionIntervals.add(intervals);
+          intervals.setRegister(getMoveExceptionRegister());
+          if (!overlappingMoveExceptionIntervals) {
+            for (LiveIntervals other : moveExceptionIntervals) {
+              overlappingMoveExceptionIntervals |= other.overlaps(intervals);
             }
           }
         }
       }
+      if (hasDedicatedMoveExceptionRegister()) {
+        int moveExceptionRegister = getMoveExceptionRegister();
+        assert moveExceptionRegister == maxRegisterNumber + 1;
+        increaseCapacity(moveExceptionRegister, true);
+      }
       if (overlappingMoveExceptionIntervals) {
         for (LiveIntervals intervals : moveExceptionIntervals) {
           if (intervals.getUses().size() > 1) {
-            LiveIntervalsUse firstUse = intervals.getUses().pollFirst();
-            LiveIntervalsUse secondUse = intervals.getUses().pollFirst();
-            intervals.getUses().add(firstUse);
-            intervals.getUses().add(secondUse);
+            LiveIntervalsUse secondUse = intervals.getUses().stream().skip(1).findFirst().get();
             LiveIntervals split = intervals.splitBefore(secondUse.getPosition());
             unhandled.add(split);
           }
@@ -812,6 +814,8 @@
 
     // Go through each unhandled live interval and find a register for it.
     while (!unhandled.isEmpty()) {
+      assert invariantsHold(mode);
+
       LiveIntervals unhandledInterval = unhandled.poll();
 
       setHintForDestRegOfCheckCast(unhandledInterval);
@@ -820,9 +824,9 @@
       // If this interval value is the src of an argument move. Fix the registers for the
       // consecutive arguments now and add hints to the move sources. This looks forward
       // and propagate hints backwards to avoid many moves in connection with ranged invokes.
-      allocateArgumentIntervalsWithSrc(unhandledInterval);
+      allocateArgumentIntervalsWithSrc(unhandledInterval, mode);
       if (unhandledInterval.getRegister() != NO_REGISTER) {
-        // The value itself could be in the chain that has now gotten registers allocated.
+        // The value itself is in the chain that has now gotten registers allocated.
         continue;
       }
 
@@ -833,12 +837,12 @@
         LiveIntervals activeIntervals = activeIterator.next();
         if (start >= activeIntervals.getEnd()) {
           activeIterator.remove();
-          freeRegistersForIntervals(activeIntervals);
+          freeOccupiedRegistersForIntervals(activeIntervals);
         } else if (!activeIntervals.overlapsPosition(start)) {
           activeIterator.remove();
           assert activeIntervals.getRegister() != NO_REGISTER;
           inactive.add(activeIntervals);
-          freeRegistersForIntervals(activeIntervals);
+          freeOccupiedRegistersForIntervals(activeIntervals);
         }
       }
 
@@ -852,13 +856,13 @@
           inactiveIterator.remove();
           assert inactiveIntervals.getRegister() != NO_REGISTER;
           active.add(inactiveIntervals);
-          takeRegistersForIntervals(inactiveIntervals);
+          takeFreeRegistersForIntervals(inactiveIntervals);
         }
       }
 
       // Perform the actual allocation.
       if (unhandledInterval.isLinked() && !unhandledInterval.isArgumentInterval()) {
-        allocateLinkedIntervals(unhandledInterval);
+        allocateLinkedIntervals(unhandledInterval, false);
       } else {
         if (!allocateSingleInterval(unhandledInterval, mode)) {
           return false;
@@ -868,6 +872,76 @@
     return true;
   }
 
+  private boolean invariantsHold(ArgumentReuseMode mode) {
+    TreeSet<Integer> computedFreeRegisters = new TreeSet<>();
+    for (int register = 0; register <= maxRegisterNumber; ++register) {
+      computedFreeRegisters.add(register);
+    }
+    for (LiveIntervals activeIntervals : active) {
+      assert registersForIntervalsAreTaken(activeIntervals);
+      activeIntervals.forEachRegister(
+          register -> {
+            assert computedFreeRegisters.contains(register);
+            computedFreeRegisters.remove(register);
+          });
+    }
+    if (mode == ArgumentReuseMode.DISALLOW_ARGUMENT_REUSE) {
+      // Each time an argument interval is active, we currently require that it is present in its
+      // original, incoming argument register.
+      for (LiveIntervals activeIntervals : active) {
+        if (activeIntervals.isArgumentInterval()
+            && activeIntervals != activeIntervals.getSplitParent()) {
+          LiveIntervals parent = activeIntervals.getSplitParent();
+          if (parent.getRegister() != activeIntervals.getRegister()) {
+            activeIntervals
+                .getSplitParent()
+                .forEachRegister(
+                    register -> {
+                      assert computedFreeRegisters.contains(register);
+                      computedFreeRegisters.remove(register);
+                    });
+          }
+        }
+      }
+    }
+    if (hasDedicatedMoveExceptionRegister()) {
+      // Relax the check, since it is not currently guaranteed that the move exception register is
+      // occupied if-and-only-if there is an active live interval with the register.
+      freeRegisters.remove(getMoveExceptionRegister());
+      computedFreeRegisters.remove(getMoveExceptionRegister());
+    }
+    assert freeRegisters.equals(computedFreeRegisters);
+    return true;
+  }
+
+  private boolean freePositionsAreConsistentWithFreeRegisters(
+      RegisterPositions freePositions, int registerConstraint) {
+    int n = Math.min(maxRegisterNumber, registerConstraint);
+    for (int register = 0; register <= n; ++register) {
+      if (freePositions.get(register) > 0) {
+        // If this register is free according to freePositions, then it should also be free
+        // according to freeRegisters.
+        boolean isMoveExceptionRegister =
+            hasDedicatedMoveExceptionRegister() && register == getMoveExceptionRegister();
+        if (!isMoveExceptionRegister) {
+          assert freeRegisters.contains(register);
+        }
+      }
+    }
+    return true;
+  }
+
+  private boolean registerAssignmentNotConflictingWithArgument(LiveIntervals interval) {
+    assert interval.getRegister() != NO_REGISTER;
+    for (Value argumentValue = firstArgumentValue;
+        argumentValue != null;
+        argumentValue = argumentValue.getNextConsecutive()) {
+      assert !interval.hasConflictingRegisters(argumentValue.getLiveIntervals())
+          || !argumentValue.getLiveIntervals().anySplitOverlaps(interval);
+    }
+    return true;
+  }
+
   private void setHintForDestRegOfCheckCast(LiveIntervals unhandledInterval) {
     if (unhandledInterval.getHint() == null &&
         unhandledInterval.getValue().definition instanceof CheckCast) {
@@ -915,7 +989,7 @@
    * allocated and have been moved from unhandled to inactive. The move sources have their hints
    * updated. The rest of the register allocation state is unchanged.
    */
-  private void allocateArgumentIntervalsWithSrc(LiveIntervals srcInterval) {
+  private void allocateArgumentIntervalsWithSrc(LiveIntervals srcInterval, ArgumentReuseMode mode) {
     Value value = srcInterval.getValue();
     for (Instruction instruction : value.uniqueUsers()) {
       // If there is a move user that is an argument move, we allocate the consecutive
@@ -928,8 +1002,7 @@
         if (destIntervals.getRegister() == NO_REGISTER) {
           // Save the current register allocation state so we can restore it at the end.
           TreeSet<Integer> savedFreeRegisters = new TreeSet<>(freeRegisters);
-          int savedUnusedRegisterNumber = getNextUnusedRegisterNumber();
-          List<LiveIntervals> savedActive = new LinkedList<>(active);
+          int savedMaxRegisterNumber = maxRegisterNumber;
           List<LiveIntervals> savedInactive = new LinkedList<>(inactive);
 
           // Add all the active intervals to the inactive set. When allocating linked intervals we
@@ -944,23 +1017,35 @@
             // registers works the best for code size.
             if (active.isArgumentInterval()) {
               // Allow the ranged invoke to use argument registers if free. This improves register
-              // allocation for brigde methods that forwards all of their arguments after check-cast
+              // allocation for bridge methods that forwards all of their arguments after check-cast
               // checks on their types.
-              freeRegistersForIntervals(active);
+              freeOccupiedRegistersForIntervals(active);
             }
             inactive.add(active);
           }
 
           // Allocate the argument intervals.
           unhandled.remove(destIntervals);
-          allocateLinkedIntervals(destIntervals);
+          boolean excludeUnhandledOverlappingArgumentIntervals = false;
+          if (mode == ArgumentReuseMode.DISALLOW_ARGUMENT_REUSE) {
+            // Since we are going to do a look-ahead, there may be argument live interval splits,
+            // which are currently unhandled, but would be inactive at the invoke-range instruction.
+            // Thus, the implementation of allocateLinkedIntervals needs to exclude the argument
+            // registers for which there exists a split that overlaps with one of the inputs to the
+            // invoke-range instruction. We handle this situation by setting the following flag.
+            excludeUnhandledOverlappingArgumentIntervals = true;
+          }
+          unhandled.add(srcInterval);
+          allocateLinkedIntervals(destIntervals, excludeUnhandledOverlappingArgumentIntervals);
+          active.remove(destIntervals);
+          unhandled.remove(srcInterval);
           // Restore the register allocation state.
           freeRegisters = savedFreeRegisters;
           // In case maxRegisterNumber has changed, update freeRegisters.
-          for (int i = savedUnusedRegisterNumber, j = getNextUnusedRegisterNumber(); i < j; i++) {
+          for (int i = savedMaxRegisterNumber + 1; i <= maxRegisterNumber; i++) {
             freeRegisters.add(i);
           }
-          active = savedActive;
+
           inactive = savedInactive;
           // Move all the argument intervals to the inactive set.
           LiveIntervals current = destIntervals.getStartOfConsecutive();
@@ -976,35 +1061,43 @@
     }
   }
 
-  private void allocateLinkedIntervals(LiveIntervals unhandledInterval) {
+  private void allocateLinkedIntervals(
+      LiveIntervals unhandledInterval, boolean excludeUnhandledOverlappingArgumentIntervals) {
+    LiveIntervals start = unhandledInterval.getStartOfConsecutive();
+
     // Exclude the registers that overlap the start of one of the live ranges we are
     // going to assign registers to now.
-    LiveIntervals current = unhandledInterval.getStartOfConsecutive();
-    Set<Integer> excludedRegisters = new HashSet<>();
-    while (current != null) {
+    IntSet excludedRegisters = new IntArraySet();
+    for (LiveIntervals current = start; current != null; current = current.getNextConsecutive()) {
       for (LiveIntervals inactiveIntervals : inactive) {
         if (inactiveIntervals.overlaps(current)) {
           excludeRegistersForInterval(inactiveIntervals, excludedRegisters);
         }
       }
-      current = current.getNextConsecutive();
     }
-    current = unhandledInterval.getStartOfConsecutive();
+    if (excludeUnhandledOverlappingArgumentIntervals && firstArgumentValue != null) {
+      // Exclude the argument registers for which there exists a split that overlaps with one of
+      // the inputs to the invoke-range instruction.
+      for (LiveIntervals intervals = firstArgumentValue.getLiveIntervals();
+          intervals != null;
+          intervals = intervals.getNextConsecutive()) {
+        if (liveIntervalsHasUnhandledSplitOverlappingAnyOf(intervals, start)) {
+          excludeRegistersForInterval(intervals, excludedRegisters);
+        }
+      }
+    }
     // Exclude move exception register if the first interval overlaps a move exception interval.
-    if (overlapsMoveExceptionInterval(current) &&
-        freeRegisters.remove(getMoveExceptionRegister())) {
+    // It is not necessary to check the remaining consecutive intervals, since we always use
+    // register 0 (after remapping) for the argument register.
+    if (overlapsMoveExceptionInterval(start) && freeRegisters.remove(getMoveExceptionRegister())) {
       excludedRegisters.add(getMoveExceptionRegister());
     }
     // Select registers.
-    int numberOfRegister = current.numberOfConsecutiveRegisters();
-    int firstRegister = getFreeConsecutiveRegisters(numberOfRegister);
-    for (int i = 0; i < numberOfRegister; i++) {
-      assert current != null;
-      current.setRegister(firstRegister + i);
-      if (current.getType().isWide()) {
-        assert i < numberOfRegister;
-        i++;
-      }
+    int numberOfRegisters = start.numberOfConsecutiveRegisters();
+    int nextRegister = getFreeConsecutiveRegisters(numberOfRegisters);
+    for (LiveIntervals current = start; current != null; current = current.getNextConsecutive()) {
+      current.setRegister(nextRegister);
+      assert registerAssignmentNotConflictingWithArgument(current);
       // Propagate hints to the move sources.
       Value value = current.getValue();
       if (!value.isPhi() && value.definition.isMove()) {
@@ -1017,32 +1110,43 @@
         // intervals in the chain have been assigned registers but their start has not yet been
         // reached. Therefore, they belong in the inactive set.
         unhandled.remove(current);
-        assert current.getRegister() != NO_REGISTER;
         inactive.add(current);
-        freeRegistersForIntervals(current);
       }
-      current = current.getNextConsecutive();
+      nextRegister += current.requiredRegisters();
     }
-    assert current == null;
+
     assert unhandledInterval.getRegister() != NO_REGISTER;
+    takeFreeRegistersForIntervals(unhandledInterval);
     active.add(unhandledInterval);
     // Include the registers for inactive ranges that we had to exclude for this allocation.
     freeRegisters.addAll(excludedRegisters);
   }
 
-  // Update the information about used registers when |register| has been selected for use.
-  private void updateRegisterState(int register, boolean needsRegisterPair) {
-    int maxRegister = register + (needsRegisterPair ? 1 : 0);
-    maxRegisterNumber = Math.max(maxRegisterNumber, maxRegister);
+  // Returns true if intervals has an unhandled split, which overlaps with chain or any of its
+  // consecutives.
+  private boolean liveIntervalsHasUnhandledSplitOverlappingAnyOf(
+      LiveIntervals intervals, LiveIntervals chain) {
+    assert intervals == intervals.getSplitParent();
+    assert chain == chain.getStartOfConsecutive();
+    for (LiveIntervals split : intervals.getSplitChildren()) {
+      if (unhandled.contains(split)) {
+        for (LiveIntervals current = chain;
+            current != null;
+            current = current.getNextConsecutive()) {
+          if (split.overlaps(current)) {
+            return true;
+          }
+        }
+      }
+    }
+    return false;
   }
 
   private int getSpillRegister(LiveIntervals intervals) {
-    int registerNumber = getNextUnusedRegisterNumber();
-    maxRegisterNumber = registerNumber;
-    if (intervals.getType().isWide()) {
-      maxRegisterNumber++;
-    }
-    return registerNumber;
+    int register = maxRegisterNumber + 1;
+    increaseCapacity(maxRegisterNumber + intervals.requiredRegisters());
+    assert registersAreFree(register, intervals.getType().isWide());
+    return register;
   }
 
   private int toInstructionPosition(int position) {
@@ -1232,7 +1336,7 @@
   //   invoke method r4
   //   return
   private boolean overlapsMoveExceptionInterval(LiveIntervals intervals) {
-    if (!hasDedicatedMoveExceptionRegister) {
+    if (!hasDedicatedMoveExceptionRegister()) {
       return false;
     }
     for (LiveIntervals moveExceptionInterval : moveExceptionIntervals) {
@@ -1254,7 +1358,7 @@
     // avoid move generation for the argument.
     if (registerConstraint == Constants.U16BIT_MAX && unhandledInterval.isArgumentInterval()) {
       int argumentRegister = unhandledInterval.getSplitParent().getRegister();
-      assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, argumentRegister);
+      assignFreeRegisterToUnhandledInterval(unhandledInterval, argumentRegister);
       return true;
     }
 
@@ -1333,6 +1437,8 @@
       }
     }
 
+    assert freePositionsAreConsistentWithFreeRegisters(freePositions, registerConstraint);
+
     // Attempt to use register hints.
     if (useRegisterHint(unhandledInterval, registerConstraint, freePositions, needsRegisterPair)) {
       return true;
@@ -1376,26 +1482,35 @@
           register = getSpillRegister(unhandledInterval);
         }
         LiveIntervals split = unhandledInterval.splitBefore(nextConstrainedPosition);
-        assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, register);
+        assignFreeRegisterToUnhandledInterval(unhandledInterval, register);
         unhandled.add(split);
       } else {
         allocateBlockedRegister(unhandledInterval);
       }
-    } else if (largestFreePosition >= unhandledInterval.getEnd()) {
-      // Free for the entire interval. Allocate the register.
-      assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, candidate);
     } else {
-      if (mode == ArgumentReuseMode.ALLOW_ARGUMENT_REUSE) {
-        // No splitting is allowed when we allow argument reuse. Bailout and start over with
-        // argument reuse disallowed.
-        return false;
+      // We will use the candidate register(s) for unhandledInterval, and therefore potentially
+      // need to adjust maxRegisterNumber.
+      int candidateEnd = candidate + unhandledInterval.requiredRegisters() - 1;
+      if (candidateEnd > maxRegisterNumber) {
+        increaseCapacity(candidateEnd);
       }
-      // The candidate is free for the beginning of an interval. We split the interval
-      // and use the register for as long as we can.
-      LiveIntervals split = unhandledInterval.splitBefore(largestFreePosition);
-      assert split != unhandledInterval;
-      assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, candidate);
-      unhandled.add(split);
+
+      if (largestFreePosition >= unhandledInterval.getEnd()) {
+        // Free for the entire interval. Allocate the register.
+        assignFreeRegisterToUnhandledInterval(unhandledInterval, candidate);
+      } else {
+        if (mode == ArgumentReuseMode.ALLOW_ARGUMENT_REUSE) {
+          // No splitting is allowed when we allow argument reuse. Bailout and start over with
+          // argument reuse disallowed.
+          return false;
+        }
+        // The candidate is free for the beginning of an interval. We split the interval
+        // and use the register for as long as we can.
+        LiveIntervals split = unhandledInterval.splitBefore(largestFreePosition);
+        assert split != unhandledInterval;
+        assignFreeRegisterToUnhandledInterval(unhandledInterval, candidate);
+        unhandled.add(split);
+      }
     }
     return true;
   }
@@ -1473,7 +1588,7 @@
             isArrayGetArrayRegister(unhandledInterval, register)) {
           return false;
         }
-        assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, register);
+        assignFreeRegisterToUnhandledInterval(unhandledInterval, register);
         return true;
       }
     }
@@ -1481,6 +1596,7 @@
   }
 
   private void assignRegister(LiveIntervals intervals, int register) {
+    assert register + intervals.requiredRegisters() - 1 <= maxRegisterNumber;
     intervals.setRegister(register);
     updateRegisterHints(intervals);
   }
@@ -1520,11 +1636,10 @@
     }
   }
 
-  private void assignRegisterToUnhandledInterval(
-      LiveIntervals unhandledInterval, boolean needsRegisterPair, int register) {
+  private void assignFreeRegisterToUnhandledInterval(
+      LiveIntervals unhandledInterval, int register) {
     assignRegister(unhandledInterval, register);
-    takeRegistersForIntervals(unhandledInterval);
-    updateRegisterState(register, needsRegisterPair);
+    takeFreeRegistersForIntervals(unhandledInterval);
     active.add(unhandledInterval);
   }
 
@@ -1665,7 +1780,7 @@
         blockedPositions);
 
     // Get the register (pair) that has the highest use position.
-    boolean needsRegisterPair = unhandledInterval.requiredRegisters() == 2;
+    boolean needsRegisterPair = unhandledInterval.getType().isWide();
 
     // First look for a candidate that can be rematerialized.
     int candidate = getLargestValidCandidate(unhandledInterval, registerConstraint,
@@ -1705,17 +1820,26 @@
       LiveIntervals split = unhandledInterval.splitBefore(splitPosition);
       assert split != unhandledInterval;
       int registerNumber = getSpillRegister(unhandledInterval);
-      assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, registerNumber);
+      assignFreeRegisterToUnhandledInterval(unhandledInterval, registerNumber);
       unhandledInterval.setSpilled(true);
       unhandled.add(split);
-    } else if (blockedPosition > unhandledInterval.getEnd()) {
-      // Spilling can make a register available for the entire interval.
-      assignRegisterAndSpill(unhandledInterval, needsRegisterPair, candidate);
     } else {
-      // Spilling only makes a register available for the first part of current.
-      LiveIntervals splitChild = unhandledInterval.splitBefore(blockedPosition);
-      unhandled.add(splitChild);
-      assignRegisterAndSpill(unhandledInterval, needsRegisterPair, candidate);
+      // We will use the candidate register(s) for unhandledInterval, and therefore potentially
+      // need to adjust maxRegisterNumber.
+      int candidateEnd = candidate + unhandledInterval.requiredRegisters() - 1;
+      if (candidateEnd > maxRegisterNumber) {
+        increaseCapacity(candidateEnd);
+      }
+
+      if (blockedPosition > unhandledInterval.getEnd()) {
+        // Spilling can make a register available for the entire interval.
+        assignRegisterAndSpill(unhandledInterval, candidate, needsRegisterPair);
+      } else {
+        // Spilling only makes a register available for the first part of current.
+        LiveIntervals splitChild = unhandledInterval.splitBefore(blockedPosition);
+        unhandled.add(splitChild);
+        assignRegisterAndSpill(unhandledInterval, candidate, needsRegisterPair);
+      }
     }
   }
 
@@ -1729,29 +1853,25 @@
   }
 
   private void assignRegisterAndSpill(
-      LiveIntervals unhandledInterval,
-      boolean needsRegisterPair,
-      int candidate) {
-    assignRegister(unhandledInterval, candidate);
-    updateRegisterState(candidate, needsRegisterPair);
+      LiveIntervals unhandledInterval, int candidate, boolean candidateIsWide) {
     // Split and spill intersecting active intervals for this register.
-    spillOverlappingActiveIntervals(unhandledInterval, needsRegisterPair, candidate);
-    takeRegistersForIntervals(unhandledInterval);
+    spillOverlappingActiveIntervals(unhandledInterval, candidate, candidateIsWide);
+    // Now that that active intervals have been spilled, we are free to take the candidate.
+    assignRegister(unhandledInterval, candidate);
+    takeFreeRegistersForIntervals(unhandledInterval);
     active.add(unhandledInterval);
     // Split all overlapping inactive intervals for this register. They need to have a new
     // register assigned at the next use.
-    splitOverlappingInactiveIntervals(unhandledInterval, needsRegisterPair, candidate);
+    splitOverlappingInactiveIntervals(unhandledInterval, candidate, candidateIsWide);
   }
 
   protected void splitOverlappingInactiveIntervals(
-      LiveIntervals unhandledInterval,
-      boolean needsRegisterPair,
-      int candidate) {
+      LiveIntervals unhandledInterval, int candidate, boolean candidateIsWide) {
     List<LiveIntervals> newInactive = new ArrayList<>();
     Iterator<LiveIntervals> inactiveIterator = inactive.iterator();
     while (inactiveIterator.hasNext()) {
       LiveIntervals intervals = inactiveIterator.next();
-      if (intervals.usesRegister(candidate, needsRegisterPair)
+      if (intervals.usesRegister(candidate, candidateIsWide)
           && intervals.overlaps(unhandledInterval)) {
         if (intervals.isLinked() && !intervals.isArgumentInterval()) {
           // If the inactive register is linked but not an argument, it needs to get the
@@ -1783,21 +1903,26 @@
   }
 
   private void spillOverlappingActiveIntervals(
-      LiveIntervals unhandledInterval,
-      boolean needsRegisterPair,
-      int candidate) {
+      LiveIntervals unhandledInterval, int candidate, boolean candidateIsWide) {
+    assert unhandledInterval.getRegister() == NO_REGISTER;
+    assert atLeastOneOfRegistersAreTaken(candidate, candidateIsWide);
+    // Spill overlapping active intervals.
     List<LiveIntervals> newActive = new ArrayList<>();
     Iterator<LiveIntervals> activeIterator = active.iterator();
     while (activeIterator.hasNext()) {
       LiveIntervals intervals = activeIterator.next();
-      if (intervals.usesRegister(candidate, needsRegisterPair)) {
+      assert registersForIntervalsAreTaken(intervals);
+      if (intervals.usesRegister(candidate, candidateIsWide)) {
         activeIterator.remove();
-        freeRegistersForIntervals(intervals);
-        LiveIntervals splitChild = intervals.splitBefore(unhandledInterval.getStart());
         int registerNumber = getSpillRegister(intervals);
+        // Important not to free the registers for intervals before finding a spill register,
+        // because we might otherwise end up spilling to the current registers of intervals,
+        // depending on getSpillRegister.
+        freeOccupiedRegistersForIntervals(intervals);
+        LiveIntervals splitChild = intervals.splitBefore(unhandledInterval.getStart());
         assignRegister(splitChild, registerNumber);
         splitChild.setSpilled(true);
-        takeRegistersForIntervals(splitChild);
+        takeFreeRegistersForIntervals(splitChild);
         assert splitChild.getRegister() != NO_REGISTER;
         assert intervals.getRegister() != NO_REGISTER;
         newActive.add(splitChild);
@@ -1827,6 +1952,7 @@
       }
     }
     active.addAll(newActive);
+    assert registersAreFree(candidate, candidateIsWide);
   }
 
   private void splitRangesForSpilledArgument(LiveIntervals spilled) {
@@ -1847,7 +1973,9 @@
     assert spilled.isSpilled();
     assert !spilled.getValue().isConstNumber();
     assert !spilled.isLinked() || spilled.isArgumentInterval();
-    if (spilled.isArgumentInterval()) {
+    boolean isSpillingToArgumentRegister =
+        (spilled.isArgumentInterval() || registerNumber < numberOfArgumentRegisters);
+    if (isSpillingToArgumentRegister) {
       registerNumber = Constants.U16BIT_MAX;
     }
     LiveIntervalsUse firstUseWithLowerLimit = null;
@@ -2325,22 +2453,33 @@
   private void pinArgumentRegisters() {
     // Special handling for arguments. Pin their register.
     if (firstArgumentValue != null) {
+      increaseCapacity(numberOfArgumentRegisters - 1, true);
       int register = 0;
-      Value current = firstArgumentValue;
-      while (current != null) {
+      for (Value current = firstArgumentValue;
+          current != null;
+          current = current.getNextConsecutive()) {
         LiveIntervals argumentLiveInterval = current.getLiveIntervals();
-        // Pin the argument register. We use getFreeConsecutiveRegisters to make sure that we update
-        // the max register number.
-        register = getFreeConsecutiveRegisters(argumentLiveInterval.requiredRegisters());
         assignRegister(argumentLiveInterval, register);
-        current = current.getNextConsecutive();
+        register += current.requiredRegisters();
       }
-      // If the last argument is wide, then its register will be numberOfArgumentRegisters - 2.
-      assert register == numberOfArgumentRegisters - 1 || register == numberOfArgumentRegisters - 2;
     }
   }
 
+  private void increaseCapacity(int newMaxRegisterNumber) {
+    increaseCapacity(newMaxRegisterNumber, false);
+  }
+
+  private void increaseCapacity(int newMaxRegisterNumber, boolean takeRegisters) {
+    if (!takeRegisters) {
+      for (int register = maxRegisterNumber + 1; register <= newMaxRegisterNumber; ++register) {
+        freeRegisters.add(register);
+      }
+    }
+    maxRegisterNumber = newMaxRegisterNumber;
+  }
+
   private int getFreeConsecutiveRegisters(int numberOfRegisters) {
+    int oldMaxRegisterNumber = maxRegisterNumber;
     Iterator<Integer> freeRegistersIterator = freeRegisters.iterator();
     int first = getNextFreeRegister(freeRegistersIterator);
     int current = first;
@@ -2357,8 +2496,9 @@
         current++;
       }
     }
-    for (int register = first; register < first + numberOfRegisters; ++register) {
-      freeRegisters.remove(register);
+    for (int register = oldMaxRegisterNumber + 1; register <= maxRegisterNumber; ++register) {
+      boolean wasAdded = freeRegisters.add(register);
+      assert wasAdded;
     }
     // Either all the consecutive registers are from the argument registers, or all are from the
     // non-argument registers.
@@ -2373,35 +2513,87 @@
     if (freeRegistersIterator.hasNext()) {
       return freeRegistersIterator.next();
     }
-    maxRegisterNumber = getNextUnusedRegisterNumber();
-    return maxRegisterNumber;
+    return ++maxRegisterNumber;
   }
 
-  private void excludeRegistersForInterval(LiveIntervals intervals, Set<Integer> excluded) {
+  private void excludeRegistersForInterval(LiveIntervals intervals, IntSet excluded) {
     int register = intervals.getRegister();
+    assert register != NO_REGISTER;
+
     for (int i = 0; i < intervals.requiredRegisters(); i++) {
       if (freeRegisters.remove(register + i)) {
         excluded.add(register + i);
       }
     }
+
+    if (intervals.isArgumentInterval() && intervals != intervals.getSplitParent()) {
+      LiveIntervals parent = intervals.getSplitParent();
+      if (parent.getRegister() != register) {
+        excludeRegistersForInterval(parent, excluded);
+      }
+    }
   }
 
-  private void freeRegistersForIntervals(LiveIntervals intervals) {
+  private void freeOccupiedRegistersForIntervals(LiveIntervals intervals) {
+    assert registersForIntervalsAreTaken(intervals);
     int register = intervals.getRegister();
+    assert register + intervals.requiredRegisters() - 1 <= maxRegisterNumber;
     freeRegisters.add(register);
     if (intervals.getType().isWide()) {
       freeRegisters.add(register + 1);
     }
+
+    if (intervals.isArgumentInterval() && intervals != intervals.getSplitParent()) {
+      LiveIntervals parent = intervals.getSplitParent();
+      if (parent.getRegister() != intervals.getRegister()) {
+        freeOccupiedRegistersForIntervals(intervals.getSplitParent());
+      }
+    }
   }
 
-  private void takeRegistersForIntervals(LiveIntervals intervals) {
-    int register = intervals.getRegister();
+  private void takeFreeRegisters(int register, boolean isWide) {
+    assert registersAreFree(register, isWide);
     freeRegisters.remove(register);
-    if (intervals.getType().isWide()) {
+    if (isWide) {
       freeRegisters.remove(register + 1);
     }
   }
 
+  private void takeFreeRegistersForIntervals(LiveIntervals intervals) {
+    takeFreeRegisters(intervals.getRegister(), intervals.getType().isWide());
+
+    if (intervals.isArgumentInterval() && intervals != intervals.getSplitParent()) {
+      LiveIntervals parent = intervals.getSplitParent();
+      if (parent.getRegister() != intervals.getRegister()) {
+        takeFreeRegistersForIntervals(parent);
+      }
+    }
+  }
+
+  private boolean registerIsFree(int register) {
+    return freeRegisters.contains(register)
+        || (hasDedicatedMoveExceptionRegister() && register == getMoveExceptionRegister());
+  }
+
+  // Note: treats a register as free if it is in the set of free registers, or it is the dedicated
+  // move exception register.
+  private boolean registersAreFree(int register, boolean isWide) {
+    return registerIsFree(register) && (!isWide || registerIsFree(register + 1));
+  }
+
+  private boolean registersAreTaken(int register, boolean isWide) {
+    return !freeRegisters.contains(register) && (!isWide || !freeRegisters.contains(register + 1));
+  }
+
+  private boolean registersForIntervalsAreTaken(LiveIntervals intervals) {
+    assert intervals.getRegister() != NO_REGISTER;
+    return registersAreTaken(intervals.getRegister(), intervals.getType().isWide());
+  }
+
+  private boolean atLeastOneOfRegistersAreTaken(int register, boolean isWide) {
+    return !freeRegisters.contains(register) || (isWide && !freeRegisters.contains(register + 1));
+  }
+
   private boolean noLinkedValues() {
     for (BasicBlock block : code.blocks) {
       for (Phi phi : block.getPhis()) {
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 df5df48..7e398e6 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
@@ -15,6 +15,7 @@
 import java.util.Iterator;
 import java.util.List;
 import java.util.TreeSet;
+import java.util.function.IntConsumer;
 
 public class LiveIntervals implements Comparable<LiveIntervals> {
 
@@ -383,6 +384,14 @@
     return null;
   }
 
+  public void forEachRegister(IntConsumer consumer) {
+    assert register != NO_REGISTER;
+    consumer.accept(register);
+    if (getType().isWide()) {
+      consumer.accept(register + 1);
+    }
+  }
+
   public LiveIntervals splitBefore(int start) {
     if (toInstructionPosition(start) == toInstructionPosition(getStart())) {
       assert uses.size() == 0 || getFirstUse() != start;
diff --git a/src/test/java/com/android/tools/r8/debug/DebugTestBase.java b/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
index f65e204..e8d21f2 100644
--- a/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
+++ b/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
@@ -1118,21 +1118,27 @@
                       }));
         }
 
+        private String convertCurrentLocationToString() {
+          return getSourceFile() + ":" + getLineNumber()
+              + " (pc 0x" + Long.toHexString(location.index) + ")";
+        }
+
         private void failNoLocal(String localName) {
-          Assert.fail(
-              "line " + getLineNumber() + ": Expected local '" + localName + "' not present");
+          String locationString = convertCurrentLocationToString();
+          Assert.fail("expected local '" + localName + "' is not present at " + locationString);
         }
 
         @Override
         public void checkNoLocal(String localName) {
-          Optional<Variable> localVar = JUnit3Wrapper
-              .getVariableAt(mirror, getLocation(), localName);
-          Assert.assertFalse("Unexpected local: " + localName, localVar.isPresent());
+          Optional<Variable> localVar = getVariableAt(mirror, getLocation(), localName);
+          if (localVar.isPresent()) {
+            String locationString = convertCurrentLocationToString();
+            Assert.fail("unexpected local '" + localName + "' is present at " + locationString);
+          }
         }
 
         public void checkLocal(String localName) {
-          Optional<Variable> localVar = JUnit3Wrapper
-              .getVariableAt(mirror, getLocation(), localName);
+          Optional<Variable> localVar = getVariableAt(mirror, getLocation(), localName);
           if (!localVar.isPresent()) {
             failNoLocal(localName);
           }
diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/Regress68656641.java b/src/test/java/com/android/tools/r8/ir/regalloc/Regress68656641.java
index e76177c..9866b34 100644
--- a/src/test/java/com/android/tools/r8/ir/regalloc/Regress68656641.java
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/Regress68656641.java
@@ -29,7 +29,7 @@
     }
 
     public void splitOverlappingInactiveIntervals(LiveIntervals intervals, int register) {
-      splitOverlappingInactiveIntervals(intervals, false, register);
+      splitOverlappingInactiveIntervals(intervals, register, false);
     }
 
     public PriorityQueue<LiveIntervals> getUnhandled() {