Any passes that work on extended basic blocks?

Hi all,

I am trying to find a sample pass that works on extended basic blocks. Any suggestion or help is very much appreciated.

Thanks in advance.

Best,
Weibo

As far as I know, there is none. Pretty much every analysis or transform on EBBs can be extended to work on the dominator tree, which is what LLVM prefers.

Cameron

As far as I know, there is none. Pretty much every analysis or transform on EBBs can be extended to work on the dominator tree, which is what LLVM prefers.

At IR level, passes tend to work on the DomTree or directly on the use/def chains independent of the CFG. If you really need to scan instructions, there’s nothing wrong with walking upward in the CFG until you see multiple predecessors. It’s possible to have unreachable cycles though.

In machine code we sometimes scan the instruction list within a block up to some instruction threshold. I think most of those cases should be replaced by scanning an extended basic block, which is no more complex and much less artificially limited. Unfortunately, we don’t have reliable block layout until very late. As a workaround, you can visit blocks in RPO order, like Jakob just did in Thumb2SizeReduce:

  • ReversePostOrderTraversal<MachineFunction*> RPOT(&MF);
  • for (ReversePostOrderTraversal<MachineFunction*>::rpo_iterator
  • I = RPOT.begin(), E = RPOT.end(); I != E; ++I)

You don’t benefit from branch frequency, but it may be good enough and will tend to work when critical edges are not split.

-Andy