Better support ICs on virtual calls

Due to the way we implement profiles InlineCaches are only valid on
methods with implementations. Unfortunately due to the rather slow way
we update boot profile definitions code refactorings can lead to
inline-caches being lost. This change makes profman more resilient to
this error by searching up the superclass resolutions to try to find a
method the inline-caches can be attached to. This should ensure that
boot-profile definitions fall out of date more slowly.

Test: ./test.py --host
Bug: 168941430

Change-Id: I5f6096500fa6f17e285b5a7bab21ad8216221966
diff --git a/libdexfile/dex/dex_file.cc b/libdexfile/dex/dex_file.cc
index 247032f..dc5f27e 100644
--- a/libdexfile/dex/dex_file.cc
+++ b/libdexfile/dex/dex_file.cc
@@ -286,6 +286,13 @@
   const dex::TypeIndex class_idx = GetIndexForTypeId(declaring_klass);
   const dex::StringIndex name_idx = GetIndexForStringId(name);
   const dex::ProtoIndex proto_idx = GetIndexForProtoId(signature);
+  return FindMethodIdByIndex(class_idx, name_idx, proto_idx);
+}
+
+const MethodId* DexFile::FindMethodIdByIndex(dex::TypeIndex class_idx,
+                                             dex::StringIndex name_idx,
+                                             dex::ProtoIndex proto_idx) const {
+  // Binary search MethodIds knowing that they are sorted by class_idx, name_idx then proto_idx
   int32_t lo = 0;
   int32_t hi = NumMethodIds() - 1;
   while (hi >= lo) {
@@ -306,6 +313,9 @@
         } else if (proto_idx < method.proto_idx_) {
           hi = mid - 1;
         } else {
+          DCHECK_EQ(class_idx, method.class_idx_);
+          DCHECK_EQ(proto_idx, method.proto_idx_);
+          DCHECK_EQ(name_idx, method.name_idx_);
           return &method;
         }
       }
diff --git a/libdexfile/dex/dex_file.h b/libdexfile/dex/dex_file.h
index e0406b9..5363b00 100644
--- a/libdexfile/dex/dex_file.h
+++ b/libdexfile/dex/dex_file.h
@@ -381,6 +381,10 @@
                                     const dex::StringId& name,
                                     const dex::ProtoId& signature) const;
 
+  const dex::MethodId* FindMethodIdByIndex(dex::TypeIndex declaring_klass,
+                                           dex::StringIndex name,
+                                           dex::ProtoIndex signature) const;
+
   // Returns the declaring class descriptor string of a method id.
   const char* GetMethodDeclaringClassDescriptor(const dex::MethodId& method_id) const;
 
diff --git a/profman/profile_assistant_test.cc b/profman/profile_assistant_test.cc
index 0f85e10..d01d4fb 100644
--- a/profman/profile_assistant_test.cc
+++ b/profman/profile_assistant_test.cc
@@ -15,6 +15,8 @@
  */
 
 #include <gtest/gtest.h>
+#include <sstream>
+#include <string>
 
 #include "android-base/file.h"
 #include "android-base/strings.h"
@@ -24,6 +26,7 @@
 #include "base/utils.h"
 #include "common_runtime_test.h"
 #include "dex/descriptors_names.h"
+#include "dex/dex_file_structs.h"
 #include "dex/dex_instruction-inl.h"
 #include "dex/dex_instruction_iterator.h"
 #include "dex/type_reference.h"
@@ -1514,6 +1517,99 @@
   CheckProfileInfo(profile1, info1);
 }
 
+TEST_F(ProfileAssistantTest, TestProfileCreateWithSubtype) {
+  // Create the profile content.
+  std::vector<std::string> profile_methods = {
+      "HLTestInlineSubtype;->inlineMonomorphic(LSuper;)I+]LSuper;LSubA;",
+  };
+  std::string input_file_contents;
+  for (std::string& m : profile_methods) {
+    input_file_contents += m + std::string("\n");
+  }
+
+  // Create the profile and save it to disk.
+  ScratchFile profile_file;
+  std::string dex_filename = GetTestDexFileName("ProfileTestMultiDex");
+  ASSERT_TRUE(CreateProfile(input_file_contents, profile_file.GetFilename(), dex_filename));
+
+  // Load the profile from disk.
+  ProfileCompilationInfo info;
+  profile_file.GetFile()->ResetOffset();
+  ASSERT_TRUE(info.Load(GetFd(profile_file)));
+  LOG(ERROR) << profile_file.GetFilename();
+
+  // Load the dex files and verify that the profile contains the expected
+  // methods info.
+  ScopedObjectAccess soa(Thread::Current());
+  jobject class_loader = LoadDex("ProfileTestMultiDex");
+  ASSERT_NE(class_loader, nullptr);
+
+  // NB This is the supertype of the declared line!
+  ArtMethod* inline_monomorphic_super =
+      GetVirtualMethod(class_loader, "LTestInline;", "inlineMonomorphic");
+  const DexFile* dex_file = inline_monomorphic_super->GetDexFile();
+
+  // Verify that the inline cache is present in the superclass
+  ProfileCompilationInfo::MethodHotness hotness_super = info.GetMethodHotness(
+      MethodReference(dex_file, inline_monomorphic_super->GetDexMethodIndex()));
+  ASSERT_TRUE(hotness_super.IsHot());
+  const ProfileCompilationInfo::InlineCacheMap* inline_caches = hotness_super.GetInlineCacheMap();
+  ASSERT_EQ(inline_caches->size(), 1u);
+  const ProfileCompilationInfo::DexPcData& dex_pc_data = inline_caches->begin()->second;
+  dex::TypeIndex target_type_index(dex_file->GetIndexForTypeId(*dex_file->FindTypeId("LSubA;")));
+  ASSERT_EQ(1u, dex_pc_data.classes.size());
+  ASSERT_EQ(target_type_index, dex_pc_data.classes.begin()->type_index);
+
+  // Verify that the method is present in subclass but there are no
+  // inline-caches (since there is no code).
+  const dex::MethodId& super_method_id =
+      dex_file->GetMethodId(inline_monomorphic_super->GetDexMethodIndex());
+  uint32_t sub_method_index = dex_file->GetIndexForMethodId(
+      *dex_file->FindMethodId(*dex_file->FindTypeId("LTestInlineSubtype;"),
+                              dex_file->GetStringId(super_method_id.name_idx_),
+                              dex_file->GetProtoId(super_method_id.proto_idx_)));
+  ProfileCompilationInfo::MethodHotness hotness_sub =
+      info.GetMethodHotness(MethodReference(dex_file, sub_method_index));
+  ASSERT_TRUE(hotness_sub.IsHot());
+  ASSERT_EQ(hotness_sub.GetInlineCacheMap()->size(), 0u);
+}
+
+TEST_F(ProfileAssistantTest, TestProfileCreateWithSubtypeAndDump) {
+  // Create the profile content.
+  std::vector<std::string> profile_methods = {
+      "HLTestInlineSubtype;->inlineMonomorphic(LSuper;)I+]LSuper;LSubA;",
+  };
+  std::string input_file_contents;
+  for (std::string& m : profile_methods) {
+    input_file_contents += m + std::string("\n");
+  }
+
+  // Create the profile and save it to disk.
+  ScratchFile profile_file;
+  std::string dex_filename = GetTestDexFileName("ProfileTestMultiDex");
+  ASSERT_TRUE(CreateProfile(input_file_contents, profile_file.GetFilename(), dex_filename));
+
+  std::string dump_ic;
+  ASSERT_TRUE(DumpClassesAndMethods(
+      profile_file.GetFilename(), &dump_ic, GetTestDexFileName("ProfileTestMultiDex")));
+
+  std::vector<std::string> lines;
+  std::stringstream dump_stream(dump_ic);
+  std::string cur;
+  while (std::getline(dump_stream, cur, '\n')) {
+    lines.push_back(std::move(cur));
+  }
+
+  EXPECT_EQ(lines.size(), 2u);
+  EXPECT_TRUE(std::find(lines.cbegin(),
+                        lines.cend(),
+                        "HLTestInline;->inlineMonomorphic(LSuper;)I+]LSuper;LSubA;") !=
+              lines.cend());
+  EXPECT_TRUE(std::find(lines.cbegin(),
+                        lines.cend(),
+                        "HLTestInlineSubtype;->inlineMonomorphic(LSuper;)I") != lines.cend());
+}
+
 TEST_F(ProfileAssistantTest, TestProfileCreateWithInvalidData) {
   // Create the profile content.
   std::vector<std::string> profile_methods = {
diff --git a/profman/profman.cc b/profman/profman.cc
index b51029d..3cead19 100644
--- a/profman/profman.cc
+++ b/profman/profman.cc
@@ -24,10 +24,12 @@
 #include <cstdint>
 #include <fstream>
 #include <iostream>
+#include <optional>
 #include <ostream>
 #include <set>
 #include <string>
 #include <string_view>
+#include <tuple>
 #include <unordered_set>
 #include <vector>
 
@@ -1121,6 +1123,8 @@
           break;
         }
       }
+    } else {
+      LOG(WARNING) << "Could not find method " << method_idx;
     }
   }
 
@@ -1252,6 +1256,71 @@
     friend std::ostream& operator<<(std::ostream& os, const InlineCacheSegment& ics);
   };
 
+  struct ClassMethodReference {
+    TypeReference type_;
+    uint32_t method_index_;
+
+    bool operator==(const ClassMethodReference& ref) {
+      return ref.type_ == type_ && ref.method_index_ == method_index_;
+    }
+    bool operator!=(const ClassMethodReference& ref) {
+      return !(*this == ref);
+    }
+  };
+
+  // Try to perform simple method resolution to produce a more useful profile.
+  // This will resolve to the nearest class+method-index which is within the
+  // same dexfile and in a declared supertype of the starting class. It will
+  // return nullopt if it cannot find an appropriate method or the nearest
+  // possibility is private.
+  // TODO: This should ideally support looking in other dex files. That's getting
+  // to the point of needing to have a whole class-linker so it's probably not
+  // worth it.
+  std::optional<ClassMethodReference> ResolveMethod(TypeReference class_ref,
+                                                    uint32_t method_index) {
+    const DexFile* dex = class_ref.dex_file;
+    const dex::ClassDef* def = dex->FindClassDef(class_ref.TypeIndex());
+    if (def == nullptr || method_index >= dex->NumMethodIds()) {
+      // Class not in dex-file.
+      return std::nullopt;
+    }
+    if (LIKELY(dex->GetCodeItemOffset(*def, method_index).has_value())) {
+      return ClassMethodReference{class_ref, method_index};
+    }
+    // What to look for.
+    const dex::MethodId& method_id = dex->GetMethodId(method_index);
+    // No going between different dexs so use name and proto directly
+    const dex::ProtoIndex& method_proto = method_id.proto_idx_;
+    const dex::StringIndex& method_name = method_id.name_idx_;
+    // Floyd's algo to prevent infinite loops.
+    // Slow-iterator position for Floyd's
+    dex::TypeIndex slow_class_type = def->class_idx_;
+    // Whether to take a step with the slow iterator.
+    bool update_slow = false;
+    for (dex::TypeIndex cur_candidate = def->superclass_idx_;
+         cur_candidate != dex::TypeIndex::Invalid() && cur_candidate != slow_class_type;) {
+      const dex::ClassDef* cur_class_def = dex->FindClassDef(cur_candidate);
+      if (cur_class_def == nullptr) {
+        // We left the dex file.
+        return std::nullopt;
+      }
+      const dex::MethodId* cur_id =
+          dex->FindMethodIdByIndex(cur_candidate, method_name, method_proto);
+      if (cur_id != nullptr) {
+        if (dex->GetCodeItemOffset(*cur_class_def, dex->GetIndexForMethodId(*cur_id)).has_value()) {
+          return ClassMethodReference{TypeReference(dex, cur_candidate),
+                                      dex->GetIndexForMethodId(*cur_id)};
+        }
+      }
+      // Floyd's algo step.
+      cur_candidate = cur_class_def->superclass_idx_;
+      slow_class_type =
+          update_slow ? dex->FindClassDef(slow_class_type)->superclass_idx_ : slow_class_type;
+      update_slow = !update_slow;
+    }
+    return std::nullopt;
+  }
+
   // Process a line defining a class or a method and its inline caches.
   // Upon success return true and add the class or the method info to profile.
   // Inline caches are identified by the type of the declared receiver type.
@@ -1388,68 +1457,114 @@
 
     const uint32_t method_index = FindMethodIndex(class_ref, method_spec);
     if (method_index == dex::kDexNoIndex) {
+      LOG(WARNING) << "Could not find method " << klass << "->" << method_spec;
       return false;
     }
 
-    std::vector<ProfileMethodInfo::ProfileInlineCache> inline_caches;
-    for (const InlineCacheSegment& segment : segments) {
-      std::vector<uint32_t> dex_pcs;
-      if (segment.IsSingleReceiver()) {
-        DCHECK_EQ(segments.size(), 1u);
-        dex_pcs.resize(1, -1);
-        // TODO This single invoke format should really be phased out and removed.
-        if (!HasSingleInvoke(class_ref, method_index, &dex_pcs[0])) {
-          return false;
-        }
-      } else {
-        // Get the type-ref the method code will use.
-        std::string receiver_str(segment.GetReceiverType());
-        const dex::TypeId* type_id = class_ref.dex_file->FindTypeId(receiver_str.c_str());
-        if (type_id == nullptr) {
-          LOG(WARNING) << "Could not find class: " << segment.GetReceiverType() << " in dex-file "
-                       << class_ref.dex_file << ". Ignoring IC group: '" << segment << "'";
-          continue;
-        }
-        dex::TypeIndex target_index = class_ref.dex_file->GetIndexForTypeId(*type_id);
+    std::optional<ClassMethodReference>
+        resolved_class_method_ref = ResolveMethod(class_ref, method_index);
 
-        GetAllInvokes(class_ref, method_index, target_index, &dex_pcs);
-      }
-      bool missing_types = segment.GetIcTargets()[0] == kMissingTypesMarker;
-      bool megamorphic_types = segment.GetIcTargets()[0] == kMegamorphicTypesMarker;
-      std::vector<TypeReference> classes(
-          missing_types || megamorphic_types ? 0u : segment.NumIcTargets(),
-          TypeReference(/* dex_file= */ nullptr, dex::TypeIndex()));
-      if (!missing_types && !megamorphic_types) {
-        size_t class_it = 0;
-        for (const std::string_view& ic_class : segment.GetIcTargets()) {
-          if (ic_class.empty()) {
-            break;
+    std::vector<ProfileMethodInfo::ProfileInlineCache> inline_caches;
+    // We can only create inline-caches when we actually have code we can
+    // examine. If we couldn't resolve the method don't bother trying to create
+    // inline-caches.
+    if (resolved_class_method_ref) {
+      for (const InlineCacheSegment &segment : segments) {
+        std::vector<uint32_t> dex_pcs;
+        if (segment.IsSingleReceiver()) {
+          DCHECK_EQ(segments.size(), 1u);
+          dex_pcs.resize(1, -1);
+          // TODO This single invoke format should really be phased out and
+          // removed.
+          if (!HasSingleInvoke(class_ref, method_index, &dex_pcs[0])) {
+            return false;
           }
-          if (!FindClass(dex_files, ic_class, &(classes[class_it++]))) {
-            LOG(segment.IsSingleReceiver() ? ERROR : WARNING)
-                << "Could not find class: " << ic_class << " in " << segment;
-            if (segment.IsSingleReceiver()) {
-              return false;
-            } else {
-              // Be a bit more forgiving with profiles from servers.
-              missing_types = true;
-              classes.clear();
+        } else {
+          // Get the type-ref the method code will use.
+          std::string receiver_str(segment.GetReceiverType());
+          const dex::TypeId *type_id =
+              class_ref.dex_file->FindTypeId(receiver_str.c_str());
+          if (type_id == nullptr) {
+            LOG(WARNING) << "Could not find class: "
+                         << segment.GetReceiverType() << " in dex-file "
+                         << class_ref.dex_file << ". Ignoring IC group: '"
+                         << segment << "'";
+            continue;
+          }
+          dex::TypeIndex target_index =
+              class_ref.dex_file->GetIndexForTypeId(*type_id);
+
+          GetAllInvokes(resolved_class_method_ref->type_,
+                        resolved_class_method_ref->method_index_,
+                        target_index,
+                        &dex_pcs);
+        }
+        bool missing_types = segment.GetIcTargets()[0] == kMissingTypesMarker;
+        bool megamorphic_types =
+            segment.GetIcTargets()[0] == kMegamorphicTypesMarker;
+        std::vector<TypeReference> classes(
+            missing_types || megamorphic_types ? 0u : segment.NumIcTargets(),
+            TypeReference(/* dex_file= */ nullptr, dex::TypeIndex()));
+        if (!missing_types && !megamorphic_types) {
+          size_t class_it = 0;
+          for (const std::string_view &ic_class : segment.GetIcTargets()) {
+            if (ic_class.empty()) {
               break;
             }
+            if (!FindClass(dex_files, ic_class, &(classes[class_it++]))) {
+              LOG(segment.IsSingleReceiver() ? ERROR : WARNING)
+                  << "Could not find class: " << ic_class << " in " << segment;
+              if (segment.IsSingleReceiver()) {
+                return false;
+              } else {
+                // Be a bit more forgiving with profiles from servers.
+                missing_types = true;
+                classes.clear();
+                break;
+              }
+            }
           }
+          // Make sure we are actually the correct size
+          classes.resize(class_it, TypeReference(nullptr, dex::TypeIndex()));
         }
-        // Make sure we are actually the correct size
-        classes.resize(class_it, TypeReference(nullptr, dex::TypeIndex()));
-      }
-      for (size_t dex_pc : dex_pcs) {
-        inline_caches.emplace_back(dex_pc, missing_types, classes, megamorphic_types);
+        for (size_t dex_pc : dex_pcs) {
+          inline_caches.emplace_back(dex_pc, missing_types, classes,
+                                     megamorphic_types);
+        }
       }
     }
     MethodReference ref(class_ref.dex_file, method_index);
     if (is_hot) {
-      profile->AddMethod(ProfileMethodInfo(ref, inline_caches),
-          static_cast<ProfileCompilationInfo::MethodHotness::Flag>(flags),
-          annotation);
+      ClassMethodReference orig_cmr { class_ref, method_index };
+      if (!inline_caches.empty() &&
+          resolved_class_method_ref &&
+          orig_cmr != *resolved_class_method_ref) {
+        // We have inline-caches on a method that doesn't actually exist. We
+        // want to put the inline caches on the resolved version of the method
+        // (if we could find one) and just mark the actual method as present.
+        const DexFile *dex = resolved_class_method_ref->type_.dex_file;
+        LOG(VERBOSE) << "Adding "
+                     << dex->PrettyMethod(
+                            resolved_class_method_ref->method_index_)
+                     << " as alias for " << dex->PrettyMethod(method_index);
+        // The inline-cache refers to a supertype of the actual profile line.
+        // Include this supertype method in the profile as well.
+        MethodReference resolved_ref(class_ref.dex_file,
+                                     resolved_class_method_ref->method_index_);
+        profile->AddMethod(
+            ProfileMethodInfo(resolved_ref, inline_caches),
+            static_cast<ProfileCompilationInfo::MethodHotness::Flag>(flags),
+            annotation);
+        profile->AddMethod(
+            ProfileMethodInfo(ref),
+            static_cast<ProfileCompilationInfo::MethodHotness::Flag>(flags),
+            annotation);
+      } else {
+        profile->AddMethod(
+            ProfileMethodInfo(ref, inline_caches),
+            static_cast<ProfileCompilationInfo::MethodHotness::Flag>(flags),
+            annotation);
+      }
     }
     if (flags != 0) {
       if (!profile->AddMethod(ProfileMethodInfo(ref),
diff --git a/test/ProfileTestMultiDex/Main.java b/test/ProfileTestMultiDex/Main.java
index a84cb98..98d4d96 100644
--- a/test/ProfileTestMultiDex/Main.java
+++ b/test/ProfileTestMultiDex/Main.java
@@ -72,6 +72,12 @@
   }
 }
 
+class TestInlineSubtype extends TestInline {
+  public void foobar() {
+    this.inlineMonomorphic(new SubA());
+  }
+}
+
 abstract class Secret {
   abstract int getIdentity();
 }
diff --git a/test/ProfileTestMultiDex/main.jpp b/test/ProfileTestMultiDex/main.jpp
index bd548a8..33fede8 100644
--- a/test/ProfileTestMultiDex/main.jpp
+++ b/test/ProfileTestMultiDex/main.jpp
@@ -1,7 +1,7 @@
 Main:
   @@com.android.jack.annotations.ForceInMainDex
   class Main
-TestInqline:
+TestInline:
   @@com.android.jack.annotations.ForceInMainDex
   class TestInline
 Secret:
@@ -25,3 +25,6 @@
 ZLotsOfMethods:
 @@com.android.jack.annotations.ForceInMainDex
   class ZLotsOfMethods
+TestInlineSubtype:
+  @@com.android.jack.annotations.ForceInMainDex
+  class TestInlineSubtype
diff --git a/test/ProfileTestMultiDex/main.list b/test/ProfileTestMultiDex/main.list
index 8ef9280..023f948 100644
--- a/test/ProfileTestMultiDex/main.list
+++ b/test/ProfileTestMultiDex/main.list
@@ -1,5 +1,6 @@
 Main.class
 TestInline.class
+TestInlineSubtype.class
 Secret.class
 Super.class
 SubA.class