[Gmp-commit] /var/hg/gmp: __builtin_constant_p optimizations to turn x+0 into...

mercurial at gmplib.org mercurial at gmplib.org
Sun Aug 21 20:10:02 CEST 2011


details:   /var/hg/gmp/rev/c749307472b4
changeset: 14237:c749307472b4
user:      Marc Glisse <marc.glisse at inria.fr>
date:      Sun Aug 21 20:08:38 2011 +0200
description:
__builtin_constant_p optimizations to turn x+0 into x, x*4 into x<<2, etc, all done in the C++ layer.
Also rewrote the addition of rational and integer which always did a mpq_set first.

diffstat:

 ChangeLog           |   14 +
 gmpxx.h             |  473 +++++++++++++++++++++++++++++++++------------------
 tests/cxx/t-ops2.cc |    3 +
 3 files changed, 320 insertions(+), 170 deletions(-)

diffs (truncated from 751 to 300 lines):

diff -r 617c3cd439d2 -r c749307472b4 ChangeLog
--- a/ChangeLog	Thu Aug 18 13:28:48 2011 +0200
+++ b/ChangeLog	Sun Aug 21 20:08:38 2011 +0200
@@ -1,3 +1,17 @@
+2011-08-21  Marc Glisse  <marc.glisse at inria.fr>
+
+	* tests/cxx/t-ops2.cc: check mul-div by 2.
+
+	* gmpxx.h (__GMPXX_CONSTANT): New macro (__builtin_constant_p).
+	(__gmp_binary_lshift): Move before multiplication. Optimize x << 0.
+	(__gmp_binary_rshift): Move before division. Optimize x >> 0.
+	(__gmp_binary_plus): Optimize x + 0. Rewrite rational + integer.
+	(__gmp_binary_minus): Optimize x - 0 and 0 - x.
+	Rewrite rational - integer.
+	(__gmp_binary_multiplies): Optimize x * 2^n.
+	(__gmp_binary_divides): Optimize x / 2^n.
+	(__gmp_binary_*): Deduplicate code for symmetric operations.
+
 2011-08-18  Torbjorn Granlund  <tege at gmplib.org>
 
 	* printf/doprntf.c (__gmp_doprnt_mpf): For DOPRNT_CONV_FIXED, ask for
diff -r 617c3cd439d2 -r c749307472b4 gmpxx.h
--- a/gmpxx.h	Thu Aug 18 13:28:48 2011 +0200
+++ b/gmpxx.h	Sun Aug 21 20:08:38 2011 +0200
@@ -40,6 +40,13 @@
 #include <cfloat>
 #include <gmp.h>
 
+// wrapper for gcc's __builtin_constant_p
+#if defined (__GNUC__) && __GNUC__ >= 2
+#define __GMPXX_CONSTANT(X) __builtin_constant_p(X)
+#else
+#define __GMPXX_CONSTANT(X) false
+#endif
+
 // Max allocations for plain types when converted to mpz_t
 #define __GMPZ_DBL_LIMBS (2 + DBL_MAX_EXP / GMP_NUMB_BITS)
 
@@ -139,51 +146,59 @@
   { mpz_add(z, w, v); }
 
   static void eval(mpz_ptr z, mpz_srcptr w, unsigned long int l)
-  { mpz_add_ui(z, w, l); }
+  {
+    // Ideally, those checks should happen earlier so that the tree
+    // generated for a+0+b would just be sum(a,b).
+    if (__GMPXX_CONSTANT(l) && l == 0)
+    {
+      if (z != w) mpz_set(z, w);
+    }
+    else
+      mpz_add_ui(z, w, l);
+  }
   static void eval(mpz_ptr z, unsigned long int l, mpz_srcptr w)
-  { mpz_add_ui(z, w, l); }
+  { eval(z, w, l); }
   static void eval(mpz_ptr z, mpz_srcptr w, signed long int l)
   {
     if (l >= 0)
-      mpz_add_ui(z, w, l);
+      eval(z, w, static_cast<unsigned long>(l));
     else
       mpz_sub_ui(z, w, -l);
   }
   static void eval(mpz_ptr z, signed long int l, mpz_srcptr w)
-  {
-    if (l >= 0)
-      mpz_add_ui(z, w, l);
-    else
-      mpz_sub_ui(z, w, -l);
-  }
+  { eval(z, w, l); }
   static void eval(mpz_ptr z, mpz_srcptr w, double d)
   {  __GMPXX_TMPZ_D;    mpz_add (z, w, temp); }
   static void eval(mpz_ptr z, double d, mpz_srcptr w)
-  {  __GMPXX_TMPZ_D;    mpz_add (z, temp, w); }
+  { eval(z, w, d); }
 
   static void eval(mpq_ptr q, mpq_srcptr r, mpq_srcptr s)
   { mpq_add(q, r, s); }
 
   static void eval(mpq_ptr q, mpq_srcptr r, unsigned long int l)
-  { mpq_set(q, r); mpz_addmul_ui(mpq_numref(q), mpq_denref(q), l); }
+  {
+    if (__GMPXX_CONSTANT(l) && l == 0)
+    {
+      if (q != r) mpq_set(q, r);
+    }
+    else
+    {
+      if (q == r)
+        mpz_addmul_ui(mpq_numref(q), mpq_denref(q), l);
+      else
+      {
+        mpz_mul_ui(mpq_numref(q), mpq_denref(r), l);
+        mpz_add(mpq_numref(q), mpq_numref(q), mpq_numref(r));
+        mpz_set(mpq_denref(q), mpq_denref(r));
+      }
+    }
+  }
   static void eval(mpq_ptr q, unsigned long int l, mpq_srcptr r)
-  { mpq_set(q, r); mpz_addmul_ui(mpq_numref(q), mpq_denref(q), l); }
-  static void eval(mpq_ptr q, mpq_srcptr r, signed long int l)
-  {
-    mpq_set(q, r);
-    if (l >= 0)
-      mpz_addmul_ui(mpq_numref(q), mpq_denref(q), l);
-    else
-      mpz_submul_ui(mpq_numref(q), mpq_denref(q), -l);
-  }
+  { eval(q, r, l); }
+  static inline void eval(mpq_ptr q, mpq_srcptr r, signed long int l);
+  // defined after __gmp_binary_minus
   static void eval(mpq_ptr q, signed long int l, mpq_srcptr r)
-  {
-    mpq_set(q, r);
-    if (l >= 0)
-      mpz_addmul_ui(mpq_numref(q), mpq_denref(q), l);
-    else
-      mpz_submul_ui(mpq_numref(q), mpq_denref(q), -l);
-  }
+  { eval(q, r, l); }
   static void eval(mpq_ptr q, mpq_srcptr r, double d)
   {
     mpq_t temp;
@@ -193,18 +208,21 @@
     mpq_clear(temp);
   }
   static void eval(mpq_ptr q, double d, mpq_srcptr r)
+  { eval(q, r, d); }
+
+  static void eval(mpq_ptr q, mpq_srcptr r, mpz_srcptr z)
   {
-    mpq_t temp;
-    mpq_init(temp);
-    mpq_set_d(temp, d);
-    mpq_add(q, temp, r);
-    mpq_clear(temp);
+    if (q == r)
+      mpz_addmul(mpq_numref(q), mpq_denref(q), z);
+    else
+    {
+      mpz_mul(mpq_numref(q), mpq_denref(r), z);
+      mpz_add(mpq_numref(q), mpq_numref(q), mpq_numref(r));
+      mpz_set(mpq_denref(q), mpq_denref(r));
+    }
   }
-
-  static void eval(mpq_ptr q, mpq_srcptr r, mpz_srcptr z)
-  { mpq_set(q, r); mpz_addmul(mpq_numref(q), mpq_denref(q), z); }
   static void eval(mpq_ptr q, mpz_srcptr z, mpq_srcptr r)
-  { mpq_set(q, r); mpz_addmul(mpq_numref(q), mpq_denref(q), z); }
+  { eval(q, r, z); }
 
   static void eval(mpf_ptr f, mpf_srcptr g, mpf_srcptr h)
   { mpf_add(f, g, h); }
@@ -221,12 +239,7 @@
       mpf_sub_ui(f, g, -l);
   }
   static void eval(mpf_ptr f, signed long int l, mpf_srcptr g)
-  {
-    if (l >= 0)
-      mpf_add_ui(f, g, l);
-    else
-      mpf_sub_ui(f, g, -l);
-  }
+  { eval(f, g, l); }
   static void eval(mpf_ptr f, mpf_srcptr g, double d)
   {
     mpf_t temp;
@@ -236,13 +249,7 @@
     mpf_clear(temp);
   }
   static void eval(mpf_ptr f, double d, mpf_srcptr g)
-  {
-    mpf_t temp;
-    mpf_init2(temp, 8*sizeof(double));
-    mpf_set_d(temp, d);
-    mpf_add(f, temp, g);
-    mpf_clear(temp);
-  }
+  { eval(f, g, d); }
 };
 
 struct __gmp_binary_minus
@@ -251,20 +258,34 @@
   { mpz_sub(z, w, v); }
 
   static void eval(mpz_ptr z, mpz_srcptr w, unsigned long int l)
-  { mpz_sub_ui(z, w, l); }
+  {
+    if (__GMPXX_CONSTANT(l) && l == 0)
+    {
+      if (z != w) mpz_set(z, w);
+    }
+    else
+      mpz_sub_ui(z, w, l);
+  }
   static void eval(mpz_ptr z, unsigned long int l, mpz_srcptr w)
-  { mpz_ui_sub(z, l, w); }
+  {
+    if (__GMPXX_CONSTANT(l) && l == 0)
+    {
+      mpz_neg(z, w);
+    }
+    else
+      mpz_ui_sub(z, l, w);
+  }
   static void eval(mpz_ptr z, mpz_srcptr w, signed long int l)
   {
     if (l >= 0)
-      mpz_sub_ui(z, w, l);
+      eval(z, w, static_cast<unsigned long>(l));
     else
       mpz_add_ui(z, w, -l);
   }
   static void eval(mpz_ptr z, signed long int l, mpz_srcptr w)
   {
     if (l >= 0)
-      mpz_ui_sub(z, l, w);
+      eval(z, static_cast<unsigned long>(l), w);
     else
       {
         mpz_add_ui(z, w, -l);
@@ -280,25 +301,34 @@
   { mpq_sub(q, r, s); }
 
   static void eval(mpq_ptr q, mpq_srcptr r, unsigned long int l)
-  { mpq_set(q, r); mpz_submul_ui(mpq_numref(q), mpq_denref(q), l); }
+  {
+    if (__GMPXX_CONSTANT(l) && l == 0)
+    {
+      if (q != r) mpq_set(q, r);
+    }
+    else
+    {
+      if (q == r)
+        mpz_submul_ui(mpq_numref(q), mpq_denref(q), l);
+      else
+      {
+        mpz_mul_ui(mpq_numref(q), mpq_denref(r), l);
+        mpz_sub(mpq_numref(q), mpq_numref(r), mpq_numref(q));
+        mpz_set(mpq_denref(q), mpq_denref(r));
+      }
+    }
+  }
   static void eval(mpq_ptr q, unsigned long int l, mpq_srcptr r)
-  { mpq_neg(q, r); mpz_addmul_ui(mpq_numref(q), mpq_denref(q), l); }
+  { eval(q, r, l); mpq_neg(q, q); }
   static void eval(mpq_ptr q, mpq_srcptr r, signed long int l)
   {
-    mpq_set(q, r);
     if (l >= 0)
-      mpz_submul_ui(mpq_numref(q), mpq_denref(q), l);
+      eval(q, r, static_cast<unsigned long>(l));
     else
-      mpz_addmul_ui(mpq_numref(q), mpq_denref(q), -l);
+      __gmp_binary_plus::eval(q, r, static_cast<unsigned long>(-l));
   }
   static void eval(mpq_ptr q, signed long int l, mpq_srcptr r)
-  {
-    mpq_neg(q, r);
-    if (l >= 0)
-      mpz_addmul_ui(mpq_numref(q), mpq_denref(q), l);
-    else
-      mpz_submul_ui(mpq_numref(q), mpq_denref(q), -l);
-  }
+  { eval(q, r, l); mpq_neg(q, q); }
   static void eval(mpq_ptr q, mpq_srcptr r, double d)
   {
     mpq_t temp;
@@ -317,9 +347,18 @@
   }
 
   static void eval(mpq_ptr q, mpq_srcptr r, mpz_srcptr z)
-  { mpq_set(q, r); mpz_submul(mpq_numref(q), mpq_denref(q), z); }
+  {
+    if (q == r)
+      mpz_submul(mpq_numref(q), mpq_denref(q), z);
+    else
+    {
+      mpz_mul(mpq_numref(q), mpq_denref(r), z);
+      mpz_sub(mpq_numref(q), mpq_numref(r), mpq_numref(q));
+      mpz_set(mpq_denref(q), mpq_denref(r));
+    }
+  }
   static void eval(mpq_ptr q, mpz_srcptr z, mpq_srcptr r)
-  { mpq_neg(q, r); mpz_addmul(mpq_numref(q), mpq_denref(q), z); }
+  { eval(q, r, z); mpq_neg(q, q); }
 
   static void eval(mpf_ptr f, mpf_srcptr g, mpf_srcptr h)
   { mpf_sub(f, g, h); }
@@ -361,35 +400,158 @@
   }
 };
 
+// defined here so it can reference __gmp_binary_minus
+inline void
+__gmp_binary_plus::eval(mpq_ptr q, mpq_srcptr r, signed long int l)
+{


More information about the gmp-commit mailing list