llvm dev - Jun 2015 - [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

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.

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

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>

On 6/29/15 5:16 AM, Evgeny Astigeevich 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.
Just an FYI, there is an optimization called "If-Conversion" which 
transforms control dependencies to data dependencies; it is discussed in 
the Allen and Kennedy book ("Optimizing Compilers for Modern 
Architectures" in Chapter 6 or 7,  I think).

If you need to find control dependencies, you can find them easily using 
LLVM's ReverseDominanceFrontier pass.

Regards,

John Criswell
> What is the problem with using phi-functions in DFG? Yes they require more
> work to find out what they depend on.
>
> 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
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell