llvm dev - Jun 2007 - [LLVMdev] LLVM assembly without basic block

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 <basile at starynkevitch.net>  
>Subject: Re: [LLVMdev] LLVM assembly without basic block  
>To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu>
>
>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
>LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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} ***