diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 3d2cc25..805bdf7 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.dex.Marker.Tool;
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
@@ -249,12 +250,13 @@
       DexApplication application =
           new ApplicationReader(inputApp, options, timing).read(executorService).toDirect();
 
-      AppInfoWithSubtyping appInfo = new AppInfoWithSubtyping(application);
+      AppView<AppInfoWithSubtyping> appView =
+          new AppView<>(new AppInfoWithSubtyping(application), GraphLense.getIdentityLense());
       RootSet rootSet;
       String proguardSeedsData = null;
       timing.begin("Strip unused code");
       try {
-        Set<DexType> missingClasses = appInfo.getMissingClasses();
+        Set<DexType> missingClasses = appView.getAppInfo().getMissingClasses();
         missingClasses = filterMissingClasses(
             missingClasses, options.proguardConfiguration.getDontWarnPatterns());
         if (!missingClasses.isEmpty()) {
@@ -271,34 +273,50 @@
 
         // Compute kotlin info before setting the roots and before
         // kotlin metadata annotation is removed.
-        computeKotlinInfoForProgramClasses(application, appInfo);
+        computeKotlinInfoForProgramClasses(application, appView.getAppInfo());
 
         final ProguardConfiguration.Builder compatibility =
             ProguardConfiguration.builder(application.dexItemFactory, options.reporter);
 
-        rootSet = new RootSetBuilder(
-                    appInfo, application, options.proguardConfiguration.getRules(), options)
+        rootSet =
+            new RootSetBuilder(
+                    appView.getAppInfo(),
+                    application,
+                    options.proguardConfiguration.getRules(),
+                    options)
                 .run(executorService);
         ProtoLiteExtension protoLiteExtension =
-            options.forceProguardCompatibility ? null : new ProtoLiteExtension(appInfo);
-        Enqueuer enqueuer = new Enqueuer(appInfo, options, options.forceProguardCompatibility,
-            compatibility, protoLiteExtension);
-        appInfo = enqueuer.traceApplication(rootSet, executorService, timing);
+            options.forceProguardCompatibility
+                ? null
+                : new ProtoLiteExtension(appView.getAppInfo());
+        Enqueuer enqueuer =
+            new Enqueuer(
+                appView.getAppInfo(),
+                options,
+                options.forceProguardCompatibility,
+                compatibility,
+                protoLiteExtension);
+        appView.setAppInfo(enqueuer.traceApplication(rootSet, executorService, timing));
         if (options.proguardConfiguration.isPrintSeeds()) {
           ByteArrayOutputStream bytes = new ByteArrayOutputStream();
           PrintStream out = new PrintStream(bytes);
-          RootSetBuilder.writeSeeds(appInfo.withLiveness(), out, type -> true);
+          RootSetBuilder.writeSeeds(appView.getAppInfo().withLiveness(), out, type -> true);
           out.flush();
           proguardSeedsData = bytes.toString();
         }
         if (options.enableTreeShaking) {
-          TreePruner pruner = new TreePruner(application, appInfo.withLiveness(), options);
+          TreePruner pruner =
+              new TreePruner(application, appView.getAppInfo().withLiveness(), options);
           application = pruner.run();
           // Recompute the subtyping information.
-          appInfo = appInfo.withLiveness().prunedCopyFrom(application, pruner.getRemovedClasses());
-          new AbstractMethodRemover(appInfo).run();
+          appView.setAppInfo(
+              appView
+                  .getAppInfo()
+                  .withLiveness()
+                  .prunedCopyFrom(application, pruner.getRemovedClasses()));
+          new AbstractMethodRemover(appView.getAppInfo()).run();
         }
-        new AnnotationRemover(appInfo.withLiveness(), compatibility, options).run();
+        new AnnotationRemover(appView.getAppInfo().withLiveness(), compatibility, options).run();
 
         // TODO(69445518): This is still work in progress, and this file writing is currently used
         // for testing.
@@ -320,44 +338,52 @@
         timing.end();
       }
 
-      GraphLense graphLense = GraphLense.getIdentityLense();
-
       if (options.proguardConfiguration.isAccessModificationAllowed()) {
-        graphLense = ClassAndMemberPublicizer.run(
-            executorService, timing, application, appInfo, rootSet, graphLense);
+        appView.setGraphLense(
+            ClassAndMemberPublicizer.run(executorService, timing, application, appView, rootSet));
         // We can now remove visibility bridges. Note that we do not need to update the
         // invoke-targets here, as the existing invokes will simply dispatch to the now
         // visible super-method. MemberRebinding, if run, will then dispatch it correctly.
-        application = new VisibilityBridgeRemover(appInfo, application).run();
+        application = new VisibilityBridgeRemover(appView.getAppInfo(), application).run();
       }
 
-      if (appInfo.hasLiveness()) {
+      if (appView.getAppInfo().hasLiveness()) {
+        AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
+
         if (options.proguardConfiguration.hasApplyMappingFile()) {
           SeedMapper seedMapper =
               SeedMapper.seedMapperFromFile(options.proguardConfiguration.getApplyMappingFile());
           timing.begin("apply-mapping");
-          graphLense =
-              new ProguardMapApplier(appInfo.withLiveness(), graphLense, seedMapper).run(timing);
-          application = application.asDirect().rewrittenWithLense(graphLense);
-          appInfo = appInfo.withLiveness().rewrittenWithLense(application.asDirect(), graphLense);
+          appView.setGraphLense(
+              new ProguardMapApplier(appView.withLiveness(), seedMapper).run(timing));
+          application = application.asDirect().rewrittenWithLense(appView.getGraphLense());
+          appView.setAppInfo(
+              appView
+                  .getAppInfo()
+                  .withLiveness()
+                  .rewrittenWithLense(application.asDirect(), appView.getGraphLense()));
           timing.end();
         }
-        graphLense = new MemberRebindingAnalysis(appInfo.withLiveness(), graphLense).run();
+        appView.setGraphLense(new MemberRebindingAnalysis(appViewWithLiveness).run());
         // Class merging requires inlining.
         if (options.enableClassMerging && options.enableInlining) {
           timing.begin("ClassMerger");
           VerticalClassMerger classMerger =
-              new VerticalClassMerger(application, appInfo.withLiveness(), graphLense, timing);
-          graphLense = classMerger.run();
+              new VerticalClassMerger(application, appViewWithLiveness, timing);
+          appView.setGraphLense(classMerger.run());
           timing.end();
-          application = application.asDirect().rewrittenWithLense(graphLense);
-          appInfo = appInfo.withLiveness()
-              .prunedCopyFrom(application, classMerger.getRemovedClasses())
-              .rewrittenWithLense(application.asDirect(), graphLense);
+          application = application.asDirect().rewrittenWithLense(appView.getGraphLense());
+          appViewWithLiveness.setAppInfo(
+              appViewWithLiveness
+                  .getAppInfo()
+                  .prunedCopyFrom(application, classMerger.getRemovedClasses())
+                  .rewrittenWithLense(application.asDirect(), appView.getGraphLense()));
         }
         // Collect switch maps and ordinals maps.
-        appInfo = new SwitchMapCollector(appInfo.withLiveness(), options).run();
-        appInfo = new EnumOrdinalMapCollector(appInfo.withLiveness(), options).run();
+        appViewWithLiveness.setAppInfo(
+            new SwitchMapCollector(appViewWithLiveness.getAppInfo(), options).run());
+        appViewWithLiveness.setAppInfo(
+            new EnumOrdinalMapCollector(appViewWithLiveness.getAppInfo(), options).run());
 
         // TODO(b/79143143): re-enable once fixed.
         // graphLense = new BridgeMethodAnalysis(graphLense, appInfo.withLiveness()).run();
@@ -366,7 +392,9 @@
       timing.begin("Create IR");
       CfgPrinter printer = options.printCfg ? new CfgPrinter() : null;
       try {
-        IRConverter converter = new IRConverter(appInfo, options, timing, printer, graphLense);
+        IRConverter converter =
+            new IRConverter(
+                appView.getAppInfo(), options, timing, printer, appView.getGraphLense());
         application = converter.optimize(application, executorService);
       } finally {
         timing.end();
@@ -386,15 +414,15 @@
 
       // Overwrite SourceFile if specified. This step should be done after IR conversion.
       timing.begin("Rename SourceFile");
-      new SourceFileRewriter(appInfo, options).run();
+      new SourceFileRewriter(appView.getAppInfo(), options).run();
       timing.end();
 
       if (!options.mainDexKeepRules.isEmpty()) {
-        appInfo = new AppInfoWithSubtyping(application);
-        Enqueuer enqueuer = new Enqueuer(appInfo, options, true);
+        appView.setAppInfo(new AppInfoWithSubtyping(application));
+        Enqueuer enqueuer = new Enqueuer(appView.getAppInfo(), options, true);
         // Lets find classes which may have code executed before secondary dex files installation.
         RootSet mainDexRootSet =
-            new RootSetBuilder(appInfo, application, options.mainDexKeepRules, options)
+            new RootSetBuilder(appView.getAppInfo(), application, options.mainDexKeepRules, options)
                 .run(executorService);
         AppInfoWithLiveness mainDexAppInfo =
             enqueuer.traceMainDex(mainDexRootSet, executorService, timing);
@@ -409,18 +437,24 @@
             .build();
       }
 
-      appInfo = new AppInfoWithSubtyping(application);
+      appView.setAppInfo(new AppInfoWithSubtyping(application));
 
       if (options.enableTreeShaking || options.enableMinification) {
         timing.begin("Post optimization code stripping");
         try {
-          Enqueuer enqueuer = new Enqueuer(appInfo, options, options.forceProguardCompatibility);
-          appInfo = enqueuer.traceApplication(rootSet, executorService, timing);
+          Enqueuer enqueuer =
+              new Enqueuer(appView.getAppInfo(), options, options.forceProguardCompatibility);
+          appView.setAppInfo(enqueuer.traceApplication(rootSet, executorService, timing));
+
+          AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
           if (options.enableTreeShaking) {
-            TreePruner pruner = new TreePruner(application, appInfo.withLiveness(), options);
+            TreePruner pruner =
+                new TreePruner(application, appViewWithLiveness.getAppInfo(), options);
             application = pruner.run();
-            appInfo = appInfo.withLiveness()
-                .prunedCopyFrom(application, pruner.getRemovedClasses());
+            appViewWithLiveness.setAppInfo(
+                appViewWithLiveness
+                    .getAppInfo()
+                    .prunedCopyFrom(application, pruner.getRemovedClasses()));
             // Print reasons on the application after pruning, so that we reflect the actual result.
             ReasonPrinter reasonPrinter = enqueuer.getReasonPrinter(rootSet.reasonAsked);
             reasonPrinter.run(application);
@@ -440,7 +474,7 @@
       // will happen. Just avoid the overhead.
       NamingLens namingLens =
           options.enableMinification
-              ? new Minifier(appInfo.withLiveness(), rootSet, options).run(timing)
+              ? new Minifier(appView.getAppInfo().withLiveness(), rootSet, options).run(timing)
               : NamingLens.getIdentityLens();
       timing.end();
 
diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
new file mode 100644
index 0000000..64a4ce4
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -0,0 +1,83 @@
+// Copyright (c) 2018, 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.graph;
+
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
+
+public class AppView<T extends AppInfo> {
+
+  private T appInfo;
+  private final DexItemFactory dexItemFactory;
+  private GraphLense graphLense;
+
+  public AppView(T appInfo, GraphLense graphLense) {
+    this.appInfo = appInfo;
+    this.dexItemFactory = appInfo != null ? appInfo.dexItemFactory : null;
+    this.graphLense = graphLense;
+  }
+
+  public T getAppInfo() {
+    return appInfo;
+  }
+
+  public void setAppInfo(T appInfo) {
+    this.appInfo = appInfo;
+  }
+
+  public DexItemFactory getDexItemFactory() {
+    return dexItemFactory;
+  }
+
+  public GraphLense getGraphLense() {
+    return graphLense;
+  }
+
+  public void setGraphLense(GraphLense graphLense) {
+    this.graphLense = graphLense;
+  }
+
+  public AppView<AppInfoWithLiveness> withLiveness() {
+    return new AppViewWithLiveness();
+  }
+
+  private class AppViewWithLiveness extends AppView<AppInfoWithLiveness> {
+
+    private AppViewWithLiveness() {
+      super(null, null);
+    }
+
+    @Override
+    public AppInfoWithLiveness getAppInfo() {
+      return AppView.this.getAppInfo().withLiveness();
+    }
+
+    @Override
+    public void setAppInfo(AppInfoWithLiveness appInfoWithLiveness) {
+      @SuppressWarnings("unchecked")
+      T appInfo = (T) appInfoWithLiveness;
+      AppView.this.setAppInfo(appInfo);
+    }
+
+    @Override
+    public DexItemFactory getDexItemFactory() {
+      return AppView.this.dexItemFactory;
+    }
+
+    @Override
+    public GraphLense getGraphLense() {
+      return AppView.this.getGraphLense();
+    }
+
+    @Override
+    public void setGraphLense(GraphLense graphLense) {
+      AppView.this.setGraphLense(graphLense);
+    }
+
+    @Override
+    public AppView<AppInfoWithLiveness> withLiveness() {
+      return this;
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/graph/DexProto.java b/src/main/java/com/android/tools/r8/graph/DexProto.java
index 17f6efa..5c05605 100644
--- a/src/main/java/com/android/tools/r8/graph/DexProto.java
+++ b/src/main/java/com/android/tools/r8/graph/DexProto.java
@@ -8,6 +8,8 @@
 
 public class DexProto extends IndexedDexItem implements PresortedComparable<DexProto> {
 
+  public static final DexProto SENTINEL = new DexProto(null, null, null);
+
   public final DexString shorty;
   public final DexType returnType;
   public final DexTypeList parameters;
diff --git a/src/main/java/com/android/tools/r8/graph/JarCode.java b/src/main/java/com/android/tools/r8/graph/JarCode.java
index 640172f..d64eaf0 100644
--- a/src/main/java/com/android/tools/r8/graph/JarCode.java
+++ b/src/main/java/com/android/tools/r8/graph/JarCode.java
@@ -10,9 +10,12 @@
 import com.android.tools.r8.ir.code.ValueNumberGenerator;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.ir.conversion.JarSourceCode;
+import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import com.android.tools.r8.jar.InliningConstraintVisitor;
 import com.android.tools.r8.jar.JarRegisterEffectsVisitor;
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.InternalOptions;
 import java.io.PrintWriter;
@@ -169,6 +172,21 @@
             DescriptorUtils.getDescriptorFromClassBinaryName(tryCatchBlockNode.type))));
   }
 
+  public Constraint computeInliningConstraint(
+      AppInfoWithLiveness appInfo, GraphLense graphLense, DexType invocationContext) {
+    InliningConstraintVisitor visitor =
+        new InliningConstraintVisitor(application, appInfo, graphLense, method, invocationContext);
+    AbstractInsnNode insn = node.instructions.getFirst();
+    while (insn != null) {
+      insn.accept(visitor);
+      if (visitor.isFinished()) {
+        break;
+      }
+      insn = insn.getNext();
+    }
+    return visitor.getConstraint();
+  }
+
   @Override
   public String toString() {
     triggerDelayedParsingIfNeccessary();
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 b343de7..1ad50bc 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
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import java.util.Collection;
 import java.util.Collections;
@@ -113,7 +114,7 @@
 
   @Override
   public Constraint inliningConstraint(AppInfoWithLiveness info, DexType invocationContext) {
-    return inliningConstraintForSinlgeTargetInvoke(info, invocationContext);
+    return new InliningConstraints(info).forInvokeDirect(getInvokedMethod(), invocationContext);
   }
 
   @Override
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 ff8f0d0..0fb447b 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
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import java.util.Collection;
 import java.util.List;
@@ -95,7 +96,7 @@
 
   @Override
   public Constraint inliningConstraint(AppInfoWithLiveness info, DexType invocationContext) {
-    return inliningConstraintForVirtualInvoke(info, invocationContext);
+    return new InliningConstraints(info).forInvokeInterface(getInvokedMethod(), invocationContext);
   }
 
   @Override
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 5fe8972..56b659a 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
@@ -5,9 +5,7 @@
 
 import com.android.tools.r8.cf.LoadStoreHelper;
 import com.android.tools.r8.cf.TypeVerificationHelper;
-import com.android.tools.r8.graph.AppInfo.ResolutionResult;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
-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.DexType;
@@ -85,85 +83,11 @@
     return lookupSingleTarget(appInfo, appInfo.dexItemFactory.objectType);
   }
 
+  // TODO(christofferqa): Pass an instance of InliningConstraints instead of [info] when
+  // InliningConstraints is complete.
   @Override
-  public abstract Constraint inliningConstraint(AppInfoWithLiveness info,
-      DexType invocationContext);
-
-  protected Constraint inliningConstraintForSinlgeTargetInvoke(AppInfoWithLiveness info,
-      DexType invocationContext) {
-    if (method.holder.isArrayType()) {
-      return Constraint.ALWAYS;
-    }
-    DexEncodedMethod target = lookupSingleTarget(info, invocationContext);
-    if (target != null) {
-      DexType methodHolder = target.method.holder;
-      DexClass methodClass = info.definitionFor(methodHolder);
-      if ((methodClass != null)) {
-        Constraint methodConstraint = Constraint
-            .deriveConstraint(invocationContext, methodHolder, target.accessFlags, info);
-        // We also have to take the constraint of the enclosing class into account.
-        Constraint classConstraint = Constraint
-            .deriveConstraint(invocationContext, methodHolder, methodClass.accessFlags, info);
-        return Constraint.min(methodConstraint, classConstraint);
-      }
-    }
-    return Constraint.NEVER;
-  }
-
-  protected Constraint inliningConstraintForVirtualInvoke(AppInfoWithSubtyping info,
-      DexType invocationContext) {
-    if (method.holder.isArrayType()) {
-      return Constraint.ALWAYS;
-    }
-    Collection<DexEncodedMethod> targets = lookupTargets(info, invocationContext);
-    if (targets == null) {
-      return Constraint.NEVER;
-    }
-
-    Constraint result = Constraint.ALWAYS;
-
-    // Perform resolution and derive inlining constraints based on the accessibility of the
-    // resolution result.
-    ResolutionResult resolutionResult = info.resolveMethod(method.holder, method);
-    DexEncodedMethod resolutionTarget = resolutionResult.asResultOfResolve();
-    if (resolutionTarget == null) {
-      // This will fail at runtime.
-      return Constraint.NEVER;
-    }
-    DexType methodHolder = resolutionTarget.method.holder;
-    DexClass methodClass = info.definitionFor(methodHolder);
-    assert methodClass != null;
-    Constraint methodConstraint = Constraint
-        .deriveConstraint(invocationContext, methodHolder, resolutionTarget.accessFlags, info);
-    result = Constraint.min(result, methodConstraint);
-    // We also have to take the constraint of the enclosing class of the resolution result
-    // into account. We do not allow inlining this method if it is calling something that
-    // is inaccessible. Inlining in that case could move the code to another package making a
-    // call succeed that should not succeed. Conversely, if the resolution result is accessible,
-    // we have to make sure that inlining cannot make it inaccessible.
-    Constraint classConstraint = Constraint
-        .deriveConstraint(invocationContext, methodHolder, methodClass.accessFlags, info);
-    result = Constraint.min(result, classConstraint);
-    if (result == Constraint.NEVER) {
-      return result;
-    }
-
-    // For each of the actual potential targets, derive constraints based on the accessibility
-    // of the method itself.
-    for (DexEncodedMethod target : targets) {
-      methodHolder = target.method.holder;
-      methodClass = info.definitionFor(methodHolder);
-      assert methodClass != null;
-      methodConstraint = Constraint
-          .deriveConstraint(invocationContext, methodHolder, target.accessFlags, info);
-      result = Constraint.min(result, methodConstraint);
-      if (result == Constraint.NEVER) {
-        return result;
-      }
-    }
-
-    return result;
-  }
+  public abstract Constraint inliningConstraint(
+      AppInfoWithLiveness info, DexType invocationContext);
 
   public abstract InlineAction computeInlining(InliningOracle decider, DexType invocationContext);
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokePolymorphic.java b/src/main/java/com/android/tools/r8/ir/code/InvokePolymorphic.java
index 81d4cdc..91f657d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokePolymorphic.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokePolymorphic.java
@@ -15,6 +15,7 @@
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.ir.optimize.Inliner.InlineAction;
+import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.ir.optimize.InliningOracle;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import java.util.Collection;
@@ -126,7 +127,8 @@
 
   @Override
   public Constraint inliningConstraint(AppInfoWithLiveness info, DexType invocationContext) {
-    return Constraint.NEVER;
+    return new InliningConstraints(info)
+        .forInvokePolymorphic(getInvokedMethod(), invocationContext);
   }
 
   @Override
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 94df8d3..b985916 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
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.ir.optimize.Inliner.InlineAction;
+import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.ir.optimize.InliningOracle;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import java.util.Collection;
@@ -103,7 +104,7 @@
 
   @Override
   public Constraint inliningConstraint(AppInfoWithLiveness info, DexType invocationContext) {
-    return inliningConstraintForSinlgeTargetInvoke(info, invocationContext);
+    return new InliningConstraints(info).forInvokeStatic(getInvokedMethod(), invocationContext);
   }
 
   @Override
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 e5bd604..64f0d7b 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
@@ -14,6 +14,7 @@
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import java.util.Collection;
 import java.util.Collections;
@@ -112,7 +113,6 @@
 
   @Override
   public Constraint inliningConstraint(AppInfoWithLiveness info, DexType invocationContext) {
-    // The semantics of invoke super depend on the context.
-    return Constraint.SAMECLASS;
+    return new InliningConstraints(info).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 d104270..85c80ed 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
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import com.android.tools.r8.ir.optimize.InliningConstraints;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import java.util.Collection;
 import java.util.List;
@@ -95,7 +96,7 @@
 
   @Override
   public Constraint inliningConstraint(AppInfoWithLiveness info, DexType invocationContext) {
-    return inliningConstraintForVirtualInvoke(info, invocationContext);
+    return new InliningConstraints(info).forInvokeVirtual(getInvokedMethod(), invocationContext);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java b/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java
new file mode 100644
index 0000000..d4a06cd
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/InliningConstraints.java
@@ -0,0 +1,148 @@
+// Copyright (c) 2018, 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;
+
+import com.android.tools.r8.graph.AppInfo.ResolutionResult;
+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.DexType;
+import com.android.tools.r8.graph.GraphLense;
+import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
+import java.util.Collection;
+
+// Computes the inlining constraint for a given instruction.
+//
+// TODO(christofferqa): This class is incomplete.
+public class InliningConstraints {
+
+  private AppInfoWithLiveness appInfo;
+
+  // Currently used only by the vertical class merger (in all other cases this is the identity).
+  //
+  // When merging a type A into its subtype B we need to inline A.<init>() into B.<init>().
+  // Therefore, we need to be sure that A.<init>() can in fact be inlined into B.<init>() *before*
+  // we merge the two classes. However, at this point, we may reject the method A.<init>() from
+  // being inlined into B.<init>() only because it is not declared in the same class as B (which
+  // it would be after merging A and B).
+  //
+  // To circumvent this problem, the vertical class merger creates a graph lense that maps the
+  // type A to B, to create a temporary view of what the world would look like after class merging.
+  private GraphLense graphLense;
+
+  public InliningConstraints(AppInfoWithLiveness appInfo) {
+    this(appInfo, GraphLense.getIdentityLense());
+  }
+
+  public InliningConstraints(AppInfoWithLiveness appInfo, GraphLense graphLense) {
+    this.appInfo = appInfo;
+    this.graphLense = graphLense;
+  }
+
+  public Constraint forCheckCast(DexType type, DexType invocationContext) {
+    return Constraint.classIsVisible(invocationContext, type, appInfo);
+  }
+
+  public Constraint forInvokeDirect(DexMethod method, DexType invocationContext) {
+    return forSingleTargetInvoke(method, appInfo.lookupDirectTarget(method), invocationContext);
+  }
+
+  public Constraint forInvokeInterface(DexMethod method, DexType invocationContext) {
+    return forVirtualInvoke(method, appInfo.lookupInterfaceTargets(method), invocationContext);
+  }
+
+  public Constraint forInvokePolymorphic(DexMethod method, DexType invocationContext) {
+    return Constraint.NEVER;
+  }
+
+  public Constraint forInvokeStatic(DexMethod method, DexType invocationContext) {
+    return forSingleTargetInvoke(method, appInfo.lookupStaticTarget(method), invocationContext);
+  }
+
+  public Constraint forInvokeSuper(DexMethod method, DexType invocationContext) {
+    // The semantics of invoke super depend on the context.
+    return Constraint.SAMECLASS;
+  }
+
+  public Constraint forInvokeVirtual(DexMethod method, DexType invocationContext) {
+    return forVirtualInvoke(method, appInfo.lookupVirtualTargets(method), invocationContext);
+  }
+
+  private Constraint forSingleTargetInvoke(
+      DexMethod method, DexEncodedMethod target, DexType invocationContext) {
+    if (method.holder.isArrayType()) {
+      return Constraint.ALWAYS;
+    }
+    if (target != null) {
+      DexType methodHolder = graphLense.lookupType(target.method.holder);
+      DexClass methodClass = appInfo.definitionFor(methodHolder);
+      if (methodClass != null) {
+        Constraint methodConstraint =
+            Constraint.deriveConstraint(
+                invocationContext, methodHolder, target.accessFlags, appInfo);
+        // We also have to take the constraint of the enclosing class into account.
+        Constraint classConstraint =
+            Constraint.deriveConstraint(
+                invocationContext, methodHolder, methodClass.accessFlags, appInfo);
+        return Constraint.min(methodConstraint, classConstraint);
+      }
+    }
+    return Constraint.NEVER;
+  }
+
+  private Constraint forVirtualInvoke(
+      DexMethod method, Collection<DexEncodedMethod> targets, DexType invocationContext) {
+    if (method.holder.isArrayType()) {
+      return Constraint.ALWAYS;
+    }
+    if (targets == null) {
+      return Constraint.NEVER;
+    }
+
+    // Perform resolution and derive inlining constraints based on the accessibility of the
+    // resolution result.
+    ResolutionResult resolutionResult = appInfo.resolveMethod(method.holder, method);
+    DexEncodedMethod resolutionTarget = resolutionResult.asResultOfResolve();
+    if (resolutionTarget == null) {
+      // This will fail at runtime.
+      return Constraint.NEVER;
+    }
+
+    DexType methodHolder = graphLense.lookupType(resolutionTarget.method.holder);
+    DexClass methodClass = appInfo.definitionFor(methodHolder);
+    assert methodClass != null;
+    Constraint methodConstraint =
+        Constraint.deriveConstraint(
+            invocationContext, methodHolder, resolutionTarget.accessFlags, appInfo);
+    // We also have to take the constraint of the enclosing class of the resolution result
+    // into account. We do not allow inlining this method if it is calling something that
+    // is inaccessible. Inlining in that case could move the code to another package making a
+    // call succeed that should not succeed. Conversely, if the resolution result is accessible,
+    // we have to make sure that inlining cannot make it inaccessible.
+    Constraint classConstraint =
+        Constraint.deriveConstraint(
+            invocationContext, methodHolder, methodClass.accessFlags, appInfo);
+    Constraint result = Constraint.min(methodConstraint, classConstraint);
+    if (result == Constraint.NEVER) {
+      return result;
+    }
+
+    // For each of the actual potential targets, derive constraints based on the accessibility
+    // of the method itself.
+    for (DexEncodedMethod target : targets) {
+      methodHolder = graphLense.lookupType(target.method.holder);
+      assert appInfo.definitionFor(methodHolder) != null;
+      methodConstraint =
+          Constraint.deriveConstraint(invocationContext, methodHolder, target.accessFlags, appInfo);
+      result = Constraint.min(result, methodConstraint);
+      if (result == Constraint.NEVER) {
+        return result;
+      }
+    }
+
+    return result;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/jar/InliningConstraintVisitor.java b/src/main/java/com/android/tools/r8/jar/InliningConstraintVisitor.java
new file mode 100644
index 0000000..5652be8
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/jar/InliningConstraintVisitor.java
@@ -0,0 +1,128 @@
+// Copyright (c) 2018, 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.jar;
+
+import static org.objectweb.asm.Opcodes.ASM6;
+
+import com.android.tools.r8.dex.Constants;
+import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.GraphLense;
+import com.android.tools.r8.graph.JarApplicationReader;
+import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import com.android.tools.r8.ir.optimize.InliningConstraints;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
+import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Opcodes;
+
+// This visitor can be used to determine if a piece of jar code has any instructions that the
+// inliner would not be willing to inline. This can be used to determine if a method can be force
+// inlined although its IR is still not available.
+//
+// TODO(christofferqa): This class is incomplete. Still need to add support for ConstClass,
+// InstanceGet, InstanceOf, InstancePut, Monitor, MoveException, NewArrayEmpty, NewInstance,
+// StaticGet, StaticPut, etc.
+public class InliningConstraintVisitor extends MethodVisitor {
+
+  private final JarApplicationReader application;
+  private final AppInfoWithLiveness appInfo;
+  private final InliningConstraints inliningConstraints;
+  private final DexMethod method;
+  private final DexType invocationContext;
+
+  private Constraint constraint = Constraint.ALWAYS;
+
+  public InliningConstraintVisitor(
+      JarApplicationReader application,
+      AppInfoWithLiveness appInfo,
+      GraphLense graphLense,
+      DexMethod method,
+      DexType invocationContext) {
+    super(ASM6);
+    this.application = application;
+    this.appInfo = appInfo;
+    this.inliningConstraints = new InliningConstraints(appInfo, graphLense);
+    this.method = method;
+    this.invocationContext = invocationContext;
+  }
+
+  public Constraint getConstraint() {
+    return constraint;
+  }
+
+  private void updateConstraint(Constraint other) {
+    constraint = Constraint.min(constraint, other);
+  }
+
+  // Used to signal that the result is ready, such that we do not need to visit all instructions of
+  // the method, if we can see early on that it cannot be inlined anyway.
+  public boolean isFinished() {
+    return constraint == Constraint.NEVER;
+  }
+
+  @Override
+  public void visitMethodInsn(int opcode, String owner, String name, String desc, boolean itf) {
+    DexType ownerType = application.getTypeFromName(owner);
+    DexMethod target = application.getMethod(ownerType, name, desc);
+    switch (opcode) {
+      case Opcodes.INVOKEINTERFACE:
+        updateConstraint(inliningConstraints.forInvokeInterface(target, invocationContext));
+        break;
+
+      case Opcodes.INVOKESPECIAL:
+        if (name.equals(Constants.INSTANCE_INITIALIZER_NAME) || ownerType == invocationContext) {
+          updateConstraint(inliningConstraints.forInvokeDirect(target, invocationContext));
+        } else {
+          updateConstraint(inliningConstraints.forInvokeSuper(target, invocationContext));
+        }
+        break;
+
+      case Opcodes.INVOKESTATIC:
+        updateConstraint(inliningConstraints.forInvokeStatic(target, invocationContext));
+        break;
+
+      case Opcodes.INVOKEVIRTUAL:
+        // Instructions that target a private method in the same class are translated to
+        // invoke-direct.
+        if (target.holder == method.holder) {
+          DexClass clazz = appInfo.definitionFor(target.holder);
+          if (clazz != null && clazz.lookupDirectMethod(target) != null) {
+            updateConstraint(inliningConstraints.forInvokeDirect(target, invocationContext));
+            break;
+          }
+        }
+
+        updateConstraint(inliningConstraints.forInvokeVirtual(target, invocationContext));
+        break;
+
+      default:
+        throw new Unreachable("Unexpected opcode " + opcode);
+    }
+  }
+
+  @Override
+  public void visitTypeInsn(int opcode, String typeName) {
+    DexType type = application.getTypeFromName(typeName);
+    switch (opcode) {
+      case Opcodes.ANEWARRAY:
+        break;
+
+      case Opcodes.CHECKCAST:
+        updateConstraint(inliningConstraints.forCheckCast(type, invocationContext));
+        break;
+
+      case Opcodes.INSTANCEOF:
+        break;
+
+      case Opcodes.NEW:
+        break;
+
+      default:
+        throw new Unreachable("Unexpected opcode " + opcode);
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/naming/ProguardMapApplier.java b/src/main/java/com/android/tools/r8/naming/ProguardMapApplier.java
index f5d48fd..f114a7e 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMapApplier.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMapApplier.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.naming;
 
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexAnnotation;
 import com.android.tools.r8.graph.DexAnnotationSet;
 import com.android.tools.r8.graph.DexClass;
@@ -33,13 +34,10 @@
   private final GraphLense previousLense;
   private final SeedMapper seedMapper;
 
-  public ProguardMapApplier(
-      AppInfoWithLiveness appInfo,
-      GraphLense previousLense,
-      SeedMapper seedMapper) {
-    assert previousLense.isContextFreeForMethods();
-    this.appInfo = appInfo;
-    this.previousLense = previousLense;
+  public ProguardMapApplier(AppView<AppInfoWithLiveness> appView, SeedMapper seedMapper) {
+    assert appView.getGraphLense().isContextFreeForMethods();
+    this.appInfo = appView.getAppInfo();
+    this.previousLense = appView.getGraphLense();
     this.seedMapper = seedMapper;
   }
 
diff --git a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
index 04f8a3b..73ebf73 100644
--- a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
+++ b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
@@ -3,7 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.optimize;
 
-import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
@@ -31,42 +31,34 @@
 
 public final class ClassAndMemberPublicizer {
   private final DexApplication application;
-  private final AppInfo appInfo;
+  private final AppView appView;
   private final RootSet rootSet;
-  private final GraphLense previousLense;
   private final PublicizedLenseBuilder lenseBuilder;
 
   private final Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get();
   private final Map<DexClass, MethodPool> methodPools = new ConcurrentHashMap<>();
 
-  private ClassAndMemberPublicizer(
-      DexApplication application,
-      AppInfo appInfo,
-      RootSet rootSet,
-      GraphLense previousLense) {
+  private ClassAndMemberPublicizer(DexApplication application, AppView appView, RootSet rootSet) {
     this.application = application;
-    this.appInfo = appInfo;
+    this.appView = appView;
     this.rootSet = rootSet;
-    this.previousLense = previousLense;
     lenseBuilder = PublicizerLense.createBuilder();
   }
 
   /**
-   * Marks all package private and protected methods and fields as public.
-   * Makes all private static methods public.
-   * Makes private instance methods public final instance methods, if possible.
-   * <p>
-   * This will destructively update the DexApplication passed in as argument.
+   * Marks all package private and protected methods and fields as public. Makes all private static
+   * methods public. Makes private instance methods public final instance methods, if possible.
+   *
+   * <p>This will destructively update the DexApplication passed in as argument.
    */
   public static GraphLense run(
       ExecutorService executorService,
       Timing timing,
       DexApplication application,
-      AppInfo appInfo,
-      RootSet rootSet,
-      GraphLense previousLense) throws ExecutionException {
-    return new ClassAndMemberPublicizer(application, appInfo, rootSet, previousLense)
-        .run(executorService, timing);
+      AppView appView,
+      RootSet rootSet)
+      throws ExecutionException {
+    return new ClassAndMemberPublicizer(application, appView, rootSet).run(executorService, timing);
   }
 
   private GraphLense run(ExecutorService executorService, Timing timing)
@@ -84,11 +76,11 @@
 
     // Phase 2: Visit classes and promote class/member to public if possible.
     timing.begin("Phase 2: promoteToPublic");
-    DexType.forAllInterfaces(appInfo.dexItemFactory, this::publicizeType);
-    publicizeType(appInfo.dexItemFactory.objectType);
+    DexType.forAllInterfaces(appView.getDexItemFactory(), this::publicizeType);
+    publicizeType(appView.getDexItemFactory().objectType);
     timing.end();
 
-    return lenseBuilder.build(appInfo, previousLense);
+    return lenseBuilder.build(appView);
   }
 
   private Runnable computeMethodPoolPerClass(DexClass clazz) {
@@ -145,7 +137,7 @@
       return false;
     }
 
-    if (appInfo.dexItemFactory.isClassConstructor(encodedMethod.method)) {
+    if (appView.getDexItemFactory().isClassConstructor(encodedMethod.method)) {
       return false;
     }
 
@@ -156,7 +148,7 @@
     }
     assert accessFlags.isPrivate();
 
-    if (appInfo.dexItemFactory.isConstructor(encodedMethod.method)) {
+    if (appView.getDexItemFactory().isConstructor(encodedMethod.method)) {
       // TODO(b/72211928)
       return false;
     }
diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
index 9efd5c8..fe098cc 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.optimize;
 
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
@@ -28,10 +29,10 @@
   private final GraphLense lense;
   private final MemberRebindingLense.Builder builder;
 
-  public MemberRebindingAnalysis(AppInfoWithLiveness appInfo, GraphLense lense) {
-    assert lense.isContextFreeForMethods();
-    this.appInfo = appInfo;
-    this.lense = lense;
+  public MemberRebindingAnalysis(AppView<AppInfoWithLiveness> appView) {
+    assert appView.getGraphLense().isContextFreeForMethods();
+    this.appInfo = appView.getAppInfo();
+    this.lense = appView.getGraphLense();
     this.builder = MemberRebindingLense.builder(appInfo);
   }
 
diff --git a/src/main/java/com/android/tools/r8/optimize/PublicizerLense.java b/src/main/java/com/android/tools/r8/optimize/PublicizerLense.java
index 835135e..7a9c08f 100644
--- a/src/main/java/com/android/tools/r8/optimize/PublicizerLense.java
+++ b/src/main/java/com/android/tools/r8/optimize/PublicizerLense.java
@@ -3,7 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.optimize;
 
-import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
@@ -15,16 +15,19 @@
 import java.util.Set;
 
 final class PublicizerLense extends NestedGraphLense {
-  private final AppInfo appInfo;
+  private final AppView appView;
   private final Set<DexMethod> publicizedMethods;
 
-  PublicizerLense(
-      AppInfo appInfo, GraphLense previousLense, Set<DexMethod> publicizedMethods) {
+  PublicizerLense(AppView appView, Set<DexMethod> publicizedMethods) {
     // This lense does not map any DexItem's at all.
     // It will just tweak invoke type for publicized methods from invoke-direct to invoke-virtual.
-    super(ImmutableMap.of(), ImmutableMap.of(), ImmutableMap.of(),
-        previousLense, appInfo.dexItemFactory);
-    this.appInfo = appInfo;
+    super(
+        ImmutableMap.of(),
+        ImmutableMap.of(),
+        ImmutableMap.of(),
+        appView.getGraphLense(),
+        appView.getAppInfo().dexItemFactory);
+    this.appView = appView;
     this.publicizedMethods = publicizedMethods;
   }
 
@@ -35,18 +38,24 @@
     method = previous.getMethod();
     type = previous.getType();
     if (type == Type.DIRECT && publicizedMethods.contains(method)) {
-      DexClass holderClass = appInfo.definitionFor(method.holder);
-      if (holderClass != null) {
-        DexEncodedMethod actualEncodedTarget = holderClass.lookupVirtualMethod(method);
-        if (actualEncodedTarget != null
-            && actualEncodedTarget.isPublicized()) {
-          return new GraphLenseLookupResult(method, Type.VIRTUAL);
-        }
-      }
+      assert publicizedMethodIsPresentOnHolder(method, context);
+      return new GraphLenseLookupResult(method, Type.VIRTUAL);
     }
     return super.lookupMethod(method, context, type);
   }
 
+  private boolean publicizedMethodIsPresentOnHolder(DexMethod method, DexEncodedMethod context) {
+    GraphLenseLookupResult lookup =
+        appView.getGraphLense().lookupMethod(method, context, Type.VIRTUAL);
+    DexMethod signatureInCurrentWorld = lookup.getMethod();
+    DexClass clazz = appView.getAppInfo().definitionFor(signatureInCurrentWorld.holder);
+    assert clazz != null;
+    DexEncodedMethod actualEncodedTarget = clazz.lookupVirtualMethod(signatureInCurrentWorld);
+    assert actualEncodedTarget != null;
+    assert actualEncodedTarget.isPublicized();
+    return true;
+  }
+
   static PublicizedLenseBuilder createBuilder() {
     return new PublicizedLenseBuilder();
   }
@@ -57,8 +66,8 @@
     private PublicizedLenseBuilder() {
     }
 
-    public GraphLense build(AppInfo appInfo, GraphLense previousLense) {
-      return new PublicizerLense(appInfo, previousLense, methodSetBuilder.build());
+    public GraphLense build(AppView appView) {
+      return new PublicizerLense(appView, methodSetBuilder.build());
     }
 
     public void add(DexMethod publicizedMethod) {
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 3dc03f8..0ed3c11 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -6,6 +6,7 @@
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo.ResolutionResult;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexAnnotationSet;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexClass;
@@ -21,12 +22,14 @@
 import com.android.tools.r8.graph.DexTypeList;
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.graph.GraphLense.Builder;
+import com.android.tools.r8.graph.JarCode;
 import com.android.tools.r8.graph.KeyedDexItem;
 import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.graph.ParameterAnnotationsList;
 import com.android.tools.r8.graph.PresortedComparable;
 import com.android.tools.r8.graph.UseRegistry;
 import com.android.tools.r8.ir.code.Invoke.Type;
+import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.ir.synthetic.ForwardMethodSourceCode;
 import com.android.tools.r8.ir.synthetic.SynthesizedCode;
 import com.android.tools.r8.logging.Log;
@@ -39,6 +42,7 @@
 import com.google.common.collect.ImmutableSet;
 import it.unimi.dsi.fastutil.ints.Int2IntMap;
 import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
+import it.unimi.dsi.fastutil.objects.Reference2BooleanOpenHashMap;
 import it.unimi.dsi.fastutil.objects.Reference2IntMap;
 import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
 import java.util.ArrayDeque;
@@ -55,7 +59,6 @@
 import java.util.Map;
 import java.util.Set;
 import java.util.function.Predicate;
-import java.util.stream.Collectors;
 
 /**
  * Merges Supertypes with a single implementation into their single subtype.
@@ -143,45 +146,58 @@
   private final Timing timing;
   private Collection<DexMethod> invokes;
 
+  // Set of merge candidates.
+  private final Set<DexProgramClass> mergeCandidates = new HashSet<>();
+
   // Map from source class to target class.
   private final Map<DexType, DexType> mergedClasses = new HashMap<>();
 
   // Map from target class to the super classes that have been merged into the target class.
   private final Map<DexType, Set<DexType>> mergedClassesInverse = new HashMap<>();
 
+  // Set of types that must not be merged into their subtype.
+  private final Set<DexType> pinnedTypes = new HashSet<>();
+
   // The resulting graph lense that should be used after class merging.
   private final VerticalClassMergerGraphLense.Builder renamedMembersLense;
 
   public VerticalClassMerger(
-      DexApplication application,
-      AppInfoWithLiveness appInfo,
-      GraphLense graphLense,
-      Timing timing) {
+      DexApplication application, AppView<AppInfoWithLiveness> appView, Timing timing) {
     this.application = application;
-    this.appInfo = appInfo;
-    this.graphLense = graphLense;
+    this.appInfo = appView.getAppInfo();
+    this.graphLense = appView.getGraphLense();
     this.renamedMembersLense = VerticalClassMergerGraphLense.builder(appInfo);
     this.timing = timing;
+
+    Iterable<DexProgramClass> classes = application.classesWithDeterministicOrder();
+    initializePinnedTypes(classes); // Must be initialized prior to mergeCandidates.
+    initializeMergeCandidates(classes);
+  }
+
+  private void initializeMergeCandidates(Iterable<DexProgramClass> classes) {
+    for (DexProgramClass clazz : classes) {
+      if (isMergeCandidate(clazz, pinnedTypes) && isStillMergeCandidate(clazz)) {
+        mergeCandidates.add(clazz);
+      }
+    }
   }
 
   // Returns a set of types that must not be merged into other types.
-  private Set<DexType> getPinnedTypes(Iterable<DexProgramClass> classes) {
-    Set<DexType> pinnedTypes = new HashSet<>();
-
+  private void initializePinnedTypes(Iterable<DexProgramClass> classes) {
     // For all pinned fields, also pin the type of the field (because changing the type of the field
     // implicitly changes the signature of the field). Similarly, for all pinned methods, also pin
     // the return type and the parameter types of the method.
-    extractPinnedItems(appInfo.pinnedItems, pinnedTypes, AbortReason.PINNED_SOURCE);
+    extractPinnedItems(appInfo.pinnedItems, AbortReason.PINNED_SOURCE);
 
     // TODO(christofferqa): Remove the invariant that the graph lense should not modify any
     // methods from the sets alwaysInline and noSideEffects (see use of assertNotModified).
-    extractPinnedItems(appInfo.alwaysInline, pinnedTypes, AbortReason.ALWAYS_INLINE);
-    extractPinnedItems(appInfo.noSideEffects.keySet(), pinnedTypes, AbortReason.NO_SIDE_EFFECTS);
+    extractPinnedItems(appInfo.alwaysInline, AbortReason.ALWAYS_INLINE);
+    extractPinnedItems(appInfo.noSideEffects.keySet(), AbortReason.NO_SIDE_EFFECTS);
 
     for (DexProgramClass clazz : classes) {
       for (DexEncodedMethod method : clazz.methods()) {
         if (method.accessFlags.isNative()) {
-          markTypeAsPinned(clazz.type, pinnedTypes, AbortReason.NATIVE_METHOD);
+          markTypeAsPinned(clazz.type, AbortReason.NATIVE_METHOD);
         }
       }
     }
@@ -206,37 +222,35 @@
         pinnedTypes.add(signature.holder);
       }
     }
-    return pinnedTypes;
   }
 
-  private void extractPinnedItems(
-      Iterable<DexItem> items, Set<DexType> pinnedTypes, AbortReason reason) {
+  private void extractPinnedItems(Iterable<DexItem> items, AbortReason reason) {
     for (DexItem item : items) {
       if (item instanceof DexType || item instanceof DexClass) {
         DexType type = item instanceof DexType ? (DexType) item : ((DexClass) item).type;
-        markTypeAsPinned(type, pinnedTypes, reason);
+        markTypeAsPinned(type, reason);
       } else if (item instanceof DexField || item instanceof DexEncodedField) {
         // Pin the holder and the type of the field.
         DexField field =
             item instanceof DexField ? (DexField) item : ((DexEncodedField) item).field;
-        markTypeAsPinned(field.clazz, pinnedTypes, reason);
-        markTypeAsPinned(field.type, pinnedTypes, reason);
+        markTypeAsPinned(field.clazz, reason);
+        markTypeAsPinned(field.type, reason);
       } else if (item instanceof DexMethod || item instanceof DexEncodedMethod) {
         // Pin the holder, the return type and the parameter types of the method. If we were to
         // merge any of these types into their sub classes, then we would implicitly change the
         // signature of this method.
         DexMethod method =
             item instanceof DexMethod ? (DexMethod) item : ((DexEncodedMethod) item).method;
-        markTypeAsPinned(method.holder, pinnedTypes, reason);
-        markTypeAsPinned(method.proto.returnType, pinnedTypes, reason);
+        markTypeAsPinned(method.holder, reason);
+        markTypeAsPinned(method.proto.returnType, reason);
         for (DexType parameterType : method.proto.parameters.values) {
-          markTypeAsPinned(parameterType, pinnedTypes, reason);
+          markTypeAsPinned(parameterType, reason);
         }
       }
     }
   }
 
-  private void markTypeAsPinned(DexType type, Set<DexType> pinnedTypes, AbortReason reason) {
+  private void markTypeAsPinned(DexType type, AbortReason reason) {
     if (appInfo.isPinned(type)) {
       // We check for the case where the type is pinned according to appInfo.isPinned,
       // so we only need to add it here if it is not the case.
@@ -255,6 +269,8 @@
     }
   }
 
+  // Returns true if [clazz] is a merge candidate. Note that the result of the checks in this
+  // method do not change in response to any class merges.
   private boolean isMergeCandidate(DexProgramClass clazz, Set<DexType> pinnedTypes) {
     if (appInfo.instantiatedTypes.contains(clazz.type)
         || appInfo.instantiatedLambdas.contains(clazz.type)
@@ -262,14 +278,8 @@
         || pinnedTypes.contains(clazz.type)) {
       return false;
     }
-    if (mergedClassesInverse.containsKey(clazz.type)) {
-      // Do not allow merging the resulting class into its subclass.
-      // TODO(christofferqa): Get rid of this limitation.
-      if (Log.ENABLED) {
-        AbortReason.ALREADY_MERGED.printLogMessageForClass(clazz);
-      }
-      return false;
-    }
+    // Note that the property "singleSubtype == null" cannot change during merging, since we visit
+    // classes in a top-down order.
     DexType singleSubtype = clazz.type.getSingleSubtype();
     if (singleSubtype == null) {
       // TODO(christofferqa): Even if [clazz] has multiple subtypes, we could still merge it into
@@ -286,7 +296,7 @@
       if (appInfo.isPinned(method.method)) {
         return false;
       }
-      if (method.isInstanceInitializer() && disallowInlining(method)) {
+      if (method.isInstanceInitializer() && disallowInlining(method, singleSubtype)) {
         // Cannot guarantee that markForceInline() will work.
         if (Log.ENABLED) {
           AbortReason.UNSAFE_INLINING.printLogMessageForClass(clazz);
@@ -294,13 +304,64 @@
         return false;
       }
     }
-    DexClass targetClass = appInfo.definitionFor(singleSubtype);
+    if (clazz.getEnclosingMethod() != null || !clazz.getInnerClasses().isEmpty()) {
+      // TODO(herhut): Consider supporting merging of enclosing-method and inner-class attributes.
+      if (Log.ENABLED) {
+        AbortReason.UNSUPPORTED_ATTRIBUTES.printLogMessageForClass(clazz);
+      }
+      return false;
+    }
+    return true;
+  }
+
+  // Returns true if [clazz] is a merge candidate. Note that the result of the checks in this
+  // method may change in response to class merges. Therefore, this method should always be called
+  // before merging [clazz] into its subtype.
+  private boolean isStillMergeCandidate(DexProgramClass clazz) {
+    assert isMergeCandidate(clazz, pinnedTypes);
+    if (mergedClassesInverse.containsKey(clazz.type)) {
+      // Do not allow merging the resulting class into its subclass.
+      // TODO(christofferqa): Get rid of this limitation.
+      if (Log.ENABLED) {
+        AbortReason.ALREADY_MERGED.printLogMessageForClass(clazz);
+      }
+      return false;
+    }
+    DexClass targetClass = appInfo.definitionFor(clazz.type.getSingleSubtype());
+    if (clazz.hasClassInitializer() && targetClass.hasClassInitializer()) {
+      // TODO(herhut): Handle class initializers.
+      if (Log.ENABLED) {
+        AbortReason.STATIC_INITIALIZERS.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) {
+        AbortReason.UNSUPPORTED_ATTRIBUTES.printLogMessageForClass(clazz);
+      }
+      return false;
+    }
     if (mergeMayLeadToIllegalAccesses(clazz, targetClass)) {
       if (Log.ENABLED) {
         AbortReason.ILLEGAL_ACCESS.printLogMessageForClass(clazz);
       }
       return false;
     }
+    if (methodResolutionMayChange(clazz, targetClass)) {
+      if (Log.ENABLED) {
+        AbortReason.RESOLUTION_FOR_METHODS_MAY_CHANGE.printLogMessageForClass(clazz);
+      }
+      return false;
+    }
+    // Field resolution first considers the direct interfaces of [targetClass] before it proceeds
+    // to the super class.
+    if (fieldResolutionMayChange(clazz, targetClass)) {
+      if (Log.ENABLED) {
+        AbortReason.RESOLUTION_FOR_FIELDS_MAY_CHANGE.printLogMessageForClass(clazz);
+      }
+      return false;
+    }
     return true;
   }
 
@@ -349,49 +410,101 @@
     return false;
   }
 
-  private void addProgramMethods(Set<Wrapper<DexMethod>> set, DexMethod method,
-      Equivalence<DexMethod> equivalence) {
-    DexClass definition = appInfo.definitionFor(method.holder);
-    if (definition != null && definition.isProgramClass()) {
-      set.add(equivalence.wrap(method));
-    }
-  }
-
   private Collection<DexMethod> getInvokes() {
     if (invokes == null) {
-      // Collect all reachable methods that are not within a library class. Those defined on
-      // library classes are known not to have program classes in their signature.
-      // Also filter methods that only use types from library classes in their signatures. We
-      // know that those won't conflict.
-      Set<Wrapper<DexMethod>> filteredInvokes = new HashSet<>();
-      Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get();
-      appInfo.targetedMethods.forEach(m -> addProgramMethods(filteredInvokes, m, equivalence));
-      invokes = filteredInvokes.stream().map(Wrapper::get).filter(this::removeNonProgram)
-          .collect(Collectors.toList());
+      invokes = new OverloadedMethodSignaturesRetriever().get();
     }
     return invokes;
   }
 
-  private boolean isProgramClass(DexType type) {
-    if (type.isArrayType()) {
-      type = type.toBaseType(appInfo.dexItemFactory);
-    }
-    if (type.isClassType()) {
-      DexClass clazz = appInfo.definitionFor(type);
-      if (clazz != null && clazz.isProgramClass()) {
-        return true;
-      }
-    }
-    return false;
-  }
+  // Collects all potentially overloaded method signatures that reference at least one type that
+  // may be the source or target of a merge operation.
+  private class OverloadedMethodSignaturesRetriever {
+    private final Reference2BooleanOpenHashMap<DexProto> cache =
+        new Reference2BooleanOpenHashMap<>();
+    private final Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get();
+    private final Set<DexType> mergeeCandidates = new HashSet<>();
 
-  private boolean removeNonProgram(DexMethod dexMethod) {
-    for (DexType type : dexMethod.proto.parameters.values) {
-      if (isProgramClass(type)) {
-        return true;
+    public OverloadedMethodSignaturesRetriever() {
+      for (DexProgramClass mergeCandidate : mergeCandidates) {
+        mergeeCandidates.add(mergeCandidate.type.getSingleSubtype());
       }
     }
-    return isProgramClass(dexMethod.proto.returnType);
+
+    public Collection<DexMethod> get() {
+      Map<DexString, DexProto> overloadingInfo = new HashMap<>();
+
+      // Find all signatures that may reference a type that could be the source or target of a
+      // merge operation.
+      Set<Wrapper<DexMethod>> filteredSignatures = new HashSet<>();
+      for (DexMethod signature : appInfo.targetedMethods) {
+        DexClass definition = appInfo.definitionFor(signature.holder);
+        if (definition != null
+            && definition.isProgramClass()
+            && protoMayReferenceMergedSourceOrTarget(signature.proto)) {
+          filteredSignatures.add(equivalence.wrap(signature));
+
+          // Record that we have seen a method named [signature.name] with the proto
+          // [signature.proto]. If at some point, we find a method with the same name, but a
+          // different proto, it could be the case that a method with the given name is overloaded.
+          DexProto existing =
+              overloadingInfo.computeIfAbsent(signature.name, key -> signature.proto);
+          if (!existing.equals(signature.proto)) {
+            // Mark that this signature is overloaded by mapping it to SENTINEL.
+            overloadingInfo.put(signature.name, DexProto.SENTINEL);
+          }
+        }
+      }
+
+      List<DexMethod> result = new ArrayList<>();
+      for (Wrapper<DexMethod> wrappedSignature : filteredSignatures) {
+        DexMethod signature = wrappedSignature.get();
+
+        // Ignore those method names that are definitely not overloaded since they cannot lead to
+        // any collisions.
+        if (overloadingInfo.get(signature.name) == DexProto.SENTINEL) {
+          result.add(signature);
+        }
+      }
+      return result;
+    }
+
+    private boolean protoMayReferenceMergedSourceOrTarget(DexProto proto) {
+      boolean result;
+      if (cache.containsKey(proto)) {
+        result = cache.getBoolean(proto);
+      } else {
+        result = false;
+        if (typeMayReferenceMergedSourceOrTarget(proto.returnType)) {
+          result = true;
+        } else {
+          for (DexType type : proto.parameters.values) {
+            if (typeMayReferenceMergedSourceOrTarget(type)) {
+              result = true;
+              break;
+            }
+          }
+        }
+        cache.put(proto, result);
+      }
+      return result;
+    }
+
+    private boolean typeMayReferenceMergedSourceOrTarget(DexType type) {
+      if (type.isArrayType()) {
+        type = type.toBaseType(appInfo.dexItemFactory);
+      }
+      if (type.isClassType()) {
+        if (mergeeCandidates.contains(type)) {
+          return true;
+        }
+        DexClass clazz = appInfo.definitionFor(type);
+        if (clazz != null && clazz.isProgramClass()) {
+          return mergeCandidates.contains(clazz.asProgramClass());
+        }
+      }
+      return false;
+    }
   }
 
   public GraphLense run() {
@@ -408,19 +521,21 @@
     return result;
   }
 
-  private void addAncestorsToWorklist(
+  private void addCandidateAncestorsToWorklist(
       DexProgramClass clazz, Deque<DexProgramClass> worklist, Set<DexProgramClass> seenBefore) {
     if (seenBefore.contains(clazz)) {
       return;
     }
 
-    worklist.addFirst(clazz);
+    if (mergeCandidates.contains(clazz)) {
+      worklist.addFirst(clazz);
+    }
 
     // Add super classes to worklist.
     if (clazz.superType != null) {
       DexClass definition = appInfo.definitionFor(clazz.superType);
       if (definition != null && definition.isProgramClass()) {
-        addAncestorsToWorklist(definition.asProgramClass(), worklist, seenBefore);
+        addCandidateAncestorsToWorklist(definition.asProgramClass(), worklist, seenBefore);
       }
     }
 
@@ -428,71 +543,60 @@
     for (DexType interfaceType : clazz.interfaces.values) {
       DexClass definition = appInfo.definitionFor(interfaceType);
       if (definition != null && definition.isProgramClass()) {
-        addAncestorsToWorklist(definition.asProgramClass(), worklist, seenBefore);
+        addCandidateAncestorsToWorklist(definition.asProgramClass(), worklist, seenBefore);
       }
     }
   }
 
   private GraphLense mergeClasses(GraphLense graphLense) {
-    Iterable<DexProgramClass> classes = application.classesWithDeterministicOrder();
     Deque<DexProgramClass> worklist = new ArrayDeque<>();
     Set<DexProgramClass> seenBefore = new HashSet<>();
 
     int numberOfMerges = 0;
 
-    // Types that are pinned (in addition to those where appInfo.isPinned returns true).
-    Set<DexType> pinnedTypes = getPinnedTypes(classes);
-
-    Iterator<DexProgramClass> classIterator = classes.iterator();
+    Iterator<DexProgramClass> candidatesIterator = mergeCandidates.iterator();
 
     // Visit the program classes in a top-down order according to the class hierarchy.
-    while (classIterator.hasNext() || !worklist.isEmpty()) {
+    while (candidatesIterator.hasNext() || !worklist.isEmpty()) {
       if (worklist.isEmpty()) {
         // Add the ancestors of this class (including the class itself) to the worklist in such a
         // way that all super types of the class come before the class itself.
-        addAncestorsToWorklist(classIterator.next(), worklist, seenBefore);
+        addCandidateAncestorsToWorklist(candidatesIterator.next(), worklist, seenBefore);
         if (worklist.isEmpty()) {
           continue;
         }
       }
 
       DexProgramClass clazz = worklist.removeFirst();
-      if (!seenBefore.add(clazz) || !isMergeCandidate(clazz, pinnedTypes)) {
+      assert isMergeCandidate(clazz, pinnedTypes);
+      if (!seenBefore.add(clazz)) {
         continue;
       }
 
-      DexClass targetClass = appInfo.definitionFor(clazz.type.getSingleSubtype());
+      DexProgramClass targetClass =
+          appInfo.definitionFor(clazz.type.getSingleSubtype()).asProgramClass();
       assert !mergedClasses.containsKey(targetClass.type);
-      if (clazz.hasClassInitializer() && targetClass.hasClassInitializer()) {
-        // TODO(herhut): Handle class initializers.
-        if (Log.ENABLED) {
-          AbortReason.STATIC_INITIALIZERS.printLogMessageForClass(clazz);
+
+      boolean clazzOrTargetClassHasBeenMerged =
+          mergedClassesInverse.containsKey(clazz.type)
+              || mergedClassesInverse.containsKey(targetClass.type);
+      if (clazzOrTargetClassHasBeenMerged) {
+        if (!isStillMergeCandidate(clazz)) {
+          continue;
         }
-        continue;
+      } else {
+        assert isStillMergeCandidate(clazz);
       }
-      if (methodResolutionMayChange(clazz, targetClass)) {
-        if (Log.ENABLED) {
-          AbortReason.RESOLUTION_FOR_METHODS_MAY_CHANGE.printLogMessageForClass(clazz);
-        }
-        continue;
-      }
-      // Field resolution first considers the direct interfaces of [targetClass] before it proceeds
-      // to the super class.
-      if (fieldResolutionMayChange(clazz, targetClass)) {
-        if (Log.ENABLED) {
-          AbortReason.RESOLUTION_FOR_FIELDS_MAY_CHANGE.printLogMessageForClass(clazz);
-        }
-        continue;
-      }
+
       // 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, getInvokes(), mergedClasses)
-          .mayCollide()) {
+      if (new CollisionDetector(clazz.type, targetClass.type).mayCollide()) {
         if (Log.ENABLED) {
           AbortReason.CONFLICT.printLogMessageForClass(clazz);
         }
         continue;
       }
+
       ClassMerger merger = new ClassMerger(clazz, targetClass);
       boolean merged = merger.merge();
       if (merged) {
@@ -610,14 +714,6 @@
     }
 
     public boolean merge() {
-      if (source.getEnclosingMethod() != null || !source.getInnerClasses().isEmpty()
-          || target.getEnclosingMethod() != null || !target.getInnerClasses().isEmpty()) {
-        // TODO(herhut): Consider supporting merging of inner-class attributes.
-        if (Log.ENABLED) {
-          AbortReason.UNSUPPORTED_ATTRIBUTES.printLogMessageForClass(source);
-        }
-        return false;
-      }
       // Merge the class [clazz] into [targetClass] by adding all methods to
       // targetClass that are not currently contained.
       // Step 1: Merge methods
@@ -1157,22 +1253,18 @@
 
   private class CollisionDetector {
 
-    private static final int NOT_FOUND = 1 << (Integer.SIZE - 1);
+    private static final int NOT_FOUND = Integer.MIN_VALUE;
 
     // TODO(herhut): Maybe cache seenPositions for target classes.
     private final Map<DexString, Int2IntMap> seenPositions = new IdentityHashMap<>();
     private final Reference2IntMap<DexProto> targetProtoCache;
     private final Reference2IntMap<DexProto> sourceProtoCache;
     private final DexType source, target;
-    private final Collection<DexMethod> invokes;
-    private final Map<DexType, DexType> substituions;
+    private final Collection<DexMethod> invokes = getInvokes();
 
-    private CollisionDetector(DexType source, DexType target, Collection<DexMethod> invokes,
-        Map<DexType, DexType> substitutions) {
+    private CollisionDetector(DexType source, DexType target) {
       this.source = source;
       this.target = target;
-      this.invokes = invokes;
-      this.substituions = substitutions;
       this.targetProtoCache = new Reference2IntOpenHashMap<>(invokes.size() / 2);
       this.targetProtoCache.defaultReturnValue(NOT_FOUND);
       this.sourceProtoCache = new Reference2IntOpenHashMap<>(invokes.size() / 2);
@@ -1181,7 +1273,7 @@
 
     boolean mayCollide() {
       timing.begin("collision detection");
-      fillSeenPositions(invokes);
+      fillSeenPositions();
       boolean result = false;
       // If the type is not used in methods at all, there cannot be any conflict.
       if (!seenPositions.isEmpty()) {
@@ -1192,8 +1284,7 @@
             int previous = positionsMap.get(arity);
             if (previous != NOT_FOUND) {
               assert previous != 0;
-              int positions =
-                  computePositionsFor(method.proto, source, sourceProtoCache, substituions);
+              int positions = computePositionsFor(method.proto, source, sourceProtoCache);
               if ((positions & previous) != 0) {
                 result = true;
                 break;
@@ -1206,11 +1297,11 @@
       return result;
     }
 
-    private void fillSeenPositions(Collection<DexMethod> invokes) {
+    private void fillSeenPositions() {
       for (DexMethod method : invokes) {
         DexType[] parameters = method.proto.parameters.values;
         int arity = parameters.length;
-        int positions = computePositionsFor(method.proto, target, targetProtoCache, substituions);
+        int positions = computePositionsFor(method.proto, target, targetProtoCache);
         if (positions != 0) {
           Int2IntMap positionsMap =
               seenPositions.computeIfAbsent(method.name, k -> {
@@ -1230,8 +1321,10 @@
 
     }
 
-    private int computePositionsFor(DexProto proto, DexType type,
-        Reference2IntMap<DexProto> cache, Map<DexType, DexType> substitutions) {
+    // Given a method signature and a type, this method computes a bit vector that denotes the
+    // positions at which the given type is used in the method signature.
+    private int computePositionsFor(
+        DexProto proto, DexType type, Reference2IntMap<DexProto> cache) {
       int result = cache.getInt(proto);
       if (result != NOT_FOUND) {
         return result;
@@ -1240,13 +1333,8 @@
       int bitsUsed = 0;
       int accumulator = 0;
       for (DexType aType : proto.parameters.values) {
-        if (substitutions != null) {
-          // Substitute the type with the already merged class to estimate what it will
-          // look like.
-          while (substitutions.containsKey(aType)) {
-            aType = substitutions.get(aType);
-          }
-        }
+        // Substitute the type with the already merged class to estimate what it will look like.
+        aType = mergedClasses.getOrDefault(aType, aType);
         accumulator <<= 1;
         bitsUsed++;
         if (aType == type) {
@@ -1260,12 +1348,7 @@
         }
       }
       // We also take the return type into account for potential conflicts.
-      DexType returnType = proto.returnType;
-      if (substitutions != null) {
-        while (substitutions.containsKey(returnType)) {
-          returnType = substitutions.get(returnType);
-        }
-      }
+      DexType returnType = mergedClasses.getOrDefault(proto.returnType, proto.returnType);
       accumulator <<= 1;
       if (returnType == type) {
         accumulator |= 1;
@@ -1276,83 +1359,52 @@
     }
   }
 
-  private static boolean disallowInlining(DexEncodedMethod method) {
+  private boolean disallowInlining(DexEncodedMethod method, DexType invocationContext) {
     // TODO(christofferqa): Determine the situations where markForceInline() may fail, and ensure
     // that we always return true here in these cases.
-    MethodInlineDecision registry = new MethodInlineDecision();
-    method.getCode().registerCodeReferences(registry);
-    return registry.isInliningDisallowed();
+    if (method.getCode().isJarCode()) {
+      JarCode jarCode = method.getCode().asJarCode();
+      Constraint constraint =
+          jarCode.computeInliningConstraint(
+              appInfo,
+              new SingleTypeMapperGraphLense(method.method.holder, invocationContext),
+              invocationContext);
+      return constraint == Constraint.NEVER;
+    }
+    // TODO(christofferqa): For non-jar code we currently cannot guarantee that markForceInline()
+    // will succeed.
+    return true;
   }
 
-  private static class MethodInlineDecision extends UseRegistry {
-    private boolean disallowInlining = false;
+  private static class SingleTypeMapperGraphLense extends GraphLense {
 
-    public boolean isInliningDisallowed() {
-      return disallowInlining;
-    }
+    private final DexType source;
+    private final DexType target;
 
-    private boolean allowInlining() {
-      return true;
-    }
-
-    private boolean disallowInlining() {
-      disallowInlining = true;
-      return true;
+    public SingleTypeMapperGraphLense(DexType source, DexType target) {
+      this.source = source;
+      this.target = target;
     }
 
     @Override
-    public boolean registerInvokeInterface(DexMethod method) {
-      return disallowInlining();
+    public DexType lookupType(DexType type) {
+      return type == source ? target : type;
     }
 
     @Override
-    public boolean registerInvokeVirtual(DexMethod method) {
-      return disallowInlining();
+    public GraphLenseLookupResult lookupMethod(
+        DexMethod method, DexEncodedMethod context, Type type) {
+      throw new Unreachable();
     }
 
     @Override
-    public boolean registerInvokeDirect(DexMethod method) {
-      return allowInlining();
+    public DexField lookupField(DexField field) {
+      throw new Unreachable();
     }
 
     @Override
-    public boolean registerInvokeStatic(DexMethod method) {
-      return allowInlining();
-    }
-
-    @Override
-    public boolean registerInvokeSuper(DexMethod method) {
-      return allowInlining();
-    }
-
-    @Override
-    public boolean registerInstanceFieldWrite(DexField field) {
-      return allowInlining();
-    }
-
-    @Override
-    public boolean registerInstanceFieldRead(DexField field) {
-      return allowInlining();
-    }
-
-    @Override
-    public boolean registerNewInstance(DexType type) {
-      return allowInlining();
-    }
-
-    @Override
-    public boolean registerStaticFieldRead(DexField field) {
-      return allowInlining();
-    }
-
-    @Override
-    public boolean registerStaticFieldWrite(DexField field) {
-      return allowInlining();
-    }
-
-    @Override
-    public boolean registerTypeReference(DexType type) {
-      return allowInlining();
+    public boolean isContextFreeForMethods() {
+      throw new Unreachable();
     }
   }
 
diff --git a/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java b/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
index c2df29a..e0d73e8 100644
--- a/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
@@ -23,6 +23,8 @@
 import com.android.tools.r8.code.MoveException;
 import com.android.tools.r8.graph.DexCode;
 import com.android.tools.r8.ir.optimize.Inliner.Reason;
+import com.android.tools.r8.jasmin.JasminBuilder;
+import com.android.tools.r8.jasmin.JasminBuilder.ClassBuilder;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.smali.SmaliBuilder;
 import com.android.tools.r8.utils.AndroidApiLevel;
@@ -345,47 +347,57 @@
             "classmerging.D",
             "classmerging.F");
 
-    SmaliBuilder smaliBuilder = new SmaliBuilder();
+    JasminBuilder jasminBuilder = new JasminBuilder();
 
-    smaliBuilder.addClass(main);
-    smaliBuilder.addMainMethod(
-        2,
+    ClassBuilder classBuilder = jasminBuilder.addClass(main);
+    classBuilder.addMainMethod(
+        ".limit locals 1",
+        ".limit stack 2",
         // Instantiate B so that it is not merged into C.
-        "new-instance v1, Lclassmerging/B;",
-        "invoke-direct {v1}, Lclassmerging/B;-><init>()V",
-        "invoke-virtual {v1}, Lclassmerging/B;->m()V",
+        "new classmerging/B",
+        "dup",
+        "invokespecial classmerging/B/<init>()V",
+        "invokevirtual classmerging/B/m()V",
         // Instantiate D so that it is not merged into E.
-        "new-instance v1, Lclassmerging/D;",
-        "invoke-direct {v1}, Lclassmerging/D;-><init>()V",
-        "invoke-virtual {v1}, Lclassmerging/D;->m()V",
+        "new classmerging/D",
+        "dup",
+        "invokespecial classmerging/D/<init>()V",
+        "invokevirtual classmerging/D/m()V",
         // Start the actual testing.
-        "new-instance v1, Lclassmerging/F;",
-        "invoke-direct {v1}, Lclassmerging/F;-><init>()V",
-        "invoke-virtual {v1}, Lclassmerging/F;->invokeMethodOnB()V",
-        "invoke-virtual {v1}, Lclassmerging/F;->invokeMethodOnC()V",
-        "invoke-virtual {v1}, Lclassmerging/F;->invokeMethodOnD()V",
-        "invoke-virtual {v1}, Lclassmerging/F;->invokeMethodOnE()V",
-        "invoke-virtual {v1}, Lclassmerging/F;->invokeMethodOnF()V",
+        "new classmerging/F",
+        "dup",
+        "invokespecial classmerging/F/<init>()V",
+        "dup",
+        "invokevirtual classmerging/F/invokeMethodOnB()V",
+        "dup",
+        "invokevirtual classmerging/F/invokeMethodOnC()V",
+        "dup",
+        "invokevirtual classmerging/F/invokeMethodOnD()V",
+        "dup",
+        "invokevirtual classmerging/F/invokeMethodOnE()V",
+        "dup",
+        "invokevirtual classmerging/F/invokeMethodOnF()V",
+        "dup",
         // The method invokeMethodOnA() should yield a NoSuchMethodError.
-        ":try_start",
-        "invoke-virtual {v1}, Lclassmerging/F;->invokeMethodOnA()V",
-        ":try_end",
-        "return-void",
-        ".catch Ljava/lang/NoSuchMethodError; {:try_start .. :try_end} :catch",
-        ":catch",
-        smaliCodeForPrinting("NoSuchMethodError", 0, 1),
-        "return-void");
+        "try_start:",
+        "invokevirtual classmerging/F/invokeMethodOnA()V",
+        "try_end:",
+        "return",
+        "catch:",
+        jasminCodeForPrinting("NoSuchMethodError"),
+        "return",
+        ".catch java/lang/NoSuchMethodError from try_start to try_end using catch");
 
     // Class A deliberately has no method m. We need to make sure that the "invoke-super A.m()"
     // instruction in class F is not rewritten into something that does not throw.
-    smaliBuilder.addClass("classmerging.A");
-    smaliBuilder.addDefaultConstructor();
+    classBuilder = jasminBuilder.addClass("classmerging.A");
+    classBuilder.addDefaultConstructor();
 
     // Class B declares a virtual method m() that prints "In B.m()".
-    smaliBuilder.addClass("classmerging.B", "classmerging.A");
-    smaliBuilder.addDefaultConstructor();
-    smaliBuilder.addInstanceMethod(
-        "void", "m", 2, smaliCodeForPrinting("In B.m()", 0, 1), "return-void");
+    classBuilder = jasminBuilder.addClass("classmerging.B", "classmerging.A");
+    classBuilder.addDefaultConstructor();
+    classBuilder.addVirtualMethod(
+        "m", "V", ".limit locals 1", ".limit stack 2", jasminCodeForPrinting("In B.m()"), "return");
 
     // Class C, D, and E declare a virtual method m() that prints "In C.m()", "In D.m()", and
     // "In E.m()", respectively.
@@ -393,17 +405,24 @@
         new String[][] {new String[] {"C", "B"}, new String[] {"D", "C"}, new String[] {"E", "D"}};
     for (String[] pair : pairs) {
       String name = pair[0], superName = pair[1];
-      smaliBuilder.addClass("classmerging." + name, "classmerging." + superName);
-      smaliBuilder.addDefaultConstructor();
-      smaliBuilder.addInstanceMethod(
-          "void",
+      classBuilder = jasminBuilder.addClass("classmerging." + name, "classmerging." + superName);
+      classBuilder.addDefaultConstructor();
+      classBuilder.addVirtualMethod(
           "m",
-          2,
-          smaliCodeForPrinting("In " + name + ".m()", 0, 1),
-          buildCode("invoke-super {p0}, Lclassmerging/" + superName + ";->m()V", "return-void"));
+          "V",
+          ".limit locals 1",
+          ".limit stack 2",
+          jasminCodeForPrinting("In " + name + ".m()"),
+          "aload_0",
+          "invokespecial classmerging/" + superName + "/m()V",
+          "return");
     }
 
     // Class F declares a virtual method m that throws an exception (it is expected to be dead).
+    //
+    // Note that F is generated from smali since it is the only way to generate an instruction on
+    // the form "invoke-super F.m()".
+    SmaliBuilder smaliBuilder = new SmaliBuilder();
     smaliBuilder.addClass("classmerging.F", "classmerging.E");
     smaliBuilder.addDefaultConstructor();
     smaliBuilder.addInstanceMethod(
@@ -413,7 +432,6 @@
         "new-instance v1, Ljava/lang/Exception;",
         "invoke-direct {v1}, Ljava/lang/Exception;-><init>()V",
         "throw v1");
-
     // Add methods to F with an "invoke-super X.m()" instruction for X in {A, B, C, D, E, F}.
     for (String type : ImmutableList.of("A", "B", "C", "D", "E", "F")) {
       String code =
@@ -422,24 +440,23 @@
     }
 
     // Build app.
-    AndroidApp.Builder builder = AndroidApp.builder();
-    builder.addDexProgramData(smaliBuilder.compile(), Origin.unknown());
+    AndroidApp.Builder appBuilder = AndroidApp.builder();
+    appBuilder.addClassProgramData(jasminBuilder.buildClasses());
+    appBuilder.addDexProgramData(smaliBuilder.compile(), Origin.unknown());
 
     // Run test.
     runTestOnInput(
         main,
-        builder.build(),
+        appBuilder.build(),
         preservedClassNames::contains,
         String.format("-keep class %s { public static void main(...); }", main));
   }
 
-  private static String smaliCodeForPrinting(String message, int reg0, int reg1) {
+  private static String jasminCodeForPrinting(String message) {
     return buildCode(
-        String.format("sget-object v%d, Ljava/lang/System;->out:Ljava/io/PrintStream;", reg0),
-        String.format("const-string v1, \"%s\"", message),
-        String.format(
-            "invoke-virtual {v%d, v%d}, Ljava/io/PrintStream;->println(Ljava/lang/String;)V",
-            reg0, reg1));
+        "getstatic java/lang/System/out Ljava/io/PrintStream;",
+        String.format("ldc \"%s\"", message),
+        "invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V");
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/jasmin/JasminBuilder.java b/src/test/java/com/android/tools/r8/jasmin/JasminBuilder.java
index ba04454..82381dd 100644
--- a/src/test/java/com/android/tools/r8/jasmin/JasminBuilder.java
+++ b/src/test/java/com/android/tools/r8/jasmin/JasminBuilder.java
@@ -131,6 +131,10 @@
       return addMethod("public final", name, argumentTypes, returnType, lines);
     }
 
+    public MethodSignature addVirtualMethod(String name, String returnType, String... lines) {
+      return addVirtualMethod(name, ImmutableList.of(), returnType, lines);
+    }
+
     public MethodSignature addVirtualMethod(
         String name,
         List<String> argumentTypes,
diff --git a/src/test/java/com/android/tools/r8/naming/NamingTestBase.java b/src/test/java/com/android/tools/r8/naming/NamingTestBase.java
index 6d16184..5cc07a4 100644
--- a/src/test/java/com/android/tools/r8/naming/NamingTestBase.java
+++ b/src/test/java/com/android/tools/r8/naming/NamingTestBase.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.GraphLense;
@@ -44,7 +45,7 @@
 
   private DexApplication program;
   DexItemFactory dexItemFactory;
-  private AppInfoWithSubtyping appInfo;
+  private AppView<AppInfoWithSubtyping> appView;
 
   NamingTestBase(
       String test,
@@ -61,7 +62,7 @@
   public void readApp() throws IOException, ExecutionException {
     program = ToolHelper.buildApplication(ImmutableList.of(appFileName));
     dexItemFactory = program.dexItemFactory;
-    appInfo = new AppInfoWithSubtyping(program);
+    appView = new AppView<>(new AppInfoWithSubtyping(program), GraphLense.getIdentityLense());
   }
 
   NamingLens runMinifier(List<Path> configPaths)
@@ -73,12 +74,12 @@
 
     ExecutorService executor = ThreadUtils.getExecutorService(1);
 
+    AppInfoWithSubtyping appInfo = appView.getAppInfo();
     RootSet rootSet = new RootSetBuilder(appInfo, program, configuration.getRules(), options)
         .run(executor);
 
     if (options.proguardConfiguration.isAccessModificationAllowed()) {
-      ClassAndMemberPublicizer.run(
-          executor, timing, program, appInfo, rootSet, GraphLense.getIdentityLense());
+      ClassAndMemberPublicizer.run(executor, timing, program, appView, rootSet);
       rootSet =
           new RootSetBuilder(appInfo, program, configuration.getRules(), options).run(executor);
     }