diff --git a/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java b/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java
index e7d8ab2..04251a6 100644
--- a/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java
+++ b/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java
@@ -46,6 +46,10 @@
     return THE_EMPTY_ANNOTATIONS_SET;
   }
 
+  public int size() {
+    return annotations.length;
+  }
+
   @Override
   public int computeHashCode() {
     return Arrays.hashCode(annotations);
diff --git a/src/main/java/com/android/tools/r8/graph/ResolutionResult.java b/src/main/java/com/android/tools/r8/graph/ResolutionResult.java
index 253d014..dfd31fb 100644
--- a/src/main/java/com/android/tools/r8/graph/ResolutionResult.java
+++ b/src/main/java/com/android/tools/r8/graph/ResolutionResult.java
@@ -33,6 +33,7 @@
     return isInterface ? lookupInterfaceTargets(appInfo) : lookupVirtualTargets(appInfo);
   }
 
+  // TODO(b/140204899): Leverage refined receiver type if available.
   default Set<DexEncodedMethod> lookupVirtualTargets(AppInfoWithSubtyping appInfo) {
     assert isValidVirtualTarget(appInfo.app().options);
     // First add the target for receiver type method.type.
@@ -41,6 +42,8 @@
     // Add all matching targets from the subclass hierarchy.
     DexEncodedMethod encodedMethod = asResultOfResolve();
     DexMethod method = encodedMethod.method;
+    // TODO(b/140204899): Instead of subtypes of holder, we could iterate subtypes of refined
+    //   receiver type if available.
     for (DexType type : appInfo.subtypes(method.holder)) {
       DexClass clazz = appInfo.definitionFor(type);
       if (!clazz.isInterface()) {
@@ -56,6 +59,7 @@
     return result;
   }
 
+  // TODO(b/140204899): Leverage refined receiver type if available.
   default Set<DexEncodedMethod> lookupInterfaceTargets(AppInfoWithSubtyping appInfo) {
     assert isValidVirtualTarget(appInfo.app().options);
     Set<DexEncodedMethod> result = Sets.newIdentityHashSet();
@@ -109,8 +113,9 @@
           }
         };
 
-    Set<DexType> set = appInfo.subtypes(method.holder);
-    for (DexType type : set) {
+    // TODO(b/140204899): Instead of subtypes of holder, we could iterate subtypes of refined
+    //   receiver type if available.
+    for (DexType type : appInfo.subtypes(method.holder)) {
       DexClass clazz = appInfo.definitionFor(type);
       if (clazz.isInterface()) {
         ResolutionResult targetMethods = appInfo.resolveMethodOnInterface(clazz, method);
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java b/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
index ab51239..7cbf14d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeDirect.java
@@ -8,7 +8,6 @@
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.code.InvokeDirectRange;
 import com.android.tools.r8.dex.Constants;
-import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
@@ -28,8 +27,6 @@
 import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
 import java.util.List;
 import java.util.function.Predicate;
 
@@ -148,13 +145,6 @@
   }
 
   @Override
-  public Collection<DexEncodedMethod> lookupTargets(
-      AppView<? extends AppInfoWithSubtyping> appView, DexType invocationContext) {
-    DexEncodedMethod target = appView.appInfo().lookupDirectTarget(getInvokedMethod());
-    return target == null ? Collections.emptyList() : Collections.singletonList(target);
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, DexType invocationContext) {
     return inliningConstraints.forInvokeDirect(getInvokedMethod(), invocationContext);
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeInterface.java b/src/main/java/com/android/tools/r8/ir/code/InvokeInterface.java
index ca84fba..860080f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeInterface.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeInterface.java
@@ -5,7 +5,6 @@
 
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.code.InvokeInterfaceRange;
-import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
@@ -19,10 +18,7 @@
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import java.util.Collection;
-import java.util.Collections;
 import java.util.List;
-import java.util.stream.Collectors;
 
 public class InvokeInterface extends InvokeMethodWithReceiver {
 
@@ -104,34 +100,6 @@
   }
 
   @Override
-  public Collection<DexEncodedMethod> lookupTargets(
-      AppView<? extends AppInfoWithSubtyping> appView, DexType invocationContext) {
-    // Leverage exact receiver type if available.
-    DexEncodedMethod singleTarget = lookupSingleTarget(appView, invocationContext);
-    if (singleTarget != null) {
-      return Collections.singletonList(singleTarget);
-    }
-    DexMethod method = getInvokedMethod();
-    Collection<DexEncodedMethod> targets =
-        appView
-            .appInfo()
-            .resolveMethodOnInterface(method.holder, method)
-            .lookupInterfaceTargets(appView.appInfo());
-    if (targets == null) {
-      return targets;
-    }
-    DexType staticReceiverType = getInvokedMethod().holder;
-    DexType refinedReceiverType = TypeAnalysis.getRefinedReceiverType(appView.withLiveness(), this);
-    // Leverage refined receiver type if available.
-    if (refinedReceiverType != staticReceiverType) {
-      return targets.stream()
-          .filter(m -> appView.isSubtype(m.method.holder, refinedReceiverType).isPossiblyTrue())
-          .collect(Collectors.toSet());
-    }
-    return targets;
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, DexType invocationContext) {
     return inliningConstraints.forInvokeInterface(getInvokedMethod(), invocationContext);
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
index b790829..a974af6 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
@@ -13,13 +13,17 @@
 import com.android.tools.r8.ir.analysis.ClassInitializationAnalysis;
 import com.android.tools.r8.ir.analysis.fieldvalueanalysis.AbstractFieldSet;
 import com.android.tools.r8.ir.analysis.modeling.LibraryMethodReadSetModeling;
+import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
 import com.android.tools.r8.ir.optimize.DefaultInliningOracle;
 import com.android.tools.r8.ir.optimize.Inliner.InlineAction;
 import com.android.tools.r8.ir.optimize.Inliner.Reason;
 import com.android.tools.r8.ir.optimize.inliner.WhyAreYouNotInliningReporter;
 import com.android.tools.r8.ir.regalloc.RegisterAllocator;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Sets;
 import java.util.Collection;
 import java.util.List;
+import java.util.Set;
 
 public abstract class InvokeMethod extends Invoke {
 
@@ -61,11 +65,56 @@
 
   // In subclasses, e.g., invoke-virtual or invoke-super, use a narrower receiver type by using
   // receiver type and calling context---the holder of the method where the current invocation is.
+  // TODO(b/140204899): Refactor lookup methods to be defined in a single place.
   public abstract DexEncodedMethod lookupSingleTarget(
       AppView<?> appView, DexType invocationContext);
 
-  public abstract Collection<DexEncodedMethod> lookupTargets(
-      AppView<? extends AppInfoWithSubtyping> appView, DexType invocationContext);
+  // TODO(b/140204899): Refactor lookup methods to be defined in a single place.
+  public Collection<DexEncodedMethod> lookupTargets(
+      AppView<? extends AppInfoWithSubtyping> appView, DexType invocationContext) {
+    // Leverage exact receiver type if available.
+    DexEncodedMethod singleTarget = lookupSingleTarget(appView, invocationContext);
+    if (singleTarget != null) {
+      return ImmutableList.of(singleTarget);
+    }
+    if (!isInvokeMethodWithDynamicDispatch() || !appView.appInfo().hasLiveness()) {
+      return null;
+    }
+    Collection<DexEncodedMethod> targets;
+    if (isInvokeVirtual()) {
+      targets =
+          appView
+              .appInfo()
+              .resolveMethodOnClass(method.holder, method)
+              .lookupVirtualTargets(appView.appInfo());
+    } else {
+      assert isInvokeInterface();
+      targets =
+          appView
+              .appInfo()
+              .resolveMethodOnInterface(method.holder, method)
+              .lookupInterfaceTargets(appView.appInfo());
+    }
+    if (targets == null) {
+      return null;
+    }
+    DexType staticReceiverType = getInvokedMethod().holder;
+    DexType refinedReceiverType =
+        TypeAnalysis.getRefinedReceiverType(
+            appView.withLiveness(), this.asInvokeMethodWithReceiver());
+    // TODO(b/140204899): Instead of reprocessing here, pass refined receiver to lookup.
+    // Leverage refined receiver type if available.
+    if (refinedReceiverType != staticReceiverType) {
+      Set<DexEncodedMethod> result = Sets.newIdentityHashSet();
+      for (DexEncodedMethod target : targets) {
+        if (appView.isSubtype(target.method.holder, refinedReceiverType).isPossiblyTrue()) {
+          result.add(target);
+        }
+      }
+      return result;
+    }
+    return targets;
+  }
 
   public abstract InlineAction computeInlining(
       DexEncodedMethod singleTarget,
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java b/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
index acd864e..0c4671e 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
@@ -7,7 +7,6 @@
 
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.code.InvokeStaticRange;
-import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
@@ -25,8 +24,6 @@
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.ir.optimize.inliner.WhyAreYouNotInliningReporter;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import java.util.Collection;
-import java.util.Collections;
 import java.util.List;
 import java.util.function.Predicate;
 
@@ -127,13 +124,6 @@
   }
 
   @Override
-  public Collection<DexEncodedMethod> lookupTargets(
-      AppView<? extends AppInfoWithSubtyping> appView, DexType invocationContext) {
-    DexEncodedMethod target = appView.appInfo().lookupStaticTarget(getInvokedMethod());
-    return target == null ? Collections.emptyList() : Collections.singletonList(target);
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, DexType invocationContext) {
     return inliningConstraints.forInvokeStatic(getInvokedMethod(), invocationContext);
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java b/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java
index e866bf4..588a0f1 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeSuper.java
@@ -5,7 +5,6 @@
 
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.code.InvokeSuperRange;
-import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
@@ -18,8 +17,6 @@
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import java.util.Collection;
-import java.util.Collections;
 import java.util.List;
 
 public class InvokeSuper extends InvokeMethodWithReceiver {
@@ -108,14 +105,6 @@
   }
 
   @Override
-  public Collection<DexEncodedMethod> lookupTargets(
-      AppView<? extends AppInfoWithSubtyping> appView, DexType invocationContext) {
-    DexEncodedMethod target =
-        appView.appInfo().lookupSuperTarget(getInvokedMethod(), invocationContext);
-    return target == null ? Collections.emptyList() : Collections.singletonList(target);
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, DexType invocationContext) {
     return inliningConstraints.forInvokeSuper(getInvokedMethod(), invocationContext);
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 9ecc99d..da5a5e6 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
@@ -7,7 +7,6 @@
 
 import com.android.tools.r8.cf.code.CfInvoke;
 import com.android.tools.r8.code.InvokeVirtualRange;
-import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
@@ -21,11 +20,8 @@
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import java.util.Collection;
-import java.util.Collections;
 import java.util.List;
 import java.util.function.Predicate;
-import java.util.stream.Collectors;
 
 public class InvokeVirtual extends InvokeMethodWithReceiver {
 
@@ -107,34 +103,6 @@
   }
 
   @Override
-  public Collection<DexEncodedMethod> lookupTargets(
-      AppView<? extends AppInfoWithSubtyping> appView, DexType invocationContext) {
-    // Leverage exact receiver type if available.
-    DexEncodedMethod singleTarget = lookupSingleTarget(appView, invocationContext);
-    if (singleTarget != null) {
-      return Collections.singletonList(singleTarget);
-    }
-    DexMethod method = getInvokedMethod();
-    Collection<DexEncodedMethod> targets =
-        appView
-            .appInfo()
-            .resolveMethodOnClass(method.holder, method)
-            .lookupVirtualTargets(appView.appInfo());
-    if (targets == null) {
-      return targets;
-    }
-    DexType staticReceiverType = getInvokedMethod().holder;
-    DexType refinedReceiverType = TypeAnalysis.getRefinedReceiverType(appView.withLiveness(), this);
-    // Leverage refined receiver type if available.
-    if (refinedReceiverType != staticReceiverType) {
-      return targets.stream()
-          .filter(m -> appView.isSubtype(m.method.holder, refinedReceiverType).isPossiblyTrue())
-          .collect(Collectors.toSet());
-    }
-    return targets;
-  }
-
-  @Override
   public ConstraintWithTarget inliningConstraint(
       InliningConstraints inliningConstraints, DexType invocationContext) {
     return inliningConstraints.forInvokeVirtual(getInvokedMethod(), invocationContext);
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 7e15e72..d068677 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
@@ -706,6 +706,7 @@
     if (!options.isGeneratingClassFiles()) {
       printPhase("Class staticizer post processing");
       staticizeClasses(feedback, executorService);
+      feedback.updateVisibleOptimizationInfo();
     }
 
     // Build a new application with jumbo string info.
@@ -735,6 +736,9 @@
       builder.addSynthesizedClass(serviceLoaderRewriter.getSynthesizedClass(), true);
     }
 
+    // Update optimization info for all synthesized methods at once.
+    feedback.updateVisibleOptimizationInfo();
+
     if (outliner != null) {
       printPhase("Outlining");
       timing.begin("IR conversion phase 3");
@@ -755,6 +759,7 @@
               printMethod(code, "IR after outlining (SSA)", null);
               finalizeIR(method, code, OptimizationFeedbackIgnore.getInstance());
             });
+        feedback.updateVisibleOptimizationInfo();
         assert outliner.checkAllOutlineSitesFoundAgain();
         builder.addSynthesizedClass(outlineClass, true);
         clearDexMethodCompilationState(outlineClass);
@@ -789,6 +794,8 @@
       }
     }
 
+    assert feedback.noUpdatesLeft();
+
     // Check if what we've added to the application builder as synthesized classes are same as
     // what we've added and used through AppInfo.
     assert appView
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java b/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java
index 2649e62..0251620 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java
@@ -290,21 +290,26 @@
       return false;
     }
 
-    if (!inliner.mainDexClasses.isEmpty()) {
-      // Don't inline code with references beyond root main dex classes into a root main dex class.
-      // If we do this it can increase the size of the main dex dependent classes.
-      if (inliner.mainDexClasses.getRoots().contains(method.method.holder)
-          && MainDexDirectReferenceTracer.hasReferencesOutsideFromCode(
-              appView.appInfo(), singleTarget, inliner.mainDexClasses.getRoots())) {
-        whyAreYouNotInliningReporter.reportInlineeRefersToClassesNotInMainDex();
-        return false;
-      }
-      // Allow inlining into the classes in the main dex dependent set without restrictions.
+    // Don't inline code with references beyond root main dex classes into a root main dex class.
+    // If we do this it can increase the size of the main dex dependent classes.
+    if (reason != Reason.FORCE
+        && inlineeRefersToClassesNotInMainDex(method.method.holder, singleTarget)) {
+      whyAreYouNotInliningReporter.reportInlineeRefersToClassesNotInMainDex();
+      return false;
     }
-
+    assert reason != Reason.FORCE
+        || !inlineeRefersToClassesNotInMainDex(method.method.holder, singleTarget);
     return true;
   }
 
+  private boolean inlineeRefersToClassesNotInMainDex(DexType holder, DexEncodedMethod target) {
+    if (inliner.mainDexClasses.isEmpty() || !inliner.mainDexClasses.getRoots().contains(holder)) {
+      return false;
+    }
+    return MainDexDirectReferenceTracer.hasReferencesOutsideFromCode(
+        appView.appInfo(), target, inliner.mainDexClasses.getRoots());
+  }
+
   private boolean satisfiesRequirementsForSimpleInlining(
       InvokeMethod invoke, DexEncodedMethod target) {
     // If we are looking for a simple method, only inline if actually simple.
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/SwitchMapCollector.java b/src/main/java/com/android/tools/r8/ir/optimize/SwitchMapCollector.java
index d6f6855..cf4f72b 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/SwitchMapCollector.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/SwitchMapCollector.java
@@ -13,8 +13,8 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
-import com.android.tools.r8.ir.code.InstructionIterator;
 import com.android.tools.r8.ir.code.InvokeVirtual;
+import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceArrayMap;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
@@ -102,11 +102,28 @@
   private void extractSwitchMap(DexEncodedField encodedField, IRCode initializer) {
     DexField field = encodedField.field;
     Int2ReferenceMap<DexField> switchMap = new Int2ReferenceArrayMap<>();
-    InstructionIterator it = initializer.instructionIterator();
-    Instruction insn;
-    Predicate<Instruction> predicate = i -> i.isStaticGet() && i.asStaticGet().getField() == field;
-    while ((insn = it.nextUntil(predicate)) != null) {
-      for (Instruction use : insn.outValue().uniqueUsers()) {
+
+    // Find each array-put instruction that updates an entry of the array that is stored in
+    // `encodedField`.
+    //
+    // We do this by finding each instruction that reads the array, and iterating the users of the
+    // out-value:
+    //
+    //   int[] x = static-get <encodedField>
+    //   x[index] = value
+    //
+    // A new array is assigned into `encodedField` in the beginning of `initializer`. For
+    // completeness, we also need to visit the users of the array being stored:
+    //
+    //   int[] x = new int[size];
+    //   static-put <encodedField>, x
+    //   x[index] = value
+    Predicate<Instruction> predicate =
+        i -> (i.isStaticGet() || i.isStaticPut()) && i.asFieldInstruction().getField() == field;
+    for (Instruction instruction : initializer.instructions(predicate)) {
+      Value valueOfInterest =
+          instruction.isStaticGet() ? instruction.outValue() : instruction.asStaticPut().value();
+      for (Instruction use : valueOfInterest.uniqueUsers()) {
         if (use.isArrayPut()) {
           Instruction index = use.asArrayPut().value().definition;
           if (index == null || !index.isConstNumber()) {
@@ -135,7 +152,7 @@
           if (switchMap.put(integerIndex, enumField) != null) {
             return;
           }
-        } else {
+        } else if (use != instruction) {
           return;
         }
       }
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 a994f5d..2a80ce4 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
@@ -15,6 +15,7 @@
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.utils.IteratorUtils;
+import com.android.tools.r8.utils.StringUtils;
 import java.util.BitSet;
 import java.util.IdentityHashMap;
 import java.util.Map;
@@ -82,6 +83,16 @@
     processed.clear();
   }
 
+  public boolean noUpdatesLeft() {
+    assert fieldOptimizationInfos.isEmpty()
+        : StringUtils.join(fieldOptimizationInfos.keySet(), ", ");
+    assert methodOptimizationInfos.isEmpty()
+        : StringUtils.join(methodOptimizationInfos.keySet(), ", ");
+    assert processed.isEmpty()
+        : StringUtils.join(processed.keySet(), ", ");
+    return true;
+  }
+
   // FIELD OPTIMIZATION INFO:
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
index 45f5bed..829c227 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -153,6 +153,8 @@
   public final Set<DexType> neverClassInline;
   /** All types that *must* never be merged due to a configuration directive (testing only). */
   public final Set<DexType> neverMerge;
+  /** Set of const-class references. */
+  public final Set<DexType> constClassReferences;
   /**
    * All methods and fields whose value *must* never be propagated due to a configuration directive.
    * (testing only).
@@ -223,7 +225,8 @@
       Set<DexType> prunedTypes,
       Map<DexField, Int2ReferenceMap<DexField>> switchMaps,
       Map<DexType, Map<DexField, EnumValueInfo>> enumValueInfoMaps,
-      Set<DexType> instantiatedLambdas) {
+      Set<DexType> instantiatedLambdas,
+      Set<DexType> constClassReferences) {
     super(application);
     this.liveTypes = liveTypes;
     this.instantiatedAnnotationTypes = instantiatedAnnotationTypes;
@@ -264,6 +267,7 @@
     this.switchMaps = switchMaps;
     this.enumValueInfoMaps = enumValueInfoMaps;
     this.instantiatedLambdas = instantiatedLambdas;
+    this.constClassReferences = constClassReferences;
   }
 
   public AppInfoWithLiveness(
@@ -304,7 +308,8 @@
       Set<DexType> prunedTypes,
       Map<DexField, Int2ReferenceMap<DexField>> switchMaps,
       Map<DexType, Map<DexField, EnumValueInfo>> enumValueInfoMaps,
-      Set<DexType> instantiatedLambdas) {
+      Set<DexType> instantiatedLambdas,
+      Set<DexType> constClassReferences) {
     super(appInfoWithSubtyping);
     this.liveTypes = liveTypes;
     this.instantiatedAnnotationTypes = instantiatedAnnotationTypes;
@@ -345,6 +350,7 @@
     this.switchMaps = switchMaps;
     this.enumValueInfoMaps = enumValueInfoMaps;
     this.instantiatedLambdas = instantiatedLambdas;
+    this.constClassReferences = constClassReferences;
   }
 
   private AppInfoWithLiveness(AppInfoWithLiveness previous) {
@@ -398,7 +404,8 @@
             : CollectionUtils.mergeSets(previous.prunedTypes, removedClasses),
         previous.switchMaps,
         previous.enumValueInfoMaps,
-        previous.instantiatedLambdas);
+        previous.instantiatedLambdas,
+        previous.constClassReferences);
     copyMetadataFromPrevious(previous);
     assert removedClasses == null || assertNoItemRemoved(previous.pinnedItems, removedClasses);
   }
@@ -485,6 +492,7 @@
             .collect(Collectors.toList()));
     this.switchMaps = rewriteReferenceKeys(previous.switchMaps, lense::lookupField);
     this.enumValueInfoMaps = rewriteReferenceKeys(previous.enumValueInfoMaps, lense::lookupType);
+    this.constClassReferences = previous.constClassReferences;
   }
 
   public AppInfoWithLiveness(
@@ -531,6 +539,7 @@
     this.prunedTypes = previous.prunedTypes;
     this.switchMaps = switchMaps;
     this.enumValueInfoMaps = enumValueInfoMaps;
+    this.constClassReferences = previous.constClassReferences;
     previous.markObsolete();
   }
 
@@ -547,6 +556,9 @@
     if (liveTypes.contains(type)) {
       return true;
     }
+    if (prunedTypes.contains(type)) {
+      return false;
+    }
     DexClass clazz = definitionFor(type);
     return clazz == null || !clazz.isProgramClass();
   }
@@ -589,6 +601,16 @@
     return interfaces;
   }
 
+  /**
+   * Const-classes is a conservative set of types that may be lock-candidates and cannot be merged.
+   * When using synchronized blocks, we cannot ensure that const-class locks will not flow in. This
+   * can potentially cause incorrect behavior when merging classes. A conservative choice is to not
+   * merge any const-class classes. More info at b/142438687.
+   */
+  public boolean isLockCandidate(DexType type) {
+    return constClassReferences.contains(type);
+  }
+
   public AppInfoWithLiveness withoutStaticFieldsWrites(Set<DexField> noLongerWrittenFields) {
     assert checkIfObsolete();
     if (noLongerWrittenFields.isEmpty()) {
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 246dfa1..2306b28 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -273,6 +273,12 @@
   private final Set<DexReference> pinnedItems = Sets.newIdentityHashSet();
 
   /**
+   * A set of seen const-class references that both serve as an initial lock-candidate set and will
+   * prevent statically merging the classes referenced.
+   */
+  private final Set<DexType> constClassReferences = Sets.newIdentityHashSet();
+
+  /**
    * A map from classes to annotations that need to be processed should the classes ever become
    * live.
    */
@@ -899,6 +905,15 @@
 
     @Override
     public boolean registerConstClass(DexType type) {
+      // We conservatively group T.class and T[].class to ensure that we do not merge T with S if
+      // potential locks on T[].class and S[].class exists.
+      DexType baseType = type.toBaseType(appView.dexItemFactory());
+      if (baseType.isClassType()) {
+        DexProgramClass baseClass = getProgramClassOrNull(baseType);
+        if (baseClass != null) {
+          constClassReferences.add(baseType);
+        }
+      }
       return registerConstClassOrCheckCast(type);
     }
 
@@ -2241,7 +2256,8 @@
             Collections.emptyMap(),
             Collections.emptyMap(),
             SetUtils.mapIdentityHashSet(
-                instantiatedInterfaceTypes.getItems(), DexProgramClass::getType));
+                instantiatedInterfaceTypes.getItems(), DexProgramClass::getType),
+            constClassReferences);
     appInfo.markObsolete();
     return appInfoWithLiveness;
   }
@@ -2644,11 +2660,12 @@
       if (encodedMethod == null) {
         return;
       }
+      KeepReason reason = KeepReason.reflectiveUseIn(method);
       if (encodedMethod.accessFlags.isStatic() || encodedMethod.accessFlags.isConstructor()) {
-        markDirectStaticOrConstructorMethodAsLive(
-            clazz, encodedMethod, KeepReason.reflectiveUseIn(method));
+        markMethodAsTargeted(clazz, encodedMethod, reason);
+        markDirectStaticOrConstructorMethodAsLive(clazz, encodedMethod, reason);
       } else {
-        markVirtualMethodAsLive(clazz, encodedMethod, KeepReason.reflectiveUseIn(method));
+        markVirtualMethodAsLive(clazz, encodedMethod, reason);
       }
     }
   }
diff --git a/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
index 9326e31..bae5b40 100644
--- a/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
@@ -342,6 +342,11 @@
         // We are not allowed to merge synchronized classes with synchronized methods.
         return false;
       }
+      if (appView.appInfo().constClassReferences.contains(clazz.type)) {
+        // Since the type is const-class referenced (and the static merger does not create a lense
+        // to map the merged type) the class will likely remain and there is no gain from merging.
+        return false;
+      }
       // Check if current candidate is a better choice depending on visibility. For package private
       // or protected, the key is parameterized by the package name already, so we just have to
       // check accessibility-flags. For global this is no-op.
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index 4dc15ab..85da345 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -49,6 +49,7 @@
 import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 import com.google.common.collect.Streams;
@@ -130,6 +131,7 @@
     ALWAYS_INLINE,
     CONFLICT,
     ILLEGAL_ACCESS,
+    MAIN_DEX_ROOT_OUTSIDE_REFERENCE,
     MERGE_ACROSS_NESTS,
     NATIVE_METHOD,
     NO_SIDE_EFFECTS,
@@ -137,8 +139,8 @@
     RESOLUTION_FOR_FIELDS_MAY_CHANGE,
     RESOLUTION_FOR_METHODS_MAY_CHANGE,
     SERVICE_LOADER,
+    SOURCE_AND_TARGET_LOCK_CANDIDATES,
     STATIC_INITIALIZERS,
-    STATIC_SYNCHRONIZED_METHODS,
     UNHANDLED_INVOKE_DIRECT,
     UNHANDLED_INVOKE_SUPER,
     UNSAFE_INLINING,
@@ -163,6 +165,9 @@
         case ILLEGAL_ACCESS:
           message = "it could lead to illegal accesses";
           break;
+        case MAIN_DEX_ROOT_OUTSIDE_REFERENCE:
+          message = "contains a constructor with a reference outside the main dex classes";
+          break;
         case MERGE_ACROSS_NESTS:
           message = "cannot merge across nests, or from nest to non-nest";
           break;
@@ -184,6 +189,9 @@
         case SERVICE_LOADER:
           message = "it is used by a service loader";
           break;
+        case SOURCE_AND_TARGET_LOCK_CANDIDATES:
+          message = "source and target are both lock-candidates";
+          break;
         case STATIC_INITIALIZERS:
           message = "merging of static initializers are not supported";
           break;
@@ -199,9 +207,6 @@
         case UNSUPPORTED_ATTRIBUTES:
           message = "since inner-class attributes are not supported";
           break;
-        case STATIC_SYNCHRONIZED_METHODS:
-          message = "since it has static synchronized methods which can lead to unwanted behavior";
-          break;
         default:
           assert false;
       }
@@ -378,6 +383,11 @@
         || appInfo.neverMerge.contains(clazz.type)) {
       return false;
     }
+
+    assert Streams.stream(Iterables.concat(clazz.fields(), clazz.methods()))
+        .map(KeyedDexItem::getKey)
+        .noneMatch(appInfo::isPinned);
+
     if (appView.options().featureSplitConfiguration != null &&
         appView.options().featureSplitConfiguration.isInFeature(clazz)) {
       // TODO(b/141452765): Allow class merging between classes in features.
@@ -410,21 +420,18 @@
       //     * Have access to the no-arg constructor of its first non-serializable superclass
       return false;
     }
-    for (DexEncodedField field : clazz.fields()) {
-      if (appInfo.isPinned(field.field)) {
-        return false;
-      }
-    }
-    for (DexEncodedMethod method : clazz.methods()) {
-      if (appInfo.isPinned(method.method)) {
-        return false;
-      }
-      if (method.isInstanceInitializer() && disallowInlining(method, singleSubtype)) {
-        // Cannot guarantee that markForceInline() will work.
-        if (Log.ENABLED) {
-          AbortReason.UNSAFE_INLINING.printLogMessageForClass(clazz);
+    for (DexEncodedMethod method : clazz.directMethods()) {
+      // We rename constructors to private methods and mark them to be forced-inlined, so we have to
+      // check if we can force-inline all constructors.
+      if (method.isInstanceInitializer()) {
+        AbortReason reason = disallowInlining(method, singleSubtype);
+        if (reason != null) {
+          // Cannot guarantee that markForceInline() will work.
+          if (Log.ENABLED) {
+            reason.printLogMessageForClass(clazz);
+          }
+          return false;
         }
-        return false;
       }
     }
     if (clazz.getEnclosingMethod() != null || !clazz.getInnerClasses().isEmpty()) {
@@ -473,6 +480,17 @@
       }
       return false;
     }
+    boolean sourceCanBeSynchronizedOn =
+        appView.appInfo().isLockCandidate(clazz.type) || clazz.hasStaticSynchronizedMethods();
+    boolean targetCanBeSynchronizedOn =
+        appView.appInfo().isLockCandidate(targetClass.type)
+            || targetClass.hasStaticSynchronizedMethods();
+    if (sourceCanBeSynchronizedOn && targetCanBeSynchronizedOn) {
+      if (Log.ENABLED) {
+        AbortReason.SOURCE_AND_TARGET_LOCK_CANDIDATES.printLogMessageForClass(clazz);
+      }
+      return false;
+    }
     if (targetClass.getEnclosingMethod() != null || !targetClass.getInnerClasses().isEmpty()) {
       // TODO(herhut): Consider supporting merging of enclosing-method and inner-class attributes.
       if (Log.ENABLED) {
@@ -810,14 +828,6 @@
       assert isStillMergeCandidate(clazz);
     }
 
-    // Check for static synchronized methods on source
-    if (clazz.hasStaticSynchronizedMethods()) {
-      if (Log.ENABLED) {
-        AbortReason.STATIC_SYNCHRONIZED_METHODS.printLogMessageForClass(clazz);
-      }
-      return;
-    }
-
     // Guard against the case where we have two methods that may get the same signature
     // if we replace types. This is rare, so we approximate and err on the safe side here.
     if (new CollisionDetector(clazz.type, targetClass.type).mayCollide()) {
@@ -1665,7 +1675,7 @@
     }
   }
 
-  private boolean disallowInlining(DexEncodedMethod method, DexType invocationContext) {
+  private AbortReason disallowInlining(DexEncodedMethod method, DexType invocationContext) {
     if (appView.options().enableInlining) {
       if (method.getCode().isCfCode()) {
         CfCode code = method.getCode().asCfCode();
@@ -1675,11 +1685,21 @@
                 appView,
                 new SingleTypeMapperGraphLense(method.method.holder, invocationContext),
                 invocationContext);
-        return constraint == ConstraintWithTarget.NEVER;
+        if (constraint == ConstraintWithTarget.NEVER) {
+          return AbortReason.UNSAFE_INLINING;
+        }
+        // Constructors can have references beyond the root main dex classes. This can increase the
+        // size of the main dex dependent classes and we should bail out.
+        if (mainDexClasses.getRoots().contains(invocationContext)
+            && MainDexDirectReferenceTracer.hasReferencesOutsideFromCode(
+                appView.appInfo(), method, mainDexClasses.getRoots())) {
+          return AbortReason.MAIN_DEX_ROOT_OUTSIDE_REFERENCE;
+        }
+        return null;
       }
       // For non-jar/cf code we currently cannot guarantee that markForceInline() will succeed.
     }
-    return true;
+    return AbortReason.UNSAFE_INLINING;
   }
 
   private class SingleTypeMapperGraphLense extends GraphLense {
diff --git a/src/test/java/com/android/tools/r8/classmerging/VerticalClassMergerInitTest.java b/src/test/java/com/android/tools/r8/classmerging/VerticalClassMergerInitTest.java
index 3285930..1c4f406 100644
--- a/src/test/java/com/android/tools/r8/classmerging/VerticalClassMergerInitTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/VerticalClassMergerInitTest.java
@@ -5,9 +5,7 @@
 package com.android.tools.r8.classmerging;
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
-import static org.hamcrest.CoreMatchers.containsString;
 import static org.hamcrest.MatcherAssert.assertThat;
-import static org.hamcrest.core.IsNot.not;
 
 import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.TestBase;
@@ -43,7 +41,6 @@
   @Test
   public void testMergingClassWithConstructorNotInMainDex()
       throws IOException, CompilationFailedException, ExecutionException {
-    // TODO(b/142909854): Fix test expectation when bug has been resolved.
     testForR8(parameters.getBackend())
         .addInnerClasses(VerticalClassMergerInitTest.class)
         .addKeepMainRule(Main.class)
@@ -58,11 +55,11 @@
         .compile()
         .inspect(
             inspector -> {
-              assertThat(inspector.clazz(Base.class), not(isPresent()));
+              assertThat(inspector.clazz(Base.class), isPresent());
               assertThat(inspector.clazz(Child.class), isPresent());
             })
         .run(parameters.getRuntime(), Main.class)
-        .assertFailureWithErrorThatMatches(containsString("initialized"));
+        .assertSuccessWithOutputLines("Base.init()", "Outside.init()", "Child.init()");
   }
 
   public static class Base {
diff --git a/src/test/java/com/android/tools/r8/classmerging/VerticalClassMergerSynchronizedBlockTest.java b/src/test/java/com/android/tools/r8/classmerging/VerticalClassMergerSynchronizedBlockTest.java
index 9b3c384..2828ec4 100644
--- a/src/test/java/com/android/tools/r8/classmerging/VerticalClassMergerSynchronizedBlockTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/VerticalClassMergerSynchronizedBlockTest.java
@@ -6,10 +6,8 @@
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static org.hamcrest.MatcherAssert.assertThat;
-import static org.hamcrest.core.StringContains.containsString;
 
 import com.android.tools.r8.CompilationFailedException;
-import com.android.tools.r8.R8TestRunResult;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
@@ -51,18 +49,13 @@
   @Test
   public void testNoMergingOfClassUsedInMonitor()
       throws IOException, CompilationFailedException, ExecutionException {
-    // TODO(b/142438687): Fix expectation when fixed.
-    R8TestRunResult result =
-        testForR8(parameters.getBackend())
-            .addInnerClasses(VerticalClassMergerSynchronizedBlockTest.class)
-            .addKeepMainRule(Main.class)
-            .setMinApi(parameters.getApiLevel())
-            .compile()
-            .run(parameters.getRuntime(), Main.class)
-            .assertFailureWithErrorThatMatches(containsString("DEADLOCKED!"));
-    if (result.getExitCode() == 0) {
-      result.inspect(inspector -> assertThat(inspector.clazz(LockOne.class), isPresent()));
-    }
+    testForR8(parameters.getBackend())
+        .addInnerClasses(VerticalClassMergerSynchronizedBlockTest.class)
+        .addKeepMainRule(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutput("Hello World!")
+        .inspect(inspector -> assertThat(inspector.clazz(LockOne.class), isPresent()));
   }
 
   abstract static class LockOne {}
diff --git a/src/test/java/com/android/tools/r8/classmerging/VerticalClassMergerSynchronizedBlockWithArraysTest.java b/src/test/java/com/android/tools/r8/classmerging/VerticalClassMergerSynchronizedBlockWithArraysTest.java
new file mode 100644
index 0000000..b6039db
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/VerticalClassMergerSynchronizedBlockWithArraysTest.java
@@ -0,0 +1,121 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.classmerging;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.ToolHelper.DexVm.Version;
+import java.io.IOException;
+import java.lang.Thread.State;
+import java.util.concurrent.ExecutionException;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class VerticalClassMergerSynchronizedBlockWithArraysTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    // The 4.0.4 runtime will flakily mark threads as blocking and report DEADLOCKED.
+    return getTestParameters()
+        .withDexRuntimesStartingFromExcluding(Version.V4_0_4)
+        .withAllApiLevels()
+        .build();
+  }
+
+  public VerticalClassMergerSynchronizedBlockWithArraysTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testOnRuntime() throws IOException, CompilationFailedException, ExecutionException {
+    testForRuntime(parameters.getRuntime(), parameters.getApiLevel())
+        .addInnerClasses(VerticalClassMergerSynchronizedBlockWithArraysTest.class)
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutput("Hello World!");
+  }
+
+  @Test
+  public void testNoMergingOfClassUsedInMonitor()
+      throws IOException, CompilationFailedException, ExecutionException {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(VerticalClassMergerSynchronizedBlockWithArraysTest.class)
+        .addKeepMainRule(Main.class)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutput("Hello World!")
+        .inspect(inspector -> assertThat(inspector.clazz(LockOne.class), isPresent()));
+  }
+
+  abstract static class LockOne {}
+
+  static class LockTwo extends LockOne {}
+
+  static class LockThree {}
+
+  public static class Main {
+
+    private static volatile boolean inLockThreeCritical = false;
+    private static volatile boolean inLockTwoCritical = false;
+    private static volatile boolean arnoldWillNotBeBack = false;
+
+    private static volatile Thread t1 = new Thread(Main::lockThreeThenOne);
+    private static volatile Thread t2 = new Thread(Main::lockTwoThenThree);
+    private static volatile Thread t3 = new Thread(Main::arnold);
+
+    static void synchronizedAccessThroughLocks(String arg) {
+      System.out.print(arg);
+    }
+
+    public static void main(String[] args) {
+      t1.start();
+      t2.start();
+      // This thread is started to ensure termination in case we are rewriting incorrectly.
+      t3.start();
+
+      while (!arnoldWillNotBeBack) {}
+    }
+
+    static void lockThreeThenOne() {
+      synchronized (LockThree[].class) {
+        inLockThreeCritical = true;
+        while (!inLockTwoCritical) {}
+        synchronized (LockOne[].class) {
+          synchronizedAccessThroughLocks("Hello ");
+        }
+      }
+    }
+
+    static void lockTwoThenThree() {
+      synchronized (LockTwo[].class) {
+        inLockTwoCritical = true;
+        while (!inLockThreeCritical) {}
+        synchronized (LockThree[].class) {
+          synchronizedAccessThroughLocks("World!");
+        }
+      }
+    }
+
+    static void arnold() {
+      while (t1.getState() != State.TERMINATED || t2.getState() != State.TERMINATED) {
+        if (t1.getState() == State.BLOCKED && t2.getState() == State.BLOCKED) {
+          System.err.println("DEADLOCKED!");
+          System.exit(1);
+          break;
+        }
+      }
+      arnoldWillNotBeBack = true;
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizerTest.java b/src/test/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizerTest.java
index f0c6a78..99d27fa 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizerTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizerTest.java
@@ -65,7 +65,7 @@
   @Parameterized.Parameters(name = "{0}")
   public static TestParametersCollection data() {
     // TODO(b/112831361): support for class staticizer in CF backend.
-    return getTestParameters().withDexRuntimes().build();
+    return getTestParameters().withDexRuntimes().withAllApiLevels().build();
   }
 
   public ClassStaticizerTest(TestParameters parameters) {
@@ -95,7 +95,7 @@
             .addKeepRules("-keepattributes InnerClasses,EnclosingMethod")
             .addOptionsModification(this::configure)
             .allowAccessModification()
-            .setMinApi(parameters.getRuntime())
+            .setMinApi(parameters.getApiLevel())
             .run(parameters.getRuntime(), main)
             .assertSuccessWithOutput(javaOutput);
 
@@ -109,7 +109,9 @@
             "STATIC: String trivial.TrivialTestClass.next()"),
         references(clazz, "testSimple", "void"));
 
-    assertTrue(instanceMethods(inspector.clazz(Simple.class)).isEmpty());
+    ClassSubject simple = inspector.clazz(Simple.class);
+    assertTrue(instanceMethods(simple).isEmpty());
+    assertThat(simple.clinit(), not(isPresent()));
 
     assertEquals(
         Lists.newArrayList(
@@ -119,7 +121,9 @@
             "STATIC: String trivial.TrivialTestClass.next()"),
         references(clazz, "testSimpleWithPhi", "void", "int"));
 
-    assertTrue(instanceMethods(inspector.clazz(SimpleWithPhi.class)).isEmpty());
+    ClassSubject simpleWithPhi = inspector.clazz(SimpleWithPhi.class);
+    assertTrue(instanceMethods(simpleWithPhi).isEmpty());
+    assertThat(simpleWithPhi.clinit(), not(isPresent()));
 
     assertEquals(
         Lists.newArrayList(
@@ -128,7 +132,9 @@
             "STATIC: String trivial.TrivialTestClass.next()"),
         references(clazz, "testSimpleWithParams", "void"));
 
-    assertTrue(instanceMethods(inspector.clazz(SimpleWithParams.class)).isEmpty());
+    ClassSubject simpleWithParams = inspector.clazz(SimpleWithParams.class);
+    assertTrue(instanceMethods(simpleWithParams).isEmpty());
+    assertThat(simpleWithParams.clinit(), not(isPresent()));
 
     assertEquals(
         Lists.newArrayList(
@@ -139,7 +145,10 @@
             "trivial.SimpleWithSideEffects trivial.SimpleWithSideEffects.INSTANCE"),
         references(clazz, "testSimpleWithSideEffects", "void"));
 
-    assertTrue(instanceMethods(inspector.clazz(SimpleWithSideEffects.class)).isEmpty());
+    ClassSubject simpleWithSideEffects = inspector.clazz(SimpleWithSideEffects.class);
+    assertTrue(instanceMethods(simpleWithSideEffects).isEmpty());
+    // As its name implies, its clinit has side effects.
+    assertThat(simpleWithSideEffects.clinit(), isPresent());
 
     // TODO(b/111832046): add support for singleton instance getters.
     assertEquals(
@@ -151,7 +160,9 @@
             "trivial.SimpleWithGetter trivial.SimpleWithGetter.INSTANCE"),
         references(clazz, "testSimpleWithGetter", "void"));
 
-    assertFalse(instanceMethods(inspector.clazz(SimpleWithGetter.class)).isEmpty());
+    ClassSubject simpleWithGetter = inspector.clazz(SimpleWithGetter.class);
+    assertFalse(instanceMethods(simpleWithGetter).isEmpty());
+    assertThat(simpleWithGetter.clinit(), isPresent());
   }
 
   @Test
@@ -172,7 +183,7 @@
             .allowAccessModification()
             .noMinification()
             .addOptionsModification(this::configure)
-            .setMinApi(parameters.getRuntime())
+            .setMinApi(parameters.getApiLevel())
             .run(parameters.getRuntime(), main);
 
     CodeInspector inspector = result.inspector();
@@ -182,7 +193,7 @@
         Lists.newArrayList(),
         references(clazz, "testOk_fieldOnly", "void"));
 
-    assertFalse(inspector.clazz(CandidateOkFieldOnly.class).isPresent());
+    assertThat(inspector.clazz(CandidateOkFieldOnly.class), not(isPresent()));
   }
 
   @Test
@@ -210,7 +221,7 @@
             .allowAccessModification()
             .noMinification()
             .addOptionsModification(this::configure)
-            .setMinApi(parameters.getRuntime())
+            .setMinApi(parameters.getApiLevel())
             .run(parameters.getRuntime(), main)
             .assertSuccessWithOutput(javaOutput);
 
@@ -226,7 +237,7 @@
             "STATIC: void movetohost.HostOk.blah(String)"),
         references(clazz, "testOk", "void"));
 
-    assertFalse(inspector.clazz(CandidateOk.class).isPresent());
+    assertThat(inspector.clazz(CandidateOk.class), not(isPresent()));
 
     assertEquals(
         Lists.newArrayList(
@@ -237,7 +248,7 @@
             "movetohost.HostOkSideEffects movetohost.HostOkSideEffects.INSTANCE"),
         references(clazz, "testOkSideEffects", "void"));
 
-    assertFalse(inspector.clazz(CandidateOkSideEffects.class).isPresent());
+    assertThat(inspector.clazz(CandidateOkSideEffects.class), not(isPresent()));
 
     assertEquals(
         Lists.newArrayList(
@@ -249,7 +260,7 @@
             "VIRTUAL: String movetohost.HostConflictMethod.bar(String)"),
         references(clazz, "testConflictMethod", "void"));
 
-    assertTrue(inspector.clazz(CandidateConflictMethod.class).isPresent());
+    assertThat(inspector.clazz(CandidateConflictMethod.class), isPresent());
 
     assertEquals(
         Lists.newArrayList(
@@ -260,12 +271,12 @@
             "String movetohost.CandidateConflictField.field"),
         references(clazz, "testConflictField", "void"));
 
-    assertTrue(inspector.clazz(CandidateConflictMethod.class).isPresent());
+    assertThat(inspector.clazz(CandidateConflictMethod.class), isPresent());
   }
 
   private List<String> instanceMethods(ClassSubject clazz) {
     assertNotNull(clazz);
-    assertTrue(clazz.isPresent());
+    assertThat(clazz, isPresent());
     return Streams.stream(clazz.getDexClass().methods())
         .filter(method -> !method.isStatic())
         .map(method -> method.method.toSourceString())
@@ -276,7 +287,7 @@
   private List<String> references(
       ClassSubject clazz, String methodName, String retValue, String... params) {
     assertNotNull(clazz);
-    assertTrue(clazz.isPresent());
+    assertThat(clazz, isPresent());
 
     MethodSignature signature = new MethodSignature(methodName, retValue, params);
     DexCode code = clazz.method(signature).getMethod().getCode().asDexCode();
@@ -335,7 +346,7 @@
             .allowAccessModification()
             .noMinification()
             .addOptionsModification(this::configure)
-            .setMinApi(parameters.getRuntime())
+            .setMinApi(parameters.getApiLevel())
             .run(parameters.getRuntime(), main)
             .assertSuccessWithOutput(javaOutput);
 
diff --git a/src/test/java/com/android/tools/r8/kotlin/SimplifyIfNotNullKotlinTest.java b/src/test/java/com/android/tools/r8/kotlin/SimplifyIfNotNullKotlinTest.java
index 59aae43..b9ee37a 100644
--- a/src/test/java/com/android/tools/r8/kotlin/SimplifyIfNotNullKotlinTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/SimplifyIfNotNullKotlinTest.java
@@ -32,7 +32,10 @@
     final String mainClassName = ex1.getClassName();
     final String extraRules =
         keepMainMethod(mainClassName) + neverInlineMethod(mainClassName, testMethodSignature);
-    runTest(FOLDER, mainClassName, extraRules,
+    runTest(
+        FOLDER,
+        mainClassName,
+        extraRules,
         app -> {
           CodeInspector codeInspector = new CodeInspector(app);
           ClassSubject clazz = checkClassIsKept(codeInspector, ex1.getClassName());
@@ -40,8 +43,7 @@
           MethodSubject testMethod = checkMethodIsKept(clazz, testMethodSignature);
           long ifzCount =
               testMethod.streamInstructions().filter(i -> i.isIfEqz() || i.isIfNez()).count();
-          long paramNullCheckCount =
-              countCall(testMethod, "ArrayIteratorKt", "checkParameterIsNotNull");
+          long paramNullCheckCount = countCall(testMethod, "Intrinsics", "checkParameterIsNotNull");
           // One after Iterator#hasNext, and another in the filter predicate: sinceYear != null.
           assertEquals(2, ifzCount);
           assertEquals(allowAccessModification ? 0 : 5, paramNullCheckCount);
diff --git a/src/test/java/com/android/tools/r8/shaking/annotations/ProgramAnnotationRemovalTest.java b/src/test/java/com/android/tools/r8/shaking/annotations/ProgramAnnotationRemovalTest.java
new file mode 100644
index 0000000..0cf779d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/annotations/ProgramAnnotationRemovalTest.java
@@ -0,0 +1,118 @@
+// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.shaking.annotations;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+
+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.TestParametersCollection;
+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.lang.annotation.Annotation;
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+import java.lang.reflect.Method;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ProgramAnnotationRemovalTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public ProgramAnnotationRemovalTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    R8TestRunResult result =
+        testForR8(parameters.getBackend())
+            .addInnerClasses(ProgramAnnotationRemovalTest.class)
+            .addKeepMainRule(TestClass.class)
+            .addKeepAttributes("RuntimeVisibleAnnotations")
+            .setMinApi(parameters.getApiLevel())
+            .compile()
+            .run(parameters.getRuntime(), TestClass.class);
+
+    CodeInspector inspector = result.inspector();
+
+    ClassSubject liveAnnotationClassSubject = inspector.clazz(LiveProgramAnnotation.class);
+    assertThat(liveAnnotationClassSubject, isPresent());
+
+    ClassSubject deadAnnotationClassSubject = inspector.clazz(DeadProgramAnnotation.class);
+    assertThat(deadAnnotationClassSubject, not(isPresent()));
+
+    ClassSubject testClassSubject = inspector.clazz(TestClass.class);
+    assertThat(testClassSubject, isPresent());
+
+    MethodSubject methodWithLiveProgramAnnotationSubject =
+        testClassSubject.uniqueMethodWithName("methodWithLiveProgramAnnotation");
+    assertThat(methodWithLiveProgramAnnotationSubject, isPresent());
+    assertEquals(1, methodWithLiveProgramAnnotationSubject.getMethod().annotations.size());
+
+    MethodSubject methodWithDeadProgramAnnotationSubject =
+        testClassSubject.uniqueMethodWithName("methodWithDeadProgramAnnotation");
+    assertThat(methodWithDeadProgramAnnotationSubject, isPresent());
+    assertEquals(0, methodWithDeadProgramAnnotationSubject.getMethod().annotations.size());
+
+    result.assertSuccessWithOutputLines("@" + liveAnnotationClassSubject.getFinalName() + "()");
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) throws Exception {
+      methodWithLiveProgramAnnotation();
+      methodWithDeadProgramAnnotation();
+
+      // Do something with LiveProgramAnnotation to ensure it becomes live.
+      if (System.currentTimeMillis() <= 0) {
+        System.out.println(LiveProgramAnnotation.class);
+      }
+    }
+
+    @NeverInline
+    @LiveProgramAnnotation
+    static void methodWithLiveProgramAnnotation() throws Exception {
+      Method method = TestClass.class.getDeclaredMethod("methodWithLiveProgramAnnotation");
+      for (Annotation annotation : method.getDeclaredAnnotations()) {
+        System.out.println(annotation);
+      }
+    }
+
+    @NeverInline
+    @DeadProgramAnnotation
+    static void methodWithDeadProgramAnnotation() throws Exception {
+      Method method = TestClass.class.getDeclaredMethod("methodWithDeadProgramAnnotation");
+      for (Annotation annotation : method.getDeclaredAnnotations()) {
+        System.out.println(annotation);
+      }
+    }
+  }
+
+  @Target(ElementType.METHOD)
+  @Retention(RetentionPolicy.RUNTIME)
+  @interface LiveProgramAnnotation {}
+
+  @Target(ElementType.METHOD)
+  @Retention(RetentionPolicy.RUNTIME)
+  @interface DeadProgramAnnotation {}
+}
diff --git a/tools/run_on_app.py b/tools/run_on_app.py
index 426fef4..d93e3c0 100755
--- a/tools/run_on_app.py
+++ b/tools/run_on_app.py
@@ -148,6 +148,21 @@
                     metavar='BENCHMARKNAME',
                     help='Print the sizes of individual dex segments as ' +
                         '\'<BENCHMARKNAME>-<segment>(CodeSize): <bytes>\'')
+  result.add_option('--track-time-in-memory',
+                    help='Plot the times taken from memory starting point to '
+                         'end-point with defined memory increment',
+                    default=False,
+                    action='store_true')
+  result.add_option('--track-time-in-memory-max',
+                    help='Setting the maximum memory baseline to run in',
+                    type='int')
+  result.add_option('--track-time-in-memory-min',
+                    help='Setting the minimum memory baseline to run in',
+                    type='int')
+  result.add_option('--track-time-in-memory-increment',
+                    help='Setting the increment',
+                    type='int',
+                    default=32)
 
   return result.parse_args(argv)
 
@@ -287,6 +302,37 @@
         value = utils.cat_file_on_cloud_storage(gs_location, ignore_errors=True)
         print('%s\n' % value)
 
+def track_time_in_memory(options, args):
+  # Args will be destroyed
+  assert len(args) == 0
+  if not options.track_time_in_memory_min:
+    raise Exception(
+        'You have to specify --track_time_in_memory_min when running with '
+        '--track-time-in-memory')
+  if not options.track_time_in_memory_max:
+    raise Exception(
+        'You have to specify --track_time_in_memory_max when running with '
+        '--track-time-in-memory')
+  if not options.track_time_in_memory_increment:
+    raise Exception(
+        'You have to specify --track_time_in_memory_increment when running '
+        'with --track-time-in-memory')
+  current = options.track_time_in_memory_min
+  print('Memory (KB)\tTime (ms)')
+  with utils.TempDir() as temp:
+    stdout = os.path.join(temp, 'stdout')
+    stdout_fd = open(stdout, 'w')
+    while current <= options.track_time_in_memory_max:
+      extra_args = ['-Xmx%sM' % current]
+      t0 = time.time()
+      exit_code = run_with_options(options, [], extra_args, stdout_fd, quiet=True)
+      t1 = time.time()
+      total = (1000.0 * (t1 - t0)) if exit_code == 0 else -1
+      print('%s\t%s' % (current, total))
+      current += options.track_time_in_memory_increment
+
+  return 0
+
 def main(argv):
   (options, args) = ParseOptions(argv)
   if options.expect_oom and not options.max_memory:
@@ -295,10 +341,15 @@
   if options.expect_oom and options.timeout:
     raise Exception(
         'You should not use --timeout when also specifying --expect-oom')
+  if options.find_min_xmx and options.track_time_in_memory:
+    raise Exception(
+        'You cannot both find the min xmx and track time at the same time')
   if options.run_all:
     return run_all(options, args)
   if options.find_min_xmx:
     return find_min_xmx(options, args)
+  if options.track_time_in_memory:
+    return track_time_in_memory(options, args)
   exit_code = run_with_options(options, args)
   if options.expect_oom:
     exit_code = 0 if exit_code == OOM_EXIT_CODE else 1
@@ -335,7 +386,7 @@
     return 'deploy' if options.compiler == 'r8' else 'proguarded'
   return options.type
 
-def run_with_options(options, args, extra_args=None):
+def run_with_options(options, args, extra_args=None, stdout=None, quiet=False):
   if extra_args is None:
     extra_args = []
   app_provided_pg_conf = False;
@@ -476,14 +527,18 @@
             profile=options.profile,
             track_memory_file=options.track_memory_to_file,
             extra_args=extra_args,
+            stdout=stdout,
             stderr=stderr,
-            timeout=options.timeout)
+            timeout=options.timeout,
+            quiet=quiet)
       if exit_code != 0:
         with open(stderr_path) as stderr:
           stderr_text = stderr.read()
-          print(stderr_text)
+          if not quiet:
+            print(stderr_text)
           if 'java.lang.OutOfMemoryError' in stderr_text:
-            print('Failure was OOM')
+            if not quiet:
+              print('Failure was OOM')
             return OOM_EXIT_CODE
           return exit_code
 
diff --git a/tools/toolhelper.py b/tools/toolhelper.py
index 10da97d..2784ea5 100644
--- a/tools/toolhelper.py
+++ b/tools/toolhelper.py
@@ -11,7 +11,7 @@
 
 def run(tool, args, build=None, debug=True,
         profile=False, track_memory_file=None, extra_args=None,
-        stderr=None, stdout=None, return_stdout=False, timeout=0):
+        stderr=None, stdout=None, return_stdout=False, timeout=0, quiet=False):
   if build is None:
     build, args = extract_build_from_args(args)
   if build:
@@ -36,7 +36,7 @@
   if lib:
     cmd.extend(["--lib", lib])
   cmd.extend(args)
-  utils.PrintCmd(cmd)
+  utils.PrintCmd(cmd, quiet=quiet)
   if timeout > 0:
     kill = lambda process: process.kill()
     proc = subprocess.Popen(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE)