Control Dependence Graph builder

Hello All,

I am interested in Control Dependence Graph building using the CFG and
Dominance Frontier provided by corresponding passes. Just wandering whether
LLVM provides some kind of pass or builder which will generate the Control
Dependence Graph?

Thanks,
Arsen

Hello All,

I am interested in Control Dependence Graph building using the CFG and
Dominance Frontier provided by corresponding passes. Just wandering whether
LLVM provides some kind of pass or builder which will generate the Control
Dependence Graph?

I think the PostDominanceFrontier analysis was removed from LLVM, but the PostDominatorTree analysis may help:

http://llvm.org/doxygen/structllvm_1_1PostDominatorTree.html

-- John T.

Thank you John.
Actually the opt tool (from LLVM 3.2 version) can generate the needed graphs
(with pass "-domfrontier").
But I just want to surely know is there some pass or builder which can be
integrated somehow so it will be possible directly to generate CDG?

Thank you John.
Actually the opt tool (from LLVM 3.2 version) can generate the needed graphs
(with pass "-domfrontier").
But I just want to surely know is there some pass or builder which can be
integrated somehow so it will be possible directly to generate CDG?

Yes and no. There's isn't a control dependence pass in LLVM per se, but I believe that is primarily because control dependence is very easy to compute with the existing analysis passes in LLVM. With PostDominanceFrontier, it was extremely simple (I think it was calling two methods in the PostDominanceFrontier pass).

It might be slightly more work to compute it with PostDominatorTree, but not significantly. And, IIRC, you'll want to use PostDominatorTree instead of DominatorTree. For control dependence, I believe you essentially flip the CFG upside-down and compute the dominance frontier. Using post dominators instead of dominators does the same thing and is described in the Allen and Kennedy book.

-- John T.

Hi Arsen,
I wrote a pass that computes a control dependence graph as described in Ferrante et al’s “The Program Dependence Graph and Its Use in Optimization.” It is available at https://github.com/thinkmoore/llvm-analysis.

Thank all of you