naruse	2017-02-03 00:54:51 +0900 (Fri, 03 Feb 2017)

  New Revision: 57506

  https://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=57506

  Log:
    Use carry flag to reduce instructions
    
    NOTE:
    (1) Fixnum's LSB is always 1.
        It means you can always run `x - 1` without overflow.
    (2) Of course `z = x + (y-1)` may overflow.
        Now z's LSB is always 1, and the MSB of true result is also 1.
        You can get true result in long as `(1<<63)|(z>>1)`,
        and it equals to `(z<<63)|(z>>1)` == `ror(z)`.
    
    GCC and Clang have __builtin_add_ovewflow:
    * https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html
    * https://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins

  Modified files:
    trunk/configure.in
    trunk/insns.def
    trunk/internal.h
    trunk/numeric.c
Index: numeric.c
===================================================================
--- numeric.c	(revision 57505)
+++ numeric.c	(revision 57506)
@@ -3458,15 +3458,7 @@ static VALUE https://github.com/ruby/ruby/blob/trunk/numeric.c#L3458
 fix_plus(VALUE x, VALUE y)
 {
     if (FIXNUM_P(y)) {
-	long a, b, c;
-	VALUE r;
-
-	a = FIX2LONG(x);
-	b = FIX2LONG(y);
-	c = a + b;
-	r = LONG2NUM(c);
-
-	return r;
+	return rb_fix_plus_fix(x, y);
     }
     else if (RB_TYPE_P(y, T_BIGNUM)) {
 	return rb_big_plus(y, x);
@@ -3513,15 +3505,7 @@ static VALUE https://github.com/ruby/ruby/blob/trunk/numeric.c#L3505
 fix_minus(VALUE x, VALUE y)
 {
     if (FIXNUM_P(y)) {
-	long a, b, c;
-	VALUE r;
-
-	a = FIX2LONG(x);
-	b = FIX2LONG(y);
-	c = a - b;
-	r = LONG2NUM(c);
-
-	return r;
+	return rb_fix_minus_fix(x, y);
     }
     else if (RB_TYPE_P(y, T_BIGNUM)) {
 	x = rb_int2big(FIX2LONG(x));
Index: configure.in
===================================================================
--- configure.in	(revision 57505)
+++ configure.in	(revision 57506)
@@ -2498,6 +2498,9 @@ RUBY_CHECK_BUILTIN_FUNC(__builtin_clzl, https://github.com/ruby/ruby/blob/trunk/configure.in#L2498
 RUBY_CHECK_BUILTIN_FUNC(__builtin_clzll, [__builtin_clzll(0)])
 RUBY_CHECK_BUILTIN_FUNC(__builtin_ctz, [__builtin_ctz(0)])
 RUBY_CHECK_BUILTIN_FUNC(__builtin_ctzll, [__builtin_ctzll(0)])
+RUBY_CHECK_BUILTIN_FUNC(__builtin_add_ovewflow, [__builtin_add_ovewflow(0)])
+RUBY_CHECK_BUILTIN_FUNC(__builtin_sub_ovewflow, [__builtin_sub_ovewflow(0)])
+RUBY_CHECK_BUILTIN_FUNC(__builtin_mul_ovewflow, [__builtin_mul_ovewflow(0)])
 RUBY_CHECK_BUILTIN_FUNC(__builtin_constant_p, [__builtin_constant_p(0)])
 RUBY_CHECK_BUILTIN_FUNC(__builtin_choose_expr, [
     [int x[__extension__(__builtin_choose_expr(1, 1, -1))]];
Index: insns.def
===================================================================
--- insns.def	(revision 57505)
+++ insns.def	(revision 57506)
@@ -1373,16 +1373,7 @@ opt_plus https://github.com/ruby/ruby/blob/trunk/insns.def#L1373
 {
     if (FIXNUM_2_P(recv, obj) &&
 	BASIC_OP_UNREDEFINED_P(BOP_PLUS,INTEGER_REDEFINED_OP_FLAG)) {
-	/* fixnum + fixnum */
-#ifndef LONG_LONG_VALUE
-	VALUE msb = (VALUE)1 << ((sizeof(VALUE) * CHAR_BIT) - 1);
-	val = recv - 1 + obj;
-	if ((~(recv ^ obj) & (recv ^ val)) & msb) {
-	    val = rb_int2big((SIGNED_VALUE)((val>>1) | (recv & msb)));
-	}
-#else
-	val = LONG2NUM(FIX2LONG(recv) + FIX2LONG(obj));
-#endif
+	val = rb_fix_plus_fix(recv, obj);
     }
     else if (FLONUM_2_P(recv, obj) &&
 	     BASIC_OP_UNREDEFINED_P(BOP_PLUS, FLOAT_REDEFINED_OP_FLAG)) {
@@ -1426,12 +1417,7 @@ opt_minus https://github.com/ruby/ruby/blob/trunk/insns.def#L1417
 {
     if (FIXNUM_2_P(recv, obj) &&
 	BASIC_OP_UNREDEFINED_P(BOP_MINUS, INTEGER_REDEFINED_OP_FLAG)) {
-	long a, b, c;
-
-	a = FIX2LONG(recv);
-	b = FIX2LONG(obj);
-	c = a - b;
-	val = LONG2NUM(c);
+	val = rb_fix_minus_fix(recv, obj);
     }
     else if (FLONUM_2_P(recv, obj) &&
 	     BASIC_OP_UNREDEFINED_P(BOP_MINUS, FLOAT_REDEFINED_OP_FLAG)) {
Index: internal.h
===================================================================
--- internal.h	(revision 57505)
+++ internal.h	(revision 57506)
@@ -348,6 +348,53 @@ VALUE rb_int128t2big(int128_t n); https://github.com/ruby/ruby/blob/trunk/internal.h#L348
 
 #define ST2FIX(h) LONG2FIX((long)(h))
 
+static inline unsigned long
+rb_ulong_rotate_right(unsigned long x)
+{
+    return (x >> 1) | (x << (SIZEOF_LONG * CHAR_BIT - 1));
+}
+
+static inline VALUE
+rb_fix_plus_fix(VALUE x, VALUE y)
+{
+#ifdef HAVE_BUILTIN___BUILTIN_ADD_OVERFLOW
+    long lz;
+    /* NOTE
+     * (1) Fixnum's LSB is always 1.
+     *     It means you can always run `x - 1` without overflow.
+     * (2) Of course `z = x + (y-1)` may overflow.
+     *     Now z's LSB is always 1, and the MSB of true result is also 1.
+     *     You can get true result in long as `(1<<63)|(z>>1)`,
+     *     and it equals to `(z<<63)|(z>>1)` == `ror(z)`.
+     */
+    if (__builtin_add_overflow((long)x, (long)y-1, &lz)) {
+	return rb_int2big(rb_ulong_rotate_right((unsigned long)lz));
+    }
+    else {
+	return (VALUE)lz;
+    }
+#else
+    long lz = FIX2LONG(x) + FIX2LONG(y);
+    return LONG2NUM(lz);
+#endif
+}
+
+static inline VALUE
+rb_fix_minus_fix(VALUE x, VALUE y)
+{
+#ifdef HAVE_BUILTIN___BUILTIN_SUB_OVERFLOW
+    long lz;
+    if (__builtin_sub_overflow((long)x, (long)y-1, &lz)) {
+	return rb_int2big(rb_ulong_rotate_right((unsigned long)lz));
+    }
+    else {
+	return (VALUE)lz;
+    }
+#else
+    long lz = FIX2LONG(x) - FIX2LONG(y);
+    return LONG2NUM(lz);
+#endif
+}
 
 /* arguments must be Fixnum */
 static inline VALUE

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/