Patchwork Make VRP optimize useless conversions

login
register
mail settings
Submitter Richard Guenther
Date July 11, 2011, 12:12 p.m.
Message ID <alpine.LNX.2.00.1107111412220.810@zhemvz.fhfr.qr>
Download mbox | patch
Permalink /patch/104200/
State New
Headers show

Comments

Richard Guenther - July 11, 2011, 12:12 p.m.
On Fri, 8 Jul 2011, Richard Guenther wrote:

> On Fri, 8 Jul 2011, Michael Matz wrote:
> 
> > Hi,
> > 
> > On Fri, 8 Jul 2011, Richard Guenther wrote:
> > 
> > > It should be indeed safe with the current handling of conversions, but 
> > > better be safe.  So, like the following?
> > 
> > No.  The point is that you can't compare the bounds that VRP computes with 
> > each other when the outcome affects correctness.  Think about a very 
> > trivial and stupid VRP, that assigns the range [WIDEST_INT_MIN .. 
> > WIDEST_UINT_MAX] to each and every SSA name without looking at types and 
> > operations at all (assuming that this reflects the largest int type on the 
> > target).  It's useless but correct.  Of course we wouldn't implement such 
> > useless range discovery, but similar situations can arise when some VRP 
> > algorithms give up for certain reasons, or computation of tight bounds 
> > merely isn't implemented for some operations.
> > 
> > Your routines need to work also in the presence of such imprecise ranges.
> > 
> > Hence, the check that the intermediate conversion is useless needs to take 
> > into account the input value range (that's conservatively correct), and 
> > the precision and signedness of the target type (if it can represent all 
> > value of the input range the conversion was useless).  It must not look at 
> > the suspected value range of the destination, precisely because it is 
> > conservative only.
> 
> Ok, indeed conservative is different for what VRP does and for what
> a transformation must assess.  So the following patch makes
> a conservative attempt at checking the transformation (which of
> course non-surprisingly matches what the VRP part does).
> 
> So, more like the following?

The following actually works.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Can you double-check it?

Thanks,
Richard.

2011-07-11  Richard Guenther  <rguenther@suse.de>

	* tree-vrp.c (simplify_conversion_using_ranges): Manually
	translate the source value-range through the conversion chain.
Michael Matz - July 11, 2011, 12:46 p.m.
Hi,

On Mon, 11 Jul 2011, Richard Guenther wrote:

> The following actually works.
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
> 
> Can you double-check it?

Seems sensible.  Given this:

  short s;
  int i;
  for (s = 0; s <= 127; s++)
    i += (signed char)(unsigned char)s;
  return i;

(or similar), does it remove the conversions to signed and unsigned char 
now?  And does it _not_ remove them if the upper bound is 128, or the 
lower bound is -1 ?

Similar (now with extensions):
  signed char c;
  unsigned u;
  for (c = 1; c < 127; c++)
    u += (unsigned)(int)c;

The conversion to int is not necessary; but it is when the lower bound 
is -1.


Ciao,
Michael.
H.J. Lu - Aug. 12, 2011, 11:47 p.m.
On Mon, Jul 11, 2011 at 5:12 AM, Richard Guenther <rguenther@suse.de> wrote:
> On Fri, 8 Jul 2011, Richard Guenther wrote:
>
>> On Fri, 8 Jul 2011, Michael Matz wrote:
>>
>> > Hi,
>> >
>> > On Fri, 8 Jul 2011, Richard Guenther wrote:
>> >
>> > > It should be indeed safe with the current handling of conversions, but
>> > > better be safe.  So, like the following?
>> >
>> > No.  The point is that you can't compare the bounds that VRP computes with
>> > each other when the outcome affects correctness.  Think about a very
>> > trivial and stupid VRP, that assigns the range [WIDEST_INT_MIN ..
>> > WIDEST_UINT_MAX] to each and every SSA name without looking at types and
>> > operations at all (assuming that this reflects the largest int type on the
>> > target).  It's useless but correct.  Of course we wouldn't implement such
>> > useless range discovery, but similar situations can arise when some VRP
>> > algorithms give up for certain reasons, or computation of tight bounds
>> > merely isn't implemented for some operations.
>> >
>> > Your routines need to work also in the presence of such imprecise ranges.
>> >
>> > Hence, the check that the intermediate conversion is useless needs to take
>> > into account the input value range (that's conservatively correct), and
>> > the precision and signedness of the target type (if it can represent all
>> > value of the input range the conversion was useless).  It must not look at
>> > the suspected value range of the destination, precisely because it is
>> > conservative only.
>>
>> Ok, indeed conservative is different for what VRP does and for what
>> a transformation must assess.  So the following patch makes
>> a conservative attempt at checking the transformation (which of
>> course non-surprisingly matches what the VRP part does).
>>
>> So, more like the following?
>
> The following actually works.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>
> Can you double-check it?
>
> Thanks,
> Richard.
>
> 2011-07-11  Richard Guenther  <rguenther@suse.de>
>
>        * tree-vrp.c (simplify_conversion_using_ranges): Manually
>        translate the source value-range through the conversion chain.
>

This may have caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50066

Patch

Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 176030)
+++ gcc/tree-vrp.c	(working copy)
@@ -7347,30 +7347,55 @@  simplify_switch_using_ranges (gimple stm
 static bool
 simplify_conversion_using_ranges (gimple stmt)
 {
-  tree rhs1 = gimple_assign_rhs1 (stmt);
-  gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
-  value_range_t *final, *inner;
+  tree innerop, middleop, finaltype;
+  gimple def_stmt;
+  value_range_t *innervr;
+  double_int innermin, innermax, middlemin, middlemax;
 
-  /* Obtain final and inner value-ranges for a conversion
-     sequence (final-type)(intermediate-type)inner-type.  */
-  final = get_value_range (gimple_assign_lhs (stmt));
-  if (final->type != VR_RANGE)
-    return false;
+  finaltype = TREE_TYPE (gimple_assign_lhs (stmt));
+  middleop = gimple_assign_rhs1 (stmt);
+  def_stmt = SSA_NAME_DEF_STMT (middleop);
   if (!is_gimple_assign (def_stmt)
       || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
     return false;
-  rhs1 = gimple_assign_rhs1 (def_stmt);
-  if (TREE_CODE (rhs1) != SSA_NAME)
+  innerop = gimple_assign_rhs1 (def_stmt);
+  if (TREE_CODE (innerop) != SSA_NAME)
     return false;
-  inner = get_value_range (rhs1);
-  if (inner->type != VR_RANGE)
+
+  /* Get the value-range of the inner operand.  */
+  innervr = get_value_range (innerop);
+  if (innervr->type != VR_RANGE
+      || TREE_CODE (innervr->min) != INTEGER_CST
+      || TREE_CODE (innervr->max) != INTEGER_CST)
     return false;
-  /* If the value-range is preserved by the conversion sequence strip
-     the intermediate conversion.  */
-  if (!tree_int_cst_equal (final->min, inner->min)
-      || !tree_int_cst_equal (final->max, inner->max))
+
+  /* Simulate the conversion chain to check if the result is equal if
+     the middle conversion is removed.  */
+  innermin = tree_to_double_int (innervr->min);
+  innermax = tree_to_double_int (innervr->max);
+  middlemin = double_int_ext (innermin, TYPE_PRECISION (TREE_TYPE (middleop)),
+			      TYPE_UNSIGNED (TREE_TYPE (middleop)));
+  middlemax = double_int_ext (innermax, TYPE_PRECISION (TREE_TYPE (middleop)),
+			      TYPE_UNSIGNED (TREE_TYPE (middleop)));
+  /* If the middle values do not represent a proper range fail.  */
+  if (double_int_cmp (middlemin, middlemax,
+		      TYPE_UNSIGNED (TREE_TYPE (middleop))) > 0)
     return false;
-  gimple_assign_set_rhs1 (stmt, rhs1);
+  if (!double_int_equal_p (double_int_ext (middlemin,
+					   TYPE_PRECISION (finaltype),
+					   TYPE_UNSIGNED (finaltype)),
+			   double_int_ext (innermin,
+					   TYPE_PRECISION (finaltype),
+					   TYPE_UNSIGNED (finaltype)))
+      || !double_int_equal_p (double_int_ext (middlemax,
+					      TYPE_PRECISION (finaltype),
+					      TYPE_UNSIGNED (finaltype)),
+			      double_int_ext (innermax,
+					      TYPE_PRECISION (finaltype),
+					      TYPE_UNSIGNED (finaltype))))
+    return false;
+
+  gimple_assign_set_rhs1 (stmt, innerop);
   update_stmt (stmt);
   return true;
 }