[builtins] Make __umodsi3/__udivdi3/__umoddi3 standalone (shift and subtract)

[MaskRay]

Summary

@kamleshbhalui reported that when the Standard Extension M
(Multiplication and Division) is disabled for RISC-V,
__udivdi3 will call __udivmodti4 which will in turn calls __udivdi3.

This patch moves __udivsi3 (shift and subtract) to int_div_impl.inc
__udivXi3, optimize a bit, add a __umodXi3, and use __udivXi3 and
__umodXi3 to define __udivsi3 __umodsi3 __udivdi3 __umoddi3.

[kamleshbhalui]

Code review in D77744 is performance-wise better than this.

[MaskRay]

Add __builtin_clzll to speed up

[kamleshbhalui]

it's still less optimal.

[MaskRay]

In D77912#1975893, @kamleshbhalui wrote:

it's still less optimal.

How?

[kamleshbhalui]

for this input
a=3325549423267495579 ,b=2351357301745665781
and compiled with -O2 with clang-9.
it takes 299 ns.
while D77744 takes only 91ns.

[kamleshbhalui]

here is compiler detils i tried upon.

clang version 9.0.0 (tags/RELEASE_900/final)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /usr/local/clang_9.0.0/bin

[MaskRay]

Re-purpose

[MaskRay]

In D77912#1976373, @kamleshbhalui wrote:

here is compiler detils i tried upon.

clang version 9.0.0 (tags/RELEASE_900/final)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /usr/local/clang_9.0.0/bin

OK. I benchmarked __udivsi3. That version is actually slightly faster than D77744. I moved that function to int_div_impl.inc

[kamleshbhalui]

Thanks, LGTM.

[luismarques]

In D77912#1976893, @MaskRay wrote:

OK. I benchmarked __udivsi3. That version is actually slightly faster than D77744. I moved that function to int_div_impl.inc

What was the benchmark methodology?
I'm wondering if PC benchmark results make sense for the kinds of targets that are likely to benefit from these software implementations. For microcontrollers I also wonder if a simpler but smaller implementation might be a better trade-off, but I understand that the code came from udivsi3.c so that concern is arguably outside the scope of this patch.
Ideally this patch should have test changes that show its impact and how it fixes the problem.

[MaskRay]

In D77912#1978786, @luismarques wrote:

In D77912#1976893, @MaskRay wrote:

OK. I benchmarked __udivsi3. That version is actually slightly faster than D77744. I moved that function to int_div_impl.inc

What was the benchmark methodology?

int main() {
#ifdef B
  du_int s=1;
  for (int i=0; i <100000000; i++) {
    du_int a = xorshift64(&s);
    du_int b = xorshift64(&s);
    du_int c = div(a, b);
    asm volatile("" : : "r"(c));
  }
#else

  for (int a = 0; a < 2000; a++)
    for (int b = 1; b < 2000; b++) {
      if (div(a, b) != a/b) {
        printf("%d/%d\n", a, b);
        return 1;
      }
      if (mod(a, b) != a%b) {
        printf("%d%%%d\n", a, b);
        return 1;
      }
    }
#endif
}

-DB for benchmark. perf stat -r 30 ./a
The default for correctness. compiler-rt/test/builtins/Unit/ has some large number tests.

I'm wondering if PC benchmark results make sense for the kinds of targets that are likely to benefit from these software implementations. For microcontrollers I also wonder if a simpler but smaller implementation might be a better trade-off, but I understand that the code came from udivsi3.c so that concern is arguably outside the scope of this patch.

I don't think the performance matters that much. compiler-rt/lib/builtins as is is not optimized for every architecture which may lack division instructions. We probably want to go the libgcc extreme route.

Ideally this patch should have test changes that show its impact and how it fixes the problem.

compiler-rt/test/builtins/Unit/ has some tests. This is a runtime issue which only arises in some configurations. I believe riscv32 witht M extension can trigger the problem. It is not really feasible to have a unittest.

[bjope]

compiler-rt/lib/builtins/int_div_impl.inc

1 ↗

(On Diff #257408)

This broke things for us downstream (with different char size).

Do you mind if I change the condition to

sizeof(a) * CHAR_BIT== 64

Btw,. shouldn't there be a file header in this file with copyright/license information etc (see http://llvm.org/docs/CodingStandards.html#file-headers)? How could that slip through review?

[bjope]

compiler-rt/lib/builtins/int_div_impl.inc

1 ↗

(On Diff #257408)

Suggested fixup: https://reviews.llvm.org/D78300

[MaskRay]

compiler-rt/lib/builtins/int_div_impl.inc

1 ↗

(On Diff #257408)

This broke things for us downstream (with different char size).

Can you clarify the CHAR_BIT value on your platform? sizeof(a) * CHAR_BIT == 64 does not make the code clearer. A better version than the current one will be sizeof(a) == sizeof(unsigned long long)

Lots of places can have implication that CHAR_BIT=8. Importantly, POSIX CX requires CHAR_BIT to be 8.
Supporting a CHAR_BIT!=8 may be impractical in practice... For your particular problem, if sizeof(a) == sizeof(unsigned long long) looks good to you, I can fix that. I am more concerned that supporting a different CHAR_BIT!=8 will require numerous fixups everywhere in LLVM and will impose huge mental burden for various places people use bitwise arithemtics and many other operations.

[bjope]

compiler-rt/lib/builtins/int_div_impl.inc

1 ↗

(On Diff #257408)

We certainly got some other fixes downstream for CHAR_BIT==16, so this was just "yet another" problem that popped up for something that has been working in the past. I can keep this as yet-another-size-of-char-fixup downstream, but thought it wouldn't hurt to make this change.

I suggested using CHAR_BIT for two reasons:

1. I was a bit fooled by the defines in int_lib.h that __builtin_clzll was expecting uint64_t as input. But now I realize that "unsigned long long" is the correct type for the argument.
2. I got the feeling that sizeof(...) * CHAR_BIT was a quite common pattern in compiler-rt/lib/builtins.

I have updated https://reviews.llvm.org/D78300 according to your suggestion. It makes sense considering (1) above. Maybe we can continue the discussion in that review.

[tonic]

Unfortunately, this patch violates copyright of the The PowerPC Compiler Writer's Guide. Please revert this patch, remove the copyrighted code, and you can submit a new patch for the other changes. For future patches that use guides with copyright, please consult with the LLVM Foundation board before committing. Thank you!

[MaskRay]

In D77912#3465400, @tonic wrote:

Unfortunately, this patch violates copyright of the The PowerPC Compiler Writer's Guide. Please revert this patch, remove the copyrighted code, and you can submit a new patch for the other changes. For future patches that use guides with copyright, please consult with the LLVM Foundation board before committing. Thank you!

If this request is related to "// Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide" in the code, then I think it should apply to the very first commit
fd089990f76ec6392dbd0138ab874d90c632d2a4 (2009) by @ddunbar .

This patch merely copied this old comment. I don't think I am the appropriate one to take any action here.

Please also read the nature of the patch :)

[tonic]

In D77912#3465553, @MaskRay wrote:

In D77912#3465400, @tonic wrote:

Unfortunately, this patch violates copyright of the The PowerPC Compiler Writer's Guide. Please revert this patch, remove the copyrighted code, and you can submit a new patch for the other changes. For future patches that use guides with copyright, please consult with the LLVM Foundation board before committing. Thank you!

If this request is related to "// Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide" in the code, then I think it should apply to the very first commit
fd089990f76ec6392dbd0138ab874d90c632d2a4 (2009) by @ddunbar .

This patch merely copied this old comment. I don't think I am the appropriate one to take any action here.

Please also read the nature of the patch :)

My apologies for missing that. I will be creating a patch to remove this then and other references.

[compnerd]

In D77912#3465615, @tonic wrote:

In D77912#3465553, @MaskRay wrote:

In D77912#3465400, @tonic wrote:

Unfortunately, this patch violates copyright of the The PowerPC Compiler Writer's Guide. Please revert this patch, remove the copyrighted code, and you can submit a new patch for the other changes. For future patches that use guides with copyright, please consult with the LLVM Foundation board before committing. Thank you!

If this request is related to "// Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide" in the code, then I think it should apply to the very first commit
fd089990f76ec6392dbd0138ab874d90c632d2a4 (2009) by @ddunbar .

This patch merely copied this old comment. I don't think I am the appropriate one to take any action here.

Please also read the nature of the patch :)

My apologies for missing that. I will be creating a patch to remove this then and other references.

I believe that the comment may be referring to the algorithm rather than the implementation itself as the book provides assembly listings for PPC.

[tonic]

In D77912#3465723, @compnerd wrote:

In D77912#3465615, @tonic wrote:

In D77912#3465553, @MaskRay wrote:

In D77912#3465400, @tonic wrote:

Unfortunately, this patch violates copyright of the The PowerPC Compiler Writer's Guide. Please revert this patch, remove the copyrighted code, and you can submit a new patch for the other changes. For future patches that use guides with copyright, please consult with the LLVM Foundation board before committing. Thank you!

If this request is related to "// Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide" in the code, then I think it should apply to the very first commit
fd089990f76ec6392dbd0138ab874d90c632d2a4 (2009) by @ddunbar .

This patch merely copied this old comment. I don't think I am the appropriate one to take any action here.

Please also read the nature of the patch :)

My apologies for missing that. I will be creating a patch to remove this then and other references.

I believe that the comment may be referring to the algorithm rather than the implementation itself as the book provides assembly listings for PPC.

The LLVM Foundation legal counsel has advised us that it violates copyright.

[compnerd]

In D77912#3465615, @tonic wrote:

My apologies for missing that. I will be creating a patch to remove this then and other references.

I believe that the comment may be referring to the algorithm rather than the implementation itself as the book provides assembly listings for PPC.

The LLVM Foundation legal counsel has advised us that it violates copyright.

Okay, thank you for checking.

[kbarton]

I'm working with the IBM legal team to see if there is any way we can get an exception or workaround for the copyright (these probably aren't the correct legal terms, but hopefully people understand the intention). I can update here once I have more information.

compiler-rt/lib/builtins/udivdi3.c

 //
 //===----------------------------------------------------------------------===//
 
 #include "int_lib.h"
 
 // Returns: a / b
 
 COMPILER_RT_ABI du_int __udivdi3(du_int a, du_int b) {
-  return __udivmoddi4(a, b, 0);
+  if (!a) return 0;
+  const int N = sizeof(du_int) * CHAR_BIT;
+  du_int r = 0;
+  int i = __builtin_clzll(a);
+  a <<= i;
+  for (; i < N; i++) {
+    r = (r << 1) | (a >> (N-1));
+    a <<= 1;
+    if (r >= b) {
+      r -= b;
+      ++a;
+    }
+  }
+  return a;
 }

compiler-rt/lib/builtins/umoddi3.c

 //
 //===----------------------------------------------------------------------===//
 
 #include "int_lib.h"
 
 // Returns: a % b
 
 COMPILER_RT_ABI du_int __umoddi3(du_int a, du_int b) {
-  du_int r;
-  __udivmoddi4(a, b, &r);
+  if (!a) return 0;
+  const int N = sizeof(du_int) * CHAR_BIT;
+  du_int r = 0;
+  int i = __builtin_clzll(a);
+  a <<= i;
+  for (; i < N; i++) {
+    r = (r << 1) | (a >> (N-1));
+    a <<= 1;
+    if (r >= b) {
+      r -= b;
+      ++a;
+    }
+  }
   return r;
 }