devanbenz commented on code in PR #11467:
URL: https://github.com/apache/arrow-rs/pull/11467#discussion_r4379365875


##########
arrow-buffer/src/divisor.rs:
##########
@@ -0,0 +1,462 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+macro_rules! divisor_enum {
+    ($name:ident, $power_of_two:ident, $multiplier:ident, $t:ty) => {
+        #[doc = concat!("A `", stringify!($t), "` divisor, precomputed once to 
divide many values by it")]
+        ///
+        /// Division by a divisor that is only known at run time needs a 
divide instruction.
+        /// [`Self::new`] precomputes a shift and a mask when the magnitude of 
the divisor is a
+        /// power of two, and otherwise a multiplier with the method in
+        /// [Granlund and Montgomery, "Division by Invariant Integers using 
Multiplication" (1994)](https://gmplib.org/~tege/divcnst-pldi94.pdf),
+        /// so that each division is a high multiply, shifts and additions.
+        ///
+        /// To divide many values, match on the variant once, before the loop, 
and call the
+        /// variant's methods in the loop. They don't branch on the divisor, 
so the loop doesn't
+        /// depend on the compiler moving a branch out of it. Move the variant 
into the loop's
+        /// closure, so that the compiler doesn't reload its fields through a 
reference for each
+        /// value. [`Self::wrapping_div_rem`] matches on each call.
+        ///
+        /// # Example
+        /// ```
+        #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
+        #[doc = concat!("let values: Vec<", stringify!($t), "> = vec![100, 7, 
64];")]
+        #[doc = concat!("let quotients: Vec<_> = match ", stringify!($name), 
"::new(7).unwrap() {")]
+        #[doc = concat!("    ", stringify!($name), "::PowerOfTwo(d) => 
values.iter().map(move |n| d.wrapping_div_rem(*n).0).collect(),")]
+        #[doc = concat!("    ", stringify!($name), "::Multiplier(d) => 
values.iter().map(move |n| d.wrapping_div_rem(*n).0).collect(),")]
+        /// };
+        /// assert_eq!(quotients, [14, 1, 9]);
+        /// ```
+        #[derive(Debug, Clone, Copy)]
+        pub enum $name {
+            /// A divisor whose magnitude is a power of two
+            PowerOfTwo($power_of_two),
+            /// Any other divisor
+            Multiplier($multiplier),
+        }
+
+        impl $name {
+            /// Returns a divisor for `divisor`, or `None` if `divisor` is zero
+            ///
+            /// # Example
+            /// ```
+            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
+            #[doc = concat!("const SEVEN: ", stringify!($name), " = ", 
stringify!($name), "::new(7).unwrap();")]
+            #[doc = concat!("assert!(", stringify!($name), 
"::new(0).is_none());")]
+            /// ```
+            pub const fn new(divisor: $t) -> Option<Self> {
+                if divisor == 0 {
+                    return None;
+                }
+                Some(match $power_of_two::new(divisor) {
+                    Some(d) => Self::PowerOfTwo(d),
+                    None => Self::Multiplier($multiplier::new(divisor)),
+                })
+            }
+
+            /// Returns `(n.wrapping_div(divisor), n.wrapping_rem(divisor))`
+            ///
+            /// # Example
+            /// ```
+            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
+            #[doc = concat!("let divisor = ", stringify!($name), 
"::new(7).unwrap();")]
+            /// assert_eq!(divisor.wrapping_div_rem(100), (14, 2));
+            /// ```
+            #[inline]
+            pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
+                match self {
+                    Self::PowerOfTwo(d) => d.wrapping_div_rem(n),
+                    Self::Multiplier(d) => d.wrapping_div_rem(n),
+                }
+            }
+        }
+    };
+}
+
+macro_rules! unsigned_divisor {
+    ($name:ident, $power_of_two:ident, $multiplier:ident, $t:ty, $wide:ty) => {
+        divisor_enum!($name, $power_of_two, $multiplier, $t);
+
+        #[doc = concat!("A `", stringify!($t), "` divisor that is a power of 
two, see [`", stringify!($name), "`]")]
+        #[derive(Debug, Clone, Copy)]
+        pub struct $power_of_two {
+            shift: u32,
+            mask: $t,
+        }
+
+        impl $power_of_two {
+            const fn new(divisor: $t) -> Option<Self> {
+                if !divisor.is_power_of_two() {
+                    return None;
+                }
+                Some(Self {
+                    shift: divisor.trailing_zeros(),
+                    mask: divisor - 1,
+                })
+            }
+
+            /// Returns `(n / divisor, n % divisor)`
+            ///
+            /// # Example
+            /// ```
+            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
+            #[doc = concat!("let ", stringify!($name), "::PowerOfTwo(divisor) 
= ", stringify!($name), "::new(8).unwrap() else { unreachable!() };")]
+            /// assert_eq!(divisor.wrapping_div_rem(100), (12, 4));
+            /// ```
+            #[inline]
+            pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
+                (n >> self.shift, n & self.mask)
+            }
+        }
+
+        #[doc = concat!("A `", stringify!($t), "` divisor that isn't a power 
of two, see [`", stringify!($name), "`]")]
+        ///
+        /// It uses the multiplier from figure 4.1 of
+        /// [Granlund and Montgomery, "Division by Invariant Integers using 
Multiplication" (1994)](https://gmplib.org/~tege/divcnst-pldi94.pdf).
+        #[derive(Debug, Clone, Copy)]
+        pub struct $multiplier {
+            divisor: $t,
+            /// `m'` in figure 4.1
+            multiplier: $t,
+            /// `sh2` in figure 4.1
+            shift: u32,
+        }
+
+        impl $multiplier {
+            /// `divisor` must be at least 3 and not a power of two
+            const fn new(divisor: $t) -> Self {
+                // ceil(log2(divisor)), which is at least 2 because divisor >= 
3. So figure 4.1's
+                // `sh1 = min(l, 1)` is always 1 and `sh2 = max(l - 1, 0)` is 
`l - 1`
+                let l = <$t>::BITS - (divisor - 1).leading_zeros();
+                // 2^l - divisor < divisor, so the multiplier fits in the 
narrow type
+                let numerator = ((1 << l) - divisor as $wide) << <$t>::BITS;
+                Self {
+                    divisor,
+                    multiplier: (numerator / divisor as $wide + 1) as $t,
+                    shift: l - 1,
+                }
+            }
+
+            /// Returns `(n / divisor, n % divisor)`
+            ///
+            /// # Example
+            /// ```
+            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
+            #[doc = concat!("let ", stringify!($name), "::Multiplier(divisor) 
= ", stringify!($name), "::new(7).unwrap() else { unreachable!() };")]
+            /// assert_eq!(divisor.wrapping_div_rem(100), (14, 2));
+            /// ```
+            #[inline]
+            pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
+                let t = ((self.multiplier as $wide * n as $wide) >> 
<$t>::BITS) as $t;
+                // `(n + t) >> l` could overflow, so this halves `n - t` 
first, as figure 4.1 does
+                let q = (t + ((n - t) >> 1)) >> self.shift;
+                (q, n - q * self.divisor)
+            }
+        }
+    };
+}
+
+macro_rules! signed_divisor {
+    ($name:ident, $power_of_two:ident, $multiplier:ident, $t:ty, $wide:ty) => {
+        divisor_enum!($name, $power_of_two, $multiplier, $t);
+
+        impl $name {
+            #[doc = concat!("Returns `(n / divisor, n % divisor)`, or `None` 
for `", stringify!($t), "::MIN / -1`")]
+            ///
+            /// It matches on the variant on each call. Only 
[`Self::PowerOfTwo`] can return `None`.
+            ///
+            /// # Example
+            /// ```
+            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
+            #[doc = concat!("let divisor = ", stringify!($name), 
"::new(-7).unwrap();")]
+            /// assert_eq!(divisor.checked_div_rem(-100), Some((14, -2)));
+            ///
+            #[doc = concat!("let minus_one = ", stringify!($name), 
"::new(-1).unwrap();")]
+            #[doc = concat!("assert_eq!(minus_one.checked_div_rem(", 
stringify!($t), "::MIN), None);")]
+            /// ```
+            #[inline]
+            pub const fn checked_div_rem(self, n: $t) -> Option<($t, $t)> {
+                match self {
+                    Self::PowerOfTwo(d) => d.checked_div_rem(n),
+                    Self::Multiplier(d) => Some(d.wrapping_div_rem(n)),
+                }
+            }
+        }
+
+        #[doc = concat!("A `", stringify!($t), "` divisor whose magnitude is a 
power of two, see [`", stringify!($name), "`]")]
+        ///
+        /// The quotient and remainder follow sections 10-1 and 10-2 of 
Warren, "Hacker's Delight",
+        /// 2nd edition. Those sections compute the addend `2^k - 1` for a 
negative `n` with two
+        /// shifts. This type computes it with one shift that spreads the sign 
bit of `n` and an AND
+        /// with `2^k - 1`, which it computes once for the divisor.
+        #[derive(Debug, Clone, Copy)]
+        pub struct $power_of_two {
+            shift: u32,
+            /// `|divisor| - 1`
+            mask: $t,
+            /// -1 if the divisor is negative, otherwise 0
+            sign: $t,
+        }
+
+        impl $power_of_two {
+            const fn new(divisor: $t) -> Option<Self> {
+                let magnitude = divisor.unsigned_abs();
+                if !magnitude.is_power_of_two() {
+                    return None;
+                }
+                Some(Self {
+                    shift: magnitude.trailing_zeros(),
+                    mask: (magnitude - 1) as $t,
+                    sign: divisor >> (<$t>::BITS - 1),
+                })
+            }
+
+            #[doc = concat!("Returns `(n.wrapping_div(divisor), 
n.wrapping_rem(divisor))`, so `", stringify!($t), "::MIN / -1` returns `(", 
stringify!($t), "::MIN, 0)`")]
+            ///
+            /// # Example
+            /// ```
+            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
+            #[doc = concat!("let ", stringify!($name), "::PowerOfTwo(divisor) 
= ", stringify!($name), "::new(-8).unwrap() else { unreachable!() };")]
+            /// assert_eq!(divisor.wrapping_div_rem(-100), (12, -4));
+            ///
+            #[doc = concat!("let ", stringify!($name), 
"::PowerOfTwo(minus_one) = ", stringify!($name), "::new(-1).unwrap() else { 
unreachable!() };")]
+            #[doc = concat!("assert_eq!(minus_one.wrapping_div_rem(", 
stringify!($t), "::MIN), (", stringify!($t), "::MIN, 0));")]
+            /// ```
+            #[inline]
+            pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
+                // Adding `|divisor| - 1` to a negative `n` makes the shift 
round toward zero
+                let t = n + ((n >> (<$t>::BITS - 1)) & self.mask);
+                let q = t >> self.shift;
+                // `(x ^ sign) - sign` negates `x` when `sign` is -1, and 
wraps only for `MIN / -1`
+                // `t & !mask` is `n` rounded toward zero to a multiple of 
`|divisor|`
+                ((q ^ self.sign).wrapping_sub(self.sign), n - (t & !self.mask))
+            }
+
+            #[doc = concat!("Returns `(n / divisor, n % divisor)`, or `None` 
for `", stringify!($t), "::MIN / -1`")]
+            ///
+            /// # Example
+            /// ```
+            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
+            #[doc = concat!("let ", stringify!($name), "::PowerOfTwo(divisor) 
= ", stringify!($name), "::new(-8).unwrap() else { unreachable!() };")]
+            /// assert_eq!(divisor.checked_div_rem(-100), Some((12, -4)));
+            ///
+            #[doc = concat!("let ", stringify!($name), 
"::PowerOfTwo(minus_one) = ", stringify!($name), "::new(-1).unwrap() else { 
unreachable!() };")]
+            #[doc = concat!("assert_eq!(minus_one.checked_div_rem(", 
stringify!($t), "::MIN), None);")]
+            /// ```
+            #[inline]
+            pub const fn checked_div_rem(self, n: $t) -> Option<($t, $t)> {
+                // -1 is the only divisor with a negative sign and a zero mask
+                if n == <$t>::MIN && self.sign == -1 && self.mask == 0 {
+                    None
+                } else {
+                    Some(self.wrapping_div_rem(n))
+                }
+            }
+        }
+
+        #[doc = concat!("A `", stringify!($t), "` divisor whose magnitude 
isn't a power of two, see [`", stringify!($name), "`]")]
+        ///
+        /// It uses the signed multiplier from figure 5.1 of
+        /// [Granlund and Montgomery, "Division by Invariant Integers using 
Multiplication" (1994)](https://gmplib.org/~tege/divcnst-pldi94.pdf).
+        #[derive(Debug, Clone, Copy)]
+        pub struct $multiplier {
+            divisor: $t,
+            /// `m'` in figure 5.1
+            multiplier: $t,
+            /// `sh_post` in figure 5.1
+            shift: u32,
+        }
+
+        impl $multiplier {
+            /// `|divisor|` must be at least 3 and not a power of two
+            const fn new(divisor: $t) -> Self {
+                let magnitude = divisor.unsigned_abs();
+                // ceil(log2(|divisor|)), which is at least 2 because 
|divisor| >= 3, so figure
+                // 5.1's `max(..., 1)` isn't needed
+                let l = <$t>::BITS - (magnitude - 1).leading_zeros();
+                // m = 1 + floor(2^(N + l - 1) / |divisor|) is between 2^(N - 
1) and 2^N, so
+                // m - 2^N fits in the narrow type
+                let m = 1 + (1 << (<$t>::BITS + l - 1)) / magnitude as $wide;
+                Self {
+                    divisor,
+                    multiplier: (m - (1 << <$t>::BITS)) as $t,
+                    shift: l - 1,
+                }
+            }
+
+            /// Returns `(n / divisor, n % divisor)`, which can't overflow
+            ///
+            /// # Example
+            /// ```
+            #[doc = concat!("# use arrow_buffer::", stringify!($name), ";")]
+            #[doc = concat!("let ", stringify!($name), "::Multiplier(divisor) 
= ", stringify!($name), "::new(-7).unwrap() else { unreachable!() };")]
+            /// assert_eq!(divisor.wrapping_div_rem(-100), (14, -2));
+            /// ```
+            #[inline]
+            pub const fn wrapping_div_rem(self, n: $t) -> ($t, $t) {
+                // `MULSH(m', n)` in figure 5.1
+                let high = ((self.multiplier as $wide * n as $wide) >> 
<$t>::BITS) as $t;
+                // The shift rounds down, and subtracting the sign of `n` 
rounds toward zero instead
+                let q = ((n + high) >> self.shift) - (n >> (<$t>::BITS - 1));
+                let sign = self.divisor >> (<$t>::BITS - 1);
+                let q = (q ^ sign) - sign;
+                (q, n - q * self.divisor)

Review Comment:
   Have been experimenting with some performance enhancements for this block of 
code. 
   
   By adding the `magnitude` which is calculated 
[here](https://github.com/apache/arrow-rs/pull/11467/changes#diff-df0cb5d5615022ffb808be3e1f3bbaddcf9bbcb531de95e83d2e230a6334fbb8R287)
 as a field on the `$multiplier` struct: 
   
   ```rust
           #[derive(Debug, Clone, Copy)]
           pub struct $multiplier {
               divisor: $t,
               /// `m'` in figure 5.1
               multiplier: $t,
                        /// magnitude stores the absolute value for divisors
                        magnitude: $t
               /// `sh_post` in figure 5.1
               shift: u32,
           }
   ```
   
   and then lines 314-317 can become
   
   ```rust
   let q0 = ((n + high) >> self.shift) - (n >> (<$t>::BITS - 1));
   let sign = self.divisor >> (<$t>::BITS - 1);
   ((q0 ^ sign) - sign, n - q0 * self.magnitude)
   ```
   
   This results in decreased CPU time. LLVM's cost estimator appears to no 
longer favor a vector loop instead keeping a faster scalar loop for the 
operation. 
   
   Note that I grabbed LLVM output using hardcoded types instead of using the 
macro, was tested using the i64 path and i32 path, both removed the vector loop 
and used the smaller faster scalar loop.  
   
   <details>
   <summary>LLVM output with this PR</summary>
   
   ```llvm
   ; divx::i64_rem_pr
   ; Function Attrs: nofree noinline norecurse nosync nounwind nonlazybind 
memory(argmem: readwrite) uwtable
   define internal fastcc void @divx::i64_rem_pr(ptr noalias nofree noundef 
nonnull readonly align 8 captures(none) %v.0, i64 noundef range(i64 0, 
1152921504606846976) %v.1, ptr noalias nofree noundef nonnull writeonly align 8 
captures(none) %o.0, i64 noundef range(i64 0, 1152921504606846976) %o.1, ptr 
noalias nofree noundef nonnull readonly align 8 captures(none) dead_on_return 
dereferenceable(24) %d) unnamed_addr #5 personality ptr @rust_eh_personality 
!guid !241 {
   start:
     %..i.i.i = tail call noundef i64 @llvm.umin.i64(i64 range(i64 0, 
1152921504606846976) %v.1, i64 %o.1)
     %_2.i5.not = icmp eq i64 %..i.i.i, 0
     br i1 %_2.i5.not, label %bb5, label %bb4.lr.ph
   
   bb4.lr.ph:                                        ; preds = %start
     %_35 = load i64, ptr %d, align 8, !noundef !64
     %0 = getelementptr inbounds nuw i8, ptr %d, i64 8
     %_36 = load i64, ptr %0, align 8, !noundef !64
     %1 = getelementptr inbounds nuw i8, ptr %d, i64 16
     %_37 = load i32, ptr %1, align 8, !noundef !64
     %_24 = sext i64 %_36 to i128
     %2 = and i32 %_37, 63
     %3 = zext nneg i32 %2 to i64
     %_30 = ashr i64 %_35, 63
     %min.iters.check = icmp eq i64 %..i.i.i, 1
     br i1 %min.iters.check, label %bb4.preheader, label %vector.ph
   
   vector.ph:                                        ; preds = %bb4.lr.ph
     %n.vec = and i64 %..i.i.i, 1152921504606846974
     %broadcast.splatinsert = insertelement <2 x i64> poison, i64 %_35, i64 0
     %broadcast.splat = shufflevector <2 x i64> %broadcast.splatinsert, <2 x 
i64> poison, <2 x i32> zeroinitializer
     %broadcast.splatinsert7 = insertelement <2 x i128> poison, i128 %_24, i64 0
     %broadcast.splat8 = shufflevector <2 x i128> %broadcast.splatinsert7, <2 x 
i128> poison, <2 x i32> zeroinitializer
     %broadcast.splatinsert9 = insertelement <2 x i64> poison, i64 %3, i64 0
     %broadcast.splat10 = shufflevector <2 x i64> %broadcast.splatinsert9, <2 x 
i64> poison, <2 x i32> zeroinitializer
     %broadcast.splatinsert11 = insertelement <2 x i64> poison, i64 %_30, i64 0
     %broadcast.splat12 = shufflevector <2 x i64> %broadcast.splatinsert11, <2 
x i64> poison, <2 x i32> zeroinitializer
     br label %vector.body
   
   vector.body:                                      ; preds = %vector.body, 
%vector.ph
     %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
     %4 = getelementptr inbounds nuw [8 x i8], ptr %o.0, i64 %index
     %5 = getelementptr inbounds nuw [8 x i8], ptr %v.0, i64 %index
     %wide.load = load <2 x i64>, ptr %5, align 8
     %6 = sext <2 x i64> %wide.load to <2 x i128>
     %7 = mul nsw <2 x i128> %broadcast.splat8, %6
     %8 = lshr <2 x i128> %7, splat (i128 64)
     %9 = trunc nuw <2 x i128> %8 to <2 x i64>
     %10 = add <2 x i64> %wide.load, %9
     %11 = ashr <2 x i64> %10, %broadcast.splat10
     %12 = lshr <2 x i64> %wide.load, splat (i64 63)
     %13 = add <2 x i64> %11, %12
     %14 = xor <2 x i64> %13, %broadcast.splat12
     %15 = sub <2 x i64> %broadcast.splat12, %14
     %16 = mul <2 x i64> %15, %broadcast.splat
     %17 = add <2 x i64> %16, %wide.load
     store <2 x i64> %17, ptr %4, align 8
     %index.next = add nuw i64 %index, 2
     %18 = icmp eq i64 %index.next, %n.vec
     br i1 %18, label %middle.block, label %vector.body, !llvm.loop !242
   
   middle.block:                                     ; preds = %vector.body
     %cmp.n = icmp eq i64 %..i.i.i, %n.vec
     br i1 %cmp.n, label %bb5, label %bb4.preheader
   
   bb4.preheader:                                    ; preds = %bb4.lr.ph, 
%middle.block
     %iter.sroa.8.06.ph = phi i64 [ 0, %bb4.lr.ph ], [ %n.vec, %middle.block ]
     br label %bb4
   
   bb4:                                              ; preds = %bb4.preheader, 
%bb4
     %iter.sroa.8.06 = phi i64 [ %19, %bb4 ], [ %iter.sroa.8.06.ph, 
%bb4.preheader ]
     %19 = add nuw nsw i64 %iter.sroa.8.06, 1
     %_3.i.i = getelementptr inbounds nuw [8 x i8], ptr %o.0, i64 
%iter.sroa.8.06
     %_3.i1.i = getelementptr inbounds nuw [8 x i8], ptr %v.0, i64 
%iter.sroa.8.06
     %n = load i64, ptr %_3.i1.i, align 8, !noundef !64
     %_25 = sext i64 %n to i128
     %_23 = mul nsw i128 %_24, %_25
     %_22 = lshr i128 %_23, 64
     %_21 = trunc nuw i128 %_22 to i64
     %_28 = add i64 %n, %_21
     %_27 = ashr i64 %_28, %3
     %_29.neg = lshr i64 %n, 63
     %_26 = add i64 %_27, %_29.neg
     %_32 = xor i64 %_26, %_30
     %_31.neg = sub i64 %_30, %_32
     %_34.neg = mul i64 %_31.neg, %_35
     %_33 = add i64 %_34.neg, %n
     store i64 %_33, ptr %_3.i.i, align 8
     %exitcond.not = icmp eq i64 %19, %..i.i.i
     br i1 %exitcond.not, label %bb5, label %bb4, !llvm.loop !243
   
   bb5:                                              ; preds = %bb4, 
%middle.block, %start
     ret void
   }
   ```
   </details>
   
   <details>
   <summary>LLVM output with using a stored magnitude</summary>
   
   ```llvm
   ; divx::i64_rem_b
   ; Function Attrs: nofree noinline norecurse nosync nounwind nonlazybind 
memory(argmem: readwrite) uwtable
   define internal fastcc void @divx::i64_rem_b(ptr noalias nofree noundef 
nonnull readonly align 8 captures(none) %v.0, i64 noundef range(i64 0, 
1152921504606846976) %v.1, ptr noalias nofree noundef nonnull writeonly align 8 
captures(none) %o.0, i64 noundef range(i64 0, 1152921504606846976) %o.1, ptr 
noalias nofree noundef nonnull readonly align 8 captures(none) dead_on_return 
dereferenceable(24) %d) unnamed_addr #5 personality ptr @rust_eh_personality 
!guid !430 {
   start:
     %..i.i.i = tail call noundef i64 @llvm.umin.i64(i64 range(i64 0, 
1152921504606846976) %v.1, i64 %o.1)
     %_2.i5.not = icmp eq i64 %..i.i.i, 0
     br i1 %_2.i5.not, label %bb5, label %bb4.lr.ph
   
   bb4.lr.ph:                                        ; preds = %start
     %_32 = load i64, ptr %d, align 8, !noundef !64
     %0 = getelementptr inbounds nuw i8, ptr %d, i64 8
     %_33 = load i64, ptr %0, align 8, !noundef !64
     %1 = getelementptr inbounds nuw i8, ptr %d, i64 16
     %_34 = load i32, ptr %1, align 8, !noundef !64
     %_27 = sext i64 %_33 to i128
     %2 = and i32 %_34, 63
     %3 = zext nneg i32 %2 to i64
     br label %bb4
   
   bb4:                                              ; preds = %bb4.lr.ph, %bb4
     %iter.sroa.8.06 = phi i64 [ 0, %bb4.lr.ph ], [ %4, %bb4 ]
     %4 = add nuw nsw i64 %iter.sroa.8.06, 1
     %_3.i.i = getelementptr inbounds nuw [8 x i8], ptr %o.0, i64 
%iter.sroa.8.06
     %_3.i1.i = getelementptr inbounds nuw [8 x i8], ptr %v.0, i64 
%iter.sroa.8.06
     %n = load i64, ptr %_3.i1.i, align 8, !noundef !64
     %_28 = sext i64 %n to i128
     %_26 = mul nsw i128 %_27, %_28
     %_25 = lshr i128 %_26, 64
     %_24 = trunc nuw i128 %_25 to i64
     %_30 = add i64 %n, %_24
     %_29 = ashr i64 %_30, %3
     %_31.neg = lshr i64 %n, 63
     %_23 = add i64 %_29, %_31.neg
     %_22 = mul i64 %_23, %_32
     %_12 = sub i64 %n, %_22
     store i64 %_12, ptr %_3.i.i, align 8
     %exitcond.not = icmp eq i64 %4, %..i.i.i
     br i1 %exitcond.not, label %bb5, label %bb4
   
   bb5:                                              ; preds = %bb4, %start
     ret void
   }
   ```
   </details>
   
   Results from intel analyzer:
   
   This PR:
   ```
   Program Elapsed Time: 1.93s
   
   CPU Time: 1.93s
   Time in 1 Vectorized Loop: 1.77s
   GFLOPS: < 0.00
   GINTOPS: 26.31
   ```
   
   With magnitude change:
   ```
   Program Elapsed Time: 1.03s
   
   CPU Time: 1.03s
   GFLOPS: < 0.00
   GINTOPS: 14.25
   ```
   
   LLVM's cost model chose a 2-wide SSE2 loop on my machine that runs slower 
than the scalar one. 
   
   I'd be interested to test this theory on other hardware. 



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]

Reply via email to