in compiler/optimizing/graph_checker.cc [45:247]
void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
current_block_ = block;
// 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.
ArenaVector<HBasicBlock*>& sorted_predecessors = blocks_storage_;
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()));
}
}
// 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.
ArenaVector<HBasicBlock*>& sorted_successors = blocks_storage_;
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()));
}
}
// Ensure `block` ends with a branch instruction.
// This invariant is not enforced on non-SSA graphs. Graph built from DEX with
// dead code that falls out of the method will not end with a control-flow
// instruction. Such code is removed during the SSA-building DCE phase.
if (GetGraph()->IsInSsaForm() && !block->EndsWithControlFlowInstruction()) {
AddError(StringPrintf("Block %d does not end with a branch instruction.",
block->GetBlockId()));
}
// Ensure that only Return(Void) and Throw jump to Exit. An exiting TryBoundary
// may be between the instructions if the Throw/Return(Void) is in a try block.
if (block->IsExitBlock()) {
for (HBasicBlock* predecessor : block->GetPredecessors()) {
HInstruction* last_instruction = IsExitTryBoundaryIntoExitBlock(predecessor) ?
predecessor->GetSinglePredecessor()->GetLastInstruction() :
predecessor->GetLastInstruction();
if (!IsAllowedToJumpToExitBlock(last_instruction)) {
AddError(StringPrintf("Unexpected instruction %s:%d jumps into the exit block.",
last_instruction->DebugName(),
last_instruction->GetId()));
}
}
}
// Visit this block's list of phis.
for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
// Ensure this block's list of phis contains only phis.
if (!current->IsPhi()) {
AddError(StringPrintf("Block %d has a non-phi in its phi list.",
current_block_->GetBlockId()));
}
if (current->GetNext() == nullptr && current != block->GetLastPhi()) {
AddError(StringPrintf("The recorded last phi of block %d does not match "
"the actual last phi %d.",
current_block_->GetBlockId(),
current->GetId()));
}
current->Accept(this);
}
// Visit this block's list of instructions.
for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
// Ensure this block's list of instructions does not contains phis.
if (current->IsPhi()) {
AddError(StringPrintf("Block %d has a phi in its non-phi list.",
current_block_->GetBlockId()));
}
if (current->GetNext() == nullptr && current != block->GetLastInstruction()) {
AddError(StringPrintf("The recorded last instruction of block %d does not match "
"the actual last instruction %d.",
current_block_->GetBlockId(),
current->GetId()));
}
current->Accept(this);
}
// Ensure that catch blocks are not normal successors, and normal blocks are
// never exceptional successors.
for (HBasicBlock* successor : block->GetNormalSuccessors()) {
if (successor->IsCatchBlock()) {
AddError(StringPrintf("Catch block %d is a normal successor of block %d.",
successor->GetBlockId(),
block->GetBlockId()));
}
}
for (HBasicBlock* successor : block->GetExceptionalSuccessors()) {
if (!successor->IsCatchBlock()) {
AddError(StringPrintf("Normal block %d is an exceptional successor of block %d.",
successor->GetBlockId(),
block->GetBlockId()));
}
}
// Ensure dominated blocks have `block` as the dominator.
for (HBasicBlock* dominated : block->GetDominatedBlocks()) {
if (dominated->GetDominator() != block) {
AddError(StringPrintf("Block %d should be the dominator of %d.",
block->GetBlockId(),
dominated->GetBlockId()));
}
}
// Ensure there is no critical edge (i.e., an edge connecting a
// block with multiple successors to a block with multiple
// predecessors). Exceptional edges are synthesized and hence
// not accounted for.
if (block->GetSuccessors().size() > 1) {
if (IsExitTryBoundaryIntoExitBlock(block)) {
// Allowed critical edge (Throw/Return/ReturnVoid)->TryBoundary->Exit.
} else {
for (HBasicBlock* successor : block->GetNormalSuccessors()) {
if (successor->GetPredecessors().size() > 1) {
AddError(StringPrintf("Critical edge between blocks %d and %d.",
block->GetBlockId(),
successor->GetBlockId()));
}
}
}
}
// Ensure try membership information is consistent.
if (block->IsCatchBlock()) {
if (block->IsTryBlock()) {
const HTryBoundary& try_entry = block->GetTryCatchInformation()->GetTryEntry();
AddError(StringPrintf("Catch blocks should not be try blocks but catch block %d "
"has try entry %s:%d.",
block->GetBlockId(),
try_entry.DebugName(),
try_entry.GetId()));
}
if (block->IsLoopHeader()) {
AddError(StringPrintf("Catch blocks should not be loop headers but catch block %d is.",
block->GetBlockId()));
}
} else {
for (HBasicBlock* predecessor : block->GetPredecessors()) {
const HTryBoundary* incoming_try_entry = predecessor->ComputeTryEntryOfSuccessors();
if (block->IsTryBlock()) {
const HTryBoundary& stored_try_entry = block->GetTryCatchInformation()->GetTryEntry();
if (incoming_try_entry == nullptr) {
AddError(StringPrintf("Block %d has try entry %s:%d but no try entry follows "
"from predecessor %d.",
block->GetBlockId(),
stored_try_entry.DebugName(),
stored_try_entry.GetId(),
predecessor->GetBlockId()));
} else if (!incoming_try_entry->HasSameExceptionHandlersAs(stored_try_entry)) {
AddError(StringPrintf("Block %d has try entry %s:%d which is not consistent "
"with %s:%d that follows from predecessor %d.",
block->GetBlockId(),
stored_try_entry.DebugName(),
stored_try_entry.GetId(),
incoming_try_entry->DebugName(),
incoming_try_entry->GetId(),
predecessor->GetBlockId()));
}
} else if (incoming_try_entry != nullptr) {
AddError(StringPrintf("Block %d is not a try block but try entry %s:%d follows "
"from predecessor %d.",
block->GetBlockId(),
incoming_try_entry->DebugName(),
incoming_try_entry->GetId(),
predecessor->GetBlockId()));
}
}
}
if (block->IsLoopHeader()) {
HandleLoop(block);
}
}