Re: [PATCH] tree-optimization/114074 - CHREC multiplication and undefined overflow

[Jakub Jelinek <jakub@redhat.com>]

On Mon, Feb 26, 2024 at 03:15:02PM +0100, Richard Biener wrote:
> When folding a multiply CHRECs are handled like {a, +, b} * c
> is {a*c, +, b*c} but that isn't generally correct when overflow
> invokes undefined behavior.  The following uses unsigned arithmetic
> unless either a is zero or a and b have the same sign.
> 
> I've used simple early outs for INTEGER_CSTs and otherwise use
> a range-query since we lack a tree_expr_nonpositive_p.
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
> 
> I'm not sure it's worth using ranger, there might be also more
> cases where the integer multiply is OK, say when abs (A) > abs (B).
> But also {-2, +, 2}, but not for {1, +, -1} for example.

So, given that we found that get_range_pos_neg is not what you want,
I think the patch is ok, except a minor nit

> @@ -428,10 +434,41 @@ chrec_fold_multiply (tree type,
>  	  if (integer_zerop (op1))
>  	    return build_int_cst (type, 0);
>  
> -	  return build_polynomial_chrec
> -	    (CHREC_VARIABLE (op0),
> -	     chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
> -	     chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
> +	  /* When overflow is undefined and CHREC_LEFT/RIGHT do not have the
> +	     same sign or CHREC_LEFT is zero then folding the multiply into
> +	     the addition does not have the same behavior on overflow.  Use
> +	     unsigned arithmetic in that case.  */
> +	  value_range rl, rr;
> +	  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 ()))))
> +	    return build_polynomial_chrec
> +		     (CHREC_VARIABLE (op0),
> +		      chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
> +		      chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
> +	  else
> +	    {
> +	      tree utype = unsigned_type_for (type);
> +	      op1 = chrec_convert_rhs (utype, op1);
> +	      tree tem = build_polynomial_chrec
> +		(CHREC_VARIABLE (op0),
> +		 chrec_fold_multiply
> +		   (utype, chrec_convert_rhs (utype, CHREC_LEFT (op0)), op1),
> +		 chrec_fold_multiply
> +		   (utype, chrec_convert_rhs (utype, CHREC_RIGHT (op0)), op1));
> +	      return chrec_convert_rhs (type, tem);

When you touch these, can you please rewrite it to more readable code with
temporaries, instead of the ugly calls with ( on different line from the
function name?
	    {
	      tree left = chrec_fold_multiply (type, CHREC_LEFT (op0), op1);
	      tree right = chrec_fold_multiply (type, CHREC_RIGHT (op0), op1);
	      return build_polynomial_chrec (CHREC_VARIABLE (op0),
					     left, right);
	    }
and
	      tree left = chrec_convert_rhs (utype, CHREC_LEFT (op0));
	      left = chrec_fold_multiply (utype, left, op1);
	      tree right = chrec_convert_rhs (utype, CHREC_RIGHT (op0));
	      right = chrec_fold_multiply (utype, right, op1);
	      tree tem = build_polynomial_chrec (CHREC_VARIABLE (op0),
						 left, right);
	      return chrec_convert_rhs (type, tem);
?

	Jakub