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/policies/NoClassInitializerCycles.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoClassInitializerCycles.java
index f8faefd..a6145ec 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,12 @@
 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.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 +20,12 @@
 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.horizontalclassmerging.policies.deadlock.SingleCallerInformation;
 import com.android.tools.r8.ir.desugar.LambdaDescriptor;
 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,23 +98,38 @@
   // 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);
     }
     return removeTrivialGroups(newGroups);
   }
@@ -118,12 +138,12 @@
       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 +183,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 +253,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;
   }
 
@@ -222,34 +297,26 @@
       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) {
@@ -284,20 +351,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 +394,7 @@
         // Ensures that hasPossibleClassInitializerDeadlock() returns true for each tracing root.
         recordTracingRootsIneligibleForClassMerging();
         doBreak();
+        clearWorklist();
       }
 
       private void triggerClassInitializerIfNotAlreadyTriggeredInContext(DexType type) {
@@ -338,8 +411,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);
       }
 
@@ -400,7 +471,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 +509,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
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/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/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())