<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Seung,<div><br class="webkit-block-placeholder"></div><div>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:</div><div><br class="webkit-block-placeholder"></div><div><span class="Apple-style-span" style="font-family: Times; font-size: 14px; "><a href="http://llvm.cs.uiuc.edu/~vadve/CS526/public_html/html/Papers/OSR.toplas01.cooper.pdf">Operator Strength Reduction,</a> Keith Cooper, L. Taylor Simpson and Christopher Vick, <i>ACM Transactions on Programming Languages and Systems</i>, 23(5), Sept. 2001.</span></div><div><div apple-content-edited="true"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 11px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 11px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="font-family: Helvetica; "><br class="webkit-block-placeholder"></div><div style="font-family: Helvetica; "><span class="Apple-style-span" style="font-family: Arial; font-size: 12px; ">If that's not your main problem, exactly what problem are you having with Phi nodes? </span></div><div style="font-family: Helvetica; "><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br class="webkit-block-placeholder"></span></font></div><div style="font-family: Helvetica; "><span class="Apple-style-span" style="font-family: Helvetica; ">--Vikram</span></div><div style="font-family: Helvetica; "><span class="Apple-style-span" style="font-family: Helvetica; "><a href="http://www.cs.uiuc.edu/~vadve">http://www.cs.uiuc.edu/~vadve</a></span></div><div style="font-family: Helvetica; "><span class="Apple-style-span" style="font-family: Helvetica; "><a href="http://llvm.org/">http://llvm.org/</a></span></div><br class="Apple-interchange-newline"></span><br class="Apple-interchange-newline"></div></span> </div><br><div><div>On Jan 27, 2008, at 10:50 AM, Seung Jae Lee wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div>Thank you, Bill.<br>Seems to be better.<br>Anyway...Is there a way I can do what you showed for me?<br><br>Thanks,<br>Seung J. Lee<br><br>---- Original message ----<br><blockquote type="cite">Date: Sat, 26 Jan 2008 22:10:01 -0800<br></blockquote><blockquote type="cite">From: Bill Wendling <<a href="mailto:isanbard@gmail.com">isanbard@gmail.com</a>><br></blockquote><blockquote type="cite">Subject: Re: [LLVMdev] Question to Chris<br></blockquote><blockquote type="cite">To: LLVM Developers Mailing List <<a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a>><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">On Jan 26, 2008, at 9:48 AM, Seung Jae Lee wrote:<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><blockquote type="cite">Dear Dr.Lattner<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite"><br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">Hello, Dr.Lattner.<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">You may find your reply at <a href="http://lists.cs.uiuc.edu/pipermail/">http://lists.cs.uiuc.edu/pipermail/</a><br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">llvmdev/2007-August/010479.html and other your replies to me right<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">up and down at the list.<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">You had suggested me to read the "structural analysis" section in<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">Muchnick's book.<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">Thank you for this. I bought and read it, which was very helpful<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">but...<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">I still don't have any idea about how to deal with phi-nodes in<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">LLVM Intermediate Representation systemically to resolve my problem.<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">In order to construct high-level 'for' from LLVM IR, it is critical<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">to move Phi-nodes hither and thither or split them but... I can't<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">find any material about this from anywhere.<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">So could you reply to me briefly about this if you are fine?<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite"><br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">Thank you very much and have a good day.<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">Seung J. Lee<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite"><br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">P.S: In fact, I am thinking about an alternative way for doing this<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">by using reverse engineering. Now that LLVM IR has phi-nodes which<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">is tricky to handle for this issue, I just slightly changed my way<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">to use the machine assembly which does not have phi-nodes. Already<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">someone (like Doug Simon in Sun microsystems) got high-level C code<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">"which is quite same with the original including loops,<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">conditionals and so on" from Sparc assembly by using de-compilation.<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">Therefore, if you reply "it is difficult to handle phi-nodes for<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">constructing high-level loops", I am almost ready to go the other<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">way using the machine assembly.<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">Anyway, could you shed some lights on me?<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">Thank you very much<br></blockquote></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Hi Seung,<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">It would appear to me that you would simply need to perform a<br></blockquote><blockquote type="cite">modified form of "un-SSAification". For instance, if you have PHI<br></blockquote><blockquote type="cite">nodes whose values come from the back edges of a loop, then you could<br></blockquote><blockquote type="cite">perhaps store those values to memory and then load them inside of the<br></blockquote><blockquote type="cite">loop in place of the PHI node.<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Meta-code:<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">BB1:<br></blockquote><blockquote type="cite"> %v1 = ...<br></blockquote><blockquote type="cite"> ...<br></blockquote><blockquote type="cite"> br label %Loop<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Loop:<br></blockquote><blockquote type="cite"> %v2 = phi i32 [%v1, %BB1], [%v3, %BB2]<br></blockquote><blockquote type="cite"> ...<br></blockquote><blockquote type="cite"> br label %BB2<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">BB2:<br></blockquote><blockquote type="cite"> %v3 = ...<br></blockquote><blockquote type="cite"> br label %Loop<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">into something like:<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Entry:<br></blockquote><blockquote type="cite"> %ptr = alloca i32<br></blockquote><blockquote type="cite">...<br></blockquote><blockquote type="cite">BB1:<br></blockquote><blockquote type="cite"> %v1 = ...<br></blockquote><blockquote type="cite"> store i32 %v1, %32* %ptr<br></blockquote><blockquote type="cite"> ...<br></blockquote><blockquote type="cite"> br label %Loop<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Loop:<br></blockquote><blockquote type="cite"> %v2 = load i32* %ptr<br></blockquote><blockquote type="cite"> ...<br></blockquote><blockquote type="cite"> br label %BB2<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">BB2:<br></blockquote><blockquote type="cite"> %v3 = ...<br></blockquote><blockquote type="cite"> store i32 %v3, i32* %ptr<br></blockquote><blockquote type="cite"> ...<br></blockquote><blockquote type="cite"> br label %Loop<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">What do you think?<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">-bw<br></blockquote><blockquote type="cite">_______________________________________________<br></blockquote><blockquote type="cite">LLVM Developers mailing list<br></blockquote><blockquote type="cite">LLVMdev@cs.uiuc.edu <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br></blockquote><blockquote type="cite"><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></blockquote>_______________________________________________<br>LLVM Developers mailing list<br>LLVMdev@cs.uiuc.edu <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></div></blockquote></div><br></div></body></html>