Refactor code in inliner.

- Code refactoring to dissociate CHA attempts and devirtualization
attemps
- Only devirtualize (currently invoke-interface -> invoke-virtual) when
the target can be statically resolved. The benefits for CHA and inline
caches are less clear.

Test: test.py
Change-Id: I2d41cef8143ab1ce66b2c2e149674eaf228d15a3

3 files changed, 160 insertions, 145 deletions

diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 312b8ed748..a86fffde00 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -342,7 +342,7 @@ static inline ObjPtr<mirror::Class> GetMonomorphicType(
   return classes.GetReference(0)->AsClass();
 }
 
-ArtMethod* HInliner::TryCHADevirtualization(ArtMethod* resolved_method) {
+ArtMethod* HInliner::FindMethodFromCHA(ArtMethod* resolved_method) {
   if (!resolved_method->HasSingleImplementation()) {
     return nullptr;
   }
@@ -432,27 +432,6 @@ static bool AlwaysThrows(const CompilerOptions& compiler_options, ArtMethod* met
   return throw_seen;
 }
 
-ArtMethod* HInliner::FindActualCallTarget(HInvoke* invoke_instruction, bool* cha_devirtualize) {
-  ArtMethod* actual_method = nullptr;
-  if (invoke_instruction->IsInvokeStaticOrDirect()) {
-    actual_method = invoke_instruction->GetResolvedMethod();
-  } else {
-    // Check if we can statically find the method.
-    actual_method = FindVirtualOrInterfaceTarget(invoke_instruction);
-  }
-
-  if (actual_method == nullptr) {
-    ArtMethod* method = TryCHADevirtualization(invoke_instruction->GetResolvedMethod());
-    if (method != nullptr) {
-      *cha_devirtualize = true;
-      actual_method = method;
-      LOG_NOTE() << "Try CHA-based inlining of " << actual_method->PrettyMethod();
-    }
-  }
-
-  return actual_method;
-}
-
 bool HInliner::TryInline(HInvoke* invoke_instruction) {
   MaybeRecordStat(stats_, MethodCompilationStat::kTryInline);
 
@@ -480,40 +459,66 @@ bool HInliner::TryInline(HInvoke* invoke_instruction) {
     return false;
   }
 
-  bool cha_devirtualize = false;
-  ArtMethod* actual_method = FindActualCallTarget(invoke_instruction, &cha_devirtualize);
-
-  // If we didn't find a method, see if we can inline from the inline caches.
-  if (actual_method == nullptr) {
-    DCHECK(!invoke_instruction->IsInvokeStaticOrDirect());
-    return TryInlineFromInlineCache(invoke_instruction);
-  }
-
-  // Single target.
-  bool result = TryInlineAndReplace(invoke_instruction,
-                                    actual_method,
-                                    ReferenceTypeInfo::CreateInvalid(),
-                                    /* do_rtp= */ true,
-                                    cha_devirtualize);
-  if (result) {
-    // Successfully inlined.
-    if (!invoke_instruction->IsInvokeStaticOrDirect()) {
-      if (cha_devirtualize) {
-        // Add dependency due to devirtualization. We've assumed resolved_method
-        // has single implementation.
-        outermost_graph_->AddCHASingleImplementationDependency(resolved_method);
-        MaybeRecordStat(stats_, MethodCompilationStat::kCHAInline);
+  ArtMethod* actual_method = invoke_instruction->IsInvokeStaticOrDirect()
+      ? invoke_instruction->GetResolvedMethod()
+      : FindVirtualOrInterfaceTarget(invoke_instruction);
+
+  if (actual_method != nullptr) {
+    // Single target.
+    bool result = TryInlineAndReplace(invoke_instruction,
+                                      actual_method,
+                                      ReferenceTypeInfo::CreateInvalid(),
+                                      /* do_rtp= */ true);
+    if (result) {
+      MaybeRecordStat(stats_, MethodCompilationStat::kInlinedInvokeVirtualOrInterface);
+    } else {
+      HInvoke* invoke_to_analyze = nullptr;
+      if (TryDevirtualize(invoke_instruction, actual_method, &invoke_to_analyze)) {
+        // Consider devirtualization as inlining.
+        result = true;
+        MaybeRecordStat(stats_, MethodCompilationStat::kDevirtualized);
       } else {
-        MaybeRecordStat(stats_, MethodCompilationStat::kInlinedInvokeVirtualOrInterface);
+        invoke_to_analyze = invoke_instruction;
+      }
+      // Set always throws property for non-inlined method call with single
+      // target.
+      if (AlwaysThrows(codegen_->GetCompilerOptions(), actual_method)) {
+        invoke_to_analyze->SetAlwaysThrows(true);
       }
     }
-  } else if (!cha_devirtualize && AlwaysThrows(codegen_->GetCompilerOptions(), actual_method)) {
-    // Set always throws property for non-inlined method call with single target
-    // (unless it was obtained through CHA, because that would imply we have
-    // to add the CHA dependency, which seems not worth it).
-    invoke_instruction->SetAlwaysThrows(true);
+    return result;
   }
-  return result;
+
+  DCHECK(!invoke_instruction->IsInvokeStaticOrDirect());
+
+  if (TryInlineFromCHA(invoke_instruction)) {
+    return true;
+  }
+  return TryInlineFromInlineCache(invoke_instruction);
+}
+
+bool HInliner::TryInlineFromCHA(HInvoke* invoke_instruction) {
+  ArtMethod* method = FindMethodFromCHA(invoke_instruction->GetResolvedMethod());
+  if (method == nullptr) {
+    return false;
+  }
+  LOG_NOTE() << "Try CHA-based inlining of " << method->PrettyMethod();
+
+  uint32_t dex_pc = invoke_instruction->GetDexPc();
+  HInstruction* cursor = invoke_instruction->GetPrevious();
+  HBasicBlock* bb_cursor = invoke_instruction->GetBlock();
+  if (!TryInlineAndReplace(invoke_instruction,
+                           method,
+                           ReferenceTypeInfo::CreateInvalid(),
+                           /* do_rtp= */ true)) {
+    return false;
+  }
+  AddCHAGuard(invoke_instruction, dex_pc, cursor, bb_cursor);
+  // Add dependency due to devirtualization. We've assumed resolved_method
+  // has single implementation.
+  outermost_graph_->AddCHASingleImplementationDependency(method);
+  MaybeRecordStat(stats_, MethodCompilationStat::kCHAInline);
+  return true;
 }
 
 bool HInliner::UseOnlyPolymorphicInliningWithNoDeopt() {
@@ -803,8 +808,7 @@ bool HInliner::TryInlineMonomorphicCall(
   if (!TryInlineAndReplace(invoke_instruction,
                            resolved_method,
                            ReferenceTypeInfo::Create(monomorphic_type, /* is_exact= */ true),
-                           /* do_rtp= */ false,
-                           /* cha_devirtualize= */ false)) {
+                           /* do_rtp= */ false)) {
     return false;
   }
 
@@ -1221,91 +1225,97 @@ bool HInliner::TryInlinePolymorphicCallToSameTarget(
   return true;
 }
 
+void HInliner::MaybeRunReferenceTypePropagation(HInstruction* replacement,
+                                                HInvoke* invoke_instruction) {
+  if (ReturnTypeMoreSpecific(replacement, invoke_instruction)) {
+    // Actual return value has a more specific type than the method's declared
+    // return type. Run RTP again on the outer graph to propagate it.
+    ReferenceTypePropagation(graph_,
+                             outer_compilation_unit_.GetClassLoader(),
+                             outer_compilation_unit_.GetDexCache(),
+                             /* is_first_run= */ false).Run();
+  }
+}
+
+bool HInliner::TryDevirtualize(HInvoke* invoke_instruction,
+                               ArtMethod* method,
+                               HInvoke** replacement) {
+  DCHECK(!method->IsProxyMethod());
+  DCHECK(invoke_instruction != *replacement);
+  if (!invoke_instruction->IsInvokeInterface()) {
+    // TODO: Consider sharpening an invoke virtual once it is not dependent on the
+    // compiler driver.
+    return false;
+  }
+  // Devirtualization by exact type uses a method in the vtable, so we should
+  // not see a default non-copied method.
+  DCHECK(!method->IsDefault() || method->IsCopied());
+  // Turn an invoke-interface into an invoke-virtual. An invoke-virtual is always
+  // better than an invoke-interface because:
+  // 1) In the best case, the interface call has one more indirection (to fetch the IMT).
+  // 2) We will not go to the conflict trampoline with an invoke-virtual.
+  // TODO: Consider sharpening once it is not dependent on the compiler driver.
+
+  if (kIsDebugBuild && method->IsDefaultConflicting()) {
+    ReferenceTypeInfo receiver_type = invoke_instruction->InputAt(0)->GetReferenceTypeInfo();
+    // Devirtualization by exact type uses a method in the vtable,
+    // so it's OK to change this invoke into a HInvokeVirtual.
+    ObjPtr<mirror::Class> receiver_class = receiver_type.GetTypeHandle().Get();
+    CHECK(!receiver_class->IsInterface());
+    PointerSize pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize();
+    CHECK(method == receiver_class->GetVTableEntry(method->GetMethodIndex(), pointer_size));
+  }
+
+  uint32_t dex_method_index = FindMethodIndexIn(
+      method,
+      *invoke_instruction->GetMethodReference().dex_file,
+      invoke_instruction->GetMethodReference().index);
+  if (dex_method_index == dex::kDexNoIndex) {
+    return false;
+  }
+  HInvokeVirtual* new_invoke = new (graph_->GetAllocator()) HInvokeVirtual(
+      graph_->GetAllocator(),
+      invoke_instruction->GetNumberOfArguments(),
+      invoke_instruction->GetType(),
+      invoke_instruction->GetDexPc(),
+      MethodReference(invoke_instruction->GetMethodReference().dex_file, dex_method_index),
+      method,
+      MethodReference(method->GetDexFile(), method->GetDexMethodIndex()),
+      method->GetMethodIndex());
+  HInputsRef inputs = invoke_instruction->GetInputs();
+  for (size_t index = 0; index != inputs.size(); ++index) {
+    new_invoke->SetArgumentAt(index, inputs[index]);
+  }
+  invoke_instruction->GetBlock()->InsertInstructionBefore(new_invoke, invoke_instruction);
+  new_invoke->CopyEnvironmentFrom(invoke_instruction->GetEnvironment());
+  if (invoke_instruction->GetType() == DataType::Type::kReference) {
+    new_invoke->SetReferenceTypeInfo(invoke_instruction->GetReferenceTypeInfo());
+  }
+  *replacement = new_invoke;
+
+  MaybeReplaceAndRemove(*replacement, invoke_instruction);
+  // No need to call MaybeRunReferenceTypePropagation, as we know the return type
+  // cannot be more specific.
+  DCHECK(!ReturnTypeMoreSpecific(*replacement, invoke_instruction));
+  return true;
+}
+
+
 bool HInliner::TryInlineAndReplace(HInvoke* invoke_instruction,
                                    ArtMethod* method,
                                    ReferenceTypeInfo receiver_type,
-                                   bool do_rtp,
-                                   bool cha_devirtualize) {
+                                   bool do_rtp) {
   DCHECK(!invoke_instruction->IsIntrinsic());
   HInstruction* return_replacement = nullptr;
-  uint32_t dex_pc = invoke_instruction->GetDexPc();
-  HInstruction* cursor = invoke_instruction->GetPrevious();
-  HBasicBlock* bb_cursor = invoke_instruction->GetBlock();
 
   if (!TryBuildAndInline(invoke_instruction, method, receiver_type, &return_replacement)) {
-    if (invoke_instruction->IsInvokeInterface()) {
-      DCHECK(!method->IsProxyMethod());
-      // Turn an invoke-interface into an invoke-virtual. An invoke-virtual is always
-      // better than an invoke-interface because:
-      // 1) In the best case, the interface call has one more indirection (to fetch the IMT).
-      // 2) We will not go to the conflict trampoline with an invoke-virtual.
-      // TODO: Consider sharpening once it is not dependent on the compiler driver.
-
-      if (method->IsDefault() && !method->IsCopied()) {
-        // Changing to invoke-virtual cannot be done on an original default method
-        // since it's not in any vtable. Devirtualization by exact type/inline-cache
-        // always uses a method in the iftable which is never an original default
-        // method.
-        // On the other hand, inlining an original default method by CHA is fine.
-        DCHECK(cha_devirtualize);
-        return false;
-      }
-
-      if (kIsDebugBuild && method->IsDefaultConflicting()) {
-        CHECK(!cha_devirtualize) << "CHA cannot have a default conflict method as target";
-        // Devirtualization by exact type/inline-cache always uses a method in the vtable,
-        // so it's OK to change this invoke into a HInvokeVirtual.
-        ObjPtr<mirror::Class> receiver_class = receiver_type.GetTypeHandle().Get();
-        CHECK(!receiver_class->IsInterface());
-        PointerSize pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize();
-        CHECK(method == receiver_class->GetVTableEntry(method->GetMethodIndex(), pointer_size));
-      }
-
-      uint32_t dex_method_index = FindMethodIndexIn(
-          method,
-          *invoke_instruction->GetMethodReference().dex_file,
-          invoke_instruction->GetMethodReference().index);
-      if (dex_method_index == dex::kDexNoIndex) {
-        return false;
-      }
-      HInvokeVirtual* new_invoke = new (graph_->GetAllocator()) HInvokeVirtual(
-          graph_->GetAllocator(),
-          invoke_instruction->GetNumberOfArguments(),
-          invoke_instruction->GetType(),
-          invoke_instruction->GetDexPc(),
-          MethodReference(invoke_instruction->GetMethodReference().dex_file, dex_method_index),
-          method,
-          MethodReference(method->GetDexFile(), method->GetDexMethodIndex()),
-          method->GetMethodIndex());
-      HInputsRef inputs = invoke_instruction->GetInputs();
-      for (size_t index = 0; index != inputs.size(); ++index) {
-        new_invoke->SetArgumentAt(index, inputs[index]);
-      }
-      invoke_instruction->GetBlock()->InsertInstructionBefore(new_invoke, invoke_instruction);
-      new_invoke->CopyEnvironmentFrom(invoke_instruction->GetEnvironment());
-      if (invoke_instruction->GetType() == DataType::Type::kReference) {
-        new_invoke->SetReferenceTypeInfo(invoke_instruction->GetReferenceTypeInfo());
-      }
-      return_replacement = new_invoke;
-    } else {
-      // TODO: Consider sharpening an invoke virtual once it is not dependent on the
-      // compiler driver.
-      return false;
-    }
+    return false;
   }
 
-  if (cha_devirtualize) {
-    AddCHAGuard(invoke_instruction, dex_pc, cursor, bb_cursor);
-  }
   MaybeReplaceAndRemove(return_replacement, invoke_instruction);
   FixUpReturnReferenceType(method, return_replacement);
-  if (do_rtp && ReturnTypeMoreSpecific(invoke_instruction, return_replacement)) {
-    // Actual return value has a more specific type than the method's declared
-    // return type. Run RTP again on the outer graph to propagate it.
-    ReferenceTypePropagation(graph_,
-                             outer_compilation_unit_.GetClassLoader(),
-                             outer_compilation_unit_.GetDexCache(),
-                             /* is_first_run= */ false).Run();
+  if (do_rtp) {
+    MaybeRunReferenceTypePropagation(return_replacement, invoke_instruction);
   }
   return true;
 }
@@ -2131,8 +2141,8 @@ bool HInliner::ArgumentTypesMoreSpecific(HInvoke* invoke_instruction, ArtMethod*
   return false;
 }
 
-bool HInliner::ReturnTypeMoreSpecific(HInvoke* invoke_instruction,
-                                      HInstruction* return_replacement) {
+bool HInliner::ReturnTypeMoreSpecific(HInstruction* return_replacement,
+                                      HInvoke* invoke_instruction) {
   // Check the integrity of reference types and run another type propagation if needed.
   if (return_replacement != nullptr) {
     if (return_replacement->GetType() == DataType::Type::kReference) {
diff --git a/compiler/optimizing/inliner.h b/compiler/optimizing/inliner.h
index 241c63bcc2..e98a66b314 100644
--- a/compiler/optimizing/inliner.h
+++ b/compiler/optimizing/inliner.h
@@ -72,24 +72,13 @@ class HInliner : public HOptimization {
 
   bool TryInline(HInvoke* invoke_instruction);
 
-  // Attempt to resolve the target of the invoke instruction to an acutal call
-  // target.
-  //
-  // Returns the target directly in the case of static or direct invokes.
-  // Otherwise, uses CHA devirtualization or other methods to try to find the
-  // call target.
-  ArtMethod* FindActualCallTarget(HInvoke* invoke_instruction, bool* cha_devirtualize)
-    REQUIRES_SHARED(Locks::mutator_lock_);
-
   // Try to inline `resolved_method` in place of `invoke_instruction`. `do_rtp` is whether
   // reference type propagation can run after the inlining. If the inlining is successful, this
-  // method will replace and remove the `invoke_instruction`. If `cha_devirtualize` is true,
-  // a CHA guard needs to be added for the inlining.
+  // method will replace and remove the `invoke_instruction`.
   bool TryInlineAndReplace(HInvoke* invoke_instruction,
                            ArtMethod* resolved_method,
                            ReferenceTypeInfo receiver_type,
-                           bool do_rtp,
-                           bool cha_devirtualize)
+                           bool do_rtp)
     REQUIRES_SHARED(Locks::mutator_lock_);
 
   bool TryBuildAndInline(HInvoke* invoke_instruction,
@@ -170,6 +159,17 @@ class HInliner : public HOptimization {
   bool TryInlineFromInlineCache(HInvoke* invoke_instruction)
     REQUIRES_SHARED(Locks::mutator_lock_);
 
+  // Try inlining the invoke instruction using CHA.
+  bool TryInlineFromCHA(HInvoke* invoke_instruction)
+    REQUIRES_SHARED(Locks::mutator_lock_);
+
+  // When we fail inlining `invoke_instruction`, we will try to devirtualize the
+  // call.
+  bool TryDevirtualize(HInvoke* invoke_instruction,
+                       ArtMethod* method,
+                       HInvoke** replacement)
+    REQUIRES_SHARED(Locks::mutator_lock_);
+
   // Try getting the inline cache from JIT code cache.
   // Return true if the inline cache was successfully allocated and the
   // invoke info was found in the profile info.
@@ -215,7 +215,7 @@ class HInliner : public HOptimization {
   // Try CHA-based devirtualization to change virtual method calls into
   // direct calls.
   // Returns the actual method that resolved_method can be devirtualized to.
-  ArtMethod* TryCHADevirtualization(ArtMethod* resolved_method)
+  ArtMethod* FindMethodFromCHA(ArtMethod* resolved_method)
     REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Add a CHA guard for a CHA-based devirtualized call. A CHA guard checks a
@@ -230,13 +230,17 @@ class HInliner : public HOptimization {
                                            uint32_t dex_pc) const
     REQUIRES_SHARED(Locks::mutator_lock_);
 
+  void MaybeRunReferenceTypePropagation(HInstruction* replacement,
+                                        HInvoke* invoke_instruction)
+    REQUIRES_SHARED(Locks::mutator_lock_);
+
   void FixUpReturnReferenceType(ArtMethod* resolved_method, HInstruction* return_replacement)
     REQUIRES_SHARED(Locks::mutator_lock_);
 
   bool ArgumentTypesMoreSpecific(HInvoke* invoke_instruction, ArtMethod* resolved_method)
     REQUIRES_SHARED(Locks::mutator_lock_);
 
-  bool ReturnTypeMoreSpecific(HInvoke* invoke_instruction, HInstruction* return_replacement)
+  bool ReturnTypeMoreSpecific(HInstruction* return_replacement, HInvoke* invoke_instruction)
     REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Add a type guard on the given `receiver`. This will add to the graph:
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index a2f71cfdf3..3d0815f1eb 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -116,6 +116,7 @@ enum class MethodCompilationStat {
   kPartialAllocationMoved,
   kPredicatedLoadAdded,
   kPredicatedStoreAdded,
+  kDevirtualized,
   kLastStat
 };
 std::ostream& operator<<(std::ostream& os, MethodCompilationStat rhs);