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 4c60ed6..242f2dc 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
@@ -19,7 +19,10 @@
 import it.unimi.dsi.fastutil.ints.Int2IntMap;
 import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
 import it.unimi.dsi.fastutil.ints.IntArraySet;
+import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
+import it.unimi.dsi.fastutil.ints.IntRBTreeSet;
 import it.unimi.dsi.fastutil.ints.IntSet;
+import it.unimi.dsi.fastutil.ints.IntSortedSet;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Deque;
@@ -34,25 +37,27 @@
   // 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();
-  // Number of temp registers used to schedule the moves.
-  private int usedTempRegisters = 0;
   // Location at which to insert the scheduled moves.
   private final InstructionListIterator insertAt;
   // Debug position associated with insertion point.
   private final Position position;
   // The first available temporary register.
-  private final int tempRegister;
+  private final int firstTempRegister;
+  private int nextTempRegister;
+  // Free registers.
+  private final IntSortedSet freeRegisters = new IntRBTreeSet();
 
   public RegisterMoveScheduler(
-      InstructionListIterator insertAt, int tempRegister, Position position) {
+      InstructionListIterator insertAt, int firstTempRegister, Position position) {
     this.insertAt = insertAt;
-    this.tempRegister = tempRegister;
+    this.firstTempRegister = firstTempRegister;
+    this.nextTempRegister = firstTempRegister;
     this.position = position;
     this.valueMap.defaultReturnValue(NO_REGISTER);
   }
 
-  public RegisterMoveScheduler(InstructionListIterator insertAt, int tempRegister) {
-    this(insertAt, tempRegister, Position.none());
+  public RegisterMoveScheduler(InstructionListIterator insertAt, int firstTempRegister) {
+    this(insertAt, firstTempRegister, Position.none());
   }
 
   public void addMove(RegisterMove move) {
@@ -117,7 +122,7 @@
   }
 
   public int getUsedTempRegisters() {
-    return usedTempRegisters;
+    return nextTempRegister - firstTempRegister;
   }
 
   private List<RegisterMove> findMovesWithSrc(int src, TypeElement type) {
@@ -159,14 +164,15 @@
         }
       }
     } else {
+      int mappedSrc = valueMap.get(move.src);
       Value to = new FixedRegisterValue(move.type, move.dst);
-      Value from = new FixedRegisterValue(move.type, valueMap.get(move.src));
+      Value from = new FixedRegisterValue(move.type, mappedSrc);
       instruction = new Move(to, from);
+      returnTemporaryRegister(mappedSrc, move.isWide());
     }
     instruction.setPosition(position);
     insertAt.add(instruction);
     return move.dst;
-
   }
 
   private void createMoveDestToTemp(RegisterMove move) {
@@ -174,24 +180,70 @@
     // registers if we are unlucky with the overlap for values that use two registers.
     List<RegisterMove> movesWithSrc = findMovesWithSrc(move.dst, move.type);
     assert movesWithSrc.size() > 0;
+    assert verifyMovesHaveDifferentSources(movesWithSrc);
     for (RegisterMove moveWithSrc : movesWithSrc) {
-      // TODO(b/375147902): For now we always use a new temporary register whenever we have to
-      //  unblock a move. The move scheduler can have multiple unblocking temps live at the same
-      //  time and therefore we cannot have just one tempRegister (pair). However, we could check
-      //  here if the previously used tempRegisters is still needed by any of the moves in the move
-      //  set (taking the value map into account). If not, we can reuse the temp register instead
-      //  of generating a new one.
-      int register = tempRegister + usedTempRegisters;
+      // TODO(b/375147902): Maybe seed the move scheduler with a set of registers known to be free
+      //  at this point.
+      int register = takeFreeRegister(moveWithSrc.isWide());
       Value to = new FixedRegisterValue(moveWithSrc.type, register);
       Value from = new FixedRegisterValue(moveWithSrc.type, valueMap.get(moveWithSrc.src));
       Move instruction = new Move(to, from);
       instruction.setPosition(position);
       insertAt.add(instruction);
       valueMap.put(moveWithSrc.src, register);
-      usedTempRegisters += moveWithSrc.type.requiredRegisters();
     }
   }
 
+  private int takeFreeRegister(boolean wide) {
+    for (int freeRegister : freeRegisters) {
+      if (wide && !freeRegisters.remove(freeRegister + 1)) {
+        continue;
+      }
+      freeRegisters.remove(freeRegister);
+      return freeRegister;
+    }
+    // We don't have a free register.
+    int register = allocateExtraRegister();
+    if (!wide) {
+      return register;
+    }
+    if (freeRegisters.remove(register - 1)) {
+      return register - 1;
+    }
+    allocateExtraRegister();
+    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);
+      }
+    } else if (wide && isTemporaryRegister(register + 1)) {
+      freeRegisters.add(register + 1);
+    }
+  }
+
+  private boolean isTemporaryRegister(int register) {
+    return register >= firstTempRegister;
+  }
+
+  private int allocateExtraRegister() {
+    return nextTempRegister++;
+  }
+
+  private boolean verifyMovesHaveDifferentSources(List<RegisterMove> movesWithSrc) {
+    IntSet seen = new IntOpenHashSet();
+    for (RegisterMove move : movesWithSrc) {
+      assert seen.add(move.src);
+    }
+    return true;
+  }
+
   private RegisterMove pickMoveToUnblock() {
     Iterator<RegisterMove> iterator = moveSet.iterator();
     RegisterMove move = null;
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 fab0924..ae83eee 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
@@ -5,6 +5,9 @@
 
 import static org.junit.Assert.assertEquals;
 
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.errors.Unimplemented;
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.AppView;
@@ -39,8 +42,12 @@
 import java.util.function.Consumer;
 import java.util.function.UnaryOperator;
 import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
 
-public class RegisterMoveSchedulerTest {
+@RunWith(Parameterized.class)
+public class RegisterMoveSchedulerTest extends TestBase {
 
   private static class CollectMovesIterator implements InstructionListIterator {
 
@@ -244,6 +251,15 @@
     }
   }
 
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  public RegisterMoveSchedulerTest(TestParameters parameters) {
+    parameters.assertNoneRuntime();
+  }
+
   @Test
   public void testSingleParallelMove() {
     CollectMovesIterator moves = new CollectMovesIterator();
@@ -486,6 +502,26 @@
     assertEquals(43, moves.get(5).asMove().src().asFixedRegisterValue().getRegister());
   }
 
+  @Test
+  public void reuseTempRegister() {
+    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.addMove(new RegisterMove(3, 2, TypeElement.getInt()));
+    scheduler.schedule();
+    // Verify that the temp register has been reused.
+    assertEquals("42 <- 1", toString(moves.get(0)));
+    assertEquals("1 <- 0", toString(moves.get(1)));
+    assertEquals("0 <- 42", toString(moves.get(2)));
+    assertEquals("42 <- 3", toString(moves.get(3)));
+    assertEquals("3 <- 2", toString(moves.get(4)));
+    assertEquals("2 <- 42", toString(moves.get(5)));
+    assertEquals(1, scheduler.getUsedTempRegisters());
+  }
+
   // Debugging aid.
   private void printMoves(List<Instruction> moves) {
     System.out.println("Generated moves:");
@@ -496,4 +532,10 @@
     }
     System.out.println("----------------");
   }
+
+  private String toString(Instruction move) {
+    return move.outValue().asFixedRegisterValue().getRegister()
+        + " <- "
+        + move.getFirstOperand().asFixedRegisterValue().getRegister();
+  }
 }