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

[Jakub Jelinek <jakub@redhat.com>]

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