Differential D115985
[JumpThreading] Remove unreachable blocks after jumpthreading Authored by duanyangjing on Dec 17 2021, 11:49 PM.
Details In the jumpthreading main loop, we handle unreachable blocks generated in the middle of transformation by checking pred_empty(&BB), and delete this block. But this mechanism cannot handle all unreachable blocks: when a BB is made unreachable, it may still have a predecessor. This is true when the bb is part of a connected component and the edge from entry block to the component is removed. This patch adds a full clean-up of unreachable blocks after the transformation.
Diff Detail
Unit Tests Event TimelineComment Actions Please submit patches with full context (-U99999). Why is it necessary for jump threading to remove unreachable blocks?
Comment Actions Because right now we have the following code snippet which seems to try to handle unreachable blocks: if (pred_empty(&BB)) {
// When processBlock makes BB unreachable it doesn't bother to fix up
// the instructions in it. We must remove BB to prevent invalid IR.
LLVM_DEBUG(dbgs() << " JT: Deleting dead block '" << BB.getName()
<< "' with terminator: " << *BB.getTerminator()
<< '\n');
LoopHeaders.erase(&BB);
LVI->eraseBlock(&BB);
DeleteDeadBlock(&BB, DTU);
Changed = true;
continue;
}Comment Actions @duanyangjing So you're saying that keeping the unreachable block is a correctness issue, not an optimization issue? Is the IR produced by JumpThreading invalid in some way? Your comment in the test indicates that this causes issues in a subsequent pass, but we generally expect passes to be able to deal with unreachable code and the peculiar IR constructs that can appear inside it.
Comment Actions OK thanks for the suggestions, will update soon. Yes I'm saying it should be a correctness issue to keep the unreachable block. Because the existing code already tries to delete unreachable block, but only when pred_empty(BB) holds. This does not cover situations like this (Sorry I cann't think of a better way to illustrate the CFG): ----edge from entry ---> | bb1 in cycle | --> | bb2 in cycle| ---imagine this edge goes back to bb1--> Is the above argument alone (regardless of how other passes should handle peculiar IR constructs) strong enough to warrant a fix to remove the unreachable blocks? The actual problem happenes later in loop deletion, because some value defined in the unreachable cycle is used in the main component of the CFG. I can give a more detailed description if you think it's necessary. Comment Actions As suggested, make it work for both legacy and new pass manager, also rename the test with opt -instnamer. Comment Actions Didn't include filecheck pattern in previous tests. Didn't use update_test_checks.py because I think it's more clear to show the problem. | ||||||||||||
This code is only used by the legacy pass manager, so your test case cannot be using it. You'd have to do this in runImpl() for it to apply to both the legacy and new pass manager.