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 0ef2bb6..831c65f 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
@@ -3,18 +3,23 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import static com.android.tools.r8.optimize.MemberRebindingAnalysis.isClassTypeVisibleFromContext;
+
 import com.android.tools.r8.cf.LoadStoreHelper;
 import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.cf.code.CfMultiANewArray;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.AbstractError;
 import com.android.tools.r8.ir.analysis.type.Nullability;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
+import com.android.tools.r8.utils.LongInterval;
 import java.util.List;
 
 public class InvokeMultiNewArray extends Invoke {
@@ -108,6 +113,80 @@
   }
 
   @Override
+  public AbstractError instructionInstanceCanThrow(AppView<?> appView, DexType context) {
+    DexType baseType = type.isArrayType() ? type.toBaseType(appView.dexItemFactory()) : type;
+    if (baseType.isPrimitiveType()) {
+      // Primitives types are known to be present and accessible.
+      assert !type.isWideType() : "The array's contents must be single-word";
+      return instructionInstanceCanThrowNegativeArraySizeException();
+    }
+
+    assert baseType.isReferenceType();
+
+    if (baseType == context) {
+      // The enclosing type is known to be present and accessible.
+      return instructionInstanceCanThrowNegativeArraySizeException();
+    }
+
+    if (!appView.enableWholeProgramOptimizations()) {
+      // Conservatively bail-out in D8, because we require whole program knowledge to determine if
+      // the type is present and accessible.
+      return AbstractError.top();
+    }
+
+    // Check if the type is guaranteed to be present.
+    DexClass clazz = appView.definitionFor(baseType);
+    if (clazz == null) {
+      return AbstractError.top();
+    }
+
+    if (clazz.isLibraryClass()
+        && !appView.dexItemFactory().libraryTypesAssumedToBePresent.contains(baseType)) {
+      return AbstractError.top();
+    }
+
+    // Check if the type is guaranteed to be accessible.
+    if (!isClassTypeVisibleFromContext(appView, context, clazz)) {
+      return AbstractError.top();
+    }
+
+    // The type is known to be present and accessible.
+    return instructionInstanceCanThrowNegativeArraySizeException();
+  }
+
+  private AbstractError instructionInstanceCanThrowNegativeArraySizeException() {
+    boolean mayHaveNegativeArraySize = false;
+    for (Value value : arguments()) {
+      if (!value.hasValueRange()) {
+        mayHaveNegativeArraySize = true;
+        break;
+      }
+      LongInterval valueRange = value.getValueRange();
+      if (valueRange.getMin() < 0) {
+        mayHaveNegativeArraySize = true;
+        break;
+      }
+    }
+    return mayHaveNegativeArraySize ? AbstractError.top() : AbstractError.bottom();
+  }
+
+  @Override
+  public boolean instructionMayHaveSideEffects(AppView<?> appView, DexType context) {
+    // Check if the instruction has a side effect on the locals environment.
+    if (hasOutValue() && outValue().hasLocalInfo()) {
+      assert appView.options().debug;
+      return true;
+    }
+
+    return instructionInstanceCanThrow(appView, context).isThrowing();
+  }
+
+  @Override
+  public boolean canBeDeadCode(AppView<?> appView, IRCode code) {
+    return !instructionMayHaveSideEffects(appView, code.method.method.holder);
+  }
+
+  @Override
   public boolean instructionMayTriggerMethodInvocation(AppView<?> appView, DexType context) {
     return false;
   }
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/sideeffect/InvokeMultiNewArraySideEffectTest.java b/src/test/java/com/android/tools/r8/ir/analysis/sideeffect/InvokeMultiNewArraySideEffectTest.java
new file mode 100644
index 0000000..487d60a
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/analysis/sideeffect/InvokeMultiNewArraySideEffectTest.java
@@ -0,0 +1,72 @@
+// 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.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 static org.hamcrest.core.StringContains.containsString;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+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 InvokeMultiNewArraySideEffectTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimes().build();
+  }
+
+  public InvokeMultiNewArraySideEffectTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(InvokeMultiNewArraySideEffectTest.class)
+        .addKeepMainRule(TestClass.class)
+        .setMinApi(parameters.getRuntime())
+        .compile()
+        .inspect(
+            inspector -> {
+              ClassSubject aClassSubject = inspector.clazz(A.class);
+              if (parameters.isCfRuntime()) {
+                assertThat(aClassSubject, not(isPresent()));
+              } else {
+                // TODO(b/138779026): If we allow InvokeMultiNewArray instructions in the IR when
+                //  compiling to DEX, A would become dead.
+                assertThat(aClassSubject, isPresent());
+              }
+
+              ClassSubject bClassSubject = inspector.clazz(B.class);
+              assertThat(bClassSubject, isPresent());
+            })
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertFailureWithErrorThatMatches(
+            containsString(NegativeArraySizeException.class.getSimpleName()));
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      A[][] a = new A[42][42];
+      B[][] b = new B[42][-1];
+    }
+  }
+
+  static class A {}
+
+  static class B {}
+}