diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java
index 407717c..5f0bea9 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java
@@ -608,7 +608,7 @@
       }
 
       @Override
-      protected List<Void> getFinalStateForRoots(Collection<StringBuilderNode> roots) {
+      protected List<Void> getFinalStateForRoots(Collection<? extends StringBuilderNode> roots) {
         return null;
       }
 
diff --git a/src/main/java/com/android/tools/r8/optimize/proto/ProtoNormalizer.java b/src/main/java/com/android/tools/r8/optimize/proto/ProtoNormalizer.java
index a3f2d38..3c032b3 100644
--- a/src/main/java/com/android/tools/r8/optimize/proto/ProtoNormalizer.java
+++ b/src/main/java/com/android/tools/r8/optimize/proto/ProtoNormalizer.java
@@ -8,6 +8,7 @@
 
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexMethodSignature;
@@ -15,31 +16,35 @@
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexTypeList;
 import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
-import com.android.tools.r8.graph.ObjectAllocationInfoCollection;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.graph.proto.RewrittenPrototypeDescription;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.KeepMethodInfo;
+import com.android.tools.r8.utils.DepthFirstSearchWorkListBase.StatefulDepthFirstSearchWorkList;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.IterableUtils;
 import com.android.tools.r8.utils.MapUtils;
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.Timing;
+import com.android.tools.r8.utils.TraversalContinuation;
 import com.android.tools.r8.utils.WorkList;
 import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
 import com.android.tools.r8.utils.collections.DexMethodSignatureSet;
 import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
+import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
+import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
+import java.util.function.Function;
 
 public class ProtoNormalizer {
 
@@ -60,47 +65,93 @@
   private void run(ExecutorService executorService) throws ExecutionException {
     GlobalReservationState globalReservationState = computeGlobalReservationState(executorService);
 
-    // TODO(b/173398086): This uses a single LocalReservationState for the entire program. This
-    //  should process the strongly connected program components in parallel, each with their own
-    //  LocalReservationState.
-    LocalReservationState localReservationState = new LocalReservationState();
+    // To ensure we do not add collisions of method signatures when creating the new method
+    // signatures we keep a map of methods in the type hierarchy, similar to what we do for
+    // minification.
     ProtoNormalizerGraphLens.Builder lensBuilder = ProtoNormalizerGraphLens.builder(appView);
-    for (DexProgramClass clazz : appView.appInfo().classesWithDeterministicOrder()) {
-      Map<DexMethodSignature, DexMethodSignature> newInstanceInitializerSignatures =
-          computeNewInstanceInitializerSignatures(
-              clazz, localReservationState, globalReservationState);
-      clazz
-          .getMethodCollection()
-          .replaceMethods(
-              method -> {
-                DexMethodSignature methodSignature = method.getSignature();
-                DexMethodSignature newMethodSignature =
-                    method.isInstanceInitializer()
-                        ? newInstanceInitializerSignatures.get(methodSignature)
-                        : localReservationState.getAndReserveNewMethodSignature(
-                            methodSignature, dexItemFactory, globalReservationState);
-                if (methodSignature.equals(newMethodSignature)) {
-                  return method;
-                }
-                DexMethod newMethodReference = newMethodSignature.withHolder(clazz, dexItemFactory);
-                RewrittenPrototypeDescription prototypeChanges =
-                    lensBuilder.recordNewMethodSignature(method, newMethodReference);
-                // TODO(b/195112263): Assert that the method does not have any optimization info.
-                //  If/when enabling proto normalization after the final round of tree shaking, this
-                //  should simply clear the optimization info, or replace it by a
-                //  ThrowingMethodOptimizationInfo since we should never use the optimization info
-                //  after this point.
-                return method.toTypeSubstitutedMethod(
-                    newMethodReference,
-                    builder -> {
-                      if (!prototypeChanges.isEmpty()) {
-                        builder
-                            .apply(prototypeChanges.createParameterAnnotationsRemover(method))
-                            .setGenericSignature(MethodTypeSignature.noSignature());
-                      }
-                    });
-              });
-    }
+    new StatefulDepthFirstSearchWorkList<DexClass, LocalReservationState, Void>() {
+
+      @Override
+      @SuppressWarnings("ReturnValueIgnored")
+      protected TraversalContinuation<Void, LocalReservationState> process(
+          DFSNodeWithState<DexClass, LocalReservationState> node,
+          Function<DexClass, DFSNodeWithState<DexClass, LocalReservationState>> childNodeConsumer) {
+        DexClass clazz = node.getNode();
+        node.setState(new LocalReservationState());
+        if (clazz.getSuperType() != null) {
+          appView
+              .contextIndependentDefinitionForWithResolutionResult(clazz.getSuperType())
+              .forEachClassResolutionResult(childNodeConsumer::apply);
+        }
+        return TraversalContinuation.doContinue();
+      }
+
+      @Override
+      protected TraversalContinuation<Void, LocalReservationState> joiner(
+          DFSNodeWithState<DexClass, LocalReservationState> node,
+          List<DFSNodeWithState<DexClass, LocalReservationState>> childStates) {
+        DexClass clazz = node.getNode();
+        assert childStates.size() >= 1
+            || clazz.getType() == dexItemFactory.objectType
+            || clazz.hasMissingSuperType(appView.appInfo());
+        // We can have multiple child states if there are multiple definitions of a class.
+        assert childStates.size() <= 1 || options.loadAllClassDefinitions;
+        LocalReservationState localReservationState = node.getState();
+        if (!childStates.isEmpty()) {
+          localReservationState.linkParent(childStates.get(0).getState());
+        }
+        Map<DexMethodSignature, DexMethodSignature> newInstanceInitializerSignatures =
+            clazz.isProgramClass()
+                ? computeNewInstanceInitializerSignatures(
+                    clazz.asProgramClass(), localReservationState, globalReservationState)
+                : null;
+        clazz
+            .getMethodCollection()
+            .replaceMethods(
+                method -> {
+                  DexMethodSignature methodSignature = method.getSignature();
+                  if (!clazz.isProgramClass()) {
+                    // We cannot change the signature of the method. Record it to ensure we do not
+                    // change a program signature in a sub class to override this.
+                    localReservationState.recordNoSignatureChange(methodSignature, dexItemFactory);
+                    return method;
+                  } else {
+                    assert newInstanceInitializerSignatures != null;
+                    DexMethodSignature newMethodSignature =
+                        method.isInstanceInitializer()
+                            ? newInstanceInitializerSignatures.get(methodSignature)
+                            : localReservationState.getAndReserveNewMethodSignature(
+                                methodSignature, dexItemFactory, globalReservationState);
+                    if (methodSignature.equals(newMethodSignature)) {
+                      // This method could not be optimized, record it as identity mapping to ensure
+                      // we keep it going forward.
+                      localReservationState.recordNoSignatureChange(
+                          methodSignature, dexItemFactory);
+                      return method;
+                    }
+                    DexMethod newMethodReference =
+                        newMethodSignature.withHolder(clazz.asProgramClass(), dexItemFactory);
+                    RewrittenPrototypeDescription prototypeChanges =
+                        lensBuilder.recordNewMethodSignature(method, newMethodReference);
+                    // TODO(b/195112263): Assert that the method does not have optimization info.
+                    // If/when enabling proto normalization after the final round of tree shaking,
+                    // this should simply clear the optimization info, or replace it by a
+                    // ThrowingMethodOptimizationInfo since we should never use the optimization
+                    // info after this point.
+                    return method.toTypeSubstitutedMethod(
+                        newMethodReference,
+                        builder -> {
+                          if (!prototypeChanges.isEmpty()) {
+                            builder
+                                .apply(prototypeChanges.createParameterAnnotationsRemover(method))
+                                .setGenericSignature(MethodTypeSignature.noSignature());
+                          }
+                        });
+                  }
+                });
+        return TraversalContinuation.doContinue(localReservationState);
+      }
+    }.run(appView.appInfo().classesWithDeterministicOrder());
 
     if (!lensBuilder.isEmpty()) {
       appView.rewriteWithLens(lensBuilder.build());
@@ -331,15 +382,13 @@
     if (appInfo.isBootstrapMethod(method)) {
       return true;
     }
-    ObjectAllocationInfoCollection objectAllocationInfoCollection =
-        appInfo.getObjectAllocationInfoCollection();
-    if (method.getHolder().isInterface()
+    // As long as we do not consider interface method and overrides as optimizable we can change
+    // method signatures in a top-down traversal.
+    return method.getHolder().isInterface()
         && method.getDefinition().isAbstract()
-        && objectAllocationInfoCollection.isImmediateInterfaceOfInstantiatedLambda(
-            method.getHolder())) {
-      return true;
-    }
-    return false;
+        && appInfo
+            .getObjectAllocationInfoCollection()
+            .isImmediateInterfaceOfInstantiatedLambda(method.getHolder());
   }
 
   static class GlobalReservationState {
@@ -389,8 +438,10 @@
 
   static class LocalReservationState {
 
-    MutableBidirectionalOneToOneMap<DexMethodSignature, DexMethodSignature> newMethodSignatures =
-        new BidirectionalOneToOneHashMap<>();
+    private final List<LocalReservationState> parents = new ArrayList<>(2);
+
+    private final MutableBidirectionalOneToOneMap<DexMethodSignature, DexMethodSignature>
+        newMethodSignatures = new BidirectionalOneToOneHashMap<>();
 
     DexMethodSignature getNewMethodSignature(
         DexMethodSignature methodSignature,
@@ -414,33 +465,68 @@
         GlobalReservationState globalReservationState,
         boolean reserve) {
       if (globalReservationState.isUnoptimizable(methodSignature)) {
-        assert !newMethodSignatures.containsKey(methodSignature);
+        assert getReserved(methodSignature) == null
+            || methodSignature.equals(getReserved(methodSignature));
         return methodSignature;
       }
-      DexMethodSignature reservedSignature = newMethodSignatures.get(methodSignature);
+      DexMethodSignature reservedSignature = getReserved(methodSignature);
       if (reservedSignature != null) {
-        assert reservedSignature
-            .getParameters()
-            .equals(globalReservationState.getReservedParameters(methodSignature));
         return reservedSignature;
       }
       DexTypeList reservedParameters =
           globalReservationState.getReservedParameters(methodSignature);
       DexMethodSignature newMethodSignature =
           methodSignature.withParameters(reservedParameters, dexItemFactory);
-      if (newMethodSignatures.containsValue(newMethodSignature)) {
+      if (isDestinationTaken(newMethodSignature)) {
         int index = 1;
         String newMethodBaseName = methodSignature.getName().toString();
         do {
           DexString newMethodName = dexItemFactory.createString(newMethodBaseName + "$" + index);
           newMethodSignature = newMethodSignature.withName(newMethodName);
           index++;
-        } while (newMethodSignatures.containsValue(newMethodSignature));
+        } while (isDestinationTaken(newMethodSignature));
       }
       if (reserve) {
         newMethodSignatures.put(methodSignature, newMethodSignature);
       }
       return newMethodSignature;
     }
+
+    private void linkParent(LocalReservationState parent) {
+      this.parents.add(parent);
+    }
+
+    private DexMethodSignature getReserved(DexMethodSignature signature) {
+      WorkList<LocalReservationState> workList = WorkList.newIdentityWorkList(this);
+      while (workList.hasNext()) {
+        LocalReservationState localReservationState = workList.next();
+        DexMethodSignature reservedSignature =
+            localReservationState.newMethodSignatures.get(signature);
+        if (reservedSignature != null) {
+          return reservedSignature;
+        }
+        workList.addIfNotSeen(localReservationState.parents);
+      }
+      return null;
+    }
+
+    private boolean isDestinationTaken(DexMethodSignature signature) {
+      WorkList<LocalReservationState> workList = WorkList.newIdentityWorkList(this);
+      while (workList.hasNext()) {
+        LocalReservationState localReservationState = workList.next();
+        if (localReservationState.newMethodSignatures.containsValue(signature)) {
+          return true;
+        }
+        workList.addIfNotSeen(localReservationState.parents);
+      }
+      return false;
+    }
+
+    public void recordNoSignatureChange(
+        DexMethodSignature methodSignature, DexItemFactory factory) {
+      if (!methodSignature.getName().equals(factory.constructorMethodName)) {
+        newMethodSignatures.put(methodSignature, methodSignature);
+      }
+    }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/utils/DepthFirstSearchWorkListBase.java b/src/main/java/com/android/tools/r8/utils/DepthFirstSearchWorkListBase.java
index 37a55bb..a4d1c8f 100644
--- a/src/main/java/com/android/tools/r8/utils/DepthFirstSearchWorkListBase.java
+++ b/src/main/java/com/android/tools/r8/utils/DepthFirstSearchWorkListBase.java
@@ -115,7 +115,7 @@
   /** The joining of state during backtracking of the algorithm. */
   abstract TraversalContinuation<TB, TC> internalOnJoin(T node);
 
-  protected abstract List<TC> getFinalStateForRoots(Collection<N> roots);
+  protected abstract List<TC> getFinalStateForRoots(Collection<? extends N> roots);
 
   final T internalEnqueueNode(N value) {
     T dfsNode = nodeToNodeWithStateMap.computeIfAbsent(value, this::createDfsNode);
@@ -138,7 +138,7 @@
     return run(Arrays.asList(roots));
   }
 
-  public final TraversalContinuation<TB, List<TC>> run(Collection<N> roots) {
+  public final TraversalContinuation<TB, List<TC>> run(Collection<? extends N> roots) {
     roots.forEach(this::internalEnqueueNode);
     while (!workList.isEmpty()) {
       T node = workList.removeLast();
@@ -199,7 +199,7 @@
     }
 
     @Override
-    protected List<TC> getFinalStateForRoots(Collection<N> roots) {
+    protected List<TC> getFinalStateForRoots(Collection<? extends N> roots) {
       return null;
     }
   }
@@ -264,7 +264,7 @@
     }
 
     @Override
-    public List<S> getFinalStateForRoots(Collection<N> roots) {
+    public List<S> getFinalStateForRoots(Collection<? extends N> roots) {
       return ListUtils.map(roots, root -> getNodeStateForNode(root).state);
     }
   }
diff --git a/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationDestinationOverrideLibraryTest.java b/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationDestinationOverrideLibraryTest.java
index 3b7a115..f58336a 100644
--- a/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationDestinationOverrideLibraryTest.java
+++ b/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationDestinationOverrideLibraryTest.java
@@ -4,10 +4,6 @@
 
 package com.android.tools.r8.optimize.proto;
 
-import static org.hamcrest.CoreMatchers.containsString;
-import static org.junit.Assert.assertThrows;
-
-import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.NoMethodStaticizing;
 import com.android.tools.r8.TestBase;
@@ -44,26 +40,19 @@
 
   @Test
   public void testR8() throws Exception {
-    // TODO(b/258720808): We should not fail compilation.
-    assertThrows(
-        CompilationFailedException.class,
-        () ->
-            testForR8(parameters.getBackend())
-                .addProgramClasses(Main.class, ProgramClass.class, X.class)
-                .addDefaultRuntimeLibrary(parameters)
-                .addLibraryClasses(LibraryClass.class)
-                .setMinApi(parameters.getApiLevel())
-                .addKeepMainRule(Main.class)
-                .addDontObfuscate()
-                .enableInliningAnnotations()
-                .enableNoMethodStaticizingAnnotations()
-                .compileWithExpectedDiagnostics(
-                    diagnostics -> {
-                      diagnostics.assertErrorMessageThatMatches(
-                          containsString(
-                              "went from not overriding a library method to overriding a library"
-                                  + " method"));
-                    }));
+    testForR8(parameters.getBackend())
+        .addProgramClasses(Main.class, ProgramClass.class, X.class)
+        .addDefaultRuntimeLibrary(parameters)
+        .addLibraryClasses(LibraryClass.class)
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMainRule(Main.class)
+        .addDontObfuscate()
+        .enableInliningAnnotations()
+        .enableNoMethodStaticizingAnnotations()
+        .compile()
+        .addBootClasspathClasses(LibraryClass.class)
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(EXPECTED);
   }
 
   public static class LibraryClass {
diff --git a/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationDuplicateMethodTest.java b/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationDuplicateMethodTest.java
index 899ca4d..c935224 100644
--- a/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationDuplicateMethodTest.java
+++ b/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationDuplicateMethodTest.java
@@ -4,10 +4,6 @@
 
 package com.android.tools.r8.optimize.proto;
 
-import static org.hamcrest.CoreMatchers.containsString;
-import static org.junit.Assert.assertThrows;
-
-import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.TestBase;
@@ -42,24 +38,17 @@
 
   @Test
   public void testR8() throws Exception {
-    // TODO(b/258720808): We should not cause collision with an existing method.
-    assertThrows(
-        CompilationFailedException.class,
-        () -> {
-          testForR8(parameters.getBackend())
-              .addInnerClasses(getClass())
-              .setMinApi(parameters.getApiLevel())
-              .addKeepMainRule(Main.class)
-              .addKeepMethodRules(
-                  Reference.methodFromMethod(
-                      B.class.getDeclaredMethod("foo$1", int.class, int.class, String.class)))
-              .enableInliningAnnotations()
-              .enableNoHorizontalClassMergingAnnotations()
-              .compileWithExpectedDiagnostics(
-                  diagnostics ->
-                      diagnostics.assertErrorMessageThatMatches(
-                          containsString("Duplicate method")));
-        });
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .setMinApi(parameters.getApiLevel())
+        .addKeepMainRule(Main.class)
+        .addKeepMethodRules(
+            Reference.methodFromMethod(
+                B.class.getDeclaredMethod("foo$1", int.class, int.class, String.class)))
+        .enableInliningAnnotations()
+        .enableNoHorizontalClassMergingAnnotations()
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(EXPECTED);
   }
 
   @NoHorizontalClassMerging
diff --git a/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationIntroduceCollisionTest.java b/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationIntroduceCollisionTest.java
index f4b8ccd..947e3e7 100644
--- a/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationIntroduceCollisionTest.java
+++ b/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationIntroduceCollisionTest.java
@@ -19,7 +19,6 @@
 public class ProtoNormalizationIntroduceCollisionTest extends TestBase {
 
   private final String[] EXPECTED = new String[] {"Base::foo-42Calling B::foo1337"};
-  private final String[] R8_EXPECTED = new String[] {"Sub::foo-Calling B::foo421337"};
 
   @Parameter() public TestParameters parameters;
 
@@ -46,8 +45,7 @@
         .enableInliningAnnotations()
         .enableNoVerticalClassMergingAnnotations()
         .run(parameters.getRuntime(), Main.class)
-        // TODO(b/258720808): We should produce the expected result.
-        .assertSuccessWithOutputLines(R8_EXPECTED);
+        .assertSuccessWithOutputLines(EXPECTED);
   }
 
   public static class Base {
diff --git a/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationWithVirtualMethodCollisionTest.java b/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationWithVirtualMethodCollisionTest.java
index c179493..c3997c9 100644
--- a/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationWithVirtualMethodCollisionTest.java
+++ b/src/test/java/com/android/tools/r8/optimize/proto/ProtoNormalizationWithVirtualMethodCollisionTest.java
@@ -36,9 +36,6 @@
   private final String[] EXPECTED =
       new String[] {"A::foo", "B", "A", "B::foo", "B", "A", "B::foo", "B", "A"};
 
-  private final String[] R8_EXPECTED =
-      new String[] {"A::foo", "B", "A", "A::foo", "B", "A", "B::foo", "B", "A"};
-
   @Test
   public void testRuntime() throws Exception {
     testForRuntime(parameters)
@@ -59,8 +56,7 @@
         .setMinApi(parameters.getApiLevel())
         .compile()
         .run(parameters.getRuntime(), Main.class)
-        // TODO(b/258720808): We should not produce incorrect results.
-        .assertSuccessWithOutputLines(R8_EXPECTED)
+        .assertSuccessWithOutputLines(EXPECTED)
         .inspect(
             inspector -> {
               ClassSubject bClassSubject = inspector.clazz(B.class);
@@ -72,7 +68,7 @@
               TypeSubject bTypeSubject = bClassSubject.asTypeSubject();
               TypeSubject aTypeSubject = aClassSubject.asTypeSubject();
 
-              MethodSubject fooMethodSubject = aClassSubject.uniqueMethodWithOriginalName("foo");
+              MethodSubject fooMethodSubject = aClassSubject.uniqueMethodWithFinalName("foo$1");
               assertThat(fooMethodSubject, isPresent());
               assertThat(fooMethodSubject, hasParameters(aTypeSubject, bTypeSubject));