diff mbox

[RFC] Check number of uses in simplify_cond_using_ranges().

Message ID 20161110205239.GA9225@linux.vnet.ibm.com
State New
Headers show

Commit Message

Dominik Vogt Nov. 10, 2016, 8:52 p.m. UTC 
On Wed, Nov 09, 2016 at 03:46:38PM +0100, Richard Biener wrote:
> On Wed, Nov 9, 2016 at 3:30 PM, Dominik Vogt <vogt@linux.vnet.ibm.com> wrote:
> > Something like the attached patch?  Robin and me have spent quite
> > some time to figure out the new pattern.  Two questions:
> >
> > 1) In the match expression you cannot just use SSA_NAME@0 because
> >    then the "case SSA_NAME:" is added to a switch for another
> >    pattern that already has that label.  Thus we made that "proxy"
> >    predicate "ssa_name_p" that forces the code for the new pattern
> >    out of the old switch and into a separate code block.  We
> >    couldn't figure out whether this joining of case labels is a
> >    feature in the matching language.  So, is this the right way to
> >    deal with the conflicting labels?
> 
> No, just do not match SSA_NAME.  And instead of
> 
> +  (with { gimple *def_stmt = SSA_NAME_DEF_STMT (@0); }
> +   (if (is_gimple_assign (def_stmt)
> +       && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
> 
> you instead want to change the pattern to
> 
> (simpify
>   (cmp (convert @0) INTEGER_CST@1)
> 
> @0 will then be your innerop
> 
> note that you can't use get_value_range but you have to use the
> get_range_info interface instead.  I suppose a helper function
> somewhere that computes whether an expression fits a type
> would be helpful (see expr_not_equal_to for sth related,
> thus expr_fits_type_p (@0, TREE_TYPE (@1)))

All right, I think we got that (new patch attached).

> Likewise the overflow_infinity checks do not translate to match.pd
> (or rahter the range info you get).

Can you give us another hint here, please?  The overflow check
should probably go into expr_fits_type_p, but with only the min
and max values from get_range_info, how can the overflow
TREE_OVERFLOW_P flag be retrieved from @1, to duplicate the logic
from is_{nega,posi}tive_overflow_infinity?  Is it availably
somewhere, or is it necessary to somehow re-calculate it from the
expression?

(This is really necessary so that cases like this don't start
folding with the patch:

--
signed char foo3uu (unsigned char a) 
{ 
  unsigned char d; 
  unsigned long un; 
 
  d = (a & 63) + 200; 
  un = d; 
  if (un >= 12) 
    ubar(un); 
 
  return d; 
}
--

)

Ciao

Dominik ^_^  ^_^

Comments

Marc Glisse Nov. 10, 2016, 10:53 p.m. UTC | #1 
On Thu, 10 Nov 2016, Dominik Vogt wrote:

> On Wed, Nov 09, 2016 at 03:46:38PM +0100, Richard Biener wrote:
>> On Wed, Nov 9, 2016 at 3:30 PM, Dominik Vogt <vogt@linux.vnet.ibm.com> wrote:
>>> Something like the attached patch?  Robin and me have spent quite
>>> some time to figure out the new pattern.  Two questions:
>>>
>>> 1) In the match expression you cannot just use SSA_NAME@0 because
>>>    then the "case SSA_NAME:" is added to a switch for another
>>>    pattern that already has that label.  Thus we made that "proxy"
>>>    predicate "ssa_name_p" that forces the code for the new pattern
>>>    out of the old switch and into a separate code block.  We
>>>    couldn't figure out whether this joining of case labels is a
>>>    feature in the matching language.  So, is this the right way to
>>>    deal with the conflicting labels?
>>
>> No, just do not match SSA_NAME.  And instead of
>>
>> +  (with { gimple *def_stmt = SSA_NAME_DEF_STMT (@0); }
>> +   (if (is_gimple_assign (def_stmt)
>> +       && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
>>
>> you instead want to change the pattern to
>>
>> (simpify
>>   (cmp (convert @0) INTEGER_CST@1)
>>
>> @0 will then be your innerop
>>
>> note that you can't use get_value_range but you have to use the
>> get_range_info interface instead.  I suppose a helper function
>> somewhere that computes whether an expression fits a type
>> would be helpful (see expr_not_equal_to for sth related,
>> thus expr_fits_type_p (@0, TREE_TYPE (@1)))
>
> All right, I think we got that (new patch attached).
>
>> Likewise the overflow_infinity checks do not translate to match.pd
>> (or rahter the range info you get).
>
> Can you give us another hint here, please?  The overflow check
> should probably go into expr_fits_type_p, but with only the min
> and max values from get_range_info, how can the overflow
> TREE_OVERFLOW_P flag be retrieved from @1, to duplicate the logic
> from is_{nega,posi}tive_overflow_infinity?  Is it availably
> somewhere, or is it necessary to somehow re-calculate it from the
> expression?
>
> (This is really necessary so that cases like this don't start
> folding with the patch:
>
> --
> signed char foo3uu (unsigned char a)
> {
>  unsigned char d;
>  unsigned long un;
>
>  d = (a & 63) + 200;
>  un = d;
>  if (un >= 12)
>    ubar(un);
>
>  return d;
> }
> --

What's wrong with folding un >= 12 to d >= 12 (ignoring profitability, 
which you already handle with single_use)? I am not convinced we need the 
overflow stuff at all here.

+(for cmp (eq ne gt ge lt le)

(for cmp (simple_comparison)

+ (cmp (convert@0 @1) INTEGER_CST@2)
+     (if (TREE_CODE (@1) == SSA_NAME

(cmp (convert@0 SSA_NAME@1) INTEGER_CST@2)

+	   (cmp { @1; } (convert @2))))))

(cmp @1 (convert @2))))))
Dominik Vogt Nov. 10, 2016, 11:34 p.m. UTC | #2 
On Thu, Nov 10, 2016 at 11:53:07PM +0100, Marc Glisse wrote:
> On Thu, 10 Nov 2016, Dominik Vogt wrote:
> 
> >On Wed, Nov 09, 2016 at 03:46:38PM +0100, Richard Biener wrote:
> >>On Wed, Nov 9, 2016 at 3:30 PM, Dominik Vogt <vogt@linux.vnet.ibm.com> wrote:
> >>>Something like the attached patch?  Robin and me have spent quite
> >>>some time to figure out the new pattern.  Two questions:
> >>>
> >>>1) In the match expression you cannot just use SSA_NAME@0 because
> >>>   then the "case SSA_NAME:" is added to a switch for another
> >>>   pattern that already has that label.  Thus we made that "proxy"
> >>>   predicate "ssa_name_p" that forces the code for the new pattern
> >>>   out of the old switch and into a separate code block.  We
> >>>   couldn't figure out whether this joining of case labels is a
> >>>   feature in the matching language.  So, is this the right way to
> >>>   deal with the conflicting labels?
> >>
> >>No, just do not match SSA_NAME.  And instead of
> >>
> >>+  (with { gimple *def_stmt = SSA_NAME_DEF_STMT (@0); }
> >>+   (if (is_gimple_assign (def_stmt)
> >>+       && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
> >>
> >>you instead want to change the pattern to
> >>
> >>(simpify
> >>  (cmp (convert @0) INTEGER_CST@1)
> >>
> >>@0 will then be your innerop
> >>
> >>note that you can't use get_value_range but you have to use the
> >>get_range_info interface instead.  I suppose a helper function
> >>somewhere that computes whether an expression fits a type
> >>would be helpful (see expr_not_equal_to for sth related,
> >>thus expr_fits_type_p (@0, TREE_TYPE (@1)))
> >
> >All right, I think we got that (new patch attached).
> >
> >>Likewise the overflow_infinity checks do not translate to match.pd
> >>(or rahter the range info you get).
> >
> >Can you give us another hint here, please?  The overflow check
> >should probably go into expr_fits_type_p, but with only the min
> >and max values from get_range_info, how can the overflow
> >TREE_OVERFLOW_P flag be retrieved from @1, to duplicate the logic
> >from is_{nega,posi}tive_overflow_infinity?  Is it availably
> >somewhere, or is it necessary to somehow re-calculate it from the
> >expression?
> >
> >(This is really necessary so that cases like this don't start
> >folding with the patch:
> >
> >--
> >signed char foo3uu (unsigned char a)
> >{
> > unsigned char d;
> > unsigned long un;
> >
> > d = (a & 63) + 200;
> > un = d;
> > if (un >= 12)
> >   ubar(un);
> >
> > return d;
> >}
> >--
> 
> What's wrong with folding un >= 12 to d >= 12 (ignoring
> profitability, which you already handle with single_use)? I am not
> convinced we need the overflow stuff at all here.

This is the patch that added the overflow check:

https://gcc.gnu.org/ml/gcc-patches/2013-05/msg00037.html
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57124
--
       	PR tree-optimization/57124
       	* tree-vrp.c (simplify_cond_using_ranges): Only simplify a
       	conversion feeding a condition if the range has an
overflow
       	if -fstrict-overflow.  Add warnings for when we do make
the
       	transformation.

       	PR tree-optimization/57124
       	* gcc.c-torture/execute/pr57124.c: New test.
       	* gcc.c-torture/execute/pr57124.x: Set
       	* -fno-strict-overflow.

    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@199305
138bc75d-0d04-0410-961f-82ee72b054a4
--

> +(for cmp (eq ne gt ge lt le)
> 
> (for cmp (simple_comparison)
> 
> + (cmp (convert@0 @1) INTEGER_CST@2)
> +     (if (TREE_CODE (@1) == SSA_NAME
> 
> (cmp (convert@0 SSA_NAME@1) INTEGER_CST@2)
> 
> +	   (cmp { @1; } (convert @2))))))
> 
> (cmp @1 (convert @2))))))

With some more cleaning:

(for cmp (simple_comparison) 
 (simplify 
  (cmp (convert@0 SSA_NAME@1) INTEGER_CST@2) 
  (if (!POINTER_TYPE_P (TREE_TYPE (@1)) 
       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (@1) 
       && desired_pro_or_demotion_p (TREE_TYPE (@1), TREE_TYPE (@0))) 
       && expr_fits_type_p (@1, TREE_TYPE (@0)) 
       && int_fits_type_p (@2, TREE_TYPE (@1)) 
       && (!has_single_use (@1) || has_single_use (@0))) 
   (cmp @1 (convert @2)))))) 

Ciao

Dominik ^_^  ^_^
Richard Biener Nov. 16, 2016, 1:41 p.m. UTC | #3 
On Thu, Nov 10, 2016 at 9:52 PM, Dominik Vogt <vogt@linux.vnet.ibm.com> wrote:
> On Wed, Nov 09, 2016 at 03:46:38PM +0100, Richard Biener wrote:
>> On Wed, Nov 9, 2016 at 3:30 PM, Dominik Vogt <vogt@linux.vnet.ibm.com> wrote:
>> > Something like the attached patch?  Robin and me have spent quite
>> > some time to figure out the new pattern.  Two questions:
>> >
>> > 1) In the match expression you cannot just use SSA_NAME@0 because
>> >    then the "case SSA_NAME:" is added to a switch for another
>> >    pattern that already has that label.  Thus we made that "proxy"
>> >    predicate "ssa_name_p" that forces the code for the new pattern
>> >    out of the old switch and into a separate code block.  We
>> >    couldn't figure out whether this joining of case labels is a
>> >    feature in the matching language.  So, is this the right way to
>> >    deal with the conflicting labels?
>>
>> No, just do not match SSA_NAME.  And instead of
>>
>> +  (with { gimple *def_stmt = SSA_NAME_DEF_STMT (@0); }
>> +   (if (is_gimple_assign (def_stmt)
>> +       && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
>>
>> you instead want to change the pattern to
>>
>> (simpify
>>   (cmp (convert @0) INTEGER_CST@1)
>>
>> @0 will then be your innerop
>>
>> note that you can't use get_value_range but you have to use the
>> get_range_info interface instead.  I suppose a helper function
>> somewhere that computes whether an expression fits a type
>> would be helpful (see expr_not_equal_to for sth related,
>> thus expr_fits_type_p (@0, TREE_TYPE (@1)))
>
> All right, I think we got that (new patch attached).
>
>> Likewise the overflow_infinity checks do not translate to match.pd
>> (or rahter the range info you get).
>
> Can you give us another hint here, please?  The overflow check
> should probably go into expr_fits_type_p, but with only the min
> and max values from get_range_info, how can the overflow
> TREE_OVERFLOW_P flag be retrieved from @1, to duplicate the logic
> from is_{nega,posi}tive_overflow_infinity?  Is it availably
> somewhere, or is it necessary to somehow re-calculate it from the
> expression?

You can't - just drop it (I've been dropping those already).

> (This is really necessary so that cases like this don't start
> folding with the patch:
>
> --
> signed char foo3uu (unsigned char a)
> {
>   unsigned char d;
>   unsigned long un;
>
>   d = (a & 63) + 200;
>   un = d;
>   if (un >= 12)
>     ubar(un);
>
>   return d;
> }

as Marc said there is nothing wrong with this folding.


+  if (has_range)
+    {
+      if (sign == tsign)
+       {
+         if (wi::le_p (max, TYPE_MAX_VALUE (type), sign)
+             && wi::ge_p (min, TYPE_MIN_VALUE (type), sign))
+           return true;
...

I believe you need to use widest_ints here, otherwise mixed precision
max / type will either lead to ICEs or truncations.  You then can also
always resort to signed compares.

from your other mail:

(for cmp (simple_comparison)
 (simplify
  (cmp (convert@0 SSA_NAME@1) INTEGER_CST@2)
  (if (!POINTER_TYPE_P (TREE_TYPE (@1))
       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (@1)
       && desired_pro_or_demotion_p (TREE_TYPE (@1), TREE_TYPE (@0)))
       && expr_fits_type_p (@1, TREE_TYPE (@0))
       && int_fits_type_p (@2, TREE_TYPE (@1))
       && (!has_single_use (@1) || has_single_use (@0)))
   (cmp @1 (convert @2))))))

that looks good now.

Thanks,
Richard.



> --
>
> )
>
> Ciao
>
> Dominik ^_^  ^_^
>
> --
>
> Dominik Vogt
> IBM Germany
diff mbox

Patch

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 593ea16..082ad46 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9100,6 +9100,70 @@  expr_not_equal_to (tree t, const wide_int &w)
     }
 }
 
+/* Return true if the value range of T is known not fit into TYPE.  */
+
+bool
+expr_fits_type_p (tree t, tree type)
+{
+  wide_int min, max;
+  value_range_type rtype;
+  signop sign;
+  signop tsign;
+  bool has_range = false;
+
+  if (!INTEGRAL_TYPE_P (type))
+    return false;
+  tsign = TYPE_SIGN (type);
+  sign = TYPE_SIGN (TREE_TYPE (t));
+  switch (TREE_CODE (t))
+    {
+    case INTEGER_CST:
+      min = t;
+      max = t;
+      has_range = true;
+      break;
+
+    case SSA_NAME:
+      if (!INTEGRAL_TYPE_P (TREE_TYPE (t)))
+	return false;
+      rtype = get_range_info (t, &min, &max);
+      if (rtype == VR_RANGE)
+	has_range = true;
+      else if (rtype == VR_ANTI_RANGE)
+	{
+	  /* As ANTI_RANGEs always wrap around, just check if T's whole type's
+	     value range fits into TYPE.  */
+	  min = TYPE_MIN_VALUE (TREE_TYPE (t));
+	  max = TYPE_MAX_VALUE (TREE_TYPE (t));
+	  has_range = true;
+	}
+      break;
+    }
+  if (has_range)
+    {
+      if (sign == tsign)
+	{
+	  if (wi::le_p (max, TYPE_MAX_VALUE (type), sign)
+	      && wi::ge_p (min, TYPE_MIN_VALUE (type), sign))
+	    return true;
+	}
+      else if (sign == SIGNED && tsign == UNSIGNED)
+	{
+	  if (wi::ge_p (min, 0, SIGNED)
+	      && wi::le_p (max, TYPE_MAX_VALUE (type), UNSIGNED)
+	      && wi::ge_p (min, TYPE_MIN_VALUE (type), UNSIGNED))
+	    return true;
+	}
+      else if (sign == UNSIGNED && tsign == SIGNED)
+	{
+	  if (wi::le_p (max, TYPE_MAX_VALUE (type), UNSIGNED))
+	    return true;
+	}
+    }
+
+  return false;
+}
+
 /* Fold a binary expression of code CODE and type TYPE with operands
    OP0 and OP1.  LOC is the location of the resulting expression.
    Return the folded expression if folding is successful.  Otherwise,
diff --git a/gcc/fold-const.h b/gcc/fold-const.h
index ae37142..46b0213 100644
--- a/gcc/fold-const.h
+++ b/gcc/fold-const.h
@@ -180,6 +180,7 @@  extern bool merge_ranges (int *, tree *, tree *, int, tree, tree, int,
 extern tree sign_bit_p (tree, const_tree);
 extern tree exact_inverse (tree, tree);
 extern bool expr_not_equal_to (tree t, const wide_int &);
+extern bool expr_fits_type_p (tree t, tree type);
 extern tree const_unop (enum tree_code, tree, tree);
 extern tree const_binop (enum tree_code, tree, tree, tree);
 extern bool negate_mathfn_p (combined_fn);
diff --git a/gcc/match.pd b/gcc/match.pd
index 48f7351..7f0fd08 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -3501,3 +3501,31 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	 { CONSTRUCTOR_ELT (ctor, idx / k)->value; })
 	(BIT_FIELD_REF { CONSTRUCTOR_ELT (ctor, idx / k)->value; }
 		       @1 { bitsize_int ((idx % k) * width); })))))))))
+
+#if GIMPLE
+/* If we have a comparison of an SSA_NAME (OP0) against a constant,
+   see if OP0 was set by a type conversion where the source of
+   the conversion is another SSA_NAME with a range that fits
+   into the range of OP0's type.
+
+   If so, the conversion is redundant as the earlier SSA_NAME can be
+   used for the comparison directly if we just massage the constant in the
+   comparison.  */
+
+(for cmp (eq ne gt ge lt le)
+ (simplify
+ (cmp (convert@0 @1) INTEGER_CST@2)
+     (if (TREE_CODE (@1) == SSA_NAME
+	  && !POINTER_TYPE_P (TREE_TYPE (@1))
+	  && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (@1)
+	  && desired_pro_or_demotion_p (TREE_TYPE (@1), TREE_TYPE (@0)))
+	  (if (expr_fits_type_p (@1, TREE_TYPE (@0))
+	       && int_fits_type_p (@2, TREE_TYPE (@1))
+	       /*!!! overflow conditions*/
+	       /* If the only use of @1 is the cast to @0, and @0 is also
+		  used in other places, folding would introduce new uses
+		  of the otherwise dead @1 without eliminating @1, so do
+		  not.  */
+	       && (!has_single_use (@1) || has_single_use (@0)))
+	   (cmp { @1; } (convert @2))))))
+#endif
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 68fe2ac..548b91e 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -9590,72 +9590,6 @@  simplify_cond_using_ranges (gcond *stmt)
 	}
     }
 
-  /* If we have a comparison of an SSA_NAME (OP0) against a constant,
-     see if OP0 was set by a type conversion where the source of
-     the conversion is another SSA_NAME with a range that fits
-     into the range of OP0's type.
-
-     If so, the conversion is redundant as the earlier SSA_NAME can be
-     used for the comparison directly if we just massage the constant in the
-     comparison.  */
-  if (TREE_CODE (op0) == SSA_NAME
-      && TREE_CODE (op1) == INTEGER_CST)
-    {
-      gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
-      tree innerop;
-
-      if (!is_gimple_assign (def_stmt)
-	  || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
-	return false;
-
-      innerop = gimple_assign_rhs1 (def_stmt);
-
-      if (TREE_CODE (innerop) == SSA_NAME
-	  && !POINTER_TYPE_P (TREE_TYPE (innerop))
-	  && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop)
-	  && desired_pro_or_demotion_p (TREE_TYPE (innerop), TREE_TYPE (op0)))
-	{
-	  value_range *vr = get_value_range (innerop);
-
-	  if (range_int_cst_p (vr)
-	      && range_fits_type_p (vr,
-				    TYPE_PRECISION (TREE_TYPE (op0)),
-				    TYPE_SIGN (TREE_TYPE (op0)))
-	      && int_fits_type_p (op1, TREE_TYPE (innerop))
-	      /* The range must not have overflowed, or if it did overflow
-		 we must not be wrapping/trapping overflow and optimizing
-		 with strict overflow semantics.  */
-	      && ((!is_negative_overflow_infinity (vr->min)
-	           && !is_positive_overflow_infinity (vr->max))
-		  || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (innerop))))
-	    {
-	      /* If the range overflowed and the user has asked for warnings
-		 when strict overflow semantics were used to optimize code,
-		 issue an appropriate warning.  */
-	      if (cond_code != EQ_EXPR && cond_code != NE_EXPR
-		  && (is_negative_overflow_infinity (vr->min)
-		      || is_positive_overflow_infinity (vr->max))
-		  && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_CONDITIONAL))
-		{
-		  location_t location;
-
-		  if (!gimple_has_location (stmt))
-		    location = input_location;
-		  else
-		    location = gimple_location (stmt);
-		  warning_at (location, OPT_Wstrict_overflow,
-			      "assuming signed overflow does not occur when "
-			      "simplifying conditional");
-		}
-
-	      tree newconst = fold_convert (TREE_TYPE (innerop), op1);
-	      gimple_cond_set_lhs (stmt, innerop);
-	      gimple_cond_set_rhs (stmt, newconst);
-	      return true;
-	    }
-	}
-    }
-
   return false;
 }