如何确定 BasicBlock 是否由 `if` 控制

Question

我想使用 LLVM 来分析一个基本块是否受到 if（即 br 指令）的控制流的影响。 “A basic block BB is NOT affected by br”的意思是无论br到BB的两个block中的哪一个都会被执行。我用一个例子简单说明一下我想要的：

我当前确定基本块 BB 是否受影响的规则是（如果 true，受影响。）

¬(postDominate(BB, BranchInst->leftBB) && postDominate(BB, BranchInst->rightBB))

由于我无法对所有可能的 CFG 详尽地测试上述规则，我想知道此规则是否 sound 和 complete .

谢谢！

进一步的问题

我也很困惑，如果我应该使用 dominate 而不是 postDominate 之类的（我知道 post-dominance 和 dominance 之间的区别，但是我应该使用哪个？两个规则在这个例子中似乎可行，但我不确定哪个 will/won 在其他情况下不起作用）：

Dominate(BranchInst->leftBB, BB) || Dominate(BranchInst->rightBB, BB)

Answer 1

块 Y 控制依赖 块 X 当且仅当 Y 后支配至少一个但不是 X 的所有后继者。

llvm::ReverseIDFCalculator in llvm/Analysis/IteratedDominanceFrontier.h 将为您计算 post-dominance 边界，这正是您所需要的。 “迭代”部分与您的用例无关，请忽略 setLiveInBlocks() 方法。

我根本没有测试过这个，但我希望像这样的东西应该可以解决问题：

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

Answer 2

关系control dependent是传递的。将定义迭代地应用于所有 control-dependent-impacted 块是正确的方法。

如何确定 BasicBlock 是否由 `if` 控制

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

llvm

llvm-ir

cfg

进一步的问题