diff --git a/src/main/java/com/android/tools/r8/kotlin/Kotlin.java b/src/main/java/com/android/tools/r8/kotlin/Kotlin.java
index 602165c..07f6b0b 100644
--- a/src/main/java/com/android/tools/r8/kotlin/Kotlin.java
+++ b/src/main/java/com/android/tools/r8/kotlin/Kotlin.java
@@ -42,7 +42,7 @@
   public static final class ClassClassifiers {
 
     public static final String arrayBinaryName = NAME + "/Array";
-    public static final String anyName = NAME + "/Any";
+    public static final String anyDescriptor = "L" + NAME + "/Any;";
   }
 
   // Mappings from JVM types to Kotlin types (of type DexType)
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinAnnotationInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinAnnotationInfo.java
index a4bc5b0..90ed44a 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinAnnotationInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinAnnotationInfo.java
@@ -4,14 +4,12 @@
 
 package com.android.tools.r8.kotlin;
 
-import static com.android.tools.r8.kotlin.KotlinMetadataUtils.referenceTypeFromBinaryName;
-
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
-import com.android.tools.r8.graph.DexString;
-import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.google.common.collect.ImmutableList;
 import java.util.List;
@@ -20,35 +18,33 @@
 import kotlinx.metadata.KmAnnotationArgument;
 
 // Holds information about a KmAnnotation
-public class KotlinAnnotationInfo {
+public class KotlinAnnotationInfo implements EnqueuerMetadataTraceable {
 
   private static final List<KotlinAnnotationInfo> EMPTY_ANNOTATIONS = ImmutableList.of();
 
-  private final DexType annotationType;
+  private final KotlinTypeReference annotationType;
   // TODO(b/155053894): Model KmAnnotationArgument.
   private final Map<String, KmAnnotationArgument<?>> arguments;
 
   private KotlinAnnotationInfo(
-      DexType annotationType, Map<String, KmAnnotationArgument<?>> arguments) {
+      KotlinTypeReference annotationType, Map<String, KmAnnotationArgument<?>> arguments) {
     this.annotationType = annotationType;
     this.arguments = arguments;
   }
 
-  private static KotlinAnnotationInfo create(
-      KmAnnotation annotation, DexDefinitionSupplier definitionSupplier) {
+  private static KotlinAnnotationInfo create(KmAnnotation annotation, DexItemFactory factory) {
     return new KotlinAnnotationInfo(
-        referenceTypeFromBinaryName(annotation.getClassName(), definitionSupplier),
+        KotlinTypeReference.fromBinaryName(annotation.getClassName(), factory),
         annotation.getArguments());
   }
 
-  static List<KotlinAnnotationInfo> create(
-      List<KmAnnotation> annotations, DexDefinitionSupplier definitionSupplier) {
+  static List<KotlinAnnotationInfo> create(List<KmAnnotation> annotations, DexItemFactory factory) {
     if (annotations.isEmpty()) {
       return EMPTY_ANNOTATIONS;
     }
     ImmutableList.Builder<KotlinAnnotationInfo> builder = ImmutableList.builder();
     for (KmAnnotation annotation : annotations) {
-      builder.add(create(annotation, definitionSupplier));
+      builder.add(create(annotation, factory));
     }
     return builder.build();
   }
@@ -57,12 +53,20 @@
       KmVisitorProviders.KmAnnotationVisitorProvider visitorProvider,
       AppView<AppInfoWithLiveness> appView,
       NamingLens namingLens) {
-    if (appView.appInfo().wasPruned(annotationType)) {
+    String renamedDescriptor =
+        annotationType.toRenamedDescriptorOrDefault(appView, namingLens, null);
+    if (renamedDescriptor == null) {
+      // The type has been pruned
       return;
     }
-    DexString descriptor = namingLens.lookupDescriptor(annotationType);
-    String classifier = DescriptorUtils.descriptorToKotlinClassifier(descriptor.toString());
+    String classifier = DescriptorUtils.descriptorToKotlinClassifier(renamedDescriptor);
     KmAnnotation annotation = new KmAnnotation(classifier, arguments);
     visitorProvider.get(annotation);
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    annotationType.trace(definitionSupplier);
+    // TODO(b/155053894): Trace annotation arguments.
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinClassInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinClassInfo.java
index b507093..b0b381e 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinClassInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinClassInfo.java
@@ -4,17 +4,17 @@
 
 package com.android.tools.r8.kotlin;
 
-import static com.android.tools.r8.kotlin.KotlinMetadataUtils.referenceTypeFromBinaryName;
 import static com.android.tools.r8.kotlin.KotlinMetadataUtils.toJvmFieldSignature;
 import static com.android.tools.r8.kotlin.KotlinMetadataUtils.toJvmMethodSignature;
+import static com.android.tools.r8.utils.FunctionUtils.forEachApply;
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexString;
-import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.DescriptorUtils;
@@ -41,14 +41,14 @@
   private final KotlinDeclarationContainerInfo declarationContainerInfo;
   private final List<KotlinTypeParameterInfo> typeParameters;
   private final List<KotlinTypeInfo> superTypes;
-  private final List<DexType> sealedSubClasses;
-  private final List<DexType> nestedClasses;
+  private final List<KotlinTypeReference> sealedSubClasses;
+  private final List<KotlinTypeReference> nestedClasses;
   // TODO(b/154347404): Understand enum entries.
   private final List<String> enumEntries;
-  private final DexType anonymousObjectOrigin;
+  private final KotlinTypeReference anonymousObjectOrigin;
   private final String packageName;
 
-  public KotlinClassInfo(
+  private KotlinClassInfo(
       int flags,
       String name,
       String moduleName,
@@ -56,10 +56,10 @@
       List<KotlinTypeParameterInfo> typeParameters,
       List<KotlinConstructorInfo> constructorsWithNoBacking,
       List<KotlinTypeInfo> superTypes,
-      List<DexType> sealedSubClasses,
-      List<DexType> nestedClasses,
+      List<KotlinTypeReference> sealedSubClasses,
+      List<KotlinTypeReference> nestedClasses,
       List<String> enumEntries,
-      DexType anonymousObjectOrigin,
+      KotlinTypeReference anonymousObjectOrigin,
       String packageName) {
     this.flags = flags;
     this.name = name;
@@ -79,7 +79,7 @@
       KmClass kmClass,
       String packageName,
       DexClass hostClass,
-      DexDefinitionSupplier definitionSupplier,
+      DexItemFactory factory,
       Reporter reporter,
       Consumer<DexEncodedMethod> keepByteCode) {
     Map<String, DexEncodedField> fieldMap = new HashMap<>();
@@ -93,7 +93,7 @@
     ImmutableList.Builder<KotlinConstructorInfo> notBackedConstructors = ImmutableList.builder();
     for (KmConstructor kmConstructor : kmClass.getConstructors()) {
       KotlinConstructorInfo constructorInfo =
-          KotlinConstructorInfo.create(kmConstructor, definitionSupplier, reporter);
+          KotlinConstructorInfo.create(kmConstructor, factory, reporter);
       JvmMethodSignature signature = JvmExtensionsKt.getSignature(kmConstructor);
       if (signature != null) {
         DexEncodedMethod method = methodMap.get(signature.asString());
@@ -107,60 +107,60 @@
     }
     KotlinDeclarationContainerInfo container =
         KotlinDeclarationContainerInfo.create(
-            kmClass, methodMap, fieldMap, definitionSupplier, reporter, keepByteCode);
+            kmClass, methodMap, fieldMap, factory, reporter, keepByteCode);
     setCompanionObject(kmClass, hostClass, reporter);
     return new KotlinClassInfo(
         kmClass.getFlags(),
         kmClass.name,
         JvmExtensionsKt.getModuleName(kmClass),
         container,
-        KotlinTypeParameterInfo.create(kmClass.getTypeParameters(), definitionSupplier, reporter),
+        KotlinTypeParameterInfo.create(kmClass.getTypeParameters(), factory, reporter),
         notBackedConstructors.build(),
-        getSuperTypes(kmClass.getSupertypes(), definitionSupplier, reporter),
-        getSealedSubClasses(hostClass, kmClass.getSealedSubclasses(), definitionSupplier),
-        getNestedClasses(hostClass, kmClass.getNestedClasses(), definitionSupplier),
+        getSuperTypes(kmClass.getSupertypes(), factory, reporter),
+        getSealedSubClasses(kmClass.getSealedSubclasses(), factory),
+        getNestedClasses(hostClass, kmClass.getNestedClasses(), factory),
         kmClass.getEnumEntries(),
-        getAnonymousObjectOrigin(kmClass, definitionSupplier),
+        getAnonymousObjectOrigin(kmClass, factory),
         packageName);
   }
 
-  private static DexType getAnonymousObjectOrigin(
-      KmClass kmClass, DexDefinitionSupplier definitionSupplier) {
+  private static KotlinTypeReference getAnonymousObjectOrigin(
+      KmClass kmClass, DexItemFactory factory) {
     String anonymousObjectOriginName = JvmExtensionsKt.getAnonymousObjectOriginName(kmClass);
     if (anonymousObjectOriginName != null) {
-      return referenceTypeFromBinaryName(anonymousObjectOriginName, definitionSupplier);
+      return KotlinTypeReference.fromBinaryName(anonymousObjectOriginName, factory);
     }
     return null;
   }
 
-  private static List<DexType> getNestedClasses(
-      DexClass clazz, List<String> nestedClasses, DexDefinitionSupplier definitionSupplier) {
-    ImmutableList.Builder<DexType> nestedTypes = ImmutableList.builder();
+  private static List<KotlinTypeReference> getNestedClasses(
+      DexClass clazz, List<String> nestedClasses, DexItemFactory factory) {
+    ImmutableList.Builder<KotlinTypeReference> nestedTypes = ImmutableList.builder();
     for (String nestedClass : nestedClasses) {
       String binaryName =
           clazz.type.toBinaryName() + DescriptorUtils.INNER_CLASS_SEPARATOR + nestedClass;
-      nestedTypes.add(referenceTypeFromBinaryName(binaryName, definitionSupplier));
+      nestedTypes.add(KotlinTypeReference.fromBinaryName(binaryName, factory));
     }
     return nestedTypes.build();
   }
 
-  private static List<DexType> getSealedSubClasses(
-      DexClass clazz, List<String> sealedSubclasses, DexDefinitionSupplier definitionSupplier) {
-    ImmutableList.Builder<DexType> sealedTypes = ImmutableList.builder();
+  private static List<KotlinTypeReference> getSealedSubClasses(
+      List<String> sealedSubclasses, DexItemFactory factory) {
+    ImmutableList.Builder<KotlinTypeReference> sealedTypes = ImmutableList.builder();
     for (String sealedSubClass : sealedSubclasses) {
       String binaryName =
           sealedSubClass.replace(
               DescriptorUtils.JAVA_PACKAGE_SEPARATOR, DescriptorUtils.INNER_CLASS_SEPARATOR);
-      sealedTypes.add(referenceTypeFromBinaryName(binaryName, definitionSupplier));
+      sealedTypes.add(KotlinTypeReference.fromBinaryName(binaryName, factory));
     }
     return sealedTypes.build();
   }
 
   private static List<KotlinTypeInfo> getSuperTypes(
-      List<KmType> superTypes, DexDefinitionSupplier definitionSupplier, Reporter reporter) {
+      List<KmType> superTypes, DexItemFactory factory, Reporter reporter) {
     ImmutableList.Builder<KotlinTypeInfo> superTypeInfos = ImmutableList.builder();
     for (KmType superType : superTypes) {
-      superTypeInfos.add(KotlinTypeInfo.create(superType, definitionSupplier, reporter));
+      superTypeInfos.add(KotlinTypeInfo.create(superType, factory, reporter));
     }
     return superTypeInfos.build();
   }
@@ -205,7 +205,7 @@
     kmClass.setName(
         originalDescriptor.equals(rewrittenDescriptor)
             ? this.name
-            : KotlinMetadataUtils.kotlinNameFromDescriptor(rewrittenDescriptor));
+            : DescriptorUtils.getBinaryNameFromDescriptor(rewrittenDescriptor.toString()));
     // Find a companion object.
     for (DexEncodedField field : clazz.fields()) {
       if (field.getKotlinMemberInfo().isCompanion()) {
@@ -240,24 +240,22 @@
       superType.rewrite(kmClass::visitSupertype, appView, namingLens);
     }
     // Rewrite nested classes.
-    for (DexType nestedClass : nestedClasses) {
-      if (appView.appInfo().isNonProgramTypeOrLiveProgramType(nestedClass)) {
-        String descriptor =
-            KotlinMetadataUtils.kotlinNameFromDescriptor(namingLens.lookupDescriptor(nestedClass));
+    for (KotlinTypeReference nestedClass : nestedClasses) {
+      String nestedDescriptor = nestedClass.toRenamedBinaryNameOrDefault(appView, namingLens, null);
+      if (nestedDescriptor != null) {
         // If the class is a nested class, it should be on the form Foo.Bar$Baz, where Baz is the
         // name we should record.
-        int innerClassIndex = descriptor.lastIndexOf(DescriptorUtils.INNER_CLASS_SEPARATOR);
-        kmClass.visitNestedClass(descriptor.substring(innerClassIndex + 1));
+        int innerClassIndex = nestedDescriptor.lastIndexOf(DescriptorUtils.INNER_CLASS_SEPARATOR);
+        kmClass.visitNestedClass(nestedDescriptor.substring(innerClassIndex + 1));
       }
     }
     // Rewrite sealed sub classes.
-    for (DexType sealedSubClass : sealedSubClasses) {
-      if (appView.appInfo().isNonProgramTypeOrLiveProgramType(sealedSubClass)) {
-        String descriptor =
-            KotlinMetadataUtils.kotlinNameFromDescriptor(
-                namingLens.lookupDescriptor(sealedSubClass));
+    for (KotlinTypeReference sealedSubClass : sealedSubClasses) {
+      String sealedDescriptor =
+          sealedSubClass.toRenamedBinaryNameOrDefault(appView, namingLens, null);
+      if (sealedDescriptor != null) {
         kmClass.visitSealedSubclass(
-            descriptor.replace(
+            sealedDescriptor.replace(
                 DescriptorUtils.INNER_CLASS_SEPARATOR, DescriptorUtils.JAVA_PACKAGE_SEPARATOR));
       }
     }
@@ -266,8 +264,11 @@
 
     JvmExtensionsKt.setModuleName(kmClass, moduleName);
     if (anonymousObjectOrigin != null) {
-      JvmExtensionsKt.setAnonymousObjectOriginName(
-          kmClass, KotlinMetadataUtils.kotlinNameFromDescriptor(anonymousObjectOrigin.descriptor));
+      String renamedAnon =
+          anonymousObjectOrigin.toRenamedBinaryNameOrDefault(appView, namingLens, null);
+      if (renamedAnon != null) {
+        JvmExtensionsKt.setAnonymousObjectOriginName(kmClass, renamedAnon);
+      }
     }
 
     KotlinClassMetadata.Class.Writer writer = new KotlinClassMetadata.Class.Writer();
@@ -279,4 +280,18 @@
   public String getPackageName() {
     return packageName;
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    forEachApply(constructorsWithNoBacking, constructor -> constructor::trace, definitionSupplier);
+    declarationContainerInfo.trace(definitionSupplier);
+    forEachApply(typeParameters, param -> param::trace, definitionSupplier);
+    forEachApply(superTypes, type -> type::trace, definitionSupplier);
+    forEachApply(sealedSubClasses, sealed -> sealed::trace, definitionSupplier);
+    forEachApply(nestedClasses, nested -> nested::trace, definitionSupplier);
+    // TODO(b/154347404): trace enum entries.
+    if (anonymousObjectOrigin != null) {
+      anonymousObjectOrigin.trace(definitionSupplier);
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinClassLevelInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinClassLevelInfo.java
index f9662ef..1a24001 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinClassLevelInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinClassLevelInfo.java
@@ -8,9 +8,14 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import kotlinx.metadata.jvm.KotlinClassHeader;
 
-public interface KotlinClassLevelInfo {
+public interface KotlinClassLevelInfo extends EnqueuerMetadataTraceable {
+
+  default boolean isNoKotlinInformation() {
+    return false;
+  }
 
   default boolean isClass() {
     return false;
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java b/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java
index 5fe02b2..2171a00 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java
@@ -12,6 +12,7 @@
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedAnnotation;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexValue;
 import com.android.tools.r8.graph.DexValue.DexValueArray;
@@ -31,22 +32,18 @@
   public static KotlinClassLevelInfo getKotlinInfo(
       Kotlin kotlin,
       DexClass clazz,
-      DexDefinitionSupplier definitionSupplier,
+      DexItemFactory factory,
       Reporter reporter,
       boolean onlyProcessLambda,
       Consumer<DexEncodedMethod> keepByteCode) {
-    DexAnnotation meta =
-        clazz
-            .annotations()
-            .getFirstMatching(definitionSupplier.dexItemFactory().kotlinMetadataType);
+    DexAnnotation meta = clazz.annotations().getFirstMatching(factory.kotlinMetadataType);
     if (meta != null) {
       try {
         KotlinClassMetadata kMetadata = toKotlinClassMetadata(kotlin, meta.annotation);
         if (onlyProcessLambda && kMetadata.getHeader().getKind() != KOTLIN_METADATA_KIND_LAMBDA) {
           return NO_KOTLIN_INFO;
         }
-        return createKotlinInfo(
-            kotlin, clazz, kMetadata, definitionSupplier, reporter, keepByteCode);
+        return createKotlinInfo(kotlin, clazz, kMetadata, factory, reporter, keepByteCode);
       } catch (ClassCastException | InconsistentKotlinMetadataException | MetadataError e) {
         reporter.info(
             new StringDiagnostic(
@@ -68,6 +65,14 @@
     return NO_KOTLIN_INFO;
   }
 
+  public static boolean hasKotlinClassMetadataAnnotation(
+      DexClass clazz, DexDefinitionSupplier definitionSupplier) {
+    return clazz
+            .annotations()
+            .getFirstMatching(definitionSupplier.dexItemFactory().kotlinMetadataType)
+        != null;
+  }
+
   public static KotlinClassMetadata toKotlinClassMetadata(
       Kotlin kotlin, DexEncodedAnnotation metadataAnnotation) {
     Map<DexString, DexAnnotationElement> elementMap = new IdentityHashMap<>();
@@ -103,7 +108,7 @@
       Kotlin kotlin,
       DexClass clazz,
       KotlinClassMetadata kMetadata,
-      DexDefinitionSupplier definitionSupplier,
+      DexItemFactory factory,
       Reporter reporter,
       Consumer<DexEncodedMethod> keepByteCode) {
     String packageName = kMetadata.getHeader().getPackageName();
@@ -112,7 +117,7 @@
           ((KotlinClassMetadata.Class) kMetadata).toKmClass(),
           packageName,
           clazz,
-          definitionSupplier,
+          factory,
           reporter,
           keepByteCode);
     } else if (kMetadata instanceof KotlinClassMetadata.FileFacade) {
@@ -121,20 +126,20 @@
           (KotlinClassMetadata.FileFacade) kMetadata,
           packageName,
           clazz,
-          definitionSupplier,
+          factory,
           reporter,
           keepByteCode);
     } else if (kMetadata instanceof KotlinClassMetadata.MultiFileClassFacade) {
       // multi-file class with the same @JvmName.
       return KotlinMultiFileClassFacadeInfo.create(
-          (KotlinClassMetadata.MultiFileClassFacade) kMetadata, packageName, definitionSupplier);
+          (KotlinClassMetadata.MultiFileClassFacade) kMetadata, packageName, factory);
     } else if (kMetadata instanceof KotlinClassMetadata.MultiFileClassPart) {
       // A single file, which is part of multi-file class.
       return KotlinMultiFileClassPartInfo.create(
           (KotlinClassMetadata.MultiFileClassPart) kMetadata,
           packageName,
           clazz,
-          definitionSupplier,
+          factory,
           reporter,
           keepByteCode);
     } else if (kMetadata instanceof KotlinClassMetadata.SyntheticClass) {
@@ -143,7 +148,7 @@
           packageName,
           clazz,
           kotlin,
-          definitionSupplier,
+          factory,
           reporter);
     } else {
       throw new MetadataError("unsupported 'k' value: " + kMetadata.getHeader().getKind());
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinClassifierInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinClassifierInfo.java
index d6ff5b4..ac19e28 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinClassifierInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinClassifierInfo.java
@@ -4,15 +4,13 @@
 
 package com.android.tools.r8.kotlin;
 
-import static com.android.tools.r8.kotlin.KotlinMetadataUtils.referenceTypeFromDescriptor;
-
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
-import com.android.tools.r8.graph.DexString;
-import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.kotlin.Kotlin.ClassClassifiers;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.Reporter;
 import kotlinx.metadata.KmClassifier;
@@ -20,10 +18,10 @@
 import kotlinx.metadata.KmClassifier.TypeParameter;
 import kotlinx.metadata.KmTypeVisitor;
 
-public abstract class KotlinClassifierInfo {
+public abstract class KotlinClassifierInfo implements EnqueuerMetadataTraceable {
 
   public static KotlinClassifierInfo create(
-      KmClassifier classifier, DexDefinitionSupplier definitionSupplier, Reporter reporter) {
+      KmClassifier classifier, DexItemFactory factory, Reporter reporter) {
     if (classifier instanceof KmClassifier.Class) {
       String originalTypeName = ((KmClassifier.Class) classifier).getName();
       // If this name starts with '.', it represents a local class or an anonymous object. This is
@@ -35,7 +33,7 @@
               isLocalOrAnonymous ? originalTypeName.substring(1) : originalTypeName);
       if (DescriptorUtils.isClassDescriptor(descriptor)) {
         return new KotlinClassClassifierInfo(
-            referenceTypeFromDescriptor(descriptor, definitionSupplier), isLocalOrAnonymous);
+            KotlinTypeReference.fromDescriptor(descriptor, factory), isLocalOrAnonymous);
       } else {
         return new KotlinUnknownClassClassifierInfo(originalTypeName);
       }
@@ -54,10 +52,10 @@
 
   public static class KotlinClassClassifierInfo extends KotlinClassifierInfo {
 
-    private final DexType type;
+    private final KotlinTypeReference type;
     private final boolean isLocalOrAnonymous;
 
-    private KotlinClassClassifierInfo(DexType type, boolean isLocalOrAnonymous) {
+    private KotlinClassClassifierInfo(KotlinTypeReference type, boolean isLocalOrAnonymous) {
       this.type = type;
       this.isLocalOrAnonymous = isLocalOrAnonymous;
     }
@@ -65,20 +63,21 @@
     @Override
     void rewrite(
         KmTypeVisitor visitor, AppView<AppInfoWithLiveness> appView, NamingLens namingLens) {
-      if (appView.appInfo().wasPruned(type)) {
-        visitor.visitClass(ClassClassifiers.anyName);
-        return;
-      }
-      DexString descriptor = namingLens.lookupDescriptor(type);
+      String descriptor =
+          type.toRenamedDescriptorOrDefault(appView, namingLens, ClassClassifiers.anyDescriptor);
       // For local or anonymous classes, the classifier is prefixed with '.' and inner classes are
       // separated with '$'.
       if (isLocalOrAnonymous) {
-        visitor.visitClass(
-            "." + DescriptorUtils.getBinaryNameFromDescriptor(descriptor.toString()));
+        visitor.visitClass("." + DescriptorUtils.getBinaryNameFromDescriptor(descriptor));
       } else {
-        visitor.visitClass(DescriptorUtils.descriptorToKotlinClassifier(descriptor.toString()));
+        visitor.visitClass(DescriptorUtils.descriptorToKotlinClassifier(descriptor));
       }
     }
+
+    @Override
+    public void trace(DexDefinitionSupplier definitionSupplier) {
+      type.trace(definitionSupplier);
+    }
   }
 
   public static class KotlinTypeParameterClassifierInfo extends KotlinClassifierInfo {
@@ -94,6 +93,11 @@
         KmTypeVisitor visitor, AppView<AppInfoWithLiveness> appView, NamingLens namingLens) {
       visitor.visitTypeParameter(typeId);
     }
+
+    @Override
+    public void trace(DexDefinitionSupplier definitionSupplier) {
+      // Intentionally empty.
+    }
   }
 
   public static class KotlinTypeAliasClassifierInfo extends KotlinClassifierInfo {
@@ -109,6 +113,11 @@
         KmTypeVisitor visitor, AppView<AppInfoWithLiveness> appView, NamingLens namingLens) {
       visitor.visitTypeAlias(typeAlias);
     }
+
+    @Override
+    public void trace(DexDefinitionSupplier definitionSupplier) {
+      // Intentionally empty.
+    }
   }
 
   public static class KotlinUnknownClassClassifierInfo extends KotlinClassifierInfo {
@@ -123,6 +132,11 @@
         KmTypeVisitor visitor, AppView<AppInfoWithLiveness> appView, NamingLens namingLens) {
       visitor.visitClass(classifier);
     }
+
+    @Override
+    public void trace(DexDefinitionSupplier definitionSupplier) {
+      // Intentionally empty.
+    }
   }
 
   public static class KotlinUnknownClassifierInfo extends KotlinClassifierInfo {
@@ -137,5 +151,10 @@
         KmTypeVisitor visitor, AppView<AppInfoWithLiveness> appView, NamingLens namingLens) {
       visitor.visitTypeAlias(classifier);
     }
+
+    @Override
+    public void trace(DexDefinitionSupplier definitionSupplier) {
+      // Intentionally empty.
+    }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinCompanionInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinCompanionInfo.java
index 2f97b4f..1e19f1a 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinCompanionInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinCompanionInfo.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.kotlin;
 
+import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.naming.NamingLens;
@@ -27,4 +28,9 @@
     String finalName = dexString.toString();
     visitor.visitCompanionObject(finalName);
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    // Do nothing.
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinConstructorInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinConstructorInfo.java
index 6f9f366..857ef39 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinConstructorInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinConstructorInfo.java
@@ -4,9 +4,12 @@
 
 package com.android.tools.r8.kotlin;
 
+import static com.android.tools.r8.utils.FunctionUtils.forEachApply;
+
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.Reporter;
@@ -35,13 +38,11 @@
   }
 
   public static KotlinConstructorInfo create(
-      KmConstructor kmConstructor, DexDefinitionSupplier definitionSupplier, Reporter reporter) {
+      KmConstructor kmConstructor, DexItemFactory factory, Reporter reporter) {
     return new KotlinConstructorInfo(
         kmConstructor.getFlags(),
-        KotlinValueParameterInfo.create(
-            kmConstructor.getValueParameters(), definitionSupplier, reporter),
-        KotlinJvmMethodSignatureInfo.create(
-            JvmExtensionsKt.getSignature(kmConstructor), definitionSupplier));
+        KotlinValueParameterInfo.create(kmConstructor.getValueParameters(), factory, reporter),
+        KotlinJvmMethodSignatureInfo.create(JvmExtensionsKt.getSignature(kmConstructor), factory));
   }
 
   public void rewrite(
@@ -71,4 +72,12 @@
   public KotlinConstructorInfo asConstructor() {
     return this;
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    forEachApply(valueParameterInfos, param -> param::trace, definitionSupplier);
+    if (signature != null) {
+      signature.trace(definitionSupplier);
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinDeclarationContainerInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinDeclarationContainerInfo.java
index cd349ab..a83f77a 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinDeclarationContainerInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinDeclarationContainerInfo.java
@@ -5,15 +5,18 @@
 package com.android.tools.r8.kotlin;
 
 import static com.android.tools.r8.kotlin.KotlinMetadataUtils.isValidMethodDescriptor;
+import static com.android.tools.r8.utils.FunctionUtils.forEachApply;
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.kotlin.KotlinMetadataUtils.KmPropertyProcessor;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import com.android.tools.r8.utils.Reporter;
 import com.google.common.collect.ImmutableList;
 import java.util.IdentityHashMap;
@@ -29,7 +32,7 @@
 import kotlinx.metadata.jvm.JvmMethodSignature;
 
 // Holds information about KmDeclarationContainer
-public class KotlinDeclarationContainerInfo {
+public class KotlinDeclarationContainerInfo implements EnqueuerMetadataTraceable {
 
   private final List<KotlinTypeAliasInfo> typeAliases;
   // The functions in notBackedFunctions are KmFunctions where we could not find a representative.
@@ -51,7 +54,7 @@
       KmDeclarationContainer container,
       Map<String, DexEncodedMethod> methodSignatureMap,
       Map<String, DexEncodedField> fieldSignatureMap,
-      DexDefinitionSupplier definitionSupplier,
+      DexItemFactory factory,
       Reporter reporter,
       Consumer<DexEncodedMethod> keepByteCode) {
     ImmutableList.Builder<KotlinFunctionInfo> notBackedFunctions = ImmutableList.builder();
@@ -62,7 +65,7 @@
         continue;
       }
       KotlinFunctionInfo kotlinFunctionInfo =
-          KotlinFunctionInfo.create(kmFunction, definitionSupplier, reporter);
+          KotlinFunctionInfo.create(kmFunction, factory, reporter);
       DexEncodedMethod method = methodSignatureMap.get(signature.asString());
       if (method == null) {
         notBackedFunctions.add(kotlinFunctionInfo);
@@ -85,7 +88,7 @@
     ImmutableList.Builder<KotlinPropertyInfo> notBackedProperties = ImmutableList.builder();
     for (KmProperty kmProperty : container.getProperties()) {
       KotlinPropertyInfo kotlinPropertyInfo =
-          KotlinPropertyInfo.create(kmProperty, definitionSupplier, reporter);
+          KotlinPropertyInfo.create(kmProperty, factory, reporter);
       KmPropertyProcessor propertyProcessor = new KmPropertyProcessor(kmProperty);
       boolean hasBacking = false;
       if (propertyProcessor.fieldSignature() != null) {
@@ -119,7 +122,7 @@
       }
     }
     return new KotlinDeclarationContainerInfo(
-        getTypeAliases(container.getTypeAliases(), definitionSupplier, reporter),
+        getTypeAliases(container.getTypeAliases(), factory, reporter),
         notBackedFunctions.build(),
         notBackedProperties.build());
   }
@@ -139,10 +142,10 @@
   }
 
   private static List<KotlinTypeAliasInfo> getTypeAliases(
-      List<KmTypeAlias> aliases, DexDefinitionSupplier definitionSupplier, Reporter reporter) {
+      List<KmTypeAlias> aliases, DexItemFactory factory, Reporter reporter) {
     ImmutableList.Builder<KotlinTypeAliasInfo> builder = ImmutableList.builder();
     for (KmTypeAlias alias : aliases) {
-      builder.add(KotlinTypeAliasInfo.create(alias, definitionSupplier, reporter));
+      builder.add(KotlinTypeAliasInfo.create(alias, factory, reporter));
     }
     return builder.build();
   }
@@ -208,6 +211,13 @@
     }
   }
 
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    forEachApply(typeAliases, alias -> alias::trace, definitionSupplier);
+    forEachApply(functionsWithNoBacking, function -> function::trace, definitionSupplier);
+    forEachApply(propertiesWithNoBacking, property -> property::trace, definitionSupplier);
+  }
+
   public static class KotlinPropertyGroup {
 
     private DexEncodedField backingField = null;
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinFieldLevelInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinFieldLevelInfo.java
index 7df7afb..8d9d468 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinFieldLevelInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinFieldLevelInfo.java
@@ -4,7 +4,9 @@
 
 package com.android.tools.r8.kotlin;
 
-public interface KotlinFieldLevelInfo {
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
+
+public interface KotlinFieldLevelInfo extends EnqueuerMetadataTraceable {
 
   default boolean isCompanion() {
     return false;
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinFileFacadeInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinFileFacadeInfo.java
index c31df8c..94617e1 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinFileFacadeInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinFileFacadeInfo.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.Reporter;
@@ -32,12 +33,12 @@
       FileFacade kmFileFacade,
       String packageName,
       DexClass clazz,
-      DexDefinitionSupplier definitionSupplier,
+      DexItemFactory factory,
       Reporter reporter,
       Consumer<DexEncodedMethod> keepByteCode) {
     return new KotlinFileFacadeInfo(
         KotlinPackageInfo.create(
-            kmFileFacade.toKmPackage(), clazz, definitionSupplier, reporter, keepByteCode),
+            kmFileFacade.toKmPackage(), clazz, factory, reporter, keepByteCode),
         packageName);
   }
 
@@ -65,4 +66,9 @@
   public String getPackageName() {
     return packageName;
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    packageInfo.trace(definitionSupplier);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinFlexibleTypeUpperBoundInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinFlexibleTypeUpperBoundInfo.java
index c8c8836..da2e960 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinFlexibleTypeUpperBoundInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinFlexibleTypeUpperBoundInfo.java
@@ -6,6 +6,7 @@
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.Reporter;
@@ -45,22 +46,20 @@
   }
 
   static KotlinFlexibleTypeUpperBoundInfo create(
-      KmFlexibleTypeUpperBound flexibleTypeUpperBound,
-      DexDefinitionSupplier definitionSupplier,
-      Reporter reporter) {
+      KmFlexibleTypeUpperBound flexibleTypeUpperBound, DexItemFactory factory, Reporter reporter) {
     if (flexibleTypeUpperBound == null) {
       return NO_FLEXIBLE_UPPER_BOUND;
     }
     KmType kmType = flexibleTypeUpperBound.getType();
     return new KotlinFlexibleTypeUpperBoundInfo(
         kmType.getFlags(),
-        KotlinClassifierInfo.create(kmType.classifier, definitionSupplier, reporter),
-        KotlinTypeInfo.create(kmType.getAbbreviatedType(), definitionSupplier, reporter),
-        KotlinTypeInfo.create(kmType.getOuterType(), definitionSupplier, reporter),
-        getArguments(kmType.getArguments(), definitionSupplier, reporter),
-        KotlinAnnotationInfo.create(JvmExtensionsKt.getAnnotations(kmType), definitionSupplier),
+        KotlinClassifierInfo.create(kmType.classifier, factory, reporter),
+        KotlinTypeInfo.create(kmType.getAbbreviatedType(), factory, reporter),
+        KotlinTypeInfo.create(kmType.getOuterType(), factory, reporter),
+        getArguments(kmType.getArguments(), factory, reporter),
+        KotlinAnnotationInfo.create(JvmExtensionsKt.getAnnotations(kmType), factory),
         KotlinFlexibleTypeUpperBoundInfo.create(
-            kmType.getFlexibleTypeUpperBound(), definitionSupplier, reporter),
+            kmType.getFlexibleTypeUpperBound(), factory, reporter),
         flexibleTypeUpperBound.getTypeFlexibilityId());
   }
 
@@ -74,4 +73,12 @@
     }
     super.rewrite(flags -> visitorProvider.get(flags, typeFlexibilityId), appView, namingLens);
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    if (this == NO_FLEXIBLE_UPPER_BOUND) {
+      return;
+    }
+    super.trace(definitionSupplier);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinFunctionInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinFunctionInfo.java
index 58b07cb..341d7b0 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinFunctionInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinFunctionInfo.java
@@ -4,12 +4,12 @@
 
 package com.android.tools.r8.kotlin;
 
-import static com.android.tools.r8.kotlin.KotlinMetadataUtils.referenceTypeFromBinaryName;
+import static com.android.tools.r8.utils.FunctionUtils.forEachApply;
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.Reporter;
@@ -36,7 +36,7 @@
   // Information about the signature
   private final KotlinJvmMethodSignatureInfo signature;
   // Information about the lambdaClassOrigin.
-  private final DexType lambdaClassOrigin;
+  private final KotlinTypeReference lambdaClassOrigin;
 
   private KotlinFunctionInfo(
       int flags,
@@ -46,7 +46,7 @@
       List<KotlinValueParameterInfo> valueParameters,
       List<KotlinTypeParameterInfo> typeParameters,
       KotlinJvmMethodSignatureInfo signature,
-      DexType lambdaClassOrigin) {
+      KotlinTypeReference lambdaClassOrigin) {
     this.flags = flags;
     this.name = name;
     this.returnType = returnType;
@@ -58,26 +58,23 @@
   }
 
   static KotlinFunctionInfo create(
-      KmFunction kmFunction, DexDefinitionSupplier definitionSupplier, Reporter reporter) {
+      KmFunction kmFunction, DexItemFactory factory, Reporter reporter) {
     return new KotlinFunctionInfo(
         kmFunction.getFlags(),
         kmFunction.getName(),
-        KotlinTypeInfo.create(kmFunction.getReturnType(), definitionSupplier, reporter),
-        KotlinTypeInfo.create(kmFunction.getReceiverParameterType(), definitionSupplier, reporter),
-        KotlinValueParameterInfo.create(
-            kmFunction.getValueParameters(), definitionSupplier, reporter),
-        KotlinTypeParameterInfo.create(
-            kmFunction.getTypeParameters(), definitionSupplier, reporter),
-        KotlinJvmMethodSignatureInfo.create(
-            JvmExtensionsKt.getSignature(kmFunction), definitionSupplier),
-        getlambdaClassOrigin(kmFunction, definitionSupplier));
+        KotlinTypeInfo.create(kmFunction.getReturnType(), factory, reporter),
+        KotlinTypeInfo.create(kmFunction.getReceiverParameterType(), factory, reporter),
+        KotlinValueParameterInfo.create(kmFunction.getValueParameters(), factory, reporter),
+        KotlinTypeParameterInfo.create(kmFunction.getTypeParameters(), factory, reporter),
+        KotlinJvmMethodSignatureInfo.create(JvmExtensionsKt.getSignature(kmFunction), factory),
+        getlambdaClassOrigin(kmFunction, factory));
   }
 
-  private static DexType getlambdaClassOrigin(
-      KmFunction kmFunction, DexDefinitionSupplier definitionSupplier) {
+  private static KotlinTypeReference getlambdaClassOrigin(
+      KmFunction kmFunction, DexItemFactory factory) {
     String lambdaClassOriginName = JvmExtensionsKt.getLambdaClassOriginName(kmFunction);
     if (lambdaClassOriginName != null) {
-      return referenceTypeFromBinaryName(lambdaClassOriginName, definitionSupplier);
+      return KotlinTypeReference.fromBinaryName(lambdaClassOriginName, factory);
     }
     return null;
   }
@@ -114,8 +111,11 @@
       extensionVisitor.visit(signature.rewrite(method, appView, namingLens));
     }
     if (lambdaClassOrigin != null && extensionVisitor != null) {
-      extensionVisitor.visitLambdaClassOriginName(
-          KotlinMetadataUtils.kotlinNameFromDescriptor(lambdaClassOrigin.descriptor));
+      String lambdaClassOriginName =
+          lambdaClassOrigin.toRenamedBinaryNameOrDefault(appView, namingLens, null);
+      if (lambdaClassOriginName != null) {
+        extensionVisitor.visitLambdaClassOriginName(lambdaClassOriginName);
+      }
     }
   }
 
@@ -132,4 +132,24 @@
   public boolean isExtensionFunction() {
     return receiverParameterType != null;
   }
+
+  public KotlinJvmMethodSignatureInfo getSignature() {
+    return signature;
+  }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    forEachApply(valueParameters, param -> param::trace, definitionSupplier);
+    returnType.trace(definitionSupplier);
+    if (receiverParameterType != null) {
+      receiverParameterType.trace(definitionSupplier);
+    }
+    forEachApply(typeParameters, param -> param::trace, definitionSupplier);
+    if (signature != null) {
+      signature.trace(definitionSupplier);
+    }
+    if (lambdaClassOrigin != null) {
+      lambdaClassOrigin.trace(definitionSupplier);
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinJvmFieldSignatureInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinJvmFieldSignatureInfo.java
index 69c0442..6daf3d7 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinJvmFieldSignatureInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinJvmFieldSignatureInfo.java
@@ -4,39 +4,37 @@
 
 package com.android.tools.r8.kotlin;
 
-import static com.android.tools.r8.kotlin.KotlinMetadataUtils.referenceTypeFromDescriptor;
-import static com.android.tools.r8.kotlin.KotlinMetadataUtils.toRenamedDescriptorOrDefault;
-
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedField;
-import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import kotlinx.metadata.jvm.JvmFieldSignature;
 
 /**
  * The JvmSignature for a method or property does not always correspond to the actual signature, see
  * b/154201250. We therefore need to model the signature as well.
  */
-public class KotlinJvmFieldSignatureInfo {
+public class KotlinJvmFieldSignatureInfo implements EnqueuerMetadataTraceable {
 
-  private final DexType type;
+  private final KotlinTypeReference type;
   private final String name;
 
-  private KotlinJvmFieldSignatureInfo(String name, DexType type) {
+  private KotlinJvmFieldSignatureInfo(String name, KotlinTypeReference type) {
     this.name = name;
     this.type = type;
   }
 
   public static KotlinJvmFieldSignatureInfo create(
-      JvmFieldSignature fieldSignature, DexDefinitionSupplier definitionSupplier) {
+      JvmFieldSignature fieldSignature, DexItemFactory factory) {
     if (fieldSignature == null) {
       return null;
     }
     return new KotlinJvmFieldSignatureInfo(
         fieldSignature.getName(),
-        referenceTypeFromDescriptor(fieldSignature.getDesc(), definitionSupplier));
+        KotlinTypeReference.fromDescriptor(fieldSignature.getDesc(), factory));
   }
 
   public JvmFieldSignature rewrite(
@@ -51,6 +49,11 @@
     }
     String defValue = appView.dexItemFactory().objectType.toDescriptorString();
     return new JvmFieldSignature(
-        finalName, toRenamedDescriptorOrDefault(type, appView, namingLens, defValue));
+        finalName, type.toRenamedDescriptorOrDefault(appView, namingLens, defValue));
+  }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    type.trace(definitionSupplier);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinJvmMethodSignatureInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinJvmMethodSignatureInfo.java
index d9d5c9d..f4674a1 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinJvmMethodSignatureInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinJvmMethodSignatureInfo.java
@@ -4,15 +4,15 @@
 
 package com.android.tools.r8.kotlin;
 
-import static com.android.tools.r8.kotlin.KotlinMetadataUtils.referenceTypeFromDescriptor;
-import static com.android.tools.r8.kotlin.KotlinMetadataUtils.toRenamedDescriptorOrDefault;
+import static com.android.tools.r8.utils.FunctionUtils.forEachApply;
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.google.common.collect.ImmutableList;
 import java.util.List;
@@ -22,36 +22,51 @@
  * The JvmSignature for a method or property does not always correspond to the actual signature, see
  * b/154201250. We therefore need to model the signature as well.
  */
-public class KotlinJvmMethodSignatureInfo {
+public class KotlinJvmMethodSignatureInfo implements EnqueuerMetadataTraceable {
 
-  private static final List<DexType> EMPTY_PARAMETERS_LIST = ImmutableList.of();
+  private static final List<KotlinTypeReference> EMPTY_PARAMETERS_LIST = ImmutableList.of();
 
   private final String name;
-  private final DexType returnType;
-  private final List<DexType> parameters;
+  private final KotlinTypeReference returnType;
+  private final List<KotlinTypeReference> parameters;
+  private final String invalidDescriptor;
 
-  private KotlinJvmMethodSignatureInfo(String name, DexType returnType, List<DexType> parameters) {
+  private KotlinJvmMethodSignatureInfo(
+      String name, KotlinTypeReference returnType, List<KotlinTypeReference> parameters) {
     this.name = name;
     this.returnType = returnType;
     this.parameters = parameters;
+    this.invalidDescriptor = null;
+  }
+
+  private KotlinJvmMethodSignatureInfo(String name, String invalidDescriptor) {
+    this.name = name;
+    this.invalidDescriptor = invalidDescriptor;
+    this.parameters = EMPTY_PARAMETERS_LIST;
+    this.returnType = null;
   }
 
   public static KotlinJvmMethodSignatureInfo create(
-      JvmMethodSignature methodSignature, DexDefinitionSupplier definitionSupplier) {
+      JvmMethodSignature methodSignature, DexItemFactory factory) {
     if (methodSignature == null) {
       return null;
     }
     String kotlinDescriptor = methodSignature.getDesc();
+    if (!KotlinMetadataUtils.isValidMethodDescriptor(kotlinDescriptor)) {
+      // If the method descriptor is invalid, keep it as invalid.
+      return new KotlinJvmMethodSignatureInfo(methodSignature.getName(), kotlinDescriptor);
+    }
     String returnTypeDescriptor = DescriptorUtils.getReturnTypeDescriptor(kotlinDescriptor);
-    DexType returnType = referenceTypeFromDescriptor(returnTypeDescriptor, definitionSupplier);
+    KotlinTypeReference returnType =
+        KotlinTypeReference.fromDescriptor(returnTypeDescriptor, factory);
     String[] descriptors = DescriptorUtils.getArgumentTypeDescriptors(kotlinDescriptor);
     if (descriptors.length == 0) {
       return new KotlinJvmMethodSignatureInfo(
           methodSignature.getName(), returnType, EMPTY_PARAMETERS_LIST);
     }
-    ImmutableList.Builder<DexType> parameters = ImmutableList.builder();
+    ImmutableList.Builder<KotlinTypeReference> parameters = ImmutableList.builder();
     for (String descriptor : descriptors) {
-      parameters.add(referenceTypeFromDescriptor(descriptor, definitionSupplier));
+      parameters.add(KotlinTypeReference.fromDescriptor(descriptor, factory));
     }
     return new KotlinJvmMethodSignatureInfo(
         methodSignature.getName(), returnType, parameters.build());
@@ -59,6 +74,10 @@
 
   public JvmMethodSignature rewrite(
       DexEncodedMethod method, AppView<AppInfoWithLiveness> appView, NamingLens namingLens) {
+    if (invalidDescriptor != null) {
+      return new JvmMethodSignature(name, invalidDescriptor);
+    }
+    assert returnType != null;
     String finalName = name;
     if (method != null) {
       String methodName = method.method.name.toString();
@@ -70,11 +89,38 @@
     StringBuilder descBuilder = new StringBuilder();
     descBuilder.append("(");
     String defValue = appView.dexItemFactory().objectType.toDescriptorString();
-    for (DexType parameter : parameters) {
-      descBuilder.append(toRenamedDescriptorOrDefault(parameter, appView, namingLens, defValue));
+    for (KotlinTypeReference parameter : parameters) {
+      descBuilder.append(parameter.toRenamedDescriptorOrDefault(appView, namingLens, defValue));
     }
     descBuilder.append(")");
-    descBuilder.append(toRenamedDescriptorOrDefault(returnType, appView, namingLens, defValue));
+    descBuilder.append(returnType.toRenamedDescriptorOrDefault(appView, namingLens, defValue));
     return new JvmMethodSignature(finalName, descBuilder.toString());
   }
+
+  @Override
+  public String toString() {
+    if (invalidDescriptor != null) {
+      return name + "(" + invalidDescriptor + ")";
+    }
+    assert returnType != null;
+    StringBuilder descBuilder = new StringBuilder();
+    descBuilder.append(name);
+    descBuilder.append("(");
+    for (KotlinTypeReference parameter : parameters) {
+      descBuilder.append(parameter.toString());
+    }
+    descBuilder.append(")");
+    descBuilder.append(returnType.toString());
+    return descBuilder.toString();
+  }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    if (invalidDescriptor != null) {
+      return;
+    }
+    assert returnType != null;
+    returnType.trace(definitionSupplier);
+    forEachApply(parameters, param -> param::trace, definitionSupplier);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinLambdaInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinLambdaInfo.java
index d25f105..459599b 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinLambdaInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinLambdaInfo.java
@@ -10,48 +10,44 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import com.android.tools.r8.utils.Reporter;
 import kotlinx.metadata.KmLambda;
-import kotlinx.metadata.KmLambdaVisitor;
 import kotlinx.metadata.jvm.JvmExtensionsKt;
 import kotlinx.metadata.jvm.JvmMethodSignature;
 
 // Holds information about a KmLambda
-public class KotlinLambdaInfo {
+public class KotlinLambdaInfo implements EnqueuerMetadataTraceable {
 
   private final KotlinFunctionInfo function;
+  private final boolean hasBacking;
 
-  private KotlinLambdaInfo(KotlinFunctionInfo function) {
+  private KotlinLambdaInfo(KotlinFunctionInfo function, boolean hasBacking) {
     this.function = function;
+    this.hasBacking = hasBacking;
   }
 
   static KotlinLambdaInfo create(
-      DexClass clazz,
-      KmLambda lambda,
-      DexDefinitionSupplier definitionSupplier,
-      Reporter reporter) {
+      DexClass clazz, KmLambda lambda, DexItemFactory factory, Reporter reporter) {
     if (lambda == null) {
       assert false;
       return null;
     }
+    KotlinFunctionInfo kotlinFunctionInfo =
+        KotlinFunctionInfo.create(lambda.function, factory, reporter);
     JvmMethodSignature signature = JvmExtensionsKt.getSignature(lambda.function);
-    if (signature == null) {
-      assert false;
-      return null;
-    }
-    for (DexEncodedMethod method : clazz.methods()) {
-      if (toJvmMethodSignature(method.method).asString().equals(signature.asString())) {
-        KotlinFunctionInfo kotlinFunctionInfo =
-            KotlinFunctionInfo.create(lambda.function, definitionSupplier, reporter);
-        method.setKotlinMemberInfo(kotlinFunctionInfo);
-        return new KotlinLambdaInfo(kotlinFunctionInfo);
+    if (signature != null) {
+      for (DexEncodedMethod method : clazz.methods()) {
+        if (toJvmMethodSignature(method.method).asString().equals(signature.asString())) {
+          method.setKotlinMemberInfo(kotlinFunctionInfo);
+          return new KotlinLambdaInfo(kotlinFunctionInfo, true);
+        }
       }
     }
-    // TODO(b/155536535): Resolve this assert for NestTreeShakeJarVerificationTest.
-    // assert false;
-    return null;
+    return new KotlinLambdaInfo(kotlinFunctionInfo, false);
   }
 
   boolean rewrite(
@@ -59,13 +55,31 @@
       DexClass clazz,
       AppView<AppInfoWithLiveness> appView,
       NamingLens namingLens) {
+    if (!hasBacking) {
+      function.rewrite(visitorProvider.get()::visitFunction, null, appView, namingLens);
+      return true;
+    }
+    DexEncodedMethod backing = null;
     for (DexEncodedMethod method : clazz.methods()) {
       if (method.getKotlinMemberInfo() == function) {
-        KmLambdaVisitor kmLambdaVisitor = visitorProvider.get();
-        function.rewrite(kmLambdaVisitor::visitFunction, method, appView, namingLens);
-        return true;
+        backing = method;
+        break;
       }
     }
-    return false;
+    if (backing == null) {
+      appView
+          .options()
+          .reporter
+          .info(
+              KotlinMetadataDiagnostic.lambdaBackingNotFound(clazz.type, function.getSignature()));
+      return false;
+    }
+    function.rewrite(visitorProvider.get()::visitFunction, backing, appView, namingLens);
+    return true;
+  }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    function.trace(definitionSupplier);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataDiagnostic.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataDiagnostic.java
index 83947d7..3415e13 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataDiagnostic.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataDiagnostic.java
@@ -73,4 +73,18 @@
             + StringUtils.LINE_SEPARATOR
             + StringUtils.stacktraceAsString(t));
   }
+
+  static KotlinMetadataDiagnostic lambdaBackingNotFound(
+      DexType type, KotlinJvmMethodSignatureInfo signatureInfo) {
+    return new KotlinMetadataDiagnostic(
+        Origin.unknown(),
+        Position.UNKNOWN,
+        "The lambda function "
+            + signatureInfo.toString()
+            + " could no longer be found in "
+            + type.toSourceString()
+            + " . The method is most likely pruned and would require a specific keep rule to keep"
+            + " alive. As a result, the metadata information regarding the lambda structure has"
+            + " been discarded.");
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataEnqueuerExtension.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataEnqueuerExtension.java
index 8b503e6..3fbf7ce 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataEnqueuerExtension.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataEnqueuerExtension.java
@@ -4,10 +4,22 @@
 
 package com.android.tools.r8.kotlin;
 
+import static com.android.tools.r8.kotlin.KotlinClassMetadataReader.hasKotlinClassMetadataAnnotation;
+import static com.android.tools.r8.kotlin.KotlinMetadataUtils.NO_KOTLIN_INFO;
+import static com.android.tools.r8.utils.FunctionUtils.forEachApply;
+
+import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexDefinition;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
+import com.android.tools.r8.graph.DexEncodedField;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.analysis.EnqueuerAnalysis;
 import com.android.tools.r8.shaking.Enqueuer;
@@ -18,12 +30,11 @@
 
   private final AppView<?> appView;
   private final DexDefinitionSupplier definitionSupplier;
-  private final Set<DexMethod> keepByteCodeFunctions = Sets.newIdentityHashSet();
 
   public KotlinMetadataEnqueuerExtension(
-      AppView<?> appView, DexDefinitionSupplier definitionSupplier) {
+      AppView<?> appView, DexDefinitionSupplier definitionSupplier, Set<DexType> prunedTypes) {
     this.appView = appView;
-    this.definitionSupplier = definitionSupplier;
+    this.definitionSupplier = new KotlinMetadataDefinitionSupplier(definitionSupplier, prunedTypes);
   }
 
   @Override
@@ -31,23 +42,99 @@
     DexType kotlinMetadataType = appView.dexItemFactory().kotlinMetadataType;
     DexClass kotlinMetadataClass =
         appView.appInfo().definitionForWithoutExistenceAssert(kotlinMetadataType);
-    // We will process kotlin.Metadata even if the type is not present in the program, as long as
-    // the annotation will be in the output
+    // In the first round of tree shaking build up all metadata such that it can be traced later.
     boolean keepMetadata =
         kotlinMetadataClass == null
             || kotlinMetadataClass.isNotProgramClass()
             || enqueuer.isPinned(kotlinMetadataType);
+    if (enqueuer.getMode().isInitialTreeShaking()) {
+      Set<DexMethod> keepByteCodeFunctions = Sets.newIdentityHashSet();
+      enqueuer.forAllLiveClasses(
+          clazz -> {
+            boolean onlyProcessLambdas = !keepMetadata || !enqueuer.isPinned(clazz.type);
+            assert clazz.getKotlinInfo().isNoKotlinInformation();
+            clazz.setKotlinInfo(
+                KotlinClassMetadataReader.getKotlinInfo(
+                    appView.dexItemFactory().kotlin,
+                    clazz,
+                    definitionSupplier.dexItemFactory(),
+                    appView.options().reporter,
+                    onlyProcessLambdas,
+                    method -> keepByteCodeFunctions.add(method.method)));
+          });
+      appView.setCfByteCodePassThrough(keepByteCodeFunctions);
+    } else {
+      assert verifyKotlinMetadataModeledForAllClasses(enqueuer, keepMetadata);
+    }
+    // Trace through the modeled kotlin metadata.
     enqueuer.forAllLiveClasses(
         clazz -> {
-          clazz.setKotlinInfo(
-              KotlinClassMetadataReader.getKotlinInfo(
-                  appView.dexItemFactory().kotlin,
-                  clazz,
-                  definitionSupplier,
-                  appView.options().reporter,
-                  !keepMetadata || !enqueuer.isPinned(clazz.type),
-                  method -> keepByteCodeFunctions.add(method.method)));
+          clazz.getKotlinInfo().trace(definitionSupplier);
+          forEachApply(
+              clazz.methods(), method -> method.getKotlinMemberInfo()::trace, definitionSupplier);
+          forEachApply(
+              clazz.fields(), field -> field.getKotlinMemberInfo()::trace, definitionSupplier);
         });
-    appView.setCfByteCodePassThrough(keepByteCodeFunctions);
+  }
+
+  private boolean verifyKotlinMetadataModeledForAllClasses(
+      Enqueuer enqueuer, boolean keepMetadata) {
+    enqueuer.forAllLiveClasses(
+        clazz -> {
+          // Trace through class and member definitions
+          assert !hasKotlinClassMetadataAnnotation(clazz, definitionSupplier)
+              || !keepMetadata
+              || !enqueuer.isPinned(clazz.type)
+              || clazz.getKotlinInfo() != NO_KOTLIN_INFO;
+        });
+    return true;
+  }
+
+  public static class KotlinMetadataDefinitionSupplier implements DexDefinitionSupplier {
+
+    private final DexDefinitionSupplier baseSupplier;
+    private final Set<DexType> prunedTypes;
+
+    private KotlinMetadataDefinitionSupplier(
+        DexDefinitionSupplier baseSupplier, Set<DexType> prunedTypes) {
+      this.baseSupplier = baseSupplier;
+      this.prunedTypes = prunedTypes;
+    }
+
+    @Override
+    public DexDefinition definitionFor(DexReference reference) {
+      throw new Unreachable("Should not be called");
+    }
+
+    @Override
+    public DexEncodedField definitionFor(DexField field) {
+      throw new Unreachable("Should not be called");
+    }
+
+    @Override
+    public DexEncodedMethod definitionFor(DexMethod method) {
+      throw new Unreachable("Should not be called");
+    }
+
+    @Override
+    public DexClass definitionFor(DexType type) {
+      // TODO(b/157700128) Metadata cannot at this point keep anything alive. Therefore, if a type
+      //  has been pruned it may still be referenced, so we do an early check here to ensure it will
+      //  not end up as. Ideally, those types should be removed by a pass on the modeled data.
+      if (prunedTypes != null && prunedTypes.contains(type)) {
+        return null;
+      }
+      return baseSupplier.definitionFor(type);
+    }
+
+    @Override
+    public DexProgramClass definitionForProgramType(DexType type) {
+      throw new Unreachable("Should not be called");
+    }
+
+    @Override
+    public DexItemFactory dexItemFactory() {
+      return baseSupplier.dexItemFactory();
+    }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataUtils.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataUtils.java
index 1f21451..1ee78a5 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataUtils.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMetadataUtils.java
@@ -12,7 +12,6 @@
 import com.android.tools.r8.graph.DexField;
 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.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
@@ -59,6 +58,16 @@
     public String getPackageName() {
       throw new Unreachable("Should never be called");
     }
+
+    @Override
+    public boolean isNoKotlinInformation() {
+      return true;
+    }
+
+    @Override
+    public void trace(DexDefinitionSupplier definitionSupplier) {
+      // No information needed to trace.
+    }
   }
 
   static JvmFieldSignature toJvmFieldSignature(DexField field) {
@@ -137,41 +146,6 @@
     }
   }
 
-  static String toRenamedDescriptorOrDefault(
-      DexType type,
-      AppView<AppInfoWithLiveness> appView,
-      NamingLens namingLens,
-      String defaultValue) {
-    if (appView.appInfo().wasPruned(type)) {
-      return defaultValue;
-    }
-    DexString descriptor = namingLens.lookupDescriptor(type);
-    if (descriptor != null) {
-      return descriptor.toString();
-    }
-    return defaultValue;
-  }
-
-  static String kotlinNameFromDescriptor(DexString descriptor) {
-    return DescriptorUtils.getBinaryNameFromDescriptor(descriptor.toString());
-  }
-
-  static DexType referenceTypeFromBinaryName(
-      String binaryName, DexDefinitionSupplier definitionSupplier) {
-    return referenceTypeFromDescriptor(
-        DescriptorUtils.getDescriptorFromClassBinaryName(binaryName), definitionSupplier);
-  }
-
-  static DexType referenceTypeFromDescriptor(
-      String descriptor, DexDefinitionSupplier definitionSupplier) {
-    DexType type = definitionSupplier.dexItemFactory().createType(descriptor);
-    // Lookup the definition, ignoring the result. This populates the sets in the Enqueuer.
-    if (type.isClassType()) {
-      definitionSupplier.definitionFor(type);
-    }
-    return type;
-  }
-
   public static boolean mayProcessKotlinMetadata(AppView<?> appView) {
     // This can run before we have determined the pinned items, because we may need to load the
     // stack-map table on input. This is therefore a conservative guess on kotlin.Metadata is kept.
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMethodLevelInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMethodLevelInfo.java
index 604374e..a02cb0a 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMethodLevelInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMethodLevelInfo.java
@@ -4,7 +4,9 @@
 
 package com.android.tools.r8.kotlin;
 
-public interface KotlinMethodLevelInfo {
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
+
+public interface KotlinMethodLevelInfo extends EnqueuerMetadataTraceable {
 
   default boolean isConstructor() {
     return false;
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMultiFileClassFacadeInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMultiFileClassFacadeInfo.java
index 3baea9c..1ccd35f 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMultiFileClassFacadeInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMultiFileClassFacadeInfo.java
@@ -4,14 +4,14 @@
 
 package com.android.tools.r8.kotlin;
 
+import static com.android.tools.r8.utils.FunctionUtils.forEachApply;
+
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
-import com.android.tools.r8.graph.DexString;
-import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import com.android.tools.r8.utils.DescriptorUtils;
 import com.google.common.collect.ImmutableList;
 import java.util.ArrayList;
 import java.util.List;
@@ -22,23 +22,20 @@
 // Holds information about Metadata.MultiFileClassFace
 public class KotlinMultiFileClassFacadeInfo implements KotlinClassLevelInfo {
 
-  private final List<DexType> partClassNames;
+  private final List<KotlinTypeReference> partClassNames;
   private final String packageName;
 
-  private KotlinMultiFileClassFacadeInfo(List<DexType> partClassNames, String packageName) {
+  private KotlinMultiFileClassFacadeInfo(
+      List<KotlinTypeReference> partClassNames, String packageName) {
     this.partClassNames = partClassNames;
     this.packageName = packageName;
   }
 
   static KotlinMultiFileClassFacadeInfo create(
-      MultiFileClassFacade kmMultiFileClassFacade,
-      String packageName,
-      DexDefinitionSupplier definitionSupplier) {
-    ImmutableList.Builder<DexType> builder = ImmutableList.builder();
+      MultiFileClassFacade kmMultiFileClassFacade, String packageName, DexItemFactory factory) {
+    ImmutableList.Builder<KotlinTypeReference> builder = ImmutableList.builder();
     for (String partClassName : kmMultiFileClassFacade.getPartClassNames()) {
-      String descriptor = DescriptorUtils.getDescriptorFromClassBinaryName(partClassName);
-      DexType type = definitionSupplier.dexItemFactory().createType(descriptor);
-      builder.add(type);
+      builder.add(KotlinTypeReference.fromBinaryName(partClassName, factory));
     }
     return new KotlinMultiFileClassFacadeInfo(builder.build(), packageName);
   }
@@ -59,11 +56,10 @@
     KotlinClassMetadata.MultiFileClassFacade.Writer writer =
         new KotlinClassMetadata.MultiFileClassFacade.Writer();
     List<String> partClassNameStrings = new ArrayList<>(partClassNames.size());
-    for (DexType partClassName : partClassNames) {
-      if (appView.appInfo().isNonProgramTypeOrLiveProgramType(partClassName)) {
-        DexString descriptor = namingLens.lookupDescriptor(partClassName);
-        String classifier = DescriptorUtils.descriptorToKotlinClassifier(descriptor.toString());
-        partClassNameStrings.add(classifier);
+    for (KotlinTypeReference partClassName : partClassNames) {
+      String binaryName = partClassName.toRenamedBinaryNameOrDefault(appView, namingLens, null);
+      if (binaryName != null) {
+        partClassNameStrings.add(binaryName);
       }
     }
     return writer.write(partClassNameStrings).getHeader();
@@ -73,4 +69,9 @@
   public String getPackageName() {
     return packageName;
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    forEachApply(partClassNames, type -> type::trace, definitionSupplier);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMultiFileClassPartInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMultiFileClassPartInfo.java
index d4ec800..9470082 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMultiFileClassPartInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMultiFileClassPartInfo.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.Reporter;
@@ -20,6 +21,7 @@
 // Holds information about Metadata.MultiFileClassPartInfo
 public class KotlinMultiFileClassPartInfo implements KotlinClassLevelInfo {
 
+  // TODO(b/157630779): Maybe model facadeClassName.
   private final String facadeClassName;
   private final KotlinPackageInfo packageInfo;
   private final String packageName;
@@ -35,13 +37,12 @@
       MultiFileClassPart classPart,
       String packageName,
       DexClass clazz,
-      DexDefinitionSupplier definitionSupplier,
+      DexItemFactory factory,
       Reporter reporter,
       Consumer<DexEncodedMethod> keepByteCode) {
     return new KotlinMultiFileClassPartInfo(
         classPart.getFacadeClassName(),
-        KotlinPackageInfo.create(
-            classPart.toKmPackage(), clazz, definitionSupplier, reporter, keepByteCode),
+        KotlinPackageInfo.create(classPart.toKmPackage(), clazz, factory, reporter, keepByteCode),
         packageName);
   }
 
@@ -70,4 +71,9 @@
   public String getPackageName() {
     return packageName;
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    packageInfo.trace(definitionSupplier);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinPackageInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinPackageInfo.java
index d98e109..8f0268a 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinPackageInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinPackageInfo.java
@@ -12,8 +12,10 @@
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import com.android.tools.r8.utils.Reporter;
 import java.util.HashMap;
 import java.util.Map;
@@ -22,7 +24,7 @@
 import kotlinx.metadata.jvm.JvmExtensionsKt;
 
 // Holds information about a KmPackage object.
-public class KotlinPackageInfo {
+public class KotlinPackageInfo implements EnqueuerMetadataTraceable {
 
   private final String moduleName;
   private final KotlinDeclarationContainerInfo containerInfo;
@@ -35,7 +37,7 @@
   public static KotlinPackageInfo create(
       KmPackage kmPackage,
       DexClass clazz,
-      DexDefinitionSupplier definitionSupplier,
+      DexItemFactory factory,
       Reporter reporter,
       Consumer<DexEncodedMethod> keepByteCode) {
     Map<String, DexEncodedField> fieldMap = new HashMap<>();
@@ -49,7 +51,7 @@
     return new KotlinPackageInfo(
         JvmExtensionsKt.getModuleName(kmPackage),
         KotlinDeclarationContainerInfo.create(
-            kmPackage, methodMap, fieldMap, definitionSupplier, reporter, keepByteCode));
+            kmPackage, methodMap, fieldMap, factory, reporter, keepByteCode));
   }
 
   public void rewrite(
@@ -66,4 +68,9 @@
         namingLens);
     JvmExtensionsKt.setModuleName(kmPackage, moduleName);
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    containerInfo.trace(definitionSupplier);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinPropertyInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinPropertyInfo.java
index 802428a..94afee8 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinPropertyInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinPropertyInfo.java
@@ -4,10 +4,13 @@
 
 package com.android.tools.r8.kotlin;
 
+import static com.android.tools.r8.utils.FunctionUtils.forEachApply;
+
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.Reporter;
@@ -81,27 +84,24 @@
   }
 
   public static KotlinPropertyInfo create(
-      KmProperty kmProperty, DexDefinitionSupplier definitionSupplier, Reporter reporter) {
+      KmProperty kmProperty, DexItemFactory factory, Reporter reporter) {
     return new KotlinPropertyInfo(
         kmProperty.getFlags(),
         kmProperty.getGetterFlags(),
         kmProperty.getSetterFlags(),
         kmProperty.getName(),
-        KotlinTypeInfo.create(kmProperty.getReturnType(), definitionSupplier, reporter),
-        KotlinTypeInfo.create(kmProperty.getReceiverParameterType(), definitionSupplier, reporter),
-        KotlinValueParameterInfo.create(
-            kmProperty.getSetterParameter(), definitionSupplier, reporter),
-        KotlinTypeParameterInfo.create(
-            kmProperty.getTypeParameters(), definitionSupplier, reporter),
+        KotlinTypeInfo.create(kmProperty.getReturnType(), factory, reporter),
+        KotlinTypeInfo.create(kmProperty.getReceiverParameterType(), factory, reporter),
+        KotlinValueParameterInfo.create(kmProperty.getSetterParameter(), factory, reporter),
+        KotlinTypeParameterInfo.create(kmProperty.getTypeParameters(), factory, reporter),
         JvmExtensionsKt.getJvmFlags(kmProperty),
-        KotlinJvmFieldSignatureInfo.create(
-            JvmExtensionsKt.getFieldSignature(kmProperty), definitionSupplier),
+        KotlinJvmFieldSignatureInfo.create(JvmExtensionsKt.getFieldSignature(kmProperty), factory),
         KotlinJvmMethodSignatureInfo.create(
-            JvmExtensionsKt.getGetterSignature(kmProperty), definitionSupplier),
+            JvmExtensionsKt.getGetterSignature(kmProperty), factory),
         KotlinJvmMethodSignatureInfo.create(
-            JvmExtensionsKt.getSetterSignature(kmProperty), definitionSupplier),
+            JvmExtensionsKt.getSetterSignature(kmProperty), factory),
         KotlinJvmMethodSignatureInfo.create(
-            JvmExtensionsKt.getSyntheticMethodForAnnotations(kmProperty), definitionSupplier));
+            JvmExtensionsKt.getSyntheticMethodForAnnotations(kmProperty), factory));
   }
 
   @Override
@@ -160,4 +160,30 @@
       }
     }
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    if (returnType != null) {
+      returnType.trace(definitionSupplier);
+    }
+    if (receiverParameterType != null) {
+      receiverParameterType.trace(definitionSupplier);
+    }
+    if (setterParameter != null) {
+      setterParameter.trace(definitionSupplier);
+    }
+    forEachApply(typeParameters, param -> param::trace, definitionSupplier);
+    if (fieldSignature != null) {
+      fieldSignature.trace(definitionSupplier);
+    }
+    if (getterSignature != null) {
+      getterSignature.trace(definitionSupplier);
+    }
+    if (setterSignature != null) {
+      setterSignature.trace(definitionSupplier);
+    }
+    if (syntheticMethodForAnnotations != null) {
+      syntheticMethodForAnnotations.trace(definitionSupplier);
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClassInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClassInfo.java
index 38933b5..5af2a4c 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClassInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClassInfo.java
@@ -7,6 +7,7 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.Reporter;
@@ -41,7 +42,7 @@
       String packageName,
       DexClass clazz,
       Kotlin kotlin,
-      DexDefinitionSupplier definitionSupplier,
+      DexItemFactory factory,
       Reporter reporter) {
     KmLambda lambda = null;
     if (syntheticClass.isLambda()) {
@@ -49,9 +50,7 @@
       assert lambda != null;
     }
     return new KotlinSyntheticClassInfo(
-        lambda != null
-            ? KotlinLambdaInfo.create(clazz, lambda, definitionSupplier, reporter)
-            : null,
+        lambda != null ? KotlinLambdaInfo.create(clazz, lambda, factory, reporter) : null,
         getFlavour(syntheticClass, clazz, kotlin),
         packageName);
   }
@@ -92,6 +91,13 @@
   }
 
   @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    if (lambda != null) {
+      lambda.trace(definitionSupplier);
+    }
+  }
+
+  @Override
   public String getPackageName() {
     return packageName;
   }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinTypeAliasInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinTypeAliasInfo.java
index b4b5354..3872963 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinTypeAliasInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinTypeAliasInfo.java
@@ -4,17 +4,21 @@
 
 package com.android.tools.r8.kotlin;
 
+import static com.android.tools.r8.utils.FunctionUtils.forEachApply;
+
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import com.android.tools.r8.utils.Reporter;
 import java.util.List;
 import kotlinx.metadata.KmTypeAlias;
 import kotlinx.metadata.KmTypeAliasVisitor;
 
 // Holds information about KmTypeAlias
-public class KotlinTypeAliasInfo {
+public class KotlinTypeAliasInfo implements EnqueuerMetadataTraceable {
 
   private final int flags;
   private final String name;
@@ -41,14 +45,14 @@
   }
 
   public static KotlinTypeAliasInfo create(
-      KmTypeAlias alias, DexDefinitionSupplier definitionSupplier, Reporter reporter) {
+      KmTypeAlias alias, DexItemFactory factory, Reporter reporter) {
     return new KotlinTypeAliasInfo(
         alias.getFlags(),
         alias.getName(),
-        KotlinTypeInfo.create(alias.underlyingType, definitionSupplier, reporter),
-        KotlinTypeInfo.create(alias.expandedType, definitionSupplier, reporter),
-        KotlinTypeParameterInfo.create(alias.getTypeParameters(), definitionSupplier, reporter),
-        KotlinAnnotationInfo.create(alias.getAnnotations(), definitionSupplier));
+        KotlinTypeInfo.create(alias.underlyingType, factory, reporter),
+        KotlinTypeInfo.create(alias.expandedType, factory, reporter),
+        KotlinTypeParameterInfo.create(alias.getTypeParameters(), factory, reporter),
+        KotlinAnnotationInfo.create(alias.getAnnotations(), factory));
   }
 
   void rewrite(
@@ -65,4 +69,12 @@
       annotation.rewrite(kmTypeAliasVisitor::visitAnnotation, appView, namingLens);
     }
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    underlyingType.trace(definitionSupplier);
+    expandedType.trace(definitionSupplier);
+    forEachApply(typeParameters, typeParam -> typeParam::trace, definitionSupplier);
+    forEachApply(annotations, annotation -> annotation::trace, definitionSupplier);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinTypeInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinTypeInfo.java
index 8601667..f21db98 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinTypeInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinTypeInfo.java
@@ -4,10 +4,14 @@
 
 package com.android.tools.r8.kotlin;
 
+import static com.android.tools.r8.utils.FunctionUtils.forEachApply;
+
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import com.android.tools.r8.utils.Reporter;
 import com.google.common.collect.ImmutableList;
 import java.util.List;
@@ -18,7 +22,7 @@
 import kotlinx.metadata.jvm.JvmTypeExtensionVisitor;
 
 // Provides access to Kotlin information about a kotlin type.
-public class KotlinTypeInfo {
+public class KotlinTypeInfo implements EnqueuerMetadataTraceable {
 
   private static final List<KotlinTypeProjectionInfo> EMPTY_ARGUMENTS = ImmutableList.of();
 
@@ -47,32 +51,29 @@
     this.flexibleTypeUpperBoundInfo = flexibleTypeUpperBoundInfo;
   }
 
-  static KotlinTypeInfo create(
-      KmType kmType, DexDefinitionSupplier definitionSupplier, Reporter reporter) {
+  static KotlinTypeInfo create(KmType kmType, DexItemFactory factory, Reporter reporter) {
     if (kmType == null) {
       return null;
     }
     return new KotlinTypeInfo(
         kmType.getFlags(),
-        KotlinClassifierInfo.create(kmType.classifier, definitionSupplier, reporter),
-        KotlinTypeInfo.create(kmType.getAbbreviatedType(), definitionSupplier, reporter),
-        KotlinTypeInfo.create(kmType.getOuterType(), definitionSupplier, reporter),
-        getArguments(kmType.getArguments(), definitionSupplier, reporter),
-        KotlinAnnotationInfo.create(JvmExtensionsKt.getAnnotations(kmType), definitionSupplier),
+        KotlinClassifierInfo.create(kmType.classifier, factory, reporter),
+        KotlinTypeInfo.create(kmType.getAbbreviatedType(), factory, reporter),
+        KotlinTypeInfo.create(kmType.getOuterType(), factory, reporter),
+        getArguments(kmType.getArguments(), factory, reporter),
+        KotlinAnnotationInfo.create(JvmExtensionsKt.getAnnotations(kmType), factory),
         KotlinFlexibleTypeUpperBoundInfo.create(
-            kmType.getFlexibleTypeUpperBound(), definitionSupplier, reporter));
+            kmType.getFlexibleTypeUpperBound(), factory, reporter));
   }
 
   static List<KotlinTypeProjectionInfo> getArguments(
-      List<KmTypeProjection> projections,
-      DexDefinitionSupplier definitionSupplier,
-      Reporter reporter) {
+      List<KmTypeProjection> projections, DexItemFactory factory, Reporter reporter) {
     if (projections.isEmpty()) {
       return EMPTY_ARGUMENTS;
     }
     ImmutableList.Builder<KotlinTypeProjectionInfo> arguments = ImmutableList.builder();
     for (KmTypeProjection projection : projections) {
-      arguments.add(KotlinTypeProjectionInfo.create(projection, definitionSupplier, reporter));
+      arguments.add(KotlinTypeProjectionInfo.create(projection, factory, reporter));
     }
     return arguments.build();
   }
@@ -107,4 +108,18 @@
       }
     }
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    classifier.trace(definitionSupplier);
+    if (abbreviatedType != null) {
+      abbreviatedType.trace(definitionSupplier);
+    }
+    if (outerType != null) {
+      outerType.trace(definitionSupplier);
+    }
+    forEachApply(arguments, argument -> argument::trace, definitionSupplier);
+    flexibleTypeUpperBoundInfo.trace(definitionSupplier);
+    forEachApply(annotations, annotation -> annotation::trace, definitionSupplier);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinTypeParameterInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinTypeParameterInfo.java
index fd11c11..53c2eb2 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinTypeParameterInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinTypeParameterInfo.java
@@ -4,10 +4,14 @@
 
 package com.android.tools.r8.kotlin;
 
+import static com.android.tools.r8.utils.FunctionUtils.forEachApply;
+
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import com.android.tools.r8.utils.Reporter;
 import com.google.common.collect.ImmutableList;
 import java.util.List;
@@ -19,7 +23,7 @@
 import kotlinx.metadata.jvm.JvmTypeParameterExtensionVisitor;
 
 // Provides access to Kotlin information about a type-parameter.
-public class KotlinTypeParameterInfo {
+public class KotlinTypeParameterInfo implements EnqueuerMetadataTraceable {
 
   private static final List<KotlinTypeParameterInfo> EMPTY_TYPE_PARAMETERS = ImmutableList.of();
   private static final List<KotlinTypeInfo> EMPTY_UPPER_BOUNDS = ImmutableList.of();
@@ -47,41 +51,36 @@
   }
 
   private static KotlinTypeParameterInfo create(
-      KmTypeParameter kmTypeParameter,
-      DexDefinitionSupplier definitionSupplier,
-      Reporter reporter) {
+      KmTypeParameter kmTypeParameter, DexItemFactory factory, Reporter reporter) {
     return new KotlinTypeParameterInfo(
         kmTypeParameter.getFlags(),
         kmTypeParameter.getId(),
         kmTypeParameter.getName(),
         kmTypeParameter.getVariance(),
-        getUpperBounds(kmTypeParameter.getUpperBounds(), definitionSupplier, reporter),
-        KotlinAnnotationInfo.create(
-            JvmExtensionsKt.getAnnotations(kmTypeParameter), definitionSupplier));
+        getUpperBounds(kmTypeParameter.getUpperBounds(), factory, reporter),
+        KotlinAnnotationInfo.create(JvmExtensionsKt.getAnnotations(kmTypeParameter), factory));
   }
 
   static List<KotlinTypeParameterInfo> create(
-      List<KmTypeParameter> kmTypeParameters,
-      DexDefinitionSupplier definitionSupplier,
-      Reporter reporter) {
+      List<KmTypeParameter> kmTypeParameters, DexItemFactory factory, Reporter reporter) {
     if (kmTypeParameters.isEmpty()) {
       return EMPTY_TYPE_PARAMETERS;
     }
     ImmutableList.Builder<KotlinTypeParameterInfo> builder = ImmutableList.builder();
     for (KmTypeParameter kmTypeParameter : kmTypeParameters) {
-      builder.add(create(kmTypeParameter, definitionSupplier, reporter));
+      builder.add(create(kmTypeParameter, factory, reporter));
     }
     return builder.build();
   }
 
   private static List<KotlinTypeInfo> getUpperBounds(
-      List<KmType> upperBounds, DexDefinitionSupplier definitionSupplier, Reporter reporter) {
+      List<KmType> upperBounds, DexItemFactory factory, Reporter reporter) {
     if (upperBounds.isEmpty()) {
       return EMPTY_UPPER_BOUNDS;
     }
     ImmutableList.Builder<KotlinTypeInfo> builder = ImmutableList.builder();
     for (KmType upperBound : upperBounds) {
-      builder.add(KotlinTypeInfo.create(upperBound, definitionSupplier, reporter));
+      builder.add(KotlinTypeInfo.create(upperBound, factory, reporter));
     }
     return builder.build();
   }
@@ -104,4 +103,10 @@
       annotation.rewrite(extensionVisitor::visitAnnotation, appView, namingLens);
     }
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    forEachApply(originalUpperBounds, upperBound -> upperBound::trace, definitionSupplier);
+    forEachApply(annotations, annotation -> annotation::trace, definitionSupplier);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinTypeProjectionInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinTypeProjectionInfo.java
index 68da5db..9ab3de0 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinTypeProjectionInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinTypeProjectionInfo.java
@@ -6,14 +6,16 @@
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import com.android.tools.r8.utils.Reporter;
 import kotlinx.metadata.KmTypeProjection;
 import kotlinx.metadata.KmVariance;
 
 // Provides access to Kotlin information about the type projection of a type (arguments).
-public class KotlinTypeProjectionInfo {
+public class KotlinTypeProjectionInfo implements EnqueuerMetadataTraceable {
 
   final KmVariance variance;
   final KotlinTypeInfo typeInfo;
@@ -24,12 +26,10 @@
   }
 
   static KotlinTypeProjectionInfo create(
-      KmTypeProjection kmTypeProjection,
-      DexDefinitionSupplier definitionSupplier,
-      Reporter reporter) {
+      KmTypeProjection kmTypeProjection, DexItemFactory factory, Reporter reporter) {
     return new KotlinTypeProjectionInfo(
         kmTypeProjection.getVariance(),
-        KotlinTypeInfo.create(kmTypeProjection.getType(), definitionSupplier, reporter));
+        KotlinTypeInfo.create(kmTypeProjection.getType(), factory, reporter));
   }
 
   private boolean isStarProjection() {
@@ -47,4 +47,11 @@
       typeInfo.rewrite(flags -> visitorProvider.get(flags, variance), appView, namingLens);
     }
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    if (typeInfo != null) {
+      typeInfo.trace(definitionSupplier);
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinTypeReference.java b/src/main/java/com/android/tools/r8/kotlin/KotlinTypeReference.java
new file mode 100644
index 0000000..f621afb
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinTypeReference.java
@@ -0,0 +1,102 @@
+// 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.kotlin;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexDefinitionSupplier;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.naming.NamingLens;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
+import com.android.tools.r8.utils.DescriptorUtils;
+
+/**
+ * To account for invalid type references in kotlin metadata, the class KotlinTypeReference will
+ * either hold a DexType reference, or a String, with the original name reference, which is not a
+ * valid jvm descriptor/name. The values will be disjoint.
+ */
+class KotlinTypeReference implements EnqueuerMetadataTraceable {
+
+  private final DexType known;
+  private final String unknown;
+
+  private KotlinTypeReference(DexType known) {
+    this.known = known;
+    this.unknown = null;
+    assert known != null;
+  }
+
+  private KotlinTypeReference(String unknown) {
+    this.known = null;
+    this.unknown = unknown;
+    assert unknown != null;
+  }
+
+  static KotlinTypeReference fromBinaryName(String binaryName, DexItemFactory factory) {
+    if (DescriptorUtils.isValidBinaryName(binaryName)) {
+      return fromDescriptor(DescriptorUtils.getDescriptorFromClassBinaryName(binaryName), factory);
+    }
+    return new KotlinTypeReference(binaryName);
+  }
+
+  static KotlinTypeReference fromDescriptor(String descriptor, DexItemFactory factory) {
+    if (DescriptorUtils.isDescriptor(descriptor)) {
+      DexType type = factory.createType(descriptor);
+      return new KotlinTypeReference(type);
+    }
+    return new KotlinTypeReference(descriptor);
+  }
+
+  String toRenamedDescriptorOrDefault(
+      AppView<AppInfoWithLiveness> appView, NamingLens namingLens, String defaultValue) {
+    if (unknown != null) {
+      return unknown;
+    }
+    assert known != null;
+    if (!known.isClassType()) {
+      return known.descriptor.toString();
+    }
+    if (!appView.appInfo().isNonProgramTypeOrLiveProgramType(known)) {
+      return defaultValue;
+    }
+    DexString descriptor = namingLens.lookupDescriptor(known);
+    if (descriptor != null) {
+      return descriptor.toString();
+    }
+    return defaultValue;
+  }
+
+  String toRenamedBinaryNameOrDefault(
+      AppView<AppInfoWithLiveness> appView, NamingLens namingLens, String defaultValue) {
+    if (unknown != null) {
+      // Unknown values are always on the input form, so we can just return it.
+      return unknown;
+    }
+    String descriptor = toRenamedDescriptorOrDefault(appView, namingLens, defaultValue);
+    if (descriptor == null) {
+      return null;
+    }
+    if (descriptor.equals(defaultValue)) {
+      // We assume that the default value passed in is already a binary name.
+      return descriptor;
+    }
+    return DescriptorUtils.getBinaryNameFromDescriptor(descriptor);
+  }
+
+  @Override
+  public String toString() {
+    return known != null ? known.descriptor.toString() : unknown;
+  }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    if (known != null && known.isClassType()) {
+      // Lookup the definition, ignoring the result. This populates the sets in the Enqueuer.
+      definitionSupplier.definitionFor(known);
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinValueParameterInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinValueParameterInfo.java
index ee2f99b..bd7daac 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinValueParameterInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinValueParameterInfo.java
@@ -6,8 +6,10 @@
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexDefinitionSupplier;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
 import com.android.tools.r8.utils.Reporter;
 import com.google.common.collect.ImmutableList;
 import java.util.List;
@@ -16,7 +18,7 @@
 import kotlinx.metadata.KmValueParameterVisitor;
 
 // Provides access to Kotlin information about value parameter.
-class KotlinValueParameterInfo {
+class KotlinValueParameterInfo implements EnqueuerMetadataTraceable {
   private static final List<KotlinValueParameterInfo> EMPTY_VALUE_PARAMETERS = ImmutableList.of();
   // Original parameter name.
   final String name;
@@ -36,9 +38,7 @@
   }
 
   static KotlinValueParameterInfo create(
-      KmValueParameter kmValueParameter,
-      DexDefinitionSupplier definitionSupplier,
-      Reporter reporter) {
+      KmValueParameter kmValueParameter, DexItemFactory factory, Reporter reporter) {
     if (kmValueParameter == null) {
       return null;
     }
@@ -46,21 +46,18 @@
     return new KotlinValueParameterInfo(
         kmValueParameter.getFlags(),
         kmValueParameter.getName(),
-        KotlinTypeInfo.create(kmType, definitionSupplier, reporter),
-        KotlinTypeInfo.create(
-            kmValueParameter.getVarargElementType(), definitionSupplier, reporter));
+        KotlinTypeInfo.create(kmType, factory, reporter),
+        KotlinTypeInfo.create(kmValueParameter.getVarargElementType(), factory, reporter));
   }
 
   static List<KotlinValueParameterInfo> create(
-      List<KmValueParameter> parameters,
-      DexDefinitionSupplier definitionSupplier,
-      Reporter reporter) {
+      List<KmValueParameter> parameters, DexItemFactory factory, Reporter reporter) {
     if (parameters.isEmpty()) {
       return EMPTY_VALUE_PARAMETERS;
     }
     ImmutableList.Builder<KotlinValueParameterInfo> builder = ImmutableList.builder();
     for (KmValueParameter parameter : parameters) {
-      builder.add(create(parameter, definitionSupplier, reporter));
+      builder.add(create(parameter, factory, reporter));
     }
     return builder.build();
   }
@@ -76,4 +73,12 @@
           kmValueParameterVisitor::visitVarargElementType, appView, namingLens);
     }
   }
+
+  @Override
+  public void trace(DexDefinitionSupplier definitionSupplier) {
+    type.trace(definitionSupplier);
+    if (varargElementType != null) {
+      varargElementType.trace(definitionSupplier);
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 484786f..ff991cf 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -2634,9 +2634,10 @@
     this.dontWarnPatterns = dontWarnPatterns;
     // Translate the result of root-set computation into enqueuer actions.
     if (appView.options().getProguardConfiguration() != null
-        && !options.kotlinOptimizationOptions().disableKotlinSpecificOptimizations
-        && mode.isInitialTreeShaking()) {
-      registerAnalysis(new KotlinMetadataEnqueuerExtension(appView, enqueuerDefinitionSupplier));
+        && !options.kotlinOptimizationOptions().disableKotlinSpecificOptimizations) {
+      registerAnalysis(
+          new KotlinMetadataEnqueuerExtension(
+              appView, enqueuerDefinitionSupplier, initialPrunedTypes));
     }
     if (appView.options().isShrinking() || appView.options().getProguardConfiguration() == null) {
       enqueueRootItems(rootSet.noShrinking);
diff --git a/src/main/java/com/android/tools/r8/shaking/EnqueuerMetadataTraceable.java b/src/main/java/com/android/tools/r8/shaking/EnqueuerMetadataTraceable.java
new file mode 100644
index 0000000..e17e571
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/EnqueuerMetadataTraceable.java
@@ -0,0 +1,12 @@
+// 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.shaking;
+
+import com.android.tools.r8.graph.DexDefinitionSupplier;
+
+public interface EnqueuerMetadataTraceable {
+
+  void trace(DexDefinitionSupplier definitionSupplier);
+}
diff --git a/src/main/java/com/android/tools/r8/utils/DescriptorUtils.java b/src/main/java/com/android/tools/r8/utils/DescriptorUtils.java
index 196091e..2d78c0d 100644
--- a/src/main/java/com/android/tools/r8/utils/DescriptorUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/DescriptorUtils.java
@@ -369,13 +369,6 @@
     return 'L' + className.replace(JAVA_PACKAGE_SEPARATOR, INNER_CLASS_SEPARATOR) + ';';
   }
 
-  // TODO(b/151195430): Remove once a new version of kotlinx-metadata is released.
-  // Kotlin @Metadata deserialization has plain "kotlin", which will be relocated in r8lib.
-  // See b/70169921#comment25 for more details.
-  private static String backwardRelocatedName(String name) {
-    return name.replace("com/android/tools/r8/jetbrains/", "");
-  }
-
   /**
    * Get unqualified class name from its binary name.
    *
@@ -512,6 +505,11 @@
     return 'L' + descriptor + ';';
   }
 
+  public static boolean isValidBinaryName(String binaryName) {
+    return isValidJavaType(
+        binaryName.replace(DESCRIPTOR_PACKAGE_SEPARATOR, JAVA_PACKAGE_SEPARATOR));
+  }
+
   public static class ModuleAndDescriptor {
     private final String module;
     private final String descriptor;
diff --git a/src/main/java/com/android/tools/r8/utils/FunctionUtils.java b/src/main/java/com/android/tools/r8/utils/FunctionUtils.java
new file mode 100644
index 0000000..64e8537
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/FunctionUtils.java
@@ -0,0 +1,18 @@
+// 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.utils;
+
+import java.util.function.Consumer;
+import java.util.function.Function;
+
+public class FunctionUtils {
+
+  public static <T, R> void forEachApply(
+      Iterable<T> list, Function<T, Consumer<R>> func, R argument) {
+    for (T t : list) {
+      func.apply(t).accept(argument);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/kotlin/coroutines/KotlinxCoroutinesTestRunner.java b/src/test/java/com/android/tools/r8/kotlin/coroutines/KotlinxCoroutinesTestRunner.java
index f0179f8..7925c58 100644
--- a/src/test/java/com/android/tools/r8/kotlin/coroutines/KotlinxCoroutinesTestRunner.java
+++ b/src/test/java/com/android/tools/r8/kotlin/coroutines/KotlinxCoroutinesTestRunner.java
@@ -5,7 +5,6 @@
 package com.android.tools.r8.kotlin.coroutines;
 
 import static com.android.tools.r8.KotlinCompilerTool.KOTLINC;
-import static org.hamcrest.CoreMatchers.anyOf;
 import static org.hamcrest.CoreMatchers.containsString;
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assert.assertEquals;
@@ -88,16 +87,11 @@
             .addKeepAllAttributes()
             // The BASE_LIBRARY contains proguard rules that do not match.
             .allowUnusedProguardConfigurationRules()
-            .allowDiagnosticInfoMessages()
             .addKeepRules(
                 "-dontwarn reactor.blockhound.integration.BlockHoundIntegration",
                 "-dontwarn org.junit.runners.model.Statement",
                 "-dontwarn org.junit.rules.TestRule")
             .compile()
-            .assertAllInfoMessagesMatch(
-                anyOf(
-                    containsString("Unexpected error while reading kotlinx.coroutines"),
-                    containsString("Proguard configuration rule does not match anything")))
             .writeToZip();
     ProcessResult kotlincResult =
         kotlinc(KOTLINC, targetVersion)
diff --git a/src/test/java/com/android/tools/r8/shaking/b134858535/EventPublisherTest.java b/src/test/java/com/android/tools/r8/shaking/b134858535/EventPublisherTest.java
index d4801ea..23a5616 100644
--- a/src/test/java/com/android/tools/r8/shaking/b134858535/EventPublisherTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/b134858535/EventPublisherTest.java
@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.shaking.b134858535;
 
+import static org.hamcrest.CoreMatchers.containsString;
+
 import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.utils.AndroidApiLevel;
@@ -26,7 +28,13 @@
         .addProgramClassFileData(EventPublisher$bDump.dump())
         .addKeepClassRules(Interface.class)
         .addKeepMainRule(Main.class)
+        .allowDiagnosticInfoMessages()
         .setMinApi(AndroidApiLevel.L)
-        .compile();
+        .compile()
+        // TODO(b/157537996): Handle JStyle lambdas with private methods.
+        .assertAllInfoMessagesMatch(
+            containsString(
+                "Unrecognized Kotlin lambda"
+                    + " [com.android.tools.r8.shaking.b134858535.EventPublisher$b]"));
   }
 }