[RFC] Add new flag to specify output constraint in match.pd

[Richard Biener]

On Wed, Sep 2, 2020 at 9:35 AM Feng Xue OS <fxue@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