diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index 2c3d9a5..b0ef472 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
@@ -1292,36 +1292,17 @@
       builder.append(": ");
       builder.append(instruction.toString());
       if (DebugLocalInfo.PRINT_LEVEL != PrintLevel.NONE) {
-        List<Value> localEnds = new ArrayList<>(instruction.getDebugValues().size());
-        List<Value> localStarts = new ArrayList<>(instruction.getDebugValues().size());
-        List<Value> localLive = new ArrayList<>(instruction.getDebugValues().size());
-        for (Value value : instruction.getDebugValues()) {
-          if (value.getDebugLocalEnds().contains(instruction)) {
-            localEnds.add(value);
-          } else if (value.getDebugLocalStarts().contains(instruction)) {
-            localStarts.add(value);
-          } else {
-            assert value.debugUsers().contains(instruction);
-            localLive.add(value);
-          }
+        if (!instruction.getDebugValues().isEmpty()) {
+          builder.append(" [end: ");
+          StringUtils.append(builder, instruction.getDebugValues(), ", ", BraceType.NONE);
+          builder.append("]");
         }
-        printDebugValueSet("live", localLive, builder);
-        printDebugValueSet("end", localEnds, builder);
-        printDebugValueSet("start", localStarts, builder);
       }
       builder.append("\n");
     }
     return builder.toString();
   }
 
-  private void printDebugValueSet(String header, List<Value> locals, StringBuilder builder) {
-    if (!locals.isEmpty()) {
-      builder.append(" [").append(header).append(": ");
-      StringUtils.append(builder, locals, ", ", BraceType.NONE);
-      builder.append("]");
-    }
-  }
-
   public void print(CfgPrinter printer) {
     printer.begin("block");
     printer.print("name \"B").append(number).append("\"\n");
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index a0af5e2..32e5dea 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -245,10 +245,14 @@
             liveStack.addLast(use);
           }
         }
-        assert instruction.getDebugValues().stream().allMatch(Value::needsRegister);
-        assert instruction.getDebugValues().stream().allMatch(Value::hasLocalInfo);
-        live.addAll(instruction.getDebugValues());
-        liveLocals.addAll(instruction.getDebugValues());
+        if (!instruction.getDebugValues().isEmpty()) {
+          ArrayList<Value> sortedValues = new ArrayList<>(instruction.getDebugValues());
+          sortedValues.sort(Value::compareTo);
+          assert sortedValues.stream().allMatch(Value::needsRegister);
+          assert sortedValues.stream().allMatch(Value::hasLocalInfo);
+          live.addAll(sortedValues);
+          liveLocals.addAll(sortedValues);
+        }
       }
       for (Phi phi : block.getPhis()) {
         if (phi.isValueOnStack()) {
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 9e25dcf..6e5dfa3 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
@@ -32,9 +32,9 @@
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.StringUtils.BraceType;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
 import java.util.ArrayList;
 import java.util.Iterator;
-import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Set;
 import java.util.function.Function;
@@ -45,7 +45,7 @@
   protected final List<Value> inValues = new ArrayList<>();
   private BasicBlock block = null;
   private int number = -1;
-  private LinkedHashSet<Value> debugValues = null;
+  private Set<Value> debugValues = null;
   private Position position = null;
 
   protected Instruction(Value outValue) {
@@ -154,11 +154,9 @@
   public void addDebugValue(Value value) {
     assert value.hasLocalInfo();
     if (debugValues == null) {
-      debugValues = new LinkedHashSet<>();
+      debugValues = Sets.newIdentityHashSet();
     }
-    if (debugValues.add(value)) {
-      value.addDebugUser(this);
-    }
+    debugValues.add(value);
   }
 
   public static void clearUserInfo(Instruction instruction) {
@@ -197,17 +195,19 @@
   }
 
   public void replaceDebugValue(Value oldValue, Value newValue) {
-    if (debugValues.remove(oldValue)) {
-      assert newValue.getLocalInfo() == oldValue.getLocalInfo()
-          : "Replacing debug values with inconsistent locals "
-              + oldValue.getLocalInfo()
-              + " and "
-              + newValue.getLocalInfo()
-              + ". This is likely a code transformation bug "
-              + "that has not taken local information into account";
-      if (newValue.hasLocalInfo()) {
-        addDebugValue(newValue);
-      }
+    assert oldValue.hasLocalInfo();
+    assert newValue.hasLocalInfo();
+    assert newValue.getLocalInfo() == oldValue.getLocalInfo()
+        : "Replacing debug values with inconsistent locals "
+            + oldValue.getLocalInfo()
+            + " and "
+            + newValue.getLocalInfo()
+            + ". This is likely a code transformation bug "
+            + "that has not taken local information into account";
+    boolean removed = debugValues.remove(oldValue);
+    assert removed;
+    if (removed && newValue.hasLocalInfo()) {
+      newValue.addDebugLocalEnd(this);
     }
   }
 
@@ -221,12 +221,6 @@
     debugValues.clear();
   }
 
-  public void moveDebugValue(Value value, Instruction target) {
-    assert debugValues.contains(value);
-    value.replaceDebugUser(this, target);
-    debugValues.remove(value);
-  }
-
   public void removeDebugValue(Value value) {
     assert value.hasLocalInfo();
     if (debugValues != null) {
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 f49c1e3..4b9b2d1 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
@@ -37,14 +37,10 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
 import it.unimi.dsi.fastutil.ints.IntList;
-import java.util.ArrayList;
 import java.util.Collections;
-import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedList;
-import java.util.List;
 import java.util.Map;
-import java.util.Map.Entry;
 import java.util.Set;
 import java.util.function.Consumer;
 import java.util.function.Predicate;
@@ -153,65 +149,13 @@
   private static class DebugData {
 
     final DebugLocalInfo local;
-    Map<Instruction, DebugUse> users = new HashMap<>();
+    Set<Instruction> users = Sets.newIdentityHashSet();
 
     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.
-  // TODO(b/157466079): Clean/remove the use markers. With the current local construction in the
-  //   IRBuilder, the only needed markers should be 'end' markers.
-  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();
-      }
-    }
-
-    static DebugUse join(DebugUse a, DebugUse b) {
-      if (a == LIVE_FINAL || b == LIVE_FINAL) {
-        return LIVE_FINAL;
-      }
-      if (a == b) {
-        return a;
-      }
-      if (a == LIVE) {
-        return b;
-      }
-      if (b == LIVE) {
-        return a;
-      }
-      assert (a == START && b == END) || (a == END && b == START);
-      return LIVE_FINAL;
-    }
-  }
-
   public static final int UNDEFINED_NUMBER = -1;
 
   public static final Value UNDEFINED = new Value(UNDEFINED_NUMBER, TypeElement.getBottom(), null);
@@ -328,62 +272,16 @@
     debugData = new DebugData(local);
   }
 
-  public void clearLocalInfo() {
-    assert debugData.users.isEmpty();
-    debugData = null;
-  }
-
-  public boolean hasSameOrNoLocal(Value other) {
-    assert other != null;
-    return hasLocalInfo()
-        ? other.getLocalInfo() == this.getLocalInfo()
-        : !other.hasLocalInfo();
-  }
-
-  public List<Instruction> getDebugLocalStarts() {
-    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() {
-    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.users.put(start, markStart(debugData.users.get(start)));
-  }
-
-  private DebugUse markStart(DebugUse use) {
-    assert use != null;
-    return use == null ? DebugUse.START : use.start();
+  public Set<Instruction> getDebugLocalEnds() {
+    return debugData == null
+        ? Collections.emptySet()
+        : Collections.unmodifiableSet(debugData.users);
   }
 
   public void addDebugLocalEnd(Instruction end) {
     assert end != null;
-    debugData.users.put(end, markEnd(debugData.users.get(end)));
-  }
-
-  private DebugUse markEnd(DebugUse use) {
-    assert use != null;
-    return use == null ? DebugUse.END : use.end();
+    debugData.users.add(end);
+    end.addDebugValue(this);
   }
 
   public void linkTo(Value other) {
@@ -493,7 +391,7 @@
   }
 
   public Set<Instruction> debugUsers() {
-    return debugData == null ? null : Collections.unmodifiableSet(debugData.users.keySet());
+    return debugData == null ? null : Collections.unmodifiableSet(debugData.users);
   }
 
   public boolean hasAnyUsers() {
@@ -620,11 +518,6 @@
     uniquePhiUsers = null;
   }
 
-  public void addDebugUser(Instruction user) {
-    assert hasLocalInfo();
-    debugData.users.putIfAbsent(user, DebugUse.LIVE);
-  }
-
   public boolean isUninitializedLocal() {
     return definition != null && definition.isDebugLocalUninitialized();
   }
@@ -686,7 +579,7 @@
       user.replaceOperand(this, newValue);
     }
     if (debugData != null) {
-      for (Entry<Instruction, DebugUse> user : debugData.users.entrySet()) {
+      for (Instruction user : debugData.users) {
         replaceUserInDebugData(user, newValue);
       }
       debugData.users.clear();
@@ -748,10 +641,10 @@
       }
     }
     if (debugData != null) {
-      Iterator<Entry<Instruction, DebugUse>> users = debugData.users.entrySet().iterator();
+      Iterator<Instruction> users = debugData.users.iterator();
       while (users.hasNext()) {
-        Entry<Instruction, DebugUse> user = users.next();
-        if (selectedInstructions.contains(user.getKey())) {
+        Instruction user = users.next();
+        if (selectedInstructions.contains(user)) {
           replaceUserInDebugData(user, newValue);
           users.remove();
         }
@@ -759,30 +652,18 @@
     }
   }
 
-  private void replaceUserInDebugData(Entry<Instruction, DebugUse> user, Value newValue) {
-    Instruction instruction = user.getKey();
-    DebugUse debugUse = user.getValue();
-    instruction.replaceDebugValue(this, newValue);
+  private void replaceUserInDebugData(Instruction user, Value newValue) {
+    user.replaceDebugValue(this, newValue);
     // If user is a DebugLocalRead and now has no debug values, we would like to remove it.
     // However, replaceUserInDebugData() is called in contexts where the instruction list is being
     // iterated, so we cannot remove user from the instruction list at this point.
-    if (newValue.hasLocalInfo()) {
-      DebugUse existing = newValue.debugData.users.get(instruction);
-      assert existing != null;
-      newValue.debugData.users.put(instruction, DebugUse.join(debugUse, existing));
-    }
   }
 
   public void replaceDebugUser(Instruction oldUser, Instruction newUser) {
-    DebugUse use = debugData.users.remove(oldUser);
-    if (use == DebugUse.START && newUser.outValue == this) {
-      // Register allocation requires that debug values are live at the entry to the instruction.
-      // Remove this debug use since it is starting at the instruction that defines it.
-      return;
-    }
-    if (use != null) {
-      newUser.addDebugValue(this);
-      debugData.users.put(newUser, use);
+    boolean removed = debugData.users.remove(oldUser);
+    assert removed;
+    if (removed) {
+      addDebugLocalEnd(newUser);
     }
   }
 
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 0dd98e2..60fcec2 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
@@ -2377,12 +2377,10 @@
     // Add a use if this instruction is overwriting a previous value of the same local.
     if (previousLocalValue != null && previousLocalValue.getLocalInfo() == ir.getLocalInfo()) {
       assert ir.outValue() != null;
-      ir.addDebugValue(previousLocalValue);
       previousLocalValue.addDebugLocalEnd(ir);
     }
     // Add reads of locals if any are pending.
     for (Value value : debugLocalEnds) {
-      ir.addDebugValue(value);
       value.addDebugLocalEnd(ir);
     }
     previousLocalValue = null;
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 172a6b3..3181f66 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
@@ -2232,7 +2232,6 @@
             instruction.outValue().replaceUsers(inValue);
             Value overwrittenLocal = instruction.removeDebugValue(localInfo);
             if (overwrittenLocal != null) {
-              inValue.definition.addDebugValue(overwrittenLocal);
               overwrittenLocal.addDebugLocalEnd(inValue.definition);
             }
             if (prevInstruction != null &&
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 7eddfcc..7af08f9 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
@@ -347,6 +347,7 @@
       while (instructionIterator.hasNext()) {
         Instruction instruction = instructionIterator.next();
         if (!instructionIterator.hasNext()) {
+          instruction.clearDebugValues();
           break;
         }