diff options
author | 2023-09-29 09:14:41 +0100 | |
---|---|---|
committer | 2023-10-04 10:19:12 +0000 | |
commit | 599b2e5d64e3b04864a9e6daca74ae836b9353d4 (patch) | |
tree | 34b1e1434e6ba2944d8889fdf31efe2cb317d993 /compiler/optimizing/graph_checker.cc | |
parent | 19adcfbc7b435ac2357b0a33a82a667ace9010af (diff) |
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
Diffstat (limited to 'compiler/optimizing/graph_checker.cc')
-rw-r--r-- | compiler/optimizing/graph_checker.cc | 151 |
1 files changed, 92 insertions, 59 deletions
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc index 596049f369..31ba3fe98a 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -168,52 +168,68 @@ void GraphChecker::CheckGraphFlags() { void GraphChecker::VisitBasicBlock(HBasicBlock* block) { current_block_ = block; - // Use local allocator for allocating memory. - ScopedArenaAllocator allocator(GetGraph()->GetArenaStack()); - - // Check consistency with respect to predecessors of `block`. - // Note: Counting duplicates with a sorted vector uses up to 6x less memory - // than ArenaSafeMap<HBasicBlock*, size_t> and also allows storage reuse. - ScopedArenaVector<HBasicBlock*> sorted_predecessors(allocator.Adapter(kArenaAllocGraphChecker)); - sorted_predecessors.assign(block->GetPredecessors().begin(), block->GetPredecessors().end()); - std::sort(sorted_predecessors.begin(), sorted_predecessors.end()); - for (auto it = sorted_predecessors.begin(), end = sorted_predecessors.end(); it != end; ) { - HBasicBlock* p = *it++; - size_t p_count_in_block_predecessors = 1u; - for (; it != end && *it == p; ++it) { - ++p_count_in_block_predecessors; - } - size_t block_count_in_p_successors = - std::count(p->GetSuccessors().begin(), p->GetSuccessors().end(), block); - if (p_count_in_block_predecessors != block_count_in_p_successors) { - AddError(StringPrintf( - "Block %d lists %zu occurrences of block %d in its predecessors, whereas " - "block %d lists %zu occurrences of block %d in its successors.", - block->GetBlockId(), p_count_in_block_predecessors, p->GetBlockId(), - p->GetBlockId(), block_count_in_p_successors, block->GetBlockId())); - } - } + { + // Use local allocator for allocating memory. We use C++ scopes (i.e. `{}`) to reclaim the + // memory as soon as possible, and to end the scope of this `ScopedArenaAllocator`. + ScopedArenaAllocator allocator(GetGraph()->GetArenaStack()); - // Check consistency with respect to successors of `block`. - // Note: Counting duplicates with a sorted vector uses up to 6x less memory - // than ArenaSafeMap<HBasicBlock*, size_t> and also allows storage reuse. - ScopedArenaVector<HBasicBlock*> sorted_successors(allocator.Adapter(kArenaAllocGraphChecker)); - sorted_successors.assign(block->GetSuccessors().begin(), block->GetSuccessors().end()); - std::sort(sorted_successors.begin(), sorted_successors.end()); - for (auto it = sorted_successors.begin(), end = sorted_successors.end(); it != end; ) { - HBasicBlock* s = *it++; - size_t s_count_in_block_successors = 1u; - for (; it != end && *it == s; ++it) { - ++s_count_in_block_successors; + { + // Check consistency with respect to predecessors of `block`. + // Note: Counting duplicates with a sorted vector uses up to 6x less memory + // than ArenaSafeMap<HBasicBlock*, size_t> and also allows storage reuse. + ScopedArenaVector<HBasicBlock*> sorted_predecessors( + allocator.Adapter(kArenaAllocGraphChecker)); + sorted_predecessors.assign(block->GetPredecessors().begin(), block->GetPredecessors().end()); + std::sort(sorted_predecessors.begin(), sorted_predecessors.end()); + for (auto it = sorted_predecessors.begin(), end = sorted_predecessors.end(); it != end;) { + HBasicBlock* p = *it++; + size_t p_count_in_block_predecessors = 1u; + for (; it != end && *it == p; ++it) { + ++p_count_in_block_predecessors; + } + size_t block_count_in_p_successors = + std::count(p->GetSuccessors().begin(), p->GetSuccessors().end(), block); + if (p_count_in_block_predecessors != block_count_in_p_successors) { + AddError(StringPrintf( + "Block %d lists %zu occurrences of block %d in its predecessors, whereas " + "block %d lists %zu occurrences of block %d in its successors.", + block->GetBlockId(), + p_count_in_block_predecessors, + p->GetBlockId(), + p->GetBlockId(), + block_count_in_p_successors, + block->GetBlockId())); + } + } } - size_t block_count_in_s_predecessors = - std::count(s->GetPredecessors().begin(), s->GetPredecessors().end(), block); - if (s_count_in_block_successors != block_count_in_s_predecessors) { - AddError(StringPrintf( - "Block %d lists %zu occurrences of block %d in its successors, whereas " - "block %d lists %zu occurrences of block %d in its predecessors.", - block->GetBlockId(), s_count_in_block_successors, s->GetBlockId(), - s->GetBlockId(), block_count_in_s_predecessors, block->GetBlockId())); + + { + // Check consistency with respect to successors of `block`. + // Note: Counting duplicates with a sorted vector uses up to 6x less memory + // than ArenaSafeMap<HBasicBlock*, size_t> and also allows storage reuse. + ScopedArenaVector<HBasicBlock*> sorted_successors(allocator.Adapter(kArenaAllocGraphChecker)); + sorted_successors.assign(block->GetSuccessors().begin(), block->GetSuccessors().end()); + std::sort(sorted_successors.begin(), sorted_successors.end()); + for (auto it = sorted_successors.begin(), end = sorted_successors.end(); it != end;) { + HBasicBlock* s = *it++; + size_t s_count_in_block_successors = 1u; + for (; it != end && *it == s; ++it) { + ++s_count_in_block_successors; + } + size_t block_count_in_s_predecessors = + std::count(s->GetPredecessors().begin(), s->GetPredecessors().end(), block); + if (s_count_in_block_successors != block_count_in_s_predecessors) { + AddError( + StringPrintf("Block %d lists %zu occurrences of block %d in its successors, whereas " + "block %d lists %zu occurrences of block %d in its predecessors.", + block->GetBlockId(), + s_count_in_block_successors, + s->GetBlockId(), + s->GetBlockId(), + block_count_in_s_predecessors, + block->GetBlockId())); + } + } } } @@ -587,21 +603,38 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) { } // Ensure 'instruction' has pointers to its inputs' use entries. - auto&& input_records = instruction->GetInputRecords(); - for (size_t i = 0; i < input_records.size(); ++i) { - const HUserRecord<HInstruction*>& input_record = input_records[i]; - HInstruction* input = input_record.GetInstruction(); - if ((input_record.GetBeforeUseNode() == input->GetUses().end()) || - (input_record.GetUseNode() == input->GetUses().end()) || - !input->GetUses().ContainsNode(*input_record.GetUseNode()) || - (input_record.GetUseNode()->GetIndex() != i)) { - AddError(StringPrintf("Instruction %s:%d has an invalid iterator before use entry " - "at input %u (%s:%d).", - instruction->DebugName(), - instruction->GetId(), - static_cast<unsigned>(i), - input->DebugName(), - input->GetId())); + { + auto&& input_records = instruction->GetInputRecords(); + for (size_t i = 0; i < input_records.size(); ++i) { + const HUserRecord<HInstruction*>& input_record = input_records[i]; + HInstruction* input = input_record.GetInstruction(); + + // Populate bookkeeping, if needed. See comment in graph_checker.h for uses_per_instruction_. + auto it = uses_per_instruction_.find(input->GetId()); + if (it == uses_per_instruction_.end()) { + it = uses_per_instruction_ + .insert({input->GetId(), + ScopedArenaSet<const art::HUseListNode<art::HInstruction*>*>( + allocator_.Adapter(kArenaAllocGraphChecker))}) + .first; + for (auto&& use : input->GetUses()) { + it->second.insert(std::addressof(use)); + } + } + + if ((input_record.GetBeforeUseNode() == input->GetUses().end()) || + (input_record.GetUseNode() == input->GetUses().end()) || + (it->second.find(std::addressof(*input_record.GetUseNode())) == it->second.end()) || + (input_record.GetUseNode()->GetIndex() != i)) { + AddError( + StringPrintf("Instruction %s:%d has an invalid iterator before use entry " + "at input %u (%s:%d).", + instruction->DebugName(), + instruction->GetId(), + static_cast<unsigned>(i), + input->DebugName(), + input->GetId())); + } } } |