llvm dev - Jun 2015 - [LLVMdev] Inferring dependencies in phi instructions

On Jun 29, 2015 3:16 AM, "Evgeny Astigeevich" <evgeny.astigeevich
at arm.com>
wrote:
>
> Hi Anirudh,
>
> 'x' has a control dependency on 'y' because the value
assigned to 'x'
> depends on a path selected. This dependency can be converted into a data
> dependency by means of a 'select' instruction because the control
flow is
> simple.
> What is the problem with using phi-functions in DFG? Yes they require more
> work to find out what they depend on.
>
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?
> Kind regards,
> Evgeny Astigeevich
>
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu] On
> Behalf Of Anirudh Sivaraman
> Sent: 29 June 2015 07:25
> To: LLVM Developers Mailing List
> Subject: [LLVMdev] Inferring dependencies in phi instructions
>
> I am trying to infer data dependencies using LLVM's def-use chains and
I
am
> having trouble dealing with 'phi' instructions. Specifically,
>
> If I am given the code snippet:
>
> int foo() {
>   int y = 1;
>   int x;
>   if (y) {
>     x = 2;
>   } else {
>     x = 3;
>   }
>   return x;
> }
>
> Here, x has a data dependence on y (not control because x is assigned in
> both halves), but LLVM expresses 'x' as: %x.0 = phi i32 [ 2, %2 ],
[ 3,
%3 ]
> using phi-nodes, omitting the dependence on y.
>
> If I write the function as:
>
> int foo() {
>   int y = 1;
>   int x = y ? 2 : 3;
>   return x;
> },
>
> the dependencies work out alright because LLVM now uses a select
> instruction, where the dependence on y is explicit:
>
> %y = select i1 %x, i32 2, i32 3
>
> In general, I don't think I can convert phi nodes into select
statements
> (because a phi node can refer to values from more than two paths in
general,
> while select statements permit only two options, one each for a true and a
> false branch). Any thoughts on how this is handled in practice would be
very
> helpful.
>
> Anirudh
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150629/1aa1a69a/attachment.html>

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).
Then for a phi-function you get its basic block A and for the basic block A you
get RDF(A). Your phi-function depends on conditions in basic blocks from RDF(A).

Kind regards,
Evgeny Astigeevich


From: Anirudh Sivaraman [mailto:sk.anirudh at gmail.com]
Sent: 29 June 2015 15:22
To: Evgeny Astigeevich
Cc: LLVM Developers Mailing List
Subject: RE: [LLVMdev] Inferring dependencies in phi instructions


On Jun 29, 2015 3:16 AM, "Evgeny Astigeevich" <evgeny.astigeevich
at arm.com<mailto:evgeny.astigeevich at arm.com>>
wrote:
>
> Hi Anirudh,
>
> 'x' has a control dependency on 'y' because the value
assigned to 'x'
> depends on a path selected. This dependency can be converted into a data
> dependency by means of a 'select' instruction because the control
flow is
> simple.
> What is the problem with using phi-functions in DFG? Yes they require more
> work to find out what they depend on.
>
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?
> Kind regards,
> Evgeny Astigeevich
>
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu<mailto:llvmdev-bounces at
cs.uiuc.edu> [mailto:llvmdev-bounces at cs.uiuc.edu<mailto:llvmdev-bounces
at cs.uiuc.edu>] On
> Behalf Of Anirudh Sivaraman
> Sent: 29 June 2015 07:25
> To: LLVM Developers Mailing List
> Subject: [LLVMdev] Inferring dependencies in phi instructions
>
> I am trying to infer data dependencies using LLVM's def-use chains and
I am
> having trouble dealing with 'phi' instructions. Specifically,
>
> If I am given the code snippet:
>
> int foo() {
>   int y = 1;
>   int x;
>   if (y) {
>     x = 2;
>   } else {
>     x = 3;
>   }
>   return x;
> }
>
> Here, x has a data dependence on y (not control because x is assigned in
> both halves), but LLVM expresses 'x' as: %x.0 = phi i32 [ 2, %2 ],
[ 3, %3 ]
> using phi-nodes, omitting the dependence on y.
>
> If I write the function as:
>
> int foo() {
>   int y = 1;
>   int x = y ? 2 : 3;
>   return x;
> },
>
> the dependencies work out alright because LLVM now uses a select
> instruction, where the dependence on y is explicit:
>
> %y = select i1 %x, i32 2, i32 3
>
> In general, I don't think I can convert phi nodes into select
statements
> (because a phi node can refer to values from more than two paths in
general,
> while select statements permit only two options, one each for a true and a
> false branch). Any thoughts on how this is handled in practice would be
very
> helpful.
>
> Anirudh
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu<mailto:LLVMdev at cs.uiuc.edu>        
http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
-- IMPORTANT NOTICE: The contents of this email and any attachments are
confidential and may also be privileged. If you are not the intended recipient,
please notify the sender immediately and do not disclose the contents to any
other person, use it for any purpose, or store or copy the information in any
medium. Thank you.

ARM Limited, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ, Registered
in England & Wales, Company No: 2557590
ARM Holdings plc, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ,
Registered in England & Wales, Company No: 2548782
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150629/4fad63c6/attachment.html>

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.