diff --git a/src/main/java/com/android/tools/r8/cf/CfConstants.java b/src/main/java/com/android/tools/r8/cf/CfConstants.java
deleted file mode 100644
index 06a2562..0000000
--- a/src/main/java/com/android/tools/r8/cf/CfConstants.java
+++ /dev/null
@@ -1,220 +0,0 @@
-// Copyright (c) 2017, 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.cf;
-
-import it.unimi.dsi.fastutil.ints.Int2ReferenceArrayMap;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
-import org.objectweb.asm.Opcodes;
-
-public abstract class CfConstants {
-
-  private static final Int2ReferenceMap<String> OPCODE_NAMES;
-  static {
-    OPCODE_NAMES = new Int2ReferenceArrayMap<>(Opcodes.IFNONNULL + 1);
-    OPCODE_NAMES.put(0, "nop");
-    OPCODE_NAMES.put(1, "aconst_null");
-    OPCODE_NAMES.put(2, "iconst_m1");
-    OPCODE_NAMES.put(3, "iconst_0");
-    OPCODE_NAMES.put(4, "iconst_1");
-    OPCODE_NAMES.put(5, "iconst_2");
-    OPCODE_NAMES.put(6, "iconst_3");
-    OPCODE_NAMES.put(7, "iconst_4");
-    OPCODE_NAMES.put(8, "iconst_5");
-    OPCODE_NAMES.put(9, "lconst_0");
-    OPCODE_NAMES.put(10, "lconst_1");
-    OPCODE_NAMES.put(11, "fconst_0");
-    OPCODE_NAMES.put(12, "fconst_1");
-    OPCODE_NAMES.put(13, "fconst_2");
-    OPCODE_NAMES.put(14, "dconst_0");
-    OPCODE_NAMES.put(15, "dconst_1");
-    OPCODE_NAMES.put(16, "bipush");
-    OPCODE_NAMES.put(17, "sipush");
-    OPCODE_NAMES.put(18, "ldc");
-    // LDC_W  = 19;
-    // LDC2_W = 20;
-    OPCODE_NAMES.put(21, "iload");
-    OPCODE_NAMES.put(22, "lload");
-    OPCODE_NAMES.put(23, "fload");
-    OPCODE_NAMES.put(24, "dload");
-    OPCODE_NAMES.put(25, "aload");
-    // ILOAD_0 = 26;
-    // ILOAD_1 = 27;
-    // ILOAD_2 = 28;
-    // ILOAD_3 = 29;
-    // LLOAD_0 = 30;
-    // LLOAD_1 = 31;
-    // LLOAD_2 = 32;
-    // LLOAD_3 = 33;
-    // FLOAD_0 = 34;
-    // FLOAD_1 = 35;
-    // FLOAD_2 = 36;
-    // FLOAD_3 = 37;
-    // DLOAD_0 = 38;
-    // DLOAD_1 = 39;
-    // DLOAD_2 = 40;
-    // DLOAD_3 = 41;
-    // ALOAD_0 = 42;
-    // ALOAD_1 = 43;
-    // ALOAD_2 = 44;
-    // ALOAD_3 = 45;
-    OPCODE_NAMES.put(46, "iaload");
-    OPCODE_NAMES.put(47, "laload");
-    OPCODE_NAMES.put(48, "faload");
-    OPCODE_NAMES.put(49, "daload");
-    OPCODE_NAMES.put(50, "aaload");
-    OPCODE_NAMES.put(51, "baload");
-    OPCODE_NAMES.put(52, "caload");
-    OPCODE_NAMES.put(53, "saload");
-    OPCODE_NAMES.put(54, "istore");
-    OPCODE_NAMES.put(55, "lstore");
-    OPCODE_NAMES.put(56, "fstore");
-    OPCODE_NAMES.put(57, "dstore");
-    OPCODE_NAMES.put(58, "astore");
-    // ISTORE_0 = 59;
-    // ISTORE_1 = 60;
-    // ISTORE_2 = 61;
-    // ISTORE_3 = 62;
-    // LSTORE_0 = 63;
-    // LSTORE_1 = 64;
-    // LSTORE_2 = 65;
-    // LSTORE_3 = 66;
-    // FSTORE_0 = 67;
-    // FSTORE_1 = 68;
-    // FSTORE_2 = 69;
-    // FSTORE_3 = 70;
-    // DSTORE_0 = 71;
-    // DSTORE_1 = 72;
-    // DSTORE_2 = 73;
-    // DSTORE_3 = 74;
-    // ASTORE_0 = 75;
-    // ASTORE_1 = 76;
-    // ASTORE_2 = 77;
-    // ASTORE_3 = 78;
-    OPCODE_NAMES.put(79, "iastore");
-    OPCODE_NAMES.put(80, "lastore");
-    OPCODE_NAMES.put(81, "fastore");
-    OPCODE_NAMES.put(82, "dastore");
-    OPCODE_NAMES.put(83, "aastore");
-    OPCODE_NAMES.put(84, "bastore");
-    OPCODE_NAMES.put(85, "castore");
-    OPCODE_NAMES.put(86, "sastore");
-    OPCODE_NAMES.put(87, "pop");
-    OPCODE_NAMES.put(88, "pop2");
-    OPCODE_NAMES.put(89, "dup");
-    OPCODE_NAMES.put(90, "dup_x1");
-    OPCODE_NAMES.put(91, "dup_x2");
-    OPCODE_NAMES.put(92, "dup2");
-    OPCODE_NAMES.put(93, "dup2_x1");
-    OPCODE_NAMES.put(94, "dup2_x2");
-    OPCODE_NAMES.put(95, "swap");
-    OPCODE_NAMES.put(96, "iadd");
-    OPCODE_NAMES.put(97, "ladd");
-    OPCODE_NAMES.put(98, "fadd");
-    OPCODE_NAMES.put(99, "dadd");
-    OPCODE_NAMES.put(100, "isub");
-    OPCODE_NAMES.put(101, "lsub");
-    OPCODE_NAMES.put(102, "fsub");
-    OPCODE_NAMES.put(103, "dsub");
-    OPCODE_NAMES.put(104, "imul");
-    OPCODE_NAMES.put(105, "lmul");
-    OPCODE_NAMES.put(106, "fmul");
-    OPCODE_NAMES.put(107, "dmul");
-    OPCODE_NAMES.put(108, "idiv");
-    OPCODE_NAMES.put(109, "ldiv");
-    OPCODE_NAMES.put(110, "fdiv");
-    OPCODE_NAMES.put(111, "ddiv");
-    OPCODE_NAMES.put(112, "irem");
-    OPCODE_NAMES.put(113, "lrem");
-    OPCODE_NAMES.put(114, "frem");
-    OPCODE_NAMES.put(115, "drem");
-    OPCODE_NAMES.put(116, "ineg");
-    OPCODE_NAMES.put(117, "lneg");
-    OPCODE_NAMES.put(118, "fneg");
-    OPCODE_NAMES.put(119, "dneg");
-    OPCODE_NAMES.put(120, "ishl");
-    OPCODE_NAMES.put(121, "lshl");
-    OPCODE_NAMES.put(122, "ishr");
-    OPCODE_NAMES.put(123, "lshr");
-    OPCODE_NAMES.put(124, "iushr");
-    OPCODE_NAMES.put(125, "lushr");
-    OPCODE_NAMES.put(126, "iand");
-    OPCODE_NAMES.put(127, "land");
-    OPCODE_NAMES.put(128, "ior");
-    OPCODE_NAMES.put(129, "lor");
-    OPCODE_NAMES.put(130, "ixor");
-    OPCODE_NAMES.put(131, "lxor");
-    OPCODE_NAMES.put(132, "iinc");
-    OPCODE_NAMES.put(133, "i2l");
-    OPCODE_NAMES.put(134, "i2f");
-    OPCODE_NAMES.put(135, "i2d");
-    OPCODE_NAMES.put(136, "l2i");
-    OPCODE_NAMES.put(137, "l2f");
-    OPCODE_NAMES.put(138, "l2d");
-    OPCODE_NAMES.put(139, "f2i");
-    OPCODE_NAMES.put(140, "f2l");
-    OPCODE_NAMES.put(141, "f2d");
-    OPCODE_NAMES.put(142, "d2i");
-    OPCODE_NAMES.put(143, "d2l");
-    OPCODE_NAMES.put(144, "d2f");
-    OPCODE_NAMES.put(145, "i2b");
-    OPCODE_NAMES.put(146, "i2c");
-    OPCODE_NAMES.put(147, "i2s");
-    OPCODE_NAMES.put(148, "lcmp");
-    OPCODE_NAMES.put(149, "fcmpl");
-    OPCODE_NAMES.put(150, "fcmpg");
-    OPCODE_NAMES.put(151, "dcmpl");
-    OPCODE_NAMES.put(152, "dcmpg");
-    OPCODE_NAMES.put(153, "ifeq");
-    OPCODE_NAMES.put(154, "ifne");
-    OPCODE_NAMES.put(155, "iflt");
-    OPCODE_NAMES.put(156, "ifge");
-    OPCODE_NAMES.put(157, "ifgt");
-    OPCODE_NAMES.put(158, "ifle");
-    OPCODE_NAMES.put(159, "if_icmpeq");
-    OPCODE_NAMES.put(160, "if_icmpne");
-    OPCODE_NAMES.put(161, "if_icmplt");
-    OPCODE_NAMES.put(162, "if_icmpge");
-    OPCODE_NAMES.put(163, "if_icmpgt");
-    OPCODE_NAMES.put(164, "if_icmple");
-    OPCODE_NAMES.put(165, "if_acmpeq");
-    OPCODE_NAMES.put(166, "if_acmpne");
-    OPCODE_NAMES.put(167, "goto");
-    OPCODE_NAMES.put(168, "jsr");
-    OPCODE_NAMES.put(169, "ret");
-    OPCODE_NAMES.put(170, "tableswitch");
-    OPCODE_NAMES.put(171, "lookupswitch");
-    OPCODE_NAMES.put(172, "ireturn");
-    OPCODE_NAMES.put(173, "lreturn");
-    OPCODE_NAMES.put(174, "freturn");
-    OPCODE_NAMES.put(175, "dreturn");
-    OPCODE_NAMES.put(176, "areturn");
-    OPCODE_NAMES.put(177, "return");
-    OPCODE_NAMES.put(178, "getstatic");
-    OPCODE_NAMES.put(179, "putstatic");
-    OPCODE_NAMES.put(180, "getfield");
-    OPCODE_NAMES.put(181, "putfield");
-    OPCODE_NAMES.put(182, "invokevirtual");
-    OPCODE_NAMES.put(183, "invokespecial");
-    OPCODE_NAMES.put(184, "invokestatic");
-    OPCODE_NAMES.put(185, "invokeinterface");
-    OPCODE_NAMES.put(186, "invokedynamic");
-    OPCODE_NAMES.put(187, "new");
-    OPCODE_NAMES.put(188, "newarray");
-    OPCODE_NAMES.put(189, "anewarray");
-    OPCODE_NAMES.put(190, "arraylength");
-    OPCODE_NAMES.put(191, "athrow");
-    OPCODE_NAMES.put(192, "checkcast");
-    OPCODE_NAMES.put(193, "instanceof");
-    OPCODE_NAMES.put(194, "monitorenter");
-    OPCODE_NAMES.put(195, "monitorexit");
-    // WIDE = 196
-    OPCODE_NAMES.put(197, "multianewarray");
-    OPCODE_NAMES.put(198, "ifnull");
-    OPCODE_NAMES.put(199, "ifnonnull");
-  }
-
-  public static String opcodeName(int opcode) {
-    return OPCODE_NAMES.get(opcode);
-  }
-}
diff --git a/src/main/java/com/android/tools/r8/cf/CfPrinter.java b/src/main/java/com/android/tools/r8/cf/CfPrinter.java
index da6b2f3..32f2f9f 100644
--- a/src/main/java/com/android/tools/r8/cf/CfPrinter.java
+++ b/src/main/java/com/android/tools/r8/cf/CfPrinter.java
@@ -39,6 +39,7 @@
 import java.util.HashMap;
 import java.util.Map;
 import org.objectweb.asm.Type;
+import org.objectweb.asm.util.Printer;
 
 /**
  * Utility to print CF code and instructions.
@@ -121,11 +122,11 @@
   }
 
   public void print(CfBinop binop) {
-    print(CfConstants.opcodeName(binop.getOpcode()));
+    print(opcodeName(binop.getOpcode()));
   }
 
   public void print(CfUnop unop) {
-    print(CfConstants.opcodeName(unop.getOpcode()));
+    print(opcodeName(unop.getOpcode()));
   }
 
   public void print(CfPop pop) {
@@ -149,7 +150,7 @@
 
   public void print(CfInvoke invoke) {
     indent();
-    builder.append(invoke.getOpcode()).append(' ');
+    builder.append(opcodeName(invoke.getOpcode())).append(' ');
     appendMethod(invoke.getMethod());
   }
 
@@ -336,6 +337,10 @@
     builder.append(method.proto.toDescriptorString());
   }
 
+  private String opcodeName(int opcode) {
+    return Printer.OPCODES[opcode].toLowerCase();
+  }
+
   @Override
   public String toString() {
     return builder.toString();
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 febbda3..412a7a1 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
@@ -12,6 +12,7 @@
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.utils.InternalOptions;
+import java.io.UTFDataFormatException;
 
 public class ConstString extends ConstInstruction {
 
@@ -86,8 +87,21 @@
 
   @Override
   public boolean canBeDeadCode(IRCode code, InternalOptions options) {
-    // The const-string instruction is a throwing instruction in DEX, but not so in CF.
-    return options.outputClassFiles;
+    // The const-string instruction can be a throwing instruction in DEX, if decode() fails,
+    // but not so in CF.
+    if (options.outputClassFiles) {
+      return true;
+    }
+    try {
+      value.toString();
+    } catch (RuntimeException e) {
+      if (e.getCause() instanceof UTFDataFormatException) {
+        return false;
+      } else {
+        throw e;
+      }
+    }
+    return true;
   }
 
   @Override
diff --git a/src/test/java/com/android/tools/r8/compatproguard/ForNameTest.java b/src/test/java/com/android/tools/r8/compatproguard/ForNameTest.java
index 2c7927e..8480791 100644
--- a/src/test/java/com/android/tools/r8/compatproguard/ForNameTest.java
+++ b/src/test/java/com/android/tools/r8/compatproguard/ForNameTest.java
@@ -53,15 +53,11 @@
     assertTrue(method.isPresent());
 
     DexCode code = method.getMethod().getCode().asDexCode();
-    // TODO(b/36799092): DeadCodeRemover should be able to remove this instruction.
     assertTrue(code.instructions[0] instanceof ConstString);
     ConstString constString = (ConstString) code.instructions[0];
-    assertEquals(BOO, constString.getString().toString());
-    assertTrue(code.instructions[1] instanceof ConstString);
-    constString = (ConstString) code.instructions[1];
     assertNotEquals(BOO, constString.getString().toString());
-    assertTrue(code.instructions[2] instanceof InvokeStatic);
-    assertTrue(code.instructions[3] instanceof ReturnVoid);
+    assertTrue(code.instructions[1] instanceof InvokeStatic);
+    assertTrue(code.instructions[2] instanceof ReturnVoid);
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/naming/IdentifierNameStringMarkerTest.java b/src/test/java/com/android/tools/r8/naming/IdentifierNameStringMarkerTest.java
index fa7a608..62c1bec 100644
--- a/src/test/java/com/android/tools/r8/naming/IdentifierNameStringMarkerTest.java
+++ b/src/test/java/com/android/tools/r8/naming/IdentifierNameStringMarkerTest.java
@@ -62,14 +62,10 @@
     DexCode code = method.getCode().asDexCode();
     assertTrue(code.instructions[0] instanceof InvokeDirect);
     assertTrue(code.instructions[1] instanceof ConstString);
-    // TODO(b/36799092): DeadCodeRemover should be able to remove this instruction.
     ConstString constString = (ConstString) code.instructions[1];
     assertEquals(BOO, constString.getString().toString());
-    assertTrue(code.instructions[2] instanceof ConstString);
-    constString = (ConstString) code.instructions[2];
-    assertEquals(BOO, constString.getString().toString());
-    assertTrue(code.instructions[3] instanceof IputObject);
-    assertTrue(code.instructions[4] instanceof ReturnVoid);
+    assertTrue(code.instructions[2] instanceof IputObject);
+    assertTrue(code.instructions[3] instanceof ReturnVoid);
   }
 
   @Test
@@ -169,15 +165,11 @@
     assertNotNull(method);
 
     DexCode code = method.getCode().asDexCode();
-    // TODO(b/36799092): DeadCodeRemover should be able to remove this instruction.
     assertTrue(code.instructions[0] instanceof ConstString);
     ConstString constString = (ConstString) code.instructions[0];
     assertEquals(BOO, constString.getString().toString());
-    assertTrue(code.instructions[1] instanceof ConstString);
-    constString = (ConstString) code.instructions[1];
-    assertEquals(BOO, constString.getString().toString());
-    assertTrue(code.instructions[2] instanceof SputObject);
-    assertTrue(code.instructions[3] instanceof ReturnVoid);
+    assertTrue(code.instructions[1] instanceof SputObject);
+    assertTrue(code.instructions[2] instanceof ReturnVoid);
   }
 
   @Test
@@ -375,18 +367,14 @@
 
     DexCode code = method.getCode().asDexCode();
     assertTrue(code.instructions[0] instanceof InvokeDirect);
-    // TODO(b/36799092): DeadCodeRemover should be able to remove this instruction.
     assertTrue(code.instructions[1] instanceof ConstString);
     ConstString constString = (ConstString) code.instructions[1];
-    assertEquals(BOO, constString.getString().toString());
+    assertEquals("Mixed/form.Boo", constString.getString().toString());
     assertTrue(code.instructions[2] instanceof ConstString);
     constString = (ConstString) code.instructions[2];
-    assertEquals("Mixed/form.Boo", constString.getString().toString());
-    assertTrue(code.instructions[3] instanceof ConstString);
-    constString = (ConstString) code.instructions[3];
     assertEquals(BOO, constString.getString().toString());
-    assertTrue(code.instructions[4] instanceof InvokeStatic);
-    assertTrue(code.instructions[5] instanceof ReturnVoid);
+    assertTrue(code.instructions[3] instanceof InvokeStatic);
+    assertTrue(code.instructions[4] instanceof ReturnVoid);
   }
 
   @Test
@@ -516,15 +504,11 @@
     DexCode code = method.getCode().asDexCode();
     assertTrue(code.instructions[0] instanceof InvokeDirect);
     assertTrue(code.instructions[1] instanceof ConstClass);
-    // TODO(b/36799092): DeadCodeRemover should be able to remove this instruction.
     assertTrue(code.instructions[2] instanceof ConstString);
     ConstString constString = (ConstString) code.instructions[2];
     assertEquals("foo", constString.getString().toString());
-    assertTrue(code.instructions[3] instanceof ConstString);
-    constString = (ConstString) code.instructions[3];
-    assertEquals("foo", constString.getString().toString());
-    assertTrue(code.instructions[4] instanceof InvokeStatic);
-    assertTrue(code.instructions[5] instanceof ReturnVoid);
+    assertTrue(code.instructions[3] instanceof InvokeStatic);
+    assertTrue(code.instructions[4] instanceof ReturnVoid);
   }
 
   @Test
@@ -568,15 +552,11 @@
     DexCode code = method.getCode().asDexCode();
     assertTrue(code.instructions[0] instanceof InvokeDirect);
     assertTrue(code.instructions[1] instanceof ConstClass);
-    // TODO(b/36799092): DeadCodeRemover should be able to remove this instruction.
     assertTrue(code.instructions[2] instanceof ConstString);
     ConstString constString = (ConstString) code.instructions[2];
-    assertEquals("foo", constString.getString().toString());
-    assertTrue(code.instructions[3] instanceof ConstString);
-    constString = (ConstString) code.instructions[3];
     assertNotEquals("foo", constString.getString().toString());
-    assertTrue(code.instructions[4] instanceof InvokeStatic);
-    assertTrue(code.instructions[5] instanceof ReturnVoid);
+    assertTrue(code.instructions[3] instanceof InvokeStatic);
+    assertTrue(code.instructions[4] instanceof ReturnVoid);
   }
 
   @Test
@@ -631,15 +611,11 @@
     assertTrue(code.instructions[3] instanceof NewArray);
     assertTrue(code.instructions[4] instanceof Const4);
     assertTrue(code.instructions[5] instanceof AputObject);
-    // TODO(b/36799092): DeadCodeRemover should be able to remove this instruction.
     assertTrue(code.instructions[6] instanceof ConstString);
     ConstString constString = (ConstString) code.instructions[6];
     assertEquals("foo", constString.getString().toString());
-    assertTrue(code.instructions[7] instanceof ConstString);
-    constString = (ConstString) code.instructions[7];
-    assertEquals("foo", constString.getString().toString());
-    assertTrue(code.instructions[8] instanceof InvokeStatic);
-    assertTrue(code.instructions[9] instanceof ReturnVoid);
+    assertTrue(code.instructions[7] instanceof InvokeStatic);
+    assertTrue(code.instructions[8] instanceof ReturnVoid);
   }
 
   @Test
@@ -694,15 +670,11 @@
     assertTrue(code.instructions[3] instanceof NewArray);
     assertTrue(code.instructions[4] instanceof Const4);
     assertTrue(code.instructions[5] instanceof AputObject);
-    // TODO(b/36799092): DeadCodeRemover should be able to remove this instruction.
     assertTrue(code.instructions[6] instanceof ConstString);
     ConstString constString = (ConstString) code.instructions[6];
-    assertEquals("foo", constString.getString().toString());
-    assertTrue(code.instructions[7] instanceof ConstString);
-    constString = (ConstString) code.instructions[7];
     assertNotEquals("foo", constString.getString().toString());
-    assertTrue(code.instructions[8] instanceof InvokeStatic);
-    assertTrue(code.instructions[9] instanceof ReturnVoid);
+    assertTrue(code.instructions[7] instanceof InvokeStatic);
+    assertTrue(code.instructions[8] instanceof ReturnVoid);
   }
 
   private DexInspector getInspectorAfterRunR8(