[LLVMdev] Control Dependence Graph builder

[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?

Thanks,
Arsen



--
View this message in context: http://llvm.1065342.n5.nabble.com/Control-Dependence-Graph-builder-tp56687.html
Sent from the LLVM - Dev mailing list archive at Nabble.com.
_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[John Criswell]

On 4/12/13 2:37 PM, Arsen wrote:
> 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.

[Arsen]

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?



--
View this message in context: http://llvm.1065342.n5.nabble.com/Control-Dependence-Graph-builder-tp56687p56689.html

[John Criswell]

On 4/12/13 3:19 PM, Arsen wrote:
> 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.

[Scott Moore]

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.

Cheers,
Scott

[Arsen]

Thank all of you



--
View this message in context: http://llvm.1065342.n5.nabble.com/Control-Dependence-Graph-builder-tp56687p56702.html