Re: [PATCH] match.pd: reassociate multiplications with constants

[Alexander Monakov <amonakov@ispras.ru>]

On Wed, 19 Jul 2017, Richard Biener wrote:
> >> --- a/gcc/match.pd
> >> +++ b/gcc/match.pd
> >> @@ -283,6 +283,20 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> >>          || mul != wi::min_value (TYPE_PRECISION (type), SIGNED))
> >>       { build_zero_cst (type); })))))
> >>
> >> +/* Combine successive multiplications.  Similar to above, but handling
> >> +   overflow is different.  */
> >> +(simplify
> >> + (mult (mult @0 INTEGER_CST@1) INTEGER_CST@2)
> >> + /* More specific rules can handle 0 and -1; skip them here to avoid
> >> +    wrong transformations for sanitized and saturating types.  */
> >> + (if (!integer_zerop (@2) && !integer_minus_onep (@2))
> >
> > I think integer_zerop (@2) should never happen here if you order the
> > pattern after [...]
> > which I think you do.  Why's @1 == -1 ok when sanitizing but not @2 == -1?

Because we ruled out @2 being 0 or -1. If @2 == 1 then @1 == -1 is fine,
otherwise abs(@2) > 1, thus if X * @1 overflows, so does X * (@1 * @2)
(assuming type range is from -2**L to 2**L - 1).

@2 == -1 is not ok because with @1 == -1 it may lead to wrong result for
saturating types if their range can be asymmetrical.  It would also
conceal intermediate overflow for sanitized ops.

> > So unless you can come up with a testcase that breaks I'd remove the
> > integer_zerop/integer_minus_onep checks.

Well, initially I suggested using 'gcc_checking_assert' to ensure that such a
pattern is not triggered under wrong circumstances (such as bisecting match.pd
by #if 0'ing parts of it), but I believe Marc said he would prefer plain ifs.
I agree with him that we shouldn't just implicitly depend on ordering, but
keep the ifs or use asserts.  Do you insist?  Are there other instances already
where GCC relies on ordering within match.pd for correctness?

> So for saturating types isn't the issue when @1 and @2 have opposite
> sign and the inner multiply would have saturated?

No, I think the only special case is @1 == @2 == -1, otherwise either @2 is
0 or 1, or @1 * @2 is larger in magnitude than @1 (unless @1 == 0), and
folding doesn't conceal an intermediate saturation.

> [how do saturated
> types behave with sign-changing multiplication/negation anyway?]

Actually I'm not sure they need to be handled here, afaict only fixed-point
types can be saturating, but then wouldn't constant operands be FIXED_CST?
(but there are already some instances in match.pd that anticipate
TYPE_SATURATING in patterns that match INTEGER_CST)

> > I think overflow in the constant multiplication is ok unless
> > TYPE_OVERFLOW_SANITIZED
> > (and can we have a ubsan testcase for that that would otherwise fail?).
> > It's not that we introduce new overflow here.

This is to allow deducing that X must be zero. Otherwise, exploiting
undefined overflow allows to fold X * CST1 * CST2 to just 0 if CST1 * CST2
overflows (this is what Marc originally suggested), but shouldn't we
rather keep X in the IR to later deduce that X is zero?

Alexander