[LLVMdev] Question to Chris

[Vikram S. Adve]

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>