diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java
index 8db4392..e359150 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -1154,6 +1154,10 @@
   /** Returns kotlin class info if the class is synthesized by kotlin compiler. */
   public abstract KotlinClassLevelInfo getKotlinInfo();
 
+  public final String getSimpleName() {
+    return getType().getSimpleName();
+  }
+
   public final String getTypeName() {
     return getType().getTypeName();
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexMethodHandle.java b/src/main/java/com/android/tools/r8/graph/DexMethodHandle.java
index 227270d..63c3261 100644
--- a/src/main/java/com/android/tools/r8/graph/DexMethodHandle.java
+++ b/src/main/java/com/android/tools/r8/graph/DexMethodHandle.java
@@ -323,7 +323,7 @@
         .withConditionalItem(DexMethodHandle::isFieldHandle, DexMethodHandle::asField)
         .withConditionalItem(DexMethodHandle::isMethodHandle, DexMethodHandle::asMethod)
         .withBool(m -> m.isInterface)
-        .withItem(m -> m.rewrittenTarget);
+        .withNullableItem(m -> m.rewrittenTarget);
   }
 
   public Handle toAsmHandle() {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
index e16a15f..202f78c 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
@@ -83,7 +83,8 @@
     // Run the policies on all program classes to produce a final grouping.
     List<Policy> policies =
         PolicyScheduler.getPolicies(appView, codeProvider, mode, runtimeTypeCheckInfo);
-    Collection<MergeGroup> groups = new PolicyExecutor().run(getInitialGroups(), policies, timing);
+    Collection<MergeGroup> groups =
+        new PolicyExecutor().run(getInitialGroups(), policies, executorService, timing);
 
     // If there are no groups, then end horizontal class merging.
     if (groups.isEmpty()) {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/MultiClassPolicyWithPreprocessing.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/MultiClassPolicyWithPreprocessing.java
index 067fcd5..d634479 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/MultiClassPolicyWithPreprocessing.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/MultiClassPolicyWithPreprocessing.java
@@ -5,6 +5,8 @@
 package com.android.tools.r8.horizontalclassmerging;
 
 import java.util.Collection;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
 
 public abstract class MultiClassPolicyWithPreprocessing<T> extends Policy {
 
@@ -12,14 +14,15 @@
    * Apply the multi class policy to a group of program classes.
    *
    * @param group This is a group of program classes which can currently still be merged.
-   * @param data The result of calling {@link #preprocess(Collection)}.
+   * @param data The result of calling {@link #preprocess(Collection, ExecutorService)}.
    * @return The same collection of program classes split into new groups of candidates which can be
    *     merged. If the policy detects no issues then `group` will be returned unchanged. If classes
    *     cannot be merged with any other classes they are returned as singleton lists.
    */
   public abstract Collection<MergeGroup> apply(MergeGroup group, T data);
 
-  public abstract T preprocess(Collection<MergeGroup> groups);
+  public abstract T preprocess(Collection<MergeGroup> groups, ExecutorService executorService)
+      throws ExecutionException;
 
   @Override
   public boolean isMultiClassPolicyWithPreprocessing() {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyExecutor.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyExecutor.java
index c1c4f64..c206e75 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyExecutor.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyExecutor.java
@@ -9,6 +9,8 @@
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.LinkedList;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
 
 /**
  * This is a simple policy executor that ensures regular sequential execution of policies. It should
@@ -50,9 +52,12 @@
   }
 
   private <T> LinkedList<MergeGroup> applyMultiClassPolicyWithPreprocessing(
-      MultiClassPolicyWithPreprocessing<T> policy, LinkedList<MergeGroup> groups) {
+      MultiClassPolicyWithPreprocessing<T> policy,
+      LinkedList<MergeGroup> groups,
+      ExecutorService executorService)
+      throws ExecutionException {
     // For each group apply the multi class policy and add all the new groups together.
-    T data = policy.preprocess(groups);
+    T data = policy.preprocess(groups, executorService);
     LinkedList<MergeGroup> newGroups = new LinkedList<>();
     groups.forEach(
         group -> {
@@ -73,7 +78,11 @@
    * class groups.
    */
   public Collection<MergeGroup> run(
-      Collection<MergeGroup> inputGroups, Collection<Policy> policies, Timing timing) {
+      Collection<MergeGroup> inputGroups,
+      Collection<Policy> policies,
+      ExecutorService executorService,
+      Timing timing)
+      throws ExecutionException {
     LinkedList<MergeGroup> linkedGroups;
 
     if (inputGroups instanceof LinkedList) {
@@ -96,7 +105,7 @@
         assert policy.isMultiClassPolicyWithPreprocessing();
         linkedGroups =
             applyMultiClassPolicyWithPreprocessing(
-                policy.asMultiClassPolicyWithPreprocessing(), linkedGroups);
+                policy.asMultiClassPolicyWithPreprocessing(), linkedGroups, executorService);
       }
       timing.end();
 
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyScheduler.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyScheduler.java
index b536669..fbbe362 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyScheduler.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyScheduler.java
@@ -71,6 +71,7 @@
             .addAll(getSingleClassPolicies(appView, mode, runtimeTypeCheckInfo))
             .addAll(getMultiClassPolicies(appView, codeProvider, mode, runtimeTypeCheckInfo))
             .build();
+    policies = appView.options().testing.horizontalClassMergingPolicyRewriter.apply(policies);
     assert verifyPolicyOrderingConstraints(policies);
     return policies;
   }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoClassInitializerCycles.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoClassInitializerCycles.java
index f8faefd..e8eb14e 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoClassInitializerCycles.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoClassInitializerCycles.java
@@ -5,12 +5,13 @@
 package com.android.tools.r8.horizontalclassmerging.policies;
 
 import static com.android.tools.r8.graph.DexClassAndMethod.asProgramMethodOrNull;
-import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
+import static com.android.tools.r8.ir.desugar.LambdaDescriptor.isLambdaMetafactoryMethod;
 import static com.android.tools.r8.utils.MapUtils.ignoreKey;
 
 import com.android.tools.r8.code.CfOrDexInstruction;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexCallSite;
+import com.android.tools.r8.graph.DexClassAndMethod;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
@@ -20,10 +21,11 @@
 import com.android.tools.r8.graph.UseRegistry;
 import com.android.tools.r8.horizontalclassmerging.MergeGroup;
 import com.android.tools.r8.horizontalclassmerging.MultiClassPolicyWithPreprocessing;
-import com.android.tools.r8.ir.desugar.LambdaDescriptor;
+import com.android.tools.r8.horizontalclassmerging.policies.deadlock.SingleCallerInformation;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.InternalOptions.HorizontalClassMergerOptions;
 import com.android.tools.r8.utils.SetUtils;
+import com.android.tools.r8.utils.TraversalContinuation;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Sets;
@@ -32,11 +34,14 @@
 import java.util.Collections;
 import java.util.Deque;
 import java.util.IdentityHashMap;
+import java.util.LinkedHashMap;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.ListIterator;
 import java.util.Map;
 import java.util.Set;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
 
 /**
  * Disallows merging of classes when the merging could introduce class initialization deadlocks.
@@ -93,37 +98,68 @@
   // Mapping from each merge candidate to its merge group.
   final Map<DexProgramClass, MergeGroup> allGroups = new IdentityHashMap<>();
 
+  private SingleCallerInformation singleCallerInformation;
+
   public NoClassInitializerCycles(AppView<AppInfoWithLiveness> appView) {
     this.appView = appView;
   }
 
   @Override
   public Collection<MergeGroup> apply(MergeGroup group, Void nothing) {
-    Tracer tracer = new Tracer(group);
-    removeClassesWithPossibleClassInitializerDeadlock(group, tracer);
-
+    // Partition the merge group into smaller groups that may be merged. If the class initialization
+    // of a parent class may initialize a member of the merge group, then this member is not
+    // eligible for class merging, unless the only way to class initialize this member is from the
+    // class initialization of the parent class. In this case, the member may be merged with other
+    // group members that are also guaranteed to only be class initialized from the class
+    // initialization of the parent class.
+    List<MergeGroup> partitioning = partitionClassesWithPossibleClassInitializerDeadlock(group);
     List<MergeGroup> newGroups = new LinkedList<>();
-    for (DexProgramClass clazz : group) {
-      MergeGroup newGroup = getOrCreateGroupFor(clazz, newGroups, tracer);
-      if (newGroup != null) {
-        newGroup.add(clazz);
-      } else {
-        // Ineligible for merging.
+
+    // Revisit each partition. If the class initialization of a group member may initialize another
+    // class (not necessarily a group member), and vice versa, then class initialization could
+    // deadlock if the group member is merged with another class that is initialized concurrently.
+    for (MergeGroup partition : partitioning) {
+      List<MergeGroup> newGroupsFromPartition = new LinkedList<>();
+      Tracer tracer = new Tracer(partition);
+      for (DexProgramClass clazz : partition) {
+        MergeGroup newGroup = getOrCreateGroupFor(clazz, newGroupsFromPartition, tracer);
+        if (newGroup != null) {
+          newGroup.add(clazz);
+        } else {
+          // Ineligible for merging.
+        }
+      }
+      newGroups.addAll(newGroupsFromPartition);
+    }
+    removeTrivialGroups(newGroups);
+    commit(group, newGroups);
+    return newGroups;
+  }
+
+  private void commit(MergeGroup oldGroup, List<MergeGroup> newGroups) {
+    for (MergeGroup newGroup : newGroups) {
+      for (DexProgramClass member : newGroup) {
+        allGroups.put(member, newGroup);
       }
     }
-    return removeTrivialGroups(newGroups);
+    for (DexProgramClass member : oldGroup) {
+      MergeGroup newGroup = allGroups.get(member);
+      if (newGroup == oldGroup) {
+        allGroups.remove(member);
+      }
+    }
   }
 
   private MergeGroup getOrCreateGroupFor(
       DexProgramClass clazz, List<MergeGroup> groups, Tracer tracer) {
     assert !tracer.hasPossibleClassInitializerDeadlock(clazz);
 
-    ProgramMethod classInitializer = clazz.getProgramClassInitializer();
-    if (classInitializer != null) {
-      assert tracer.verifySeenSetIsEmpty();
-      assert tracer.verifyWorklistIsEmpty();
+    if (clazz.hasClassInitializer()) {
+      // Trace from the class initializer of this group member. If an execution path is found that
+      // leads back to the class initializer then this class may be involved in a deadlock, and we
+      // should not merge any other classes into it.
       tracer.setTracingRoot(clazz);
-      tracer.enqueueMethod(classInitializer);
+      tracer.enqueueTracingRoot(clazz.getProgramClassInitializer());
       tracer.trace();
       if (tracer.hasPossibleClassInitializerDeadlock(clazz)) {
         // Ineligible for merging.
@@ -163,11 +199,63 @@
    * If the class initializer of one of the classes in the merge group is reached, then that class
    * is not eligible for merging.
    */
-  private void removeClassesWithPossibleClassInitializerDeadlock(MergeGroup group, Tracer tracer) {
+  private List<MergeGroup> partitionClassesWithPossibleClassInitializerDeadlock(MergeGroup group) {
+    Set<DexProgramClass> superclasses = Sets.newIdentityHashSet();
+    appView
+        .appInfo()
+        .traverseSuperClasses(
+            group.iterator().next(),
+            (supertype, superclass, immediateSubclass) -> {
+              if (superclass != null && superclass.isProgramClass()) {
+                superclasses.add(superclass.asProgramClass());
+                return TraversalContinuation.CONTINUE;
+              }
+              return TraversalContinuation.BREAK;
+            });
+
+    // Run the tracer from the class initializers of the superclasses.
+    Tracer tracer = new Tracer(group);
     tracer.setTracingRoots(group);
-    tracer.enqueueParentClassInitializers(group);
+    for (DexProgramClass superclass : superclasses) {
+      if (superclass.hasClassInitializer()) {
+        tracer.enqueueTracingRoot(superclass.getProgramClassInitializer());
+      }
+    }
     tracer.trace();
-    group.removeIf(tracer::hasPossibleClassInitializerDeadlock);
+
+    MergeGroup notInitializedByInitializationOfParent = new MergeGroup();
+    Map<DexProgramClass, MergeGroup> partitioning = new LinkedHashMap<>();
+    for (DexProgramClass member : group) {
+      if (tracer.hasPossibleClassInitializerDeadlock(member)) {
+        DexProgramClass nearestLock = getNearestLock(member, superclasses);
+        if (nearestLock != null) {
+          partitioning.computeIfAbsent(nearestLock, ignoreKey(MergeGroup::new)).add(member);
+        } else {
+          // Ineligible for merging.
+        }
+      } else {
+        notInitializedByInitializationOfParent.add(member);
+      }
+    }
+
+    return ImmutableList.<MergeGroup>builder()
+        .add(notInitializedByInitializationOfParent)
+        .addAll(partitioning.values())
+        .build();
+  }
+
+  private DexProgramClass getNearestLock(
+      DexProgramClass clazz, Set<DexProgramClass> candidateOwners) {
+    ProgramMethodSet seen = ProgramMethodSet.create();
+    ProgramMethod singleCaller = singleCallerInformation.getSingleClassInitializerCaller(clazz);
+    while (singleCaller != null && seen.add(singleCaller)) {
+      if (singleCaller.getDefinition().isClassInitializer()
+          && candidateOwners.contains(singleCaller.getHolder())) {
+        return singleCaller.getHolder();
+      }
+      singleCaller = singleCallerInformation.getSingleCaller(singleCaller);
+    }
+    return null;
   }
 
   @Override
@@ -181,12 +269,15 @@
   }
 
   @Override
-  public Void preprocess(Collection<MergeGroup> groups) {
+  public Void preprocess(Collection<MergeGroup> groups, ExecutorService executorService)
+      throws ExecutionException {
     for (MergeGroup group : groups) {
       for (DexProgramClass clazz : group) {
         allGroups.put(clazz, group);
       }
     }
+    singleCallerInformation =
+        SingleCallerInformation.builder(appView).analyze(executorService).build();
     return null;
   }
 
@@ -198,7 +289,10 @@
 
   private class Tracer {
 
-    final Set<DexProgramClass> group;
+    final MergeGroup group;
+
+    // The members of the existing merge group, for efficient membership querying.
+    final Set<DexProgramClass> groupMembers;
 
     private final Set<DexProgramClass> seenClassInitializers = Sets.newIdentityHashSet();
     private final ProgramMethodSet seenMethods = ProgramMethodSet.create();
@@ -214,7 +308,8 @@
     private Collection<DexProgramClass> tracingRoots;
 
     Tracer(MergeGroup group) {
-      this.group = SetUtils.newIdentityHashSet(group);
+      this.group = group;
+      this.groupMembers = SetUtils.newIdentityHashSet(group);
     }
 
     void clearSeen() {
@@ -222,38 +317,30 @@
       seenMethods.clear();
     }
 
+    void clearWorklist() {
+      worklist.clear();
+    }
+
     boolean markClassInitializerAsSeen(DexProgramClass clazz) {
       return seenClassInitializers.add(clazz);
     }
 
     boolean enqueueMethod(ProgramMethod method) {
       if (seenMethods.add(method)) {
-        worklist.add(method);
+        worklist.addLast(method);
         return true;
       }
       return false;
     }
 
-    void enqueueParentClassInitializers(MergeGroup group) {
-      DexProgramClass member = group.iterator().next();
-      enqueueParentClassInitializers(member);
-    }
-
-    void enqueueParentClassInitializers(DexProgramClass clazz) {
-      DexProgramClass superClass =
-          asProgramClassOrNull(appView.definitionFor(clazz.getSuperType()));
-      if (superClass == null) {
-        return;
-      }
-      ProgramMethod classInitializer = superClass.getProgramClassInitializer();
-      if (classInitializer != null) {
-        enqueueMethod(classInitializer);
-      }
-      enqueueParentClassInitializers(superClass);
+    void enqueueTracingRoot(ProgramMethod tracingRoot) {
+      boolean added = seenMethods.add(tracingRoot);
+      assert added;
+      worklist.add(tracingRoot);
     }
 
     void recordClassInitializerReachableFromTracingRoots(DexProgramClass clazz) {
-      assert group.contains(clazz);
+      assert groupMembers.contains(clazz);
       classInitializerReachableFromClasses
           .computeIfAbsent(clazz, ignoreKey(Sets::newIdentityHashSet))
           .addAll(tracingRoots);
@@ -284,20 +371,25 @@
           .contains(classBeingInitialized);
     }
 
+    private void processWorklist() {
+      while (!worklist.isEmpty()) {
+        ProgramMethod method = worklist.removeLast();
+        method.registerCodeReferences(new TracerUseRegistry(method));
+      }
+    }
+
     void setTracingRoot(DexProgramClass tracingRoot) {
       setTracingRoots(ImmutableList.of(tracingRoot));
     }
 
     void setTracingRoots(Collection<DexProgramClass> tracingRoots) {
+      assert verifySeenSetIsEmpty();
+      assert verifyWorklistIsEmpty();
       this.tracingRoots = tracingRoots;
     }
 
     void trace() {
-      // TODO(b/205611444): Avoid redundant tracing of the same methods.
-      while (!worklist.isEmpty()) {
-        ProgramMethod method = worklist.removeLast();
-        method.registerCodeReferences(new TracerUseRegistry(method));
-      }
+      processWorklist();
       clearSeen();
     }
 
@@ -322,6 +414,7 @@
         // Ensures that hasPossibleClassInitializerDeadlock() returns true for each tracing root.
         recordTracingRootsIneligibleForClassMerging();
         doBreak();
+        clearWorklist();
       }
 
       private void triggerClassInitializerIfNotAlreadyTriggeredInContext(DexType type) {
@@ -338,8 +431,6 @@
       }
 
       private boolean isClassAlreadyInitializedInCurrentContext(DexProgramClass clazz) {
-        // TODO(b/205611444): There is only a risk of a deadlock if the execution path comes from
-        //  outside the merge group. We could address this by updating this check.
         return appView.appInfo().isSubtype(getContext().getHolder(), clazz);
       }
 
@@ -350,15 +441,12 @@
         }
       }
 
-      // TODO(b/205611444): This needs to account for pending merging. If the given class is in a
-      //  merge group, then this should trigger the class initializers of all of the classes in the
-      //  merge group.
       private void triggerClassInitializer(DexProgramClass clazz) {
         if (!markClassInitializerAsSeen(clazz)) {
           return;
         }
 
-        if (group.contains(clazz)) {
+        if (groupMembers.contains(clazz)) {
           if (hasSingleTracingRoot(clazz)) {
             // We found an execution path from the class initializer of the given class back to its
             // own class initializer. Therefore this class is not eligible for merging.
@@ -379,11 +467,19 @@
         }
 
         triggerClassInitializer(clazz.getSuperType());
+
+        MergeGroup other = allGroups.get(clazz);
+        if (other != null && other != group) {
+          for (DexProgramClass member : other) {
+            triggerClassInitializer(member);
+          }
+        }
       }
 
       @Override
       public void registerInitClass(DexType type) {
-        triggerClassInitializerIfNotAlreadyTriggeredInContext(type);
+        DexType rewrittenType = appView.graphLens().lookupType(type);
+        triggerClassInitializerIfNotAlreadyTriggeredInContext(rewrittenType);
       }
 
       @Override
@@ -400,7 +496,13 @@
 
       @Override
       public void registerInvokeInterface(DexMethod method) {
-        fail();
+        DexMethod rewrittenMethod =
+            appView.graphLens().lookupInvokeInterface(method, getContext()).getReference();
+        DexClassAndMethod resolvedMethod =
+            appView.appInfo().resolveMethodOnInterface(rewrittenMethod).getResolutionPair();
+        if (resolvedMethod != null) {
+          fail();
+        }
       }
 
       @Override
@@ -432,7 +534,17 @@
 
       @Override
       public void registerInvokeVirtual(DexMethod method) {
-        fail();
+        DexMethod rewrittenMethod =
+            appView.graphLens().lookupInvokeVirtual(method, getContext()).getReference();
+        DexClassAndMethod resolvedMethod =
+            appView.appInfo().resolveMethodOnClass(rewrittenMethod).getResolutionPair();
+        if (resolvedMethod != null) {
+          if (!resolvedMethod.getHolder().isEffectivelyFinal(appView)) {
+            fail();
+          } else if (resolvedMethod.isProgramMethod()) {
+            enqueueMethod(resolvedMethod.asProgramMethod());
+          }
+        }
       }
 
       @Override
@@ -460,9 +572,7 @@
 
       @Override
       public void registerCallSite(DexCallSite callSite) {
-        LambdaDescriptor descriptor =
-            LambdaDescriptor.tryInfer(callSite, appView.appInfo(), getContext());
-        if (descriptor != null) {
+        if (isLambdaMetafactoryMethod(callSite, appView.appInfo())) {
           // Use of lambda metafactory does not trigger any class initialization.
         } else {
           fail();
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoConstructorCollisions.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoConstructorCollisions.java
index 191adc4..e77b31a 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoConstructorCollisions.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoConstructorCollisions.java
@@ -25,6 +25,7 @@
 import java.util.IdentityHashMap;
 import java.util.Map;
 import java.util.Set;
+import java.util.concurrent.ExecutorService;
 
 /**
  * In the final round, we're not allowed to resolve constructor collisions by appending null
@@ -66,7 +67,7 @@
    * lead to constructor collisions.
    */
   @Override
-  public Set<DexType> preprocess(Collection<MergeGroup> groups) {
+  public Set<DexType> preprocess(Collection<MergeGroup> groups, ExecutorService executorService) {
     // Build a mapping from types to groups.
     Map<DexType, MergeGroup> groupsByType = new IdentityHashMap<>();
     for (MergeGroup group : groups) {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoDefaultInterfaceMethodCollisions.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoDefaultInterfaceMethodCollisions.java
index a2362bd..5ebe1a6 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoDefaultInterfaceMethodCollisions.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoDefaultInterfaceMethodCollisions.java
@@ -36,6 +36,7 @@
 import java.util.IdentityHashMap;
 import java.util.Map;
 import java.util.Set;
+import java.util.concurrent.ExecutorService;
 import java.util.function.Function;
 
 /**
@@ -143,7 +144,8 @@
   }
 
   @Override
-  public Map<DexType, InterfaceInfo> preprocess(Collection<MergeGroup> groups) {
+  public Map<DexType, InterfaceInfo> preprocess(
+      Collection<MergeGroup> groups, ExecutorService executorService) {
     SubtypingInfo subtypingInfo = new SubtypingInfo(appView);
     Collection<DexProgramClass> classesOfInterest = computeClassesOfInterest(subtypingInfo);
     Map<DexType, DexMethodSignatureSet> inheritedClassMethodsPerClass =
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/OnlyDirectlyConnectedOrUnrelatedInterfaces.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/OnlyDirectlyConnectedOrUnrelatedInterfaces.java
index c53395c..f86a398 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/OnlyDirectlyConnectedOrUnrelatedInterfaces.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/OnlyDirectlyConnectedOrUnrelatedInterfaces.java
@@ -27,6 +27,7 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.concurrent.ExecutorService;
 import java.util.function.Function;
 
 /**
@@ -160,7 +161,7 @@
   }
 
   @Override
-  public SubtypingInfo preprocess(Collection<MergeGroup> groups) {
+  public SubtypingInfo preprocess(Collection<MergeGroup> groups, ExecutorService executorService) {
     return new SubtypingInfo(appView);
   }
 
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/deadlock/SingleCallerInformation.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/deadlock/SingleCallerInformation.java
new file mode 100644
index 0000000..0e35bf3
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/deadlock/SingleCallerInformation.java
@@ -0,0 +1,262 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.horizontalclassmerging.policies.deadlock;
+
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexMethod;
+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.graph.UseRegistry;
+import com.android.tools.r8.utils.ThreadUtils;
+import com.android.tools.r8.utils.collections.ProgramMethodMap;
+import java.util.IdentityHashMap;
+import java.util.Map;
+import java.util.Optional;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+
+/**
+ * Stores the single caller (if any) for each non-virtual method. Virtual methods are not considered
+ * since computing single caller information for such methods is expensive (it involves computing
+ * the possible dispatch targets for each virtual invoke).
+ *
+ * <p>Unlike the {@link com.android.tools.r8.ir.conversion.CallGraph} that is used to determine if a
+ * method can be single caller inlined, this considers a method that is called from multiple call
+ * sites in the same method to have a single caller.
+ */
+// TODO(b/205611444): account for -keep rules.
+public class SingleCallerInformation {
+
+  private final ProgramMethodMap<ProgramMethod> singleCallers;
+  private final Map<DexProgramClass, ProgramMethod> singleClinitCallers;
+
+  SingleCallerInformation(
+      ProgramMethodMap<ProgramMethod> singleCallers,
+      Map<DexProgramClass, ProgramMethod> singleClinitCallers) {
+    this.singleCallers = singleCallers;
+    this.singleClinitCallers = singleClinitCallers;
+  }
+
+  public static Builder builder(AppView<? extends AppInfoWithClassHierarchy> appView) {
+    return new Builder(appView);
+  }
+
+  public ProgramMethod getSingleCaller(ProgramMethod method) {
+    return singleCallers.get(method);
+  }
+
+  public ProgramMethod getSingleClassInitializerCaller(DexProgramClass clazz) {
+    return singleClinitCallers.get(clazz);
+  }
+
+  public static class Builder {
+
+    private final AppView<? extends AppInfoWithClassHierarchy> appView;
+
+    // The single callers for each method and class initializer.
+    // If a method is not in the map, then a call to that method has never been seen.
+    // If a method is mapped to Optional.empty(), then the method has multiple calling contexts.
+    // If a method is mapped to Optional.of(m), then the method is only called from method m.
+    final ProgramMethodMap<Optional<ProgramMethod>> callers = ProgramMethodMap.createConcurrent();
+    final Map<DexProgramClass, Optional<ProgramMethod>> clinitCallers = new ConcurrentHashMap<>();
+
+    Builder(AppView<? extends AppInfoWithClassHierarchy> appView) {
+      this.appView = appView;
+    }
+
+    public Builder analyze(ExecutorService executorService) throws ExecutionException {
+      ThreadUtils.processItems(
+          appView.appInfo()::forEachMethod, this::processMethod, executorService);
+      return this;
+    }
+
+    public SingleCallerInformation build() {
+      ProgramMethodMap<ProgramMethod> singleCallers = ProgramMethodMap.create();
+      callers.forEach(
+          (method, callers) -> callers.ifPresent(caller -> singleCallers.put(method, caller)));
+      Map<DexProgramClass, ProgramMethod> singleClinitCallers = new IdentityHashMap<>();
+      clinitCallers.forEach(
+          (clazz, callers) -> callers.ifPresent(caller -> singleClinitCallers.put(clazz, caller)));
+      return new SingleCallerInformation(singleCallers, singleClinitCallers);
+    }
+
+    private void processMethod(ProgramMethod method) {
+      method.registerCodeReferences(new InvokeExtractor(appView, method));
+    }
+
+    private class InvokeExtractor extends UseRegistry<ProgramMethod> {
+
+      private final AppView<? extends AppInfoWithClassHierarchy> appView;
+
+      InvokeExtractor(AppView<? extends AppInfoWithClassHierarchy> appView, ProgramMethod context) {
+        super(appView, context);
+        this.appView = appView;
+      }
+
+      private void recordDispatchTarget(ProgramMethod target) {
+        callers.compute(
+            target,
+            (key, value) -> {
+              if (value == null) {
+                // This target is now called from the current context (only).
+                return Optional.of(getContext());
+              }
+              // If the target is only called from the current context, then that is still the
+              // case.
+              if (value.orElse(null) == getContext()) {
+                return value;
+              }
+              // The target is now called from more than one place.
+              return Optional.empty();
+            });
+      }
+
+      private void triggerClassInitializerIfNotAlreadyTriggeredInContext(DexType type) {
+        DexProgramClass clazz = type.asProgramClass(appView);
+        if (clazz != null) {
+          triggerClassInitializerIfNotAlreadyTriggeredInContext(clazz);
+        }
+      }
+
+      private void triggerClassInitializerIfNotAlreadyTriggeredInContext(DexProgramClass clazz) {
+        if (!isClassAlreadyInitializedInCurrentContext(clazz)) {
+          triggerClassInitializer(clazz);
+        }
+      }
+
+      private boolean isClassAlreadyInitializedInCurrentContext(DexProgramClass clazz) {
+        return appView.appInfo().isSubtype(getContext().getHolder(), clazz);
+      }
+
+      private void triggerClassInitializer(DexType type) {
+        DexProgramClass clazz = type.asProgramClass(appView);
+        if (clazz != null) {
+          triggerClassInitializer(clazz);
+        }
+      }
+
+      private void triggerClassInitializer(DexProgramClass clazz) {
+        Optional<ProgramMethod> callers = clinitCallers.get(clazz);
+        if (callers != null) {
+          if (!callers.isPresent()) {
+            // Optional.empty() represents that this class initializer has multiple (unknown)
+            // callers. Since this <clinit> and all of the parent <clinit>s are already triggered
+            // from multiple places, there is no need to record it is also triggered from the
+            // current context.
+            return;
+          }
+          if (callers.get() == getContext()) {
+            // This <clinit> is already triggered from the current context. No need to record this
+            // again.
+            return;
+          }
+        }
+
+        // Record that the given class is now initialized from the current context.
+        clinitCallers.compute(
+            clazz,
+            (key, value) -> {
+              if (value == null) {
+                // This <clinit> was not triggered before.
+                return Optional.of(getContext());
+              }
+              // This <clinit> was triggered from another context than the current.
+              assert value.orElse(null) != getContext();
+              return Optional.empty();
+            });
+
+        // Repeat for the parent classes.
+        triggerClassInitializer(clazz.getSuperType());
+      }
+
+      @Override
+      public void registerInitClass(DexType type) {
+        DexType rewrittenType = appView.graphLens().lookupType(type);
+        triggerClassInitializerIfNotAlreadyTriggeredInContext(rewrittenType);
+      }
+
+      @Override
+      public void registerInstanceFieldRead(DexField field) {
+        // Intentionally empty.
+      }
+
+      @Override
+      public void registerInstanceFieldWrite(DexField field) {
+        // Intentionally empty.
+      }
+
+      @Override
+      public void registerInvokeDirect(DexMethod method) {
+        DexMethod rewrittenMethod =
+            appView.graphLens().lookupInvokeDirect(method, getContext()).getReference();
+        DexProgramClass holder = rewrittenMethod.getHolderType().asProgramClass(appView);
+        ProgramMethod target = rewrittenMethod.lookupOnProgramClass(holder);
+        if (target != null) {
+          recordDispatchTarget(target);
+        }
+      }
+
+      @Override
+      public void registerInvokeInterface(DexMethod method) {
+        // Intentionally empty, as we don't aim to collect single caller information for virtual
+        // methods.
+      }
+
+      @Override
+      public void registerInvokeStatic(DexMethod method) {
+        DexMethod rewrittenMethod =
+            appView.graphLens().lookupInvokeDirect(method, getContext()).getReference();
+        ProgramMethod target =
+            appView
+                .appInfo()
+                .unsafeResolveMethodDueToDexFormat(rewrittenMethod)
+                .getResolvedProgramMethod();
+        if (target != null) {
+          recordDispatchTarget(target);
+          triggerClassInitializerIfNotAlreadyTriggeredInContext(target.getHolder());
+        }
+      }
+
+      @Override
+      public void registerInvokeSuper(DexMethod method) {
+        // Intentionally empty, as we don't aim to collect single caller information for virtual
+        // methods.
+      }
+
+      @Override
+      public void registerInvokeVirtual(DexMethod method) {
+        // Intentionally empty, as we don't aim to collect single caller information for virtual
+        // methods.
+      }
+
+      @Override
+      public void registerNewInstance(DexType type) {
+        DexType rewrittenType = appView.graphLens().lookupType(type);
+        triggerClassInitializerIfNotAlreadyTriggeredInContext(rewrittenType);
+      }
+
+      @Override
+      public void registerStaticFieldRead(DexField field) {
+        DexField rewrittenField = appView.graphLens().lookupField(field);
+        triggerClassInitializerIfNotAlreadyTriggeredInContext(rewrittenField.getHolderType());
+      }
+
+      @Override
+      public void registerStaticFieldWrite(DexField field) {
+        DexField rewrittenField = appView.graphLens().lookupField(field);
+        triggerClassInitializerIfNotAlreadyTriggeredInContext(rewrittenField.getHolderType());
+      }
+
+      @Override
+      public void registerTypeReference(DexType type) {
+        // Intentionally empty.
+      }
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
index 40c2ce3..674493f 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
@@ -59,7 +59,6 @@
 import com.android.tools.r8.ir.optimize.inliner.InliningReasonStrategy;
 import com.android.tools.r8.ir.optimize.inliner.NopWhyAreYouNotInliningReporter;
 import com.android.tools.r8.ir.optimize.inliner.WhyAreYouNotInliningReporter;
-import com.android.tools.r8.kotlin.Kotlin;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.MainDexInfo;
 import com.android.tools.r8.utils.InternalOptions;
@@ -71,7 +70,6 @@
 import com.android.tools.r8.utils.collections.LongLivedProgramMethodSetBuilder;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
@@ -86,7 +84,6 @@
 
   protected final AppView<AppInfoWithLiveness> appView;
   private final IRConverter converter;
-  private final Set<DexMethod> extraNeverInlineMethods;
   private final LensCodeRewriter lensCodeRewriter;
   final MainDexInfo mainDexInfo;
 
@@ -107,17 +104,8 @@
       AppView<AppInfoWithLiveness> appView,
       IRConverter converter,
       LensCodeRewriter lensCodeRewriter) {
-    Kotlin.Intrinsics intrinsics = appView.dexItemFactory().kotlin.intrinsics;
     this.appView = appView;
     this.converter = converter;
-    this.extraNeverInlineMethods =
-        appView.options().kotlinOptimizationOptions().disableKotlinSpecificOptimizations
-            ? ImmutableSet.of()
-            : ImmutableSet.of(
-                intrinsics.throwNpe,
-                intrinsics.throwParameterIsNullException,
-                intrinsics.throwParameterIsNullNPE,
-                intrinsics.throwParameterIsNullIAE);
     this.lensCodeRewriter = lensCodeRewriter;
     this.mainDexInfo = appView.appInfo().getMainDexInfo();
     this.singleInlineCallers =
@@ -140,12 +128,6 @@
       return true;
     }
 
-    if (extraNeverInlineMethods.contains(
-        appView.graphLens().getOriginalMethodSignature(singleTargetReference))) {
-      whyAreYouNotInliningReporter.reportExtraNeverInline();
-      return true;
-    }
-
     if (appInfo.isNeverInlineMethod(singleTargetReference)) {
       whyAreYouNotInliningReporter.reportMarkedAsNeverInline();
       return true;
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/inliner/NopWhyAreYouNotInliningReporter.java b/src/main/java/com/android/tools/r8/ir/optimize/inliner/NopWhyAreYouNotInliningReporter.java
index 218a8fc..cc7d4ec 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/inliner/NopWhyAreYouNotInliningReporter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/inliner/NopWhyAreYouNotInliningReporter.java
@@ -22,9 +22,6 @@
   }
 
   @Override
-  public void reportExtraNeverInline() {}
-
-  @Override
   public void reportCallerNotSameClass() {}
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/inliner/WhyAreYouNotInliningReporter.java b/src/main/java/com/android/tools/r8/ir/optimize/inliner/WhyAreYouNotInliningReporter.java
index 8063674..66d6108 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/inliner/WhyAreYouNotInliningReporter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/inliner/WhyAreYouNotInliningReporter.java
@@ -45,8 +45,6 @@
     }
   }
 
-  public abstract void reportExtraNeverInline();
-
   public abstract void reportCallerNotSameClass();
 
   public abstract void reportCallerNotSameNest();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/inliner/WhyAreYouNotInliningReporterImpl.java b/src/main/java/com/android/tools/r8/ir/optimize/inliner/WhyAreYouNotInliningReporterImpl.java
index f9418b4..94632b6 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/inliner/WhyAreYouNotInliningReporterImpl.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/inliner/WhyAreYouNotInliningReporterImpl.java
@@ -48,11 +48,6 @@
   }
 
   @Override
-  public void reportExtraNeverInline() {
-    print("method is marked as an additional never inline method.");
-  }
-
-  @Override
   public void reportCallerNotSameClass() {
     print("inlinee can only be inlined into methods in the same class.");
   }
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 c012686..fca35a8 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -46,6 +46,7 @@
 import com.android.tools.r8.graph.classmerging.VerticallyMergedClasses;
 import com.android.tools.r8.horizontalclassmerging.HorizontalClassMerger;
 import com.android.tools.r8.horizontalclassmerging.HorizontallyMergedClasses;
+import com.android.tools.r8.horizontalclassmerging.Policy;
 import com.android.tools.r8.inspector.internal.InspectorImpl;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.desugar.desugaredlibrary.DesugaredLibraryConfiguration;
@@ -1372,7 +1373,7 @@
         !Version.isDevelopmentVersion()
             || System.getProperty("com.android.tools.r8.disableHorizontalClassMerging") == null;
     // TODO(b/205611444): Enable by default.
-    private boolean enableClassInitializerDeadlockDetection = false;
+    private boolean enableClassInitializerDeadlockDetection = true;
     private boolean enableInterfaceMerging =
         System.getProperty("com.android.tools.r8.disableHorizontalInterfaceMerging") == null;
     private boolean enableInterfaceMergingInInitial = false;
@@ -1592,6 +1593,8 @@
 
     public BiConsumer<DexItemFactory, HorizontallyMergedClasses> horizontallyMergedClassesConsumer =
         ConsumerUtils.emptyBiConsumer();
+    public Function<List<Policy>, List<Policy>> horizontalClassMergingPolicyRewriter =
+        Function.identity();
     public TriFunction<AppView<?>, Iterable<DexProgramClass>, DexProgramClass, DexProgramClass>
         horizontalClassMergingTarget = (appView, candidates, target) -> target;
 
diff --git a/src/main/java/com/android/tools/r8/utils/collections/ProgramMemberMap.java b/src/main/java/com/android/tools/r8/utils/collections/ProgramMemberMap.java
index 3a648fe..9c1c5af 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/ProgramMemberMap.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/ProgramMemberMap.java
@@ -8,6 +8,7 @@
 import com.google.common.base.Equivalence.Wrapper;
 import java.util.Map;
 import java.util.function.BiConsumer;
+import java.util.function.BiFunction;
 import java.util.function.BiPredicate;
 import java.util.function.Function;
 import java.util.function.Supplier;
@@ -28,6 +29,10 @@
     backing.clear();
   }
 
+  public V compute(K member, BiFunction<K, V, V> fn) {
+    return backing.compute(wrap(member), (key, value) -> fn.apply(member, value));
+  }
+
   public V computeIfAbsent(K member, Function<K, V> fn) {
     return backing.computeIfAbsent(wrap(member), key -> fn.apply(key.get()));
   }
@@ -44,6 +49,10 @@
     return backing.get(wrap(member));
   }
 
+  public V getOrDefault(K member, V defaultValue) {
+    return backing.getOrDefault(wrap(member), defaultValue);
+  }
+
   public boolean isEmpty() {
     return backing.isEmpty();
   }
diff --git a/src/test/java/com/android/tools/r8/Dex2OatTestRunResult.java b/src/test/java/com/android/tools/r8/Dex2OatTestRunResult.java
index cb33702..145a48c 100644
--- a/src/test/java/com/android/tools/r8/Dex2OatTestRunResult.java
+++ b/src/test/java/com/android/tools/r8/Dex2OatTestRunResult.java
@@ -32,4 +32,14 @@
         matcher);
     return self();
   }
+
+  public Dex2OatTestRunResult assertSoftVerificationErrors() {
+    assertSuccess();
+    Matcher<? super String> matcher = CoreMatchers.containsString("Soft verification failures");
+    assertThat(
+        errorMessage("Run dex2oat did not produce soft verification errors.", matcher.toString()),
+        getStdErr(),
+        matcher);
+    return self();
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/ToolHelper.java b/src/test/java/com/android/tools/r8/ToolHelper.java
index 033e512..52b4ac9 100644
--- a/src/test/java/com/android/tools/r8/ToolHelper.java
+++ b/src/test/java/com/android/tools/r8/ToolHelper.java
@@ -1924,6 +1924,8 @@
     command.add(getDex2OatPath(vm).toString());
     command.add("--android-root=" + getProductPath(vm) + "/system");
     command.add("--runtime-arg");
+    command.add("-verbose:verifier");
+    command.add("--runtime-arg");
     command.add("-Xnorelocate");
     command.add("--dex-file=" + file.toAbsolutePath());
     command.add("--oat-file=" + outFile.toAbsolutePath());
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/ClinitDeadlockAfterMergingMultipleGroupsTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/ClinitDeadlockAfterMergingMultipleGroupsTest.java
new file mode 100644
index 0000000..3d07644
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/ClinitDeadlockAfterMergingMultipleGroupsTest.java
@@ -0,0 +1,143 @@
+// 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.classmerging.horizontal;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.horizontalclassmerging.MultiClassSameReferencePolicy;
+import com.android.tools.r8.horizontalclassmerging.Policy;
+import com.google.common.collect.ImmutableList;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ClinitDeadlockAfterMergingMultipleGroupsTest extends TestBase {
+
+  @Parameter(0)
+  public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection parameters() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepClassAndMembersRules(Main.class)
+        .addHorizontallyMergedClassesInspector(
+            inspector ->
+                inspector
+                    .assertClassesNotMerged(A1.class, A2.class)
+                    .assertIsCompleteMergeGroup(B1.class, B2.class)
+                    .assertIsCompleteMergeGroup(C1.class, C2.class)
+                    .assertIsCompleteMergeGroup(D1.class, D2.class)
+                    .assertNoOtherClassesMerged())
+        .addOptionsModification(
+            options -> {
+              options.horizontalClassMergerOptions().setEnableClassInitializerDeadlockDetection();
+              options.testing.horizontalClassMergingPolicyRewriter =
+                  policies ->
+                      ImmutableList.<Policy>builder()
+                          .add(getPolicyForTesting())
+                          .addAll(policies)
+                          .build();
+            })
+        .setMinApi(parameters.getApiLevel())
+        .compile();
+  }
+
+  // A custom policy for splitting the merge group {A1, A2, B1, B2, C1, C2, D1, D2} into {A1, A2},
+  // {B1, B2}, {C1, C2}, {D1, D2}.
+  private Policy getPolicyForTesting() {
+    return new MultiClassSameReferencePolicy<String>() {
+
+      @Override
+      public String getMergeKey(DexProgramClass clazz) {
+        String simpleName = clazz.getSimpleName();
+        String simpleNameExcludingIndex = simpleName.substring(0, simpleName.length() - 1);
+        return simpleNameExcludingIndex;
+      }
+
+      @Override
+      public String getName() {
+        return ClinitDeadlockAfterMergingMultipleGroupsTest.class.getTypeName();
+      }
+    };
+  }
+
+  static class Main {
+
+    // @Keep
+    public static void thread0() {
+      // Will take the followings locks in the specified order: A1, B1.
+      System.out.println(A1.b1);
+    }
+
+    // @Keep
+    public static void thread1() {
+      // Will take the following locks in the specified order: B2, C2.
+      System.out.println(B2.c2);
+    }
+
+    // @Keep
+    public static void thread2() {
+      // Will take the following locks in the specified order: C1, D1.
+      System.out.println(C1.d1);
+    }
+
+    // @Keep
+    public static void thread3() {
+      // Will take the following locks in the specified order: D2, A2.
+      System.out.println(D2.a2);
+    }
+
+    // @Keep
+    public static void thread4() {
+      System.out.println(new A1());
+      System.out.println(new A2());
+      System.out.println(new B1());
+      System.out.println(new B2());
+      System.out.println(new C1());
+      System.out.println(new C2());
+      System.out.println(new D1());
+      System.out.println(new D2());
+    }
+  }
+
+  static class A1 {
+
+    static B1 b1 = new B1();
+  }
+
+  static class A2 {}
+
+  static class B1 {}
+
+  static class B2 {
+
+    static C2 c2 = new C2();
+  }
+
+  static class C1 {
+
+    static D1 d1 = new D1();
+  }
+
+  static class C2 {}
+
+  static class D1 {}
+
+  static class D2 {
+
+    static A2 a2 = new A2();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/ClinitDeadlockAfterMergingSingletonClassesInstantiatedByCompanionTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/ClinitDeadlockAfterMergingSingletonClassesInstantiatedByCompanionTest.java
index 2ea472e..f7ca4c1 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/ClinitDeadlockAfterMergingSingletonClassesInstantiatedByCompanionTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/ClinitDeadlockAfterMergingSingletonClassesInstantiatedByCompanionTest.java
@@ -9,7 +9,6 @@
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.classmerging.horizontal.ClinitDeadlockAfterMergingSingletonClassesInstantiatedByCompanionTest.Host.Companion.HostA;
 import com.android.tools.r8.classmerging.horizontal.ClinitDeadlockAfterMergingSingletonClassesInstantiatedByCompanionTest.Host.Companion.HostB;
-import com.android.tools.r8.utils.codeinspector.HorizontallyMergedClassesInspector;
 import com.google.common.collect.ImmutableList;
 import java.util.List;
 import org.junit.Test;
@@ -43,9 +42,12 @@
             "  public static void thread0();",
             "  public static void thread" + thread + "();",
             "}")
-        // TODO(b/205611444): HostA and HostB should be merged when thread is 1.
         .addHorizontallyMergedClassesInspector(
-            HorizontallyMergedClassesInspector::assertNoClassesMerged)
+            inspector ->
+                inspector
+                    .applyIf(
+                        thread == 1, i -> i.assertIsCompleteMergeGroup(HostA.class, HostB.class))
+                    .assertNoOtherClassesMerged())
         .addOptionsModification(
             options ->
                 options.horizontalClassMergerOptions().setEnableClassInitializerDeadlockDetection())
diff --git a/src/test/java/com/android/tools/r8/kotlin/KotlinClassInlinerTest.java b/src/test/java/com/android/tools/r8/kotlin/KotlinClassInlinerTest.java
index 4aaea25..2d2611f 100644
--- a/src/test/java/com/android/tools/r8/kotlin/KotlinClassInlinerTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/KotlinClassInlinerTest.java
@@ -259,9 +259,11 @@
               String kotlinIntrinsics = "void kotlin.jvm.internal.Intrinsics";
               assertEquals(
                   Lists.newArrayList(
-                      kotlinc.is(KOTLINC_1_3_72)
-                          ? kotlinIntrinsics + ".throwParameterIsNullException(java.lang.String)"
-                          : kotlinIntrinsics + ".throwParameterIsNullNPE(java.lang.String)"),
+                      kotlinIntrinsics
+                          + (kotlinc.is(KOTLINC_1_3_72)
+                              ? ".checkParameterIsNotNull"
+                              : ".checkNotNullParameter")
+                          + "(java.lang.Object, java.lang.String)"),
                   collectStaticCalls(clazz, "main", String[].class.getCanonicalName()));
             });
   }
diff --git a/src/test/java/com/android/tools/r8/kotlin/KotlinIntrinsicsInlineChainTest.java b/src/test/java/com/android/tools/r8/kotlin/KotlinIntrinsicsInlineChainTest.java
index 802be75..da2f568 100644
--- a/src/test/java/com/android/tools/r8/kotlin/KotlinIntrinsicsInlineChainTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/KotlinIntrinsicsInlineChainTest.java
@@ -78,10 +78,10 @@
               long checkParameterIsNotNull = countCall(main, "checkParameterIsNotNull");
               long checkNotNullParameter = countCall(main, "checkNotNullParameter");
               if (kotlinParameters.is(KotlinCompilerVersion.KOTLINC_1_3_72)) {
-                assertEquals(allowAccessModification ? 0 : 1, checkParameterIsNotNull);
+                assertEquals(1, checkParameterIsNotNull);
                 assertEquals(0, checkNotNullParameter);
               } else {
-                assertEquals(allowAccessModification ? 0 : 1, checkNotNullParameter);
+                assertEquals(1, checkNotNullParameter);
                 assertEquals(0, checkParameterIsNotNull);
               }
             });
diff --git a/src/test/java/com/android/tools/r8/kotlin/KotlinIntrinsicsInlineTest.java b/src/test/java/com/android/tools/r8/kotlin/KotlinIntrinsicsInlineTest.java
index c407a5b..a03ebb2 100644
--- a/src/test/java/com/android/tools/r8/kotlin/KotlinIntrinsicsInlineTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/KotlinIntrinsicsInlineTest.java
@@ -76,9 +76,7 @@
               MethodSubject isSupported = main.uniqueMethodWithName("isSupported");
               assertThat(isSupported, isPresent());
               assertEquals(
-                  !kotlinc.is(KotlinCompilerVersion.KOTLINC_1_3_72) || allowAccessModification
-                      ? 0
-                      : 1,
+                  kotlinc.is(KotlinCompilerVersion.KOTLINC_1_3_72) ? 1 : 0,
                   countCall(isSupported, "checkParameterIsNotNull"));
 
               // In general cases, null check won't be invoked only once or twice, hence no subtle
@@ -92,9 +90,7 @@
   @Test
   public void b139432507_isSupported() throws Exception {
     assumeTrue("Different inlining behavior on CF backend", parameters.isDexRuntime());
-    testSingle(
-        "isSupported",
-        kotlinc.is(KotlinCompilerVersion.KOTLINC_1_3_72) && !allowAccessModification);
+    testSingle("isSupported", kotlinc.is(KotlinCompilerVersion.KOTLINC_1_3_72));
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/kotlin/R8KotlinIntrinsicsTest.java b/src/test/java/com/android/tools/r8/kotlin/R8KotlinIntrinsicsTest.java
index 142e48d..d8a7e1c 100644
--- a/src/test/java/com/android/tools/r8/kotlin/R8KotlinIntrinsicsTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/R8KotlinIntrinsicsTest.java
@@ -62,15 +62,25 @@
                               "throwParameterIsNullException",
                               "void",
                               Collections.singletonList("java.lang.String")),
-                          // throwParameterIsNullException is not added for test starting from 1.4
-                          kotlinc.is(KotlinCompilerVersion.KOTLINC_1_3_72))
+                          false)
+                      .put(
+                          new MethodSignature(
+                              "throwParameterIsNullNPE",
+                              "void",
+                              Collections.singletonList("java.lang.String")),
+                          false)
                       .put(
                           new MethodSignature(
                               "checkParameterIsNotNull",
                               "void",
                               Lists.newArrayList("java.lang.Object", "java.lang.String")),
-                          kotlinc.is(KotlinCompilerVersion.KOTLINC_1_3_72)
-                              && !allowAccessModification)
+                          kotlinc.is(KotlinCompilerVersion.KOTLINC_1_3_72))
+                      .put(
+                          new MethodSignature(
+                              "checkNotNullParameter",
+                              "void",
+                              Lists.newArrayList("java.lang.Object", "java.lang.String")),
+                          !kotlinc.is(KotlinCompilerVersion.KOTLINC_1_3_72))
                       .build());
             });
   }
diff --git a/src/test/java/com/android/tools/r8/naming/KotlinIntrinsicsIdentifierTest.java b/src/test/java/com/android/tools/r8/naming/KotlinIntrinsicsIdentifierTest.java
index e6f1c6d..63cacfc 100644
--- a/src/test/java/com/android/tools/r8/naming/KotlinIntrinsicsIdentifierTest.java
+++ b/src/test/java/com/android/tools/r8/naming/KotlinIntrinsicsIdentifierTest.java
@@ -118,7 +118,7 @@
     boolean metKotlinIntrinsicsNullChecks = false;
     while (it.hasNext()) {
       DexMethod invokedMethod = it.next().getMethod();
-      if (invokedMethod.holder.toSourceString().contains("java.net")) {
+      if (invokedMethod.holder.getTypeName().contains("java.net")) {
         continue;
       }
       ClassSubject invokedMethodHolderSubject =
@@ -165,7 +165,11 @@
                     "-neverinline class **." + targetClassName + " { <methods>; }",
                     "-keepconstantarguments class kotlin.jvm.internal.Intrinsics {",
                     "  *** checkParameterIsNotNull(...);",
+                    "}",
+                    "-neversinglecallerinline class kotlin.jvm.internal.Intrinsics {",
+                    "  *** checkParameterIsNotNull(...);",
                     "}"))
+            .addNeverSingleCallerInlineAnnotations()
             .allowDiagnosticWarningMessages()
             .minification(minification)
             .compile()
diff --git a/src/test/java/com/android/tools/r8/softverification/FoundClass.java b/src/test/java/com/android/tools/r8/softverification/FoundClass.java
new file mode 100644
index 0000000..cc25389
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/FoundClass.java
@@ -0,0 +1,20 @@
+// 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.softverification;
+
+public class FoundClass {
+
+  public static int staticField = 42;
+
+  public int instanceField = 42;
+
+  public static void staticMethod() {
+    System.out.println("FoundClass::staticMethod");
+  }
+
+  public void instanceMethod() {
+    System.out.println("FoundClass::instanceMethod");
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/softverification/MissingClass.java b/src/test/java/com/android/tools/r8/softverification/MissingClass.java
new file mode 100644
index 0000000..d653af7
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/MissingClass.java
@@ -0,0 +1,20 @@
+// 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.softverification;
+
+public class MissingClass {
+
+  public static int staticField = 42;
+
+  public int instanceField = 42;
+
+  public static void staticMethod() {
+    System.out.println("MissingClass::staticMethod");
+  }
+
+  public void instanceMethod() {
+    System.out.println("MissingClass::instanceMethod");
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/softverification/MissingMember.java b/src/test/java/com/android/tools/r8/softverification/MissingMember.java
new file mode 100644
index 0000000..9fee087
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/MissingMember.java
@@ -0,0 +1,20 @@
+// 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.softverification;
+
+public class MissingMember {
+
+  public static int staticField = 42;
+
+  public int instanceField = 42;
+
+  public static void staticMethod() {
+    System.out.println("MissingMember::staticMethod");
+  }
+
+  public void instanceMethod() {
+    System.out.println("MissingMember::instanceMethod");
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/softverification/TestCheckCast.java b/src/test/java/com/android/tools/r8/softverification/TestCheckCast.java
new file mode 100644
index 0000000..bee31ea
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/TestCheckCast.java
@@ -0,0 +1,26 @@
+// 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.softverification;
+
+public class TestCheckCast {
+
+  public static Object getObject() {
+    return new Object();
+  }
+
+  public static String run() {
+    if (System.currentTimeMillis() == 0) {
+      MissingClass foo = (MissingClass) getObject();
+    }
+    if (System.currentTimeMillis() == 0) {
+      MissingClass foo = (MissingClass) getObject();
+    }
+    String currentString = "foobar";
+    for (int i = 0; i < 10; i++) {
+      currentString = "foobar" + (i + currentString.length());
+    }
+    return currentString;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/softverification/TestInstanceField.java b/src/test/java/com/android/tools/r8/softverification/TestInstanceField.java
new file mode 100644
index 0000000..e5cf5f7
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/TestInstanceField.java
@@ -0,0 +1,26 @@
+// 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.softverification;
+
+public class TestInstanceField {
+
+  public static String run() {
+    return run(null);
+  }
+
+  public static String run(MissingClass missingClass) {
+    if (System.currentTimeMillis() == 0) {
+      System.out.println(missingClass.instanceField);
+    }
+    if (System.currentTimeMillis() == 0) {
+      System.out.println(missingClass.instanceField);
+    }
+    String currentString = "foobar";
+    for (int i = 0; i < 10; i++) {
+      currentString = "foobar" + (i + currentString.length());
+    }
+    return currentString;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/softverification/TestInstanceMethod.java b/src/test/java/com/android/tools/r8/softverification/TestInstanceMethod.java
new file mode 100644
index 0000000..2a8ee20
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/TestInstanceMethod.java
@@ -0,0 +1,26 @@
+// 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.softverification;
+
+public class TestInstanceMethod {
+
+  public static String run() {
+    return run(null);
+  }
+
+  public static String run(MissingClass missingClass) {
+    if (System.currentTimeMillis() == 0) {
+      missingClass.instanceMethod();
+    }
+    if (System.currentTimeMillis() == 0) {
+      missingClass.instanceMethod();
+    }
+    String currentString = "foobar";
+    for (int i = 0; i < 10; i++) {
+      currentString = "foobar" + (i + currentString.length());
+    }
+    return currentString;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/softverification/TestInstanceOf.java b/src/test/java/com/android/tools/r8/softverification/TestInstanceOf.java
new file mode 100644
index 0000000..ee0c2db
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/TestInstanceOf.java
@@ -0,0 +1,30 @@
+// 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.softverification;
+
+public class TestInstanceOf {
+
+  public static Object getObject() {
+    return new Object();
+  }
+
+  public static String run() {
+    if (System.currentTimeMillis() == 0) {
+      if (getObject() instanceof MissingClass) {
+        throw new RuntimeException("Foo");
+      }
+    }
+    if (System.currentTimeMillis() == 0) {
+      if (getObject() instanceof MissingClass) {
+        throw new RuntimeException("Foo");
+      }
+    }
+    String currentString = "foobar";
+    for (int i = 0; i < 10; i++) {
+      currentString = "foobar" + (i + currentString.length());
+    }
+    return currentString;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/softverification/TestNewInstance.java b/src/test/java/com/android/tools/r8/softverification/TestNewInstance.java
new file mode 100644
index 0000000..7b67609
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/TestNewInstance.java
@@ -0,0 +1,22 @@
+// 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.softverification;
+
+public class TestNewInstance {
+
+  public static String run() {
+    if (System.currentTimeMillis() == 0) {
+      new MissingClass();
+    }
+    if (System.currentTimeMillis() == 0) {
+      new MissingClass();
+    }
+    String currentString = "foobar";
+    for (int i = 0; i < 10; i++) {
+      currentString = "foobar" + (i + currentString.length());
+    }
+    return currentString;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/softverification/TestRunner.java b/src/test/java/com/android/tools/r8/softverification/TestRunner.java
new file mode 100644
index 0000000..6baef2a
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/TestRunner.java
@@ -0,0 +1,59 @@
+// 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.softverification;
+
+public class TestRunner {
+
+  public static class Measure {
+    private long start;
+    private String description;
+
+    public Measure() {}
+
+    public void start(String description) {
+      start = System.currentTimeMillis();
+      this.description = description;
+    }
+
+    public String stop() {
+      long end = System.currentTimeMillis();
+      return "Time for " + description + " took: " + (end - start) + "\n";
+    }
+  }
+
+  public static String run() {
+    StringBuilder sb = new StringBuilder();
+    Measure measure = new Measure();
+    measure.start("InstanceSourceObject");
+    TestInstanceOf.run();
+    sb.append(measure.stop());
+    measure.start("CheckCastSourceObject");
+    TestCheckCast.run();
+    sb.append(measure.stop());
+    measure.start("TypeReference");
+    TestTypeReference.run();
+    sb.append(measure.stop());
+    measure.start("NewInstance");
+    TestNewInstance.run();
+    sb.append(measure.stop());
+    measure.start("StaticField");
+    TestStaticField.run();
+    sb.append(measure.stop());
+    measure.start("StaticMethod");
+    TestStaticMethod.run();
+    sb.append(measure.stop());
+    measure.start("InstanceField");
+    TestInstanceField.run();
+    sb.append(measure.stop());
+    measure.start("InstanceMethod");
+    TestInstanceMethod.run();
+    sb.append(measure.stop());
+    return sb.toString();
+  }
+
+  public static void main(String[] args) {
+    System.out.println(run());
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/softverification/TestRunnerBuilder.java b/src/test/java/com/android/tools/r8/softverification/TestRunnerBuilder.java
new file mode 100644
index 0000000..7a19f09
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/TestRunnerBuilder.java
@@ -0,0 +1,192 @@
+// 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.softverification;
+
+import static com.android.tools.r8.utils.DescriptorUtils.getDescriptorFromClassBinaryName;
+
+import com.android.tools.r8.D8TestCompileResult;
+import com.android.tools.r8.Dex2OatTestRunResult;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.DexVm.Version;
+import com.android.tools.r8.softverification.TestRunner.Measure;
+import com.android.tools.r8.transformers.ClassFileTransformer;
+import com.android.tools.r8.transformers.ClassFileTransformer.FieldPredicate;
+import com.android.tools.r8.transformers.ClassFileTransformer.MethodPredicate;
+import com.android.tools.r8.transformers.MethodTransformer;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.ZipUtils.ZipBuilder;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import java.io.IOException;
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import java.util.Set;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+/**
+ * This runner produces a benchmark jar that can be used to investigate the time penalty that soft-
+ * verification errors have on the runtime of an app. It will build a set of different tests:
+ *
+ * <pre>
+ * - CheckCast
+ * - InstanceOf
+ * - TypeReference
+ * - NewInstance
+ * - StaticField
+ * - StaticMethod
+ * - InstanceField
+ * - InstanceMethod
+ * </pre>
+ *
+ * where for each test, there is a reference to either a missing class, existing class with missing
+ * members or a full class with all definitions. Each test column can be run by invoking the
+ * corresponding test runner:
+ *
+ * <p>TestRunner_MissingClass, TestRunner_MissingMember, TestRunner_FoundClass
+ *
+ * <p>To test in a setting with a studio project, modify ANDROID_STUDIO_LIB_PATH to point to an
+ * android project. A reference android project can be found at:
+ * /google/data/ro/teams/r8/deps/DexVerificationSample.tar.gz
+ */
+@RunWith(Parameterized.class)
+public class TestRunnerBuilder extends TestBase {
+
+  @Parameter() public TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters()
+        .withDexRuntime(Version.V9_0_0)
+        .withApiLevel(AndroidApiLevel.M)
+        .build();
+  }
+
+  private static final Path ANDROID_STUDIO_LIB_PATH = Paths.get("PATH_TO_PROJECT/libs/library.jar");
+
+  private static final int COUNT = 1100;
+
+  private static final Set<String> testClasses =
+      ImmutableSet.of(
+          binaryName(TestCheckCast.class),
+          binaryName(TestInstanceOf.class),
+          binaryName(TestTypeReference.class),
+          binaryName(TestNewInstance.class),
+          binaryName(TestStaticField.class),
+          binaryName(TestStaticMethod.class),
+          binaryName(TestInstanceField.class),
+          binaryName(TestInstanceMethod.class));
+
+  private static void buildJar(Path path) throws Exception {
+    ZipBuilder builder = ZipBuilder.builder(path);
+    builder.addFilesRelative(
+        ToolHelper.getClassPathForTests(), ToolHelper.getClassFileForTestClass(Measure.class));
+    for (Class<?> clazz :
+        ImmutableList.of(MissingClass.class, MissingMember.class, FoundClass.class)) {
+      String postFix = clazz.getSimpleName();
+      int classCounter = 0;
+      for (int i = 0; i < COUNT; i++) {
+        addClass(builder, TestCheckCast.class, clazz, postFix, i, classCounter++);
+        addClass(builder, TestInstanceOf.class, clazz, postFix, i, classCounter++);
+        addClass(builder, TestTypeReference.class, clazz, postFix, i, classCounter++);
+        addClass(builder, TestNewInstance.class, clazz, postFix, i, classCounter++);
+        addClass(builder, TestStaticField.class, clazz, postFix, i, classCounter++);
+        addClass(builder, TestStaticMethod.class, clazz, postFix, i, classCounter++);
+        addClass(builder, TestInstanceField.class, clazz, postFix, i, classCounter++);
+        addClass(builder, TestInstanceMethod.class, clazz, postFix, i, classCounter++);
+      }
+      if (clazz != MissingClass.class) {
+        for (int i = 0; i < classCounter; i++) {
+          String binaryName = binaryName(clazz) + "_" + i;
+          ClassFileTransformer transformer =
+              transformer(clazz).setClassDescriptor(getDescriptorFromClassBinaryName(binaryName));
+          if (clazz == MissingMember.class) {
+            transformer.removeMethods(MethodPredicate.all()).removeFields(FieldPredicate.all());
+          }
+          builder.addBytes(binaryName + ".class", transformer.transform());
+        }
+      }
+      String runnerClass = binaryName(TestRunner.class) + "_" + postFix;
+      builder.addBytes(
+          runnerClass + ".class",
+          transformer(TestRunner.class)
+              .setClassDescriptor(getDescriptorFromClassBinaryName(runnerClass))
+              .addMethodTransformer(
+                  new MethodTransformer() {
+
+                    @Override
+                    public void visitMaxs(int maxStack, int maxLocals) {
+                      super.visitMaxs(-1, maxLocals);
+                    }
+
+                    @Override
+                    public void visitMethodInsn(
+                        int opcode,
+                        String owner,
+                        String name,
+                        String descriptor,
+                        boolean isInterface) {
+                      if (!testClasses.contains(owner)) {
+                        super.visitMethodInsn(opcode, owner, name, descriptor, isInterface);
+                        return;
+                      }
+                      for (int i = 0; i < COUNT; i++) {
+                        super.visitMethodInsn(
+                            opcode, owner + "_" + postFix + "_" + i, name, descriptor, isInterface);
+                      }
+                    }
+                  })
+              .transform());
+    }
+    builder.build();
+  }
+
+  private static void addClass(
+      ZipBuilder builder,
+      Class<?> clazz,
+      Class<?> classReference,
+      String postFix,
+      int index,
+      int referenceIndex)
+      throws IOException {
+    String binaryName = binaryName(clazz) + "_" + postFix + "_" + index;
+    String referenceBinaryName = binaryName(classReference) + "_" + referenceIndex;
+    builder.addBytes(
+        binaryName + ".class",
+        transformer(clazz)
+            .setClassDescriptor(getDescriptorFromClassBinaryName(binaryName))
+            .replaceClassDescriptorInMembers(
+                descriptor(MissingClass.class),
+                getDescriptorFromClassBinaryName(referenceBinaryName))
+            .replaceClassDescriptorInMethodInstructions(
+                descriptor(MissingClass.class),
+                getDescriptorFromClassBinaryName(referenceBinaryName))
+            .transform());
+  }
+
+  @Test
+  public void buildTest() throws Exception {
+    Path benchmarkJar = temp.newFile("library.jar").toPath();
+    buildJar(benchmarkJar);
+    D8TestCompileResult compileResult =
+        testForD8(parameters.getBackend())
+            .setMinApi(parameters.getApiLevel())
+            .addProgramFiles(benchmarkJar)
+            .compile();
+    Dex2OatTestRunResult dex2OatTestRunResult = compileResult.runDex2Oat(parameters.getRuntime());
+    dex2OatTestRunResult.assertSoftVerificationErrors();
+  }
+
+  public static void main(String[] args) throws Exception {
+    System.out.println("Building jar and placing in " + ANDROID_STUDIO_LIB_PATH);
+    buildJar(ANDROID_STUDIO_LIB_PATH);
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/softverification/TestStaticField.java b/src/test/java/com/android/tools/r8/softverification/TestStaticField.java
new file mode 100644
index 0000000..3d0b711
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/TestStaticField.java
@@ -0,0 +1,22 @@
+// 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.softverification;
+
+public class TestStaticField {
+
+  public static String run() {
+    if (System.currentTimeMillis() == 0) {
+      System.out.println(MissingClass.staticField);
+    }
+    if (System.currentTimeMillis() == 0) {
+      System.out.println(MissingClass.staticField);
+    }
+    String currentString = "foobar";
+    for (int i = 0; i < 10; i++) {
+      currentString = "foobar" + (i + currentString.length());
+    }
+    return currentString;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/softverification/TestStaticMethod.java b/src/test/java/com/android/tools/r8/softverification/TestStaticMethod.java
new file mode 100644
index 0000000..8e6fe5d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/TestStaticMethod.java
@@ -0,0 +1,22 @@
+// 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.softverification;
+
+public class TestStaticMethod {
+
+  public static String run() {
+    if (System.currentTimeMillis() == 0) {
+      MissingClass.staticMethod();
+    }
+    if (System.currentTimeMillis() == 0) {
+      MissingClass.staticMethod();
+    }
+    String currentString = "foobar";
+    for (int i = 0; i < 10; i++) {
+      currentString = "foobar" + (i + currentString.length());
+    }
+    return currentString;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/softverification/TestTypeReference.java b/src/test/java/com/android/tools/r8/softverification/TestTypeReference.java
new file mode 100644
index 0000000..0d064f0
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/softverification/TestTypeReference.java
@@ -0,0 +1,25 @@
+// 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.softverification;
+
+public class TestTypeReference {
+
+  public static String run() {
+    return run(null);
+  }
+
+  public static String test(MissingClass missingClass) {
+    return missingClass == null ? "nobar" : null;
+  }
+
+  public static String run(MissingClass missingClass) {
+    String currentString = missingClass == null ? "foobar" : test(missingClass);
+    currentString = missingClass == null ? currentString : test(missingClass);
+    for (int i = 0; i < 10; i++) {
+      currentString = "foobar" + (i + currentString.length());
+    }
+    return currentString;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/transformers/ClassFileTransformer.java b/src/test/java/com/android/tools/r8/transformers/ClassFileTransformer.java
index 5e37647..296004d 100644
--- a/src/test/java/com/android/tools/r8/transformers/ClassFileTransformer.java
+++ b/src/test/java/com/android/tools/r8/transformers/ClassFileTransformer.java
@@ -524,6 +524,10 @@
   public interface MethodPredicate {
     boolean test(int access, String name, String descriptor, String signature, String[] exceptions);
 
+    static MethodPredicate all() {
+      return (access, name, descriptor, signature, exceptions) -> true;
+    }
+
     static MethodPredicate onName(String name) {
       return (access, otherName, descriptor, signature, exceptions) -> name.equals(otherName);
     }
@@ -543,6 +547,10 @@
   public interface FieldPredicate {
     boolean test(int access, String name, String descriptor, String signature, Object value);
 
+    static FieldPredicate all() {
+      return (access, name, descriptor, signature, value) -> true;
+    }
+
     static FieldPredicate onNameAndSignature(String name, String descriptor) {
       return (access, otherName, otherDescriptor, signature, value) ->
           name.equals(otherName) && descriptor.equals(otherDescriptor);
diff --git a/tools/archive_desugar_jdk_libs.py b/tools/archive_desugar_jdk_libs.py
index 2572610..733e59b 100755
--- a/tools/archive_desugar_jdk_libs.py
+++ b/tools/archive_desugar_jdk_libs.py
@@ -20,6 +20,7 @@
 
 import archive
 import git_utils
+import jdk
 import optparse
 import os
 import re
@@ -89,6 +90,13 @@
     'https://github.com/'
         + github_account + '/' + LIBRARY_NAME, checkout_dir)
 
+def GetJavaEnv():
+  java_env = dict(os.environ, JAVA_HOME = jdk.GetJdk11Home())
+  java_env['PATH'] = java_env['PATH'] + os.pathsep + os.path.join(jdk.GetJdk11Home(), 'bin')
+  java_env['GRADLE_OPTS'] = '-Xmx1g'
+  return java_env
+
+
 def BuildDesugaredLibrary(checkout_dir, variant):
   if (variant != 'jdk8' and variant != 'jdk11'):
     raise Exception('Variant ' + variant + 'is not supported')
@@ -98,15 +106,12 @@
         bazel,
         '--bazelrc=/dev/null',
         'build',
-        'maven_release' + ('_jdk11' if variant == 'jdk11' else ''),
-         '--java_language_version=' + ('11' if variant == 'jdk11' else '8')]
-    if variant == 'jdk11':
-        cmd.append('--java_runtime_version=remotejdk_11')
+        'maven_release' + ('_jdk11' if variant == 'jdk11' else '')]
     utils.PrintCmd(cmd)
-    subprocess.check_call(cmd)
+    subprocess.check_call(cmd, env=GetJavaEnv())
     cmd = [bazel, 'shutdown']
     utils.PrintCmd(cmd)
-    subprocess.check_call(cmd)
+    subprocess.check_call(cmd, env=GetJavaEnv())
 
     # Locate the library jar and the maven zip with the jar from the
     # bazel build.
diff --git a/tools/jdk.py b/tools/jdk.py
index 7138fda..b3af7a6 100755
--- a/tools/jdk.py
+++ b/tools/jdk.py
@@ -20,6 +20,17 @@
   else:
     return os.environ['JAVA_HOME']
 
+def GetJdk11Home():
+  root = os.path.join(JDK_DIR, 'jdk-11')
+  if defines.IsLinux():
+    return os.path.join(root, 'linux')
+  elif defines.IsOsX():
+    return os.path.join(root, 'osx')
+  elif defines.IsWindows():
+    return os.path.join(root, 'windows')
+  else:
+    return os.environ['JAVA_HOME']
+
 def GetJdk8Home():
   root = os.path.join(JDK_DIR, 'jdk8')
   if defines.IsLinux():