jump table ?

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

jump table ?

Simon Burton

Is it possible to take the address
of a basic block ?
I'd like to put a whole bunch of these
addresses into an array, and then select
one to branch to. Eg. like a switch statement.
(i'm thinking also of GCC's computed goto's)

I'm finding the code generated by an llvm switch
is a big bunch of compares and jump instructions,
which i'm not sure is the most efficent way of
doing this.

GCC generates jump tables for big switches.

Simon.
_______________________________________________
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: jump table ?

Chris Lattner
On Wed, 28 Jun 2006, Simon Burton wrote:
> Is it possible to take the address
> of a basic block ?

Nope.

> I'd like to put a whole bunch of these
> addresses into an array, and then select
> one to branch to. Eg. like a switch statement.
> (i'm thinking also of GCC's computed goto's)

llvm-gcc supports gcc's computed goto's.  You can see what code it
generates.

> I'm finding the code generated by an llvm switch
> is a big bunch of compares and jump instructions,
> which i'm not sure is the most efficent way of
> doing this.

LLVM does support switch table emission, but only in certain modes.  I
think it's only supported in non-pic codegen mode.  Patches to improve
this would be welcome :)

-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: jump table ?

Simon Burton
On Wed, 28 Jun 2006 11:53:56 -0500 (CDT)
Chris Lattner <[hidden email]> wrote:

> On Wed, 28 Jun 2006, Simon Burton wrote:
> > Is it possible to take the address
> > of a basic block ?
>
> Nope.
>
> > I'd like to put a whole bunch of these
> > addresses into an array, and then select
> > one to branch to. Eg. like a switch statement.
> > (i'm thinking also of GCC's computed goto's)
>
> llvm-gcc supports gcc's computed goto's.  You can see what code it
> generates.

Yes: a bunch of switch statements.

>
> > I'm finding the code generated by an llvm switch
> > is a big bunch of compares and jump instructions,
> > which i'm not sure is the most efficent way of
> > doing this.
>
> LLVM does support switch table emission, but only in certain modes.  I
> think it's only supported in non-pic codegen mode.  Patches to improve
> this would be welcome :)

I am not sure what "non-pic codegen mode" is.
PIC is relocatable code ? ie. object files ?
So if i'm using the JIT then it will generate a switch table ?
How can i test this, since
i've been examining the native assembly output (is this 'pic' mode?) of llc.

I guess I can compare the speed of a big switch construct with
a nest of branch statements and see if it's any faster.

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
_______________________________________________
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: jump table ?

Ralph Corderoy

Hi Simon,

> So if i'm using the JIT then it will generate a switch table ?  How
> can i test this, since i've been examining the native assembly output
> (is this 'pic' mode?) of llc.

Presumably the JIT means you end up with a `function pointer' that you
call to execute the just built code?  Can't you just save a lump of
memory starting at that address to a file and then run objdump(1) on it
to see what native instructions were generated?

objdump's -i option will show you the available file formats, one's
normally `binary' or something similar.

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: jump table ?

Simon Burton
On Thu, 29 Jun 2006 10:36:23 +0100
Ralph Corderoy <[hidden email]> wrote:

>
> Hi Simon,
>
> > So if i'm using the JIT then it will generate a switch table ?  How
> > can i test this, since i've been examining the native assembly output
> > (is this 'pic' mode?) of llc.
>
> Presumably the JIT means you end up with a `function pointer' that you
> call to execute the just built code?  Can't you just save a lump of
> memory starting at that address to a file and then run objdump(1) on it
> to see what native instructions were generated?
>
> objdump's -i option will show you the available file formats, one's
> normally `binary' or something similar.

I've had a look at this, and it's not yielding any results so far.
Surely objdump expects an elf header, symbol table, etc. ?

Simon.
_______________________________________________
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: jump table ?

Ralph Corderoy

Hi Simon,

> > objdump's -i option will show you the available file formats, one's
> > normally `binary' or something similar.
>
> I've had a look at this, and it's not yielding any results so far.
> Surely objdump expects an elf header, symbol table, etc. ?

Try

    objdump -D -b binary -m i386 /etc/passwd

objdump is happy to treat a file of bytes as nothing but machine
instructions with no headers, symbols tables, or other guff.

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: jump table ?

Simon Burton
On Thu, 29 Jun 2006 13:03:35 +0100
Ralph Corderoy <[hidden email]> wrote:

>
> Hi Simon,
>
> > > objdump's -i option will show you the available file formats, one's
> > > normally `binary' or something similar.
> >
> > I've had a look at this, and it's not yielding any results so far.
> > Surely objdump expects an elf header, symbol table, etc. ?
>
> Try
>
>     objdump -D -b binary -m i386 /etc/passwd

Wow.

OK, this is what I get:

       0:       81 ec 0c 08 00 00       sub    $0x80c,%esp
       6:       8b 84 24 10 08 00 00    mov    0x810(%esp),%eax
       d:       8a 00                   mov    (%eax),%al
       f:       80 f8 80                cmp    $0x80,%al
      12:       0f 82 c5 05 00 00       jb     0x5dd
      18:       e9 00 00 00 00          jmp    0x1d
      1d:       80 f8 c0                cmp    $0xc0,%al
      20:       0f 82 e0 02 00 00       jb     0x306
      26:       80 f8 e0                cmp    $0xe0,%al
      29:       0f 82 70 01 00 00       jb     0x19f
      2f:       80 f8 f0                cmp    $0xf0,%al
      32:       0f 82 b8 00 00 00       jb     0xf0
      38:       80 f8 f8                cmp    $0xf8,%al
      3b:       0f 82 5c 00 00 00       jb     0x9d
      41:       80 f8 fc                cmp    $0xfc,%al
      44:       0f 82 2e 00 00 00       jb     0x78
  ....

Which looks like the big switch statement that it comes from... yuck.

Simon.


_______________________________________________
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: jump table ?

Chris Lattner
In reply to this post by Simon Burton
On Thu, 29 Jun 2006, Simon Burton wrote:

>> LLVM does support switch table emission, but only in certain modes.  I
>> think it's only supported in non-pic codegen mode.  Patches to improve
>> this would be welcome :)
>
> I am not sure what "non-pic codegen mode" is.
> PIC is relocatable code ? ie. object files ?
> So if i'm using the JIT then it will generate a switch table ?
> How can i test this, since
> i've been examining the native assembly output (is this 'pic' mode?) of llc.
>
> I guess I can compare the speed of a big switch construct with
> a nest of branch statements and see if it's any faster.

Are you using LLVM 1.7 or CVS?  LLVM 1.7 never uses jump tables.


PIC = Position Independent Code.

You can see internal representation of the code generated by passing
-print-machineinstrs to the JIT, e.g.:

lli -print-machineinstrs program.bc <args>

You can control whether PIC is generated or not with LLC by using the
"llc -relocation-model=xyz" option.

Currently switches get lowered when not in PIC mode, and if the target
supports it.  The x86 and PPC targets support jump tables currently.
Also, only certain switches are lowered to jump tables: the table must
have high enough density for it to be worthwhile, etc.

If you're not getting a jump table and you think you should be, file a bug
and include the args passed to llc you are using.

-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: jump table ?

Simon Burton
On Thu, 29 Jun 2006 11:55:22 -0500 (CDT)
Chris Lattner <[hidden email]> wrote:

> Are you using LLVM 1.7 or CVS?  LLVM 1.7 never uses jump tables.
>

OK, switching to CVS fixes this. The code runs much faster now.
(and it looks like there are big tables in the assembly output)

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