Merge commit '744d742137a82656b8ee27513f975e0528aecd78' into dev-release
diff --git a/build.gradle b/build.gradle
index c65df58e..5220ac2 100644
--- a/build.gradle
+++ b/build.gradle
@@ -13,6 +13,7 @@
 import utils.Utils
 import org.gradle.api.tasks.testing.logging.TestExceptionFormat
 import org.gradle.api.tasks.testing.logging.TestLogEvent
+import org.gradle.api.tasks.testing.TestOutputEvent
 
 import java.nio.charset.StandardCharsets
 import java.nio.file.Files
@@ -1928,57 +1929,172 @@
     }
 }
 
+static def escapeHtml(String string) {
+    return string.replace("&", "&amp;").replace("<", "&lt;").replace(">", "&gt;")
+}
+
+static def urlEncode(String string) {
+    // Not sure why, but the + also needs to be converted to have working links.
+    return URLEncoder.encode(string, "UTF-8").replace("+","%20")
+}
+
 def ensureDir(File dir) {
     dir.mkdirs()
     return dir
 }
 
+// Some of our test parameters have new lines :-( We really don't want test names to span lines.
+static def sanitizedTestName(testDesc) {
+    if (testDesc.getName().contains("\n")) {
+        throw new RuntimeException("Unsupported use of newline in test name: '${testDesc.getName()}'")
+    }
+    return testDesc.getName()
+}
+
+static def desanitizedTestName(testName) {
+    return testName
+}
+
 def getTestReportEntryDir(reportDir, testDesc) {
     return ensureDir(reportDir.toPath()
             .resolve(testDesc.getClassName())
-            .resolve(testDesc.getName())
+            .resolve(sanitizedTestName(testDesc))
             .toFile())
 }
 
+def getTestReportEntryURL(reportDir, testDesc) {
+    def classDir = urlEncode(testDesc.getClassName())
+    def testDir = urlEncode(sanitizedTestName(testDesc))
+    return "file://${reportDir}/${classDir}/${testDir}"
+}
+
 def getTestResultEntryOutputFile(reportDir, testDesc, fileName) {
     def dir = getTestReportEntryDir(reportDir, testDesc).toPath()
     return dir.resolve(fileName).toFile()
 }
 
-def getGitBranchName() {
+def withTestResultEntryWriter(reportDir, testDesc, fileName, append, fn) {
+    def file = getTestResultEntryOutputFile(reportDir, testDesc, fileName)
+    new FileWriter(file, append).withCloseable fn
+}
+
+static def getGitBranchName() {
     def out = new StringBuilder()
     def err = new StringBuilder()
     def proc = "git rev-parse --abbrev-ref HEAD".execute()
     proc.waitForProcessOutput(out, err)
-    return out
+    return out.toString().trim()
 }
 
-def setUpNewTestReporting(Test task) {
+static def getFreshTestReportIndex(File reportDir) {
+    def number = 0
+    while (true) {
+        def freshIndex = reportDir.toPath().resolve("index.${number++}.html").toFile()
+        if (!freshIndex.exists()) {
+            return freshIndex
+        }
+    }
+}
+
+def forEachTestReportAlreadyX(File reportDir, fileName, onTest) {
+    def out = new StringBuilder()
+    def err = new StringBuilder()
+    def proc = "find . -name ${fileName}".execute([], reportDir)
+    proc.waitForProcessOutput(out, err)
+    def outString = out.toString()
+    outString.eachLine {
+        // Lines are of the form: ./<class>/<name>/FAILURE
+        def clazz = null
+        def name = null
+        try {
+            def trimmed = it.trim()
+            def line = trimmed.substring(2)
+            def sep = line.indexOf("/")
+            clazz = line.substring(0, sep)
+            name = line.substring(sep + 1, line.length() - fileName.length() - 1)
+        } catch (Exception e) {
+            logger.lifecycle("WARNING: failed attempt to read test description from: '${it}'")
+            return
+        }
+        onTest(clazz, desanitizedTestName(name))
+    }
+    return !outString.trim().isEmpty()
+}
+
+def forEachTestReportAlreadyFailing(File reportDir, onFailureTest) {
+    return forEachTestReportAlreadyX(reportDir, TestResult.ResultType.FAILURE.name(), onFailureTest)
+}
+
+def forEachTestReportAlreadyPassing(File reportDir, onSucceededTest) {
+    return forEachTestReportAlreadyX(reportDir, TestResult.ResultType.SUCCESS.name(), onSucceededTest)
+}
+
+def forEachTestReportAlreadySkipped(File reportDir, onSucceededTest) {
+    return forEachTestReportAlreadyX(reportDir, TestResult.ResultType.SKIPPED.name(), onSucceededTest)
+}
+
+def setUpTestingState(Test task) {
     // Hide all test events from the console, they are written to the report.
     task.testLogging { events = [] }
 
-    def testReportOutput = project.hasProperty('test_report_output')
-            ? file(project.hasProperty('test_report_output'))
-            : file("${buildDir}/testreport")
-    def index = testReportOutput.toPath().resolve("index.html").toFile()
+    def branch = getGitBranchName()
+    def reportDir = file("${buildDir}/test-state/${branch}")
+    def index = reportDir.toPath().resolve("index.html").toFile()
+    def resetState = project.hasProperty('reset-testing-state')
+    def reportDirExists = reportDir.exists()
+    def resuming = !resetState && reportDirExists
+
+    def hasFailingTests = false;
+    if (resuming) {
+        // Test filtering happens before the test execution is initiated so compute it here.
+        // If there are still failing tests in the report, include only those.
+        hasFailingTests = forEachTestReportAlreadyFailing(reportDir, {
+            clazz, name -> task.filter.includeTestsMatching("$clazz.$name")
+        })
+        // Otherwise exclude all of the test already marked as succeeding.
+        if (!hasFailingTests) {
+            // Also allow the test to overall succeed if there are no remaining tests that match,
+            // which is natural if the state already succeeded in full.
+            task.filter.failOnNoMatchingTests = false
+            forEachTestReportAlreadyPassing(reportDir, {
+                clazz, name -> task.filter.excludeTestsMatching("$clazz.$name")
+            })
+            forEachTestReportAlreadySkipped(reportDir, {
+                clazz, name -> task.filter.excludeTestsMatching("$clazz.$name")
+            })
+        }
+    }
 
     task.beforeSuite { desc ->
         if (!desc.parent) {
-            // Start by printing a link to the test report for easy access.
-            println "Test report being written to:"
-            println "file://${index}"
-
-            def branch = getGitBranchName()
-            def title = "${desc} @ ${branch}"
-
-            // TODO(b/186607794): Support resuming testing based on the existing report.
-            delete testReportOutput
-            testReportOutput.mkdirs()
-            index << "<html><head><title>${title}</title></head>"
-            index << "<body><h1>${title}</h1>"
+            def parentReport = null
+            if (resetState && reportDirExists) {
+                delete reportDir
+            }
+            if (resuming) {
+                if (index.exists()) {
+                    parentReport = getFreshTestReportIndex(reportDir)
+                    index.renameTo(parentReport)
+                }
+            } else {
+                reportDir.mkdirs()
+            }
+            def runPrefix = resuming ? "Resuming" : "Starting"
+            def title =  "${runPrefix} @ ${branch}"
+            // Print a console link to the test report for easy access.
+            println "${runPrefix} test, report written to:"
+            println "  file://${index}"
+            // Print the new index content.
+            index << "<html><head><title>${title}</title>"
+            index << "<style> * { font-family: monospace; }</style>"
+            index << "</head><body><h1>${title}</h1>"
             index << "<p>Run on: ${new Date()}</p>"
             index << "<p>Git branch: ${branch}</p>"
-            index << "<p><a href=\"file://${testReportOutput}\">Test directories</a></p>"
+            if (parentReport != null) {
+                index << "<p><a href=\"file://${parentReport}\">Previous result index</a></p>"
+            }
+            index << "<p><a href=\"file://${index}\">Most recent result index</a></p>"
+            index << "<p><a href=\"file://${reportDir}\">Test directories</a></p>"
             index << "<h2>Failing tests (reload to refresh)</h2><ul>"
         }
     }
@@ -1987,7 +2103,18 @@
         if (!desc.parent) {
             // Update the final test results in the index.
             index << "</ul>"
-            index << "<h2>Tests finished: ${result.resultType.name()}</h2><ul>"
+            if (result.resultType == TestResult.ResultType.SUCCESS) {
+                if (hasFailingTests) {
+                    index << "<h2>Rerun of failed tests now pass!</h2>"
+                    index << "<h2>Rerun again to continue with outstanding tests!</h2>"
+                } else {
+                    index << "<h2 style=\"background-color:#62D856\">GREEN BAR == YOU ROCK!</h2>"
+                }
+            } else if (result.resultType == TestResult.ResultType.FAILURE) {
+                index << "<h2 style=\"background-color:#6D130A\">Some tests failed: ${result.resultType.name()}</h2><ul>"
+            } else {
+                index << "<h2>Tests finished: ${result.resultType.name()}</h2><ul>"
+            }
             index << "<li>Number of tests: ${result.testCount}"
             index << "<li>Failing tests: ${result.failedTestCount}"
             index << "<li>Successful tests: ${result.successfulTestCount}"
@@ -1998,45 +2125,60 @@
 
     // Events to stdout/err are appended to the files in the test directories.
     task.onOutput { desc, event ->
-        getTestResultEntryOutputFile(testReportOutput, desc, event.getDestination().name()) <<
-                event.getMessage()
+        withTestResultEntryWriter(reportDir, desc, event.getDestination().name(), true, {
+            it.append(event.getMessage())
+        })
+    }
+
+    task.beforeTest { desc ->
+        // Remove any stale output files before running the test.
+        for (def destType : TestOutputEvent.Destination.values()) {
+            def destFile = getTestResultEntryOutputFile(reportDir, desc, destType.name())
+            if (destFile.exists()) {
+                delete destFile
+            }
+        }
     }
 
     task.afterTest { desc, result ->
         if (result.getTestCount() != 1) {
             throw new IllegalStateException("Unexpected test with more than one result: ${desc}")
         }
-        def testReportPath = getTestReportEntryDir(testReportOutput, desc)
+        // Clear any previous result files.
+        for (def resultType : TestResult.ResultType.values()) {
+            delete getTestResultEntryOutputFile(reportDir, desc, resultType.name())
+        }
         // Emit the result type status in a file of the same name: SUCCESS, FAILURE or SKIPPED.
-        getTestResultEntryOutputFile(testReportOutput, desc, result.getResultType().name()) <<
-                result.getResultType().name()
+        withTestResultEntryWriter(reportDir, desc, result.getResultType().name(), false, {
+            it.append(result.getResultType().name())
+        })
         // Emit the test time.
-        getTestResultEntryOutputFile(testReportOutput, desc, "time") <<
-                "${result.getEndTime() - result.getStartTime()}"
+        withTestResultEntryWriter(reportDir, desc, "time", false, {
+            it.append("${result.getEndTime() - result.getStartTime()}")
+        })
         // For failed tests, update the index and emit stack trace information.
         if (result.resultType == TestResult.ResultType.FAILURE) {
-            def title = "${desc.className}.${desc.name}"
-            index << "<li><a href=\"file://${testReportPath}\">${title}</a></li>"
+            def title = escapeHtml("${desc.className}.${desc.name}")
+            def link = getTestReportEntryURL(reportDir, desc)
+            index << "<li><a href=\"${link}\">${title}</a></li>"
             if (!result.exceptions.isEmpty()) {
                 printAllStackTracesToFile(
                         result.exceptions,
                         getTestResultEntryOutputFile(
-                                testReportOutput,
+                                reportDir,
                                 desc,
                                 "exceptions-raw.txt"))
                 filterStackTraces(result)
                 printAllStackTracesToFile(
                         result.exceptions,
                         getTestResultEntryOutputFile(
-                                testReportOutput,
+                                reportDir,
                                 desc,
                                 "exceptions-filtered.txt"))
                 if (shouldRetrace()) {
-                    def out = getTestResultEntryOutputFile(
-                            testReportOutput,
-                            desc,
-                            "exceptions-retraced.txt")
-                    result.exceptions.forEach { out << retrace(it) }
+                    withTestResultEntryWriter(reportDir, desc, "exceptions-retraced.txt", false, { writer ->
+                        result.exceptions.forEach { writer.append(retrace(it)) }
+                    })
                 }
             }
         }
@@ -2044,7 +2186,7 @@
 }
 
 def testTimes = [:]
-def numberOfTestTimesToPrint = 40
+def numberOfTestTimesToPrint = 100
 
 test { task ->
 
@@ -2053,9 +2195,9 @@
     // R8.jar is required for running bootstrap tests.
     dependsOn r8
 
-    def newTestingReport = project.hasProperty('testing-report')
-    if (newTestingReport) {
-        setUpNewTestReporting(task)
+    def useTestingState = project.hasProperty('testing-state')
+    if (useTestingState) {
+        setUpTestingState(task)
     }
 
     if (project.hasProperty('generate_golden_files_to')) {
@@ -2071,7 +2213,7 @@
     }
 
 
-    if (!newTestingReport) {
+    if (!useTestingState) {
         testLogging.exceptionFormat = 'full'
         if (project.hasProperty('print_test_stdout')) {
             testLogging.showStandardStreams = true
@@ -2100,7 +2242,7 @@
         systemProperty 'desugar_jdk_libs', project.property('desugar_jdk_libs')
     }
 
-    if (!newTestingReport) {
+    if (!useTestingState) {
         if (project.hasProperty('print_times') || project.hasProperty('one_line_per_test')) {
             afterTest { desc, result ->
                 def executionTime = (result.endTime - result.startTime) / 1000
diff --git a/src/main/java/com/android/tools/r8/D8Command.java b/src/main/java/com/android/tools/r8/D8Command.java
index 7dbcb32..f1ed0cd 100644
--- a/src/main/java/com/android/tools/r8/D8Command.java
+++ b/src/main/java/com/android/tools/r8/D8Command.java
@@ -241,9 +241,6 @@
         return;
       }
       Reporter reporter = getReporter();
-      if (getProgramConsumer() instanceof ClassFileConsumer) {
-        reporter.warning("Compiling to Java class files with D8 is not officially supported");
-      }
       if (getAppBuilder().hasMainDexList()) {
         if (intermediate) {
           reporter.error("Option --main-dex-list cannot be used with --intermediate");
diff --git a/src/main/java/com/android/tools/r8/PrintUses.java b/src/main/java/com/android/tools/r8/PrintUses.java
index 926577f..dc284ed 100644
--- a/src/main/java/com/android/tools/r8/PrintUses.java
+++ b/src/main/java/com/android/tools/r8/PrintUses.java
@@ -233,7 +233,8 @@
       if (typeMethods != null) {
         DexClass holder = appInfo.definitionForHolder(method);
         DexEncodedMethod definition = method.lookupOnClass(holder);
-        assert definition != null : "Could not find method " + method.toString();
+        assert definition != null
+            : "Could not find method " + method.toString() + " in " + context.getTypeName();
         if (!allowObfuscation) {
           noObfuscationTypes.add(method.holder);
         }
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index d814466..2404763 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -32,6 +32,7 @@
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
+import com.android.tools.r8.graph.GenericSignatureTypeVariableRemover;
 import com.android.tools.r8.graph.GraphLens;
 import com.android.tools.r8.graph.InitClassLens;
 import com.android.tools.r8.graph.PrunedItems;
@@ -376,6 +377,10 @@
           appView.withGeneratedExtensionRegistryShrinker(
               shrinker -> shrinker.run(Mode.INITIAL_TREE_SHAKING));
 
+          // Build enclosing information and type-paramter information before pruning.
+          GenericSignatureTypeVariableRemover typeVariableRemover =
+              GenericSignatureTypeVariableRemover.create(appView, appView.appInfo().classes());
+
           TreePruner pruner = new TreePruner(appViewWithLiveness);
           DirectMappedDexApplication prunedApp = pruner.run(executorService);
 
@@ -402,6 +407,7 @@
           annotationRemover.ensureValid().run();
           classesToRetainInnerClassAttributeFor =
               annotationRemover.getClassesToRetainInnerClassAttributeFor();
+          typeVariableRemover.removeDeadGenericSignatureTypeVariables(appView);
           new GenericSignatureRewriter(appView, NamingLens.getIdentityLens())
               .run(appView.appInfo().classes(), executorService);
         }
@@ -611,6 +617,9 @@
                     shrinker -> shrinker.run(enqueuer.getMode()),
                     DefaultTreePrunerConfiguration.getInstance());
 
+            GenericSignatureTypeVariableRemover typeVariableRemover =
+                GenericSignatureTypeVariableRemover.create(appView, appView.appInfo().classes());
+
             TreePruner pruner = new TreePruner(appViewWithLiveness, treePrunerConfiguration);
             DirectMappedDexApplication application = pruner.run(executorService);
             Set<DexType> removedClasses = pruner.getRemovedClasses();
@@ -652,6 +661,7 @@
                 .setClassesToRetainInnerClassAttributeFor(classesToRetainInnerClassAttributeFor)
                 .build(appView.withLiveness(), removedClasses)
                 .run();
+            typeVariableRemover.removeDeadGenericSignatureTypeVariables(appView);
             // Synthesize fields for triggering class initializers.
             new ClassInitFieldSynthesizer(appViewWithLiveness).run(executorService);
           }
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfFrame.java b/src/main/java/com/android/tools/r8/cf/code/CfFrame.java
index 98bc101..e55bf9a 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfFrame.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfFrame.java
@@ -30,6 +30,7 @@
 import java.util.ArrayDeque;
 import java.util.Deque;
 import java.util.Objects;
+import java.util.SortedMap;
 import org.objectweb.asm.MethodVisitor;
 import org.objectweb.asm.Opcodes;
 
@@ -342,10 +343,26 @@
     this.stack = stack;
   }
 
+  // This is used from tests. As fastutils are repackaged and minified the method above is
+  // not available from tests which use fastutils in their original namespace.
+  public CfFrame(SortedMap<Integer, FrameType> locals, Deque<FrameType> stack) {
+    this(
+        locals instanceof Int2ReferenceAVLTreeMap
+            ? (Int2ReferenceAVLTreeMap<FrameType>) locals
+            : new Int2ReferenceAVLTreeMap<>(locals),
+        stack);
+  }
+
   public Int2ReferenceSortedMap<FrameType> getLocals() {
     return locals;
   }
 
+  // This is used from tests. As fastutils are repackaged and minified the method above is
+  // not available from tests which use fastutils in their original namespace.
+  public SortedMap<Integer, FrameType> getLocalsAsSortedMap() {
+    return locals;
+  }
+
   public Deque<FrameType> getStack() {
     return stack;
   }
diff --git a/src/main/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLibraryKeepRuleGenerator.java b/src/main/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLibraryKeepRuleGenerator.java
index fb4b86e..6386b61 100644
--- a/src/main/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLibraryKeepRuleGenerator.java
+++ b/src/main/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLibraryKeepRuleGenerator.java
@@ -131,7 +131,10 @@
       ClassReference rewrittenReference = rewrittenWithLens(tracedClass.getReference());
       super.acceptType(
           rewrittenReference != tracedClass.getReference()
-              ? new TracedClassImpl(rewrittenReference, tracedClass.getAccessFlags())
+              ? new TracedClassImpl(
+                  rewrittenReference,
+                  tracedClass.getReferencedFromContext(),
+                  tracedClass.getAccessFlags())
               : tracedClass,
           handler);
     }
@@ -141,7 +144,10 @@
       FieldReference rewrittenReference = rewrittenWithLens(tracedField.getReference());
       super.acceptField(
           rewrittenReference != tracedField.getReference()
-              ? new TracedFieldImpl(rewrittenReference, tracedField.getAccessFlags())
+              ? new TracedFieldImpl(
+                  rewrittenReference,
+                  tracedField.getReferencedFromContext(),
+                  tracedField.getAccessFlags())
               : tracedField,
           handler);
     }
@@ -151,7 +157,10 @@
       MethodReference rewrittenReference = rewrittenWithLens(tracedMethod.getReference());
       super.acceptMethod(
           rewrittenReference != tracedMethod.getReference()
-              ? new TracedMethodImpl(rewrittenReference, tracedMethod.getAccessFlags())
+              ? new TracedMethodImpl(
+                  rewrittenReference,
+                  tracedMethod.getReferencedFromContext(),
+                  tracedMethod.getAccessFlags())
               : tracedMethod,
           handler);
     }
diff --git a/src/main/java/com/android/tools/r8/diagnostic/internal/MissingClassInfoImpl.java b/src/main/java/com/android/tools/r8/diagnostic/internal/MissingClassInfoImpl.java
index 82d5a35..011bfdd 100644
--- a/src/main/java/com/android/tools/r8/diagnostic/internal/MissingClassInfoImpl.java
+++ b/src/main/java/com/android/tools/r8/diagnostic/internal/MissingClassInfoImpl.java
@@ -29,7 +29,7 @@
     return classReference;
   }
 
-  public static class Builder extends MissingDefinitionInfoBase.Builder {
+  public static class Builder extends MissingDefinitionInfoBase.Builder<Builder> {
 
     private ClassReference classReference;
 
@@ -43,5 +43,10 @@
     public MissingDefinitionInfo build() {
       return new MissingClassInfoImpl(classReference, referencedFromContextsBuilder.build());
     }
+
+    @Override
+    Builder self() {
+      return this;
+    }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/diagnostic/internal/MissingDefinitionInfoBase.java b/src/main/java/com/android/tools/r8/diagnostic/internal/MissingDefinitionInfoBase.java
index 8d90a92..aed2299 100644
--- a/src/main/java/com/android/tools/r8/diagnostic/internal/MissingDefinitionInfoBase.java
+++ b/src/main/java/com/android/tools/r8/diagnostic/internal/MissingDefinitionInfoBase.java
@@ -29,16 +29,23 @@
     return referencedFromContexts;
   }
 
-  public abstract static class Builder {
+  public abstract static class Builder<B extends Builder<B>> {
 
     final ImmutableList.Builder<DefinitionContext> referencedFromContextsBuilder =
         ImmutableList.builder();
 
     Builder() {}
 
-    public Builder addReferencedFromContext(DefinitionContext missingDefinitionContext) {
+    public B addReferencedFromContext(DefinitionContext missingDefinitionContext) {
       referencedFromContextsBuilder.add(missingDefinitionContext);
-      return this;
+      return self();
     }
+
+    public B addReferencedFromContexts(Iterable<DefinitionContext> missingDefinitionContexts) {
+      missingDefinitionContexts.forEach(this::addReferencedFromContext);
+      return self();
+    }
+
+    abstract B self();
   }
 }
diff --git a/src/main/java/com/android/tools/r8/diagnostic/internal/MissingFieldInfoImpl.java b/src/main/java/com/android/tools/r8/diagnostic/internal/MissingFieldInfoImpl.java
index d7acc21..679158d 100644
--- a/src/main/java/com/android/tools/r8/diagnostic/internal/MissingFieldInfoImpl.java
+++ b/src/main/java/com/android/tools/r8/diagnostic/internal/MissingFieldInfoImpl.java
@@ -29,7 +29,7 @@
     return fieldReference;
   }
 
-  public static class Builder extends MissingDefinitionInfoBase.Builder {
+  public static class Builder extends MissingDefinitionInfoBase.Builder<Builder> {
 
     private FieldReference fieldReference;
 
@@ -43,5 +43,10 @@
     public MissingDefinitionInfo build() {
       return new MissingFieldInfoImpl(fieldReference, referencedFromContextsBuilder.build());
     }
+
+    @Override
+    Builder self() {
+      return this;
+    }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/diagnostic/internal/MissingMethodInfoImpl.java b/src/main/java/com/android/tools/r8/diagnostic/internal/MissingMethodInfoImpl.java
index 8ab85d9..39f7e20 100644
--- a/src/main/java/com/android/tools/r8/diagnostic/internal/MissingMethodInfoImpl.java
+++ b/src/main/java/com/android/tools/r8/diagnostic/internal/MissingMethodInfoImpl.java
@@ -29,7 +29,7 @@
     return methodReference;
   }
 
-  public static class Builder extends MissingDefinitionInfoBase.Builder {
+  public static class Builder extends MissingDefinitionInfoBase.Builder<Builder> {
 
     private MethodReference methodReference;
 
@@ -43,5 +43,10 @@
     public MissingDefinitionInfo build() {
       return new MissingMethodInfoImpl(methodReference, referencedFromContextsBuilder.build());
     }
+
+    @Override
+    Builder self() {
+      return this;
+    }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index acd8b41..7d95e87 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -780,6 +780,7 @@
               classMethods.getName,
               classMethods.getSimpleName,
               classMethods.forName,
+              objectMembers.getClass,
               objectsMethods.requireNonNull,
               objectsMethods.requireNonNullWithMessage,
               objectsMethods.requireNonNullWithMessageSupplier,
@@ -2135,7 +2136,31 @@
    *
    * @param holder indicates where the method originates from.
    */
-  public DexMethod createFreshMethodName(
+  public DexMethod createFreshMethodNameWithHolder(
+      String baseName,
+      DexType holder,
+      DexProto proto,
+      DexType target,
+      Predicate<DexMethod> isFresh) {
+    assert holder != null;
+    return internalCreateFreshMethodNameWithHolder(baseName, holder, proto, target, isFresh);
+  }
+
+  /**
+   * Tries to find a method name for insertion into the class {@code target} of the form baseName$n,
+   * where {@code baseName} is supplied by the user, and {@code n} is picked to be the first number
+   * so that {@code isFresh.apply(method)} returns {@code true}.
+   */
+  public DexMethod createFreshMethodNameWithoutHolder(
+      String baseName, DexProto proto, DexType target, Predicate<DexMethod> isFresh) {
+    return internalCreateFreshMethodNameWithHolder(baseName, null, proto, target, isFresh);
+  }
+
+  /**
+   * Used to find a fresh method name of the from {@code baseName$n}, or {@code baseName$holder$n}
+   * if {@param holder} is non-null.
+   */
+  private DexMethod internalCreateFreshMethodNameWithHolder(
       String baseName,
       DexType holder,
       DexProto proto,
@@ -2298,6 +2323,8 @@
   }
 
   private DexType createStaticallyKnownType(Class<?> clazz) {
+    // This uses Class.getName() and not Class.getTypeName(), as the compilers are also
+    // running on Art versions where Class.getTypeName() is not present (7.0 and before).
     return createStaticallyKnownType(
         createString(DescriptorUtils.javaTypeToDescriptor(clazz.getName())));
   }
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignature.java b/src/main/java/com/android/tools/r8/graph/GenericSignature.java
index e38a163..9a34638 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignature.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignature.java
@@ -98,10 +98,26 @@
  */
 public class GenericSignature {
 
-  static final List<FormalTypeParameter> EMPTY_TYPE_PARAMS = ImmutableList.of();
-  static final List<FieldTypeSignature> EMPTY_TYPE_ARGUMENTS = ImmutableList.of();
-  static final List<ClassTypeSignature> EMPTY_SUPER_INTERFACES = ImmutableList.of();
-  static final List<TypeSignature> EMPTY_TYPE_SIGNATURES = ImmutableList.of();
+  private static final List<FormalTypeParameter> EMPTY_TYPE_PARAMS = ImmutableList.of();
+  private static final List<FieldTypeSignature> EMPTY_TYPE_ARGUMENTS = ImmutableList.of();
+  private static final List<ClassTypeSignature> EMPTY_SUPER_INTERFACES = ImmutableList.of();
+  private static final List<TypeSignature> EMPTY_TYPE_SIGNATURES = ImmutableList.of();
+
+  public static List<FormalTypeParameter> getEmptyTypeParams() {
+    return EMPTY_TYPE_PARAMS;
+  }
+
+  public static List<FieldTypeSignature> getEmptyTypeArguments() {
+    return EMPTY_TYPE_ARGUMENTS;
+  }
+
+  public static List<ClassTypeSignature> getEmptySuperInterfaces() {
+    return EMPTY_SUPER_INTERFACES;
+  }
+
+  public static List<TypeSignature> getEmptyTypeSignatures() {
+    return EMPTY_TYPE_SIGNATURES;
+  }
 
   interface DexDefinitionSignature<T extends DexDefinition> {
 
@@ -561,10 +577,11 @@
       if (visitedType == null) {
         return null;
       }
-      List<FieldTypeSignature> rewrittenArguments = visitor.visitTypeArguments(typeArguments);
+      List<FieldTypeSignature> rewrittenArguments =
+          visitor.visitTypeArguments(visitedType, typeArguments);
       ClassTypeSignature rewrittenOuter = null;
       if (enclosingTypeSignature != null) {
-        rewrittenOuter = visitor.visitSimpleClass(enclosingTypeSignature);
+        rewrittenOuter = visitor.visitEnclosing(enclosingTypeSignature, this);
       }
       if (type == visitedType
           && typeArguments == rewrittenArguments
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignaturePartialTypeArgumentApplier.java b/src/main/java/com/android/tools/r8/graph/GenericSignaturePartialTypeArgumentApplier.java
index dfa8a95..adb256f 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignaturePartialTypeArgumentApplier.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignaturePartialTypeArgumentApplier.java
@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.graph;
 
+import static com.android.tools.r8.graph.GenericSignature.getEmptyTypeArguments;
+
 import com.android.tools.r8.graph.GenericSignature.ClassSignature;
 import com.android.tools.r8.graph.GenericSignature.ClassTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.FieldTypeSignature;
@@ -14,31 +16,66 @@
 import com.android.tools.r8.graph.GenericSignature.TypeSignature;
 import com.android.tools.r8.graph.GenericSignature.WildcardIndicator;
 import com.android.tools.r8.utils.ListUtils;
-import java.util.HashSet;
+import com.google.common.collect.ImmutableSet;
+import java.util.Collections;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.function.BiPredicate;
+import java.util.function.Predicate;
 
 public class GenericSignaturePartialTypeArgumentApplier implements GenericSignatureVisitor {
 
   private final Map<String, DexType> substitutions;
+  private final Set<String> liveTypeVariables;
   private final DexType objectType;
-  private final Set<String> introducedClassTypeVariables = new HashSet<>();
-  private final Set<String> introducedMethodTypeVariables = new HashSet<>();
+  private final BiPredicate<DexType, DexType> enclosingPruned;
+  private final Predicate<DexType> hasGenericTypeParameters;
 
   private GenericSignaturePartialTypeArgumentApplier(
-      Map<String, DexType> substitutions, DexType objectType) {
+      Map<String, DexType> substitutions,
+      Set<String> liveTypeVariables,
+      DexType objectType,
+      BiPredicate<DexType, DexType> enclosingPruned,
+      Predicate<DexType> hasGenericTypeParameters) {
     this.substitutions = substitutions;
+    this.liveTypeVariables = liveTypeVariables;
     this.objectType = objectType;
+    this.enclosingPruned = enclosingPruned;
+    this.hasGenericTypeParameters = hasGenericTypeParameters;
   }
 
   public static GenericSignaturePartialTypeArgumentApplier build(
-      DexType objectType, ClassSignature classSignature, Map<String, DexType> substitutions) {
-    GenericSignaturePartialTypeArgumentApplier applier =
-        new GenericSignaturePartialTypeArgumentApplier(substitutions, objectType);
-    classSignature.formalTypeParameters.forEach(
-        parameter -> applier.introducedClassTypeVariables.add(parameter.name));
-    return applier;
+      DexType objectType,
+      BiPredicate<DexType, DexType> enclosingPruned,
+      Predicate<DexType> hasGenericTypeParameters) {
+    return new GenericSignaturePartialTypeArgumentApplier(
+        Collections.emptyMap(),
+        Collections.emptySet(),
+        objectType,
+        enclosingPruned,
+        hasGenericTypeParameters);
+  }
+
+  public GenericSignaturePartialTypeArgumentApplier addSubstitutionsAndVariables(
+      Map<String, DexType> substitutions, Set<String> liveTypeVariables) {
+    return new GenericSignaturePartialTypeArgumentApplier(
+        substitutions, liveTypeVariables, objectType, enclosingPruned, hasGenericTypeParameters);
+  }
+
+  public GenericSignaturePartialTypeArgumentApplier buildForMethod(
+      List<FormalTypeParameter> formals) {
+    if (formals.isEmpty()) {
+      return this;
+    }
+    ImmutableSet.Builder<String> liveVariablesBuilder = ImmutableSet.builder();
+    liveVariablesBuilder.addAll(liveTypeVariables);
+    formals.forEach(
+        formal -> {
+          liveVariablesBuilder.add(formal.name);
+        });
+    return new GenericSignaturePartialTypeArgumentApplier(
+        substitutions, liveTypeVariables, objectType, enclosingPruned, hasGenericTypeParameters);
   }
 
   @Override
@@ -48,12 +85,7 @@
 
   @Override
   public MethodTypeSignature visitMethodSignature(MethodTypeSignature methodSignature) {
-    assert introducedMethodTypeVariables.isEmpty();
-    methodSignature.formalTypeParameters.forEach(
-        parameter -> introducedMethodTypeVariables.add(parameter.name));
-    MethodTypeSignature rewritten = methodSignature.visit(this);
-    introducedMethodTypeVariables.clear();
-    return rewritten;
+    return methodSignature.visit(this);
   }
 
   @Override
@@ -96,9 +128,10 @@
   }
 
   @Override
-  public List<FieldTypeSignature> visitTypeArguments(List<FieldTypeSignature> typeArguments) {
-    if (typeArguments.isEmpty()) {
-      return typeArguments;
+  public List<FieldTypeSignature> visitTypeArguments(
+      DexType type, List<FieldTypeSignature> typeArguments) {
+    if (typeArguments.isEmpty() || !hasGenericTypeParameters.test(type)) {
+      return getEmptyTypeArguments();
     }
     // Wildcards can only be called be used in certain positions:
     // https://docs.oracle.com/javase/tutorial/java/generics/wildcards.html
@@ -121,8 +154,13 @@
   }
 
   @Override
-  public ClassTypeSignature visitSimpleClass(ClassTypeSignature classTypeSignature) {
-    return classTypeSignature.visit(this);
+  public ClassTypeSignature visitEnclosing(
+      ClassTypeSignature enclosingSignature, ClassTypeSignature enclosedSignature) {
+    if (enclosingPruned.test(enclosingSignature.type(), enclosedSignature.type())) {
+      return null;
+    } else {
+      return enclosingSignature.visit(this);
+    }
   }
 
   @Override
@@ -185,8 +223,7 @@
       assert fieldSignature.isTypeVariableSignature();
       String typeVariableName = fieldSignature.asTypeVariableSignature().typeVariable();
       if (substitutions.containsKey(typeVariableName)
-          && !introducedClassTypeVariables.contains(typeVariableName)
-          && !introducedMethodTypeVariables.contains(typeVariableName)) {
+          && !liveTypeVariables.contains(typeVariableName)) {
         DexType substitution = substitutions.get(typeVariableName);
         if (substitution == null) {
           substitution = objectType;
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignaturePrinter.java b/src/main/java/com/android/tools/r8/graph/GenericSignaturePrinter.java
index 739bc27..d04e3af 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignaturePrinter.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignaturePrinter.java
@@ -138,13 +138,15 @@
   }
 
   @Override
-  public ClassTypeSignature visitSimpleClass(ClassTypeSignature classTypeSignature) {
-    printFieldTypeSignature(classTypeSignature, true);
-    return classTypeSignature;
+  public ClassTypeSignature visitEnclosing(
+      ClassTypeSignature enclosingSignature, ClassTypeSignature enclosedSignature) {
+    printFieldTypeSignature(enclosingSignature, true);
+    return enclosingSignature;
   }
 
   @Override
-  public List<FieldTypeSignature> visitTypeArguments(List<FieldTypeSignature> typeArguments) {
+  public List<FieldTypeSignature> visitTypeArguments(
+      DexType type, List<FieldTypeSignature> typeArguments) {
     if (typeArguments.isEmpty()) {
       return typeArguments;
     }
@@ -185,7 +187,7 @@
       }
       // Visit enclosing before printing the type name to ensure we
       if (classTypeSignature.enclosingTypeSignature != null) {
-        visitSimpleClass(classTypeSignature.enclosingTypeSignature);
+        visitEnclosing(classTypeSignature.enclosingTypeSignature, classTypeSignature);
       }
       String renamedString = namingLens.lookupDescriptor(classTypeSignature.type).toString();
       if (classTypeSignature.enclosingTypeSignature == null) {
@@ -205,7 +207,7 @@
         }
         sb.append(".").append(innerClassName);
       }
-      visitTypeArguments(classTypeSignature.typeArguments);
+      visitTypeArguments(null, classTypeSignature.typeArguments);
       if (!printingOuter) {
         sb.append(";");
       }
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeRewriter.java b/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeRewriter.java
index 6df0d8b..956b076 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeRewriter.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeRewriter.java
@@ -4,7 +4,7 @@
 
 package com.android.tools.r8.graph;
 
-import static com.android.tools.r8.graph.GenericSignature.EMPTY_TYPE_ARGUMENTS;
+import static com.android.tools.r8.graph.GenericSignature.getEmptyTypeArguments;
 import static com.google.common.base.Predicates.alwaysFalse;
 
 import com.android.tools.r8.graph.GenericSignature.ClassSignature;
@@ -48,7 +48,7 @@
     this.wasPruned = wasPruned;
     this.lookupType = lookupType;
     this.context = context;
-    objectTypeSignature = new ClassTypeSignature(factory.objectType, EMPTY_TYPE_ARGUMENTS);
+    objectTypeSignature = new ClassTypeSignature(factory.objectType, getEmptyTypeArguments());
   }
 
   public ClassSignature rewrite(ClassSignature classSignature) {
@@ -138,9 +138,7 @@
     @Override
     public ClassTypeSignature visitSuperClass(ClassTypeSignature classTypeSignature) {
       ClassTypeSignature rewritten = classTypeSignature.visit(this);
-      return rewritten == null || rewritten.type() == context
-          ? new ClassTypeSignature(factory.objectType, EMPTY_TYPE_ARGUMENTS)
-          : rewritten;
+      return rewritten == null || rewritten.type() == context ? objectTypeSignature : rewritten;
     }
 
     @Override
@@ -216,12 +214,14 @@
     }
 
     @Override
-    public ClassTypeSignature visitSimpleClass(ClassTypeSignature classTypeSignature) {
-      return classTypeSignature.visit(this);
+    public ClassTypeSignature visitEnclosing(
+        ClassTypeSignature enclosingSignature, ClassTypeSignature enclosedSignature) {
+      return enclosingSignature.visit(this);
     }
 
     @Override
-    public List<FieldTypeSignature> visitTypeArguments(List<FieldTypeSignature> typeArguments) {
+    public List<FieldTypeSignature> visitTypeArguments(
+        DexType type, List<FieldTypeSignature> typeArguments) {
       if (typeArguments.isEmpty()) {
         return typeArguments;
       }
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeVariableRemover.java b/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeVariableRemover.java
index 23500e9..f2a359a 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeVariableRemover.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeVariableRemover.java
@@ -4,122 +4,299 @@
 
 package com.android.tools.r8.graph;
 
-import com.android.tools.r8.graph.GenericSignature.FieldTypeSignature;
+import static com.android.tools.r8.graph.GenericSignatureTypeVariableRemover.TypeParameterContext.empty;
+import static com.google.common.base.Predicates.alwaysFalse;
+
 import com.android.tools.r8.graph.GenericSignature.FormalTypeParameter;
+import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
+import java.util.Collections;
 import java.util.HashMap;
+import java.util.HashSet;
+import java.util.IdentityHashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import java.util.function.Predicate;
 
 public class GenericSignatureTypeVariableRemover {
 
-  private final AppView<?> appView;
-  private final Predicate<InnerClassAttribute> innerClassPruned;
-  private final Predicate<EnclosingMethodAttribute> enclosingClassOrMethodPruned;
+  private final DexType objectType;
+  private final Map<DexReference, TypeParameterSubstitutions> formalsInfo;
+  private final Map<DexReference, DexReference> enclosingInfo;
 
-  public GenericSignatureTypeVariableRemover(
-      AppView<?> appView,
-      Predicate<InnerClassAttribute> innerClassPruned,
-      Predicate<EnclosingMethodAttribute> enclosingClassOrMethodPruned) {
-    this.appView = appView;
-    this.innerClassPruned = innerClassPruned;
-    this.enclosingClassOrMethodPruned = enclosingClassOrMethodPruned;
+  private static class TypeParameterSubstitutions {
+
+    private final Map<String, DexType> parametersWithBounds;
+
+    private TypeParameterSubstitutions(Map<String, DexType> parametersWithBounds) {
+      this.parametersWithBounds = parametersWithBounds;
+    }
+
+    private static TypeParameterSubstitutions create(List<FormalTypeParameter> formals) {
+      Map<String, DexType> map = new IdentityHashMap<>();
+      formals.forEach(
+          formal -> {
+            DexType bound = null;
+            if (formal.getClassBound() != null
+                && formal.getClassBound().hasSignature()
+                && formal.getClassBound().isClassTypeSignature()) {
+              bound = formal.getClassBound().asClassTypeSignature().type;
+            } else if (!formal.getInterfaceBounds().isEmpty()
+                && formal.getInterfaceBounds().get(0).isClassTypeSignature()) {
+              bound = formal.getInterfaceBounds().get(0).asClassTypeSignature().type;
+            }
+            map.put(formal.getName(), bound);
+          });
+      return new TypeParameterSubstitutions(map);
+    }
   }
 
-  public void removeDeadGenericSignatureTypeVariables(DexProgramClass clazz) {
-    if (clazz.getClassSignature().hasNoSignature() || clazz.getClassSignature().isInvalid()) {
-      return;
+  static class TypeParameterContext {
+
+    private static final TypeParameterContext EMPTY =
+        new TypeParameterContext(Collections.emptyMap(), Collections.emptySet());
+
+    private final Map<String, DexType> prunedParametersWithBounds;
+    private final Set<String> liveParameters;
+
+    private TypeParameterContext(
+        Map<String, DexType> prunedParametersWithBounds, Set<String> liveParameters) {
+      this.prunedParametersWithBounds = prunedParametersWithBounds;
+      this.liveParameters = liveParameters;
     }
-    Map<String, DexType> substitutions = new HashMap<>();
-    getPrunedTypeParameters(clazz, substitutions, false);
-    if (substitutions.isEmpty()) {
-      return;
+
+    private TypeParameterContext combine(TypeParameterSubstitutions information, boolean dead) {
+      if (information == null) {
+        return this;
+      }
+      HashMap<String, DexType> newPruned = new HashMap<>(prunedParametersWithBounds);
+      HashSet<String> newLiveParameters = new HashSet<>(liveParameters);
+      information.parametersWithBounds.forEach(
+          (param, type) -> {
+            if (dead) {
+              newPruned.put(param, type);
+              newLiveParameters.remove(param);
+            } else {
+              newLiveParameters.add(param);
+              newPruned.remove(param);
+            }
+          });
+      return new TypeParameterContext(newPruned, newLiveParameters);
     }
-    GenericSignaturePartialTypeArgumentApplier genericSignatureTypeArgumentApplier =
-        GenericSignaturePartialTypeArgumentApplier.build(
-            appView.dexItemFactory().objectType, clazz.getClassSignature(), substitutions);
-    clazz.setClassSignature(
-        genericSignatureTypeArgumentApplier.visitClassSignature(clazz.getClassSignature()));
-    clazz
-        .methods()
-        .forEach(
-            method -> {
-              if (method.getGenericSignature().hasSignature()
-                  && method.getGenericSignature().isValid()
-                  && method.isVirtualMethod()) {
-                method.setGenericSignature(
-                    genericSignatureTypeArgumentApplier.visitMethodSignature(
-                        method.getGenericSignature()));
-              }
-            });
-    clazz
-        .instanceFields()
-        .forEach(
-            field -> {
-              if (field.getGenericSignature().hasSignature()
-                  && field.getGenericSignature().isValid()) {
-                field.setGenericSignature(
-                    genericSignatureTypeArgumentApplier.visitFieldTypeSignature(
-                        field.getGenericSignature()));
-              }
-            });
+
+    public static TypeParameterContext empty() {
+      return EMPTY;
+    }
   }
 
-  private void getPrunedTypeParameters(
-      DexClass clazz, Map<String, DexType> substitutions, boolean seenPruned) {
-    InnerClassAttribute innerClassAttribute = clazz.getInnerClassAttributeForThisClass();
-    if (innerClassAttribute != null
-        && innerClassAttribute.getOuter() != null
-        && (seenPruned || innerClassPruned.test(innerClassAttribute))) {
-      DexClass outerClass = appView.definitionFor(innerClassAttribute.getOuter());
-      if (outerClass != null && outerClass.getClassSignature().isValid()) {
-        updateMap(outerClass.getClassSignature().getFormalTypeParameters(), substitutions);
-        getPrunedTypeParameters(outerClass, substitutions, true);
-      }
-    }
-    if (clazz.getEnclosingMethodAttribute() != null
-        && (seenPruned || enclosingClassOrMethodPruned.test(clazz.getEnclosingMethodAttribute()))) {
-      DexClass outerClass =
-          appView.definitionFor(clazz.getEnclosingMethodAttribute().getEnclosingType());
-      if (outerClass == null) {
-        return;
-      }
-      if (clazz.getEnclosingMethodAttribute().getEnclosingMethod() != null) {
-        DexEncodedMethod enclosingMethod =
-            outerClass.lookupMethod(clazz.getEnclosingMethodAttribute().getEnclosingMethod());
-        if (enclosingMethod != null) {
-          updateMap(enclosingMethod.getGenericSignature().getFormalTypeParameters(), substitutions);
-          if (enclosingMethod.isStatic()) {
-            return;
+  private GenericSignatureTypeVariableRemover(
+      Map<DexReference, TypeParameterSubstitutions> formalsInfo,
+      Map<DexReference, DexReference> enclosingInfo,
+      DexType objectType) {
+    this.formalsInfo = formalsInfo;
+    this.enclosingInfo = enclosingInfo;
+    this.objectType = objectType;
+  }
+
+  public static GenericSignatureTypeVariableRemover create(
+      AppView<?> appView, List<DexProgramClass> programClasses) {
+    Map<DexReference, TypeParameterSubstitutions> formalsInfo = new IdentityHashMap<>();
+    Map<DexReference, DexReference> enclosingInfo = new IdentityHashMap<>();
+    programClasses.forEach(
+        clazz -> {
+          // Build up a map of type variables to bounds for every reference such that we can
+          // lookup the information even after we prune the generic signatures.
+          if (clazz.getClassSignature().isValid()) {
+            formalsInfo.put(
+                clazz.getReference(),
+                TypeParameterSubstitutions.create(clazz.classSignature.getFormalTypeParameters()));
+            clazz.forEachProgramMethod(
+                method -> {
+                  MethodTypeSignature methodSignature =
+                      method.getDefinition().getGenericSignature();
+                  if (methodSignature.isValid()) {
+                    formalsInfo.put(
+                        method.getReference(),
+                        TypeParameterSubstitutions.create(
+                            methodSignature.getFormalTypeParameters()));
+                  }
+                });
           }
+          // Build up an enclosing class context such that the enclosing class can be looked up
+          // even after inner class and enclosing method attribute attributes are removed.
+          InnerClassAttribute innerClassAttribute = clazz.getInnerClassAttributeForThisClass();
+          if (innerClassAttribute != null) {
+            enclosingInfo.put(clazz.getType(), innerClassAttribute.getOuter());
+          }
+          EnclosingMethodAttribute enclosingMethodAttribute = clazz.getEnclosingMethodAttribute();
+          if (enclosingMethodAttribute != null) {
+            enclosingInfo.put(
+                clazz.getType(),
+                enclosingMethodAttribute.getEnclosingMethod() != null
+                    ? enclosingMethodAttribute.getEnclosingMethod()
+                    : enclosingMethodAttribute.getEnclosingClass());
+          }
+        });
+    return new GenericSignatureTypeVariableRemover(
+        formalsInfo, enclosingInfo, appView.dexItemFactory().objectType);
+  }
+
+  private TypeParameterContext computeTypeParameterContext(
+      AppView<?> appView,
+      DexReference reference,
+      Predicate<DexType> wasPruned,
+      boolean seenPruned) {
+    if (reference == null) {
+      return empty();
+    }
+    DexType contextType = reference.getContextType();
+    // TODO(b/187035453): We should visit generic signatures in the enqueuer.
+    DexClass clazz =
+        appView.appInfo().definitionForWithoutExistenceAssert(reference.getContextType());
+    boolean prunedHere = seenPruned || clazz == null;
+    if (appView.hasLiveness()
+        && appView
+            .withLiveness()
+            .appInfo()
+            .getMissingClasses()
+            .contains(reference.getContextType())) {
+      prunedHere = seenPruned;
+    }
+    if (reference.isDexMethod()) {
+      TypeParameterSubstitutions typeParameterSubstitutions = formalsInfo.get(reference);
+      if (clazz != null) {
+        assert clazz.isProgramClass();
+        DexEncodedMethod method = clazz.lookupMethod(reference.asDexMethod());
+        if (method == null) {
+          prunedHere = true;
+        } else if (method.isStatic()) {
+          // Static methods define their own scope.
+          return empty().combine(typeParameterSubstitutions, seenPruned);
         }
       }
-      if (outerClass.getClassSignature().isValid()) {
-        updateMap(outerClass.getClassSignature().getFormalTypeParameters(), substitutions);
+      // Lookup the formals in the enclosing context.
+      return computeTypeParameterContext(
+              appView,
+              contextType,
+              wasPruned,
+              prunedHere
+                  || hasPrunedRelationship(
+                      appView, enclosingInfo.get(contextType), contextType, wasPruned))
+          // Add the formals for the class.
+          .combine(formalsInfo.get(contextType), prunedHere)
+          // Add the formals for the method.
+          .combine(formalsInfo.get(reference), prunedHere);
+    }
+    assert reference.isDexType();
+    return computeTypeParameterContext(
+            appView,
+            enclosingInfo.get(reference),
+            wasPruned,
+            prunedHere
+                || hasPrunedRelationship(
+                    appView, enclosingInfo.get(reference), contextType, wasPruned))
+        .combine(formalsInfo.get(reference), prunedHere);
+  }
+
+  private static boolean hasPrunedRelationship(
+      AppView<?> appView,
+      DexReference enclosingReference,
+      DexType enclosedClassType,
+      Predicate<DexType> wasPruned) {
+    assert enclosedClassType != null;
+    if (enclosingReference == null) {
+      // There is no relationship, so it does not really matter what we return since the
+      // algorithm will return the base case.
+      return true;
+    }
+    if (wasPruned.test(enclosingReference.getContextType()) || wasPruned.test(enclosedClassType)) {
+      return true;
+    }
+    DexClass enclosingClass = appView.definitionFor(enclosingReference.getContextType());
+    DexClass enclosedClass = appView.definitionFor(enclosedClassType);
+    if (enclosingClass == null || enclosedClass == null) {
+      return true;
+    }
+    if (enclosingReference.isDexMethod()) {
+      return enclosedClass.getEnclosingMethodAttribute() == null
+          || enclosedClass.getEnclosingMethodAttribute().getEnclosingMethod() != enclosingReference;
+    } else {
+      InnerClassAttribute innerClassAttribute = enclosedClass.getInnerClassAttributeForThisClass();
+      if (innerClassAttribute != null) {
+        return innerClassAttribute.getOuter() != enclosingReference;
       }
-      getPrunedTypeParameters(outerClass, substitutions, true);
+      return enclosedClass.getEnclosingMethodAttribute() == null
+          || enclosedClass.getEnclosingMethodAttribute().getEnclosingClass() != enclosingReference;
     }
   }
 
-  private void updateMap(
-      List<FormalTypeParameter> formalTypeParameters, Map<String, DexType> substitutions) {
-    // We are updating the map going from inner most to outer, thus the any overriding formal type
-    // parameters will be in the substitution map already.
-    formalTypeParameters.forEach(
-        parameter -> {
-          if (substitutions.containsKey(parameter.getName())) {
-            return;
-          }
-          // The null substitution will use the wildcard as argument, which is smaller than using
-          // Ljava/lang/Object;
-          DexType substitution = null;
-          FieldTypeSignature classBound = parameter.getClassBound();
-          if (classBound != null
-              && classBound.hasSignature()
-              && classBound.isClassTypeSignature()) {
-            substitution = classBound.asClassTypeSignature().type();
-          }
-          substitutions.put(parameter.getName(), substitution);
-        });
+  private static boolean hasGenericTypeVariables(
+      AppView<?> appView, DexType type, Predicate<DexType> wasPruned) {
+    if (wasPruned.test(type)) {
+      return false;
+    }
+    DexClass clazz = appView.definitionFor(type);
+    if (clazz == null || clazz.isNotProgramClass() || clazz.getClassSignature().isInvalid()) {
+      return true;
+    }
+    return !clazz.getClassSignature().getFormalTypeParameters().isEmpty();
+  }
+
+  public void removeDeadGenericSignatureTypeVariables(AppView<?> appView) {
+    Predicate<DexType> wasPruned =
+        appView.hasLiveness() ? appView.withLiveness().appInfo()::wasPruned : alwaysFalse();
+    GenericSignaturePartialTypeArgumentApplier baseArgumentApplier =
+        GenericSignaturePartialTypeArgumentApplier.build(
+            objectType,
+            (enclosing, enclosed) -> hasPrunedRelationship(appView, enclosing, enclosed, wasPruned),
+            type -> hasGenericTypeVariables(appView, type, wasPruned));
+    appView
+        .appInfo()
+        .classes()
+        .forEach(
+            clazz -> {
+              if (clazz.getClassSignature().isInvalid()) {
+                return;
+              }
+              TypeParameterContext computedClassFormals =
+                  computeTypeParameterContext(appView, clazz.getType(), wasPruned, false);
+              GenericSignaturePartialTypeArgumentApplier classArgumentApplier =
+                  baseArgumentApplier.addSubstitutionsAndVariables(
+                      computedClassFormals.prunedParametersWithBounds,
+                      computedClassFormals.liveParameters);
+              clazz.setClassSignature(
+                  classArgumentApplier.visitClassSignature(clazz.getClassSignature()));
+              clazz
+                  .methods()
+                  .forEach(
+                      method -> {
+                        MethodTypeSignature methodSignature = method.getGenericSignature();
+                        if (methodSignature.hasSignature()
+                            && method.getGenericSignature().isValid()) {
+                          if (method.isStatic()) {
+                            method.setGenericSignature(
+                                baseArgumentApplier
+                                    .buildForMethod(methodSignature.getFormalTypeParameters())
+                                    .visitMethodSignature(methodSignature));
+                          } else {
+                            method.setGenericSignature(
+                                classArgumentApplier
+                                    .buildForMethod(methodSignature.getFormalTypeParameters())
+                                    .visitMethodSignature(methodSignature));
+                          }
+                        }
+                      });
+              clazz
+                  .instanceFields()
+                  .forEach(
+                      field -> {
+                        if (field.getGenericSignature().hasSignature()
+                            && field.getGenericSignature().isValid()) {
+                          field.setGenericSignature(
+                              classArgumentApplier.visitFieldTypeSignature(
+                                  field.getGenericSignature()));
+                        }
+                      });
+            });
   }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeVisitor.java b/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeVisitor.java
index dff8d5d..c6d0e6a 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeVisitor.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeVisitor.java
@@ -116,8 +116,9 @@
   }
 
   @Override
-  public ClassTypeSignature visitSimpleClass(ClassTypeSignature classTypeSignature) {
-    return classTypeSignature.visit(this);
+  public ClassTypeSignature visitEnclosing(
+      ClassTypeSignature enclosingSignature, ClassTypeSignature enclosedSignature) {
+    return enclosingSignature.visit(this);
   }
 
   @Override
@@ -142,7 +143,8 @@
   }
 
   @Override
-  public List<FieldTypeSignature> visitTypeArguments(List<FieldTypeSignature> typeArguments) {
+  public List<FieldTypeSignature> visitTypeArguments(
+      DexType type, List<FieldTypeSignature> typeArguments) {
     typeArguments.forEach(this::visitFieldTypeSignature);
     return typeArguments;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignatureVisitor.java b/src/main/java/com/android/tools/r8/graph/GenericSignatureVisitor.java
index ba1d8f2..b321ad1 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureVisitor.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureVisitor.java
@@ -66,7 +66,8 @@
     throw new Unreachable("Implement if visited");
   }
 
-  default ClassTypeSignature visitSimpleClass(ClassTypeSignature classTypeSignature) {
+  default ClassTypeSignature visitEnclosing(
+      ClassTypeSignature enclosingSignature, ClassTypeSignature enclosedSignature) {
     throw new Unreachable("Implement if visited");
   }
 
@@ -82,7 +83,8 @@
     throw new Unreachable("Implement if visited");
   }
 
-  default List<FieldTypeSignature> visitTypeArguments(List<FieldTypeSignature> typeArguments) {
+  default List<FieldTypeSignature> visitTypeArguments(
+      DexType type, List<FieldTypeSignature> typeArguments) {
     throw new Unreachable("Implement if visited");
   }
 
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java
index 23b27f3..880890d 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java
@@ -29,6 +29,7 @@
 import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.graph.ParameterAnnotationsList;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.horizontalclassmerging.code.ClassInitializerSynthesizedCode;
 import com.android.tools.r8.ir.analysis.value.NumberFromIntervalValue;
 import com.android.tools.r8.ir.optimize.info.OptimizationFeedback;
 import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackSimple;
@@ -167,10 +168,9 @@
    */
   DexMethod renameDirectMethod(ProgramMethod method) {
     assert method.getDefinition().belongsToDirectPool();
-    return dexItemFactory.createFreshMethodName(
-        method.getDefinition().getReference().name.toSourceString(),
-        method.getHolderType(),
-        method.getDefinition().getProto(),
+    return dexItemFactory.createFreshMethodNameWithoutHolder(
+        method.getName().toSourceString(),
+        method.getProto(),
         group.getTarget().getType(),
         classMethodsBuilder::isFresh);
   }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorMerger.java
index 25066e7..fb98a86 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorMerger.java
@@ -18,6 +18,7 @@
 import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
 import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.graph.ParameterAnnotationsList;
+import com.android.tools.r8.horizontalclassmerging.code.ConstructorEntryPointSynthesizedCode;
 import com.android.tools.r8.ir.conversion.ExtraConstantIntParameter;
 import com.android.tools.r8.ir.conversion.ExtraParameter;
 import com.android.tools.r8.ir.conversion.ExtraUnusedNullParameter;
@@ -109,7 +110,7 @@
   private DexMethod moveConstructor(
       ClassMethodsBuilder classMethodsBuilder, DexEncodedMethod constructor) {
     DexMethod method =
-        dexItemFactory.createFreshMethodName(
+        dexItemFactory.createFreshMethodNameWithHolder(
             TEMPORARY_INSTANCE_INITIALIZER_PREFIX,
             constructor.getHolderType(),
             constructor.getProto(),
@@ -173,9 +174,8 @@
     // unintended side-effects such as leading to unused argument removal being applied to the
     // synthesized constructor all-though it by construction doesn't have any unused arguments.
     DexMethod bridgeConstructorReference =
-        dexItemFactory.createFreshMethodName(
+        dexItemFactory.createFreshMethodNameWithoutHolder(
             "$r8$init$bridge",
-            null,
             originalConstructorReference.getProto(),
             originalConstructorReference.getHolderType(),
             classMethodsBuilder::isFresh);
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
index d475710..53ca8c8 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
@@ -254,9 +254,8 @@
             Collections.nCopies(extraNulls, new ExtraUnusedNullParameter()));
       } else {
         newMethodReference =
-            dexItemFactory.createFreshMethodName(
+            dexItemFactory.createFreshMethodNameWithoutHolder(
                 newMethodReference.getName().toSourceString(),
-                null,
                 newMethodReference.proto,
                 newMethodReference.holder,
                 tryMethod ->
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java
index efcbb27..cb810de 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java
@@ -18,6 +18,7 @@
 import com.android.tools.r8.graph.ParameterAnnotationsList;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.graph.ResolutionResult.SingleResolutionResult;
+import com.android.tools.r8.horizontalclassmerging.code.VirtualMethodEntryPointSynthesizedCode;
 import com.android.tools.r8.ir.synthetic.AbstractSynthesizedCode;
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.OptionalBool;
@@ -101,7 +102,7 @@
   private DexMethod moveMethod(ClassMethodsBuilder classMethodsBuilder, ProgramMethod oldMethod) {
     DexMethod oldMethodReference = oldMethod.getReference();
     DexMethod method =
-        dexItemFactory.createFreshMethodName(
+        dexItemFactory.createFreshMethodNameWithHolder(
             oldMethodReference.name.toSourceString(),
             oldMethod.getHolderType(),
             oldMethodReference.proto,
@@ -131,8 +132,10 @@
     if (result.isBridge() && Iterables.any(allFlags, flags -> !flags.isBridge())) {
       result.unsetBridge();
     }
-    if (result.isFinal() && Iterables.any(allFlags, flags -> !flags.isFinal())) {
-      result.unsetFinal();
+    if (result.isFinal()) {
+      if (methods.size() < group.size() || Iterables.any(allFlags, flags -> !flags.isFinal())) {
+        result.unsetFinal();
+      }
     }
     if (result.isSynthetic() && Iterables.any(allFlags, flags -> !flags.isSynthetic())) {
       result.unsetSynthetic();
@@ -259,9 +262,8 @@
     DexMethod originalMethodReference =
         appView.graphLens().getOriginalMethodSignature(representative.getReference());
     DexMethod bridgeMethodReference =
-        dexItemFactory.createFreshMethodName(
+        dexItemFactory.createFreshMethodNameWithoutHolder(
             originalMethodReference.getName().toSourceString() + "$bridge",
-            null,
             originalMethodReference.proto,
             originalMethodReference.getHolderType(),
             classMethodsBuilder::isFresh);
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassInitializerSynthesizedCode.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/code/ClassInitializerSynthesizedCode.java
similarity index 98%
rename from src/main/java/com/android/tools/r8/horizontalclassmerging/ClassInitializerSynthesizedCode.java
rename to src/main/java/com/android/tools/r8/horizontalclassmerging/code/ClassInitializerSynthesizedCode.java
index d78d74d..99d8f48 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassInitializerSynthesizedCode.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/code/ClassInitializerSynthesizedCode.java
@@ -2,7 +2,7 @@
 // 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.horizontalclassmerging;
+package com.android.tools.r8.horizontalclassmerging.code;
 
 import static com.android.tools.r8.utils.ConsumerUtils.apply;
 import static java.lang.Integer.max;
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorEntryPointSynthesizedCode.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/code/ConstructorEntryPointSynthesizedCode.java
similarity index 92%
rename from src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorEntryPointSynthesizedCode.java
rename to src/main/java/com/android/tools/r8/horizontalclassmerging/code/ConstructorEntryPointSynthesizedCode.java
index bbce62b..8c649b0 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorEntryPointSynthesizedCode.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/code/ConstructorEntryPointSynthesizedCode.java
@@ -2,11 +2,12 @@
 // 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.horizontalclassmerging;
+package com.android.tools.r8.horizontalclassmerging.code;
 
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.UseRegistry;
+import com.android.tools.r8.horizontalclassmerging.ConstructorEntryPoint;
 import com.android.tools.r8.ir.synthetic.AbstractSynthesizedCode;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
 import java.util.function.Consumer;
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodEntryPointSynthesizedCode.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/code/VirtualMethodEntryPointSynthesizedCode.java
similarity index 87%
rename from src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodEntryPointSynthesizedCode.java
rename to src/main/java/com/android/tools/r8/horizontalclassmerging/code/VirtualMethodEntryPointSynthesizedCode.java
index a1aaa6b..3995fd8 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodEntryPointSynthesizedCode.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/code/VirtualMethodEntryPointSynthesizedCode.java
@@ -1,12 +1,13 @@
-// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// Copyright (c) 2021, 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.horizontalclassmerging;
+package com.android.tools.r8.horizontalclassmerging.code;
 
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.UseRegistry;
+import com.android.tools.r8.horizontalclassmerging.VirtualMethodEntryPoint;
 import com.android.tools.r8.ir.synthetic.SynthesizedCode;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
 import java.util.function.Consumer;
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 a241a05..2cbebcd 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
@@ -88,6 +88,7 @@
 import com.android.tools.r8.ir.optimize.string.StringOptimizer;
 import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator;
 import com.android.tools.r8.ir.regalloc.RegisterAllocator;
+import com.android.tools.r8.ir.synthetic.SynthesizedCode;
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.naming.IdentifierNameStringMarker;
 import com.android.tools.r8.position.MethodPosition;
@@ -540,9 +541,6 @@
       return;
     }
     checkPrefixMerging(method);
-    if (!needsIRConversion(definition.getCode(), method)) {
-      return;
-    }
     if (options.isGeneratingClassFiles()
         || !(options.passthroughDexCode && definition.getCode().isDexCode())) {
       // We do not process in call graph order, so anything could be a leaf.
@@ -560,7 +558,10 @@
     }
   }
 
-  private boolean needsIRConversion(Code code, ProgramMethod method) {
+  private boolean needsIRConversion(ProgramMethod method) {
+    if (appView.enableWholeProgramOptimizations()) {
+      return true;
+    }
     if (options.testing.forceIRForCfToCfDesugar) {
       return true;
     }
@@ -570,23 +571,23 @@
     if (!options.cfToCfDesugar) {
       return true;
     }
-    if (instructionDesugaring.needsDesugaring(method)) {
-      return true;
-    }
     if (desugaredLibraryAPIConverter != null
         && desugaredLibraryAPIConverter.shouldRegisterCallback(method)) {
       return true;
     }
-
-    NeedsIRDesugarUseRegistry useRegistry =
-        new NeedsIRDesugarUseRegistry(
-            appView,
-            desugaredLibraryRetargeter,
-            interfaceMethodRewriter,
-            desugaredLibraryAPIConverter);
-    method.registerCodeReferences(useRegistry);
-
-    return useRegistry.needsDesugaring();
+    if (method.getDefinition().getCode() instanceof SynthesizedCode) {
+      // SynthesizedCode needs IR to generate the code.
+      return true;
+    } else {
+      NeedsIRDesugarUseRegistry useRegistry =
+          new NeedsIRDesugarUseRegistry(
+              appView,
+              desugaredLibraryRetargeter,
+              interfaceMethodRewriter,
+              desugaredLibraryAPIConverter);
+      method.registerCodeReferences(useRegistry);
+      return useRegistry.needsDesugaring();
+    }
   }
 
   private void checkPrefixMerging(ProgramMethod method) {
@@ -1119,10 +1120,12 @@
     if (options.testing.hookInIrConversion != null) {
       options.testing.hookInIrConversion.run();
     }
-    if (options.skipIR) {
+
+    if (!needsIRConversion(method) || options.skipIR) {
       feedback.markProcessed(method.getDefinition(), ConstraintWithTarget.NEVER);
       return Timing.empty();
     }
+
     IRCode code = method.buildIR(appView);
     if (code == null) {
       feedback.markProcessed(method.getDefinition(), ConstraintWithTarget.NEVER);
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/PostMethodProcessor.java b/src/main/java/com/android/tools/r8/ir/conversion/PostMethodProcessor.java
index 06ddf34..4623428 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/PostMethodProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/PostMethodProcessor.java
@@ -149,7 +149,7 @@
     Deque<SortedProgramMethodSet> waves = new ArrayDeque<>();
     int waveCount = 1;
     while (!callGraph.isEmpty()) {
-      SortedProgramMethodSet wave = callGraph.extractRoots();
+      SortedProgramMethodSet wave = callGraph.extractLeaves();
       waves.addLast(wave);
       if (Log.ENABLED && Log.isLoggingEnabledFor(PostMethodProcessor.class)) {
         Log.info(getClass(), "Wave #%d: %d", waveCount++, wave.size());
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/RecordCfMethods.java b/src/main/java/com/android/tools/r8/ir/desugar/RecordCfMethods.java
index 85a7982..47bc98b 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/RecordCfMethods.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/RecordCfMethods.java
@@ -44,8 +44,6 @@
 public final class RecordCfMethods {
 
   public static void registerSynthesizedCodeReferences(DexItemFactory factory) {
-    factory.createSynthesizedType(
-        "Lcom/android/tools/r8/desugar/records/RecordMethods$RecordStub;");
     factory.createSynthesizedType("Ljava/lang/Record;");
     factory.createSynthesizedType("Ljava/util/Arrays;");
     factory.createSynthesizedType("[Ljava/lang/Object;");
@@ -121,9 +119,7 @@
                 new Int2ReferenceAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
-                      FrameType.initialized(
-                          options.itemFactory.createType(
-                              "Lcom/android/tools/r8/desugar/records/RecordMethods$RecordStub;")),
+                      FrameType.initialized(options.itemFactory.createType("Ljava/lang/Record;")),
                       FrameType.initialized(options.itemFactory.objectType)
                     }),
                 new ArrayDeque<>(Arrays.asList())),
@@ -133,9 +129,7 @@
                 new Int2ReferenceAVLTreeMap<>(
                     new int[] {0, 1},
                     new FrameType[] {
-                      FrameType.initialized(
-                          options.itemFactory.createType(
-                              "Lcom/android/tools/r8/desugar/records/RecordMethods$RecordStub;")),
+                      FrameType.initialized(options.itemFactory.createType("Ljava/lang/Record;")),
                       FrameType.initialized(options.itemFactory.objectType)
                     }),
                 new ArrayDeque<>(
@@ -240,9 +234,7 @@
                 new Int2ReferenceAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
-                      FrameType.initialized(
-                          options.itemFactory.createType(
-                              "Lcom/android/tools/r8/desugar/records/RecordMethods$RecordStub;")),
+                      FrameType.initialized(options.itemFactory.createType("Ljava/lang/Record;")),
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.stringType)
                     }),
@@ -263,9 +255,7 @@
                 new Int2ReferenceAVLTreeMap<>(
                     new int[] {0, 1, 2},
                     new FrameType[] {
-                      FrameType.initialized(
-                          options.itemFactory.createType(
-                              "Lcom/android/tools/r8/desugar/records/RecordMethods$RecordStub;")),
+                      FrameType.initialized(options.itemFactory.createType("Ljava/lang/Record;")),
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.stringType)
                     }),
@@ -325,9 +315,7 @@
                 new Int2ReferenceAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5, 6},
                     new FrameType[] {
-                      FrameType.initialized(
-                          options.itemFactory.createType(
-                              "Lcom/android/tools/r8/desugar/records/RecordMethods$RecordStub;")),
+                      FrameType.initialized(options.itemFactory.createType("Ljava/lang/Record;")),
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/String;")),
@@ -398,9 +386,7 @@
                 new Int2ReferenceAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5, 6},
                     new FrameType[] {
-                      FrameType.initialized(
-                          options.itemFactory.createType(
-                              "Lcom/android/tools/r8/desugar/records/RecordMethods$RecordStub;")),
+                      FrameType.initialized(options.itemFactory.createType("Ljava/lang/Record;")),
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/String;")),
@@ -416,9 +402,7 @@
                 new Int2ReferenceAVLTreeMap<>(
                     new int[] {0, 1, 2, 3, 4, 5},
                     new FrameType[] {
-                      FrameType.initialized(
-                          options.itemFactory.createType(
-                              "Lcom/android/tools/r8/desugar/records/RecordMethods$RecordStub;")),
+                      FrameType.initialized(options.itemFactory.createType("Ljava/lang/Record;")),
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.stringType),
                       FrameType.initialized(options.itemFactory.createType("[Ljava/lang/String;")),
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/RecordRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/RecordRewriter.java
index b9a8880..1b5e6aa 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/RecordRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/RecordRewriter.java
@@ -130,7 +130,11 @@
     assert !instruction.isInitClass();
     if (instruction.isInvokeDynamic() && needsDesugaring(instruction.asInvokeDynamic(), context)) {
       return desugarInvokeDynamicOnRecord(
-          instruction.asInvokeDynamic(), context, eventConsumer, methodProcessingContext);
+          instruction.asInvokeDynamic(),
+          localStackAllocator,
+          context,
+          eventConsumer,
+          methodProcessingContext);
     }
     if (instruction.isInvoke()) {
       CfInvoke cfInvoke = instruction.asInvoke();
@@ -146,6 +150,7 @@
 
   public List<CfInstruction> desugarInvokeDynamicOnRecord(
       CfInvokeDynamic invokeDynamic,
+      LocalStackAllocator localStackAllocator,
       ProgramMethod context,
       CfInstructionDesugaringEventConsumer eventConsumer,
       MethodProcessingContext methodProcessingContext) {
@@ -166,7 +171,13 @@
           ClassNameComputationInfo.ClassNameMapping.SIMPLE_NAME.map(
               recordValueType.getValue().toDescriptorString(), context.getHolder(), factory);
       return desugarInvokeRecordToString(
-          recordClass, fieldNames, fields, simpleName, eventConsumer, methodProcessingContext);
+          recordClass,
+          fieldNames,
+          fields,
+          simpleName,
+          localStackAllocator,
+          eventConsumer,
+          methodProcessingContext);
     }
     if (callSite.methodName == factory.hashCodeMethodName) {
       return desugarInvokeRecordHashCode(
@@ -273,12 +284,14 @@
       DexString fieldNames,
       DexField[] fields,
       DexString simpleName,
+      LocalStackAllocator localStackAllocator,
       CfInstructionDesugaringEventConsumer eventConsumer,
       MethodProcessingContext methodProcessingContext) {
     ensureGetFieldsAsObjects(recordClass, fields, eventConsumer);
     ArrayList<CfInstruction> instructions = new ArrayList<>();
     instructions.add(new CfConstString(simpleName));
     instructions.add(new CfConstString(fieldNames));
+    localStackAllocator.allocateLocalStack(2);
     ProgramMethod programMethod =
         synthesizeRecordHelper(
             recordToStringHelperProto,
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/itf/InterfaceProcessor.java b/src/main/java/com/android/tools/r8/ir/desugar/itf/InterfaceProcessor.java
index 206a3ed..e8e1cdd 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/itf/InterfaceProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/itf/InterfaceProcessor.java
@@ -233,12 +233,14 @@
     CfCode code =
         new CfCode(
             companionType,
-            1,
+            clinitField.getType().isWideType() ? 2 : 1,
             0,
             ImmutableList.of(
                 new CfFieldInstruction(
                     Opcodes.GETSTATIC, clinitField.getReference(), clinitField.getReference()),
-                new CfStackInstruction(Opcode.Pop),
+                clinitField.getType().isWideType()
+                    ? new CfStackInstruction(Opcode.Pop2)
+                    : new CfStackInstruction(Opcode.Pop),
                 new CfReturnVoid()),
             ImmutableList.of(),
             ImmutableList.of());
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CallSiteOptimizationInfoPropagator.java b/src/main/java/com/android/tools/r8/ir/optimize/CallSiteOptimizationInfoPropagator.java
index 43be45b..2fdd282 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CallSiteOptimizationInfoPropagator.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CallSiteOptimizationInfoPropagator.java
@@ -94,6 +94,11 @@
     if (mode != Mode.COLLECT) {
       return;
     }
+
+    if (appView.appInfo().isMethodTargetedByInvokeDynamic(code.context().getReference())) {
+      abandonCallSitePropagationForMethodAndOverrides(code.context());
+    }
+
     ProgramMethod context = code.context();
     for (Instruction instruction : code.instructions()) {
       if (instruction.isInvokeMethod()) {
@@ -286,6 +291,31 @@
     }
   }
 
+  private void abandonCallSitePropagationForMethodAndOverrides(ProgramMethod method) {
+    Set<ProgramMethod> abandonSet = Sets.newIdentityHashSet();
+    if (method.getDefinition().isNonPrivateVirtualMethod()) {
+      SingleResolutionResult resolutionResult =
+          new SingleResolutionResult(
+              method.getHolder(), method.getHolder(), method.getDefinition());
+      resolutionResult
+          .lookupVirtualDispatchTargets(method.getHolder(), appView.appInfo())
+          .forEach(
+              methodTarget -> {
+                if (methodTarget.isProgramMethod()) {
+                  abandonSet.add(methodTarget.asProgramMethod());
+                }
+              },
+              lambdaTarget -> {
+                if (lambdaTarget.getImplementationMethod().isProgramMethod()) {
+                  abandonSet.add(lambdaTarget.getImplementationMethod().asProgramMethod());
+                }
+              });
+    } else {
+      abandonSet.add(method);
+    }
+    abandonCallSitePropagation(abandonSet::forEach);
+  }
+
   private CallSiteOptimizationInfo computeCallSiteOptimizationInfoFromArguments(
       InvokeMethod invoke, ProgramMethod context, Timing timing) {
     timing.begin("Compute argument info");
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxer.java b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxer.java
index bbbb543..bba0af1 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxer.java
@@ -350,7 +350,10 @@
       markEnumAsUnboxable(Reason.CONST_CLASS, enumClass);
       return;
     }
-    for (Instruction user : constClass.outValue().uniqueUsers()) {
+    for (Instruction user : constClass.outValue().aliasedUsers()) {
+      if (user.isAssume()) {
+        continue;
+      }
       if (user.isInvokeVirtual()
           && isUnboxableNameMethod(user.asInvokeVirtual().getInvokedMethod())) {
         continue;
diff --git a/src/main/java/com/android/tools/r8/naming/signature/GenericSignatureRewriter.java b/src/main/java/com/android/tools/r8/naming/signature/GenericSignatureRewriter.java
index 3893e32..c44e4e7 100644
--- a/src/main/java/com/android/tools/r8/naming/signature/GenericSignatureRewriter.java
+++ b/src/main/java/com/android/tools/r8/naming/signature/GenericSignatureRewriter.java
@@ -8,7 +8,6 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.GenericSignatureTypeRewriter;
 import com.android.tools.r8.naming.NamingLens;
-import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.ThreadUtils;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
@@ -18,12 +17,10 @@
 
   private final AppView<?> appView;
   private final NamingLens namingLens;
-  private final InternalOptions options;
 
   public GenericSignatureRewriter(AppView<?> appView, NamingLens namingLens) {
     this.appView = appView;
     this.namingLens = namingLens;
-    this.options = appView.options();
   }
 
   public void run(Iterable<? extends DexProgramClass> classes, ExecutorService executorService)
diff --git a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
index f17d49b..c5d7038 100644
--- a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
@@ -190,14 +190,17 @@
 
   public void run() {
     for (DexProgramClass clazz : appView.appInfo().classes()) {
-      stripAttributes(clazz);
+      boolean enclosingMethodPinned = enclosingMethodPinned(appView, clazz);
+      stripAttributes(clazz, enclosingMethodPinned);
       clazz.setAnnotations(
           clazz.annotations().rewrite(annotation -> rewriteAnnotation(clazz, annotation)));
       // Kotlin properties are split over fields and methods. Check if any is pinned before pruning
       // the information.
       Set<KotlinPropertyInfo> pinnedKotlinProperties = Sets.newIdentityHashSet();
-      clazz.forEachMethod(method -> processMethod(method, clazz, pinnedKotlinProperties));
-      clazz.forEachField(field -> processField(field, clazz, pinnedKotlinProperties));
+      clazz.forEachMethod(
+          method -> processMethod(method, clazz, pinnedKotlinProperties, enclosingMethodPinned));
+      clazz.forEachField(
+          field -> processField(field, clazz, pinnedKotlinProperties, enclosingMethodPinned));
       clazz.forEachProgramMember(
           member -> {
             KotlinMemberLevelInfo kotlinInfo = member.getKotlinInfo();
@@ -212,13 +215,14 @@
   private void processMethod(
       DexEncodedMethod method,
       DexProgramClass clazz,
-      Set<KotlinPropertyInfo> pinnedKotlinProperties) {
+      Set<KotlinPropertyInfo> pinnedKotlinProperties,
+      boolean enclosingMethodPinned) {
     method.setAnnotations(
         method.annotations().rewrite(annotation -> rewriteAnnotation(method, annotation)));
     method.parameterAnnotationsList =
         method.parameterAnnotationsList.keepIf(this::filterParameterAnnotations);
     KeepMethodInfo methodInfo = appView.getKeepInfo().getMethodInfo(method, clazz);
-    if (methodInfo.isAllowSignatureAttributeRemovalAllowed(options)) {
+    if (!enclosingMethodPinned && methodInfo.isAllowSignatureAttributeRemovalAllowed(options)) {
       method.clearGenericSignature();
     }
     if (!methodInfo.isPinned() && method.getKotlinInfo().isFunction()) {
@@ -232,11 +236,12 @@
   private void processField(
       DexEncodedField field,
       DexProgramClass clazz,
-      Set<KotlinPropertyInfo> pinnedKotlinProperties) {
+      Set<KotlinPropertyInfo> pinnedKotlinProperties,
+      boolean enclosingMethodPinned) {
     field.setAnnotations(
         field.annotations().rewrite(annotation -> rewriteAnnotation(field, annotation)));
     KeepFieldInfo fieldInfo = appView.getKeepInfo().getFieldInfo(field, clazz);
-    if (fieldInfo.isAllowSignatureAttributeRemovalAllowed(options)) {
+    if (!enclosingMethodPinned && fieldInfo.isAllowSignatureAttributeRemovalAllowed(options)) {
       field.clearGenericSignature();
     }
     if (fieldInfo.isPinned() && field.getKotlinInfo().isProperty()) {
@@ -302,7 +307,7 @@
     return false;
   }
 
-  private void stripAttributes(DexProgramClass clazz) {
+  private void stripAttributes(DexProgramClass clazz, boolean enclosingMethodPinned) {
     // If [clazz] is mentioned by a keep rule, it could be used for reflection, and we therefore
     // need to keep the enclosing method and inner classes attributes, if requested. In Proguard
     // compatibility mode we keep these attributes independent of whether the given class is kept.
@@ -311,7 +316,7 @@
     // is kept.
     boolean keptAnyway =
         appView.appInfo().isPinned(clazz.type)
-            || enclosingMethodPinned(appView, clazz)
+            || enclosingMethodPinned
             || appView.options().forceProguardCompatibility;
     boolean keepForThisInnerClass = false;
     boolean keepForThisEnclosingClass = false;
@@ -356,10 +361,12 @@
       clazz.clearEnclosingMethodAttribute();
       clazz.clearInnerClasses();
     }
-    if (appView
-        .getKeepInfo()
-        .getClassInfo(clazz)
-        .isAllowSignatureAttributeRemovalAllowed(options)) {
+    if (!enclosingMethodPinned
+        && clazz.getClassSignature().isValid()
+        && appView
+            .getKeepInfo()
+            .getClassInfo(clazz)
+            .isAllowSignatureAttributeRemovalAllowed(options)) {
       clazz.clearClassSignature();
     }
   }
diff --git a/src/main/java/com/android/tools/r8/shaking/KeepInfo.java b/src/main/java/com/android/tools/r8/shaking/KeepInfo.java
index 36f5cdd..1040ae2 100644
--- a/src/main/java/com/android/tools/r8/shaking/KeepInfo.java
+++ b/src/main/java/com/android/tools/r8/shaking/KeepInfo.java
@@ -84,9 +84,10 @@
 
   public boolean isAllowSignatureAttributeRemovalAllowed(
       GlobalKeepInfoConfiguration configuration) {
-    // TODO(b/172999267): For full mode we should be able to remove for not pinned items if
-    //  java reflect will not throw up.
-    return !configuration.isKeepAttributesSignatureEnabled();
+    if (!configuration.isKeepAttributesSignatureEnabled()) {
+      return true;
+    }
+    return !(configuration.isForceProguardCompatibilityEnabled() || isPinned());
   }
 
   public abstract boolean isTop();
diff --git a/src/main/java/com/android/tools/r8/shaking/TreePruner.java b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
index 577ecc2..ef2f149 100644
--- a/src/main/java/com/android/tools/r8/shaking/TreePruner.java
+++ b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
@@ -15,7 +15,6 @@
 import com.android.tools.r8.graph.DexTypeList;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
 import com.android.tools.r8.graph.EnclosingMethodAttribute;
-import com.android.tools.r8.graph.GenericSignatureTypeVariableRemover;
 import com.android.tools.r8.graph.InnerClassAttribute;
 import com.android.tools.r8.graph.NestMemberClassAttribute;
 import com.android.tools.r8.ir.optimize.info.MutableFieldOptimizationInfo;
@@ -46,7 +45,6 @@
   private final UnusedItemsPrinter unusedItemsPrinter;
   private final Set<DexType> prunedTypes = Sets.newIdentityHashSet();
   private final Set<DexMethod> methodsToKeepForConfigurationDebugging = Sets.newIdentityHashSet();
-  private final GenericSignatureTypeVariableRemover typeVariableRemover;
 
   public TreePruner(AppView<AppInfoWithLiveness> appView) {
     this(appView, DefaultTreePrunerConfiguration.getInstance());
@@ -63,11 +61,6 @@
                     ExceptionUtils.withConsumeResourceHandler(
                         options.reporter, options.usageInformationConsumer, s))
             : UnusedItemsPrinter.DONT_PRINT;
-    this.typeVariableRemover =
-        new GenericSignatureTypeVariableRemover(
-            appView,
-            this::isAttributeReferencingMissingOrPrunedType,
-            this::isAttributeReferencingPrunedItem);
   }
 
   public DirectMappedDexApplication run(ExecutorService executorService) throws ExecutionException {
@@ -200,7 +193,6 @@
     if (reachableStaticFields != null) {
       clazz.setStaticFields(reachableStaticFields);
     }
-    typeVariableRemover.removeDeadGenericSignatureTypeVariables(clazz);
     clazz.removeInnerClasses(this::isAttributeReferencingMissingOrPrunedType);
     clazz.removeEnclosingMethodAttribute(this::isAttributeReferencingPrunedItem);
     rewriteNestAttributes(clazz);
diff --git a/src/main/java/com/android/tools/r8/tracereferences/Formatter.java b/src/main/java/com/android/tools/r8/tracereferences/Formatter.java
index fd188c0..2f19681 100644
--- a/src/main/java/com/android/tools/r8/tracereferences/Formatter.java
+++ b/src/main/java/com/android/tools/r8/tracereferences/Formatter.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.tracereferences.TraceReferencesConsumer.TracedClass;
 import com.android.tools.r8.tracereferences.TraceReferencesConsumer.TracedField;
 import com.android.tools.r8.tracereferences.TraceReferencesConsumer.TracedMethod;
+import com.android.tools.r8.tracereferences.internal.TraceReferencesResult;
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.StringUtils.BraceType;
@@ -76,7 +77,11 @@
   protected abstract void printTypeFooter();
 
   void format(TraceReferencesResult result) {
-    print(result.types, result.keepPackageNames, result.fields, result.methods);
+    print(
+        result.getTracedClasses(),
+        result.getTracedPackageNames(),
+        result.getTracedFields(),
+        result.getTracedMethods());
   }
 
   private void print(
diff --git a/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesCheckConsumer.java b/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesCheckConsumer.java
new file mode 100644
index 0000000..6912b15
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesCheckConsumer.java
@@ -0,0 +1,138 @@
+// Copyright (c) 2021, 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.tracereferences;
+
+import com.android.tools.r8.DiagnosticsHandler;
+import com.android.tools.r8.Keep;
+import com.android.tools.r8.diagnostic.DefinitionContext;
+import com.android.tools.r8.diagnostic.MissingDefinitionsDiagnostic;
+import com.android.tools.r8.diagnostic.internal.DefinitionContextUtils;
+import com.android.tools.r8.diagnostic.internal.MissingClassInfoImpl;
+import com.android.tools.r8.diagnostic.internal.MissingDefinitionsDiagnosticImpl;
+import com.android.tools.r8.diagnostic.internal.MissingFieldInfoImpl;
+import com.android.tools.r8.diagnostic.internal.MissingMethodInfoImpl;
+import com.android.tools.r8.references.ClassReference;
+import com.android.tools.r8.references.FieldReference;
+import com.android.tools.r8.references.MethodReference;
+import com.android.tools.r8.references.PackageReference;
+import java.util.Map;
+import java.util.concurrent.ConcurrentHashMap;
+
+/**
+ * A {@link TraceReferencesConsumer.ForwardingConsumer}, which forwards all callbacks to the wrapped
+ * {@link TraceReferencesConsumer}.
+ *
+ * <p>This consumer collects the set of missing definitions and reports a {@link
+ * com.android.tools.r8.diagnostic.MissingDefinitionsDiagnostic} as an error, if any missing
+ * definitions were found.
+ */
+@Keep
+public class TraceReferencesCheckConsumer extends TraceReferencesConsumer.ForwardingConsumer {
+
+  private final Map<ClassReference, Map<Object, DefinitionContext>> missingClassesContexts =
+      new ConcurrentHashMap<>();
+  private final Map<FieldReference, Map<Object, DefinitionContext>> missingFieldsContexts =
+      new ConcurrentHashMap<>();
+  private final Map<MethodReference, Map<Object, DefinitionContext>> missingMethodsContexts =
+      new ConcurrentHashMap<>();
+
+  public TraceReferencesCheckConsumer(TraceReferencesConsumer consumer) {
+    super(consumer);
+  }
+
+  @Override
+  public void acceptType(TracedClass tracedClass, DiagnosticsHandler handler) {
+    super.acceptType(tracedClass, handler);
+    if (tracedClass.isMissingDefinition()) {
+      Map<Object, DefinitionContext> missingClassContexts =
+          missingClassesContexts.computeIfAbsent(
+              tracedClass.getReference(), ignore -> new ConcurrentHashMap<>());
+      DefinitionContextUtils.accept(
+          tracedClass.getReferencedFromContext(),
+          classContext -> missingClassContexts.put(classContext.getClassReference(), classContext),
+          fieldContext -> missingClassContexts.put(fieldContext.getFieldReference(), fieldContext),
+          methodContext ->
+              missingClassContexts.put(methodContext.getMethodReference(), methodContext));
+    }
+  }
+
+  @Override
+  public void acceptField(TracedField tracedField, DiagnosticsHandler handler) {
+    super.acceptField(tracedField, handler);
+    if (tracedField.isMissingDefinition()) {
+      Map<Object, DefinitionContext> missingFieldContexts =
+          missingFieldsContexts.computeIfAbsent(
+              tracedField.getReference(), ignore -> new ConcurrentHashMap<>());
+      DefinitionContextUtils.accept(
+          tracedField.getReferencedFromContext(),
+          classContext -> missingFieldContexts.put(classContext.getClassReference(), classContext),
+          fieldContext -> missingFieldContexts.put(fieldContext.getFieldReference(), fieldContext),
+          methodContext ->
+              missingFieldContexts.put(methodContext.getMethodReference(), methodContext));
+    }
+  }
+
+  @Override
+  public void acceptMethod(TracedMethod tracedMethod, DiagnosticsHandler handler) {
+    super.acceptMethod(tracedMethod, handler);
+    if (tracedMethod.isMissingDefinition()) {
+      Map<Object, DefinitionContext> missingMethodContexts =
+          missingMethodsContexts.computeIfAbsent(
+              tracedMethod.getReference(), ignore -> new ConcurrentHashMap<>());
+      DefinitionContextUtils.accept(
+          tracedMethod.getReferencedFromContext(),
+          classContext -> missingMethodContexts.put(classContext.getClassReference(), classContext),
+          fieldContext -> missingMethodContexts.put(fieldContext.getFieldReference(), fieldContext),
+          methodContext ->
+              missingMethodContexts.put(methodContext.getMethodReference(), methodContext));
+    }
+  }
+
+  @Override
+  public void acceptPackage(PackageReference pkg, DiagnosticsHandler handler) {
+    super.acceptPackage(pkg, handler);
+  }
+
+  @Override
+  public void finished(DiagnosticsHandler handler) {
+    super.finished(handler);
+    if (!isEmpty()) {
+      handler.error(buildDiagnostic());
+    }
+  }
+
+  private boolean isEmpty() {
+    return missingClassesContexts.isEmpty()
+        && missingFieldsContexts.isEmpty()
+        && missingMethodsContexts.isEmpty();
+  }
+
+  private MissingDefinitionsDiagnostic buildDiagnostic() {
+    MissingDefinitionsDiagnosticImpl.Builder diagnosticBuilder =
+        MissingDefinitionsDiagnosticImpl.builder();
+    missingClassesContexts.forEach(
+        (reference, referencedFrom) ->
+            diagnosticBuilder.addMissingDefinitionInfo(
+                MissingClassInfoImpl.builder()
+                    .setClass(reference)
+                    .addReferencedFromContexts(referencedFrom.values())
+                    .build()));
+    missingFieldsContexts.forEach(
+        (reference, referencedFrom) ->
+            diagnosticBuilder.addMissingDefinitionInfo(
+                MissingFieldInfoImpl.builder()
+                    .setField(reference)
+                    .addReferencedFromContexts(referencedFrom.values())
+                    .build()));
+    missingMethodsContexts.forEach(
+        (reference, referencedFrom) ->
+            diagnosticBuilder.addMissingDefinitionInfo(
+                MissingMethodInfoImpl.builder()
+                    .setMethod(reference)
+                    .addReferencedFromContexts(referencedFrom.values())
+                    .build()));
+    return diagnosticBuilder.build();
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesCommandParser.java b/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesCommandParser.java
index 96956b0..c3c8e30 100644
--- a/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesCommandParser.java
+++ b/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesCommandParser.java
@@ -186,17 +186,19 @@
 
     switch (command) {
       case CHECK:
-        builder.setConsumer(TraceReferencesConsumer.emptyConsumer());
+        builder.setConsumer(
+            new TraceReferencesCheckConsumer(TraceReferencesConsumer.emptyConsumer()));
         break;
       case KEEP_RULES:
         builder.setConsumer(
-            TraceReferencesKeepRules.builder()
-                .setAllowObfuscation(allowObfuscation)
-                .setOutputConsumer(
-                    output != null
-                        ? new FileConsumer(output)
-                        : new WriterConsumer(null, new PrintWriter(System.out)))
-                .build());
+            new TraceReferencesCheckConsumer(
+                TraceReferencesKeepRules.builder()
+                    .setAllowObfuscation(allowObfuscation)
+                    .setOutputConsumer(
+                        output != null
+                            ? new FileConsumer(output)
+                            : new WriterConsumer(null, new PrintWriter(System.out)))
+                    .build()));
         break;
       default:
         throw new Unreachable();
diff --git a/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesConsumer.java b/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesConsumer.java
index f364c72..e5251f7 100644
--- a/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesConsumer.java
+++ b/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesConsumer.java
@@ -6,6 +6,7 @@
 import com.android.tools.r8.DiagnosticsHandler;
 import com.android.tools.r8.Keep;
 import com.android.tools.r8.KeepForSubclassing;
+import com.android.tools.r8.diagnostic.DefinitionContext;
 import com.android.tools.r8.references.ClassReference;
 import com.android.tools.r8.references.FieldReference;
 import com.android.tools.r8.references.MethodReference;
@@ -55,6 +56,9 @@
     /** Returns the reference traced. */
     T getReference();
 
+    /** Returns the context from which this was referenced. */
+    DefinitionContext getReferencedFromContext();
+
     /**
      * Returns the access flags for the reference traced. If the definition is not found (<code>
      * isMissingDefinition()</code> returns <code>true</code>) the access flags are not known and
diff --git a/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesKeepRules.java b/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesKeepRules.java
index d1926db..f648da4 100644
--- a/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesKeepRules.java
+++ b/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesKeepRules.java
@@ -7,6 +7,7 @@
 import com.android.tools.r8.Keep;
 import com.android.tools.r8.StringConsumer;
 import com.android.tools.r8.StringConsumer.FileConsumer;
+import com.android.tools.r8.tracereferences.internal.TraceReferencesResult;
 import java.nio.file.Path;
 
 /**
diff --git a/src/main/java/com/android/tools/r8/tracereferences/Tracer.java b/src/main/java/com/android/tools/r8/tracereferences/Tracer.java
index 3e8de35..21bb4be 100644
--- a/src/main/java/com/android/tools/r8/tracereferences/Tracer.java
+++ b/src/main/java/com/android/tools/r8/tracereferences/Tracer.java
@@ -6,10 +6,8 @@
 
 import com.android.tools.r8.DiagnosticsHandler;
 import com.android.tools.r8.dex.ApplicationReader;
-import com.android.tools.r8.diagnostic.internal.MissingClassInfoImpl;
-import com.android.tools.r8.diagnostic.internal.MissingDefinitionsDiagnosticImpl;
-import com.android.tools.r8.diagnostic.internal.MissingFieldInfoImpl;
-import com.android.tools.r8.diagnostic.internal.MissingMethodInfoImpl;
+import com.android.tools.r8.diagnostic.DefinitionContext;
+import com.android.tools.r8.diagnostic.internal.DefinitionContextUtils;
 import com.android.tools.r8.features.ClassToFeatureSplitMap;
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
@@ -17,7 +15,6 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexClassAndField;
 import com.android.tools.r8.graph.DexClassAndMethod;
-import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
@@ -30,6 +27,7 @@
 import com.android.tools.r8.graph.GraphLens.FieldLookupResult;
 import com.android.tools.r8.graph.GraphLens.MethodLookupResult;
 import com.android.tools.r8.graph.InitClassLens;
+import com.android.tools.r8.graph.ProgramField;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.graph.ResolutionResult;
 import com.android.tools.r8.graph.UseRegistry;
@@ -101,11 +99,12 @@
   public void run(TraceReferencesConsumer consumer) {
     UseCollector useCollector = new UseCollector(appInfo, consumer, diagnostics, targetPredicate);
     for (DexProgramClass clazz : appInfo.classes()) {
-      useCollector.registerSuperType(clazz, clazz.superType);
+      DefinitionContext classContext = DefinitionContextUtils.create(clazz);
+      useCollector.registerSuperType(clazz, clazz.superType, classContext);
       for (DexType implementsType : clazz.getInterfaces()) {
-        useCollector.registerSuperType(clazz, implementsType);
+        useCollector.registerSuperType(clazz, implementsType, classContext);
       }
-      clazz.forEachField(useCollector::registerField);
+      clazz.forEachProgramField(useCollector::registerField);
       clazz.forEachProgramMethod(
           method -> {
             useCollector.registerMethod(method);
@@ -113,7 +112,6 @@
           });
     }
     consumer.finished(diagnostics);
-    useCollector.reportMissingDefinitions();
   }
 
   // The graph lens is intentionally only made accessible to the MethodUseCollector, since the
@@ -146,37 +144,39 @@
       return targetPredicate.test(type);
     }
 
-    private void addType(DexType type) {
+    private void addType(DexType type, DefinitionContext referencedFrom) {
       if (type.isArrayType()) {
-        addType(type.toBaseType(factory));
+        addType(type.toBaseType(factory), referencedFrom);
         return;
       }
       if (type.isPrimitiveType() || type.isVoidType()) {
         return;
       }
       assert type.isClassType();
-      addClassType(type);
+      addClassType(type, referencedFrom);
     }
 
-    private void addTypes(DexTypeList types) {
-      types.forEach(this::addType);
+    private void addTypes(DexTypeList types, DefinitionContext referencedFrom) {
+      for (DexType type : types) {
+        addType(type, referencedFrom);
+      }
     }
 
-    private void addClassType(DexType type) {
+    private void addClassType(DexType type, DefinitionContext referencedFrom) {
       assert type.isClassType();
       DexClass clazz = appInfo.definitionFor(type);
       if (clazz != null) {
-        addClass(clazz);
+        addClass(clazz, referencedFrom);
       } else {
-        TracedClassImpl tracedClass = new TracedClassImpl(type);
+        TracedClassImpl tracedClass = new TracedClassImpl(type, referencedFrom);
         collectMissingClass(tracedClass);
         consumer.acceptType(tracedClass, diagnostics);
       }
     }
 
-    private void addClass(DexClass clazz) {
+    private void addClass(DexClass clazz, DefinitionContext referencedFrom) {
       if (isTargetType(clazz.getType())) {
-        TracedClassImpl tracedClass = new TracedClassImpl(clazz);
+        TracedClassImpl tracedClass = new TracedClassImpl(clazz, referencedFrom);
         consumer.acceptType(tracedClass, diagnostics);
         if (clazz.getAccessFlags().isVisibilityDependingOnPackage()) {
           consumer.acceptPackage(
@@ -185,7 +185,8 @@
       }
     }
 
-    private void addSuperMethodFromTarget(DexClassAndMethod method) {
+    private void addSuperMethodFromTarget(
+        DexClassAndMethod method, DefinitionContext referencedFrom) {
       assert !method.isProgramMethod();
       assert isTargetType(method.getHolderType());
 
@@ -195,7 +196,7 @@
       // - The holder type is registered from visiting the extends/implements clause of the sub
       //   class.
 
-      TracedMethodImpl tracedMethod = new TracedMethodImpl(method);
+      TracedMethodImpl tracedMethod = new TracedMethodImpl(method, referencedFrom);
       if (isTargetType(method.getHolderType())) {
         consumer.acceptMethod(tracedMethod, diagnostics);
         if (method.getAccessFlags().isVisibilityDependingOnPackage()) {
@@ -227,38 +228,20 @@
       collectMissing(tracedMethod, missingMethods);
     }
 
-    private void reportMissingDefinitions() {
-      if (missingClasses.size() > 0 || missingFields.size() > 0 || missingMethods.size() > 0) {
-        MissingDefinitionsDiagnosticImpl.Builder diagnosticBuilder =
-            MissingDefinitionsDiagnosticImpl.builder();
-        missingClasses.forEach(
-            classReference ->
-                diagnosticBuilder.addMissingDefinitionInfo(
-                    MissingClassInfoImpl.builder().setClass(classReference).build()));
-        missingFields.forEach(
-            fieldReference ->
-                diagnosticBuilder.addMissingDefinitionInfo(
-                    MissingFieldInfoImpl.builder().setField(fieldReference).build()));
-        missingMethods.forEach(
-            methodReference ->
-                diagnosticBuilder.addMissingDefinitionInfo(
-                    MissingMethodInfoImpl.builder().setMethod(methodReference).build()));
-        diagnostics.error(diagnosticBuilder.build());
-      }
-    }
-
-    private void registerField(DexEncodedField field) {
-      addType(field.getType());
+    private void registerField(ProgramField field) {
+      DefinitionContext referencedFrom = DefinitionContextUtils.create(field);
+      addType(field.getType(), referencedFrom);
     }
 
     private void registerMethod(ProgramMethod method) {
-      addTypes(method.getParameters());
-      addType(method.getReturnType());
+      DefinitionContext referencedFrom = DefinitionContextUtils.create(method);
+      addTypes(method.getParameters(), referencedFrom);
+      addType(method.getReturnType(), referencedFrom);
       for (DexAnnotation annotation : method.getDefinition().annotations().annotations) {
         if (annotation.getAnnotationType() == appInfo.dexItemFactory().annotationThrows) {
           DexValueArray dexValues = annotation.annotation.elements[0].value.asDexValueArray();
           for (DexValue dexValType : dexValues.getValues()) {
-            addType(dexValType.asDexValueType().value);
+            addType(dexValType.asDexValueType().value, referencedFrom);
           }
         }
       }
@@ -270,7 +253,7 @@
       if (superTarget != null
           && !superTarget.isProgramMethod()
           && isTargetType(superTarget.getHolderType())) {
-        addSuperMethodFromTarget(superTarget);
+        addSuperMethodFromTarget(superTarget, referencedFrom);
       }
     }
 
@@ -278,8 +261,9 @@
       method.registerCodeReferences(new MethodUseCollector(method, graphLens, initClassLens));
     }
 
-    private void registerSuperType(DexProgramClass clazz, DexType superType) {
-      addType(superType);
+    private void registerSuperType(
+        DexProgramClass clazz, DexType superType, DefinitionContext referencedFrom) {
+      addType(superType, referencedFrom);
       // If clazz overrides any methods in superType, we should keep those as well.
       clazz.forEachMethod(
           method -> {
@@ -290,7 +274,7 @@
             if (resolvedMethod != null
                 && !resolvedMethod.isProgramMethod()
                 && isTargetType(resolvedMethod.getHolderType())) {
-              addSuperMethodFromTarget(resolvedMethod);
+              addSuperMethodFromTarget(resolvedMethod, referencedFrom);
             }
           });
     }
@@ -300,6 +284,7 @@
       private final ProgramMethod context;
       private final GraphLens graphLens;
       private final InitClassLens initClassLens;
+      private final DefinitionContext referencedFrom;
 
       public MethodUseCollector(
           ProgramMethod context, GraphLens graphLens, InitClassLens initClassLens) {
@@ -307,6 +292,7 @@
         this.context = context;
         this.graphLens = graphLens;
         this.initClassLens = initClassLens;
+        this.referencedFrom = DefinitionContextUtils.create(context);
       }
 
       // Method references.
@@ -358,7 +344,7 @@
         DexMethod method = lookupResult.getReference();
         if (method.getHolderType().isArrayType()) {
           assert lookupResult.getType().isVirtual();
-          addType(method.getHolderType());
+          addType(method.getHolderType(), referencedFrom);
           return;
         }
         assert lookupResult.getType().isInterface() || lookupResult.getType().isVirtual();
@@ -374,15 +360,15 @@
       private void handleRewrittenMethodReference(
           DexMethod method, DexClassAndMethod resolvedMethod) {
         assert resolvedMethod == null || resolvedMethod.getReference().match(method);
-        addType(method.getHolderType());
-        addTypes(method.getParameters());
-        addType(method.getReturnType());
+        addType(method.getHolderType(), referencedFrom);
+        addTypes(method.getParameters(), referencedFrom);
+        addType(method.getReturnType(), referencedFrom);
         if (resolvedMethod != null) {
           if (isTargetType(resolvedMethod.getHolderType())) {
             if (resolvedMethod.getHolderType() != method.getHolderType()) {
-              addType(resolvedMethod.getHolderType());
+              addType(resolvedMethod.getHolderType(), referencedFrom);
             }
-            TracedMethodImpl tracedMethod = new TracedMethodImpl(resolvedMethod);
+            TracedMethodImpl tracedMethod = new TracedMethodImpl(resolvedMethod, referencedFrom);
             consumer.acceptMethod(tracedMethod, diagnostics);
             if (resolvedMethod.getAccessFlags().isVisibilityDependingOnPackage()) {
               consumer.acceptPackage(
@@ -391,7 +377,7 @@
             }
           }
         } else {
-          TracedMethodImpl tracedMethod = new TracedMethodImpl(method);
+          TracedMethodImpl tracedMethod = new TracedMethodImpl(method, referencedFrom);
           collectMissingMethod(tracedMethod);
           consumer.acceptMethod(tracedMethod, diagnostics);
         }
@@ -432,16 +418,16 @@
       }
 
       private void handleRewrittenFieldReference(DexField field) {
-        addType(field.getHolderType());
-        addType(field.getType());
+        addType(field.getHolderType(), referencedFrom);
+        addType(field.getType(), referencedFrom);
 
         DexClassAndField resolvedField = appInfo.resolveField(field).getResolutionPair();
         if (resolvedField != null) {
           if (isTargetType(resolvedField.getHolderType())) {
             if (resolvedField.getHolderType() != field.getHolderType()) {
-              addClass(resolvedField.getHolder());
+              addClass(resolvedField.getHolder(), referencedFrom);
             }
-            TracedFieldImpl tracedField = new TracedFieldImpl(resolvedField);
+            TracedFieldImpl tracedField = new TracedFieldImpl(resolvedField, referencedFrom);
             consumer.acceptField(tracedField, diagnostics);
             if (resolvedField.getAccessFlags().isVisibilityDependingOnPackage()) {
               consumer.acceptPackage(
@@ -450,7 +436,7 @@
             }
           }
         } else {
-          TracedFieldImpl tracedField = new TracedFieldImpl(field);
+          TracedFieldImpl tracedField = new TracedFieldImpl(field, referencedFrom);
           collectMissingField(tracedField);
           consumer.acceptField(tracedField, diagnostics);
         }
@@ -460,7 +446,7 @@
 
       @Override
       public void registerTypeReference(DexType type) {
-        addType(graphLens.lookupType(type));
+        addType(graphLens.lookupType(type), referencedFrom);
       }
     }
   }
diff --git a/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesResult.java b/src/main/java/com/android/tools/r8/tracereferences/internal/TraceReferencesResult.java
similarity index 73%
rename from src/main/java/com/android/tools/r8/tracereferences/TraceReferencesResult.java
rename to src/main/java/com/android/tools/r8/tracereferences/internal/TraceReferencesResult.java
index 1b16d54..94ffff7 100644
--- a/src/main/java/com/android/tools/r8/tracereferences/TraceReferencesResult.java
+++ b/src/main/java/com/android/tools/r8/tracereferences/internal/TraceReferencesResult.java
@@ -1,13 +1,14 @@
-// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
+// Copyright (c) 2021, 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.tracereferences;
+package com.android.tools.r8.tracereferences.internal;
 
 import com.android.tools.r8.DiagnosticsHandler;
 import com.android.tools.r8.references.ClassReference;
 import com.android.tools.r8.references.FieldReference;
 import com.android.tools.r8.references.MethodReference;
 import com.android.tools.r8.references.PackageReference;
+import com.android.tools.r8.tracereferences.TraceReferencesConsumer;
 import com.android.tools.r8.tracereferences.TraceReferencesConsumer.TracedClass;
 import com.android.tools.r8.tracereferences.TraceReferencesConsumer.TracedField;
 import com.android.tools.r8.tracereferences.TraceReferencesConsumer.TracedMethod;
@@ -18,10 +19,10 @@
 
 public class TraceReferencesResult {
 
-  final Set<TracedClass> types;
-  final Map<ClassReference, Set<TracedField>> fields;
-  final Map<ClassReference, Set<TracedMethod>> methods;
-  final Set<PackageReference> keepPackageNames;
+  private final Set<TracedClass> types;
+  private final Map<ClassReference, Set<TracedField>> fields;
+  private final Map<ClassReference, Set<TracedMethod>> methods;
+  private final Set<PackageReference> keepPackageNames;
 
   TraceReferencesResult(
       Set<TracedClass> types,
@@ -34,11 +35,27 @@
     this.keepPackageNames = keepPackageNames;
   }
 
+  public Set<TracedClass> getTracedClasses() {
+    return types;
+  }
+
+  public Map<ClassReference, Set<TracedField>> getTracedFields() {
+    return fields;
+  }
+
+  public Map<ClassReference, Set<TracedMethod>> getTracedMethods() {
+    return methods;
+  }
+
+  public Set<PackageReference> getTracedPackageNames() {
+    return keepPackageNames;
+  }
+
   public static Builder builder() {
     return new Builder();
   }
 
-  static class Builder implements TraceReferencesConsumer {
+  public static class Builder implements TraceReferencesConsumer {
     private final Set<TracedClass> types = new HashSet<>();
     private final Map<ClassReference, Set<TracedField>> fields = new HashMap<>();
     private final Map<ClassReference, Set<TracedMethod>> methods = new HashMap<>();
@@ -69,7 +86,7 @@
     @Override
     public void finished(DiagnosticsHandler handler) {}
 
-    TraceReferencesResult build() {
+    public TraceReferencesResult build() {
       return new TraceReferencesResult(types, fields, methods, keepPackageNames);
     }
   }
diff --git a/src/main/java/com/android/tools/r8/tracereferences/internal/TracedClassImpl.java b/src/main/java/com/android/tools/r8/tracereferences/internal/TracedClassImpl.java
index fd9a353..c876442 100644
--- a/src/main/java/com/android/tools/r8/tracereferences/internal/TracedClassImpl.java
+++ b/src/main/java/com/android/tools/r8/tracereferences/internal/TracedClassImpl.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.tracereferences.internal;
 
+import com.android.tools.r8.diagnostic.DefinitionContext;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.references.ClassReference;
@@ -12,16 +13,22 @@
 
 public class TracedClassImpl extends TracedReferenceBase<ClassReference, ClassAccessFlags>
     implements TracedClass {
-  public TracedClassImpl(DexType type) {
-    this(type.asClassReference(), null);
+  public TracedClassImpl(DexType type, DefinitionContext referencedFrom) {
+    this(type.asClassReference(), referencedFrom, null);
   }
 
-  public TracedClassImpl(DexClass clazz) {
-    this(clazz.getClassReference(), new ClassAccessFlagsImpl(clazz.getAccessFlags()));
+  public TracedClassImpl(DexClass clazz, DefinitionContext referencedFrom) {
+    this(
+        clazz.getClassReference(),
+        referencedFrom,
+        new ClassAccessFlagsImpl(clazz.getAccessFlags()));
   }
 
-  public TracedClassImpl(ClassReference classReference, ClassAccessFlags accessFlags) {
-    super(classReference, accessFlags, accessFlags == null);
+  public TracedClassImpl(
+      ClassReference classReference,
+      DefinitionContext referencedFrom,
+      ClassAccessFlags accessFlags) {
+    super(classReference, referencedFrom, accessFlags, accessFlags == null);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/tracereferences/internal/TracedFieldImpl.java b/src/main/java/com/android/tools/r8/tracereferences/internal/TracedFieldImpl.java
index 9c6ac2d..59e58db 100644
--- a/src/main/java/com/android/tools/r8/tracereferences/internal/TracedFieldImpl.java
+++ b/src/main/java/com/android/tools/r8/tracereferences/internal/TracedFieldImpl.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.tracereferences.internal;
 
+import com.android.tools.r8.diagnostic.DefinitionContext;
 import com.android.tools.r8.graph.DexClassAndField;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.references.FieldReference;
@@ -12,16 +13,22 @@
 
 public class TracedFieldImpl extends TracedReferenceBase<FieldReference, FieldAccessFlags>
     implements TracedField {
-  public TracedFieldImpl(DexField field) {
-    this(field.asFieldReference(), null);
+  public TracedFieldImpl(DexField field, DefinitionContext referencedFrom) {
+    this(field.asFieldReference(), referencedFrom, null);
   }
 
-  public TracedFieldImpl(DexClassAndField field) {
-    this(field.getFieldReference(), new FieldAccessFlagsImpl(field.getAccessFlags()));
+  public TracedFieldImpl(DexClassAndField field, DefinitionContext referencedFrom) {
+    this(
+        field.getFieldReference(),
+        referencedFrom,
+        new FieldAccessFlagsImpl(field.getAccessFlags()));
   }
 
-  public TracedFieldImpl(FieldReference fieldReference, FieldAccessFlags accessFlags) {
-    super(fieldReference, accessFlags, accessFlags == null);
+  public TracedFieldImpl(
+      FieldReference fieldReference,
+      DefinitionContext referencedFrom,
+      FieldAccessFlags accessFlags) {
+    super(fieldReference, referencedFrom, accessFlags, accessFlags == null);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/tracereferences/internal/TracedMethodImpl.java b/src/main/java/com/android/tools/r8/tracereferences/internal/TracedMethodImpl.java
index c12cbd4..1ea760a 100644
--- a/src/main/java/com/android/tools/r8/tracereferences/internal/TracedMethodImpl.java
+++ b/src/main/java/com/android/tools/r8/tracereferences/internal/TracedMethodImpl.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.tracereferences.internal;
 
+import com.android.tools.r8.diagnostic.DefinitionContext;
 import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.references.MethodReference;
@@ -12,16 +13,22 @@
 
 public class TracedMethodImpl extends TracedReferenceBase<MethodReference, MethodAccessFlags>
     implements TracedMethod {
-  public TracedMethodImpl(DexMethod method) {
-    this(method.asMethodReference(), null);
+  public TracedMethodImpl(DexMethod method, DefinitionContext referencedFrom) {
+    this(method.asMethodReference(), referencedFrom, null);
   }
 
-  public TracedMethodImpl(DexClassAndMethod method) {
-    this(method.getMethodReference(), new MethodAccessFlagsImpl(method.getAccessFlags()));
+  public TracedMethodImpl(DexClassAndMethod method, DefinitionContext referencedFrom) {
+    this(
+        method.getMethodReference(),
+        referencedFrom,
+        new MethodAccessFlagsImpl(method.getAccessFlags()));
   }
 
-  public TracedMethodImpl(MethodReference methodReference, MethodAccessFlags accessFlags) {
-    super(methodReference, accessFlags, accessFlags == null);
+  public TracedMethodImpl(
+      MethodReference methodReference,
+      DefinitionContext referencedFrom,
+      MethodAccessFlags accessFlags) {
+    super(methodReference, referencedFrom, accessFlags, accessFlags == null);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/tracereferences/internal/TracedReferenceBase.java b/src/main/java/com/android/tools/r8/tracereferences/internal/TracedReferenceBase.java
index 254048b..d426b96 100644
--- a/src/main/java/com/android/tools/r8/tracereferences/internal/TracedReferenceBase.java
+++ b/src/main/java/com/android/tools/r8/tracereferences/internal/TracedReferenceBase.java
@@ -4,16 +4,21 @@
 
 package com.android.tools.r8.tracereferences.internal;
 
+import com.android.tools.r8.diagnostic.DefinitionContext;
 import com.android.tools.r8.tracereferences.TraceReferencesConsumer.TracedReference;
 
 abstract class TracedReferenceBase<T, F> implements TracedReference<T, F> {
+
   private final T reference;
+  private final DefinitionContext referencedFrom;
   private final F accessFlags;
   private final boolean missingDefinition;
 
-  TracedReferenceBase(T reference, F accessFlags, boolean missingDefinition) {
+  TracedReferenceBase(
+      T reference, DefinitionContext referencedFrom, F accessFlags, boolean missingDefinition) {
     assert accessFlags != null || missingDefinition;
     this.reference = reference;
+    this.referencedFrom = referencedFrom;
     this.accessFlags = accessFlags;
     this.missingDefinition = missingDefinition;
   }
@@ -24,6 +29,11 @@
   }
 
   @Override
+  public DefinitionContext getReferencedFromContext() {
+    return referencedFrom;
+  }
+
+  @Override
   public boolean isMissingDefinition() {
     return missingDefinition;
   }
diff --git a/src/main/java/com/android/tools/r8/utils/TypeReferenceUtils.java b/src/main/java/com/android/tools/r8/utils/TypeReferenceUtils.java
index 20f1e99..9d322e6 100644
--- a/src/main/java/com/android/tools/r8/utils/TypeReferenceUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/TypeReferenceUtils.java
@@ -66,7 +66,7 @@
       DexItemFactory dexItemFactory,
       Function<ClassReference, DexType> classReferenceConverter) {
     if (typeReference == null) {
-      return null;
+      return dexItemFactory.voidType;
     }
     if (typeReference.isPrimitive()) {
       PrimitiveReference primitiveReference = typeReference.asPrimitive();
diff --git a/src/test/java/com/android/tools/r8/D8TestBuilder.java b/src/test/java/com/android/tools/r8/D8TestBuilder.java
index 822a5bd..1cae06b 100644
--- a/src/test/java/com/android/tools/r8/D8TestBuilder.java
+++ b/src/test/java/com/android/tools/r8/D8TestBuilder.java
@@ -5,7 +5,6 @@
 
 import com.android.tools.r8.D8Command.Builder;
 import com.android.tools.r8.TestBase.Backend;
-import com.android.tools.r8.desugar.desugaredlibrary.DesugaredLibraryTestBase.KeepRuleConsumer;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.AndroidApp;
@@ -83,7 +82,7 @@
   @Override
   public D8TestBuilder enableCoreLibraryDesugaring(
       AndroidApiLevel minApiLevel,
-      KeepRuleConsumer keepRuleConsumer,
+      StringConsumer keepRuleConsumer,
       StringResource desugaredLibraryConfiguration) {
     if (minApiLevel.getLevel() < AndroidApiLevel.O.getLevel()) {
       super.enableCoreLibraryDesugaring(
diff --git a/src/test/java/com/android/tools/r8/ExternalR8TestCompileResult.java b/src/test/java/com/android/tools/r8/ExternalR8TestCompileResult.java
index cef49f7..8c2623a 100644
--- a/src/test/java/com/android/tools/r8/ExternalR8TestCompileResult.java
+++ b/src/test/java/com/android/tools/r8/ExternalR8TestCompileResult.java
@@ -11,7 +11,6 @@
 import java.io.IOException;
 import java.nio.file.Path;
 import java.util.Set;
-import java.util.concurrent.ExecutionException;
 
 public class ExternalR8TestCompileResult
     extends TestCompileResult<ExternalR8TestCompileResult, ExternalR8TestRunResult> {
@@ -68,7 +67,7 @@
   }
 
   @Override
-  public CodeInspector inspector() throws IOException, ExecutionException {
+  public CodeInspector inspector() throws IOException {
     return new CodeInspector(app, proguardMap);
   }
 
diff --git a/src/test/java/com/android/tools/r8/L8TestCompileResult.java b/src/test/java/com/android/tools/r8/L8TestCompileResult.java
new file mode 100644
index 0000000..aefa32a
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/L8TestCompileResult.java
@@ -0,0 +1,84 @@
+// Copyright (c) 2021, 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;
+
+import static org.junit.Assert.assertNotNull;
+
+import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.errors.Unimplemented;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.FileUtils;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.util.Set;
+
+public class L8TestCompileResult extends TestCompileResult<L8TestCompileResult, L8TestRunResult> {
+
+  private final String generatedKeepRules;
+  private final Path mapping;
+
+  public L8TestCompileResult(
+      AndroidApp app,
+      AndroidApiLevel apiLevel,
+      String generatedKeepRules,
+      Path mapping,
+      TestState state) {
+    super(state, app, apiLevel.getLevel(), OutputMode.DexIndexed);
+    this.generatedKeepRules = generatedKeepRules;
+    this.mapping = mapping;
+  }
+
+  @Override
+  public TestDiagnosticMessages getDiagnosticMessages() {
+    return state.getDiagnosticsMessages();
+  }
+
+  @Override
+  public Set<String> getMainDexClasses() {
+    throw new Unimplemented();
+  }
+
+  @Override
+  public String getStdout() {
+    throw new Unimplemented();
+  }
+
+  @Override
+  public String getStderr() {
+    throw new Unimplemented();
+  }
+
+  @Override
+  protected L8TestRunResult createRunResult(TestRuntime runtime, ProcessResult result) {
+    throw new Unimplemented();
+  }
+
+  @Override
+  public CodeInspector inspector() throws IOException {
+    return mapping != null && mapping.toFile().exists()
+        ? new CodeInspector(app, mapping)
+        : super.inspector();
+  }
+
+  @Override
+  public L8TestCompileResult self() {
+    return this;
+  }
+
+  public L8TestCompileResult writeGeneratedKeepRules(Path path) throws IOException {
+    assertNotNull(generatedKeepRules);
+    FileUtils.writeTextFile(path, generatedKeepRules);
+    return self();
+  }
+
+  public L8TestCompileResult writeProguardMap(Path path) throws IOException {
+    assertNotNull(mapping);
+    Files.copy(mapping, path);
+    return self();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/L8TestRunResult.java b/src/test/java/com/android/tools/r8/L8TestRunResult.java
new file mode 100644
index 0000000..a9a9a78
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/L8TestRunResult.java
@@ -0,0 +1,55 @@
+// Copyright (c) 2021, 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;
+
+import com.android.tools.r8.errors.Unimplemented;
+import com.android.tools.r8.utils.ThrowingConsumer;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import java.io.IOException;
+import java.util.concurrent.ExecutionException;
+import org.hamcrest.Matcher;
+
+public class L8TestRunResult extends TestRunResult<L8TestRunResult> {
+
+  public L8TestRunResult() {
+    throw new Unimplemented();
+  }
+
+  @Override
+  L8TestRunResult self() {
+    throw new Unimplemented();
+  }
+
+  @Override
+  public L8TestRunResult assertSuccess() {
+    throw new Unimplemented();
+  }
+
+  @Override
+  public L8TestRunResult assertStdoutMatches(Matcher<String> matcher) {
+    throw new Unimplemented();
+  }
+
+  @Override
+  public L8TestRunResult assertFailure() {
+    throw new Unimplemented();
+  }
+
+  @Override
+  public L8TestRunResult assertStderrMatches(Matcher<String> matcher) {
+    throw new Unimplemented();
+  }
+
+  @Override
+  public <E extends Throwable> L8TestRunResult inspect(ThrowingConsumer<CodeInspector, E> consumer)
+      throws IOException, ExecutionException, E {
+    throw new Unimplemented();
+  }
+
+  @Override
+  public L8TestRunResult disassemble() throws IOException, ExecutionException {
+    throw new Unimplemented();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ProguardTestCompileResult.java b/src/test/java/com/android/tools/r8/ProguardTestCompileResult.java
index ca1a0a7..faf07a6 100644
--- a/src/test/java/com/android/tools/r8/ProguardTestCompileResult.java
+++ b/src/test/java/com/android/tools/r8/ProguardTestCompileResult.java
@@ -10,7 +10,6 @@
 import java.io.IOException;
 import java.nio.file.Path;
 import java.util.Set;
-import java.util.concurrent.ExecutionException;
 
 public class ProguardTestCompileResult
     extends TestCompileResult<ProguardTestCompileResult, ProguardTestRunResult> {
@@ -58,7 +57,7 @@
   }
 
   @Override
-  public CodeInspector inspector() throws IOException, ExecutionException {
+  public CodeInspector inspector() throws IOException {
     return new CodeInspector(app, proguardMap);
   }
 
diff --git a/src/test/java/com/android/tools/r8/R8TestBuilder.java b/src/test/java/com/android/tools/r8/R8TestBuilder.java
index d85d8d9..637a88b 100644
--- a/src/test/java/com/android/tools/r8/R8TestBuilder.java
+++ b/src/test/java/com/android/tools/r8/R8TestBuilder.java
@@ -9,7 +9,6 @@
 
 import com.android.tools.r8.R8Command.Builder;
 import com.android.tools.r8.TestBase.Backend;
-import com.android.tools.r8.desugar.desugaredlibrary.DesugaredLibraryTestBase.KeepRuleConsumer;
 import com.android.tools.r8.dexsplitter.SplitterTestBase.RunInterface;
 import com.android.tools.r8.dexsplitter.SplitterTestBase.SplitRunner;
 import com.android.tools.r8.errors.Unreachable;
@@ -624,7 +623,7 @@
   @Override
   public T enableCoreLibraryDesugaring(
       AndroidApiLevel minApiLevel,
-      KeepRuleConsumer keepRuleConsumer,
+      StringConsumer keepRuleConsumer,
       StringResource desugaredLibraryConfiguration) {
     if (minApiLevel.getLevel() < AndroidApiLevel.O.getLevel()) {
       super.enableCoreLibraryDesugaring(
diff --git a/src/test/java/com/android/tools/r8/TestBase.java b/src/test/java/com/android/tools/r8/TestBase.java
index 79bfbde..a6895ce 100644
--- a/src/test/java/com/android/tools/r8/TestBase.java
+++ b/src/test/java/com/android/tools/r8/TestBase.java
@@ -4,11 +4,9 @@
 
 package com.android.tools.r8;
 
-import static com.android.tools.r8.DiagnosticsMatcher.diagnosticMessage;
 import static com.android.tools.r8.TestBuilder.getTestingAnnotations;
 import static com.android.tools.r8.utils.InternalOptions.ASM_VERSION;
 import static com.google.common.collect.Lists.cartesianProduct;
-import static org.hamcrest.CoreMatchers.containsString;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertTrue;
 
@@ -121,7 +119,6 @@
 import java.util.stream.Stream;
 import java.util.zip.ZipEntry;
 import java.util.zip.ZipOutputStream;
-import org.hamcrest.Matcher;
 import org.junit.AfterClass;
 import org.junit.BeforeClass;
 import org.junit.Rule;
@@ -1818,9 +1815,4 @@
         extractor, ClassReader.SKIP_CODE | ClassReader.SKIP_DEBUG | ClassReader.SKIP_FRAMES);
     return extractor.getClassFileVersion();
   }
-
-  // Default messages
-  protected final Matcher<Diagnostic> cfD8NotSupportedDiagnostic =
-      diagnosticMessage(
-          containsString("Compiling to Java class files with D8 is not officially supported"));
 }
diff --git a/src/test/java/com/android/tools/r8/TestBaseResult.java b/src/test/java/com/android/tools/r8/TestBaseResult.java
index 392b4b0..b643e54 100644
--- a/src/test/java/com/android/tools/r8/TestBaseResult.java
+++ b/src/test/java/com/android/tools/r8/TestBaseResult.java
@@ -4,7 +4,8 @@
 
 package com.android.tools.r8;
 
-public abstract class TestBaseResult<CR extends TestBaseResult<CR, RR>, RR extends TestRunResult> {
+public abstract class TestBaseResult<
+    CR extends TestBaseResult<CR, RR>, RR extends TestRunResult<RR>> {
 
   final TestState state;
 
diff --git a/src/test/java/com/android/tools/r8/TestCompileResult.java b/src/test/java/com/android/tools/r8/TestCompileResult.java
index f7395d1..5788681 100644
--- a/src/test/java/com/android/tools/r8/TestCompileResult.java
+++ b/src/test/java/com/android/tools/r8/TestCompileResult.java
@@ -25,6 +25,7 @@
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.DescriptorUtils;
+import com.android.tools.r8.utils.FileUtils;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.ThrowingConsumer;
 import com.android.tools.r8.utils.TriFunction;
@@ -278,6 +279,18 @@
     return self();
   }
 
+  public CR writeSingleDexOutputToFile(Path file) throws IOException {
+    assertTrue(getApp().getClassProgramResourcesForTesting().isEmpty());
+    try {
+      List<ProgramResource> dexProgramSources = getApp().getDexProgramResourcesForTesting();
+      assertEquals(1, dexProgramSources.size());
+      FileUtils.writeToFile(file, null, dexProgramSources.get(0).getBytes());
+      return self();
+    } catch (ResourceException e) {
+      throw new IOException(e);
+    }
+  }
+
   public Path writeToZip() throws IOException {
     Path file = state.getNewTempFolder().resolve("out.zip");
     writeToZip(file);
@@ -305,17 +318,17 @@
     return self();
   }
 
-  public CodeInspector inspector() throws IOException, ExecutionException {
+  public CodeInspector inspector() throws IOException {
     return new CodeInspector(app);
   }
 
   public CodeInspector inspector(Consumer<InternalOptions> debugOptionsConsumer)
-      throws IOException, ExecutionException {
+      throws IOException {
     return new CodeInspector(app, debugOptionsConsumer);
   }
 
   public <E extends Throwable> CR inspect(ThrowingConsumer<CodeInspector, E> consumer)
-      throws IOException, ExecutionException, E {
+      throws IOException, E {
     consumer.accept(inspector());
     return self();
   }
diff --git a/src/test/java/com/android/tools/r8/TestCompilerBuilder.java b/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
index cd584e0..97a95be8 100644
--- a/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
+++ b/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
@@ -440,7 +440,7 @@
 
   public T enableCoreLibraryDesugaring(
       AndroidApiLevel minApiLevel,
-      KeepRuleConsumer keepRuleConsumer,
+      StringConsumer keepRuleConsumer,
       StringResource desugaredLibraryConfiguration) {
     assert minApiLevel.getLevel() < AndroidApiLevel.O.getLevel();
     builder.addDesugaredLibraryConfiguration(desugaredLibraryConfiguration);
diff --git a/src/test/java/com/android/tools/r8/TestState.java b/src/test/java/com/android/tools/r8/TestState.java
index a30033b..601208f 100644
--- a/src/test/java/com/android/tools/r8/TestState.java
+++ b/src/test/java/com/android/tools/r8/TestState.java
@@ -35,7 +35,7 @@
     return getNewTempFolder().resolve(name);
   }
 
-  DiagnosticsHandler getDiagnosticsHandler() {
+  public DiagnosticsHandler getDiagnosticsHandler() {
     return messages;
   }
 
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/NonFinalOverrideOfFinalMethodNonTrivialMergeTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/NonFinalOverrideOfFinalMethodNonTrivialMergeTest.java
new file mode 100644
index 0000000..5e95a1e
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/NonFinalOverrideOfFinalMethodNonTrivialMergeTest.java
@@ -0,0 +1,103 @@
+// Copyright (c) 2020, 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.classmerging.horizontal;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertFalse;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoVerticalClassMerging;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import org.junit.Test;
+import org.junit.runners.Parameterized;
+
+public class NonFinalOverrideOfFinalMethodNonTrivialMergeTest
+    extends HorizontalClassMergingTestBase {
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public NonFinalOverrideOfFinalMethodNonTrivialMergeTest(TestParameters parameters) {
+    super(parameters);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .enableNoVerticalClassMergingAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .addHorizontallyMergedClassesInspector(
+            inspector -> inspector.assertIsCompleteMergeGroup(A.class, B.class, C.class))
+        .compile()
+        .inspect(
+            inspector -> {
+              ClassSubject classSubject = inspector.clazz(A.class);
+              assertThat(classSubject, isPresent());
+
+              MethodSubject methodSubject = classSubject.uniqueMethodWithName("foo$bridge");
+              assertThat(methodSubject, isPresent());
+              assertFalse(methodSubject.isFinal());
+            })
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("A", "B", "C", "CSub");
+  }
+
+  public static class Main {
+    public static void main(String[] args) {
+      new A().foo();
+      new B().foo();
+      new C().bar();
+      new CSub().foo();
+    }
+  }
+
+  @NeverClassInline
+  public static class A {
+
+    @NeverInline
+    public final void foo() {
+      System.out.println("A");
+    }
+  }
+
+  @NeverClassInline
+  public static class B {
+
+    @NeverInline
+    public final void foo() {
+      System.out.println("B");
+    }
+  }
+
+  @NeverClassInline
+  @NoVerticalClassMerging
+  public static class C {
+
+    @NeverInline
+    public void bar() {
+      System.out.println("C");
+    }
+  }
+
+  @NeverClassInline
+  public static class CSub extends C {
+
+    @NeverInline
+    public void foo() {
+      System.out.println("CSub");
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/NonFinalOverrideOfFinalMethodTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/NonFinalOverrideOfFinalMethodTest.java
index 110f7f6..6287174 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/NonFinalOverrideOfFinalMethodTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/NonFinalOverrideOfFinalMethodTest.java
@@ -43,12 +43,12 @@
         .compile()
         .inspect(
             inspector -> {
-              ClassSubject aClassSubject = inspector.clazz(A.class);
-              assertThat(aClassSubject, isPresent());
+              ClassSubject classSubject = inspector.clazz(A.class);
+              assertThat(classSubject, isPresent());
 
-              MethodSubject synchronizedMethodSubject = aClassSubject.uniqueMethodWithName("foo");
-              assertThat(synchronizedMethodSubject, isPresent());
-              assertFalse(synchronizedMethodSubject.isFinal());
+              MethodSubject methodSubject = classSubject.uniqueMethodWithName("foo");
+              assertThat(methodSubject, isPresent());
+              assertFalse(methodSubject.isFinal());
             })
         .run(parameters.getRuntime(), Main.class)
         .assertSuccessWithOutputLines("A", "B", "BSub");
diff --git a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLibraryTestBase.java b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLibraryTestBase.java
index 3b9a63d..fdb7faa 100644
--- a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLibraryTestBase.java
+++ b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLibraryTestBase.java
@@ -5,20 +5,23 @@
 package com.android.tools.r8.desugar.desugaredlibrary;
 
 import static com.android.tools.r8.utils.InternalOptions.ASM_VERSION;
+import static junit.framework.Assert.assertNull;
 import static junit.framework.TestCase.assertEquals;
 import static junit.framework.TestCase.assertTrue;
 
 import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.CompilationMode;
+import com.android.tools.r8.DexIndexedConsumer;
 import com.android.tools.r8.DiagnosticsHandler;
 import com.android.tools.r8.L8Command;
+import com.android.tools.r8.L8TestCompileResult;
 import com.android.tools.r8.OutputMode;
 import com.android.tools.r8.StringConsumer;
 import com.android.tools.r8.StringResource;
 import com.android.tools.r8.TestBase;
-import com.android.tools.r8.TestDiagnosticMessagesImpl;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.TestState;
 import com.android.tools.r8.ThrowableConsumer;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.ToolHelper.DexVm.Version;
@@ -28,10 +31,10 @@
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.tracereferences.TraceReferences;
 import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.AndroidAppConsumers;
 import com.android.tools.r8.utils.ConsumerUtils;
 import com.android.tools.r8.utils.FileUtils;
 import com.android.tools.r8.utils.InternalOptions;
-import com.android.tools.r8.utils.codeinspector.CodeInspector;
 import com.google.common.base.Charsets;
 import com.google.common.collect.ImmutableList;
 import java.io.IOException;
@@ -41,9 +44,11 @@
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.concurrent.ExecutionException;
 import java.util.function.Consumer;
 import org.junit.BeforeClass;
 import org.junit.rules.TemporaryFolder;
@@ -102,9 +107,10 @@
   public static class L8TestBuilder {
 
     private final AndroidApiLevel apiLevel;
-    private final TemporaryFolder temp;
+    private final TestState state;
 
     private CompilationMode mode = CompilationMode.RELEASE;
+    private String generatedKeepRules = null;
     private List<String> keepRules = new ArrayList<>();
     private List<Path> additionalProgramFiles = new ArrayList<>();
     private Consumer<InternalOptions> optionsModifier = ConsumerUtils.emptyConsumer();
@@ -112,6 +118,7 @@
     private Path desugarJDKLibsConfiguration = ToolHelper.DESUGAR_LIB_CONVERSIONS;
     private StringResource desugaredLibraryConfiguration =
         StringResource.fromFile(ToolHelper.getDesugarLibJsonForTesting());
+    private List<Path> libraryFiles = new ArrayList<>();
 
     public static L8TestBuilder builder(AndroidApiLevel apiLevel, TemporaryFolder temp) {
       return new L8TestBuilder(apiLevel, temp);
@@ -119,7 +126,7 @@
 
     private L8TestBuilder(AndroidApiLevel apiLevel, TemporaryFolder temp) {
       this.apiLevel = apiLevel;
-      this.temp = temp;
+      this.state = new TestState(temp);
     }
 
     public L8TestBuilder addProgramFiles(Collection<Path> programFiles) {
@@ -127,16 +134,25 @@
       return this;
     }
 
-    public L8TestBuilder addKeepRules(String keepRules) {
-      if (!keepRules.trim().isEmpty()) {
-        this.keepRules.add(keepRules);
-      }
+    public L8TestBuilder addLibraryFiles(Path... libraryFiles) {
+      Collections.addAll(this.libraryFiles, libraryFiles);
+      return this;
+    }
+
+    public L8TestBuilder addGeneratedKeepRules(String generatedKeepRules) {
+      assertNull(this.generatedKeepRules);
+      this.generatedKeepRules = generatedKeepRules;
+      return this;
+    }
+
+    public L8TestBuilder addKeepRuleFile(Path keepRuleFile) throws IOException {
+      this.keepRules.add(FileUtils.readTextFile(keepRuleFile, StandardCharsets.UTF_8));
       return this;
     }
 
     public L8TestBuilder addKeepRuleFiles(Collection<Path> keepRuleFiles) throws IOException {
       for (Path keepRuleFile : keepRuleFiles) {
-        addKeepRules(FileUtils.readTextFile(keepRuleFile, StandardCharsets.UTF_8));
+        addKeepRuleFile(keepRuleFile);
       }
       return this;
     }
@@ -182,60 +198,44 @@
       return this;
     }
 
-    public Path compile() {
+    private L8TestBuilder setDisableL8AnnotationRemoval(boolean disableL8AnnotationRemoval) {
+      return addOptionsModifier(
+          options -> options.testing.disableL8AnnotationRemoval = disableL8AnnotationRemoval);
+    }
+
+    public L8TestCompileResult compile()
+        throws IOException, CompilationFailedException, ExecutionException {
       // We wrap exceptions in a RuntimeException to call this from a lambda.
-      try {
-        // If we compile extended library here, it means we use TestNG.
-        // TestNG requires annotations, hence we disable AnnotationRemoval.
-        // This implies that extra warning are generated if this is set.
-        TestDiagnosticMessagesImpl diagnosticsHandler = new TestDiagnosticMessagesImpl();
-        Path desugaredLib = temp.newFolder().toPath().resolve("desugar_jdk_libs_dex.zip");
-        L8Command.Builder l8Builder =
-            L8Command.builder(diagnosticsHandler)
-                .addProgramFiles(getProgramFiles())
-                .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.P))
-                .setMode(mode)
-                .addDesugaredLibraryConfiguration(desugaredLibraryConfiguration)
-                .setMinApiLevel(apiLevel.getLevel())
-                .setOutput(desugaredLib, OutputMode.DexIndexed);
-        Path mapping = null;
-        if (!keepRules.isEmpty()) {
-          mapping = temp.newFolder().toPath().resolve("mapping.txt");
-          l8Builder.addProguardConfiguration(
-              ImmutableList.<String>builder()
-                  .addAll(keepRules)
-                  .add("-printmapping " + mapping)
-                  .build(),
-              Origin.unknown());
+      AndroidAppConsumers sink = new AndroidAppConsumers();
+      L8Command.Builder l8Builder =
+          L8Command.builder(state.getDiagnosticsHandler())
+              .addProgramFiles(getProgramFiles())
+              .addLibraryFiles(getLibraryFiles())
+              .setMode(mode)
+              .addDesugaredLibraryConfiguration(desugaredLibraryConfiguration)
+              .setMinApiLevel(apiLevel.getLevel())
+              .setProgramConsumer(sink.wrapProgramConsumer(DexIndexedConsumer.emptyConsumer()));
+      Path mapping = null;
+      if (!keepRules.isEmpty() || generatedKeepRules != null) {
+        mapping = state.getNewTempFile("mapping.txt");
+        l8Builder
+            .addProguardConfiguration(
+                ImmutableList.<String>builder()
+                    .addAll(keepRules)
+                    .addAll(
+                        generatedKeepRules != null
+                            ? ImmutableList.of(generatedKeepRules)
+                            : Collections.emptyList())
+                    .build(),
+                Origin.unknown())
+            .setProguardMapOutputPath(mapping);
         }
-        ToolHelper.runL8(
-            l8Builder.build(),
-            options -> {
-              if (!additionalProgramFiles.isEmpty()) {
-                options.testing.disableL8AnnotationRemoval = true;
-              }
-              optionsModifier.accept(options);
-            });
-        if (additionalProgramFiles.isEmpty()) {
-          assertTrue(
-              diagnosticsHandler.getInfos().stream()
-                  .noneMatch(
-                      string ->
-                          string
-                              .getDiagnosticMessage()
-                              .startsWith(
-                                  "Invalid parameter counts in MethodParameter attributes.")));
-        }
-        new CodeInspector(desugaredLib, mapping)
-            .forAllClasses(clazz -> assertTrue(clazz.getFinalName().startsWith("j$.")));
-        return desugaredLib;
-      } catch (Exception e) {
-        // Don't wrap assumption violation so junit can catch it.
-        if (e instanceof RuntimeException) {
-          throw ((RuntimeException) e);
-        }
-        throw new RuntimeException(e);
-      }
+      ToolHelper.runL8(l8Builder.build(), optionsModifier);
+      return new L8TestCompileResult(sink.build(), apiLevel, generatedKeepRules, mapping, state)
+          .inspect(
+              inspector ->
+                  inspector.forAllClasses(
+                      clazz -> assertTrue(clazz.getFinalName().startsWith("j$."))));
     }
 
     private Collection<Path> getProgramFiles() {
@@ -245,6 +245,10 @@
           .addAll(additionalProgramFiles)
           .build();
     }
+
+    private Collection<Path> getLibraryFiles() {
+      return libraryFiles;
+    }
   }
 
   protected L8TestBuilder testForL8(AndroidApiLevel apiLevel) {
@@ -252,12 +256,12 @@
   }
 
   protected Path buildDesugaredLibrary(AndroidApiLevel apiLevel) {
-    return buildDesugaredLibrary(apiLevel, "", false);
+    return buildDesugaredLibrary(apiLevel, null, false);
   }
 
   protected Path buildDesugaredLibrary(
       AndroidApiLevel apiLevel, Consumer<InternalOptions> optionsModifier) {
-    return buildDesugaredLibrary(apiLevel, "", false, ImmutableList.of(), optionsModifier);
+    return buildDesugaredLibrary(apiLevel, null, false, ImmutableList.of(), optionsModifier);
   }
 
   protected Path buildDesugaredLibrary(AndroidApiLevel apiLevel, String keepRules) {
@@ -279,15 +283,46 @@
 
   protected Path buildDesugaredLibrary(
       AndroidApiLevel apiLevel,
-      String keepRules,
-      boolean shrink,
+      String generatedKeepRules,
+      boolean release,
       List<Path> additionalProgramFiles,
       Consumer<InternalOptions> optionsModifier) {
-    return testForL8(apiLevel)
-        .addProgramFiles(additionalProgramFiles)
-        .applyIf(shrink, builder -> builder.addKeepRules(keepRules), L8TestBuilder::setDebug)
-        .addOptionsModifier(optionsModifier)
-        .compile();
+    try {
+      return testForL8(apiLevel)
+          .addProgramFiles(additionalProgramFiles)
+          .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.P))
+          .applyIf(
+              release,
+              builder -> {
+                if (generatedKeepRules != null && !generatedKeepRules.trim().isEmpty()) {
+                  builder.addGeneratedKeepRules(generatedKeepRules);
+                }
+              },
+              L8TestBuilder::setDebug)
+          .addOptionsModifier(optionsModifier)
+          // If we compile extended library here, it means we use TestNG. TestNG requires
+          // annotations, hence we disable annotation removal. This implies that extra warnings are
+          // generated.
+          .setDisableL8AnnotationRemoval(!additionalProgramFiles.isEmpty())
+          .compile()
+          .applyIf(
+              additionalProgramFiles.isEmpty(),
+              builder ->
+                  builder.inspectDiagnosticMessages(
+                      diagnostics ->
+                          assertTrue(
+                              diagnostics.getInfos().stream()
+                                  .noneMatch(
+                                      string ->
+                                          string
+                                              .getDiagnosticMessage()
+                                              .startsWith(
+                                                  "Invalid parameter counts in MethodParameter"
+                                                      + " attributes.")))))
+          .writeToZip();
+    } catch (CompilationFailedException | ExecutionException | IOException e) {
+      throw new RuntimeException(e);
+    }
   }
 
   protected void assertLines2By2Correct(String stdOut) {
diff --git a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLocalDateReflectionTest.java b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLocalDateReflectionTest.java
index 980c9ff..f5205f1 100644
--- a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLocalDateReflectionTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLocalDateReflectionTest.java
@@ -25,7 +25,7 @@
   private final boolean shrinkDesugaredLibrary;
   private static final String EXPECTED = StringUtils.lines("1992");
 
-  @Parameters(name = "{1}, shrinkDesugaredLibrary: {0}")
+  @Parameters(name = "{0}, shrinkDesugaredLibrary: {1}")
   public static List<Object[]> data() {
     return buildParameters(
         getTestParameters().withDexRuntimes().withAllApiLevels().build(), BooleanUtils.values());
diff --git a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/gson/gson.cfg b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/gson/gson.cfg
index e7560e1f..2b36e8a 100644
--- a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/gson/gson.cfg
+++ b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/gson/gson.cfg
@@ -30,6 +30,7 @@
 
 # Prevent R8 from removing the generic signature of TypeToken
 -keep,allowobfuscation class * extends com.google.gson.reflect.TypeToken
+-keep,allowobfuscation class com.google.gson.reflect.TypeToken
 
 # Prevent R8 from leaving Data object members always null
 -keepclassmembers,allowobfuscation class * {
diff --git a/src/test/java/com/android/tools/r8/desugar/records/GenerateRecordMethods.java b/src/test/java/com/android/tools/r8/desugar/records/GenerateRecordMethods.java
index 53d6201..e3078a2 100644
--- a/src/test/java/com/android/tools/r8/desugar/records/GenerateRecordMethods.java
+++ b/src/test/java/com/android/tools/r8/desugar/records/GenerateRecordMethods.java
@@ -8,22 +8,30 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.TestRuntime.CfVm;
+import com.android.tools.r8.cf.code.CfFrame;
+import com.android.tools.r8.cf.code.CfFrame.FrameType;
 import com.android.tools.r8.cf.code.CfInstruction;
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.cf.code.CfTypeInstruction;
 import com.android.tools.r8.cfmethodgeneration.MethodGenerationBase;
+import com.android.tools.r8.desugar.records.RecordMethods.RecordStub;
 import com.android.tools.r8.graph.CfCode;
-import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.desugar.RecordRewriter;
+import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.FileUtils;
 import com.google.common.collect.ImmutableList;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
 import java.nio.charset.StandardCharsets;
+import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Comparator;
+import java.util.Deque;
 import java.util.List;
+import java.util.SortedMap;
 import java.util.stream.Collectors;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -34,6 +42,8 @@
 public class GenerateRecordMethods extends MethodGenerationBase {
   private final DexType GENERATED_TYPE =
       factory.createType("Lcom/android/tools/r8/ir/desugar/RecordCfMethods;");
+  private final DexType RECORD_STUB_TYPE =
+      factory.createType(DescriptorUtils.javaTypeToDescriptor(RecordStub.class.getTypeName()));
   private final List<Class<?>> METHOD_TEMPLATE_CLASSES = ImmutableList.of(RecordMethods.class);
 
   protected final TestParameters parameters;
@@ -64,32 +74,30 @@
 
   @Override
   protected CfCode getCode(String holderName, String methodName, CfCode code) {
-    DexType recordStubType =
-        factory.createType("Lcom/android/tools/r8/desugar/records/RecordMethods$RecordStub;");
     code.setInstructions(
         code.getInstructions().stream()
-            .map(instruction -> rewriteRecordStub(factory, instruction, recordStubType))
+            .map(instruction -> rewriteRecordStub(instruction))
             .collect(Collectors.toList()));
     return code;
   }
 
-  private CfInstruction rewriteRecordStub(
-      DexItemFactory factory, CfInstruction instruction, DexType recordStubType) {
+  private CfInstruction rewriteRecordStub(CfInstruction instruction) {
     if (instruction.isTypeInstruction()) {
       CfTypeInstruction typeInstruction = instruction.asTypeInstruction();
-      return typeInstruction.withType(
-          rewriteType(factory, recordStubType, typeInstruction.getType()));
+      return typeInstruction.withType(rewriteType(typeInstruction.getType()));
     }
     if (instruction.isInvoke()) {
       CfInvoke cfInvoke = instruction.asInvoke();
       DexMethod method = cfInvoke.getMethod();
       DexMethod newMethod =
-          factory.createMethod(
-              rewriteType(factory, recordStubType, method.holder),
-              method.proto,
-              rewriteName(method.name));
+          factory.createMethod(rewriteType(method.holder), method.proto, rewriteName(method.name));
       return new CfInvoke(cfInvoke.getOpcode(), newMethod, cfInvoke.isInterface());
     }
+    if (instruction.isFrame()) {
+      CfFrame cfFrame = instruction.asFrame();
+      return new CfFrame(
+          rewriteLocals(cfFrame.getLocalsAsSortedMap()), rewriteStack(cfFrame.getStack()));
+    }
     return instruction;
   }
 
@@ -99,8 +107,40 @@
         : name.toString();
   }
 
-  private DexType rewriteType(DexItemFactory factory, DexType recordStubType, DexType type) {
-    return type == recordStubType ? factory.recordType : type;
+  private DexType rewriteType(DexType type) {
+    DexType baseType = type.isArrayType() ? type.toBaseType(factory) : type;
+    if (baseType != RECORD_STUB_TYPE) {
+      return type;
+    }
+    return type.isArrayType()
+        ? type.replaceBaseType(factory.recordType, factory)
+        : factory.recordType;
+  }
+
+  private FrameType rewriteFrameType(FrameType frameType) {
+    if (frameType.isInitialized() && frameType.getInitializedType().isReferenceType()) {
+      DexType newType = rewriteType(frameType.getInitializedType());
+      if (newType == frameType.getInitializedType()) {
+        return frameType;
+      }
+      return FrameType.initialized(newType);
+    } else {
+      assert !frameType.isUninitializedNew();
+      assert !frameType.isUninitializedThis();
+      return frameType;
+    }
+  }
+
+  private SortedMap<Integer, FrameType> rewriteLocals(SortedMap<Integer, FrameType> locals) {
+    Int2ReferenceSortedMap<FrameType> newLocals = new Int2ReferenceAVLTreeMap<>();
+    locals.forEach((index, local) -> newLocals.put((int) index, rewriteFrameType(local)));
+    return newLocals;
+  }
+
+  private Deque<FrameType> rewriteStack(Deque<FrameType> stack) {
+    ArrayDeque<FrameType> newStack = new ArrayDeque<>();
+    stack.forEach(frameType -> newStack.add(rewriteFrameType(frameType)));
+    return newStack;
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureKeepAttributesTest.java b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureKeepAttributesTest.java
new file mode 100644
index 0000000..21cc62c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureKeepAttributesTest.java
@@ -0,0 +1,151 @@
+// Copyright (c) 2021, 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.genericsignature;
+
+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.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.graph.genericsignature.GenericSignatureKeepAttributesTest.Outer.Middle;
+import com.android.tools.r8.graph.genericsignature.GenericSignatureKeepAttributesTest.Outer.Middle.Inner;
+import com.android.tools.r8.utils.BooleanUtils;
+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 java.util.List;
+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 GenericSignatureKeepAttributesTest extends TestBase {
+
+  private final TestParameters parameters;
+  private final boolean isCompat;
+
+  private final String[] EXPECTED_JVM =
+      new String[] {
+        "Outer.Middle.Inner::test",
+        "public class com.android.tools.r8.graph.genericsignature"
+            + ".GenericSignatureKeepAttributesTest$Outer$Middle$Inner<I>"
+      };
+
+  private final String[] EXPECTED_DEX =
+      new String[] {
+        "Outer.Middle.Inner::test",
+        "class com.android.tools.r8.graph.genericsignature"
+            + ".GenericSignatureKeepAttributesTest$Outer$Middle$Inner"
+      };
+
+  @Parameters(name = "{0}, isCompat: {1}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        getTestParameters().withAllRuntimesAndApiLevels().build(), BooleanUtils.values());
+  }
+
+  public GenericSignatureKeepAttributesTest(TestParameters parameters, boolean isCompat) {
+    this.parameters = parameters;
+    this.isCompat = isCompat;
+  }
+
+  @Test
+  public void testRuntime() throws Exception {
+    testForRuntime(parameters)
+        .addProgramClasses(Supplier.class, Predicate.class, Outer.class, Middle.class, Main.class)
+        .addProgramClassFileData(getClassFileData())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(parameters.isCfRuntime() ? EXPECTED_JVM : EXPECTED_DEX);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    (isCompat ? testForR8Compat(parameters.getBackend()) : testForR8(parameters.getBackend()))
+        .addProgramClasses(Supplier.class, Predicate.class, Outer.class, Middle.class, Main.class)
+        .addProgramClassFileData(getClassFileData())
+        .setMinApi(parameters.getApiLevel())
+        .addKeepAttributeSignature()
+        .addKeepAttributeInnerClassesAndEnclosingMethod()
+        .addKeepMainRule(Main.class)
+        .addKeepClassAndMembersRules(Outer.Middle.Inner.class, Supplier.class, Predicate.class)
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(parameters.isCfRuntime() ? EXPECTED_JVM : EXPECTED_DEX)
+        .inspect(this::inspectSignatures);
+  }
+
+  private byte[] getClassFileData() throws Exception {
+    return transformer(Inner.class)
+        .transformMethodInsnInMethod(
+            "test",
+            ((opcode, owner, name, descriptor, isInterface, continuation) -> {
+              if (parameters.isCfRuntime() && name.equals("toString")) {
+                name = "toGenericString";
+              }
+              continuation.visitMethodInsn(opcode, owner, name, descriptor, isInterface);
+            }))
+        .transform();
+  }
+
+  private void inspectSignatures(CodeInspector inspector) {
+    ClassSubject outerClass = inspector.clazz(Outer.class);
+    assertThat(outerClass, isPresent());
+    assertEquals(
+        isCompat ? "<O::L" + binaryName(Supplier.class) + "<*>;>Ljava/lang/Object;" : null,
+        outerClass.getFinalSignatureAttribute());
+
+    ClassSubject middleClass = inspector.clazz(Middle.class);
+    assertThat(middleClass, isPresent());
+    assertEquals(
+        isCompat ? "<M::L" + binaryName(Predicate.class) + "<TO;>;>Ljava/lang/Object;" : null,
+        middleClass.getFinalSignatureAttribute());
+
+    ClassSubject innerClass = inspector.clazz(Inner.class);
+    assertThat(innerClass, isPresent());
+    MethodSubject testMethod = innerClass.uniqueMethodWithName("test");
+    assertThat(testMethod, isPresent());
+    // TODO(b/184927364): TO; should be replaced with Supplier
+    assertEquals("(TO;TM;)TI;", testMethod.getFinalSignatureAttribute());
+  }
+
+  public interface Supplier<T> {}
+
+  public interface Predicate<T> {}
+
+  public static class Outer<O extends Supplier<?>> {
+
+    public class Middle<M extends Predicate<O>> {
+
+      public class Inner<I> {
+
+        public I test(O o, M m) {
+          System.out.println("Outer.Middle.Inner::test");
+          System.out.println(this.getClass().toString()); // .toGenericString() for JVMs
+          return null;
+        }
+      }
+
+      private Outer<O>.Middle<M>.Inner<Object> createInner() {
+        return new Inner<>();
+      }
+    }
+
+    private Outer<O>.Middle<?> createMiddle() {
+      return new Outer<O>.Middle<>();
+    }
+
+    public static Outer<?>.Middle<?>.Inner<Object> create() {
+      return new Outer<>().createMiddle().createInner();
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      Outer.create().test(null, null);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureKeepReferencesPruneTest.java b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureKeepReferencesPruneTest.java
index 1c3ddbb..177ea63 100644
--- a/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureKeepReferencesPruneTest.java
+++ b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureKeepReferencesPruneTest.java
@@ -43,6 +43,14 @@
         "Hello world"
       };
 
+  private final String[] EXPECTED_FULL_MODE =
+      new String[] {
+        "class " + Foo.class.getTypeName(),
+        "interface " + I.class.getTypeName(),
+        "interface " + I.class.getTypeName(),
+        "Hello world"
+      };
+
   private final TestParameters parameters;
   private final boolean isCompat;
 
@@ -79,34 +87,37 @@
         .enableInliningAnnotations()
         .enableNeverClassInliningAnnotations()
         .noMinification()
+        .compile()
+        .inspect(this::inspectSignatures)
         .run(parameters.getRuntime(), Main.class)
-        // TODO(b/184927364): Should have different output due to pruning the inner class.
-        .assertSuccessWithOutputLines(EXPECTED)
-        .inspect(this::inspectSignatures);
+        .assertSuccessWithOutputLines(isCompat ? EXPECTED : EXPECTED_FULL_MODE);
   }
 
   private void inspectSignatures(CodeInspector inspector) {
     ClassSubject fooClass = inspector.clazz(Foo.class);
     assertThat(fooClass, isPresent());
-    // TODO(b/184927364): Fullmode should not keep the interface bound.
     assertEquals(
-        "<T::Ljava/lang/Comparable<TT;>;>Ljava/lang/Object;",
+        isCompat ? "<T::Ljava/lang/Comparable<TT;>;>Ljava/lang/Object;" : null,
         fooClass.getFinalSignatureAttribute());
     ClassSubject iClass = inspector.clazz(I.class);
     assertThat(iClass, isPresent());
-    // TODO(b/184927364): Fullmode should not keep the interface and class bound.
     assertEquals(
-        "<T::Ljava/lang/Comparable<TT;>;R:L" + binaryName(Foo.class) + "<TT;>;>Ljava/lang/Object;",
+        isCompat
+            ? "<T::Ljava/lang/Comparable<TT;>;R:L"
+                + binaryName(Foo.class)
+                + "<TT;>;>Ljava/lang/Object;"
+            : null,
         iClass.getFinalSignatureAttribute());
     ClassSubject fooInnerClass = inspector.clazz(Main.class.getTypeName() + "$1");
     assertThat(fooInnerClass, isPresent());
-    // TODO(b/184927364): Fullmode should completely remove this signature
     assertEquals(
-        "Ljava/lang/Object;L"
-            + binaryName(I.class)
-            + "<Ljava/lang/String;L"
-            + binaryName(Foo.class)
-            + "<Ljava/lang/String;>;>;",
+        isCompat
+            ? "Ljava/lang/Object;L"
+                + binaryName(I.class)
+                + "<Ljava/lang/String;L"
+                + binaryName(Foo.class)
+                + "<Ljava/lang/String;>;>;"
+            : null,
         fooInnerClass.getFinalSignatureAttribute());
   }
 }
diff --git a/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignaturePartialTypeArgumentApplierTest.java b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignaturePartialTypeArgumentApplierTest.java
index f3cee7b..c1d8c5f 100644
--- a/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignaturePartialTypeArgumentApplierTest.java
+++ b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignaturePartialTypeArgumentApplierTest.java
@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.graph.genericsignature;
 
+import static com.google.common.base.Predicates.alwaysFalse;
+import static com.google.common.base.Predicates.alwaysTrue;
 import static org.junit.Assert.assertEquals;
 
 import com.android.tools.r8.TestBase;
@@ -14,12 +16,16 @@
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.GenericSignature;
-import com.android.tools.r8.graph.GenericSignature.ClassSignature;
 import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
 import com.android.tools.r8.graph.GenericSignaturePartialTypeArgumentApplier;
 import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.utils.BiPredicateUtils;
 import com.google.common.collect.ImmutableMap;
+import java.util.Collections;
 import java.util.Map;
+import java.util.Set;
+import java.util.function.BiPredicate;
+import java.util.function.Predicate;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -45,6 +51,9 @@
   public void testVariablesInOuterPosition() {
     runTest(
             ImmutableMap.of("T", objectType, "R", objectType),
+            Collections.emptySet(),
+            BiPredicateUtils.alwaysFalse(),
+            alwaysTrue(),
             "(TT;)TR;",
             "(Ljava/lang/Object;)Ljava/lang/Object;")
         .assertNoMessages();
@@ -54,18 +63,50 @@
   public void testVariablesInInnerPosition() {
     runTest(
             ImmutableMap.of("T", objectType, "R", objectType),
+            Collections.emptySet(),
+            BiPredicateUtils.alwaysFalse(),
+            alwaysTrue(),
             "(LList<TT;>;)LList<TR;>;",
             "(LList<*>;)LList<*>;")
         .assertNoMessages();
   }
 
+  @Test
+  public void testRemovingPrunedLink() {
+    runTest(
+            Collections.emptyMap(),
+            Collections.emptySet(),
+            BiPredicateUtils.alwaysTrue(),
+            alwaysTrue(),
+            "(LFoo<Ljava/lang/String;>.Bar<Ljava/lang/Integer;>;)"
+                + "LFoo<Ljava/lang/String;>.Bar<Ljava/lang/Integer;>;",
+            "(LFoo$Bar<Ljava/lang/Integer;>;)LFoo$Bar<Ljava/lang/Integer;>;")
+        .assertNoMessages();
+  }
+
+  @Test
+  public void testRemovedGenericArguments() {
+    runTest(
+            Collections.emptyMap(),
+            Collections.emptySet(),
+            BiPredicateUtils.alwaysTrue(),
+            alwaysFalse(),
+            "(LFoo<Ljava/lang/String;>;)LFoo<Ljava/lang/String;>.Bar<Ljava/lang/Integer;>;",
+            "(LFoo;)LFoo$Bar;")
+        .assertNoMessages();
+  }
+
   private TestDiagnosticMessages runTest(
       Map<String, DexType> substitutions,
+      Set<String> liveVariables,
+      BiPredicate<DexType, DexType> removedLink,
+      Predicate<DexType> hasFormalTypeParameters,
       String initialSignature,
       String expectedRewrittenSignature) {
     GenericSignaturePartialTypeArgumentApplier argumentApplier =
         GenericSignaturePartialTypeArgumentApplier.build(
-            objectType, ClassSignature.noSignature(), substitutions);
+                objectType, removedLink, hasFormalTypeParameters)
+            .addSubstitutionsAndVariables(substitutions, liveVariables);
     TestDiagnosticMessagesImpl diagnosticsHandler = new TestDiagnosticMessagesImpl();
     MethodTypeSignature methodTypeSignature =
         argumentApplier.visitMethodSignature(
diff --git a/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureReflectiveInnerTest.java b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureReflectiveInnerTest.java
new file mode 100644
index 0000000..e34a36c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureReflectiveInnerTest.java
@@ -0,0 +1,86 @@
+// Copyright (c) 2021, 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.genericsignature;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import java.lang.reflect.TypeVariable;
+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 GenericSignatureReflectiveInnerTest extends TestBase {
+
+  private final String EXPECTED = "S";
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public GenericSignatureReflectiveInnerTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testRuntime() throws Exception {
+    testForRuntime(parameters)
+        .addInnerClasses(getClass())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(EXPECTED);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .addKeepAttributeInnerClassesAndEnclosingMethod()
+        .addKeepAttributeSignature()
+        .addKeepClassRules(Foo.Bar.class)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(EXPECTED)
+        .inspect(
+            inspector -> {
+              assertThat(inspector.clazz(Foo.class), isPresent());
+              assertThat(inspector.clazz(Foo.Bar.class), isPresent());
+            });
+  }
+
+  public static class Foo<T> {
+
+    public class Bar<S> {
+
+      public void test() {
+        Class<? extends Bar> aClass = (Class<? extends Bar>) this.getClass();
+        for (TypeVariable<? extends Class<? extends Bar>> typeParameter :
+            aClass.getTypeParameters()) {
+          System.out.println(typeParameter);
+        }
+      }
+    }
+
+    public Bar<String> foo() {
+      return new Bar<>();
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      Foo<Integer>.Bar<String> foo = new Foo<Integer>().foo();
+      foo.test();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/internal/YouTubeCompilationTestBase.java b/src/test/java/com/android/tools/r8/internal/YouTubeCompilationTestBase.java
index b3853ef..aea7348 100644
--- a/src/test/java/com/android/tools/r8/internal/YouTubeCompilationTestBase.java
+++ b/src/test/java/com/android/tools/r8/internal/YouTubeCompilationTestBase.java
@@ -5,10 +5,13 @@
 
 import static org.junit.Assert.assertTrue;
 
-import com.android.tools.r8.CompilationMode;
-import com.android.tools.r8.R8RunArtTestsTest.CompilerUnderTest;
+import com.android.tools.r8.R8TestCompileResult;
 import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.FileUtils;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.analysis.ProtoApplicationStats;
 import com.google.common.collect.ImmutableList;
 import java.io.IOException;
 import java.nio.file.Path;
@@ -25,14 +28,20 @@
   static final String PG_MISSING_CLASSES_CONF = "YouTubeRelease_proguard_missing_classes.config";
 
   final String base;
+  final AndroidApiLevel apiLevel;
 
-  public YouTubeCompilationTestBase(int majorVersion, int minorVersion) {
+  public YouTubeCompilationTestBase(int majorVersion, int minorVersion, AndroidApiLevel apiLevel) {
     this.base =
         "third_party/youtube/youtube.android_"
             + majorVersion
             + "."
             + String.format("%02d", minorVersion)
             + "/";
+    this.apiLevel = apiLevel;
+  }
+
+  protected AndroidApiLevel getApiLevel() {
+    return apiLevel;
   }
 
   protected Path getDesugaredLibraryConfiguration() {
@@ -118,4 +127,18 @@
   Path getReleaseProguardMap() {
     return Paths.get(base).resolve(PG_MAP);
   }
+
+  void printProtoStats(R8TestCompileResult compileResult) throws Exception {
+    if (ToolHelper.isLocalDevelopment()) {
+      DexItemFactory dexItemFactory = new DexItemFactory();
+      ProtoApplicationStats original =
+          new ProtoApplicationStats(dexItemFactory, new CodeInspector(getProgramFiles()));
+      ProtoApplicationStats actual =
+          new ProtoApplicationStats(dexItemFactory, compileResult.inspector(), original);
+      ProtoApplicationStats baseline =
+          new ProtoApplicationStats(
+              dexItemFactory, new CodeInspector(getReleaseApk(), getReleaseProguardMap()));
+      System.out.println(actual.getStats(baseline));
+    }
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/internal/YouTubeV1533TreeShakeJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/YouTubeV1533TreeShakeJarVerificationTest.java
index 1fe6af5..24ae3c1 100644
--- a/src/test/java/com/android/tools/r8/internal/YouTubeV1533TreeShakeJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/YouTubeV1533TreeShakeJarVerificationTest.java
@@ -3,16 +3,15 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.internal;
 
+import static com.android.tools.r8.ToolHelper.isLocalDevelopment;
+import static com.android.tools.r8.ToolHelper.shouldRunSlowTests;
 import static org.junit.Assert.assertTrue;
+import static org.junit.Assume.assumeTrue;
 
 import com.android.tools.r8.R8TestCompileResult;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
-import com.android.tools.r8.ToolHelper;
-import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.utils.AndroidApiLevel;
-import com.android.tools.r8.utils.codeinspector.CodeInspector;
-import com.android.tools.r8.utils.codeinspector.analysis.ProtoApplicationStats;
 import java.nio.file.Paths;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -31,15 +30,15 @@
   }
 
   public YouTubeV1533TreeShakeJarVerificationTest(TestParameters parameters) {
-    super(15, 33);
+    super(15, 33, AndroidApiLevel.H_MR2);
     parameters.assertNoneRuntime();
   }
 
   @Test
   public void testR8() throws Exception {
     // TODO(b/141603168): Enable this on the bots.
-    // assumeTrue(isLocalDevelopment());
-    // assumeTrue(shouldRunSlowTests());
+    assumeTrue(isLocalDevelopment());
+    assumeTrue(shouldRunSlowTests());
 
     LibrarySanitizer librarySanitizer =
         new LibrarySanitizer(temp)
@@ -58,25 +57,16 @@
             .allowDiagnosticMessages()
             .allowUnusedDontWarnPatterns()
             .allowUnusedProguardConfigurationRules()
-            .setMinApi(AndroidApiLevel.H_MR2)
-            .compile();
+            .setMinApi(getApiLevel())
+            .compile()
+            .apply(this::printProtoStats);
 
-    if (ToolHelper.isLocalDevelopment()) {
+    if (isLocalDevelopment()) {
       if (DUMP) {
         long time = System.currentTimeMillis();
         compileResult.writeToZip(Paths.get("YouTubeV1533-" + time + ".zip"));
         compileResult.writeProguardMap(Paths.get("YouTubeV1533-" + time + ".map"));
       }
-
-      DexItemFactory dexItemFactory = new DexItemFactory();
-      ProtoApplicationStats original =
-          new ProtoApplicationStats(dexItemFactory, new CodeInspector(getProgramFiles()));
-      ProtoApplicationStats actual =
-          new ProtoApplicationStats(dexItemFactory, compileResult.inspector(), original);
-      ProtoApplicationStats baseline =
-          new ProtoApplicationStats(
-              dexItemFactory, new CodeInspector(getReleaseApk(), getReleaseProguardMap()));
-      System.out.println(actual.getStats(baseline));
     }
 
     int applicationSize = compileResult.app.applicationSize();
diff --git a/src/test/java/com/android/tools/r8/internal/YouTubeV1612Test.java b/src/test/java/com/android/tools/r8/internal/YouTubeV1612Test.java
new file mode 100644
index 0000000..611cc70
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/internal/YouTubeV1612Test.java
@@ -0,0 +1,191 @@
+// Copyright (c) 2021, 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.internal;
+
+import static com.android.tools.r8.ToolHelper.isLocalDevelopment;
+import static com.android.tools.r8.ToolHelper.shouldRunSlowTests;
+import static com.android.tools.r8.internal.proto.ProtoShrinkingTestBase.assertRewrittenProtoSchemasMatch;
+import static com.android.tools.r8.internal.proto.ProtoShrinkingTestBase.keepAllProtosRule;
+import static com.android.tools.r8.internal.proto.ProtoShrinkingTestBase.keepDynamicMethodSignatureRule;
+import static com.android.tools.r8.internal.proto.ProtoShrinkingTestBase.keepNewMessageInfoSignatureRule;
+import static org.hamcrest.CoreMatchers.anyOf;
+import static org.hamcrest.CoreMatchers.containsString;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assume.assumeTrue;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.L8TestCompileResult;
+import com.android.tools.r8.R8FullTestBuilder;
+import com.android.tools.r8.R8TestCompileResult;
+import com.android.tools.r8.ResourceException;
+import com.android.tools.r8.StringConsumer;
+import com.android.tools.r8.StringResource;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.ThrowableConsumer;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.DexVm.Version;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.Reporter;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import java.util.concurrent.ExecutionException;
+import org.junit.After;
+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 YouTubeV1612Test extends YouTubeCompilationTestBase {
+
+  private static final int MAX_APPLICATION_SIZE = 29000000;
+  private static final int MAX_DESUGARED_LIBRARY_SIZE = 375000;
+
+  private final TestParameters parameters;
+
+  private final Path dumpDirectory = Paths.get("YouTubeV1612-" + System.currentTimeMillis());
+  private final Reporter reporter = new Reporter();
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters()
+        .withDexRuntime(Version.V9_0_0)
+        .withApiLevel(AndroidApiLevel.L)
+        .build();
+  }
+
+  public YouTubeV1612Test(TestParameters parameters) {
+    super(16, 12, parameters.getApiLevel());
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    assumeTrue(isLocalDevelopment());
+    assumeTrue(shouldRunSlowTests());
+
+    KeepRuleConsumer keepRuleConsumer = new PresentKeepRuleConsumer();
+    R8TestCompileResult r8CompileResult = compileApplicationWithR8(keepRuleConsumer);
+    L8TestCompileResult l8CompileResult = compileDesugaredLibraryWithL8(keepRuleConsumer);
+
+    inspect(r8CompileResult, l8CompileResult);
+
+    if (isLocalDevelopment()) {
+      dump(r8CompileResult, l8CompileResult);
+    }
+  }
+
+  @Test
+  public void testProtoRewriting() throws Exception {
+    assumeTrue(shouldRunSlowTests());
+
+    StringConsumer keepRuleConsumer = StringConsumer.emptyConsumer();
+    R8TestCompileResult r8CompileResult =
+        compileApplicationWithR8(
+            keepRuleConsumer,
+            builder ->
+                builder
+                    .addKeepRules(
+                        keepAllProtosRule(),
+                        keepDynamicMethodSignatureRule(),
+                        keepNewMessageInfoSignatureRule())
+                    .allowCheckDiscardedErrors(true));
+    assertRewrittenProtoSchemasMatch(
+        new CodeInspector(getProgramFiles()), r8CompileResult.inspector());
+  }
+
+  @After
+  public void teardown() {
+    reporter.failIfPendingErrors();
+  }
+
+  private R8TestCompileResult compileApplicationWithR8(StringConsumer keepRuleConsumer)
+      throws IOException, CompilationFailedException {
+    return compileApplicationWithR8(keepRuleConsumer, ThrowableConsumer.empty());
+  }
+
+  private R8TestCompileResult compileApplicationWithR8(
+      StringConsumer keepRuleConsumer, ThrowableConsumer<R8FullTestBuilder> configuration)
+      throws IOException, CompilationFailedException {
+    return testForR8(parameters.getBackend())
+        .addProgramFiles(getProgramFiles())
+        .addLibraryFiles(getLibraryFiles())
+        .addKeepRuleFiles(getKeepRuleFiles())
+        .addDontWarn("android.app.Activity$TranslucentConversionListener")
+        .allowDiagnosticMessages()
+        .allowUnusedDontWarnPatterns()
+        .allowUnusedProguardConfigurationRules()
+        .apply(configuration)
+        .setMinApi(getApiLevel())
+        .enableCoreLibraryDesugaring(
+            getApiLevel(),
+            keepRuleConsumer,
+            StringResource.fromFile(getDesugaredLibraryConfiguration()))
+        .compile()
+        .assertAllInfoMessagesMatch(
+            anyOf(
+                containsString("Ignoring option: -optimizations"),
+                containsString("Proguard configuration rule does not match anything")))
+        .apply(this::printProtoStats);
+  }
+
+  private L8TestCompileResult compileDesugaredLibraryWithL8(KeepRuleConsumer keepRuleConsumer)
+      throws CompilationFailedException, IOException, ExecutionException {
+    return testForL8(getApiLevel())
+        .setDesugaredLibraryConfiguration(getDesugaredLibraryConfiguration())
+        .setDesugarJDKLibs(getDesugaredLibraryJDKLibs())
+        .setDesugarJDKLibsConfiguration(getDesugaredLibraryJDKLibsConfiguration())
+        .addGeneratedKeepRules(keepRuleConsumer.get())
+        .addKeepRuleFiles(getDesugaredLibraryKeepRuleFiles())
+        .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.P))
+        .compile();
+  }
+
+  private void inspect(R8TestCompileResult r8CompileResult, L8TestCompileResult l8CompileResult)
+      throws IOException, ResourceException {
+    r8CompileResult.runDex2Oat(parameters.getRuntime()).assertNoVerificationErrors();
+    l8CompileResult.runDex2Oat(parameters.getRuntime()).assertNoVerificationErrors();
+
+    int applicationSize = r8CompileResult.getApp().applicationSize();
+    if (applicationSize > MAX_APPLICATION_SIZE) {
+      reporter.error(
+          "Expected application size to be <="
+              + MAX_APPLICATION_SIZE
+              + ", but was "
+              + applicationSize);
+    }
+
+    int desugaredLibrarySize = l8CompileResult.getApp().applicationSize();
+    if (desugaredLibrarySize > MAX_DESUGARED_LIBRARY_SIZE) {
+      reporter.error(
+          "Expected desugared library size to be <="
+              + MAX_DESUGARED_LIBRARY_SIZE
+              + ", but was "
+              + desugaredLibrarySize);
+    }
+
+    if (isLocalDevelopment()) {
+      System.out.println("Dex size (application, excluding desugared library): " + applicationSize);
+      System.out.println("Dex size (desugared library): " + desugaredLibrarySize);
+      System.out.println("Dex size (total): " + (applicationSize + desugaredLibrarySize));
+    }
+  }
+
+  private void dump(R8TestCompileResult r8CompileResult, L8TestCompileResult l8CompileResult)
+      throws IOException {
+    assertTrue(isLocalDevelopment());
+    Files.createDirectories(dumpDirectory);
+    r8CompileResult
+        .writeToDirectory(dumpDirectory)
+        .writeProguardMap(dumpDirectory.resolve("mapping.txt"));
+    l8CompileResult
+        .writeSingleDexOutputToFile(dumpDirectory.resolve("classes5.dex"))
+        .writeGeneratedKeepRules(dumpDirectory.resolve("l8-keep.txt"))
+        .writeProguardMap(dumpDirectory.resolve("l8-mapping.txt"));
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/internal/YouTubeV1612TreeShakeJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/YouTubeV1612TreeShakeJarVerificationTest.java
deleted file mode 100644
index 0f07300..0000000
--- a/src/test/java/com/android/tools/r8/internal/YouTubeV1612TreeShakeJarVerificationTest.java
+++ /dev/null
@@ -1,113 +0,0 @@
-// Copyright (c) 2021, 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.internal;
-
-import static com.android.tools.r8.ToolHelper.isLocalDevelopment;
-import static org.junit.Assert.assertTrue;
-import static org.junit.Assume.assumeTrue;
-
-import com.android.tools.r8.R8TestCompileResult;
-import com.android.tools.r8.StringResource;
-import com.android.tools.r8.TestParameters;
-import com.android.tools.r8.TestParametersCollection;
-import com.android.tools.r8.ToolHelper;
-import com.android.tools.r8.graph.DexItemFactory;
-import com.android.tools.r8.utils.AndroidApiLevel;
-import com.android.tools.r8.utils.ZipUtils;
-import com.android.tools.r8.utils.codeinspector.CodeInspector;
-import com.android.tools.r8.utils.codeinspector.analysis.ProtoApplicationStats;
-import java.nio.file.Files;
-import java.nio.file.Path;
-import java.nio.file.Paths;
-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 YouTubeV1612TreeShakeJarVerificationTest extends YouTubeCompilationTestBase {
-
-  private static final boolean DUMP = false;
-  private static final int MAX_SIZE = 30000000;
-
-  private final Path dumpDirectory = Paths.get("YouTubeV1612-" + System.currentTimeMillis());
-
-  @Parameters(name = "{0}")
-  public static TestParametersCollection data() {
-    return getTestParameters().withNoneRuntime().build();
-  }
-
-  public YouTubeV1612TreeShakeJarVerificationTest(TestParameters parameters) {
-    super(16, 12);
-    parameters.assertNoneRuntime();
-  }
-
-  @Test
-  public void testR8() throws Exception {
-    assumeTrue(isLocalDevelopment());
-
-    KeepRuleConsumer keepRuleConsumer = new PresentKeepRuleConsumer();
-    R8TestCompileResult compileResult =
-        testForR8(Backend.DEX)
-            .addProgramFiles(getProgramFiles())
-            .addLibraryFiles(getLibraryFiles())
-            .addKeepRuleFiles(getKeepRuleFiles())
-            .addIgnoreWarnings()
-            .allowDiagnosticMessages()
-            .allowUnusedDontWarnPatterns()
-            .allowUnusedProguardConfigurationRules()
-            .setMinApi(AndroidApiLevel.L)
-            .enableCoreLibraryDesugaring(
-                AndroidApiLevel.L,
-                keepRuleConsumer,
-                StringResource.fromFile(getDesugaredLibraryConfiguration()))
-            .compile();
-
-    if (ToolHelper.isLocalDevelopment()) {
-      if (DUMP) {
-        dumpDirectory.toFile().mkdirs();
-        compileResult.writeToZip(dumpDirectory.resolve("app.zip"));
-        compileResult.writeProguardMap(dumpDirectory.resolve("mapping.txt"));
-      }
-
-      DexItemFactory dexItemFactory = new DexItemFactory();
-      ProtoApplicationStats original =
-          new ProtoApplicationStats(dexItemFactory, new CodeInspector(getProgramFiles()));
-      ProtoApplicationStats actual =
-          new ProtoApplicationStats(dexItemFactory, compileResult.inspector(), original);
-      ProtoApplicationStats baseline =
-          new ProtoApplicationStats(
-              dexItemFactory, new CodeInspector(getReleaseApk(), getReleaseProguardMap()));
-      System.out.println(actual.getStats(baseline));
-    }
-
-    int applicationSize = compileResult.getApp().applicationSize();
-    System.out.println("Dex size (app, excluding desugared library): " + applicationSize);
-
-    Path desugaredLibrary =
-        testForL8(AndroidApiLevel.L)
-            .setDesugaredLibraryConfiguration(getDesugaredLibraryConfiguration())
-            .setDesugarJDKLibs(getDesugaredLibraryJDKLibs())
-            .setDesugarJDKLibsConfiguration(getDesugaredLibraryJDKLibsConfiguration())
-            .addKeepRules(keepRuleConsumer.get())
-            .addKeepRuleFiles(getDesugaredLibraryKeepRuleFiles())
-            .compile();
-
-    byte[] desugaredLibraryDex = ZipUtils.readSingleEntry(desugaredLibrary, "classes.dex");
-
-    if (DUMP) {
-      Files.write(dumpDirectory.resolve("desugared_jdk_libs.dex"), desugaredLibraryDex);
-    }
-
-    int desugaredLibrarySize = desugaredLibraryDex.length;
-    System.out.println("Dex size (desugared library): " + desugaredLibrarySize);
-
-    int totalApplicationSize = applicationSize + desugaredLibrarySize;
-    System.out.println("Dex size (total): " + totalApplicationSize);
-
-    assertTrue(
-        "Expected max size of " + MAX_SIZE + ", got " + totalApplicationSize,
-        totalApplicationSize < MAX_SIZE);
-  }
-}
diff --git a/src/test/java/com/android/tools/r8/internal/proto/Proto2ShrinkingTest.java b/src/test/java/com/android/tools/r8/internal/proto/Proto2ShrinkingTest.java
index 348a7f5..dd056e1 100644
--- a/src/test/java/com/android/tools/r8/internal/proto/Proto2ShrinkingTest.java
+++ b/src/test/java/com/android/tools/r8/internal/proto/Proto2ShrinkingTest.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.internal.proto;
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static com.android.tools.r8.utils.codeinspector.Matchers.notIf;
 import static org.hamcrest.CoreMatchers.anyOf;
 import static org.hamcrest.CoreMatchers.containsString;
 import static org.hamcrest.CoreMatchers.equalTo;
@@ -233,7 +234,10 @@
     }
 
     // Verify that the registry methods are still present in the output.
-    // TODO(b/112437944): Should they be optimized into a single findLiteExtensionByNumber() method?
+    //
+    // We expect findLiteExtensionByNumber2() to be inlined into findLiteExtensionByNumber1(). The
+    // method findLiteExtensionByNumber1() has two call sites from findLiteExtensionByNumber(),
+    // which prevents it from being single-caller inlined.
     {
       ClassSubject generatedExtensionRegistryLoader = outputInspector.clazz(extensionRegistryName);
       assertThat(generatedExtensionRegistryLoader, isPresent());
@@ -245,7 +249,7 @@
           isPresent());
       assertThat(
           generatedExtensionRegistryLoader.uniqueMethodWithName("findLiteExtensionByNumber2"),
-          isPresent());
+          notIf(isPresent(), enableMinification));
     }
 
     // Verify that unused extensions have been removed with -allowaccessmodification.
diff --git a/src/test/java/com/android/tools/r8/internal/proto/ProtoShrinkingTestBase.java b/src/test/java/com/android/tools/r8/internal/proto/ProtoShrinkingTestBase.java
index 478a51a..c0ce178 100644
--- a/src/test/java/com/android/tools/r8/internal/proto/ProtoShrinkingTestBase.java
+++ b/src/test/java/com/android/tools/r8/internal/proto/ProtoShrinkingTestBase.java
@@ -52,7 +52,7 @@
   public static final Path PROTO3_PROTO_JAR =
       Paths.get(ToolHelper.GENERATED_PROTO_BUILD_DIR).resolve("proto3.jar");
 
-  static void assertRewrittenProtoSchemasMatch(
+  public static void assertRewrittenProtoSchemasMatch(
       CodeInspector expectedInspector, CodeInspector actualInspector) throws Exception {
     Map<String, IntList> actualInfos = getInfoValues(actualInspector);
 
@@ -84,13 +84,13 @@
         "}");
   }
 
-  static String keepAllProtosRule() {
+  public static String keepAllProtosRule() {
     return StringUtils.lines(
         "-if class * extends com.google.protobuf.GeneratedMessageLite",
         "-keep,allowobfuscation class <1> { <init>(...); <fields>; }");
   }
 
-  static String keepDynamicMethodSignatureRule() {
+  public static String keepDynamicMethodSignatureRule() {
     return StringUtils.lines(
         "-keepclassmembers,includedescriptorclasses class com.google.protobuf.GeneratedMessageLite "
             + "{",
@@ -99,7 +99,7 @@
         "}");
   }
 
-  static String keepNewMessageInfoSignatureRule() {
+  public static String keepNewMessageInfoSignatureRule() {
     return StringUtils.lines(
         "-keepclassmembers,includedescriptorclasses class com.google.protobuf.GeneratedMessageLite "
             + "{",
diff --git a/src/test/java/com/android/tools/r8/internal/proto/YouTubeV1508ProtoRewritingTest.java b/src/test/java/com/android/tools/r8/internal/proto/YouTubeV1508ProtoRewritingTest.java
deleted file mode 100644
index dbdeed0..0000000
--- a/src/test/java/com/android/tools/r8/internal/proto/YouTubeV1508ProtoRewritingTest.java
+++ /dev/null
@@ -1,69 +0,0 @@
-// 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.internal.proto;
-
-import static com.android.tools.r8.ToolHelper.shouldRunSlowTests;
-import static com.android.tools.r8.internal.proto.ProtoShrinkingTestBase.assertRewrittenProtoSchemasMatch;
-import static com.android.tools.r8.internal.proto.ProtoShrinkingTestBase.keepAllProtosRule;
-import static com.android.tools.r8.internal.proto.ProtoShrinkingTestBase.keepDynamicMethodSignatureRule;
-import static com.android.tools.r8.internal.proto.ProtoShrinkingTestBase.keepNewMessageInfoSignatureRule;
-import static org.junit.Assume.assumeTrue;
-
-import com.android.tools.r8.TestParameters;
-import com.android.tools.r8.TestParametersCollection;
-import com.android.tools.r8.internal.LibrarySanitizer;
-import com.android.tools.r8.internal.YouTubeCompilationTestBase;
-import com.android.tools.r8.utils.AndroidApiLevel;
-import com.android.tools.r8.utils.codeinspector.CodeInspector;
-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 YouTubeV1508ProtoRewritingTest extends YouTubeCompilationTestBase {
-
-  @Parameters(name = "{0}")
-  public static TestParametersCollection data() {
-    return getTestParameters().withNoneRuntime().build();
-  }
-
-  public YouTubeV1508ProtoRewritingTest(TestParameters parameters) {
-    super(15, 8);
-    parameters.assertNoneRuntime();
-  }
-
-  @Test
-  public void test() throws Exception {
-    assumeTrue(shouldRunSlowTests());
-
-    LibrarySanitizer librarySanitizer =
-        new LibrarySanitizer(temp)
-            .addProgramFiles(getProgramFiles())
-            .addLibraryFiles(getLibraryFiles())
-            .sanitize()
-            .assertSanitizedProguardConfigurationIsEmpty();
-
-    testForR8(Backend.DEX)
-        .addProgramFiles(getProgramFiles())
-        .addLibraryFiles(librarySanitizer.getSanitizedLibrary())
-        .addKeepRuleFiles(getKeepRuleFiles())
-        .addKeepRules(
-            keepAllProtosRule(),
-            keepDynamicMethodSignatureRule(),
-            keepNewMessageInfoSignatureRule())
-        .addMainDexRuleFiles(getMainDexRuleFiles())
-        .allowCheckDiscardedErrors(true)
-        .allowDiagnosticMessages()
-        .allowUnusedDontWarnPatterns()
-        .allowUnusedProguardConfigurationRules()
-        .setMinApi(AndroidApiLevel.H_MR2)
-        .compile()
-        .inspect(this::inspect);
-  }
-
-  private void inspect(CodeInspector inspector) throws Exception {
-    assertRewrittenProtoSchemasMatch(new CodeInspector(getProgramFiles()), inspector);
-  }
-}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/callsites/CallSiteOptimizationLibraryLambdaPropagationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/callsites/CallSiteOptimizationLibraryLambdaPropagationTest.java
new file mode 100644
index 0000000..774267d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/callsites/CallSiteOptimizationLibraryLambdaPropagationTest.java
@@ -0,0 +1,71 @@
+// Copyright (c) 2020, 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.callsites;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import java.util.function.Consumer;
+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 CallSiteOptimizationLibraryLambdaPropagationTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters()
+        .withCfRuntimes()
+        .withDexRuntimes()
+        .withApiLevelsStartingAtIncluding(AndroidApiLevel.N)
+        .build();
+  }
+
+  public CallSiteOptimizationLibraryLambdaPropagationTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(CallSiteOptimizationLibraryLambdaPropagationTest.class)
+        .addKeepMainRule(TestClass.class)
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("A", "B");
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      add(new A());
+      Consumer<Object> consumer = TestClass::add;
+      consumer.accept("B");
+    }
+
+    @NeverInline
+    static void add(Object o) {
+      System.out.println(o.toString());
+    }
+  }
+
+  @NeverClassInline
+  static class A {
+
+    @Override
+    public String toString() {
+      return "A";
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/callsites/CallSiteOptimizationProgramLambdaPropagationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/callsites/CallSiteOptimizationProgramLambdaPropagationTest.java
new file mode 100644
index 0000000..86145c6
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/callsites/CallSiteOptimizationProgramLambdaPropagationTest.java
@@ -0,0 +1,69 @@
+// Copyright (c) 2020, 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.callsites;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+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 CallSiteOptimizationProgramLambdaPropagationTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public CallSiteOptimizationProgramLambdaPropagationTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(CallSiteOptimizationProgramLambdaPropagationTest.class)
+        .addKeepMainRule(TestClass.class)
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("A", "B");
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      add(new A());
+      Consumer consumer = TestClass::add;
+      consumer.accept("B");
+    }
+
+    @NeverInline
+    static void add(Object o) {
+      System.out.println(o.toString());
+    }
+  }
+
+  interface Consumer {
+    void accept(Object o);
+  }
+
+  @NeverClassInline
+  static class A {
+
+    @Override
+    public String toString() {
+      return "A";
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/inliner/SyntheticInlineNullCheckPositionTest.java b/src/test/java/com/android/tools/r8/ir/optimize/inliner/SyntheticInlineNullCheckPositionTest.java
index b5588bd..7cdd9d0 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/inliner/SyntheticInlineNullCheckPositionTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/inliner/SyntheticInlineNullCheckPositionTest.java
@@ -71,7 +71,7 @@
         .assertFailureWithErrorThatThrows(NullPointerException.class)
         .inspectStackTrace(
             stackTrace -> {
-              if (canUseJavaUtilObjectsIsNull(parameters)) {
+              if (canUseJavaUtilObjectsRequireNonNull(parameters)) {
                 assertThat(
                     stackTrace,
                     isSameExceptForSpecificLineNumber(
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/AssumeInstanceFieldValueTest.java b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/AssumeInstanceFieldValueTest.java
index 18618ca..4e275f4 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/AssumeInstanceFieldValueTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/membervaluepropagation/AssumeInstanceFieldValueTest.java
@@ -70,7 +70,7 @@
 
     MethodSubject mainMethodSubject = testClassSubject.mainMethod();
     assertThat(mainMethodSubject, isPresent());
-    if (canUseJavaUtilObjectsIsNull(parameters)) {
+    if (canUseJavaUtilObjectsRequireNonNull(parameters)) {
       assertThat(mainMethodSubject, invokesMethodWithName("requireNonNull"));
     } else {
       assertThat(mainMethodSubject, invokesMethodWithName("getClass"));
diff --git a/src/test/java/com/android/tools/r8/jasmin/InvalidDebugInfoTests.java b/src/test/java/com/android/tools/r8/jasmin/InvalidDebugInfoTests.java
index 36c9ba5..8591490 100644
--- a/src/test/java/com/android/tools/r8/jasmin/InvalidDebugInfoTests.java
+++ b/src/test/java/com/android/tools/r8/jasmin/InvalidDebugInfoTests.java
@@ -56,13 +56,8 @@
   }
 
   private void assertInvalidInfoMessages(TestDiagnosticMessages diagnostics, String message) {
-    if (parameters.isCfRuntime()) {
-      diagnostics.assertNoErrors();
-      diagnostics.assertWarningsMatch(cfD8NotSupportedDiagnostic);
-    } else {
-      diagnostics.assertOnlyInfos();
-    }
     // The reporting of invalid debug info issues three info items:
+    diagnostics.assertOnlyInfos();
     diagnostics.assertInfosMatch(
         ImmutableList.of(
             diagnosticMessage(containsString("Stripped invalid locals information")),
@@ -70,15 +65,6 @@
             diagnosticMessage(containsString("sign of using an outdated Java toolchain"))));
   }
 
-  private void assertNoMessages(TestDiagnosticMessages diagnostics) {
-    if (parameters.isCfRuntime()) {
-      diagnostics.assertOnlyWarnings();
-      diagnostics.assertWarningsMatch(cfD8NotSupportedDiagnostic);
-    } else {
-      diagnostics.assertNoMessages();
-    }
-  }
-
   // This is a regression test for invalid live-ranges of locals generated by some old Java
   // compilers. The issue is that a local slot may have been initialized outside the live-scope of
   // the variable and then the subsequent live-scope of the variable extends beyond its actual
@@ -151,7 +137,7 @@
               if (strict) {
                 assertUninitializedLocalMessage(diagnostics);
               } else {
-                assertNoMessages(diagnostics);
+                diagnostics.assertNoMessages();
               }
             })
         .run(parameters.getRuntime(), clazz.name)
@@ -216,7 +202,7 @@
               if (strict) {
                 assertUninitializedLocalMessage(diagnostics);
               } else {
-                assertNoMessages(diagnostics);
+                diagnostics.assertNoMessages();
               }
             })
         .run(parameters.getRuntime(), clazz.name)
@@ -453,7 +439,7 @@
         .addProgramClassFileData(builder.buildClasses())
         .addOptionsModification(this::optionsModification)
         .setMinApi(parameters.getApiLevel())
-        .compileWithExpectedDiagnostics(this::assertNoMessages)
+        .compileWithExpectedDiagnostics(TestDiagnosticMessages::assertNoMessages)
         .run(parameters.getRuntime(), clazz.name)
         .assertSuccessWithOutput(expected)
         .inspect(
diff --git a/src/test/java/com/android/tools/r8/missingclasses/MissingClassesTestBase.java b/src/test/java/com/android/tools/r8/missingclasses/MissingClassesTestBase.java
index 4dfeca1..2e6ffd2 100644
--- a/src/test/java/com/android/tools/r8/missingclasses/MissingClassesTestBase.java
+++ b/src/test/java/com/android/tools/r8/missingclasses/MissingClassesTestBase.java
@@ -14,9 +14,9 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.ThrowableConsumer;
 import com.android.tools.r8.diagnostic.DefinitionContext;
-import com.android.tools.r8.diagnostic.internal.DefinitionContextUtils;
 import com.android.tools.r8.references.ClassReference;
 import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.utils.MissingDefinitionsDiagnosticTestUtils;
 import java.lang.annotation.Retention;
 import java.lang.annotation.RetentionPolicy;
 import java.util.List;
@@ -106,8 +106,8 @@
     inspectDiagnosticsWithIgnoreWarnings(
         diagnostics,
         referencedFrom,
-        getExpectedDiagnosticMessage(
-            DefinitionContextUtils.toSourceString(referencedFrom[0]), referencedFrom.length));
+        MissingDefinitionsDiagnosticTestUtils.getMissingClassMessage(
+            getMissingClassReference(), referencedFrom));
   }
 
   void inspectDiagnosticsWithIgnoreWarnings(
@@ -136,8 +136,8 @@
     inspectDiagnosticsWithNoRules(
         diagnostics,
         referencedFrom,
-        getExpectedDiagnosticMessage(
-            DefinitionContextUtils.toSourceString(referencedFrom[0]), referencedFrom.length));
+        MissingDefinitionsDiagnosticTestUtils.getMissingClassMessage(
+            getMissingClassReference(), referencedFrom));
   }
 
   void inspectDiagnosticsWithNoRules(
@@ -159,19 +159,4 @@
                     .assertHasMessage(expectedDiagnosticMessage)
                     .assertNumberOfMissingClasses(1));
   }
-
-  private String getExpectedDiagnosticMessage(String referencedFrom, int numberOfContexts) {
-    StringBuilder builder =
-        new StringBuilder("Missing class ")
-            .append(getMissingClassReference().getTypeName())
-            .append(" (referenced from: ")
-            .append(referencedFrom);
-    if (numberOfContexts > 1) {
-      builder.append(" and ").append(numberOfContexts - 1).append(" other context");
-      if (numberOfContexts > 2) {
-        builder.append("s");
-      }
-    }
-    return builder.append(")").toString();
-  }
 }
diff --git a/src/test/java/com/android/tools/r8/naming/InterfaceRenamingTestRunner.java b/src/test/java/com/android/tools/r8/naming/InterfaceRenamingTestRunner.java
index f40e8b3..4748dad 100644
--- a/src/test/java/com/android/tools/r8/naming/InterfaceRenamingTestRunner.java
+++ b/src/test/java/com/android/tools/r8/naming/InterfaceRenamingTestRunner.java
@@ -14,13 +14,11 @@
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.ToolHelper.ProcessResult;
-import com.android.tools.r8.VmTestRunner;
 import com.android.tools.r8.origin.Origin;
 import java.nio.file.Path;
 import java.util.Arrays;
 import java.util.List;
 import org.junit.Test;
-import org.junit.runner.RunWith;
 
 public class InterfaceRenamingTestRunner extends TestBase {
 
diff --git a/src/test/java/com/android/tools/r8/naming/MinifierClassSignatureTest.java b/src/test/java/com/android/tools/r8/naming/MinifierClassSignatureTest.java
index e3e965c..dc3acee 100644
--- a/src/test/java/com/android/tools/r8/naming/MinifierClassSignatureTest.java
+++ b/src/test/java/com/android/tools/r8/naming/MinifierClassSignatureTest.java
@@ -69,6 +69,9 @@
   String extendsInnerSignature = "LOuter<TT;>.Inner;";
   String extendsInnerInnerSignature = "LOuter<TT;>.Inner.InnerInner;";
 
+  String extendsInnerSignatureInvalidOuter = "LOuter.Inner;";
+  String extendsInnerInnerSignatureInvalidOuter = "LOuter.Inner.InnerInner;";
+
   private final TestParameters parameters;
 
   @Parameters(name = "{0}")
@@ -80,13 +83,12 @@
     this.parameters = parameters;
   }
 
-  private byte[] dumpSimple(String classSignature) throws Exception {
+  private byte[] dumpSimple(String classSignature) {
 
     ClassWriter cw = new ClassWriter(0);
     MethodVisitor mv;
 
-    String signature = classSignature;
-    cw.visit(V1_8, ACC_SUPER, "Simple", signature, "java/lang/Object", null);
+    cw.visit(V1_8, ACC_SUPER, "Simple", classSignature, "java/lang/Object", null);
 
     {
       mv = cw.visitMethod(0, "<init>", "()V", null, null);
@@ -102,7 +104,7 @@
     return cw.toByteArray();
   }
 
-  private byte[] dumpBase(String classSignature) throws Exception {
+  private byte[] dumpBase(String classSignature) {
 
     final String javacClassSignature = baseSignature;
     ClassWriter cw = new ClassWriter(0);
@@ -190,7 +192,7 @@
     return cw.toByteArray();
   }
 
-  private byte[] dumpExtendsInner(String classSignature) throws Exception {
+  private byte[] dumpExtendsInner(String classSignature) {
 
     final String javacClassSignature = extendsInnerSignature;
     ClassWriter cw = new ClassWriter(0);
@@ -226,7 +228,7 @@
     return cw.toByteArray();
   }
 
-  private byte[] dumpInnerInner(String classSignature) throws Exception {
+  private byte[] dumpInnerInner(String classSignature) {
 
     final String javacClassSignature = null;
     ClassWriter cw = new ClassWriter(0);
@@ -261,7 +263,7 @@
     return cw.toByteArray();
   }
 
-  private byte[] dumpExtendsInnerInner(String classSignature) throws Exception {
+  private byte[] dumpExtendsInnerInner(String classSignature) {
 
     final String javacClassSignature = extendsInnerInnerSignature;
     ClassWriter cw = new ClassWriter(0);
@@ -304,7 +306,8 @@
   public void runTest(
       ImmutableMap<String, String> signatures,
       Consumer<TestDiagnosticMessages> diagnostics,
-      ThrowingConsumer<CodeInspector, Exception> inspect)
+      ThrowingConsumer<CodeInspector, Exception> inspect,
+      boolean noOuterFormals)
       throws Exception {
     R8TestCompileResult compileResult =
         testForR8(parameters.getBackend())
@@ -355,14 +358,16 @@
       assertNull(inspector.clazz("Outer$Inner").getOriginalSignatureAttribute());
     }
     if (!signatures.containsKey("Outer$ExtendsInner")) {
-      assertEquals(extendsInnerSignature,
+      assertEquals(
+          noOuterFormals ? extendsInnerSignatureInvalidOuter : extendsInnerSignature,
           inspector.clazz("Outer$ExtendsInner").getOriginalSignatureAttribute());
     }
     if (!signatures.containsKey("Outer$Inner$InnerInner")) {
       assertNull(inspector.clazz("Outer$Inner$InnerInner").getOriginalSignatureAttribute());
     }
     if (!signatures.containsKey("Outer$Inner$ExtendsInnerInner")) {
-      assertEquals(extendsInnerInnerSignature,
+      assertEquals(
+          noOuterFormals ? extendsInnerInnerSignatureInvalidOuter : extendsInnerInnerSignature,
           inspector.clazz("Outer$Inner$ExtendsInnerInner").getOriginalSignatureAttribute());
     }
 
@@ -374,10 +379,11 @@
       String name,
       String signature,
       Consumer<TestDiagnosticMessages> diagnostics,
-      ThrowingConsumer<CodeInspector, Exception> inspector)
+      ThrowingConsumer<CodeInspector, Exception> inspector,
+      boolean noOuterFormals)
       throws Exception {
     ImmutableMap<String, String> signatures = ImmutableMap.of(name, signature);
-    runTest(signatures, diagnostics, inspector);
+    runTest(signatures, diagnostics, inspector, noOuterFormals);
   }
 
   private void noInspection(CodeInspector inspector) {
@@ -391,7 +397,7 @@
   @Test
   public void originalJavacSignatures() throws Exception {
     // Test using the signatures generated by javac.
-    runTest(ImmutableMap.of(), TestDiagnosticMessages::assertNoWarnings, this::noInspection);
+    runTest(ImmutableMap.of(), TestDiagnosticMessages::assertNoWarnings, this::noInspection, false);
   }
 
   @Test
@@ -404,7 +410,8 @@
           ClassSubject outer = inspector.clazz("Outer");
           assertNull(outer.getFinalSignatureAttribute());
           assertNull(outer.getOriginalSignatureAttribute());
-        });
+        },
+        true);
   }
 
   @Test
@@ -425,7 +432,8 @@
               "<T:" + simple.getFinalDescriptor() + ">" + baseDescriptorWithoutSemicolon + "<TT;>;";
           assertEquals(minifiedSignature, outer.getFinalSignatureAttribute());
           assertEquals(signature, outer.getOriginalSignatureAttribute());
-        });
+        },
+        false);
   }
 
   @Test
@@ -447,7 +455,8 @@
           String minifiedSignature = outerDescriptorWithoutSemicolon + "<TT;>." + innerLastPart;
           assertEquals(minifiedSignature, extendsInner.getFinalSignatureAttribute());
           assertEquals(signature, extendsInner.getOriginalSignatureAttribute());
-        });
+        },
+        false);
   }
 
   @Test
@@ -461,7 +470,8 @@
           assertThat(inspector.clazz("NotFound"), not(isPresent()));
           ClassSubject outer = inspector.clazz("Outer");
           assertEquals(signature, outer.getOriginalSignatureAttribute());
-        });
+        },
+        false);
   }
 
   @Test
@@ -474,13 +484,15 @@
         inspector -> {
           assertThat(inspector.clazz("NotFound"), not(isPresent()));
           ClassSubject outer = inspector.clazz("Outer$ExtendsInner");
-          assertEquals(signature, outer.getOriginalSignatureAttribute());
-        });
+          // TODO(b/1867459990): What to do here.
+          assertEquals("LOuter$NotFound;", outer.getOriginalSignatureAttribute());
+        },
+        false);
   }
 
   @Test
   public void classSignatureExtendsInner_outerAndInnerClassNotFound() throws Exception {
-    String signature = "LNotFound<TT;>.AlsoNotFound;";
+    String signature = "LNotFound$AlsoNotFound;";
     testSingleClass(
         "Outer$ExtendsInner",
         signature,
@@ -489,7 +501,8 @@
           assertThat(inspector.clazz("NotFound"), not(isPresent()));
           ClassSubject outer = inspector.clazz("Outer$ExtendsInner");
           assertEquals(signature, outer.getOriginalSignatureAttribute());
-        });
+        },
+        false);
   }
 
   @Test
@@ -502,8 +515,10 @@
         inspector -> {
           assertThat(inspector.clazz("NotFound"), not(isPresent()));
           ClassSubject outer = inspector.clazz("Outer$ExtendsInner");
-          assertEquals(signature, outer.getOriginalSignatureAttribute());
-        });
+          // TODO(b/1867459990): What to do here.
+          assertEquals("LOuter$Inner$NotFound;", outer.getOriginalSignatureAttribute());
+        },
+        false);
   }
 
   @Test
@@ -516,8 +531,10 @@
         inspector -> {
           assertThat(inspector.clazz("NotFound"), not(isPresent()));
           ClassSubject outer = inspector.clazz("Outer$ExtendsInner");
-          assertEquals(signature, outer.getOriginalSignatureAttribute());
-        });
+          // TODO(b/1867459990): What to do here.
+          assertEquals("LOuter$NotFound$AlsoNotFound;", outer.getOriginalSignatureAttribute());
+        },
+        false);
   }
 
   @Test
@@ -533,7 +550,8 @@
                   diagnosticMessage(containsString("Expected L at position 1")),
                   diagnosticOrigin(Origin.unknown())));
         },
-        inspector -> noSignatureAttribute(inspector.clazz("Outer")));
+        inspector -> noSignatureAttribute(inspector.clazz("Outer")),
+        true);
   }
 
   @Test
@@ -549,7 +567,8 @@
                   diagnosticMessage(containsString("Unexpected end of signature at position 3")),
                   diagnosticOrigin(Origin.unknown())));
         },
-        inspector -> noSignatureAttribute(inspector.clazz("Outer")));
+        inspector -> noSignatureAttribute(inspector.clazz("Outer")),
+        true);
   }
 
   @Test
@@ -566,7 +585,8 @@
                   diagnosticMessage(containsString("Expected L at position 1")),
                   diagnosticOrigin(Origin.unknown())));
         },
-        inspector -> noSignatureAttribute(inspector.clazz("Outer$ExtendsInner")));
+        inspector -> noSignatureAttribute(inspector.clazz("Outer$ExtendsInner")),
+        false);
   }
 
   @Test
@@ -584,7 +604,8 @@
                   diagnosticMessage(containsString("Expected L at position 1")),
                   diagnosticOrigin(Origin.unknown())));
         },
-        inspector -> noSignatureAttribute(inspector.clazz("Outer$Inner$ExtendsInnerInner")));
+        inspector -> noSignatureAttribute(inspector.clazz("Outer$Inner$ExtendsInnerInner")),
+        false);
   }
 
   @Test
@@ -601,7 +622,8 @@
           noSignatureAttribute(inspector.clazz("Outer"));
           noSignatureAttribute(inspector.clazz("Outer$ExtendsInner"));
           noSignatureAttribute(inspector.clazz("Outer$Inner$ExtendsInnerInner"));
-        });
+        },
+        false);
   }
 
   @Test
@@ -622,6 +644,7 @@
         },
         inspector -> {
           noSignatureAttribute(inspector.clazz("Outer$ExtendsInner"));
-        });
+        },
+        false);
   }
 }
diff --git a/src/test/java/com/android/tools/r8/naming/MinifierFieldSignatureTest.java b/src/test/java/com/android/tools/r8/naming/MinifierFieldSignatureTest.java
index 53e52b4..1e5b66c 100644
--- a/src/test/java/com/android/tools/r8/naming/MinifierFieldSignatureTest.java
+++ b/src/test/java/com/android/tools/r8/naming/MinifierFieldSignatureTest.java
@@ -296,7 +296,7 @@
 
   @Test
   public void classNotFound() throws Exception {
-    String signature = "LNotFound<TX;>.InnerNotFound.InnerAlsoNotFound;";
+    String signature = "LNotFound$InnerNotFound$InnerAlsoNotFound;";
     testSingleField(
         "anX",
         signature,
diff --git a/src/test/java/com/android/tools/r8/naming/MinifierMethodSignatureTest.java b/src/test/java/com/android/tools/r8/naming/MinifierMethodSignatureTest.java
index f88443d..9f693b0 100644
--- a/src/test/java/com/android/tools/r8/naming/MinifierMethodSignatureTest.java
+++ b/src/test/java/com/android/tools/r8/naming/MinifierMethodSignatureTest.java
@@ -103,7 +103,7 @@
 
   @Test
   public void classNotFound() throws Exception {
-    String signature = "<T:LNotFound;>(TT;LAlsoNotFound<TT;>.InnerNotFound.InnerAlsoNotFound;)TT;";
+    String signature = "<T:LNotFound;>(TT;LAlsoNotFound$InnerNotFound$InnerAlsoNotFound;)TT;";
     testSingleMethod(
         "generic",
         signature,
diff --git a/src/test/java/com/android/tools/r8/naming/b124357885/B124357885Test.java b/src/test/java/com/android/tools/r8/naming/b124357885/B124357885Test.java
index d56503c..bd10054 100644
--- a/src/test/java/com/android/tools/r8/naming/b124357885/B124357885Test.java
+++ b/src/test/java/com/android/tools/r8/naming/b124357885/B124357885Test.java
@@ -49,15 +49,7 @@
   private void checkSignature(CodeInspector inspector, String signature) {
     String fooImplFinalDescriptor =
         DescriptorUtils.javaTypeToDescriptor(inspector.clazz(FooImpl.class).getFinalName());
-    StringBuilder expected =
-        new StringBuilder()
-            .append("()")
-            // Remove the final ; from the descriptor to add the generic type.
-            .append(fooImplFinalDescriptor.substring(0, fooImplFinalDescriptor.length() - 1))
-            .append("<Ljava/lang/String;>")
-            // Add the ; after the generic type.
-            .append(";");
-    assertEquals(expected.toString(), signature);
+    assertEquals("()" + fooImplFinalDescriptor, signature);
   }
 
   @Test
@@ -98,9 +90,14 @@
   public static class Main {
     public static void main(String... args) throws Exception {
       Method method = Service.class.getMethod("fooList");
-      ParameterizedType type = (ParameterizedType) method.getGenericReturnType();
-      Class<?> rawType = (Class<?>) type.getRawType();
-      System.out.println(rawType.getName());
+
+      try {
+        ParameterizedType type = (ParameterizedType) method.getGenericReturnType();
+        Class<?> rawType = (Class<?>) type.getRawType();
+        System.out.println(rawType.getName());
+      } catch (ClassCastException e) {
+        System.out.println(((Class<?>) method.getGenericReturnType()).getName());
+      }
 
       // Convince R8 we only use subtypes to get class merging of Foo into FooImpl.
       Foo<String> foo = new FooImpl<>();
diff --git a/src/test/java/com/android/tools/r8/regress/b152973695/CompileToInvalidFileTest.java b/src/test/java/com/android/tools/r8/regress/b152973695/CompileToInvalidFileTest.java
index 7d3d07b..152656f 100644
--- a/src/test/java/com/android/tools/r8/regress/b152973695/CompileToInvalidFileTest.java
+++ b/src/test/java/com/android/tools/r8/regress/b152973695/CompileToInvalidFileTest.java
@@ -80,11 +80,7 @@
   }
 
   private void checkDiagnostics(TestDiagnosticMessages diagnostics, boolean isD8) {
-    if (classFileConsumer && isD8) {
-      diagnostics.assertWarningsMatch(cfD8NotSupportedDiagnostic);
-    } else {
-      diagnostics.assertOnlyErrors();
-    }
+    diagnostics.assertOnlyErrors();
     diagnostics.assertAllErrorsMatch(diagnosticMessage(containsString(INVALID_FILE.toString())));
   }
 
diff --git a/src/test/java/com/android/tools/r8/regress/b72485384/Regress72485384Test.java b/src/test/java/com/android/tools/r8/regress/b72485384/Regress72485384Test.java
index 2a7889d..a3d670e 100644
--- a/src/test/java/com/android/tools/r8/regress/b72485384/Regress72485384Test.java
+++ b/src/test/java/com/android/tools/r8/regress/b72485384/Regress72485384Test.java
@@ -23,9 +23,6 @@
 
   @Parameters(name = "{1}, allowUnusedProguardConfigurationRules: {0}")
   public static Collection<Object[]> getParameters() {
-    String baseConfig =
-        keepMainProguardConfiguration(Main.class)
-            + "-keepattributes Signature,InnerClasses,EnclosingMethod ";
     TestParametersCollection parametersCollection =
         getTestParameters()
             .withDexRuntimes()
@@ -36,10 +33,10 @@
       Collections.addAll(
           tests,
           new Object[][] {
-            {parameters, baseConfig},
-            {parameters, baseConfig + "-dontshrink"},
-            {parameters, baseConfig + "-dontshrink -dontobfuscate"},
-            {parameters, baseConfig + "-dontobfuscate"}
+            {parameters, ""},
+            {parameters, "-dontshrink"},
+            {parameters, "-dontshrink -dontobfuscate"},
+            {parameters, "-dontobfuscate"}
           });
     }
     return tests;
@@ -50,7 +47,10 @@
 
   public Regress72485384Test(TestParameters parameters, String proguardConfig) {
     this.parameters = parameters;
-    this.proguardConfig = proguardConfig;
+    this.proguardConfig =
+        keepMainProguardConfiguration(Main.class)
+            + "-keepattributes Signature,InnerClasses,EnclosingMethod "
+            + proguardConfig;
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/shaking/attributes/KeepSignatureTest.java b/src/test/java/com/android/tools/r8/shaking/attributes/KeepSignatureTest.java
index ef2e860..9dfff6e 100644
--- a/src/test/java/com/android/tools/r8/shaking/attributes/KeepSignatureTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/attributes/KeepSignatureTest.java
@@ -56,8 +56,7 @@
 
   @Test
   public void testKeptClassFieldAndMethodFull() throws Exception {
-    // TODO(b/172999267): The below should be true
-    runTest(testForR8(parameters.getBackend()), true);
+    runTest(testForR8(parameters.getBackend()), false);
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceInitializedByInvokeStaticTest.java b/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceInitializedByInvokeStaticTest.java
index e7a460d..1931487 100644
--- a/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceInitializedByInvokeStaticTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceInitializedByInvokeStaticTest.java
@@ -35,7 +35,7 @@
     testForDesugaring(parameters)
         .addInnerClasses(getClass())
         .run(parameters.getRuntime(), TestClass.class)
-        .assertSuccessWithOutputLines("I");
+        .assertSuccessWithOutputLines("I", "J");
   }
 
   @Test
@@ -47,7 +47,7 @@
         .setMinApi(parameters.getApiLevel())
         .compile()
         .run(parameters.getRuntime(), TestClass.class)
-        .assertSuccessWithOutputLines("I");
+        .assertSuccessWithOutputLines("I", "J");
   }
 
   @Test
@@ -56,7 +56,7 @@
     testForJvm()
         .addTestClasspath()
         .run(parameters.getRuntime(), TestClass.class)
-        .assertSuccessWithOutputLines("I");
+        .assertSuccessWithOutputLines("I", "J");
   }
 
   @Test
@@ -68,12 +68,14 @@
                 .build(),
             TestClass.class);
     assertMayHaveClassInitializationSideEffects(appView, I.class);
+    assertMayHaveClassInitializationSideEffects(appView, J.class);
   }
 
   static class TestClass {
 
     public static void main(String[] args) {
       I.greet();
+      J.greet();
     }
   }
 
@@ -84,10 +86,21 @@
     static void greet() {}
   }
 
+  interface J {
+
+    long value = new Greeter("J").longValue();
+
+    static void greet() {}
+  }
+
   static class Greeter {
 
     Greeter(String greeting) {
       System.out.println(greeting);
     }
+
+    long longValue() {
+      return 42;
+    }
   }
 }
diff --git a/src/test/java/com/android/tools/r8/tracereferences/TraceReferencesCommandTest.java b/src/test/java/com/android/tools/r8/tracereferences/TraceReferencesCommandTest.java
index 02deedd..d905d4c 100644
--- a/src/test/java/com/android/tools/r8/tracereferences/TraceReferencesCommandTest.java
+++ b/src/test/java/com/android/tools/r8/tracereferences/TraceReferencesCommandTest.java
@@ -3,6 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.tracereferences;
 
+import static com.android.tools.r8.utils.MissingDefinitionsDiagnosticTestUtils.getMissingClassMessage;
+import static com.android.tools.r8.utils.MissingDefinitionsDiagnosticTestUtils.getMissingFieldMessage;
+import static com.android.tools.r8.utils.MissingDefinitionsDiagnosticTestUtils.getMissingMethodMessage;
 import static org.hamcrest.CoreMatchers.containsString;
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assert.assertEquals;
@@ -17,6 +20,8 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.diagnostic.DefinitionContext;
+import com.android.tools.r8.diagnostic.internal.DefinitionMethodContextImpl;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.references.Reference;
 import com.android.tools.r8.utils.AndroidApiLevel;
@@ -236,7 +241,7 @@
               .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.P))
               .addTargetFiles(targetJar)
               .addSourceFiles(sourceJar)
-              .setConsumer(consumer)
+              .setConsumer(new TraceReferencesCheckConsumer(consumer))
               .build());
       assertEquals(expected, stringConsumer.get());
       if (diagnosticsCheckerConsumer != null) {
@@ -571,18 +576,23 @@
       System.setOut(originalOut);
     }
 
+    DefinitionContext referencedFrom =
+        DefinitionMethodContextImpl.builder()
+            .setMethodContext(Reference.methodFromMethod(Source.class.getDeclaredMethod("source")))
+            .setOrigin(getOrigin(Source.class))
+            .build();
     assertThat(
         baosErr.toString(Charsets.UTF_8.name()),
         containsString(
             StringUtils.lines(
-                "Warning: Missing class " + Target.class.getTypeName(),
-                "Missing field "
-                    + FieldReferenceUtils.toSourceString(
-                        FieldReferenceUtils.fieldFromField(Target.class, "field")),
-                "Missing method "
-                    + MethodReferenceUtils.toSourceString(
-                        MethodReferenceUtils.methodFromMethod(
-                            Target.class, "method", int.class)))));
+                "Warning: "
+                    + getMissingClassMessage(
+                        Reference.classFromClass(Target.class), referencedFrom),
+                getMissingFieldMessage(
+                    FieldReferenceUtils.fieldFromField(Target.class, "field"), referencedFrom),
+                getMissingMethodMessage(
+                    MethodReferenceUtils.methodFromMethod(Target.class, "method", int.class),
+                    referencedFrom))));
     assertEquals(0, baosOut.size());
   }
 
@@ -621,18 +631,24 @@
     }
 
     assertEquals(0, baosErr.size());
+
+    DefinitionContext referencedFrom =
+        DefinitionMethodContextImpl.builder()
+            .setMethodContext(Reference.methodFromMethod(Source.class.getDeclaredMethod("source")))
+            .setOrigin(getOrigin(Source.class))
+            .build();
     assertThat(
         baosOut.toString(Charsets.UTF_8.name()),
         containsString(
             StringUtils.lines(
-                "Info: Missing class " + Target.class.getTypeName(),
-                "Missing field "
-                    + FieldReferenceUtils.toSourceString(
-                        FieldReferenceUtils.fieldFromField(Target.class, "field")),
-                "Missing method "
-                    + MethodReferenceUtils.toSourceString(
-                        MethodReferenceUtils.methodFromMethod(
-                            Target.class, "method", int.class)))));
+                "Info: "
+                    + getMissingClassMessage(
+                        Reference.classFromClass(Target.class), referencedFrom),
+                getMissingFieldMessage(
+                    FieldReferenceUtils.fieldFromField(Target.class, "field"), referencedFrom),
+                getMissingMethodMessage(
+                    MethodReferenceUtils.methodFromMethod(Target.class, "method", int.class),
+                    referencedFrom))));
   }
 
   private void checkTargetPartlyMissing(DiagnosticsChecker diagnosticsChecker) {
diff --git a/src/test/java/com/android/tools/r8/tracereferences/TraceReferencesDiagnosticTest.java b/src/test/java/com/android/tools/r8/tracereferences/TraceReferencesDiagnosticTest.java
index 292271d..c12e681 100644
--- a/src/test/java/com/android/tools/r8/tracereferences/TraceReferencesDiagnosticTest.java
+++ b/src/test/java/com/android/tools/r8/tracereferences/TraceReferencesDiagnosticTest.java
@@ -3,6 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.tracereferences;
 
+import static com.android.tools.r8.utils.MissingDefinitionsDiagnosticTestUtils.getMissingClassMessage;
+import static com.android.tools.r8.utils.MissingDefinitionsDiagnosticTestUtils.getMissingFieldMessage;
+import static com.android.tools.r8.utils.MissingDefinitionsDiagnosticTestUtils.getMissingMethodMessage;
 import static org.junit.Assert.fail;
 
 import com.android.tools.r8.CompilationFailedException;
@@ -12,7 +15,10 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.diagnostic.DefinitionContext;
+import com.android.tools.r8.diagnostic.internal.DefinitionMethodContextImpl;
 import com.android.tools.r8.references.Reference;
+import com.android.tools.r8.tracereferences.TraceReferencesCommandTest.Source;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.StringDiagnostic;
@@ -68,28 +74,49 @@
               .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.P))
               .addSourceFiles(sourceJar)
               .addTargetFiles(targetJar)
-              .setConsumer(TraceReferencesConsumer.emptyConsumer())
+              .setConsumer(
+                  new TraceReferencesCheckConsumer(TraceReferencesConsumer.emptyConsumer()))
               .build());
       fail("Unexpected success");
     } catch (CompilationFailedException e) {
       // Expected.
     }
 
+    DefinitionContext referencedFrom =
+        DefinitionMethodContextImpl.builder()
+            .setMethodContext(Reference.methodFromMethod(Source.class.getDeclaredMethod("source")))
+            .setOrigin(getOrigin(Source.class))
+            .build();
     testDiagnosticMessages.inspectErrors(
         diagnostic ->
             diagnostic
                 .assertIsMissingDefinitionsDiagnostic()
                 .assertHasMessage(
                     StringUtils.joinLines(
-                        "Missing class " + Target1.class.getTypeName(),
-                        "Missing method void " + Target1.class.getTypeName() + ".<init>()",
-                        "Missing class " + Target2.class.getTypeName(),
-                        "Missing method void " + Target2.class.getTypeName() + ".<init>()",
-                        "Missing class " + Target3.class.getTypeName(),
-                        "Missing method void " + Target3.class.getTypeName() + ".<init>()",
-                        "Missing field int " + Target.class.getTypeName() + ".missingField1",
-                        "Missing field int " + Target.class.getTypeName() + ".missingField2",
-                        "Missing method void " + Target.class.getTypeName() + ".missingMethod()"))
+                        getMissingClassMessage(Target1.class, referencedFrom),
+                        getMissingMethodMessage(
+                            Reference.methodFromMethod(Target1.class.getDeclaredConstructor()),
+                            referencedFrom),
+                        getMissingClassMessage(Target2.class, referencedFrom),
+                        getMissingMethodMessage(
+                            Reference.methodFromMethod(Target2.class.getDeclaredConstructor()),
+                            referencedFrom),
+                        getMissingClassMessage(Target3.class, referencedFrom),
+                        getMissingMethodMessage(
+                            Reference.methodFromMethod(Target3.class.getDeclaredConstructor()),
+                            referencedFrom),
+                        getMissingFieldMessage(
+                            Reference.fieldFromField(
+                                Target.class.getDeclaredField("missingField1")),
+                            referencedFrom),
+                        getMissingFieldMessage(
+                            Reference.fieldFromField(
+                                Target.class.getDeclaredField("missingField2")),
+                            referencedFrom),
+                        getMissingMethodMessage(
+                            Reference.methodFromMethod(
+                                Target.class.getDeclaredMethod("missingMethod")),
+                            referencedFrom)))
                 .assertIsAllMissingClasses(Target1.class, Target2.class, Target3.class)
                 .assertIsAllMissingFields(
                     Reference.fieldFromField(Target.class.getField("missingField1")),
@@ -139,22 +166,37 @@
               .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.P))
               .addSourceFiles(sourceJar)
               .addTargetFiles(targetJar)
-              .setConsumer(TraceReferencesConsumer.emptyConsumer())
+              .setConsumer(
+                  new TraceReferencesCheckConsumer(TraceReferencesConsumer.emptyConsumer()))
               .build());
       fail("Unexpected success");
     } catch (CompilationFailedException e) {
       // Expected.
     }
 
+    DefinitionContext referencedFrom =
+        DefinitionMethodContextImpl.builder()
+            .setMethodContext(Reference.methodFromMethod(Source.class.getDeclaredMethod("source")))
+            .setOrigin(getOrigin(Source.class))
+            .build();
     testDiagnosticMessages.inspectErrors(
         diagnostic ->
             diagnostic
                 .assertIsMissingDefinitionsDiagnostic()
                 .assertHasMessage(
                     StringUtils.joinLines(
-                        "Missing field int " + Target.class.getTypeName() + ".missingField1",
-                        "Missing field int " + Target.class.getTypeName() + ".missingField2",
-                        "Missing method void " + Target.class.getTypeName() + ".missingMethod()"))
+                        getMissingFieldMessage(
+                            Reference.fieldFromField(
+                                Target.class.getDeclaredField("missingField1")),
+                            referencedFrom),
+                        getMissingFieldMessage(
+                            Reference.fieldFromField(
+                                Target.class.getDeclaredField("missingField2")),
+                            referencedFrom),
+                        getMissingMethodMessage(
+                            Reference.methodFromMethod(
+                                Target.class.getDeclaredMethod("missingMethod")),
+                            referencedFrom)))
                 .assertNoMissingClasses()
                 .assertIsAllMissingFields(
                     Reference.fieldFromField(Target.class.getField("missingField1")),
@@ -195,19 +237,27 @@
               .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.P))
               .addSourceFiles(sourceJar)
               .addTargetFiles(targetJar)
-              .setConsumer(TraceReferencesConsumer.emptyConsumer())
+              .setConsumer(
+                  new TraceReferencesCheckConsumer(TraceReferencesConsumer.emptyConsumer()))
               .build());
       fail("Unexpected success");
     } catch (CompilationFailedException e) {
       // Expected.
     }
 
+    DefinitionContext referencedFrom =
+        DefinitionMethodContextImpl.builder()
+            .setMethodContext(Reference.methodFromMethod(Source.class.getDeclaredMethod("source")))
+            .setOrigin(getOrigin(Source.class))
+            .build();
     testDiagnosticMessages.inspectErrors(
         diagnostic ->
             diagnostic
                 .assertIsMissingDefinitionsDiagnostic()
                 .assertHasMessage(
-                    "Missing method void " + Target.class.getTypeName() + ".missingMethod()")
+                    getMissingMethodMessage(
+                        Reference.methodFromMethod(Target.class.getDeclaredMethod("missingMethod")),
+                        referencedFrom))
                 .assertNoMissingClasses()
                 .assertNoMissingFields()
                 .assertIsAllMissingMethods(
diff --git a/src/test/java/com/android/tools/r8/tracereferences/TraceReferencesMissingReferencesInDexTest.java b/src/test/java/com/android/tools/r8/tracereferences/TraceReferencesMissingReferencesInDexTest.java
index 61f5dab..b1e75c2 100644
--- a/src/test/java/com/android/tools/r8/tracereferences/TraceReferencesMissingReferencesInDexTest.java
+++ b/src/test/java/com/android/tools/r8/tracereferences/TraceReferencesMissingReferencesInDexTest.java
@@ -76,7 +76,7 @@
           TraceReferencesCommand.builder(diagnosticsChecker)
               .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.P))
               .addSourceFiles(sourceDex)
-              .setConsumer(consumer)
+              .setConsumer(new TraceReferencesCheckConsumer(consumer))
               .build());
       fail("Expected compilation to fail");
     } catch (CompilationFailedException e) {
@@ -113,7 +113,7 @@
           TraceReferencesCommand.builder(diagnosticsChecker)
               .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.P))
               .addSourceFiles(sourceDex)
-              .setConsumer(consumer)
+              .setConsumer(new TraceReferencesCheckConsumer(consumer))
               .build());
       fail("Expected compilation to fail");
     } catch (CompilationFailedException e) {
diff --git a/src/test/java/com/android/tools/r8/utils/MissingDefinitionsDiagnosticTestUtils.java b/src/test/java/com/android/tools/r8/utils/MissingDefinitionsDiagnosticTestUtils.java
new file mode 100644
index 0000000..18814e1
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/utils/MissingDefinitionsDiagnosticTestUtils.java
@@ -0,0 +1,61 @@
+// Copyright (c) 2021, 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.utils;
+
+import com.android.tools.r8.diagnostic.DefinitionContext;
+import com.android.tools.r8.diagnostic.internal.DefinitionContextUtils;
+import com.android.tools.r8.references.ClassReference;
+import com.android.tools.r8.references.FieldReference;
+import com.android.tools.r8.references.MethodReference;
+import com.android.tools.r8.references.Reference;
+
+public class MissingDefinitionsDiagnosticTestUtils {
+
+  public static String getMissingClassMessage(
+      Class<?> missingClass, DefinitionContext... referencedFrom) {
+    return getMissingClassMessage(Reference.classFromClass(missingClass), referencedFrom);
+  }
+
+  public static String getMissingClassMessage(
+      ClassReference missingReference, DefinitionContext... referencedFrom) {
+    StringBuilder builder =
+        new StringBuilder("Missing class ").append(missingReference.getTypeName());
+    appendReferencedFromSuffix(builder, referencedFrom);
+    return builder.toString();
+  }
+
+  public static String getMissingFieldMessage(
+      FieldReference missingReference, DefinitionContext... referencedFrom) {
+    StringBuilder builder =
+        new StringBuilder("Missing field ")
+            .append(FieldReferenceUtils.toSourceString(missingReference));
+    appendReferencedFromSuffix(builder, referencedFrom);
+    return builder.toString();
+  }
+
+  public static String getMissingMethodMessage(
+      MethodReference missingReference, DefinitionContext... referencedFrom) {
+    StringBuilder builder =
+        new StringBuilder("Missing method ")
+            .append(MethodReferenceUtils.toSourceString(missingReference));
+    appendReferencedFromSuffix(builder, referencedFrom);
+    return builder.toString();
+  }
+
+  private static void appendReferencedFromSuffix(
+      StringBuilder builder, DefinitionContext... referencedFrom) {
+    builder
+        .append(" (referenced from: ")
+        .append(DefinitionContextUtils.toSourceString(referencedFrom[0]));
+    int numberOfContexts = referencedFrom.length;
+    if (numberOfContexts > 1) {
+      builder.append(" and ").append(numberOfContexts - 1).append(" other context");
+      if (numberOfContexts > 2) {
+        builder.append("s");
+      }
+    }
+    builder.append(")");
+  }
+}
diff --git a/tools/test.py b/tools/test.py
index 685cbf2..157bd28 100755
--- a/tools/test.py
+++ b/tools/test.py
@@ -171,8 +171,12 @@
       help='Print the execution time of the slowest tests..',
       default=False, action='store_true')
   result.add_option(
-      '--testing-report',
-      help='Use the custom testing report output format',
+      '--with-testing-state',
+      help='Run/resume tests using testing state.',
+      default=False, action='store_true')
+  result.add_option(
+      '--reset-testing-state',
+      help='Clean the testing state and rerun tests (implies --with-testing-state).',
       default=False, action='store_true')
   result.add_option(
       '--stacktrace',
@@ -313,8 +317,11 @@
     gradle_args.append('-Pdesugar_jdk_json_dir=' + desugar_jdk_json_dir)
   if desugar_jdk_libs:
     gradle_args.append('-Pdesugar_jdk_libs=' + desugar_jdk_libs)
-  if options.testing_report:
-    gradle_args.append('-Ptesting-report')
+  if options.reset_testing_state:
+    gradle_args.append('-Ptesting-state')
+    gradle_args.append('-Preset-testing-state')
+  elif options.with_testing_state:
+    gradle_args.append('-Ptesting-state')
 
   # Build an R8 with dependencies for bootstrapping tests before adding test sources.
   gradle_args.append('r8WithDeps')