I want to use LLVM to analyze if a basic block is affected by a control flow of an if
(i.e., br
instruction). "A basic block BB
is NOT affected by br
" means that no matter which of two blocks the br
goes to BB
will be executed for sure. I use an example to briefly show what I want:
My current rule to determine if a basic block BB
is affected is (if true
, affected.)
¬(postDominate(BB, BranchInst->leftBB) && postDominate(BB, BranchInst->rightBB))
Since I can not exhaustively test the rule above to all possible CFGs, I want to know if this rule is sound and complete.
Thanks!
I am also confused if I should use dominate
rather than postDominate
like (I know the difference between post-dominance and dominance, but which should I use? Both rules seems work in this example, but I am not sure which one will/won't work in other cases):
Dominate(BranchInst->leftBB, BB) || Dominate(BranchInst->rightBB, BB)
A block Y is control dependent on block X if and only if Y postdominates at least one but not all successors of X.
llvm::ReverseIDFCalculator
in llvm/Analysis/IteratedDominanceFrontier.h
will calculate the post-dominance frontier for you, which is exactly what you need. The "iterated" part isn't relevant to your use case, ignore the setLiveInBlocks() method.
I have not tested this at all, but I expect that something like this should do the trick:
// PDT is the llvm::PostDominatorTree
SmallPtrSet<BasicBlock *, 1> BBSet{block_with_branch};
SmallVector<BasicBlock *, 32> IDFBlocks;
ReverseIDFCalculator IDFs(PDT);
IDFs.setDefiningBlocks(BBSet);
IDFs.calculate(IDFBlocks);