diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 094a4c7..c2ee174 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -660,6 +660,14 @@
             new GenericSignatureRewriter(
                     appView, NamingLens.getIdentityLens(), genericContextBuilder)
                 .run(appView.appInfo().classes(), executorService);
+            assert appView.checkForTesting(
+                    () ->
+                        GenericSignatureCorrectnessHelper.createForVerification(
+                                appView,
+                                GenericSignatureContextBuilder.create(appView.appInfo().classes()))
+                            .run(appView.appInfo().classes())
+                            .isValid())
+                : "Could not validate generic signatures";
 
             // Synthesize fields for triggering class initializers.
             new ClassInitFieldSynthesizer(appViewWithLiveness).run(executorService);
@@ -739,6 +747,9 @@
       // need to build IR.
       appView.dexItemFactory().clearTypeElementsCache();
 
+      GenericSignatureContextBuilder genericContextBuilderBeforeFinalMerging =
+          GenericSignatureContextBuilder.create(appView.appInfo().classes());
+
       // Run horizontal class merging. This runs even if shrinking is disabled to ensure synthetics
       // are always merged.
       HorizontalClassMerger.createForFinalClassMerging(appView)
@@ -813,6 +824,17 @@
         options.syntheticProguardRulesConsumer.accept(synthesizedProguardRules);
       }
 
+      NamingLens prefixRewritingNamingLens =
+          PrefixRewritingNamingLens.createPrefixRewritingNamingLens(appView, namingLens);
+
+      timing.begin("MinifyKotlinMetadata");
+      new KotlinMetadataRewriter(appView, prefixRewritingNamingLens).runForR8(executorService);
+      timing.end();
+
+      new GenericSignatureRewriter(
+              appView, prefixRewritingNamingLens, genericContextBuilderBeforeFinalMerging)
+          .run(appView.appInfo().classes(), executorService);
+
       assert appView.checkForTesting(
               () ->
                   !options.isShrinking()
@@ -823,16 +845,6 @@
                           .isValid())
           : "Could not validate generic signatures";
 
-      NamingLens prefixRewritingNamingLens =
-          PrefixRewritingNamingLens.createPrefixRewritingNamingLens(appView, namingLens);
-
-      timing.begin("MinifyKotlinMetadata");
-      new KotlinMetadataRewriter(appView, prefixRewritingNamingLens).runForR8(executorService);
-      timing.end();
-
-      new GenericSignatureRewriter(appView, prefixRewritingNamingLens)
-          .run(appView.appInfo().classes(), executorService);
-
       new DesugaredLibraryKeepRuleGenerator(appView, prefixRewritingNamingLens)
           .runIfNecessary(timing);
 
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 419125d..920fbc1 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignature.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignature.java
@@ -15,6 +15,7 @@
 import com.google.common.collect.ImmutableList;
 import java.lang.reflect.GenericSignatureFormatError;
 import java.nio.CharBuffer;
+import java.util.ArrayList;
 import java.util.List;
 import java.util.function.Predicate;
 
@@ -293,6 +294,53 @@
     public ClassSignature toObjectBoundWithSameFormals(ClassTypeSignature objectBound) {
       return new ClassSignature(formalTypeParameters, objectBound, getEmptySuperInterfaces());
     }
+
+    public List<FieldTypeSignature> getGenericArgumentsToSuperType(DexType type) {
+      assert hasSignature();
+      if (superClassSignature.type == type) {
+        return superClassSignature.typeArguments;
+      }
+      for (ClassTypeSignature superInterfaceSignature : superInterfaceSignatures) {
+        if (superInterfaceSignature.type == type) {
+          return superInterfaceSignature.typeArguments;
+        }
+      }
+      return null;
+    }
+
+    public static ClassSignatureBuilder builder() {
+      return new ClassSignatureBuilder();
+    }
+
+    public static class ClassSignatureBuilder {
+
+      private List<FormalTypeParameter> formalTypeParameters = new ArrayList<>();
+      private ClassTypeSignature superClassSignature = null;
+      private List<ClassTypeSignature> superInterfaceSignatures = new ArrayList<>();
+
+      private ClassSignatureBuilder() {}
+
+      public ClassSignatureBuilder addFormalTypeParameters(List<FormalTypeParameter> formals) {
+        formalTypeParameters.addAll(formals);
+        return this;
+      }
+
+      public ClassSignatureBuilder setSuperClassSignature(ClassTypeSignature superClassSignature) {
+        this.superClassSignature = superClassSignature;
+        return this;
+      }
+
+      public ClassSignatureBuilder addInterface(ClassTypeSignature iface) {
+        superInterfaceSignatures.add(iface);
+        return this;
+      }
+
+      public ClassSignature build() {
+        ClassSignature classSignature =
+            new ClassSignature(formalTypeParameters, superClassSignature, superInterfaceSignatures);
+        return classSignature;
+      }
+    }
   }
 
   private static class InvalidClassSignature extends ClassSignature {
@@ -585,7 +633,7 @@
         return null;
       }
       List<FieldTypeSignature> rewrittenArguments =
-          visitor.visitTypeArguments(visitedType, typeArguments);
+          visitor.visitTypeArguments(type, visitedType, typeArguments);
       ClassTypeSignature rewrittenOuter = null;
       if (enclosingTypeSignature != null) {
         rewrittenOuter = visitor.visitEnclosing(enclosingTypeSignature, this);
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignatureContextBuilder.java b/src/main/java/com/android/tools/r8/graph/GenericSignatureContextBuilder.java
index 2a0636b..1b1eabf 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureContextBuilder.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureContextBuilder.java
@@ -6,8 +6,10 @@
 
 import static com.android.tools.r8.graph.GenericSignatureContextBuilder.TypeParameterContext.empty;
 
+import com.android.tools.r8.graph.GenericSignature.FieldTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.FormalTypeParameter;
 import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
+import com.android.tools.r8.utils.WorkList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
@@ -25,26 +27,26 @@
 
   private static class TypeParameterSubstitutions {
 
-    private final Map<String, DexType> parametersWithBounds;
+    private final Map<String, FieldTypeSignature> parametersWithBounds;
 
-    private TypeParameterSubstitutions(Map<String, DexType> parametersWithBounds) {
+    private TypeParameterSubstitutions(Map<String, FieldTypeSignature> parametersWithBounds) {
       this.parametersWithBounds = parametersWithBounds;
     }
 
     private static TypeParameterSubstitutions create(List<FormalTypeParameter> formals) {
-      Map<String, DexType> map = new IdentityHashMap<>();
+      Map<String, FieldTypeSignature> map = new HashMap<>();
       formals.forEach(
           formal -> {
-            DexType bound = null;
             if (formal.getClassBound() != null
                 && formal.getClassBound().hasSignature()
                 && formal.getClassBound().isClassTypeSignature()) {
-              bound = formal.getClassBound().asClassTypeSignature().type;
+              map.put(formal.getName(), formal.getClassBound());
             } else if (!formal.getInterfaceBounds().isEmpty()
                 && formal.getInterfaceBounds().get(0).isClassTypeSignature()) {
-              bound = formal.getInterfaceBounds().get(0).asClassTypeSignature().type;
+              map.put(formal.getName(), formal.getInterfaceBounds().get(0));
+            } else {
+              map.put(formal.getName(), null);
             }
-            map.put(formal.getName(), bound);
           });
       return new TypeParameterSubstitutions(map);
     }
@@ -55,11 +57,11 @@
     private static final TypeParameterContext EMPTY =
         new TypeParameterContext(Collections.emptyMap(), Collections.emptySet());
 
-    private final Map<String, DexType> prunedParametersWithBounds;
+    private final Map<String, FieldTypeSignature> prunedParametersWithBounds;
     private final Set<String> liveParameters;
 
     private TypeParameterContext(
-        Map<String, DexType> prunedParametersWithBounds, Set<String> liveParameters) {
+        Map<String, FieldTypeSignature> prunedParametersWithBounds, Set<String> liveParameters) {
       this.prunedParametersWithBounds = prunedParametersWithBounds;
       this.liveParameters = liveParameters;
     }
@@ -81,7 +83,7 @@
       return liveParameters.contains(parameterName);
     }
 
-    public DexType getPrunedSubstitution(String parameterName) {
+    public FieldTypeSignature getPrunedSubstitution(String parameterName) {
       assert !isLiveParameter(parameterName);
       return prunedParametersWithBounds.get(parameterName);
     }
@@ -93,7 +95,7 @@
       HashSet<String> newLiveParameters = new HashSet<>();
       newLiveParameters.addAll(liveParameters);
       newLiveParameters.addAll(typeParameters);
-      HashMap<String, DexType> newPruned = new HashMap<>();
+      HashMap<String, FieldTypeSignature> newPruned = new HashMap<>();
       prunedParametersWithBounds.forEach(
           (name, type) -> {
             if (!typeParameters.contains(name)) {
@@ -103,11 +105,12 @@
       return new TypeParameterContext(newPruned, newLiveParameters);
     }
 
-    public TypeParameterContext addPrunedSubstitutions(Map<String, DexType> substitutions) {
+    public TypeParameterContext addPrunedSubstitutions(
+        Map<String, FieldTypeSignature> substitutions) {
       if (substitutions.isEmpty()) {
         return this;
       }
-      HashMap<String, DexType> newPruned = new HashMap<>();
+      HashMap<String, FieldTypeSignature> newPruned = new HashMap<>();
       newPruned.putAll(prunedParametersWithBounds);
       newPruned.putAll(substitutions);
       HashSet<String> newLiveParameters = new HashSet<>();
@@ -121,38 +124,6 @@
     }
   }
 
-  public static class AlwaysLiveTypeParameterContext extends TypeParameterContext {
-
-    private AlwaysLiveTypeParameterContext() {
-      super(Collections.emptyMap(), Collections.emptySet());
-    }
-
-    public static AlwaysLiveTypeParameterContext create() {
-      return new AlwaysLiveTypeParameterContext();
-    }
-
-    @Override
-    public boolean isLiveParameter(String parameterName) {
-      return true;
-    }
-
-    @Override
-    public DexType getPrunedSubstitution(String parameterName) {
-      assert false;
-      return null;
-    }
-
-    @Override
-    public TypeParameterContext addLiveParameters(Collection<String> typeParameters) {
-      return this;
-    }
-
-    @Override
-    public TypeParameterContext addPrunedSubstitutions(Map<String, DexType> substitutions) {
-      return this;
-    }
-  }
-
   private GenericSignatureContextBuilder(
       Map<DexReference, TypeParameterSubstitutions> formalsInfo,
       Map<DexReference, DexReference> enclosingInfo) {
@@ -160,7 +131,7 @@
     this.enclosingInfo = enclosingInfo;
   }
 
-  public static GenericSignatureContextBuilder create(List<DexProgramClass> programClasses) {
+  public static GenericSignatureContextBuilder create(Collection<DexProgramClass> programClasses) {
     Map<DexReference, TypeParameterSubstitutions> formalsInfo = new IdentityHashMap<>();
     Map<DexReference, DexReference> enclosingInfo = new IdentityHashMap<>();
     programClasses.forEach(
@@ -201,6 +172,24 @@
     return new GenericSignatureContextBuilder(formalsInfo, enclosingInfo);
   }
 
+  public static GenericSignatureContextBuilder createForSingleClass(
+      AppView<?> appView, DexProgramClass clazz) {
+    WorkList<DexProgramClass> workList = WorkList.newIdentityWorkList(clazz);
+    while (workList.hasNext()) {
+      DexProgramClass current = workList.next();
+      DexClass outer = null;
+      if (current.getEnclosingMethodAttribute() != null) {
+        outer = appView.definitionFor(current.getEnclosingMethodAttribute().getEnclosingType());
+      } else if (current.getInnerClassAttributeForThisClass() != null) {
+        outer = appView.definitionFor(current.getInnerClassAttributeForThisClass().getOuter());
+      }
+      if (outer != null && outer.isProgramClass()) {
+        workList.addIfNotSeen(outer.asProgramClass());
+      }
+    }
+    return create(workList.getSeenSet());
+  }
+
   public TypeParameterContext computeTypeParameterContext(
       AppView<?> appView, DexReference reference, Predicate<DexType> wasPruned) {
     assert !wasPruned.test(reference.getContextType()) : "Building context for pruned type";
@@ -218,27 +207,42 @@
     DexType contextType = reference.getContextType();
     // TODO(b/187035453): We should visit generic signatures in the enqueuer.
     DexClass clazz = appView.appInfo().definitionForWithoutExistenceAssert(contextType);
-    boolean prunedHere = seenPruned || clazz == null;
-    if (appView.hasLiveness()
-        && appView.withLiveness().appInfo().getMissingClasses().contains(contextType)) {
-      prunedHere = seenPruned;
-    }
+    boolean prunedHere = seenPruned;
+    // If the class cannot be looked up and it is not missing it was pruned here.
+    prunedHere |=
+        clazz == null
+            && appView.hasLiveness()
+            && !appView.withLiveness().appInfo().getMissingClasses().contains(contextType);
     // Lookup the formals in the enclosing context.
+    TypeParameterSubstitutions formalsInfo = this.formalsInfo.get(contextType);
+    // If formals has been pruned then the context is also pruned here.
+    prunedHere |=
+        clazz != null
+            && formalsInfo != null
+            && !formalsInfo.parametersWithBounds.isEmpty()
+            && clazz.getClassSignature().getFormalTypeParameters().isEmpty();
+    DexReference enclosingReference = enclosingInfo.get(contextType);
     TypeParameterContext typeParameterContext =
         computeTypeParameterContext(
                 appView,
-                enclosingInfo.get(contextType),
+                enclosingReference,
                 wasPruned,
                 prunedHere
-                    || hasPrunedRelationship(
-                        appView, enclosingInfo.get(contextType), contextType, wasPruned))
+                    || hasPrunedRelationship(appView, enclosingReference, contextType, wasPruned))
             // Add formals for the context
-            .combine(formalsInfo.get(contextType), prunedHere);
+            .combine(formalsInfo, prunedHere);
     if (!reference.isDexMethod()) {
       return typeParameterContext;
     }
-    prunedHere = prunedHere || clazz == null || clazz.lookupMethod(reference.asDexMethod()) == null;
-    return typeParameterContext.combine(formalsInfo.get(reference), prunedHere);
+    TypeParameterSubstitutions methodFormals = this.formalsInfo.get(reference);
+    if (clazz != null && !prunedHere) {
+      DexEncodedMethod method = clazz.lookupMethod(reference.asDexMethod());
+      prunedHere =
+          method == null
+              || (!methodFormals.parametersWithBounds.isEmpty()
+                  && method.getGenericSignature().getFormalTypeParameters().isEmpty());
+    }
+    return typeParameterContext.combine(methodFormals, prunedHere);
   }
 
   public boolean hasPrunedRelationship(
@@ -257,15 +261,9 @@
     }
     // TODO(b/187035453): We should visit generic signatures in the enqueuer.
     DexClass enclosingClass =
-        appView
-            .appInfo()
-            .definitionForWithoutExistenceAssert(
-                appView.graphLens().lookupClassType(enclosingReference.getContextType()));
+        appView.appInfo().definitionForWithoutExistenceAssert(enclosingReference.getContextType());
     DexClass enclosedClass =
-        appView
-            .appInfo()
-            .definitionForWithoutExistenceAssert(
-                appView.graphLens().lookupClassType(enclosedClassType));
+        appView.appInfo().definitionForWithoutExistenceAssert(enclosedClassType);
     if (enclosingClass == null || enclosedClass == null) {
       return true;
     }
@@ -279,12 +277,12 @@
     }
   }
 
-  public boolean hasGenericTypeVariables(
+  public static boolean hasGenericTypeVariables(
       AppView<?> appView, DexType type, Predicate<DexType> wasPruned) {
     if (wasPruned.test(type)) {
       return false;
     }
-    DexClass clazz = appView.definitionFor(appView.graphLens().lookupClassType(type));
+    DexClass clazz = appView.definitionFor(type);
     if (clazz == null || clazz.isNotProgramClass() || clazz.getClassSignature().isInvalid()) {
       return true;
     }
diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignatureCorrectnessHelper.java b/src/main/java/com/android/tools/r8/graph/GenericSignatureCorrectnessHelper.java
index 03f4259..1946512 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureCorrectnessHelper.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureCorrectnessHelper.java
@@ -234,8 +234,7 @@
       if (context.superType == appView.dexItemFactory().objectType
           && classSignature.superClassSignature().hasNoSignature()) {
         // We represent no signature as object.
-      } else if (context.superType
-          != appView.graphLens().lookupClassType(classSignature.superClassSignature().type())) {
+      } else if (context.superType != classSignature.superClassSignature().type()) {
         assert mode.doNotVerify() : "Super type inconsistency in generic signature";
         return INVALID_SUPER_TYPE;
       }
@@ -393,10 +392,7 @@
         }
       }
       // TODO(b/187035453): We should visit generic signatures in the enqueuer.
-      DexClass clazz =
-          appView
-              .appInfo()
-              .definitionForWithoutExistenceAssert(appView.graphLens().lookupClassType(type));
+      DexClass clazz = appView.appInfo().definitionForWithoutExistenceAssert(type);
       if (clazz == null) {
         // We do not know if the application of arguments works or not.
         return VALID;
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 56a6496..12ca041 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignaturePartialTypeArgumentApplier.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignaturePartialTypeArgumentApplier.java
@@ -26,6 +26,8 @@
   private final BiPredicate<DexType, DexType> enclosingPruned;
   private final Predicate<DexType> hasGenericTypeParameters;
   private final AppView<?> appView;
+  private final ClassTypeSignature objectArgument;
+  private boolean makeAllTypeArgumentsObject = false;
 
   private GenericSignaturePartialTypeArgumentApplier(
       AppView<?> appView,
@@ -36,6 +38,9 @@
     this.typeParameterContext = typeParameterContext;
     this.enclosingPruned = enclosingPruned;
     this.hasGenericTypeParameters = hasGenericTypeParameters;
+    objectArgument =
+        new ClassTypeSignature(appView.dexItemFactory().objectType)
+            .asArgument(WildcardIndicator.NONE);
   }
 
   public static GenericSignaturePartialTypeArgumentApplier build(
@@ -78,6 +83,10 @@
 
   @Override
   public DexType visitType(DexType type) {
+    // It is important that the type is not looked up in the applier. The type-parameter context is
+    // a mapping from fully applied -> old references, which may seem a bit odd, but that is simply
+    // because we do not rewrite the signatures in lock step with rewriting the app.
+    // The actual lookup will be performed in the GenericSignatureTypeRewriter.
     return type;
   }
 
@@ -117,8 +126,12 @@
 
   @Override
   public List<FieldTypeSignature> visitTypeArguments(
-      DexType type, List<FieldTypeSignature> typeArguments) {
-    if (typeArguments.isEmpty() || !hasGenericTypeParameters.test(type)) {
+      DexType originalType, DexType lookedUpType, List<FieldTypeSignature> typeArguments) {
+    assert originalType == lookedUpType;
+    if (typeArguments.isEmpty()) {
+      return typeArguments;
+    }
+    if (!hasGenericTypeParameters.test(appView.graphLens().lookupType(originalType))) {
       return getEmptyTypeArguments();
     }
     return ListUtils.mapOrElse(typeArguments, this::visitFieldTypeSignature);
@@ -145,7 +158,9 @@
   @Override
   public ClassTypeSignature visitEnclosing(
       ClassTypeSignature enclosingSignature, ClassTypeSignature enclosedSignature) {
-    if (enclosingPruned.test(enclosingSignature.type(), enclosedSignature.type())) {
+    DexType enclosingType = appView.graphLens().lookupType(enclosingSignature.type());
+    DexType enclosedType = appView.graphLens().lookupType(enclosedSignature.type());
+    if (enclosingPruned.test(enclosingType, enclosedType)) {
       return null;
     } else {
       return enclosingSignature.visit(this);
@@ -208,15 +223,26 @@
       return fieldSignature.asArrayTypeSignature().visit(this);
     } else {
       assert fieldSignature.isTypeVariableSignature();
-      String typeVariableName = fieldSignature.asTypeVariableSignature().typeVariable();
-      if (!typeParameterContext.isLiveParameter(typeVariableName)) {
-        DexType substitution = typeParameterContext.getPrunedSubstitution(typeVariableName);
-        if (substitution == null) {
-          substitution = appView.dexItemFactory().objectType;
-        }
-        return new ClassTypeSignature(substitution).asArgument(WildcardIndicator.NONE);
+      // TODO(b/b/191871201): If we track where type-variables are introduced, we can move this
+      //  past typeParameterContext.isLiveParameter(typeVariableName) and get more precision.
+      if (makeAllTypeArgumentsObject) {
+        return objectArgument;
       }
-      return fieldSignature;
+      String typeVariableName = fieldSignature.asTypeVariableSignature().typeVariable();
+      if (typeParameterContext.isLiveParameter(typeVariableName)) {
+        return fieldSignature;
+      }
+      FieldTypeSignature substitution =
+          typeParameterContext.getPrunedSubstitution(typeVariableName);
+      if (substitution == null) {
+        return objectArgument;
+      }
+      makeAllTypeArgumentsObject = true;
+      substitution = visitFieldTypeSignature(substitution);
+      makeAllTypeArgumentsObject = false;
+      return substitution.isArgument()
+          ? substitution
+          : substitution.asArgument(WildcardIndicator.NONE);
     }
   }
 }
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 b111c57..9d54705 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignaturePrinter.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignaturePrinter.java
@@ -146,7 +146,7 @@
 
   @Override
   public List<FieldTypeSignature> visitTypeArguments(
-      DexType type, List<FieldTypeSignature> typeArguments) {
+      DexType originalType, DexType lookedUpType, List<FieldTypeSignature> typeArguments) {
     if (typeArguments.isEmpty()) {
       return typeArguments;
     }
@@ -207,7 +207,7 @@
         }
         sb.append(".").append(innerClassName);
       }
-      visitTypeArguments(null, classTypeSignature.typeArguments);
+      visitTypeArguments(null, 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 332aa8d..7f224bb 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeRewriter.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeRewriter.java
@@ -29,26 +29,31 @@
   private final DexProgramClass context;
 
   private final ClassTypeSignature objectTypeSignature;
+  private final Predicate<DexType> hasGenericTypeVariables;
 
-  public GenericSignatureTypeRewriter(AppView<?> appView, DexProgramClass context) {
+  public GenericSignatureTypeRewriter(
+      AppView<?> appView, DexProgramClass context, Predicate<DexType> hasGenericTypeVariables) {
     this(
         appView.dexItemFactory(),
         appView.appInfo().hasLiveness()
             ? appView.appInfo().withLiveness()::wasPruned
             : alwaysFalse(),
         appView.graphLens()::lookupType,
-        context);
+        context,
+        hasGenericTypeVariables);
   }
 
   public GenericSignatureTypeRewriter(
       DexItemFactory factory,
       Predicate<DexType> wasPruned,
       Function<DexType, DexType> lookupType,
-      DexProgramClass context) {
+      DexProgramClass context,
+      Predicate<DexType> hasGenericTypeVariables) {
     this.factory = factory;
     this.wasPruned = wasPruned;
     this.lookupType = lookupType;
     this.context = context;
+    this.hasGenericTypeVariables = hasGenericTypeVariables;
     objectTypeSignature = new ClassTypeSignature(factory.objectType, getEmptyTypeArguments());
   }
 
@@ -138,10 +143,13 @@
 
     @Override
     public ClassTypeSignature visitSuperClass(ClassTypeSignature classTypeSignature) {
+      if (context.superType == factory.objectType) {
+        return classTypeSignature.type == factory.objectType
+            ? classTypeSignature
+            : objectTypeSignature;
+      }
       ClassTypeSignature rewritten = classTypeSignature.visit(this);
-      return rewritten == null || rewritten.type() == context.type
-          ? objectTypeSignature
-          : rewritten;
+      return rewritten == null ? objectTypeSignature : rewritten;
     }
 
     @Override
@@ -239,10 +247,17 @@
 
     @Override
     public List<FieldTypeSignature> visitTypeArguments(
-        DexType type, List<FieldTypeSignature> typeArguments) {
+        DexType originalType, DexType lookedUpType, List<FieldTypeSignature> typeArguments) {
+      assert lookedUpType != null;
       if (typeArguments.isEmpty()) {
         return typeArguments;
       }
+      // If the original type has been pruned it must be because the old type has been merged into
+      // the looked up type. We can therefore not guarantee the type arguments to be consistent and
+      // have to remove them.
+      if (wasPruned.test(originalType) || !hasGenericTypeVariables.test(lookedUpType)) {
+        return getEmptyTypeArguments();
+      }
       return ListUtils.mapOrElse(
           typeArguments,
           fieldTypeSignature -> {
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 59cd879..a619129 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeVisitor.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureTypeVisitor.java
@@ -144,7 +144,7 @@
 
   @Override
   public List<FieldTypeSignature> visitTypeArguments(
-      DexType type, List<FieldTypeSignature> typeArguments) {
+      DexType originalType, DexType lookedUpType, 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 b321ad1..37b3cbe 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignatureVisitor.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignatureVisitor.java
@@ -84,7 +84,7 @@
   }
 
   default List<FieldTypeSignature> visitTypeArguments(
-      DexType type, List<FieldTypeSignature> typeArguments) {
+      DexType originalType, DexType lookedUpType, 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 db0178c..7483522 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java
@@ -24,6 +24,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.graph.ProgramMember;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.horizontalclassmerging.HorizontalClassMerger.Mode;
 import com.android.tools.r8.horizontalclassmerging.code.ClassInitializerMerger;
@@ -325,6 +326,8 @@
     mergeInterfaces();
     mergeFields();
     mergeMethods(syntheticArgumentClass, syntheticInitializerConverterBuilder);
+    group.getTarget().clearClassSignature();
+    group.getTarget().forEachProgramMember(ProgramMember::clearGenericSignature);
   }
 
   public static class Builder {
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 16b6508..b719c89 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
@@ -13,6 +13,7 @@
 import com.android.tools.r8.graph.GenericSignaturePartialTypeArgumentApplier;
 import com.android.tools.r8.graph.GenericSignatureTypeRewriter;
 import com.android.tools.r8.naming.NamingLens;
+import com.android.tools.r8.utils.IterableUtils;
 import com.android.tools.r8.utils.ThreadUtils;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
@@ -50,13 +51,15 @@
     // ClassNameMinifier.
     Predicate<DexType> wasPruned =
         appView.hasLiveness() ? appView.withLiveness().appInfo()::wasPruned : alwaysFalse();
+    Predicate<DexType> hasGenericTypeVariables =
+        type -> GenericSignatureContextBuilder.hasGenericTypeVariables(appView, type, wasPruned);
     BiPredicate<DexType, DexType> hasPrunedRelationship =
         (enclosing, enclosed) ->
             contextBuilder.hasPrunedRelationship(appView, enclosing, enclosed, wasPruned);
-    Predicate<DexType> hasGenericTypeVariables =
-        type -> contextBuilder.hasGenericTypeVariables(appView, type, wasPruned);
     ThreadUtils.processItems(
-        classes,
+        // Final merging of classes can introduce pruned types that still exists in classes, we
+        // therefore prune them from work here.
+        IterableUtils.filter(classes, clazz -> !wasPruned.test(clazz.getType())),
         clazz -> {
           GenericSignaturePartialTypeArgumentApplier classArgumentApplier =
               contextBuilder != null
@@ -68,7 +71,7 @@
                       hasGenericTypeVariables)
                   : null;
           GenericSignatureTypeRewriter genericSignatureTypeRewriter =
-              new GenericSignatureTypeRewriter(appView, clazz);
+              new GenericSignatureTypeRewriter(appView, clazz, hasGenericTypeVariables);
           clazz.setClassSignature(
               genericSignatureTypeRewriter.rewrite(
                   classArgumentApplier != null
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index 77b119d..061eb02 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -29,7 +29,16 @@
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DexTypeList;
+import com.android.tools.r8.graph.GenericSignature.ClassSignature;
+import com.android.tools.r8.graph.GenericSignature.ClassSignature.ClassSignatureBuilder;
+import com.android.tools.r8.graph.GenericSignature.ClassTypeSignature;
+import com.android.tools.r8.graph.GenericSignature.FieldTypeSignature;
+import com.android.tools.r8.graph.GenericSignature.FormalTypeParameter;
 import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
+import com.android.tools.r8.graph.GenericSignatureContextBuilder;
+import com.android.tools.r8.graph.GenericSignatureContextBuilder.TypeParameterContext;
+import com.android.tools.r8.graph.GenericSignatureCorrectnessHelper;
+import com.android.tools.r8.graph.GenericSignaturePartialTypeArgumentApplier;
 import com.android.tools.r8.graph.GraphLens;
 import com.android.tools.r8.graph.GraphLens.MethodLookupResult;
 import com.android.tools.r8.graph.GraphLens.NonIdentityGraphLens;
@@ -56,6 +65,7 @@
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.Box;
+import com.android.tools.r8.utils.CollectionUtils;
 import com.android.tools.r8.utils.FieldSignatureEquivalence;
 import com.android.tools.r8.utils.MethodSignatureEquivalence;
 import com.android.tools.r8.utils.OptionalBool;
@@ -1079,6 +1089,9 @@
         return false;
       }
 
+      // Rewrite generic signatures before we merge fields.
+      rewriteGenericSignatures(target, source, directMethods.values(), virtualMethods.values());
+
       // Step 2: Merge fields
       Set<DexString> existingFieldNames = new HashSet<>();
       for (DexEncodedField field : target.fields()) {
@@ -1139,9 +1152,148 @@
       // Step 4: Record merging.
       mergedClasses.put(source.type, target.type);
       assert !abortMerge;
+      assert GenericSignatureCorrectnessHelper.createForVerification(
+              appView, GenericSignatureContextBuilder.createForSingleClass(appView, target))
+          .evaluateSignaturesForClass(target)
+          .isValid();
       return true;
     }
 
+    /**
+     * The rewriting of generic signatures is pretty simple, but require some bookkeeping. We take
+     * the arguments to the base type:
+     *
+     * <pre>
+     *   class Sub<X> extends Base<X, String>
+     * </pre>
+     *
+     * for
+     *
+     * <pre>
+     *   class Base<T,R> extends OtherBase<T> implements I<R> {
+     *     T t() { ... };
+     *   }
+     * </pre>
+     *
+     * and substitute T -> X and R -> String
+     */
+    private void rewriteGenericSignatures(
+        DexProgramClass target,
+        DexProgramClass source,
+        Collection<DexEncodedMethod> directMethods,
+        Collection<DexEncodedMethod> virtualMethods) {
+      ClassSignature targetSignature = target.getClassSignature();
+      if (targetSignature.hasNoSignature()) {
+        // Null out all source signatures that is moved, but do not clear out the class since this
+        // could be referred to by other generic signatures.
+        // TODO(b/147504070): If merging classes with enclosing/innerclasses, this needs to be
+        //  reconsidered.
+        directMethods.forEach(DexEncodedMethod::clearGenericSignature);
+        virtualMethods.forEach(DexEncodedMethod::clearGenericSignature);
+        source.fields().forEach(DexEncodedMember::clearGenericSignature);
+        return;
+      }
+      GenericSignaturePartialTypeArgumentApplier classApplier =
+          getGenericSignatureArgumentApplier(target, source);
+      if (classApplier == null) {
+        target.clearClassSignature();
+        target.members().forEach(DexEncodedMember::clearGenericSignature);
+        return;
+      }
+      // We could generate a substitution map.
+      ClassSignature rewrittenSource = classApplier.visitClassSignature(source.getClassSignature());
+      // The variables in the class signature is now rewritten to use the targets argument.
+      ClassSignatureBuilder builder = ClassSignature.builder();
+      builder.addFormalTypeParameters(targetSignature.getFormalTypeParameters());
+      if (!source.isInterface()) {
+        if (rewrittenSource.hasSignature()) {
+          builder.setSuperClassSignature(rewrittenSource.superClassSignature());
+        } else {
+          builder.setSuperClassSignature(new ClassTypeSignature(source.superType));
+        }
+      } else {
+        builder.setSuperClassSignature(targetSignature.superClassSignature());
+      }
+      // Compute the seen set for interfaces to add. This is similar to the merging of interfaces
+      // but allow us to maintain the type arguments.
+      Set<DexType> seenInterfaces = new HashSet<>();
+      if (source.isInterface()) {
+        seenInterfaces.add(source.type);
+      }
+      for (ClassTypeSignature iFace : targetSignature.superInterfaceSignatures()) {
+        if (seenInterfaces.add(iFace.type())) {
+          builder.addInterface(iFace);
+        }
+      }
+      if (rewrittenSource.hasSignature()) {
+        for (ClassTypeSignature iFace : rewrittenSource.superInterfaceSignatures()) {
+          if (!seenInterfaces.contains(iFace.type())) {
+            builder.addInterface(iFace);
+          }
+        }
+      } else {
+        // Synthesize raw uses of interfaces to align with the actual class
+        for (DexType iFace : source.interfaces) {
+          if (!seenInterfaces.contains(iFace)) {
+            builder.addInterface(new ClassTypeSignature(iFace));
+          }
+        }
+      }
+      target.setClassSignature(builder.build());
+
+      // Go through all type-variable references for members and update them.
+      CollectionUtils.forEach(
+          method -> {
+            MethodTypeSignature methodSignature = method.getGenericSignature();
+            if (methodSignature.hasNoSignature()) {
+              return;
+            }
+            method.setGenericSignature(
+                classApplier
+                    .buildForMethod(methodSignature.getFormalTypeParameters())
+                    .visitMethodSignature(methodSignature));
+          },
+          directMethods,
+          virtualMethods);
+
+      source.forEachField(
+          field -> {
+            if (field.getGenericSignature().hasNoSignature()) {
+              return;
+            }
+            field.setGenericSignature(
+                classApplier.visitFieldTypeSignature(field.getGenericSignature()));
+          });
+    }
+
+    private GenericSignaturePartialTypeArgumentApplier getGenericSignatureArgumentApplier(
+        DexProgramClass target, DexProgramClass source) {
+      assert target.getClassSignature().hasSignature();
+      // We can assert proper structure below because the generic signature validator has run
+      // before and pruned invalid signatures.
+      List<FieldTypeSignature> genericArgumentsToSuperType =
+          target.getClassSignature().getGenericArgumentsToSuperType(source.type);
+      if (genericArgumentsToSuperType == null) {
+        assert false : "Type should be present in generic signature";
+        return null;
+      }
+      List<FormalTypeParameter> formals = source.getClassSignature().getFormalTypeParameters();
+      if (genericArgumentsToSuperType.size() != formals.size()) {
+        assert false : "Invalid argument count to formals";
+        return null;
+      }
+      Map<String, FieldTypeSignature> substitutionMap = new HashMap<>();
+      for (int i = 0; i < formals.size(); i++) {
+        // It is OK to override a generic type variable so we just use put.
+        substitutionMap.put(formals.get(i).getName(), genericArgumentsToSuperType.get(i));
+      }
+      return GenericSignaturePartialTypeArgumentApplier.build(
+          appView,
+          TypeParameterContext.empty().addPrunedSubstitutions(substitutionMap),
+          (type1, type2) -> true,
+          type -> true);
+    }
+
     private boolean restoreDebuggingState(Stream<DexEncodedMethod> toBeDiscarded) {
       toBeDiscarded.forEach(
           method -> {
diff --git a/src/main/java/com/android/tools/r8/utils/CollectionUtils.java b/src/main/java/com/android/tools/r8/utils/CollectionUtils.java
index 6584f77..91b0638 100644
--- a/src/main/java/com/android/tools/r8/utils/CollectionUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/CollectionUtils.java
@@ -7,12 +7,21 @@
 import com.google.common.collect.ImmutableSet;
 import java.util.Collection;
 import java.util.Set;
+import java.util.function.Consumer;
 
 public class CollectionUtils {
+
   public static <T> Set<T> mergeSets(Collection<T> first, Collection<T> second) {
     ImmutableSet.Builder<T> builder = ImmutableSet.builder();
     builder.addAll(first);
     builder.addAll(second);
     return builder.build();
   }
+
+  @SafeVarargs
+  public static <T> void forEach(Consumer<T> consumer, Collection<T>... collections) {
+    for (Collection<T> collection : collections) {
+      collection.forEach(consumer);
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/utils/ListUtils.java b/src/main/java/com/android/tools/r8/utils/ListUtils.java
index 5781f91..91bfbe6 100644
--- a/src/main/java/com/android/tools/r8/utils/ListUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ListUtils.java
@@ -48,6 +48,17 @@
     return result != null ? result : defaultValue;
   }
 
+  public static <T> List<T> filter(List<T> list, Predicate<? super T> predicate) {
+    ArrayList<T> filtered = new ArrayList<>(list.size());
+    list.forEach(
+        t -> {
+          if (predicate.test(t)) {
+            filtered.add(t);
+          }
+        });
+    return filtered;
+  }
+
   public static <T> T first(List<T> list) {
     return list.get(0);
   }
diff --git a/src/main/java/com/android/tools/r8/utils/MapUtils.java b/src/main/java/com/android/tools/r8/utils/MapUtils.java
index ba04d86..2460a3c 100644
--- a/src/main/java/com/android/tools/r8/utils/MapUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/MapUtils.java
@@ -47,21 +47,21 @@
         ",", map.entrySet(), entry -> entry.getKey() + ":" + entry.getValue(), BraceType.TUBORG);
   }
 
-  public static <K, V> Map<K, V> transform(
-      Map<K, V> map,
-      IntFunction<Map<K, V>> factory,
-      Function<K, K> keyMapping,
-      Function<V, V> valueMapping,
-      BiFunction<V, V, V> valueMerger) {
-    Map<K, V> result = factory.apply(map.size());
+  public static <K1, V1, K2, V2> Map<K2, V2> transform(
+      Map<K1, V1> map,
+      IntFunction<Map<K2, V2>> factory,
+      Function<K1, K2> keyMapping,
+      Function<V1, V2> valueMapping,
+      BiFunction<V2, V2, V2> valueMerger) {
+    Map<K2, V2> result = factory.apply(map.size());
     map.forEach(
         (key, value) -> {
-          K newKey = keyMapping.apply(key);
+          K2 newKey = keyMapping.apply(key);
           if (newKey == null) {
             return;
           }
-          V newValue = valueMapping.apply(value);
-          V existingValue = result.put(newKey, newValue);
+          V2 newValue = valueMapping.apply(value);
+          V2 existingValue = result.put(newKey, newValue);
           if (existingValue != null) {
             result.put(newKey, valueMerger.apply(existingValue, newValue));
           }
diff --git a/src/test/java/com/android/tools/r8/graph/genericsignature/ClassSignatureTest.java b/src/test/java/com/android/tools/r8/graph/genericsignature/ClassSignatureTest.java
index 75306f7..dd835a2 100644
--- a/src/test/java/com/android/tools/r8/graph/genericsignature/ClassSignatureTest.java
+++ b/src/test/java/com/android/tools/r8/graph/genericsignature/ClassSignatureTest.java
@@ -6,6 +6,7 @@
 
 import static com.android.tools.r8.DiagnosticsMatcher.diagnosticMessage;
 import static com.google.common.base.Predicates.alwaysFalse;
+import static com.google.common.base.Predicates.alwaysTrue;
 import static org.hamcrest.CoreMatchers.containsString;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertNotNull;
@@ -179,7 +180,8 @@
             factory,
             dexType -> dexType.toDescriptorString().equals("Lj$/util/Spliterator$OfPrimitive;"),
             Function.identity(),
-            null);
+            null,
+            alwaysTrue());
     MethodTypeSignature rewritten = rewriter.rewrite(parsedMethodSignature);
     assertNotNull(rewritten);
     assertTrue(rewritten.hasSignature());
diff --git a/src/test/java/com/android/tools/r8/graph/genericsignature/FieldSignatureTest.java b/src/test/java/com/android/tools/r8/graph/genericsignature/FieldSignatureTest.java
index c17ea6b..aafeadf 100644
--- a/src/test/java/com/android/tools/r8/graph/genericsignature/FieldSignatureTest.java
+++ b/src/test/java/com/android/tools/r8/graph/genericsignature/FieldSignatureTest.java
@@ -122,7 +122,8 @@
             "A", "Lfoo/bar/Baz;", Origin.unknown(), factory, new Reporter());
     assertTrue(parsed.hasSignature());
     GenericSignatureTypeRewriter rewriter =
-        new GenericSignatureTypeRewriter(factory, alwaysTrue(), Function.identity(), null);
+        new GenericSignatureTypeRewriter(
+            factory, alwaysTrue(), Function.identity(), null, alwaysTrue());
     FieldTypeSignature rewrittenType = rewriter.rewrite(parsed);
     assertNotNull(rewrittenType);
     assertTrue(rewrittenType.hasNoSignature());
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
index b091f5e..fe4a189 100644
--- a/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureKeepAttributesTest.java
+++ b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureKeepAttributesTest.java
@@ -111,7 +111,11 @@
       assertEquals("(TO;TM;)TI;", testMethod.getFinalSignatureAttribute());
     } else {
       assertEquals(
-          "(" + descriptor(Supplier.class) + descriptor(Predicate.class) + ")TI;",
+          "(L"
+              + binaryName(Supplier.class)
+              + "<*>;L"
+              + binaryName(Predicate.class)
+              + "<Ljava/lang/Object;>;)TI;",
           testMethod.getFinalSignatureAttribute());
     }
   }
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 177ea63..f412cdf 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
@@ -9,6 +9,7 @@
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assume.assumeTrue;
 
+import com.android.tools.r8.R8TestRunResult;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.graph.genericsignature.testclasses.Foo;
@@ -29,68 +30,73 @@
 @RunWith(Parameterized.class)
 public class GenericSignatureKeepReferencesPruneTest extends TestBase {
 
-  private final String[] EXPECTED =
-      new String[] {
-        Foo.class.getTypeName() + "<java.lang.String>",
-        I.class.getTypeName()
-            + "<java.lang.Integer, "
-            + Foo.class.getTypeName()
-            + "<java.lang.Integer>>",
-        I.class.getTypeName()
-            + "<java.lang.String, "
-            + Foo.class.getTypeName()
-            + "<java.lang.String>>",
-        "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;
+  private final boolean minify;
 
-  @Parameters(name = "{0}, isCompat: {1}")
+  @Parameters(name = "{0}, isCompat: {1}, minify: {2}")
   public static List<Object[]> data() {
     return buildParameters(
-        getTestParameters().withAllRuntimesAndApiLevels().build(), BooleanUtils.values());
+        getTestParameters().withAllRuntimesAndApiLevels().build(),
+        BooleanUtils.values(),
+        BooleanUtils.values());
   }
 
-  public GenericSignatureKeepReferencesPruneTest(TestParameters parameters, boolean isCompat) {
+  public GenericSignatureKeepReferencesPruneTest(
+      TestParameters parameters, boolean isCompat, boolean minify) {
     this.parameters = parameters;
     this.isCompat = isCompat;
+    this.minify = minify;
   }
 
   @Test
   public void testJvm() throws Exception {
     assumeTrue(parameters.isCfRuntime());
+    assumeTrue(isCompat);
+    assumeTrue(!minify);
     testForJvm()
         .addProgramClasses(I.class, Foo.class, J.class, K.class, L.class)
         .addProgramClassesAndInnerClasses(Main.class)
         .run(parameters.getRuntime(), Main.class)
-        .assertSuccessWithOutputLines(EXPECTED);
+        .assertSuccessWithOutputLines(getExpected(Foo.class.getTypeName(), I.class.getTypeName()));
   }
 
   @Test
   public void testR8() throws Exception {
-    (isCompat ? testForR8Compat(parameters.getBackend()) : testForR8(parameters.getBackend()))
-        .addProgramClasses(I.class, Foo.class, J.class, K.class, L.class)
-        .addProgramClassesAndInnerClasses(Main.class)
-        .addKeepClassAndMembersRules(Main.class)
-        .setMinApi(parameters.getApiLevel())
-        .addKeepAttributeSignature()
-        .addKeepAttributeInnerClassesAndEnclosingMethod()
-        .enableInliningAnnotations()
-        .enableNeverClassInliningAnnotations()
-        .noMinification()
-        .compile()
-        .inspect(this::inspectSignatures)
-        .run(parameters.getRuntime(), Main.class)
-        .assertSuccessWithOutputLines(isCompat ? EXPECTED : EXPECTED_FULL_MODE);
+    R8TestRunResult runResult =
+        (isCompat ? testForR8Compat(parameters.getBackend()) : testForR8(parameters.getBackend()))
+            .addProgramClasses(I.class, Foo.class, J.class, K.class, L.class)
+            .addProgramClassesAndInnerClasses(Main.class)
+            .addKeepClassAndMembersRules(Main.class)
+            .setMinApi(parameters.getApiLevel())
+            .addKeepAttributeSignature()
+            .addKeepAttributeInnerClassesAndEnclosingMethod()
+            .enableInliningAnnotations()
+            .enableNeverClassInliningAnnotations()
+            .compile()
+            .inspect(this::inspectSignatures)
+            .run(parameters.getRuntime(), Main.class);
+    runResult.assertSuccess();
+    CodeInspector inspector = runResult.inspector();
+    // Foo and I exists due to the assertions in the inspection.
+    runResult.assertSuccessWithOutputLines(
+        getExpected(
+            inspector.clazz(Foo.class).getFinalName(), inspector.clazz(I.class).getFinalName()));
+  }
+
+  private String[] getExpected(String fooName, String iName) {
+    if (isCompat) {
+      return new String[] {
+        fooName + "<java.lang.String>",
+        iName + "<java.lang.Integer, " + fooName + "<java.lang.Integer>>",
+        iName + "<java.lang.String, " + fooName + "<java.lang.String>>",
+        "Hello world"
+      };
+    } else {
+      return new String[] {
+        "class " + fooName, "interface " + iName, "interface " + iName, "Hello world"
+      };
+    }
   }
 
   private void inspectSignatures(CodeInspector inspector) {
@@ -104,7 +110,7 @@
     assertEquals(
         isCompat
             ? "<T::Ljava/lang/Comparable<TT;>;R:L"
-                + binaryName(Foo.class)
+                + fooClass.getFinalBinaryName()
                 + "<TT;>;>Ljava/lang/Object;"
             : null,
         iClass.getFinalSignatureAttribute());
@@ -113,9 +119,9 @@
     assertEquals(
         isCompat
             ? "Ljava/lang/Object;L"
-                + binaryName(I.class)
+                + iClass.getFinalBinaryName()
                 + "<Ljava/lang/String;L"
-                + binaryName(Foo.class)
+                + fooClass.getFinalBinaryName()
                 + "<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 1fb82ab..a040b37 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
@@ -13,19 +13,23 @@
 import com.android.tools.r8.TestDiagnosticMessagesImpl;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.AppView;
 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.ClassTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
 import com.android.tools.r8.graph.GenericSignatureContextBuilder.TypeParameterContext;
 import com.android.tools.r8.graph.GenericSignaturePartialTypeArgumentApplier;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.BiPredicateUtils;
+import com.android.tools.r8.utils.MapUtils;
 import com.google.common.collect.ImmutableMap;
 import java.util.Collections;
+import java.util.HashMap;
 import java.util.Map;
 import java.util.Set;
 import java.util.function.BiPredicate;
@@ -113,7 +117,15 @@
         GenericSignaturePartialTypeArgumentApplier.build(
             appView,
             TypeParameterContext.empty()
-                .addPrunedSubstitutions(substitutions)
+                .addPrunedSubstitutions(
+                    MapUtils.transform(
+                        substitutions,
+                        HashMap::new,
+                        s -> s,
+                        ClassTypeSignature::new,
+                        (val1, val2) -> {
+                          throw new Unreachable("No keys should be merged");
+                        }))
                 .addLiveParameters(liveVariables),
             removedLink,
             hasFormalTypeParameters);
diff --git a/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignaturePrunedOuterRecursiveTest.java b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignaturePrunedOuterRecursiveTest.java
new file mode 100644
index 0000000..79534a4
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignaturePrunedOuterRecursiveTest.java
@@ -0,0 +1,94 @@
+// 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.utils.BooleanUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+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 GenericSignaturePrunedOuterRecursiveTest extends TestBase {
+
+  private final TestParameters parameters;
+  private final boolean isCompat;
+
+  @Parameters(name = "{0}, isCompat: {1}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        getTestParameters().withAllRuntimesAndApiLevels().build(), BooleanUtils.values());
+  }
+
+  public GenericSignaturePrunedOuterRecursiveTest(TestParameters parameters, boolean isCompat) {
+    this.parameters = parameters;
+    this.isCompat = isCompat;
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    (isCompat ? testForR8Compat(parameters.getBackend()) : testForR8(parameters.getBackend()))
+        .addInnerClasses(getClass())
+        .addKeepClassAndMembersRules(Foo.class)
+        .addKeepMainRule(Main.class)
+        .addKeepAttributeSignature()
+        .addKeepAttributeInnerClassesAndEnclosingMethod()
+        .setMinApi(parameters.getApiLevel())
+        .addOptionsModification(options -> options.horizontalClassMergerOptions().disable())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("Bar::enclosingMethod")
+        .inspect(this::checkSignatures);
+  }
+
+  public void checkSignatures(CodeInspector inspector) {
+    checkSignature(
+        inspector.clazz(Bar.class.getTypeName() + "$1"),
+        "L" + binaryName(Foo.class) + "<Ljava/util/List<Ljava/lang/Object;>;>;");
+  }
+
+  private void checkSignature(ClassSubject classSubject, String expectedSignature) {
+    assertThat(classSubject, isPresent());
+    assertEquals(isCompat ? expectedSignature : null, classSubject.getFinalSignatureAttribute());
+  }
+
+  public abstract static class Foo<T> {
+
+    void foo(T r) {
+      System.out.println("Hello World");
+    }
+  }
+
+  public static class Bar {
+
+    public static <T extends List<T>> Foo<T> enclosingMethod() {
+      return new Foo<T>() {
+        @Override
+        void foo(T r) {
+          System.out.println("Bar::enclosingMethod");
+        }
+      };
+    }
+
+    public static void run() {
+      enclosingMethod().foo(null);
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      Bar.run();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureVerticalMergeTest.java b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureVerticalMergeTest.java
index b8d02f6..a1cce6b 100644
--- a/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureVerticalMergeTest.java
+++ b/src/test/java/com/android/tools/r8/graph/genericsignature/GenericSignatureVerticalMergeTest.java
@@ -4,15 +4,17 @@
 
 package com.android.tools.r8.graph.genericsignature;
 
-import static org.hamcrest.CoreMatchers.containsString;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
 
-import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.NoVerticalClassMerging;
+import com.android.tools.r8.R8TestRunResult;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import java.lang.reflect.Type;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -33,26 +35,32 @@
     this.parameters = parameters;
   }
 
-  @Test(expected = CompilationFailedException.class)
+  @Test
   public void testR8() throws Exception {
-    testForR8Compat(parameters.getBackend())
-        .addInnerClasses(getClass())
-        .setMinApi(parameters.getApiLevel())
-        .addKeepMainRule(Main.class)
-        .addKeepClassRules(I.class, J.class)
-        .addKeepClassAndMembersRulesWithAllowObfuscation(Base.class)
-        .addKeepAttributeInnerClassesAndEnclosingMethod()
-        .addKeepAttributeSignature()
-        .enableInliningAnnotations()
-        .enableNeverClassInliningAnnotations()
-        .enableNoVerticalClassMergingAnnotations()
-        .addVerticallyMergedClassesInspector(
-            inspector -> inspector.assertMergedIntoSubtype(A.class))
-        .compileWithExpectedDiagnostics(
-            diagnostics -> {
-              diagnostics.assertErrorMessageThatMatches(
-                  containsString("Super type inconsistency in generic signature"));
-            });
+    R8TestRunResult runResult =
+        testForR8Compat(parameters.getBackend())
+            .addInnerClasses(getClass())
+            .setMinApi(parameters.getApiLevel())
+            .addKeepMainRule(Main.class)
+            .addKeepClassRules(I.class, J.class)
+            .addKeepClassAndMembersRulesWithAllowObfuscation(Base.class)
+            .addKeepAttributeInnerClassesAndEnclosingMethod()
+            .addKeepAttributeSignature()
+            .enableInliningAnnotations()
+            .enableNeverClassInliningAnnotations()
+            .enableNoVerticalClassMergingAnnotations()
+            .addVerticallyMergedClassesInspector(
+                inspector -> inspector.assertMergedIntoSubtype(A.class))
+            .run(parameters.getRuntime(), Main.class);
+    ClassSubject baseSubject = runResult.inspector().clazz(Base.class);
+    assertThat(baseSubject, isPresent());
+    runResult.assertSuccessWithOutputLines(
+        baseSubject.getFinalName() + "<" + String.class.getTypeName() + ">",
+        J.class.getTypeName() + "<X>",
+        // TODO(b/191871201): This could be `X` if we tracked where type-variables are introduced.
+        I.class.getTypeName() + "<java.lang.Object>",
+        "I::t",
+        "B::r");
   }
 
   public interface I<T> {
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 bd10054..a3ae2e9 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
@@ -16,7 +16,6 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.shaking.ProguardKeepAttributes;
 import com.android.tools.r8.utils.BooleanUtils;
-import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
@@ -47,9 +46,7 @@
   }
 
   private void checkSignature(CodeInspector inspector, String signature) {
-    String fooImplFinalDescriptor =
-        DescriptorUtils.javaTypeToDescriptor(inspector.clazz(FooImpl.class).getFinalName());
-    assertEquals("()" + fooImplFinalDescriptor, signature);
+    assertEquals("()" + inspector.clazz(FooImpl.class).getFinalDescriptor(), signature);
   }
 
   @Test
diff --git a/tools/compiledump.py b/tools/compiledump.py
index 46b09b8..83bc2aa 100755
--- a/tools/compiledump.py
+++ b/tools/compiledump.py
@@ -300,6 +300,7 @@
       cmd.append('-Xmx' + args.xmx)
     if args.ea:
       cmd.append('-ea')
+      cmd.append('-Dcom.android.tools.r8.enableTestAssertions=1')
     if args.print_times:
       cmd.append('-Dcom.android.tools.r8.printtimes=1')
     if hasattr(args, 'properties'):