diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 15af102..39ed0b5 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -20,7 +20,6 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexDefinition;
 import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
@@ -99,7 +98,6 @@
 import com.android.tools.r8.utils.StringDiagnostic;
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.Timing;
-import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.io.ByteStreams;
 import java.io.ByteArrayOutputStream;
@@ -791,13 +789,7 @@
       // Remove unneeded visibility bridges that have been inserted for member rebinding.
       // This can only be done if we have AppInfoWithLiveness.
       if (appView.appInfo().hasLiveness()) {
-        ImmutableSet.Builder<DexMethod> unneededVisibilityBridgeMethods = ImmutableSet.builder();
-        new VisibilityBridgeRemover(
-                appView.withLiveness(),
-                unneededVisibilityBridgeMethod ->
-                    unneededVisibilityBridgeMethods.add(unneededVisibilityBridgeMethod.method))
-            .run();
-        appView.setUnneededVisibilityBridgeMethods(unneededVisibilityBridgeMethods.build());
+        new VisibilityBridgeRemover(appView.withLiveness()).run();
       } else {
         // If we don't have AppInfoWithLiveness here, it must be because we are not shrinking. When
         // we are not shrinking, we can't move visibility bridges. In principle, though, it would be
diff --git a/src/main/java/com/android/tools/r8/androidapi/AvailableApiExceptions.java b/src/main/java/com/android/tools/r8/androidapi/AvailableApiExceptions.java
new file mode 100644
index 0000000..c44f1f4
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/androidapi/AvailableApiExceptions.java
@@ -0,0 +1,405 @@
+// 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.androidapi;
+
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.SetUtils;
+import java.util.Set;
+
+/**
+ * Provides a mapping of API levels to exceptions introduced at that API level.
+ *
+ * <p>The mapping is only provided up to excluding the API level 21 (Android L) at which point the
+ * verification issue for unresolved exception types was fixed.
+ *
+ * <p>See b/153514654 and b/131349148.
+ *
+ * <p>See GenerateAvailableApiExceptions.main in tests module for generating the buildMap function.
+ */
+public class AvailableApiExceptions {
+
+  private final Set<DexType> exceptions;
+
+  public AvailableApiExceptions(InternalOptions options) {
+    assert options.minApiLevel < AndroidApiLevel.L.getLevel();
+    exceptions = build(options.itemFactory, options.minApiLevel);
+  }
+
+  public boolean canCauseVerificationError(DexType type) {
+    return !exceptions.contains(type);
+  }
+
+  /** The content of this method can be regenerated with GenerateAvailableExceptions.main. */
+  public static Set<DexType> build(DexItemFactory factory, int minApiLevel) {
+    Set<DexType> types = SetUtils.newIdentityHashSet(333);
+    if (minApiLevel >= 1) {
+      types.add(factory.createType("Landroid/app/PendingIntent$CanceledException;"));
+      types.add(factory.createType("Landroid/content/ActivityNotFoundException;"));
+      types.add(factory.createType("Landroid/content/IntentFilter$MalformedMimeTypeException;"));
+      types.add(factory.createType("Landroid/content/ReceiverCallNotAllowedException;"));
+      types.add(factory.createType("Landroid/content/pm/PackageManager$NameNotFoundException;"));
+      types.add(factory.createType("Landroid/content/res/Resources$NotFoundException;"));
+      types.add(factory.createType("Landroid/database/CursorIndexOutOfBoundsException;"));
+      types.add(factory.createType("Landroid/database/SQLException;"));
+      types.add(factory.createType("Landroid/database/StaleDataException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteAbortException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteConstraintException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteDatabaseCorruptException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteDiskIOException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteDoneException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteFullException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteMisuseException;"));
+      types.add(factory.createType("Landroid/net/ParseException;"));
+      types.add(factory.createType("Landroid/opengl/GLException;"));
+      types.add(factory.createType("Landroid/os/BadParcelableException;"));
+      types.add(factory.createType("Landroid/os/DeadObjectException;"));
+      types.add(factory.createType("Landroid/os/ParcelFormatException;"));
+      types.add(factory.createType("Landroid/os/RemoteException;"));
+      types.add(factory.createType("Landroid/provider/Settings$SettingNotFoundException;"));
+      types.add(factory.createType("Landroid/test/AssertionFailedError;"));
+      types.add(factory.createType("Landroid/test/ComparisonFailure;"));
+      types.add(factory.createType("Landroid/util/AndroidException;"));
+      types.add(factory.createType("Landroid/util/AndroidRuntimeException;"));
+      types.add(factory.createType("Landroid/util/TimeFormatException;"));
+      types.add(factory.createType("Landroid/view/InflateException;"));
+      types.add(factory.createType("Landroid/view/Surface$OutOfResourcesException;"));
+      types.add(factory.createType("Landroid/view/SurfaceHolder$BadSurfaceTypeException;"));
+      types.add(factory.createType("Landroid/view/WindowManager$BadTokenException;"));
+      types.add(factory.createType("Landroid/widget/RemoteViews$ActionException;"));
+      types.add(factory.createType("Ljava/io/CharConversionException;"));
+      types.add(factory.createType("Ljava/io/EOFException;"));
+      types.add(factory.createType("Ljava/io/FileNotFoundException;"));
+      types.add(factory.createType("Ljava/io/IOException;"));
+      types.add(factory.createType("Ljava/io/InterruptedIOException;"));
+      types.add(factory.createType("Ljava/io/InvalidClassException;"));
+      types.add(factory.createType("Ljava/io/InvalidObjectException;"));
+      types.add(factory.createType("Ljava/io/NotActiveException;"));
+      types.add(factory.createType("Ljava/io/NotSerializableException;"));
+      types.add(factory.createType("Ljava/io/ObjectStreamException;"));
+      types.add(factory.createType("Ljava/io/OptionalDataException;"));
+      types.add(factory.createType("Ljava/io/StreamCorruptedException;"));
+      types.add(factory.createType("Ljava/io/SyncFailedException;"));
+      types.add(factory.createType("Ljava/io/UTFDataFormatException;"));
+      types.add(factory.createType("Ljava/io/UnsupportedEncodingException;"));
+      types.add(factory.createType("Ljava/io/WriteAbortedException;"));
+      types.add(factory.createType("Ljava/lang/AbstractMethodError;"));
+      types.add(factory.createType("Ljava/lang/ArithmeticException;"));
+      types.add(factory.createType("Ljava/lang/ArrayIndexOutOfBoundsException;"));
+      types.add(factory.createType("Ljava/lang/ArrayStoreException;"));
+      types.add(factory.createType("Ljava/lang/AssertionError;"));
+      types.add(factory.createType("Ljava/lang/ClassCastException;"));
+      types.add(factory.createType("Ljava/lang/ClassCircularityError;"));
+      types.add(factory.createType("Ljava/lang/ClassFormatError;"));
+      types.add(factory.createType("Ljava/lang/ClassNotFoundException;"));
+      types.add(factory.createType("Ljava/lang/CloneNotSupportedException;"));
+      types.add(factory.createType("Ljava/lang/EnumConstantNotPresentException;"));
+      types.add(factory.createType("Ljava/lang/Error;"));
+      types.add(factory.createType("Ljava/lang/Exception;"));
+      types.add(factory.createType("Ljava/lang/ExceptionInInitializerError;"));
+      types.add(factory.createType("Ljava/lang/IllegalAccessError;"));
+      types.add(factory.createType("Ljava/lang/IllegalAccessException;"));
+      types.add(factory.createType("Ljava/lang/IllegalArgumentException;"));
+      types.add(factory.createType("Ljava/lang/IllegalMonitorStateException;"));
+      types.add(factory.createType("Ljava/lang/IllegalStateException;"));
+      types.add(factory.createType("Ljava/lang/IllegalThreadStateException;"));
+      types.add(factory.createType("Ljava/lang/IncompatibleClassChangeError;"));
+      types.add(factory.createType("Ljava/lang/IndexOutOfBoundsException;"));
+      types.add(factory.createType("Ljava/lang/InstantiationError;"));
+      types.add(factory.createType("Ljava/lang/InstantiationException;"));
+      types.add(factory.createType("Ljava/lang/InternalError;"));
+      types.add(factory.createType("Ljava/lang/InterruptedException;"));
+      types.add(factory.createType("Ljava/lang/LinkageError;"));
+      types.add(factory.createType("Ljava/lang/NegativeArraySizeException;"));
+      types.add(factory.createType("Ljava/lang/NoClassDefFoundError;"));
+      types.add(factory.createType("Ljava/lang/NoSuchFieldError;"));
+      types.add(factory.createType("Ljava/lang/NoSuchFieldException;"));
+      types.add(factory.createType("Ljava/lang/NoSuchMethodError;"));
+      types.add(factory.createType("Ljava/lang/NoSuchMethodException;"));
+      types.add(factory.createType("Ljava/lang/NullPointerException;"));
+      types.add(factory.createType("Ljava/lang/NumberFormatException;"));
+      types.add(factory.createType("Ljava/lang/OutOfMemoryError;"));
+      types.add(factory.createType("Ljava/lang/RuntimeException;"));
+      types.add(factory.createType("Ljava/lang/SecurityException;"));
+      types.add(factory.createType("Ljava/lang/StackOverflowError;"));
+      types.add(factory.createType("Ljava/lang/StringIndexOutOfBoundsException;"));
+      types.add(factory.createType("Ljava/lang/ThreadDeath;"));
+      types.add(factory.createType("Ljava/lang/Throwable;"));
+      types.add(factory.createType("Ljava/lang/TypeNotPresentException;"));
+      types.add(factory.createType("Ljava/lang/UnknownError;"));
+      types.add(factory.createType("Ljava/lang/UnsatisfiedLinkError;"));
+      types.add(factory.createType("Ljava/lang/UnsupportedClassVersionError;"));
+      types.add(factory.createType("Ljava/lang/UnsupportedOperationException;"));
+      types.add(factory.createType("Ljava/lang/VerifyError;"));
+      types.add(factory.createType("Ljava/lang/VirtualMachineError;"));
+      types.add(factory.createType("Ljava/lang/annotation/AnnotationFormatError;"));
+      types.add(factory.createType("Ljava/lang/annotation/AnnotationTypeMismatchException;"));
+      types.add(factory.createType("Ljava/lang/annotation/IncompleteAnnotationException;"));
+      types.add(factory.createType("Ljava/lang/reflect/GenericSignatureFormatError;"));
+      types.add(factory.createType("Ljava/lang/reflect/InvocationTargetException;"));
+      types.add(factory.createType("Ljava/lang/reflect/MalformedParameterizedTypeException;"));
+      types.add(factory.createType("Ljava/lang/reflect/UndeclaredThrowableException;"));
+      types.add(factory.createType("Ljava/net/BindException;"));
+      types.add(factory.createType("Ljava/net/ConnectException;"));
+      types.add(factory.createType("Ljava/net/HttpRetryException;"));
+      types.add(factory.createType("Ljava/net/MalformedURLException;"));
+      types.add(factory.createType("Ljava/net/NoRouteToHostException;"));
+      types.add(factory.createType("Ljava/net/PortUnreachableException;"));
+      types.add(factory.createType("Ljava/net/ProtocolException;"));
+      types.add(factory.createType("Ljava/net/SocketException;"));
+      types.add(factory.createType("Ljava/net/SocketTimeoutException;"));
+      types.add(factory.createType("Ljava/net/URISyntaxException;"));
+      types.add(factory.createType("Ljava/net/UnknownHostException;"));
+      types.add(factory.createType("Ljava/net/UnknownServiceException;"));
+      types.add(factory.createType("Ljava/nio/BufferOverflowException;"));
+      types.add(factory.createType("Ljava/nio/BufferUnderflowException;"));
+      types.add(factory.createType("Ljava/nio/InvalidMarkException;"));
+      types.add(factory.createType("Ljava/nio/ReadOnlyBufferException;"));
+      types.add(factory.createType("Ljava/nio/channels/AlreadyConnectedException;"));
+      types.add(factory.createType("Ljava/nio/channels/AsynchronousCloseException;"));
+      types.add(factory.createType("Ljava/nio/channels/CancelledKeyException;"));
+      types.add(factory.createType("Ljava/nio/channels/ClosedByInterruptException;"));
+      types.add(factory.createType("Ljava/nio/channels/ClosedChannelException;"));
+      types.add(factory.createType("Ljava/nio/channels/ClosedSelectorException;"));
+      types.add(factory.createType("Ljava/nio/channels/ConnectionPendingException;"));
+      types.add(factory.createType("Ljava/nio/channels/FileLockInterruptionException;"));
+      types.add(factory.createType("Ljava/nio/channels/IllegalBlockingModeException;"));
+      types.add(factory.createType("Ljava/nio/channels/IllegalSelectorException;"));
+      types.add(factory.createType("Ljava/nio/channels/NoConnectionPendingException;"));
+      types.add(factory.createType("Ljava/nio/channels/NonReadableChannelException;"));
+      types.add(factory.createType("Ljava/nio/channels/NonWritableChannelException;"));
+      types.add(factory.createType("Ljava/nio/channels/NotYetBoundException;"));
+      types.add(factory.createType("Ljava/nio/channels/NotYetConnectedException;"));
+      types.add(factory.createType("Ljava/nio/channels/OverlappingFileLockException;"));
+      types.add(factory.createType("Ljava/nio/channels/UnresolvedAddressException;"));
+      types.add(factory.createType("Ljava/nio/channels/UnsupportedAddressTypeException;"));
+      types.add(factory.createType("Ljava/nio/charset/CharacterCodingException;"));
+      types.add(factory.createType("Ljava/nio/charset/CoderMalfunctionError;"));
+      types.add(factory.createType("Ljava/nio/charset/IllegalCharsetNameException;"));
+      types.add(factory.createType("Ljava/nio/charset/MalformedInputException;"));
+      types.add(factory.createType("Ljava/nio/charset/UnmappableCharacterException;"));
+      types.add(factory.createType("Ljava/nio/charset/UnsupportedCharsetException;"));
+      types.add(factory.createType("Ljava/security/AccessControlException;"));
+      types.add(factory.createType("Ljava/security/DigestException;"));
+      types.add(factory.createType("Ljava/security/GeneralSecurityException;"));
+      types.add(factory.createType("Ljava/security/InvalidAlgorithmParameterException;"));
+      types.add(factory.createType("Ljava/security/InvalidKeyException;"));
+      types.add(factory.createType("Ljava/security/InvalidParameterException;"));
+      types.add(factory.createType("Ljava/security/KeyException;"));
+      types.add(factory.createType("Ljava/security/KeyManagementException;"));
+      types.add(factory.createType("Ljava/security/KeyStoreException;"));
+      types.add(factory.createType("Ljava/security/NoSuchAlgorithmException;"));
+      types.add(factory.createType("Ljava/security/NoSuchProviderException;"));
+      types.add(factory.createType("Ljava/security/PrivilegedActionException;"));
+      types.add(factory.createType("Ljava/security/ProviderException;"));
+      types.add(factory.createType("Ljava/security/SignatureException;"));
+      types.add(factory.createType("Ljava/security/UnrecoverableEntryException;"));
+      types.add(factory.createType("Ljava/security/UnrecoverableKeyException;"));
+      types.add(factory.createType("Ljava/security/acl/AclNotFoundException;"));
+      types.add(factory.createType("Ljava/security/acl/LastOwnerException;"));
+      types.add(factory.createType("Ljava/security/acl/NotOwnerException;"));
+      types.add(factory.createType("Ljava/security/cert/CRLException;"));
+      types.add(factory.createType("Ljava/security/cert/CertPathBuilderException;"));
+      types.add(factory.createType("Ljava/security/cert/CertPathValidatorException;"));
+      types.add(factory.createType("Ljava/security/cert/CertStoreException;"));
+      types.add(factory.createType("Ljava/security/cert/CertificateEncodingException;"));
+      types.add(factory.createType("Ljava/security/cert/CertificateException;"));
+      types.add(factory.createType("Ljava/security/cert/CertificateExpiredException;"));
+      types.add(factory.createType("Ljava/security/cert/CertificateNotYetValidException;"));
+      types.add(factory.createType("Ljava/security/cert/CertificateParsingException;"));
+      types.add(factory.createType("Ljava/security/spec/InvalidKeySpecException;"));
+      types.add(factory.createType("Ljava/security/spec/InvalidParameterSpecException;"));
+      types.add(factory.createType("Ljava/sql/BatchUpdateException;"));
+      types.add(factory.createType("Ljava/sql/DataTruncation;"));
+      types.add(factory.createType("Ljava/sql/SQLException;"));
+      types.add(factory.createType("Ljava/sql/SQLWarning;"));
+      types.add(factory.createType("Ljava/text/ParseException;"));
+      types.add(factory.createType("Ljava/util/ConcurrentModificationException;"));
+      types.add(factory.createType("Ljava/util/DuplicateFormatFlagsException;"));
+      types.add(factory.createType("Ljava/util/EmptyStackException;"));
+      types.add(factory.createType("Ljava/util/FormatFlagsConversionMismatchException;"));
+      types.add(factory.createType("Ljava/util/FormatterClosedException;"));
+      types.add(factory.createType("Ljava/util/IllegalFormatCodePointException;"));
+      types.add(factory.createType("Ljava/util/IllegalFormatConversionException;"));
+      types.add(factory.createType("Ljava/util/IllegalFormatException;"));
+      types.add(factory.createType("Ljava/util/IllegalFormatFlagsException;"));
+      types.add(factory.createType("Ljava/util/IllegalFormatPrecisionException;"));
+      types.add(factory.createType("Ljava/util/IllegalFormatWidthException;"));
+      types.add(factory.createType("Ljava/util/InputMismatchException;"));
+      types.add(factory.createType("Ljava/util/InvalidPropertiesFormatException;"));
+      types.add(factory.createType("Ljava/util/MissingFormatArgumentException;"));
+      types.add(factory.createType("Ljava/util/MissingFormatWidthException;"));
+      types.add(factory.createType("Ljava/util/MissingResourceException;"));
+      types.add(factory.createType("Ljava/util/NoSuchElementException;"));
+      types.add(factory.createType("Ljava/util/TooManyListenersException;"));
+      types.add(factory.createType("Ljava/util/UnknownFormatConversionException;"));
+      types.add(factory.createType("Ljava/util/UnknownFormatFlagsException;"));
+      types.add(factory.createType("Ljava/util/concurrent/BrokenBarrierException;"));
+      types.add(factory.createType("Ljava/util/concurrent/CancellationException;"));
+      types.add(factory.createType("Ljava/util/concurrent/ExecutionException;"));
+      types.add(factory.createType("Ljava/util/concurrent/RejectedExecutionException;"));
+      types.add(factory.createType("Ljava/util/concurrent/TimeoutException;"));
+      types.add(factory.createType("Ljava/util/jar/JarException;"));
+      types.add(factory.createType("Ljava/util/prefs/BackingStoreException;"));
+      types.add(factory.createType("Ljava/util/prefs/InvalidPreferencesFormatException;"));
+      types.add(factory.createType("Ljava/util/regex/PatternSyntaxException;"));
+      types.add(factory.createType("Ljava/util/zip/DataFormatException;"));
+      types.add(factory.createType("Ljava/util/zip/ZipException;"));
+      types.add(factory.createType("Ljavax/crypto/BadPaddingException;"));
+      types.add(factory.createType("Ljavax/crypto/ExemptionMechanismException;"));
+      types.add(factory.createType("Ljavax/crypto/IllegalBlockSizeException;"));
+      types.add(factory.createType("Ljavax/crypto/NoSuchPaddingException;"));
+      types.add(factory.createType("Ljavax/crypto/ShortBufferException;"));
+      types.add(factory.createType("Ljavax/net/ssl/SSLException;"));
+      types.add(factory.createType("Ljavax/net/ssl/SSLHandshakeException;"));
+      types.add(factory.createType("Ljavax/net/ssl/SSLKeyException;"));
+      types.add(factory.createType("Ljavax/net/ssl/SSLPeerUnverifiedException;"));
+      types.add(factory.createType("Ljavax/net/ssl/SSLProtocolException;"));
+      types.add(factory.createType("Ljavax/security/auth/DestroyFailedException;"));
+      types.add(factory.createType("Ljavax/security/auth/callback/UnsupportedCallbackException;"));
+      types.add(factory.createType("Ljavax/security/auth/login/LoginException;"));
+      types.add(factory.createType("Ljavax/security/cert/CertificateEncodingException;"));
+      types.add(factory.createType("Ljavax/security/cert/CertificateException;"));
+      types.add(factory.createType("Ljavax/security/cert/CertificateExpiredException;"));
+      types.add(factory.createType("Ljavax/security/cert/CertificateNotYetValidException;"));
+      types.add(factory.createType("Ljavax/security/cert/CertificateParsingException;"));
+      types.add(factory.createType("Ljavax/xml/parsers/FactoryConfigurationError;"));
+      types.add(factory.createType("Ljavax/xml/parsers/ParserConfigurationException;"));
+      types.add(factory.createType("Ljunit/framework/AssertionFailedError;"));
+      types.add(factory.createType("Ljunit/framework/ComparisonFailure;"));
+      types.add(factory.createType("Lorg/apache/http/ConnectionClosedException;"));
+      types.add(factory.createType("Lorg/apache/http/HttpException;"));
+      types.add(factory.createType("Lorg/apache/http/MalformedChunkCodingException;"));
+      types.add(factory.createType("Lorg/apache/http/MethodNotSupportedException;"));
+      types.add(factory.createType("Lorg/apache/http/NoHttpResponseException;"));
+      types.add(factory.createType("Lorg/apache/http/ParseException;"));
+      types.add(factory.createType("Lorg/apache/http/ProtocolException;"));
+      types.add(factory.createType("Lorg/apache/http/UnsupportedHttpVersionException;"));
+      types.add(factory.createType("Lorg/apache/http/auth/AuthenticationException;"));
+      types.add(factory.createType("Lorg/apache/http/auth/InvalidCredentialsException;"));
+      types.add(factory.createType("Lorg/apache/http/auth/MalformedChallengeException;"));
+      types.add(factory.createType("Lorg/apache/http/client/CircularRedirectException;"));
+      types.add(factory.createType("Lorg/apache/http/client/ClientProtocolException;"));
+      types.add(factory.createType("Lorg/apache/http/client/HttpResponseException;"));
+      types.add(factory.createType("Lorg/apache/http/client/NonRepeatableRequestException;"));
+      types.add(factory.createType("Lorg/apache/http/client/RedirectException;"));
+      types.add(factory.createType("Lorg/apache/http/conn/ConnectTimeoutException;"));
+      types.add(factory.createType("Lorg/apache/http/conn/ConnectionPoolTimeoutException;"));
+      types.add(factory.createType("Lorg/apache/http/conn/HttpHostConnectException;"));
+      types.add(factory.createType("Lorg/apache/http/cookie/MalformedCookieException;"));
+      types.add(factory.createType("Lorg/apache/http/impl/auth/NTLMEngineException;"));
+      types.add(
+          factory.createType("Lorg/apache/http/impl/auth/UnsupportedDigestAlgorithmException;"));
+      types.add(factory.createType("Lorg/apache/http/impl/client/TunnelRefusedException;"));
+      types.add(factory.createType("Lorg/apache/http/impl/cookie/DateParseException;"));
+      types.add(factory.createType("Lorg/json/JSONException;"));
+      types.add(factory.createType("Lorg/w3c/dom/DOMException;"));
+      types.add(factory.createType("Lorg/xml/sax/SAXException;"));
+      types.add(factory.createType("Lorg/xml/sax/SAXNotRecognizedException;"));
+      types.add(factory.createType("Lorg/xml/sax/SAXNotSupportedException;"));
+      types.add(factory.createType("Lorg/xml/sax/SAXParseException;"));
+      types.add(factory.createType("Lorg/xmlpull/v1/XmlPullParserException;"));
+    }
+    if (minApiLevel >= 4) {
+      types.add(factory.createType("Landroid/content/IntentSender$SendIntentException;"));
+    }
+    if (minApiLevel >= 5) {
+      types.add(factory.createType("Landroid/accounts/AccountsException;"));
+      types.add(factory.createType("Landroid/accounts/AuthenticatorException;"));
+      types.add(factory.createType("Landroid/accounts/NetworkErrorException;"));
+      types.add(factory.createType("Landroid/accounts/OperationCanceledException;"));
+      types.add(factory.createType("Landroid/content/OperationApplicationException;"));
+    }
+    if (minApiLevel >= 8) {
+      types.add(factory.createType("Ljavax/xml/datatype/DatatypeConfigurationException;"));
+      types.add(factory.createType("Ljavax/xml/transform/TransformerConfigurationException;"));
+      types.add(factory.createType("Ljavax/xml/transform/TransformerException;"));
+      types.add(factory.createType("Ljavax/xml/transform/TransformerFactoryConfigurationError;"));
+      types.add(factory.createType("Ljavax/xml/xpath/XPathException;"));
+      types.add(factory.createType("Ljavax/xml/xpath/XPathExpressionException;"));
+      types.add(factory.createType("Ljavax/xml/xpath/XPathFactoryConfigurationException;"));
+      types.add(factory.createType("Ljavax/xml/xpath/XPathFunctionException;"));
+      types.add(factory.createType("Lorg/w3c/dom/ls/LSException;"));
+    }
+    if (minApiLevel >= 9) {
+      types.add(factory.createType("Landroid/net/sip/SipException;"));
+      types.add(factory.createType("Landroid/nfc/FormatException;"));
+      types.add(factory.createType("Ljava/io/IOError;"));
+      types.add(factory.createType("Ljava/sql/SQLClientInfoException;"));
+      types.add(factory.createType("Ljava/sql/SQLDataException;"));
+      types.add(factory.createType("Ljava/sql/SQLFeatureNotSupportedException;"));
+      types.add(factory.createType("Ljava/sql/SQLIntegrityConstraintViolationException;"));
+      types.add(factory.createType("Ljava/sql/SQLInvalidAuthorizationSpecException;"));
+      types.add(factory.createType("Ljava/sql/SQLNonTransientConnectionException;"));
+      types.add(factory.createType("Ljava/sql/SQLNonTransientException;"));
+      types.add(factory.createType("Ljava/sql/SQLRecoverableException;"));
+      types.add(factory.createType("Ljava/sql/SQLSyntaxErrorException;"));
+      types.add(factory.createType("Ljava/sql/SQLTimeoutException;"));
+      types.add(factory.createType("Ljava/sql/SQLTransactionRollbackException;"));
+      types.add(factory.createType("Ljava/sql/SQLTransientConnectionException;"));
+      types.add(factory.createType("Ljava/sql/SQLTransientException;"));
+      types.add(factory.createType("Ljava/util/ServiceConfigurationError;"));
+      types.add(factory.createType("Ljava/util/zip/ZipError;"));
+    }
+    if (minApiLevel >= 10) {
+      types.add(factory.createType("Landroid/nfc/TagLostException;"));
+    }
+    if (minApiLevel >= 11) {
+      types.add(factory.createType("Landroid/app/Fragment$InstantiationException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteAccessPermException;"));
+      types.add(
+          factory.createType(
+              "Landroid/database/sqlite/SQLiteBindOrColumnIndexOutOfRangeException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteBlobTooBigException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteCantOpenDatabaseException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteDatabaseLockedException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteDatatypeMismatchException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteOutOfMemoryException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteReadOnlyDatabaseException;"));
+      types.add(factory.createType("Landroid/database/sqlite/SQLiteTableLockedException;"));
+      types.add(factory.createType("Landroid/graphics/SurfaceTexture$OutOfResourcesException;"));
+      types.add(factory.createType("Landroid/os/NetworkOnMainThreadException;"));
+      types.add(factory.createType("Landroid/renderscript/RSDriverException;"));
+      types.add(factory.createType("Landroid/renderscript/RSIllegalArgumentException;"));
+      types.add(factory.createType("Landroid/renderscript/RSInvalidStateException;"));
+      types.add(factory.createType("Landroid/renderscript/RSRuntimeException;"));
+      types.add(factory.createType("Landroid/util/Base64DataException;"));
+      types.add(factory.createType("Landroid/util/MalformedJsonException;"));
+      types.add(factory.createType("Landroid/view/KeyCharacterMap$UnavailableException;"));
+    }
+    if (minApiLevel >= 14) {
+      types.add(factory.createType("Landroid/security/KeyChainException;"));
+      types.add(factory.createType("Landroid/util/NoSuchPropertyException;"));
+    }
+    if (minApiLevel >= 15) {
+      types.add(factory.createType("Landroid/os/TransactionTooLargeException;"));
+    }
+    if (minApiLevel >= 16) {
+      types.add(factory.createType("Landroid/media/MediaCodec$CryptoException;"));
+      types.add(factory.createType("Landroid/media/MediaCryptoException;"));
+      types.add(factory.createType("Landroid/os/OperationCanceledException;"));
+    }
+    if (minApiLevel >= 17) {
+      types.add(factory.createType("Landroid/view/WindowManager$InvalidDisplayException;"));
+    }
+    if (minApiLevel >= 18) {
+      types.add(factory.createType("Landroid/media/DeniedByServerException;"));
+      types.add(factory.createType("Landroid/media/MediaDrmException;"));
+      types.add(factory.createType("Landroid/media/NotProvisionedException;"));
+      types.add(factory.createType("Landroid/media/UnsupportedSchemeException;"));
+    }
+    if (minApiLevel >= 19) {
+      types.add(factory.createType("Landroid/media/ResourceBusyException;"));
+      types.add(
+          factory.createType("Landroid/os/ParcelFileDescriptor$FileDescriptorDetachedException;"));
+      types.add(factory.createType("Ljava/lang/ReflectiveOperationException;"));
+      types.add(factory.createType("Ljavax/crypto/AEADBadTagException;"));
+    }
+    return types;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/dex/VirtualFile.java b/src/main/java/com/android/tools/r8/dex/VirtualFile.java
index a9ff477..4eee167 100644
--- a/src/main/java/com/android/tools/r8/dex/VirtualFile.java
+++ b/src/main/java/com/android/tools/r8/dex/VirtualFile.java
@@ -633,7 +633,7 @@
 
     @Override
     public DexString getRenamedName(DexMethod method) {
-      assert namingLens.checkTargetCanBeTranslated(method);
+      assert namingLens.verifyRenamingConsistentWithResolution(method);
       return namingLens.lookupName(method);
     }
 
@@ -729,7 +729,7 @@
 
     @Override
     public DexString getRenamedName(DexMethod method) {
-      assert namingLens.checkTargetCanBeTranslated(method);
+      assert namingLens.verifyRenamingConsistentWithResolution(method);
       return namingLens.lookupName(method);
     }
 
diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
index 20216c4..0e4b9cf 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -25,10 +25,8 @@
 import com.android.tools.r8.utils.OptionalBool;
 import com.android.tools.r8.utils.ThrowingConsumer;
 import com.google.common.base.Predicates;
-import com.google.common.collect.ImmutableSet;
 import java.util.IdentityHashMap;
 import java.util.Map;
-import java.util.Set;
 import java.util.function.Consumer;
 import java.util.function.Function;
 import java.util.function.Predicate;
@@ -64,7 +62,6 @@
   private boolean allCodeProcessed = false;
   private Predicate<DexType> classesEscapingIntoLibrary = Predicates.alwaysTrue();
   private InitializedClassesInInstanceMethods initializedClassesInInstanceMethods;
-  private Set<DexMethod> unneededVisibilityBridgeMethods = ImmutableSet.of();
   private HorizontallyMergedLambdaClasses horizontallyMergedLambdaClasses;
   private VerticallyMergedClasses verticallyMergedClasses;
   private EnumValueInfoMapCollection unboxedEnums = EnumValueInfoMapCollection.empty();
@@ -350,14 +347,6 @@
     this.rootSet = rootSet;
   }
 
-  public Set<DexMethod> unneededVisibilityBridgeMethods() {
-    return unneededVisibilityBridgeMethods;
-  }
-
-  public void setUnneededVisibilityBridgeMethods(Set<DexMethod> unneededVisibilityBridgeMethods) {
-    this.unneededVisibilityBridgeMethods = unneededVisibilityBridgeMethods;
-  }
-
   public MergedClassesCollection allMergedClasses() {
     MergedClassesCollection collection = new MergedClassesCollection();
     if (horizontallyMergedLambdaClasses != null) {
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 9dd0398..f8043c3 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -150,8 +150,8 @@
     methodCollection.addDirectMethods(methods);
   }
 
-  public void removeDirectMethod(DexMethod method) {
-    methodCollection.removeDirectMethod(method);
+  public void removeMethod(DexMethod method) {
+    methodCollection.removeMethod(method);
   }
 
   public void setDirectMethods(DexEncodedMethod[] methods) {
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index 20337fd..03f1415 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -257,6 +257,10 @@
     assert parameterAnnotationsList != null;
   }
 
+  public DexType returnType() {
+    return method.proto.returnType;
+  }
+
   public ParameterAnnotationsList liveParameterAnnotations(AppView<AppInfoWithLiveness> appView) {
     return parameterAnnotationsList.keepIf(
         annotation -> AnnotationRemover.shouldKeepAnnotation(appView, this, annotation));
@@ -299,6 +303,10 @@
     return accessFlags.isAbstract();
   }
 
+  public boolean isBridge() {
+    return accessFlags.isBridge();
+  }
+
   public boolean isFinal() {
     return accessFlags.isFinal();
   }
diff --git a/src/main/java/com/android/tools/r8/graph/MethodArrayBacking.java b/src/main/java/com/android/tools/r8/graph/MethodArrayBacking.java
index 4eda679..5b05c3f 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodArrayBacking.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodArrayBacking.java
@@ -12,6 +12,7 @@
 import java.util.Collection;
 import java.util.List;
 import java.util.Set;
+import java.util.function.Consumer;
 import java.util.function.Function;
 import java.util.function.Predicate;
 
@@ -82,25 +83,42 @@
     assert verifyNoDuplicateMethods();
   }
 
-  private void removeDirectMethod(int index) {
-    DexEncodedMethod[] newMethods = new DexEncodedMethod[directMethods.length - 1];
-    System.arraycopy(directMethods, 0, newMethods, 0, index);
-    System.arraycopy(directMethods, index + 1, newMethods, index, directMethods.length - index - 1);
-    directMethods = newMethods;
+  @Override
+  DexEncodedMethod removeMethod(DexMethod method) {
+    DexEncodedMethod removedDirectMethod =
+        removeMethodHelper(
+            method, directMethods, newDirectMethods -> directMethods = newDirectMethods);
+    if (removedDirectMethod != null) {
+      assert belongsToDirectPool(removedDirectMethod);
+      return removedDirectMethod;
+    }
+    DexEncodedMethod removedVirtualMethod =
+        removeMethodHelper(
+            method, virtualMethods, newVirtualMethods -> virtualMethods = newVirtualMethods);
+    assert removedVirtualMethod == null || belongsToVirtualPool(removedVirtualMethod);
+    return removedVirtualMethod;
   }
 
-  @Override
-  void removeDirectMethod(DexMethod method) {
-    int index = -1;
-    for (int i = 0; i < directMethods.length; i++) {
-      if (method.match(directMethods[i])) {
-        index = i;
-        break;
+  private DexEncodedMethod removeMethodHelper(
+      DexMethod method,
+      DexEncodedMethod[] methods,
+      Consumer<DexEncodedMethod[]> newMethodsConsumer) {
+    for (int i = 0; i < methods.length; i++) {
+      if (method.match(methods[i])) {
+        return removeMethodWithIndex(i, methods, newMethodsConsumer);
       }
     }
-    if (index >= 0) {
-      removeDirectMethod(index);
-    }
+    return null;
+  }
+
+  private DexEncodedMethod removeMethodWithIndex(
+      int index, DexEncodedMethod[] methods, Consumer<DexEncodedMethod[]> newMethodsConsumer) {
+    DexEncodedMethod removed = methods[index];
+    DexEncodedMethod[] newMethods = new DexEncodedMethod[methods.length - 1];
+    System.arraycopy(methods, 0, newMethods, 0, index);
+    System.arraycopy(methods, index + 1, newMethods, index, methods.length - index - 1);
+    newMethodsConsumer.accept(newMethods);
+    return removed;
   }
 
   @Override
@@ -243,7 +261,8 @@
       if (method.match(directMethod)) {
         DexEncodedMethod newMethod = replacement.apply(directMethod);
         assert belongsToVirtualPool(newMethod);
-        removeDirectMethod(i);
+        removeMethodWithIndex(
+            i, directMethods, newDirectMethods -> directMethods = newDirectMethods);
         addVirtualMethod(newMethod);
         return newMethod;
       }
diff --git a/src/main/java/com/android/tools/r8/graph/MethodCollection.java b/src/main/java/com/android/tools/r8/graph/MethodCollection.java
index 6fecde6..ed2f612 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodCollection.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodCollection.java
@@ -181,9 +181,16 @@
     backing.addDirectMethods(methods);
   }
 
-  public void removeDirectMethod(DexMethod method) {
-    resetDirectMethodCaches();
-    backing.removeDirectMethod(method);
+  public void removeMethod(DexMethod method) {
+    DexEncodedMethod removed = backing.removeMethod(method);
+    if (removed != null) {
+      if (backing.belongsToDirectPool(removed)) {
+        resetDirectMethodCaches();
+      } else {
+        assert backing.belongsToVirtualPool(removed);
+        resetVirtualMethodCaches();
+      }
+    }
   }
 
   public void setDirectMethods(DexEncodedMethod[] methods) {
diff --git a/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java b/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
index 427f022..913a563 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
@@ -75,7 +75,7 @@
 
   // Removal methods.
 
-  abstract void removeDirectMethod(DexMethod method);
+  abstract DexEncodedMethod removeMethod(DexMethod method);
 
   // Replacement/mutation methods.
 
diff --git a/src/main/java/com/android/tools/r8/graph/MethodMapBacking.java b/src/main/java/com/android/tools/r8/graph/MethodMapBacking.java
index 8afffc6..d03e741 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodMapBacking.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodMapBacking.java
@@ -186,8 +186,8 @@
   }
 
   @Override
-  void removeDirectMethod(DexMethod method) {
-    methodMap.remove(wrap(method));
+  DexEncodedMethod removeMethod(DexMethod method) {
+    return methodMap.remove(wrap(method));
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java
index 3d1c2b5..ffd23cc 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java
@@ -6,6 +6,7 @@
 
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.IRCode;
@@ -157,9 +158,13 @@
 
   public static DexType getRefinedReceiverType(
       AppView<? extends AppInfoWithSubtyping> appView, InvokeMethodWithReceiver invoke) {
-    Value receiver = invoke.getReceiver();
+    return getRefinedReceiverType(appView, invoke.getInvokedMethod(), invoke.getReceiver());
+  }
+
+  public static DexType getRefinedReceiverType(
+      AppView<? extends AppInfoWithSubtyping> appView, DexMethod method, Value receiver) {
     TypeElement lattice = receiver.getDynamicUpperBoundType(appView);
-    DexType staticReceiverType = invoke.getInvokedMethod().holder;
+    DexType staticReceiverType = method.holder;
     if (lattice.isClassType()) {
       ClassTypeElement classType = lattice.asClassType();
       DexType refinedType = classType.getClassType();
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index 53573ac..268c065 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -23,6 +23,7 @@
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.IteratorUtils;
 import com.android.tools.r8.utils.ListUtils;
+import com.android.tools.r8.utils.SetUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
@@ -43,6 +44,7 @@
 import java.util.Map;
 import java.util.Queue;
 import java.util.Set;
+import java.util.function.Function;
 import java.util.function.Predicate;
 import java.util.stream.Collectors;
 import java.util.stream.Stream;
@@ -715,22 +717,39 @@
   }
 
   private boolean consistentPredecessorSuccessors() {
+    Set<BasicBlock> blockSet = SetUtils.newIdentityHashSet(blocks);
+    Map<BasicBlock, Collection<BasicBlock>> predecessorCollections =
+        new IdentityHashMap<>(blocks.size());
+    Map<BasicBlock, Collection<BasicBlock>> successorCollections =
+        new IdentityHashMap<>(blocks.size());
+    Function<Collection<BasicBlock>, Collection<BasicBlock>> optimizeForMembershipQueries =
+        collection -> collection.size() > 5 ? SetUtils.newIdentityHashSet(collection) : collection;
     for (BasicBlock block : blocks) {
-      // Check that all successors are distinct.
-      assert new HashSet<>(block.getSuccessors()).size() == block.getSuccessors().size();
-      for (BasicBlock succ : block.getSuccessors()) {
-        // Check that successors are in the block list.
-        assert blocks.contains(succ);
-        // Check that successors have this block as a predecessor.
-        assert succ.getPredecessors().contains(block);
+      Collection<BasicBlock> predecessors =
+          predecessorCollections.computeIfAbsent(
+              block, key -> optimizeForMembershipQueries.apply(key.getPredecessors()));
+      Collection<BasicBlock> successors =
+          successorCollections.computeIfAbsent(
+              block, key -> optimizeForMembershipQueries.apply(key.getSuccessors()));
+      // Check that all predecessors and successors are distinct.
+      assert predecessors.size() == block.getPredecessors().size();
+      assert successors.size() == block.getSuccessors().size();
+      // Check that predecessors and successors are in the block list.
+      assert blockSet.containsAll(predecessors);
+      assert blockSet.containsAll(successors);
+      // Check that successors have this block as a predecessor.
+      for (BasicBlock succ : successors) {
+        Collection<BasicBlock> succPredecessors =
+            predecessorCollections.computeIfAbsent(
+                succ, key -> optimizeForMembershipQueries.apply(key.getPredecessors()));
+        assert succPredecessors.contains(block);
       }
-      // Check that all predecessors are distinct.
-      assert new HashSet<>(block.getPredecessors()).size() == block.getPredecessors().size();
-      for (BasicBlock pred : block.getPredecessors()) {
-        // Check that predecessors are in the block list.
-        assert blocks.contains(pred);
-        // Check that predecessors have this block as a successor.
-        assert pred.getSuccessors().contains(block);
+      // Check that predecessors have this block as a successor.
+      for (BasicBlock pred : predecessors) {
+        Collection<BasicBlock> predSuccessors =
+            successorCollections.computeIfAbsent(
+                pred, key -> optimizeForMembershipQueries.apply(key.getSuccessors()));
+        assert predSuccessors.contains(block);
       }
     }
     return true;
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java b/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java
index c30a8cb..92eb384 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeVirtual.java
@@ -91,26 +91,31 @@
 
   @Override
   public DexEncodedMethod lookupSingleTarget(AppView<?> appView, DexType invocationContext) {
+    return lookupSingleTarget(appView, invocationContext, getInvokedMethod(), getReceiver());
+  }
+
+  public static DexEncodedMethod lookupSingleTarget(
+      AppView<?> appView, DexType invocationContext, DexMethod method, Value receiver) {
     if (appView.appInfo().hasLiveness()) {
       AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
       return appViewWithLiveness
           .appInfo()
           .lookupSingleVirtualTarget(
-              getInvokedMethod(),
+              method,
               invocationContext,
               false,
               appView,
-              TypeAnalysis.getRefinedReceiverType(appViewWithLiveness, this),
-              getReceiver().getDynamicLowerBoundType(appViewWithLiveness));
+              TypeAnalysis.getRefinedReceiverType(appViewWithLiveness, method, receiver),
+              receiver.getDynamicLowerBoundType(appViewWithLiveness));
     }
     // In D8, allow lookupSingleTarget() to be used for finding final library methods. This is used
     // for library modeling.
-    DexType holder = getInvokedMethod().holder;
+    DexType holder = method.holder;
     if (holder.isClassType()) {
       DexClass clazz = appView.definitionFor(holder);
       if (clazz != null
           && (clazz.isLibraryClass() || appView.libraryMethodOptimizer().isModeled(clazz.type))) {
-        DexEncodedMethod singleTargetCandidate = appView.definitionFor(getInvokedMethod());
+        DexEncodedMethod singleTargetCandidate = appView.definitionFor(method);
         if (singleTargetCandidate != null && (clazz.isFinal() || singleTargetCandidate.isFinal())) {
           return singleTargetCandidate;
         }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Value.java b/src/main/java/com/android/tools/r8/ir/code/Value.java
index 57c923c..ca2cdd4 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Value.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Value.java
@@ -440,6 +440,10 @@
     return uniqueUsers = ImmutableSet.copyOf(users);
   }
 
+  public boolean hasSingleUniqueUser() {
+    return uniqueUsers().size() == 1;
+  }
+
   public Instruction singleUniqueUser() {
     assert ImmutableSet.copyOf(users).size() == 1;
     return users.getFirst();
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index 1b78ff7..6550178 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.conversion;
 
+import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
 import static com.android.tools.r8.ir.desugar.InterfaceMethodRewriter.Flavor.ExcludeDexResources;
 import static com.android.tools.r8.ir.desugar.InterfaceMethodRewriter.Flavor.IncludeAllResources;
 
@@ -725,7 +726,8 @@
     }
     if (enumUnboxer != null) {
       enumUnboxer.finishAnalysis();
-      enumUnboxer.unboxEnums(postMethodProcessorBuilder, executorService, feedback);
+      enumUnboxer.unboxEnums(
+          postMethodProcessorBuilder, executorService, feedback, classStaticizer);
     }
     new TrivialFieldAccessReprocessor(appView.withLiveness(), postMethodProcessorBuilder)
         .run(executorService, feedback, timing);
@@ -1122,6 +1124,9 @@
   private Timing optimize(
       IRCode code, OptimizationFeedback feedback, MethodProcessor methodProcessor) {
     DexEncodedMethod method = code.method;
+    DexProgramClass holder = asProgramClassOrNull(appView.definitionForHolder(method));
+    assert holder != null;
+
     Timing timing = Timing.create(method.qualifiedName(), options);
 
     if (Log.ENABLED) {
@@ -1280,7 +1285,7 @@
     if (devirtualizer != null) {
       assert code.verifyTypes(appView);
       timing.begin("Devirtualize invoke interface");
-      devirtualizer.devirtualizeInvokeInterface(code, method.holder());
+      devirtualizer.devirtualizeInvokeInterface(code, holder);
       timing.end();
     }
 
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/MethodOptimizationFeedback.java b/src/main/java/com/android/tools/r8/ir/conversion/MethodOptimizationFeedback.java
index 8982b5a..7211439 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/MethodOptimizationFeedback.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/MethodOptimizationFeedback.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.classinliner.ClassInlinerEligibilityInfo;
 import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo;
+import com.android.tools.r8.ir.optimize.info.bridge.BridgeInfo;
 import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.BitSet;
@@ -55,6 +56,8 @@
 
   void markTriggerClassInitBeforeAnySideEffect(DexEncodedMethod method, boolean mark);
 
+  void setBridgeInfo(DexEncodedMethod method, BridgeInfo bridgeInfo);
+
   void setClassInlinerEligibility(DexEncodedMethod method, ClassInlinerEligibilityInfo eligibility);
 
   void setInstanceInitializerInfo(
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 85b98ba..4236e52 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
@@ -174,7 +174,7 @@
   /** Remove lambda deserialization methods. */
   public void removeLambdaDeserializationMethods(Iterable<DexProgramClass> classes) {
     for (DexProgramClass clazz : classes) {
-      clazz.removeDirectMethod(getFactory().deserializeLambdaMethod);
+      clazz.removeMethod(getFactory().deserializeLambdaMethod);
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/AssertionsRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/AssertionsRewriter.java
index 68453b8..81b43ef 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/AssertionsRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/AssertionsRewriter.java
@@ -345,7 +345,8 @@
         }
       } else if (current.isStaticPut()) {
         StaticPut staticPut = current.asStaticPut();
-        if (staticPut.getField().name == dexItemFactory.assertionsDisabled) {
+        if (isInitializerEnablingJavaVmAssertions
+            && staticPut.getField().name == dexItemFactory.assertionsDisabled) {
           iterator.remove();
         }
       } else if (current.isStaticGet()) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
index 897b85b..0366798 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
@@ -7,6 +7,7 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.ResolutionResult;
 import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
@@ -19,8 +20,8 @@
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionListIterator;
-import com.android.tools.r8.ir.code.Invoke;
 import com.android.tools.r8.ir.code.InvokeInterface;
+import com.android.tools.r8.ir.code.InvokeSuper;
 import com.android.tools.r8.ir.code.InvokeVirtual;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
@@ -51,7 +52,7 @@
     this.appView = appView;
   }
 
-  public void devirtualizeInvokeInterface(IRCode code, DexType invocationContext) {
+  public void devirtualizeInvokeInterface(IRCode code, DexProgramClass context) {
     Set<Value> affectedValues = Sets.newIdentityHashSet();
     Map<InvokeInterface, InvokeVirtual> devirtualizedCall = new IdentityHashMap<>();
     DominatorTree dominatorTree = new DominatorTree(code);
@@ -114,25 +115,43 @@
           }
         }
 
+        if (appView.options().testing.enableInvokeSuperToInvokeVirtualRewriting) {
+          if (current.isInvokeSuper()) {
+            InvokeSuper invoke = current.asInvokeSuper();
+            DexEncodedMethod singleTarget = invoke.lookupSingleTarget(appView, context.type);
+            if (singleTarget != null) {
+              DexClass holder = appView.definitionForHolder(singleTarget);
+              assert holder != null;
+              DexMethod invokedMethod = invoke.getInvokedMethod();
+              DexEncodedMethod newSingleTarget =
+                  InvokeVirtual.lookupSingleTarget(
+                      appView, context.type, invokedMethod, invoke.getReceiver());
+              if (newSingleTarget == singleTarget) {
+                it.replaceCurrentInstruction(
+                    new InvokeVirtual(invokedMethod, invoke.outValue(), invoke.arguments()));
+              }
+            }
+            continue;
+          }
+        }
+
         if (current.isInvokeVirtual()) {
           InvokeVirtual invoke = current.asInvokeVirtual();
           DexMethod invokedMethod = invoke.getInvokedMethod();
           DexMethod reboundTarget =
-              rebindVirtualInvokeToMostSpecific(
-                  invokedMethod, invoke.getReceiver(), invocationContext);
+              rebindVirtualInvokeToMostSpecific(invokedMethod, invoke.getReceiver(), context.type);
           if (reboundTarget != invokedMethod) {
-            Invoke newInvoke =
-                Invoke.create(
-                    Invoke.Type.VIRTUAL, reboundTarget, null, invoke.outValue(), invoke.inValues());
-            it.replaceCurrentInstruction(newInvoke);
+            it.replaceCurrentInstruction(
+                new InvokeVirtual(reboundTarget, invoke.outValue(), invoke.arguments()));
           }
+          continue;
         }
 
         if (!current.isInvokeInterface()) {
           continue;
         }
         InvokeInterface invoke = current.asInvokeInterface();
-        DexEncodedMethod target = invoke.lookupSingleTarget(appView, invocationContext);
+        DexEncodedMethod target = invoke.lookupSingleTarget(appView, context.type);
         if (target == null) {
           continue;
         }
@@ -144,7 +163,7 @@
         }
         // Due to the potential downcast below, make sure the new target holder is visible.
         ConstraintWithTarget visibility =
-            ConstraintWithTarget.classIsVisible(invocationContext, holderType, appView);
+            ConstraintWithTarget.classIsVisible(context.type, holderType, appView);
         if (visibility == ConstraintWithTarget.NEVER) {
           continue;
         }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
index 40f9b7f..d579a34 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
@@ -6,6 +6,7 @@
 import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
 import static com.google.common.base.Predicates.not;
 
+import com.android.tools.r8.androidapi.AvailableApiExceptions;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AccessFlags;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
@@ -87,6 +88,8 @@
   private final Set<DexEncodedMethod> doubleInlineSelectedTargets = Sets.newIdentityHashSet();
   private final Map<DexEncodedMethod, DexEncodedMethod> doubleInlineeCandidates = new HashMap<>();
 
+  private final AvailableApiExceptions availableApiExceptions;
+
   public Inliner(
       AppView<AppInfoWithLiveness> appView,
       MainDexClasses mainDexClasses,
@@ -101,6 +104,10 @@
     this.lambdaMerger = lambdaMerger;
     this.lensCodeRewriter = lensCodeRewriter;
     this.mainDexClasses = mainDexClasses;
+    availableApiExceptions =
+        appView.options().canHaveDalvikCatchHandlerVerificationBug()
+            ? new AvailableApiExceptions(appView.options())
+            : null;
   }
 
   boolean isBlacklisted(
@@ -145,8 +152,7 @@
   }
 
   public ConstraintWithTarget computeInliningConstraint(IRCode code, DexEncodedMethod method) {
-    if (appView.options().canHaveDalvikCatchHandlerVerificationBug()
-        && useReflectiveOperationExceptionOrUnknownClassInCatch(code)) {
+    if (containsPotentialCatchHandlerVerificationError(code)) {
       return ConstraintWithTarget.NEVER;
     }
 
@@ -1076,13 +1082,16 @@
     assert code.isConsistentSSA();
   }
 
-  private boolean useReflectiveOperationExceptionOrUnknownClassInCatch(IRCode code) {
+  private boolean containsPotentialCatchHandlerVerificationError(IRCode code) {
+    if (availableApiExceptions == null) {
+      assert !appView.options().canHaveDalvikCatchHandlerVerificationBug();
+      return false;
+    }
     for (BasicBlock block : code.blocks) {
       for (CatchHandler<BasicBlock> catchHandler : block.getCatchHandlers()) {
-        if (catchHandler.guard == appView.dexItemFactory().reflectiveOperationExceptionType) {
-          return true;
-        }
-        if (appView.definitionFor(catchHandler.guard) == null) {
+        DexClass clazz = appView.definitionFor(catchHandler.guard);
+        if ((clazz == null || clazz.isLibraryClass())
+            && availableApiExceptions.canCauseVerificationError(catchHandler.guard)) {
           return true;
         }
       }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/RedundantFieldLoadElimination.java b/src/main/java/com/android/tools/r8/ir/optimize/RedundantFieldLoadElimination.java
index e25949d..a7e4875 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/RedundantFieldLoadElimination.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/RedundantFieldLoadElimination.java
@@ -34,11 +34,12 @@
 import com.google.common.collect.Sets;
 import it.unimi.dsi.fastutil.objects.Reference2IntMap;
 import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
-import java.util.ArrayDeque;
-import java.util.Deque;
-import java.util.HashMap;
-import java.util.IdentityHashMap;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Set;
 
 /**
@@ -47,9 +48,11 @@
  * <p>Simple algorithm that goes through all blocks in one pass in topological order and propagates
  * active field sets across control-flow edges where the target has only one predecessor.
  */
-// TODO(ager): Evaluate speed/size for computing active field sets in a fixed-point computation.
 public class RedundantFieldLoadElimination {
 
+  private static final int MAX_CAPACITY = 10000;
+  private static final int MAX_CAPACITY_PER_BLOCK = 50;
+
   private final AppView<?> appView;
   private final DexEncodedMethod method;
   private final IRCode code;
@@ -58,11 +61,11 @@
   private final Set<Value> affectedValues = Sets.newIdentityHashSet();
 
   // Maps keeping track of fields that have an already loaded value at basic block entry.
-  private final Map<BasicBlock, State> activeStateAtExit = new IdentityHashMap<>();
+  private final BlockStates activeStates = new BlockStates();
 
   // Maps keeping track of fields with already loaded values for the current block during
   // elimination.
-  private State activeState;
+  private BlockState activeState;
 
   public RedundantFieldLoadElimination(AppView<?> appView, IRCode code) {
     this.appView = appView;
@@ -72,9 +75,7 @@
 
   public static boolean shouldRun(AppView<?> appView, IRCode code) {
     return appView.options().enableRedundantFieldLoadElimination
-        && (code.metadata().mayHaveFieldGet() || code.metadata().mayHaveInitClass())
-        // TODO(b/154064966): Remove workaround.
-        && code.blocks.size() < 20000;
+        && (code.metadata().mayHaveFieldGet() || code.metadata().mayHaveInitClass());
   }
 
   private interface FieldValue {
@@ -162,18 +163,18 @@
     DexType context = method.holder();
     Reference2IntMap<BasicBlock> pendingNormalSuccessors = new Reference2IntOpenHashMap<>();
     for (BasicBlock block : code.blocks) {
-      if (!block.hasUniqueSuccessor()) {
+      if (!block.hasUniqueNormalSuccessor()) {
         pendingNormalSuccessors.put(block, block.numberOfNormalSuccessors());
       }
     }
 
-    Set<BasicBlock> visited = Sets.newIdentityHashSet();
     for (BasicBlock head : code.topologicallySortedBlocks()) {
-      if (!visited.add(head)) {
+      if (head.hasUniquePredecessor() && head.getUniquePredecessor().hasUniqueNormalSuccessor()) {
+        // Already visited.
         continue;
       }
-      computeActiveStateOnBlockEntry(head);
-      removeDeadBlockExitStates(head, pendingNormalSuccessors);
+      activeState = activeStates.computeActiveStateOnBlockEntry(head);
+      activeStates.removeDeadBlockExitStates(head, pendingNormalSuccessors);
       BasicBlock block = head;
       BasicBlock end = null;
       do {
@@ -314,15 +315,13 @@
         }
         if (block.hasUniqueNormalSuccessorWithUniquePredecessor()) {
           block = block.getUniqueNormalSuccessor();
-          assert !visited.contains(block);
-          visited.add(block);
         } else {
           end = block;
           block = null;
         }
       } while (block != null);
       assert end != null;
-      recordActiveStateOnBlockExit(end);
+      activeStates.recordActiveStateOnBlockExit(end, activeState);
     }
     if (!affectedValues.isEmpty()) {
       new TypeAnalysis(appView).narrowing(affectedValues);
@@ -386,66 +385,6 @@
         });
   }
 
-  private void computeActiveStateOnBlockEntry(BasicBlock block) {
-    if (block.isEntry()) {
-      activeState = new State();
-      return;
-    }
-    Deque<State> predecessorExitStates = new ArrayDeque<>(block.getPredecessors().size());
-    for (BasicBlock predecessor : block.getPredecessors()) {
-      State predecessorExitState = activeStateAtExit.get(predecessor);
-      if (predecessorExitState == null) {
-        // Not processed yet.
-        activeState = new State();
-        return;
-      }
-      // Allow propagation across exceptional edges, just be careful not to propagate if the
-      // throwing instruction is a field instruction.
-      if (predecessor.hasCatchSuccessor(block)) {
-        Instruction exceptionalExit = predecessor.exceptionalExit();
-        if (exceptionalExit != null) {
-          predecessorExitState = new State(predecessorExitState);
-          if (exceptionalExit.isFieldInstruction()) {
-            predecessorExitState.killActiveFieldsForExceptionalExit(
-                exceptionalExit.asFieldInstruction());
-          } else if (exceptionalExit.isInitClass()) {
-            predecessorExitState.killActiveInitializedClassesForExceptionalExit(
-                exceptionalExit.asInitClass());
-          }
-        }
-      }
-      predecessorExitStates.addLast(predecessorExitState);
-    }
-    State state = new State(predecessorExitStates.removeFirst());
-    predecessorExitStates.forEach(state::intersect);
-    activeState = state;
-  }
-
-  private void removeDeadBlockExitStates(
-      BasicBlock current, Reference2IntMap<BasicBlock> pendingNormalSuccessorsMap) {
-    for (BasicBlock predecessor : current.getPredecessors()) {
-      if (predecessor.hasUniqueSuccessor()) {
-        activeStateAtExit.remove(predecessor);
-      } else {
-        if (predecessor.hasNormalSuccessor(current)) {
-          int pendingNormalSuccessors = pendingNormalSuccessorsMap.getInt(predecessor) - 1;
-          if (pendingNormalSuccessors == 0) {
-            activeStateAtExit.remove(predecessor);
-          } else {
-            pendingNormalSuccessorsMap.put(predecessor, pendingNormalSuccessors);
-          }
-        }
-      }
-    }
-  }
-
-  private void recordActiveStateOnBlockExit(BasicBlock block) {
-    assert !activeStateAtExit.containsKey(block);
-    if (!activeState.isEmpty()) {
-      activeStateAtExit.put(block, activeState);
-    }
-  }
-
   private void killAllNonFinalActiveFields() {
     activeState.clearNonFinalInstanceFields();
     activeState.clearNonFinalStaticFields();
@@ -476,41 +415,162 @@
     }
   }
 
-  static class State {
+  static class BlockStates {
 
-    private Map<FieldAndObject, FieldValue> finalInstanceFieldValues;
+    // Maps keeping track of fields that have an already loaded value at basic block entry.
+    private final LinkedHashMap<BasicBlock, BlockState> activeStateAtExit = new LinkedHashMap<>();
 
-    private Map<DexField, FieldValue> finalStaticFieldValues;
+    private int capacity = MAX_CAPACITY;
 
-    private Set<DexType> initializedClasses;
-
-    private Map<FieldAndObject, FieldValue> nonFinalInstanceFieldValues;
-
-    private Map<DexField, FieldValue> nonFinalStaticFieldValues;
-
-    public State() {}
-
-    public State(State state) {
-      if (state.finalInstanceFieldValues != null && !state.finalInstanceFieldValues.isEmpty()) {
-        finalInstanceFieldValues = new HashMap<>();
-        finalInstanceFieldValues.putAll(state.finalInstanceFieldValues);
+    BlockState computeActiveStateOnBlockEntry(BasicBlock block) {
+      if (block.isEntry()) {
+        return new BlockState();
       }
-      if (state.finalStaticFieldValues != null && !state.finalStaticFieldValues.isEmpty()) {
-        finalStaticFieldValues = new IdentityHashMap<>();
-        finalStaticFieldValues.putAll(state.finalStaticFieldValues);
+      List<BasicBlock> predecessors = block.getPredecessors();
+      Iterator<BasicBlock> predecessorIterator = predecessors.iterator();
+      BlockState state = new BlockState(activeStateAtExit.get(predecessorIterator.next()));
+      while (predecessorIterator.hasNext()) {
+        BasicBlock predecessor = predecessorIterator.next();
+        BlockState predecessorExitState = activeStateAtExit.get(predecessor);
+        if (predecessorExitState == null) {
+          // Not processed yet.
+          return new BlockState();
+        }
+        state.intersect(predecessorExitState);
       }
-      if (state.initializedClasses != null && !state.initializedClasses.isEmpty()) {
-        initializedClasses = Sets.newIdentityHashSet();
-        initializedClasses.addAll(state.initializedClasses);
+      // Allow propagation across exceptional edges, just be careful not to propagate if the
+      // throwing instruction is a field instruction.
+      for (BasicBlock predecessor : predecessors) {
+        if (predecessor.hasCatchSuccessor(block)) {
+          Instruction exceptionalExit = predecessor.exceptionalExit();
+          if (exceptionalExit != null) {
+            if (exceptionalExit.isFieldInstruction()) {
+              state.killActiveFieldsForExceptionalExit(exceptionalExit.asFieldInstruction());
+            } else if (exceptionalExit.isInitClass()) {
+              state.killActiveInitializedClassesForExceptionalExit(exceptionalExit.asInitClass());
+            }
+          }
+        }
       }
-      if (state.nonFinalInstanceFieldValues != null
-          && !state.nonFinalInstanceFieldValues.isEmpty()) {
-        nonFinalInstanceFieldValues = new HashMap<>();
-        nonFinalInstanceFieldValues.putAll(state.nonFinalInstanceFieldValues);
+      return state;
+    }
+
+    private void ensureCapacity(BlockState state) {
+      int stateSize = state.size();
+      assert stateSize <= MAX_CAPACITY_PER_BLOCK;
+      int numberOfItemsToRemove = stateSize - capacity;
+      if (numberOfItemsToRemove <= 0) {
+        return;
       }
-      if (state.nonFinalStaticFieldValues != null && !state.nonFinalStaticFieldValues.isEmpty()) {
-        nonFinalStaticFieldValues = new IdentityHashMap<>();
-        nonFinalStaticFieldValues.putAll(state.nonFinalStaticFieldValues);
+      Iterator<Entry<BasicBlock, BlockState>> iterator = activeStateAtExit.entrySet().iterator();
+      while (iterator.hasNext() && numberOfItemsToRemove > 0) {
+        Entry<BasicBlock, BlockState> entry = iterator.next();
+        BlockState existingState = entry.getValue();
+        int existingStateSize = existingState.size();
+        assert existingStateSize > 0;
+        if (existingStateSize <= numberOfItemsToRemove) {
+          iterator.remove();
+          capacity += existingStateSize;
+          numberOfItemsToRemove -= existingStateSize;
+        } else {
+          existingState.reduceSize(numberOfItemsToRemove);
+          capacity += numberOfItemsToRemove;
+          numberOfItemsToRemove = 0;
+        }
+      }
+      if (numberOfItemsToRemove > 0) {
+        state.reduceSize(numberOfItemsToRemove);
+      }
+      assert capacity == MAX_CAPACITY - size();
+    }
+
+    void removeDeadBlockExitStates(
+        BasicBlock current, Reference2IntMap<BasicBlock> pendingNormalSuccessorsMap) {
+      for (BasicBlock predecessor : current.getPredecessors()) {
+        if (predecessor.hasUniqueSuccessor()) {
+          removeState(predecessor);
+        } else {
+          if (predecessor.hasNormalSuccessor(current)) {
+            int pendingNormalSuccessors = pendingNormalSuccessorsMap.getInt(predecessor) - 1;
+            if (pendingNormalSuccessors == 0) {
+              pendingNormalSuccessorsMap.removeInt(predecessor);
+              removeState(predecessor);
+            } else {
+              pendingNormalSuccessorsMap.put(predecessor, pendingNormalSuccessors);
+            }
+          }
+        }
+      }
+    }
+
+    void recordActiveStateOnBlockExit(BasicBlock block, BlockState state) {
+      assert !activeStateAtExit.containsKey(block);
+      if (state.isEmpty()) {
+        return;
+      }
+      ensureCapacity(state);
+      activeStateAtExit.put(block, state);
+      capacity -= state.size();
+      assert capacity >= 0;
+    }
+
+    private void removeState(BasicBlock block) {
+      BlockState state = activeStateAtExit.remove(block);
+      if (state != null) {
+        int stateSize = state.size();
+        assert stateSize > 0;
+        capacity += stateSize;
+      }
+    }
+
+    private int size() {
+      int size = 0;
+      for (BlockState state : activeStateAtExit.values()) {
+        int stateSize = state.size();
+        assert stateSize > 0;
+        size += stateSize;
+      }
+      return size;
+    }
+  }
+
+  static class BlockState {
+
+    private LinkedHashMap<FieldAndObject, FieldValue> finalInstanceFieldValues;
+
+    private LinkedHashMap<DexField, FieldValue> finalStaticFieldValues;
+
+    private LinkedHashSet<DexType> initializedClasses;
+
+    private LinkedHashMap<FieldAndObject, FieldValue> nonFinalInstanceFieldValues;
+
+    private LinkedHashMap<DexField, FieldValue> nonFinalStaticFieldValues;
+
+    public BlockState() {}
+
+    public BlockState(BlockState state) {
+      if (state != null) {
+        if (state.finalInstanceFieldValues != null && !state.finalInstanceFieldValues.isEmpty()) {
+          finalInstanceFieldValues = new LinkedHashMap<>();
+          finalInstanceFieldValues.putAll(state.finalInstanceFieldValues);
+        }
+        if (state.finalStaticFieldValues != null && !state.finalStaticFieldValues.isEmpty()) {
+          finalStaticFieldValues = new LinkedHashMap<>();
+          finalStaticFieldValues.putAll(state.finalStaticFieldValues);
+        }
+        if (state.initializedClasses != null && !state.initializedClasses.isEmpty()) {
+          initializedClasses = new LinkedHashSet<>();
+          initializedClasses.addAll(state.initializedClasses);
+        }
+        if (state.nonFinalInstanceFieldValues != null
+            && !state.nonFinalInstanceFieldValues.isEmpty()) {
+          nonFinalInstanceFieldValues = new LinkedHashMap<>();
+          nonFinalInstanceFieldValues.putAll(state.nonFinalInstanceFieldValues);
+        }
+        if (state.nonFinalStaticFieldValues != null && !state.nonFinalStaticFieldValues.isEmpty()) {
+          nonFinalStaticFieldValues = new LinkedHashMap<>();
+          nonFinalStaticFieldValues.putAll(state.nonFinalStaticFieldValues);
+        }
       }
     }
 
@@ -522,6 +582,14 @@
       nonFinalStaticFieldValues = null;
     }
 
+    public void ensureCapacityForNewElement() {
+      int size = size();
+      assert size <= MAX_CAPACITY_PER_BLOCK;
+      if (size == MAX_CAPACITY_PER_BLOCK) {
+        reduceSize(1);
+      }
+    }
+
     public FieldValue getInstanceFieldValue(FieldAndObject field) {
       FieldValue value =
           nonFinalInstanceFieldValues != null ? nonFinalInstanceFieldValues.get(field) : null;
@@ -540,7 +608,7 @@
       return finalStaticFieldValues != null ? finalStaticFieldValues.get(field) : null;
     }
 
-    public void intersect(State state) {
+    public void intersect(BlockState state) {
       if (finalInstanceFieldValues != null && state.finalInstanceFieldValues != null) {
         intersectFieldValues(finalInstanceFieldValues, state.finalInstanceFieldValues);
       } else {
@@ -619,12 +687,41 @@
     }
 
     public void markClassAsInitialized(DexType clazz) {
+      ensureCapacityForNewElement();
       if (initializedClasses == null) {
-        initializedClasses = Sets.newIdentityHashSet();
+        initializedClasses = new LinkedHashSet<>();
       }
       initializedClasses.add(clazz);
     }
 
+    public void reduceSize(int numberOfItemsToRemove) {
+      assert numberOfItemsToRemove > 0;
+      assert numberOfItemsToRemove < size();
+      numberOfItemsToRemove = reduceSize(numberOfItemsToRemove, initializedClasses);
+      numberOfItemsToRemove = reduceSize(numberOfItemsToRemove, nonFinalInstanceFieldValues);
+      numberOfItemsToRemove = reduceSize(numberOfItemsToRemove, nonFinalStaticFieldValues);
+      numberOfItemsToRemove = reduceSize(numberOfItemsToRemove, finalInstanceFieldValues);
+      numberOfItemsToRemove = reduceSize(numberOfItemsToRemove, finalStaticFieldValues);
+      assert numberOfItemsToRemove == 0;
+    }
+
+    private static int reduceSize(int numberOfItemsToRemove, Set<?> set) {
+      if (set == null || numberOfItemsToRemove == 0) {
+        return numberOfItemsToRemove;
+      }
+      Iterator<?> iterator = set.iterator();
+      while (iterator.hasNext() && numberOfItemsToRemove > 0) {
+        iterator.next();
+        iterator.remove();
+        numberOfItemsToRemove--;
+      }
+      return numberOfItemsToRemove;
+    }
+
+    private static int reduceSize(int numberOfItemsToRemove, Map<?, ?> map) {
+      return reduceSize(numberOfItemsToRemove, map != null ? map.keySet() : null);
+    }
+
     public void removeInstanceField(FieldAndObject field) {
       removeFinalInstanceField(field);
       removeNonFinalInstanceField(field);
@@ -666,33 +763,53 @@
     }
 
     public void putFinalInstanceField(FieldAndObject field, FieldValue value) {
+      ensureCapacityForNewElement();
       if (finalInstanceFieldValues == null) {
-        finalInstanceFieldValues = new HashMap<>();
+        finalInstanceFieldValues = new LinkedHashMap<>();
       }
       finalInstanceFieldValues.put(field, value);
     }
 
     public void putFinalStaticField(DexField field, FieldValue value) {
+      ensureCapacityForNewElement();
       if (finalStaticFieldValues == null) {
-        finalStaticFieldValues = new IdentityHashMap<>();
+        finalStaticFieldValues = new LinkedHashMap<>();
       }
       finalStaticFieldValues.put(field, value);
     }
 
     public void putNonFinalInstanceField(FieldAndObject field, FieldValue value) {
+      ensureCapacityForNewElement();
       assert finalInstanceFieldValues == null || !finalInstanceFieldValues.containsKey(field);
       if (nonFinalInstanceFieldValues == null) {
-        nonFinalInstanceFieldValues = new HashMap<>();
+        nonFinalInstanceFieldValues = new LinkedHashMap<>();
       }
       nonFinalInstanceFieldValues.put(field, value);
     }
 
     public void putNonFinalStaticField(DexField field, FieldValue value) {
+      ensureCapacityForNewElement();
       assert nonFinalStaticFieldValues == null || !nonFinalStaticFieldValues.containsKey(field);
       if (nonFinalStaticFieldValues == null) {
-        nonFinalStaticFieldValues = new IdentityHashMap<>();
+        nonFinalStaticFieldValues = new LinkedHashMap<>();
       }
       nonFinalStaticFieldValues.put(field, value);
     }
+
+    public int size() {
+      return size(finalInstanceFieldValues)
+          + size(finalStaticFieldValues)
+          + size(initializedClasses)
+          + size(nonFinalInstanceFieldValues)
+          + size(nonFinalStaticFieldValues);
+    }
+
+    private static int size(Set<?> set) {
+      return set != null ? set.size() : 0;
+    }
+
+    private static int size(Map<?, ?> map) {
+      return map != null ? map.size() : 0;
+    }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxer.java b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxer.java
index 6a91188..0a35a6f 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxer.java
@@ -48,6 +48,7 @@
 import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
 import com.android.tools.r8.ir.optimize.info.OptimizationFeedback.OptimizationInfoFixer;
 import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackDelayed;
+import com.android.tools.r8.ir.optimize.staticizer.ClassStaticizer;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.BooleanUtils;
 import com.android.tools.r8.utils.Reporter;
@@ -283,7 +284,8 @@
   public void unboxEnums(
       PostMethodProcessor.Builder postBuilder,
       ExecutorService executorService,
-      OptimizationFeedbackDelayed feedback)
+      OptimizationFeedbackDelayed feedback,
+      ClassStaticizer classStaticizer)
       throws ExecutionException {
     // At this point the enumsToUnbox are no longer candidates, they will all be unboxed.
     if (enumsUnboxingCandidates.isEmpty()) {
@@ -299,7 +301,7 @@
           appView
               .appInfo()
               .rewrittenWithLens(appView.appInfo().app().asDirect(), enumUnboxingLens));
-
+      classStaticizer.filterCandidates();
       // Update optimization info.
       feedback.fixupOptimizationInfos(
           appView,
@@ -659,7 +661,21 @@
       for (DexProgramClass clazz : appView.appInfo().classes()) {
         if (enumsToUnbox.contains(clazz.type)) {
           assert clazz.instanceFields().size() == 0;
-          clearEnumToUnboxMethods(clazz);
+          // TODO(b/150370354): Remove when static methods are supported.
+          if (appView.options().testing.enumUnboxingRewriteJavaCGeneratedMethod) {
+            // Clear only the initializers.
+            clazz
+                .methods()
+                .forEach(
+                    m -> {
+                      if (m.isInitializer()) {
+                        clearEnumToUnboxMethod(m);
+                      }
+                    });
+            clazz.getMethodCollection().replaceMethods(this::fixupMethod);
+          } else {
+            clazz.methods().forEach(this::clearEnumToUnboxMethod);
+          }
         } else {
           clazz.getMethodCollection().replaceMethods(this::fixupMethod);
           fixupFields(clazz.staticFields(), clazz::setStaticField);
@@ -672,19 +688,17 @@
       return lensBuilder.build(factory, appView.graphLense());
     }
 
-    private void clearEnumToUnboxMethods(DexProgramClass clazz) {
+    private void clearEnumToUnboxMethod(DexEncodedMethod enumMethod) {
       // The compiler may have references to the enum methods, but such methods will be removed
       // and they cannot be reprocessed since their rewriting through the lensCodeRewriter/
       // enumUnboxerRewriter will generate invalid code.
       // To work around this problem we clear such methods, i.e., we replace the code object by
       // an empty throwing code object, so reprocessing won't take time and will be valid.
-      for (DexEncodedMethod method : clazz.methods()) {
-        method.setCode(
-            appView.options().isGeneratingClassFiles()
-                ? method.buildEmptyThrowingCfCode()
-                : method.buildEmptyThrowingDexCode(),
-            appView);
-      }
+      enumMethod.setCode(
+          appView.options().isGeneratingClassFiles()
+              ? enumMethod.buildEmptyThrowingCfCode()
+              : enumMethod.buildEmptyThrowingDexCode(),
+          appView);
     }
 
     private DexEncodedMethod fixupMethod(DexEncodedMethod encodedMethod) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingRewriter.java
index 6ba4154..7b91c7e 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingRewriter.java
@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.ir.optimize.enums;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.CfCode;
@@ -12,6 +14,7 @@
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
@@ -20,6 +23,7 @@
 import com.android.tools.r8.graph.EnumValueInfoMapCollection;
 import com.android.tools.r8.graph.EnumValueInfoMapCollection.EnumValueInfo;
 import com.android.tools.r8.graph.EnumValueInfoMapCollection.EnumValueInfoMap;
+import com.android.tools.r8.graph.FieldAccessFlags;
 import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.graph.ParameterAnnotationsList;
 import com.android.tools.r8.ir.analysis.type.ArrayTypeElement;
@@ -38,8 +42,10 @@
 import com.android.tools.r8.ir.synthetic.EnumUnboxingCfCodeProvider;
 import com.android.tools.r8.origin.SynthesizedOrigin;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collections;
 import java.util.List;
 import java.util.Map;
@@ -51,17 +57,22 @@
 public class EnumUnboxingRewriter {
 
   public static final String ENUM_UNBOXING_UTILITY_CLASS_NAME = "$r8$EnumUnboxingUtility";
+  public static final String ENUM_UNBOXING_UTILITY_ORDINAL = "$enumboxing$ordinal";
+  private static final String ENUM_UNBOXING_UTILITY_VALUES = "$enumboxing$values";
   private static final int REQUIRED_CLASS_FILE_VERSION = 52;
 
   private final AppView<AppInfoWithLiveness> appView;
   private final DexItemFactory factory;
   private final EnumValueInfoMapCollection enumsToUnbox;
-  private final Map<DexMethod, DexType> extraMethods = new ConcurrentHashMap<>();
+  private final Map<DexMethod, DexEncodedMethod> extraUtilityMethods = new ConcurrentHashMap<>();
+  private final Map<DexField, DexEncodedField> extraUtilityFields = new ConcurrentHashMap<>();
 
   private final DexType utilityClassType;
   private final DexMethod ordinalUtilityMethod;
+  private final DexMethod valuesUtilityMethod;
 
   private boolean requiresOrdinalUtilityMethod = false;
+  private boolean requiresValuesUtilityMethod = false;
 
   EnumUnboxingRewriter(AppView<AppInfoWithLiveness> appView, Set<DexType> enumsToUnbox) {
     this.appView = appView;
@@ -77,7 +88,12 @@
         factory.createMethod(
             utilityClassType,
             factory.createProto(factory.intType, factory.intType),
-            "$enumboxing$ordinal");
+            ENUM_UNBOXING_UTILITY_ORDINAL);
+    this.valuesUtilityMethod =
+        factory.createMethod(
+            utilityClassType,
+            factory.createProto(factory.intArrayType, factory.intType),
+            ENUM_UNBOXING_UTILITY_VALUES);
   }
 
   public EnumValueInfoMapCollection getEnumsToUnbox() {
@@ -146,12 +162,28 @@
           }
           EnumValueInfoMap enumValueInfoMap = enumsToUnbox.getEnumValueInfoMap(holder);
           assert enumValueInfoMap != null;
-          // Replace by ordinal + 1 for null check (null is 0).
-          EnumValueInfo enumValueInfo = enumValueInfoMap.getEnumValueInfo(staticGet.getField());
-          assert enumValueInfo != null
-              : "Invalid read to " + staticGet.getField().name + ", error during enum analysis";
           affectedPhis.addAll(staticGet.outValue().uniquePhiUsers());
-          iterator.replaceCurrentInstruction(code.createIntConstant(enumValueInfo.convertToInt()));
+          EnumValueInfo enumValueInfo = enumValueInfoMap.getEnumValueInfo(staticGet.getField());
+          if (enumValueInfo == null && staticGet.getField().name == factory.enumValuesFieldName) {
+            requiresValuesUtilityMethod = true;
+            DexField fieldValues = createValuesField(holder);
+            extraUtilityFields.computeIfAbsent(fieldValues, this::computeValuesEncodedField);
+            DexMethod methodValues = createValuesMethod(holder);
+            extraUtilityMethods.computeIfAbsent(
+                methodValues,
+                m -> computeValuesEncodedMethod(m, fieldValues, enumValueInfoMap.size()));
+            Value rewrittenOutValue =
+                code.createValue(
+                    ArrayTypeElement.create(TypeElement.getInt(), definitelyNotNull()));
+            iterator.replaceCurrentInstruction(
+                new InvokeStatic(methodValues, rewrittenOutValue, ImmutableList.of()));
+          } else {
+            // Replace by ordinal + 1 for null check (null is 0).
+            assert enumValueInfo != null
+                : "Invalid read to " + staticGet.getField().name + ", error during enum analysis";
+            iterator.replaceCurrentInstruction(
+                code.createIntConstant(enumValueInfo.convertToInt()));
+          }
         }
       }
       // Rewrite array accesses from MyEnum[] (OBJECT) to int[] (INT).
@@ -186,19 +218,59 @@
     return enumsToUnbox.containsEnum(type.asClassType().getClassType());
   }
 
+  private String compatibleName(DexType type) {
+    return type.toSourceString().replace('.', '$');
+  }
+
+  private DexField createValuesField(DexType type) {
+    return factory.createField(
+        utilityClassType,
+        factory.intArrayType,
+        factory.enumValuesFieldName + "$field$" + compatibleName(type));
+  }
+
+  private DexEncodedField computeValuesEncodedField(DexField field) {
+    return new DexEncodedField(
+        field,
+        FieldAccessFlags.fromSharedAccessFlags(
+            Constants.ACC_SYNTHETIC | Constants.ACC_STATIC | Constants.ACC_PUBLIC),
+        DexAnnotationSet.empty(),
+        null);
+  }
+
+  private DexMethod createValuesMethod(DexType type) {
+    return factory.createMethod(
+        utilityClassType,
+        factory.createProto(factory.intArrayType),
+        factory.enumValuesFieldName + "$method$" + compatibleName(type));
+  }
+
+  private DexEncodedMethod computeValuesEncodedMethod(
+      DexMethod method, DexField fieldValues, int numEnumInstances) {
+    CfCode cfCode =
+        new EnumUnboxingCfCodeProvider.EnumUnboxingValuesCfCodeProvider(
+                appView, utilityClassType, fieldValues, numEnumInstances, valuesUtilityMethod)
+            .generateCfCode();
+    return synthesizeUtilityMethod(cfCode, method, true);
+  }
+
   private DexMethod computeValueOfUtilityMethod(DexType type) {
     assert enumsToUnbox.containsEnum(type);
     DexMethod valueOf =
         factory.createMethod(
             utilityClassType,
             factory.createProto(factory.intType, factory.stringType),
-            "valueOf" + type.toSourceString().replace('.', '$'));
-    extraMethods.putIfAbsent(valueOf, type);
+            "valueOf" + compatibleName(type));
+    extraUtilityMethods.computeIfAbsent(valueOf, m -> synthesizeValueOfUtilityMethod(m, type));
     return valueOf;
   }
 
   private boolean shouldRewriteArrayAccess(ArrayAccess arrayAccess) {
     ArrayTypeElement arrayType = arrayAccess.array().getType().asArrayType();
+    if (arrayType == null) {
+      assert arrayAccess.array().getType().isNullType();
+      return false;
+    }
     if (arrayType.getNesting() != 1) {
       return false;
     }
@@ -213,19 +285,21 @@
       throws ExecutionException {
     // Synthesize a class which holds various utility methods that may be called from the IR
     // rewriting. If any of these methods are not used, they will be removed by the Enqueuer.
-    List<DexEncodedMethod> requiredMethods = new ArrayList<>();
-    extraMethods.forEach(
-        (method, enumType) -> {
-          requiredMethods.add(synthesizeValueOfUtilityMethod(method, enumType));
-        });
+    List<DexEncodedMethod> requiredMethods = new ArrayList<>(extraUtilityMethods.values());
+    // Sort for deterministic order.
     requiredMethods.sort((m1, m2) -> m1.method.name.slowCompareTo(m2.method.name));
     if (requiresOrdinalUtilityMethod) {
       requiredMethods.add(synthesizeOrdinalMethod());
     }
+    if (requiresValuesUtilityMethod) {
+      requiredMethods.add(synthesizeValuesUtilityMethod());
+    }
     // TODO(b/147860220): synthesize also other enum methods.
     if (requiredMethods.isEmpty()) {
       return;
     }
+    DexEncodedField[] fields = extraUtilityFields.values().toArray(DexEncodedField.EMPTY_ARRAY);
+    Arrays.sort(fields, (f1, f2) -> f1.field.name.slowCompareTo(f2.field.name));
     DexProgramClass utilityClass =
         new DexProgramClass(
             utilityClassType,
@@ -240,7 +314,7 @@
             null,
             Collections.emptyList(),
             DexAnnotationSet.empty(),
-            DexEncodedField.EMPTY_ARRAY,
+            fields,
             DexEncodedField.EMPTY_ARRAY,
             // All synthesized methods are static in this case.
             requiredMethods.toArray(DexEncodedMethod.EMPTY_ARRAY),
@@ -259,7 +333,7 @@
             .generateCfCode();
     return new DexEncodedMethod(
         method,
-        synthesizedMethodAccessFlags(),
+        synthesizedMethodAccessFlags(false),
         DexAnnotationSet.empty(),
         ParameterAnnotationsList.empty(),
         cfCode,
@@ -280,9 +354,19 @@
   private DexEncodedMethod synthesizeOrdinalMethod() {
     CfCode cfCode =
         EnumUnboxingCfMethods.EnumUnboxingMethods_ordinal(appView.options(), ordinalUtilityMethod);
+    return synthesizeUtilityMethod(cfCode, ordinalUtilityMethod, false);
+  }
+
+  private DexEncodedMethod synthesizeValuesUtilityMethod() {
+    CfCode cfCode =
+        EnumUnboxingCfMethods.EnumUnboxingMethods_values(appView.options(), valuesUtilityMethod);
+    return synthesizeUtilityMethod(cfCode, valuesUtilityMethod, false);
+  }
+
+  private DexEncodedMethod synthesizeUtilityMethod(CfCode cfCode, DexMethod method, boolean sync) {
     return new DexEncodedMethod(
-        ordinalUtilityMethod,
-        synthesizedMethodAccessFlags(),
+        method,
+        synthesizedMethodAccessFlags(sync),
         DexAnnotationSet.empty(),
         ParameterAnnotationsList.empty(),
         cfCode,
@@ -290,8 +374,11 @@
         true);
   }
 
-  private MethodAccessFlags synthesizedMethodAccessFlags() {
-    return MethodAccessFlags.fromSharedAccessFlags(
-        Constants.ACC_PUBLIC | Constants.ACC_SYNTHETIC | Constants.ACC_STATIC, false);
+  private MethodAccessFlags synthesizedMethodAccessFlags(boolean sync) {
+    int access = Constants.ACC_PUBLIC | Constants.ACC_SYNTHETIC | Constants.ACC_STATIC;
+    if (sync) {
+      access = access | Constants.ACC_SYNCHRONIZED;
+    }
+    return MethodAccessFlags.fromSharedAccessFlags(access, false);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/DefaultMethodOptimizationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/DefaultMethodOptimizationInfo.java
index 414e55f..59e24a6 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/DefaultMethodOptimizationInfo.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/DefaultMethodOptimizationInfo.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.ir.analysis.value.UnknownValue;
 import com.android.tools.r8.ir.optimize.classinliner.ClassInlinerEligibilityInfo;
 import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo.ParameterUsage;
+import com.android.tools.r8.ir.optimize.info.bridge.BridgeInfo;
 import com.android.tools.r8.ir.optimize.info.initializer.DefaultInstanceInitializerInfo;
 import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
 import com.google.common.collect.ImmutableSet;
@@ -133,6 +134,11 @@
   }
 
   @Override
+  public BridgeInfo getBridgeInfo() {
+    return null;
+  }
+
+  @Override
   public ClassInlinerEligibilityInfo getClassInlinerEligibility() {
     return UNKNOWN_CLASS_INLINER_ELIGIBILITY;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/MethodOptimizationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/MethodOptimizationInfo.java
index c74bc0a..16ce797 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/MethodOptimizationInfo.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/MethodOptimizationInfo.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.ir.analysis.value.AbstractValue;
 import com.android.tools.r8.ir.optimize.classinliner.ClassInlinerEligibilityInfo;
 import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo.ParameterUsage;
+import com.android.tools.r8.ir.optimize.info.bridge.BridgeInfo;
 import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
 import java.util.BitSet;
 import java.util.Set;
@@ -54,6 +55,8 @@
 
   boolean neverReturnsNormally();
 
+  BridgeInfo getBridgeInfo();
+
   ClassInlinerEligibilityInfo getClassInlinerEligibility();
 
   Set<DexType> getInitializedClassesOnNormalExit();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/MethodOptimizationInfoCollector.java b/src/main/java/com/android/tools/r8/ir/optimize/info/MethodOptimizationInfoCollector.java
index 4889b2e..d1ddce9 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/MethodOptimizationInfoCollector.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/MethodOptimizationInfoCollector.java
@@ -85,6 +85,7 @@
 import com.android.tools.r8.ir.optimize.classinliner.ClassInlinerReceiverAnalysis;
 import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo.ParameterUsage;
 import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo.ParameterUsageBuilder;
+import com.android.tools.r8.ir.optimize.info.bridge.BridgeAnalyzer;
 import com.android.tools.r8.ir.optimize.info.field.InstanceFieldInitializationInfoCollection;
 import com.android.tools.r8.ir.optimize.info.initializer.DefaultInstanceInitializerInfo;
 import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
@@ -126,6 +127,7 @@
       DynamicTypeOptimization dynamicTypeOptimization,
       InstanceFieldInitializationInfoCollection instanceFieldInitializationInfos,
       Timing timing) {
+    identifyBridgeInfo(method, code, feedback, timing);
     identifyClassInlinerEligibility(method, code, feedback, timing);
     identifyParameterUsages(method, code, feedback, timing);
     identifyReturnsArgument(method, code, feedback, timing);
@@ -142,6 +144,13 @@
     computeNonNullParamOnNormalExits(feedback, code, timing);
   }
 
+  private void identifyBridgeInfo(
+      DexEncodedMethod method, IRCode code, OptimizationFeedback feedback, Timing timing) {
+    timing.begin("Identify bridge info");
+    feedback.setBridgeInfo(method, BridgeAnalyzer.analyzeMethod(method, code));
+    timing.end();
+  }
+
   private void identifyClassInlinerEligibility(
       DexEncodedMethod method, IRCode code, OptimizationFeedback feedback, Timing timing) {
     timing.begin("Identify class inliner eligibility");
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/OptimizationFeedbackDelayed.java b/src/main/java/com/android/tools/r8/ir/optimize/info/OptimizationFeedbackDelayed.java
index 212a044..d4eef20 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/OptimizationFeedbackDelayed.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/OptimizationFeedbackDelayed.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.analysis.value.AbstractValue;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.classinliner.ClassInlinerEligibilityInfo;
+import com.android.tools.r8.ir.optimize.info.bridge.BridgeInfo;
 import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.AppInfoWithLivenessModifier;
@@ -242,6 +243,11 @@
   }
 
   @Override
+  public void setBridgeInfo(DexEncodedMethod method, BridgeInfo bridgeInfo) {
+    getMethodOptimizationInfoForUpdating(method).setBridgeInfo(bridgeInfo);
+  }
+
+  @Override
   public synchronized void setClassInlinerEligibility(
       DexEncodedMethod method, ClassInlinerEligibilityInfo eligibility) {
     getMethodOptimizationInfoForUpdating(method).setClassInlinerEligibility(eligibility);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/OptimizationFeedbackIgnore.java b/src/main/java/com/android/tools/r8/ir/optimize/info/OptimizationFeedbackIgnore.java
index 2f20a39..435f05f 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/OptimizationFeedbackIgnore.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/OptimizationFeedbackIgnore.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.analysis.value.AbstractValue;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.classinliner.ClassInlinerEligibilityInfo;
+import com.android.tools.r8.ir.optimize.info.bridge.BridgeInfo;
 import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.BitSet;
@@ -107,6 +108,9 @@
   public void markTriggerClassInitBeforeAnySideEffect(DexEncodedMethod method, boolean mark) {}
 
   @Override
+  public void setBridgeInfo(DexEncodedMethod method, BridgeInfo bridgeInfo) {}
+
+  @Override
   public void setClassInlinerEligibility(
       DexEncodedMethod method, ClassInlinerEligibilityInfo eligibility) {}
 
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/OptimizationFeedbackSimple.java b/src/main/java/com/android/tools/r8/ir/optimize/info/OptimizationFeedbackSimple.java
index 302a58b..c03c8e0d 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/OptimizationFeedbackSimple.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/OptimizationFeedbackSimple.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.analysis.value.AbstractValue;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.classinliner.ClassInlinerEligibilityInfo;
+import com.android.tools.r8.ir.optimize.info.bridge.BridgeInfo;
 import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.BitSet;
@@ -154,6 +155,11 @@
   }
 
   @Override
+  public void setBridgeInfo(DexEncodedMethod method, BridgeInfo bridgeInfo) {
+    // Ignored.
+  }
+
+  @Override
   public void setClassInlinerEligibility(
       DexEncodedMethod method, ClassInlinerEligibilityInfo eligibility) {
     // Ignored.
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/UpdatableMethodOptimizationInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/UpdatableMethodOptimizationInfo.java
index ed6233f..5ad6c86 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/info/UpdatableMethodOptimizationInfo.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/UpdatableMethodOptimizationInfo.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.analysis.value.AbstractValue;
 import com.android.tools.r8.ir.optimize.classinliner.ClassInlinerEligibilityInfo;
 import com.android.tools.r8.ir.optimize.info.ParameterUsagesInfo.ParameterUsage;
+import com.android.tools.r8.ir.optimize.info.bridge.BridgeInfo;
 import com.android.tools.r8.ir.optimize.info.initializer.DefaultInstanceInitializerInfo;
 import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
@@ -34,6 +35,7 @@
   private InlinePreference inlining = InlinePreference.Default;
   // Stores information about instance methods and constructors for
   // class inliner, null value indicates that the method is not eligible.
+  private BridgeInfo bridgeInfo = null;
   private ClassInlinerEligibilityInfo classInlinerEligibility =
       DefaultMethodOptimizationInfo.UNKNOWN_CLASS_INLINER_ELIGIBILITY;
   private InstanceInitializerInfo instanceInitializerInfo =
@@ -134,6 +136,7 @@
     returnsObjectWithUpperBoundType = template.returnsObjectWithUpperBoundType;
     returnsObjectWithLowerBoundType = template.returnsObjectWithLowerBoundType;
     inlining = template.inlining;
+    bridgeInfo = template.bridgeInfo;
     classInlinerEligibility = template.classInlinerEligibility;
     instanceInitializerInfo = template.instanceInitializerInfo;
     parametersUsages = template.parametersUsages;
@@ -300,6 +303,15 @@
   }
 
   @Override
+  public BridgeInfo getBridgeInfo() {
+    return bridgeInfo;
+  }
+
+  void setBridgeInfo(BridgeInfo bridgeInfo) {
+    this.bridgeInfo = bridgeInfo;
+  }
+
+  @Override
   public ClassInlinerEligibilityInfo getClassInlinerEligibility() {
     return classInlinerEligibility;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/bridge/BridgeAnalyzer.java b/src/main/java/com/android/tools/r8/ir/optimize/info/bridge/BridgeAnalyzer.java
new file mode 100644
index 0000000..8f28fd5
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/bridge/BridgeAnalyzer.java
@@ -0,0 +1,175 @@
+// 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.ir.optimize.info.bridge;
+
+import static com.android.tools.r8.ir.code.Opcodes.ARGUMENT;
+import static com.android.tools.r8.ir.code.Opcodes.ASSUME;
+import static com.android.tools.r8.ir.code.Opcodes.CHECK_CAST;
+import static com.android.tools.r8.ir.code.Opcodes.INVOKE_VIRTUAL;
+import static com.android.tools.r8.ir.code.Opcodes.RETURN;
+
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.ir.code.CheckCast;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.InvokeVirtual;
+import com.android.tools.r8.ir.code.Return;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.utils.BooleanUtils;
+
+public class BridgeAnalyzer {
+
+  /** Returns a {@link BridgeInfo} object describing this method if it is recognized as a bridge. */
+  public static BridgeInfo analyzeMethod(DexEncodedMethod method, IRCode code) {
+    // TODO(b/154263783): Consider computing BridgeInfo also for non-declared bridges.
+    if (!method.isBridge() || code.blocks.size() > 1) {
+      return failure();
+    }
+
+    // Scan through the instructions one-by-one. We expect a sequence of Argument instructions,
+    // followed by a (possibly empty) sequence of CheckCast instructions, followed by a single
+    // InvokeMethod instruction, followed by an optional CheckCast instruction, followed by a Return
+    // instruction.
+    InvokeVirtual uniqueInvoke = null;
+    CheckCast uniqueReturnCast = null;
+    for (Instruction instruction : code.entryBlock().getInstructions()) {
+      switch (instruction.opcode()) {
+        case ARGUMENT:
+          break;
+
+        case ASSUME:
+          break;
+
+        case CHECK_CAST:
+          {
+            CheckCast checkCast = instruction.asCheckCast();
+            if (!analyzeCheckCast(method, checkCast, uniqueInvoke)) {
+              return failure();
+            }
+            // If we have moved past the single invoke instruction, then record that this cast is
+            // the cast instruction for the result value.
+            if (uniqueInvoke != null) {
+              if (uniqueReturnCast != null) {
+                return failure();
+              }
+              uniqueReturnCast = checkCast;
+            }
+            break;
+          }
+
+        case INVOKE_VIRTUAL:
+          {
+            if (uniqueInvoke != null) {
+              return failure();
+            }
+            InvokeVirtual invoke = instruction.asInvokeVirtual();
+            if (!analyzeInvokeVirtual(invoke)) {
+              return failure();
+            }
+            // Record that we have seen the single invoke instruction.
+            uniqueInvoke = invoke;
+            break;
+          }
+
+        case RETURN:
+          if (!analyzeReturn(instruction.asReturn(), uniqueInvoke, uniqueReturnCast)) {
+            return failure();
+          }
+          break;
+
+        default:
+          return failure();
+      }
+    }
+
+    assert uniqueInvoke != null;
+    return new VirtualBridgeInfo(uniqueInvoke.getInvokedMethod());
+  }
+
+  private static boolean analyzeCheckCast(
+      DexEncodedMethod method, CheckCast checkCast, InvokeMethod invoke) {
+    return invoke == null
+        ? analyzeCheckCastBeforeInvoke(checkCast)
+        : analyzeCheckCastAfterInvoke(method, checkCast, invoke);
+  }
+
+  private static boolean analyzeCheckCastBeforeInvoke(CheckCast checkCast) {
+    Value object = checkCast.object().getAliasedValue();
+    // It must be casting one of the arguments.
+    if (!object.isArgument()) {
+      return false;
+    }
+    int argumentIndex = object.definition.asArgument().getIndex();
+    Value castValue = checkCast.outValue();
+    // The out value cannot have any phi users since there is only one block.
+    assert !castValue.hasPhiUsers();
+    // It is not allowed to have any other users than the invoke instruction.
+    if (castValue.hasDebugUsers() || !castValue.hasSingleUniqueUser()) {
+      return false;
+    }
+    InvokeMethod invoke = castValue.singleUniqueUser().asInvokeMethod();
+    if (invoke == null) {
+      return false;
+    }
+    if (invoke.arguments().size() <= argumentIndex) {
+      return false;
+    }
+    int parameterIndex = argumentIndex - BooleanUtils.intValue(invoke.isInvokeMethodWithReceiver());
+    // It is not allowed to cast the receiver.
+    if (parameterIndex == -1) {
+      return false;
+    }
+    // The type of the cast must match the type of the parameter.
+    if (checkCast.getType() != invoke.getInvokedMethod().proto.getParameter(parameterIndex)) {
+      return false;
+    }
+    // It must be forwarded at the same argument index.
+    Value argument = invoke.getArgument(argumentIndex);
+    if (argument != castValue) {
+      return false;
+    }
+    return true;
+  }
+
+  private static boolean analyzeCheckCastAfterInvoke(
+      DexEncodedMethod method, CheckCast checkCast, InvokeMethod invoke) {
+    Value returnValue = invoke.outValue();
+    Value uncastValue = checkCast.object().getAliasedValue();
+    Value castValue = checkCast.outValue();
+    // The out value cannot have any phi users since there is only one block.
+    assert !castValue.hasPhiUsers();
+    // It must cast the result to the return type of the enclosing method and return the cast value.
+    return uncastValue == returnValue
+        && checkCast.getType() == method.returnType()
+        && !castValue.hasDebugUsers()
+        && castValue.hasSingleUniqueUser()
+        && castValue.singleUniqueUser().isReturn();
+  }
+
+  private static boolean analyzeInvokeVirtual(InvokeVirtual invoke) {
+    // All of the forwarded arguments of the enclosing method must be in the same argument position.
+    for (int argumentIndex = 0; argumentIndex < invoke.arguments().size(); argumentIndex++) {
+      Value argument = invoke.getArgument(argumentIndex);
+      if (argument.isArgument() && argumentIndex != argument.definition.asArgument().getIndex()) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  private static boolean analyzeReturn(Return ret, InvokeMethod invoke, CheckCast returnCast) {
+    // If we haven't seen an invoke this is not a bridge.
+    if (invoke == null) {
+      return false;
+    }
+    // It must not return a value, or the return value must be the result value of the invoke.
+    return ret.isReturnVoid()
+        || ret.returnValue() == (returnCast != null ? returnCast : invoke).outValue();
+  }
+
+  private static BridgeInfo failure() {
+    return null;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/bridge/BridgeInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/bridge/BridgeInfo.java
new file mode 100644
index 0000000..2683d2f
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/bridge/BridgeInfo.java
@@ -0,0 +1,19 @@
+// 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.ir.optimize.info.bridge;
+
+/**
+ * A piece of optimization info that is computed for bridge methods. The info stores details about
+ * the behavior of the bridge.
+ */
+public abstract class BridgeInfo {
+
+  public boolean isVirtualBridgeInfo() {
+    return false;
+  }
+
+  public VirtualBridgeInfo asVirtualBridgeInfo() {
+    return null;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/info/bridge/VirtualBridgeInfo.java b/src/main/java/com/android/tools/r8/ir/optimize/info/bridge/VirtualBridgeInfo.java
new file mode 100644
index 0000000..a07abdc
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/info/bridge/VirtualBridgeInfo.java
@@ -0,0 +1,49 @@
+// 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.ir.optimize.info.bridge;
+
+import com.android.tools.r8.graph.DexMethod;
+
+/**
+ * Optimization info computed for bridge methods that use an invoke-virtual instruction.
+ *
+ * <p>If the method is {@code String A.m(Object)} and {@link #invokedMethod} is {@code Object
+ * B.m(String)}, then the bridge is implemented as:
+ *
+ * <pre>
+ *   java.lang.String A.m(java.lang.Object o) {
+ *     v0 <- Argument
+ *     v1 <- CheckCast v0, java.lang.String
+ *     v2 <- InvokeVirtual { v0, v1 }, java.lang.Object B.m(java.lang.String)
+ *     v3 <- CheckCast v2, java.lang.String
+ *     Return v3
+ *   }
+ * </pre>
+ *
+ * <p>This currently does not allow any permutation of the argument order, and it also does not
+ * allow constants to be passed as arguments.
+ */
+public class VirtualBridgeInfo extends BridgeInfo {
+
+  // The targeted method.
+  private final DexMethod invokedMethod;
+
+  public VirtualBridgeInfo(DexMethod invokedMethod) {
+    this.invokedMethod = invokedMethod;
+  }
+
+  public DexMethod getInvokedMethod() {
+    return invokedMethod;
+  }
+
+  @Override
+  public boolean isVirtualBridgeInfo() {
+    return true;
+  }
+
+  @Override
+  public VirtualBridgeInfo asVirtualBridgeInfo() {
+    return this;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java
index 41df56a..ed3e72a 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizer.java
@@ -96,6 +96,15 @@
       candidates.remove(candidate.type);
       return null;
     }
+
+    void filterMethods() {
+      Set<DexEncodedMethod> newReferencedFrom = Sets.newIdentityHashSet();
+      for (DexEncodedMethod dexEncodedMethod : referencedFrom) {
+        newReferencedFrom.add(appView.graphLense().mapDexEncodedMethod(dexEncodedMethod, appView));
+      }
+      referencedFrom.clear();
+      referencedFrom.addAll(newReferencedFrom);
+    }
   }
 
   // The map storing all the potential candidates for staticizing.
@@ -651,6 +660,17 @@
     return false;
   }
 
+  // Methods may have their signature changed in-between the IR processing rounds, leading to
+  // duplicates where one version is the outdated version. Remove these.
+  // This also ensures no unboxed enum are staticized, if that would be the case, then
+  // the candidate would need to be removed from the candidate list.
+  public void filterCandidates() {
+    for (Map.Entry<DexType, CandidateInfo> entry : candidates.entrySet()) {
+      assert !appView.unboxedEnums().containsEnum(entry.getKey());
+      entry.getValue().filterMethods();
+    }
+  }
+
   // Perform staticizing candidates:
   //
   //  1. After filtering candidates based on usage, finalize the list of candidates by
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
index 1d679ecc..c451bd7 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
@@ -286,12 +286,22 @@
       if (getter != null) {
         singletonGetters.put(getter.method, candidate);
       }
+      assert validMethods(candidate.referencedFrom);
       referencingExtraMethods.addAll(candidate.referencedFrom);
     }
 
     referencingExtraMethods.removeAll(removedInstanceMethods);
   }
 
+  private boolean validMethods(Set<DexEncodedMethod> referencedFrom) {
+    for (DexEncodedMethod dexEncodedMethod : referencedFrom) {
+      DexClass clazz = appView.definitionForHolder(dexEncodedMethod.method);
+      assert clazz != null;
+      assert clazz.lookupMethod(dexEncodedMethod.method) == dexEncodedMethod;
+    }
+    return true;
+  }
+
   private void enqueueMethodsWithCodeOptimizations(
       Iterable<DexEncodedMethod> methods,
       Consumer<ImmutableList.Builder<BiConsumer<IRCode, MethodProcessor>>> extension) {
diff --git a/src/main/java/com/android/tools/r8/ir/synthetic/EnumUnboxingCfCodeProvider.java b/src/main/java/com/android/tools/r8/ir/synthetic/EnumUnboxingCfCodeProvider.java
index b30d567..f9f66e8 100644
--- a/src/main/java/com/android/tools/r8/ir/synthetic/EnumUnboxingCfCodeProvider.java
+++ b/src/main/java/com/android/tools/r8/ir/synthetic/EnumUnboxingCfCodeProvider.java
@@ -6,6 +6,7 @@
 
 import com.android.tools.r8.cf.code.CfConstNumber;
 import com.android.tools.r8.cf.code.CfConstString;
+import com.android.tools.r8.cf.code.CfFieldInstruction;
 import com.android.tools.r8.cf.code.CfIf;
 import com.android.tools.r8.cf.code.CfInstruction;
 import com.android.tools.r8.cf.code.CfInvoke;
@@ -18,7 +19,9 @@
 import com.android.tools.r8.cf.code.CfThrow;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.CfCode;
+import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.EnumValueInfoMapCollection.EnumValueInfoMap;
 import com.android.tools.r8.ir.code.If;
@@ -104,4 +107,47 @@
       return standardCfCodeFromInstructions(instructions);
     }
   }
+
+  public static class EnumUnboxingValuesCfCodeProvider extends EnumUnboxingCfCodeProvider {
+
+    private final DexField utilityField;
+    private final int numEnumInstances;
+    private final DexMethod initializationMethod;
+
+    public EnumUnboxingValuesCfCodeProvider(
+        AppView<?> appView,
+        DexType holder,
+        DexField utilityField,
+        int numEnumInstances,
+        DexMethod initializationMethod) {
+      super(appView, holder);
+      assert utilityField.type == appView.dexItemFactory().intArrayType;
+      this.utilityField = utilityField;
+      this.numEnumInstances = numEnumInstances;
+      this.initializationMethod = initializationMethod;
+    }
+
+    @Override
+    public CfCode generateCfCode() {
+      // Generated static method, for class com.x.MyEnum {A,B}, and a field in VALUES$com$x$MyEnum
+      // on Utility class, would look like:
+      // synchronized int[] UtilityClass#com$x$MyEnum_VALUES() {
+      //    if (VALUES$com$x$MyEnum == null) {
+      //      VALUES$com$x$MyEnum = EnumUnboxingMethods_values(2);
+      //    }
+      //    return VALUES$com$x$MyEnum;
+      List<CfInstruction> instructions = new ArrayList<>();
+      CfLabel nullDest = new CfLabel();
+      instructions.add(new CfFieldInstruction(Opcodes.GETSTATIC, utilityField, utilityField));
+      instructions.add(new CfIf(If.Type.NE, ValueType.OBJECT, nullDest));
+      instructions.add((new CfConstNumber(numEnumInstances, ValueType.INT)));
+      assert initializationMethod.getArity() == 1;
+      instructions.add(new CfInvoke(Opcodes.INVOKESTATIC, initializationMethod, false));
+      instructions.add(new CfFieldInstruction(Opcodes.PUTSTATIC, utilityField, utilityField));
+      instructions.add(nullDest);
+      instructions.add(new CfFieldInstruction(Opcodes.GETSTATIC, utilityField, utilityField));
+      instructions.add(new CfReturn(ValueType.OBJECT));
+      return standardCfCodeFromInstructions(instructions);
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java b/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java
index 609feaa..59fee69 100644
--- a/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java
+++ b/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java
@@ -4,9 +4,9 @@
 
 package com.android.tools.r8.naming;
 
+
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexCallSite;
-import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItem;
@@ -16,11 +16,9 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.InnerClassAttribute;
 import com.android.tools.r8.graph.ResolutionResult;
-import com.android.tools.r8.graph.ResolutionResult.SingleResolutionResult;
 import com.android.tools.r8.naming.ClassNameMinifier.ClassRenaming;
 import com.android.tools.r8.naming.FieldNameMinifier.FieldRenaming;
 import com.android.tools.r8.naming.MethodNameMinifier.MethodRenaming;
-import com.android.tools.r8.optimize.MemberRebindingAnalysis;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.InternalOptions;
 import com.google.common.collect.ImmutableMap;
@@ -158,31 +156,49 @@
   }
 
   /**
-   * Checks whether the target is precise enough to be translated,
-   *
-   * <p>We only track the renaming of actual definitions, Thus, if we encounter a method id that
-   * does not directly point at a definition, we won't find the actual renaming. To avoid
-   * dispatching on every lookup, we assume that the tree has been fully dispatched by {@link
-   * MemberRebindingAnalysis}.
-   *
-   * <p>Library methods are excluded from this check, as those are never renamed.
+   * Checks that the renaming of the method reference {@param method} is consistent with the
+   * renaming of the resolution target of {@param method}.
    */
   @Override
-  public boolean checkTargetCanBeTranslated(DexMethod item) {
-    if (item.holder.isArrayType()) {
+  public boolean verifyRenamingConsistentWithResolution(DexMethod method) {
+    if (method.holder.isArrayType()) {
       // Array methods are never renamed, so do not bother to check.
       return true;
     }
-    DexClass holder = appView.definitionFor(item.holder);
-    if (holder == null || holder.isNotProgramClass()) {
+
+    ResolutionResult resolution = appView.appInfo().resolveMethod(method.holder, method);
+    assert resolution != null;
+
+    if (resolution.isSingleResolution()) {
+      // If we can resolve `item`, then the renaming for `item` and its resolution should be the
+      // same.
+      DexEncodedMethod resolvedMethod = resolution.asSingleResolution().getResolvedMethod();
+      assert lookupName(method) == lookupName(resolvedMethod.method);
       return true;
     }
-    SingleResolutionResult resolution =
-        appView.appInfo().resolveMethod(item.holder, item).asSingleResolution();
-    // The resolution is either unknown or resolved to the item or a visibility bridge.
-    assert resolution == null
-        || resolution.getResolvedMethod().method == item
-        || appView.unneededVisibilityBridgeMethods().contains(item);
+
+    assert resolution.isFailedResolution();
+
+    // If we can't resolve `item` it is questionable to record a renaming for it. However, it can
+    // be required to preserve errors.
+    //
+    // Example:
+    //   class A { private void m() }
+    //   class B extends A {}
+    //   class Main { public static void main() { new B().m(); } }
+    //
+    // In this example, the invoke-virtual instruction targeting m() in Main does not resolve,
+    // since the method is private. On the JVM this fails with an IllegalAccessError.
+    //
+    // If A.m() is renamed to A.a(), and the invoke-virtual instruction in Main is not changed to
+    // target a(), then the program will start failing with a NoSuchMethodError instead of an
+    // IllegalAccessError.
+    resolution
+        .asFailedResolution()
+        .forEachFailureDependency(
+            failureDependence -> {
+              assert lookupName(method) == lookupName(failureDependence.method);
+            });
     return true;
   }
 
diff --git a/src/main/java/com/android/tools/r8/naming/NamingLens.java b/src/main/java/com/android/tools/r8/naming/NamingLens.java
index d1c195f..b3694f7 100644
--- a/src/main/java/com/android/tools/r8/naming/NamingLens.java
+++ b/src/main/java/com/android/tools/r8/naming/NamingLens.java
@@ -135,7 +135,7 @@
    * <p>Normally, this means that the target corresponds to an actual definition that has been
    * renamed. For identity renamings, we are more relaxed, as no targets will be translated anyway.
    */
-  public abstract boolean checkTargetCanBeTranslated(DexMethod item);
+  public abstract boolean verifyRenamingConsistentWithResolution(DexMethod item);
 
   public final boolean verifyNoCollisions(
       Iterable<DexProgramClass> classes, DexItemFactory dexItemFactory) {
@@ -222,7 +222,7 @@
     }
 
     @Override
-    public boolean checkTargetCanBeTranslated(DexMethod item) {
+    public boolean verifyRenamingConsistentWithResolution(DexMethod item) {
       return true;
     }
   }
diff --git a/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java b/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java
index 6c78e0b..e411211 100644
--- a/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java
+++ b/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java
@@ -173,7 +173,7 @@
   }
 
   @Override
-  public boolean checkTargetCanBeTranslated(DexMethod item) {
-    return namingLens.checkTargetCanBeTranslated(item);
+  public boolean verifyRenamingConsistentWithResolution(DexMethod item) {
+    return namingLens.verifyRenamingConsistentWithResolution(item);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/optimize/VisibilityBridgeRemover.java b/src/main/java/com/android/tools/r8/optimize/VisibilityBridgeRemover.java
index 942cb91..d37ef84 100644
--- a/src/main/java/com/android/tools/r8/optimize/VisibilityBridgeRemover.java
+++ b/src/main/java/com/android/tools/r8/optimize/VisibilityBridgeRemover.java
@@ -14,22 +14,13 @@
 import com.google.common.collect.Sets;
 import java.util.List;
 import java.util.Set;
-import java.util.function.Consumer;
 
 public class VisibilityBridgeRemover {
 
   private final AppView<AppInfoWithLiveness> appView;
-  private final Consumer<DexEncodedMethod> unneededVisibilityBridgeConsumer;
 
   public VisibilityBridgeRemover(AppView<AppInfoWithLiveness> appView) {
-    this(appView, null);
-  }
-
-  public VisibilityBridgeRemover(
-      AppView<AppInfoWithLiveness> appView,
-      Consumer<DexEncodedMethod> unneededVisibilityBridgeConsumer) {
     this.appView = appView;
-    this.unneededVisibilityBridgeConsumer = unneededVisibilityBridgeConsumer;
   }
 
   private void removeUnneededVisibilityBridgesFromClass(DexProgramClass clazz) {
@@ -51,9 +42,6 @@
           methodsToBeRemoved = Sets.newIdentityHashSet();
         }
         methodsToBeRemoved.add(method);
-        if (unneededVisibilityBridgeConsumer != null) {
-          unneededVisibilityBridgeConsumer.accept(method);
-        }
       }
     }
     if (methodsToBeRemoved != null) {
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 8c79dd7..4b599bf 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -2755,7 +2755,7 @@
 
     // Remove all '$deserializeLambda$' methods which are not supported by desugaring.
     for (DexProgramClass clazz : classesWithSerializableLambdas) {
-      clazz.removeDirectMethod(appView.dexItemFactory().deserializeLambdaMethod);
+      clazz.removeMethod(appView.dexItemFactory().deserializeLambdaMethod);
     }
 
     // Clear state before next fixed point iteration.
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 51c6934..6ab3fcd 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -1103,6 +1103,7 @@
     public boolean alwaysUsePessimisticRegisterAllocation = false;
     public boolean enableCheckCastAndInstanceOfRemoval = true;
     public boolean enableDeadSwitchCaseElimination = true;
+    public boolean enableInvokeSuperToInvokeVirtualRewriting = true;
     public boolean enableSwitchToIfRewriting = true;
     public boolean enableEnumUnboxingDebugLogs = false;
     public boolean forceRedundantConstNumberRemoval = false;
@@ -1123,6 +1124,7 @@
     public boolean trackDesugaredAPIConversions =
         System.getProperty("com.android.tools.r8.trackDesugaredAPIConversions") != null;
     public boolean forceLibBackportsInL8CfToCf = false;
+    public boolean enumUnboxingRewriteJavaCGeneratedMethod = false;
 
     // TODO(b/144781417): This is disabled by default as some test apps appear to have such classes.
     public boolean allowNonAbstractClassesWithAbstractMethods = true;
diff --git a/src/test/java/com/android/tools/r8/androidapi/GenerateAvailableApiExceptions.java b/src/test/java/com/android/tools/r8/androidapi/GenerateAvailableApiExceptions.java
new file mode 100644
index 0000000..83821f8
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/androidapi/GenerateAvailableApiExceptions.java
@@ -0,0 +1,116 @@
+// 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.androidapi;
+
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.cfmethodgeneration.MethodGenerationBase;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.DescriptorUtils;
+import com.android.tools.r8.utils.FileUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import java.util.IdentityHashMap;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeSet;
+import javax.xml.parsers.DocumentBuilderFactory;
+import org.w3c.dom.Document;
+import org.w3c.dom.Node;
+import org.w3c.dom.NodeList;
+
+public class GenerateAvailableApiExceptions {
+
+  private static final int fixedApiLevel = AndroidApiLevel.L.getLevel();
+
+  private static String generateBuildMapCode(Path apiVersionsXml) throws Exception {
+    CodeInspector inspector = new CodeInspector(ToolHelper.getAndroidJar(fixedApiLevel));
+    Map<DexClass, Boolean> isExceptionCache = new IdentityHashMap<>();
+    Int2ReferenceMap<Set<String>> exceptionsMap = new Int2ReferenceOpenHashMap<>();
+
+    // Read api-versions.xml locating all classes that derive throwable and adding them to the map.
+    DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
+    Document document = factory.newDocumentBuilder().parse(apiVersionsXml.toFile());
+    NodeList classes = document.getElementsByTagName("class");
+    int totalCount = 0;
+    for (int i = 0; i < classes.getLength(); i++) {
+      Node node = classes.item(i);
+      assert node.getNodeType() == Node.ELEMENT_NODE;
+      Node sinceAttr = node.getAttributes().getNamedItem("since");
+      if (sinceAttr == null) {
+        continue;
+      }
+      int since = Integer.parseInt(sinceAttr.getNodeValue());
+      if (since >= fixedApiLevel) {
+        continue;
+      }
+      String name = node.getAttributes().getNamedItem("name").getNodeValue();
+      String type = DescriptorUtils.getJavaTypeFromBinaryName(name);
+      ClassSubject clazz = inspector.clazz(type);
+      if (isThrowable(clazz, isExceptionCache, inspector)) {
+        exceptionsMap.computeIfAbsent(since, k -> new TreeSet<>()).add(name);
+        totalCount++;
+      }
+    }
+
+    // Build the code for the buildMap method.
+    StringBuilder builder = new StringBuilder();
+    builder.append("public class DoNotCommit {");
+    builder.append("public static Set<DexType> build(DexItemFactory factory, int minApiLevel) {");
+    builder.append("  Set<DexType> types = SetUtils.newIdentityHashSet(" + totalCount + ");");
+    for (int api = 1; api < fixedApiLevel; api++) {
+      Set<String> names = exceptionsMap.get(api);
+      if (names == null || names.isEmpty()) {
+        continue;
+      }
+      builder.append("if (minApiLevel >= " + api + ") {");
+      for (String name : names) {
+        String desc = DescriptorUtils.getDescriptorFromClassBinaryName(name);
+        builder.append("  types.add(factory.createType(\"" + desc + "\"));");
+      }
+      builder.append("}");
+    }
+    builder.append("  return types;");
+    builder.append("}");
+    builder.append("}");
+
+    // Write to temp file and format that file.
+    String rawOutput = builder.toString();
+    Path tempFile = Files.createTempFile("output-", ".java");
+    FileUtils.writeTextFile(tempFile, rawOutput);
+    return MethodGenerationBase.formatRawOutput(tempFile);
+  }
+
+  private static boolean isThrowable(
+      ClassSubject clazz, Map<DexClass, Boolean> cache, CodeInspector inspector) {
+    if (!clazz.isPresent()) {
+      return false;
+    }
+    if (clazz.getDexClass().type == inspector.getFactory().objectType) {
+      return false;
+    }
+    if (clazz.getDexClass().type == inspector.getFactory().throwableType) {
+      return true;
+    }
+    return cache.computeIfAbsent(
+        clazz.getDexClass(),
+        c -> {
+          return c.superType != null
+              && isThrowable(inspector.clazz(c.superType.toSourceString()), cache, inspector);
+        });
+  }
+
+  public static void main(String[] args) throws Exception {
+    Path apiVersionsXml =
+        args.length == 1
+            ? Paths.get(args[0])
+            : Paths.get("<your-android-checkout>/development/sdk/api-versions.xml");
+    System.out.println(generateBuildMapCode(apiVersionsXml));
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/bridgeremoval/RemoveVisibilityBridgeMethodsTest.java b/src/test/java/com/android/tools/r8/bridgeremoval/RemoveVisibilityBridgeMethodsTest.java
index 6bc3814..32fa0b8 100644
--- a/src/test/java/com/android/tools/r8/bridgeremoval/RemoveVisibilityBridgeMethodsTest.java
+++ b/src/test/java/com/android/tools/r8/bridgeremoval/RemoveVisibilityBridgeMethodsTest.java
@@ -13,9 +13,7 @@
 import com.android.tools.r8.jasmin.JasminBuilder;
 import com.android.tools.r8.jasmin.JasminBuilder.ClassBuilder;
 import com.android.tools.r8.utils.BooleanUtils;
-import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
-import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import java.util.Collections;
 import java.util.List;
 import org.junit.Test;
@@ -73,7 +71,7 @@
         "ldc \"Hello World\"",
         "areturn");
 
-    // Generate a subclass with a method with same
+    // Generate a subclass with a bridge method targeting SuperClass.method().
     ClassBuilder subclass = jasminBuilder.addClass("SubClass", superClass.name);
     subclass.addBridgeMethod("getMethod", Collections.emptyList(), "Ljava/lang/String;",
         ".limit stack 1",
@@ -113,17 +111,8 @@
         .compile()
         .inspect(
             inspector -> {
-              ClassSubject classSubject = inspector.clazz(superClass.name);
-              assertThat(classSubject, isPresent());
-              MethodSubject methodSubject =
-                  classSubject.method("java.lang.String", "method", Collections.emptyList());
-              assertThat(methodSubject, isPresent());
-
-              classSubject = inspector.clazz(subclass.name);
-              assertThat(classSubject, isPresent());
-              methodSubject =
-                  classSubject.method("java.lang.String", "getMethod", Collections.emptyList());
-              assertThat(methodSubject, isPresent());
+              assertThat(inspector.clazz(superClass.name), not(isPresent()));
+              assertThat(inspector.clazz(subclass.name), not(isPresent()));
             })
         .run(parameters.getRuntime(), mainClass.name)
         .assertSuccessWithOutputLines("Hello World");
diff --git a/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/BridgeHoistingAccessibilityTest.java b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/BridgeHoistingAccessibilityTest.java
new file mode 100644
index 0000000..ebb7662
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/BridgeHoistingAccessibilityTest.java
@@ -0,0 +1,106 @@
+// 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.bridgeremoval.hoisting;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NeverMerge;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.bridgeremoval.hoisting.testclasses.BridgeHoistingAccessibilityTestClasses;
+import com.android.tools.r8.bridgeremoval.hoisting.testclasses.BridgeHoistingAccessibilityTestClasses.User;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class BridgeHoistingAccessibilityTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public BridgeHoistingAccessibilityTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(TestClass.class)
+        .addInnerClasses(BridgeHoistingAccessibilityTestClasses.class)
+        .addProgramClassFileData(
+            transformer(B.class)
+                .setBridge(B.class.getDeclaredMethod("bridgeB", Object.class))
+                .transform(),
+            transformer(C.class)
+                .setBridge(C.class.getDeclaredMethod("bridgeC", Object.class))
+                .transform())
+        .addKeepMainRule(TestClass.class)
+        .enableInliningAnnotations()
+        .enableMergeAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(this::inspect)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("Hello world!");
+  }
+
+  private void inspect(CodeInspector inspector) {
+    ClassSubject aClassSubject = inspector.clazz(BridgeHoistingAccessibilityTestClasses.A.class);
+    assertThat(aClassSubject, isPresent());
+    assertThat(aClassSubject.uniqueMethodWithName("m"), isPresent());
+
+    ClassSubject bClassSubject = inspector.clazz(B.class);
+    assertThat(bClassSubject, isPresent());
+    assertThat(bClassSubject.uniqueMethodWithName("bridgeB"), isPresent());
+
+    ClassSubject cClassSubject = inspector.clazz(C.class);
+    assertThat(cClassSubject, isPresent());
+    // TODO(b/153147967): Should be hoisted to A.
+    assertThat(cClassSubject.uniqueMethodWithName("bridgeC"), isPresent());
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      C instance = new C();
+      System.out.print(instance.bridgeB("Hello"));
+      System.out.println(User.invokeBridgeC(instance));
+    }
+  }
+
+  @NeverMerge
+  static class B extends BridgeHoistingAccessibilityTestClasses.A {
+
+    // This bridge cannot be hoisted to A, since it would then become inaccessible to the call site
+    // in TestClass.main().
+    @NeverInline
+    /*bridge*/ String bridgeB(Object o) {
+      return (String) m((String) o);
+    }
+  }
+
+  @NeverClassInline
+  public static class C extends B {
+
+    // This bridge is invoked from another package. However, this does not prevent us from hoisting
+    // the bridge to B, although B is not public, since users from outside this package can still
+    // access bridgeC() via class C. From B, the bridge can be hoisted again to A.
+    @NeverInline
+    public /*bridge*/ String bridgeC(Object o) {
+      return (String) m((String) o);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/InterfaceBridgeHoistingTest.java b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/InterfaceBridgeHoistingTest.java
new file mode 100644
index 0000000..9fdc87f
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/InterfaceBridgeHoistingTest.java
@@ -0,0 +1,78 @@
+// 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.bridgeremoval.hoisting;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NeverMerge;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class InterfaceBridgeHoistingTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public InterfaceBridgeHoistingTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(TestClass.class, A.class, I.class)
+        .addProgramClassFileData(
+            transformer(B.class)
+                .setBridge(B.class.getDeclaredMethod("bridge", Object.class))
+                .transform())
+        .addKeepMainRule(TestClass.class)
+        .enableInliningAnnotations()
+        .enableMergeAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("Hello world!");
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      System.out.println(new B().bridge("Hello world!"));
+    }
+  }
+
+  @NeverMerge
+  static class A {}
+
+  @NeverMerge
+  interface I {
+
+    @NeverInline
+    default Object m(String arg) {
+      return System.currentTimeMillis() >= 0 ? arg : null;
+    }
+  }
+
+  @NeverClassInline
+  static class B extends A implements I {
+
+    // Hoisting this bridge to class A would lead to a NoSuchMethodError since the targeted method
+    // is defined on the interface I.
+    @NeverInline
+    public /*bridge*/ String bridge(Object o) {
+      return (String) m((String) o);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/KeptBridgeHoistingTest.java b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/KeptBridgeHoistingTest.java
new file mode 100644
index 0000000..b4ce765
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/KeptBridgeHoistingTest.java
@@ -0,0 +1,90 @@
+// 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.bridgeremoval.hoisting;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NeverMerge;
+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 com.android.tools.r8.utils.codeinspector.CodeInspector;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class KeptBridgeHoistingTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public KeptBridgeHoistingTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(TestClass.class, A.class)
+        .addProgramClassFileData(
+            transformer(B.class)
+                .setBridge(B.class.getDeclaredMethod("bridge", Object.class))
+                .transform())
+        .addKeepMainRule(TestClass.class)
+        .addKeepRules("-keep class " + B.class.getTypeName() + " { java.lang.String bridge(...); }")
+        .enableInliningAnnotations()
+        .enableMergeAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(this::inspect)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("Hello world!");
+  }
+
+  private void inspect(CodeInspector inspector) {
+    ClassSubject aClassSubject = inspector.clazz(A.class);
+    assertThat(aClassSubject, isPresent());
+    assertThat(aClassSubject.uniqueMethodWithName("m"), isPresent());
+
+    ClassSubject bClassSubject = inspector.clazz(B.class);
+    assertThat(bClassSubject, isPresent());
+    assertThat(bClassSubject.uniqueMethodWithName("bridge"), isPresent());
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      System.out.println(new B().bridge("Hello world!"));
+    }
+  }
+
+  @NeverMerge
+  static class A {
+
+    @NeverInline
+    public Object m(String arg) {
+      return System.currentTimeMillis() >= 0 ? arg : null;
+    }
+  }
+
+  @NeverClassInline
+  static class B extends A {
+
+    // This bridge is kept by a Proguard configuration rule and must therefore not be hoisted to A.
+    @NeverInline
+    public /*bridge*/ String bridge(Object o) {
+      return (String) m((String) o);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/NonReboundBridgeHoistingTest.java b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/NonReboundBridgeHoistingTest.java
new file mode 100644
index 0000000..362f6a2
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/NonReboundBridgeHoistingTest.java
@@ -0,0 +1,89 @@
+// 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.bridgeremoval.hoisting;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.bridgeremoval.hoisting.testclasses.NonReboundBridgeHoistingTestClasses;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class NonReboundBridgeHoistingTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public NonReboundBridgeHoistingTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(TestClass.class)
+        .addInnerClasses(NonReboundBridgeHoistingTestClasses.class)
+        .addProgramClassFileData(
+            transformer(C.class).setBridge(C.class.getDeclaredMethod("bridge")).transform())
+        .addKeepMainRule(TestClass.class)
+        .enableInliningAnnotations()
+        .enableMergeAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(this::inspect)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("Hello world!");
+  }
+
+  private void inspect(CodeInspector inspector) {
+    ClassSubject aClassSubject = inspector.clazz(NonReboundBridgeHoistingTestClasses.getClassA());
+    assertThat(aClassSubject, isPresent());
+    assertThat(aClassSubject.uniqueMethodWithName("m"), isPresent());
+    assertThat(aClassSubject.uniqueMethodWithName("bridge"), not(isPresent()));
+
+    ClassSubject bClassSubject = inspector.clazz(NonReboundBridgeHoistingTestClasses.B.class);
+    assertThat(bClassSubject, isPresent());
+
+    ClassSubject cClassSubject = inspector.clazz(C.class);
+    assertThat(cClassSubject, isPresent());
+    // TODO(b/153147967): This bridge should be hoisted to B.
+    assertThat(cClassSubject.uniqueMethodWithName("bridge"), isPresent());
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      new C().bridge();
+    }
+  }
+
+  @NeverClassInline
+  static class C extends NonReboundBridgeHoistingTestClasses.B {
+
+    // The invoke instruction in this bridge cannot be rewritten to target A.m(), since A is not
+    // accessible in this context. It therefore points to B.m(), where there is no definition of the
+    // method. As a result of this, we cannot move this bridge to A without also rewriting the
+    // signature referenced from the invoke instruction.
+    @NeverInline
+    public /*bridge*/ void bridge() {
+      m();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/NonSuperclassBridgeHoistingTest.java b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/NonSuperclassBridgeHoistingTest.java
new file mode 100644
index 0000000..353a9b9
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/NonSuperclassBridgeHoistingTest.java
@@ -0,0 +1,91 @@
+// 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.bridgeremoval.hoisting;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NeverMerge;
+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 com.android.tools.r8.utils.codeinspector.CodeInspector;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class NonSuperclassBridgeHoistingTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public NonSuperclassBridgeHoistingTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(TestClass.class, A.class)
+        .addProgramClassFileData(
+            transformer(B.class)
+                .setBridge(B.class.getDeclaredMethod("bridge", Object.class))
+                .transform())
+        .addKeepMainRule(TestClass.class)
+        .enableInliningAnnotations()
+        .enableMergeAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(this::inspect)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("Hello world!");
+  }
+
+  private void inspect(CodeInspector inspector) {
+    ClassSubject aClassSubject = inspector.clazz(A.class);
+    assertThat(aClassSubject, isPresent());
+    assertEquals(0, aClassSubject.getDexClass().virtualMethods().size());
+
+    ClassSubject b1ClassSubject = inspector.clazz(B.class);
+    assertThat(b1ClassSubject, isPresent());
+    assertThat(b1ClassSubject.uniqueMethodWithName("m"), isPresent());
+    assertThat(b1ClassSubject.uniqueMethodWithName("bridge"), isPresent());
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      System.out.println(new B().bridge("Hello world!"));
+    }
+  }
+
+  @NeverMerge
+  static class A {}
+
+  @NeverClassInline
+  static class B extends A {
+
+    @NeverInline
+    public Object m(String arg) {
+      return System.currentTimeMillis() >= 0 ? arg : null;
+    }
+
+    // This bridge cannot be hoisted to A, since it targets a method on the enclosing class.
+    // Hoisting the bridge to A would lead to a NoSuchMethodError.
+    @NeverInline
+    public /*bridge*/ String bridge(Object o) {
+      return (String) m((String) o);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/PositiveBridgeHoistingTest.java b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/PositiveBridgeHoistingTest.java
new file mode 100644
index 0000000..50fc23c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/PositiveBridgeHoistingTest.java
@@ -0,0 +1,146 @@
+// 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.bridgeremoval.hoisting;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+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 com.android.tools.r8.utils.codeinspector.CodeInspector;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class PositiveBridgeHoistingTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public PositiveBridgeHoistingTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(TestClass.class, A.class, B3.class)
+        .addProgramClassFileData(
+            transformer(B1.class)
+                .setBridge(B1.class.getDeclaredMethod("superBridge", Object.class))
+                .setBridge(B1.class.getDeclaredMethod("virtualBridge", Object.class))
+                .transform(),
+            transformer(B2.class)
+                .setBridge(B2.class.getDeclaredMethod("superBridge", Object.class))
+                .setBridge(B2.class.getDeclaredMethod("virtualBridge", Object.class))
+                .transform())
+        .addKeepMainRule(TestClass.class)
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(this::inspect)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("Hello world!");
+  }
+
+  private void inspect(CodeInspector inspector) {
+    ClassSubject aClassSubject = inspector.clazz(A.class);
+    assertThat(aClassSubject, isPresent());
+    assertThat(aClassSubject.uniqueMethodWithName("m"), isPresent());
+    // TODO(b/153147967): This should become present after hoisting.
+    assertThat(aClassSubject.uniqueMethodWithName("superBridge"), not(isPresent()));
+    // TODO(b/153147967): This should become present after hoisting.
+    assertThat(aClassSubject.uniqueMethodWithName("virtualBridge"), not(isPresent()));
+
+    ClassSubject b1ClassSubject = inspector.clazz(B1.class);
+    assertThat(b1ClassSubject, isPresent());
+    // TODO(b/153147967): This bridge should be hoisted to A.
+    assertThat(b1ClassSubject.uniqueMethodWithName("superBridge"), isPresent());
+    // TODO(b/153147967): This bridge should be hoisted to A.
+    assertThat(b1ClassSubject.uniqueMethodWithName("virtualBridge"), isPresent());
+
+    ClassSubject b2ClassSubject = inspector.clazz(B2.class);
+    assertThat(b2ClassSubject, isPresent());
+    // TODO(b/153147967): This bridge should be hoisted to A.
+    assertThat(b2ClassSubject.uniqueMethodWithName("superBridge"), isPresent());
+    // TODO(b/153147967): This bridge should be hoisted to A.
+    assertThat(b2ClassSubject.uniqueMethodWithName("virtualBridge"), isPresent());
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      System.out.print(new B1().superBridge("Hello"));
+      System.out.print(new B1().virtualBridge(" "));
+      System.out.print(new B2().superBridge("world"));
+      System.out.print(new B2().virtualBridge("!"));
+      System.out.println(new B3().m(""));
+    }
+  }
+
+  static class A {
+
+    @NeverInline
+    public Object m(String arg) {
+      return System.currentTimeMillis() >= 0 ? arg : null;
+    }
+  }
+
+  @NeverClassInline
+  static class B1 extends A {
+
+    // This bridge can be hoisted to A if the invoke-super instruction is rewritten to an
+    // invoke-virtual instruction.
+    @NeverInline
+    public /*bridge*/ String superBridge(Object o) {
+      return (String) super.m((String) o);
+    }
+
+    // This bridge can be hoisted to A.
+    @NeverInline
+    public /*bridge*/ String virtualBridge(Object o) {
+      return (String) m((String) o);
+    }
+  }
+
+  @NeverClassInline
+  static class B2 extends A {
+
+    // By hoisting B1.superBridge() to A this method bridge redundant.
+    @NeverInline
+    public /*bridge*/ String superBridge(Object o) {
+      return (String) super.m((String) o);
+    }
+
+    // By hoisting B1.virtualBridge() to A this method bridge redundant.
+    @NeverInline
+    public /*bridge*/ String virtualBridge(Object o) {
+      return (String) m((String) o);
+    }
+  }
+
+  // The fact that this class does not declare superBridge() or virtualBridge() should not prevent
+  // us from hoisting these bridges from B1/B2 to A.
+  //
+  // Strictly speaking, there could be an invoke-virtual instruction that targets B3.virtualBridge()
+  // and fails with a NoSuchMethodError in the input program. After hoisting B1.virtualBridge() to A
+  // such an instruction would no longer fail with a NoSuchMethodError in the generated program.
+  //
+  // If this ever turns out be an issue, it would be possible to track if there is an invoke
+  // instruction targeting B3.virtualBridge() that fails with a NoSuchMethodError in the Enqueuer,
+  // but this should never be the case in practice.
+  @NeverClassInline
+  static class B3 extends A {}
+}
diff --git a/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/testclasses/BridgeHoistingAccessibilityTestClasses.java b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/testclasses/BridgeHoistingAccessibilityTestClasses.java
new file mode 100644
index 0000000..bc91e00
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/testclasses/BridgeHoistingAccessibilityTestClasses.java
@@ -0,0 +1,29 @@
+// 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.bridgeremoval.hoisting.testclasses;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NeverMerge;
+import com.android.tools.r8.bridgeremoval.hoisting.BridgeHoistingAccessibilityTest;
+
+public class BridgeHoistingAccessibilityTestClasses {
+
+  @NeverMerge
+  public static class A {
+
+    @NeverInline
+    public Object m(String arg) {
+      return System.currentTimeMillis() > 0 ? arg : null;
+    }
+  }
+
+  public static class User {
+
+    @NeverInline
+    public static String invokeBridgeC(BridgeHoistingAccessibilityTest.C instance) {
+      return instance.bridgeC(" world!");
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/testclasses/NonReboundBridgeHoistingTestClasses.java b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/testclasses/NonReboundBridgeHoistingTestClasses.java
new file mode 100644
index 0000000..f66c6a3
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/bridgeremoval/hoisting/testclasses/NonReboundBridgeHoistingTestClasses.java
@@ -0,0 +1,27 @@
+// 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.bridgeremoval.hoisting.testclasses;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NeverMerge;
+
+public class NonReboundBridgeHoistingTestClasses {
+
+  public static Class<A> getClassA() {
+    return A.class;
+  }
+
+  @NeverMerge
+  static class A {
+
+    @NeverInline
+    public void m() {
+      System.out.println("Hello world!");
+    }
+  }
+
+  @NeverMerge
+  public static class B extends A {}
+}
diff --git a/src/test/java/com/android/tools/r8/cfmethodgeneration/MethodGenerationBase.java b/src/test/java/com/android/tools/r8/cfmethodgeneration/MethodGenerationBase.java
index 3240d08..9cffd4e 100644
--- a/src/test/java/com/android/tools/r8/cfmethodgeneration/MethodGenerationBase.java
+++ b/src/test/java/com/android/tools/r8/cfmethodgeneration/MethodGenerationBase.java
@@ -47,7 +47,7 @@
 
   protected abstract List<Class<?>> getMethodTemplateClasses();
 
-  private String getHeaderString(Class<? extends MethodGenerationBase> generationClass) {
+  public static String getHeaderString(Class<?> generationClass, String generatedPackage) {
     int year = Calendar.getInstance().get(Calendar.YEAR);
     String simpleName = generationClass.getSimpleName();
     return StringUtils.lines(
@@ -59,7 +59,7 @@
         "// GENERATED FILE. DO NOT EDIT! See " + simpleName + ".java.",
         "// ***********************************************************************************",
         "",
-        "package " + getGeneratedClassPackageName() + ";");
+        "package " + generatedPackage + ";");
   }
 
   protected Path getGeneratedFile() {
@@ -116,7 +116,7 @@
 
   private void generateRawOutput(CfCodePrinter codePrinter, Path tempFile) throws IOException {
     try (PrintStream printer = new PrintStream(Files.newOutputStream(tempFile))) {
-      printer.print(getHeaderString(this.getClass()));
+      printer.print(getHeaderString(this.getClass(), getGeneratedClassPackageName()));
       printer.println("import com.android.tools.r8.graph.DexItemFactory;");
       codePrinter.getImports().forEach(i -> printer.println("import " + i + ";"));
       printer.println("public final class " + getGeneratedClassName() + " {\n");
@@ -131,7 +131,7 @@
     }
   }
 
-  private String formatRawOutput(Path tempFile) throws IOException {
+  public static String formatRawOutput(Path tempFile) throws IOException {
     // Apply google format.
     ProcessBuilder builder =
         new ProcessBuilder(
diff --git a/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingArrayTest.java b/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingArrayTest.java
index c97b7a7..d9c9350 100644
--- a/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingArrayTest.java
+++ b/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingArrayTest.java
@@ -22,6 +22,7 @@
     EnumVarArgs.class,
     EnumArrayReadWriteNoEscape.class,
     EnumArrayReadWrite.class,
+    EnumArrayNullRead.class,
     Enum2DimArrayReadWrite.class
   };
 
@@ -144,6 +145,24 @@
     }
   }
 
+  static class EnumArrayNullRead {
+
+    @SuppressWarnings("ConstantConditions")
+    public static void main(String[] args) {
+      try {
+        System.out.println(((MyEnum[]) null)[0]);
+      } catch (NullPointerException ignored) {
+      }
+    }
+
+    @NeverClassInline
+    enum MyEnum {
+      A,
+      B,
+      C;
+    }
+  }
+
   static class Enum2DimArrayReadWrite {
 
     public static void main(String[] args) {
diff --git a/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingClassStaticizerTest.java b/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingClassStaticizerTest.java
new file mode 100644
index 0000000..6fb5fd1
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingClassStaticizerTest.java
@@ -0,0 +1,126 @@
+// 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.enumunboxing;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static junit.framework.TestCase.assertEquals;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.R8TestRunResult;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class EnumUnboxingClassStaticizerTest extends EnumUnboxingTestBase {
+
+  private final TestParameters parameters;
+  private final boolean enumValueOptimization;
+  private final KeepRule enumKeepRules;
+
+  @Parameterized.Parameters(name = "{0} valueOpt: {1} keep: {2}")
+  public static List<Object[]> data() {
+    return enumUnboxingTestParameters();
+  }
+
+  public EnumUnboxingClassStaticizerTest(
+      TestParameters parameters, boolean enumValueOptimization, KeepRule enumKeepRules) {
+    this.parameters = parameters;
+    this.enumValueOptimization = enumValueOptimization;
+    this.enumKeepRules = enumKeepRules;
+  }
+
+  @Test
+  public void testEnumUnboxing() throws Exception {
+    R8TestRunResult run =
+        testForR8(parameters.getBackend())
+            .addInnerClasses(EnumUnboxingClassStaticizerTest.class)
+            .addKeepMainRule(TestClass.class)
+            .addKeepRules(enumKeepRules.getKeepRule())
+            .enableNeverClassInliningAnnotations()
+            .enableInliningAnnotations()
+            .noMinification() // For assertions.
+            .addOptionsModification(opt -> enableEnumOptions(opt, enumValueOptimization))
+            .allowDiagnosticInfoMessages()
+            .setMinApi(parameters.getApiLevel())
+            .compile()
+            .inspect(this::assertClassStaticized)
+            .inspectDiagnosticMessages(
+                m ->
+                    assertEnumIsUnboxed(
+                        UnboxableEnum.class,
+                        EnumUnboxingClassStaticizerTest.class.getSimpleName(),
+                        m))
+            .run(parameters.getRuntime(), TestClass.class)
+            .assertSuccess();
+    assertLines2By2Correct(run.getStdOut());
+  }
+
+  private void assertClassStaticized(CodeInspector codeInspector) {
+    if (parameters.isCfRuntime()) {
+      // There is no class staticizer in Cf.
+      assertThat(codeInspector.clazz(Companion.class).uniqueMethodWithName("method"), isPresent());
+      return;
+    }
+    MethodSubject method = codeInspector.clazz(CompanionHost.class).uniqueMethodWithName("method");
+    assertThat(method, isPresent());
+    assertEquals("int", method.getMethod().method.proto.parameters.toString());
+  }
+
+  static class TestClass {
+    public static void main(String[] args) {
+      CompanionHost.toKeep();
+      test(UnboxableEnum.A);
+      System.out.println("0");
+      test(UnboxableEnum.B);
+      System.out.println("1");
+      test(UnboxableEnum.C);
+      System.out.println("2");
+    }
+
+    @NeverInline
+    static void test(UnboxableEnum obj) {
+      // The class staticizer will move Companion.method() into CompanionHost.method().
+      // As a result of this transformation, this call site will need to be processed.
+      // To keep track of this, the staticizer will keep a reference to the method
+      // `void test(UnboxableEnum)`, but after enum unboxing this has been rewritten to
+      // `void test(int)`. Therefore, the staticizer's internal structure needs to be
+      // updated after enum unboxing.
+      CompanionHost.COMPANION.method(obj);
+    }
+  }
+
+  @NeverClassInline
+  static class CompanionHost {
+    static final Companion COMPANION = new Companion();
+
+    @NeverInline
+    static void toKeep() {
+      System.out.println("Keep me!");
+      System.out.println("Keep me!");
+    }
+  }
+
+  @NeverClassInline
+  static class Companion {
+    @NeverInline
+    public void method(UnboxableEnum obj) {
+      System.out.println(obj.ordinal());
+    }
+  }
+
+  @NeverClassInline
+  enum UnboxableEnum {
+    A,
+    B,
+    C;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingTestBase.java b/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingTestBase.java
index e367418..9f7b5bd 100644
--- a/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingTestBase.java
+++ b/src/test/java/com/android/tools/r8/enumunboxing/EnumUnboxingTestBase.java
@@ -77,7 +77,9 @@
     Diagnostic diagnostic = m.getInfos().get(0);
     assertTrue(diagnostic.getDiagnosticMessage().startsWith("Unboxed enums"));
     assertTrue(
-        "Expected enum to be removed (" + testName + "): ",
+        StringUtils.joinLines(
+            "Expected enum to be removed (" + testName + "):",
+            m.getInfos().get(1).getDiagnosticMessage()),
         diagnostic.getDiagnosticMessage().contains(enumClass.getSimpleName()));
   }
 
@@ -86,7 +88,7 @@
     Diagnostic diagnostic = m.getInfos().get(1);
     assertTrue(diagnostic.getDiagnosticMessage().startsWith("Boxed enums"));
     assertTrue(
-        "Expected enum NOT to be removed (" + testName + "): ",
+        "Expected enum NOT to be removed (" + testName + ")",
         diagnostic.getDiagnosticMessage().contains(enumClass.getSimpleName()));
   }
 
diff --git a/src/test/java/com/android/tools/r8/enumunboxing/JavaCGeneratedMethodTest.java b/src/test/java/com/android/tools/r8/enumunboxing/JavaCGeneratedMethodTest.java
new file mode 100644
index 0000000..728a346
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/enumunboxing/JavaCGeneratedMethodTest.java
@@ -0,0 +1,72 @@
+// 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.enumunboxing;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.R8TestRunResult;
+import com.android.tools.r8.TestParameters;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class JavaCGeneratedMethodTest extends EnumUnboxingTestBase {
+
+  private static final Class<?> ENUM_CLASS = MyEnum.class;
+
+  private final TestParameters parameters;
+  private final boolean enumValueOptimization;
+  private final KeepRule enumKeepRules;
+
+  @Parameterized.Parameters(name = "{0} valueOpt: {1} keep: {2}")
+  public static List<Object[]> data() {
+    return enumUnboxingTestParameters();
+  }
+
+  public JavaCGeneratedMethodTest(
+      TestParameters parameters, boolean enumValueOptimization, KeepRule enumKeepRules) {
+    this.parameters = parameters;
+    this.enumValueOptimization = enumValueOptimization;
+    this.enumKeepRules = enumKeepRules;
+  }
+
+  @Test
+  public void testEnumUnboxing() throws Exception {
+    Class<?> classToTest = Ordinal.class;
+    R8TestRunResult run =
+        testForR8(parameters.getBackend())
+            .addProgramClasses(classToTest, ENUM_CLASS)
+            .addKeepMainRule(classToTest)
+            .addKeepRules(enumKeepRules.getKeepRule())
+            .enableNeverClassInliningAnnotations()
+            .addOptionsModification(opt -> enableEnumOptions(opt, enumValueOptimization))
+            .addOptionsModification(
+                opt -> opt.testing.enumUnboxingRewriteJavaCGeneratedMethod = true)
+            .allowDiagnosticInfoMessages()
+            .setMinApi(parameters.getApiLevel())
+            .compile()
+            .inspectDiagnosticMessages(
+                m -> assertEnumIsUnboxed(ENUM_CLASS, classToTest.getSimpleName(), m))
+            .run(parameters.getRuntime(), classToTest)
+            .assertSuccess();
+    assertLines2By2Correct(run.getStdOut());
+  }
+
+  @NeverClassInline
+  enum MyEnum {
+    A,
+    B,
+    C
+  }
+
+  static class Ordinal {
+
+    public static void main(String[] args) {
+      System.out.println(MyEnum.A.ordinal());
+      System.out.println(0);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/R8InliningTest.java b/src/test/java/com/android/tools/r8/ir/optimize/R8InliningTest.java
index 3b77ead..49718d4 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/R8InliningTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/R8InliningTest.java
@@ -14,6 +14,7 @@
 import com.android.tools.r8.ToolHelper.ProcessResult;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.ir.optimize.enums.EnumUnboxingRewriter;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.BooleanUtils;
 import com.android.tools.r8.utils.FileUtils;
@@ -356,11 +357,8 @@
     assertEquals(1, instanceGetCount);
     assertEquals(0, invokeCount);
 
-    m =
-        clazz.method(
-            "int",
-            "moreControlFlows",
-            ImmutableList.of("inlining.A", "inlining.Nullability$Factor"));
+    // The enum parameter may get unboxed.
+    m = clazz.uniqueMethodWithName("moreControlFlows");
     assertTrue(m.isPresent());
 
     // Verify that a.b() is resolved to an inline instance-get.
@@ -372,6 +370,11 @@
       if (instruction.isInstanceGet()) {
         ++instanceGetCount;
       } else if (instruction.isInvoke()
+          && !instruction
+              .getMethod()
+              .name
+              .toString()
+              .equals(EnumUnboxingRewriter.ENUM_UNBOXING_UTILITY_ORDINAL)
           && !((InvokeInstructionSubject) instruction)
               .holder()
               .toString()
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliningOracleTest.java b/src/test/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliningOracleTest.java
index d35a11d..bd87a92 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliningOracleTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliningOracleTest.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.ir.optimize.classinliner;
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
 import static org.hamcrest.MatcherAssert.assertThat;
 
 import com.android.tools.r8.KeepUnusedArguments;
@@ -12,25 +13,57 @@
 import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.NeverMerge;
 import com.android.tools.r8.TestBase;
-import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.utils.BooleanUtils;
+import java.util.List;
 import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
 
 /** Regression test for b/121119666. */
+@RunWith(Parameterized.class)
 public class ClassInliningOracleTest extends TestBase {
 
+  private final boolean enableInvokeSuperToInvokeVirtualRewriting;
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{1}, enable invoke-super to invoke-virtual rewriting: {0}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        BooleanUtils.values(), getTestParameters().withAllRuntimesAndApiLevels().build());
+  }
+
+  public ClassInliningOracleTest(
+      boolean enableInvokeSuperToInvokeVirtualRewriting, TestParameters parameters) {
+    this.enableInvokeSuperToInvokeVirtualRewriting = enableInvokeSuperToInvokeVirtualRewriting;
+    this.parameters = parameters;
+  }
+
   @Test
   public void test() throws Exception {
-    CodeInspector inspector =
-        testForR8(Backend.DEX)
-            .addInnerClasses(ClassInliningOracleTest.class)
-            .addKeepMainRule(TestClass.class)
-            .enableInliningAnnotations()
-            .enableNeverClassInliningAnnotations()
-            .enableMergeAnnotations()
-            .enableUnusedArgumentAnnotations()
-            .compile()
-            .inspector();
-    assertThat(inspector.clazz(Builder.class), isPresent());
+    testForR8(parameters.getBackend())
+        .addInnerClasses(ClassInliningOracleTest.class)
+        .addKeepMainRule(TestClass.class)
+        .addOptionsModification(
+            options ->
+                options.testing.enableInvokeSuperToInvokeVirtualRewriting =
+                    enableInvokeSuperToInvokeVirtualRewriting)
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .enableMergeAnnotations()
+        .enableUnusedArgumentAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(
+            inspector -> {
+              if (enableInvokeSuperToInvokeVirtualRewriting) {
+                assertThat(inspector.clazz(Builder.class), not(isPresent()));
+              } else {
+                assertThat(inspector.clazz(Builder.class), isPresent());
+              }
+            })
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccess();
   }
 
   static class TestClass {
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/InvokeSuperToInvokeVirtualTest.java b/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/InvokeSuperToInvokeVirtualTest.java
new file mode 100644
index 0000000..a85906b
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/devirtualize/InvokeSuperToInvokeVirtualTest.java
@@ -0,0 +1,124 @@
+// 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.ir.optimize.devirtualize;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NeverMerge;
+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 com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.InstructionSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class InvokeSuperToInvokeVirtualTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public InvokeSuperToInvokeVirtualTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(InvokeSuperToInvokeVirtualTest.class)
+        .addKeepMainRule(TestClass.class)
+        .enableInliningAnnotations()
+        .enableMergeAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(this::inspect)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("Hello world!");
+  }
+
+  private void inspect(CodeInspector inspector) {
+    ClassSubject bClassSubject = inspector.clazz(B.class);
+    assertThat(bClassSubject, isPresent());
+
+    MethodSubject negativeTestSubject = bClassSubject.uniqueMethodWithName("negativeTest");
+    assertThat(negativeTestSubject, isPresent());
+    assertTrue(negativeTestSubject.streamInstructions().anyMatch(this::isInvokeSuper));
+    assertTrue(
+        negativeTestSubject.streamInstructions().noneMatch(InstructionSubject::isInvokeVirtual));
+
+    MethodSubject positiveTestSubject = bClassSubject.uniqueMethodWithName("positiveTest");
+    assertThat(positiveTestSubject, isPresent());
+    assertTrue(positiveTestSubject.streamInstructions().noneMatch(this::isInvokeSuper));
+    assertTrue(
+        positiveTestSubject.streamInstructions().anyMatch(InstructionSubject::isInvokeVirtual));
+  }
+
+  private boolean isInvokeSuper(InstructionSubject instruction) {
+    if (parameters.isCfRuntime()) {
+      return instruction.isInvokeSpecial();
+    } else {
+      return instruction.asDexInstruction().isInvokeSuper();
+    }
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      new B().negativeTest();
+      new B().positiveTest();
+
+      if (System.currentTimeMillis() < 0) {
+        // To keep B.hello().
+        new B().hello();
+      }
+    }
+  }
+
+  @NeverMerge
+  static class A {
+
+    @NeverInline
+    void hello() {
+      System.out.print("Hello");
+    }
+
+    @NeverInline
+    void world() {
+      System.out.println(" world!");
+    }
+  }
+
+  @NeverClassInline
+  static class B extends A {
+
+    @Override
+    void hello() {
+      System.out.println("Unexpected!");
+    }
+
+    @NeverInline
+    void negativeTest() {
+      super.hello();
+    }
+
+    @NeverInline
+    void positiveTest() {
+      super.world();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/inliner/InlineCatchHandlerWithLibraryTypeTest.java b/src/test/java/com/android/tools/r8/ir/optimize/inliner/InlineCatchHandlerWithLibraryTypeTest.java
new file mode 100644
index 0000000..15e37c1
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/inliner/InlineCatchHandlerWithLibraryTypeTest.java
@@ -0,0 +1,171 @@
+// 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.ir.optimize.inliner;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.R8TestRunResult;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.DexVm.Version;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.DescriptorUtils;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Streams;
+import java.io.IOException;
+import java.util.List;
+import java.util.Map;
+import java.util.TreeSet;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+/** This test extends that of Regress131349148 for other API-introduced exceptions. */
+@RunWith(Parameterized.class)
+public class InlineCatchHandlerWithLibraryTypeTest extends TestBase {
+
+  private static final String TEMPLATE_CODE_EXCEPTION_BINARY_NAME = "java/lang/RuntimeException";
+
+  // A subset of exception types introduced in API levels between 16 to 24.
+  private static final Map<String, Integer> EXCEPTIONS =
+      ImmutableMap.<String, Integer>builder()
+          // VM 4.0.4 (api 15) is the first VM we have so no need to go prior to that.
+          .put("android.media.MediaCryptoException", 16)
+          .put("android.view.WindowManager$InvalidDisplayException", 17)
+          .put("android.media.DeniedByServerException", 18)
+          .put("android.media.ResourceBusyException", 19)
+          .put("java.lang.ReflectiveOperationException", 19)
+          .put("javax.crypto.AEADBadTagException", 19)
+          .put("android.system.ErrnoException", 21)
+          .put("android.media.MediaDrmResetException", 23)
+          .put("java.io.UncheckedIOException", 24)
+          .put("java.util.concurrent.CompletionException", 24)
+          // Verify error was fixed in 21 so up to 24 should catch post-fix issues.
+          .build();
+
+  private static final String EXPECTED = StringUtils.lines("Done...");
+
+  private final TestParameters parameters;
+  private final String exception;
+
+  @Parameters(name = "{0}, {1}")
+  public static List<Object[]> params() {
+    return buildParameters(
+        getTestParameters().withAllRuntimesAndApiLevels().build(),
+        new TreeSet<>(EXCEPTIONS.keySet()));
+  }
+
+  public InlineCatchHandlerWithLibraryTypeTest(TestParameters parameters, String exception) {
+    this.parameters = parameters;
+    this.exception = exception;
+  }
+
+  private String getExceptionBinaryName() {
+    return DescriptorUtils.getBinaryNameFromJavaType(exception);
+  }
+
+  private byte[] getClassWithCatchHandler() throws IOException {
+    return transformer(ClassWithCatchHandler.class)
+        .transformTryCatchBlock(
+            "methodWithCatch",
+            (start, end, handler, type, continuation) -> {
+              String newType =
+                  type.equals(TEMPLATE_CODE_EXCEPTION_BINARY_NAME)
+                      ? getExceptionBinaryName()
+                      : type;
+              continuation.apply(start, end, handler, newType);
+            })
+        .transform();
+  }
+
+  private boolean compilationTargetIsMissingExceptionType() {
+    // A CF target could target any API in the end.
+    return parameters.isCfRuntime()
+        || parameters.getApiLevel().getLevel() < EXCEPTIONS.get(exception);
+  }
+
+  private boolean compileTargetHasVerificationBug() {
+    // A CF target could target any API in the end.
+    return parameters.isCfRuntime() || parameters.getApiLevel().isLessThan(AndroidApiLevel.L);
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .enableInliningAnnotations()
+        .addProgramClasses(TestClass.class)
+        .addProgramClassFileData(getClassWithCatchHandler())
+        .addKeepMainRule(TestClass.class)
+        .setMinApi(parameters.getApiLevel())
+        // Use the latest library so that all of the exceptions are defined.
+        .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.LATEST))
+        .compile()
+        .inspect(this::checkInlined)
+        .run(parameters.getRuntime(), TestClass.class)
+        .apply(this::checkResult);
+  }
+
+  private void checkResult(R8TestRunResult runResult) {
+    // The bootclasspath for our build of 4.4.4 does not contain various bits. Allow verify error.
+    if (!compilationTargetIsMissingExceptionType()
+        && parameters.getRuntime().asDex().getVm().getVersion().equals(Version.V4_4_4)
+        && (exception.startsWith("android.media") || exception.startsWith("android.view"))) {
+      runResult.assertFailureWithErrorThatThrows(VerifyError.class);
+      return;
+    }
+    // Correct compilation should ensure that all programs run without error.
+    runResult.assertSuccessWithOutput(EXPECTED);
+  }
+
+  private void checkInlined(CodeInspector inspector) {
+    ClassSubject classSubject = inspector.clazz(TestClass.class);
+    boolean mainHasInlinedCatchHandler =
+        Streams.stream(classSubject.mainMethod().iterateTryCatches())
+            .anyMatch(tryCatch -> tryCatch.isCatching(exception));
+    if (compileTargetHasVerificationBug() && compilationTargetIsMissingExceptionType()) {
+      assertFalse(mainHasInlinedCatchHandler);
+    } else {
+      assertTrue(mainHasInlinedCatchHandler);
+    }
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      if (args.length == 200) {
+        // Never called
+        ClassWithCatchHandler.methodWithCatch();
+      }
+      System.out.println("Done...");
+    }
+  }
+
+  static class ClassWithCatchHandler {
+
+    @NeverInline
+    public static void maybeThrow() {
+      if (System.nanoTime() > 0) {
+        throw new RuntimeException();
+      }
+    }
+
+    public static void methodWithCatch() {
+      try {
+        maybeThrow();
+      } catch (RuntimeException e) {
+        // We must use the exception, otherwise there is no move-exception that triggers the
+        // verification error.
+        System.out.println(e.getClass().getName());
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/inliner/InlineCatchHandlerWithProgramTypeTest.java b/src/test/java/com/android/tools/r8/ir/optimize/inliner/InlineCatchHandlerWithProgramTypeTest.java
new file mode 100644
index 0000000..bcb4b9b
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/inliner/InlineCatchHandlerWithProgramTypeTest.java
@@ -0,0 +1,85 @@
+// 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.ir.optimize.inliner;
+
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.NeverInline;
+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 com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.google.common.collect.Streams;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+/** Simple test to ensure that we do inline program defined types used in catch handler guards. */
+@RunWith(Parameterized.class)
+public class InlineCatchHandlerWithProgramTypeTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public InlineCatchHandlerWithProgramTypeTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(InlineCatchHandlerWithProgramTypeTest.class)
+        .addKeepMainRule(TestClass.class)
+        .enableInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("Done...")
+        .inspect(this::checkInlined);
+  }
+
+  private void checkInlined(CodeInspector inspector) {
+    ClassSubject classSubject = inspector.clazz(TestClass.class);
+    ClassSubject exceptionSubject = inspector.clazz(MyException.class);
+    boolean mainHasInlinedCatchHandler =
+        Streams.stream(classSubject.mainMethod().iterateTryCatches())
+            .anyMatch(tryCatch -> tryCatch.isCatching(exceptionSubject.getFinalName()));
+    assertTrue(mainHasInlinedCatchHandler);
+  }
+
+  static class MyException extends RuntimeException {}
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      if (args.length == 200) {
+        // Never called
+        ClassWithCatchHandler.methodWithCatch();
+      }
+      System.out.println("Done...");
+    }
+  }
+
+  static class ClassWithCatchHandler {
+
+    @NeverInline
+    public static void maybeThrow() {
+      if (System.nanoTime() > 0) {
+        throw new MyException();
+      }
+    }
+
+    public static void methodWithCatch() {
+      try {
+        maybeThrow();
+      } catch (MyException e) {
+        System.out.println(e.getClass().getName());
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/inliner/Regress131349148.java b/src/test/java/com/android/tools/r8/ir/optimize/inliner/Regress131349148.java
index 98a6e9e..287fe21 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/inliner/Regress131349148.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/inliner/Regress131349148.java
@@ -49,7 +49,7 @@
             .anyMatch(
                 tryCatch -> tryCatch.isCatching("java.lang.ReflectiveOperationException"));
     int runtimeLevel = parameters.getApiLevel().getLevel();
-    assertEquals(runtimeLevel >= AndroidApiLevel.L.getLevel(), mainHasReflectiveOperationException);
+    assertEquals(runtimeLevel >= AndroidApiLevel.K.getLevel(), mainHasReflectiveOperationException);
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/rewrite/enums/EnumValuesLengthTest.java b/src/test/java/com/android/tools/r8/rewrite/enums/EnumValuesLengthTest.java
index 7a5300d..176e6f5 100644
--- a/src/test/java/com/android/tools/r8/rewrite/enums/EnumValuesLengthTest.java
+++ b/src/test/java/com/android/tools/r8/rewrite/enums/EnumValuesLengthTest.java
@@ -11,10 +11,15 @@
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
 import com.android.tools.r8.utils.codeinspector.FoundClassSubject;
 import com.android.tools.r8.utils.codeinspector.FoundMethodSubject;
 import com.android.tools.r8.utils.codeinspector.InstructionSubject;
+import java.io.IOException;
+import java.nio.file.Path;
+import java.util.Collection;
+import java.util.Collections;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -57,6 +62,7 @@
   @Test
   public void testValuesLengthSwitchMapRemoved() throws Exception {
     // Make sure SwitchMap can still be removed with valuesLength optimization.
+    assertSwitchMapPresent();
     testForR8(parameters.getBackend())
         .addKeepMainRule(Main.class)
         .addInnerClasses(EnumValuesLengthTest.class)
@@ -72,10 +78,15 @@
         .assertSuccessWithOutputLines("0", "2", "5", "a", "D", "c", "D");
   }
 
+  private void assertSwitchMapPresent() throws IOException {
+    Collection<Path> classFilesForInnerClasses =
+        ToolHelper.getClassFilesForInnerClasses(
+            Collections.singletonList(EnumValuesLengthTest.class));
+    assertTrue(classFilesForInnerClasses.stream().anyMatch(p -> p.toString().endsWith("$1.class")));
+  }
+
   private void assertSwitchMapRemoved(CodeInspector inspector) {
-    assertTrue(
-        inspector.allClasses().stream()
-            .noneMatch(c -> !c.getDexClass().isEnum() && !c.getFinalName().endsWith("Main")));
+    assertTrue(inspector.allClasses().stream().noneMatch(c -> c.getOriginalName().endsWith("$1")));
   }
 
   private void assertValuesLengthRemoved(CodeInspector inspector) {
diff --git a/src/test/java/com/android/tools/r8/transformers/ClassFileTransformer.java b/src/test/java/com/android/tools/r8/transformers/ClassFileTransformer.java
index 38a6346..c67c66c 100644
--- a/src/test/java/com/android/tools/r8/transformers/ClassFileTransformer.java
+++ b/src/test/java/com/android/tools/r8/transformers/ClassFileTransformer.java
@@ -28,6 +28,7 @@
 import org.objectweb.asm.ClassReader;
 import org.objectweb.asm.ClassVisitor;
 import org.objectweb.asm.ClassWriter;
+import org.objectweb.asm.Label;
 import org.objectweb.asm.MethodVisitor;
 
 public class ClassFileTransformer {
@@ -301,6 +302,10 @@
             });
   }
 
+  public ClassFileTransformer setBridge(Method method) {
+    return setAccessFlags(method, MethodAccessFlags::setBridge);
+  }
+
   public ClassFileTransformer setPublic(Method method) {
     return setAccessFlags(
         method,
@@ -405,6 +410,21 @@
     void apply(int opcode, String type);
   }
 
+  @FunctionalInterface
+  public interface TryCatchBlockTransform {
+    void visitTryCatchBlock(
+        Label start,
+        Label end,
+        Label handler,
+        String type,
+        TryCatchBlockTransformContinuation continuation);
+  }
+
+  @FunctionalInterface
+  public interface TryCatchBlockTransformContinuation {
+    void apply(Label start, Label end, Label handler, String type);
+  }
+
   public ClassFileTransformer transformMethodInsnInMethod(
       String methodName, MethodInsnTransform transform) {
     return addMethodTransformer(
@@ -437,6 +457,21 @@
         });
   }
 
+  public ClassFileTransformer transformTryCatchBlock(
+      String methodName, TryCatchBlockTransform transform) {
+    return addMethodTransformer(
+        new MethodTransformer() {
+          @Override
+          public void visitTryCatchBlock(Label start, Label end, Label handler, String type) {
+            if (getContext().method.getMethodName().equals(methodName)) {
+              transform.visitTryCatchBlock(start, end, handler, type, super::visitTryCatchBlock);
+            } else {
+              super.visitTryCatchBlock(start, end, handler, type);
+            }
+          }
+        });
+  }
+
   /** Abstraction of the MethodVisitor.visitLdcInsn method with its continuation. */
   @FunctionalInterface
   public interface LdcInsnTransform {
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/CfInstructionSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/CfInstructionSubject.java
index b2c8b6f..2387655 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/CfInstructionSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/CfInstructionSubject.java
@@ -50,6 +50,11 @@
   }
 
   @Override
+  public DexInstructionSubject asDexInstruction() {
+    return null;
+  }
+
+  @Override
   public boolean isFieldAccess() {
     return instruction instanceof CfFieldInstruction;
   }
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/DexInstructionSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/DexInstructionSubject.java
index e487726..0335a5d 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/DexInstructionSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/DexInstructionSubject.java
@@ -116,6 +116,11 @@
   }
 
   @Override
+  public DexInstructionSubject asDexInstruction() {
+    return this;
+  }
+
+  @Override
   public boolean isFieldAccess() {
     return isInstanceGet() || isInstancePut() || isStaticGet() || isStaticPut();
   }
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/InstructionSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/InstructionSubject.java
index 6eba32b..c5ca6c9 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/InstructionSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/InstructionSubject.java
@@ -16,6 +16,8 @@
     DISALLOW
   };
 
+  DexInstructionSubject asDexInstruction();
+
   boolean isFieldAccess();
 
   boolean isInstancePut();
diff --git a/tools/internal_test.py b/tools/internal_test.py
index d8e8c62..9309237 100755
--- a/tools/internal_test.py
+++ b/tools/internal_test.py
@@ -111,6 +111,8 @@
       '--find-min-xmx-archive']
 
 def compile_with_memory_max_command(record):
+  # TODO(b/152939233): Remove this special handling when fixed.
+  factor = 1.25 if record['app'] == 'chrome' else 1.15
   return [] if 'skip-find-xmx-max' in record else [
       'tools/run_on_app.py',
       '--compiler=r8',
@@ -119,7 +121,7 @@
       '--version=%s' % record['version'],
       '--no-debug',
       '--no-build',
-      '--max-memory=%s' % int(record['oom-threshold'] * 1.15)
+      '--max-memory=%s' % int(record['oom-threshold'] * factor)
   ]
 
 def compile_with_memory_min_command(record):