Dominance frontier & Postdominance frontier


I found that LLVM 3.1 says Dominance frontier is deprecated. Can anyone please tell me, if there is any replacement for Dominance frontier & Postdominance frontier in LLVM? What are the options if we need to use them?


You may want to read this thread on llvmdev from August: Marco’s reply mentions an alternative algorithm in Muchnick’s compiler book. I believe the algorithm in Section 7.3 of Allen and Kennedy uses the post dominator tree only. – John T.

You can easily calculate the DF(x) of a node if you have the J-edges. Look at V Sreedhar’s classic thesis on DJ graphs. Look at our work in TOPLAS 2005 for computing DF and phi using DJ graphs. Its pretty straightforward if u hv the dom tree and J-edges. J-edges are nothing else but CFG edges which are not present in the dominator tree.

Hope this helps. Post-dom-frontier is an analogous problem on the reverse cfg and pdom tree.

  • Dibyendu