On Wed, Sep 2, 2020 at 9:27 AM Marc Glisse <marc.gli...@inria.fr> wrote:
>
> On Wed, 2 Sep 2020, Richard Biener via Gcc wrote:
>
> > On Mon, Aug 24, 2020 at 8:20 AM Feng Xue OS via Gcc <gcc@gcc.gnu.org> wrote:
> >>
> >>>> There is a match-folding issue derived from pr94234. A piece of code
> >>>> like:
> >>>>
> >>>> int foo (int n)
> >>>> {
> >>>> int t1 = 8 * n;
> >>>> int t2 = 8 * (n - 1);
> >>>>
> >>>> return t1 - t2;
> >>>> }
> >>>>
> >>>> It can be perfectly caught by the rule "(A * C) +- (B * C) -> (A +- B)
> >>>> * C", and
> >>>> be folded to constant "8". But this folding will fail if both v1 and v2
> >>>> have
> >>>> multiple uses, as the following code.
> >>>>
> >>>> int foo (int n)
> >>>> {
> >>>> int t1 = 8 * n;
> >>>> int t2 = 8 * (n - 1);
> >>>>
> >>>> use_fn (t1, t2);
> >>>> return t1 - t2;
> >>>> }
> >>>>
> >>>> Given an expression with non-single-use operands, folding it will
> >>>> introduce
> >>>> duplicated computation in most situations, and is deemed to be
> >>>> unprofitable.
> >>>> But it is always beneficial if final result is a constant or existing
> >>>> SSA value.
> >>>>
> >>>> And the rule is:
> >>>> (simplify
> >>>> (plusminus (mult:cs@3 @0 @1) (mult:cs@4 @0 @2))
> >>>> (if ((!ANY_INTEGRAL_TYPE_P (type)
> >>>> || TYPE_OVERFLOW_WRAPS (type)
> >>>> || (INTEGRAL_TYPE_P (type)
> >>>> && tree_expr_nonzero_p (@0)
> >>>> && expr_not_equal_to (@0, wi::minus_one (TYPE_PRECISION
> >>>> (type)))))
> >>>> /* If @1 +- @2 is constant require a hard single-use on either
> >>>> original operand (but not on both). */
> >>>> && (single_use (@3) || single_use (@4))) <----- control whether
> >>>> match or not
> >>>> (mult (plusminus @1 @2) @0)))
> >>>>
> >>>> Current matcher only provides a way to check something before folding,
> >>>> but no mechanism to affect decision after folding. If has, for the above
> >>>> case, we can let it go when we find result is a constant.
> >>>
> >>> :s already has a counter-measure where it still folds if the output is at
> >>> most one operation. So this transformation has a counter-counter-measure
> >>> of checking single_use explicitly. And now we want a counter^3-measure...
> >>>
> >> Counter-measure is key factor to matching-cost. ":s" seems to be somewhat
> >> coarse-grained. And here we do need more control over it.
> >>
> >> But ideally, we could decouple these counter-measures from definitions of
> >> match-rule, and let gimple-matcher get a more reasonable match-or-not
> >> decision based on these counters. Anyway, it is another story.
> >>
> >>>> Like the way to describe input operand using flags, we could also add
> >>>> a new flag to specify this kind of constraint on output that we expect
> >>>> it is a simple gimple value.
> >>>>
> >>>> Proposed syntax is
> >>>>
> >>>> (opcode:v{ condition } ....)
> >>>>
> >>>> The char "v" stands for gimple value, if more descriptive, other char is
> >>>> preferred. "condition" enclosed by { } is an optional c-syntax condition
> >>>> expression. If present, only when "condition" is met, matcher will check
> >>>> whether folding result is a gimple value using
> >>>> gimple_simplified_result_is_gimple_val ().
> >>>>
> >>>> Since there is no SSA concept in GENERIC, this is only for GIMPLE-match,
> >>>> not GENERIC-match.
> >>>>
> >>>> With this syntax, the rule is changed to
> >>>>
> >>>> #Form 1:
> >>>> (simplify
> >>>> (plusminus (mult:cs@3 @0 @1) (mult:cs@4 @0 @2))
> >>>> (if ((!ANY_INTEGRAL_TYPE_P (type)
> >>>> || TYPE_OVERFLOW_WRAPS (type)
> >>>> || (INTEGRAL_TYPE_P (type)
> >>>> && tree_expr_nonzero_p (@0)
> >>>> && expr_not_equal_to (@0, wi::minus_one (TYPE_PRECISION
> >>>> (type))))))
> >>>> ( if (!single_use (@3) && !single_use (@4))
> >>>> (mult:v (plusminus @1 @2) @0)))
> >>>> (mult (plusminus @1 @2) @0)))))
> >>>
> >>> That seems to match what you can do with '!' now (that's very recent).
> >
> > It's also what :s does but a slight bit more "local". When any operand is
> > marked :s and it has more than a single-use we only allow simplifications
> > that do not require insertion of extra stmts. So basically the above
> > pattern
> > doesn't behave any different than if you omit your :v. Only if you'd
> > place :v on an inner expression there would be a difference. Correlating
> > the inner expression we'd not want to insert new expressions for with
> > a specific :s (or multiple ones) would be a more natural extension of what
> > :s provides.
> >
> > Thus, for the above case (Form 1), you do not need :v at all and :s works.
>
> Let's consider that multiplication is expensive. We have code like
> 5*X-3*X, which can be simplified to 2*X. However, if both 5*X and 3*X have
> other uses, that would increase the number of multiplications. :s would
> not block a simplification to 2*X, which is a single stmt. So the existing
> transformation has extra explicit checks for single_use. And those extra
> checks block the transformation even for 5*X-4*X -> X which does not
> increase the number of multiplications. Which is where '!' (or :v here)
> comes in.
Yeah, I guess the existing :s cannot capture the fact that in case one
multiplication is single-use only the transform is still clearly profitable,
saving the subtraction.
Well, as you said it will allow simplification to 2*X anyway.
> Or we could decide that the extra multiplication is not that bad if it
> saves an addition, simplifies the expression, possibly gains more insn
> parallelism, etc, in which case we could just drop the existing hard
> single_use check...
;)
it's all going to be heuristics because the decision is made
locally. If you consider the other two uses might be
5*X + 3*X then converting both to 2*X and 8*X should be
a win because we save one addition and one subtraction.
But that would require folding everything tentatively and
then applying some global costing ...
Richard.
> --
> Marc Glisse
