1230025Sed/* 2230025Sed * This m4 code has been taken from The SPARC Architecture Manual Version 8. 3230025Sed */ 4230025Sed 5230025Sed/* 6230025Sed * Division/Remainder 7230025Sed * 8230025Sed * Input is: 9230025Sed * dividend -- the thing being divided 10230025Sed * divisor -- how many ways to divide it 11230025Sed * Important parameters: 12230025Sed * N -- how many bits per iteration we try to get 13230025Sed * as our current guess: define(N, 4) define(TWOSUPN, 16) 14230025Sed * WORDSIZE -- how many bits altogether we're talking about: 15230025Sed * obviously: define(WORDSIZE, 32) 16230025Sed * A derived constant: 17230025Sed * TOPBITS -- how many bits are in the top "decade" of a number: 18230025Sed * define(TOPBITS, eval( WORDSIZE - N*((WORDSIZE-1)/N) ) ) 19230025Sed * Important variables are: 20230025Sed * Q -- the partial quotient under development -- initially 0 21230025Sed * R -- the remainder so far -- initially == the dividend 22230025Sed * ITER -- number of iterations of the main division loop which will 23230025Sed * be required. Equal to CEIL( lg2(quotient)/N ) 24230025Sed * Note that this is log_base_(2��N) of the quotient. 25230025Sed * V -- the current comparand -- initially divisor*2��(ITER*N-1) 26230025Sed * Cost: 27230025Sed * current estimate for non-large dividend is 28230025Sed * CEIL( lg2(quotient) / N ) x ( 10 + 7N/2 ) + C 29230025Sed * a large dividend is one greater than 2��(31-TOPBITS) and takes a 30230025Sed * different path, as the upper bits of the quotient must be developed 31230025Sed * one bit at a time. 32230025Sed * This uses the m4 and cpp macro preprocessors. 33230025Sed */ 34230025Sed 35230025Seddefine(dividend, `%o0') 36230025Seddefine(divisor,`%o1') 37230025Seddefine(Q, `%o2') 38230025Seddefine(R, `%o3') 39230025Seddefine(ITER, `%o4') 40230025Seddefine(V, `%o5') 41230025Seddefine(SIGN, `%g3') 42230025Seddefine(T, `%g1') 43230025Seddefine(SC,`%g2') 44230025Sed/* 45230025Sed * This is the recursive definition of how we develop quotient digits. 46230025Sed * It takes three important parameters: 47230025Sed * $1 -- the current depth, 1<=$1<=N 48230025Sed * $2 -- the current accumulation of quotient bits 49230025Sed * N -- max depth 50230025Sed * We add a new bit to $2 and either recurse or insert the bits in the quotient. 51230025Sed * Dynamic input: 52230025Sed * R -- current remainder 53230025Sed * Q -- current quotient 54230025Sed * V -- current comparand 55230025Sed * cc -- set on current value of R 56230025Sed * Dynamic output: 57230025Sed * R', Q', V', cc' 58230025Sed */ 59230025Sed 60230025Sed#include "../assembly.h" 61230025Sed 62230025Seddefine(DEVELOP_QUOTIENT_BITS, 63230025Sed` !depth $1, accumulated bits $2 64230025Sed bl L.$1.eval(TWOSUPN+$2) 65230025Sed srl V,1,V 66230025Sed ! remainder is nonnegative 67230025Sed subcc R,V,R 68230025Sed ifelse( $1, N, 69230025Sed ` b 9f 70230025Sed add Q, ($2*2+1), Q 71230025Sed ',` DEVELOP_QUOTIENT_BITS( incr($1), `eval(2*$2+1)') 72230025Sed ') 73230025SedL.$1.eval(TWOSUPN+$2): 74230025Sed ! remainder is negative 75230025Sed addcc R,V,R 76230025Sed ifelse( $1, N, 77230025Sed ` b 9f 78230025Sed add Q, ($2*2-1), Q 79230025Sed ',` DEVELOP_QUOTIENT_BITS( incr($1), `eval(2*$2-1)') 80230025Sed ') 81230025Sed ifelse( $1, 1, `9:') 82230025Sed') 83230025Sedifelse( ANSWER, `quotient', ` 84235388Smarius.text 85235388Smarius .align 32 86230025SedDEFINE_COMPILERRT_FUNCTION(__udivsi3) 87230025Sed b divide 88230025Sed mov 0,SIGN ! result always nonnegative 89235388Smarius.text 90235388Smarius .align 32 91230025SedDEFINE_COMPILERRT_FUNCTION(__divsi3) 92230025Sed orcc divisor,dividend,%g0 ! are either dividend or divisor negative 93230025Sed bge divide ! if not, skip this junk 94230025Sed xor divisor,dividend,SIGN ! record sign of result in sign of SIGN 95230025Sed tst divisor 96230025Sed bge 2f 97230025Sed tst dividend 98230025Sed ! divisor < 0 99230025Sed bge divide 100230025Sed neg divisor 101230025Sed 2: 102230025Sed ! dividend < 0 103230025Sed neg dividend 104230025Sed ! FALL THROUGH 105230025Sed',` 106235388Smarius.text 107235388Smarius .align 32 108230025SedDEFINE_COMPILERRT_FUNCTION(__umodsi3) 109230025Sed b divide 110230025Sed mov 0,SIGN ! result always nonnegative 111235388Smarius.text 112235388Smarius .align 32 113230025SedDEFINE_COMPILERRT_FUNCTION(__modsi3) 114230025Sed orcc divisor,dividend,%g0 ! are either dividend or divisor negative 115230025Sed bge divide ! if not, skip this junk 116230025Sed mov dividend,SIGN ! record sign of result in sign of SIGN 117230025Sed tst divisor 118230025Sed bge 2f 119230025Sed tst dividend 120230025Sed ! divisor < 0 121230025Sed bge divide 122230025Sed neg divisor 123230025Sed 2: 124230025Sed ! dividend < 0 125230025Sed neg dividend 126230025Sed ! FALL THROUGH 127230025Sed') 128230025Sed 129230025Seddivide: 130230025Sed ! Compute size of quotient, scale comparand. 131230025Sed orcc divisor,%g0,V ! movcc divisor,V 132230025Sed te 2 ! if divisor = 0 133230025Sed mov dividend,R 134230025Sed mov 0,Q 135230025Sed sethi %hi(1<<(WORDSIZE-TOPBITS-1)),T 136230025Sed cmp R,T 137230025Sed blu not_really_big 138230025Sed mov 0,ITER 139230025Sed ! 140230025Sed ! Here, the dividend is >= 2��(31-N) or so. We must be careful here, 141230025Sed ! as our usual N-at-a-shot divide step will cause overflow and havoc. 142230025Sed ! The total number of bits in the result here is N*ITER+SC, where 143230025Sed ! SC <= N. 144230025Sed ! Compute ITER in an unorthodox manner: know we need to Shift V into 145230025Sed! the top decade: so don't even bother to compare to R. 146230025Sed1: 147230025Sed cmp V,T 148230025Sed bgeu 3f 149230025Sed mov 1,SC 150230025Sed sll V,N,V 151230025Sed b 1b 152230025Sed inc ITER 153230025Sed! Now compute SC 154230025Sed2: addcc V,V,V 155230025Sed bcc not_too_big 156230025Sed add SC,1,SC 157230025Sed ! We're here if the divisor overflowed when Shifting. 158230025Sed ! This means that R has the high-order bit set. 159230025Sed ! Restore V and subtract from R. 160230025Sed sll T,TOPBITS,T ! high order bit 161230025Sed srl V,1,V ! rest of V 162230025Sed add V,T,V 163230025Sed b do_single_div 164230025Sed dec SC 165230025Sednot_too_big: 166230025Sed3: cmp V,R 167230025Sed blu 2b 168230025Sed nop 169230025Sed be do_single_div 170230025Sed nop 171230025Sed! V > R: went too far: back up 1 step 172230025Sed! srl V,1,V 173230025Sed! dec SC 174230025Sed! do single-bit divide steps 175230025Sed! 176230025Sed! We have to be careful here. We know that R >= V, so we can do the 177230025Sed! first divide step without thinking. BUT, the others are conditional, 178230025Sed! and are only done if R >= 0. Because both R and V may have the high- 179230025Sed! order bit set in the first step, just falling into the regular 180230025Sed! division loop will mess up the first time around. 181230025Sed! So we unroll slightly... 182230025Seddo_single_div: 183230025Sed deccc SC 184230025Sed bl end_regular_divide 185230025Sed nop 186230025Sed sub R,V,R 187230025Sed mov 1,Q 188235388Smarius b,a end_single_divloop 189235388Smarius ! EMPTY 190230025Sedsingle_divloop: 191230025Sed sll Q,1,Q 192230025Sed bl 1f 193230025Sed srl V,1,V 194230025Sed ! R >= 0 195230025Sed sub R,V,R 196230025Sed b 2f 197230025Sed inc Q 198230025Sed 1: ! R < 0 199230025Sed add R,V,R 200230025Sed dec Q 201230025Sed 2: 202230025Sed end_single_divloop: 203230025Sed deccc SC 204230025Sed bge single_divloop 205230025Sed tst R 206235388Smarius b,a end_regular_divide 207235388Smarius ! EMPTY 208230025Sed 209230025Sednot_really_big: 210230025Sed1: 211230025Sed sll V,N,V 212230025Sed cmp V,R 213230025Sed bleu 1b 214230025Sed inccc ITER 215230025Sed be got_result 216230025Sed dec ITER 217230025Seddo_regular_divide: 218230025Sed ! Do the main division iteration 219230025Sed tst R 220230025Sed ! Fall through into divide loop 221230025Seddivloop: 222230025Sed sll Q,N,Q 223230025Sed DEVELOP_QUOTIENT_BITS( 1, 0 ) 224230025Sedend_regular_divide: 225230025Sed deccc ITER 226230025Sed bge divloop 227230025Sed tst R 228235388Smarius bl,a got_result 229235388Smarius ! non-restoring fixup if remainder < 0, otherwise annulled 230230025Sedifelse( ANSWER, `quotient', 231230025Sed` dec Q 232230025Sed',` add R,divisor,R 233230025Sed') 234230025Sed 235230025Sedgot_result: 236230025Sed tst SIGN 237235388Smarius bl,a 1f 238235388Smarius ! negate for answer < 0, otherwise annulled 239230025Sedifelse( ANSWER, `quotient', 240235388Smarius` neg %o2,%o2 ! Q <- -Q 241235388Smarius',` neg %o3,%o3 ! R <- -R 242230025Sed') 243230025Sed1: 244230025Sed retl ! leaf-routine return 245230025Sedifelse( ANSWER, `quotient', 246230025Sed` mov %o2,%o0 ! quotient <- Q 247230025Sed',` mov %o3,%o0 ! remainder <- R 248230025Sed') 249