contrib/llvm-project/compiler-rt/lib/builtins/i386/moddi3.S

   1 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   2 // See https://llvm.org/LICENSE.txt for license information.
   3 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   4
   5 #include "../assembly.h"
   6
   7 // di_int __moddi3(di_int a, di_int b);
   8
   9 // result = remainder of a / b.
  10 // both inputs and the output are 64-bit signed integers.
  11 // This will do whatever the underlying hardware is set to do on division by zero.
  12 // No other exceptions are generated, as the divide cannot overflow.
  13 //
  14 // This is targeted at 32-bit x86 *only*, as this can be done directly in hardware
  15 // on x86_64.  The performance goal is ~40 cycles per divide, which is faster than
  16 // currently possible via simulation of integer divides on the x87 unit.
  17 //
  18
  19 // Stephen Canon, December 2008
  20
  21 #ifdef __i386__
  22
  23 .text
  24 .balign 4
  25 DEFINE_COMPILERRT_FUNCTION(__moddi3)
  26
  27 // This is currently implemented by wrapping the unsigned modulus up in an absolute
  28 // value.  This could certainly be improved upon.
  29
  30         pushl           %esi
  31         movl     20(%esp),                      %edx    // high word of b
  32         movl     16(%esp),                      %eax    // low word of b
  33         movl            %edx,                   %ecx
  34         sarl            $31,                    %ecx    // (b < 0) ? -1 : 0
  35         xorl            %ecx,                   %eax
  36         xorl            %ecx,                   %edx    // EDX:EAX = (b < 0) ? not(b) : b
  37         subl            %ecx,                   %eax
  38         sbbl            %ecx,                   %edx    // EDX:EAX = abs(b)
  39         movl            %edx,            20(%esp)
  40         movl            %eax,            16(%esp)       // store abs(b) back to stack
  41
  42         movl     12(%esp),                      %edx    // high word of b
  43         movl      8(%esp),                      %eax    // low word of b
  44         movl            %edx,                   %ecx
  45         sarl            $31,                    %ecx    // (a < 0) ? -1 : 0
  46         xorl            %ecx,                   %eax
  47         xorl            %ecx,                   %edx    // EDX:EAX = (a < 0) ? not(a) : a
  48         subl            %ecx,                   %eax
  49         sbbl            %ecx,                   %edx    // EDX:EAX = abs(a)
  50         movl            %edx,            12(%esp)
  51         movl            %eax,             8(%esp)       // store abs(a) back to stack
  52         movl            %ecx,                   %esi    // set aside sign of a
  53
  54         pushl           %ebx
  55         movl     24(%esp),                      %ebx    // Find the index i of the leading bit in b.
  56         bsrl            %ebx,                   %ecx    // If the high word of b is zero, jump to
  57         jz                      9f                                              // the code to handle that special case [9].
  58
  59         // High word of b is known to be non-zero on this branch
  60
  61         movl     20(%esp),                      %eax    // Construct bhi, containing bits [1+i:32+i] of b
  62
  63         shrl            %cl,                    %eax    // Practically, this means that bhi is given by:
  64         shrl            %eax                                    //
  65         notl            %ecx                                    //              bhi = (high word of b) << (31 - i) |
  66         shll            %cl,                    %ebx    //                        (low word of b) >> (1 + i)
  67         orl                     %eax,                   %ebx    //
  68         movl     16(%esp),                      %edx    // Load the high and low words of a, and jump
  69         movl     12(%esp),                      %eax    // to [2] if the high word is larger than bhi
  70         cmpl            %ebx,                   %edx    // to avoid overflowing the upcoming divide.
  71         jae                     2f
  72
  73         // High word of a is greater than or equal to (b >> (1 + i)) on this branch
  74
  75         divl            %ebx                                    // eax <-- qs, edx <-- r such that ahi:alo = bs*qs + r
  76
  77         pushl           %edi
  78         notl            %ecx
  79         shrl            %eax
  80         shrl            %cl,                    %eax    // q = qs >> (1 + i)
  81         movl            %eax,                   %edi
  82         mull     24(%esp)                                       // q*blo
  83         movl     16(%esp),                      %ebx
  84         movl     20(%esp),                      %ecx    // ECX:EBX = a
  85         subl            %eax,                   %ebx
  86         sbbl            %edx,                   %ecx    // ECX:EBX = a - q*blo
  87         movl     28(%esp),                      %eax
  88         imull           %edi,                   %eax    // q*bhi
  89         subl            %eax,                   %ecx    // ECX:EBX = a - q*b
  90
  91         jnc                     1f                                              // if positive, this is the result.
  92         addl     24(%esp),                      %ebx    // otherwise
  93         adcl     28(%esp),                      %ecx    // ECX:EBX = a - (q-1)*b = result
  94 1:      movl            %ebx,                   %eax
  95         movl            %ecx,                   %edx
  96
  97         addl            %esi,                   %eax    // Restore correct sign to result
  98         adcl            %esi,                   %edx
  99         xorl            %esi,                   %eax
 100         xorl            %esi,                   %edx
 101         popl            %edi                                    // Restore callee-save registers
 102         popl            %ebx
 103         popl            %esi
 104         retl                                                            // Return
 105
 106 2:      // High word of a is greater than or equal to (b >> (1 + i)) on this branch
 107
 108         subl            %ebx,                   %edx    // subtract bhi from ahi so that divide will not
 109         divl            %ebx                                    // overflow, and find q and r such that
 110                                                                                 //
 111                                                                                 //              ahi:alo = (1:q)*bhi + r
 112                                                                                 //
 113                                                                                 // Note that q is a number in (31-i).(1+i)
 114                                                                                 // fix point.
 115
 116         pushl           %edi
 117         notl            %ecx
 118         shrl            %eax
 119         orl                     $0x80000000,    %eax
 120         shrl            %cl,                    %eax    // q = (1:qs) >> (1 + i)
 121         movl            %eax,                   %edi
 122         mull     24(%esp)                                       // q*blo
 123         movl     16(%esp),                      %ebx
 124         movl     20(%esp),                      %ecx    // ECX:EBX = a
 125         subl            %eax,                   %ebx
 126         sbbl            %edx,                   %ecx    // ECX:EBX = a - q*blo
 127         movl     28(%esp),                      %eax
 128         imull           %edi,                   %eax    // q*bhi
 129         subl            %eax,                   %ecx    // ECX:EBX = a - q*b
 130
 131         jnc                     3f                                              // if positive, this is the result.
 132         addl     24(%esp),                      %ebx    // otherwise
 133         adcl     28(%esp),                      %ecx    // ECX:EBX = a - (q-1)*b = result
 134 3:      movl            %ebx,                   %eax
 135         movl            %ecx,                   %edx
 136
 137         addl            %esi,                   %eax    // Restore correct sign to result
 138         adcl            %esi,                   %edx
 139         xorl            %esi,                   %eax
 140         xorl            %esi,                   %edx
 141         popl            %edi                                    // Restore callee-save registers
 142         popl            %ebx
 143         popl            %esi
 144         retl                                                            // Return
 145
 146 9:      // High word of b is zero on this branch
 147
 148         movl     16(%esp),                      %eax    // Find qhi and rhi such that
 149         movl     20(%esp),                      %ecx    //
 150         xorl            %edx,                   %edx    //              ahi = qhi*b + rhi       with    0 ≤ rhi < b
 151         divl            %ecx                                    //
 152         movl            %eax,                   %ebx    //
 153         movl     12(%esp),                      %eax    // Find rlo such that
 154         divl            %ecx                                    //
 155         movl            %edx,                   %eax    //              rhi:alo = qlo*b + rlo  with 0 ≤ rlo < b
 156         popl            %ebx                                    //
 157         xorl            %edx,                   %edx    // and return 0:rlo
 158
 159         addl            %esi,                   %eax    // Restore correct sign to result
 160         adcl            %esi,                   %edx
 161         xorl            %esi,                   %eax
 162         xorl            %esi,                   %edx
 163         popl            %esi
 164         retl                                                            // Return
 165 END_COMPILERRT_FUNCTION(__moddi3)
 166
 167 #endif // __i386__
 168
 169 NO_EXEC_STACK_DIRECTIVE
 170