On Wed, Sep 2, 2020 at 9:35 AM Feng Xue OS <f...@os.amperecomputing.com> 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.
>
> Between ":s" and ":v", there is a subtle difference. ":s" only ensures
> interior
> transform does not insert any new stmts, but this is not true for final one.
>
> Code snippet generated for (A * C) +- (B * C) -> (A+-B) * C:
>
> gimple_seq *lseq = seq;
> if (lseq
> && (!single_use (captures[0])
> || !single_use (captures[3])))
> lseq = NULL;
> if (__builtin_expect (!dbg_cnt (match), 0)) goto next_after_fail621;
> if (__builtin_expect (dump_file && (dump_flags & TDF_FOLDING), 0))
> fprintf (dump_file, "Applying pattern %s:%d, %s:%d\n", "match.pd", 2581,
> __FILE__, __LINE__);
> {
> res_op->set_op (MULT_EXPR, type, 2);
> {
> tree _o1[2], _r1;
> _o1[0] = captures[2];
> _o1[1] = captures[4];
> gimple_match_op tem_op (res_op->cond.any_else (), plusminus,
> TREE_TYPE (_o1[0]), _o1[0], _o1[1]);
> tem_op.resimplify (lseq, valueize);
>
> // lseq has been already set to NULL as ":s" is specified, so
> // interior result is expected to be simple value.
> _r1 = maybe_push_res_to_seq (&tem_op, lseq);
>
> if (!_r1) goto next_after_fail621;
> res_op->ops[0] = _r1;
> }
> res_op->ops[1] = captures[1];
> res_op->resimplify (lseq, valueize);
>
> // But final result is not checked, and it could be mapped
> // to binary operation.
> return true;
> }
>
> The new specifier "!" is nearly same as ":v", but also does not
> check final result.
But the final result is irrelevant as we're supposed to replace
the original expression anyway. The only thing there is
relative cost of add vs. mult.
Richard.
>
> Thanks,
> Feng
