Re: patch to canonize small wide-ints.

[Kenneth Zadeck <zadeck at naturalbridge dot com>]

Richard and others,

This patch changes the way that unsigned trees are canonicalized. As 
with the last patch, I think that this patch is not that much of a step 
forward.   While it is still true that the signed tree-csts match the 
representation of wide-ints, unsigned tree-csts do not and require 
conversion on the way in and out, as before.   The only thing is that 
the conversion is different.   Again, if Richard wants it in then i will 
commit it.

Kenny

Index: gcc/tree.c
===================================================================
--- gcc/tree.c	(revision 203039)
+++ gcc/tree.c	(working copy)
@@ -1187,10 +1187,10 @@ wide_int_to_tree (tree type, const wide_
   tree t;
   int ix = -1;
   int limit = 0;
-  int i;
+  unsigned int i;
 
   gcc_assert (type);
-  int prec = TYPE_PRECISION (type);
+  unsigned int prec = TYPE_PRECISION (type);
   signop sgn = TYPE_SIGN (type);
 
   /* Verify that everything is canonical.  */
@@ -1204,11 +1204,11 @@ wide_int_to_tree (tree type, const wide_
     }
 
   wide_int cst = wide_int::from (pcst, prec, sgn);
-  int len = int (cst.get_len ());
-  int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);
+  unsigned int len = int (cst.get_len ());
+  unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);
   bool recanonize = sgn == UNSIGNED
-    && (prec + HOST_BITS_PER_WIDE_INT - 1) / HOST_BITS_PER_WIDE_INT == len
-    && small_prec;
+    && small_prec
+    && (prec + HOST_BITS_PER_WIDE_INT - 1) / HOST_BITS_PER_WIDE_INT == len;
 
   switch (TREE_CODE (type))
     {
@@ -1235,7 +1235,7 @@ wide_int_to_tree (tree type, const wide_
 
     case INTEGER_TYPE:
     case OFFSET_TYPE:
-      if (TYPE_UNSIGNED (type))
+      if (TYPE_SIGN (type) == UNSIGNED)
 	{
 	  /* Cache 0..N */
 	  limit = INTEGER_SHARE_LIMIT;
@@ -1294,7 +1294,7 @@ wide_int_to_tree (tree type, const wide_
 	     must be careful here because tree-csts and wide-ints are
 	     not canonicalized in the same way.  */
 	  gcc_assert (TREE_TYPE (t) == type);
-	  gcc_assert (TREE_INT_CST_NUNITS (t) == len);
+	  gcc_assert (TREE_INT_CST_NUNITS (t) == (int)len);
 	  if (recanonize)
 	    {
 	      len--;
@@ -1321,7 +1321,10 @@ wide_int_to_tree (tree type, const wide_
 	  TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
 	}
     }
-  else if (cst.get_len () == 1)
+  else if (cst.get_len () == 1
+	   && (TYPE_SIGN (type) == SIGNED
+	       || recanonize
+	       || cst.elt (0) >= 0))
     {
       /* 99.99% of all int csts will fit in a single HWI.  Do that one
 	 efficiently.  */
@@ -1351,14 +1354,29 @@ wide_int_to_tree (tree type, const wide_
 	 for the gc to take care of.  There will not be enough of them
 	 to worry about.  */
       void **slot;
-      tree nt = make_int_cst (len);
-      TREE_INT_CST_NUNITS (nt) = len;
+      tree nt;
+      if (!recanonize
+	  && TYPE_SIGN (type) == UNSIGNED 
+	  && cst.elt (len - 1) < 0)
+	{
+	  unsigned int blocks_needed 
+	    = (prec + HOST_BITS_PER_WIDE_INT - 1) / HOST_BITS_PER_WIDE_INT;
+
+	  nt = make_int_cst (blocks_needed + 1);
+	  for (i = len; i < blocks_needed; i++)
+	    TREE_INT_CST_ELT (nt, i) = (HOST_WIDE_INT)-1;
+    
+	  TREE_INT_CST_ELT (nt, blocks_needed) = 0;
+	}
+      else
+	nt = make_int_cst (len);
       if (recanonize)
 	{
 	  len--;
 	  TREE_INT_CST_ELT (nt, len) = zext_hwi (cst.elt (len), small_prec);
 	}
-      for (int i = 0; i < len; i++)
+	
+      for (i = 0; i < len; i++)
 	TREE_INT_CST_ELT (nt, i) = cst.elt (i);
       TREE_TYPE (nt) = type;
 
@@ -10556,7 +10574,8 @@ widest_int_cst_value (const_tree x)
 
 #if HOST_BITS_PER_WIDEST_INT > HOST_BITS_PER_WIDE_INT
   gcc_assert (HOST_BITS_PER_WIDEST_INT >= HOST_BITS_PER_DOUBLE_INT);
-  gcc_assert (TREE_INT_CST_NUNITS (x) <= 2);
+  gcc_assert (TREE_INT_CST_NUNITS (x) <= 2
+	      || (TREE_INT_CST_NUNITS (x) == 3 && TREE_INT_CST_ELT (x, 2) == 0));
   
   if (TREE_INT_CST_NUNITS (x) == 1)
     val = ((HOST_WIDEST_INT)val << HOST_BITS_PER_WIDE_INT) >> HOST_BITS_PER_WIDE_INT;
@@ -10565,7 +10584,8 @@ widest_int_cst_value (const_tree x)
 	    << HOST_BITS_PER_WIDE_INT);
 #else
   /* Make sure the sign-extended value will fit in a HOST_WIDE_INT.  */
-  gcc_assert (TREE_INT_CST_NUNITS (x) == 1);
+  gcc_assert (TREE_INT_CST_NUNITS (x) == 1
+	      || (TREE_INT_CST_NUNITS (x) == 2 && TREE_INT_CST_ELT (x, 1) == 0));
 #endif
 
   if (bits < HOST_BITS_PER_WIDEST_INT)
Index: gcc/tree.h
===================================================================
--- gcc/tree.h	(revision 203039)
+++ gcc/tree.h	(working copy)
@@ -3050,7 +3050,8 @@ cst_fits_shwi_p (const_tree x)
   if (TREE_CODE (x) != INTEGER_CST)
     return false;
 
-  return TREE_INT_CST_NUNITS (x) == 1;
+  return TREE_INT_CST_NUNITS (x) == 1
+    || (TREE_INT_CST_NUNITS (x) == 2 && TREE_INT_CST_ELT (x, 1) == 0);
 }
 
 /* Checks that X is integer constant that can be expressed in signed
@@ -3093,7 +3094,7 @@ tree_fits_uhwi_p (const_tree cst)
       /* For numbers of unsigned type that are longer than a HWI, if
 	 the top bit of the bottom word is set, and there is not
 	 another element, then this is too large to fit in a single
-	 hwi.  */
+	 hwi.  For signed numbers, negative values are not allowed. */
       if (TREE_INT_CST_ELT (cst, 0) >= 0)
 	return true;
     }
@@ -5172,39 +5173,43 @@ wi::int_traits <const_tree>::get_precisi
   return TYPE_PRECISION (TREE_TYPE (tcst));
 }
 
-/* Convert the tree_cst X into a wide_int.  */
+/* Convert the tree_cst X into a wide_int of PRECISION.  */
 inline wi::storage_ref
 wi::int_traits <const_tree>::decompose (HOST_WIDE_INT *scratch,
 					unsigned int precision, const_tree x)
 {
-  unsigned int xprecision = get_precision (x);
   unsigned int len = TREE_INT_CST_NUNITS (x);
   const HOST_WIDE_INT *val = (const HOST_WIDE_INT *) &TREE_INT_CST_ELT (x, 0);
   unsigned int max_len = ((precision + HOST_BITS_PER_WIDE_INT - 1)
 			  / HOST_BITS_PER_WIDE_INT);
-  /* Truncate the constant if necessary.  */
-  if (len > max_len)
-    return wi::storage_ref (val, max_len, precision);
 
-  if (precision <= xprecision)
+  /* Got to be careful of precision 0 values.  */
+  if (precision)
+    len = MIN (len, max_len);
+  if (TYPE_SIGN (TREE_TYPE (x)) == UNSIGNED)
     {
-      if (precision < HOST_BITS_PER_WIDE_INT 
-	  && TYPE_SIGN (TREE_TYPE (x)) == UNSIGNED)
+      unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
+      if (small_prec)
 	{
-	  /* The rep of wide-int is signed, so if the value comes from
-	     an unsigned int_cst, we have to sign extend it to make it
-	     correct.  */
-	  scratch[0] = sext_hwi (val[0], precision);
-	  return wi::storage_ref (scratch, 1, precision);
+	  /* We have to futz with this because the canonization for
+	     short unsigned numbers in wide-int is different from the
+	     canonized short unsigned numbers in the tree-cst.  */
+	  if (len == max_len) 
+	    {
+	      for (unsigned int i = 0; i < len - 1; i++)
+		scratch[i] = val[i];
+	      scratch[len - 1] = sext_hwi (val[len - 1], precision);
+	      return wi::storage_ref (scratch, len, precision);
+	    }
 	}
-      /* Otherwise we can use the constant as-is when not extending.  */
-      return wi::storage_ref (val, len, precision);
+
+      unsigned int xprecision = get_precision (x);
+      len = wi::force_to_size (scratch, val, len, xprecision, precision, UNSIGNED);
+      return wi::storage_ref (scratch, len, precision);
     }
 
-  /* Widen the constant according to its sign.  */
-  len = wi::force_to_size (scratch, val, len, xprecision, precision,
-			   TYPE_SIGN (TREE_TYPE (x)));
-  return wi::storage_ref (scratch, len, precision);
+  /* Signed and the rest of the unsigned cases are easy.  */
+  return wi::storage_ref (val, len, precision);
 }
 
 namespace wi
Index: gcc/wide-int.cc
===================================================================
--- gcc/wide-int.cc	(revision 203039)
+++ gcc/wide-int.cc	(working copy)
@@ -342,9 +342,7 @@ wi::force_to_size (HOST_WIDE_INT *val, c
 	    }
 	}
     }
-  else if (precision < xprecision)
-    /* Contracting.  */
-    len = canonize (val, len, precision);
+  len = canonize (val, len, precision);
 
   return len;
 }