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