llvm dev - Jan 2008 - [LLVMdev] Question to Chris

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

On Jan 26, 2008, at 9:48 AM, Seung Jae Lee wrote:
> In order to construct high-level 'for'
I'd point you to things like:

   http://www.itee.uq.edu.au/~cristina/dcc.html

and other things that google could find with terms like decompilation,  
reverse engineering, reengineering and so one.  These should be able  
to provide a back drop to the problem.  Curious, a quick 5 second  
search turns up:

   http://boomerang.sourceforge.net/

in which they claim to use ssa to help out. You can study how they  
raise code back up into for statements and how the code works.

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