diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 05557f3..bc99ee3 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 = "2.0.75";
+  public static final String LABEL = "2.0.76";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java b/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
index 936757f..a52eba7 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
@@ -25,7 +25,6 @@
 import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
 import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import java.util.ArrayList;
 import java.util.List;
 import java.util.function.Predicate;
 
@@ -233,48 +232,15 @@
     if (instructionMayHaveSideEffects(appView, method.method.holder)) {
       return false;
     }
-
-    if (appView.dexItemFactory().isConstructor(getInvokedMethod())) {
-      // If it is a constructor call that initializes an uninitialized object, then the
-      // uninitialized object must be dead. This is the case if all the constructor calls cannot
-      // have side effects and the instance is dead except for the constructor calls.
-      List<Instruction> otherInitCalls = null;
-      for (Instruction user : getReceiver().uniqueUsers()) {
-        if (user == this) {
-          continue;
-        }
-        if (user.isInvokeDirect()) {
-          InvokeDirect invoke = user.asInvokeDirect();
-          if (appView.dexItemFactory().isConstructor(invoke.getInvokedMethod())
-              && invoke.getReceiver() == getReceiver()) {
-            // If another constructor call than `this` is found, then it must not have side effects.
-            if (invoke.instructionMayHaveSideEffects(appView, method.method.holder)) {
-              return false;
-            }
-            if (otherInitCalls == null) {
-              otherInitCalls = new ArrayList<>();
-            }
-            otherInitCalls.add(invoke);
-          }
-        }
-      }
-
-      // Now check that the instance is dead except for the constructor calls.
-      final List<Instruction> finalOtherInitCalls = otherInitCalls;
-      Predicate<Instruction> ignoreConstructorCalls =
-          instruction ->
-              instruction == this
-                  || (finalOtherInitCalls != null && finalOtherInitCalls.contains(instruction));
-      if (!getReceiver().isDead(appView, code, ignoreConstructorCalls)) {
-        return false;
-      }
-
-      // Verify that it is not a super-constructor call (these cannot be removed).
-      if (getReceiver().getAliasedValue() == code.getThis()) {
-        return false;
-      }
+    if (!appView.dexItemFactory().isConstructor(getInvokedMethod())) {
+      return true;
     }
-
+    // Super-constructor calls cannot be removed.
+    if (getReceiver().getAliasedValue() == code.getThis()) {
+      return false;
+    }
+    // Constructor calls can only be removed if the receiver is dead. It is the responsibility of
+    // the caller to check this property.
     return true;
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/Value.java b/src/main/java/com/android/tools/r8/ir/code/Value.java
index 819e684..bb631c5 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Value.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Value.java
@@ -1057,6 +1057,16 @@
       if (!instruction.canBeDeadCode(appView, code)) {
         return false;
       }
+      if (instruction.isInvokeDirect()) {
+        // Constructor calls can only be removed if the receiver is dead.
+        // This fixes b/157926129, but note that the fix is different in R8 version 2.1 and higher.
+        InvokeDirect invoke = instruction.asInvokeDirect();
+        if (appView.dexItemFactory().isConstructor(invoke.getInvokedMethod())
+            && !active.contains(invoke.getReceiver())
+            && !invoke.getReceiver().isDead(appView, code, ignoreUser, active)) {
+          continue;
+        }
+      }
       Value outValue = instruction.outValue();
       if (outValue != null
           && !active.contains(outValue)
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java b/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
index f94b7a7..716f9e6 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
@@ -14,6 +14,7 @@
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeDirect;
 import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
@@ -102,6 +103,14 @@
       if (!current.canBeDeadCode(appView, code)) {
         continue;
       }
+      if (current.isInvokeDirect()) {
+        // Constructor calls can only be removed if the receiver is dead.
+        InvokeDirect invoke = current.asInvokeDirect();
+        if (appView.dexItemFactory().isConstructor(invoke.getInvokedMethod())
+            && !invoke.getReceiver().isDead(appView, code)) {
+          continue;
+        }
+      }
       Value outValue = current.outValue();
       if (outValue != null && !outValue.isDead(appView, code)) {
         continue;
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/sideeffect/DeadConstructorWithCycleTest.java b/src/test/java/com/android/tools/r8/ir/analysis/sideeffect/DeadConstructorWithCycleTest.java
new file mode 100644
index 0000000..ef95b71
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/analysis/sideeffect/DeadConstructorWithCycleTest.java
@@ -0,0 +1,69 @@
+// Copyright (c) 2020, 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.ir.analysis.sideeffect;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class DeadConstructorWithCycleTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public DeadConstructorWithCycleTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(DeadConstructorWithCycleTest.class)
+        .addKeepMainRule(TestClass.class)
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(inspector -> assertThat(inspector.clazz(A.class), not(isPresent())))
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput("");
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      Object o1 = null;
+      Object o2 = null;
+      for (int i = 1; i <= 2; i++) {
+        o1 = new A(o1, o2);
+        o2 = new A(o1, o2);
+      }
+    }
+  }
+
+  @NeverClassInline
+  static class A {
+
+    Object f1;
+    Object f2;
+
+    A(Object o1, Object o2) {
+      this.f1 = o1;
+      this.f2 = o2;
+    }
+  }
+}