diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 4b23ef3..0182e69 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -484,14 +484,14 @@
           if (options.enableUninstantiatedTypeOptimization) {
             timing.begin("UninstantiatedTypeOptimization");
             appView.setGraphLense(
-                new UninstantiatedTypeOptimization(appViewWithLiveness, options)
-                    .run(new MethodPoolCollection(application), executorService, timing));
+                new UninstantiatedTypeOptimization(appViewWithLiveness)
+                    .run(new MethodPoolCollection(appView), executorService, timing));
             application = application.asDirect().rewrittenWithLense(appView.graphLense());
-            timing.end();
             appViewWithLiveness.setAppInfo(
                 appViewWithLiveness
                     .appInfo()
                     .rewrittenWithLense(application.asDirect(), appView.graphLense()));
+            timing.end();
           }
         }
 
diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index bb835e0..4b0f4b8 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.4.91";
+  public static final String LABEL = "1.4.92";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
index 084ad80..f6851fd 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -8,7 +8,7 @@
 import com.android.tools.r8.shaking.VerticalClassMerger.VerticallyMergedClasses;
 import com.android.tools.r8.utils.InternalOptions;
 
-public class AppView<T extends AppInfo> {
+public class AppView<T extends AppInfo> implements DexDefinitionSupplier {
 
   private T appInfo;
   private AppServices appServices;
@@ -40,6 +40,27 @@
     this.appServices = appServices;
   }
 
+  @Override
+  public final DexDefinition definitionFor(DexReference reference) {
+    return appInfo().definitionFor(reference);
+  }
+
+  @Override
+  public final DexEncodedField definitionFor(DexField field) {
+    return appInfo().definitionFor(field);
+  }
+
+  @Override
+  public final DexEncodedMethod definitionFor(DexMethod method) {
+    return appInfo().definitionFor(method);
+  }
+
+  @Override
+  public final DexClass definitionFor(DexType type) {
+    return appInfo().definitionFor(type);
+  }
+
+  @Override
   public DexItemFactory dexItemFactory() {
     return dexItemFactory;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexDefinitionSupplier.java b/src/main/java/com/android/tools/r8/graph/DexDefinitionSupplier.java
new file mode 100644
index 0000000..7d9888e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/DexDefinitionSupplier.java
@@ -0,0 +1,18 @@
+// Copyright (c) 2019, 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.graph;
+
+public interface DexDefinitionSupplier {
+
+  DexDefinition definitionFor(DexReference reference);
+
+  DexEncodedField definitionFor(DexField field);
+
+  DexEncodedMethod definitionFor(DexMethod method);
+
+  DexClass definitionFor(DexType type);
+
+  DexItemFactory dexItemFactory();
+}
diff --git a/src/main/java/com/android/tools/r8/graph/TopDownClassHierarchyTraversal.java b/src/main/java/com/android/tools/r8/graph/TopDownClassHierarchyTraversal.java
index e8d6a4f..14c98e4 100644
--- a/src/main/java/com/android/tools/r8/graph/TopDownClassHierarchyTraversal.java
+++ b/src/main/java/com/android/tools/r8/graph/TopDownClassHierarchyTraversal.java
@@ -11,59 +11,93 @@
 import java.util.Set;
 import java.util.function.Consumer;
 
-public class TopDownClassHierarchyTraversal {
+public class TopDownClassHierarchyTraversal<T extends DexClass> {
 
-  public static void visit(
-      AppView<? extends AppInfo> appView,
-      Iterable<DexProgramClass> classes,
-      Consumer<DexProgramClass> visitor) {
-    Deque<DexProgramClass> worklist = new ArrayDeque<>();
-    Set<DexProgramClass> visited = new HashSet<>();
+  private enum Scope {
+    ALL_CLASSES,
+    ONLY_PROGRAM_CLASSES
+  }
 
-    Iterator<DexProgramClass> classIterator = classes.iterator();
+  private final DexDefinitionSupplier definitions;
+  private final Scope scope;
+
+  private final Set<T> visited = new HashSet<>();
+  private final Deque<T> worklist = new ArrayDeque<>();
+
+  private TopDownClassHierarchyTraversal(DexDefinitionSupplier definitions, Scope scope) {
+    this.definitions = definitions;
+    this.scope = scope;
+  }
+
+  /**
+   * Returns a visitor that can be used to visit all the classes (including class path and library
+   * classes) that are reachable from a given set of sources.
+   */
+  public static TopDownClassHierarchyTraversal<DexClass> forAllClasses(
+      DexDefinitionSupplier definitions) {
+    return new TopDownClassHierarchyTraversal<>(definitions, Scope.ALL_CLASSES);
+  }
+
+  /**
+   * Returns a visitor that can be used to visit all the program classes that are reachable from a
+   * given set of sources.
+   */
+  public static TopDownClassHierarchyTraversal<DexProgramClass> forProgramClasses(
+      DexDefinitionSupplier definitions) {
+    return new TopDownClassHierarchyTraversal<>(definitions, Scope.ONLY_PROGRAM_CLASSES);
+  }
+
+  public void visit(Iterable<DexProgramClass> sources, Consumer<T> visitor) {
+    Iterator<DexProgramClass> sourceIterator = sources.iterator();
 
     // Visit the program classes in a top-down order according to the class hierarchy.
-    while (classIterator.hasNext() || !worklist.isEmpty()) {
+    while (sourceIterator.hasNext() || !worklist.isEmpty()) {
       if (worklist.isEmpty()) {
-        // Add the ancestors of this class (including the class itself) to the worklist in such a
-        // way that all super types of the class come before the class itself.
-        addAncestorsToWorklist(classIterator.next(), worklist, visited, appView);
+        // Add the ancestors of the next source (including the source itself) to the worklist in
+        // such a way that all super types of the source class come before the class itself.
+        addAncestorsToWorklist(sourceIterator.next());
         if (worklist.isEmpty()) {
           continue;
         }
       }
 
-      DexProgramClass clazz = worklist.removeFirst();
+      T clazz = worklist.removeFirst();
       if (visited.add(clazz)) {
+        assert scope != Scope.ONLY_PROGRAM_CLASSES || clazz.isProgramClass();
         visitor.accept(clazz);
       }
     }
+
+    visited.clear();
   }
 
-  private static void addAncestorsToWorklist(
-      DexProgramClass clazz,
-      Deque<DexProgramClass> worklist,
-      Set<DexProgramClass> visited,
-      AppView<? extends AppInfo> appView) {
-    if (visited.contains(clazz)) {
+  private void addAncestorsToWorklist(DexClass clazz) {
+    @SuppressWarnings("unchecked")
+    T clazzWithTypeT = (T) clazz;
+
+    if (visited.contains(clazzWithTypeT)) {
       return;
     }
 
-    worklist.addFirst(clazz);
+    worklist.addFirst(clazzWithTypeT);
 
     // Add super classes to worklist.
     if (clazz.superType != null) {
-      DexClass definition = appView.appInfo().definitionFor(clazz.superType);
-      if (definition != null && definition.isProgramClass()) {
-        addAncestorsToWorklist(definition.asProgramClass(), worklist, visited, appView);
+      DexClass definition = definitions.definitionFor(clazz.superType);
+      if (definition != null) {
+        if (scope != Scope.ONLY_PROGRAM_CLASSES || definition.isProgramClass()) {
+          addAncestorsToWorklist(definition);
+        }
       }
     }
 
     // Add super interfaces to worklist.
     for (DexType interfaceType : clazz.interfaces.values) {
-      DexClass definition = appView.appInfo().definitionFor(interfaceType);
-      if (definition != null && definition.isProgramClass()) {
-        addAncestorsToWorklist(definition.asProgramClass(), worklist, visited, appView);
+      DexClass definition = definitions.definitionFor(interfaceType);
+      if (definition != null) {
+        if (scope != Scope.ONLY_PROGRAM_CLASSES || definition.isProgramClass()) {
+          addAncestorsToWorklist(definition);
+        }
       }
     }
   }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index 32fc687..2adc697 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -194,7 +194,7 @@
     if (enableWholeProgramOptimizations) {
       assert appInfo.hasLiveness();
       AppInfoWithLiveness appInfoWithLiveness = appInfo.withLiveness();
-      AppView<? extends AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
+      AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
       assert rootSet != null;
       this.nonNullTracker = new NonNullTracker(
           appInfoWithLiveness, libraryMethodsReturningNonNull(appInfo.dexItemFactory));
@@ -213,7 +213,7 @@
           options.enableDevirtualization ? new Devirtualizer(appViewWithLiveness) : null;
       this.uninstantiatedTypeOptimization =
           options.enableUninstantiatedTypeOptimization
-              ? new UninstantiatedTypeOptimization(appViewWithLiveness, options)
+              ? new UninstantiatedTypeOptimization(appViewWithLiveness)
               : null;
       this.typeChecker = new TypeChecker(appView);
     } else {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java
index 26dee92..52de259 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/MethodPoolCollection.java
@@ -4,7 +4,8 @@
 
 package com.android.tools.r8.ir.optimize;
 
-import com.android.tools.r8.graph.DexApplication;
+import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
@@ -34,19 +35,18 @@
 
   private static final Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get();
 
-  private final DexApplication application;
+  private final AppView<? extends AppInfo> appView;
   private final Map<DexClass, MethodPool> methodPools = new ConcurrentHashMap<>();
 
-  public MethodPoolCollection(DexApplication application) {
-    this.application = application;
+  public MethodPoolCollection(AppView<? extends AppInfo> appView) {
+    this.appView = appView;
   }
 
   public void buildAll(ExecutorService executorService, Timing timing) throws ExecutionException {
     timing.begin("Building method pool collection");
     try {
       List<Future<?>> futures = new ArrayList<>();
-      @SuppressWarnings("unchecked")
-      List<DexClass> classes = (List) application.classes();
+      Iterable<? extends DexClass> classes = appView.appInfo().classes();
       submitAll(classes, futures, executorService);
       ThreadUtils.awaitFutures(futures);
     } finally {
@@ -85,7 +85,9 @@
   }
 
   private void submitAll(
-      Iterable<DexClass> classes, List<Future<?>> futures, ExecutorService executorService) {
+      Iterable<? extends DexClass> classes,
+      List<Future<?>> futures,
+      ExecutorService executorService) {
     for (DexClass clazz : classes) {
       futures.add(executorService.submit(computeMethodPoolPerClass(clazz)));
     }
@@ -102,7 +104,7 @@
             }
           });
       if (clazz.superType != null) {
-        DexClass superClazz = application.definitionFor(clazz.superType);
+        DexClass superClazz = appView.definitionFor(clazz.superType);
         if (superClazz != null) {
           MethodPool superPool = methodPools.computeIfAbsent(superClazz, k -> new MethodPool());
           superPool.linkSubtype(methodPool);
@@ -111,9 +113,10 @@
       }
       if (clazz.isInterface()) {
         for (DexType subtype : clazz.type.allImmediateSubtypes()) {
-          DexClass subClazz = application.definitionFor(subtype);
+          DexClass subClazz = appView.definitionFor(subtype);
           if (subClazz != null) {
             MethodPool childPool = methodPools.computeIfAbsent(subClazz, k -> new MethodPool());
+            methodPool.linkSubtype(childPool);
             childPool.linkInterface(methodPool);
           }
         }
@@ -133,10 +136,10 @@
       }
       if (superTypes.add(clazz)) {
         if (clazz.superType != null) {
-          addNonNull(worklist, application.definitionFor(clazz.superType));
+          addNonNull(worklist, appView.definitionFor(clazz.superType));
         }
         for (DexType interfaceType : clazz.interfaces.values) {
-          addNonNull(worklist, application.definitionFor(interfaceType));
+          addNonNull(worklist, appView.definitionFor(interfaceType));
         }
       }
     }
@@ -147,20 +150,18 @@
       DexClass subject, Predicate<DexClass> stoppingCriterion) {
     Set<DexClass> subTypes = new HashSet<>();
     Deque<DexClass> worklist = new ArrayDeque<>();
-    subject.type.forAllExtendsSubtypes(
-        type -> addNonNull(worklist, application.definitionFor(type)));
+    subject.type.forAllExtendsSubtypes(type -> addNonNull(worklist, appView.definitionFor(type)));
     subject.type.forAllImplementsSubtypes(
-        type -> addNonNull(worklist, application.definitionFor(type)));
+        type -> addNonNull(worklist, appView.definitionFor(type)));
     while (!worklist.isEmpty()) {
       DexClass clazz = worklist.pop();
       if (stoppingCriterion.test(clazz)) {
         continue;
       }
       if (subTypes.add(clazz)) {
-        clazz.type.forAllExtendsSubtypes(
-            type -> addNonNull(worklist, application.definitionFor(type)));
+        clazz.type.forAllExtendsSubtypes(type -> addNonNull(worklist, appView.definitionFor(type)));
         clazz.type.forAllImplementsSubtypes(
-            type -> addNonNull(worklist, application.definitionFor(type)));
+            type -> addNonNull(worklist, appView.definitionFor(type)));
       }
     }
     return subTypes;
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java b/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
index 7385237..c0d0266 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
@@ -15,6 +15,7 @@
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.GraphLense;
@@ -39,7 +40,6 @@
 import com.android.tools.r8.ir.optimize.MethodPoolCollection.MethodPool;
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
-import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.MethodSignatureEquivalence;
 import com.android.tools.r8.utils.Timing;
 import com.google.common.base.Equivalence.Wrapper;
@@ -104,29 +104,20 @@
     }
   }
 
+  private static final MethodSignatureEquivalence equivalence = MethodSignatureEquivalence.get();
+
   private final AppView<? extends AppInfoWithLiveness> appView;
-  private final DexItemFactory dexItemFactory;
-  private final InternalOptions options;
 
   private int numberOfInstanceGetOrInstancePutWithNullReceiver = 0;
   private int numberOfInvokesWithNullArgument = 0;
   private int numberOfInvokesWithNullReceiver = 0;
 
-  public UninstantiatedTypeOptimization(
-      AppView<? extends AppInfoWithLiveness> appView, InternalOptions options) {
+  public UninstantiatedTypeOptimization(AppView<AppInfoWithLiveness> appView) {
     this.appView = appView;
-    this.dexItemFactory = appView.dexItemFactory();
-    this.options = options;
   }
 
   public GraphLense run(
       MethodPoolCollection methodPoolCollection, ExecutorService executorService, Timing timing) {
-    BiMap<DexMethod, DexMethod> methodMapping = HashBiMap.create();
-    Map<DexMethod, RemovedArgumentsInfo> removedArgumentsInfoPerMethod = new IdentityHashMap<>();
-
-    MethodSignatureEquivalence equivalence = MethodSignatureEquivalence.get();
-
-    Map<Wrapper<DexMethod>, Set<DexType>> changedVirtualMethods = new HashMap<>();
 
     try {
       methodPoolCollection.buildAll(executorService, timing);
@@ -134,135 +125,21 @@
       throw new RuntimeException(e);
     }
 
-    TopDownClassHierarchyTraversal.visit(
-        appView,
-        appView.appInfo().classes(),
-        clazz -> {
-          MethodPool methodPool = methodPoolCollection.get(clazz);
+    Map<Wrapper<DexMethod>, Set<DexType>> changedVirtualMethods = new HashMap<>();
+    BiMap<DexMethod, DexMethod> methodMapping = HashBiMap.create();
+    Map<DexMethod, RemovedArgumentsInfo> removedArgumentsInfoPerMethod = new IdentityHashMap<>();
 
-          if (clazz.isInterface()) {
-            // Do not allow changing the prototype of methods that override an interface method.
-            // This achieved by faking that there is already a method with the given signature.
-            for (DexEncodedMethod virtualMethod : clazz.virtualMethods()) {
-              RewrittenPrototypeDescription prototypeChanges =
-                  new RewrittenPrototypeDescription(
-                      isAlwaysNull(virtualMethod.method.proto.returnType),
-                      getRemovedArgumentsInfo(virtualMethod, ALLOW_ARGUMENT_REMOVAL));
-              if (!prototypeChanges.isEmpty()) {
-                DexMethod newMethod = getNewMethodSignature(virtualMethod, prototypeChanges);
-                Wrapper<DexMethod> wrapper = equivalence.wrap(newMethod);
-                if (!methodPool.hasSeenDirectly(wrapper)) {
-                  methodPool.seen(wrapper);
-                }
-              }
-            }
-            return;
-          }
+    TopDownClassHierarchyTraversal.forProgramClasses(appView)
+        .visit(
+            appView.appInfo().classes(),
+            clazz ->
+                processClass(
+                    clazz,
+                    changedVirtualMethods,
+                    methodMapping,
+                    methodPoolCollection,
+                    removedArgumentsInfoPerMethod));
 
-          Map<DexEncodedMethod, RewrittenPrototypeDescription> prototypeChangesPerMethod =
-              new IdentityHashMap<>();
-          for (DexEncodedMethod directMethod : clazz.directMethods()) {
-            RewrittenPrototypeDescription prototypeChanges =
-                getPrototypeChanges(directMethod, ALLOW_ARGUMENT_REMOVAL);
-            if (!prototypeChanges.isEmpty()) {
-              prototypeChangesPerMethod.put(directMethod, prototypeChanges);
-            }
-          }
-
-          // Reserve all signatures which are known to not be touched below.
-          Set<Wrapper<DexMethod>> usedSignatures = new HashSet<>();
-          for (DexEncodedMethod method : clazz.methods()) {
-            if (!prototypeChangesPerMethod.containsKey(method)) {
-              usedSignatures.add(equivalence.wrap(method.method));
-            }
-          }
-
-          // Change the return type of direct methods that return an uninstantiated type to void.
-          List<DexEncodedMethod> directMethods = clazz.directMethods();
-          for (int i = 0; i < directMethods.size(); ++i) {
-            DexEncodedMethod encodedMethod = directMethods.get(i);
-            DexMethod method = encodedMethod.method;
-            RewrittenPrototypeDescription prototypeChanges =
-                prototypeChangesPerMethod.getOrDefault(
-                    encodedMethod, RewrittenPrototypeDescription.none());
-            RemovedArgumentsInfo removedArgumentsInfo = prototypeChanges.getRemovedArgumentsInfo();
-            DexMethod newMethod = getNewMethodSignature(encodedMethod, prototypeChanges);
-            if (newMethod != method) {
-              Wrapper<DexMethod> wrapper = equivalence.wrap(newMethod);
-
-              // TODO(b/110806787): Can be extended to handle collisions by renaming the given
-              // method.
-              if (usedSignatures.add(wrapper)) {
-                clazz.setDirectMethod(i, encodedMethod.toTypeSubstitutedMethod(newMethod));
-                methodMapping.put(method, newMethod);
-                if (removedArgumentsInfo.hasRemovedArguments()) {
-                  removedArgumentsInfoPerMethod.put(newMethod, removedArgumentsInfo);
-                }
-              }
-            }
-          }
-
-          // Change the return type of virtual methods that return an uninstantiated type to void.
-          // This is done in two steps. First we change the return type of all methods that override
-          // a method whose return type has already been changed to void previously. Note that
-          // all supertypes of the current class are always visited prior to the current class.
-          // This is important to ensure that a method that used to override a method in its super
-          // class will continue to do so after this optimization.
-          List<DexEncodedMethod> virtualMethods = clazz.virtualMethods();
-          for (int i = 0; i < virtualMethods.size(); ++i) {
-            DexEncodedMethod encodedMethod = virtualMethods.get(i);
-            DexMethod method = encodedMethod.method;
-            RewrittenPrototypeDescription prototypeChanges =
-                getPrototypeChanges(encodedMethod, DISALLOW_ARGUMENT_REMOVAL);
-            DexMethod newMethod = getNewMethodSignature(encodedMethod, prototypeChanges);
-            if (newMethod != method) {
-              Wrapper<DexMethod> wrapper = equivalence.wrap(newMethod);
-
-              boolean isOverrideOfPreviouslyChangedMethodInSuperClass =
-                  changedVirtualMethods.getOrDefault(equivalence.wrap(method), ImmutableSet.of())
-                      .stream()
-                      .anyMatch(other -> clazz.type.isSubtypeOf(other, appView.appInfo()));
-              if (isOverrideOfPreviouslyChangedMethodInSuperClass) {
-                assert methodPool.hasSeen(wrapper);
-
-                boolean signatureIsAvailable = usedSignatures.add(wrapper);
-                assert signatureIsAvailable;
-
-                clazz.setVirtualMethod(i, encodedMethod.toTypeSubstitutedMethod(newMethod));
-                methodMapping.put(method, newMethod);
-              }
-            }
-          }
-          for (int i = 0; i < virtualMethods.size(); ++i) {
-            DexEncodedMethod encodedMethod = virtualMethods.get(i);
-            DexMethod method = encodedMethod.method;
-            RewrittenPrototypeDescription prototypeChanges =
-                getPrototypeChanges(encodedMethod, DISALLOW_ARGUMENT_REMOVAL);
-            DexMethod newMethod = getNewMethodSignature(encodedMethod, prototypeChanges);
-            if (newMethod != method) {
-              Wrapper<DexMethod> wrapper = equivalence.wrap(newMethod);
-
-              // TODO(b/110806787): Can be extended to handle collisions by renaming the given
-              // method. Note that this also requires renaming all of the methods that override this
-              // method, though.
-              if (!methodPool.hasSeen(wrapper) && usedSignatures.add(wrapper)) {
-                methodPool.seen(wrapper);
-
-                clazz.setVirtualMethod(i, encodedMethod.toTypeSubstitutedMethod(newMethod));
-                methodMapping.put(method, newMethod);
-
-                boolean added =
-                    changedVirtualMethods
-                        .computeIfAbsent(equivalence.wrap(method), key -> Sets.newIdentityHashSet())
-                        .add(clazz.type);
-                assert added;
-              }
-            }
-          }
-        });
-
-    // TODO(christofferqa): There is no need to do anything at the call site when the graph lense
-    // is unchanged!
     if (!methodMapping.isEmpty()) {
       return new UninstantiatedTypeOptimizationGraphLense(
           methodMapping, removedArgumentsInfoPerMethod, appView);
@@ -270,6 +147,134 @@
     return appView.graphLense();
   }
 
+  private void processClass(
+      DexProgramClass clazz,
+      Map<Wrapper<DexMethod>, Set<DexType>> changedVirtualMethods,
+      BiMap<DexMethod, DexMethod> methodMapping,
+      MethodPoolCollection methodPoolCollection,
+      Map<DexMethod, RemovedArgumentsInfo> removedArgumentsInfoPerMethod) {
+    MethodPool methodPool = methodPoolCollection.get(clazz);
+
+    if (clazz.isInterface()) {
+      // Do not allow changing the prototype of methods that override an interface method.
+      // This achieved by faking that there is already a method with the given signature.
+      for (DexEncodedMethod virtualMethod : clazz.virtualMethods()) {
+        RewrittenPrototypeDescription prototypeChanges =
+            new RewrittenPrototypeDescription(
+                isAlwaysNull(virtualMethod.method.proto.returnType),
+                getRemovedArgumentsInfo(virtualMethod, ALLOW_ARGUMENT_REMOVAL));
+        if (!prototypeChanges.isEmpty()) {
+          DexMethod newMethod = getNewMethodSignature(virtualMethod, prototypeChanges);
+          Wrapper<DexMethod> wrapper = equivalence.wrap(newMethod);
+          if (!methodPool.hasSeenDirectly(wrapper)) {
+            methodPool.seen(wrapper);
+          }
+        }
+      }
+      return;
+    }
+
+    Map<DexEncodedMethod, RewrittenPrototypeDescription> prototypeChangesPerMethod =
+        new IdentityHashMap<>();
+    for (DexEncodedMethod directMethod : clazz.directMethods()) {
+      RewrittenPrototypeDescription prototypeChanges =
+          getPrototypeChanges(directMethod, ALLOW_ARGUMENT_REMOVAL);
+      if (!prototypeChanges.isEmpty()) {
+        prototypeChangesPerMethod.put(directMethod, prototypeChanges);
+      }
+    }
+
+    // Reserve all signatures which are known to not be touched below.
+    Set<Wrapper<DexMethod>> usedSignatures = new HashSet<>();
+    for (DexEncodedMethod method : clazz.methods()) {
+      if (!prototypeChangesPerMethod.containsKey(method)) {
+        usedSignatures.add(equivalence.wrap(method.method));
+      }
+    }
+
+    // Change the return type of direct methods that return an uninstantiated type to void.
+    List<DexEncodedMethod> directMethods = clazz.directMethods();
+    for (int i = 0; i < directMethods.size(); ++i) {
+      DexEncodedMethod encodedMethod = directMethods.get(i);
+      DexMethod method = encodedMethod.method;
+      RewrittenPrototypeDescription prototypeChanges =
+          prototypeChangesPerMethod.getOrDefault(
+              encodedMethod, RewrittenPrototypeDescription.none());
+      RemovedArgumentsInfo removedArgumentsInfo = prototypeChanges.getRemovedArgumentsInfo();
+      DexMethod newMethod = getNewMethodSignature(encodedMethod, prototypeChanges);
+      if (newMethod != method) {
+        Wrapper<DexMethod> wrapper = equivalence.wrap(newMethod);
+
+        // TODO(b/110806787): Can be extended to handle collisions by renaming the given
+        // method.
+        if (usedSignatures.add(wrapper)) {
+          clazz.setDirectMethod(i, encodedMethod.toTypeSubstitutedMethod(newMethod));
+          methodMapping.put(method, newMethod);
+          if (removedArgumentsInfo.hasRemovedArguments()) {
+            removedArgumentsInfoPerMethod.put(newMethod, removedArgumentsInfo);
+          }
+        }
+      }
+    }
+
+    // Change the return type of virtual methods that return an uninstantiated type to void.
+    // This is done in two steps. First we change the return type of all methods that override
+    // a method whose return type has already been changed to void previously. Note that
+    // all supertypes of the current class are always visited prior to the current class.
+    // This is important to ensure that a method that used to override a method in its super
+    // class will continue to do so after this optimization.
+    List<DexEncodedMethod> virtualMethods = clazz.virtualMethods();
+    for (int i = 0; i < virtualMethods.size(); ++i) {
+      DexEncodedMethod encodedMethod = virtualMethods.get(i);
+      DexMethod method = encodedMethod.method;
+      RewrittenPrototypeDescription prototypeChanges =
+          getPrototypeChanges(encodedMethod, DISALLOW_ARGUMENT_REMOVAL);
+      DexMethod newMethod = getNewMethodSignature(encodedMethod, prototypeChanges);
+      if (newMethod != method) {
+        Wrapper<DexMethod> wrapper = equivalence.wrap(newMethod);
+
+        boolean isOverrideOfPreviouslyChangedMethodInSuperClass =
+            changedVirtualMethods.getOrDefault(equivalence.wrap(method), ImmutableSet.of()).stream()
+                .anyMatch(other -> clazz.type.isSubtypeOf(other, appView.appInfo()));
+        if (isOverrideOfPreviouslyChangedMethodInSuperClass) {
+          assert methodPool.hasSeen(wrapper);
+
+          boolean signatureIsAvailable = usedSignatures.add(wrapper);
+          assert signatureIsAvailable;
+
+          clazz.setVirtualMethod(i, encodedMethod.toTypeSubstitutedMethod(newMethod));
+          methodMapping.put(method, newMethod);
+        }
+      }
+    }
+    for (int i = 0; i < virtualMethods.size(); ++i) {
+      DexEncodedMethod encodedMethod = virtualMethods.get(i);
+      DexMethod method = encodedMethod.method;
+      RewrittenPrototypeDescription prototypeChanges =
+          getPrototypeChanges(encodedMethod, DISALLOW_ARGUMENT_REMOVAL);
+      DexMethod newMethod = getNewMethodSignature(encodedMethod, prototypeChanges);
+      if (newMethod != method) {
+        Wrapper<DexMethod> wrapper = equivalence.wrap(newMethod);
+
+        // TODO(b/110806787): Can be extended to handle collisions by renaming the given
+        //  method. Note that this also requires renaming all of the methods that override this
+        //  method, though.
+        if (!methodPool.hasSeen(wrapper) && usedSignatures.add(wrapper)) {
+          methodPool.seen(wrapper);
+
+          clazz.setVirtualMethod(i, encodedMethod.toTypeSubstitutedMethod(newMethod));
+          methodMapping.put(method, newMethod);
+
+          boolean added =
+              changedVirtualMethods
+                  .computeIfAbsent(equivalence.wrap(method), key -> Sets.newIdentityHashSet())
+                  .add(clazz.type);
+          assert added;
+        }
+      }
+    }
+  }
+
   private RewrittenPrototypeDescription getPrototypeChanges(
       DexEncodedMethod encodedMethod, Strategy strategy) {
     if (ArgumentRemovalUtils.isPinned(encodedMethod, appView)
@@ -311,6 +316,8 @@
 
   private DexMethod getNewMethodSignature(
       DexEncodedMethod encodedMethod, RewrittenPrototypeDescription prototypeChanges) {
+    DexItemFactory dexItemFactory = appView.dexItemFactory();
+
     DexMethod method = encodedMethod.method;
     RemovedArgumentsInfo removedArgumentsInfo = prototypeChanges.getRemovedArgumentsInfo();
 
@@ -477,7 +484,7 @@
             TypeLatticeElement.fromDexType(fieldType, true, appView.appInfo());
         if (!value.getTypeLattice().lessThanOrEqual(fieldLatticeType, appView.appInfo())) {
           // Broken type hierarchy. See FieldTypeTest#test_brokenTypeHierarchy.
-          assert options.testing.allowTypeErrors;
+          assert appView.options().testing.allowTypeErrors;
           return;
         }
 
@@ -554,7 +561,8 @@
     Value nullValue = new Value(code.valueNumberGenerator.next(), TypeLatticeElement.NULL, null);
     ConstNumber constNumberInstruction = new ConstNumber(nullValue, 0);
     // Note that we only keep position info for throwing instructions in release mode.
-    constNumberInstruction.setPosition(options.debug ? instruction.getPosition() : Position.none());
+    constNumberInstruction.setPosition(
+        appView.options().debug ? instruction.getPosition() : Position.none());
     instructionIterator.add(constNumberInstruction);
     instructionIterator.next();
 
@@ -580,8 +588,8 @@
               // target.
               return;
             }
-            if (guard != dexItemFactory.catchAllType
-                && !dexItemFactory.npeType.isSubtypeOf(guard, appView.appInfo())) {
+            if (guard != DexItemFactory.catchAllType
+                && !appView.dexItemFactory().npeType.isSubtypeOf(guard, appView.appInfo())) {
               // TODO(christofferqa): Consider updating previous dominator tree instead of
               // rebuilding it from scratch.
               DominatorTree dominatorTree = new DominatorTree(code, MAY_HAVE_UNREACHABLE_BLOCKS);
diff --git a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
index 3b3c125..a08f5d9 100644
--- a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
+++ b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
@@ -35,7 +35,7 @@
       RootSet rootSet) {
     this.application = application;
     this.appView = appView;
-    this.methodPoolCollection = new MethodPoolCollection(application);
+    this.methodPoolCollection = new MethodPoolCollection(appView);
     this.rootSet = rootSet;
   }
 
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index 965d563..116a9e3 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -202,9 +202,7 @@
   private final AppInfoWithLiveness appInfo;
   private final AppView<? extends AppInfoWithLiveness> appView;
   private final ExecutorService executorService;
-  private final GraphLense graphLense;
   private final MethodPoolCollection methodPoolCollection;
-  private final InternalOptions options;
   private final Timing timing;
   private Collection<DexMethod> invokes;
 
@@ -239,9 +237,7 @@
     this.appInfo = appView.appInfo();
     this.appView = appView;
     this.executorService = executorService;
-    this.graphLense = appView.graphLense();
-    this.methodPoolCollection = new MethodPoolCollection(application);
-    this.options = options;
+    this.methodPoolCollection = new MethodPoolCollection(appView);
     this.renamedMembersLense = new VerticalClassMergerGraphLense.Builder();
     this.timing = timing;
     this.mainDexClasses = mainDexClasses;
@@ -607,7 +603,7 @@
 
   public GraphLense run() {
     timing.begin("merge");
-    GraphLense mergingGraphLense = mergeClasses(graphLense);
+    GraphLense mergingGraphLense = mergeClasses();
     timing.end();
     timing.begin("fixup");
     GraphLense result = new TreeFixer().fixupTypeReferences(mergingGraphLense);
@@ -683,13 +679,14 @@
     return true;
   }
 
-  private GraphLense mergeClasses(GraphLense graphLense) {
+  private GraphLense mergeClasses() {
     // Visit the program classes in a top-down order according to the class hierarchy.
-    TopDownClassHierarchyTraversal.visit(appView, mergeCandidates, this::mergeClassIfPossible);
+    TopDownClassHierarchyTraversal.forProgramClasses(appView)
+        .visit(mergeCandidates, this::mergeClassIfPossible);
     if (Log.ENABLED) {
       Log.debug(getClass(), "Merged %d classes.", mergedClasses.size());
     }
-    return renamedMembersLense.build(graphLense, mergedClasses, appInfo);
+    return renamedMembersLense.build(appView.graphLense(), mergedClasses, appInfo);
   }
 
   private boolean methodResolutionMayChange(DexClass source, DexClass target) {
@@ -1189,7 +1186,7 @@
       SynthesizedBridgeCode code =
           new SynthesizedBridgeCode(
               newMethod,
-              graphLense.getOriginalMethodSignature(method.method),
+              appView.graphLense().getOriginalMethodSignature(method.method),
               invocationTarget.method,
               invocationTarget.isPrivateMethod() ? DIRECT : STATIC);
 
@@ -1625,7 +1622,7 @@
   }
 
   private boolean disallowInlining(DexEncodedMethod method, DexType invocationContext) {
-    if (options.enableInlining) {
+    if (appView.options().enableInlining) {
       if (method.getCode().isJarCode()) {
         JarCode jarCode = method.getCode().asJarCode();
         ConstraintWithTarget constraint =
@@ -1686,7 +1683,7 @@
     public GraphLenseLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
       // First look up the method using the existing graph lense (for example, the type will have
       // changed if the method was publicized by ClassAndMemberPublicizer).
-      GraphLenseLookupResult lookup = graphLense.lookupMethod(method, context, type);
+      GraphLenseLookupResult lookup = appView.graphLense().lookupMethod(method, context, type);
       DexMethod previousMethod = lookup.getMethod();
       Type previousType = lookup.getType();
       // Then check if there is a renaming due to the vertical class merger.
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/unusedarguments/CollisionWithLibraryMethodsTest.java b/src/test/java/com/android/tools/r8/ir/optimize/unusedarguments/CollisionWithLibraryMethodsTest.java
new file mode 100644
index 0000000..28c5b2f
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/unusedarguments/CollisionWithLibraryMethodsTest.java
@@ -0,0 +1,75 @@
+// Copyright (c) 2019, 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.optimize.unusedarguments;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class CollisionWithLibraryMethodsTest extends TestBase {
+
+  private final Backend backend;
+
+  @Parameters(name = "Backend: {0}")
+  public static Backend[] params() {
+    return Backend.values();
+  }
+
+  public CollisionWithLibraryMethodsTest(Backend backend) {
+    this.backend = backend;
+  }
+
+  @Test
+  public void test() throws Exception {
+    String expectedOutput = StringUtils.lines("Hello world!");
+    testForR8(backend)
+        .addInnerClasses(CollisionWithLibraryMethodsTest.class)
+        .addKeepMainRule(TestClass.class)
+        .enableClassInliningAnnotations()
+        .enableInliningAnnotations()
+        .compile()
+        .inspect(this::verify)
+        .run(TestClass.class)
+        .assertSuccessWithOutput(expectedOutput);
+  }
+
+  private void verify(CodeInspector inspector) {
+    ClassSubject classSubject = inspector.clazz(Greeting.class);
+    assertThat(classSubject, isPresent());
+
+    MethodSubject methodSubject = classSubject.uniqueMethodWithName("toString");
+    assertThat(methodSubject, isPresent());
+    assertEquals("java.lang.Object", methodSubject.getMethod().method.proto.parameters.toString());
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      System.out.println(new Greeting().toString(null));
+    }
+  }
+
+  @NeverClassInline
+  static class Greeting {
+
+    @NeverInline
+    public String toString(Object unused) {
+      return "Hello world!";
+    }
+  }
+}
diff --git a/tools/archive.py b/tools/archive.py
index c37b304..e9233c7 100755
--- a/tools/archive.py
+++ b/tools/archive.py
@@ -47,6 +47,10 @@
 def IsMaster(version):
   branches = subprocess.check_output(['git', 'branch', '-r', '--contains',
                                       'HEAD'])
+  # CL runs from gerrit does not have a branch, we always treat them as master
+  # commits to archive these to the hash based location
+  if len(branches) == 0:
+    return True
   if not version.endswith('-dev'):
     # Sanity check, we don't want to archive on top of release builds EVER
     # Note that even though we branch, we never push the bots to build the same