On Mon, Jun 29, 2015 at 10:16 AM, Evgeny Astigeevich <Evgeny.Astigeevich at arm.com> wrote:> Hi Anirudh, > > > > I hope these lecture slides about SSA and the dominance frontier will help > you with SSA and control flow analysis: > > > > http://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec04-SSA.pdf > > > > Unfortunately a use of DominanceFrontierBase is deprecated in LLVM. > > > >>Thank you for your response. Going by your definition, x is control >> dependent on y. > >> To extract this control dependency, do I need to maintain path conditions >> for each basic block or can I do something simpler? > >>Also, I feel like this should be a recurring problem. Could you point me to >> any code example that identifies all dependencies (control and data) for phi >> instructions? > > You won’t have any of this problems if you build dominance frontiers in the > reverse CFG (ReverseDominanceFrontiers). >You actually don't even need reverse dominance frontiers, you can do it with a post-dominator tree.
Anirudh Sivaraman
2015-Jun-29 17:57 UTC
[LLVMdev] Inferring dependencies in phi instructions
On Mon, Jun 29, 2015 at 10:22 AM, Daniel Berlin <dberlin at dberlin.org> wrote:> On Mon, Jun 29, 2015 at 10:16 AM, Evgeny Astigeevich > <Evgeny.Astigeevich at arm.com> wrote: >> Hi Anirudh, >> >> >> >> I hope these lecture slides about SSA and the dominance frontier will help >> you with SSA and control flow analysis: >> >> >> >> http://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec04-SSA.pdf >> >> >> >> Unfortunately a use of DominanceFrontierBase is deprecated in LLVM. >> >> >> >>>Thank you for your response. Going by your definition, x is control >>> dependent on y. >> >>> To extract this control dependency, do I need to maintain path conditions >>> for each basic block or can I do something simpler? >> >>>Also, I feel like this should be a recurring problem. Could you point me to >>> any code example that identifies all dependencies (control and data) for phi >>> instructions? >> >> You won’t have any of this problems if you build dominance frontiers in the >> reverse CFG (ReverseDominanceFrontiers). >> > > You actually don't even need reverse dominance frontiers, you can do > it with a post-dominator tree.Thanks for all these responses; they clarify quite a bit. I am still confused though. I don't see how a ReverseDominanceFrontier (or any other method to compute the CDG) helps me solve my problem. Here's a minimal working example: define i32 @foo(i32 %a, i32 %b) #0 { %1 = icmp sgt i32 %a, %b br i1 %1, label %2, label %3 ; <label>:2 ; preds = %0 br label %4 ; <label>:3 ; preds = %0 br label %4 ; <label>:4 ; preds = %3, %2 %r.0 = phi i32 [ %a, %2 ], [ %b, %3 ] ret i32 %r.0 } Here the basic block with label 4 isn't control dependent on basic blocks 0, 2, or 3 by the definition of control dependence (from Appel's book: "We say that a node y is control-dependent on x if from x we can branch to u or v; from u there is a path to exit that avoids y, and from v every path to exit hits y"). Because control _always_ flows from any of basic blocks 0, 2, or 3 to 4, 4 isn't control dependent on either of 0, 2, or 3. This in turn, means that the phi node within basic block 4 isn't control dependent on basic blocks 0, 2, or 3. In this particular case, I know that using the simplifycfg pass solves my problem by converting phi nodes into selects. I would like to know how to handle the general case. Thanks in advance for any advice you may have. Anirudh
Evgeny Astigeevich
2015-Jun-30 10:51 UTC
[LLVMdev] Inferring dependencies in phi instructions
Hi Anirudh, I agree with Daniel. You can use the post-dominator tree. In LLVM you can get it as follows: getAnalysis<PostDominatorTree>() Of course you must specify it in dependencies of your pass: void getAnalysisUsage(AnalysisUsage &AU) const override { ... // some code AU.addRequired<PostDominatorTree>(); ... // some other code } INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) To find all control dependencies the following simple algorithm can be used: 1. Consider all edges <X, Y> such that Y does not post-dominate X (X has more than one successor). 2. Traverse the post-dominator tree bottom-up: B = Y while (B != parent of X in PDT) B is control dependent on X B = parent of B in PDT You can use the following algorithm to find all conditions a phi-function depends on: 1. For each incoming basic block, get all blocks it is control dependent on. Add the incoming block to the set if the parent of the phi-function is control dependent on it. 2. For each found block, get its terminator and find a condition the terminator uses. Let's consider your example: CFG: ---- Entry---- | | v v 2 3 | | ---> 4 <---- PDT: ----4----- | | | v v v 2 3 Entry Edges of interest in CFG: <Entry, 2>, <Entry, 3> (<2, 4> and <3, 4> are not because 4 post-dominates 2 and 3.) The parent of Entry in PDT is 4. We have: - 2 is control dependent on Entry - 3 is control dependent on Entry - 4 is not control dependent on any basic block The phi-function in 4 has incoming blocks: 2 and 3. 2 and 3 are control dependent on Entry. The terminator of entry uses %1. So the phi-function depends on %1. No other conditions are added as 2 and 3 have unconditional jumps. Hope this gives you more understanding of the topic. Kind regards, Evgeny Astigeevich -----Original Message----- From: Anirudh Sivaraman [mailto:sk.anirudh at gmail.com] Sent: 29 June 2015 18:58 To: Daniel Berlin Cc: Evgeny Astigeevich; LLVM Developers Mailing List Subject: Re: [LLVMdev] Inferring dependencies in phi instructions On Mon, Jun 29, 2015 at 10:22 AM, Daniel Berlin <dberlin at dberlin.org> wrote:> On Mon, Jun 29, 2015 at 10:16 AM, Evgeny Astigeevich > <Evgeny.Astigeevich at arm.com> wrote: >> Hi Anirudh, >> >> >> >> I hope these lecture slides about SSA and the dominance frontier will >> help you with SSA and control flow analysis: >> >> >> >> http://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec04-SSA.pdf >> >> >> >> Unfortunately a use of DominanceFrontierBase is deprecated in LLVM. >> >> >> >>>Thank you for your response. Going by your definition, x is control >>>dependent on y. >> >>> To extract this control dependency, do I need to maintain path >>> conditions for each basic block or can I do something simpler? >> >>>Also, I feel like this should be a recurring problem. Could you point >>>me to any code example that identifies all dependencies (control and >>>data) for phi instructions? >> >> You won’t have any of this problems if you build dominance frontiers >> in the reverse CFG (ReverseDominanceFrontiers). >> > > You actually don't even need reverse dominance frontiers, you can do > it with a post-dominator tree.Thanks for all these responses; they clarify quite a bit. I am still confused though. I don't see how a ReverseDominanceFrontier (or any other method to compute the CDG) helps me solve my problem. Here's a minimal working example: define i32 @foo(i32 %a, i32 %b) #0 { %1 = icmp sgt i32 %a, %b br i1 %1, label %2, label %3 ; <label>:2 ; preds = %0 br label %4 ; <label>:3 ; preds = %0 br label %4 ; <label>:4 ; preds = %3, %2 %r.0 = phi i32 [ %a, %2 ], [ %b, %3 ] ret i32 %r.0 } Here the basic block with label 4 isn't control dependent on basic blocks 0, 2, or 3 by the definition of control dependence (from Appel's book: "We say that a node y is control-dependent on x if from x we can branch to u or v; from u there is a path to exit that avoids y, and from v every path to exit hits y"). Because control _always_ flows from any of basic blocks 0, 2, or 3 to 4, 4 isn't control dependent on either of 0, 2, or 3. This in turn, means that the phi node within basic block 4 isn't control dependent on basic blocks 0, 2, or 3. In this particular case, I know that using the simplifycfg pass solves my problem by converting phi nodes into selects. I would like to know how to handle the general case. Thanks in advance for any advice you may have. Anirudh