On Wed, Jul 19, 2017 at 4:39 PM, Alexander Monakov <amona...@ispras.ru> wrote:
> 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.
I'm not so much worried about false negatives for ubsan -- it's ubsan
implementations
fault that it runs so late after folding.
>> > 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?
Not for correctness AFAIK but for optimization. IIRC I implemented strict
ordering because of a bug.
>> 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.
Ok, but you don't check for @1 == @2 == -1 because you rely on
the subtree being folded (we rely on this for optimization, not sure we should
rely on this for correctness -- only checking @1 == -1 is if course
conservatively
correct).
Note that with folding X * -1 to -X a related pattern would optimize
(mult (negate X) CST)
and (negate (mult X CST)).
>> [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)
At least
/* In a non-aggregate type, indicates a saturating type. */
#define TYPE_SATURATING(NODE) \
(TREE_NOT_CHECK4 (NODE, RECORD_TYPE, UNION_TYPE, QUAL_UNION_TYPE,
ARRAY_TYPE)->base.u.bits.saturating_flag)
suggests that non-fixed point saturating types are possible. Maybe no such
ones exist though. fixed-point math has other issues (but I think at least
has symmetric negative/positive ranges).
>> > 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?
I don't think we should care here. After all we could immediately fold
X * CST1 * CST2 to zero if CST1 * CST2 overflows and overflow invokes
undefined behavior, right in this reassoc pattern.
So -- I'd prefer to just give up for TYPE_SATURATING (as you say currently
it can't happen anyway because the only saturating types we have are
fixed-point),
thus remove the zero/minus_one checks (not worry about false positive in ubsan).
Richard.
>
> Alexander
