[flang] Optimize / and % operators for int128.

[sunshaoce]

Summary

I think these modifications should be able to optimize related calculations.
Sorry if I am mistaken.

[klausler]

This patch only optimizes cases with upper halves all zero. Signed division has opportunities for optimization when upper halves are all ones, too.

But this code only exists as a backstop for builds with C compilers that don't have native 128-bit ints. Correctness is the only thing that matters. I would be very nervous about changing this code unless its performance became important.

flang/include/flang/Common/uint128.h

23

Please use the CHECK macro from flang/include/Common rather than assert(). Or don't crash at all; the original code returns maximum values for division by zero, which is not unreasonable.

168–169

The original statement ("++quotient;") is more clear.

181

I think this code is wrong for negative *this. Are you sure that (-1) % 2 should be -1? Are you sure that (-3) % (-2) should be -3?

[sunshaoce]

Update

[sunshaoce]

Thank you so much for your comments. I learned a lot from them! I noticed algorithms are ingenious here, so I just wanted to make them faster. I kept only one modification and added a corresponding comment. If you think it's unnecessary, I will close this revision. Thanks again!

flang/include/flang/Common/uint128.h

 // Define AVOID_NATIVE_UINT128_T to force the use of UnsignedInt128 below
 // instead of the C++ compiler's native 128-bit unsigned integer type, if
 // it has one.
 #ifndef AVOID_NATIVE_UINT128_T
 #define AVOID_NATIVE_UINT128_T 0
 #endif
 
 #include "leading-zero-bit-count.h"
 #include <cstdint>
 #include <type_traits>
 
 namespace Fortran::common {
 
 template <bool IS_SIGNED = false> class Int128 {
 public:
   constexpr Int128() {}
   // This means of definition provides some portability for
constexpr Int128 operator/(Int128 that) const {
     for (; j < 128; ++j) {
       numerator <<= 1;
       if (bits.high_ & topBit) {
         numerator.low_ |= 1;
       }
       bits <<= 1;
       quotient <<= 1;
       if (numerator >= that) {
-        ++quotient;
+        // Optimized for ++quotient here
+        quotient |= 1;
         numerator -= that;
       }
     }
     return quotient;
   }
 
   constexpr Int128 operator%(Int128 that) const {
     int j{LeadingZeroes()};
     Int128 bits{*this};
     bits <<= j;
     Int128 remainder{};
     for (; j < 128; ++j) {
       remainder <<= 1;
       if (bits.high_ & topBit) {
         remainder.low_ |= 1;
       }
       bits <<= 1;
       if (remainder >= that) {
         remainder -= that;
       }