diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java
index 4a2e1e3..07f9e1c 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -14,6 +14,7 @@
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Iterators;
 import com.google.common.collect.Sets;
+import com.google.common.collect.Streams;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
@@ -726,6 +727,14 @@
     return false;
   }
 
+  public boolean isResolvable(AppView<?> appView) {
+    if (!isProgramClass()
+        && !appView.dexItemFactory().libraryTypesAssumedToBePresent.contains(type)) {
+      return false;
+    }
+    return Streams.stream(allImmediateSupertypes()).allMatch(type -> type.isResolvable(appView));
+  }
+
   public boolean isSerializable(AppView<? extends AppInfoWithSubtyping> appView) {
     return appView.appInfo().isSerializable(type);
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index a476e44..43a2815 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -208,6 +208,7 @@
   public final DexString serviceLoaderDescriptor = createString("Ljava/util/ServiceLoader;");
   public final DexString listDescriptor = createString("Ljava/util/List;");
   public final DexString comparatorDescriptor = createString("Ljava/util/Comparator;");
+  public final DexString callableDescriptor = createString("Ljava/util/concurrent/Callable;");
 
   public final DexString throwableDescriptor = createString(throwableDescriptorString);
   public final DexString illegalAccessErrorDescriptor =
@@ -215,6 +216,8 @@
   public final DexString icceDescriptor = createString("Ljava/lang/IncompatibleClassChangeError;");
   public final DexString exceptionInInitializerErrorDescriptor =
       createString("Ljava/lang/ExceptionInInitializerError;");
+  public final DexString noClassDefFoundErrorDescriptor =
+      createString("Ljava/lang/NoClassDefFoundError;");
   public final DexString noSuchFieldErrorDescriptor = createString("Ljava/lang/NoSuchFieldError;");
   public final DexString npeDescriptor = createString("Ljava/lang/NullPointerException;");
   public final DexString reflectiveOperationExceptionDescriptor =
@@ -283,12 +286,14 @@
   public final DexType serviceLoaderType = createType(serviceLoaderDescriptor);
   public final DexType listType = createType(listDescriptor);
   public final DexType comparatorType = createType(comparatorDescriptor);
+  public final DexType callableType = createType(callableDescriptor);
 
   public final DexType throwableType = createType(throwableDescriptor);
   public final DexType illegalAccessErrorType = createType(illegalAccessErrorDescriptor);
   public final DexType icceType = createType(icceDescriptor);
   public final DexType exceptionInInitializerErrorType =
       createType(exceptionInInitializerErrorDescriptor);
+  public final DexType noClassDefFoundErrorType = createType(noClassDefFoundErrorDescriptor);
   public final DexType noSuchFieldErrorType = createType(noSuchFieldErrorDescriptor);
   public final DexType npeType = createType(npeDescriptor);
   public final DexType reflectiveOperationExceptionType =
@@ -492,7 +497,7 @@
           .build();
 
   public Set<DexType> libraryTypesAssumedToBePresent =
-      ImmutableSet.of(objectType, stringBufferType, stringBuilderType);
+      ImmutableSet.of(objectType, callableType, stringBufferType, stringBuilderType);
 
   public final Set<DexType> libraryClassesWithoutStaticInitialization =
       ImmutableSet.of(objectType, stringBufferType, stringBuilderType);
diff --git a/src/main/java/com/android/tools/r8/graph/DexType.java b/src/main/java/com/android/tools/r8/graph/DexType.java
index 98fe0ec..6a2d270 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -258,6 +258,11 @@
     return clazz != null && clazz.isProgramClass();
   }
 
+  public boolean isResolvable(AppView<?> appView) {
+    DexClass clazz = appView.definitionFor(this);
+    return clazz != null && clazz.isResolvable(appView);
+  }
+
   public int elementSizeForPrimitiveArrayType() {
     assert isPrimitiveArrayType();
     switch (descriptor.content[1]) {
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 3077daf..b122429 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
@@ -11,6 +11,7 @@
 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;
@@ -82,29 +83,47 @@
 
   @Override
   public boolean instructionInstanceCanThrow() {
-    // TODO(christofferqa): Should return false in R8 if the class is in the program.
     return true;
   }
 
   @Override
-  public boolean instructionMayHaveSideEffects(AppView<?> appView, DexType context) {
+  public AbstractError instructionInstanceCanThrow(AppView<?> appView, DexType context) {
     DexType baseType = getValue().toBaseType(appView.dexItemFactory());
     if (baseType.isPrimitiveType()) {
-      return false;
+      return AbstractError.bottom();
     }
 
-    if (appView.enableWholeProgramOptimizations()) {
-      DexClass clazz = appView.definitionFor(baseType);
-      if (clazz != null && clazz.isProgramClass()) {
-        return false;
-      }
-    } else {
+    // Not applicable for D8.
+    if (!appView.enableWholeProgramOptimizations()) {
+      // Unless the type of interest is same as the context.
       if (baseType == context) {
-        return false;
+        return AbstractError.bottom();
       }
+      return AbstractError.top();
     }
 
-    return true;
+    DexClass clazz = appView.definitionFor(baseType);
+
+    if (clazz == null) {
+      return AbstractError.specific(appView.dexItemFactory().noClassDefFoundErrorType);
+    }
+    // * NoClassDefFoundError (resolution failure).
+    if (!clazz.isResolvable(appView)) {
+      return AbstractError.specific(appView.dexItemFactory().noClassDefFoundErrorType);
+    }
+    // * IllegalAccessError (not visible from the access context).
+    ConstraintWithTarget classVisibility =
+        ConstraintWithTarget.deriveConstraint(context, baseType, clazz.accessFlags, appView);
+    if (classVisibility == ConstraintWithTarget.NEVER) {
+      return AbstractError.specific(appView.dexItemFactory().illegalAccessErrorType);
+    }
+
+    return AbstractError.bottom();
+  }
+
+  @Override
+  public boolean instructionMayHaveSideEffects(AppView<?> appView, DexType context) {
+    return instructionInstanceCanThrow(appView, context).isThrowing();
   }
 
   @Override
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/IllegalAccessConstClassTest.java b/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/IllegalAccessConstClassTest.java
index 6f4bb79..88e9d07 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/IllegalAccessConstClassTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/IllegalAccessConstClassTest.java
@@ -17,7 +17,6 @@
 import com.android.tools.r8.utils.codeinspector.InstructionSubject;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import com.google.common.collect.Streams;
-import org.junit.Ignore;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -32,7 +31,7 @@
     if (System.currentTimeMillis() < -2) {
       System.out.println(PackagePrivateClass.class.getName());
     } else if (System.currentTimeMillis() < -1) {
-      System.out.println(PackagePrivateClass.class.getName());
+      System.out.println(PackagePrivateClass.class.getSimpleName());
     } else {
       System.out.println("No need to load any classes");
     }
@@ -83,7 +82,6 @@
         .assertSuccessWithOutput(JAVA_OUTPUT);
   }
 
-  @Ignore("b/135210786")
   @Test
   public void testR8() throws Exception {
     testForR8(parameters.getBackend())
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/IllegalAccessConstClassTestDump.java b/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/IllegalAccessConstClassTestDump.java
index 077750c..ea11c78 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/IllegalAccessConstClassTestDump.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/IllegalAccessConstClassTestDump.java
@@ -55,7 +55,7 @@
   //       if (System.currentTimeMillis() < -2) {
   //         System.out.println(PackagePrivateClass.class.getName());
   //       } else if (System.currentTimeMillis() < -1) {
-  //         System.out.println(PackagePrivateClass.class.getName());
+  //         System.out.println(PackagePrivateClass.class.getSimpleName());
   //       } else {
   //         System.out.println("No need to load any classes");
   //       }
@@ -140,7 +140,7 @@
         methodVisitor.visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;");
         methodVisitor.visitLdcInsn(Type.getType("LPackagePrivateClass;"));
         methodVisitor.visitMethodInsn(
-            INVOKEVIRTUAL, "java/lang/Class", "getName", "()Ljava/lang/String;", false);
+            INVOKEVIRTUAL, "java/lang/Class", "getSimpleName", "()Ljava/lang/String;", false);
         methodVisitor.visitMethodInsn(
             INVOKEVIRTUAL, "java/io/PrintStream", "println", "(Ljava/lang/String;)V", false);
         methodVisitor.visitJumpInsn(GOTO, label3);
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/UnresolvableLibraryConstClassTest.java b/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/UnresolvableLibraryConstClassTest.java
index a054c1b..7d98e26 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/UnresolvableLibraryConstClassTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/canonicalization/UnresolvableLibraryConstClassTest.java
@@ -19,7 +19,6 @@
 import com.android.tools.r8.utils.codeinspector.InstructionSubject;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import com.google.common.collect.Streams;
-import org.junit.Ignore;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -50,15 +49,15 @@
     if (System.currentTimeMillis() < -6) {
       System.out.println(ProgramSubClass.class.getName());
     } else if (System.currentTimeMillis() < -5) {
-      System.out.println(ProgramSubClass.class.getName());
+      System.out.println(ProgramSubClass.class.getSimpleName());
     } else if (System.currentTimeMillis() < -4) {
       System.out.println(ProgramClass1.class.getName());
     } else if (System.currentTimeMillis() < -3) {
-      System.out.println(ProgramClass1.class.getName());
+      System.out.println(ProgramClass1.class.getSimpleName());
     } else if (System.currentTimeMillis() < -2) {
       System.out.println(ProgramClass2.class.getName());
     } else if (System.currentTimeMillis() < -1) {
-      System.out.println(ProgramClass2.class.getName());
+      System.out.println(ProgramClass2.class.getSimpleName());
     } else {
       System.out.println("No need to load any classes");
     }
@@ -106,7 +105,6 @@
         .assertSuccessWithOutput(JAVA_OUTPUT);
   }
 
-  @Ignore("b/135210786")
   @Test
   public void testR8() throws Exception {
     testForR8(parameters.getBackend())