This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: patch to canonize unsigned tree-csts


i added the assertion that richard requested and tested this on x86-64.

committed as revision 203602.


On 10/06/2013 05:13 AM, Richard Sandiford wrote:
Kenneth Zadeck <zadeck@naturalbridge.com> writes:
On 10/04/2013 01:00 PM, Richard Sandiford wrote:
I was hoping Richard would weigh in here.  In case not...

Kenneth Zadeck <zadeck@naturalbridge.com> writes:
I was thinking that we should always be able to use the constant as-is
for max_wide_int-based and addr_wide_int-based operations.  The small_prec
again, you can get edge cased to death here.    i think it would work
for max because that really is bigger than anything else, but it is
possible (though unlikely) to have something big converted to an address
by truncation.
But I'd have expected that conversion to be represented by an explicit
CONVERT_EXPR or NOP_EXPR.  It seems wrong to use addr_wide_int directly on
something that isn't bit- or byte-address-sized.  It'd be the C equivalent
of int + long -> int rather than the expected int + long -> long.

Same goes for wide_int.  If we're doing arithmetic at a specific
precision, it seems odd for one of the inputs to be wider and yet
not have an explicit truncation.
you miss the second reason why we needed addr-wide-int.   A large amount
of the places where the addressing arithmetic is done are not "type
safe".    Only the gimple and rtl that is translated from the source
code is really type safe.     In passes like the strength reduction
where they just "grab things from all over", the addr-wide-int or the
max-wide-int are safe haven structures that are guaranteed to be large
enough to not matter.    So what i fear here is something like a very
wide loop counter being grabbed into some address calculation.
It still seems really dangerous to be implicitly truncating a wider type
to addr_wide_int.  It's not something we'd ever do in mainline, because
uses of addr_wide_int are replacing uses of double_int, and double_int
is our current maximum-width representation.

Using addr_wide_int rather than max_wide_int is an optimisation.
IMO part of implementating that optimisation should be to introduce
explicit truncations whenever we try to use addr_wide_int to operate
on inputs than might be wider than addr_wide_int.

So I still think the assert is the way to go.
addr_wide_int is not as much of an optimization as it is documentation
of what you are doing - i.e. this is addressing arithmetic.  My
justification for putting it in was that we wanted a sort of an abstract
type to say that this was not just user math, it was addressing
arithmetic and that the ultimate result is going to be slammed into a
target pointer.

I was only using that as an example to try to indicate that I did not
think that it was wrong if someone did truncate.   In particular, would
you want the assert to be that the value was truncated or that the type
of the value would allow numbers that would be truncated?   I actually
think neither.
I'm arguing for:

     gcc_assert (precision >= xprecision);

in wi::int_traits <const_tree>::decompose.

IIRC one of the reasons for wanting addr_wide_int rather than wide_int
was that we wanted a type that could handle both bit and byte sizes.
And we wanted to be able to convert between bits and bytes seamlessly.
That means that shifting is a valid operation for addr_wide_int.  But if
we also implicitly (and that's the key word) used addr_wide_int
directly on tree constants that are wider than addr_wide_int, and say
shifted the result right, the answer would be different from what you'd
get if you did the shift in max_wide_int.  That seems like new behaviour,
since all address arithmetic is effectively done to maximum precision on
mainline.  It's just that the maximum on mainline is rather small.

If code is looking through casts to see wider-than-addr_wide_int types,
I think it's reasonable for that code to have to explicitly force the
tree to addr_wide_int size, via addr_wide_int::from.  Leaving it implicit
seems too subtle and also means that every caller to wi::int_traits
<const_tree>::decompose does a check that is usually unnecessary.

If a programmer uses a long long on a 32 bit machine for some index
variable and slams that into a pointer, he either knows what he is doing
or has made a mistake.    do you really think that the compiler should ice?
No, I'm saying that passes that operate on addr_wide_ints while "grabbing
trees from all over" (still not sure what that means in practice) should
explicitly mark places where a truncation is deliberately allowed.
Those places then guarantee that the dropped bits wouldn't affect any of
the later calculations, which is something only the pass itself can know.

We already forbid direct assignments like:

    addr_wide_int x = max_wide_int(...);

at compile time, for similar reasons.

Thanks,
Richard

Index: gcc/tree.c
===================================================================
--- gcc/tree.c	(revision 203521)
+++ 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 203521)
+++ 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,48 @@ 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);
+  unsigned int xprecision = get_precision (x);
+
+  gcc_assert (precision >= xprecision);
 
-  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)
+	{
+	  /* 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);
+	    }
+	}
+
+      if (precision < xprecision + HOST_BITS_PER_WIDE_INT)
 	{
-	  /* 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);
+	  len = wi::force_to_size (scratch, val, len, xprecision, precision, UNSIGNED);
+	  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);
     }
 
-  /* 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 203521)
+++ 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;
 }

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]