[LLVMdev] Inferring dependencies in phi instructions

[Anirudh Sivaraman]

On Tue, Jun 30, 2015 at 3:51 AM, Evgeny Astigeevich
<evgeny.astigeevich at arm.com> wrote:
> 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.

Thank you for spelling this out in so much detail. This makes much
more sense to me now. I 'll try using this approach when constructing
the control dependence graph.

Anirudh

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