diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
index f5bc204..40a4776 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
@@ -140,29 +140,13 @@
       assert newInstruction.outValue() != null;
       current.outValue().replaceUsers(newInstruction.outValue());
     }
-    for (Value value : current.getDebugValues()) {
-      replaceInstructionInList(current, newInstruction, value.getDebugLocalStarts());
-      replaceInstructionInList(current, newInstruction, value.getDebugLocalEnds());
-      value.removeDebugUser(current);
-      newInstruction.addDebugValue(value);
-    }
+    current.moveDebugValues(newInstruction);
     newInstruction.setBlock(block);
     listIterator.remove();
     listIterator.add(newInstruction);
     current.clearBlock();
   }
 
-  private static void replaceInstructionInList(
-      Instruction instruction,
-      Instruction newInstruction,
-      List<Instruction> instructions) {
-    for (int i = 0; i < instructions.size(); i++) {
-      if (instructions.get(i) == instruction) {
-        instructions.set(i, newInstruction);
-      }
-    }
-  }
-
   public BasicBlock split(IRCode code, ListIterator<BasicBlock> blocksIterator) {
     List<BasicBlock> blocks = code.blocks;
     assert blocksIterator == null || IteratorUtils.peekPrevious(blocksIterator) == block;
diff --git a/src/main/java/com/android/tools/r8/ir/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index e99dbf1..a8004a1 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -74,8 +74,9 @@
     if (debugValues == null) {
       debugValues = new HashSet<>();
     }
-    debugValues.add(value);
-    value.addDebugUser(this);
+    if (debugValues.add(value)) {
+      value.addDebugUser(this);
+    }
   }
 
   public static void clearUserInfo(Instruction instruction) {
@@ -115,6 +116,16 @@
     }
   }
 
+  public void moveDebugValues(Instruction target) {
+    if (debugValues == null) {
+      return;
+    }
+    for (Value value : debugValues) {
+      value.replaceDebugUser(this, target);
+    }
+    debugValues.clear();
+  }
+
   /**
    * Returns the basic block containing this instruction.
    */
diff --git a/src/main/java/com/android/tools/r8/ir/code/Value.java b/src/main/java/com/android/tools/r8/ir/code/Value.java
index dfa8548..7412dd7 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Value.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Value.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.ir.code;
 
 import com.android.tools.r8.dex.Constants;
+import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.DebugLocalInfo;
 import com.android.tools.r8.ir.regalloc.LiveIntervals;
 import com.android.tools.r8.utils.InternalOptions;
@@ -11,9 +12,12 @@
 import com.google.common.collect.ImmutableSet;
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Set;
 
 public class Value {
@@ -21,17 +25,49 @@
   // Lazily allocated internal data for the debug information of locals.
   // This is wrapped in a class to avoid multiple pointers in the value structure.
   private static class DebugData {
+
     final DebugLocalInfo local;
-    Set<Instruction> users = new HashSet<>();
+    Map<Instruction, DebugUse> users = new HashMap<>();
     Set<Phi> phiUsers = new HashSet<>();
-    List<Instruction> localStarts = new ArrayList<>();
-    List<Instruction> localEnds = new ArrayList<>();
 
     DebugData(DebugLocalInfo local) {
       this.local = local;
     }
   }
 
+  // A debug-value user represents a point where the value is live, ends or starts.
+  // If a point is marked as both ending and starting then it is simply live, but we maintain
+  // the marker so as not to unintentionally end it if marked again.
+  private enum DebugUse {
+    LIVE, START, END, LIVE_FINAL;
+
+    DebugUse start() {
+      switch (this) {
+        case LIVE:
+        case START:
+          return START;
+        case END:
+        case LIVE_FINAL:
+          return LIVE_FINAL;
+        default:
+          throw new Unreachable();
+      }
+    }
+
+    DebugUse end() {
+      switch (this) {
+        case LIVE:
+        case END:
+          return END;
+        case START:
+        case LIVE_FINAL:
+          return LIVE_FINAL;
+        default:
+          throw new Unreachable();
+      }
+    }
+  }
+
   public static final Value UNDEFINED = new Value(-1, MoveType.OBJECT, null);
 
   protected final int number;
@@ -79,21 +115,49 @@
   }
 
   public List<Instruction> getDebugLocalStarts() {
-    return debugData.localStarts;
+    if (debugData == null) {
+      return Collections.emptyList();
+    }
+    List<Instruction> starts = new ArrayList<>(debugData.users.size());
+    for (Entry<Instruction, DebugUse> entry : debugData.users.entrySet()) {
+      if (entry.getValue() == DebugUse.START) {
+        starts.add(entry.getKey());
+      }
+    }
+    return starts;
   }
 
   public List<Instruction> getDebugLocalEnds() {
-    return debugData.localEnds;
+    if (debugData == null) {
+      return Collections.emptyList();
+    }
+    List<Instruction> ends = new ArrayList<>(debugData.users.size());
+    for (Entry<Instruction, DebugUse> entry : debugData.users.entrySet()) {
+      if (entry.getValue() == DebugUse.END) {
+        ends.add(entry.getKey());
+      }
+    }
+    return ends;
   }
 
   public void addDebugLocalStart(Instruction start) {
     assert start != null;
-    debugData.localStarts.add(start);
+    debugData.users.put(start, markStart(debugData.users.get(start)));
+  }
+
+  private DebugUse markStart(DebugUse use) {
+    assert use != null;
+    return use == null ? DebugUse.START : use.start();
   }
 
   public void addDebugLocalEnd(Instruction end) {
     assert end != null;
-    debugData.localEnds.add(end);
+    debugData.users.put(end, markEnd(debugData.users.get(end)));
+  }
+
+  private DebugUse markEnd(DebugUse use) {
+    assert use != null;
+    return use == null ? DebugUse.END : use.end();
   }
 
   public void linkTo(Value other) {
@@ -152,7 +216,7 @@
   }
 
   public Set<Instruction> debugUsers() {
-    return debugData == null ? null : Collections.unmodifiableSet(debugData.users);
+    return debugData == null ? null : Collections.unmodifiableSet(debugData.users.keySet());
   }
 
   public Set<Phi> debugPhiUsers() {
@@ -244,7 +308,7 @@
     if (isUninitializedLocal()) {
       return;
     }
-    debugData.users.add(user);
+    debugData.users.putIfAbsent(user, DebugUse.LIVE);
   }
 
   public void addDebugPhiUser(Phi user) {
@@ -263,11 +327,19 @@
   }
 
   public void removeDebugUser(Instruction user) {
-    debugData.users.remove(user);
+    if (debugData != null && debugData.users != null) {
+      debugData.users.remove(user);
+      return;
+    }
+    assert false;
   }
 
   public void removeDebugPhiUser(Phi user) {
-    debugData.phiUsers.remove(user);
+    if (debugData != null && debugData.phiUsers != null) {
+      debugData.phiUsers.remove(user);
+      return;
+    }
+    assert false;
   }
 
   public boolean hasUsersInfo() {
@@ -355,6 +427,14 @@
     }
   }
 
+  public void replaceDebugUser(Instruction oldUser, Instruction newUser) {
+    DebugUse use = debugData.users.remove(oldUser);
+    if (use != null) {
+      newUser.addDebugValue(this);
+      debugData.users.put(newUser, use);
+    }
+  }
+
   public void setLiveIntervals(LiveIntervals intervals) {
     assert liveIntervals == null;
     liveIntervals = intervals;
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
index 7f7b726..4f462cf 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
@@ -1792,12 +1792,7 @@
         }
         Goto gotoExit = new Goto();
         gotoExit.setBlock(block);
-        if (options.debug) {
-          for (Value value : ret.getDebugValues()) {
-            gotoExit.addDebugValue(value);
-            value.removeDebugUser(ret);
-          }
-        }
+        ret.moveDebugValues(gotoExit);
         instructions.set(instructions.size() - 1, gotoExit);
         block.link(normalExitBlock);
         gotoExit.setTarget(normalExitBlock);
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 6cd453b..f4c51ce 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
@@ -197,7 +197,6 @@
       }
     }
 
-    clearUserInfo();
     assert code.isConsistentGraph();
     if (Log.ENABLED) {
       Log.debug(this.getClass(), toString());
@@ -206,6 +205,7 @@
     if (debug) {
       computeDebugInfo(blocks);
     }
+    clearUserInfo();
     clearState();
   }