Marc:
Thanks for beta 22.
As you ware well aware, in the bignum code, we access the bignum
digits either as adigits (usually 64 bits), mdigits (16 or 32 bits,
depending on word size) and fdigits (8 bits), and we do it by casting
pointers, which is no longer allowed by the C standard. The standard
way to do it would be to write it as a structure containing two
elements, the first being the header word, and the second being a
union of {array of adigits, array of mdigits, array of fdigits} and
then accessing the various bignum digits through these arrays. This
is one of the few things in the back end that requires us to put -fno-
strict-aliasing in the gcc command line as a gcc extension. (We also
exploit the fact that signed integer arithmetic wraps on overflow on
all current hardware, but signed integer overflow is undefined in
standard C, so we need the -ftrapv flag.)
I thought I might see what affect the -fno-strict-aliasing is having
on the generated code, so I took the inner loop in the fft code:
> ___DEF_GLBL(___L12_direct_2d_fft_2d_recursive)
> ___SET_R4(___FIXADD(___R3,___FIX(1L)))
> ___SET_STK(1,___FIXADD(___R3,___STK(-1)))
> ___SET_STK(2,___FIXADD(___STK(1),___FIX(1L)))
> ___SET_F64(___F64V1,___F64VECTORREF(___STK(-4),___STK(2)))
> ___SET_F64(___F64V2,___F64VECTORREF(___STK(-4),___STK(1)))
> ___SET_F64(___F64V3,___F64VECTORREF(___STK(-4),___R4))
> ___SET_F64(___F64V4,___F64VECTORREF(___STK(-4),___R3))
> ___SET_F64(___F64V5,___F64VECTORREF(___STK(0),___FIX(1L)))
> ___SET_F64(___F64V6,___F64VECTORREF(___STK(0),___FIX(0L)))
> ___SET_F64(___F64V7,___F64MUL(___F64V5,___F64V2))
> ___SET_F64(___F64V8,___F64MUL(___F64V6,___F64V1))
> ___SET_F64(___F64V9,___F64ADD(___F64V8,___F64V7))
> ___SET_F64(___F64V10,___F64MUL(___F64V5,___F64V1))
> ___SET_F64(___F64V11,___F64MUL(___F64V6,___F64V2))
> ___SET_F64(___F64V12,___F64SUB(___F64V11,___F64V10))
> ___SET_F64(___F64V13,___F64SUB(___F64V3,___F64V9))
> ___SET_F64(___F64V14,___F64SUB(___F64V4,___F64V12))
> ___SET_F64(___F64V15,___F64ADD(___F64V3,___F64V9))
> ___SET_F64(___F64V16,___F64ADD(___F64V4,___F64V12))
> ___F64VECTORSET(___STK(-4),___R3,___F64V16)
> ___F64VECTORSET(___STK(-4),___R4,___F64V15)
> ___F64VECTORSET(___STK(-4),___STK(1),___F64V14)
> ___F64VECTORSET(___STK(-4),___STK(2),___F64V13)
> ___SET_R3(___FIXADD(___R3,___FIX(2L)))
> ___IF(___FIXLT(___R3,___R2))
> ___GOTO(___L12_direct_2d_fft_2d_recursive)
You'll see that there are lots of loads of stack variables, and with -
fno-strict-aliasing, gcc doesn't know whether the stores to the
floating-point arrays overwrite the integer stack variables, so it
has to reread the variables from the stack again; in fact, it has to
reload them from the stack after every floating-point store! This
loop is scheduled on the G5 in 112 cycles:
> ;; 0--> 1397 r2=[r7+0x8] :lsq_power4
> ;; 0--> 1394 r30=r28+0x4 :iq_power4
> ;; 0--> 1420 r0=r28<<0x1 :iq_power4
> ;; 2--> 1416 r10=r30<<0x1 :iq_power4
> ;; 4--> 1398 r2=r28+r2 :iq_power4
> ;; 4--> 1462 r28=r28+0x8 :iq_power4
> ;; 6--> 1399 [r8]=r2 :
> (du1_power4,lsu1_power4,iu1_power4)|
> (du2_power4,lsu2_power4,iu2_power4)|
> (du3_power4,lsu2_power4,iu2_power4)|
> (du4_power4,lsu1_power4,iu1_power4)
> ;; 6--> 1402 r2=r2+0x4 :iq_power4
> ;; 6--> 1464 cr7=cmp(r6,r28) :iq_power4
> ;; 8--> 1403 [r7-0x10]=r2 :
> (du1_power4,lsu1_power4,iu1_power4)|
> (du2_power4,lsu2_power4,iu2_power4)|
> (du3_power4,lsu2_power4,iu2_power4)|
> (du4_power4,lsu1_power4,iu1_power4)
> ;; 8--> 1407 r2=r2<<0x1 :iq_power4
> ;; 18--> 1406 r11=[r7+0x20] :lsq_power4
> ;; 20--> 1411 r9=[r8] :lsq_power4
> ;; 22--> 1408 r2=r11+r2 :iq_power4
> ;; 24--> 1409 f12=[r2+0x7] :lsq_power4
> ;; 24--> 1417 r2=r11+r10 :iq_power4
> ;; 24--> 1412 r9=r9<<0x1 :iq_power4
> ;; 26--> 1418 f8=[r2+0x7] :lsq_power4
> ;; 26--> 1425 r2=[r7] :lsq_power4
> ;; 26--> 1413 r9=r11+r9 :iq_power4
> ;; 26--> 1421 r11=r11+r0 :iq_power4
> ;; 28--> 1414 f10=[r9+0x7] :lsq_power4
> ;; 28--> 1423 f11=[r11+0x7] :lsq_power4
> ;; 30--> 1430 f13=[r2+0x7] :lsq_power4
> ;; 30--> 1427 f0=[r2+0xf] :lsq_power4
> ;; 36--> 1433 f9=f12*f13 :fpq_power4
> ;; 36--> 1437 f12=f12*f0 :fpq_power4
> ;; 42--> 1434 f9=f10*f0+f9 :fpq_power4
> ;; 42--> 1438 f10=f10*f13-f12 :fpq_power4
> ;; 48--> 1440 f0=f11+f10 :fpq_power4
> ;; 48--> 1452 f11=f11-f10 :fpq_power4
> ;; 54--> 1441 [r11+0x7]=f0 :
> (du1_power4,lsu1_power4,fpu1_power4)|
> (du2_power4,lsu2_power4,fpu2_power4)|
> (du3_power4,lsu2_power4,fpu2_power4)|
> (du4_power4,lsu1_power4,fpu1_power4)
> ;; 54--> 1445 f0=f8+f9 :fpq_power4
> ;; 54--> 1459 f8=f8-f9 :fpq_power4
> ;; 66--> 1443 r0=[r7+0x20] :lsq_power4
> ;; 70--> 1444 r10=r10+r0 :iq_power4
> ;; 72--> 1446 [r10+0x7]=f0 :
> (du1_power4,lsu1_power4,fpu1_power4)|
> (du2_power4,lsu2_power4,fpu2_power4)|
> (du3_power4,lsu2_power4,fpu2_power4)|
> (du4_power4,lsu1_power4,fpu1_power4)
> ;; 84--> 1448 r0=[r8] :lsq_power4
> ;; 84--> 1450 r2=[r7+0x20] :lsq_power4
> ;; 88--> 1449 r0=r0<<0x1 :iq_power4
> ;; 90--> 1451 r2=r2+r0 :iq_power4
> ;; 92--> 1453 [r2+0x7]=f11 :
> (du1_power4,lsu1_power4,fpu1_power4)|
> (du2_power4,lsu2_power4,fpu2_power4)|
> (du3_power4,lsu2_power4,fpu2_power4)|
> (du4_power4,lsu1_power4,fpu1_power4)
> ;; 104--> 1455 r0=[r7-0x10] :lsq_power4
> ;; 104--> 1457 r2=[r7+0x20] :lsq_power4
> ;; 108--> 1456 r0=r0<<0x1 :iq_power4
> ;; 110--> 1458 r2=r2+r0 :iq_power4
> ;; 112--> 1460 [r2+0x7]=f8 :
> (du1_power4,lsu1_power4,fpu1_power4)|
> (du2_power4,lsu2_power4,fpu2_power4)|
> (du3_power4,lsu2_power4,fpu2_power4)|
> (du4_power4,lsu1_power4,fpu1_power4)
> ;; 112--> 1465 pc={(cr7>0x0)?L5577:pc} :du5_power4|
> (du4_power4+du5_power4)|(du3_power4+du4_power4+du5_power4)|
> (du2_power4+du3_power4+du4_power4+du5_power4)|(du1_power4+du2_power4
> +du3_power4+du4_power4+du5_power4),bpu_power4
Just for fun, I added -fstrict-aliasing to the command line in gsc-cc-
o and found that the same look is scheduled in 48 cycles:
> ;; 0--> 1397 r9=[r7+0x8] :lsq_power4
> ;; 0--> 1394 r30=r28+0x4 :iq_power4
> ;; 0--> 1420 r0=r28<<0x1 :iq_power4
> ;; 2--> 1416 r8=r30<<0x1 :iq_power4
> ;; 4--> 1398 r9=r28+r9 :iq_power4
> ;; 4--> 1462 r28=r28+0x8 :iq_power4
> ;; 6--> 1399 [r6]=r9 :
> (du1_power4,lsu1_power4,iu1_power4)|
> (du2_power4,lsu2_power4,iu2_power4)|
> (du3_power4,lsu2_power4,iu2_power4)|
> (du4_power4,lsu1_power4,iu1_power4)
> ;; 6--> 1402 r9=r9+0x4 :iq_power4
> ;; 6--> 1464 cr7=cmp(r5,r28) :iq_power4
> ;; 8--> 1403 [r7-0x10]=r9 :
> (du1_power4,lsu1_power4,iu1_power4)|
> (du2_power4,lsu2_power4,iu2_power4)|
> (du3_power4,lsu2_power4,iu2_power4)|
> (du4_power4,lsu1_power4,iu1_power4)
> ;; 8--> 1407 r9=r9<<0x1 :iq_power4
> ;; 18--> 1406 r11=[r7+0x20] :lsq_power4
> ;; 18--> 1425 r2=[r7] :lsq_power4
> ;; 20--> 1411 r10=[r6] :lsq_power4
> ;; 22--> 1408 r9=r11+r9 :iq_power4
> ;; 22--> 1427 f0=[r2+0xf] :lsq_power4
> ;; 22--> 1430 f13=[r2+0x7] :lsq_power4
> ;; 23--> 1417 r8=r11+r8 :iq_power4
> ;; 24--> 1409 f9=[r9+0x7] :lsq_power4
> ;; 24--> 1412 r10=r10<<0x1 :iq_power4
> ;; 25--> 1418 f8=[r8+0x7] :lsq_power4
> ;; 26--> 1413 r10=r11+r10 :iq_power4
> ;; 26--> 1421 r11=r11+r0 :iq_power4
> ;; 28--> 1414 f10=[r10+0x7] :lsq_power4
> ;; 28--> 1423 f11=[r11+0x7] :lsq_power4
> ;; 30--> 1433 f12=f9*f13 :fpq_power4
> ;; 30--> 1437 f9=f9*f0 :fpq_power4
> ;; 36--> 1434 f12=f10*f0+f12 :fpq_power4
> ;; 36--> 1438 f10=f10*f13-f9 :fpq_power4
> ;; 42--> 1445 f13=f8+f12 :fpq_power4
> ;; 42--> 1440 f0=f11+f10 :fpq_power4
> ;; 43--> 1459 f8=f8-f12 :fpq_power4
> ;; 43--> 1452 f11=f11-f10 :fpq_power4
> ;; 48--> 1441 [r11+0x7]=f0 :
> (du1_power4,lsu1_power4,fpu1_power4)|
> (du2_power4,lsu2_power4,fpu2_power4)|
> (du3_power4,lsu2_power4,fpu2_power4)|
> (du4_power4,lsu1_power4,fpu1_power4)
> ;; 48--> 1446 [r8+0x7]=f13 :
> (du1_power4,lsu1_power4,fpu1_power4)|
> (du2_power4,lsu2_power4,fpu2_power4)|
> (du3_power4,lsu2_power4,fpu2_power4)|
> (du4_power4,lsu1_power4,fpu1_power4)
> ;; 49--> 1453 [r10+0x7]=f11 :
> (du1_power4,lsu1_power4,fpu1_power4)|
> (du2_power4,lsu2_power4,fpu2_power4)|
> (du3_power4,lsu2_power4,fpu2_power4)|
> (du4_power4,lsu1_power4,fpu1_power4)
> ;; 49--> 1460 [r9+0x7]=f8 :
> (du1_power4,lsu1_power4,fpu1_power4)|
> (du2_power4,lsu2_power4,fpu2_power4)|
> (du3_power4,lsu2_power4,fpu2_power4)|
> (du4_power4,lsu1_power4,fpu1_power4)
> ;; 49--> 1465 pc={(cr7>0x0)?L5587:pc} :du5_power4|
> (du4_power4+du5_power4)|(du3_power4+du4_power4+du5_power4)|
> (du2_power4+du3_power4+du4_power4+du5_power4)|(du1_power4+du2_power4
> +du3_power4+du4_power4+du5_power4),bpu_power4
For this code, -fstrict-aliasing doesn't make any difference in
correctness (we're accessing bignums only as fdigits), and once
you're outside the second-level cache this speedup is not a factor of
2, but about 15%:
> [descartes:~/programs/gambc40b17/fftmul] lucier% gsc
> Gambit Version 4.0 beta 22
>
> > (load "fftmul-fast.o12")
> "/Users/lucier/programs/gambc40b17/fftmul/fftmul-fast.o12"
> > (define a (time (expt 3 10000000)))
> (time (expt 3 10000000))
> 2384 ms real time
> 1860 ms cpu time (1708 user, 152 system)
> 9 collections accounting for 63 ms real time (28 user, 20 system)
> 110237992 bytes allocated
> no minor faults
> no major faults
> > (define b (time (* a a)))
> (time (* a a))
> 2477 ms real time
> 2066 ms cpu time (1914 user, 152 system)
> 2 collections accounting for 28 ms real time (7 user, 21 system)
> 110229552 bytes allocated
> no minor faults
> no major faults
> > (define c (time (fft-mul a a)))
> (time (fft-mul a a))
> 2557 ms real time
> 2089 ms cpu time (1858 user, 231 system)
> 1 collection accounting for 45 ms real time (4 user, 40 system)
> 112621200 bytes allocated
> no minor faults
> no major faults
> > (load "fftmul-fast.o13")
> "/Users/lucier/programs/gambc40b17/fftmul/fftmul-fast.o13"
> > (define c (time (fft-mul a a)))
> (time (fft-mul a a))
> 2899 ms real time
> 2387 ms cpu time (2123 user, 264 system)
> 1 collection accounting for 78 ms real time (4 user, 73 system)
> 112621200 bytes allocated
> no minor faults
> no major faults
> > (integer-length c)
> 31699251
This is using 64MB per fft.
But this experiment is very intriguing. Changing the C code so it
does not do pointer casting to incompatible types and setting -
fstrict-aliasing might give a significant speedup to general code.
Also, changing the overflow checks to use only unsigned integer
arithmetic (which is *defined* to wrap in standard C) would allow us
to get rid of -ftrapv. That would enable other optimizations in gcc.
Brad
