diff --git a/src/main/java/com/android/tools/r8/experimental/graphinfo/GraphEdgeInfo.java b/src/main/java/com/android/tools/r8/experimental/graphinfo/GraphEdgeInfo.java
index 14833f5..f645d0b 100644
--- a/src/main/java/com/android/tools/r8/experimental/graphinfo/GraphEdgeInfo.java
+++ b/src/main/java/com/android/tools/r8/experimental/graphinfo/GraphEdgeInfo.java
@@ -31,6 +31,8 @@
     IsLibraryMethod,
     OverridingMethod,
     MethodHandleUseFrom,
+    CompanionClass,
+    CompanionMethod,
     Unknown
   }
 
@@ -79,6 +81,10 @@
         return "defined in library method overridden by";
       case MethodHandleUseFrom:
         return "referenced by method handle";
+      case CompanionClass:
+        return "companion class for";
+      case CompanionMethod:
+        return "companion method for";
       default:
         assert false : "Unknown edge kind: " + edgeKind();
         // fall through
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 8b2e770..3a1904e 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -58,6 +58,7 @@
 import com.android.tools.r8.ir.code.InvokeMethod;
 import com.android.tools.r8.ir.code.InvokeVirtual;
 import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.desugar.InterfaceMethodRewriter;
 import com.android.tools.r8.ir.desugar.LambdaDescriptor;
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.origin.Origin;
@@ -67,6 +68,7 @@
 import com.android.tools.r8.shaking.RootSetBuilder.ConsequentRootSet;
 import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
 import com.android.tools.r8.shaking.ScopedDexMethodSet.AddMethodIfMoreVisibleResult;
+import com.android.tools.r8.utils.DequeUtils;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.SetUtils;
 import com.android.tools.r8.utils.StringDiagnostic;
@@ -322,6 +324,7 @@
 
   private final GraphReporter graphReporter;
   private final GraphConsumer keptGraphConsumer;
+  private CollectingGraphConsumer verificationGraphConsumer = null;
 
   Enqueuer(
       AppView<? extends AppInfoWithSubtyping> appView,
@@ -335,7 +338,7 @@
     this.compatibility = compatibility;
     this.forceProguardCompatibility = options.forceProguardCompatibility;
     this.graphReporter = new GraphReporter();
-    this.keptGraphConsumer = keptGraphConsumer;
+    this.keptGraphConsumer = recordKeptGraph(options, keptGraphConsumer);
     this.mode = mode;
     this.options = options;
     this.workList = EnqueuerWorklist.createWorklist(appView);
@@ -1669,8 +1672,10 @@
   private void markStaticFieldAsLive(DexEncodedField encodedField, KeepReason reason) {
     // Mark the type live here, so that the class exists at runtime.
     DexField field = encodedField.field;
-    markTypeAsLive(field.holder, reason);
-    markTypeAsLive(field.type, reason);
+    markTypeAsLive(
+        field.holder, clazz -> graphReporter.reportClassReferencedFrom(clazz, encodedField));
+    markTypeAsLive(
+        field.type, clazz -> graphReporter.reportClassReferencedFrom(clazz, encodedField));
 
     DexProgramClass clazz = getProgramClassOrNull(field.holder);
     if (clazz == null) {
@@ -1804,8 +1809,10 @@
       Log.verbose(getClass(), "Marking instance field `%s` as reachable.", field);
     }
 
-    markTypeAsLive(field.holder, reason);
-    markTypeAsLive(field.type, reason);
+    markTypeAsLive(
+        field.holder, clazz -> graphReporter.reportClassReferencedFrom(clazz, encodedField));
+    markTypeAsLive(
+        field.type, clazz -> graphReporter.reportClassReferencedFrom(clazz, encodedField));
 
     DexProgramClass clazz = getProgramClassOrNull(field.holder);
     if (clazz == null) {
@@ -1821,7 +1828,8 @@
     } else {
       if (isInstantiatedOrHasInstantiatedSubtype(clazz)) {
         // We have at least one live subtype, so mark it as live.
-        markInstanceFieldAsLive(encodedField, reason);
+        // TODO(b/120959039): Consider linking the keep reason to the actual instantiated type.
+        markInstanceFieldAsLive(encodedField, KeepReason.reachableFromLiveType(clazz.type));
       } else {
         // Add the field to the reachable set if the type later becomes instantiated.
         reachableInstanceFields
@@ -2110,9 +2118,49 @@
     trace(executorService, timing);
     options.reporter.failIfPendingErrors();
     analyses.forEach(EnqueuerAnalysis::done);
+    assert verifyKeptGraph();
     return createAppInfo(appInfo);
   }
 
+  private GraphConsumer recordKeptGraph(InternalOptions options, GraphConsumer consumer) {
+    if (options.testing.verifyKeptGraphInfo) {
+      verificationGraphConsumer = new CollectingGraphConsumer(consumer);
+      return verificationGraphConsumer;
+    }
+    return consumer;
+  }
+
+  private boolean verifyKeptGraph() {
+    assert verificationGraphConsumer != null;
+    for (DexProgramClass liveType : liveTypes.items) {
+      assert verifyRootedPath(liveType, verificationGraphConsumer);
+    }
+    return true;
+  }
+
+  private boolean verifyRootedPath(DexProgramClass liveType, CollectingGraphConsumer graph) {
+    ClassGraphNode node = getClassGraphNode(liveType.type);
+    Set<GraphNode> seen = Sets.newIdentityHashSet();
+    Deque<GraphNode> targets = DequeUtils.newArrayDeque(node);
+    while (!targets.isEmpty()) {
+      GraphNode item = targets.pop();
+      if (item instanceof KeepRuleGraphNode) {
+        KeepRuleGraphNode rule = (KeepRuleGraphNode) item;
+        if (rule.getPreconditions().isEmpty()) {
+          return true;
+        }
+      }
+      if (seen.add(item)) {
+        Map<GraphNode, Set<GraphEdgeInfo>> sources = graph.getSourcesTargeting(item);
+        assert sources != null : "No sources set for " + item;
+        assert !sources.isEmpty() : "Empty sources set for " + item;
+        targets.addAll(sources.keySet());
+      }
+    }
+    assert false : "No rooted path to " + liveType.type;
+    return true;
+  }
+
   private AppInfoWithLiveness createAppInfo(AppInfoWithSubtyping appInfo) {
     ImmutableSortedSet.Builder<DexType> builder =
         ImmutableSortedSet.orderedBy(PresortedComparable::slowCompareTo);
@@ -2367,8 +2415,11 @@
           DexEncodedMethod implementation = target.getDefaultInterfaceMethodImplementation();
           if (implementation != null) {
             DexProgramClass companion = getProgramClassOrNull(implementation.method.holder);
-            markTypeAsLive(companion, reason);
-            markVirtualMethodAsLive(companion, implementation, reason);
+            markTypeAsLive(companion, graphReporter.reportCompanionClass(holder, companion));
+            markVirtualMethodAsLive(
+                companion,
+                implementation,
+                graphReporter.reportCompanionMethod(target, implementation));
           }
         }
       }
@@ -3128,6 +3179,40 @@
       return KeepReasonWitness.INSTANCE;
     }
 
+    public KeepReasonWitness reportClassReferencedFrom(
+        DexProgramClass clazz, DexEncodedField field) {
+      if (keptGraphConsumer != null) {
+        FieldGraphNode source = getFieldGraphNode(field.field);
+        ClassGraphNode target = getClassGraphNode(clazz.type);
+        return reportEdge(source, target, EdgeKind.ReferencedFrom);
+      }
+      return KeepReasonWitness.INSTANCE;
+    }
+
+    private KeepReason reportCompanionClass(DexProgramClass iface, DexProgramClass companion) {
+      assert iface.isInterface();
+      assert InterfaceMethodRewriter.isCompanionClassType(companion.type);
+      if (keptGraphConsumer == null) {
+        return KeepReasonWitness.INSTANCE;
+      }
+      return reportEdge(
+          getClassGraphNode(iface.type),
+          getClassGraphNode(companion.type),
+          EdgeKind.CompanionClass);
+    }
+
+    private KeepReason reportCompanionMethod(
+        DexEncodedMethod definition, DexEncodedMethod implementation) {
+      assert InterfaceMethodRewriter.isCompanionClassType(implementation.method.holder);
+      if (keptGraphConsumer == null) {
+        return KeepReasonWitness.INSTANCE;
+      }
+      return reportEdge(
+          getMethodGraphNode(definition.method),
+          getMethodGraphNode(implementation.method),
+          EdgeKind.CompanionMethod);
+    }
+
     private KeepReasonWitness reportEdge(
         GraphNode source, GraphNode target, GraphEdgeInfo.EdgeKind kind) {
       assert keptGraphConsumer != null;
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 dbd4989..0e9c611 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -966,6 +966,7 @@
 
     // Flag to turn on/off JDK11+ nest-access control even when not required (Cf backend)
     public boolean enableForceNestBasedAccessDesugaringForTest = false;
+    public boolean verifyKeptGraphInfo = false;
 
     public boolean desugarLambdasThroughLensCodeRewriter() {
       return enableStatefulLambdaCreateInstanceMethod;
diff --git a/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/IfRuleWithVerticalClassMerging.java b/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/IfRuleWithVerticalClassMerging.java
index c3dd579..4dba762 100644
--- a/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/IfRuleWithVerticalClassMerging.java
+++ b/src/test/java/com/android/tools/r8/shaking/ifrule/verticalclassmerging/IfRuleWithVerticalClassMerging.java
@@ -84,6 +84,10 @@
 
   private void configure(InternalOptions options) {
     options.enableVerticalClassMerging = enableVerticalClassMerging;
+    // TODO(b/141093535): The precondition set for conditionals is currently based on the syntactic
+    // form, when merging is enabled, if the precondition is merged to a differently named type, the
+    // rule will still fire, but the reported precondition type is incorrect.
+    options.testing.verifyKeptGraphInfo = !enableVerticalClassMerging;
   }
 
   @Test