Speed up graph checker for graphs with instructions with many uses

As part of VisitInstruction, we verify that the instruction's
input_record is present in the corresponding input's GetUses. If
an instruction is used in many places (e.g. 200K+ uses), the
linear search through GetUses is too slow. We can use bookkeeping
to search in a set, instead of a list.

This makes dex2oatd over an order of magnitude faster for such cases.

Bug: 301264418
Test: Manually compile the app+profile in the bug
Change-Id: I3dd6d1b9b2fd65a4bf5ee8324602a412e3f1715f

1 files changed, 15 insertions, 7 deletions

diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index d6644f3b50..4dee42738e 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -22,7 +22,7 @@
 #include "base/arena_bit_vector.h"
 #include "base/bit_vector-inl.h"
 #include "base/macros.h"
-#include "base/scoped_arena_allocator.h"
+#include "base/scoped_arena_containers.h"
 #include "nodes.h"
 
 namespace art HIDDEN {
@@ -35,12 +35,13 @@ class GraphChecker : public HGraphDelegateVisitor {
   explicit GraphChecker(HGraph* graph,
                         CodeGenerator* codegen = nullptr,
                         const char* dump_prefix = "art::GraphChecker: ")
-    : HGraphDelegateVisitor(graph),
-      errors_(graph->GetAllocator()->Adapter(kArenaAllocGraphChecker)),
-      dump_prefix_(dump_prefix),
-      allocator_(graph->GetArenaStack()),
-      seen_ids_(&allocator_, graph->GetCurrentInstructionId(), false, kArenaAllocGraphChecker),
-      codegen_(codegen) {
+      : HGraphDelegateVisitor(graph),
+        errors_(graph->GetAllocator()->Adapter(kArenaAllocGraphChecker)),
+        dump_prefix_(dump_prefix),
+        allocator_(graph->GetArenaStack()),
+        seen_ids_(&allocator_, graph->GetCurrentInstructionId(), false, kArenaAllocGraphChecker),
+        uses_per_instruction_(allocator_.Adapter(kArenaAllocGraphChecker)),
+        codegen_(codegen) {
     seen_ids_.ClearAllBits();
   }
 
@@ -129,6 +130,13 @@ class GraphChecker : public HGraphDelegateVisitor {
   ScopedArenaAllocator allocator_;
   ArenaBitVector seen_ids_;
 
+  // As part of VisitInstruction, we verify that the instruction's input_record is present in the
+  // corresponding input's GetUses. If an instruction is used in many places (e.g. 200K+ uses), the
+  // linear search through GetUses is too slow. We can use bookkeeping to search in a set, instead
+  // of a list.
+  ScopedArenaSafeMap<int, ScopedArenaSet<const art::HUseListNode<art::HInstruction*>*>>
+      uses_per_instruction_;
+
   // Used to access target information.
   CodeGenerator* codegen_;