diff --git a/src/main/java/com/android/tools/r8/ir/analysis/equivalence/BasicBlockBehavioralSubsumption.java b/src/main/java/com/android/tools/r8/ir/analysis/equivalence/BasicBlockBehavioralSubsumption.java
index e4235e6..a186d7c 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/equivalence/BasicBlockBehavioralSubsumption.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/equivalence/BasicBlockBehavioralSubsumption.java
@@ -14,11 +14,13 @@
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.ConstString;
 import com.android.tools.r8.ir.code.DexItemBasedConstString;
+import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionIterator;
 import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.Return;
 import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.optimize.DeadCodeRemover.DeadInstructionResult;
 import com.android.tools.r8.utils.SetUtils;
 import java.util.List;
 import java.util.Set;
@@ -33,11 +35,13 @@
 public class BasicBlockBehavioralSubsumption {
 
   private final AppView<?> appView;
+  private final IRCode code;
   private final ProgramMethod context;
 
-  public BasicBlockBehavioralSubsumption(AppView<?> appView, ProgramMethod context) {
+  public BasicBlockBehavioralSubsumption(AppView<?> appView, IRCode code) {
     this.appView = appView;
-    this.context = context;
+    this.code = code;
+    this.context = code.context();
   }
 
   public boolean isSubsumedBy(BasicBlock block, BasicBlock other) {
@@ -148,7 +152,14 @@
   }
 
   private boolean isBlockLocalInstructionWithoutSideEffects(Instruction instruction) {
-    return definesBlockLocalValue(instruction) && !instructionMayHaveSideEffects(instruction);
+    if (!definesBlockLocalValue(instruction)) {
+      return false;
+    }
+    DeadInstructionResult deadInstructionResult = instruction.canBeDeadCode(appView, code);
+    if (!deadInstructionResult.isMaybeDead() || deadInstructionResult.isDeadIfInValueIsDead()) {
+      return false;
+    }
+    return true;
   }
 
   private boolean definesBlockLocalValue(Instruction instruction) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index 70efbeb..4c61a1c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -1129,10 +1129,9 @@
     BasicBlock defaultTarget = theSwitch.fallthroughBlock();
     SwitchCaseEliminator eliminator = null;
     BasicBlockBehavioralSubsumption behavioralSubsumption =
-        new BasicBlockBehavioralSubsumption(appView, code.context());
+        new BasicBlockBehavioralSubsumption(appView, code);
 
     // Compute the set of switch cases that can be removed.
-    int alwaysHitCase = -1;
     for (int i = 0; i < theSwitch.numberOfKeys(); i++) {
       BasicBlock targetBlock = theSwitch.targetBlock(i);
 
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 71684b1..26aa681 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
@@ -255,12 +255,21 @@
         }
 
         @Override
+        public boolean isDeadIfInValueIsDead() {
+          return true;
+        }
+
+        @Override
         public Iterable<Value> getValuesRequiredToBeDead() {
           return () -> Iterators.singletonIterator(inValueRequiredToBeDead);
         }
       };
     }
 
+    public boolean isDeadIfInValueIsDead() {
+      return false;
+    }
+
     public boolean isDeadIfOutValueIsDead() {
       return false;
     }
diff --git a/src/test/java/com/android/tools/r8/TestCompilerBuilder.java b/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
index 4149659..37f8a22 100644
--- a/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
+++ b/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
@@ -126,6 +126,15 @@
                             dexItemFactory, horizontallyMergedClasses))));
   }
 
+  public T addHorizontallyMergedClassesInspectorIf(
+      boolean condition, Consumer<HorizontallyMergedClassesInspector> inspector) {
+
+    if (condition) {
+      return addHorizontallyMergedClassesInspector(inspector);
+    }
+    return self();
+  }
+
   public T addHorizontallyMergedLambdaClassesInspector(
       Consumer<HorizontallyMergedLambdaClassesInspector> inspector) {
     return addOptionsModification(
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/CompanionClassMergingTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/CompanionClassMergingTest.java
new file mode 100644
index 0000000..b14763f
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/CompanionClassMergingTest.java
@@ -0,0 +1,115 @@
+// 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.classmerging.horizontal;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static com.android.tools.r8.utils.codeinspector.Matchers.notIf;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.classmerging.horizontal.EmptyClassTest.A;
+import com.android.tools.r8.classmerging.horizontal.EmptyClassTest.B;
+import com.android.tools.r8.classmerging.horizontal.EmptyClassTest.Main;
+import org.junit.Test;
+
+public class CompanionClassMergingTest extends HorizontalClassMergingTestBase {
+  public CompanionClassMergingTest(
+      TestParameters parameters, boolean enableHorizontalClassMerging) {
+    super(parameters, enableHorizontalClassMerging);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .addOptionsModification(
+            options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
+        .addOptionsModification(options -> options.enableClassInlining = false)
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .addHorizontallyMergedClassesInspectorIf(
+            enableHorizontalClassMerging,
+            inspector -> inspector.assertMergedInto(B.Companion.class, A.Companion.class))
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("foo a 0", "foo b 1")
+        .inspect(
+            codeInspector -> {
+              assertThat(codeInspector.clazz(A.class), isPresent());
+              assertThat(codeInspector.clazz(B.class), isPresent());
+
+              assertThat(codeInspector.clazz(A.Companion.class), isPresent());
+              assertThat(
+                  codeInspector.clazz(B.Companion.class),
+                  notIf(isPresent(), enableHorizontalClassMerging));
+            });
+  }
+
+  @NeverClassInline
+  public static class A {
+    public static final Companion companion = new Companion(null);
+    public static String foo;
+
+    static {
+      foo = "foo a " + Main.next();
+    }
+
+    public static String access$getFoo$cp() {
+      return foo;
+    }
+
+    public static class Companion {
+      public Companion() {}
+
+      public Companion(Object obj) {
+        this();
+      }
+
+      public String getFoo() {
+        return access$getFoo$cp();
+      }
+    }
+  }
+
+  @NeverClassInline
+  public static class B {
+    public static final Companion companion = new Companion(null);
+    public static String foo;
+
+    static {
+      foo = "foo b " + Main.next();
+    }
+
+    public static String access$getFoo$cp() {
+      return foo;
+    }
+
+    public static class Companion {
+      public Companion() {}
+
+      public Companion(Object obj) {
+        this();
+      }
+
+      public String getFoo() {
+        return access$getFoo$cp();
+      }
+    }
+  }
+
+  public static class Main {
+    static int COUNT = 0;
+
+    public static int next() {
+      return COUNT++;
+    }
+
+    public static void main(String[] args) {
+      System.out.println(A.companion.getFoo());
+      System.out.println(B.companion.getFoo());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/EmptyClassTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/EmptyClassTest.java
index ffdae33..4cdca16 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/EmptyClassTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/EmptyClassTest.java
@@ -5,11 +5,13 @@
 package com.android.tools.r8.classmerging.horizontal;
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static com.android.tools.r8.utils.codeinspector.Matchers.notIf;
 import static org.hamcrest.MatcherAssert.assertThat;
-import static org.hamcrest.core.IsNot.not;
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.classmerging.horizontal.CompanionClassMergingTest.A;
+import com.android.tools.r8.classmerging.horizontal.CompanionClassMergingTest.B;
 import org.junit.Test;
 
 public class EmptyClassTest extends HorizontalClassMergingTestBase {
@@ -26,36 +28,36 @@
             options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
         .enableNeverClassInliningAnnotations()
         .setMinApi(parameters.getApiLevel())
+        .addHorizontallyMergedClassesInspectorIf(
+            enableHorizontalClassMerging, inspector -> inspector.assertMergedInto(B.class, A.class))
         .run(parameters.getRuntime(), Main.class)
-        .assertSuccess()
+        .assertSuccessWithOutputLines("a", "b: foo")
         .inspect(
             codeInspector -> {
-              if (enableHorizontalClassMerging) {
-                assertThat(codeInspector.clazz(A.class), isPresent());
-                assertThat(codeInspector.clazz(B.class), not(isPresent()));
-                // TODO(b/165517236): Explicitly check classes have been merged.
-              } else {
-                assertThat(codeInspector.clazz(A.class), isPresent());
-                assertThat(codeInspector.clazz(B.class), isPresent());
-              }
+              assertThat(codeInspector.clazz(A.class), isPresent());
+              assertThat(
+                  codeInspector.clazz(B.class), notIf(isPresent(), enableHorizontalClassMerging));
             });
   }
 
   @NeverClassInline
-  public static class A {}
+  public static class A {
+    public A() {
+      System.out.println("a");
+    }
+  }
 
   @NeverClassInline
   public static class B {
-    // TODO(b/164924717): remove non overlapping constructor requirement
-    public B(String s) {}
+    public B(String s) {
+      System.out.println("b: " + s);
+    }
   }
 
   public static class Main {
     public static void main(String[] args) {
       A a = new A();
-      System.out.println(a);
-      B b = new B("");
-      System.out.println(b);
+      B b = new B("foo");
     }
   }
 }
diff --git a/src/test/java/com/android/tools/r8/kotlin/KotlinClassStaticizerTest.java b/src/test/java/com/android/tools/r8/kotlin/KotlinClassStaticizerTest.java
index 179333f..2cbef3e 100644
--- a/src/test/java/com/android/tools/r8/kotlin/KotlinClassStaticizerTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/KotlinClassStaticizerTest.java
@@ -36,7 +36,6 @@
 
   @Test
   public void testCompanionAndRegularObjects() throws Exception {
-    expectThrowsWithHorizontalClassMerging();
     assumeTrue("Only work with -allowaccessmodification", allowAccessModification);
     final String mainClassName = "class_staticizer.MainKt";
 
@@ -47,7 +46,6 @@
         false,
         app -> {
           CodeInspector inspector = new CodeInspector(app);
-          assertThat(inspector.clazz("class_staticizer.Regular$Companion"), isPresent());
           assertThat(inspector.clazz("class_staticizer.Derived$Companion"), isPresent());
 
           // The Util class is there, but its instance methods have been inlined.
@@ -67,7 +65,6 @@
         app -> {
           CodeInspector inspector = new CodeInspector(app);
           assertThat(inspector.clazz("class_staticizer.Regular$Companion"), not(isPresent()));
-          assertThat(inspector.clazz("class_staticizer.Derived$Companion"), not(isPresent()));
 
           ClassSubject utilClass = inspector.clazz("class_staticizer.Util");
           assertThat(utilClass, isPresent());
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/HorizontallyMergedClassesInspector.java b/src/test/java/com/android/tools/r8/utils/codeinspector/HorizontallyMergedClassesInspector.java
index 1eca176..a440523 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/HorizontallyMergedClassesInspector.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/HorizontallyMergedClassesInspector.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.utils.codeinspector;
 
 import static com.android.tools.r8.TestBase.toDexType;
+import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 
@@ -22,6 +23,13 @@
     this.horizontallyMergedClasses = horizontallyMergedClasses;
   }
 
+  public HorizontallyMergedClassesInspector assertMergedInto(Class<?> from, Class<?> target) {
+    assertEquals(
+        horizontallyMergedClasses.getMergeTargetOrDefault(toDexType(from, dexItemFactory)),
+        toDexType(target, dexItemFactory));
+    return this;
+  }
+
   public HorizontallyMergedClassesInspector assertNoClassesMerged() {
     assertTrue(horizontallyMergedClasses.getSources().isEmpty());
     return this;