LLVM assembly without basic block

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

LLVM assembly without basic block

Seung Jae Lee
Hello, guys.

I just wonder if there is any way to spit out LLVM assembly without any basic block division.
E.g.,
If I emit LLVM assembly for the following simple code:
------------------------------------------------------------
void f_loop(long* c, long sz) {

   long i;
   for (i = 0; i < sz; i++) {
      long offset = i * sz;
      long* out = c + offset;
      out[i] = 0;
   }
}
------------------------------------------------------------
You know the LLVM assembly is printed out as follows for this code.
------------------------------------------------------------
void %f_loop(int* %c, int %sz) {
entry:
        %sz = cast int %sz to uint              ; <uint> [#uses=1]
        %tmp18 = setgt int %sz, 0               ; <bool> [#uses=1]
        br bool %tmp18, label %bb, label %return

bb:             ; preds = %bb, %entry
        %indvar = phi uint [ 0, %entry ], [ %indvar.next, %bb ]         ; <uint> [#uses=2]
        %i.0.0 = cast uint %indvar to int               ; <int> [#uses=2]
        %tmp2 = mul int %i.0.0, %sz             ; <int> [#uses=1]
        %tmp4.sum = add int %tmp2, %i.0.0               ; <int> [#uses=1]
        %tmp7 = getelementptr int* %c, int %tmp4.sum            ; <int*> [#uses=1]
        store int 0, int* %tmp7
        %indvar.next = add uint %indvar, 1              ; <uint> [#uses=2]
        %exitcond = seteq uint %indvar.next, %sz                ; <bool> [#uses=1]
        br bool %exitcond, label %return, label %bb

return:         ; preds = %bb, %entry
        ret void
}
------------------------------------------------------------
As you can see, there are three basic blocks composing this code.
Is there any way to get the assembly for this function without any basic block division?
I know this may be absurd but curious.

Thanks,
Seung Jae Lee
_______________________________________________
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: LLVM assembly without basic block

Basile Starynkevitch
Seung Jae Lee wrote:
> Hello, guys.
>
> I just wonder if there is any way to spit out LLVM assembly without any basic block division.

I believe you cannot do that, since the basic blocks are defined by the control flow graph, i.e. by the points in the
program to which (conditional or unconditional) jumps go. In other words, basic blocks are defined by the destination of
goto (in particular those in loops and tests) and calls.

If you restrict yourself to a single basic block, you need to avoid tests and loops.

--
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faïencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***


_______________________________________________
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: LLVM assembly without basic block

Seung Jae Lee
In reply to this post by Seung Jae Lee
Thank you for this reply.
If so, is there any way to merge basic blocks into a single one?

Thanks,
Seung J. Lee

---- Original message ----

>Date: Fri, 29 Jun 2007 22:27:38 +0200
>From: Basile STARYNKEVITCH <[hidden email]>  
>Subject: Re: [LLVMdev] LLVM assembly without basic block  
>To: LLVM Developers Mailing List <[hidden email]>
>
>Seung Jae Lee wrote:
>> Hello, guys.
>>
>> I just wonder if there is any way to spit out LLVM assembly without any basic block division.
>
>I believe you cannot do that, since the basic blocks are defined by the control flow graph, i.e. by the points in the
>program to which (conditional or unconditional) jumps go. In other words, basic blocks are defined by the destination of
>goto (in particular those in loops and tests) and calls.
>
>If you restrict yourself to a single basic block, you need to avoid tests and loops.
>
>--
>Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
>email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
>8, rue de la Faïencerie, 92340 Bourg La Reine, France
>*** opinions {are only mines, sont seulement les miennes} ***
>
>
>_______________________________________________
>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: LLVM assembly without basic block

Basile Starynkevitch
Seung Jae Lee wrote:
> Thank you for this reply.
> If so, is there any way to merge basic blocks into a single one?
Why are you asking and what do you want to do?


I (Basile) wrote previously:

>> I believe you cannot do that, since the basic blocks are defined by the control flow graph, i.e. by the points in the
>> program to which (conditional or unconditional) jumps go. In other words, basic blocks are defined by the destination of
>> goto (in particular those in loops and tests) and calls.


Basic blocks is not some LLVM pecularity, it is a notion you can find in any compiler book!

The only way to have bigger basic blocks is to avoid branching (ie any kind of jumps, including loops, tests, function
calls and returns).

Intuitively you cannot jump inside a basic block or outside of it, only at the start (jumping to before the first
instruction of the block) or end (jumping from after the last instruction of the basic block).

I cannot figure what you are asking. Does your pecular language have no tests, no loops, no jumps, no calls? If it is
the case (hence your language is not Turing complete) then you might have choosen a too big tool (a compiler like LLVM)
for your goals.

Remember that the LLVM language is an intermediate language. Your translator has to analyze your source code to break
into "atomic" control flow parts, which are precisely the basic blocks.

Please take a few hours to read some basic tutorial on compilation...

Or maybe you are thinking of loop unrolling or inlining or other optimisation (or program transformations).

What is hurting you in the notion of basic blocks and in the LLVM usage of them?

--
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faïencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***


_______________________________________________
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: LLVM assembly without basic block

Seung Jae Lee
In reply to this post by Seung Jae Lee
Thank you for reminding me the notion of the basic block.
Of course, I know all the assembly takes the form of BBs and is divided into units of BB.
OK. It looks better for me to explain what I wanted to do more clear from the first.

Actually, I am working on emitting out an assembly of VM by using LLVM. LLVM assembly looks similar with this VM assembly except BB. The VM assembly does not have the explicit concept of BB. (I know this is quite foreign.)
For this reason, this assembly looks like more HLL. ('for' statement is a mnemonic for looping in this assembly. :-( )
For example, the VM assembly looks like the following for the simple C code I showed you before. (I write it again, for your convenience.)
----------------------------------------------------------
void f_loop(long* c, long sz) {

   long i;

   for (i = 0; i < sz; i++)
   {
      long offset = i * sz;
      long* out = c + offset;
      out[i] = 0;
   }
}
----------------------------------------------------------
The assembly is shown like this:
----------------------------------------------------------
Enter f_loop; c,sz
reg i
reg temp1:1
nfor l0;sz;i
        reg out, offset
        reg temp0
        multiply i,sz;offset
        add offset<<2,c;out
        add i<<2,out;temp0
        write temp0;0;4;;
end l0
exit f_loop
----------------------------------------------------------
Even if the case that there are more loops, this VM assembly does not divide the function into BBs 'cause there is no concept of BB.

For optimization of this assembly, I'm taking benefits from using the optimized LLVM bytecode which LLVM-GCC spits out. It has BBs, though. Therefore, I should combine BBs into 'for' statements when several 'for's are used in HLL.
This is why I asked that.
I should have asked you more clear.
Sorry for any misunderstanding I might have caused.

Thanks,
Seung J. Lee


---- Original message ----

>Date: Fri, 29 Jun 2007 23:14:10 +0200
>From: Basile STARYNKEVITCH <[hidden email]>  
>Subject: Re: [LLVMdev] LLVM assembly without basic block  
>To: LLVM Developers Mailing List <[hidden email]>
>
>Seung Jae Lee wrote:
>> Thank you for this reply.
>> If so, is there any way to merge basic blocks into a single one?
>Why are you asking and what do you want to do?
>
>
>I (Basile) wrote previously:
>
>>> I believe you cannot do that, since the basic blocks are defined by the control flow graph, i.e. by the points in the
>>> program to which (conditional or unconditional) jumps go. In other words, basic blocks are defined by the destination of
>>> goto (in particular those in loops and tests) and calls.
>
>
>Basic blocks is not some LLVM pecularity, it is a notion you can find in any compiler book!
>
>The only way to have bigger basic blocks is to avoid branching (ie any kind of jumps, including loops, tests, function
>calls and returns).
>
>Intuitively you cannot jump inside a basic block or outside of it, only at the start (jumping to before the first
>instruction of the block) or end (jumping from after the last instruction of the basic block).
>
>I cannot figure what you are asking. Does your pecular language have no tests, no loops, no jumps, no calls? If it is
>the case (hence your language is not Turing complete) then you might have choosen a too big tool (a compiler like LLVM)
>for your goals.
>
>Remember that the LLVM language is an intermediate language. Your translator has to analyze your source code to break
>into "atomic" control flow parts, which are precisely the basic blocks.
>
>Please take a few hours to read some basic tutorial on compilation...
>
>Or maybe you are thinking of loop unrolling or inlining or other optimisation (or program transformations).
>
>What is hurting you in the notion of basic blocks and in the LLVM usage of them?
>
>--
>Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
>email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
>8, rue de la Faïencerie, 92340 Bourg La Reine, France
>*** opinions {are only mines, sont seulement les miennes} ***
>
>
>_______________________________________________
>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: LLVM assembly without basic block

Basile Starynkevitch
Seung Jae Lee wrote:

> Thank you for reminding me the notion of the basic block.
> Of course, I know all the assembly takes the form of BBs and is divided into units of BB.
> OK. It looks better for me to explain what I wanted to do more clear from the first.
>
> Actually, I am working on emitting out an assembly of VM by using LLVM. LLVM assembly looks similar with this VM assembly except BB. The VM assembly does not have the explicit concept of BB. (I know this is quite foreign.)
> For this reason, this assembly looks like more HLL. ('for' statement is a mnemonic for looping in this assembly. :-( )
> For example, the VM assembly looks like the following for the simple C code I showed you before. (I write it again, for your convenience.)
> ----------------------------------------------------------
> void f_loop(long* c, long sz) {
>
>    long i;
>
>    for (i = 0; i < sz; i++)
>    {
>       long offset = i * sz;
>       long* out = c + offset;
>       out[i] = 0;
>    }
> }
> ----------------------------------------------------------
> The assembly is shown like this:
> ----------------------------------------------------------
> Enter f_loop; c,sz
> reg i
> reg temp1:1
> nfor l0;sz;i
>         reg out, offset
>         reg temp0
>         multiply i,sz;offset
>         add offset<<2,c;out
>         add i<<2,out;temp0
>         write temp0;0;4;;
> end l0
> exit f_loop
> ----------------------------------------------------------
> Even if the case that there are more loops, this VM assembly does not divide the function into BBs 'cause there is no concept of BB.

Then you have to reconstruct the basic blocks, probably by taking into account the branches in your pseudo assembly code
and the labels. Hence you'll develop a translator from your assembly language to LLVM.

You could also patch the tool generating your assembly code so that its generate LLVM language. This could be simpler.

Or you could use other code generators like GNU lightning.

Or your might generate C code.


--
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faïencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***


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