[LLVMdev] Inferring dependencies in phi instructions
Anirudh Sivaraman
sk.anirudh at gmail.com
Mon Jun 29 10:57:35 PDT 2015
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
More information about the llvm-dev
mailing list