Question to Chris

Project Infrastructure LLVM Dev List Archives
1

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

2

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.

3

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