Search code examples
llvmllvm-ircontrol-flow-graph

How to determine if a BasicBlock is controled by a `if`

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:

enter image description here

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!

Further question

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)
Solution

  • 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);