diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMove.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMove.java
index 963bc1f..70d2ab8 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMove.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMove.java
@@ -11,6 +11,7 @@
 import it.unimi.dsi.fastutil.ints.Int2IntMap;
 import java.util.Objects;
 import java.util.Set;
+import java.util.function.IntConsumer;
 
 // Register moves used by the spilling register allocator. These are used both for spill and
 // for phi moves and they are moves between actual registers represented by their register number.
@@ -36,6 +37,22 @@
     this.type = type;
   }
 
+  public void forEachDestinationRegister(IntConsumer consumer) {
+    consumer.accept(dst);
+    if (isWide()) {
+      consumer.accept(dst + 1);
+    }
+  }
+
+  public void forEachSourceRegister(IntConsumer consumer) {
+    if (src != NO_REGISTER) {
+      consumer.accept(src);
+      if (isWide()) {
+        consumer.accept(src + 1);
+      }
+    }
+  }
+
   public boolean writes(int register, boolean otherIsWide) {
     if (dst == register) {
       return true;
@@ -49,7 +66,11 @@
     return false;
   }
 
-  public boolean isBlocked(Set<RegisterMove> moveSet, Int2IntMap valueMap) {
+  public boolean isBlocked(
+      RegisterMoveScheduler scheduler, Set<RegisterMove> moveSet, Int2IntMap valueMap) {
+    if (isDestUsedAsTemporary(scheduler)) {
+      return true;
+    }
     for (RegisterMove move : moveSet) {
       if (isIdentical(move) || move.src == NO_REGISTER) {
         continue;
@@ -61,10 +82,19 @@
     return false;
   }
 
+  public boolean isDestUsedAsTemporary(RegisterMoveScheduler scheduler) {
+    return scheduler.activeTempRegisters.contains(dst)
+        || (isWide() && scheduler.activeTempRegisters.contains(dst + 1));
+  }
+
   public boolean isIdentical(RegisterMove move) {
     return ObjectUtils.identical(this, move);
   }
 
+  public boolean isNotIdentical(RegisterMove move) {
+    return !isIdentical(move);
+  }
+
   public boolean isWide() {
     return type.isWidePrimitive();
   }
@@ -113,4 +143,16 @@
     }
     return definition.getNumber() - o.definition.getNumber();
   }
+
+  @Override
+  public String toString() {
+    if (type.isSinglePrimitive()) {
+      return "move " + dst + ", " + src;
+    } else if (type.isWidePrimitive()) {
+      return "move-wide " + dst + ", " + src;
+    } else {
+      assert type.isReferenceType();
+      return "move-object " + dst + ", " + src;
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveCycle.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveCycle.java
new file mode 100644
index 0000000..a1e986d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveCycle.java
@@ -0,0 +1,28 @@
+// Copyright (c) 2024, 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.ir.regalloc;
+
+import java.util.TreeSet;
+
+class RegisterMoveCycle {
+
+  private final TreeSet<RegisterMove> moves;
+
+  // Whether the cycle is closed, i.e., the moves in the cycle are only blocked by moves also
+  // present in this cycle.
+  private final boolean closed;
+
+  RegisterMoveCycle(TreeSet<RegisterMove> cycle, boolean closed) {
+    this.moves = cycle;
+    this.closed = closed;
+  }
+
+  public TreeSet<RegisterMove> getMoves() {
+    return moves;
+  }
+
+  public boolean isClosed() {
+    return closed;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveCycleDetector.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveCycleDetector.java
new file mode 100644
index 0000000..a6b2ad6
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveCycleDetector.java
@@ -0,0 +1,138 @@
+// Copyright (c) 2024, 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.ir.regalloc;
+
+import com.android.tools.r8.utils.SetUtils;
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.TreeSet;
+
+public class RegisterMoveCycleDetector {
+
+  @SuppressWarnings("MixedMutabilityReturnType")
+  static List<RegisterMoveCycle> getMoveCycles(TreeSet<RegisterMove> moveSet) {
+    if (moveSet.size() <= 1) {
+      return Collections.emptyList();
+    }
+    List<RegisterMoveCycle> moveCycles = new ArrayList<>();
+    Int2ObjectMap<TreeSet<RegisterMove>> readBy = createReadByGraph(moveSet);
+    Set<RegisterMove> finished = new HashSet<>();
+    Deque<RegisterMove> stack = new ArrayDeque<>();
+    TreeSet<RegisterMove> stackSet = new TreeSet<>();
+    for (RegisterMove move : moveSet) {
+      if (finished.contains(move)) {
+        continue;
+      }
+      dfs(move, finished, readBy, stack, stackSet, moveCycles);
+      assert finished.contains(move);
+      assert stack.isEmpty();
+      assert stackSet.isEmpty();
+    }
+    return moveCycles;
+  }
+
+  private static void dfs(
+      RegisterMove move,
+      Set<RegisterMove> finished,
+      Int2ObjectMap<TreeSet<RegisterMove>> readBy,
+      Deque<RegisterMove> stack,
+      TreeSet<RegisterMove> stackSet,
+      List<RegisterMoveCycle> moveCycles) {
+    stack.addLast(move);
+    boolean addedToStack = stackSet.add(move);
+    assert addedToStack;
+    // Explore all outgoing edges. The successors of this move are the moves that read the
+    // destination registers of the current move.
+    for (RegisterMove successor : getSuccessors(move, readBy)) {
+      if (finished.contains(successor)) {
+        // Already fully explored.
+        continue;
+      }
+      if (successor.isIdentical(move)) {
+        // This move is reading/writing overlapping registers (e.g., move-wide 0, 1).
+        continue;
+      }
+      if (stackSet.contains(successor)) {
+        moveCycles.add(extractCycle(stack, successor, readBy));
+      } else {
+        dfs(successor, finished, readBy, stack, stackSet, moveCycles);
+      }
+    }
+    RegisterMove removedFromStack = stack.removeLast();
+    assert removedFromStack.isIdentical(move);
+    boolean removedFromStackSet = stackSet.remove(move);
+    assert removedFromStackSet;
+    boolean markedFinished = finished.add(move);
+    assert markedFinished;
+  }
+
+  // Returns a one-to-many map from registers to the set of moves that read that register.
+  private static Int2ObjectMap<TreeSet<RegisterMove>> createReadByGraph(
+      TreeSet<RegisterMove> moveSet) {
+    Int2ObjectMap<TreeSet<RegisterMove>> readBy = new Int2ObjectOpenHashMap<>();
+    for (RegisterMove move : moveSet) {
+      move.forEachSourceRegister(
+          register -> {
+            if (readBy.containsKey(register)) {
+              readBy.get(register).add(move);
+            } else {
+              readBy.put(register, SetUtils.newTreeSet(move));
+            }
+          });
+    }
+    return readBy;
+  }
+
+  private static Set<RegisterMove> getSuccessors(
+      RegisterMove move, Int2ObjectMap<TreeSet<RegisterMove>> readBy) {
+    TreeSet<RegisterMove> successors = readBy.get(move.dst);
+    if (move.isWide()) {
+      TreeSet<RegisterMove> additionalSuccessors = readBy.get(move.dst + 1);
+      if (successors == null) {
+        successors = additionalSuccessors;
+      } else if (additionalSuccessors != null) {
+        successors = new TreeSet<>(successors);
+        successors.addAll(additionalSuccessors);
+      }
+    }
+    return successors != null ? successors : Collections.emptySet();
+  }
+
+  private static RegisterMoveCycle extractCycle(
+      Deque<RegisterMove> stack,
+      RegisterMove cycleEntry,
+      Int2ObjectMap<TreeSet<RegisterMove>> readBy) {
+    Deque<RegisterMove> cycle = new ArrayDeque<>();
+    while (!cycleEntry.isIdentical(cycle.peekFirst())) {
+      cycle.addFirst(stack.removeLast());
+    }
+    stack.addAll(cycle);
+    TreeSet<RegisterMove> cycleSet = new TreeSet<>(cycle);
+    return new RegisterMoveCycle(cycleSet, isClosedCycle(cycleSet, readBy));
+  }
+
+  private static boolean isClosedCycle(
+      TreeSet<RegisterMove> cycle, Int2ObjectMap<TreeSet<RegisterMove>> readBy) {
+    for (RegisterMove move : cycle) {
+      for (int i = 0; i < move.type.requiredRegisters(); i++) {
+        TreeSet<RegisterMove> successors = readBy.get(move.dst + i);
+        if (successors != null) {
+          for (RegisterMove successor : successors) {
+            if (!cycle.contains(successor)) {
+              return false;
+            }
+          }
+        }
+      }
+    }
+    return true;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveScheduler.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveScheduler.java
index 242f2dc..43c2ed3 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveScheduler.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveScheduler.java
@@ -4,6 +4,8 @@
 package com.android.tools.r8.ir.regalloc;
 
 import static com.android.tools.r8.ir.regalloc.LiveIntervals.NO_REGISTER;
+import static com.android.tools.r8.utils.IntConsumerUtils.emptyIntConsumer;
+import static com.google.common.base.Predicates.not;
 
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.ir.analysis.type.TypeElement;
@@ -16,6 +18,8 @@
 import com.android.tools.r8.ir.code.Move;
 import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.utils.ObjectUtils;
+import com.google.common.collect.Iterables;
 import it.unimi.dsi.fastutil.ints.Int2IntMap;
 import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
 import it.unimi.dsi.fastutil.ints.IntArraySet;
@@ -26,14 +30,13 @@
 import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Deque;
-import java.util.Iterator;
 import java.util.List;
-import java.util.Set;
 import java.util.TreeSet;
+import java.util.function.IntConsumer;
 
 public class RegisterMoveScheduler {
   // The set of moves to schedule.
-  private final Set<RegisterMove> moveSet = new TreeSet<>();
+  private final TreeSet<RegisterMove> moveSet = new TreeSet<>();
   // Mapping to keep track of which values currently corresponds to each other.
   // This is initially an identity map but changes as we insert moves.
   private final Int2IntMap valueMap = new Int2IntOpenHashMap();
@@ -44,8 +47,15 @@
   // The first available temporary register.
   private final int firstTempRegister;
   private int nextTempRegister;
-  // Free registers.
+  // Free temporary registers that have been allocated by move scheduling.
   private final IntSortedSet freeRegisters = new IntRBTreeSet();
+  // Registers that can be used as temporary registers until they are assigned by a move in the
+  // move set.
+  private final IntSortedSet freeRegistersUntilAssigned = new IntRBTreeSet();
+  // Registers that are the destination register of some move in the move set, but which are
+  // currently being used as a temporary register for another value. Moves in the move set that
+  // write a register in this set are blocked until the temporary registers are released.
+  public final IntSet activeTempRegisters = new IntOpenHashSet();
 
   public RegisterMoveScheduler(
       InstructionListIterator insertAt, int firstTempRegister, Position position) {
@@ -60,6 +70,19 @@
     this(insertAt, firstTempRegister, Position.none());
   }
 
+  private void initializeFreeRegistersUntilAssigned() {
+    // All registers that are assigned by the move set but not read can be used as temporary
+    // registers until they are assigned.
+    assert activeTempRegisters.isEmpty();
+    assert freeRegistersUntilAssigned.isEmpty();
+    for (RegisterMove move : moveSet) {
+      move.forEachDestinationRegister(freeRegistersUntilAssigned::add);
+    }
+    for (RegisterMove move : moveSet) {
+      move.forEachSourceRegister(freeRegistersUntilAssigned::remove);
+    }
+  }
+
   public void addMove(RegisterMove move) {
     moveSet.add(move);
     if (move.src != NO_REGISTER) {
@@ -70,53 +93,58 @@
 
   public void schedule() {
     assert everyDestinationOnlyWrittenOnce();
+    initializeFreeRegistersUntilAssigned();
 
     // Worklist of moves that are ready to be inserted.
     Deque<RegisterMove> worklist = new ArrayDeque<>();
 
-    // Initialize worklist with the moves that do not interfere with other moves.
-    Iterator<RegisterMove> iterator = moveSet.iterator();
-    while (iterator.hasNext()) {
-      RegisterMove move = iterator.next();
-      if (!move.isBlocked(moveSet, valueMap)) {
-        worklist.addLast(move);
-        iterator.remove();
+    // If there are destination registers we can use until they are assigned, then instead of
+    // emitting these unblocked moves, we use them as temporary registers to unblock move cycles.
+    List<RegisterMoveCycle> moveCycles = RegisterMoveCycleDetector.getMoveCycles(moveSet);
+    for (RegisterMoveCycle moveCycle : moveCycles) {
+      for (RegisterMove move : moveCycle.getMoves()) {
+        assert move.isBlocked(this, moveSet, valueMap) || !moveSet.contains(move);
+        removeFromFreeRegistersUntilAssigned(move.dst, move.isWide(), emptyIntConsumer());
       }
+      // If the cycle is not closed then some moves in the cycle are blocked by other moves.
+      // TODO(b/375147902): Try to schedule these other moves before scheduling the cycle to
+      //  unblock the cycle. In JetNews 15% of move cycles are open.
+      if (moveCycle.isClosed()) {
+        assert moveSet.containsAll(moveCycle.getMoves());
+        assert worklist.isEmpty();
+        schedulePartial(moveCycle.getMoves(), worklist);
+      }
+      assert activeTempRegisters.isEmpty();
     }
 
+    // Initialize worklist with the moves that do not interfere with other moves.
+    enqueueUnblockedMoves(worklist);
+    schedulePartial(moveSet, worklist);
+    assert freeRegistersUntilAssigned.isEmpty();
+  }
+
+  private void schedulePartial(
+      TreeSet<RegisterMove> movesToSchedule, Deque<RegisterMove> worklist) {
     // Process the worklist generating moves. If the worklist becomes empty while the move set
     // still contains elements we need to use a temporary to break cycles.
-    while (!worklist.isEmpty() || !moveSet.isEmpty()) {
+    while (!worklist.isEmpty() || !movesToSchedule.isEmpty()) {
       while (!worklist.isEmpty()) {
-        RegisterMove move = worklist.removeFirst();
-        assert !move.isBlocked(moveSet, valueMap);
-        // Insert the move.
-        int generatedDest = createMove(move);
-        // Update the value map with the information that dest can be used instead of
-        // src starting now.
-        if (move.src != NO_REGISTER) {
-          valueMap.put(move.src, generatedDest);
+        while (!worklist.isEmpty()) {
+          RegisterMove move = worklist.removeFirst();
+          assert !move.isBlocked(this, moveSet, valueMap);
+          createMove(move);
         }
-        // Iterate and find the moves that were blocked because they need to write to
-        // one of the move src. That is now valid because the move src is preserved in dest.
-        iterator = moveSet.iterator();
-        while (iterator.hasNext()) {
-          RegisterMove other = iterator.next();
-          if (!other.isBlocked(moveSet, valueMap)) {
-            worklist.addLast(other);
-            iterator.remove();
-          }
-        }
+        enqueueUnblockedMoves(worklist, movesToSchedule);
       }
-      if (!moveSet.isEmpty()) {
+      if (!movesToSchedule.isEmpty()) {
         // The remaining moves are conflicting. Chose a move and unblock it by generating moves to
         // temporary registers for its destination value(s).
-        RegisterMove move = pickMoveToUnblock();
+        RegisterMove move = pickMoveToUnblock(movesToSchedule);
         createMoveDestToTemp(move);
         // TODO(b/375147902): After emitting the newly unblocked move, try to prioritize the moves
         //  that blocked it, so that we free up the temp register, rather than getting overlapping
         //  temporary registers.
-        worklist.addLast(move);
+        worklist.add(move);
       }
     }
   }
@@ -135,7 +163,7 @@
       int moveSrc = valueMap.get(move.src);
       if (moveSrc == src) {
         result.add(move);
-      } else if (move.type.isWidePrimitive() && (moveSrc + 1) == src) {
+      } else if (move.isWide() && (moveSrc + 1) == src) {
         result.add(move);
       } else if (type.isWidePrimitive() && (moveSrc - 1) == src) {
         result.add(move);
@@ -144,7 +172,7 @@
     return result;
   }
 
-  private int createMove(RegisterMove move) {
+  private void createMove(RegisterMove move) {
     Instruction instruction;
     if (move.definition != null) {
       if (move.definition.isArgument()) {
@@ -172,7 +200,43 @@
     }
     instruction.setPosition(position);
     insertAt.add(instruction);
-    return move.dst;
+
+    // Update the value map with the information that dest can be used instead of
+    // src starting now.
+    if (move.src != NO_REGISTER) {
+      valueMap.put(move.src, move.dst);
+    }
+    removeFromFreeRegistersUntilAssigned(move.dst, move.isWide(), emptyIntConsumer());
+  }
+
+  private void enqueueUnblockedMoves(Deque<RegisterMove> worklist) {
+    // Iterate and find the moves that were blocked because they need to write to one of the move
+    // src. That is now valid because the move src is preserved in dest.
+    moveSet.removeIf(
+        move -> {
+          if (move.isBlocked(this, moveSet, valueMap)) {
+            return false;
+          }
+          worklist.addLast(move);
+          return true;
+        });
+  }
+
+  private void enqueueUnblockedMoves(
+      Deque<RegisterMove> worklist, TreeSet<RegisterMove> movesToSchedule) {
+    // Iterate and find the moves that were blocked because they need to write to one of the move
+    // src. That is now valid because the move src is preserved in dest.
+    movesToSchedule.removeIf(
+        move -> {
+          if (move.isBlocked(this, moveSet, valueMap)) {
+            return false;
+          }
+          if (ObjectUtils.notIdentical(moveSet, movesToSchedule)) {
+            moveSet.remove(move);
+          }
+          worklist.addLast(move);
+          return true;
+        });
   }
 
   private void createMoveDestToTemp(RegisterMove move) {
@@ -195,15 +259,17 @@
   }
 
   private int takeFreeRegister(boolean wide) {
-    for (int freeRegister : freeRegisters) {
-      if (wide && !freeRegisters.remove(freeRegister + 1)) {
-        continue;
-      }
-      freeRegisters.remove(freeRegister);
-      return freeRegister;
+    int register = takeFreeRegisterFrom(freeRegistersUntilAssigned, wide);
+    if (register != NO_REGISTER) {
+      addActiveTempRegisters(register, wide);
+      return register;
+    }
+    register = takeFreeRegisterFrom(freeRegisters, wide);
+    if (register != NO_REGISTER) {
+      return register;
     }
     // We don't have a free register.
-    int register = allocateExtraRegister();
+    register = allocateExtraRegister();
     if (!wide) {
       return register;
     }
@@ -214,21 +280,78 @@
     return register;
   }
 
-  private void returnTemporaryRegister(int register, boolean wide) {
-    // TODO(b/375147902): If we seed the move scheduler with a set of free registers, then this
-    //  should also return non-temporary registers that are below firstTempRegister.
-    if (isTemporaryRegister(register)) {
-      freeRegisters.add(register);
-      if (wide) {
-        assert isTemporaryRegister(register + 1);
-        freeRegisters.add(register + 1);
+  private static int takeFreeRegisterFrom(IntSortedSet freeRegisters, boolean wide) {
+    for (int freeRegister : freeRegisters) {
+      if (wide && !freeRegisters.remove(freeRegister + 1)) {
+        continue;
       }
-    } else if (wide && isTemporaryRegister(register + 1)) {
+      freeRegisters.remove(freeRegister);
+      return freeRegister;
+    }
+    return NO_REGISTER;
+  }
+
+  private void addActiveTempRegisters(int register, boolean wide) {
+    boolean addedRegister = activeTempRegisters.add(register);
+    assert addedRegister;
+    if (wide) {
+      boolean addedHighRegister = activeTempRegisters.add(register + 1);
+      assert addedHighRegister;
+    }
+  }
+
+  private void returnTemporaryRegister(int register, boolean wide) {
+    if (returnActiveTempRegister(register, wide)) {
+      addFreeRegistersUntilAssigned(register, wide);
+    } else if (isExtraTemporaryRegister(register)) {
+      returnExtraTemporaryRegister(register, wide);
+    }
+  }
+
+  private boolean returnActiveTempRegister(int register, boolean wide) {
+    boolean removedRegister = activeTempRegisters.remove(register);
+    if (wide) {
+      if (removedRegister) {
+        boolean removedHighRegister = activeTempRegisters.remove(register + 1);
+        assert removedHighRegister;
+      } else {
+        assert !activeTempRegisters.contains(register + 1);
+      }
+    }
+    return removedRegister;
+  }
+
+  private void addFreeRegistersUntilAssigned(int register, boolean wide) {
+    boolean addedRegister = freeRegistersUntilAssigned.add(register);
+    assert addedRegister;
+    if (wide) {
+      boolean addedHighRegister = freeRegistersUntilAssigned.add(register + 1);
+      assert addedHighRegister;
+    }
+  }
+
+  private void returnExtraTemporaryRegister(int register, boolean wide) {
+    assert isExtraTemporaryRegister(register);
+    freeRegisters.add(register);
+    if (wide) {
+      assert isExtraTemporaryRegister(register + 1);
       freeRegisters.add(register + 1);
     }
   }
 
-  private boolean isTemporaryRegister(int register) {
+  private void removeFromFreeRegistersUntilAssigned(
+      int register, boolean wide, IntConsumer changedConsumer) {
+    if (freeRegistersUntilAssigned.remove(register)) {
+      changedConsumer.accept(register);
+    }
+    if (wide) {
+      if (freeRegistersUntilAssigned.remove(register + 1)) {
+        changedConsumer.accept(register + 1);
+      }
+    }
+  }
+
+  private boolean isExtraTemporaryRegister(int register) {
     return register >= firstTempRegister;
   }
 
@@ -244,17 +367,16 @@
     return true;
   }
 
-  private RegisterMove pickMoveToUnblock() {
-    Iterator<RegisterMove> iterator = moveSet.iterator();
-    RegisterMove move = null;
+  private RegisterMove pickMoveToUnblock(TreeSet<RegisterMove> moves) {
     // Pick a non-wide move to unblock if possible.
-    while (iterator.hasNext()) {
-      move = iterator.next();
-      if (!move.type.isWidePrimitive()) {
-        break;
-      }
+    Iterable<RegisterMove> eligible =
+        Iterables.filter(moves, move -> !move.isDestUsedAsTemporary(this));
+    RegisterMove move =
+        Iterables.find(eligible, not(RegisterMove::isWide), eligible.iterator().next());
+    moves.remove(move);
+    if (ObjectUtils.notIdentical(moves, moveSet)) {
+      moveSet.remove(move);
     }
-    iterator.remove();
     return move;
   }
 
diff --git a/src/main/java/com/android/tools/r8/utils/SetUtils.java b/src/main/java/com/android/tools/r8/utils/SetUtils.java
index ea46d64..7ec47cb 100644
--- a/src/main/java/com/android/tools/r8/utils/SetUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/SetUtils.java
@@ -13,6 +13,7 @@
 import java.util.IdentityHashMap;
 import java.util.LinkedHashSet;
 import java.util.Set;
+import java.util.TreeSet;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.function.Function;
 
@@ -118,6 +119,12 @@
     return builder.build();
   }
 
+  public static <T extends Comparable<T>> TreeSet<T> newTreeSet(T element) {
+    TreeSet<T> result = new TreeSet<>();
+    result.add(element);
+    return result;
+  }
+
   public static <T, S> Set<T> mapIdentityHashSet(Collection<S> set, Function<S, T> fn) {
     Set<T> out = newIdentityHashSet(set.size());
     for (S element : set) {
diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java b/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
index ae83eee..7e42fa9 100644
--- a/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
@@ -388,18 +388,10 @@
     scheduler.addMove(new RegisterMove(0, 3, TypeElement.getLong()));
     scheduler.schedule();
     assertEquals(3, moves.size());
-    Move firstMove = moves.get(0).asMove();
-    Move secondMove = moves.get(1).asMove();
-    Move thirdMove = moves.get(2).asMove();
-    assertEquals(ValueType.LONG, firstMove.outType());
-    assertEquals(ValueType.LONG, secondMove.outType());
-    assertEquals(ValueType.LONG, thirdMove.outType());
-    assertEquals(42, firstMove.dest().asFixedRegisterValue().getRegister());
-    assertEquals(1, firstMove.src().asFixedRegisterValue().getRegister());
-    assertEquals(0, secondMove.dest().asFixedRegisterValue().getRegister());
-    assertEquals(3, secondMove.src().asFixedRegisterValue().getRegister());
-    assertEquals(2, thirdMove.dest().asFixedRegisterValue().getRegister());
-    assertEquals(42, thirdMove.src().asFixedRegisterValue().getRegister());
+    assertEquals("42 <- 3", toString(moves.get(0)));
+    assertEquals("2 <- 1", toString(moves.get(1)));
+    assertEquals("0 <- 42", toString(moves.get(2)));
+    assertEquals(2, scheduler.getUsedTempRegisters());
   }
 
   @Test
@@ -460,12 +452,13 @@
     scheduler.addMove(new RegisterMove(12, 19, TypeElement.getLong()));
     scheduler.schedule();
     // In order to resolve these moves, we need to use two temporary register pairs.
-    assertEquals(6, moves.size());
-    assertEquals(42, moves.get(0).asMove().dest().asFixedRegisterValue().getRegister());
-    assertEquals(11, moves.get(0).asMove().src().asFixedRegisterValue().getRegister());
-    assertEquals(44, moves.get(1).asMove().dest().asFixedRegisterValue().getRegister());
-    assertEquals(13, moves.get(1).asMove().src().asFixedRegisterValue().getRegister());
-    assertEquals(12, moves.get(2).asMove().dest().asFixedRegisterValue().getRegister());
+    assertEquals(5, moves.size());
+    assertEquals("42 <- 13", toString(moves.get(0)));
+    assertEquals("14 <- 11", toString(moves.get(1)));
+    assertEquals("10 <- 17", toString(moves.get(2)));
+    assertEquals("16 <- 42", toString(moves.get(3)));
+    assertEquals("12 <- 19", toString(moves.get(4)));
+    assertEquals(2, scheduler.getUsedTempRegisters());
   }
 
   @Test
@@ -487,19 +480,13 @@
     scheduler.addMove(new RegisterMove(23, 28, TypeElement.getLong()));
     scheduler.schedule();
     // For this example we need recursive unblocking.
-    assertEquals(6, moves.size());
-    assertEquals(42, moves.get(0).asMove().dest().asFixedRegisterValue().getRegister());
-    assertEquals(26, moves.get(0).asMove().src().asFixedRegisterValue().getRegister());
-    assertEquals(26, moves.get(1).asMove().dest().asFixedRegisterValue().getRegister());
-    assertEquals(22, moves.get(1).asMove().src().asFixedRegisterValue().getRegister());
-    assertEquals(43, moves.get(2).asMove().dest().asFixedRegisterValue().getRegister());
-    assertEquals(28, moves.get(2).asMove().src().asFixedRegisterValue().getRegister());
-    assertEquals(28, moves.get(3).asMove().dest().asFixedRegisterValue().getRegister());
-    assertEquals(42, moves.get(3).asMove().src().asFixedRegisterValue().getRegister());
-    assertEquals(29, moves.get(4).asMove().dest().asFixedRegisterValue().getRegister());
-    assertEquals(24, moves.get(4).asMove().src().asFixedRegisterValue().getRegister());
-    assertEquals(23, moves.get(5).asMove().dest().asFixedRegisterValue().getRegister());
-    assertEquals(43, moves.get(5).asMove().src().asFixedRegisterValue().getRegister());
+    assertEquals(5, moves.size());
+    assertEquals("42 <- 28", toString(moves.get(0)));
+    assertEquals("29 <- 24", toString(moves.get(1)));
+    assertEquals("23 <- 42", toString(moves.get(2)));
+    assertEquals("28 <- 26", toString(moves.get(3)));
+    assertEquals("26 <- 22", toString(moves.get(4)));
+    assertEquals(2, scheduler.getUsedTempRegisters());
   }
 
   @Test
@@ -522,6 +509,56 @@
     assertEquals(1, scheduler.getUsedTempRegisters());
   }
 
+  @Test
+  public void useDestinationRegisterAsTemporary() {
+    CollectMovesIterator moves = new CollectMovesIterator();
+    int temp = 42;
+    RegisterMoveScheduler scheduler = new RegisterMoveScheduler(moves, temp);
+    scheduler.addMove(new RegisterMove(0, 1, TypeElement.getInt()));
+    scheduler.addMove(new RegisterMove(1, 0, TypeElement.getInt()));
+    scheduler.addMove(new RegisterMove(2, 3, TypeElement.getInt()));
+    scheduler.schedule();
+    // Verify that the temp register has been reused.
+    assertEquals("2 <- 1", toString(moves.get(0)));
+    assertEquals("1 <- 0", toString(moves.get(1)));
+    assertEquals("0 <- 2", toString(moves.get(2)));
+    assertEquals("2 <- 3", toString(moves.get(3)));
+    assertEquals(0, scheduler.getUsedTempRegisters());
+  }
+
+  @Test
+  public void openMoveCycle() {
+    CollectMovesIterator moves = new CollectMovesIterator();
+    int temp = 42;
+    RegisterMoveScheduler scheduler = new RegisterMoveScheduler(moves, temp);
+    scheduler.addMove(new RegisterMove(2, 0, TypeElement.getInt()));
+    scheduler.addMove(new RegisterMove(0, 2, TypeElement.getLong()));
+    scheduler.addMove(new RegisterMove(4, 1, TypeElement.getInt()));
+    scheduler.schedule();
+    // The cycle is blocked by the move 4 <- 1, so we should emit this move first.
+    assertEquals(4, moves.size());
+    assertEquals("4 <- 1", toString(moves.get(0)));
+    assertEquals("42 <- 2", toString(moves.get(1)));
+    assertEquals("2 <- 0", toString(moves.get(2)));
+    assertEquals("0 <- 42", toString(moves.get(3)));
+    assertEquals(2, scheduler.getUsedTempRegisters());
+  }
+
+  @Test
+  public void regressionTestBug378850589() {
+    CollectMovesIterator moves = new CollectMovesIterator();
+    int temp = 42;
+    RegisterMoveScheduler scheduler = new RegisterMoveScheduler(moves, temp);
+    scheduler.addMove(new RegisterMove(9, 12, TypeElement.getLong()));
+    scheduler.addMove(new RegisterMove(11, 8, TypeElement.getLong()));
+    scheduler.schedule();
+    assertEquals(3, moves.size());
+    assertEquals("42 <- 12", toString(moves.get(0)));
+    assertEquals("11 <- 8", toString(moves.get(1)));
+    assertEquals("9 <- 42", toString(moves.get(3)));
+    assertEquals(2, scheduler.getUsedTempRegisters());
+  }
+
   // Debugging aid.
   private void printMoves(List<Instruction> moves) {
     System.out.println("Generated moves:");