Thank you, Bill. Seems to be better. Anyway...Is there a way I can do what you showed for me? Thanks, Seung J. Lee ---- Original message ---->Date: Sat, 26 Jan 2008 22:10:01 -0800 >From: Bill Wendling <isanbard at gmail.com> >Subject: Re: [LLVMdev] Question to Chris >To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu> > >On Jan 26, 2008, at 9:48 AM, Seung Jae Lee wrote: > >> Dear Dr.Lattner >> >> Hello, Dr.Lattner. >> You may find your reply at http://lists.cs.uiuc.edu/pipermail/ >> llvmdev/2007-August/010479.html and other your replies to me right >> up and down at the list. >> You had suggested me to read the "structural analysis" section in >> Muchnick's book. >> Thank you for this. I bought and read it, which was very helpful >> but... >> I still don't have any idea about how to deal with phi-nodes in >> LLVM Intermediate Representation systemically to resolve my problem. >> In order to construct high-level 'for' from LLVM IR, it is critical >> to move Phi-nodes hither and thither or split them but... I can't >> find any material about this from anywhere. >> So could you reply to me briefly about this if you are fine? >> >> Thank you very much and have a good day. >> Seung J. Lee >> >> P.S: In fact, I am thinking about an alternative way for doing this >> by using reverse engineering. Now that LLVM IR has phi-nodes which >> is tricky to handle for this issue, I just slightly changed my way >> to use the machine assembly which does not have phi-nodes. Already >> someone (like Doug Simon in Sun microsystems) got high-level C code >> "which is quite same with the original including loops, >> conditionals and so on" from Sparc assembly by using de-compilation. >> Therefore, if you reply "it is difficult to handle phi-nodes for >> constructing high-level loops", I am almost ready to go the other >> way using the machine assembly. >> Anyway, could you shed some lights on me? >> Thank you very much > >Hi Seung, > >It would appear to me that you would simply need to perform a >modified form of "un-SSAification". For instance, if you have PHI >nodes whose values come from the back edges of a loop, then you could >perhaps store those values to memory and then load them inside of the >loop in place of the PHI node. > >Meta-code: > >BB1: > %v1 = ... > ... > br label %Loop > > >Loop: > %v2 = phi i32 [%v1, %BB1], [%v3, %BB2] > ... > br label %BB2 > > >BB2: > %v3 = ... > br label %Loop > > >into something like: > >Entry: > %ptr = alloca i32 >... >BB1: > %v1 = ... > store i32 %v1, %32* %ptr > ... > br label %Loop > >Loop: > %v2 = load i32* %ptr > ... > br label %BB2 > >BB2: > %v3 = ... > store i32 %v3, i32* %ptr > ... > br label %Loop > >What do you think? > >-bw >_______________________________________________ >LLVM Developers mailing list >LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Seung, If your main problem is identifying loop induction variables (and other linked recurrences which may also be used to index arrays in the loop), then SSA form actually will help you. Here is a very good algorithm for identifying and optimizing such variables using SSA form: Operator Strength Reduction, Keith Cooper, L. Taylor Simpson and Christopher Vick, ACM Transactions on Programming Languages and Systems, 23(5), Sept. 2001. If that's not your main problem, exactly what problem are you having with Phi nodes? --Vikram http://www.cs.uiuc.edu/~vadve http://llvm.org/ On Jan 27, 2008, at 10:50 AM, Seung Jae Lee wrote:> Thank you, Bill. > Seems to be better. > Anyway...Is there a way I can do what you showed for me? > > Thanks, > Seung J. Lee > > ---- Original message ---- >> Date: Sat, 26 Jan 2008 22:10:01 -0800 >> From: Bill Wendling <isanbard at gmail.com> >> Subject: Re: [LLVMdev] Question to Chris >> To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu> >> >> On Jan 26, 2008, at 9:48 AM, Seung Jae Lee wrote: >> >>> Dear Dr.Lattner >>> >>> Hello, Dr.Lattner. >>> You may find your reply at http://lists.cs.uiuc.edu/pipermail/ >>> llvmdev/2007-August/010479.html and other your replies to me right >>> up and down at the list. >>> You had suggested me to read the "structural analysis" section in >>> Muchnick's book. >>> Thank you for this. I bought and read it, which was very helpful >>> but... >>> I still don't have any idea about how to deal with phi-nodes in >>> LLVM Intermediate Representation systemically to resolve my problem. >>> In order to construct high-level 'for' from LLVM IR, it is critical >>> to move Phi-nodes hither and thither or split them but... I can't >>> find any material about this from anywhere. >>> So could you reply to me briefly about this if you are fine? >>> >>> Thank you very much and have a good day. >>> Seung J. Lee >>> >>> P.S: In fact, I am thinking about an alternative way for doing this >>> by using reverse engineering. Now that LLVM IR has phi-nodes which >>> is tricky to handle for this issue, I just slightly changed my way >>> to use the machine assembly which does not have phi-nodes. Already >>> someone (like Doug Simon in Sun microsystems) got high-level C code >>> "which is quite same with the original including loops, >>> conditionals and so on" from Sparc assembly by using de-compilation. >>> Therefore, if you reply "it is difficult to handle phi-nodes for >>> constructing high-level loops", I am almost ready to go the other >>> way using the machine assembly. >>> Anyway, could you shed some lights on me? >>> Thank you very much >> >> Hi Seung, >> >> It would appear to me that you would simply need to perform a >> modified form of "un-SSAification". For instance, if you have PHI >> nodes whose values come from the back edges of a loop, then you could >> perhaps store those values to memory and then load them inside of the >> loop in place of the PHI node. >> >> Meta-code: >> >> BB1: >> %v1 = ... >> ... >> br label %Loop >> >> >> Loop: >> %v2 = phi i32 [%v1, %BB1], [%v3, %BB2] >> ... >> br label %BB2 >> >> >> BB2: >> %v3 = ... >> br label %Loop >> >> >> into something like: >> >> Entry: >> %ptr = alloca i32 >> ... >> BB1: >> %v1 = ... >> store i32 %v1, %32* %ptr >> ... >> br label %Loop >> >> Loop: >> %v2 = load i32* %ptr >> ... >> br label %BB2 >> >> BB2: >> %v3 = ... >> store i32 %v3, i32* %ptr >> ... >> br label %Loop >> >> What do you think? >> >> -bw >> _______________________________________________ >> 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-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080127/c4797ee1/attachment.html>
Hi Seung, It should be fairly straight-forward to do in LLVM. Once you identify the loops, then identify the PHI nodes that you need to convert, then apply the transformation below. The fine details on how to create an instruction and replace one instruction with another are documented in the docs section and in other code. :-) One thing to be careful of, if you convert a variable like I showed, then you need to make sure that it's not used in any other PHI nodes (if it is, then you'll need to perform some other type of transformation). -bw On Jan 27, 2008, at 8:50 AM, Seung Jae Lee wrote:> Thank you, Bill. > Seems to be better. > Anyway...Is there a way I can do what you showed for me? > > Thanks, > Seung J. Lee > > ---- Original message ---- >> Date: Sat, 26 Jan 2008 22:10:01 -0800 >> From: Bill Wendling <isanbard at gmail.com> >> Subject: Re: [LLVMdev] Question to Chris >> To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu> >> >> On Jan 26, 2008, at 9:48 AM, Seung Jae Lee wrote: >> >>> Dear Dr.Lattner >>> >>> Hello, Dr.Lattner. >>> You may find your reply at http://lists.cs.uiuc.edu/pipermail/ >>> llvmdev/2007-August/010479.html and other your replies to me right >>> up and down at the list. >>> You had suggested me to read the "structural analysis" section in >>> Muchnick's book. >>> Thank you for this. I bought and read it, which was very helpful >>> but... >>> I still don't have any idea about how to deal with phi-nodes in >>> LLVM Intermediate Representation systemically to resolve my problem. >>> In order to construct high-level 'for' from LLVM IR, it is critical >>> to move Phi-nodes hither and thither or split them but... I can't >>> find any material about this from anywhere. >>> So could you reply to me briefly about this if you are fine? >>> >>> Thank you very much and have a good day. >>> Seung J. Lee >>> >>> P.S: In fact, I am thinking about an alternative way for doing this >>> by using reverse engineering. Now that LLVM IR has phi-nodes which >>> is tricky to handle for this issue, I just slightly changed my way >>> to use the machine assembly which does not have phi-nodes. Already >>> someone (like Doug Simon in Sun microsystems) got high-level C code >>> "which is quite same with the original including loops, >>> conditionals and so on" from Sparc assembly by using de-compilation. >>> Therefore, if you reply "it is difficult to handle phi-nodes for >>> constructing high-level loops", I am almost ready to go the other >>> way using the machine assembly. >>> Anyway, could you shed some lights on me? >>> Thank you very much >> >> Hi Seung, >> >> It would appear to me that you would simply need to perform a >> modified form of "un-SSAification". For instance, if you have PHI >> nodes whose values come from the back edges of a loop, then you could >> perhaps store those values to memory and then load them inside of the >> loop in place of the PHI node. >> >> Meta-code: >> >> BB1: >> %v1 = ... >> ... >> br label %Loop >> >> >> Loop: >> %v2 = phi i32 [%v1, %BB1], [%v3, %BB2] >> ... >> br label %BB2 >> >> >> BB2: >> %v3 = ... >> br label %Loop >> >> >> into something like: >> >> Entry: >> %ptr = alloca i32 >> ... >> BB1: >> %v1 = ... >> store i32 %v1, %32* %ptr >> ... >> br label %Loop >> >> Loop: >> %v2 = load i32* %ptr >> ... >> br label %BB2 >> >> BB2: >> %v3 = ... >> store i32 %v3, i32* %ptr >> ... >> br label %Loop >> >> What do you think? >> >> -bw >> _______________________________________________ >> 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
Bill, Depending on what Seung's problem is, converting *out* of SSA form may actually be the wrong thing to do. Seung needs to explain exactly problem he is unable solve using SSA form. --Vikram http://www.cs.uiuc.edu/~vadve http://llvm.org/ On Jan 28, 2008, at 1:10 AM, Bill Wendling wrote:> Hi Seung, > > It should be fairly straight-forward to do in LLVM. Once you identify > the loops, then identify the PHI nodes that you need to convert, then > apply the transformation below. The fine details on how to create an > instruction and replace one instruction with another are documented > in the docs section and in other code. :-) One thing to be careful > of, if you convert a variable like I showed, then you need to make > sure that it's not used in any other PHI nodes (if it is, then you'll > need to perform some other type of transformation). > > -bw > > On Jan 27, 2008, at 8:50 AM, Seung Jae Lee wrote: > >> Thank you, Bill. >> Seems to be better. >> Anyway...Is there a way I can do what you showed for me? >> >> Thanks, >> Seung J. Lee >> >> ---- Original message ---- >>> Date: Sat, 26 Jan 2008 22:10:01 -0800 >>> From: Bill Wendling <isanbard at gmail.com> >>> Subject: Re: [LLVMdev] Question to Chris >>> To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu> >>> >>> On Jan 26, 2008, at 9:48 AM, Seung Jae Lee wrote: >>> >>>> Dear Dr.Lattner >>>> >>>> Hello, Dr.Lattner. >>>> You may find your reply at http://lists.cs.uiuc.edu/pipermail/ >>>> llvmdev/2007-August/010479.html and other your replies to me right >>>> up and down at the list. >>>> You had suggested me to read the "structural analysis" section in >>>> Muchnick's book. >>>> Thank you for this. I bought and read it, which was very helpful >>>> but... >>>> I still don't have any idea about how to deal with phi-nodes in >>>> LLVM Intermediate Representation systemically to resolve my >>>> problem. >>>> In order to construct high-level 'for' from LLVM IR, it is critical >>>> to move Phi-nodes hither and thither or split them but... I can't >>>> find any material about this from anywhere. >>>> So could you reply to me briefly about this if you are fine? >>>> >>>> Thank you very much and have a good day. >>>> Seung J. Lee >>>> >>>> P.S: In fact, I am thinking about an alternative way for doing this >>>> by using reverse engineering. Now that LLVM IR has phi-nodes which >>>> is tricky to handle for this issue, I just slightly changed my way >>>> to use the machine assembly which does not have phi-nodes. Already >>>> someone (like Doug Simon in Sun microsystems) got high-level C code >>>> "which is quite same with the original including loops, >>>> conditionals and so on" from Sparc assembly by using de- >>>> compilation. >>>> Therefore, if you reply "it is difficult to handle phi-nodes for >>>> constructing high-level loops", I am almost ready to go the other >>>> way using the machine assembly. >>>> Anyway, could you shed some lights on me? >>>> Thank you very much >>> >>> Hi Seung, >>> >>> It would appear to me that you would simply need to perform a >>> modified form of "un-SSAification". For instance, if you have PHI >>> nodes whose values come from the back edges of a loop, then you >>> could >>> perhaps store those values to memory and then load them inside of >>> the >>> loop in place of the PHI node. >>> >>> Meta-code: >>> >>> BB1: >>> %v1 = ... >>> ... >>> br label %Loop >>> >>> >>> Loop: >>> %v2 = phi i32 [%v1, %BB1], [%v3, %BB2] >>> ... >>> br label %BB2 >>> >>> >>> BB2: >>> %v3 = ... >>> br label %Loop >>> >>> >>> into something like: >>> >>> Entry: >>> %ptr = alloca i32 >>> ... >>> BB1: >>> %v1 = ... >>> store i32 %v1, %32* %ptr >>> ... >>> br label %Loop >>> >>> Loop: >>> %v2 = load i32* %ptr >>> ... >>> br label %BB2 >>> >>> BB2: >>> %v3 = ... >>> store i32 %v3, i32* %ptr >>> ... >>> br label %Loop >>> >>> What do you think? >>> >>> -bw >>> _______________________________________________ >>> 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 > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev