diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index 51ed473..e71310b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
@@ -15,6 +15,7 @@
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.utils.CfgPrinter;
+import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.StringUtils.BraceType;
@@ -1170,10 +1171,15 @@
     return block;
   }
 
-  public static BasicBlock createRethrowBlock(IRCode code, Position position) {
+
+
+  public static BasicBlock createRethrowBlock(
+      IRCode code, Position position, DexType guard, InternalOptions options) {
     BasicBlock block = new BasicBlock();
-    MoveException moveException =
-        new MoveException(new Value(code.valueNumberGenerator.next(), ValueType.OBJECT, null));
+    MoveException moveException = new MoveException(
+        new Value(code.valueNumberGenerator.next(), ValueType.OBJECT, null),
+        guard,
+        options);
     moveException.setPosition(position);
     Throw throwInstruction = new Throw(moveException.outValue);
     throwInstruction.setPosition(position);
@@ -1182,6 +1188,7 @@
     block.close(null);
     block.setNumber(code.getHighestBlockNumber() + 1);
     return block;
+
   }
 
   public boolean isTrivialGoto() {
@@ -1391,7 +1398,10 @@
    * Clone catch successors from `fromBlock` into this block.
    */
   public void copyCatchHandlers(
-      IRCode code, ListIterator<BasicBlock> blockIterator, BasicBlock fromBlock) {
+      IRCode code,
+      ListIterator<BasicBlock> blockIterator,
+      BasicBlock fromBlock,
+      InternalOptions options) {
     if (catchHandlers != null && catchHandlers.hasCatchAll()) {
       return;
     }
@@ -1411,7 +1421,8 @@
       catchSuccessor.splitCriticalExceptionEdges(
           code.getHighestBlockNumber() + 1,
           code.valueNumberGenerator,
-          blockIterator::add);
+          blockIterator::add,
+          options);
     }
   }
 
@@ -1431,14 +1442,17 @@
   public int splitCriticalExceptionEdges(
       int nextBlockNumber,
       ValueNumberGenerator valueNumberGenerator,
-      Consumer<BasicBlock> onNewBlock) {
-    List<BasicBlock> predecessors = this.getPredecessors();
+      Consumer<BasicBlock> onNewBlock,
+      InternalOptions options) {
+    List<BasicBlock> predecessors = getPredecessors();
     boolean hasMoveException = entry().isMoveException();
+    DexType exceptionType = null;
     MoveException move = null;
     Position position = entry().getPosition();
     if (hasMoveException) {
       // Remove the move-exception instruction.
       move = entry().asMoveException();
+      exceptionType = move.getExceptionType();
       assert move.getDebugValues().isEmpty();
       getInstructions().remove(0);
     }
@@ -1456,7 +1470,7 @@
       if (hasMoveException) {
         Value value = new Value(valueNumberGenerator.next(), ValueType.OBJECT, move.getLocalInfo());
         values.add(value);
-        MoveException newMove = new MoveException(value);
+        MoveException newMove = new MoveException(value, exceptionType, options);
         newBlock.add(newMove);
         newMove.setPosition(position);
       }
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
index 08d7a07..1dbf098 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
@@ -280,7 +280,7 @@
         } else {
           nextBlock = null;
         }
-        currentBlock.copyCatchHandlers(code, blocksIterator, invokeBlock);
+        currentBlock.copyCatchHandlers(code, blocksIterator, invokeBlock, code.options);
         if (nextBlock != null) {
           BasicBlock b = blocksIterator.next();
           assert b == nextBlock;
@@ -316,7 +316,7 @@
       if (inlinedBlock.hasCatchHandlers()) {
         // The block already has catch handlers, so it has only one throwing instruction, and no
         // splitting is required.
-        inlinedBlock.copyCatchHandlers(code, blocksIterator, invokeBlock);
+        inlinedBlock.copyCatchHandlers(code, blocksIterator, invokeBlock, code.options);
       } else {
         // The block does not have catch handlers, so it can have several throwing instructions.
         // Therefore the block must be split after each throwing instruction, and the catch
diff --git a/src/main/java/com/android/tools/r8/ir/code/CatchHandlers.java b/src/main/java/com/android/tools/r8/ir/code/CatchHandlers.java
index 99ce3cc..c203c0a 100644
--- a/src/main/java/com/android/tools/r8/ir/code/CatchHandlers.java
+++ b/src/main/java/com/android/tools/r8/ir/code/CatchHandlers.java
@@ -9,6 +9,7 @@
 import com.google.common.collect.ImmutableSet;
 import java.util.List;
 import java.util.Set;
+import java.util.function.BiConsumer;
 
 public class CatchHandlers<T> {
 
@@ -61,6 +62,12 @@
         getGuards().get(getGuards().size() - 1) == DexItemFactory.catchAllType;
   }
 
+  public void forEach(BiConsumer<DexType, T> consumer) {
+    for (int i = 0; i < size(); ++i) {
+      consumer.accept(guards.get(i), targets.get(i));
+    }
+  }
+
   @Override
   public boolean equals(Object o) {
     if (this == o) {
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 c92ac50..9781f13 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
@@ -7,7 +7,6 @@
 import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfo;
-import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
@@ -15,14 +14,15 @@
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.utils.InternalOptions;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Set;
 
 public class MoveException extends Instruction {
+  private final DexType exceptionType;
+  private final InternalOptions options;
 
-  public MoveException(Value dest) {
+  public MoveException(Value dest, DexType exceptionType, InternalOptions options) {
     super(dest);
+    this.exceptionType = exceptionType;
+    this.options = options;
     dest.markNeverNull();
   }
 
@@ -49,7 +49,13 @@
 
   @Override
   public boolean identicalNonValueNonPositionParts(Instruction other) {
-    return other.isMoveException();
+    if (!other.isMoveException()) {
+      return false;
+    }
+    if (options.canHaveExceptionTypeBug()) {
+      return other.asMoveException().exceptionType == exceptionType;
+    }
+    return true;
   }
 
   @Override
@@ -94,35 +100,17 @@
     return true;
   }
 
-  private Set<DexType> collectExceptionTypes(DexItemFactory dexItemFactory) {
-    Set<DexType> exceptionTypes = new HashSet<>(getBlock().getPredecessors().size());
-    for (BasicBlock block : getBlock().getPredecessors()) {
-      int size = block.getCatchHandlers().size();
-      List<BasicBlock> targets = block.getCatchHandlers().getAllTargets();
-      List<DexType> guards = block.getCatchHandlers().getGuards();
-      for (int i = 0; i < size; i++) {
-        if (targets.get(i) == getBlock()) {
-          DexType guard = guards.get(i);
-          exceptionTypes.add(
-              guard == dexItemFactory.catchAllType
-                  ? dexItemFactory.throwableType
-                  : guard);
-        }
-      }
-    }
-    return exceptionTypes;
-  }
-
   @Override
   public DexType computeVerificationType(TypeVerificationHelper helper) {
-    return helper.join(collectExceptionTypes(helper.getFactory()));
+    return exceptionType;
   }
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    Set<DexType> exceptionTypes = collectExceptionTypes(appInfo.dexItemFactory);
-    return TypeLatticeElement.join(
-        appInfo,
-        exceptionTypes.stream().map(t -> TypeLatticeElement.fromDexType(appInfo, t, false)));
+    return TypeLatticeElement.fromDexType(appInfo, exceptionType, false);
+  }
+
+  public DexType getExceptionType() {
+    return exceptionType;
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
index d855e0e..93aa151 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
@@ -88,6 +88,7 @@
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.Pair;
+import com.google.common.collect.Sets;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
@@ -103,7 +104,6 @@
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
-import java.util.IdentityHashMap;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
@@ -140,11 +140,14 @@
   }
 
   private static class MoveExceptionWorklistItem extends WorklistItem {
+    private final DexType guard;
     private final int sourceOffset;
     private final int targetOffset;
 
-    private MoveExceptionWorklistItem(BasicBlock block, int sourceOffset, int targetOffset) {
+    private MoveExceptionWorklistItem(
+        BasicBlock block, DexType guard, int sourceOffset, int targetOffset) {
       super(block, -1);
+      this.guard = guard;
       this.sourceOffset = sourceOffset;
       this.targetOffset = targetOffset;
     }
@@ -597,12 +600,9 @@
     // construction and prior to building the IR.
     for (BlockInfo info : targets.values()) {
       if (info != null && info.block == block) {
-        assert info.predecessorCount() == block.getPredecessors().size();
+        assert info.predecessorCount() == nonSplitPredecessorCount(block);
         assert info.normalSuccessors.size() == block.getNormalSuccessors().size();
-        if (block.hasCatchHandlers()) {
-          assert info.exceptionalSuccessors.size()
-              == block.getCatchHandlers().getUniqueTargets().size();
-        } else {
+        if (!block.hasCatchHandlers()) {
           assert !block.canThrow()
               || info.exceptionalSuccessors.isEmpty()
               || (info.exceptionalSuccessors.size() == 1
@@ -616,6 +616,38 @@
     return true;
   }
 
+  private int nonSplitPredecessorCount(BasicBlock block) {
+    Set<BasicBlock> set = Sets.newIdentityHashSet();
+    for (BasicBlock predecessor : block.getPredecessors()) {
+      if (offsets.containsKey(predecessor)) {
+        set.add(predecessor);
+      } else {
+        assert predecessor.getSuccessors().size() == 1;
+        assert predecessor.getPredecessors().size() == 1;
+        assert trivialGotoBlockPotentiallyWithMoveException(predecessor);
+        // Combine the exceptional edges to just one, for normal edges that have been split
+        // record them separately. That means that we are checking that there are the expected
+        // number of normal edges and some number of exceptional edges (which we count as one edge).
+        if (predecessor.getPredecessors().get(0).hasCatchSuccessor(predecessor)) {
+          set.add(predecessor.getPredecessors().get(0));
+        } else {
+          set.add(predecessor);
+        }
+      }
+    }
+    return set.size();
+  }
+
+  // Check that all instructions are either move-exception, goto or debug instructions.
+  private boolean trivialGotoBlockPotentiallyWithMoveException(BasicBlock block) {
+    for (Instruction instruction : block.getInstructions()) {
+      assert instruction.isMoveException()
+          || instruction.isGoto()
+          || instruction.isDebugInstruction();
+    }
+    return true;
+  }
+
   private void processWorklist() {
     for (WorklistItem item = ssaWorklist.poll(); item != null; item = ssaWorklist.poll()) {
       if (item.block.isFilled()) {
@@ -673,7 +705,7 @@
     Position position = source.getCanonicalDebugPositionAtOffset(moveExceptionItem.targetOffset);
     if (moveExceptionDest >= 0) {
       Value out = writeRegister(moveExceptionDest, ValueType.OBJECT, ThrowingInfo.NO_THROW, null);
-      MoveException moveException = new MoveException(out);
+      MoveException moveException = new MoveException(out, moveExceptionItem.guard, options);
       moveException.setPosition(position);
       currentBlock.add(moveException);
     }
@@ -1961,21 +1993,22 @@
         assert !throwingInstructionInCurrentBlock;
         throwingInstructionInCurrentBlock = true;
         List<BasicBlock> targets = new ArrayList<>(catchHandlers.getAllTargets().size());
-        // Construct unique move-exception header blocks for each unique target.
-        Map<BasicBlock, BasicBlock> moveExceptionHeaders =
-            new IdentityHashMap<>(catchHandlers.getUniqueTargets().size());
-        for (int targetOffset : catchHandlers.getAllTargets()) {
-          BasicBlock target = getTarget(targetOffset);
-          BasicBlock header = moveExceptionHeaders.get(target);
-          if (header == null) {
-            header = new BasicBlock();
-            header.incrementUnfilledPredecessorCount();
-            moveExceptionHeaders.put(target, header);
-            ssaWorklist.add(
-                new MoveExceptionWorklistItem(header, currentInstructionOffset, targetOffset));
-          }
+        Set<BasicBlock> moveExceptionTargets = Sets.newIdentityHashSet();
+        catchHandlers.forEach((type, targetOffset) -> {
+          DexType exceptionType = type == options.itemFactory.catchAllType
+              ? options.itemFactory.throwableType
+              : type;
+          BasicBlock header = new BasicBlock();
+          header.incrementUnfilledPredecessorCount();
+          ssaWorklist.add(
+              new MoveExceptionWorklistItem(
+                  header, exceptionType, currentInstructionOffset, targetOffset));
           targets.add(header);
-        }
+          BasicBlock target = getTarget(targetOffset);
+          if (!moveExceptionTargets.add(target)) {
+            target.incrementUnfilledPredecessorCount();
+          }
+        });
         currentBlock.linkCatchSuccessors(catchHandlers.getGuards(), targets);
       }
     }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
index c87c849..367d35d 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
@@ -325,6 +325,6 @@
     BasicBlock currentBlock = newInstance.getBlock();
     BasicBlock nextBlock = instructions.split(code, blocks);
     assert !instructions.hasNext();
-    nextBlock.copyCatchHandlers(code, blocks, currentBlock);
+    nextBlock.copyCatchHandlers(code, blocks, currentBlock, code.options);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/StringConcatRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/StringConcatRewriter.java
index 399ae92..e6ad575 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/StringConcatRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/StringConcatRewriter.java
@@ -383,7 +383,7 @@
       }
       // Copy catch handlers after all blocks are split.
       for (BasicBlock newBlock : newBlocks) {
-        newBlock.copyCatchHandlers(code, blocks, currentBlock);
+        newBlock.copyCatchHandlers(code, blocks, currentBlock, code.options);
       }
     }
 
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 809ef70..899e25d 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
@@ -289,8 +289,12 @@
       splitIterator.previous();
       BasicBlock newBlock = splitIterator.split(code, 1);
       // Generate rethrow block.
-      BasicBlock rethrowBlock =
-          BasicBlock.createRethrowBlock(code, lastSelfRecursiveCall.getPosition());
+      DexType guard = options.itemFactory.throwableType;
+      BasicBlock rethrowBlock = BasicBlock.createRethrowBlock(
+          code,
+          lastSelfRecursiveCall.getPosition(),
+          guard,
+          options);
       code.blocks.add(rethrowBlock);
       // Add catch handler to the block containing the last recursive call.
       newBlock.addCatchHandler(rethrowBlock, options.itemFactory.throwableType);
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index 9b7fbf4..ec157e9 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -806,4 +806,17 @@
     // Marshmallow and Nougat arm64 devices and they do not have the bug.
     return minApiLevel < AndroidApiLevel.M.getLevel();
   }
+
+  // The Art VM for Android N through P has a bug in the JIT that means that if the same
+  // exception block with a move-exception instruction is targeted with more than one type
+  // of exception the JIT will incorrectly assume that the exception object has one of these
+  // types and will optimize based on that one type instead of taking all the types into account.
+  //
+  // In order to workaround that, we always generate distinct move-exception instructions for
+  // distinct dex types.
+  //
+  // See b/120164595.
+  public boolean canHaveExceptionTypeBug() {
+    return minApiLevel < AndroidApiLevel.Q.getLevel();
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java b/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java
index 0cf2f53..9982c4d 100644
--- a/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java
+++ b/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java
@@ -196,7 +196,7 @@
 
   public void runCatchHandlerTest(boolean codeThrows, boolean twoGuards) throws Exception {
     final int secondBlockInstructions = 4;
-    final int initialBlockCount = 6;
+    final int initialBlockCount = twoGuards ? 7 : 6;
     // Try split between all instructions in second block.
     for (int i = 1; i < secondBlockInstructions; i++) {
       TestApplication test = codeWithCatchHandlers(codeThrows, twoGuards);
@@ -235,7 +235,7 @@
   public void runCatchHandlerSplitThreeTest(boolean codeThrows, boolean twoGuards)
       throws Exception {
     final int secondBlockInstructions = 4;
-    final int initialBlockCount = 6;
+    final int initialBlockCount = twoGuards ? 7 : 6;
     // Try split out all instructions in second block.
     for (int i = 1; i < secondBlockInstructions - 1; i++) {
       TestApplication test = codeWithCatchHandlers(codeThrows, twoGuards);
diff --git a/src/test/java/com/android/tools/r8/regress/b120164595/B120164595.java b/src/test/java/com/android/tools/r8/regress/b120164595/B120164595.java
new file mode 100644
index 0000000..69b3a96
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/regress/b120164595/B120164595.java
@@ -0,0 +1,81 @@
+// 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.regress.b120164595;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestCompileResult;
+import com.android.tools.r8.ToolHelper.DexVm;
+import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import java.io.IOException;
+import org.junit.Test;
+
+/**
+ * Regression test for art issue with multi catch-handlers.
+ * The problem is that if d8/r8 creates the same target address for two different exceptions,
+ * art will use that address to check if it was already handled.
+ */
+class TestClass {
+  public static void main(String[] args) {
+    for (int i = 0; i < 20000; i++) {
+      toBeOptimized();
+    }
+  }
+
+  private static void toBeOptimized() {
+    try {
+      willThrow();
+    } catch (IllegalStateException | NullPointerException e) {
+      if (e instanceof NullPointerException) {
+        return;
+      }
+      throw new Error("Expected NullPointerException");
+    }
+  }
+
+  private static void willThrow() {
+    throw new NullPointerException();
+  }
+}
+
+public class B120164595 extends TestBase {
+  @Test
+  public void testD8()
+      throws IOException, CompilationFailedException {
+    TestCompileResult d8Result = testForD8()
+        .setMinApi(AndroidApiLevel.N_MR1)
+        .addProgramClasses(TestClass.class)
+        .compile();
+    checkArt(d8Result);
+  }
+
+  @Test
+  public void testR8()
+      throws IOException, CompilationFailedException {
+    TestCompileResult r8Result = testForR8(Backend.DEX)
+        .setMinApi(AndroidApiLevel.N_MR1)
+        .addProgramClasses(TestClass.class)
+        .addKeepAllClassesRule()
+        .compile();
+    checkArt(r8Result);
+  }
+
+  private void checkArt(TestCompileResult result) throws IOException {
+    ProcessResult artResult = runOnArtRaw(
+        result.app,
+        TestClass.class.getCanonicalName(),
+        builder -> {
+          builder.appendArtOption("-Xusejit:true");
+        },
+        DexVm.ART_7_0_0_HOST
+    );
+    assertEquals(0, artResult.exitCode);
+    assertFalse(artResult.stderr.contains("Expected NullPointerException"));
+  }
+}