diff --git a/src/main/java/com/android/tools/r8/experimental/graphinfo/ConditionalKeepRuleGraphNode.java b/src/main/java/com/android/tools/r8/experimental/graphinfo/ConditionalKeepRuleGraphNode.java
new file mode 100644
index 0000000..6b293e4
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/experimental/graphinfo/ConditionalKeepRuleGraphNode.java
@@ -0,0 +1,87 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.experimental.graphinfo;
+
+import com.android.tools.r8.Keep;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.position.Position;
+import com.android.tools.r8.position.TextPosition;
+import com.android.tools.r8.position.TextRange;
+import com.android.tools.r8.shaking.ProguardKeepRule;
+import com.google.common.base.Objects;
+import java.util.Set;
+
+@Keep
+public final class ConditionalKeepRuleGraphNode extends GraphNode {
+
+  private final ProguardKeepRule rule;
+  private final Set<GraphNode> preconditions;
+
+  public ConditionalKeepRuleGraphNode(ProguardKeepRule rule, Set<GraphNode> preconditions) {
+    super(false);
+    assert rule != null;
+    assert preconditions != null;
+    assert !preconditions.isEmpty();
+    this.rule = rule;
+    this.preconditions = preconditions;
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) {
+      return true;
+    }
+    if (!(o instanceof ConditionalKeepRuleGraphNode)) {
+      return false;
+    }
+    ConditionalKeepRuleGraphNode other = (ConditionalKeepRuleGraphNode) o;
+    return other.rule == rule && other.preconditions.equals(preconditions);
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hashCode(rule, preconditions);
+  }
+
+  public Origin getOrigin() {
+    return rule.getOrigin();
+  }
+
+  public Position getPosition() {
+    return rule.getPosition();
+  }
+
+  public String getContent() {
+    return rule.getSource();
+  }
+
+  public Set<GraphNode> getPreconditions() {
+    return preconditions;
+  }
+
+  /**
+   * Get an identity string determining this keep rule.
+   *
+   * <p>The identity string is typically the source-file (if present) followed by the line number.
+   * {@code <keep-rule-file>:<keep-rule-start-line>:<keep-rule-start-column>}.
+   */
+  @Override
+  public String toString() {
+    return (getOrigin() == Origin.unknown() ? getContent() : getOrigin())
+        + ":"
+        + shortPositionInfo(getPosition());
+  }
+
+  private static String shortPositionInfo(Position position) {
+    if (position instanceof TextRange) {
+      TextPosition start = ((TextRange) position).getStart();
+      return start.getLine() + ":" + start.getColumn();
+    }
+    if (position instanceof TextPosition) {
+      TextPosition start = (TextPosition) position;
+      return start.getLine() + ":" + start.getColumn();
+    }
+    return position.getDescription();
+  }
+}
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 3e55242..214d103 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
@@ -16,6 +16,8 @@
     // Prioritized list of edge types.
     KeepRule,
     CompatibilityRule,
+    ConditionalKeepRule,
+    KeepRulePrecondition,
     InstantiatedIn,
     InvokedViaSuper,
     TargetedBySuper,
@@ -45,7 +47,10 @@
     switch (edgeKind()) {
       case KeepRule:
       case CompatibilityRule:
+      case ConditionalKeepRule:
         return "referenced in keep rule";
+      case KeepRulePrecondition:
+        return "satisfied with precondition";
       case InstantiatedIn:
         return "instantiated in";
       case InvokedViaSuper:
diff --git a/src/main/java/com/android/tools/r8/experimental/graphinfo/KeepRuleGraphNode.java b/src/main/java/com/android/tools/r8/experimental/graphinfo/KeepRuleGraphNode.java
index 7eb55a8..5aaf157 100644
--- a/src/main/java/com/android/tools/r8/experimental/graphinfo/KeepRuleGraphNode.java
+++ b/src/main/java/com/android/tools/r8/experimental/graphinfo/KeepRuleGraphNode.java
@@ -10,6 +10,8 @@
 import com.android.tools.r8.position.TextRange;
 import com.android.tools.r8.shaking.ProguardKeepRule;
 
+// Note: this could potentially be merged with ConditionalKeepRuleGraphNode
+// and an empty precondition set.
 @Keep
 public final class KeepRuleGraphNode extends GraphNode {
 
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 8ae75ff..04b9b53 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -874,12 +874,28 @@
       } else {
         assert !deferredAnnotations.containsKey(holder.type);
       }
-      rootSet.forEachDependentStaticMember(holder, appView, this::enqueueRootItem);
+      rootSet.forEachDependentStaticMember(holder, appView, this::enqueueDependentItem);
       compatEnqueueHolderIfDependentNonStaticMember(
           holder, rootSet.getDependentKeepClassCompatRule(holder.getType()));
     }
   }
 
+  private void enqueueDependentItem(
+      DexDefinition precondition, DexDefinition consequent, Set<ProguardKeepRule> reasons) {
+    DexReference preconditionReference = precondition.toReference();
+    if (keptGraphConsumer != null) {
+      GraphNode consequentNode = getGraphNode(consequent.toReference());
+      for (ProguardKeepRule rule : reasons) {
+        registerEdge(
+            consequentNode, KeepReason.dueToConditionalKeepRule(rule, preconditionReference));
+      }
+    }
+    // Note: the reason for keeping is reproted above, so this just uses the first.
+    ProguardKeepRule reason = reasons.iterator().next();
+    internalEnqueueRootItem(
+        consequent, KeepReason.dueToConditionalKeepRule(reason, preconditionReference));
+  }
+
   private void processAnnotations(DexDefinition holder, DexAnnotation[] annotations) {
     for (DexAnnotation annotation : annotations) {
       processAnnotation(holder, annotation);
@@ -2498,7 +2514,15 @@
     GraphNode sourceNode = getSourceNode(reason);
     // TODO(b/120959039): Make sure we do have edges to nodes deriving library nodes!
     if (!sourceNode.isLibraryNode()) {
-      keptGraphConsumer.acceptEdge(sourceNode, target, getEdgeInfo(reason));
+      GraphEdgeInfo edgeInfo = getEdgeInfo(reason);
+      keptGraphConsumer.acceptEdge(sourceNode, target, edgeInfo);
+      if (reason.isDueToConditionalKeepRule()) {
+        GraphEdgeInfo conditionEdge = new GraphEdgeInfo(EdgeKind.KeepRulePrecondition);
+        for (DexReference precondition : reason.getPreconditions()) {
+          GraphNode preconditionNode = getGraphNode(precondition);
+          keptGraphConsumer.acceptEdge(preconditionNode, sourceNode, conditionEdge);
+        }
+      }
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/shaking/KeepReason.java b/src/main/java/com/android/tools/r8/shaking/KeepReason.java
index 4218b569..09f80d1 100644
--- a/src/main/java/com/android/tools/r8/shaking/KeepReason.java
+++ b/src/main/java/com/android/tools/r8/shaking/KeepReason.java
@@ -3,13 +3,18 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.shaking;
 
+import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.experimental.graphinfo.GraphEdgeInfo;
 import com.android.tools.r8.experimental.graphinfo.GraphEdgeInfo.EdgeKind;
 import com.android.tools.r8.experimental.graphinfo.GraphNode;
 import com.android.tools.r8.graph.DexDefinition;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexItem;
+import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Set;
 
 // TODO(herhut): Canonicalize reason objects.
 public abstract class KeepReason {
@@ -26,6 +31,10 @@
     return new DueToKeepRule(rule);
   }
 
+  static KeepReason dueToConditionalKeepRule(ProguardKeepRule rule, DexReference reference) {
+    return new DueToConditionalKeepRule(rule, reference);
+  }
+
   static KeepReason dueToProguardCompatibilityKeepRule(ProguardKeepRule rule) {
     return new DueToProguardCompatibilityKeepRule(rule);
   }
@@ -74,6 +83,10 @@
     return false;
   }
 
+  public boolean isDueToConditionalKeepRule() {
+    return false;
+  }
+
   public ProguardKeepRule getProguardKeepRule() {
     return null;
   }
@@ -90,6 +103,10 @@
     return new MethodHandleReferencedFrom(method);
   }
 
+  public Collection<DexReference> getPreconditions() {
+    throw new Unreachable();
+  }
+
   private static class DueToKeepRule extends KeepReason {
 
     final ProguardKeepRule keepRule;
@@ -135,6 +152,32 @@
     }
   }
 
+  private static class DueToConditionalKeepRule extends DueToKeepRule {
+
+    private final DexReference condition;
+
+    public DueToConditionalKeepRule(ProguardKeepRule rule, DexReference condition) {
+      super(rule);
+      assert condition != null;
+      this.condition = condition;
+    }
+
+    @Override
+    public Set<DexReference> getPreconditions() {
+      return Collections.singleton(condition);
+    }
+
+    @Override
+    public boolean isDueToConditionalKeepRule() {
+      return true;
+    }
+
+    @Override
+    public EdgeKind edgeKind() {
+      return EdgeKind.ConditionalKeepRule;
+    }
+  }
+
   private abstract static class BasedOnOtherMethod extends KeepReason {
 
     private final DexEncodedMethod method;
diff --git a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
index 819c4ff..3cabdf2 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
@@ -27,6 +27,7 @@
 import com.android.tools.r8.graph.DirectMappedDexApplication;
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.logging.Log;
+import com.android.tools.r8.utils.Consumer3;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.MethodSignatureEquivalence;
 import com.android.tools.r8.utils.StringDiagnostic;
@@ -1260,13 +1261,15 @@
     public void forEachDependentStaticMember(
         DexDefinition item,
         AppView<?> appView,
-        BiConsumer<DexDefinition, Set<ProguardKeepRule>> fn) {
-      getDependentItems(item).forEach((reference, reasons) -> {
-        DexDefinition definition = appView.definitionFor(reference);
-        if (definition != null && !definition.isDexClass() && definition.isStaticMember()) {
-          fn.accept(definition, reasons);
-        }
-      });
+        Consumer3<DexDefinition, DexDefinition, Set<ProguardKeepRule>> fn) {
+      getDependentItems(item)
+          .forEach(
+              (reference, reasons) -> {
+                DexDefinition definition = appView.definitionFor(reference);
+                if (definition != null && !definition.isDexClass() && definition.isStaticMember()) {
+                  fn.accept(item, definition, reasons);
+                }
+              });
     }
 
     public void forEachDependentNonStaticMember(
diff --git a/src/main/java/com/android/tools/r8/utils/Consumer3.java b/src/main/java/com/android/tools/r8/utils/Consumer3.java
new file mode 100644
index 0000000..029ed3d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/Consumer3.java
@@ -0,0 +1,9 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.utils;
+
+@FunctionalInterface
+public interface Consumer3<F1, F2, F3> {
+  void accept(F1 f1, F2 f2, F3 f3);
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptByKeepClassMembersTest.java b/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptByKeepClassMembersTest.java
new file mode 100644
index 0000000..9d4c94c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptByKeepClassMembersTest.java
@@ -0,0 +1,23 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.shaking.keptgraph;
+
+import com.android.tools.r8.NeverInline;
+
+public class KeptByKeepClassMembersTest {
+
+  public static void main(String[] args) {
+    bar();
+  }
+
+  @NeverInline
+  static void bar() {
+    System.out.println("called bar");
+  }
+
+  @NeverInline
+  static void baz() {
+    System.out.println("called baz");
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptByKeepClassMembersTestRunner.java b/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptByKeepClassMembersTestRunner.java
new file mode 100644
index 0000000..50e381c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/keptgraph/KeptByKeepClassMembersTestRunner.java
@@ -0,0 +1,103 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.shaking.keptgraph;
+
+import static com.android.tools.r8.references.Reference.classFromClass;
+import static com.android.tools.r8.references.Reference.methodFromMethod;
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.references.ClassReference;
+import com.android.tools.r8.references.MethodReference;
+import com.android.tools.r8.shaking.WhyAreYouKeepingConsumer;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.graphinspector.GraphInspector;
+import com.android.tools.r8.utils.graphinspector.GraphInspector.QueryNode;
+import java.io.ByteArrayOutputStream;
+import java.io.PrintStream;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class KeptByKeepClassMembersTestRunner extends TestBase {
+
+  private static final Class<?> CLASS = KeptByKeepClassMembersTest.class;
+  private static final String PKG = CLASS.getPackage().getName();
+  private final String EXPECTED = StringUtils.lines("called bar");
+  private final String EXPECTED_WHYAREYOUKEEPING =
+      StringUtils.lines(
+          "void " + PKG + ".KeptByKeepClassMembersTest.baz()",
+          "|- is referenced in keep rule:",
+          "|  -keepclassmembers class "
+              + PKG
+              + ".KeptByKeepClassMembersTest { static void baz(); }",
+          "|- is satisfied with precondition:",
+          "|  " + PKG + ".KeptByKeepClassMembersTest",
+          "|- is referenced in keep rule:",
+          "|  -keep class "
+              + PKG
+              + ".KeptByKeepClassMembersTest"
+              + " { public static void main(java.lang.String[]); }");
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimes().withAllApiLevels().build();
+  }
+
+  public KeptByKeepClassMembersTestRunner(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testKeptMethod() throws Exception {
+    ClassReference clazz = classFromClass(CLASS);
+    MethodReference mainMethod = methodFromMethod(CLASS.getDeclaredMethod("main", String[].class));
+    MethodReference barMethod = methodFromMethod(CLASS.getDeclaredMethod("bar"));
+    MethodReference bazMethod = methodFromMethod(CLASS.getDeclaredMethod("baz"));
+
+    String keepClassMembersRuleContent =
+        "-keepclassmembers class "
+            + KeptByKeepClassMembersTest.class.getTypeName()
+            + " { static void baz(); }";
+
+    WhyAreYouKeepingConsumer whyAreYouKeepingConsumer = new WhyAreYouKeepingConsumer(null);
+    GraphInspector inspector =
+        testForR8(parameters.getBackend())
+            .enableGraphInspector(whyAreYouKeepingConsumer)
+            .enableInliningAnnotations()
+            .addProgramClasses(CLASS)
+            .addKeepMainRule(KeptByKeepClassMembersTest.class)
+            .addKeepRules(keepClassMembersRuleContent)
+            .setMinApi(parameters.getApiLevel())
+            .run(parameters.getRuntime(), CLASS)
+            .assertSuccessWithOutput(EXPECTED)
+            .graphInspector();
+
+    // The only root should be the keep annotation rule.
+    assertEquals(1, inspector.getRoots().size());
+    QueryNode keepMainRule = inspector.rule(Origin.unknown(), 1, 1).assertRoot();
+    QueryNode keepClassMembersRule = inspector.rule(keepClassMembersRuleContent).assertNotRoot();
+
+    // Check that the call chain goes from root -> main(unchanged) -> bar(renamed).
+    inspector.method(barMethod).assertRenamed().assertInvokedFrom(mainMethod);
+    inspector.method(mainMethod).assertNotRenamed().assertKeptBy(keepMainRule);
+
+    // Check baz is kept by the dependent rule.
+    inspector.method(bazMethod).assertNotRenamed().assertKeptBy(keepClassMembersRule);
+
+    // Regression for b/131822600, the dependent rule must be satisfied by Bar being kept.
+    keepClassMembersRule.assertSatisfiedBy(inspector.clazz(clazz));
+
+    ByteArrayOutputStream baos = new ByteArrayOutputStream();
+    whyAreYouKeepingConsumer.printWhyAreYouKeeping(bazMethod, new PrintStream(baos));
+    assertEquals(EXPECTED_WHYAREYOUKEEPING, baos.toString());
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/utils/graphinspector/GraphInspector.java b/src/test/java/com/android/tools/r8/utils/graphinspector/GraphInspector.java
index 1d53013..cd77042 100644
--- a/src/test/java/com/android/tools/r8/utils/graphinspector/GraphInspector.java
+++ b/src/test/java/com/android/tools/r8/utils/graphinspector/GraphInspector.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.utils.graphinspector;
 
 import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
 
@@ -75,6 +76,8 @@
 
     abstract boolean isKeptBy(QueryNode node);
 
+    abstract boolean isSatisfiedBy(QueryNode node);
+
     abstract String getNodeDescription();
 
     protected String errorMessage(String expected, String actual) {
@@ -101,6 +104,11 @@
       return this;
     }
 
+    public QueryNode assertNotRoot() {
+      assertFalse(errorMessage("non-root", "root"), isRoot());
+      return this;
+    }
+
     public QueryNode assertRenamed() {
       assertTrue(errorMessage("renamed", "not-renamed"), isRenamed());
       return this;
@@ -153,6 +161,15 @@
           isKeptBy(node));
       return this;
     }
+
+    public QueryNode assertSatisfiedBy(QueryNode node) {
+      assertTrue(
+          "Invalid call to assertSatisfiedBy with: " + node.getNodeDescription(), node.isPresent());
+      assertTrue(
+          errorMessage("satisfied by " + node.getNodeDescription(), "was not satisfied by it"),
+          isSatisfiedBy(node));
+      return this;
+    }
   }
 
   private static class AbsentQueryNode extends QueryNode {
@@ -201,6 +218,12 @@
       fail("Invalid call to isKeptBy on " + getNodeDescription());
       throw new Unreachable();
     }
+
+    @Override
+    public boolean isSatisfiedBy(QueryNode node) {
+      fail("Invalid call to isTriggeredBy on " + getNodeDescription());
+      throw new Unreachable();
+    }
   }
 
   // Class representing a point in the kept-graph structure.
@@ -281,9 +304,22 @@
       return filterSources((source, infos) -> impl.graphNode == source).findFirst().isPresent();
     }
 
+    @Override
+    public boolean isSatisfiedBy(QueryNode node) {
+      assertTrue(
+          "Invalid call to isTriggeredBy on non-keep rule node: " + graphNode,
+          graphNode instanceof KeepRuleGraphNode);
+      if (!(node instanceof QueryNodeImpl)) {
+        return false;
+      }
+      QueryNodeImpl impl = (QueryNodeImpl) node;
+      return filterSources((source, infos) -> impl.graphNode == source).findFirst().isPresent();
+    }
+
     private Stream<GraphNode> filterSources(BiPredicate<GraphNode, Set<GraphEdgeInfo>> test) {
       Map<GraphNode, Set<GraphEdgeInfo>> sources =
           inspector.consumer.getSourcesTargeting(graphNode);
+      assertNotNull("Attempt to iterate sources of apparent root node: " + graphNode, sources);
       return sources.entrySet().stream()
           .filter(e -> test.test(e.getKey(), e.getValue()))
           .map(Entry::getKey);