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
Anirudh Sivaraman
2015-Jun-29 14:57 UTC
[LLVMdev] Inferring dependencies in phi instructions
On Mon, Jun 29, 2015 at 7:23 AM, John Criswell <jtcriswel at gmail.com> wrote:> 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). >I tried this, but how do I express the resulting predicated instructions in llvm's IR? For instance, X = a + b becomes X = if (path_condition) (a + b) I couldn't find an appropriate instruction type for predicated instructions.> If you need to find control dependencies, you can find them easily using > LLVM's ReverseDominanceFrontier pass. >Ok, I didn't know about this and implemented the cdg on my own. However, regardless of how the cdg is implemented, I don't think it captures control dependencies in phi instructions?> 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 >
> On Jun 29, 2015, at 7:57 AM, Anirudh Sivaraman <sk.anirudh at gmail.com> wrote: > > On Mon, Jun 29, 2015 at 7:23 AM, John Criswell <jtcriswel at gmail.com <mailto:jtcriswel at gmail.com>> wrote: >> 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). >> > > I tried this, but how do I express the resulting predicated > instructions in llvm's IR? For instance, > > X = a + b > > becomes > > X = if (path_condition) (a + b) > > I couldn't find an appropriate instruction type for predicated instructions.I believe you’re looking for the “select” IR instruction. —escha -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150629/33635db2/attachment.html>
On 6/29/15 9:57 AM, Anirudh Sivaraman wrote:> On Mon, Jun 29, 2015 at 7:23 AM, John Criswell <jtcriswel at gmail.com> wrote: >> 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). >> > I tried this, but how do I express the resulting predicated > instructions in llvm's IR? For instance, > > X = a + b > > becomes > > X = if (path_condition) (a + b) > > I couldn't find an appropriate instruction type for predicated instructions.The "select" instruction you mentioned earlier is what you want.> >> If you need to find control dependencies, you can find them easily using >> LLVM's ReverseDominanceFrontier pass. >> > Ok, I didn't know about this and implemented the cdg on my own. > However, regardless of how the cdg is implemented, I don't think it > captures control dependencies in phi instructions?Control dependence is usually computed on basic block granularity (e.g., basic block B is control-dependent on a conditional branch at the end of basic block A). Given that basic block B is control-dependent on basic block A, then all the phi-nodes at the beginning of basic block B are control-dependent on the conditional branch at the end of basic block A. If you're not familiar with the DominanceFrontier algorithm for computing control-dependence, I recommend you read it. You can find it described in the Allen/Kennedy book as well as the paper "Efficiently Computing Static Single Assignment Form and the Control-Dependence Graph." Regards, John Criswell> >> 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 >>-- John Criswell Assistant Professor Department of Computer Science, University of Rochester http://www.cs.rochester.edu/u/criswell