[PATCH] tree-optimization/114151 - handle POLY_INT_CST in get_range_pos_neg

[PATCH] tree-optimization/114151 - handle POLY_INT_CST in get_range_pos_neg

[Richard Biener]

The following switches the logic in chrec_fold_multiply to
get_range_pos_neg since handling POLY_INT_CST possibly mixed with
non-poly ranges will make the open-coding awkward and while not
a perfect fit it should work.

In turn the following makes get_range_pos_neg aware of POLY_INT_CSTs.
I couldn't make it work with poly_wide_int since the compares always
fail to build but poly_widest_int works fine and it should be
semantically the same.  I've also changed get_range_pos_neg to
use get_range_query (cfun), problematical passes shouldn't have
a range query activated so it shouldn't make a difference there.

This doesn't make a difference for the PR but not considering
POLY_INT_CSTs was a mistake.

Bootstrap and regtest running on x86_64-unknown-linux-gnu, OK?

Thanks,
Richard.

	PR tree-optimization/114151
	* tree.cc (get_range_pos_neg): Handle POLY_INT_CST, use
	the passes range-query if available.
	* tree-chre.cc (chrec_fold_multiply): Use get_range_pos_neg
	to see if both operands have the same range.
---
 gcc/tree-chrec.cc | 14 ++------------
 gcc/tree.cc       | 12 +++++++-----
 2 files changed, 9 insertions(+), 17 deletions(-)

diff --git a/gcc/tree-chrec.cc b/gcc/tree-chrec.cc
index 2e6c7356d3b..450d018ce6f 100644
--- a/gcc/tree-chrec.cc
+++ b/gcc/tree-chrec.cc
@@ -442,18 +442,8 @@ chrec_fold_multiply (tree type,
 	  if (!ANY_INTEGRAL_TYPE_P (type)
 	      || TYPE_OVERFLOW_WRAPS (type)
 	      || integer_zerop (CHREC_LEFT (op0))
-	      || (TREE_CODE (CHREC_LEFT (op0)) == INTEGER_CST
-		  && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST
-		  && (tree_int_cst_sgn (CHREC_LEFT (op0))
-		      == tree_int_cst_sgn (CHREC_RIGHT (op0))))
-	      || (get_range_query (cfun)->range_of_expr (rl, CHREC_LEFT (op0))
-		  && !rl.undefined_p ()
-		  && (rl.nonpositive_p () || rl.nonnegative_p ())
-		  && get_range_query (cfun)->range_of_expr (rr,
-							    CHREC_RIGHT (op0))
-		  && !rr.undefined_p ()
-		  && ((rl.nonpositive_p () && rr.nonpositive_p ())
-		      || (rl.nonnegative_p () && rr.nonnegative_p ()))))
+	      || (get_range_pos_neg (CHREC_LEFT (op0))
+		  | get_range_pos_neg (CHREC_RIGHT (op0))) != 3)
 	    {
 	      tree left = chrec_fold_multiply (type, CHREC_LEFT (op0), op1);
 	      tree right = chrec_fold_multiply (type, CHREC_RIGHT (op0), op1);
diff --git a/gcc/tree.cc b/gcc/tree.cc
index f801712c9dd..fcc914f0f7a 100644
--- a/gcc/tree.cc
+++ b/gcc/tree.cc
@@ -14408,13 +14408,15 @@ get_range_pos_neg (tree arg)
 
   int prec = TYPE_PRECISION (TREE_TYPE (arg));
   int cnt = 0;
-  if (TREE_CODE (arg) == INTEGER_CST)
+  if (poly_int_tree_p (arg))
     {
-      wide_int w = wi::sext (wi::to_wide (arg), prec);
-      if (wi::neg_p (w))
+      poly_widest_int w = wi::sext (wi::to_poly_widest (arg), prec);
+      if (known_lt (w, 0))
 	return 2;
-      else
+      else if (known_ge (w, 0))
 	return 1;
+      else
+	return 3;
     }
   while (CONVERT_EXPR_P (arg)
 	 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))
@@ -14434,7 +14436,7 @@ get_range_pos_neg (tree arg)
   if (TREE_CODE (arg) != SSA_NAME)
     return 3;
   value_range r;
-  while (!get_global_range_query ()->range_of_expr (r, arg)
+  while (!get_range_query (cfun)->range_of_expr (r, arg)
 	 || r.undefined_p () || r.varying_p ())
     {
       gimple *g = SSA_NAME_DEF_STMT (arg);
-- 
2.35.3

Re: [PATCH] tree-optimization/114151 - handle POLY_INT_CST in get_range_pos_neg

[Jakub Jelinek]

On Thu, Feb 29, 2024 at 09:21:02AM +0100, Richard Biener wrote:
> The following switches the logic in chrec_fold_multiply to
> get_range_pos_neg since handling POLY_INT_CST possibly mixed with
> non-poly ranges will make the open-coding awkward and while not
> a perfect fit it should work.
> 
> In turn the following makes get_range_pos_neg aware of POLY_INT_CSTs.
> I couldn't make it work with poly_wide_int since the compares always
> fail to build but poly_widest_int works fine and it should be
> semantically the same.  I've also changed get_range_pos_neg to
> use get_range_query (cfun), problematical passes shouldn't have
> a range query activated so it shouldn't make a difference there.
> 
> This doesn't make a difference for the PR but not considering
> POLY_INT_CSTs was a mistake.
> 
> Bootstrap and regtest running on x86_64-unknown-linux-gnu, OK?
> 
> Thanks,
> Richard.
> 
> 	PR tree-optimization/114151
> 	* tree.cc (get_range_pos_neg): Handle POLY_INT_CST, use
> 	the passes range-query if available.
> 	* tree-chre.cc (chrec_fold_multiply): Use get_range_pos_neg
> 	to see if both operands have the same range.
> ---
>  gcc/tree-chrec.cc | 14 ++------------
>  gcc/tree.cc       | 12 +++++++-----
>  2 files changed, 9 insertions(+), 17 deletions(-)
> 
> diff --git a/gcc/tree-chrec.cc b/gcc/tree-chrec.cc
> index 2e6c7356d3b..450d018ce6f 100644
> --- a/gcc/tree-chrec.cc
> +++ b/gcc/tree-chrec.cc
> @@ -442,18 +442,8 @@ chrec_fold_multiply (tree type,
>  	  if (!ANY_INTEGRAL_TYPE_P (type)
>  	      || TYPE_OVERFLOW_WRAPS (type)
>  	      || integer_zerop (CHREC_LEFT (op0))
> -	      || (TREE_CODE (CHREC_LEFT (op0)) == INTEGER_CST
> -		  && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST
> -		  && (tree_int_cst_sgn (CHREC_LEFT (op0))
> -		      == tree_int_cst_sgn (CHREC_RIGHT (op0))))
> -	      || (get_range_query (cfun)->range_of_expr (rl, CHREC_LEFT (op0))
> -		  && !rl.undefined_p ()
> -		  && (rl.nonpositive_p () || rl.nonnegative_p ())
> -		  && get_range_query (cfun)->range_of_expr (rr,
> -							    CHREC_RIGHT (op0))
> -		  && !rr.undefined_p ()
> -		  && ((rl.nonpositive_p () && rr.nonpositive_p ())
> -		      || (rl.nonnegative_p () && rr.nonnegative_p ()))))
> +	      || (get_range_pos_neg (CHREC_LEFT (op0))
> +		  | get_range_pos_neg (CHREC_RIGHT (op0))) != 3)
>  	    {
>  	      tree left = chrec_fold_multiply (type, CHREC_LEFT (op0), op1);
>  	      tree right = chrec_fold_multiply (type, CHREC_RIGHT (op0), op1);

So, wouldn't it be better to outline what you have above + POLY_INT_CST
handling into a helper function, which similarly to get_range_pos_neg
returns a bitmask, but rather than 1 bit for may be [0, max] and another bit for
may be [min, -1] you return 3 bits, 1 bit for may be [1, max], another for
may be [0, 0] and another for may be [min, -1]?
Also, I bet you actually want to handle TREE_UNSIGNED just as [0, 0]
and [1, max] ranges unlike get_range_pos_neg.

So perhaps
  int ret = 7;
  if (TYPE_UNSIGNED (TREE_TYPE (arg)))
    ret = 3;
  if (poly_int_tree_p (arg))
    {
      poly_wide_int w = wi::to_poly_wide (arg);
      if (known_lt (w, 0))
	return 4;
      else if (known_eq (w, 0))
	return 2;
      else if (known_gt (w, 0))
	return 1;
      else
	return 7;
    }
  value_range r;
  if (!get_range_query (cfun)->range_of_expr (r, arg)
      || r.undefined_p ())
    return ret;
  if (r.nonpositive_p ())
    ret &= ~1;
  if (r.nonzero_p ())
    ret &= ~2;
  if (r.nonnegative_p ())
    ret &= ~4;
  return ret;

?  And then you can use it similarly,
  ((whatever_fn (CHREC_LEFT (op0))
    | whatever_fn (CHREC_RIGHT (op0))) & ~2) != 5

Sure, if it is written just for this case and not other uses,
it could be just 2 bits, can contain [1, max] and can contain [min, -1]
because you don't care about zero, return 0 for the known_eq (w, 0)
there...

Though see below, perhaps it should just handle INTEGER_CSTs and
is_constant () POLY_INT_CSTs, not really sure what happens if there
are overflows in the POLY_INT_CST evaluation.

> --- a/gcc/tree.cc
> +++ b/gcc/tree.cc
> @@ -14408,13 +14408,15 @@ get_range_pos_neg (tree arg)
>  
>    int prec = TYPE_PRECISION (TREE_TYPE (arg));
>    int cnt = 0;
> -  if (TREE_CODE (arg) == INTEGER_CST)
> +  if (poly_int_tree_p (arg))
>      {
> -      wide_int w = wi::sext (wi::to_wide (arg), prec);
> -      if (wi::neg_p (w))
> +      poly_widest_int w = wi::sext (wi::to_poly_widest (arg), prec);
> +      if (known_lt (w, 0))
>  	return 2;
> -      else
> +      else if (known_ge (w, 0))
>  	return 1;
> +      else
> +	return 3;
>      }
>    while (CONVERT_EXPR_P (arg)
>  	 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))

I doubt POLY_INT_CST will appear on what the function is being called on
(types with scalar integral modes, mainly in .*_OVERFLOW expansion or say
division/modulo expansion, but maybe my imagination is limited);
so, if you think this is a good idea and the poly int in that case somehow
guarantees the existing behavior (guess for signed it would be at least when
not -fwrapv in action UB if the addition of the first POLY_INT_CST coeff
and the others multiplied by the runtime value wraps around, but for
unsigned is there a guarantee that if all the POLY_INT_CST coefficients
don't have msb set that the resulting value will not have msb set either?

> @@ -14434,7 +14436,7 @@ get_range_pos_neg (tree arg)
>    if (TREE_CODE (arg) != SSA_NAME)
>      return 3;
>    value_range r;
> -  while (!get_global_range_query ()->range_of_expr (r, arg)
> +  while (!get_range_query (cfun)->range_of_expr (r, arg)
>  	 || r.undefined_p () || r.varying_p ())
>      {
>        gimple *g = SSA_NAME_DEF_STMT (arg);

This hunk is certainly ok.

	Jakub

Re: [PATCH] tree-optimization/114151 - handle POLY_INT_CST in get_range_pos_neg

[Richard Biener]

On Thu, 29 Feb 2024, Jakub Jelinek wrote:

> On Thu, Feb 29, 2024 at 09:21:02AM +0100, Richard Biener wrote:
> > The following switches the logic in chrec_fold_multiply to
> > get_range_pos_neg since handling POLY_INT_CST possibly mixed with
> > non-poly ranges will make the open-coding awkward and while not
> > a perfect fit it should work.
> > 
> > In turn the following makes get_range_pos_neg aware of POLY_INT_CSTs.
> > I couldn't make it work with poly_wide_int since the compares always
> > fail to build but poly_widest_int works fine and it should be
> > semantically the same.  I've also changed get_range_pos_neg to
> > use get_range_query (cfun), problematical passes shouldn't have
> > a range query activated so it shouldn't make a difference there.
> > 
> > This doesn't make a difference for the PR but not considering
> > POLY_INT_CSTs was a mistake.
> > 
> > Bootstrap and regtest running on x86_64-unknown-linux-gnu, OK?
> > 
> > Thanks,
> > Richard.
> > 
> > 	PR tree-optimization/114151
> > 	* tree.cc (get_range_pos_neg): Handle POLY_INT_CST, use
> > 	the passes range-query if available.
> > 	* tree-chre.cc (chrec_fold_multiply): Use get_range_pos_neg
> > 	to see if both operands have the same range.
> > ---
> >  gcc/tree-chrec.cc | 14 ++------------
> >  gcc/tree.cc       | 12 +++++++-----
> >  2 files changed, 9 insertions(+), 17 deletions(-)
> > 
> > diff --git a/gcc/tree-chrec.cc b/gcc/tree-chrec.cc
> > index 2e6c7356d3b..450d018ce6f 100644
> > --- a/gcc/tree-chrec.cc
> > +++ b/gcc/tree-chrec.cc
> > @@ -442,18 +442,8 @@ chrec_fold_multiply (tree type,
> >  	  if (!ANY_INTEGRAL_TYPE_P (type)
> >  	      || TYPE_OVERFLOW_WRAPS (type)
> >  	      || integer_zerop (CHREC_LEFT (op0))
> > -	      || (TREE_CODE (CHREC_LEFT (op0)) == INTEGER_CST
> > -		  && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST
> > -		  && (tree_int_cst_sgn (CHREC_LEFT (op0))
> > -		      == tree_int_cst_sgn (CHREC_RIGHT (op0))))
> > -	      || (get_range_query (cfun)->range_of_expr (rl, CHREC_LEFT (op0))
> > -		  && !rl.undefined_p ()
> > -		  && (rl.nonpositive_p () || rl.nonnegative_p ())
> > -		  && get_range_query (cfun)->range_of_expr (rr,
> > -							    CHREC_RIGHT (op0))
> > -		  && !rr.undefined_p ()
> > -		  && ((rl.nonpositive_p () && rr.nonpositive_p ())
> > -		      || (rl.nonnegative_p () && rr.nonnegative_p ()))))
> > +	      || (get_range_pos_neg (CHREC_LEFT (op0))
> > +		  | get_range_pos_neg (CHREC_RIGHT (op0))) != 3)
> >  	    {
> >  	      tree left = chrec_fold_multiply (type, CHREC_LEFT (op0), op1);
> >  	      tree right = chrec_fold_multiply (type, CHREC_RIGHT (op0), op1);
> 
> So, wouldn't it be better to outline what you have above + POLY_INT_CST
> handling into a helper function, which similarly to get_range_pos_neg
> returns a bitmask, but rather than 1 bit for may be [0, max] and another bit for
> may be [min, -1] you return 3 bits, 1 bit for may be [1, max], another for
> may be [0, 0] and another for may be [min, -1]?
> Also, I bet you actually want to handle TREE_UNSIGNED just as [0, 0]
> and [1, max] ranges unlike get_range_pos_neg.

I'm just lazy and given TYPE_OVERFLOW_WRAPS (and thus unsigned) doesn't
ever get here and I special-case integer_zerop it doesn't really matter
that in these cases get_range_pos_neg isn't exactly what's wanted - I'm
asking it only for those cases where it works just fine.

> So perhaps
>   int ret = 7;
>   if (TYPE_UNSIGNED (TREE_TYPE (arg)))
>     ret = 3;
>   if (poly_int_tree_p (arg))
>     {
>       poly_wide_int w = wi::to_poly_wide (arg);
>       if (known_lt (w, 0))
> 	return 4;
>       else if (known_eq (w, 0))
> 	return 2;
>       else if (known_gt (w, 0))
> 	return 1;
>       else
> 	return 7;
>     }
>   value_range r;
>   if (!get_range_query (cfun)->range_of_expr (r, arg)
>       || r.undefined_p ())
>     return ret;
>   if (r.nonpositive_p ())
>     ret &= ~1;
>   if (r.nonzero_p ())
>     ret &= ~2;
>   if (r.nonnegative_p ())
>     ret &= ~4;
>   return ret;
> 
> ?  And then you can use it similarly,
>   ((whatever_fn (CHREC_LEFT (op0))
>     | whatever_fn (CHREC_RIGHT (op0))) & ~2) != 5
> 
> Sure, if it is written just for this case and not other uses,
> it could be just 2 bits, can contain [1, max] and can contain [min, -1]
> because you don't care about zero, return 0 for the known_eq (w, 0)
> there...
> 
> Though see below, perhaps it should just handle INTEGER_CSTs and
> is_constant () POLY_INT_CSTs, not really sure what happens if there
> are overflows in the POLY_INT_CST evaluation.

I'm indeed also not sure whether the POLY_INT_CST is behaving
correctly.  I think POLYs are always constrained somehow but
whether known_gt ([__INT_MAX__, 1], 0) computes correctly
(or whether we treat overflow there as undefined?) I don't know.

I was trying to avoid adding yet another helper that does nearly
the same when I can actually use the existing one.

> > --- a/gcc/tree.cc
> > +++ b/gcc/tree.cc
> > @@ -14408,13 +14408,15 @@ get_range_pos_neg (tree arg)
> >  
> >    int prec = TYPE_PRECISION (TREE_TYPE (arg));
> >    int cnt = 0;
> > -  if (TREE_CODE (arg) == INTEGER_CST)
> > +  if (poly_int_tree_p (arg))
> >      {
> > -      wide_int w = wi::sext (wi::to_wide (arg), prec);
> > -      if (wi::neg_p (w))
> > +      poly_widest_int w = wi::sext (wi::to_poly_widest (arg), prec);
> > +      if (known_lt (w, 0))
> >  	return 2;
> > -      else
> > +      else if (known_ge (w, 0))
> >  	return 1;
> > +      else
> > +	return 3;
> >      }
> >    while (CONVERT_EXPR_P (arg)
> >  	 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (arg, 0)))
> 
> I doubt POLY_INT_CST will appear on what the function is being called on
> (types with scalar integral modes, mainly in .*_OVERFLOW expansion or say
> division/modulo expansion, but maybe my imagination is limited);
> so, if you think this is a good idea and the poly int in that case somehow
> guarantees the existing behavior (guess for signed it would be at least when
> not -fwrapv in action UB if the addition of the first POLY_INT_CST coeff
> and the others multiplied by the runtime value wraps around, but for
> unsigned is there a guarantee that if all the POLY_INT_CST coefficients
> don't have msb set that the resulting value will not have msb set either?

I hope so, but ...

Thanks,
Richard.

> > @@ -14434,7 +14436,7 @@ get_range_pos_neg (tree arg)
> >    if (TREE_CODE (arg) != SSA_NAME)
> >      return 3;
> >    value_range r;
> > -  while (!get_global_range_query ()->range_of_expr (r, arg)
> > +  while (!get_range_query (cfun)->range_of_expr (r, arg)
> >  	 || r.undefined_p () || r.varying_p ())
> >      {
> >        gimple *g = SSA_NAME_DEF_STMT (arg);
> 
> This hunk is certainly ok.

Re: [PATCH] tree-optimization/114151 - handle POLY_INT_CST in get_range_pos_neg

[Jakub Jelinek]

On Thu, Feb 29, 2024 at 02:08:19PM +0100, Richard Biener wrote:
> > So, wouldn't it be better to outline what you have above + POLY_INT_CST
> > handling into a helper function, which similarly to get_range_pos_neg
> > returns a bitmask, but rather than 1 bit for may be [0, max] and another bit for
> > may be [min, -1] you return 3 bits, 1 bit for may be [1, max], another for
> > may be [0, 0] and another for may be [min, -1]?
> > Also, I bet you actually want to handle TREE_UNSIGNED just as [0, 0]
> > and [1, max] ranges unlike get_range_pos_neg.
> 
> I'm just lazy and given TYPE_OVERFLOW_WRAPS (and thus unsigned) doesn't
> ever get here and I special-case integer_zerop it doesn't really matter
> that in these cases get_range_pos_neg isn't exactly what's wanted - I'm
> asking it only for those cases where it works just fine.

Just handling integer_zerop doesn't cover the case where the chrec
operand isn't INTEGER_CST, just includes zero in its range.  And I'd think
that is something quite common (sure, INTEGER_CST chrec operands are likely
more common than that) that we know that something isn't negative, or isn't
positive, or is non-negative, or is non-positive etc.

> > So perhaps
> >   int ret = 7;
> >   if (TYPE_UNSIGNED (TREE_TYPE (arg)))
> >     ret = 3;
> >   if (poly_int_tree_p (arg))
> >     {
> >       poly_wide_int w = wi::to_poly_wide (arg);
> >       if (known_lt (w, 0))
> > 	return 4;
> >       else if (known_eq (w, 0))
> > 	return 2;
> >       else if (known_gt (w, 0))
> > 	return 1;
> >       else
> > 	return 7;
> >     }
> >   value_range r;
> >   if (!get_range_query (cfun)->range_of_expr (r, arg)
> >       || r.undefined_p ())
> >     return ret;
> >   if (r.nonpositive_p ())
> >     ret &= ~1;
> >   if (r.nonzero_p ())
> >     ret &= ~2;
> >   if (r.nonnegative_p ())
> >     ret &= ~4;
> >   return ret;

And the above should be short/simple enough to be added even if it
just has a single user (ok, 2 in the same stmt).
Could be even just a lambda if there are no other uses for it,
so you would need to care less how to name it/where to declare etc.

> > I doubt POLY_INT_CST will appear on what the function is being called on
> > (types with scalar integral modes, mainly in .*_OVERFLOW expansion or say
> > division/modulo expansion, but maybe my imagination is limited);
> > so, if you think this is a good idea and the poly int in that case somehow
> > guarantees the existing behavior (guess for signed it would be at least when
> > not -fwrapv in action UB if the addition of the first POLY_INT_CST coeff
> > and the others multiplied by the runtime value wraps around, but for
> > unsigned is there a guarantee that if all the POLY_INT_CST coefficients
> > don't have msb set that the resulting value will not have msb set either?
> 
> I hope so, but ...

Let's wait for Richard there.
Anyway, if for the chrec case it only uses it on non-wrapping signed,
then the POLY_INT_CST handling is fine in there...

	Jakub