[wide-int]

Richard Sandiford rdsandiford@googlemail.com
Sun Dec 1 10:51:00 GMT 2013


At the moment we only use host divisions for precisions <=
HOST_BITS_PER_WIDE_INT.  This patch extends it to any division in which
the inputs fit in HWIs.  The easiest way seemed to be to construct
wide_int_refs for the numbers and reuse wi::fits_*hwi_p.  This also
simplifies some of the other code.

The only tricky thing is that we need to handle HOST_WIDE_INT_MIN / -1
specially for precisions > HOST_BITS_PER_WIDE_INT, since that isn't an
overflow and is the only case where the result needs two HWIs.

The slow path is now only used 7 times for insn-recog.ii, 4 for
cp/parser.ii and not at all for fold-const.ii.

Tested on x86_64-linux-gnu.  OK to install?

Thanks,
Richard


Index: gcc/wide-int.cc
===================================================================
--- gcc/wide-int.cc	2013-11-30 10:30:07.512582970 +0000
+++ gcc/wide-int.cc	2013-12-01 10:48:47.128907474 +0000
@@ -1663,9 +1663,10 @@ divmod_internal_2 (unsigned HOST_HALF_WI
    the division overflowed.  */
 unsigned int
 wi::divmod_internal (HOST_WIDE_INT *quotient, unsigned int *remainder_len,
-		     HOST_WIDE_INT *remainder, const HOST_WIDE_INT *dividend,
+		     HOST_WIDE_INT *remainder,
+		     const HOST_WIDE_INT *dividend_val,
 		     unsigned int dividend_len, unsigned int dividend_prec,
-		     const HOST_WIDE_INT *divisor, unsigned int divisor_len,
+		     const HOST_WIDE_INT *divisor_val, unsigned int divisor_len,
 		     unsigned int divisor_prec, signop sgn,
 		     bool *oflow)
 {
@@ -1680,42 +1681,25 @@ wi::divmod_internal (HOST_WIDE_INT *quot
   unsigned HOST_HALF_WIDE_INT
     b_divisor[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
   unsigned int m, n;
-  HOST_WIDE_INT u0[WIDE_INT_MAX_ELTS];
-  HOST_WIDE_INT u1[WIDE_INT_MAX_ELTS];
   bool dividend_neg = false;
   bool divisor_neg = false;
   bool overflow = false;
+  wide_int neg_dividend, neg_divisor;
 
-  if (divisor[0] == 0 && divisor_len == 1)
+  wide_int_ref dividend = wi::storage_ref (dividend_val, dividend_len,
+					   dividend_prec);
+  wide_int_ref divisor = wi::storage_ref (divisor_val, divisor_len,
+					  divisor_prec);
+  if (divisor == 0)
     overflow = true;
 
-  /* The smallest signed number / -1 causes overflow.  */
+  /* The smallest signed number / -1 causes overflow.  The dividend_len
+     check is for speed rather than correctness.  */
   if (sgn == SIGNED
       && dividend_len == BLOCKS_NEEDED (dividend_prec)
-      && divisor_len == 1)
-    {
-      HOST_WIDE_INT divisor_low = divisor[0];
-      if (divisor_prec < HOST_BITS_PER_WIDE_INT)
-	divisor_low = sext_hwi (divisor_low, divisor_prec);
-      unsigned HOST_WIDE_INT dividend_high = dividend[dividend_len - 1];
-      dividend_high <<= -dividend_prec % HOST_BITS_PER_WIDE_INT;
-      if (divisor_low == -1
-	  && HOST_WIDE_INT (dividend_high) == HOST_WIDE_INT_MIN)
-	{
-	  /* The smallest neg number is 100...00.  The high word was
-	     checked above, now check the rest of the words are zero.  */
-	  unsigned int i;
-	  bool all_zero = true;
-	  for (i = 0; i + 1 < dividend_len; i++)
-	    if (dividend[i] != 0)
-	      {
-		all_zero = false;
-		break;
-	      }
-	  if (all_zero)
-	    overflow = true;
-	}
-    }
+      && divisor == -1
+      && wi::only_sign_bit_p (dividend))
+    overflow = true;
 
   /* If overflow is set, just get out.  There will only be grief by
      continuing.  */
@@ -1737,27 +1721,30 @@ wi::divmod_internal (HOST_WIDE_INT *quot
     *oflow = false;
 
   /* Do it on the host if you can.  */
-  if (dividend_prec <= HOST_BITS_PER_WIDE_INT
-      && divisor_prec <= HOST_BITS_PER_WIDE_INT)
+  if (sgn == SIGNED
+      && wi::fits_shwi_p (dividend)
+      && wi::fits_shwi_p (divisor))
     {
-      if (sgn == SIGNED)
-	{
-	  HOST_WIDE_INT o0 = sext_hwi (dividend[0], dividend_prec);
-	  HOST_WIDE_INT o1 = sext_hwi (divisor[0], divisor_prec);
+      HOST_WIDE_INT o0 = dividend.to_shwi ();
+      HOST_WIDE_INT o1 = divisor.to_shwi ();
 
+      if (o0 == HOST_WIDE_INT_MIN && o1 == -1)
+	{
+	  gcc_checking_assert (dividend_prec > HOST_BITS_PER_WIDE_INT);
 	  if (quotient)
-	    quotient[0] = o0 / o1;
+	    {
+	      quotient[0] = HOST_WIDE_INT_MIN;
+	      quotient[1] = 0;
+	    }
 	  if (remainder)
 	    {
-	      remainder[0] = o0 % o1;
+	      remainder[0] = 0;
 	      *remainder_len = 1;
 	    }
+	  return 2;
 	}
       else
 	{
-	  unsigned HOST_WIDE_INT o0 = zext_hwi (dividend[0], dividend_prec);
-	  unsigned HOST_WIDE_INT o1 = zext_hwi (divisor[0], divisor_prec);
-
 	  if (quotient)
 	    quotient[0] = o0 / o1;
 	  if (remainder)
@@ -1765,8 +1752,24 @@ wi::divmod_internal (HOST_WIDE_INT *quot
 	      remainder[0] = o0 % o1;
 	      *remainder_len = 1;
 	    }
+	  return 1;
 	}
+    }
+
+  if (sgn == UNSIGNED
+      && wi::fits_uhwi_p (dividend)
+      && wi::fits_uhwi_p (divisor))
+    {
+      unsigned HOST_WIDE_INT o0 = dividend.to_uhwi ();
+      unsigned HOST_WIDE_INT o1 = divisor.to_uhwi ();
 
+      if (quotient)
+	quotient[0] = o0 / o1;
+      if (remainder)
+	{
+	  remainder[0] = o0 % o1;
+	  *remainder_len = 1;
+	}
       return 1;
     }
 
@@ -1774,36 +1777,34 @@ wi::divmod_internal (HOST_WIDE_INT *quot
      did.  */
   if (sgn == SIGNED)
     {
-      if (top_bit_of (dividend, dividend_len, dividend_prec))
+      if (wi::neg_p (dividend))
 	{
-	  dividend_len = wi::sub_large (u0, zeros, 1, dividend, dividend_len,
-					dividend_prec, UNSIGNED, 0);
-	  dividend = u0;
+	  neg_dividend = -dividend;
+	  dividend = neg_dividend;
 	  dividend_neg = true;
 	}
-      if (top_bit_of (divisor, divisor_len, divisor_prec))
+      if (wi::neg_p (divisor))
 	{
-	  divisor_len = wi::sub_large (u1, zeros, 1, divisor, divisor_len,
-				       divisor_prec, UNSIGNED, 0);
-	  divisor = u1;
+	  neg_divisor = -divisor;
+	  divisor = neg_divisor;
 	  divisor_neg = true;
 	}
     }
 
-  wi_unpack (b_dividend, (const unsigned HOST_WIDE_INT*)dividend,
-	     dividend_len, dividend_blocks_needed, dividend_prec, sgn);
-  wi_unpack (b_divisor, (const unsigned HOST_WIDE_INT*)divisor,
-	     divisor_len, divisor_blocks_needed, divisor_prec, sgn);
+  wi_unpack (b_dividend, (const unsigned HOST_WIDE_INT *) dividend.get_val (),
+	     dividend.get_len (), dividend_blocks_needed, dividend_prec, sgn);
+  wi_unpack (b_divisor, (const unsigned HOST_WIDE_INT *) divisor.get_val (),
+	     divisor.get_len (), divisor_blocks_needed, divisor_prec, sgn);
 
-  if (top_bit_of (dividend, dividend_len, dividend_prec) && sgn == SIGNED)
+  if (wi::neg_p (dividend, sgn))
     m = dividend_blocks_needed;
   else
-    m = 2 * dividend_len;
+    m = 2 * dividend.get_len ();
 
-  if (top_bit_of (divisor, divisor_len, divisor_prec) && sgn == SIGNED)
+  if (wi::neg_p (divisor, sgn))
     n = divisor_blocks_needed;
   else
-    n = 2 * divisor_len;
+    n = 2 * divisor.get_len ();
 
   /* We need to find the top non zero block of b_divisor.  At most the
      top two blocks are zero.  */
Index: gcc/wide-int.h
===================================================================
--- gcc/wide-int.h	2013-11-30 10:07:06.567433289 +0000
+++ gcc/wide-int.h	2013-11-30 10:51:42.289006762 +0000
@@ -889,6 +889,8 @@ struct wide_int_ref_storage : public wi:
   HOST_WIDE_INT scratch[2];
 
 public:
+  wide_int_ref_storage (const wi::storage_ref &);
+
   template <typename T>
   wide_int_ref_storage (const T &);
 
@@ -896,6 +898,13 @@ struct wide_int_ref_storage : public wi:
   wide_int_ref_storage (const T &, unsigned int);
 };
 
+/* Create a reference from an existing reference.  */
+template <bool SE>
+inline wide_int_ref_storage <SE>::
+wide_int_ref_storage (const wi::storage_ref &x)
+  : storage_ref (x)
+{}
+
 /* Create a reference to integer X in its natural precision.  Note
    that the natural precision is host-dependent for primitive
    types.  */



More information about the Gcc-patches mailing list