how to code a loop in llvm assembly

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

how to code a loop in llvm assembly

Simon Burton
Hi,

I've read over the "LLVM Language Reference Manual"
a few times, and writing some ll code, but i'm stuck at
a very basic point. How to decrement a counter variable ?

int %count(int %n) {
EntryBlock:
  %cond = seteq int %n, 0
  br bool %cond, label %Exit, label %Next
Next:
; how to decrement n ?
  %new_n = sub int %n, 1
  br label %EntryBlock
Exit:
  ret int 0
}

I guess I could malloc a variable and use store/load. Is that the right way ?

Also the above code is invalid:
Entry block to function must not have predecessors!
label %EntryBlock
Broken module found, compilation aborted!

thanks for any hints,

Simon.

--
Simon Burton, B.Sc.
Licensed PO Box 8066
ANU Canberra 2601
Australia
Ph. 61 02 6249 6940
http://arrowtheory.com 

_______________________________________________
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: how to code a loop in llvm assembly

Óscar Fuentes-3
Simon Burton <[hidden email]> writes:

> Hi,
>
> I've read over the "LLVM Language Reference Manual"
> a few times, and writing some ll code, but i'm stuck at
> a very basic point. How to decrement a counter variable ?
>
> int %count(int %n) {
> EntryBlock:
>   %cond = seteq int %n, 0
>   br bool %cond, label %Exit, label %Next
> Next:
> ; how to decrement n ?
>   %new_n = sub int %n, 1
>   br label %EntryBlock
> Exit:
>   ret int 0
> }
>
> I guess I could malloc a variable and use store/load. Is that the right way ?
>
> Also the above code is invalid:
> Entry block to function must not have predecessors!
> label %EntryBlock
> Broken module found, compilation aborted!

You need a phi node.

A good way to learn how to write LLVM assembler is to use the online
demo available at http://llvm.org/demo/ You feed a C/C++/Stacker
program and you get the equivalent LLVM code. In this case, something
like this C code is necessary:

int foo(int n, int x) {
  while(n > x) --n;
  return n;
}

The extra stuff is for circumventing the optimizer. If you write

int foo(int n) {
  while(n) --n;
  return 0;
}

the optimizer will reduce it to a ret int 0, which teach us nothing.

An option for disabing optimizations would be very helpful for
learners.

BTW, Simon, is there a reason for writing LLVM assembler and not
generating LLVM code directly? The later is simpler and relieves you
from some nasty burdens. It doesn't require you to generate SSA
conformant code, for instance. Relating to your present problem, it is
"natural" to code a loop without resorting to phi nodes.

--
Oscar

_______________________________________________
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: how to code a loop in llvm assembly

Óscar Fuentes-3
Oscar Fuentes <[hidden email]> writes:

[snip]

> BTW, Simon, is there a reason for writing LLVM assembler and not
> generating LLVM code directly? The later is simpler and relieves you
> from some nasty burdens. It doesn't require you to generate SSA
> conformant code, for instance. Relating to your present problem, it is
> "natural" to code a loop without resorting to phi nodes.

Clarification: it is incorrect to say that generating LLVM code by
instantiating LLVM instructions doesn't require to follow SSA
rules. The truth is that the API is designed in such a way that you
follow SSA rules without knowing about them, except for things like
entries/exits of basic blocks (at least, I have not found any other
issues with SSA so far).

--
Oscar

_______________________________________________
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: how to code a loop in llvm assembly

Ralph Corderoy
In reply to this post by Simon Burton

Hi Simon,

> I've read over the "LLVM Language Reference Manual" a few times, and
> writing some ll code, but i'm stuck at a very basic point. How to
> decrement a counter variable ?

As Oscar pointed out, you need a phi-node.  I read some of the published
papers on LLVM before the Language Reference Manual and found them to be
of use.  You may also find Wikipedia's explanation of SSA useful,
especially the key paragraph

    http://en.wikipedia.org/wiki/Static_single_assignment_form

    "Note: the phi functions are not actually implemented; instead,
    they're just markers for the compiler to place the value of all the
    variables grouped together by the phi function, in the same location
    in memory (or same register)."

Cheers,


Ralph.


_______________________________________________
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: Re: how to code a loop in llvm assembly

Misha Brukman-2
In reply to this post by Óscar Fuentes-3
On Sat, Apr 15, 2006 at 07:47:00AM +0200, Oscar Fuentes wrote:
> Simon Burton <[hidden email]> writes:
> > I've read over the "LLVM Language Reference Manual"
> > a few times, and writing some ll code, but i'm stuck at
> > a very basic point. How to decrement a counter variable ?
[snip]
> > I guess I could malloc a variable and use store/load. Is that the right way ?
[snip]
> You need a phi node.

As others have pointed out, because LLVM is in SSA form, you will need
to use a phi node.  To see how it would be written, try using the demo
script as Oscar suggested, or you can do what you suggested (I would use
alloca instead of malloc, though I think either should work) and then
run it through "opt -mem2reg" to convert it to the phi-node form.

--
Misha Brukman :: http://misha.brukman.net

_______________________________________________
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: Re: how to code a loop in llvm assembly

Reid Spencer
FYI, in case you're wondering about the validity of this approach,
generating alloca instructions and relying on -mem2reg is what the C/C++
front ends do. It is a little more straight forward to code than
manually worrying about the PHI nodes. Either approach will work, take
your pick :)

Reid.

On Sat, 2006-04-15 at 09:13 -0500, Misha Brukman wrote:
> As others have pointed out, because LLVM is in SSA form, you will need
> to use a phi node.  To see how it would be written, try using the demo
> script as Oscar suggested, or you can do what you suggested (I would use
> alloca instead of malloc, though I think either should work) and then
> run it through "opt -mem2reg" to convert it to the phi-node form.
>

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

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: how to code a loop in llvm assembly

Patrick Meredith
In reply to this post by Ralph Corderoy
Using an alloca'd variable with loads and stores would work well  
too.  To date this
is how every llvm language front end works.  You would want to avoid  
malloc for
such a purpose generally.  mem2reg is nice enough to take your local  
load
and stores and promote them to registers with PHINodes :-)

On Apr 15, 2006, at 4:43 AM, Ralph Corderoy wrote:

>
> Hi Simon,
>
>> I've read over the "LLVM Language Reference Manual" a few times, and
>> writing some ll code, but i'm stuck at a very basic point. How to
>> decrement a counter variable ?
>
> As Oscar pointed out, you need a phi-node.  I read some of the  
> published
> papers on LLVM before the Language Reference Manual and found them  
> to be
> of use.  You may also find Wikipedia's explanation of SSA useful,
> especially the key paragraph
>
>     http://en.wikipedia.org/wiki/Static_single_assignment_form
>
>     "Note: the phi functions are not actually implemented; instead,
>     they're just markers for the compiler to place the value of all  
> the
>     variables grouped together by the phi function, in the same  
> location
>     in memory (or same register)."
>
> Cheers,
>
>
> Ralph.
>
>
> _______________________________________________
> 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: Re: how to code a loop in llvm assembly

Patrick Meredith
In reply to this post by Reid Spencer

On Apr 15, 2006, at 2:24 PM, Reid Spencer wrote:

> FYI, in case you're wondering about the validity of this approach,
> generating alloca instructions and relying on -mem2reg is what the  
> C/C++
> front ends do. It is a little more straight forward to code than
> manually worrying about the PHI nodes.

Yeah I wouldn't want to worry about calculating dominance frontiers  
in my
code generator unless I had to :)


> Either approach will work, take
> your pick :)
>
> Reid.
>
> On Sat, 2006-04-15 at 09:13 -0500, Misha Brukman wrote:
>> As others have pointed out, because LLVM is in SSA form, you will  
>> need
>> to use a phi node.  To see how it would be written, try using the  
>> demo
>> script as Oscar suggested, or you can do what you suggested (I  
>> would use
>> alloca instead of malloc, though I think either should work) and then
>> run it through "opt -mem2reg" to convert it to the phi-node form.
>>
> _______________________________________________
> 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: how to code a loop in llvm assembly

Carl Friedrich Bolz
In reply to this post by Patrick Meredith
Patrick Meredith wrote:
> Using an alloca'd variable with loads and stores would work well  too.  
> To date this
> is how every llvm language front end works.

nope :-). PyPy produces SSA code diretly when using the LLVM backend,
which is not surprising, since PyPy uses SSA internally.

> You would want to avoid  malloc for
> such a purpose generally.  mem2reg is nice enough to take your local  load
> and stores and promote them to registers with PHINodes :-)

Cheers,

Carl Friedrich Bolz

_______________________________________________
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: Re: how to code a loop in llvm assembly

Simon Burton
In reply to this post by Óscar Fuentes-3
On Sat, 15 Apr 2006 07:47:00 +0200
Oscar Fuentes <[hidden email]> wrote:

>
> BTW, Simon, is there a reason for writing LLVM assembler and not
> generating LLVM code directly?

You mean write C++ code that calls the LLVM library ?
I have a mild C++ allergy that I don't wish to aggravate.

> The later is simpler and relieves you
> from some nasty burdens.

Yes, i'm finding it quite hairy!

:)

Simon.

--
Simon Burton, B.Sc.
Licensed PO Box 8066
ANU Canberra 2601
Australia
Ph. 61 02 6249 6940
http://arrowtheory.com 

_______________________________________________
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: Re: how to code a loop in llvm assembly

Joseph Altea
I also suffer from the same C++ allergy notably shoot in foot with dynamic grammers and overloading.. creates gasey code feeling..especially in the backend.. :)cheers!

Simon Burton <[hidden email]> wrote:
On Sat, 15 Apr 2006 07:47:00 +0200
Oscar Fuentes wrote:

>
> BTW, Simon, is there a reason for writing LLVM assembler and not
> generating LLVM code directly?

You mean write C++ code that calls the LLVM library ?
I have a mild C++ allergy that I don't wish to aggravate.

> The later is simpler and relieves you
> from some nasty burdens.

Yes, i'm finding it quite hairy!

:)

Simon.

--
Simon Burton, B.Sc.
Licensed PO Box 8066
ANU Canberra 2601
Australia
Ph. 61 02 6249 6940
http://arrowtheory.com

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

Send instant messages to your online friends http://uk.messenger.yahoo.com
_______________________________________________
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: Re: how to code a loop in llvm assembly

Chris Lattner
On Tue, 18 Apr 2006, Joseph Altea wrote:

> I also suffer from the same C++ allergy notably shoot in foot with
> dynamic grammers and overloading.. creates gasey code
> feeling..especially in the backend.. :)cheers!

I have no idea what this is supposed to mean: "creates gasey code
feeling..especially in the backend.."

However, if there is serious interest, many people would like an easy to
use C wrapper around the LLVM API's.

libjit, for all its flaws, seems to have a pretty reasonable C api, one
that would be trivial to implement with LLVM:
http://www.southern-storm.com.au/doc/libjit/libjit_toc.html

If someone wanted to write a libjit-compatible C interface, or something
completely different, but similar in spirit, it would be a very cool and
useful project, and would fit in naturally with the rest of the LLVM
libraries.

This is a way that those with "C++ Allergies" could band together and help
each other out :)

-Chris


> Simon Burton <[hidden email]> wrote: On Sat, 15 Apr 2006 07:47:00 +0200
> Oscar Fuentes  wrote:
>
>>
>> BTW, Simon, is there a reason for writing LLVM assembler and not
>> generating LLVM code directly?
>
> You mean write C++ code that calls the LLVM library ?
> I have a mild C++ allergy that I don't wish to aggravate.
>
>> The later is simpler and relieves you
>> from some nasty burdens.
>
> Yes, i'm finding it quite hairy!
>
> :)
>
> Simon.
>
>

-Chris

--
http://nondot.org/sabre/
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: Re: how to code a loop in llvm assembly

Ralph Corderoy

Hi,

Chris Lattner wrote:
> if there is serious interest, many people would like an easy to use C
> wrapper around the LLVM API's.
>
> ...
>
> This is a way that those with "C++ Allergies" could band together and
> help each other out :)

I'm hoping the PyPy effort will see the start of a C interface to LLVM
that can be filled out as others need more bits.  I'm another one that's
+1 for a C interface.  :-)

Cheers,


Ralph.


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