contrib/compiler-rt/lib/builtins/i386/udivdi3.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 // du_int __udivdi3(du_int a, du_int b);
   8
   9 // result = a / b.
  10 // both inputs and the output are 64-bit unsigned 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 // Stephen Canon, December 2008
  19
  20 #ifdef __i386__
  21
  22 .text
  23 .balign 4
  24 DEFINE_COMPILERRT_FUNCTION(__udivdi3)
  25
  26         pushl           %ebx
  27         movl     20(%esp),                      %ebx    // Find the index i of the leading bit in b.
  28         bsrl            %ebx,                   %ecx    // If the high word of b is zero, jump to
  29         jz                      9f                                              // the code to handle that special case [9].
  30
  31         // High word of b is known to be non-zero on this branch
  32
  33         movl     16(%esp),                      %eax    // Construct bhi, containing bits [1+i:32+i] of b
  34
  35         shrl            %cl,                    %eax    // Practically, this means that bhi is given by:
  36         shrl            %eax                                    //
  37         notl            %ecx                                    //              bhi = (high word of b) << (31 - i) |
  38         shll            %cl,                    %ebx    //                        (low word of b) >> (1 + i)
  39         orl                     %eax,                   %ebx    //
  40         movl     12(%esp),                      %edx    // Load the high and low words of a, and jump
  41         movl      8(%esp),                      %eax    // to [1] if the high word is larger than bhi
  42         cmpl            %ebx,                   %edx    // to avoid overflowing the upcoming divide.
  43         jae                     1f
  44
  45         // High word of a is greater than or equal to (b >> (1 + i)) on this branch
  46
  47         divl            %ebx                                    // eax <-- qs, edx <-- r such that ahi:alo = bs*qs + r
  48
  49         pushl           %edi
  50         notl            %ecx
  51         shrl            %eax
  52         shrl            %cl,                    %eax    // q = qs >> (1 + i)
  53         movl            %eax,                   %edi
  54         mull     20(%esp)                                       // q*blo
  55         movl     12(%esp),                      %ebx
  56         movl     16(%esp),                      %ecx    // ECX:EBX = a
  57         subl            %eax,                   %ebx
  58         sbbl            %edx,                   %ecx    // ECX:EBX = a - q*blo
  59         movl     24(%esp),                      %eax
  60         imull           %edi,                   %eax    // q*bhi
  61         subl            %eax,                   %ecx    // ECX:EBX = a - q*b
  62         sbbl            $0,                             %edi    // decrement q if remainder is negative
  63         xorl            %edx,                   %edx
  64         movl            %edi,                   %eax
  65         popl            %edi
  66         popl            %ebx
  67         retl
  68
  69
  70 1:      // High word of a is greater than or equal to (b >> (1 + i)) on this branch
  71
  72         subl            %ebx,                   %edx    // subtract bhi from ahi so that divide will not
  73         divl            %ebx                                    // overflow, and find q and r such that
  74                                                                                 //
  75                                                                                 //              ahi:alo = (1:q)*bhi + r
  76                                                                                 //
  77                                                                                 // Note that q is a number in (31-i).(1+i)
  78                                                                                 // fix point.
  79
  80         pushl           %edi
  81         notl            %ecx
  82         shrl            %eax
  83         orl                     $0x80000000,    %eax
  84         shrl            %cl,                    %eax    // q = (1:qs) >> (1 + i)
  85         movl            %eax,                   %edi
  86         mull     20(%esp)                                       // q*blo
  87         movl     12(%esp),                      %ebx
  88         movl     16(%esp),                      %ecx    // ECX:EBX = a
  89         subl            %eax,                   %ebx
  90         sbbl            %edx,                   %ecx    // ECX:EBX = a - q*blo
  91         movl     24(%esp),                      %eax
  92         imull           %edi,                   %eax    // q*bhi
  93         subl            %eax,                   %ecx    // ECX:EBX = a - q*b
  94         sbbl            $0,                             %edi    // decrement q if remainder is negative
  95         xorl            %edx,                   %edx
  96         movl            %edi,                   %eax
  97         popl            %edi
  98         popl            %ebx
  99         retl
 100
 101
 102 9:      // High word of b is zero on this branch
 103
 104         movl     12(%esp),                      %eax    // Find qhi and rhi such that
 105         movl     16(%esp),                      %ecx    //
 106         xorl            %edx,                   %edx    //              ahi = qhi*b + rhi       with    0 ≤ rhi < b
 107         divl            %ecx                                    //
 108         movl            %eax,                   %ebx    //
 109         movl      8(%esp),                      %eax    // Find qlo such that
 110         divl            %ecx                                    //
 111         movl            %ebx,                   %edx    //              rhi:alo = qlo*b + rlo  with 0 ≤ rlo < b
 112         popl            %ebx                                    //
 113         retl                                                            // and return qhi:qlo
 114 END_COMPILERRT_FUNCTION(__udivdi3)
 115
 116 #endif // __i386__
 117
 118 NO_EXEC_STACK_DIRECTIVE
 119