diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 5193ef8..0a02824 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.1.30";
+  public static final String LABEL = "2.1.31";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexMethod.java b/src/main/java/com/android/tools/r8/graph/DexMethod.java
index d3dd5fc..dbccbd6 100644
--- a/src/main/java/com/android/tools/r8/graph/DexMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexMethod.java
@@ -191,4 +191,8 @@
     return name == dexItemFactory.deserializeLambdaMethodName
         && proto == dexItemFactory.deserializeLambdaMethodProto;
   }
+
+  public boolean isInstanceInitializer(DexDefinitionSupplier definitions) {
+    return definitions.dexItemFactory().isConstructor(this);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingDefinition.java b/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingDefinition.java
index 3f0d75a..ed2cdd8 100644
--- a/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingDefinition.java
+++ b/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingDefinition.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 
 public class AlwaysMaterializingDefinition extends ConstInstruction {
 
@@ -29,9 +30,9 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
     // This instruction may never be considered dead as it must remain.
-    return false;
+    return DeadInstructionResult.notDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingNop.java b/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingNop.java
index 3cd25ea..45fa439 100644
--- a/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingNop.java
+++ b/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingNop.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 
@@ -30,8 +31,8 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return false;
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
+    return DeadInstructionResult.notDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingUser.java b/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingUser.java
index 4b99975..21b02ba 100644
--- a/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingUser.java
+++ b/src/main/java/com/android/tools/r8/ir/code/AlwaysMaterializingUser.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 
@@ -29,9 +30,9 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
     // This instruction may never be considered dead as it must remain.
-    return false;
+    return DeadInstructionResult.notDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/Argument.java b/src/main/java/com/android/tools/r8/ir/code/Argument.java
index 5b68bf5..fbca901 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Argument.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Argument.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import java.util.Set;
@@ -62,11 +63,11 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appview, IRCode code) {
+  public DeadInstructionResult canBeDeadCode(AppView<?> appview, IRCode code) {
     // Never remove argument instructions. That would change the signature of the method.
     // TODO(b/65810338): If we can tell that a method never uses an argument we might be able to
     // rewrite the signature and call-sites.
-    return false;
+    return DeadInstructionResult.notDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java b/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
index e9f074b..4f0995b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
@@ -84,11 +84,6 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return !instructionMayHaveSideEffects(appView, code.context());
-  }
-
-  @Override
   public boolean identicalAfterRegisterAllocation(Instruction other, RegisterAllocator allocator) {
     if (super.identicalAfterRegisterAllocation(other, allocator)) {
       // The array length instruction doesn't carry the element type. The art verifier doesn't
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java b/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java
index 860473c..9dae2a8 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayPut.java
@@ -191,11 +191,6 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return !instructionMayHaveSideEffects(appView, code.context());
-  }
-
-  @Override
   public boolean identicalAfterRegisterAllocation(Instruction other, RegisterAllocator allocator) {
     // We cannot share ArrayPut instructions without knowledge of the type of the array input.
     // If multiple primitive array types flow to the same ArrayPut instruction the art verifier
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstClass.java b/src/main/java/com/android/tools/r8/ir/code/ConstClass.java
index 4594db9..d28135d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstClass.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstClass.java
@@ -133,11 +133,6 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return !instructionMayHaveSideEffects(appView, code.context());
-  }
-
-  @Override
   public boolean isOutConstant() {
     return true;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstString.java b/src/main/java/com/android/tools/r8/ir/code/ConstString.java
index 3bd1d56..453c161 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstString.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstString.java
@@ -18,6 +18,7 @@
 import com.android.tools.r8.ir.code.BasicBlock.ThrowingInfo;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.io.UTFDataFormatException;
 
@@ -132,9 +133,12 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
     // No side-effect, such as throwing an exception, in CF.
-    return appView.options().isGeneratingClassFiles() || !instructionInstanceCanThrow();
+    if (appView.options().isGeneratingClassFiles() || !instructionInstanceCanThrow()) {
+      return DeadInstructionResult.deadIfOutValueIsDead();
+    }
+    return DeadInstructionResult.notDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/DebugLocalRead.java b/src/main/java/com/android/tools/r8/ir/code/DebugLocalRead.java
index 292d6b7..5a3e094 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DebugLocalRead.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DebugLocalRead.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 
@@ -71,10 +72,10 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
     // Reads are never dead code.
     // They should also have a non-empty set of debug values (see RegAlloc::computeDebugInfo)
-    return false;
+    return DeadInstructionResult.notDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/DebugLocalsChange.java b/src/main/java/com/android/tools/r8/ir/code/DebugLocalsChange.java
index 842eaa4..1ff7509 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DebugLocalsChange.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DebugLocalsChange.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.utils.StringUtils;
@@ -83,8 +84,8 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return false;
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
+    return DeadInstructionResult.notDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/DebugPosition.java b/src/main/java/com/android/tools/r8/ir/code/DebugPosition.java
index fd6f9a9..c347f87 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DebugPosition.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DebugPosition.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 
@@ -67,8 +68,8 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return false;
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
+    return DeadInstructionResult.notDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/DexItemBasedConstString.java b/src/main/java/com/android/tools/r8/ir/code/DexItemBasedConstString.java
index 959dbfc..0753447 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DexItemBasedConstString.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DexItemBasedConstString.java
@@ -16,6 +16,7 @@
 import com.android.tools.r8.ir.code.BasicBlock.ThrowingInfo;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.naming.dexitembasedstring.NameComputationInfo;
@@ -131,9 +132,9 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
     // No side-effect, such as throwing an exception, in CF.
-    return true;
+    return DeadInstructionResult.deadIfOutValueIsDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java b/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
index 924d256..7dad747 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
@@ -123,16 +123,6 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    // instance-get can be dead code as long as it cannot have any of the following:
-    // * NoSuchFieldError (resolution failure)
-    // * IncompatibleClassChangeError (instance-* instruction for static fields)
-    // * IllegalAccessError (not visible from the access context)
-    // * NullPointerException (null receiver)
-    return !instructionMayHaveSideEffects(appView, code.context());
-  }
-
-  @Override
   public int maxInValueRegister() {
     return Constants.U4BIT_MAX;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstancePut.java b/src/main/java/com/android/tools/r8/ir/code/InstancePut.java
index b8a5787..296b2f9 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstancePut.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstancePut.java
@@ -142,20 +142,6 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    // instance-put can be dead as long as it cannot have any of the following:
-    // * NoSuchFieldError (resolution failure)
-    // * IncompatibleClassChangeError (static-* instruction for instance fields)
-    // * IllegalAccessError (not visible from the access context)
-    // * NullPointerException (null receiver)
-    // * not read at all
-    boolean haveSideEffects = instructionMayHaveSideEffects(appView, code.context());
-    assert appView.enableWholeProgramOptimizations() || haveSideEffects
-        : "Expected instance-put instruction to have side effects in D8";
-    return !haveSideEffects;
-  }
-
-  @Override
   public boolean identicalAfterRegisterAllocation(Instruction other, RegisterAllocator allocator) {
     if (!super.identicalAfterRegisterAllocation(other, allocator)) {
       return false;
diff --git a/src/main/java/com/android/tools/r8/ir/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index 1400455..4b1f1bf 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -24,6 +24,7 @@
 import com.android.tools.r8.ir.analysis.value.UnknownValue;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.ir.regalloc.RegisterAllocator;
@@ -591,10 +592,10 @@
   }
 
   /** Returns true is this instruction can be treated as dead code if its outputs are not used. */
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    // TODO(b/129530569): instructions with fine-grained side effect analysis may use:
-    // return !instructionMayHaveSideEffects(appView, code.method.holder());
-    return !instructionInstanceCanThrow();
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
+    return instructionMayHaveSideEffects(appView, code.context())
+        ? DeadInstructionResult.notDead()
+        : DeadInstructionResult.deadIfOutValueIsDead();
   }
 
   /**
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 0f736a0..020254f 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
@@ -20,12 +20,11 @@
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import java.util.ArrayList;
 import java.util.List;
-import java.util.function.Predicate;
 
 public class InvokeDirect extends InvokeMethodWithReceiver {
 
@@ -162,54 +161,20 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
     ProgramMethod context = code.context();
     if (instructionMayHaveSideEffects(appView, context)) {
-      return false;
+      return DeadInstructionResult.notDead();
     }
-
-    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, context)) {
-              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 (!getInvokedMethod().isInstanceInitializer(appView)) {
+      return DeadInstructionResult.deadIfOutValueIsDead();
     }
-
-    return true;
+    // Super-constructor calls cannot be removed.
+    if (getReceiver().getAliasedValue() == code.getThis()) {
+      return DeadInstructionResult.notDead();
+    }
+    // Constructor calls can only be removed if the receiver is dead.
+    return DeadInstructionResult.deadIfInValueIsDead(getReceiver());
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
index a2aa502..5e0e3eb 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
@@ -242,9 +242,4 @@
 
     return optimizationInfo.mayHaveSideEffects();
   }
-
-  @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return !instructionMayHaveSideEffects(appView, code.context());
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
index cc83815..314317e 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
@@ -182,11 +182,6 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return !instructionMayHaveSideEffects(appView, code.context());
-  }
-
-  @Override
   public boolean instructionMayTriggerMethodInvocation(AppView<?> appView, ProgramMethod context) {
     return false;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java b/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
index fc6028f..2783471 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
@@ -195,11 +195,6 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return !instructionMayHaveSideEffects(appView, code.context());
-  }
-
-  @Override
   public boolean instructionMayTriggerMethodInvocation(AppView<?> appView, ProgramMethod context) {
     return false;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java b/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
index 7f5836a..00c88b8 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
@@ -229,9 +229,4 @@
             type -> appInfoWithLiveness.isSubtype(context.getHolderType(), type),
             Sets.newIdentityHashSet());
   }
-
-  @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return !instructionMayHaveSideEffects(appView, code.context());
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/JumpInstruction.java b/src/main/java/com/android/tools/r8/ir/code/JumpInstruction.java
index 9536919..9f4a26f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/JumpInstruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/JumpInstruction.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import java.util.List;
@@ -32,8 +33,8 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return false;
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
+    return DeadInstructionResult.notDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/MoveException.java b/src/main/java/com/android/tools/r8/ir/code/MoveException.java
index 4c87b70..dd74687 100644
--- a/src/main/java/com/android/tools/r8/ir/code/MoveException.java
+++ b/src/main/java/com/android/tools/r8/ir/code/MoveException.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.utils.InternalOptions;
@@ -80,10 +81,14 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return !(appView.options().debug
-            || code.method().getOptimizationInfo().isReachabilitySensitive())
-        && appView.options().isGeneratingDex();
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
+    InternalOptions options = appView.options();
+    if (options.debug
+        || code.context().getDefinition().getOptimizationInfo().isReachabilitySensitive()
+        || options.isGeneratingClassFiles()) {
+      return DeadInstructionResult.notDead();
+    }
+    return DeadInstructionResult.deadIfOutValueIsDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java b/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
index c730efc..eb12b5a 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
@@ -15,6 +15,7 @@
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 
@@ -82,13 +83,16 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
     if (instructionInstanceCanThrow()) {
-      return false;
+      return DeadInstructionResult.notDead();
     }
     // This would belong better in instructionInstanceCanThrow, but that is not passed an appInfo.
     DexType baseType = type.toBaseType(appView.dexItemFactory());
-    return baseType.isPrimitiveType() || appView.definitionFor(baseType) != null;
+    if (baseType.isPrimitiveType() || appView.definitionFor(baseType) != null) {
+      return DeadInstructionResult.deadIfOutValueIsDead();
+    }
+    return DeadInstructionResult.notDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java b/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java
index 54d1ad4..bc75936 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java
@@ -138,9 +138,4 @@
   public boolean instructionMayTriggerMethodInvocation(AppView<?> appView, ProgramMethod context) {
     return false;
   }
-
-  @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return !instructionMayHaveSideEffects(appView, code.context());
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewInstance.java b/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
index c1b2bd7..81af63c 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
@@ -198,11 +198,6 @@
     return false;
   }
 
-  @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return !instructionMayHaveSideEffects(appView, code.context());
-  }
-
   public void markNoSpilling() {
     allowSpilling = false;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Pop.java b/src/main/java/com/android/tools/r8/ir/code/Pop.java
index 0124c45..9ec7256 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Pop.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Pop.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 
@@ -91,9 +92,9 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
     // Pop cannot be dead code as it modifies the stack height.
-    return false;
+    return DeadInstructionResult.notDead();
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/StaticGet.java b/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
index 4dc7c12..2a5ffbd 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
@@ -149,16 +149,6 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    // static-get can be dead as long as it cannot have any of the following:
-    // * NoSuchFieldError (resolution failure)
-    // * IncompatibleClassChangeError (static-* instruction for instance fields)
-    // * IllegalAccessError (not visible from the access context)
-    // * side-effects in <clinit>
-    return !instructionMayHaveSideEffects(appView, code.context());
-  }
-
-  @Override
   public int maxInValueRegister() {
     return Constants.U8BIT_MAX;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/StaticPut.java b/src/main/java/com/android/tools/r8/ir/code/StaticPut.java
index 36b6520..e268cbe 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StaticPut.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StaticPut.java
@@ -138,20 +138,6 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    // static-put can be dead as long as it cannot have any of the following:
-    // * NoSuchFieldError (resolution failure)
-    // * IncompatibleClassChangeError (static-* instruction for instance fields)
-    // * IllegalAccessError (not visible from the access context)
-    // * side-effects in <clinit>
-    // * not read _globally_
-    boolean haveSideEffects = instructionMayHaveSideEffects(appView, code.context());
-    assert appView.enableWholeProgramOptimizations() || haveSideEffects
-        : "Expected static-put instruction to have side effects in D8";
-    return !haveSideEffects;
-  }
-
-  @Override
   public int maxInValueRegister() {
     return Constants.U8BIT_MAX;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Store.java b/src/main/java/com/android/tools/r8/ir/code/Store.java
index ccd57ea..8100111 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Store.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Store.java
@@ -15,6 +15,7 @@
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 
@@ -100,8 +101,11 @@
   }
 
   @Override
-  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
-    return !(outValue instanceof FixedLocalValue);
+  public DeadInstructionResult canBeDeadCode(AppView<?> appView, IRCode code) {
+    if (outValue instanceof FixedLocalValue) {
+      return DeadInstructionResult.notDead();
+    }
+    return DeadInstructionResult.deadIfOutValueIsDead();
   }
 
   @Override
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 53af0fc..82b3919 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
@@ -25,6 +25,7 @@
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.ir.analysis.value.AbstractValue;
 import com.android.tools.r8.ir.analysis.value.UnknownValue;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.ir.regalloc.LiveIntervals;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.position.MethodPosition;
@@ -1093,9 +1094,18 @@
       if (ignoreUser.test(instruction)) {
         continue;
       }
-      if (!instruction.canBeDeadCode(appView, code)) {
+      DeadInstructionResult result = instruction.canBeDeadCode(appView, code);
+      if (result.isNotDead()) {
         return false;
       }
+      if (result.isMaybeDead()) {
+        for (Value valueRequiredToBeDead : result.getValuesRequiredToBeDead()) {
+          if (!active.contains(valueRequiredToBeDead)
+              && !valueRequiredToBeDead.isDead(appView, code, ignoreUser, active)) {
+            return false;
+          }
+        }
+      }
       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 ef9c66c..71684b1 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
@@ -5,6 +5,7 @@
 
 import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
 
+import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
@@ -19,6 +20,7 @@
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.Timing;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterators;
 import java.util.ArrayDeque;
 import java.util.Collection;
 import java.util.Deque;
@@ -68,7 +70,7 @@
             || !instruction.hasOutValue()
             || instruction.outValue().hasAnyUsers();
         // No dead instructions.
-        assert !instruction.canBeDeadCode(appView, code)
+        assert !instruction.canBeDeadCode(appView, code).isDeadIfOutValueIsDead()
             || (instruction.hasOutValue() && !instruction.outValue().isDead(appView, code));
       }
     }
@@ -117,14 +119,25 @@
     while (iterator.hasPrevious()) {
       Instruction current = iterator.previous();
       // Remove unused invoke results.
-      if (current.isInvoke()
-          && current.outValue() != null
-          && !current.outValue().isUsed()) {
+      if (current.isInvoke() && current.hasOutValue() && !current.outValue().isUsed()) {
         current.setOutValue(null);
       }
-      if (!current.canBeDeadCode(appView, code)) {
+      DeadInstructionResult deadInstructionResult = current.canBeDeadCode(appView, code);
+      if (deadInstructionResult.isNotDead()) {
         continue;
       }
+      if (deadInstructionResult.isMaybeDead()) {
+        boolean satisfied = true;
+        for (Value valueRequiredToBeDead : deadInstructionResult.getValuesRequiredToBeDead()) {
+          if (!valueRequiredToBeDead.isDead(appView, code)) {
+            satisfied = false;
+            break;
+          }
+        }
+        if (!satisfied) {
+          continue;
+        }
+      }
       Value outValue = current.outValue();
       if (outValue != null && !outValue.isDead(appView, code)) {
         continue;
@@ -207,4 +220,61 @@
     }
     return builder.build();
   }
+
+  public abstract static class DeadInstructionResult {
+
+    private static final DeadInstructionResult DEFINITELY_DEAD_INSTANCE =
+        new DeadInstructionResult() {
+          @Override
+          public boolean isDeadIfOutValueIsDead() {
+            return true;
+          }
+        };
+
+    private static final DeadInstructionResult DEFINITELY_NOT_DEAD_INSTANCE =
+        new DeadInstructionResult() {
+          @Override
+          public boolean isNotDead() {
+            return true;
+          }
+        };
+
+    public static DeadInstructionResult deadIfOutValueIsDead() {
+      return DEFINITELY_DEAD_INSTANCE;
+    }
+
+    public static DeadInstructionResult notDead() {
+      return DEFINITELY_NOT_DEAD_INSTANCE;
+    }
+
+    public static DeadInstructionResult deadIfInValueIsDead(Value inValueRequiredToBeDead) {
+      return new DeadInstructionResult() {
+        @Override
+        public boolean isMaybeDead() {
+          return true;
+        }
+
+        @Override
+        public Iterable<Value> getValuesRequiredToBeDead() {
+          return () -> Iterators.singletonIterator(inValueRequiredToBeDead);
+        }
+      };
+    }
+
+    public boolean isDeadIfOutValueIsDead() {
+      return false;
+    }
+
+    public boolean isNotDead() {
+      return false;
+    }
+
+    public boolean isMaybeDead() {
+      return false;
+    }
+
+    public Iterable<Value> getValuesRequiredToBeDead() {
+      throw new Unreachable();
+    }
+  }
 }
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..e64fedd
--- /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)
+        .assertSuccessWithEmptyOutput();
+  }
+
+  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;
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/dynamictype/DynamicTypeOptimizationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/dynamictype/DynamicTypeOptimizationTest.java
index 4cab645..f9dbf89 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/dynamictype/DynamicTypeOptimizationTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/dynamictype/DynamicTypeOptimizationTest.java
@@ -170,6 +170,7 @@
 
   static class A implements I {
 
+    @NeverInline
     @Override
     public void hello() {
       System.out.print("Hello");