diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index a30d724..9ee8f98 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -25,6 +25,7 @@
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.GraphLense;
+import com.android.tools.r8.graph.analysis.InitializedClassesInInstanceMethodsAnalysis;
 import com.android.tools.r8.ir.analysis.proto.GeneratedExtensionRegistryShrinker;
 import com.android.tools.r8.ir.conversion.IRConverter;
 import com.android.tools.r8.ir.desugar.R8NestBasedAccessDesugaring;
@@ -317,6 +318,10 @@
 
         Enqueuer enqueuer = new Enqueuer(appView, options, null, compatibility);
 
+        if (appView.options().enableInitializedClassesInInstanceMethodsAnalysis) {
+          enqueuer.registerAnalysis(new InitializedClassesInInstanceMethodsAnalysis(appView));
+        }
+
         AppView<AppInfoWithLiveness> appViewWithLiveness =
             appView.setAppInfo(
                 enqueuer.traceApplication(
diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
index ddfc2ed..7163e4e 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.graph;
 
 import com.android.tools.r8.OptionalBool;
+import com.android.tools.r8.graph.analysis.InitializedClassesInInstanceMethodsAnalysis.InitializedClassesInInstanceMethods;
 import com.android.tools.r8.ir.analysis.proto.GeneratedExtensionRegistryShrinker;
 import com.android.tools.r8.ir.analysis.proto.ProtoShrinker;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
@@ -38,6 +39,7 @@
 
   // Optimization results.
   private Predicate<DexType> classesEscapingIntoLibrary = Predicates.alwaysTrue();
+  private InitializedClassesInInstanceMethods initializedClassesInInstanceMethods;
   private Set<DexMethod> unneededVisibilityBridgeMethods = ImmutableSet.of();
   private VerticallyMergedClasses verticallyMergedClasses;
 
@@ -177,6 +179,19 @@
     return false;
   }
 
+  public void setInitializedClassesInInstanceMethods(
+      InitializedClassesInInstanceMethods initializedClassesInInstanceMethods) {
+    this.initializedClassesInInstanceMethods = initializedClassesInInstanceMethods;
+  }
+
+  public <U> U withInitializedClassesInInstanceMethods(
+      Function<InitializedClassesInInstanceMethods, U> fn, U defaultValue) {
+    if (initializedClassesInInstanceMethods != null) {
+      return fn.apply(initializedClassesInInstanceMethods);
+    }
+    return defaultValue;
+  }
+
   public InternalOptions options() {
     return options;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/analysis/EnqueuerAnalysis.java b/src/main/java/com/android/tools/r8/graph/analysis/EnqueuerAnalysis.java
new file mode 100644
index 0000000..1a54866
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/analysis/EnqueuerAnalysis.java
@@ -0,0 +1,15 @@
+// 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.graph.analysis;
+
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.shaking.KeepReason;
+
+public interface EnqueuerAnalysis {
+
+  void processNewlyInstantiatedClass(DexProgramClass clazz, KeepReason reason);
+
+  void done();
+}
diff --git a/src/main/java/com/android/tools/r8/graph/analysis/InitializedClassesInInstanceMethodsAnalysis.java b/src/main/java/com/android/tools/r8/graph/analysis/InitializedClassesInInstanceMethodsAnalysis.java
new file mode 100644
index 0000000..eb7f627
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/analysis/InitializedClassesInInstanceMethodsAnalysis.java
@@ -0,0 +1,90 @@
+// 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.graph.analysis;
+
+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.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.shaking.KeepReason;
+import java.util.IdentityHashMap;
+import java.util.Map;
+
+public class InitializedClassesInInstanceMethodsAnalysis implements EnqueuerAnalysis {
+
+  // A simple structure that stores the result of the analysis.
+  public static class InitializedClassesInInstanceMethods {
+
+    private final AppView<? extends AppInfoWithSubtyping> appView;
+    private final Map<DexType, DexType> mapping;
+
+    private InitializedClassesInInstanceMethods(
+        AppView<? extends AppInfoWithSubtyping> appView, Map<DexType, DexType> mapping) {
+      this.appView = appView;
+      this.mapping = mapping;
+    }
+
+    public boolean isClassDefinitelyLoadedInInstanceMethodsOn(DexType subject, DexType context) {
+      // If `subject` is kept, then it is instantiated by reflection, which means that the analysis
+      // has not seen all allocation sites. In that case, we conservatively return false.
+      AppInfoWithSubtyping appInfo = appView.appInfo();
+      if (appInfo.hasLiveness() && appInfo.withLiveness().isPinned(subject)) {
+        return false;
+      }
+
+      // Check that `subject` is guaranteed to be initialized in all instance methods of `context`.
+      DexType guaranteedToBeInitializedInContext =
+          mapping.getOrDefault(context, appView.dexItemFactory().objectType);
+      if (!appInfo.isSubtype(guaranteedToBeInitializedInContext, subject)) {
+        return false;
+      }
+
+      // Also check that `subject` is not an interface, since interfaces are not initialized
+      // transitively.
+      DexClass clazz = appView.definitionFor(subject);
+      return clazz != null && !clazz.isInterface();
+    }
+  }
+
+  private final AppView<? extends AppInfoWithSubtyping> appView;
+
+  // If the mapping contains an entry `X -> Y`, then the type Y is guaranteed to be initialized in
+  // all instance methods of X.
+  private final Map<DexType, DexType> mapping = new IdentityHashMap<>();
+
+  public InitializedClassesInInstanceMethodsAnalysis(
+      AppView<? extends AppInfoWithSubtyping> appView) {
+    this.appView = appView;
+  }
+
+  @Override
+  public void processNewlyInstantiatedClass(DexProgramClass clazz, KeepReason reason) {
+    DexType key = clazz.type;
+    DexType objectType = appView.dexItemFactory().objectType;
+    if (!reason.isInstantiatedIn()) {
+      // Record that we don't know anything about the set of classes that are guaranteed to be
+      // initialized in the instance methods of `clazz`.
+      mapping.put(key, objectType);
+      return;
+    }
+
+    // Record that the enclosing class is guaranteed to be initialized at the allocation site.
+    AppInfoWithSubtyping appInfo = appView.appInfo();
+    DexType guaranteedToBeInitialized = reason.asInstantiatedIn().getMethod().holder;
+    DexType existingGuaranteedToBeInitialized =
+        mapping.getOrDefault(key, guaranteedToBeInitialized);
+    mapping.put(
+        key,
+        appInfo.computeLeastUpperBoundOfClasses(
+            guaranteedToBeInitialized, existingGuaranteedToBeInitialized));
+  }
+
+  @Override
+  public void done() {
+    appView.setInitializedClassesInInstanceMethods(
+        new InitializedClassesInInstanceMethods(appView, mapping));
+  }
+}
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 89adfc7..8477ed7 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
@@ -145,6 +145,17 @@
     if (target.getOptimizationInfo().triggersClassInitBeforeAnySideEffect()) {
       return true;
     }
+    if (!method.isStatic()) {
+      boolean targetIsGuaranteedToBeInitialized =
+          appView.withInitializedClassesInInstanceMethods(
+              analysis ->
+                  analysis.isClassDefinitelyLoadedInInstanceMethodsOn(
+                      target.method.holder, method.method.holder),
+              false);
+      if (targetIsGuaranteedToBeInitialized) {
+        return true;
+      }
+    }
     if (classInitializationAnalysis.isClassDefinitelyLoadedBeforeInstruction(
         target.method.holder, invoke)) {
       return true;
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 dc68e3c..b2c4439 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -49,6 +49,7 @@
 import com.android.tools.r8.graph.KeyedDexItem;
 import com.android.tools.r8.graph.PresortedComparable;
 import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
+import com.android.tools.r8.graph.analysis.EnqueuerAnalysis;
 import com.android.tools.r8.ir.code.ArrayPut;
 import com.android.tools.r8.ir.code.ConstantValueUtils;
 import com.android.tools.r8.ir.code.IRCode;
@@ -113,6 +114,7 @@
   private final boolean forceProguardCompatibility;
   private boolean tracingMainDex = false;
 
+  private Set<EnqueuerAnalysis> analyses = Sets.newIdentityHashSet();
   private final AppInfoWithSubtyping appInfo;
   private final AppView<? extends AppInfoWithSubtyping> appView;
   private final InternalOptions options;
@@ -305,6 +307,11 @@
     this.options = options;
   }
 
+  public Enqueuer registerAnalysis(EnqueuerAnalysis analysis) {
+    this.analyses.add(analysis);
+    return this;
+  }
+
   private Set<DexField> staticFieldsWrittenOnlyInEnclosingStaticInitializer() {
     Set<DexField> result = Sets.newIdentityHashSet();
     fieldAccessInfoCollection.forEach(
@@ -1165,6 +1172,9 @@
    * depending on the currently seen invokes and field reads.
    */
   private void processNewlyInstantiatedClass(DexClass clazz, KeepReason reason) {
+    if (!clazz.isProgramClass()) {
+      return;
+    }
     if (!instantiatedTypes.add(clazz.type, reason)) {
       return;
     }
@@ -1181,6 +1191,9 @@
     transitionFieldsForInstantiatedClass(clazz.type);
     // Add all dependent instance members to the workqueue.
     transitionDependentItemsForInstantiatedClass(clazz);
+    // Notify analyses.
+    analyses.forEach(
+        analysis -> analysis.processNewlyInstantiatedClass(clazz.asProgramClass(), reason));
   }
 
   /**
@@ -1373,10 +1386,7 @@
     enqueueRootItems(rootSet.getDependentItems(field));
   }
 
-  private void markInstantiated(DexType type, KeepReason keepReason) {
-    if (instantiatedTypes.contains(type)) {
-      return;
-    }
+  private void markInstantiated(DexType type, KeepReason reason) {
     DexClass clazz = appView.definitionFor(type);
     if (clazz == null) {
       reportMissingClass(type);
@@ -1385,7 +1395,7 @@
     if (Log.ENABLED) {
       Log.verbose(getClass(), "Register new instantiation of `%s`.", clazz);
     }
-    workList.add(Action.markInstantiated(clazz, keepReason));
+    workList.add(Action.markInstantiated(clazz, reason));
   }
 
   private void markLambdaInstantiated(DexType itf, DexEncodedMethod method) {
@@ -1678,6 +1688,7 @@
   // Returns the set of live types.
   public SortedSet<DexType> traceMainDex(
       RootSet rootSet, ExecutorService executorService, Timing timing) throws ExecutionException {
+    assert analyses.isEmpty();
     this.tracingMainDex = true;
     this.rootSet = rootSet;
     // Translate the result of root-set computation into enqueuer actions.
@@ -1702,6 +1713,7 @@
         .visit(appView.appInfo().classes(), this::markAllLibraryVirtualMethodsReachable);
     trace(executorService, timing);
     options.reporter.failIfPendingErrors();
+    analyses.forEach(EnqueuerAnalysis::done);
     return createAppInfo(appInfo);
   }
 
diff --git a/src/main/java/com/android/tools/r8/shaking/KeepReason.java b/src/main/java/com/android/tools/r8/shaking/KeepReason.java
index cfdb292..673326c 100644
--- a/src/main/java/com/android/tools/r8/shaking/KeepReason.java
+++ b/src/main/java/com/android/tools/r8/shaking/KeepReason.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.DexDefinition;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexItem;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import java.util.Collection;
@@ -94,6 +95,14 @@
     return false;
   }
 
+  public boolean isInstantiatedIn() {
+    return false;
+  }
+
+  public InstatiatedIn asInstantiatedIn() {
+    return null;
+  }
+
   public ProguardKeepRuleBase getProguardKeepRule() {
     return null;
   }
@@ -200,19 +209,33 @@
 
     abstract String getKind();
 
+    public DexMethod getMethod() {
+      return method.method;
+    }
+
     @Override
     public GraphNode getSourceNode(Enqueuer enqueuer) {
       return enqueuer.getMethodGraphNode(method.method);
     }
   }
 
-  private static class InstatiatedIn extends BasedOnOtherMethod {
+  public static class InstatiatedIn extends BasedOnOtherMethod {
 
     private InstatiatedIn(DexEncodedMethod method) {
       super(method);
     }
 
     @Override
+    public boolean isInstantiatedIn() {
+      return true;
+    }
+
+    @Override
+    public InstatiatedIn asInstantiatedIn() {
+      return this;
+    }
+
+    @Override
     public EdgeKind edgeKind() {
       return EdgeKind.InstantiatedIn;
     }
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index da65ece..e55b769 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -217,6 +217,7 @@
   public boolean enableStringSwitchConversion = false;
   public boolean enableEnumValueOptimization = true;
   public final OutlineOptions outline = new OutlineOptions();
+  public boolean enableInitializedClassesInInstanceMethodsAnalysis = true;
   public boolean enableRedundantFieldLoadElimination = true;
   public boolean enableValuePropagation = true;
   public boolean enableUninstantiatedTypeOptimization = true;
diff --git a/src/test/java/com/android/tools/r8/graph/initializedclasses/InitializedClassesInInstanceMethodsTest.java b/src/test/java/com/android/tools/r8/graph/initializedclasses/InitializedClassesInInstanceMethodsTest.java
new file mode 100644
index 0000000..269befa
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/graph/initializedclasses/InitializedClassesInInstanceMethodsTest.java
@@ -0,0 +1,158 @@
+// 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.graph.initializedclasses;
+
+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.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.utils.BooleanUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import java.util.List;
+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 InitializedClassesInInstanceMethodsTest extends TestBase {
+
+  private final boolean enableInitializedClassesInInstanceMethodsAnalysis;
+  private final TestParameters parameters;
+
+  @Parameters(name = "{1}, enabled: {0}")
+  public static List<Object[]> data() {
+    return buildParameters(BooleanUtils.values(), getTestParameters().withAllRuntimes().build());
+  }
+
+  public InitializedClassesInInstanceMethodsTest(
+      boolean enableInitializedClassesInInstanceMethodsAnalysis, TestParameters parameters) {
+    this.enableInitializedClassesInInstanceMethodsAnalysis =
+        enableInitializedClassesInInstanceMethodsAnalysis;
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(InitializedClassesInInstanceMethodsTest.class)
+        .addKeepMainRule(TestClass.class)
+        .addKeepRules("-allowaccessmodification")
+        .addOptionsModification(
+            options -> {
+              options.enableInitializedClassesInInstanceMethodsAnalysis =
+                  enableInitializedClassesInInstanceMethodsAnalysis;
+
+              // TODO(b/137174854): No need to explicitly turn this on when it gets enabled by
+              //  default.
+              assert !options.enableInliningOfInvokesWithNullableReceivers;
+              options.enableInliningOfInvokesWithNullableReceivers = true;
+            })
+        .enableClassInliningAnnotations()
+        .enableInliningAnnotations()
+        .setMinApi(parameters.getRuntime())
+        .compile()
+        .inspect(this::verifyOutput)
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutputLines("Hello world!");
+  }
+
+  private void verifyOutput(CodeInspector inspector) {
+    ClassSubject outerClassSubject = inspector.clazz(Outer.class);
+    assertThat(outerClassSubject, isPresent());
+
+    // In any case, Outer.hello(), Outer.world(), and Outer.exclamationMark() should be inlined into
+    // the accessibility bridges.
+    assertThat(outerClassSubject.uniqueMethodWithName("hello"), not(isPresent()));
+    assertThat(outerClassSubject.uniqueMethodWithName("world"), not(isPresent()));
+    assertThat(outerClassSubject.uniqueMethodWithName("exclamationMark"), not(isPresent()));
+
+    int numberOfExpectedAccessibilityBridges =
+        enableInitializedClassesInInstanceMethodsAnalysis ? 0 : 3;
+    assertEquals(
+        numberOfExpectedAccessibilityBridges,
+        outerClassSubject
+            .allMethods(method -> method.getOriginalName().contains("access$"))
+            .size());
+
+    ClassSubject aClassSubject = inspector.clazz(Outer.A.class);
+    assertThat(aClassSubject, isPresent());
+    assertThat(aClassSubject.uniqueMethodWithName("hello"), isPresent());
+
+    ClassSubject bClassSubject = inspector.clazz(Outer.B.class);
+    assertThat(bClassSubject, isPresent());
+    assertThat(bClassSubject.uniqueMethodWithName("world"), isPresent());
+
+    ClassSubject cClassSubject = inspector.clazz(C.class);
+    assertThat(cClassSubject, isPresent());
+    assertThat(cClassSubject.uniqueMethodWithName("exclamationMark"), isPresent());
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      new Outer().test();
+    }
+  }
+
+  static class Outer {
+
+    static {
+      // To ensure that we consider the class initialization of TestClass as having side effects.
+      System.out.print("");
+    }
+
+    public void test() {
+      new A().hello();
+      new B().world(this);
+      new C().exclamationMark(this);
+    }
+
+    private void hello() {
+      System.out.print("Hello");
+    }
+
+    private void world() {
+      System.out.print(" world");
+    }
+
+    private void exclamationMark() {
+      System.out.println("!");
+    }
+
+    @NeverClassInline
+    class A {
+
+      @NeverInline
+      void hello() {
+        Outer.this.hello();
+      }
+    }
+
+    @NeverClassInline
+    static class B {
+
+      @NeverInline
+      void world(Outer outer) {
+        outer.world();
+      }
+    }
+  }
+
+  @NeverClassInline
+  static class C {
+
+    @NeverInline
+    void exclamationMark(Outer outer) {
+      outer.exclamationMark();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/kotlin/R8KotlinAccessorTest.java b/src/test/java/com/android/tools/r8/kotlin/R8KotlinAccessorTest.java
index 27cc0b8..f0a8a84 100644
--- a/src/test/java/com/android/tools/r8/kotlin/R8KotlinAccessorTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/R8KotlinAccessorTest.java
@@ -311,9 +311,10 @@
           MemberNaming.MethodSignature getter = testedClass.getGetterForProperty(propertyName);
           checkMethodIsAbsent(companionClass, getter);
 
+          // The accessor is also inlined.
           MemberNaming.MethodSignature getterAccessor =
               testedClass.getGetterAccessorForProperty(propertyName, AccessorKind.FROM_COMPANION);
-          checkMethodIsKept(outerClass, getterAccessor);
+          checkMethodIsRemoved(outerClass, getterAccessor);
         });
   }