constructing 'for' statement from LLVM bitcode

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

constructing 'for' statement from LLVM bitcode

Seung Jae Lee
Hello, guys.
I am trying to construct higher-level 'for' from the low-level LLVM bitcode(ver 1.9).
It's partly successful thanks to David A. Greene's advice suggested to use Control Dependence Graph(CDG).
I could find which BB contributes to form which loop with CDG.
For example, for this simple function:
-----------------------------------------------------------
void bsloop(int n, int pM, Params* ps) {
   int i, sim;  
   for (sim=0; sim < pM; sim++) {
      for (i = 0; i < n; i++) {
         Params* p = ps + i;
         double eps = norm(0,1);
      }
   }
}
-----------------------------------------------------------
LLVM bitcode is emitted like this:
-----------------------------------------------------------
void %bsloop(int %n, int %pM, %struct.Params* %ps) {
entry:
        %pM = cast int %pM to uint              ; <uint> [#uses=1]
        %tmp1822 = setgt int %pM, 0             ; <bool> [#uses=1]
        br bool %tmp1822, label %bb9.outer, label %return

bb9.outer:              ; preds = %bb12, %entry
        %indvar23 = phi uint [ 0, %entry ], [ %indvar.next24, %bb12 ]           ; <uint> [#uses=1]
        br label %bb9

bb1:            ; preds = %bb9
        %tmp = tail call double %mtrandres53( sbyte 1 )         ; <double> [#uses=0]
        %indvar.next = add uint %indvar, 1              ; <uint> [#uses=1]
        br label %bb9

bb9:            ; preds = %bb1, %bb9.outer
        %indvar = phi uint [ 0, %bb9.outer ], [ %indvar.next, %bb1 ]            ; <uint> [#uses=2]
        %i.1 = cast uint %indvar to int         ; <int> [#uses=1]
        %tmp = setlt int %i.1, %n               ; <bool> [#uses=1]
        br bool %tmp, label %bb1, label %bb12

bb12:           ; preds = %bb9
        %indvar.next24 = add uint %indvar23, 1          ; <uint> [#uses=2]
        %exitcond = seteq uint %indvar.next24, %pM              ; <bool> [#uses=1]
        br bool %exitcond, label %return, label %bb9.outer

return:         ; preds = %bb12, %entry
        ret void
}
-----------------------------------------------------------
This code above offers me info of Control Flow Graph(CFG).
(If I could number each BB above like this:)
-----------------------------------------------------------
entry -> (0)
bb9.outer -> (1)
bb1 -> (2)
bb9 -> (3)
bb12 -> (4)
return -> (5)
-----------------------------------------------------------
With the CFG info, I could make the dominator tree, dominance frontier and finally Control Depedence Graph(CDG) shown as follows:
-----------------------------------------------------------
(x) | CDG of (x)
(0) | (1),(3),(4)
(1) | -
(2) | -
(3) | (2),(3)
(4) | (1),(3),(4)
(5) | -
-----------------------------------------------------------
Now that (3) is a member of CDG of (3) and (4) is a member of CDG of (4), they are found as loops and the loop which is composed of BB (2) and (3) is inside of the loop comprises BB (1)~(4).
I can manage to re-construct 'for' with this CDG info but generally it might be much complex if 'for' is nested several times and mixed with 'if' and so on in the high-level code so it's not sure if I can succeed in those cases.
Do you have any idea on how I can construct 'for' more systemically with this CDG info from LLVM bitcode?

Thanks,
SJL
_______________________________________________
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: constructing 'for' statement from LLVM bitcode

Chris Lattner

On Aug 24, 2007, at 10:07 PM, Seung Jae Lee wrote:

> Do you have any idea on how I can construct 'for' more systemically  
> with this CDG info from LLVM bitcode?
>

I strongly suggest looking at the Muchnick book: http://
www.amazon.com/Advanced-Compiler-Design-Implementation-Muchnick/dp/
1558603204

It has a section on "structural analysis" that you will find useful.

Why do you want "for statements"?

-Chris
_______________________________________________
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: constructing 'for' statement from LLVM bitcode

Seung Jae Lee
In reply to this post by Seung Jae Lee
---- Original message ----

>Date: Fri, 24 Aug 2007 22:23:39 -0700
>From: Chris Lattner <[hidden email]>  
>Subject: Re: [LLVMdev] constructing 'for' statement from LLVM bitcode  
>To: LLVM Developers Mailing List <[hidden email]>
>
>
>On Aug 24, 2007, at 10:07 PM, Seung Jae Lee wrote:
>
>> Do you have any idea on how I can construct 'for' more systemically  
>> with this CDG info from LLVM bitcode?
>>
>
>I strongly suggest looking at the Muchnick book: http://
>www.amazon.com/Advanced-Compiler-Design-Implementation-Muchnick/dp/
>1558603204
>
>It has a section on "structural analysis" that you will find useful.
>
>Why do you want "for statements"?
>

Thank you for this info, Chris.
I'm doing this 'cause I'm making a backend for a virtual machine assembly has an instruction which is very similar to 'for' statement.
I know this seems quite strange for that machine instruction looks quite high-level.
Furthermore, it doesn't have instructions such as 'br' in LLVM so this is why I have to re-construct 'for' statement for the assembly from LLVM bitcode. (I must not use 'goto' in the high-level source code, either. :-/)

Thanks,
SJL

>-Chris
>_______________________________________________
>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: constructing 'for' statement from LLVM bitcode

Chris Lattner
>> It has a section on "structural analysis" that you will find useful.
>>
>> Why do you want "for statements"?
>>
>
> Thank you for this info, Chris.
> I'm doing this 'cause I'm making a backend for a virtual machine  
> assembly has an instruction which is very similar to 'for' statement.
> I know this seems quite strange for that machine instruction looks  
> quite high-level.
> Furthermore, it doesn't have instructions such as 'br' in LLVM so  
> this is why I have to re-construct 'for' statement for the assembly  
> from LLVM bitcode. (I must not use 'goto' in the high-level source  
> code, either. :-/)

Ok.  Note that LLVM can represent irreducible loops.  You can handle  
this through code duplication.

-Chris
_______________________________________________
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: constructing 'for' statement from LLVM bitcode

Domagoj Babic
Seung,

On 8/25/07, Chris Lattner <[hidden email]> wrote:
> Ok.  Note that LLVM can represent irreducible loops.  You can handle
> this through code duplication.
> -Chris


If you are willing to invest more effort into a more complicated analysis,
in many cases you can even avoid code duplication. See this paper for
details:

@inproceedings{erosa94taming,
  author    = {Ana M. Erosa and
               Laurie J. Hendren},
  title     = {Taming Control Flow: A Structured Approach to Eliminating
               Goto Statements.},
  booktitle = {ICCL},
  year      = {1994},
  pages     = {229--240},
 }

Cheers,

--
        Domagoj Babic

        http://www.domagoj.info/
        http://www.calysto.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: constructing 'for' statement from LLVM bitcode

Daniel Berlin
On 8/29/07, Domagoj Babic <[hidden email]> wrote:

> Seung,
>
> On 8/25/07, Chris Lattner <[hidden email]> wrote:
> > Ok.  Note that LLVM can represent irreducible loops.  You can handle
> > this through code duplication.
> > -Chris
>
>
> If you are willing to invest more effort into a more complicated analysis,
> in many cases you can even avoid code duplication. See this paper for
> details:

We implemented this in GCC early on in the days of GIMPLE, and while
theoretically it removes code duplication, in practice it made the
code take significantly more space and run slower. :)

>
> @inproceedings{erosa94taming,
>   author    = {Ana M. Erosa and
>                Laurie J. Hendren},
>   title     = {Taming Control Flow: A Structured Approach to Eliminating
>                Goto Statements.},
>   booktitle = {ICCL},
>   year      = {1994},
>   pages     = {229--240},
>  }
>
> Cheers,
>
> --
>         Domagoj Babic
>
>         http://www.domagoj.info/
>         http://www.calysto.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: constructing 'for' statement from LLVM bitcode

Domagoj Babic
Daniel,

On 8/30/07, Daniel Berlin <[hidden email]> wrote:

> On 8/29/07, Domagoj Babic <[hidden email]> wrote:
> > Seung,
> >
> > On 8/25/07, Chris Lattner <[hidden email]> wrote:
> > > Ok.  Note that LLVM can represent irreducible loops.  You can handle
> > > this through code duplication.
> > > -Chris
> >
> >
> > If you are willing to invest more effort into a more complicated analysis,
> > in many cases you can even avoid code duplication. See this paper for
> > details:
>
> We implemented this in GCC early on in the days of GIMPLE, and while
> theoretically it removes code duplication, in practice it made the
> code take significantly more space and run slower. :)

This is good to know, I've never implemented it myself.

I'm a bit surprised that the code took significantly more space.

Cheers,

--
        Domagoj Babic

        http://www.domagoj.info/
        http://www.calysto.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: constructing 'for' statement from LLVM bitcode

Sebastian Pop-2
On 8/30/07, Domagoj Babic <[hidden email]> wrote:
>
> I'm a bit surprised that the code took significantly more space.
>

That's because of the new conditions, and new control variables.  As
this technique transforms control flow dependences to data deps, it
depends on how many cfg edges you are redirecting via temp variables.

A nice example is when the transformed jump is from a loop to another
loop: the number of checks to the control variable is the depth from
the first loop to the common parent plus the depth for the second loop
to the parent.
_______________________________________________
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: constructing 'for' statement from LLVM bitcode

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

Seung Jae Lee wrote:
> Hello, guys.
> I am trying to construct higher-level 'for' from the low-level LLVM bitcode(ver 1.9).
> It's partly successful thanks to David A. Greene's advice suggested to use Control Dependence Graph(CDG).
> I could find which BB contributes to form which loop with CDG.

I know my post comes late... Are you still interested in this subject?
No? Just ignore it;)

I have been recently dealing with a task which is somehow similar to
yours. I was trying to reconstruct simple 'for' loops and check if it's
possible to automatically parallelize their execution.

> For example, for this simple function:
> -----------------------------------------------------------
> void bsloop(int n, int pM, Params* ps) {
>    int i, sim;  
>    for (sim=0; sim < pM; sim++) {
>       for (i = 0; i < n; i++) {
>          Params* p = ps + i;
>          double eps = norm(0,1);
>       }
>    }
> }

I think it would be possible to reconstruct loops like this. However, it
might be very difficult (impossible in general?) if they contained
'break', 'continue' or 'goto' statements.

Have you tried the use LoopInfo pass for your aim? If you compile the
example to bitcode without optimization and then choose optimizer passes
manually:
 opt -mem2reg -instcombine -indvars -o bsloop-opt.bc bsloop.bc
you will get the following code for bsloop() function (llvm and
llvm-gcc-4.2 from SVN):
--------------------------------------------------------
define void @bsloop(i32 %n, i32 %pM, %struct.Params* %ps) {
entry:
        br label %bb16

bb1: ; preds = %bb8
        %tmp4 = call i32 (...)* @norm( i32 0, i32 1 )
        %indvar.next = add i32 %i.0, 1
        br label %bb8

bb8: ; preds = %bb16, %bb1
        %i.0 = phi i32 [ %indvar.next, %bb1 ], [ 0, %bb16 ]
        %tmp11 = icmp slt i32 %i.0, %n
        br i1 %tmp11, label %bb1, label %bb13

bb13:
        %indvar.next1 = add i32 %sim.0, 1
        br label %bb16

bb16:
        %sim.0 = phi i32 [ 0, %entry ], [ %indvar.next1, %bb13 ]
        %tmp19 = icmp slt i32 %sim.0, %pM
        br i1 %tmp19, label %bb8, label %return

return:
        ret void
}
--------------------------------------------------------

Then, running LoopInfo pass:
 opt -analyze -loops bsloop-opt.bc
prints:
--------------------------------------------------------
Printing analysis 'Natural Loop Construction' for function 'bsloop':
Loop Containing:  %bb16, %bb13, %bb8, %bb1
    Loop Containing:  %bb8, %bb1
--------------------------------------------------------

Using the LoopInfo interface allows you to gather much useful
information. In the internal loop basic block bb8 is the header, %i.0 is
the canonical induction variable (and the only induction variable). Loop
has a trip count %n which is a loop invariant. Inspecting the header
shows it doesn't produce any values that are used outside of it, except
for the loop induction variable. Furthermore, it doesn't produce any
side effects. Hence, in this simple case a 'for' loop could be
reconstructed:
 FOR %i.0 = 0 TO %n - 1 STEP 1:
   %tmp4 = call i32 (...)* @norm( i32 0, i32 1 )
   //%indvar.next is no longer needed

I know such a heuristic applies to very simple 'for' loops only.
However, "very simple 'for' loops" are quite popular;)

--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: constructing 'for' statement from LLVM bitcode

Seung Jae Lee
In reply to this post by Seung Jae Lee
Wow... Thank you so much for this.
I'll try this one.
Thanks again, Wojciech.

SJL

---- Original message ----

>Date: Sat, 15 Sep 2007 15:07:34 +0200
>From: Wojciech Matyjewicz <[hidden email]>  
>Subject: Re: [LLVMdev] constructing 'for' statement from LLVM bitcode  
>To: LLVM Developers Mailing List <[hidden email]>
>
>Hi,
>
>Seung Jae Lee wrote:
>> Hello, guys.
>> I am trying to construct higher-level 'for' from the low-level LLVM bitcode(ver 1.9).
>> It's partly successful thanks to David A. Greene's advice suggested to use Control Dependence Graph(CDG).
>> I could find which BB contributes to form which loop with CDG.
>
>I know my post comes late... Are you still interested in this subject?
>No? Just ignore it;)
>
>I have been recently dealing with a task which is somehow similar to
>yours. I was trying to reconstruct simple 'for' loops and check if it's
>possible to automatically parallelize their execution.
>
>> For example, for this simple function:
>> -----------------------------------------------------------
>> void bsloop(int n, int pM, Params* ps) {
>>    int i, sim;  
>>    for (sim=0; sim < pM; sim++) {
>>       for (i = 0; i < n; i++) {
>>          Params* p = ps + i;
>>          double eps = norm(0,1);
>>       }
>>    }
>> }
>
>I think it would be possible to reconstruct loops like this. However, it
>might be very difficult (impossible in general?) if they contained
>'break', 'continue' or 'goto' statements.
>
>Have you tried the use LoopInfo pass for your aim? If you compile the
>example to bitcode without optimization and then choose optimizer passes
>manually:
> opt -mem2reg -instcombine -indvars -o bsloop-opt.bc bsloop.bc
>you will get the following code for bsloop() function (llvm and
>llvm-gcc-4.2 from SVN):
>--------------------------------------------------------
>define void @bsloop(i32 %n, i32 %pM, %struct.Params* %ps) {
>entry:
> br label %bb16
>
>bb1: ; preds = %bb8
> %tmp4 = call i32 (...)* @norm( i32 0, i32 1 )
> %indvar.next = add i32 %i.0, 1
> br label %bb8
>
>bb8: ; preds = %bb16, %bb1
> %i.0 = phi i32 [ %indvar.next, %bb1 ], [ 0, %bb16 ]
> %tmp11 = icmp slt i32 %i.0, %n
> br i1 %tmp11, label %bb1, label %bb13
>
>bb13:
> %indvar.next1 = add i32 %sim.0, 1
> br label %bb16
>
>bb16:
> %sim.0 = phi i32 [ 0, %entry ], [ %indvar.next1, %bb13 ]
> %tmp19 = icmp slt i32 %sim.0, %pM
> br i1 %tmp19, label %bb8, label %return
>
>return:
> ret void
>}
>--------------------------------------------------------
>
>Then, running LoopInfo pass:
> opt -analyze -loops bsloop-opt.bc
>prints:
>--------------------------------------------------------
>Printing analysis 'Natural Loop Construction' for function 'bsloop':
>Loop Containing:  %bb16, %bb13, %bb8, %bb1
>    Loop Containing:  %bb8, %bb1
>--------------------------------------------------------
>
>Using the LoopInfo interface allows you to gather much useful
>information. In the internal loop basic block bb8 is the header, %i.0 is
>the canonical induction variable (and the only induction variable). Loop
>has a trip count %n which is a loop invariant. Inspecting the header
>shows it doesn't produce any values that are used outside of it, except
>for the loop induction variable. Furthermore, it doesn't produce any
>side effects. Hence, in this simple case a 'for' loop could be
>reconstructed:
> FOR %i.0 = 0 TO %n - 1 STEP 1:
>   %tmp4 = call i32 (...)* @norm( i32 0, i32 1 )
>   //%indvar.next is no longer needed
>
>I know such a heuristic applies to very simple 'for' loops only.
>However, "very simple 'for' loops" are quite popular;)
>
>--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: constructing 'for' statement from LLVM bitcode

Seung Jae Lee
In reply to this post by Seung Jae Lee
Dear Wojciech Matyjewicz:

Thank you for your advice.
I could follow what you had suggested upto
  opt -analyze -loops bsloop-opt.bc

Therefore, I could get the prints you had showed me as follows:
--------------------------------------------------------
Printing analysis 'Natural Loop Construction' for function 'bsloop':
Loop Containing:  %bb16, %bb13, %bb8, %bb1
    Loop Containing:  %bb8, %bb1
--------------------------------------------------------

In your reply, you could re-construct the simple 'for' from the info above like this:
--------------------------------------------------------
 FOR %i.0 = 0 TO %n - 1 STEP 1:
   %tmp4 = call i32 (...)* @norm( i32 0, i32 1 )
   //%indvar.next is no longer needed
--------------------------------------------------------

I'd just like to make it sure whether you did this manually.
(LLVM doesn't support any pass doing this automatically for us. Am I right?)

And there seems to be more issues, Wojciech.
What about PHI nodes?
To construct 'for' as it was, we should handle PHI nodes.
I also wonder how you treated them.

Thank you so much.
SJ Lee

---- Original message ----

>Date: Sat, 15 Sep 2007 15:07:34 +0200
>From: Wojciech Matyjewicz <[hidden email]>  
>Subject: Re: [LLVMdev] constructing 'for' statement from LLVM bitcode  
>To: LLVM Developers Mailing List <[hidden email]>
>
>Hi,
>
>Seung Jae Lee wrote:
>> Hello, guys.
>> I am trying to construct higher-level 'for' from the low-level LLVM bitcode(ver 1.9).
>> It's partly successful thanks to David A. Greene's advice suggested to use Control Dependence Graph(CDG).
>> I could find which BB contributes to form which loop with CDG.
>
>I know my post comes late... Are you still interested in this subject?
>No? Just ignore it;)
>
>I have been recently dealing with a task which is somehow similar to
>yours. I was trying to reconstruct simple 'for' loops and check if it's
>possible to automatically parallelize their execution.
>
>> For example, for this simple function:
>> -----------------------------------------------------------
>> void bsloop(int n, int pM, Params* ps) {
>>    int i, sim;  
>>    for (sim=0; sim < pM; sim++) {
>>       for (i = 0; i < n; i++) {
>>          Params* p = ps + i;
>>          double eps = norm(0,1);
>>       }
>>    }
>> }
>
>I think it would be possible to reconstruct loops like this. However, it
>might be very difficult (impossible in general?) if they contained
>'break', 'continue' or 'goto' statements.
>
>Have you tried the use LoopInfo pass for your aim? If you compile the
>example to bitcode without optimization and then choose optimizer passes
>manually:
> opt -mem2reg -instcombine -indvars -o bsloop-opt.bc bsloop.bc
>you will get the following code for bsloop() function (llvm and
>llvm-gcc-4.2 from SVN):
>--------------------------------------------------------
>define void @bsloop(i32 %n, i32 %pM, %struct.Params* %ps) {
>entry:
> br label %bb16
>
>bb1: ; preds = %bb8
> %tmp4 = call i32 (...)* @norm( i32 0, i32 1 )
> %indvar.next = add i32 %i.0, 1
> br label %bb8
>
>bb8: ; preds = %bb16, %bb1
> %i.0 = phi i32 [ %indvar.next, %bb1 ], [ 0, %bb16 ]
> %tmp11 = icmp slt i32 %i.0, %n
> br i1 %tmp11, label %bb1, label %bb13
>
>bb13:
> %indvar.next1 = add i32 %sim.0, 1
> br label %bb16
>
>bb16:
> %sim.0 = phi i32 [ 0, %entry ], [ %indvar.next1, %bb13 ]
> %tmp19 = icmp slt i32 %sim.0, %pM
> br i1 %tmp19, label %bb8, label %return
>
>return:
> ret void
>}
>--------------------------------------------------------
>
>Then, running LoopInfo pass:
> opt -analyze -loops bsloop-opt.bc
>prints:
>--------------------------------------------------------
>Printing analysis 'Natural Loop Construction' for function 'bsloop':
>Loop Containing:  %bb16, %bb13, %bb8, %bb1
>    Loop Containing:  %bb8, %bb1
>--------------------------------------------------------
>
>Using the LoopInfo interface allows you to gather much useful
>information. In the internal loop basic block bb8 is the header, %i.0 is
>the canonical induction variable (and the only induction variable). Loop
>has a trip count %n which is a loop invariant. Inspecting the header
>shows it doesn't produce any values that are used outside of it, except
>for the loop induction variable. Furthermore, it doesn't produce any
>side effects. Hence, in this simple case a 'for' loop could be
>reconstructed:
> FOR %i.0 = 0 TO %n - 1 STEP 1:
>   %tmp4 = call i32 (...)* @norm( i32 0, i32 1 )
>   //%indvar.next is no longer needed
>
>I know such a heuristic applies to very simple 'for' loops only.
>However, "very simple 'for' loops" are quite popular;)
>
>--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: constructing 'for' statement from LLVM bitcode

Wojciech Matyjewicz
Hi,

Seung Jae Lee wrote:
> In your reply, you could re-construct the simple 'for' from the info above like this:
> --------------------------------------------------------
>  FOR %i.0 = 0 TO %n - 1 STEP 1:
>    %tmp4 = call i32 (...)* @norm( i32 0, i32 1 )
>    //%indvar.next is no longer needed
> --------------------------------------------------------
>
> I'd just like to make it sure whether you did this manually.
> (LLVM doesn't support any pass doing this automatically for us. Am I right?)

You're right - there is no pass that automatically reconstructs 'for'
loops. I might have gone too far with the above example, because my
algorithm doesn't represent loops literally this way. It was only a
high-level view of information gathered about the loop.

By writing "simple for loop", I mean a loop which in C would have this form:
 for (int i = low; i < up; i += step)
   // loop body

If it doesn't contain 'break', 'goto' nor 'continue' statements it is
generally translated to something like this (only -mem2reg and
-instcombine passes used):
----------------------------------------------------------
bb4: ; preds = %bb, %entry
        %i.0 = phi i32 [ %low, %entry ], [ %tmp3, %bb ]; <i32> [#uses=2]
        %tmp7 = icmp slt i32 %i.0, %up ; <i1> [#uses=1]
        br i1 %tmp7, label %bb, label %bb9

bb: ; preds = %bb4
        ; <loop body>
        %tmp3 = add i32 %i.0, %step ; <i32> [#uses=1]
        br label %bb4
----------------------------------------------------------

LoopInfo discovers the natural loop built from these basic blocks (with
%bb4 as a loop header). My algorithm then applies some heuristics to
check if it's a simple for loop. It finds the def. representing the
induction variable (%i.0) and operands representing lower bound (%low),
upper bound (%up), step (%step). Next, it can be proved that
instructions: %tmp7, %tmp3 and both branches are solely responsible for
making the loop iterate. The rest of instructions constitute the loop
body.

As far as I remember you are trying to compile for a virtual machine
with an explicit 'for' instruction... Unfortunatelly, I have no
experience with writing backends for LLVM. I was only trying to show
that simple for loops can be recognized. I believe the gathered
information could be used somehow in the backend.

> What about PHI nodes?
> To construct 'for' as it was, we should handle PHI nodes.
> I also wonder how you treated them.

I only change the loop iteration bounds in the code for the loop so
there is no special treatment of them.

What about 'if' instruction in your target? Is it also explicit? If your
VM doesn't support branching instructions it may be difficult, in my
opinion, to create an LLVM backend for it, as LLVM instruction set
models ordinary processors. Have you considered using higher-level
information for your aim? For example, using an abstract syntax tree,
which represents directly control flow statements of the source
language. You could take a look at clang - a new C frontend for LLVM...

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