Speed up graph checker by avoiding HInstructionList::Contains calls

With extra bookeeping we can look in a set, instead of a list.

Bug: 304483915
Test: art/test/testrunner/testrunner.py --host --64 -b --optimizing
Change-Id: Ia390a709b2d310590cd9296c56d9f586c72705df

2 files changed, 37 insertions, 11 deletions

diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 31ba3fe98a..f32494bb04 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -28,6 +28,7 @@
 #include "code_generator.h"
 #include "handle.h"
 #include "mirror/class.h"
+#include "nodes.h"
 #include "obj_ptr-inl.h"
 #include "scoped_thread_state_change-inl.h"
 #include "subtype_check.h"
@@ -522,6 +523,26 @@ void GraphChecker::VisitMonitorOperation(HMonitorOperation* monitor_op) {
   flag_info_.seen_monitor_operation = true;
 }
 
+bool GraphChecker::ContainedInItsBlockList(HInstruction* instruction) {
+  HBasicBlock* block = instruction->GetBlock();
+  ScopedArenaSafeMap<HBasicBlock*, ScopedArenaHashSet<HInstruction*>>& instruction_set =
+      instruction->IsPhi() ? phis_per_block_ : instructions_per_block_;
+  auto map_it = instruction_set.find(block);
+  if (map_it == instruction_set.end()) {
+    // Populate extra bookkeeping.
+    map_it = instruction_set.insert(
+        {block, ScopedArenaHashSet<HInstruction*>(allocator_.Adapter(kArenaAllocGraphChecker))})
+        .first;
+    const HInstructionList& instruction_list = instruction->IsPhi() ?
+                                                   instruction->GetBlock()->GetPhis() :
+                                                   instruction->GetBlock()->GetInstructions();
+    for (HInstructionIterator list_it(instruction_list); !list_it.Done(); list_it.Advance()) {
+        map_it->second.insert(list_it.Current());
+    }
+  }
+  return map_it->second.find(instruction) != map_it->second.end();
+}
+
 void GraphChecker::VisitInstruction(HInstruction* instruction) {
   if (seen_ids_.IsBitSet(instruction->GetId())) {
     AddError(StringPrintf("Instruction id %d is duplicate in graph.",
@@ -544,23 +565,19 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
                           instruction->GetBlock()->GetBlockId()));
   }
 
-  // Ensure the inputs of `instruction` are defined in a block of the graph.
+  // Ensure the inputs of `instruction` are defined in a block of the graph, and the entry in the
+  // use list is consistent.
   for (HInstruction* input : instruction->GetInputs()) {
     if (input->GetBlock() == nullptr) {
       AddError(StringPrintf("Input %d of instruction %d is not in any "
                             "basic block of the control-flow graph.",
                             input->GetId(),
                             instruction->GetId()));
-    } else {
-      const HInstructionList& list = input->IsPhi()
-          ? input->GetBlock()->GetPhis()
-          : input->GetBlock()->GetInstructions();
-      if (!list.Contains(input)) {
+    } else if (!ContainedInItsBlockList(input)) {
         AddError(StringPrintf("Input %d of instruction %d is not defined "
                               "in a basic block of the control-flow graph.",
                               input->GetId(),
                               instruction->GetId()));
-      }
     }
   }
 
@@ -568,10 +585,7 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) {
   // and the entry in the use list is consistent.
   for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
     HInstruction* user = use.GetUser();
-    const HInstructionList& list = user->IsPhi()
-        ? user->GetBlock()->GetPhis()
-        : user->GetBlock()->GetInstructions();
-    if (!list.Contains(user)) {
+    if (!ContainedInItsBlockList(user)) {
       AddError(StringPrintf("User %s:%d of instruction %d is not defined "
                             "in a basic block of the control-flow graph.",
                             user->DebugName(),
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index aff2358411..38e2d7ced9 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -41,6 +41,8 @@ class GraphChecker : public HGraphDelegateVisitor {
         allocator_(graph->GetArenaStack()),
         seen_ids_(&allocator_, graph->GetCurrentInstructionId(), false, kArenaAllocGraphChecker),
         uses_per_instruction_(allocator_.Adapter(kArenaAllocGraphChecker)),
+        instructions_per_block_(allocator_.Adapter(kArenaAllocGraphChecker)),
+        phis_per_block_(allocator_.Adapter(kArenaAllocGraphChecker)),
         codegen_(codegen) {
     seen_ids_.ClearAllBits();
   }
@@ -124,6 +126,11 @@ class GraphChecker : public HGraphDelegateVisitor {
   // Checks that the graph's flags are set correctly.
   void CheckGraphFlags();
 
+  // Checks if `instruction` is in its block's instruction/phi list. To do so, it searches
+  // instructions_per_block_/phis_per_block_ which are set versions of that. If the set to
+  // check hasn't been populated yet, it does so now.
+  bool ContainedInItsBlockList(HInstruction* instruction);
+
   // String displayed before dumped errors.
   const char* const dump_prefix_;
   ScopedArenaAllocator allocator_;
@@ -136,6 +143,11 @@ class GraphChecker : public HGraphDelegateVisitor {
   ScopedArenaSafeMap<int, ScopedArenaSet<const art::HUseListNode<art::HInstruction*>*>>
       uses_per_instruction_;
 
+  // Extra bookkeeping to increase GraphChecker's speed while asking if an instruction is contained
+  // in a list of instructions/phis.
+  ScopedArenaSafeMap<HBasicBlock*, ScopedArenaHashSet<HInstruction*>> instructions_per_block_;
+  ScopedArenaSafeMap<HBasicBlock*, ScopedArenaHashSet<HInstruction*>> phis_per_block_;
+
   // Used to access target information.
   CodeGenerator* codegen_;