[LLVMdev] Inferring dependencies in phi instructions

[Evgeny Astigeevich]

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>