diff mbox

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

Message ID 20161109143053.GA21900@linux.vnet.ibm.com
State New
Headers show

Commit Message

Dominik Vogt Nov. 9, 2016, 2:30 p.m. UTC 
On Wed, Nov 09, 2016 at 01:43:58PM +0100, Richard Biener wrote:
> On Tue, Nov 8, 2016 at 5:18 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> > On Tue, 8 Nov 2016, Dominik Vogt wrote:
> >
> >> On Fri, Nov 04, 2016 at 01:54:20PM +0100, Richard Biener wrote:
> >>>
> >>> On Fri, Nov 4, 2016 at 12:08 PM, Dominik Vogt <vogt@linux.vnet.ibm.com>
> >>> wrote:
> >>>>
> >>>> On Fri, Nov 04, 2016 at 09:47:26AM +0100, Richard Biener wrote:
> >>>>>
> >>>>> On Thu, Nov 3, 2016 at 4:03 PM, Dominik Vogt <vogt@linux.vnet.ibm.com>
> >>>>> wrote:
> >>>>>>
> >>>>>> Is VRP the right pass to do this optimisation or should a later
> >>>>>> pass rather attempt to eliminate the new use of b_5 instead?  Uli
> >>>>>> has brought up the idea a mini "sign extend elimination" pass that
> >>>>>> checks if the result of a sign extend could be replaced by the
> >>>>>> original quantity in all places, and if so, eliminate the ssa
> >>>>>> name.  (I guess that won't help with the above code because l is
> >>>>>> used also as a function argument.)  How could a sensible approach
> >>>>>> to deal with the situation look like?
> >>>>>
> >>>>>
> >>>>> We run into this kind of situation regularly and for general foldings
> >>>>> in match.pd we settled with single_use () even though it is not
> >>>>> perfect.
> >>>>> Note the usual complaint is not extra extension instructions but
> >>>>> the increase of register pressure.
> >>>>>
> >>>>> This is because it is hard to do better when you are doing local
> >>>>> optimization.
> >>>>>
> >>>>> As for the question on whether VRP is the right pass to do this the
> >>>>> answer is two-fold -- VRP has the most precise range information.
> >>>>> But the folding itself should be moved to generic code and use
> >>>>> get_range_info ().
> >>>>
> >>>>
> >>>> All right, is this a sensible approach then?
> >>>
> >>>
> >>> Yes.
> >>>
> >>>>   1. Using has_single_use as in the experimental patch is good
> >>>>      enough (provided further testing does not show serious
> >>>>      regressions).
> >>>
> >>>
> >>> I'd approve that, yes.
> >>>
> >>>>   2. Rip the whole top level if-block from simplify_cond_using_ranges().
> >>>>   3. Translate that code to match.pd syntax.
> >>>
> >>>
> >>> Might be some work but yes, that's also desired (you'd lose the ability
> >>> to emit the warnings though).
> >>
> >>
> >> Could you give me a match-pd-hint please?  We now have something
> >> like this:
> >>
> >> (simplify
> >>  (cond (gt SSA_NAME@0 INTEGER_CST@1) @2 @3)
> >>  (if (... many conditions ...)
> >>   (cond (gt ... ...) @2 @3))
> >>
> >> The generated code ends up in gimple_simplify_COND_EXPR, but when
> >> gimple_simplify is actually called, it goes through the
> >> GIMPLE_COND case and calls gimple_resimplify2(..., GT, ...) and
> >> there it tries gimple_simplify_GT_EXPR(), peeling of the (cond
> >> ...), i.e. it never tries the generated code.
> >
> >
> > Not sure what you mean here.
> >
> >> There is another pattern in match.pd that uses a (cond ...) as the
> >> first operand, and I do not understand how this works.  Should we
> >> just use "(gt SSA_NAME@0 INTEGER_CST@1)" as the first operand
> >> instead, and wouldn't this pattern be too general that way?
> >
> >
> > IIUC, you are trying to move the second half of simplify_cond_using_ranges
> > to match.pd. I don't see any reason to restrict it to the case where the
> > comparison result is used directly in a COND_EXPR, so that would look like:
> >
> > (for cmp (...)
> >  (simplify
> >   (cmp (convert SSA_NAME@0) INTEGER_CST@1)
> >   (if (...)
> >    (cmp @0 (convert @1)))))
> >
> > maybe? I think I may have missed your point.
> 
> Yeah, if you'd use (cond (gt ... then it only matches in assignments
> with COND_EXPRs on the RHS, _not_ in GIMPLE_CONDs.
> 
> So you ran into the (cond vs. GIMPLE_COND "mismatch".
> 
> You'd essentially implement sth similar to shorten_compare in match.pd.

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?

2) There's an awful lot of if-clauses in the replacement
   expression.  Is it the right place to do all this checking?

> Btw, moving to match.pd shouldn't be a blocker for adding proper
> single_use tests
> just in case you get lost ...

Ciao

Dominik ^_^  ^_^

Comments

Richard Biener Nov. 9, 2016, 2:46 p.m. UTC | #1 
On Wed, Nov 9, 2016 at 3:30 PM, Dominik Vogt <vogt@linux.vnet.ibm.com> wrote:
> On Wed, Nov 09, 2016 at 01:43:58PM +0100, Richard Biener wrote:
>> On Tue, Nov 8, 2016 at 5:18 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> > On Tue, 8 Nov 2016, Dominik Vogt wrote:
>> >
>> >> On Fri, Nov 04, 2016 at 01:54:20PM +0100, Richard Biener wrote:
>> >>>
>> >>> On Fri, Nov 4, 2016 at 12:08 PM, Dominik Vogt <vogt@linux.vnet.ibm.com>
>> >>> wrote:
>> >>>>
>> >>>> On Fri, Nov 04, 2016 at 09:47:26AM +0100, Richard Biener wrote:
>> >>>>>
>> >>>>> On Thu, Nov 3, 2016 at 4:03 PM, Dominik Vogt <vogt@linux.vnet.ibm.com>
>> >>>>> wrote:
>> >>>>>>
>> >>>>>> Is VRP the right pass to do this optimisation or should a later
>> >>>>>> pass rather attempt to eliminate the new use of b_5 instead?  Uli
>> >>>>>> has brought up the idea a mini "sign extend elimination" pass that
>> >>>>>> checks if the result of a sign extend could be replaced by the
>> >>>>>> original quantity in all places, and if so, eliminate the ssa
>> >>>>>> name.  (I guess that won't help with the above code because l is
>> >>>>>> used also as a function argument.)  How could a sensible approach
>> >>>>>> to deal with the situation look like?
>> >>>>>
>> >>>>>
>> >>>>> We run into this kind of situation regularly and for general foldings
>> >>>>> in match.pd we settled with single_use () even though it is not
>> >>>>> perfect.
>> >>>>> Note the usual complaint is not extra extension instructions but
>> >>>>> the increase of register pressure.
>> >>>>>
>> >>>>> This is because it is hard to do better when you are doing local
>> >>>>> optimization.
>> >>>>>
>> >>>>> As for the question on whether VRP is the right pass to do this the
>> >>>>> answer is two-fold -- VRP has the most precise range information.
>> >>>>> But the folding itself should be moved to generic code and use
>> >>>>> get_range_info ().
>> >>>>
>> >>>>
>> >>>> All right, is this a sensible approach then?
>> >>>
>> >>>
>> >>> Yes.
>> >>>
>> >>>>   1. Using has_single_use as in the experimental patch is good
>> >>>>      enough (provided further testing does not show serious
>> >>>>      regressions).
>> >>>
>> >>>
>> >>> I'd approve that, yes.
>> >>>
>> >>>>   2. Rip the whole top level if-block from simplify_cond_using_ranges().
>> >>>>   3. Translate that code to match.pd syntax.
>> >>>
>> >>>
>> >>> Might be some work but yes, that's also desired (you'd lose the ability
>> >>> to emit the warnings though).
>> >>
>> >>
>> >> Could you give me a match-pd-hint please?  We now have something
>> >> like this:
>> >>
>> >> (simplify
>> >>  (cond (gt SSA_NAME@0 INTEGER_CST@1) @2 @3)
>> >>  (if (... many conditions ...)
>> >>   (cond (gt ... ...) @2 @3))
>> >>
>> >> The generated code ends up in gimple_simplify_COND_EXPR, but when
>> >> gimple_simplify is actually called, it goes through the
>> >> GIMPLE_COND case and calls gimple_resimplify2(..., GT, ...) and
>> >> there it tries gimple_simplify_GT_EXPR(), peeling of the (cond
>> >> ...), i.e. it never tries the generated code.
>> >
>> >
>> > Not sure what you mean here.
>> >
>> >> There is another pattern in match.pd that uses a (cond ...) as the
>> >> first operand, and I do not understand how this works.  Should we
>> >> just use "(gt SSA_NAME@0 INTEGER_CST@1)" as the first operand
>> >> instead, and wouldn't this pattern be too general that way?
>> >
>> >
>> > IIUC, you are trying to move the second half of simplify_cond_using_ranges
>> > to match.pd. I don't see any reason to restrict it to the case where the
>> > comparison result is used directly in a COND_EXPR, so that would look like:
>> >
>> > (for cmp (...)
>> >  (simplify
>> >   (cmp (convert SSA_NAME@0) INTEGER_CST@1)
>> >   (if (...)
>> >    (cmp @0 (convert @1)))))
>> >
>> > maybe? I think I may have missed your point.
>>
>> Yeah, if you'd use (cond (gt ... then it only matches in assignments
>> with COND_EXPRs on the RHS, _not_ in GIMPLE_CONDs.
>>
>> So you ran into the (cond vs. GIMPLE_COND "mismatch".
>>
>> You'd essentially implement sth similar to shorten_compare in match.pd.
>
> 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)))

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

Richard.

>
> 2) There's an awful lot of if-clauses in the replacement
>    expression.  Is it the right place to do all this checking?
>
>> Btw, moving to match.pd shouldn't be a blocker for adding proper
>> single_use tests
>> just in case you get lost ...
>
> Ciao
>
> Dominik ^_^  ^_^
>
> --
>
> Dominik Vogt
> IBM Germany
diff mbox

Patch

diff --git a/gcc/match.pd b/gcc/match.pd
index 48f7351..e2a663b 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -3501,3 +3501,43 @@  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 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.  */
+
+(match ssa_name_p SSA_NAME)
+(for cmp (eq ne gt ge lt le)
+ (simplify
+ (cmp ssa_name_p@0 INTEGER_CST@1)
+  (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)))
+    (with { tree 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 (@0)))
+      (with { value_range *vr = get_value_range (innerop); }
+       (if (vr
+	    && range_int_cst_p (vr)
+	    && range_fits_type_p (vr,
+				  TYPE_PRECISION (TREE_TYPE (@0)),
+				  TYPE_SIGN (TREE_TYPE (@0)))
+	    && int_fits_type_p (@1, 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 only use of INNEROP is the cast to @0, and @0 is also
+	       used in other places, folding would introduce new uses of the
+	       otherwise dead INNEROP without eliminating @0, so do not.  */
+	    && (!has_single_use (innerop) || has_single_use (@0)))
+	   (cmp { innerop; } (convert @1))))))))))
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 68fe2ac..1b128e2 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -259,7 +259,7 @@  positive_overflow_infinity (tree type)
 
 /* Return whether VAL is a negative overflow infinity.  */
 
-static inline bool
+bool
 is_negative_overflow_infinity (const_tree val)
 {
   return (TREE_OVERFLOW_P (val)
@@ -269,7 +269,7 @@  is_negative_overflow_infinity (const_tree val)
 
 /* Return whether VAL is a positive overflow infinity.  */
 
-static inline bool
+bool
 is_positive_overflow_infinity (const_tree val)
 {
   return (TREE_OVERFLOW_P (val)
@@ -640,7 +640,7 @@  abs_extent_range (value_range *vr, tree min, tree max)
    If we have no values ranges recorded (ie, VRP is not running), then
    return NULL.  Otherwise create an empty range if none existed for VAR.  */
 
-static value_range *
+value_range *
 get_value_range (const_tree var)
 {
   static const value_range vr_const_varying
@@ -877,7 +877,7 @@  range_is_null (value_range *vr)
 /* Return true if max and min of VR are INTEGER_CST.  It's not necessary
    a singleton.  */
 
-static inline bool
+bool
 range_int_cst_p (value_range *vr)
 {
   return (vr->type == VR_RANGE
@@ -9432,7 +9432,7 @@  test_for_singularity (enum tree_code cond_code, tree op0,
 /* Return whether the value range *VR fits in an integer type specified
    by PRECISION and UNSIGNED_P.  */
 
-static bool
+bool
 range_fits_type_p (value_range *vr, unsigned dest_precision, signop dest_sgn)
 {
   tree src_type;
@@ -9486,7 +9486,7 @@  range_fits_type_p (value_range *vr, unsigned dest_precision, signop dest_sgn)
    the original conditional.  */
 
 static bool
-simplify_cond_using_ranges (gcond *stmt)
+simplify_cond_using_ranges (gimple_stmt_iterator *gsi, gcond *stmt)
 {
   tree op0 = gimple_cond_lhs (stmt);
   tree op1 = gimple_cond_rhs (stmt);
@@ -9590,73 +9590,7 @@  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;
+  return fold_stmt (gsi, follow_single_use_edges);
 }
 
 /* Simplify a switch statement using the value range of the switch
@@ -10250,7 +10184,7 @@  simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
 	}
     }
   else if (gimple_code (stmt) == GIMPLE_COND)
-    return simplify_cond_using_ranges (as_a <gcond *> (stmt));
+    return simplify_cond_using_ranges (gsi, as_a <gcond *> (stmt));
   else if (gimple_code (stmt) == GIMPLE_SWITCH)
     return simplify_switch_using_ranges (as_a <gswitch *> (stmt));
   else if (is_gimple_call (stmt)
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 5cea709..38cd1be 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -56,4 +56,9 @@  extern void extract_range_from_unary_expr (value_range *vr,
 					   tree type,
 					   value_range *vr0_,
 					   tree op0_type);
-
+extern value_range *get_value_range (const_tree var);
+extern bool range_fits_type_p (value_range *vr, unsigned dest_precision,
+			       signop dest_sgn);
+extern bool is_negative_overflow_infinity (const_tree val);
+extern bool is_positive_overflow_infinity (const_tree val);
+extern bool range_int_cst_p (value_range *vr);