Anirudh Sivaraman
2015-Jun-29 06:24 UTC
[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
Evgeny Astigeevich
2015-Jun-29 10:16 UTC
[LLVMdev] Inferring dependencies in phi instructions
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
Anirudh Sivaraman
2015-Jun-29 14:22 UTC
[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 Iam> 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 ingeneral,> 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 bevery> 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