match.pd: Optimize MIN_EXPR <addr1, addr2> etc. addr1 < addr2 would be simplified [PR102951]

  Hi!

This patch outlines the decision whether address comparison can be folded
or not from the match.pd simple comparison simplification and uses it
both there and in a new minmax simplification, such that we fold e.g.
  MAX (&a[2], &a[1])
etc.
Some of the Wstringop-overflow-62.c changes might look weird, but that
seems to be mainly due to gimple_fold_builtin_memset not bothering to
copy over location, will fix that incrementally.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2021-10-28  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/102951
	* fold-const.h (address_compare): Declare.
	* fold-const.c (address_compare): New function.
	* match.pd (cmp (convert1?@2 addr@0) (convert2? addr@1)): Use
	address_compare helper.
	(minmax cmp (convert1?@2 addr@0) (convert2?@3 addr@1)): New
	simplification.

	* gcc.dg/tree-ssa/pr102951.c: New test.
	* gcc.dg/Wstringop-overflow-62.c: Adjust expected diagnostics.


	Jakub
  

On Thu, 28 Oct 2021, Jakub Jelinek wrote:

> Hi!
> 
> This patch outlines the decision whether address comparison can be folded
> or not from the match.pd simple comparison simplification and uses it
> both there and in a new minmax simplification, such that we fold e.g.
>   MAX (&a[2], &a[1])
> etc.
> Some of the Wstringop-overflow-62.c changes might look weird, but that
> seems to be mainly due to gimple_fold_builtin_memset not bothering to
> copy over location, will fix that incrementally.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

OK.

Thanks,
Richard.

> 2021-10-28  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/102951
> 	* fold-const.h (address_compare): Declare.
> 	* fold-const.c (address_compare): New function.
> 	* match.pd (cmp (convert1?@2 addr@0) (convert2? addr@1)): Use
> 	address_compare helper.
> 	(minmax cmp (convert1?@2 addr@0) (convert2?@3 addr@1)): New
> 	simplification.
> 
> 	* gcc.dg/tree-ssa/pr102951.c: New test.
> 	* gcc.dg/Wstringop-overflow-62.c: Adjust expected diagnostics.
> 
> --- gcc/fold-const.h.jj	2021-06-14 12:27:18.572411152 +0200
> +++ gcc/fold-const.h	2021-10-27 11:54:50.781412075 +0200
> @@ -213,6 +213,8 @@ extern bool negate_mathfn_p (combined_fn
>  extern const char *getbyterep (tree, unsigned HOST_WIDE_INT *);
>  extern const char *c_getstr (tree);
>  extern wide_int tree_nonzero_bits (const_tree);
> +extern int address_compare (tree_code, tree, tree, tree, tree &, tree &,
> +			    poly_int64 &, poly_int64 &, bool);
>  
>  /* Return OFF converted to a pointer offset type suitable as offset for
>     POINTER_PLUS_EXPR.  Use location LOC for this conversion.  */
> --- gcc/fold-const.c.jj	2021-08-11 23:43:59.195893727 +0200
> +++ gcc/fold-const.c	2021-10-27 12:16:26.504267476 +0200
> @@ -16473,6 +16473,132 @@ tree_nonzero_bits (const_tree t)
>    return wi::shwi (-1, TYPE_PRECISION (TREE_TYPE (t)));
>  }
>  
> +/* Helper function for address compare simplifications in match.pd.
> +   OP0 and OP1 are ADDR_EXPR operands being compared by CODE.
> +   BASE0, BASE1, OFF0 and OFF1 are set by the function.
> +   GENERIC is true if GENERIC folding and false for GIMPLE folding.
> +   Returns 0 if OP0 is known to be unequal to OP1 regardless of OFF{0,1},
> +   1 if bases are known to be equal and OP0 cmp OP1 depends on OFF0 cmp OFF1,
> +   and 2 if unknown.  */
> +
> +int
> +address_compare (tree_code code, tree type, tree op0, tree op1,
> +		 tree &base0, tree &base1, poly_int64 &off0, poly_int64 &off1,
> +		 bool generic)
> +{
> +  gcc_checking_assert (TREE_CODE (op0) == ADDR_EXPR);
> +  gcc_checking_assert (TREE_CODE (op1) == ADDR_EXPR);
> +  base0 = get_addr_base_and_unit_offset (TREE_OPERAND (op0, 0), &off0);
> +  base1 = get_addr_base_and_unit_offset (TREE_OPERAND (op1, 0), &off1);
> +  if (base0 && TREE_CODE (base0) == MEM_REF)
> +    {
> +      off0 += mem_ref_offset (base0).force_shwi ();
> +      base0 = TREE_OPERAND (base0, 0);
> +    }
> +  if (base1 && TREE_CODE (base1) == MEM_REF)
> +    {
> +      off1 += mem_ref_offset (base1).force_shwi ();
> +      base1 = TREE_OPERAND (base1, 0);
> +    }
> +  if (base0 == NULL_TREE || base1 == NULL_TREE)
> +    return 2;
> +
> +  int equal = 2;
> +  /* Punt in GENERIC on variables with value expressions;
> +     the value expressions might point to fields/elements
> +     of other vars etc.  */
> +  if (generic
> +      && ((VAR_P (base0) && DECL_HAS_VALUE_EXPR_P (base0))
> +	  || (VAR_P (base1) && DECL_HAS_VALUE_EXPR_P (base1))))
> +    return 2;
> +  else if (decl_in_symtab_p (base0) && decl_in_symtab_p (base1))
> +    {
> +      symtab_node *node0 = symtab_node::get_create (base0);
> +      symtab_node *node1 = symtab_node::get_create (base1);
> +      equal = node0->equal_address_to (node1);
> +    }
> +  else if ((DECL_P (base0)
> +	    || TREE_CODE (base0) == SSA_NAME
> +	    || TREE_CODE (base0) == STRING_CST)
> +	   && (DECL_P (base1)
> +	       || TREE_CODE (base1) == SSA_NAME
> +	       || TREE_CODE (base1) == STRING_CST))
> +    equal = (base0 == base1);
> +  if (equal == 1)
> +    {
> +      if (code == EQ_EXPR
> +	  || code == NE_EXPR
> +	  /* If the offsets are equal we can ignore overflow.  */
> +	  || known_eq (off0, off1)
> +	  || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0))
> +	  /* Or if we compare using pointers to decls or strings.  */
> +	  || (POINTER_TYPE_P (type)
> +	      && (DECL_P (base0) || TREE_CODE (base0) == STRING_CST)))
> +	return 1;
> +      return 2;
> +    }
> +  if (equal != 0)
> +    return equal;
> +  if (code != EQ_EXPR && code != NE_EXPR)
> +    return 2;
> +
> +  HOST_WIDE_INT ioff0 = -1, ioff1 = -1;
> +  off0.is_constant (&ioff0);
> +  off1.is_constant (&ioff1);
> +  if ((DECL_P (base0) && TREE_CODE (base1) == STRING_CST)
> +       || (TREE_CODE (base0) == STRING_CST && DECL_P (base1))
> +       || (TREE_CODE (base0) == STRING_CST
> +	   && TREE_CODE (base1) == STRING_CST
> +	   && ioff0 >= 0 && ioff1 >= 0
> +	   && ioff0 < TREE_STRING_LENGTH (base0)
> +	   && ioff1 < TREE_STRING_LENGTH (base1)
> +	  /* This is a too conservative test that the STRING_CSTs
> +	     will not end up being string-merged.  */
> +	   && strncmp (TREE_STRING_POINTER (base0) + ioff0,
> +		       TREE_STRING_POINTER (base1) + ioff1,
> +		       MIN (TREE_STRING_LENGTH (base0) - ioff0,
> +			    TREE_STRING_LENGTH (base1) - ioff1)) != 0))
> +    ;
> +  else if (!DECL_P (base0) || !DECL_P (base1))
> +    return 2;
> +  /* If this is a pointer comparison, ignore for now even
> +     valid equalities where one pointer is the offset zero
> +     of one object and the other to one past end of another one.  */
> +  else if (!INTEGRAL_TYPE_P (type))
> +    ;
> +  /* Assume that automatic variables can't be adjacent to global
> +     variables.  */
> +  else if (is_global_var (base0) != is_global_var (base1))
> +    ;
> +  else
> +    {
> +      tree sz0 = DECL_SIZE_UNIT (base0);
> +      tree sz1 = DECL_SIZE_UNIT (base1);
> +      /* If sizes are unknown, e.g. VLA or not representable, punt.  */
> +      if (!tree_fits_poly_int64_p (sz0) || !tree_fits_poly_int64_p (sz1))
> +	return 2;
> +
> +      poly_int64 size0 = tree_to_poly_int64 (sz0);
> +      poly_int64 size1 = tree_to_poly_int64 (sz1);
> +      /* If one offset is pointing (or could be) to the beginning of one
> +	 object and the other is pointing to one past the last byte of the
> +	 other object, punt.  */
> +      if (maybe_eq (off0, 0) && maybe_eq (off1, size1))
> +	equal = 2;
> +      else if (maybe_eq (off1, 0) && maybe_eq (off0, size0))
> +	equal = 2;
> +      /* If both offsets are the same, there are some cases we know that are
> +	 ok.  Either if we know they aren't zero, or if we know both sizes
> +	 are no zero.  */
> +      if (equal == 2
> +	  && known_eq (off0, off1)
> +	  && (known_ne (off0, 0)
> +	      || (known_ne (size0, 0) && known_ne (size1, 0))))
> +	equal = 0;
> +     }
> +  return equal;
> +}
> +
>  #if CHECKING_P
>  
>  namespace selftest {
> --- gcc/match.pd.jj	2021-10-27 09:00:28.000000000 +0200
> +++ gcc/match.pd	2021-10-27 12:10:15.713455445 +0200
> @@ -3009,6 +3009,30 @@ (define_operator_list COND_TERNARY
>      @0
>      @2)))
>  
> +/* Simplify min (&var[off0], &var[off1]) etc. depending on whether
> +   the addresses are known to be less, equal or greater.  */
> +(for minmax (min max)
> +     cmp (lt gt)
> + (simplify
> +  (minmax (convert1?@2 addr@0) (convert2?@3 addr@1))
> +  (with
> +   {
> +     poly_int64 off0, off1;
> +     tree base0, base1;
> +     int equal = address_compare (cmp, TREE_TYPE (@2), @0, @1, base0, base1,
> +				  off0, off1, GENERIC);
> +   }
> +   (if (equal == 1)
> +    (if (minmax == MIN_EXPR)
> +     (if (known_le (off0, off1))
> +      @2
> +      (if (known_gt (off0, off1))
> +       @3))
> +     (if (known_ge (off0, off1))
> +      @2
> +      (if (known_lt (off0, off1))
> +       @3)))))))
> +
>  /* (convert (minmax ((convert (x) c)))) -> minmax (x c) if x is promoted
>     and the outer convert demotes the expression back to x's type.  */
>  (for minmax (min max)
> @@ -5291,132 +5315,30 @@ (define_operator_list COND_TERNARY
>    (with
>     {
>       poly_int64 off0, off1;
> -     tree base0 = get_addr_base_and_unit_offset (TREE_OPERAND (@0, 0), &off0);
> -     tree base1 = get_addr_base_and_unit_offset (TREE_OPERAND (@1, 0), &off1);
> -     if (base0 && TREE_CODE (base0) == MEM_REF)
> -       {
> -	 off0 += mem_ref_offset (base0).force_shwi ();
> -         base0 = TREE_OPERAND (base0, 0);
> -       }
> -     if (base1 && TREE_CODE (base1) == MEM_REF)
> -       {
> -	 off1 += mem_ref_offset (base1).force_shwi ();
> -         base1 = TREE_OPERAND (base1, 0);
> -       }
> +     tree base0, base1;
> +     int equal = address_compare (cmp, TREE_TYPE (@2), @0, @1, base0, base1,
> +				  off0, off1, GENERIC);
>     }
> -   (if (base0 && base1)
> -    (with
> -     {
> -       int equal = 2;
> -       /* Punt in GENERIC on variables with value expressions;
> -	  the value expressions might point to fields/elements
> -	  of other vars etc.  */
> -       if (GENERIC
> -	   && ((VAR_P (base0) && DECL_HAS_VALUE_EXPR_P (base0))
> -	       || (VAR_P (base1) && DECL_HAS_VALUE_EXPR_P (base1))))
> -	 ;
> -       else if (decl_in_symtab_p (base0)
> -		&& decl_in_symtab_p (base1))
> -         equal = symtab_node::get_create (base0)
> -	           ->equal_address_to (symtab_node::get_create (base1));
> -       else if ((DECL_P (base0)
> -		 || TREE_CODE (base0) == SSA_NAME
> -		 || TREE_CODE (base0) == STRING_CST)
> -		&& (DECL_P (base1)
> -		    || TREE_CODE (base1) == SSA_NAME
> -		    || TREE_CODE (base1) == STRING_CST))
> -         equal = (base0 == base1);
> -       if (equal == 0)
> -	 {
> -	   HOST_WIDE_INT ioff0 = -1, ioff1 = -1;
> -	   off0.is_constant (&ioff0);
> -	   off1.is_constant (&ioff1);
> -	   if ((DECL_P (base0) && TREE_CODE (base1) == STRING_CST)
> -	       || (TREE_CODE (base0) == STRING_CST && DECL_P (base1))
> -	       || (TREE_CODE (base0) == STRING_CST
> -		   && TREE_CODE (base1) == STRING_CST
> -		   && ioff0 >= 0 && ioff1 >= 0
> -		   && ioff0 < TREE_STRING_LENGTH (base0)
> -		   && ioff1 < TREE_STRING_LENGTH (base1)
> -		   /* This is a too conservative test that the STRING_CSTs
> -		      will not end up being string-merged.  */
> -		   && strncmp (TREE_STRING_POINTER (base0) + ioff0,
> -			       TREE_STRING_POINTER (base1) + ioff1,
> -			       MIN (TREE_STRING_LENGTH (base0) - ioff0,
> -				    TREE_STRING_LENGTH (base1) - ioff1)) != 0))
> -	     ;
> -	   else if (!DECL_P (base0) || !DECL_P (base1))
> -	     equal = 2;
> -	   else if (cmp != EQ_EXPR && cmp != NE_EXPR)
> -	     equal = 2;
> -	   /* If this is a pointer comparison, ignore for now even
> -	      valid equalities where one pointer is the offset zero
> -	      of one object and the other to one past end of another one.  */
> -	   else if (!INTEGRAL_TYPE_P (TREE_TYPE (@2)))
> -	     ;
> -	   /* Assume that automatic variables can't be adjacent to global
> -	      variables.  */
> -	   else if (is_global_var (base0) != is_global_var (base1))
> -	     ;
> -	   else
> -	     {
> -	       tree sz0 = DECL_SIZE_UNIT (base0);
> -	       tree sz1 = DECL_SIZE_UNIT (base1);
> -	       /* If sizes are unknown, e.g. VLA or not representable,
> -		  punt.  */
> -	       if (!tree_fits_poly_int64_p (sz0)
> -		   || !tree_fits_poly_int64_p (sz1))
> -		 equal = 2;
> -	       else
> -		 {
> -		   poly_int64 size0 = tree_to_poly_int64 (sz0);
> -		   poly_int64 size1 = tree_to_poly_int64 (sz1);
> -		   /* If one offset is pointing (or could be) to the beginning
> -		      of one object and the other is pointing to one past the
> -		      last byte of the other object, punt.  */
> -		   if (maybe_eq (off0, 0) && maybe_eq (off1, size1))
> -		     equal = 2;
> -		   else if (maybe_eq (off1, 0) && maybe_eq (off0, size0))
> -		     equal = 2;
> -		   /* If both offsets are the same, there are some cases
> -		      we know that are ok.  Either if we know they aren't
> -		      zero, or if we know both sizes are no zero.  */
> -		   if (equal == 2
> -		       && known_eq (off0, off1)
> -		       && (known_ne (off0, 0)
> -			   || (known_ne (size0, 0) && known_ne (size1, 0))))
> -		     equal = 0;
> -		 }
> -	     }
> -	 }
> -     }
> -     (if (equal == 1
> -	  && (cmp == EQ_EXPR || cmp == NE_EXPR
> -	      /* If the offsets are equal we can ignore overflow.  */
> -	      || known_eq (off0, off1)
> -	      || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))
> -		 /* Or if we compare using pointers to decls or strings.  */
> -	      || (POINTER_TYPE_P (TREE_TYPE (@2))
> -		  && (DECL_P (base0) || TREE_CODE (base0) == STRING_CST))))
> -      (switch
> -       (if (cmp == EQ_EXPR && (known_eq (off0, off1) || known_ne (off0, off1)))
> -	{ constant_boolean_node (known_eq (off0, off1), type); })
> -       (if (cmp == NE_EXPR && (known_eq (off0, off1) || known_ne (off0, off1)))
> -	{ constant_boolean_node (known_ne (off0, off1), type); })
> -       (if (cmp == LT_EXPR && (known_lt (off0, off1) || known_ge (off0, off1)))
> -	{ constant_boolean_node (known_lt (off0, off1), type); })
> -       (if (cmp == LE_EXPR && (known_le (off0, off1) || known_gt (off0, off1)))
> -	{ constant_boolean_node (known_le (off0, off1), type); })
> -       (if (cmp == GE_EXPR && (known_ge (off0, off1) || known_lt (off0, off1)))
> -	{ constant_boolean_node (known_ge (off0, off1), type); })
> -       (if (cmp == GT_EXPR && (known_gt (off0, off1) || known_le (off0, off1)))
> -	{ constant_boolean_node (known_gt (off0, off1), type); }))
> -      (if (equal == 0)
> -	(switch
> -	 (if (cmp == EQ_EXPR)
> -	  { constant_boolean_node (false, type); })
> -	 (if (cmp == NE_EXPR)
> -	  { constant_boolean_node (true, type); })))))))))
> +   (if (equal == 1)
> +    (switch
> +     (if (cmp == EQ_EXPR && (known_eq (off0, off1) || known_ne (off0, off1)))
> +      { constant_boolean_node (known_eq (off0, off1), type); })
> +     (if (cmp == NE_EXPR && (known_eq (off0, off1) || known_ne (off0, off1)))
> +      { constant_boolean_node (known_ne (off0, off1), type); })
> +     (if (cmp == LT_EXPR && (known_lt (off0, off1) || known_ge (off0, off1)))
> +      { constant_boolean_node (known_lt (off0, off1), type); })
> +     (if (cmp == LE_EXPR && (known_le (off0, off1) || known_gt (off0, off1)))
> +      { constant_boolean_node (known_le (off0, off1), type); })
> +     (if (cmp == GE_EXPR && (known_ge (off0, off1) || known_lt (off0, off1)))
> +      { constant_boolean_node (known_ge (off0, off1), type); })
> +     (if (cmp == GT_EXPR && (known_gt (off0, off1) || known_le (off0, off1)))
> +      { constant_boolean_node (known_gt (off0, off1), type); }))
> +    (if (equal == 0)
> +     (switch
> +      (if (cmp == EQ_EXPR)
> +       { constant_boolean_node (false, type); })
> +      (if (cmp == NE_EXPR)
> +       { constant_boolean_node (true, type); })))))))
>  
>  /* Simplify pointer equality compares using PTA.  */
>  (for neeq (ne eq)
> --- gcc/testsuite/gcc.dg/tree-ssa/pr102951.c.jj	2021-10-27 12:33:16.586143898 +0200
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr102951.c	2021-10-27 12:33:00.880363448 +0200
> @@ -0,0 +1,41 @@
> +/* PR tree-optimization/102951 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-ccp1" } */
> +/* { dg-final { scan-tree-dump-times "return \&a\\\[1\\\];" 2 "ccp1" } } */
> +/* { dg-final { scan-tree-dump-times "return \&a\\\[4\\\];" 2 "ccp1" } } */
> +/* { dg-final { scan-tree-dump-not "MIN_EXPR" "ccp1" } } */
> +/* { dg-final { scan-tree-dump-not "MAX_EXPR" "ccp1" } } */
> +
> +extern int a[5];
> +
> +int *
> +foo (void)
> +{
> +  int *p1 = &a[1];
> +  int *p2 = &a[2];
> +  return p1 < p2 ? p1 : p2;
> +}
> +
> +int *
> +bar (void)
> +{
> +  int *p1 = &a[1];
> +  int *p2 = &a[2];
> +  return p1 <= p2 ? p1 : p2;
> +}
> +
> +int *
> +baz (void)
> +{
> +  int *p1 = &a[3];
> +  int *p2 = &a[4];
> +  return p1 > p2 ? p1 : p2;
> +}
> +
> +int *
> +qux (void)
> +{
> +  int *p1 = &a[3];
> +  int *p2 = &a[4];
> +  return p1 >= p2 ? p1 : p2;
> +}
> --- gcc/testsuite/gcc.dg/Wstringop-overflow-62.c.jj	2021-09-18 09:44:31.000000000 +0200
> +++ gcc/testsuite/gcc.dg/Wstringop-overflow-62.c	2021-10-28 12:24:21.909780099 +0200
> @@ -217,14 +217,14 @@ void test_max (void)
>    {
>      /* Exercise both pointers pointing to the same object plus constant
>         offset.  */
> -    char a2[2];               // { dg-message "at offset 1 into destination object 'a2' of size 2" "note" }
> +    char a2[2];
>      char *pi = a2 + 1;
>      char *pj = a2 + 2;
>  
>      char *q = MAX (pi, pj);
>  
> -    memset (q, 0, 1);
> -    memset (q, 0, 2);         // { dg-warning "writing 2 bytes into a region of size 1 " }
> +    memset (q, 0, 1);         // { dg-warning "writing 1 byte into a region of size 0 " "" { target *-*-* } 0 }
> +    memset (q, 0, 2);         // { dg-warning "writing 2 bytes into a region of size 0 " }
>    }
>  
>    {
> @@ -345,7 +345,7 @@ void test_max (void)
>         not reflected in the determaxed offset).  */
>      char *q = MAX (p1, p2);
>  
> -    memset (q, 0, 1);         // { dg-warning "writing 1 byte into a region of size 0 " }
> +    memset (q, 0, 1);
>    }
>  
>    {
> 
> 	Jakub
> 
>