diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 8038d4e..872f8cd 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.5.54";
+  public static final String LABEL = "1.5.55";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/graph/AccessFlags.java b/src/main/java/com/android/tools/r8/graph/AccessFlags.java
index 9716eea..a0322a1 100644
--- a/src/main/java/com/android/tools/r8/graph/AccessFlags.java
+++ b/src/main/java/com/android/tools/r8/graph/AccessFlags.java
@@ -83,8 +83,18 @@
     return originalFlags | modifiedFlags;
   }
 
-  public boolean isMoreVisibleThan(AccessFlags other) {
-    return visibilityOrdinal() > other.visibilityOrdinal();
+  public boolean isMoreVisibleThan(
+      AccessFlags other, String packageNameThis, String packageNameOther) {
+    int visibilityOrdinal = visibilityOrdinal();
+    if (visibilityOrdinal > other.visibilityOrdinal()) {
+      return true;
+    }
+    if (visibilityOrdinal == other.visibilityOrdinal()
+        && isVisibilityDependingOnPackage()
+        && !packageNameThis.equals(packageNameOther)) {
+      return true;
+    }
+    return false;
   }
 
   public boolean isAtLeastAsVisibleAs(AccessFlags other) {
@@ -106,6 +116,10 @@
     return 1;
   }
 
+  public boolean isVisibilityDependingOnPackage() {
+    return visibilityOrdinal() == 1 || visibilityOrdinal() == 2;
+  }
+
   public boolean isPublic() {
     return isSet(Constants.ACC_PUBLIC);
   }
diff --git a/src/main/java/com/android/tools/r8/shaking/ScopedDexMethodSet.java b/src/main/java/com/android/tools/r8/shaking/ScopedDexMethodSet.java
index 3587cf4..6d76acd 100644
--- a/src/main/java/com/android/tools/r8/shaking/ScopedDexMethodSet.java
+++ b/src/main/java/com/android/tools/r8/shaking/ScopedDexMethodSet.java
@@ -51,7 +51,11 @@
   public boolean addMethodIfMoreVisible(DexEncodedMethod method) {
     Wrapper<DexMethod> wrapped = METHOD_EQUIVALENCE.wrap(method.method);
     DexEncodedMethod existing = lookup(wrapped);
-    if (existing == null || method.accessFlags.isMoreVisibleThan(existing.accessFlags)) {
+    if (existing == null
+        || method.accessFlags.isMoreVisibleThan(
+            existing.accessFlags,
+            method.method.holder.getPackageName(),
+            existing.method.holder.getPackageName())) {
       items.put(wrapped, method);
       return true;
     }
diff --git a/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
index 8b4bedb..cbe3961 100644
--- a/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
@@ -360,7 +360,10 @@
     Representative packageRepresentative = representatives.get(key);
     if (packageRepresentative != null) {
       if (isValidRepresentative(clazz)
-          && clazz.accessFlags.isMoreVisibleThan(packageRepresentative.clazz.accessFlags)) {
+          && clazz.accessFlags.isMoreVisibleThan(
+              packageRepresentative.clazz.accessFlags,
+              clazz.type.getPackageName(),
+              packageRepresentative.clazz.type.getPackageName())) {
         // Use `clazz` as a representative for this package instead.
         Representative newRepresentative = getOrCreateRepresentative(key, clazz);
         newRepresentative.include(packageRepresentative.clazz);
@@ -482,6 +485,7 @@
           targetClass.type.toSourceString());
     }
 
+    // TODO(b/136457753) This check is a bit weird for protected, since it is moving access.
     assert targetClass.accessFlags.isAtLeastAsVisibleAs(sourceClass.accessFlags);
     assert sourceClass.instanceFields().size() == 0;
     assert targetClass.instanceFields().size() == 0;
diff --git a/src/test/java/com/android/tools/r8/shaking/b136195382/AbstractBridgeInheritTest.java b/src/test/java/com/android/tools/r8/shaking/b136195382/AbstractBridgeInheritTest.java
new file mode 100644
index 0000000..2514381
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/b136195382/AbstractBridgeInheritTest.java
@@ -0,0 +1,49 @@
+// 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.b136195382;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.shaking.b136195382.package1.Factory;
+import com.android.tools.r8.shaking.b136195382.package1.Service;
+import com.android.tools.r8.shaking.b136195382.package2.Main;
+import com.android.tools.r8.shaking.b136195382.package2.SubFactory;
+import com.android.tools.r8.shaking.b136195382.package2.SubService;
+import java.io.IOException;
+import java.util.concurrent.ExecutionException;
+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 AbstractBridgeInheritTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimes().build();
+  }
+
+  public AbstractBridgeInheritTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testRemovingBridge()
+      throws ExecutionException, CompilationFailedException, IOException {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(
+            Service.class, Factory.class, SubService.class, SubFactory.class, Main.class)
+        .addKeepMainRule(Main.class)
+        .enableInliningAnnotations()
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("Hello World!")
+        .inspector();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/b136195382/package1/Factory.java b/src/test/java/com/android/tools/r8/shaking/b136195382/package1/Factory.java
new file mode 100644
index 0000000..90c9753
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/b136195382/package1/Factory.java
@@ -0,0 +1,15 @@
+// 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.b136195382.package1;
+
+import com.android.tools.r8.NeverInline;
+
+public class Factory {
+
+  @NeverInline
+  public static String create(Service service) {
+    return service.baseUrl();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/b136195382/package1/Service.java b/src/test/java/com/android/tools/r8/shaking/b136195382/package1/Service.java
new file mode 100644
index 0000000..3099321
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/b136195382/package1/Service.java
@@ -0,0 +1,10 @@
+// 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.b136195382.package1;
+
+public abstract class Service {
+
+  protected abstract String baseUrl();
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/b136195382/package2/Main.java b/src/test/java/com/android/tools/r8/shaking/b136195382/package2/Main.java
new file mode 100644
index 0000000..be585a4
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/b136195382/package2/Main.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.b136195382.package2;
+
+import com.android.tools.r8.shaking.b136195382.package1.Factory;
+
+public class Main extends SubService {
+
+  @Override
+  protected String baseUrl() {
+    return "Hello World!";
+  }
+
+  public static void main(String[] args) {
+    if (args.length == 0) {
+      System.out.println(SubFactory.create(new Main()));
+    } else {
+      System.out.println(Factory.create(new Main()));
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/b136195382/package2/SubFactory.java b/src/test/java/com/android/tools/r8/shaking/b136195382/package2/SubFactory.java
new file mode 100644
index 0000000..fbdeaa2
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/b136195382/package2/SubFactory.java
@@ -0,0 +1,15 @@
+// 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.b136195382.package2;
+
+import com.android.tools.r8.NeverInline;
+
+public class SubFactory {
+
+  @NeverInline
+  public static String create(SubService subService) {
+    return subService.baseUrl();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/b136195382/package2/SubService.java b/src/test/java/com/android/tools/r8/shaking/b136195382/package2/SubService.java
new file mode 100644
index 0000000..c6891ef
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/b136195382/package2/SubService.java
@@ -0,0 +1,13 @@
+// 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.b136195382.package2;
+
+import com.android.tools.r8.shaking.b136195382.package1.Service;
+
+public abstract class SubService extends Service {
+
+  @Override
+  protected abstract String baseUrl();
+}