Prevent extract_muldiv from introducing an overflow (PR sanitizer/80800)

extract_muldiv folds 

  (n * 10000 * z) * 50

to

  (n * 500000) * z

which is a wrong transformation to do, because it may introduce an overflow.
This resulted in a ubsan false positive.  So we should just disable this
folding altogether.  Does the approach I took make sense?

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

2017-05-19  Marek Polacek  <polacek@redhat.com>

	PR sanitizer/80800
	* fold-const.c (extract_muldiv_1): Don't fold ((X * C1) * Y) * C
	to (X * C2) * Y.

	* c-c++-common/ubsan/pr80800.c: New test.
	* c-c++-common/Wduplicated-branches-1.c: Adjust an expression.


	Marek

On Fri, 19 May 2017, Marek Polacek wrote:

> extract_muldiv folds 
> 
>   (n * 10000 * z) * 50
> 
> to
> 
>   (n * 500000) * z
> 
> which is a wrong transformation to do, because it may introduce an overflow.
> This resulted in a ubsan false positive.  So we should just disable this
> folding altogether.  Does the approach I took make sense?
> 
> Bootstrapped/regtested on x86_64-linux, ok for trunk?

Didn't dig very far to identify extract_muldiv, but I guess it's either
of the following recursions that trigger?

      /* If we can extract our operation from the LHS, do so and return a
         new operation.  Likewise for the RHS from a MULT_EXPR.  
Otherwise,
         do something only if the second operand is a constant.  */
      if (same_p
          && (t1 = extract_muldiv (op0, c, code, wide_type,
                                   strict_overflow_p)) != 0)
        return fold_build2 (tcode, ctype, fold_convert (ctype, t1),
                            fold_convert (ctype, op1));
      else if (tcode == MULT_EXPR && code == MULT_EXPR
               && (t1 = extract_muldiv (op1, c, code, wide_type,
                                        strict_overflow_p)) != 0)
        return fold_build2 (tcode, ctype, fold_convert (ctype, op0),
                            fold_convert (ctype, t1));

thus I'd simply guard them with TYPE_OVERFLOW_WRAPS ().

In the end I think the whole extract_muldiv mess should be truncated
down to what its name suggest - identifying and removing mul-div
cancellations.

It's for example not clear whether the recursion above assumes
TYPE_OVERFLOW_UNDEFINED (it passes a wide_type .. widening is only
ok if there's no overflow).

Richard.


> 2017-05-19  Marek Polacek  <polacek@redhat.com>
> 
> 	PR sanitizer/80800
> 	* fold-const.c (extract_muldiv_1): Don't fold ((X * C1) * Y) * C
> 	to (X * C2) * Y.
> 
> 	* c-c++-common/ubsan/pr80800.c: New test.
> 	* c-c++-common/Wduplicated-branches-1.c: Adjust an expression.
> 
> diff --git gcc/fold-const.c gcc/fold-const.c
> index 19aa722..e525c2d 100644
> --- gcc/fold-const.c
> +++ gcc/fold-const.c
> @@ -6260,6 +6260,17 @@ extract_muldiv_1 (tree t, tree c, enum tree_code code, tree wide_type,
>        break;
>  
>      case MULT_EXPR:
> +      /* ((X * C1) * Y) * C
> +	 cannot be reduced to
> +	 (X * C2) * Y (where C2 == C * C1)
> +	 because that can introduce an overflow.  */
> +      if (same_p
> +	  && op0 != NULL_TREE
> +	  && TREE_CODE (op0) == MULT_EXPR
> +	  && TREE_CODE (TREE_OPERAND (op0, 1)) == INTEGER_CST
> +	  && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (t)))
> +	break;
> +
>        /* We have a special case here if we are doing something like
>  	 (C * 8) % 4 since we know that's zero.  */
>        if ((code == TRUNC_MOD_EXPR || code == CEIL_MOD_EXPR
> diff --git gcc/testsuite/c-c++-common/Wduplicated-branches-1.c gcc/testsuite/c-c++-common/Wduplicated-branches-1.c
> index c0b93fc..7c5062d 100644
> --- gcc/testsuite/c-c++-common/Wduplicated-branches-1.c
> +++ gcc/testsuite/c-c++-common/Wduplicated-branches-1.c
> @@ -89,7 +89,7 @@ f (int i, int *p)
>    if (i == 8) /* { dg-warning "this condition has identical branches" } */
>      return i * 8 * i * 8;
>    else
> -    return 8 * i * 8 * i;
> +    return i * 8 * i * 8;
>  
>  
>    if (i == 9) /* { dg-warning "this condition has identical branches" } */
> diff --git gcc/testsuite/c-c++-common/ubsan/pr80800.c gcc/testsuite/c-c++-common/ubsan/pr80800.c
> index e69de29..992c136 100644
> --- gcc/testsuite/c-c++-common/ubsan/pr80800.c
> +++ gcc/testsuite/c-c++-common/ubsan/pr80800.c
> @@ -0,0 +1,25 @@
> +/* PR sanitizer/80800 */
> +/* { dg-do run } */
> +/* { dg-options "-fsanitize=undefined -fsanitize-undefined-trap-on-error" } */
> +
> +int n = 20000;
> +int z = 0;
> +
> +int
> +fn1 (void)
> +{
> +  return (n * 10000 * z) * 50;
> +}
> +
> +int
> +fn2 (void)
> +{
> +  return (10000 * n * z) * 50;
> +}
> +
> +int
> +main ()
> +{
> +  fn1 ();
> +  fn2 ();
> +}
> 
> 	Marek
> 
>