diff --git a/src/main/java/com/android/tools/r8/D8.java b/src/main/java/com/android/tools/r8/D8.java
index 8e44ee9..cdbcdd8 100644
--- a/src/main/java/com/android/tools/r8/D8.java
+++ b/src/main/java/com/android/tools/r8/D8.java
@@ -29,6 +29,7 @@
 import com.android.tools.r8.kotlin.KotlinMetadataRewriter;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.naming.PrefixRewritingNamingLens;
+import com.android.tools.r8.naming.RecordRewritingNamingLens;
 import com.android.tools.r8.naming.signature.GenericSignatureRewriter;
 import com.android.tools.r8.origin.CommandLineOrigin;
 import com.android.tools.r8.origin.Origin;
@@ -259,26 +260,22 @@
       Marker.checkCompatibleDesugaredLibrary(markers, options.reporter);
 
       InspectorImpl.runInspections(options.outputInspections, appView.appInfo().classes());
+      NamingLens namingLens = NamingLens.getIdentityLens();
+      if (appView.rewritePrefix.isRewriting()) {
+        namingLens = PrefixRewritingNamingLens.createPrefixRewritingNamingLens(appView, namingLens);
+      }
+      if (appView.options().shouldDesugarRecords()) {
+        namingLens = RecordRewritingNamingLens.createRecordRewritingNamingLens(appView, namingLens);
+      }
       if (options.isGeneratingClassFiles()) {
         // TODO(b/158159959): Move this out so it is shared for both CF and DEX pipelines.
         SyntheticFinalization.finalize(appView);
-        new CfApplicationWriter(
-                appView,
-                marker,
-                GraphLens.getIdentityLens(),
-                appView.rewritePrefix.isRewriting()
-                    ? PrefixRewritingNamingLens.createPrefixRewritingNamingLens(appView)
-                    : NamingLens.getIdentityLens(),
-                null)
+        new CfApplicationWriter(appView, marker, GraphLens.getIdentityLens(), namingLens, null)
             .write(options.getClassFileConsumer());
       } else {
-        NamingLens namingLens;
         if (!hasDexResources || !hasClassResources || !appView.rewritePrefix.isRewriting()) {
           // All inputs are either dex or cf, or there is nothing to rewrite.
-          namingLens =
-              hasDexResources
-                  ? NamingLens.getIdentityLens()
-                  : PrefixRewritingNamingLens.createPrefixRewritingNamingLens(appView);
+          namingLens = hasDexResources ? NamingLens.getIdentityLens() : namingLens;
           new GenericSignatureRewriter(appView, namingLens)
               .run(appView.appInfo().classes(), executor);
           new KotlinMetadataRewriter(appView, namingLens).runForD8(executor);
@@ -290,7 +287,13 @@
           timing.begin("Rewrite non-dex inputs");
           DexApplication app =
               rewriteNonDexInputs(
-                  appView, inputApp, options, executor, timing, appView.appInfo().app());
+                  appView,
+                  inputApp,
+                  options,
+                  executor,
+                  timing,
+                  appView.appInfo().app(),
+                  namingLens);
           timing.end();
           appView.setAppInfo(
               new AppInfo(
@@ -339,7 +342,8 @@
       InternalOptions options,
       ExecutorService executor,
       Timing timing,
-      DexApplication app)
+      DexApplication app,
+      NamingLens desugaringLens)
       throws IOException, ExecutionException {
     // TODO(b/154575955): Remove the naming lens in D8.
     appView
@@ -365,17 +369,15 @@
             appView.appInfo().getSyntheticItems().commit(cfApp),
             appView.appInfo().getMainDexInfo()));
     ConvertedCfFiles convertedCfFiles = new ConvertedCfFiles();
-    NamingLens prefixRewritingNamingLens =
-        PrefixRewritingNamingLens.createPrefixRewritingNamingLens(appView);
-    new GenericSignatureRewriter(appView, prefixRewritingNamingLens)
+    new GenericSignatureRewriter(appView, desugaringLens)
         .run(appView.appInfo().classes(), executor);
-    new KotlinMetadataRewriter(appView, prefixRewritingNamingLens).runForD8(executor);
+    new KotlinMetadataRewriter(appView, desugaringLens).runForD8(executor);
     new ApplicationWriter(
             appView,
             null,
             GraphLens.getIdentityLens(),
             InitClassLens.getDefault(),
-            prefixRewritingNamingLens,
+            desugaringLens,
             null,
             convertedCfFiles)
         .write(executor);
diff --git a/src/main/java/com/android/tools/r8/cf/CfPrinter.java b/src/main/java/com/android/tools/r8/cf/CfPrinter.java
index 09f14ce..9862f27 100644
--- a/src/main/java/com/android/tools/r8/cf/CfPrinter.java
+++ b/src/main/java/com/android/tools/r8/cf/CfPrinter.java
@@ -59,6 +59,7 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexMethodHandle;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexValue;
 import com.android.tools.r8.ir.code.If;
 import com.android.tools.r8.ir.code.MemberType;
 import com.android.tools.r8.ir.code.Monitor;
@@ -396,10 +397,14 @@
     builder.append(callSite.methodName);
     builder.append(callSite.methodProto.toDescriptorString());
     if (callSite.bootstrapArgs.size() > 1) {
-      DexMethodHandle handle = callSite.bootstrapArgs.get(1).asDexValueMethodHandle().getValue();
-      builder.append(", handle:");
-      builder.append(handle.toSourceString());
-      builder.append(", itf: ").append(handle.isInterface);
+      DexValue.DexValueMethodHandle dexValueMethodHandle =
+          callSite.bootstrapArgs.get(1).asDexValueMethodHandle();
+      if (dexValueMethodHandle != null) {
+        DexMethodHandle handle = dexValueMethodHandle.getValue();
+        builder.append(", handle:");
+        builder.append(handle.toSourceString());
+        builder.append(", itf: ").append(handle.isInterface);
+      }
     }
     builder.append(", bsm:");
     appendMethod(bootstrapMethod.asMethod());
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfCheckCast.java b/src/main/java/com/android/tools/r8/cf/code/CfCheckCast.java
index 277f2e2..1e25ca7 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfCheckCast.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfCheckCast.java
@@ -26,7 +26,7 @@
 import org.objectweb.asm.MethodVisitor;
 import org.objectweb.asm.Opcodes;
 
-public class CfCheckCast extends CfInstruction {
+public class CfCheckCast extends CfInstruction implements CfTypeInstruction {
 
   private final DexType type;
 
@@ -34,11 +34,27 @@
     this.type = type;
   }
 
+  @Override
+  public CfTypeInstruction asTypeInstruction() {
+    return this;
+  }
+
+  @Override
+  public boolean isTypeInstruction() {
+    return true;
+  }
+
+  @Override
   public DexType getType() {
     return type;
   }
 
   @Override
+  public CfInstruction withType(DexType newType) {
+    return new CfCheckCast(newType);
+  }
+
+  @Override
   public int getCompareToId() {
     return Opcodes.CHECKCAST;
   }
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfConstClass.java b/src/main/java/com/android/tools/r8/cf/code/CfConstClass.java
index 863dce0..a6a0933 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfConstClass.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfConstClass.java
@@ -26,7 +26,7 @@
 import org.objectweb.asm.MethodVisitor;
 import org.objectweb.asm.Type;
 
-public class CfConstClass extends CfInstruction {
+public class CfConstClass extends CfInstruction implements CfTypeInstruction {
 
   private final DexType type;
 
@@ -45,11 +45,27 @@
     return type.acceptCompareTo(((CfConstClass) other).type, visitor);
   }
 
+  @Override
+  public CfTypeInstruction asTypeInstruction() {
+    return this;
+  }
+
+  @Override
+  public boolean isTypeInstruction() {
+    return true;
+  }
+
+  @Override
   public DexType getType() {
     return type;
   }
 
   @Override
+  public CfInstruction withType(DexType newType) {
+    return new CfConstClass(newType);
+  }
+
+  @Override
   public void write(
       AppView<?> appView,
       ProgramMethod context,
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfInitClass.java b/src/main/java/com/android/tools/r8/cf/code/CfInitClass.java
index 815500d..0b8240a 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfInitClass.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfInitClass.java
@@ -55,6 +55,11 @@
   }
 
   @Override
+  public boolean isInitClass() {
+    return true;
+  }
+
+  @Override
   public void write(
       AppView<?> appView,
       ProgramMethod context,
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfInstanceOf.java b/src/main/java/com/android/tools/r8/cf/code/CfInstanceOf.java
index 3cc1f4b..b4d6d43 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfInstanceOf.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfInstanceOf.java
@@ -25,7 +25,7 @@
 import org.objectweb.asm.MethodVisitor;
 import org.objectweb.asm.Opcodes;
 
-public class CfInstanceOf extends CfInstruction {
+public class CfInstanceOf extends CfInstruction implements CfTypeInstruction {
 
   private final DexType type;
 
@@ -33,11 +33,27 @@
     this.type = type;
   }
 
+  @Override
+  public CfTypeInstruction asTypeInstruction() {
+    return this;
+  }
+
+  @Override
+  public boolean isTypeInstruction() {
+    return true;
+  }
+
+  @Override
   public DexType getType() {
     return type;
   }
 
   @Override
+  public CfInstruction withType(DexType newType) {
+    return new CfInstanceOf(newType);
+  }
+
+  @Override
   public int getCompareToId() {
     return Opcodes.INSTANCEOF;
   }
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfInstruction.java b/src/main/java/com/android/tools/r8/cf/code/CfInstruction.java
index c69ba09..1009080 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfInstruction.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfInstruction.java
@@ -221,6 +221,18 @@
     return false;
   }
 
+  public CfTypeInstruction asTypeInstruction() {
+    return null;
+  }
+
+  public boolean isTypeInstruction() {
+    return false;
+  }
+
+  public boolean isInitClass() {
+    return false;
+  }
+
   public CfDexItemBasedConstString asDexItemBasedConstString() {
     return null;
   }
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfMultiANewArray.java b/src/main/java/com/android/tools/r8/cf/code/CfMultiANewArray.java
index bac5536..682c857 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfMultiANewArray.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfMultiANewArray.java
@@ -27,7 +27,7 @@
 import org.objectweb.asm.MethodVisitor;
 import org.objectweb.asm.Opcodes;
 
-public class CfMultiANewArray extends CfInstruction {
+public class CfMultiANewArray extends CfInstruction implements CfTypeInstruction {
 
   private final DexType type;
   private final int dimensions;
@@ -41,10 +41,26 @@
     this.dimensions = dimensions;
   }
 
+  @Override
+  public CfTypeInstruction asTypeInstruction() {
+    return this;
+  }
+
+  @Override
+  public boolean isTypeInstruction() {
+    return true;
+  }
+
+  @Override
   public DexType getType() {
     return type;
   }
 
+  @Override
+  public CfInstruction withType(DexType newType) {
+    return new CfMultiANewArray(newType, dimensions);
+  }
+
   public int getDimensions() {
     return dimensions;
   }
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfNew.java b/src/main/java/com/android/tools/r8/cf/code/CfNew.java
index 7140404..53fc40c 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfNew.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfNew.java
@@ -26,7 +26,7 @@
 import org.objectweb.asm.MethodVisitor;
 import org.objectweb.asm.Opcodes;
 
-public class CfNew extends CfInstruction {
+public class CfNew extends CfInstruction implements CfTypeInstruction {
 
   private final DexType type;
 
@@ -34,11 +34,27 @@
     this.type = type;
   }
 
+  @Override
+  public CfTypeInstruction asTypeInstruction() {
+    return this;
+  }
+
+  @Override
+  public boolean isTypeInstruction() {
+    return true;
+  }
+
+  @Override
   public DexType getType() {
     return type;
   }
 
   @Override
+  public CfInstruction withType(DexType newType) {
+    return new CfNew(newType);
+  }
+
+  @Override
   public int getCompareToId() {
     return Opcodes.NEW;
   }
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfNewArray.java b/src/main/java/com/android/tools/r8/cf/code/CfNewArray.java
index 78200b7..ad50c17 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfNewArray.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfNewArray.java
@@ -28,7 +28,7 @@
 import org.objectweb.asm.MethodVisitor;
 import org.objectweb.asm.Opcodes;
 
-public class CfNewArray extends CfInstruction {
+public class CfNewArray extends CfInstruction implements CfTypeInstruction {
 
   private final DexType type;
 
@@ -37,11 +37,27 @@
     this.type = type;
   }
 
+  @Override
+  public CfTypeInstruction asTypeInstruction() {
+    return this;
+  }
+
+  @Override
+  public boolean isTypeInstruction() {
+    return true;
+  }
+
+  @Override
   public DexType getType() {
     return type;
   }
 
   @Override
+  public CfInstruction withType(DexType newType) {
+    return new CfNewArray(newType);
+  }
+
+  @Override
   public int getCompareToId() {
     return type.isPrimitiveArrayType() ? Opcodes.NEWARRAY : Opcodes.ANEWARRAY;
   }
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfTypeInstruction.java b/src/main/java/com/android/tools/r8/cf/code/CfTypeInstruction.java
new file mode 100644
index 0000000..1762c7a
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/cf/code/CfTypeInstruction.java
@@ -0,0 +1,14 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.cf.code;
+
+import com.android.tools.r8.graph.DexType;
+
+public interface CfTypeInstruction {
+
+  DexType getType();
+
+  CfInstruction withType(DexType newType);
+}
diff --git a/src/main/java/com/android/tools/r8/graph/ClassAccessFlags.java b/src/main/java/com/android/tools/r8/graph/ClassAccessFlags.java
index abeb404..be553ac6 100644
--- a/src/main/java/com/android/tools/r8/graph/ClassAccessFlags.java
+++ b/src/main/java/com/android/tools/r8/graph/ClassAccessFlags.java
@@ -95,7 +95,7 @@
   public int getAsDexAccessFlags() {
     // We unset the super flag here, as it is meaningless in DEX. Furthermore, we add missing
     // abstract to interfaces to work around a javac bug when generating package-info classes.
-    int flags = materialize() & ~Constants.ACC_SUPER;
+    int flags = materialize() & ~Constants.ACC_SUPER & ~Constants.ACC_RECORD;
     if (isInterface()) {
       return flags | Constants.ACC_ABSTRACT;
     }
@@ -186,6 +186,10 @@
     set(Constants.ACC_RECORD);
   }
 
+  public void unsetRecord() {
+    unset(Constants.ACC_RECORD);
+  }
+
   public boolean isSuper() {
     return isSet(Constants.ACC_SUPER);
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexApplication.java b/src/main/java/com/android/tools/r8/graph/DexApplication.java
index d5ea16e..d82db4a 100644
--- a/src/main/java/com/android/tools/r8/graph/DexApplication.java
+++ b/src/main/java/com/android/tools/r8/graph/DexApplication.java
@@ -199,6 +199,8 @@
       return self();
     }
 
+    public abstract void addProgramClassPotentiallyOverridingNonProgramClass(DexProgramClass clazz);
+
     public synchronized T addProgramClasses(Collection<DexProgramClass> classes) {
       programClasses.addAll(classes);
       return self();
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index 04aff56..2ce742a 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -216,6 +216,7 @@
   public final DexString stringArrayDescriptor = createString("[Ljava/lang/String;");
   public final DexString objectDescriptor = createString("Ljava/lang/Object;");
   public final DexString recordDescriptor = createString("Ljava/lang/Record;");
+  public final DexString r8RecordDescriptor = createString("Lcom/android/tools/r8/RecordTag;");
   public final DexString objectArrayDescriptor = createString("[Ljava/lang/Object;");
   public final DexString classDescriptor = createString("Ljava/lang/Class;");
   public final DexString classLoaderDescriptor = createString("Ljava/lang/ClassLoader;");
@@ -347,6 +348,7 @@
   public final DexType stringArrayType = createStaticallyKnownType(stringArrayDescriptor);
   public final DexType objectType = createStaticallyKnownType(objectDescriptor);
   public final DexType recordType = createStaticallyKnownType(recordDescriptor);
+  public final DexType r8RecordType = createStaticallyKnownType(r8RecordDescriptor);
   public final DexType objectArrayType = createStaticallyKnownType(objectArrayDescriptor);
   public final DexType classArrayType = createStaticallyKnownType(classArrayDescriptor);
   public final DexType enumType = createStaticallyKnownType(enumDescriptor);
@@ -510,6 +512,7 @@
   public final LongMembers longMembers = new LongMembers();
   public final ObjectsMethods objectsMethods = new ObjectsMethods();
   public final ObjectMembers objectMembers = new ObjectMembers();
+  public final RecordMembers recordMembers = new RecordMembers();
   public final ShortMembers shortMembers = new ShortMembers();
   public final StringMembers stringMembers = new StringMembers();
   public final DoubleMembers doubleMembers = new DoubleMembers();
@@ -1204,6 +1207,14 @@
     }
   }
 
+  public class RecordMembers {
+    public final DexMethod init = createMethod(recordType, createProto(voidType), "<init>");
+    public final DexMethod equals =
+        createMethod(recordType, createProto(booleanType, objectType), "equals");
+    public final DexMethod hashCode = createMethod(recordType, createProto(intType), "hashCode");
+    public final DexMethod toString = createMethod(recordType, createProto(stringType), "toString");
+  }
+
   public class ObjectMembers {
 
     /**
diff --git a/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java b/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java
index 86377b3..0f7b951 100644
--- a/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java
+++ b/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java
@@ -213,6 +213,37 @@
     }
 
     @Override
+    public void addProgramClassPotentiallyOverridingNonProgramClass(DexProgramClass clazz) {
+      addProgramClass(clazz);
+      if (containsType(clazz.type, libraryClasses)) {
+        replaceLibraryClasses(withoutType(clazz.type, libraryClasses));
+        return;
+      }
+      if (containsType(clazz.type, classpathClasses)) {
+        replaceClasspathClasses(withoutType(clazz.type, classpathClasses));
+      }
+    }
+
+    private boolean containsType(DexType type, List<? extends DexClass> classes) {
+      for (DexClass clazz : classes) {
+        if (clazz.type == type) {
+          return true;
+        }
+      }
+      return false;
+    }
+
+    private <T extends DexClass> ImmutableList<T> withoutType(DexType type, List<T> classes) {
+      ImmutableList.Builder<T> builder = ImmutableList.builder();
+      for (T clazz : classes) {
+        if (clazz.type != type) {
+          builder.add(clazz);
+        }
+      }
+      return builder.build();
+    }
+
+    @Override
     Builder self() {
       return this;
     }
diff --git a/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java b/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java
index 35b4574..d8815c7 100644
--- a/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java
+++ b/src/main/java/com/android/tools/r8/graph/JarClassFileReader.java
@@ -500,7 +500,7 @@
         return;
       }
       // TODO(b/169645628): Support records in all compilation.
-      if (!application.options.canUseRecords()) {
+      if (!application.options.enableExperimentalRecordDesugaring()) {
         throw new CompilationError("Records are not supported", origin);
       }
       // TODO(b/169645628): Change this logic if we start stripping the record components.
diff --git a/src/main/java/com/android/tools/r8/graph/LazyLoadedDexApplication.java b/src/main/java/com/android/tools/r8/graph/LazyLoadedDexApplication.java
index 7005e06..509a10d 100644
--- a/src/main/java/com/android/tools/r8/graph/LazyLoadedDexApplication.java
+++ b/src/main/java/com/android/tools/r8/graph/LazyLoadedDexApplication.java
@@ -226,6 +226,13 @@
     }
 
     @Override
+    public void addProgramClassPotentiallyOverridingNonProgramClass(DexProgramClass clazz) {
+      addProgramClass(clazz);
+      classpathClasses.clearType(clazz.type);
+      libraryClasses.clearType(clazz.type);
+    }
+
+    @Override
     public LazyLoadedDexApplication build() {
       return new LazyLoadedDexApplication(
           proguardMap,
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java
index 6d79c9c..8f83dca 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/ClassConverter.java
@@ -9,6 +9,8 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.desugar.CfClassDesugaringEventConsumer;
+import com.android.tools.r8.ir.desugar.CfClassDesugaringEventConsumer.D8CfClassDesugaringEventConsumer;
 import com.android.tools.r8.ir.desugar.CfInstructionDesugaringEventConsumer;
 import com.android.tools.r8.ir.desugar.CfInstructionDesugaringEventConsumer.D8CfInstructionDesugaringEventConsumer;
 import com.android.tools.r8.utils.ThreadUtils;
@@ -50,6 +52,11 @@
       ClassConverterResult.Builder resultBuilder, ExecutorService executorService)
       throws ExecutionException {
     List<DexProgramClass> classes = appView.appInfo().classes();
+
+    D8CfClassDesugaringEventConsumer classDesugaringEventConsumer =
+        CfClassDesugaringEventConsumer.createForD8(methodProcessor);
+    converter.desugarClassesForD8(classes, classDesugaringEventConsumer, executorService);
+
     while (!classes.isEmpty()) {
       Set<DexType> seenNestHosts = Sets.newIdentityHashSet();
       List<DexProgramClass> deferred = new ArrayList<>(classes.size() / 2);
@@ -65,18 +72,19 @@
         }
       }
 
-      // Process the wave and wait for all IR processing to complete.
-      D8CfInstructionDesugaringEventConsumer desugaringEventConsumer =
+      D8CfInstructionDesugaringEventConsumer instructionDesugaringEventConsumer =
           CfInstructionDesugaringEventConsumer.createForD8(methodProcessor);
+
+      // Process the wave and wait for all IR processing to complete.
       methodProcessor.newWave();
       ThreadUtils.processItems(
-          wave, clazz -> convertClass(clazz, desugaringEventConsumer), executorService);
+          wave, clazz -> convertClass(clazz, instructionDesugaringEventConsumer), executorService);
       methodProcessor.awaitMethodProcessing();
 
       // Finalize the desugaring of the processed classes. This may require processing (and
       // reprocessing) of some methods.
       List<ProgramMethod> needsProcessing =
-          desugaringEventConsumer.finalizeDesugaring(appView, resultBuilder);
+          instructionDesugaringEventConsumer.finalizeDesugaring(appView, resultBuilder);
       if (!needsProcessing.isEmpty()) {
         // Create a new processor context to ensure unique method processing contexts.
         methodProcessor.newWave();
@@ -90,13 +98,13 @@
               if (definition.isProcessed()) {
                 definition.markNotProcessed();
               }
-              methodProcessor.processMethod(method, desugaringEventConsumer);
+              methodProcessor.processMethod(method, instructionDesugaringEventConsumer);
             },
             executorService);
 
         // Verify there is nothing to finalize once method processing finishes.
         methodProcessor.awaitMethodProcessing();
-        assert desugaringEventConsumer.verifyNothingToFinalize();
+        assert instructionDesugaringEventConsumer.verifyNothingToFinalize();
       }
 
       classes = deferred;
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index 8e5c11c..54b0a66 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -42,6 +42,8 @@
 import com.android.tools.r8.ir.code.InvokeStatic;
 import com.android.tools.r8.ir.code.NumericType;
 import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.desugar.CfClassDesugaringCollection;
+import com.android.tools.r8.ir.desugar.CfClassDesugaringEventConsumer.D8CfClassDesugaringEventConsumer;
 import com.android.tools.r8.ir.desugar.CfInstructionDesugaringCollection;
 import com.android.tools.r8.ir.desugar.CfInstructionDesugaringEventConsumer;
 import com.android.tools.r8.ir.desugar.CfInstructionDesugaringEventConsumer.D8CfInstructionDesugaringEventConsumer;
@@ -125,7 +127,8 @@
   private final Timing timing;
   private final Outliner outliner;
   private final ClassInitializerDefaultsOptimization classInitializerDefaultsOptimization;
-  private final CfInstructionDesugaringCollection desugaring;
+  private final CfClassDesugaringCollection classDesugaring;
+  private final CfInstructionDesugaringCollection instructionDesugaring;
   private final FieldAccessAnalysis fieldAccessAnalysis;
   private final LibraryMethodOverrideAnalysis libraryMethodOverrideAnalysis;
   private final StringOptimizer stringOptimizer;
@@ -217,7 +220,8 @@
       // - nest based access desugaring,
       // - invoke-special desugaring.
       assert options.desugarState.isOn();
-      this.desugaring = CfInstructionDesugaringCollection.create(appView);
+      this.instructionDesugaring = CfInstructionDesugaringCollection.create(appView);
+      this.classDesugaring = instructionDesugaring.createClassDesugaringCollection();
       this.desugaredLibraryRetargeter =
           options.desugaredLibraryConfiguration.getRetargetCoreLibMember().isEmpty()
               ? null
@@ -249,10 +253,11 @@
       this.assumeInserter = null;
       return;
     }
-    this.desugaring =
+    this.instructionDesugaring =
         appView.enableWholeProgramOptimizations()
             ? CfInstructionDesugaringCollection.empty()
             : CfInstructionDesugaringCollection.create(appView);
+    this.classDesugaring = instructionDesugaring.createClassDesugaringCollection();
     this.interfaceMethodRewriter =
         options.isInterfaceMethodDesugaringEnabled()
             ? new InterfaceMethodRewriter(appView, this)
@@ -349,7 +354,7 @@
   private void synthesizeBridgesForNestBasedAccessesOnClasspath(
       D8MethodProcessor methodProcessor, ExecutorService executorService)
       throws ExecutionException {
-    desugaring.withD8NestBasedAccessDesugaring(
+    instructionDesugaring.withD8NestBasedAccessDesugaring(
         d8NestBasedAccessDesugaring ->
             d8NestBasedAccessDesugaring.synthesizeBridgesForNestBasedAccessesOnClasspath(
                 methodProcessor, executorService));
@@ -357,7 +362,7 @@
   }
 
   private void reportNestDesugarDependencies() {
-    desugaring.withD8NestBasedAccessDesugaring(
+    instructionDesugaring.withD8NestBasedAccessDesugaring(
         D8NestBasedAccessDesugaring::reportDesugarDependencies);
   }
 
@@ -460,6 +465,26 @@
         appView, classConverterResult.getForcefullyMovedLambdaMethods());
   }
 
+  public void desugarClassesForD8(
+      List<DexProgramClass> classes,
+      D8CfClassDesugaringEventConsumer desugaringEventConsumer,
+      ExecutorService executorService)
+      throws ExecutionException {
+    if (classDesugaring.isEmpty()) {
+      return;
+    }
+    // Currently the classes can be processed in any order and do not require to be sorted.
+    ThreadUtils.processItems(
+        classes, clazz -> desugarClassForD8(clazz, desugaringEventConsumer), executorService);
+  }
+
+  public void desugarClassForD8(
+      DexProgramClass clazz, D8CfClassDesugaringEventConsumer desugaringEventConsumer) {
+    if (classDesugaring.needsDesugaring(clazz)) {
+      classDesugaring.desugar(clazz, desugaringEventConsumer);
+    }
+  }
+
   void convertMethods(
       DexProgramClass clazz,
       D8CfInstructionDesugaringEventConsumer desugaringEventConsumer,
@@ -545,7 +570,7 @@
     if (!options.cfToCfDesugar) {
       return true;
     }
-    if (desugaring.needsDesugaring(method)) {
+    if (instructionDesugaring.needsDesugaring(method)) {
       return true;
     }
     if (desugaredLibraryAPIConverter != null
@@ -621,7 +646,7 @@
       AppView<AppInfoWithLiveness> appView, ExecutorService executorService)
       throws ExecutionException {
     // Desugaring happens in the enqueuer.
-    assert desugaring.isEmpty();
+    assert instructionDesugaring.isEmpty();
 
     DexApplication application = appView.appInfo().app();
 
@@ -1110,13 +1135,15 @@
       ProgramMethod method,
       CfInstructionDesugaringEventConsumer desugaringEventConsumer,
       MethodProcessingContext methodProcessingContext) {
-    if (options.desugarState.isOff()
-        || !method.getDefinition().getCode().isCfCode()
-        || !desugaring.needsDesugaring(method)) {
+    if (options.desugarState.isOff() || !method.getDefinition().getCode().isCfCode()) {
       return false;
     }
-    desugaring.desugar(method, methodProcessingContext, desugaringEventConsumer);
-    return true;
+    instructionDesugaring.scan(method, desugaringEventConsumer);
+    if (instructionDesugaring.needsDesugaring(method)) {
+      instructionDesugaring.desugar(method, methodProcessingContext, desugaringEventConsumer);
+      return true;
+    }
+    return false;
   }
 
   // TODO(b/140766440): Convert all sub steps an implementer of CodeOptimization
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/CfClassDesugaring.java b/src/main/java/com/android/tools/r8/ir/desugar/CfClassDesugaring.java
new file mode 100644
index 0000000..a885344
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/desugar/CfClassDesugaring.java
@@ -0,0 +1,16 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.desugar;
+
+import com.android.tools.r8.graph.DexProgramClass;
+
+/** Interface for desugaring a class. */
+public interface CfClassDesugaring {
+
+  void desugar(DexProgramClass clazz, CfClassDesugaringEventConsumer eventConsumer);
+
+  /** Returns true if the given class needs desugaring. */
+  boolean needsDesugaring(DexProgramClass clazz);
+}
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/CfClassDesugaringCollection.java b/src/main/java/com/android/tools/r8/ir/desugar/CfClassDesugaringCollection.java
new file mode 100644
index 0000000..9b7c709
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/desugar/CfClassDesugaringCollection.java
@@ -0,0 +1,58 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.desugar;
+
+import com.android.tools.r8.graph.DexProgramClass;
+
+/** Interface for desugaring a class. */
+public abstract class CfClassDesugaringCollection {
+
+  public abstract void desugar(DexProgramClass clazz, CfClassDesugaringEventConsumer eventConsumer);
+
+  /** Returns true if the given class needs desugaring. */
+  public abstract boolean needsDesugaring(DexProgramClass clazz);
+
+  public abstract boolean isEmpty();
+
+  public static class NonEmptyCfClassDesugaringCollection extends CfClassDesugaringCollection {
+    private final RecordRewriter recordRewriter;
+
+    NonEmptyCfClassDesugaringCollection(RecordRewriter recordRewriter) {
+      this.recordRewriter = recordRewriter;
+    }
+
+    @Override
+    public void desugar(DexProgramClass clazz, CfClassDesugaringEventConsumer eventConsumer) {
+      recordRewriter.desugar(clazz, eventConsumer);
+    }
+
+    @Override
+    public boolean needsDesugaring(DexProgramClass clazz) {
+      return recordRewriter.needsDesugaring(clazz);
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return false;
+    }
+  }
+
+  public static class EmptyCfClassDesugaringCollection extends CfClassDesugaringCollection {
+    @Override
+    public void desugar(DexProgramClass clazz, CfClassDesugaringEventConsumer eventConsumer) {
+      // Intentionally empty.
+    }
+
+    @Override
+    public boolean needsDesugaring(DexProgramClass clazz) {
+      return false;
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return true;
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/CfClassDesugaringEventConsumer.java b/src/main/java/com/android/tools/r8/ir/desugar/CfClassDesugaringEventConsumer.java
new file mode 100644
index 0000000..d5acaa7
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/desugar/CfClassDesugaringEventConsumer.java
@@ -0,0 +1,31 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.desugar;
+
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.ir.conversion.D8MethodProcessor;
+
+public abstract class CfClassDesugaringEventConsumer implements RecordDesugaringEventConsumer {
+
+  public static D8CfClassDesugaringEventConsumer createForD8(D8MethodProcessor methodProcessor) {
+    return new D8CfClassDesugaringEventConsumer(methodProcessor);
+  }
+
+  public static class D8CfClassDesugaringEventConsumer extends CfClassDesugaringEventConsumer {
+
+    private final D8MethodProcessor methodProcessor;
+
+    public D8CfClassDesugaringEventConsumer(D8MethodProcessor methodProcessor) {
+      this.methodProcessor = methodProcessor;
+    }
+
+    @Override
+    public void acceptRecordClass(DexProgramClass recordClass) {
+      methodProcessor.scheduleDesugaredMethodsForProcessing(recordClass.programMethods());
+    }
+  }
+
+  // TODO(b/): Implement R8CfClassDesugaringEventConsumer
+}
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringCollection.java b/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringCollection.java
index 21ac7ae..3fb9329 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringCollection.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.desugar.nest.D8NestBasedAccessDesugaring;
 import com.android.tools.r8.utils.ThrowingConsumer;
+import java.util.function.Consumer;
 
 /**
  * Abstracts a collection of low-level desugarings (i.e., mappings from class-file instructions to
@@ -34,6 +35,9 @@
     return EmptyCfInstructionDesugaringCollection.getInstance();
   }
 
+  public abstract void scan(
+      ProgramMethod method, CfInstructionDesugaringEventConsumer eventConsumer);
+
   /** Desugars the instructions in the given method. */
   public abstract void desugar(
       ProgramMethod method,
@@ -44,9 +48,13 @@
     return false;
   }
 
+  public abstract CfClassDesugaringCollection createClassDesugaringCollection();
+
   /** Returns true if the given method needs desugaring. */
   public abstract boolean needsDesugaring(ProgramMethod method);
 
   public abstract <T extends Throwable> void withD8NestBasedAccessDesugaring(
       ThrowingConsumer<D8NestBasedAccessDesugaring, T> consumer) throws T;
+
+  public abstract void withRecordRewriter(Consumer<RecordRewriter> consumer);
 }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringEventConsumer.java b/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringEventConsumer.java
index d765537..a95569e 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringEventConsumer.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/CfInstructionDesugaringEventConsumer.java
@@ -39,6 +39,7 @@
         InvokeSpecialToSelfDesugaringEventConsumer,
         LambdaDesugaringEventConsumer,
         NestBasedAccessDesugaringEventConsumer,
+        RecordDesugaringEventConsumer,
         TwrCloseResourceDesugaringEventConsumer {
 
   public static D8CfInstructionDesugaringEventConsumer createForD8(
@@ -58,6 +59,11 @@
     return new CfInstructionDesugaringEventConsumer() {
 
       @Override
+      public void acceptRecordClass(DexProgramClass recordClass) {
+        assert false;
+      }
+
+      @Override
       public void acceptBackportedMethod(ProgramMethod backportedMethod, ProgramMethod context) {
         assert false;
       }
@@ -121,6 +127,11 @@
     }
 
     @Override
+    public void acceptRecordClass(DexProgramClass recordClass) {
+      methodProcessor.scheduleDesugaredMethodsForProcessing(recordClass.programMethods());
+    }
+
+    @Override
     public void acceptLambdaClass(LambdaClass lambdaClass, ProgramMethod context) {
       synchronized (synthesizedLambdaClasses) {
         synthesizedLambdaClasses.add(lambdaClass);
@@ -225,6 +236,12 @@
     }
 
     @Override
+    public void acceptRecordClass(DexProgramClass recordClass) {
+      // This is called each time an instruction or a class is found to require the record class.
+      assert false : "TODO(b/179146128): To be implemented";
+    }
+
+    @Override
     public void acceptBackportedMethod(ProgramMethod backportedMethod, ProgramMethod context) {
       // Intentionally empty. The backported method will be hit by the tracing in R8 as if it was
       // present in the input code, and thus nothing needs to be done.
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/EmptyCfInstructionDesugaringCollection.java b/src/main/java/com/android/tools/r8/ir/desugar/EmptyCfInstructionDesugaringCollection.java
index 60b3537..c8b6147 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/EmptyCfInstructionDesugaringCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/EmptyCfInstructionDesugaringCollection.java
@@ -6,8 +6,10 @@
 
 import com.android.tools.r8.contexts.CompilationContext.MethodProcessingContext;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.desugar.CfClassDesugaringCollection.EmptyCfClassDesugaringCollection;
 import com.android.tools.r8.ir.desugar.nest.D8NestBasedAccessDesugaring;
 import com.android.tools.r8.utils.ThrowingConsumer;
+import java.util.function.Consumer;
 
 public class EmptyCfInstructionDesugaringCollection extends CfInstructionDesugaringCollection {
 
@@ -22,6 +24,11 @@
   }
 
   @Override
+  public void scan(ProgramMethod method, CfInstructionDesugaringEventConsumer eventConsumer) {
+    // Intentionally empty.
+  }
+
+  @Override
   public void desugar(
       ProgramMethod method,
       MethodProcessingContext methodProcessingContext,
@@ -35,6 +42,11 @@
   }
 
   @Override
+  public CfClassDesugaringCollection createClassDesugaringCollection() {
+    return new EmptyCfClassDesugaringCollection();
+  }
+
+  @Override
   public boolean needsDesugaring(ProgramMethod method) {
     return false;
   }
@@ -44,4 +56,9 @@
       ThrowingConsumer<D8NestBasedAccessDesugaring, T> consumer) {
     // Intentionally empty.
   }
+
+  @Override
+  public void withRecordRewriter(Consumer<RecordRewriter> consumer) {
+    // Intentionally empty.
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/NonEmptyCfInstructionDesugaringCollection.java b/src/main/java/com/android/tools/r8/ir/desugar/NonEmptyCfInstructionDesugaringCollection.java
index 5815053..1865244 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/NonEmptyCfInstructionDesugaringCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/NonEmptyCfInstructionDesugaringCollection.java
@@ -12,6 +12,8 @@
 import com.android.tools.r8.graph.CfCode;
 import com.android.tools.r8.graph.Code;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.desugar.CfClassDesugaringCollection.EmptyCfClassDesugaringCollection;
+import com.android.tools.r8.ir.desugar.CfClassDesugaringCollection.NonEmptyCfClassDesugaringCollection;
 import com.android.tools.r8.ir.desugar.invokespecial.InvokeSpecialToSelfDesugaring;
 import com.android.tools.r8.ir.desugar.lambda.LambdaInstructionDesugaring;
 import com.android.tools.r8.ir.desugar.nest.D8NestBasedAccessDesugaring;
@@ -28,6 +30,7 @@
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.List;
+import java.util.function.Consumer;
 
 public class NonEmptyCfInstructionDesugaringCollection extends CfInstructionDesugaringCollection {
 
@@ -35,6 +38,7 @@
   private final List<CfInstructionDesugaring> desugarings = new ArrayList<>();
 
   private final NestBasedAccessDesugaring nestBasedAccessDesugaring;
+  private final RecordRewriter recordRewriter;
 
   NonEmptyCfInstructionDesugaringCollection(AppView<?> appView) {
     this.appView = appView;
@@ -54,6 +58,11 @@
     if (nestBasedAccessDesugaring != null) {
       desugarings.add(nestBasedAccessDesugaring);
     }
+    this.recordRewriter = RecordRewriter.create(appView);
+    if (recordRewriter != null) {
+      assert !appView.enableWholeProgramOptimizations() : "To be implemented";
+      desugarings.add(recordRewriter);
+    }
   }
 
   // TODO(b/145775365): special constructor for cf-to-cf compilations with desugaring disabled.
@@ -62,6 +71,7 @@
       AppView<?> appView, InvokeSpecialToSelfDesugaring invokeSpecialToSelfDesugaring) {
     this.appView = appView;
     this.nestBasedAccessDesugaring = null;
+    this.recordRewriter = null;
     desugarings.add(invokeSpecialToSelfDesugaring);
   }
 
@@ -72,13 +82,8 @@
         appView, new InvokeSpecialToSelfDesugaring(appView));
   }
 
-  @Override
-  public void desugar(
-      ProgramMethod method,
-      MethodProcessingContext methodProcessingContext,
-      CfInstructionDesugaringEventConsumer eventConsumer) {
-    Code code = method.getDefinition().getCode();
-    if (!code.isCfCode()) {
+  private void ensureCfCode(ProgramMethod method) {
+    if (!method.getDefinition().getCode().isCfCode()) {
       appView
           .options()
           .reporter
@@ -87,10 +92,24 @@
                   "Unsupported attempt to desugar non-CF code",
                   method.getOrigin(),
                   method.getPosition()));
-      return;
     }
+  }
 
-    CfCode cfCode = code.asCfCode();
+  @Override
+  public void scan(ProgramMethod method, CfInstructionDesugaringEventConsumer eventConsumer) {
+    ensureCfCode(method);
+    if (recordRewriter != null) {
+      recordRewriter.scan(method, eventConsumer);
+    }
+  }
+
+  @Override
+  public void desugar(
+      ProgramMethod method,
+      MethodProcessingContext methodProcessingContext,
+      CfInstructionDesugaringEventConsumer eventConsumer) {
+    ensureCfCode(method);
+    CfCode cfCode = method.getDefinition().getCode().asCfCode();
 
     // Tracking of temporary locals used for instruction desugaring. The desugaring of each
     // instruction is assumed to use locals only for the duration of the instruction, such that any
@@ -135,6 +154,14 @@
     }
   }
 
+  @Override
+  public CfClassDesugaringCollection createClassDesugaringCollection() {
+    if (recordRewriter == null) {
+      return new EmptyCfClassDesugaringCollection();
+    }
+    return new NonEmptyCfClassDesugaringCollection(recordRewriter);
+  }
+
   private Collection<CfInstruction> desugarInstruction(
       CfInstruction instruction,
       FreshLocalProvider freshLocalProvider,
@@ -220,4 +247,11 @@
       consumer.accept((D8NestBasedAccessDesugaring) nestBasedAccessDesugaring);
     }
   }
+
+  @Override
+  public void withRecordRewriter(Consumer<RecordRewriter> consumer) {
+    if (recordRewriter != null) {
+      consumer.accept(recordRewriter);
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/RecordDesugaringEventConsumer.java b/src/main/java/com/android/tools/r8/ir/desugar/RecordDesugaringEventConsumer.java
new file mode 100644
index 0000000..19d9ae3
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/desugar/RecordDesugaringEventConsumer.java
@@ -0,0 +1,12 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.desugar;
+
+import com.android.tools.r8.graph.DexProgramClass;
+
+public interface RecordDesugaringEventConsumer {
+
+  void acceptRecordClass(DexProgramClass recordClass);
+}
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/RecordRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/RecordRewriter.java
new file mode 100644
index 0000000..67e2c90
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/desugar/RecordRewriter.java
@@ -0,0 +1,272 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.desugar;
+
+import com.android.tools.r8.cf.code.CfConstNull;
+import com.android.tools.r8.cf.code.CfConstNumber;
+import com.android.tools.r8.cf.code.CfFieldInstruction;
+import com.android.tools.r8.cf.code.CfInstruction;
+import com.android.tools.r8.cf.code.CfInvoke;
+import com.android.tools.r8.cf.code.CfStackInstruction;
+import com.android.tools.r8.cf.code.CfTypeInstruction;
+import com.android.tools.r8.contexts.CompilationContext.MethodProcessingContext;
+import com.android.tools.r8.dex.Constants;
+import com.android.tools.r8.errors.CompilationError;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.CfCode;
+import com.android.tools.r8.graph.DexAnnotationSet;
+import com.android.tools.r8.graph.DexClass;
+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.DexProto;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
+import com.android.tools.r8.graph.MethodAccessFlags;
+import com.android.tools.r8.graph.ParameterAnnotationsList;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.code.ValueType;
+import com.android.tools.r8.ir.synthetic.CallObjectInitCfCodeProvider;
+import com.android.tools.r8.synthesis.SyntheticNaming;
+import com.google.common.collect.ImmutableList;
+import java.util.Collection;
+import java.util.Collections;
+
+public class RecordRewriter implements CfInstructionDesugaring, CfClassDesugaring {
+
+  private final AppView<?> appView;
+  private final DexItemFactory factory;
+
+  public static RecordRewriter create(AppView<?> appView) {
+    return appView.options().shouldDesugarRecords() ? new RecordRewriter(appView) : null;
+  }
+
+  private RecordRewriter(AppView<?> appView) {
+    this.appView = appView;
+    factory = appView.dexItemFactory();
+  }
+
+  public void scan(
+      ProgramMethod programMethod, CfInstructionDesugaringEventConsumer eventConsumer) {
+    CfCode cfCode = programMethod.getDefinition().getCode().asCfCode();
+    for (CfInstruction instruction : cfCode.getInstructions()) {
+      scanInstruction(instruction, eventConsumer);
+    }
+  }
+
+  // The record rewriter scans the cf instructions to figure out if the record class needs to
+  // be added in the output. the analysis cannot be done in desugarInstruction because the analysis
+  // does not rewrite any instruction, and desugarInstruction is expected to rewrite at least one
+  // instruction for assertions to be valid.
+  private void scanInstruction(
+      CfInstruction instruction, CfInstructionDesugaringEventConsumer eventConsumer) {
+    assert !instruction.isInitClass();
+    if (instruction.isInvoke()) {
+      CfInvoke cfInvoke = instruction.asInvoke();
+      if (refersToRecord(cfInvoke.getMethod())) {
+        requiresRecordClass(eventConsumer);
+      }
+      return;
+    }
+    if (instruction.isFieldInstruction()) {
+      CfFieldInstruction fieldInstruction = instruction.asFieldInstruction();
+      if (refersToRecord(fieldInstruction.getField())) {
+        requiresRecordClass(eventConsumer);
+      }
+      return;
+    }
+    if (instruction.isTypeInstruction()) {
+      CfTypeInstruction typeInstruction = instruction.asTypeInstruction();
+      if (refersToRecord(typeInstruction.getType())) {
+        requiresRecordClass(eventConsumer);
+      }
+      return;
+    }
+    // TODO(b/179146128): Analyse MethodHandle and MethodType.
+  }
+
+  @Override
+  public Collection<CfInstruction> desugarInstruction(
+      CfInstruction instruction,
+      FreshLocalProvider freshLocalProvider,
+      LocalStackAllocator localStackAllocator,
+      CfInstructionDesugaringEventConsumer eventConsumer,
+      ProgramMethod context,
+      MethodProcessingContext methodProcessingContext) {
+
+    // TODO(b/179146128): This is a temporary work-around to test desugaring of records
+    // without rewriting the record invoke-custom. This should be removed when the record support
+    // is complete.
+    if (instruction.isInvokeDynamic()
+        && context.getHolder().superType == factory.recordType
+        && (context.getReference().match(factory.recordMembers.toString)
+            || context.getReference().match(factory.recordMembers.hashCode)
+            || context.getReference().match(factory.recordMembers.equals))) {
+      requiresRecordClass(eventConsumer);
+      CfInstruction constant =
+          context.getReference().match(factory.recordMembers.toString)
+              ? new CfConstNull()
+              : new CfConstNumber(0, ValueType.INT);
+      return ImmutableList.of(new CfStackInstruction(CfStackInstruction.Opcode.Pop), constant);
+    }
+
+    CfInstruction desugaredInstruction = desugarInstruction(instruction, context);
+    return desugaredInstruction == null ? null : Collections.singletonList(desugaredInstruction);
+  }
+
+  private CfInstruction desugarInstruction(CfInstruction instruction, ProgramMethod context) {
+    assert !instruction.isInitClass();
+    // TODO(b/179146128): Rewrite record invoke-dynamic here.
+    if (instruction.isInvoke()) {
+      CfInvoke cfInvoke = instruction.asInvoke();
+      DexMethod newMethod =
+          rewriteMethod(cfInvoke.getMethod(), cfInvoke.isInvokeSuper(context.getHolderType()));
+      if (newMethod != cfInvoke.getMethod()) {
+        return new CfInvoke(cfInvoke.getOpcode(), newMethod, cfInvoke.isInterface());
+      }
+    }
+    return null;
+  }
+
+  @Override
+  public boolean needsDesugaring(CfInstruction instruction, ProgramMethod context) {
+    assert !instruction.isInitClass();
+    // TODO(b/179146128): This is a temporary work-around to test desugaring of records
+    // without rewriting the record invoke-custom. This should be removed when the record support
+    // is complete.
+    if (instruction.isInvokeDynamic()
+        && context.getHolder().superType == factory.recordType
+        && (context.getName() == factory.toStringMethodName
+            || context.getName() == factory.hashCodeMethodName
+            || context.getName() == factory.equalsMethodName)) {
+      return true;
+    }
+    if (instruction.isInvoke()) {
+      CfInvoke cfInvoke = instruction.asInvoke();
+      return needsDesugaring(cfInvoke.getMethod(), cfInvoke.isInvokeSuper(context.getHolderType()));
+    }
+    return false;
+  }
+
+  private void requiresRecordClass(RecordDesugaringEventConsumer eventConsumer) {
+    DexProgramClass recordClass = synthesizeR8Record();
+    if (recordClass != null) {
+      eventConsumer.acceptRecordClass(recordClass);
+    }
+  }
+
+  @Override
+  public boolean needsDesugaring(DexProgramClass clazz) {
+    assert clazz.isRecord() || clazz.superType != factory.recordType;
+    return clazz.isRecord();
+  }
+
+  @Override
+  public void desugar(DexProgramClass clazz, CfClassDesugaringEventConsumer eventConsumer) {
+    if (clazz.isRecord()) {
+      assert clazz.superType == factory.recordType;
+      requiresRecordClass(eventConsumer);
+      clazz.accessFlags.unsetRecord();
+    }
+  }
+
+  private boolean refersToRecord(DexField field) {
+    assert !refersToRecord(field.holder) : "The java.lang.Record class has no fields.";
+    return refersToRecord(field.type);
+  }
+
+  private boolean refersToRecord(DexMethod method) {
+    if (refersToRecord(method.holder)) {
+      return true;
+    }
+    return refersToRecord(method.proto);
+  }
+
+  private boolean refersToRecord(DexProto proto) {
+    if (refersToRecord(proto.returnType)) {
+      return true;
+    }
+    return refersToRecord(proto.parameters.values);
+  }
+
+  private boolean refersToRecord(DexType[] types) {
+    for (DexType type : types) {
+      if (refersToRecord(type)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  private boolean refersToRecord(DexType type) {
+    return type == factory.recordType;
+  }
+
+  private boolean needsDesugaring(DexMethod method, boolean isSuper) {
+    return rewriteMethod(method, isSuper) != method;
+  }
+
+  @SuppressWarnings("ConstantConditions")
+  private DexMethod rewriteMethod(DexMethod method, boolean isSuper) {
+    if (method.holder != factory.recordType || method.isInstanceInitializer(factory)) {
+      return method;
+    }
+    assert method == factory.recordMembers.equals
+        || method == factory.recordMembers.hashCode
+        || method == factory.recordMembers.toString;
+    if (isSuper) {
+      // TODO(b/179146128): Support rewriting invoke-super to a Record method.
+      throw new CompilationError("Rewrite invoke-super to abstract method error.");
+    }
+    if (method == factory.recordMembers.equals) {
+      return factory.objectMembers.equals;
+    }
+    if (method == factory.recordMembers.toString) {
+      return factory.objectMembers.toString;
+    }
+    assert method == factory.recordMembers.hashCode;
+    return factory.objectMembers.toString;
+  }
+
+  private DexProgramClass synthesizeR8Record() {
+    DexItemFactory factory = appView.dexItemFactory();
+    DexClass recordClass =
+        appView.appInfo().definitionForWithoutExistenceAssert(factory.recordType);
+    if (recordClass != null && recordClass.isProgramClass()) {
+      return null;
+    }
+    assert recordClass == null || recordClass.isLibraryClass();
+    DexEncodedMethod init = synthesizeRecordInitMethod();
+    // TODO(b/179146128): We may want to remove here the class from the library classes if present
+    //  in cf to cf.
+    return appView
+        .getSyntheticItems()
+        .createFixedClassFromType(
+            SyntheticNaming.SyntheticKind.RECORD_TAG,
+            factory.recordType,
+            factory,
+            builder -> builder.setAbstract().setDirectMethods(Collections.singletonList(init)));
+  }
+
+  private DexEncodedMethod synthesizeRecordInitMethod() {
+    MethodAccessFlags methodAccessFlags =
+        MethodAccessFlags.fromSharedAccessFlags(
+            Constants.ACC_SYNTHETIC | Constants.ACC_PROTECTED, true);
+    DexEncodedMethod init =
+        new DexEncodedMethod(
+            factory.recordMembers.init,
+            methodAccessFlags,
+            MethodTypeSignature.noSignature(),
+            DexAnnotationSet.empty(),
+            ParameterAnnotationsList.empty(),
+            null,
+            true);
+    init.setCode(
+        new CallObjectInitCfCodeProvider(appView, factory.r8RecordType).generateCfCode(), appView);
+    return init;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/synthetic/CallObjectInitCfCodeProvider.java b/src/main/java/com/android/tools/r8/ir/synthetic/CallObjectInitCfCodeProvider.java
new file mode 100644
index 0000000..77462a4
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/synthetic/CallObjectInitCfCodeProvider.java
@@ -0,0 +1,35 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.synthetic;
+
+import com.android.tools.r8.cf.code.CfInstruction;
+import com.android.tools.r8.cf.code.CfInvoke;
+import com.android.tools.r8.cf.code.CfLoad;
+import com.android.tools.r8.cf.code.CfReturnVoid;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.CfCode;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.ValueType;
+import java.util.ArrayList;
+import java.util.List;
+import org.objectweb.asm.Opcodes;
+
+public class CallObjectInitCfCodeProvider extends SyntheticCfCodeProvider {
+
+  public CallObjectInitCfCodeProvider(AppView<?> appView, DexType holder) {
+    super(appView, holder);
+  }
+
+  @Override
+  public CfCode generateCfCode() {
+    DexItemFactory factory = appView.dexItemFactory();
+    List<CfInstruction> instructions = new ArrayList<>();
+    instructions.add(new CfLoad(ValueType.OBJECT, 0));
+    instructions.add(new CfInvoke(Opcodes.INVOKESPECIAL, factory.objectMembers.constructor, false));
+    instructions.add(new CfReturnVoid());
+    return standardCfCodeFromInstructions(instructions);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/naming/RecordRewritingNamingLens.java b/src/main/java/com/android/tools/r8/naming/RecordRewritingNamingLens.java
new file mode 100644
index 0000000..83fa84e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/naming/RecordRewritingNamingLens.java
@@ -0,0 +1,94 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.naming;
+
+import com.android.tools.r8.graph.AppView;
+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.graph.InnerClassAttribute;
+import com.android.tools.r8.naming.NamingLens.NonIdentityNamingLens;
+import com.android.tools.r8.utils.InternalOptions;
+import java.util.IdentityHashMap;
+
+// Naming lens for rewriting java.lang.Record to the internal RecordTag type.
+public class RecordRewritingNamingLens extends NonIdentityNamingLens {
+
+  final NamingLens namingLens;
+  private final DexItemFactory factory;
+
+  public static NamingLens createRecordRewritingNamingLens(AppView<?> appView) {
+    return createRecordRewritingNamingLens(appView, NamingLens.getIdentityLens());
+  }
+
+  public static NamingLens createRecordRewritingNamingLens(
+      AppView<?> appView, NamingLens namingLens) {
+    if (!appView.options().shouldDesugarRecords()) {
+      return namingLens;
+    }
+    return new RecordRewritingNamingLens(namingLens, appView);
+  }
+
+  public RecordRewritingNamingLens(NamingLens namingLens, AppView<?> appView) {
+    super(appView.dexItemFactory(), new IdentityHashMap<>());
+    this.namingLens = namingLens;
+    factory = appView.dexItemFactory();
+  }
+
+  private boolean isRenamed(DexType type) {
+    return getRenaming(type) != null;
+  }
+
+  private DexString getRenaming(DexType type) {
+    if (type == factory.recordType) {
+      return factory.r8RecordType.descriptor;
+    }
+    return null;
+  }
+
+  @Override
+  protected DexString internalLookupClassDescriptor(DexType type) {
+    DexString renaming = getRenaming(type);
+    return renaming != null ? renaming : namingLens.lookupDescriptor(type);
+  }
+
+  @Override
+  public DexString lookupInnerName(InnerClassAttribute attribute, InternalOptions options) {
+    assert !isRenamed(attribute.getInner());
+    return namingLens.lookupInnerName(attribute, options);
+  }
+
+  @Override
+  public DexString lookupName(DexMethod method) {
+    // Record rewriting does not influence method name.
+    return namingLens.lookupName(method);
+  }
+
+  @Override
+  public DexString lookupName(DexField field) {
+    // Record rewriting does not influence field name.
+    return namingLens.lookupName(field);
+  }
+
+  @Override
+  public DexString lookupDescriptorForJavaTypeName(String typeName) {
+    if (typeName.equals(factory.recordType.toSourceString())) {
+      return factory.r8RecordType.descriptor;
+    }
+    return namingLens.lookupDescriptorForJavaTypeName(typeName);
+  }
+
+  @Override
+  public String lookupPackageName(String packageName) {
+    return namingLens.lookupPackageName(packageName);
+  }
+
+  @Override
+  public boolean verifyRenamingConsistentWithResolution(DexMethod item) {
+    return namingLens.verifyRenamingConsistentWithResolution(item);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/synthesis/SynthesizingContext.java b/src/main/java/com/android/tools/r8/synthesis/SynthesizingContext.java
index 3e7f5bc..68bca58 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SynthesizingContext.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SynthesizingContext.java
@@ -44,6 +44,10 @@
         context.getContextType(), context.getContextType(), context.getOrigin());
   }
 
+  static SynthesizingContext fromType(DexType type) {
+    return new SynthesizingContext(type, type, Origin.unknown());
+  }
+
   static SynthesizingContext fromNonSyntheticInputContext(ProgramDefinition context) {
     // A context that is itself non-synthetic is the single context, thus both the input context
     // and synthesizing context coincide.
diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticClassBuilder.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticClassBuilder.java
index 01e6c75..126355f 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticClassBuilder.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticClassBuilder.java
@@ -34,6 +34,7 @@
   private final DexType type;
   private final Origin origin;
 
+  private boolean isAbstract = false;
   private Kind originKind;
   private DexType superType;
   private DexTypeList interfaces = DexTypeList.empty();
@@ -70,6 +71,11 @@
     return self();
   }
 
+  public B setAbstract() {
+    isAbstract = true;
+    return self();
+  }
+
   public B setOriginKind(Kind originKind) {
     this.originKind = originKind;
     return self();
@@ -107,9 +113,10 @@
   }
 
   public C build() {
+    int flag = isAbstract ? Constants.ACC_ABSTRACT : Constants.ACC_FINAL;
     ClassAccessFlags accessFlags =
         ClassAccessFlags.fromSharedAccessFlags(
-            Constants.ACC_FINAL | Constants.ACC_PUBLIC | Constants.ACC_SYNTHETIC);
+            flag | Constants.ACC_PUBLIC | Constants.ACC_SYNTHETIC);
     DexString sourceFile = null;
     NestHostClassAttribute nestHost = null;
     List<NestMemberClassAttribute> nestMembers = Collections.emptyList();
diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java
index 2b24294..b2cf60e 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticFinalization.java
@@ -338,7 +338,8 @@
     // Check that a context is never itself synthetic class.
     committed.forEachNonLegacyItem(
         item -> {
-          assert isNotSyntheticType(item.getContext().getSynthesizingContextType());
+          assert isNotSyntheticType(item.getContext().getSynthesizingContextType())
+              || item.getKind().allowSyntheticContext();
         });
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
index f63d186..65c53d5 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticItems.java
@@ -150,6 +150,7 @@
   @Override
   public DexClass definitionFor(DexType type, Function<DexType, DexClass> baseDefinitionFor) {
     DexClass clazz = null;
+    SyntheticKind kind = null;
     LegacySyntheticDefinition legacyItem = pending.legacyClasses.get(type);
     if (legacyItem != null) {
       clazz = legacyItem.getDefinition();
@@ -157,12 +158,15 @@
       SyntheticDefinition<?, ?, ?> item = pending.nonLegacyDefinitions.get(type);
       if (item != null) {
         clazz = item.getHolder();
+        kind = item.getKind();
         assert clazz.isProgramClass() == item.isProgramDefinition();
         assert clazz.isClasspathClass() == item.isClasspathDefinition();
       }
     }
     if (clazz != null) {
+      assert legacyItem != null || kind != null;
       assert baseDefinitionFor.apply(type) == null
+              || (kind != null && kind.mayOverridesNonProgramType)
           : "Pending synthetic definition also present in the active program: " + type;
       return clazz;
     }
@@ -386,6 +390,23 @@
     return clazz;
   }
 
+  public DexProgramClass createFixedClassFromType(
+      SyntheticKind kind,
+      DexType contextType,
+      DexItemFactory factory,
+      Consumer<SyntheticProgramClassBuilder> fn) {
+    // Obtain the outer synthesizing context in the case the context itself is synthetic.
+    // This is to ensure a flat input-type -> synthetic-item mapping.
+    SynthesizingContext outerContext = SynthesizingContext.fromType(contextType);
+    DexType type = SyntheticNaming.createFixedType(kind, outerContext, factory);
+    SyntheticProgramClassBuilder classBuilder =
+        new SyntheticProgramClassBuilder(type, outerContext, factory);
+    fn.accept(classBuilder);
+    DexProgramClass clazz = classBuilder.build();
+    addPendingDefinition(new SyntheticProgramClassDefinition(kind, outerContext, clazz));
+    return clazz;
+  }
+
   public DexClasspathClass createFixedClasspathClass(
       SyntheticKind kind, DexClasspathClass context, DexItemFactory factory) {
     // Obtain the outer synthesizing context in the case the context itself is synthetic.
@@ -476,7 +497,12 @@
         if (!removedClasses.contains(definition.getHolder().getType())) {
           if (definition.isProgramDefinition()) {
             committedProgramTypesBuilder.add(definition.getHolder().getType());
-            appBuilder.addProgramClass(definition.asProgramDefinition().getHolder());
+            if (definition.getKind().mayOverridesNonProgramType) {
+              appBuilder.addProgramClassPotentiallyOverridingNonProgramClass(
+                  definition.asProgramDefinition().getHolder());
+            } else {
+              appBuilder.addProgramClass(definition.asProgramDefinition().getHolder());
+            }
           } else if (appBuilder.isDirect()) {
             assert definition.isClasspathDefinition();
             appBuilder.asDirect().addClasspathClass(definition.asClasspathDefinition().getHolder());
diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java
index 1b80f41..c3a9d9c 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticNaming.java
@@ -23,6 +23,7 @@
    */
   public enum SyntheticKind {
     // Class synthetics.
+    RECORD_TAG("", false, true, true),
     COMPANION_CLASS("CompanionClass", false),
     LAMBDA("Lambda", false),
     INIT_TYPE_ARGUMENT("-IA", false, true),
@@ -41,6 +42,7 @@
     public final String descriptor;
     public final boolean isSingleSyntheticMethod;
     public final boolean isFixedSuffixSynthetic;
+    public final boolean mayOverridesNonProgramType;
 
     SyntheticKind(String descriptor, boolean isSingleSyntheticMethod) {
       this(descriptor, isSingleSyntheticMethod, false);
@@ -48,9 +50,22 @@
 
     SyntheticKind(
         String descriptor, boolean isSingleSyntheticMethod, boolean isFixedSuffixSynthetic) {
+      this(descriptor, isSingleSyntheticMethod, isFixedSuffixSynthetic, false);
+    }
+
+    SyntheticKind(
+        String descriptor,
+        boolean isSingleSyntheticMethod,
+        boolean isFixedSuffixSynthetic,
+        boolean mayOverridesNonProgramType) {
       this.descriptor = descriptor;
       this.isSingleSyntheticMethod = isSingleSyntheticMethod;
       this.isFixedSuffixSynthetic = isFixedSuffixSynthetic;
+      this.mayOverridesNonProgramType = mayOverridesNonProgramType;
+    }
+
+    public boolean allowSyntheticContext() {
+      return this == RECORD_TAG;
     }
 
     public static SyntheticKind fromDescriptor(String descriptor) {
diff --git a/src/main/java/com/android/tools/r8/utils/ClassMap.java b/src/main/java/com/android/tools/r8/utils/ClassMap.java
index 3c7b99b..c885d9e 100644
--- a/src/main/java/com/android/tools/r8/utils/ClassMap.java
+++ b/src/main/java/com/android/tools/r8/utils/ClassMap.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexType;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
 import java.util.Iterator;
@@ -115,6 +116,21 @@
   }
 
   /**
+   * Clears the type so if a class with the given type was present, it cannot be found anymore. This
+   * has to be run at a join point, concurrent accesses may be confused.
+   */
+  public void clearType(DexType type) {
+    if (classes.containsKey(type)) {
+      classes.remove(type);
+    }
+    ClassProvider<T> provider = classProvider.get();
+    if (provider == null) {
+      return;
+    }
+    classProvider.set(provider.without(ImmutableSet.of(type)));
+  }
+
+  /**
    * Returns all classes from the collection. The collection must be force-loaded.
    */
   public List<T> getAllClasses() {
diff --git a/src/main/java/com/android/tools/r8/utils/ClassProvider.java b/src/main/java/com/android/tools/r8/utils/ClassProvider.java
index c048529..af272b8 100644
--- a/src/main/java/com/android/tools/r8/utils/ClassProvider.java
+++ b/src/main/java/com/android/tools/r8/utils/ClassProvider.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.graph.JarApplicationReader;
 import com.android.tools.r8.graph.JarClassFileReader;
 import com.google.common.collect.ImmutableListMultimap;
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Multimap;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
@@ -70,6 +71,10 @@
     return new PreloadedClassProvider<>(classKind, builder.build());
   }
 
+  public FilteringClassProvider<T> without(Set<DexType> filteredTypes) {
+    return new FilteringClassProvider(classKind, this, filteredTypes);
+  }
+
   /** Create class provider for preloaded classes. */
   public static <T extends DexClass> ClassProvider<T> combine(
       ClassKind<T> classKind, List<ClassProvider<T>> providers) {
@@ -145,6 +150,47 @@
     }
   }
 
+  /** Class provider which ignores a list of filtered classes */
+  private static class FilteringClassProvider<T extends DexClass> extends ClassProvider<T> {
+    private final ClassProvider<T> provider;
+    private final Set<DexType> filteredOut;
+
+    FilteringClassProvider(
+        ClassKind<T> classKind, ClassProvider<T> provider, Set<DexType> filteredOut) {
+      super(classKind);
+      assert !(provider instanceof FilteringClassProvider) : "Nested Filtering class providers";
+      this.provider = provider;
+      this.filteredOut = filteredOut;
+    }
+
+    @Override
+    public FilteringClassProvider<T> without(Set<DexType> filteredTypes) {
+      ImmutableSet<DexType> newSet =
+          ImmutableSet.<DexType>builder().addAll(filteredOut).addAll(filteredTypes).build();
+      return new FilteringClassProvider(getClassKind(), provider, newSet);
+    }
+
+    @Override
+    public void collectClass(DexType type, Consumer<T> classConsumer) {
+      if (filteredOut.contains(type)) {
+        return;
+      }
+      provider.collectClass(type, classConsumer);
+    }
+
+    @Override
+    public Collection<DexType> collectTypes() {
+      Collection<DexType> dexTypes = provider.collectTypes();
+      dexTypes.removeAll(filteredOut);
+      return dexTypes;
+    }
+
+    @Override
+    public String toString() {
+      return provider + " without " + filteredOut;
+    }
+  }
+
   private static class CombinedClassProvider<T extends DexClass> extends ClassProvider<T> {
     private final List<ClassProvider<T>> providers;
 
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index 59d3b10..f2587df 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -490,9 +490,16 @@
     return !canUseNestBasedAccess();
   }
 
-  public boolean canUseRecords() {
-    // TODO(b/169645628): Replace by true when records are supported.
-    return testing.canUseRecords;
+  public boolean enableExperimentalRecordDesugaring() {
+    // TODO(b/169645628): Remove when records are supported.
+    return testing.enableExperimentalRecordDesugaring;
+  }
+
+  public boolean shouldDesugarRecords() {
+    if (!enableExperimentalRecordDesugaring()) {
+      return false;
+    }
+    return desugarState.isOn() && !canUseRecords();
   }
 
   public Set<String> extensiveLoggingFilter = getExtensiveLoggingFilter();
@@ -1294,7 +1301,7 @@
     public boolean enableSwitchToIfRewriting = true;
     public boolean enableEnumUnboxingDebugLogs = false;
     public boolean forceRedundantConstNumberRemoval = false;
-    public boolean canUseRecords = false;
+    public boolean enableExperimentalRecordDesugaring = false;
     public boolean invertConditionals = false;
     public boolean placeExceptionalBlocksLast = false;
     public boolean dontCreateMarkerInD8 = false;
@@ -1455,6 +1462,10 @@
     return !isDesugaring();
   }
 
+  public boolean canUseRecords() {
+    return !isDesugaring();
+  }
+
   public boolean canLeaveStaticInterfaceMethodInvokes() {
     return !isDesugaring() || hasMinApi(AndroidApiLevel.L);
   }
diff --git a/src/test/java/com/android/tools/r8/desugar/records/EmptyRecordTest.java b/src/test/java/com/android/tools/r8/desugar/records/EmptyRecordTest.java
index c68ec40..2e97d1e 100644
--- a/src/test/java/com/android/tools/r8/desugar/records/EmptyRecordTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/records/EmptyRecordTest.java
@@ -57,7 +57,7 @@
             .addKeepMainRule(MAIN_TYPE)
             .addLibraryFiles(RecordTestUtils.getJdk15LibraryFiles(temp))
             .addOptionsModification(TestingOptions::allowExperimentClassFileVersion)
-            .addOptionsModification(opt -> opt.testing.canUseRecords = true)
+            .addOptionsModification(opt -> opt.testing.enableExperimentalRecordDesugaring = true)
             .compile()
             .writeToZip();
     RecordTestUtils.assertRecordsAreRecords(output);
diff --git a/src/test/java/com/android/tools/r8/desugar/records/RecordInstanceOfTest.java b/src/test/java/com/android/tools/r8/desugar/records/RecordInstanceOfTest.java
index 811d24a..5fce5e2 100644
--- a/src/test/java/com/android/tools/r8/desugar/records/RecordInstanceOfTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/records/RecordInstanceOfTest.java
@@ -57,7 +57,7 @@
             .addKeepMainRule(MAIN_TYPE)
             .addLibraryFiles(RecordTestUtils.getJdk15LibraryFiles(temp))
             .addOptionsModification(TestingOptions::allowExperimentClassFileVersion)
-            .addOptionsModification(opt -> opt.testing.canUseRecords = true)
+            .addOptionsModification(opt -> opt.testing.enableExperimentalRecordDesugaring = true)
             .compile()
             .writeToZip();
     RecordTestUtils.assertRecordsAreRecords(output);
diff --git a/src/test/java/com/android/tools/r8/desugar/records/RecordInvokeCustomTest.java b/src/test/java/com/android/tools/r8/desugar/records/RecordInvokeCustomTest.java
index fc7a247..071af85 100644
--- a/src/test/java/com/android/tools/r8/desugar/records/RecordInvokeCustomTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/records/RecordInvokeCustomTest.java
@@ -70,7 +70,7 @@
             .addKeepMainRule(MAIN_TYPE)
             .addLibraryFiles(RecordTestUtils.getJdk15LibraryFiles(temp))
             .addOptionsModification(TestingOptions::allowExperimentClassFileVersion)
-            .addOptionsModification(opt -> opt.testing.canUseRecords = true)
+            .addOptionsModification(opt -> opt.testing.enableExperimentalRecordDesugaring = true)
             .compile()
             .writeToZip();
     RecordTestUtils.assertRecordsAreRecords(output);
diff --git a/src/test/java/com/android/tools/r8/desugar/records/RecordReflectionTest.java b/src/test/java/com/android/tools/r8/desugar/records/RecordReflectionTest.java
index eca975d..15684fe 100644
--- a/src/test/java/com/android/tools/r8/desugar/records/RecordReflectionTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/records/RecordReflectionTest.java
@@ -67,7 +67,7 @@
             .addKeepMainRule(MAIN_TYPE)
             .addLibraryFiles(RecordTestUtils.getJdk15LibraryFiles(temp))
             .addOptionsModification(TestingOptions::allowExperimentClassFileVersion)
-            .addOptionsModification(opt -> opt.testing.canUseRecords = true)
+            .addOptionsModification(opt -> opt.testing.enableExperimentalRecordDesugaring = true)
             .compile()
             .writeToZip();
     RecordTestUtils.assertRecordsAreRecords(output);
diff --git a/src/test/java/com/android/tools/r8/desugar/records/RecordTestUtils.java b/src/test/java/com/android/tools/r8/desugar/records/RecordTestUtils.java
index 3a0a306..7589764 100644
--- a/src/test/java/com/android/tools/r8/desugar/records/RecordTestUtils.java
+++ b/src/test/java/com/android/tools/r8/desugar/records/RecordTestUtils.java
@@ -99,7 +99,8 @@
   }
 
   public static void assertRecordsAreRecords(Path output) throws IOException {
-    CodeInspector inspector = new CodeInspector(output, opt -> opt.testing.canUseRecords = true);
+    CodeInspector inspector =
+        new CodeInspector(output, opt -> opt.testing.enableExperimentalRecordDesugaring = true);
     for (FoundClassSubject clazz : inspector.allClasses()) {
       if (clazz.getDexProgramClass().superType.toString().equals("java.lang.Record")) {
         assertTrue(clazz.getDexProgramClass().isRecord());
diff --git a/src/test/java/com/android/tools/r8/desugar/records/RecordWithMembersTest.java b/src/test/java/com/android/tools/r8/desugar/records/RecordWithMembersTest.java
index e6d1444..610b061 100644
--- a/src/test/java/com/android/tools/r8/desugar/records/RecordWithMembersTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/records/RecordWithMembersTest.java
@@ -61,7 +61,7 @@
             .addKeepMainRule(MAIN_TYPE)
             .addLibraryFiles(RecordTestUtils.getJdk15LibraryFiles(temp))
             .addOptionsModification(TestingOptions::allowExperimentClassFileVersion)
-            .addOptionsModification(opt -> opt.testing.canUseRecords = true)
+            .addOptionsModification(opt -> opt.testing.enableExperimentalRecordDesugaring = true)
             .compile()
             .writeToZip();
     RecordTestUtils.assertRecordsAreRecords(output);
diff --git a/src/test/java/com/android/tools/r8/desugar/records/SimpleRecordTest.java b/src/test/java/com/android/tools/r8/desugar/records/SimpleRecordTest.java
index ff540d1..d5d2b1a 100644
--- a/src/test/java/com/android/tools/r8/desugar/records/SimpleRecordTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/records/SimpleRecordTest.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.utils.StringUtils;
 import java.nio.file.Path;
 import java.util.List;
+import org.junit.Assume;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -36,20 +37,37 @@
   public static List<Object[]> data() {
     // TODO(b/174431251): This should be replaced with .withCfRuntimes(start = jdk15).
     return buildParameters(
-        getTestParameters().withCustomRuntime(CfRuntime.getCheckedInJdk15()).build());
+        getTestParameters()
+            .withCustomRuntime(CfRuntime.getCheckedInJdk15())
+            .withDexRuntimes()
+            .withAllApiLevels()
+            .build());
   }
 
   @Test
-  public void testJvm() throws Exception {
-    testForJvm()
+  public void testD8AndJvm() throws Exception {
+    if (parameters.isCfRuntime()) {
+      testForJvm()
+          .addProgramClassFileData(PROGRAM_DATA)
+          .enablePreview()
+          .run(parameters.getRuntime(), MAIN_TYPE)
+          .assertSuccessWithOutput(EXPECTED_RESULT);
+      // TODO(b/179146128): Add a test for D8 cf to cf.
+      return;
+    }
+    testForD8()
         .addProgramClassFileData(PROGRAM_DATA)
-        .enablePreview()
+        .setMinApi(parameters.getApiLevel())
+        .addOptionsModification(TestingOptions::allowExperimentClassFileVersion)
+        .addOptionsModification(opt -> opt.testing.enableExperimentalRecordDesugaring = true)
+        .compile()
         .run(parameters.getRuntime(), MAIN_TYPE)
         .assertSuccessWithOutput(EXPECTED_RESULT);
   }
 
   @Test
   public void testR8Cf() throws Exception {
+    Assume.assumeTrue(parameters.isCfRuntime());
     Path output =
         testForR8(parameters.getBackend())
             .addProgramClassFileData(PROGRAM_DATA)
@@ -58,7 +76,7 @@
             .addKeepMainRule(MAIN_TYPE)
             .addLibraryFiles(RecordTestUtils.getJdk15LibraryFiles(temp))
             .addOptionsModification(TestingOptions::allowExperimentClassFileVersion)
-            .addOptionsModification(opt -> opt.testing.canUseRecords = true)
+            .addOptionsModification(opt -> opt.testing.enableExperimentalRecordDesugaring = true)
             .compile()
             .writeToZip();
     RecordTestUtils.assertRecordsAreRecords(output);