On writing JITs

[Nicholas Clark]

Am I allowed to write ancillary functions I want the JIT to call in
assembler? I presume that the JIT needs to go fast, and I suspect that there
are some bits that are easier to write in assembler (eg rotates for figuring
out constants) than in C, for the same amount of eventual speed.

I guess it comes down to, are we assuming that the JIT always be run on the
CPU which is is targeting? I suspect the answer ought to be "avoid the
special case" and so the answer to my original question should be "no, make
the JIT portable"

Nicholas Clark
--
Even better than the real thing: http://nms-cgi.sourceforge.net/

[Dan Sugalski]

At 9:42 PM +0100 8/1/02, Nicholas Clark wrote:
>Am I allowed to write ancillary functions I want the JIT to call in
>assembler? I presume that the JIT needs to go fast, and I suspect that there
>are some bits that are easier to write in assembler (eg rotates for figuring
>out constants) than in C, for the same amount of eventual speed.
>
>I guess it comes down to, are we assuming that the JIT always be run on the
>CPU which is is targeting? I suspect the answer ought to be "avoid the
>special case" and so the answer to my original question should be "no, make
>the JIT portable"

It's the JIT--evil things for speed reasons are almost obligatory. :)

Sure, go ahead and write whatever you want in assembler for the
target platform. Just make sure that you'll assemble on that
platform, and we'll be fine.
--
Dan

--------------------------------------"it's like this"-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk

[Richard Prescott]

On Thu, 1 Aug 2002, Dan Sugalski wrote:

> At 9:42 PM +0100 8/1/02, Nicholas Clark wrote:
> >Am I allowed to write ancillary functions I want the JIT to call in
> >assembler? I presume that the JIT needs to go fast, and I suspect that there
> >are some bits that are easier to write in assembler (eg rotates for figuring
> >out constants) than in C, for the same amount of eventual speed.
> >
> >I guess it comes down to, are we assuming that the JIT always be run on the
> >CPU which is is targeting? I suspect the answer ought to be "avoid the
> >special case" and so the answer to my original question should be "no, make
> >the JIT portable"
>
> It's the JIT--evil things for speed reasons are almost obligatory. :)
>
> Sure, go ahead and write whatever you want in assembler for the
> target platform. Just make sure that you'll assemble on that
> platform, and we'll be fine.
> --
> Dan

IMHO, C version shall exist anyway, for speed comparaison first (it is
always surprising how good compilers can be in some situations), then you
could find tricks that are faster on some processors (let's say AMD) and
not on some others for the same instructions set.

I still encourage the asm version.

my .02$

Richard

[Nicholas Clark]

On Fri, Aug 02, 2002 at 03:59:28PM -0400, Richard Prescott wrote:
> IMHO, C version shall exist anyway, for speed comparaison first (it is
> always surprising how good compilers can be in some situations), then you
> could find tricks that are faster on some processors (let's say AMD) and
> not on some others for the same instructions set.
>
> I still encourage the asm version.

The arm backend on gcc isn't always that good. I'm told its because gcc is
not really architectured on the basis that the target machine could have
all instructions conditional.

In the end I decided that it's faster for me to write C now, particularly
as the JIT may well change again a few times, but I did resort to assembler
for a single 32 bit rotate instruction, as it's terser than writing it in
C as 2 shifts orred together plus casting to unsigned to avoid sign extension.

Another question:

Is there an easy way for the jit op implementation to have a peek at its
parameters, and then decide "too hard" and fall back to inserting the code
to call the real parrot op?

I'm thinking of the case of DIV $1, $2, constant
where I'd like to be able to write (in pseudocode)

Parrot_div_i_i_ic {
if (op3 == 2) {
op1 = op2 >> 2
} else {
call the C subroutine that the jit normally uses
}
}

[I'm assuming that dividing by 2 may well be a common enough case to be
interesting, and ARM has no hardware divide, so without this I'd have to choose
between a shift operator and implementing a call to division subroutine.

It seems that foo & (foo - 1) is zero only for a power of 2 (or foo == 0)
but is there a fast way once you know that foo is a power of 2, to find out
log2 foo?

I presume in the general case I'd have to know whether to call
Parrot_jit_normal_op() or Parrot_jit_cpcf_op(), so could there be a subroutine
in jit.c that I could call to make the correct decision for me?

[Ken Fox]

Nicholas Clark wrote:
> It seems that foo & (foo - 1) is zero only for a power of 2 (or foo == 0)
> but is there a fast way once you know that foo is a power of 2, to find out
> log2 foo?

You're right about (foo & (foo -1)).

gcc uses a repeated test and shift. That's works very nicely if foo
is small -- and I bet it usually is. If you want to protect yourself
from the cases where foo is large, you can unroll the loop 2 or 3 times
and then use a binary search.

I've attached two simple implementations I wrote. Neither log2()
implementation is from gcc, so don't worry about GPL contamination.

- Ken

#include <stdio.h>
#include <assert.h>

int simple_log2(int foo) {
int log = 0;

assert((foo & (foo - 1)) == 0);

while (foo) {
++log;
foo >>= 1;
}

--log;

return log;
}

int unrolled_log2(int foo) {
int log = 0;
int mid = 4 * sizeof(foo);

assert(foo != 0);
assert((foo & (foo - 1)) == 0);

foo >>= 1;
if (foo == 0) goto done;
foo >>= 1; ++log;
if (foo == 0) goto done;
foo >>= 1; ++log;
if (foo == 0) goto done;

do {
if (foo >= (1 << mid)) {
foo >>= mid;
log += mid;
}
mid >>= 1;
}
while (mid);

++log;

done:

return log;
}

int main(int argc, char *argv[]) {

#if 1

int i = 1;
while (i < (1 << 30)) {
printf("log2(%d) == %d\n", i, unrolled_log2(i));
i <<= 1;
}

#else

/* simple timing loop */

int i = 10000000;
volatile int j;
while (i > 0) {
j = unrolled_log2(1 << 29);
j = unrolled_log2(2);
j = simple_log2(1 << 29);
j = simple_log2(2);
--i;
}

#endif

return 0;
}

[Jason Gloudon]

On Sat, Aug 03, 2002 at 11:35:08AM +0100, Nicholas Clark wrote:

> I presume in the general case I'd have to know whether to call
> Parrot_jit_normal_op() or Parrot_jit_cpcf_op(), so could there be a subroutine
> in jit.c that I could call to make the correct decision for me?

Here is a patch for the necessary function.

Index: jit.c
===================================================================
RCS file: /cvs/public/parrot/jit.c,v
retrieving revision 1.21
diff -u -r1.21 jit.c
--- jit.c 2 Aug 2002 03:24:02 -0000 1.21
+++ jit.c 3 Aug 2002 19:13:05 -0000
@@ -303,6 +303,18 @@
(ptrdiff_t)(jit_info->native_ptr - jit_info->arena_start);
}

+/* An op jitting function can call this function to emit the appropriate
+ * generic code to invoke the op function for the current op */
+
+void Parrot_jit_fallback(Parrot_jit_info *jit_info, struct Parrot_Interp * interpreter){
+ if(interpreter->op_info_table[*jit_info->cur_op].jump){
+ Parrot_jit_cpcf_op(jit_info, interpreter);
+ }
+ else {
+ Parrot_jit_normal_op(jit_info, interpreter);
+ }
+}
+
/*
* Local variables:
* c-indentation-style: bsd
Index: include/parrot/jit.h
===================================================================
RCS file: /cvs/public/parrot/include/parrot/jit.h,v
retrieving revision 1.16
diff -u -r1.16 jit.h
--- include/parrot/jit.h 7 Jun 2002 04:58:45 -0000 1.16
+++ include/parrot/jit.h 3 Aug 2002 19:13:06 -0000
@@ -97,6 +97,8 @@
struct Parrot_Interp * interpreter);
void Parrot_jit_normal_op(Parrot_jit_info *jit_info,
struct Parrot_Interp * interpreter);
+void Parrot_jit_fallback(Parrot_jit_info *jit_info,
+ struct Parrot_Interp * interpreter);

Parrot_jit_optimizer_t *
optimize_jit(struct Parrot_Interp *,

--
Jason

[Jason Gloudon]

On Sat, Aug 03, 2002 at 12:07:30PM -0400, Ken Fox wrote:
> Nicholas Clark wrote:
> >It seems that foo & (foo - 1) is zero only for a power of 2 (or foo == 0)
> >but is there a fast way once you know that foo is a power of 2, to find out
> >log2 foo?

The ARM doesn't have a find first set bit instruction ?

This code includes 3 different ways of finding log2.

http://www.ddj.com/ftp/2001/2001_07/aa0701.txt

I believe the LOOKUP method was the fastest for me on SPARC, if I recall
correctly.

--
Jason

[Ken Fox]

Jason Gloudon wrote:
> http://www.ddj.com/ftp/2001/2001_07/aa0701.txt
>
> I believe the LOOKUP method was the fastest for me on SPARC, if I recall
> correctly.

Did they really spend 64K to create a lookup table just to find
the most significant bit? Calculating log2 for a power of two is
simpler -- all you need to find is the one set bit. If you really
want to use lookup tables, just use an 8 byte table and shift
by 4 bits until a non-zero is found. (Change constants to taste.)

- Ken

[Uri Guttman]

it is the old space/time tradeoff. a 64k table can do this in one lookup
and no loops so it should be fastest (excluding cache hit issues and
such).

uri

--
Uri Guttman ------ u...@stemsystems.com -------- http://www.stemsystems.com
----- Stem and Perl Development, Systems Architecture, Design and Coding ----
Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org