libgcc/config/tilepro/softdivide.c

   1 /* Division and remainder routines for Tile.
   2    Copyright (C) 2011-2013 Free Software Foundation, Inc.
   3    Contributed by Walter Lee (walt@tilera.com)
   4
   5    This file is free software; you can redistribute it and/or modify it
   6    under the terms of the GNU General Public License as published by the
   7    Free Software Foundation; either version 3, or (at your option) any
   8    later version.
   9
  10    This file is distributed in the hope that it will be useful, but
  11    WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    General Public License for more details.
  14
  15    Under Section 7 of GPL version 3, you are granted additional
  16    permissions described in the GCC Runtime Library Exception, version
  17    3.1, as published by the Free Software Foundation.
  18
  19    You should have received a copy of the GNU General Public License and
  20    a copy of the GCC Runtime Library Exception along with this program;
  21    see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  22    <http://www.gnu.org/licenses/>.  */
  23
  24 typedef int int32_t;
  25 typedef unsigned uint32_t;
  26 typedef long long int64_t;
  27 typedef unsigned long long uint64_t;
  28
  29 /* Raise signal 8 (SIGFPE) with code 1 (FPE_INTDIV).  */
  30 static inline void
  31 raise_intdiv (void)
  32 {
  33   asm ("{ raise; moveli zero, 8 + (1 << 6) }");
  34 }
  35
  36
  37 #ifndef __tilegx__
  38 /*__udivsi3 - 32 bit integer unsigned divide  */
  39 static inline uint32_t __attribute__ ((always_inline))
  40 __udivsi3_inline (uint32_t dividend, uint32_t divisor)
  41 {
  42   /* Divide out any power of two factor from dividend and divisor.
  43      Note that when dividing by zero the divisor will remain zero,
  44      which is all we need to detect that case below.  */
  45   const int power_of_two_factor = __insn_ctz (divisor);
  46   divisor >>= power_of_two_factor;
  47   dividend >>= power_of_two_factor;
  48
  49   /* Checks for division by power of two or division by zero.  */
  50   if (divisor <= 1)
  51     {
  52       if (divisor == 0)
  53         {
  54           raise_intdiv ();
  55           return 0;
  56         }
  57       return dividend;
  58     }
  59
  60   /* Compute (a / b) by repeatedly finding the largest N
  61      such that (b << N) <= a. For each such N, set bit N in the
  62      quotient, subtract (b << N) from a, and keep going. Think of this as
  63      the reverse of the "shift-and-add" that a multiply does. The values
  64      of N are precisely those shift counts.
  65
  66      Finding N is easy. First, use clz(b) - clz(a) to find the N
  67      that lines up the high bit of (b << N) with the high bit of a.
  68      Any larger value of N would definitely make (b << N) > a,
  69      which is too big.
  70
  71      Then, if (b << N) > a (because it has larger low bits), decrement
  72      N by one.  This adjustment will definitely make (b << N) less
  73      than a, because a's high bit is now one higher than b's.  */
  74
  75   /* Precomputing the max_ values allows us to avoid a subtract
  76      in the inner loop and just right shift by clz(remainder).  */
  77   const int divisor_clz = __insn_clz (divisor);
  78   const uint32_t max_divisor = divisor << divisor_clz;
  79   const uint32_t max_qbit = 1 << divisor_clz;
  80
  81   uint32_t quotient = 0;
  82   uint32_t remainder = dividend;
  83
  84   while (remainder >= divisor)
  85     {
  86       int shift = __insn_clz (remainder);
  87       uint32_t scaled_divisor = max_divisor >> shift;
  88       uint32_t quotient_bit = max_qbit >> shift;
  89
  90       int too_big = (scaled_divisor > remainder);
  91       scaled_divisor >>= too_big;
  92       quotient_bit >>= too_big;
  93       remainder -= scaled_divisor;
  94       quotient |= quotient_bit;
  95     }
  96   return quotient;
  97 }
  98 #endif /* !__tilegx__ */
  99
 100
 101 /* __udivdi3 - 64 bit integer unsigned divide  */
 102 static inline uint64_t __attribute__ ((always_inline))
 103 __udivdi3_inline (uint64_t dividend, uint64_t divisor)
 104 {
 105   /* Divide out any power of two factor from dividend and divisor.
 106      Note that when dividing by zero the divisor will remain zero,
 107      which is all we need to detect that case below.  */
 108   const int power_of_two_factor = __builtin_ctzll (divisor);
 109   divisor >>= power_of_two_factor;
 110   dividend >>= power_of_two_factor;
 111
 112   /* Checks for division by power of two or division by zero.  */
 113   if (divisor <= 1)
 114     {
 115       if (divisor == 0)
 116         {
 117           raise_intdiv ();
 118           return 0;
 119         }
 120       return dividend;
 121     }
 122
 123 #ifndef __tilegx__
 124   if (((uint32_t) (dividend >> 32) | ((uint32_t) (divisor >> 32))) == 0)
 125     {
 126       /* Operands both fit in 32 bits, so use faster 32 bit algorithm.  */
 127       return __udivsi3_inline ((uint32_t) dividend, (uint32_t) divisor);
 128     }
 129 #endif /* !__tilegx__ */
 130
 131   /* See algorithm description in __udivsi3  */
 132
 133   const int divisor_clz = __builtin_clzll (divisor);
 134   const uint64_t max_divisor = divisor << divisor_clz;
 135   const uint64_t max_qbit = 1ULL << divisor_clz;
 136
 137   uint64_t quotient = 0;
 138   uint64_t remainder = dividend;
 139
 140   while (remainder >= divisor)
 141     {
 142       int shift = __builtin_clzll (remainder);
 143       uint64_t scaled_divisor = max_divisor >> shift;
 144       uint64_t quotient_bit = max_qbit >> shift;
 145
 146       int too_big = (scaled_divisor > remainder);
 147       scaled_divisor >>= too_big;
 148       quotient_bit >>= too_big;
 149       remainder -= scaled_divisor;
 150       quotient |= quotient_bit;
 151     }
 152   return quotient;
 153 }
 154
 155
 156 #ifndef __tilegx__
 157 /* __umodsi3 - 32 bit integer unsigned modulo  */
 158 static inline uint32_t __attribute__ ((always_inline))
 159 __umodsi3_inline (uint32_t dividend, uint32_t divisor)
 160 {
 161   /* Shortcircuit mod by a power of two (and catch mod by zero).  */
 162   const uint32_t mask = divisor - 1;
 163   if ((divisor & mask) == 0)
 164     {
 165       if (divisor == 0)
 166         {
 167           raise_intdiv ();
 168           return 0;
 169         }
 170       return dividend & mask;
 171     }
 172
 173   /* We compute the remainder (a % b) by repeatedly subtracting off
 174      multiples of b from a until a < b. The key is that subtracting
 175      off a multiple of b does not affect the result mod b.
 176
 177      To make the algorithm run efficiently, we need to subtract
 178      off a large multiple of b at each step. We subtract the largest
 179      (b << N) that is <= a.
 180
 181      Finding N is easy. First, use clz(b) - clz(a) to find the N
 182      that lines up the high bit of (b << N) with the high bit of a.
 183      Any larger value of N would definitely make (b << N) > a,
 184      which is too big.
 185
 186      Then, if (b << N) > a (because it has larger low bits), decrement
 187      N by one.  This adjustment will definitely make (b << N) less
 188      than a, because a's high bit is now one higher than b's.  */
 189   const uint32_t max_divisor = divisor << __insn_clz (divisor);
 190
 191   uint32_t remainder = dividend;
 192   while (remainder >= divisor)
 193     {
 194       const int shift = __insn_clz (remainder);
 195       uint32_t scaled_divisor = max_divisor >> shift;
 196       scaled_divisor >>= (scaled_divisor > remainder);
 197       remainder -= scaled_divisor;
 198     }
 199
 200   return remainder;
 201 }
 202 #endif /* !__tilegx__ */
 203
 204
 205 /* __umoddi3 - 64 bit integer unsigned modulo  */
 206 static inline uint64_t __attribute__ ((always_inline))
 207 __umoddi3_inline (uint64_t dividend, uint64_t divisor)
 208 {
 209 #ifndef __tilegx__
 210   if (((uint32_t) (dividend >> 32) | ((uint32_t) (divisor >> 32))) == 0)
 211     {
 212       /* Operands both fit in 32 bits, so use faster 32 bit algorithm.  */
 213       return __umodsi3_inline ((uint32_t) dividend, (uint32_t) divisor);
 214     }
 215 #endif /* !__tilegx__ */
 216
 217   /* Shortcircuit mod by a power of two (and catch mod by zero).  */
 218   const uint64_t mask = divisor - 1;
 219   if ((divisor & mask) == 0)
 220     {
 221       if (divisor == 0)
 222         {
 223           raise_intdiv ();
 224           return 0;
 225         }
 226       return dividend & mask;
 227     }
 228
 229   /* See algorithm description in __umodsi3  */
 230   const uint64_t max_divisor = divisor << __builtin_clzll (divisor);
 231
 232   uint64_t remainder = dividend;
 233   while (remainder >= divisor)
 234     {
 235       const int shift = __builtin_clzll (remainder);
 236       uint64_t scaled_divisor = max_divisor >> shift;
 237       scaled_divisor >>= (scaled_divisor > remainder);
 238       remainder -= scaled_divisor;
 239     }
 240
 241   return remainder;
 242 }
 243
 244
 245 uint32_t __udivsi3 (uint32_t dividend, uint32_t divisor);
 246 #ifdef L_tile_udivsi3
 247 uint32_t
 248 __udivsi3 (uint32_t dividend, uint32_t divisor)
 249 {
 250 #ifndef __tilegx__
 251   return __udivsi3_inline (dividend, divisor);
 252 #else /* !__tilegx__ */
 253   uint64_t n = __udivdi3_inline (((uint64_t) dividend), ((uint64_t) divisor));
 254   return (uint32_t) n;
 255 #endif /* !__tilegx__ */
 256 }
 257 #endif
 258
 259 #define ABS(x) ((x) >= 0 ? (x) : -(x))
 260
 261 int32_t __divsi3 (int32_t dividend, int32_t divisor);
 262 #ifdef L_tile_divsi3
 263 /* __divsi3 - 32 bit integer signed divide  */
 264 int32_t
 265 __divsi3 (int32_t dividend, int32_t divisor)
 266 {
 267 #ifndef __tilegx__
 268   uint32_t n = __udivsi3_inline (ABS (dividend), ABS (divisor));
 269 #else /* !__tilegx__ */
 270   uint64_t n =
 271     __udivdi3_inline (ABS ((int64_t) dividend), ABS ((int64_t) divisor));
 272 #endif /* !__tilegx__ */
 273   if ((dividend ^ divisor) < 0)
 274     n = -n;
 275   return (int32_t) n;
 276 }
 277 #endif
 278
 279
 280 uint64_t __udivdi3 (uint64_t dividend, uint64_t divisor);
 281 #ifdef L_tile_udivdi3
 282 uint64_t
 283 __udivdi3 (uint64_t dividend, uint64_t divisor)
 284 {
 285   return __udivdi3_inline (dividend, divisor);
 286 }
 287 #endif
 288
 289 /*__divdi3 - 64 bit integer signed divide  */
 290 int64_t __divdi3 (int64_t dividend, int64_t divisor);
 291 #ifdef L_tile_divdi3
 292 int64_t
 293 __divdi3 (int64_t dividend, int64_t divisor)
 294 {
 295   uint64_t n = __udivdi3_inline (ABS (dividend), ABS (divisor));
 296   if ((dividend ^ divisor) < 0)
 297     n = -n;
 298   return (int64_t) n;
 299 }
 300 #endif
 301
 302
 303 uint32_t __umodsi3 (uint32_t dividend, uint32_t divisor);
 304 #ifdef L_tile_umodsi3
 305 uint32_t
 306 __umodsi3 (uint32_t dividend, uint32_t divisor)
 307 {
 308 #ifndef __tilegx__
 309   return __umodsi3_inline (dividend, divisor);
 310 #else /* !__tilegx__ */
 311   return __umoddi3_inline ((uint64_t) dividend, (uint64_t) divisor);
 312 #endif /* !__tilegx__ */
 313 }
 314 #endif
 315
 316
 317 /* __modsi3 - 32 bit integer signed modulo  */
 318 int32_t __modsi3 (int32_t dividend, int32_t divisor);
 319 #ifdef L_tile_modsi3
 320 int32_t
 321 __modsi3 (int32_t dividend, int32_t divisor)
 322 {
 323 #ifndef __tilegx__
 324   uint32_t remainder = __umodsi3_inline (ABS (dividend), ABS (divisor));
 325 #else /* !__tilegx__ */
 326   uint64_t remainder =
 327     __umoddi3_inline (ABS ((int64_t) dividend), ABS ((int64_t) divisor));
 328 #endif /* !__tilegx__ */
 329   return (int32_t) ((dividend >= 0) ? remainder : -remainder);
 330 }
 331 #endif
 332
 333
 334 uint64_t __umoddi3 (uint64_t dividend, uint64_t divisor);
 335 #ifdef L_tile_umoddi3
 336 uint64_t
 337 __umoddi3 (uint64_t dividend, uint64_t divisor)
 338 {
 339   return __umoddi3_inline (dividend, divisor);
 340 }
 341 #endif
 342
 343
 344 /* __moddi3 - 64 bit integer signed modulo  */
 345 int64_t __moddi3 (int64_t dividend, int64_t divisor);
 346 #ifdef L_tile_moddi3
 347 int64_t
 348 __moddi3 (int64_t dividend, int64_t divisor)
 349 {
 350   uint64_t remainder = __umoddi3_inline (ABS (dividend), ABS (divisor));
 351   return (int64_t) ((dividend >= 0) ? remainder : -remainder);
 352 }
 353 #endif