2 * This m4 code has been taken from The SPARC Architecture Manual Version 8.
9 * dividend -- the thing being divided
10 * divisor -- how many ways to divide it
11 * Important parameters:
12 * N -- how many bits per iteration we try to get
13 * as our current guess: define(N, 4) define(TWOSUPN, 16)
14 * WORDSIZE -- how many bits altogether we're talking about:
15 * obviously: define(WORDSIZE, 32)
17 * TOPBITS -- how many bits are in the top "decade" of a number:
18 * define(TOPBITS, eval( WORDSIZE - N*((WORDSIZE-1)/N) ) )
19 * Important variables are:
20 * Q -- the partial quotient under development -- initially 0
21 * R -- the remainder so far -- initially == the dividend
22 * ITER -- number of iterations of the main division loop which will
23 * be required. Equal to CEIL( lg2(quotient)/N )
24 * Note that this is log_base_(2ˆN) of the quotient.
25 * V -- the current comparand -- initially divisor*2ˆ(ITER*N-1)
27 * current estimate for non-large dividend is
28 * CEIL( lg2(quotient) / N ) x ( 10 + 7N/2 ) + C
29 * a large dividend is one greater than 2ˆ(31-TOPBITS) and takes a
30 * different path, as the upper bits of the quotient must be developed
32 * This uses the m4 and cpp macro preprocessors.
35 define(dividend, `%o0')
45 * This is the recursive definition of how we develop quotient digits.
46 * It takes three important parameters:
47 * $1 -- the current depth, 1<=$1<=N
48 * $2 -- the current accumulation of quotient bits
50 * We add a new bit to $2 and either recurse or insert the bits in the quotient.
52 * R -- current remainder
53 * Q -- current quotient
54 * V -- current comparand
55 * cc -- set on current value of R
60 #include "../assembly.h"
62 define(DEVELOP_QUOTIENT_BITS,
63 ` !depth $1, accumulated bits $2
64 bl L.$1.eval(TWOSUPN+$2)
66 ! remainder is nonnegative
71 ',` DEVELOP_QUOTIENT_BITS( incr($1), `eval(2*$2+1)')
73 L.$1.eval(TWOSUPN+$2):
74 ! remainder is negative
79 ',` DEVELOP_QUOTIENT_BITS( incr($1), `eval(2*$2-1)')
83 ifelse( ANSWER, `quotient', `
86 DEFINE_COMPILERRT_FUNCTION(__udivsi3)
88 mov 0,SIGN ! result always nonnegative
91 DEFINE_COMPILERRT_FUNCTION(__divsi3)
92 orcc divisor,dividend,%g0 ! are either dividend or divisor negative
93 bge divide ! if not, skip this junk
94 xor divisor,dividend,SIGN ! record sign of result in sign of SIGN
108 DEFINE_COMPILERRT_FUNCTION(__umodsi3)
110 mov 0,SIGN ! result always nonnegative
113 DEFINE_COMPILERRT_FUNCTION(__modsi3)
114 orcc divisor,dividend,%g0 ! are either dividend or divisor negative
115 bge divide ! if not, skip this junk
116 mov dividend,SIGN ! record sign of result in sign of SIGN
130 ! Compute size of quotient, scale comparand.
131 orcc divisor,%g0,V ! movcc divisor,V
132 te 2 ! if divisor = 0
135 sethi %hi(1<<(WORDSIZE-TOPBITS-1)),T
140 ! Here, the dividend is >= 2ˆ(31-N) or so. We must be careful here,
141 ! as our usual N-at-a-shot divide step will cause overflow and havoc.
142 ! The total number of bits in the result here is N*ITER+SC, where
144 ! Compute ITER in an unorthodox manner: know we need to Shift V into
145 ! the top decade: so don't even bother to compare to R.
157 ! We're here if the divisor overflowed when Shifting.
158 ! This means that R has the high-order bit set.
159 ! Restore V and subtract from R.
160 sll T,TOPBITS,T ! high order bit
161 srl V,1,V ! rest of V
171 ! V > R: went too far: back up 1 step
174 ! do single-bit divide steps
176 ! We have to be careful here. We know that R >= V, so we can do the
177 ! first divide step without thinking. BUT, the others are conditional,
178 ! and are only done if R >= 0. Because both R and V may have the high-
179 ! order bit set in the first step, just falling into the regular
180 ! division loop will mess up the first time around.
181 ! So we unroll slightly...
184 bl end_regular_divide
188 b,a end_single_divloop
206 b,a end_regular_divide
218 ! Do the main division iteration
220 ! Fall through into divide loop
223 DEVELOP_QUOTIENT_BITS( 1, 0 )
229 ! non-restoring fixup if remainder < 0, otherwise annulled
230 ifelse( ANSWER, `quotient',
238 ! negate for answer < 0, otherwise annulled
239 ifelse( ANSWER, `quotient',
240 ` neg %o2,%o2 ! Q <- -Q
241 ',` neg %o3,%o3 ! R <- -R
244 retl ! leaf-routine return
245 ifelse( ANSWER, `quotient',
246 ` mov %o2,%o0 ! quotient <- Q
247 ',` mov %o3,%o0 ! remainder <- R