contrib/compiler-rt/lib/builtins/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 32-bit architecture.
  12  *
  13  *===----------------------------------------------------------------------===*/
  14
  15 #include "../assembly.h"
  16
  17         .syntax unified
  18         .text
  19
  20 #if __ARM_ARCH_ISA_THUMB == 2
  21         .thumb
  22 #endif
  23
  24         .p2align 2
  25 DEFINE_AEABI_FUNCTION_ALIAS(__aeabi_uidiv, __udivsi3)
  26
  27 @ unsigned int __udivsi3(unsigned int divident, unsigned int divisor)
  28 @   Calculate and return the quotient of the (unsigned) division.
  29
  30 #if __ARM_ARCH_ISA_THUMB == 2
  31 DEFINE_COMPILERRT_THUMB_FUNCTION(__udivsi3)
  32 #else
  33 DEFINE_COMPILERRT_FUNCTION(__udivsi3)
  34 #endif
  35 #if __ARM_ARCH_EXT_IDIV__
  36         tst     r1, r1
  37         beq     LOCAL_LABEL(divby0)
  38         udiv    r0, r0, r1
  39         bx      lr
  40 #else
  41         cmp     r1, #1
  42         bcc     LOCAL_LABEL(divby0)
  43 #if __ARM_ARCH_ISA_THUMB == 1
  44         bne LOCAL_LABEL(num_neq_denom)
  45         JMP(lr)
  46 LOCAL_LABEL(num_neq_denom):
  47 #else
  48         IT(eq)
  49         JMPc(lr, eq)
  50 #endif
  51         cmp     r0, r1
  52 #if __ARM_ARCH_ISA_THUMB == 1
  53         bhs LOCAL_LABEL(num_ge_denom)
  54         movs r0, #0
  55         JMP(lr)
  56 LOCAL_LABEL(num_ge_denom):
  57 #else
  58         ITT(cc)
  59         movcc   r0, #0
  60         JMPc(lr, cc)
  61 #endif
  62
  63         /*
  64          * Implement division using binary long division algorithm.
  65          *
  66          * r0 is the numerator, r1 the denominator.
  67          *
  68          * The code before JMP computes the correct shift I, so that
  69          * r0 and (r1 << I) have the highest bit set in the same position.
  70          * At the time of JMP, ip := .Ldiv0block - 12 * I.
  71          * This depends on the fixed instruction size of block.
  72          * For ARM mode, this is 12 Bytes, for THUMB mode 14 Bytes.
  73          *
  74          * block(shift) implements the test-and-update-quotient core.
  75          * It assumes (r0 << shift) can be computed without overflow and
  76          * that (r0 << shift) < 2 * r1. The quotient is stored in r3.
  77          */
  78
  79 #  if defined(__ARM_FEATURE_CLZ)
  80         clz     ip, r0
  81         clz     r3, r1
  82         /* r0 >= r1 implies clz(r0) <= clz(r1), so ip <= r3. */
  83         sub     r3, r3, ip
  84 #    if __ARM_ARCH_ISA_THUMB == 2
  85         adr     ip, LOCAL_LABEL(div0block) + 1
  86         sub     ip, ip, r3, lsl #1
  87 #    else
  88         adr     ip, LOCAL_LABEL(div0block)
  89 #    endif
  90         sub     ip, ip, r3, lsl #2
  91         sub     ip, ip, r3, lsl #3
  92         mov     r3, #0
  93         bx      ip
  94 #  else /* No CLZ Feature */
  95 #    if __ARM_ARCH_ISA_THUMB == 2
  96 #    error THUMB mode requires CLZ or UDIV
  97 #    endif
  98 #    if __ARM_ARCH_ISA_THUMB == 1
  99 #      define BLOCK_SIZE 10
 100 #    else
 101 #      define BLOCK_SIZE 12
 102 #    endif
 103
 104         mov     r2, r0
 105 #    if __ARM_ARCH_ISA_THUMB == 1
 106         mov ip, r0
 107         adr r0, LOCAL_LABEL(div0block)
 108         adds r0, #1
 109 #    else
 110         adr     ip, LOCAL_LABEL(div0block)
 111 #    endif
 112         lsrs    r3, r2, #16
 113         cmp     r3, r1
 114 #    if __ARM_ARCH_ISA_THUMB == 1
 115         blo LOCAL_LABEL(skip_16)
 116         movs r2, r3
 117         subs r0, r0, #(16 * BLOCK_SIZE)
 118 LOCAL_LABEL(skip_16):
 119 #    else
 120         movhs   r2, r3
 121         subhs   ip, ip, #(16 * BLOCK_SIZE)
 122 #    endif
 123
 124         lsrs    r3, r2, #8
 125         cmp     r3, r1
 126 #    if __ARM_ARCH_ISA_THUMB == 1
 127         blo LOCAL_LABEL(skip_8)
 128         movs r2, r3
 129         subs r0, r0, #(8 * BLOCK_SIZE)
 130 LOCAL_LABEL(skip_8):
 131 #    else
 132         movhs   r2, r3
 133         subhs   ip, ip, #(8 * BLOCK_SIZE)
 134 #    endif
 135
 136         lsrs    r3, r2, #4
 137         cmp     r3, r1
 138 #    if __ARM_ARCH_ISA_THUMB == 1
 139         blo LOCAL_LABEL(skip_4)
 140         movs r2, r3
 141         subs r0, r0, #(4 * BLOCK_SIZE)
 142 LOCAL_LABEL(skip_4):
 143 #    else
 144         movhs   r2, r3
 145         subhs   ip, #(4 * BLOCK_SIZE)
 146 #    endif
 147
 148         lsrs    r3, r2, #2
 149         cmp     r3, r1
 150 #    if __ARM_ARCH_ISA_THUMB == 1
 151         blo LOCAL_LABEL(skip_2)
 152         movs r2, r3
 153         subs r0, r0, #(2 * BLOCK_SIZE)
 154 LOCAL_LABEL(skip_2):
 155 #    else
 156         movhs   r2, r3
 157         subhs   ip, ip, #(2 * BLOCK_SIZE)
 158 #    endif
 159
 160         /* Last block, no need to update r2 or r3. */
 161 #    if __ARM_ARCH_ISA_THUMB == 1
 162         lsrs r3, r2, #1
 163         cmp r3, r1
 164         blo LOCAL_LABEL(skip_1)
 165         subs r0, r0, #(1 * BLOCK_SIZE)
 166 LOCAL_LABEL(skip_1):
 167         movs r2, r0
 168         mov r0, ip
 169         movs r3, #0
 170         JMP (r2)
 171
 172 #    else
 173         cmp     r1, r2, lsr #1
 174         subls   ip, ip, #(1 * BLOCK_SIZE)
 175
 176         movs    r3, #0
 177
 178         JMP(ip)
 179 #    endif
 180 #  endif /* __ARM_FEATURE_CLZ */
 181
 182
 183 #define IMM     #
 184         /* due to the range limit of branch in Thumb1, we have to place the
 185                  block closer */
 186 LOCAL_LABEL(divby0):
 187         movs    r0, #0
 188 #      if defined(__ARM_EABI__)
 189         bl      __aeabi_idiv0 // due to relocation limit, can't use b.
 190 #      endif
 191         JMP(lr)
 192
 193
 194 #if __ARM_ARCH_ISA_THUMB == 1
 195 #define block(shift)                                                           \
 196         lsls r2, r1, IMM shift;                                                      \
 197         cmp r0, r2;                                                                  \
 198         blo LOCAL_LABEL(block_skip_##shift);                                         \
 199         subs r0, r0, r2;                                                             \
 200         LOCAL_LABEL(block_skip_##shift) :;                                           \
 201         adcs r3, r3 /* same as ((r3 << 1) | Carry). Carry is set if r0 >= r2. */
 202
 203         /* TODO: if current location counter is not not word aligned, we don't
 204                  need the .p2align and nop */
 205         /* Label div0block must be word-aligned. First align block 31 */
 206         .p2align 2
 207         nop /* Padding to align div0block as 31 blocks = 310 bytes */
 208
 209 #else
 210 #define block(shift)                                                           \
 211         cmp     r0, r1, lsl IMM shift;                                         \
 212         ITT(hs);                                                               \
 213         WIDE(addhs)     r3, r3, IMM (1 << shift);                              \
 214         WIDE(subhs)     r0, r0, r1, lsl IMM shift
 215 #endif
 216
 217         block(31)
 218         block(30)
 219         block(29)
 220         block(28)
 221         block(27)
 222         block(26)
 223         block(25)
 224         block(24)
 225         block(23)
 226         block(22)
 227         block(21)
 228         block(20)
 229         block(19)
 230         block(18)
 231         block(17)
 232         block(16)
 233         block(15)
 234         block(14)
 235         block(13)
 236         block(12)
 237         block(11)
 238         block(10)
 239         block(9)
 240         block(8)
 241         block(7)
 242         block(6)
 243         block(5)
 244         block(4)
 245         block(3)
 246         block(2)
 247         block(1)
 248 LOCAL_LABEL(div0block):
 249         block(0)
 250
 251         mov     r0, r3
 252         JMP(lr)
 253 #endif /* __ARM_ARCH_EXT_IDIV__ */
 254
 255 #if __ARM_ARCH_EXT_IDIV__
 256 LOCAL_LABEL(divby0):
 257         mov     r0, #0
 258 #  ifdef __ARM_EABI__
 259         b       __aeabi_idiv0
 260 #  else
 261         JMP(lr)
 262 #  endif
 263 #endif
 264
 265 END_COMPILERRT_FUNCTION(__udivsi3)
 266
 267 NO_EXEC_STACK_DIRECTIVE
 268