contrib/compiler-rt/lib/arm/udivsi3.S

   1 /*===-- udivsi3.S - 32-bit unsigned integer divide ------------------------===//
   2  *
   3  *                     The LLVM Compiler Infrastructure
   4  *
   5  * This file is dual licensed under the MIT and the University of Illinois Open
   6  * Source Licenses. See LICENSE.TXT for details.
   7  *
   8  *===----------------------------------------------------------------------===//
   9  *
  10  * This file implements the __udivsi3 (32-bit unsigned integer divide)
  11  * function for the ARM architecture.  A naive digit-by-digit computation is
  12  * employed for simplicity.
  13  *
  14  *===----------------------------------------------------------------------===*/
  15
  16 #include "../assembly.h"
  17
  18 #define ESTABLISH_FRAME \
  19     push   {r7, lr}    ;\
  20     mov     r7,     sp
  21 #define CLEAR_FRAME_AND_RETURN \
  22     pop    {r7, pc}
  23
  24 #define a r0
  25 #define b r1
  26 #define r r2
  27 #define i r3
  28 #define q ip
  29 #define one lr
  30
  31 .syntax unified
  32 .align 3
  33 // Ok, APCS and AAPCS agree on 32 bit args, so it's safe to use the same routine.
  34 DEFINE_AEABI_FUNCTION_ALIAS(__aeabi_uidiv, __udivsi3)
  35 DEFINE_COMPILERRT_FUNCTION(__udivsi3)
  36 //  We use a simple digit by digit algorithm; before we get into the actual
  37 //  divide loop, we must calculate the left-shift amount necessary to align
  38 //  the MSB of the divisor with that of the dividend (If this shift is
  39 //  negative, then the result is zero, and we early out). We also conjure a
  40 //  bit mask of 1 to use in constructing the quotient, and initialize the
  41 //  quotient to zero.
  42     ESTABLISH_FRAME
  43     clz     r2,     a
  44     tst     b,      b   // detect divide-by-zero
  45     clz     r3,     b
  46     mov     q,      #0
  47     beq     LOCAL_LABEL(return)    // return 0 if b is zero.
  48     mov     one,    #1
  49     subs    i,      r3, r2
  50     blt     LOCAL_LABEL(return)    // return 0 if MSB(a) < MSB(b)
  51
  52 LOCAL_LABEL(mainLoop):
  53 //  This loop basically implements the following:
  54 //
  55 //  do {
  56 //      if (a >= b << i) {
  57 //          a -= b << i;
  58 //          q |= 1 << i;
  59 //          if (a == 0) break;
  60 //      }
  61 //  } while (--i)
  62 //
  63 //  Note that this does not perform the final iteration (i == 0); by doing it
  64 //  this way, we can merge the two branches which is a substantial win for
  65 //  such a tight loop on current ARM architectures.
  66     subs    r,      a,  b, lsl i
  67     orrhs   q,      q,one, lsl i
  68     movhs   a,      r
  69     subsne  i,      i, #1
  70     bhi     LOCAL_LABEL(mainLoop)
  71
  72 //  Do the final test subtraction and update of quotient (i == 0), as it is
  73 //  not performed in the main loop.
  74     subs    r,      a,  b
  75     orrhs   q,      #1
  76
  77 LOCAL_LABEL(return):
  78 //  Move the quotient to r0 and return.
  79     mov     r0,     q
  80     CLEAR_FRAME_AND_RETURN