diff --git a/src/main/java/com/android/tools/r8/graph/AppInfo.java b/src/main/java/com/android/tools/r8/graph/AppInfo.java
index b9542eb..86b2cb8 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfo.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.ResolutionResult.IncompatibleClassResult;
 import com.android.tools.r8.graph.ResolutionResult.NoSuchMethodResult;
 import com.android.tools.r8.graph.ResolutionResult.SingleResolutionResult;
+import com.android.tools.r8.ir.desugar.InterfaceMethodRewriter;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.InternalOptions;
@@ -144,6 +145,18 @@
     return app.definitionFor(type);
   }
 
+  public DexClass definitionForDesugarDependency(DexClass dependent, DexType type) {
+    if (dependent.type == type) {
+      return dependent;
+    }
+    DexClass definition = definitionFor(type);
+    if (definition != null && !definition.isLibraryClass() && dependent.isProgramClass()) {
+      InterfaceMethodRewriter.reportDependencyEdge(
+          dependent.asProgramClass(), definition, options());
+    }
+    return definition;
+  }
+
   @Override
   public DexProgramClass definitionForProgramType(DexType type) {
     return app.programDefinitionFor(type);
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/ClassProcessor.java b/src/main/java/com/android/tools/r8/ir/desugar/ClassProcessor.java
index 6fb1c27..a4fc2e9 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/ClassProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/ClassProcessor.java
@@ -140,12 +140,8 @@
               : closestProgramSubClass);
     }
 
-    public void reportDependency(DexClass clazz, AppView<?> appView) {
-      // If the direct subclass is in the compilation unit, report its dependencies.
-      if (clazz != directSubClass && directSubClass.isProgramClass()) {
-        InterfaceMethodRewriter.reportDependencyEdge(
-            directSubClass.asProgramClass(), clazz, appView);
-      }
+    public DexClass definitionFor(DexType type, AppView<?> appView) {
+      return appView.appInfo().definitionForDesugarDependency(directSubClass, type);
     }
 
     public void reportMissingType(DexType missingType, InterfaceMethodRewriter rewriter) {
@@ -168,8 +164,8 @@
     }
 
     @Override
-    public void reportDependency(DexClass clazz, AppView<?> appView) {
-      // Don't report dependencies in the library.
+    public DexClass definitionFor(DexType type, AppView<?> appView) {
+      return appView.definitionFor(type);
     }
 
     @Override
@@ -401,7 +397,7 @@
     if (type == null || type == dexItemFactory.objectType) {
       return null;
     }
-    DexClass clazz = appView.definitionFor(type);
+    DexClass clazz = context.definitionFor(type, appView);
     if (clazz == null) {
       context.reportMissingType(type, rewriter);
       return null;
@@ -419,7 +415,6 @@
     if (clazz.isLibraryClass()) {
       return ClassInfo.EMPTY;
     }
-    context.reportDependency(clazz, appView);
     return classInfo.computeIfAbsent(clazz, key -> visitClassInfoRaw(key, context));
   }
 
@@ -470,7 +465,6 @@
     if (iface.isLibraryClass() && ignoreLibraryInfo()) {
       return MethodSignatures.EMPTY;
     }
-    context.reportDependency(iface, appView);
     return interfaceInfo.computeIfAbsent(iface, key -> visitInterfaceInfoRaw(key, context));
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
index 795755e..7f4c043 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
@@ -961,7 +961,7 @@
     InterfaceProcessor processor = new InterfaceProcessor(appView, this);
     for (DexProgramClass clazz : builder.getProgramClasses()) {
       if (shouldProcess(clazz, flavour, true)) {
-        processor.process(clazz.asProgramClass(), graphLensBuilder);
+        processor.process(clazz, graphLensBuilder);
       }
     }
     for (Entry<DexLibraryClass, Set<DexProgramClass>> entry : requiredDispatchClasses.entrySet()) {
@@ -1114,8 +1114,8 @@
 
     // At this point we likely have a non-library type that may depend on default method information
     // from its interfaces and the dependency should be reported.
-    if (!definedInterface.isLibraryClass()) {
-      reportDependencyEdge(implementing, definedInterface, appView);
+    if (implementing.isProgramClass() && !definedInterface.isLibraryClass()) {
+      reportDependencyEdge(implementing.asProgramClass(), definedInterface, appView.options());
     }
 
     // Merge information from all superinterfaces.
@@ -1139,8 +1139,9 @@
   }
 
   public static void reportDependencyEdge(
-      DexClass dependent, DexClass dependency, AppView<?> appView) {
-    DesugarGraphConsumer consumer = appView.options().desugarGraphConsumer;
+      DexProgramClass dependent, DexClass dependency, InternalOptions options) {
+    assert !dependency.isLibraryClass();
+    DesugarGraphConsumer consumer = options.desugarGraphConsumer;
     if (consumer != null) {
       Origin dependentOrigin = dependent.getOrigin();
       Origin dependencyOrigin = dependency.getOrigin();
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java
index 787fbe1..9599834 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java
@@ -34,6 +34,7 @@
 import com.android.tools.r8.ir.synthetic.ForwardMethodSourceCode;
 import com.android.tools.r8.ir.synthetic.SynthesizedCode;
 import com.android.tools.r8.origin.SynthesizedOrigin;
+import com.android.tools.r8.utils.Pair;
 import com.google.common.collect.BiMap;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
@@ -302,6 +303,12 @@
     return true;
   }
 
+  private DexClass definitionForDependency(DexType dependency, DexClass dependent) {
+    return dependent.isProgramClass()
+        ? appView.appInfo().definitionForDesugarDependency(dependent.asProgramClass(), dependency)
+        : appView.definitionFor(dependency);
+  }
+
   // Returns true if the given interface method must be kept on [iface] after moving its
   // implementation to the companion class of [iface]. This is always the case for non-bridge
   // methods. Bridge methods that does not override an implementation in a super-interface must
@@ -313,32 +320,33 @@
       }
     }
     if (method.accessFlags.isBridge()) {
-      Deque<DexType> worklist = new ArrayDeque<>();
+      Deque<Pair<DexClass, DexType>> worklist = new ArrayDeque<>();
       Set<DexType> seenBefore = new HashSet<>();
-      if (iface.superType != null) {
-        worklist.add(iface.superType);
-      }
-      Collections.addAll(worklist, iface.interfaces.values);
+      addSuperTypes(iface, worklist);
       while (!worklist.isEmpty()) {
-        DexType superType = worklist.pop();
-        if (!seenBefore.add(superType)) {
+        Pair<DexClass, DexType> item = worklist.pop();
+        DexClass clazz = definitionForDependency(item.getSecond(), item.getFirst());
+        if (clazz == null || !seenBefore.add(clazz.type)) {
           continue;
         }
-        DexClass clazz = appView.definitionFor(superType);
-        if (clazz != null) {
-          if (clazz.lookupVirtualMethod(method.method) != null) {
-            return false;
-          }
-          if (clazz.superType != null) {
-            worklist.add(clazz.superType);
-          }
-          Collections.addAll(worklist, clazz.interfaces.values);
+        if (clazz.lookupVirtualMethod(method.method) != null) {
+          return false;
         }
+        addSuperTypes(clazz, worklist);
       }
     }
     return true;
   }
 
+  private static void addSuperTypes(DexClass clazz, Deque<Pair<DexClass, DexType>> worklist) {
+    if (clazz.superType != null) {
+      worklist.add(new Pair<>(clazz, clazz.superType));
+    }
+    for (DexType iface : clazz.interfaces.values) {
+      worklist.add(new Pair<>(clazz, iface));
+    }
+  }
+
   private boolean isStaticMethod(DexEncodedMethod method) {
     if (method.accessFlags.isNative()) {
       throw new Unimplemented("Native interface methods are not yet supported.");
diff --git a/src/test/java/com/android/tools/r8/desugar/graph/DesugarGraphTestConsumer.java b/src/test/java/com/android/tools/r8/desugar/graph/DesugarGraphTestConsumer.java
new file mode 100644
index 0000000..2111b7d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/desugar/graph/DesugarGraphTestConsumer.java
@@ -0,0 +1,34 @@
+// 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.desugar.graph;
+
+import com.android.tools.r8.DesugarGraphConsumer;
+import com.android.tools.r8.origin.Origin;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+public class DesugarGraphTestConsumer implements DesugarGraphConsumer {
+
+  private Map<Origin, Set<Origin>> edges = new HashMap<>();
+
+  public boolean contains(Origin dependency, Origin dependent) {
+    return edges.getOrDefault(dependency, Collections.emptySet()).contains(dependent);
+  }
+
+  public int totalEdgeCount() {
+    int count = 0;
+    for (Set<Origin> dependents : edges.values()) {
+      count += dependents.size();
+    }
+    return count;
+  }
+
+  @Override
+  public synchronized void accept(Origin dependent, Origin dependency) {
+    edges.computeIfAbsent(dependency, s -> new HashSet<>()).add(dependent);
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/desugar/graph/DesugarGraphUtils.java b/src/test/java/com/android/tools/r8/desugar/graph/DesugarGraphUtils.java
new file mode 100644
index 0000000..af3c6a0
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/desugar/graph/DesugarGraphUtils.java
@@ -0,0 +1,28 @@
+// 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.desugar.graph;
+
+import com.android.tools.r8.D8TestBuilder;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.origin.Origin;
+import java.io.IOException;
+
+public class DesugarGraphUtils {
+
+  public static Origin addClassWithOrigin(Class<?> clazz, D8TestBuilder builder)
+      throws IOException {
+    Origin origin = makeOrigin(clazz.getTypeName());
+    builder.getBuilder().addClassProgramData(ToolHelper.getClassAsBytes(clazz), origin);
+    return origin;
+  }
+
+  private static Origin makeOrigin(String name) {
+    return new Origin(Origin.root()) {
+      @Override
+      public String part() {
+        return name;
+      }
+    };
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/desugar/graph/InterfaceBridgeDependencyTest.java b/src/test/java/com/android/tools/r8/desugar/graph/InterfaceBridgeDependencyTest.java
new file mode 100644
index 0000000..ec8fcd4
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/desugar/graph/InterfaceBridgeDependencyTest.java
@@ -0,0 +1,98 @@
+// 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.desugar.graph;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.D8TestBuilder;
+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.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.StringUtils;
+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 InterfaceBridgeDependencyTest extends TestBase {
+
+  public interface I {
+    Object foo();
+  }
+
+  public interface J extends I {
+    // Covariant override of foo will result in a synthetic bridge method and J will depend on I.
+    default String foo() {
+      return "J::foo";
+    }
+  }
+
+  public interface K extends I {
+    // A simple override does not cause a bridge and there is no desugar dependencies for K.
+    default Object foo() {
+      return "K::foo";
+    }
+  }
+
+  public static class TestClass {
+
+    public static void main(String[] args) {
+      // There are no instances of I, J or K, so just make sure that the code requires they exist.
+      System.out.println(I.class.getName());
+      System.out.println(J.class.getName());
+      System.out.println(K.class.getName());
+    }
+  }
+
+  // Test runner follows.
+
+  private static final String EXPECTED =
+      StringUtils.lines(I.class.getName(), J.class.getName(), K.class.getName());
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimes().withAllApiLevels().build();
+  }
+
+  private final TestParameters parameters;
+
+  public InterfaceBridgeDependencyTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    if (parameters.isCfRuntime()) {
+      testForJvm()
+          .addProgramClasses(I.class, J.class, K.class, TestClass.class)
+          .run(parameters.getRuntime(), TestClass.class)
+          .assertSuccessWithOutput(EXPECTED);
+    } else {
+      D8TestBuilder builder = testForD8();
+      DesugarGraphTestConsumer consumer = new DesugarGraphTestConsumer();
+      builder.getBuilder().setDesugarGraphConsumer(consumer);
+      Origin originI = DesugarGraphUtils.addClassWithOrigin(I.class, builder);
+      Origin originJ = DesugarGraphUtils.addClassWithOrigin(J.class, builder);
+      Origin originK = DesugarGraphUtils.addClassWithOrigin(K.class, builder);
+      builder
+          .setMinApi(parameters.getApiLevel())
+          .addProgramClasses(TestClass.class)
+          .run(parameters.getRuntime(), TestClass.class)
+          .assertSuccessWithOutput(EXPECTED);
+      // If API level indicates desugaring is needed check the edges are reported.
+      if (parameters.getApiLevel().getLevel() < AndroidApiLevel.N.getLevel()) {
+        assertTrue(consumer.contains(originI, originJ));
+        assertFalse(consumer.contains(originI, originK));
+        assertEquals(1, consumer.totalEdgeCount());
+      } else {
+        assertEquals(0, consumer.totalEdgeCount());
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/desugar/graph/InterfaceToImplementingClassDependencyTest.java b/src/test/java/com/android/tools/r8/desugar/graph/InterfaceToImplementingClassDependencyTest.java
index 64044e6..7f76cad 100644
--- a/src/test/java/com/android/tools/r8/desugar/graph/InterfaceToImplementingClassDependencyTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/graph/InterfaceToImplementingClassDependencyTest.java
@@ -4,18 +4,14 @@
 package com.android.tools.r8.desugar.graph;
 
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
 
-import com.android.tools.r8.DesugarGraphConsumer;
+import com.android.tools.r8.D8TestBuilder;
 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.origin.Origin;
 import com.android.tools.r8.utils.AndroidApiLevel;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Map;
-import java.util.Set;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -26,7 +22,7 @@
 
   // The simplest program that gives rise to a dependency edge in the graph is an interface with
   // an implementing class. In this case, changes to the interface could require re-dexing the
-  // implementing class despite no derived changes happing to the classfile for the implementing
+  // implementing class despite no derived changes happening to the classfile for the implementing
   // class.
   //
   // For example, adding default method I.foo will trigger javac compilation of I and A to I.class
@@ -72,47 +68,24 @@
           .run(parameters.getRuntime(), TestClass.class)
           .assertSuccessWithOutputLines("Hello World!");
     } else {
-      MyDesugarGraphConsumer consumer = new MyDesugarGraphConsumer();
-      Origin originI = makeOrigin("I");
-      Origin originA = makeOrigin("A");
-      testForD8()
-          .setMinApi(parameters.getApiLevel())
+      D8TestBuilder builder = testForD8();
+      DesugarGraphTestConsumer consumer = new DesugarGraphTestConsumer();
+      builder.getBuilder().setDesugarGraphConsumer(consumer);
+      Origin originI = DesugarGraphUtils.addClassWithOrigin(I.class, builder);
+      Origin originA = DesugarGraphUtils.addClassWithOrigin(A.class, builder);
+      builder
           .addProgramClasses(TestClass.class)
-          .apply(
-              b ->
-                  b.getBuilder()
-                      .setDesugarGraphConsumer(consumer)
-                      .addClassProgramData(ToolHelper.getClassAsBytes(I.class), originI)
-                      .addClassProgramData(ToolHelper.getClassAsBytes(A.class), originA))
+          .setMinApi(parameters.getApiLevel())
           .run(parameters.getRuntime(), TestClass.class)
           .assertSuccessWithOutputLines("Hello World!");
       // If API level indicates desugaring is needed check the edges are reported.
       if (parameters.getApiLevel().getLevel() < AndroidApiLevel.N.getLevel()) {
-        assertEquals(1, consumer.edges.size());
-        assertEquals(originI, consumer.edges.keySet().iterator().next());
-        assertEquals(originA, consumer.edges.values().iterator().next().iterator().next());
+        assertEquals(1, consumer.totalEdgeCount());
+        assertTrue(consumer.contains(originI, originA));
       } else {
-        assertEquals(0, consumer.edges.size());
+        assertEquals(0, consumer.totalEdgeCount());
       }
     }
   }
 
-  private Origin makeOrigin(String name) {
-    return new Origin(Origin.root()) {
-      @Override
-      public String part() {
-        return name;
-      }
-    };
-  }
-
-  public static class MyDesugarGraphConsumer implements DesugarGraphConsumer {
-
-    Map<Origin, Set<Origin>> edges = new HashMap<>();
-
-    @Override
-    public synchronized void accept(Origin dependent, Origin dependency) {
-      edges.computeIfAbsent(dependency, s -> new HashSet<>()).add(dependent);
-    }
-  }
 }