diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 4025180..7858ad8 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.3.9-dev";
+  public static final String LABEL = "1.3.11-dev";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/graph/GraphLense.java b/src/main/java/com/android/tools/r8/graph/GraphLense.java
index 8de4a6e..84ceac3 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLense.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLense.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.graph;
 
 import com.android.tools.r8.ir.code.Invoke.Type;
+import com.google.common.collect.BiMap;
 import com.google.common.collect.ImmutableSet;
 import java.util.HashSet;
 import java.util.IdentityHashMap;
@@ -78,7 +79,8 @@
       if (typeMap.isEmpty() && methodMap.isEmpty() && fieldMap.isEmpty()) {
         return previousLense;
       }
-      return new NestedGraphLense(typeMap, methodMap, fieldMap, previousLense, dexItemFactory);
+      return new NestedGraphLense(
+          typeMap, methodMap, fieldMap, null, null, previousLense, dexItemFactory);
     }
 
   }
@@ -87,6 +89,10 @@
     return new Builder();
   }
 
+  public abstract DexField getOriginalFieldSignature(DexField field);
+
+  public abstract DexMethod getOriginalMethodSignature(DexMethod method);
+
   public abstract DexType lookupType(DexType type);
 
   // This overload can be used when the graph lense is known to be context insensitive.
@@ -156,6 +162,16 @@
   private static class IdentityGraphLense extends GraphLense {
 
     @Override
+    public DexField getOriginalFieldSignature(DexField field) {
+      return field;
+    }
+
+    @Override
+    public DexMethod getOriginalMethodSignature(DexMethod method) {
+      return method;
+    }
+
+    @Override
     public DexType lookupType(DexType type) {
       return type;
     }
@@ -197,16 +213,47 @@
     protected final Map<DexMethod, DexMethod> methodMap;
     protected final Map<DexField, DexField> fieldMap;
 
-    public NestedGraphLense(Map<DexType, DexType> typeMap, Map<DexMethod, DexMethod> methodMap,
-        Map<DexField, DexField> fieldMap, GraphLense previousLense, DexItemFactory dexItemFactory) {
+    // Maps that store the original signature of fields and methods that have been affected by
+    // vertical class merging. Needed to generate a correct Proguard map in the end.
+    private final BiMap<DexField, DexField> originalFieldSignatures;
+    private final BiMap<DexMethod, DexMethod> originalMethodSignatures;
+
+    public NestedGraphLense(
+        Map<DexType, DexType> typeMap,
+        Map<DexMethod, DexMethod> methodMap,
+        Map<DexField, DexField> fieldMap,
+        BiMap<DexField, DexField> originalFieldSignatures,
+        BiMap<DexMethod, DexMethod> originalMethodSignatures,
+        GraphLense previousLense,
+        DexItemFactory dexItemFactory) {
       this.typeMap = typeMap.isEmpty() ? null : typeMap;
       this.methodMap = methodMap;
       this.fieldMap = fieldMap;
+      this.originalFieldSignatures = originalFieldSignatures;
+      this.originalMethodSignatures = originalMethodSignatures;
       this.previousLense = previousLense;
       this.dexItemFactory = dexItemFactory;
     }
 
     @Override
+    public DexField getOriginalFieldSignature(DexField field) {
+      DexField originalField =
+          originalFieldSignatures != null
+              ? originalFieldSignatures.getOrDefault(field, field)
+              : field;
+      return previousLense.getOriginalFieldSignature(originalField);
+    }
+
+    @Override
+    public DexMethod getOriginalMethodSignature(DexMethod method) {
+      DexMethod originalMethod =
+          originalMethodSignatures != null
+              ? originalMethodSignatures.getOrDefault(method, method)
+              : method;
+      return previousLense.getOriginalMethodSignature(originalMethod);
+    }
+
+    @Override
     public DexType lookupType(DexType type) {
       if (type.isArrayType()) {
         synchronized (this) {
diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java b/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java
index 5b908af..c5d366a 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java
@@ -25,7 +25,10 @@
 import java.nio.charset.StandardCharsets;
 import java.nio.file.Files;
 import java.nio.file.Path;
+import java.util.ArrayList;
+import java.util.Comparator;
 import java.util.HashMap;
+import java.util.List;
 import java.util.Map;
 import java.util.function.Consumer;
 
@@ -150,7 +153,12 @@
   }
 
   public void write(Writer writer) throws IOException {
-    for (ClassNamingForNameMapper naming : classNameMappings.values()) {
+    // Sort classes by their original name such that the generated Proguard map is deterministic
+    // (and easy to navigate manually).
+    List<ClassNamingForNameMapper> classNamingForNameMappers =
+        new ArrayList<>(classNameMappings.values());
+    classNamingForNameMappers.sort(Comparator.comparing(x -> x.originalName));
+    for (ClassNamingForNameMapper naming : classNamingForNameMappers) {
       naming.write(writer);
     }
   }
diff --git a/src/main/java/com/android/tools/r8/optimize/BridgeMethodAnalysis.java b/src/main/java/com/android/tools/r8/optimize/BridgeMethodAnalysis.java
index 492bcd0..6ba18ac 100644
--- a/src/main/java/com/android/tools/r8/optimize/BridgeMethodAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/BridgeMethodAnalysis.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.optimize;
 
+import com.android.tools.r8.errors.Unimplemented;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexField;
@@ -88,6 +89,17 @@
     }
 
     @Override
+    public DexField getOriginalFieldSignature(DexField field) {
+      return previousLense.getOriginalFieldSignature(field);
+    }
+
+    @Override
+    public DexMethod getOriginalMethodSignature(DexMethod method) {
+      // TODO(b/79143143): implement this when re-enable bridge analysis.
+      throw new Unimplemented("BridgeLense.getOriginalMethodSignature() not implemented");
+    }
+
+    @Override
     public DexType lookupType(DexType type) {
       return previousLense.lookupType(type);
     }
diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingLense.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingLense.java
index 4ee0cee..98a0da4 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingLense.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingLense.java
@@ -38,7 +38,8 @@
       Map<DexMethod, DexMethod> methodMap,
       Map<DexField, DexField> fieldMap,
       GraphLense previousLense) {
-    super(ImmutableMap.of(), methodMap, fieldMap, previousLense, appInfo.dexItemFactory);
+    super(
+        ImmutableMap.of(), methodMap, fieldMap, null, null, previousLense, appInfo.dexItemFactory);
     this.appInfo = appInfo;
   }
 
diff --git a/src/main/java/com/android/tools/r8/optimize/PublicizerLense.java b/src/main/java/com/android/tools/r8/optimize/PublicizerLense.java
index 7a9c08f..ad7effd 100644
--- a/src/main/java/com/android/tools/r8/optimize/PublicizerLense.java
+++ b/src/main/java/com/android/tools/r8/optimize/PublicizerLense.java
@@ -25,6 +25,8 @@
         ImmutableMap.of(),
         ImmutableMap.of(),
         ImmutableMap.of(),
+        null,
+        null,
         appView.getGraphLense(),
         appView.getAppInfo().dexItemFactory);
     this.appView = appView;
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index a19c0d5..ee596f3 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -189,7 +189,7 @@
     this.executorService = executorService;
     this.graphLense = appView.getGraphLense();
     this.methodPoolCollection = new MethodPoolCollection(application);
-    this.renamedMembersLense = VerticalClassMergerGraphLense.builder(appInfo);
+    this.renamedMembersLense = new VerticalClassMergerGraphLense.Builder();
     this.timing = timing;
 
     Iterable<DexProgramClass> classes = application.classesWithDeterministicOrder();
@@ -651,7 +651,7 @@
     if (Log.ENABLED) {
       Log.debug(getClass(), "Merged %d classes.", numberOfMerges);
     }
-    return renamedMembersLense.build(graphLense, mergedClasses, application.dexItemFactory);
+    return renamedMembersLense.build(graphLense, mergedClasses, appInfo);
   }
 
   private boolean methodResolutionMayChange(DexClass source, DexClass target) {
@@ -733,7 +733,7 @@
     private final DexClass source;
     private final DexClass target;
     private final VerticalClassMergerGraphLense.Builder deferredRenamings =
-        VerticalClassMergerGraphLense.builder(appInfo);
+        new VerticalClassMergerGraphLense.Builder();
     private boolean abortMerge = false;
 
     private ClassMerger(DexClass source, DexClass target) {
@@ -773,6 +773,7 @@
                   directMethod.isClassInitializer() ? Rename.NEVER : Rename.IF_NEEDED);
           add(directMethods, resultingDirectMethod, MethodSignatureEquivalence.get());
           deferredRenamings.map(directMethod.method, resultingDirectMethod.method);
+          deferredRenamings.recordMove(directMethod.method, resultingDirectMethod.method);
 
           if (!directMethod.isStaticMethod()) {
             blockRedirectionOfSuperCalls(resultingDirectMethod.method);
@@ -802,6 +803,7 @@
             DexEncodedMethod resultingVirtualMethod =
                 renameMethod(virtualMethod, availableMethodSignatures, Rename.NEVER);
             deferredRenamings.map(virtualMethod.method, resultingVirtualMethod.method);
+            deferredRenamings.recordMove(virtualMethod.method, resultingVirtualMethod.method);
             add(virtualMethods, resultingVirtualMethod, MethodSignatureEquivalence.get());
             continue;
           }
@@ -856,6 +858,7 @@
         }
 
         deferredRenamings.map(virtualMethod.method, shadowedBy.method);
+        deferredRenamings.recordMove(virtualMethod.method, resultingDirectMethod.method);
       }
 
       if (abortMerge) {
@@ -1155,6 +1158,7 @@
       DexEncodedMethod result = method.toTypeSubstitutedMethod(newSignature);
       result.markForceInline();
       deferredRenamings.map(method.method, result.method);
+      deferredRenamings.recordMove(method.method, result.method);
       // Renamed constructors turn into ordinary private functions. They can be private, as
       // they are only references from their direct subclass, which they were merged into.
       result.accessFlags.unsetConstructor();
@@ -1510,6 +1514,16 @@
     }
 
     @Override
+    public DexField getOriginalFieldSignature(DexField field) {
+      throw new Unreachable();
+    }
+
+    @Override
+    public DexMethod getOriginalMethodSignature(DexMethod method) {
+      throw new Unreachable();
+    }
+
+    @Override
     public DexType lookupType(DexType type) {
       return type == source ? target : mergedClasses.getOrDefault(type, type);
     }
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLense.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLense.java
index 5974e60..4e09a9e 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLense.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLense.java
@@ -14,6 +14,9 @@
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.graph.GraphLense.NestedGraphLense;
 import com.android.tools.r8.ir.code.Invoke.Type;
+import com.google.common.collect.BiMap;
+import com.google.common.collect.HashBiMap;
+import com.google.common.collect.ImmutableBiMap;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import java.util.HashMap;
@@ -57,17 +60,22 @@
       Map<DexMethod, DexMethod> methodMap,
       Set<DexMethod> mergedMethods,
       Map<DexType, Map<DexMethod, GraphLenseLookupResult>> contextualVirtualToDirectMethodMaps,
+      BiMap<DexField, DexField> originalFieldSignatures,
+      BiMap<DexMethod, DexMethod> originalMethodSignatures,
       GraphLense previousLense) {
-    super(ImmutableMap.of(), methodMap, fieldMap, previousLense, appInfo.dexItemFactory);
+    super(
+        ImmutableMap.of(),
+        methodMap,
+        fieldMap,
+        originalFieldSignatures,
+        originalMethodSignatures,
+        previousLense,
+        appInfo.dexItemFactory);
     this.appInfo = appInfo;
     this.mergedMethods = mergedMethods;
     this.contextualVirtualToDirectMethodMaps = contextualVirtualToDirectMethodMaps;
   }
 
-  public static Builder builder(AppInfo appInfo) {
-    return new Builder(appInfo);
-  }
-
   @Override
   public GraphLenseLookupResult lookupMethod(
       DexMethod method, DexEncodedMethod context, Type type) {
@@ -136,60 +144,107 @@
   }
 
   public static class Builder {
-    private final AppInfo appInfo;
 
-    protected final Map<DexField, DexField> fieldMap = new HashMap<>();
+    protected final BiMap<DexField, DexField> fieldMap = HashBiMap.create();
     protected final Map<DexMethod, DexMethod> methodMap = new HashMap<>();
     private final ImmutableSet.Builder<DexMethod> mergedMethodsBuilder = ImmutableSet.builder();
     private final Map<DexType, Map<DexMethod, GraphLenseLookupResult>>
         contextualVirtualToDirectMethodMaps = new HashMap<>();
 
-    private Builder(AppInfo appInfo) {
-      this.appInfo = appInfo;
-    }
+    private final Map<DexMethod, DexMethod> originalMethodSignatures = HashBiMap.create();
 
     public GraphLense build(
-        GraphLense previousLense,
-        Map<DexType, DexType> mergedClasses,
-        DexItemFactory dexItemFactory) {
+        GraphLense previousLense, Map<DexType, DexType> mergedClasses, AppInfo appInfo) {
       if (fieldMap.isEmpty()
           && methodMap.isEmpty()
           && contextualVirtualToDirectMethodMaps.isEmpty()) {
         return previousLense;
       }
+      Map<DexProto, DexProto> cache = new HashMap<>();
+      BiMap<DexField, DexField> originalFieldSignatures = fieldMap.inverse();
       return new VerticalClassMergerGraphLense(
           appInfo,
           fieldMap,
           methodMap,
           getMergedMethodSignaturesAfterClassMerging(
-              mergedMethodsBuilder.build(), mergedClasses, dexItemFactory),
+              mergedMethodsBuilder.build(), mergedClasses, appInfo.dexItemFactory, cache),
           contextualVirtualToDirectMethodMaps,
+          getOriginalFieldSignaturesAfterClassMerging(
+              originalFieldSignatures, mergedClasses, appInfo.dexItemFactory),
+          getOriginalMethodSignaturesAfterClassMerging(
+              originalMethodSignatures, mergedClasses, appInfo.dexItemFactory, cache),
           previousLense);
     }
 
     // After we have recorded that a method "a.b.c.Foo;->m(A, B, C)V" was merged into another class,
     // it could be that the class B was merged into its subclass B'. In that case we update the
     // signature to "a.b.c.Foo;->m(A, B', C)V".
-    private Set<DexMethod> getMergedMethodSignaturesAfterClassMerging(
+    private static Set<DexMethod> getMergedMethodSignaturesAfterClassMerging(
         Set<DexMethod> mergedMethods,
         Map<DexType, DexType> mergedClasses,
-        DexItemFactory dexItemFactory) {
+        DexItemFactory dexItemFactory,
+        Map<DexProto, DexProto> cache) {
       ImmutableSet.Builder<DexMethod> result = ImmutableSet.builder();
-      Map<DexProto, DexProto> cache = new HashMap<>();
       for (DexMethod signature : mergedMethods) {
-        DexType newHolder = mergedClasses.getOrDefault(signature.holder, signature.holder);
-        DexProto newProto =
-            dexItemFactory.applyClassMappingToProto(
-                signature.proto, type -> mergedClasses.getOrDefault(type, type), cache);
-        if (signature.holder.equals(newHolder) && signature.proto.equals(newProto)) {
-          result.add(signature);
-        } else {
-          result.add(dexItemFactory.createMethod(newHolder, newProto, signature.name));
-        }
+        result.add(
+            getMethodSignatureAfterClassMerging(signature, mergedClasses, dexItemFactory, cache));
       }
       return result.build();
     }
 
+    private static BiMap<DexField, DexField> getOriginalFieldSignaturesAfterClassMerging(
+        Map<DexField, DexField> originalFieldSignatures,
+        Map<DexType, DexType> mergedClasses,
+        DexItemFactory dexItemFactory) {
+      ImmutableBiMap.Builder<DexField, DexField> result = ImmutableBiMap.builder();
+      for (Map.Entry<DexField, DexField> entry : originalFieldSignatures.entrySet()) {
+        result.put(
+            getFieldSignatureAfterClassMerging(entry.getKey(), mergedClasses, dexItemFactory),
+            entry.getValue());
+      }
+      return result.build();
+    }
+
+    private static BiMap<DexMethod, DexMethod> getOriginalMethodSignaturesAfterClassMerging(
+        Map<DexMethod, DexMethod> originalMethodSignatures,
+        Map<DexType, DexType> mergedClasses,
+        DexItemFactory dexItemFactory,
+        Map<DexProto, DexProto> cache) {
+      ImmutableBiMap.Builder<DexMethod, DexMethod> result = ImmutableBiMap.builder();
+      for (Map.Entry<DexMethod, DexMethod> entry : originalMethodSignatures.entrySet()) {
+        result.put(
+            getMethodSignatureAfterClassMerging(
+                entry.getKey(), mergedClasses, dexItemFactory, cache),
+            entry.getValue());
+      }
+      return result.build();
+    }
+
+    private static DexField getFieldSignatureAfterClassMerging(
+        DexField signature, Map<DexType, DexType> mergedClasses, DexItemFactory dexItemFactory) {
+      DexType newClass = mergedClasses.getOrDefault(signature.clazz, signature.clazz);
+      DexType newType = mergedClasses.getOrDefault(signature.type, signature.type);
+      if (signature.clazz.equals(newClass) && signature.type.equals(newType)) {
+        return signature;
+      }
+      return dexItemFactory.createField(newClass, newType, signature.name);
+    }
+
+    private static DexMethod getMethodSignatureAfterClassMerging(
+        DexMethod signature,
+        Map<DexType, DexType> mergedClasses,
+        DexItemFactory dexItemFactory,
+        Map<DexProto, DexProto> cache) {
+      DexType newHolder = mergedClasses.getOrDefault(signature.holder, signature.holder);
+      DexProto newProto =
+          dexItemFactory.applyClassMappingToProto(
+              signature.proto, type -> mergedClasses.getOrDefault(type, type), cache);
+      if (signature.holder.equals(newHolder) && signature.proto.equals(newProto)) {
+        return signature;
+      }
+      return dexItemFactory.createMethod(newHolder, newProto, signature.name);
+    }
+
     public boolean hasMappingForSignatureInContext(DexType context, DexMethod signature) {
       Map<DexMethod, GraphLenseLookupResult> virtualToDirectMethodMap =
           contextualVirtualToDirectMethodMaps.get(context);
@@ -211,6 +266,10 @@
       methodMap.put(from, to);
     }
 
+    public void recordMove(DexMethod from, DexMethod to) {
+      originalMethodSignatures.put(to, from);
+    }
+
     public void mapVirtualMethodToDirectInType(
         DexMethod from, GraphLenseLookupResult to, DexType type) {
       Map<DexMethod, GraphLenseLookupResult> virtualToDirectMethodMap =
@@ -222,6 +281,7 @@
       fieldMap.putAll(builder.fieldMap);
       methodMap.putAll(builder.methodMap);
       mergedMethodsBuilder.addAll(builder.mergedMethodsBuilder.build());
+      originalMethodSignatures.putAll(builder.originalMethodSignatures);
       for (DexType context : builder.contextualVirtualToDirectMethodMaps.keySet()) {
         Map<DexMethod, GraphLenseLookupResult> current =
             contextualVirtualToDirectMethodMaps.get(context);
diff --git a/src/main/java/com/android/tools/r8/utils/AndroidApiLevel.java b/src/main/java/com/android/tools/r8/utils/AndroidApiLevel.java
index 127debe..135e961 100644
--- a/src/main/java/com/android/tools/r8/utils/AndroidApiLevel.java
+++ b/src/main/java/com/android/tools/r8/utils/AndroidApiLevel.java
@@ -9,6 +9,7 @@
  * Android API level description
  */
 public enum AndroidApiLevel {
+  Q(29),  // Speculative, this can change.
   P(28),
   O_MR1(27),
   O(26),
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 93a80b6..ae99990 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -537,7 +537,7 @@
   //
   // See b/69364976 and b/77996377.
   public boolean canHaveBoundsCheckEliminationBug() {
-    return minApiLevel <= AndroidApiLevel.L.getLevel();
+    return minApiLevel < AndroidApiLevel.M.getLevel();
   }
 
   // MediaTek JIT compilers for KitKat phones did not implement the not
@@ -631,7 +631,7 @@
   //
   // See b/78493232 and b/80118070.
   public boolean canHaveArtStringNewInitBug() {
-    return minApiLevel <= AndroidApiLevel.P.getLevel();
+    return minApiLevel < AndroidApiLevel.Q.getLevel();
   }
 
   // Dalvik tracing JIT may perform invalid optimizations when int/float values are converted to
@@ -639,6 +639,6 @@
   //
   // See b/77496850.
   public boolean canHaveNumberConversionRegisterAllocationBug() {
-    return minApiLevel <= AndroidApiLevel.K.getLevel();
+    return minApiLevel < AndroidApiLevel.L.getLevel();
   }
 }