Question to Chris

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
18 messages Options
Reply | Threaded
Open this post in threaded view
|

Question to Chris

Seung Jae Lee
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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Mike Stump
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.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Seung Jae Lee
In reply to this post by Seung Jae Lee
Thank you for this reply.
However, I've already read this thesis. (Mr. Doug Simon in Sun microsystems I mentioned was her student.)
This is a quite good article for reverse engineering but this is only useful for my alternative way which is trying to derive HL code from a machine assembly.
This thesis is a little bit old before SSA form becomes quite popular so does not deal with any PHI function.
For this reason, I can't get any useful info for constructing loops from LLVM IR.

Anyway, thank you for your concerns.
Seung J. Lee


---- Original message ----

>Date: Sat, 26 Jan 2008 15:10:41 -0800
>From: Mike Stump <[hidden email]>  
>Subject: Re: [LLVMdev] Question to Chris  
>To: LLVM Developers Mailing List <[hidden email]>
>
>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.
>_______________________________________________
>LLVM Developers mailing list
>[hidden email]         http://llvm.cs.uiuc.edu
>http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Bill Wendling
In reply to this post by Seung Jae Lee
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
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Seung Jae Lee
In reply to this post by Seung Jae Lee
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 <[hidden email]>  
>Subject: Re: [LLVMdev] Question to Chris  
>To: LLVM Developers Mailing List <[hidden email]>
>
>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
>[hidden email]         http://llvm.cs.uiuc.edu
>http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: 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



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 <[hidden email]>
Subject: Re: [LLVMdev] Question to Chris
To: LLVM Developers Mailing List <[hidden email]>

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
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Bill Wendling
In reply to this post by Seung Jae Lee
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 <[hidden email]>
>> Subject: Re: [LLVMdev] Question to Chris
>> To: LLVM Developers Mailing List <[hidden email]>
>>
>> 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
>> [hidden email]         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Vikram S. Adve
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 <[hidden email]>
>>> Subject: Re: [LLVMdev] Question to Chris
>>> To: LLVM Developers Mailing List <[hidden email]>
>>>
>>> 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
>>> [hidden email]         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>> _______________________________________________
>> LLVM Developers mailing list
>> [hidden email]         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Bill Wendling
On Jan 28, 2008 7:39 AM, Vikram S. Adve <[hidden email]> wrote:
> 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.
>
Indeed. But I was just going on what he'd told us. :-) It's up to him
to do what's best for his program.

-bw
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Seung Jae Lee
In reply to this post by Seung Jae Lee
Dear Prof.Adve and Bill,

I deeply appreciate your comments and concerns.
(Please forgive my late response. I've tried some more cases to make this issue)

As Prof.Adve mentioned, I need to explain exactly what my problem is, but I have no good ability that I can explain it in this plain text space.

For this reason, I made a .pdf file and linked it as follows:

https://netfiles.uiuc.edu/lee225/www/MakingLoops.pdf

Would you please explain to me how I can access to this problem in a better way if you can figure out?

Once again, I really appreciate your time and favor, Bill and Prof.Adve.

Truly yours,
Seung J. Lee


---- Original message ----

>Date: Mon, 28 Jan 2008 09:39:52 -0600
>From: "Vikram S. Adve" <[hidden email]>  
>Subject: Re: [LLVMdev] Question to Chris  
>To: LLVM Developers Mailing List <[hidden email]>
>
>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/
>
>
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Tanya Lattner-2
Ok, here are a few suggestions and comments:

1) LLVM has the capabilities to do everything that you are trying to  
re-implement.
2) Have you looked at the C backend? It recreates loops. It may not  
create "for" loops but you can hack on it to do that.
3) The way you are converting out of SSA is wrong. You will suffer  
from lost copies. You should look at using demotePHI(). see include/
llvm/Transforms/Utils/Local.h
4) LLVM will  compute your trip counts for you, use LoopInfo. You  
need to be in SSA form to do this.

-Tanya

On Feb 1, 2008, at 11:51 PM, Seung Jae Lee wrote:

> Dear Prof.Adve and Bill,
>
> I deeply appreciate your comments and concerns.
> (Please forgive my late response. I've tried some more cases to  
> make this issue)
>
> As Prof.Adve mentioned, I need to explain exactly what my problem  
> is, but I have no good ability that I can explain it in this plain  
> text space.
>
> For this reason, I made a .pdf file and linked it as follows:
>
> https://netfiles.uiuc.edu/lee225/www/MakingLoops.pdf
>
> Would you please explain to me how I can access to this problem in  
> a better way if you can figure out?
>
> Once again, I really appreciate your time and favor, Bill and  
> Prof.Adve.
>
> Truly yours,
> Seung J. Lee
>
>
> ---- Original message ----
>> Date: Mon, 28 Jan 2008 09:39:52 -0600
>> From: "Vikram S. Adve" <[hidden email]>
>> Subject: Re: [LLVMdev] Question to Chris
>> To: LLVM Developers Mailing List <[hidden email]>
>>
>> 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/
>>
>>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Mike Stump
In reply to this post by Seung Jae Lee
On Feb 1, 2008, at 11:51 PM, Seung Jae Lee wrote:
> As Prof.Adve mentioned, I need to explain exactly what my problem  
> is, but I have no good ability that I can explain it in this plain  
> text space.

Let me rephrase your question for you.  You can then see the right  
question, and the answer for it.

The question is, why is, why can't I change:

   bb8:
     sum_1 = i_0_pn + sum_0_pn;
     br bool %exitcond, label %bb10, label %bb3

into

   bb8:
     br bool %exitcond, label %bb10, label %bb3
     sum_1 = i_0_pn + sum_0_pn;

?

The answer is, because that is an invalid transform.

   A:
     B;
     C;

has to be transformed into:

     B;
   A:
     C;

(where the motion of B is copy it to the other side of all control  
flows into A)

When you do this, you'll notice you get:

$ cat t.c
int foo() {
   unsigned indvar_next27, indvar_next;
   int sum_1, sum_0_pn, i_0_pn;
   //entry:
   unsigned indvar26 = 0;
   int sum_0_pn_ph = 0;
   //brlabel %bb8_outer
   //bb8_outer:
   for (indvar_next27=0; indvar_next27 != 10; ){
     int i_0_0_ph = (int) indvar26;
     unsigned indvar= 0;
     int sum_0_pn = sum_0_pn_ph;
     int i_0_pn = i_0_0_ph;
     //brlabel %bb8
     //bb8:
     sum_1 = i_0_pn + sum_0_pn;                           /* LOOK HERE  
*/
     for (;indvar!=3;){
       //%exitcond= setequint%indvar, 3
       //brbool %exitcond, label %bb10, label %bb3
       //bb3:
       indvar_next= indvar+ 1;
       indvar= indvar_next;
       sum_0_pn = sum_1;
       i_0_pn = 2;
       sum_1 = i_0_pn + sum_0_pn;                         /* LOOK HERE  
*/
       //brlabel %bb8
     }
     //bb10:
     indvar_next27 = indvar26 + 1;
     //%exitcond28 = setequint%indvar_next27, 10
     indvar26 = indvar_next27;
     sum_0_pn_ph = sum_1;
     //brbool %exitcond28, label %bb16, label %bb8_outer
   }
   //bb16:
   return sum_1;
}

int main() {
   printf("%d\n", foo());
}
$ gcc t.c
t.c: In function ‘main’:
t.c:40: warning: incompatible implicit declaration of built-in  
function ‘printf’
$ ./a.out
105

The cost of the .pdf file outweighed the benefit for me.  I can see  
the pretty graphs in the straight text code.  If you want to help me  
see them further, just indent.

The short answer is you can't guess at valid transforms.  You have to  
know they are valid, or prove the are valid.

The only way to get:

for (;C;) {
   S
}

is to transform:

top:
if (!C) goto end;
   S
goto top;
end:

into it.  If you have any other form, it is wrong to transform into  
it.  You _must_transform into the form just above first, and then that  
form goes into the for statement.

At the end of the day, you have a set of valid transforms, each one of  
which you can talk about and audit separately.  If you have any bugs,  
they are never in the valid transforms, and the invalid ones stand out  
to people skilled in the art.

So, if you had written down the transform you were using, we could  
have identified it.  You didn't, so, we could not.

I didn't check your other loop for correctness, or any of the other  
implied transforms that you used for correctness. If you want to  
ensure it is correct, you can run large amount of code through it and  
check the results (I'd call that the industrial approach) and hope it  
is approximately right, or, you have to reason about each and every  
transform you're using and hopefully even prove each one.  The latter  
approach I'd call the academic approach.  :-)

You're splitting and moving phi nodes seems reasonable.

The transform of:

   top:
     S;
     goto top;

into

   for (;;) {
     S;
   }

is valid.  What isn't valid is putting the induction variable into the  
condition slot and calling it done.  You must first transform it into  
the form given above.  To do that, you have to use other transforms,  
each one of which you should write down and list and prove is valid.

If you want us to audit each transform for you, write them all down,  
one by one.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Wojciech Matyjewicz
In reply to this post by Tanya Lattner-2
Seung,

> 3) The way you are converting out of SSA is wrong. You will suffer  
> from lost copies. You should look at using demotePHI(). see include/
> llvm/Transforms/Utils/Local.h

Using demotePHI() to remove PHI nodes should be the easiest way.
However, if you want to keep values in registers, you must take into
account the problem mentioned above, and also the "swap problem". You
might take a look at this article, for example:
http://www.cs.ucsb.edu/~ckrintz/papers/spe98-ssaconstruct-deconstruct.pdf.gz
to see when these problems appear and how to deal with them. If you
address these issues, I think, your algorithm to remove PHI nodes should
be okay.

-Wojtek

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Wojciech Matyjewicz
In reply to this post by Seung Jae Lee
Seung,

> Would you please explain to me how I can access to this problem in a better way if you can figure out?

Here are my thoughts on your first question: "how to make it count
correctly for the reconstruction of loops?". I believe it can't be done
for an arbitrary loop. However, IIRC from previous posts your loops are
simple - for example: they don't contain any breaks, gotos. I think,
your reconstruction could be done for two forms of loops that are very
common:

1) rotated canonical loop (bb8.outer in your example):
The loop has only one backedge, and an induction variable counting from
0 with step 1. The only basic block that branches out of the loop (so
called, exiting block) is the backedge.

header:
  %i = phi [ 0, %preheader ], [ %i.next, %body ]
  ...
  br label %body ;%header and %body may be the same block

body:
  ...
  %i.next = add %i, 1
  %c = seteq %i.next, %n
  br %c, label %exit, label %header

exit:
  ...

The loop iteration count is %n. In this case, it means that _every_
basic block is executed %n times. Your current version of reconstruction
seems to be okay for loops in this form.

2) unrotated canonical loop (bb8 in your example):
The loop has only one backedge and an induction variable counting from 0
with step 1. The only basic block that branches out of the loop is the
loop header.

header:
  %i = phi [ 0, %preheader ], [ %i.next, %body ]
  ...
  %c = seteq %i, %n
  br %c, label %exit, label %body

body:
  ...
  %i.next = add %i, 1
  br label %header

exit:
  ...

The loop iteration count is also %n. However, this time it means that
the loop header is executed %n times, while the rest of blocks - %n-1
times. The reconstruction should take it into account. For example, it
could make a "for" loop from all loop basic blocks setting the iteration
count to %n-1, and then insert a copy of the loop header with %i==%n
after the "for".

I also suggest taking look at the LoopInfo pass. It has many useful
methods to analyze loops. To determine the loop iteration count you may
use the ScalarEvolution pass as well.

-Wojtek
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Seung Jae Lee
In reply to this post by Seung Jae Lee
I appreciate your suggestions, some follow-up questions though....

>1) LLVM has the capabilities to do everything that you are trying to  
>re-implement.
>2) Have you looked at the C backend? It recreates loops. It may not  
>create "for" loops but you can hack on it to do that.

I wonder if you mean "goto elimination technique" by Ana Maria Erosa ( http://citeseer.ist.psu.edu/317208.html ) for this?

>3) The way you are converting out of SSA is wrong. You will suffer  
>from lost copies. You should look at using demotePHI(). see include/
>llvm/Transforms/Utils/Local.h

I use LLVM 1.9 where I can't find demotePHI(). Is it a function available at later versions?

>4) LLVM will  compute your trip counts for you, use LoopInfo. You  
>need to be in SSA form to do this.
>
>-Tanya
>

Do you mean -loops pass, right?

Thank you in advance.

Best regards,
Seung
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Seung Jae Lee
In reply to this post by Seung Jae Lee
Thank you for this comment, Mike.
So... your suggestion is to make a valid transform for each loop like:

>for (;C;) {
>   S
>}
>
>is to transform:
>
>top:
>if (!C) goto end;
>   S
>goto top;
>end:

For now, my code is incomplete so not ready to present for audit yet but I hope it asap.

In fact, I couldn't understand what you said:

>The cost of the .pdf file outweighed the benefit for me.  I can see  
>the pretty graphs in the straight text code.  If you want to help me  
>see them further, just indent.

Forgive my poor English. What did you mean by that?

Thanks,
Seung


---- Original message ----

>Date: Sat, 2 Feb 2008 11:31:46 -0800
>From: Mike Stump <[hidden email]>  
>Subject: Re: [LLVMdev] Question to Chris  
>To: LLVM Developers Mailing List <[hidden email]>
>
>On Feb 1, 2008, at 11:51 PM, Seung Jae Lee wrote:
>> As Prof.Adve mentioned, I need to explain exactly what my problem  
>> is, but I have no good ability that I can explain it in this plain  
>> text space.
>
>Let me rephrase your question for you.  You can then see the right  
>question, and the answer for it.
>
>The question is, why is, why can't I change:
>
>   bb8:
>     sum_1 = i_0_pn + sum_0_pn;
>     br bool %exitcond, label %bb10, label %bb3
>
>into
>
>   bb8:
>     br bool %exitcond, label %bb10, label %bb3
>     sum_1 = i_0_pn + sum_0_pn;
>
>?
>
>The answer is, because that is an invalid transform.
>
>   A:
>     B;
>     C;
>
>has to be transformed into:
>
>     B;
>   A:
>     C;
>
>(where the motion of B is copy it to the other side of all control  
>flows into A)
>
>When you do this, you'll notice you get:
>
>$ cat t.c
>int foo() {
>   unsigned indvar_next27, indvar_next;
>   int sum_1, sum_0_pn, i_0_pn;
>   //entry:
>   unsigned indvar26 = 0;
>   int sum_0_pn_ph = 0;
>   //brlabel %bb8_outer
>   //bb8_outer:
>   for (indvar_next27=0; indvar_next27 != 10; ){
>     int i_0_0_ph = (int) indvar26;
>     unsigned indvar= 0;
>     int sum_0_pn = sum_0_pn_ph;
>     int i_0_pn = i_0_0_ph;
>     //brlabel %bb8
>     //bb8:
>     sum_1 = i_0_pn + sum_0_pn;                           /* LOOK HERE  
>*/
>     for (;indvar!=3;){
>       //%exitcond= setequint%indvar, 3
>       //brbool %exitcond, label %bb10, label %bb3
>       //bb3:
>       indvar_next= indvar+ 1;
>       indvar= indvar_next;
>       sum_0_pn = sum_1;
>       i_0_pn = 2;
>       sum_1 = i_0_pn + sum_0_pn;                         /* LOOK HERE  
>*/
>       //brlabel %bb8
>     }
>     //bb10:
>     indvar_next27 = indvar26 + 1;
>     //%exitcond28 = setequint%indvar_next27, 10
>     indvar26 = indvar_next27;
>     sum_0_pn_ph = sum_1;
>     //brbool %exitcond28, label %bb16, label %bb8_outer
>   }
>   //bb16:
>   return sum_1;
>}
>
>int main() {
>   printf("%d\n", foo());
>}
>$ gcc t.c
>t.c: In function ‘main’:
>t.c:40: warning: incompatible implicit declaration of built-in  
>function ‘printf’
>$ ./a.out
>105
>
>The cost of the .pdf file outweighed the benefit for me.  I can see  
>the pretty graphs in the straight text code.  If you want to help me  
>see them further, just indent.
>
>The short answer is you can't guess at valid transforms.  You have to  
>know they are valid, or prove the are valid.
>
>The only way to get:
>
>for (;C;) {
>   S
>}
>
>is to transform:
>
>top:
>if (!C) goto end;
>   S
>goto top;
>end:
>
>into it.  If you have any other form, it is wrong to transform into  
>it.  You _must_transform into the form just above first, and then that  
>form goes into the for statement.
>
>At the end of the day, you have a set of valid transforms, each one of  
>which you can talk about and audit separately.  If you have any bugs,  
>they are never in the valid transforms, and the invalid ones stand out  
>to people skilled in the art.
>
>So, if you had written down the transform you were using, we could  
>have identified it.  You didn't, so, we could not.
>
>I didn't check your other loop for correctness, or any of the other  
>implied transforms that you used for correctness. If you want to  
>ensure it is correct, you can run large amount of code through it and  
>check the results (I'd call that the industrial approach) and hope it  
>is approximately right, or, you have to reason about each and every  
>transform you're using and hopefully even prove each one.  The latter  
>approach I'd call the academic approach.  :-)
>
>You're splitting and moving phi nodes seems reasonable.
>
>The transform of:
>
>   top:
>     S;
>     goto top;
>
>into
>
>   for (;;) {
>     S;
>   }
>
>is valid.  What isn't valid is putting the induction variable into the  
>condition slot and calling it done.  You must first transform it into  
>the form given above.  To do that, you have to use other transforms,  
>each one of which you should write down and list and prove is valid.
>
>If you want us to audit each transform for you, write them all down,  
>one by one.
>_______________________________________________
>LLVM Developers mailing list
>[hidden email]         http://llvm.cs.uiuc.edu
>http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Seung Jae Lee
In reply to this post by Seung Jae Lee
Hello, Wojtek.
I owe much to you. Thank you.
My HL code should be simple without any 'goto','break' and so on.
Simple as just loops with 'for' and 'if's inside it, so your comment looks helpful.
I'll try.
Just one thing which concerning me is demotePHI() I couldn't find it in 1.9 so seems to me another installation of the newest version of LLVM.
Anyway, Thank you.

Truly yours,
Seung

---- Original message ----

>Date: Sun, 03 Feb 2008 20:54:24 +0100
>From: Wojciech Matyjewicz <[hidden email]>  
>Subject: Re: [LLVMdev] Question to Chris  
>To: LLVM Developers Mailing List <[hidden email]>
>
>Seung,
>
>> Would you please explain to me how I can access to this problem in a better way if you can figure out?
>
>Here are my thoughts on your first question: "how to make it count
>correctly for the reconstruction of loops?". I believe it can't be done
>for an arbitrary loop. However, IIRC from previous posts your loops are
>simple - for example: they don't contain any breaks, gotos. I think,
>your reconstruction could be done for two forms of loops that are very
>common:
>
>1) rotated canonical loop (bb8.outer in your example):
>The loop has only one backedge, and an induction variable counting from
>0 with step 1. The only basic block that branches out of the loop (so
>called, exiting block) is the backedge.
>
>header:
>  %i = phi [ 0, %preheader ], [ %i.next, %body ]
>  ...
>  br label %body ;%header and %body may be the same block
>
>body:
>  ...
>  %i.next = add %i, 1
>  %c = seteq %i.next, %n
>  br %c, label %exit, label %header
>
>exit:
>  ...
>
>The loop iteration count is %n. In this case, it means that _every_
>basic block is executed %n times. Your current version of reconstruction
>seems to be okay for loops in this form.
>
>2) unrotated canonical loop (bb8 in your example):
>The loop has only one backedge and an induction variable counting from 0
>with step 1. The only basic block that branches out of the loop is the
>loop header.
>
>header:
>  %i = phi [ 0, %preheader ], [ %i.next, %body ]
>  ...
>  %c = seteq %i, %n
>  br %c, label %exit, label %body
>
>body:
>  ...
>  %i.next = add %i, 1
>  br label %header
>
>exit:
>  ...
>
>The loop iteration count is also %n. However, this time it means that
>the loop header is executed %n times, while the rest of blocks - %n-1
>times. The reconstruction should take it into account. For example, it
>could make a "for" loop from all loop basic blocks setting the iteration
>count to %n-1, and then insert a copy of the loop header with %i==%n
>after the "for".
>
>I also suggest taking look at the LoopInfo pass. It has many useful
>methods to analyze loops. To determine the loop iteration count you may
>use the ScalarEvolution pass as well.
>
>-Wojtek
>_______________________________________________
>LLVM Developers mailing list
>[hidden email]         http://llvm.cs.uiuc.edu
>http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question to Chris

Tanya Lattner-2
In reply to this post by Seung Jae Lee

>> 1) LLVM has the capabilities to do everything that you are trying to
>> re-implement.
>> 2) Have you looked at the C backend? It recreates loops. It may not
>> create "for" loops but you can hack on it to do that.
>
> I wonder if you mean "goto elimination technique" by Ana Maria Erosa (
> http://citeseer.ist.psu.edu/317208.html ) for this?

I mean exactly this: look at the C backend in LLVM. It goes from LLVM IR
in SSA form to C code.

LLVM has everything you are trying to reimplement. You should spend some
time looking through doxygen or the source code for examples.

>> 3) The way you are converting out of SSA is wrong. You will suffer
>> from lost copies. You should look at using demotePHI(). see include/
>> llvm/Transforms/Utils/Local.h
>
> I use LLVM 1.9 where I can't find demotePHI(). Is it a function available at later versions?

It is not in 1.9. You should really consider upgrading to 2.1 or 2.2 (its
out in a week). 1.9 is almost 1.5 years old! demotePHI is in 2.1.
>
>> 4) LLVM will  compute your trip counts for you, use LoopInfo. You
>> need to be in SSA form to do this.

> Do you mean -loops pass, right?
>

I mean this:
http://llvm.org/doxygen/LoopInfo_8h-source.html

Require the analysis in your pass and use it.

-Tanya
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev