contrib/compiler-rt/lib/sparc64/divmod.m4

   1 /*
   2  * This m4 code has been taken from The SPARC Architecture Manual Version 8.
   3  */
   4
   5 /*
   6  * Division/Remainder
   7  *
   8  * Input is:
   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)
  16  * A derived constant:
  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)
  26  * Cost:
  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
  31  *   one bit at a time.
  32  *   This uses the m4 and cpp macro preprocessors.
  33  */
  34
  35 define(dividend, `%o0')
  36 define(divisor,`%o1')
  37 define(Q, `%o2')
  38 define(R, `%o3')
  39 define(ITER, `%o4')
  40 define(V, `%o5')
  41 define(SIGN, `%g3')
  42 define(T, `%g1')
  43 define(SC,`%g2')
  44 /*
  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
  49  *   N -- max depth
  50  * We add a new bit to $2 and either recurse or insert the bits in the quotient.
  51  * Dynamic input:
  52  *   R -- current remainder
  53  *   Q -- current quotient
  54  *   V -- current comparand
  55  *   cc -- set on current value of R
  56  * Dynamic output:
  57  *   R', Q', V', cc'
  58  */
  59
  60 #include "../assembly.h"
  61
  62 define(DEVELOP_QUOTIENT_BITS,
  63 `       !depth $1, accumulated bits $2
  64         bl      L.$1.eval(TWOSUPN+$2)
  65         srl     V,1,V
  66         ! remainder is nonnegative
  67         subcc   R,V,R
  68         ifelse( $1, N,
  69         `       b       9f
  70                 add     Q, ($2*2+1), Q
  71         ',` DEVELOP_QUOTIENT_BITS( incr($1), `eval(2*$2+1)')
  72         ')
  73 L.$1.eval(TWOSUPN+$2):
  74         ! remainder is negative
  75         addcc   R,V,R
  76         ifelse( $1, N,
  77         `       b       9f
  78                 add     Q, ($2*2-1), Q
  79         ',` DEVELOP_QUOTIENT_BITS( incr($1), `eval(2*$2-1)')
  80         ')
  81         ifelse( $1, 1, `9:')
  82 ')
  83 ifelse( ANSWER, `quotient', `
  84 .text
  85         .align 32
  86 DEFINE_COMPILERRT_FUNCTION(__udivsi3)
  87         b       divide
  88         mov     0,SIGN                  ! result always nonnegative
  89 .text
  90         .align 32
  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
  95         tst     divisor
  96         bge     2f
  97         tst     dividend
  98         ! divisor < 0
  99         bge     divide
 100         neg     divisor
 101         2:
 102         ! dividend < 0
 103         neg     dividend
 104         ! FALL THROUGH
 105 ',`
 106 .text
 107         .align 32
 108 DEFINE_COMPILERRT_FUNCTION(__umodsi3)
 109         b       divide
 110         mov     0,SIGN                  ! result always nonnegative
 111 .text
 112         .align 32
 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
 117         tst     divisor
 118         bge     2f
 119         tst     dividend
 120         ! divisor < 0
 121         bge     divide
 122         neg     divisor
 123         2:
 124         ! dividend < 0
 125         neg     dividend
 126         ! FALL THROUGH
 127 ')
 128
 129 divide:
 130         ! Compute size of quotient, scale comparand.
 131         orcc    divisor,%g0,V           ! movcc divisor,V
 132         te      2                       ! if divisor = 0
 133         mov     dividend,R
 134         mov     0,Q
 135         sethi   %hi(1<<(WORDSIZE-TOPBITS-1)),T
 136         cmp     R,T
 137         blu     not_really_big
 138         mov     0,ITER
 139         !
 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
 143         ! SC <= N.
 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.
 146 1:
 147         cmp     V,T
 148         bgeu    3f
 149         mov     1,SC
 150         sll     V,N,V
 151         b       1b
 152         inc     ITER
 153 ! Now compute SC
 154 2:      addcc   V,V,V
 155         bcc     not_too_big
 156         add     SC,1,SC
 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
 162                 add     V,T,V
 163                 b       do_single_div
 164                 dec     SC
 165 not_too_big:
 166 3:      cmp     V,R
 167         blu     2b
 168         nop
 169         be      do_single_div
 170         nop
 171 ! V > R: went too far: back up 1 step
 172 !     srl V,1,V
 173 !      dec SC
 174 ! do single-bit divide steps
 175 !
 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...
 182 do_single_div:
 183         deccc   SC
 184         bl      end_regular_divide
 185         nop
 186         sub     R,V,R
 187         mov     1,Q
 188         b,a     end_single_divloop
 189         ! EMPTY
 190 single_divloop:
 191         sll     Q,1,Q
 192         bl      1f
 193         srl     V,1,V
 194         ! R >= 0
 195                 sub     R,V,R
 196                 b       2f
 197                 inc     Q
 198         1:      ! R < 0
 199                 add     R,V,R
 200                 dec     Q
 201         2:
 202         end_single_divloop:
 203                 deccc   SC
 204                 bge     single_divloop
 205                 tst     R
 206                 b,a     end_regular_divide
 207                 ! EMPTY
 208
 209 not_really_big:
 210 1:
 211         sll     V,N,V
 212         cmp     V,R
 213         bleu    1b
 214         inccc   ITER
 215         be      got_result
 216         dec     ITER
 217 do_regular_divide:
 218         ! Do the main division iteration
 219         tst     R
 220         ! Fall through into divide loop
 221 divloop:
 222         sll     Q,N,Q
 223         DEVELOP_QUOTIENT_BITS( 1, 0 )
 224 end_regular_divide:
 225         deccc   ITER
 226         bge     divloop
 227         tst     R
 228         bl,a    got_result
 229         ! non-restoring fixup if remainder < 0, otherwise annulled
 230 ifelse( ANSWER, `quotient',
 231 `       dec     Q
 232 ',`     add     R,divisor,R
 233 ')
 234
 235 got_result:
 236         tst     SIGN
 237         bl,a    1f
 238         ! negate for answer < 0, otherwise annulled
 239 ifelse( ANSWER, `quotient',
 240 `       neg     %o2,%o2                 ! Q <- -Q
 241 ',`     neg     %o3,%o3                 ! R <- -R
 242 ')
 243 1:
 244         retl                            ! leaf-routine return
 245 ifelse( ANSWER, `quotient',
 246 `       mov     %o2,%o0                 ! quotient <- Q
 247 ',`     mov     %o3,%o0                 ! remainder <- R
 248 ')