compiler_rt: add __paritysi2, __paritydi2, __parityti2

- use Bit Twiddling Hacks: Compute parity in parallel
- test cases derived from popcount.zig
- tests: compare naive approach 10_000 times with random numbers created
  from naive seed 42
- compiler_rt.zig: sort by LLVM builtin order and add comments to improve structure

See #1290

1 files changed, 48 insertions, 21 deletions

diff --git a/lib/std/special/compiler_rt.zig b/lib/std/special/compiler_rt.zig
index a2e19db25f..b924ae584e 100644
--- a/lib/std/special/compiler_rt.zig
+++ b/lib/std/special/compiler_rt.zig
@@ -76,10 +76,11 @@ comptime {
 
         @export(__extendhfsf2, .{ .name = "__gnu_h2f_ieee", .linkage = linkage });
 
-        const __muloti4 = @import("compiler_rt/muloti4.zig").__muloti4;
-        @export(__muloti4, .{ .name = "__muloti4", .linkage = linkage });
+        // Integral arithmetic which returns if overflow
         const __mulodi4 = @import("compiler_rt/mulodi4.zig").__mulodi4;
         @export(__mulodi4, .{ .name = "__mulodi4", .linkage = linkage });
+        const __muloti4 = @import("compiler_rt/muloti4.zig").__muloti4;
+        @export(__muloti4, .{ .name = "__muloti4", .linkage = linkage });
     }
 
     if (builtin.os.tag == .windows) {
@@ -217,6 +218,7 @@ comptime {
         const __divtf3 = @import("compiler_rt/divtf3.zig").__divtf3;
         @export(__divtf3, .{ .name = "__divtf3", .linkage = linkage });
 
+        // Integral bit manipulation
         const __ashldi3 = @import("compiler_rt/shift.zig").__ashldi3;
         @export(__ashldi3, .{ .name = "__ashldi3", .linkage = linkage });
         const __ashlti3 = @import("compiler_rt/shift.zig").__ashlti3;
@@ -230,6 +232,33 @@ comptime {
         const __lshrti3 = @import("compiler_rt/shift.zig").__lshrti3;
         @export(__lshrti3, .{ .name = "__lshrti3", .linkage = linkage });
 
+        const __clzsi2 = @import("compiler_rt/count0bits.zig").__clzsi2;
+        @export(__clzsi2, .{ .name = "__clzsi2", .linkage = linkage });
+        const __clzdi2 = @import("compiler_rt/count0bits.zig").__clzdi2;
+        @export(__clzdi2, .{ .name = "__clzdi2", .linkage = linkage });
+        const __clzti2 = @import("compiler_rt/count0bits.zig").__clzti2;
+        @export(__clzti2, .{ .name = "__clzti2", .linkage = linkage });
+        const __ctzsi2 = @import("compiler_rt/count0bits.zig").__ctzsi2;
+        @export(__ctzsi2, .{ .name = "__ctzsi2", .linkage = linkage });
+        const __ctzdi2 = @import("compiler_rt/count0bits.zig").__ctzdi2;
+        @export(__ctzdi2, .{ .name = "__ctzdi2", .linkage = linkage });
+        const __ctzti2 = @import("compiler_rt/count0bits.zig").__ctzti2;
+        @export(__ctzti2, .{ .name = "__ctzti2", .linkage = linkage });
+
+        const __paritysi2 = @import("compiler_rt/parity.zig").__paritysi2;
+        @export(__paritysi2, .{ .name = "__paritysi2", .linkage = linkage });
+        const __paritydi2 = @import("compiler_rt/parity.zig").__paritydi2;
+        @export(__paritydi2, .{ .name = "__paritydi2", .linkage = linkage });
+        const __parityti2 = @import("compiler_rt/parity.zig").__parityti2;
+        @export(__parityti2, .{ .name = "__parityti2", .linkage = linkage });
+        const __popcountsi2 = @import("compiler_rt/popcount.zig").__popcountsi2;
+        @export(__popcountsi2, .{ .name = "__popcountsi2", .linkage = linkage });
+        const __popcountdi2 = @import("compiler_rt/popcount.zig").__popcountdi2;
+        @export(__popcountdi2, .{ .name = "__popcountdi2", .linkage = linkage });
+        const __popcountti2 = @import("compiler_rt/popcount.zig").__popcountti2;
+        @export(__popcountti2, .{ .name = "__popcountti2", .linkage = linkage });
+
+        // Integral / floating point conversion (part 1/2)
         const __floatsidf = @import("compiler_rt/floatsiXf.zig").__floatsidf;
         @export(__floatsidf, .{ .name = "__floatsidf", .linkage = linkage });
         const __floatsisf = @import("compiler_rt/floatsiXf.zig").__floatsisf;
@@ -291,6 +320,7 @@ comptime {
         const __extendsfdf2 = @import("compiler_rt/extendXfYf2.zig").__extendsfdf2;
         @export(__extendsfdf2, .{ .name = "__extendsfdf2", .linkage = linkage });
 
+        // Integral / floating point conversion (part 2/2)
         const __fixunssfsi = @import("compiler_rt/fixunssfsi.zig").__fixunssfsi;
         @export(__fixunssfsi, .{ .name = "__fixunssfsi", .linkage = linkage });
         const __fixunssfdi = @import("compiler_rt/fixunssfdi.zig").__fixunssfdi;
@@ -333,18 +363,13 @@ comptime {
 
         const __udivmoddi4 = @import("compiler_rt/int.zig").__udivmoddi4;
         @export(__udivmoddi4, .{ .name = "__udivmoddi4", .linkage = linkage });
-        const __popcountsi2 = @import("compiler_rt/popcount.zig").__popcountsi2;
-        @export(__popcountsi2, .{ .name = "__popcountsi2", .linkage = linkage });
-        const __popcountdi2 = @import("compiler_rt/popcount.zig").__popcountdi2;
-        @export(__popcountdi2, .{ .name = "__popcountdi2", .linkage = linkage });
-        const __popcountti2 = @import("compiler_rt/popcount.zig").__popcountti2;
-        @export(__popcountti2, .{ .name = "__popcountti2", .linkage = linkage });
 
         if (is_darwin) {
             const __isPlatformVersionAtLeast = @import("compiler_rt/os_version_check.zig").__isPlatformVersionAtLeast;
             @export(__isPlatformVersionAtLeast, .{ .name = "__isPlatformVersionAtLeast", .linkage = linkage });
         }
 
+        // Integral arithmetic
         const __mulsi3 = @import("compiler_rt/int.zig").__mulsi3;
         @export(__mulsi3, .{ .name = "__mulsi3", .linkage = linkage });
         const __muldi3 = @import("compiler_rt/muldi3.zig").__muldi3;
@@ -372,24 +397,26 @@ comptime {
         const __udivmodsi4 = @import("compiler_rt/int.zig").__udivmodsi4;
         @export(__udivmodsi4, .{ .name = "__udivmodsi4", .linkage = linkage });
 
+        // missing: Integral arithmetic with trapping overflow
+
+        // missing: Integral arithmetic which returns if overflow
+
+        // missing: Integral comparison
+        // (a <  b) => 0
+        // (a == b) => 1
+        // (a >  b) => 2
+
+        // missing: Floating point raised to integer power
+
+        // missing: Complex arithmetic
+        // (a + ib) * (c + id)
+        // (a + ib) / (c + id)
+
         const __negsf2 = @import("compiler_rt/negXf2.zig").__negsf2;
         @export(__negsf2, .{ .name = "__negsf2", .linkage = linkage });
         const __negdf2 = @import("compiler_rt/negXf2.zig").__negdf2;
         @export(__negdf2, .{ .name = "__negdf2", .linkage = linkage });
 
-        const __clzsi2 = @import("compiler_rt/count0bits.zig").__clzsi2;
-        @export(__clzsi2, .{ .name = "__clzsi2", .linkage = linkage });
-        const __clzdi2 = @import("compiler_rt/count0bits.zig").__clzdi2;
-        @export(__clzdi2, .{ .name = "__clzdi2", .linkage = linkage });
-        const __clzti2 = @import("compiler_rt/count0bits.zig").__clzti2;
-        @export(__clzti2, .{ .name = "__clzti2", .linkage = linkage });
-        const __ctzsi2 = @import("compiler_rt/count0bits.zig").__ctzsi2;
-        @export(__ctzsi2, .{ .name = "__ctzsi2", .linkage = linkage });
-        const __ctzdi2 = @import("compiler_rt/count0bits.zig").__ctzdi2;
-        @export(__ctzdi2, .{ .name = "__ctzdi2", .linkage = linkage });
-        const __ctzti2 = @import("compiler_rt/count0bits.zig").__ctzti2;
-        @export(__ctzti2, .{ .name = "__ctzti2", .linkage = linkage });
-
         if (builtin.link_libc and os_tag == .openbsd) {
             const __emutls_get_address = @import("compiler_rt/emutls.zig").__emutls_get_address;
             @export(__emutls_get_address, .{ .name = "__emutls_get_address", .linkage = linkage });