Re: [GSoC] decision tree first steps

[Richard Biener <richard dot guenther at gmail dot com>]

On Wed, Jun 18, 2014 at 11:21 AM, Prathamesh Kulkarni
<bilbotheelffriend@gmail.com> wrote:
> On Tue, Jun 17, 2014 at 3:15 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>>
>> On Tue, Jun 17, 2014 at 12:21 AM, Prathamesh Kulkarni
>> <bilbotheelffriend@gmail.com> wrote:
>> > On Mon, Jun 16, 2014 at 4:45 PM, Richard Biener
>> > <richard.guenther@gmail.com> wrote:
>> >>
>> >> > * Patterns requiring GENERIC support like cond_expr
>> >> > I am not sure about how to handle these patterns. I was thinking about
>> >> > handling them after we have
>> >> > GENERIC code generation in place.
>> >>
>> >> Yeah, though handling GENERIC for matching is as simple as
>> >> emitting the code check twice, the 2nd check off the an else
>> >> from the if (TREE_CODE (op) == SSA_NAME).  That is,
>> >> arrange for expr::gen_gimple_match_dt to emit
>> >>
>> >>    if (TREE_CODE (...) == SSA_NAME)
>> >>      {
>> >>         gimple def_stmt = SSA_NAME_DEF_STMT (...);
>> >>         if (is_gimple_assign (def_stmt) && gimple_assign_rhs_code
>> >> (def_stmt) == <code>)
>> >>           {
>> >>   ....
>> >>      }
>> >>    else (TREE_CODE (...) == <code>)
>> >>      {
>> >>   ....
>> >>      }
>> >>
>> >> which would require some refactoring in the generator.  As for refactoring
>> >> it I'd not hook the gen_gimple_match_dt off the AST operands but
>> >> inline it in the decision tree traversal routine - that also makes the
>> >> commoning above easier.
>> > Thanks, I shall get started on this.
>>
>> Good.  You also miss the special-casing of REALPART_EXPR,
>> IMAGPART_EXPR, VIEW_CONVERT_EXPR and BIT_FIELD_REF
>> operand extraction as you say below.
>>
>> >>
>> >> Btw, I checked what we generate for (bogus)
>> >>
>> >> (match_and_simplify
>> >>   (MINUS_EXPR (PLUS_EXPR@2 @0 @1) @2)
>> >>   @1)
>> >>
>> >> and the DT looks like
>> >>
>> >> root, 1
>> >> |--operand: MINUS_EXPR, 1
>> >> |----operand: true, 1
>> >> |------operand: PLUS_EXPR, 1
>> >> |--------operand: true, 1
>> >> |----------operand: true, 1
>> >> |------------operand: match(1), 1
>> >> |--------------simplify_0, 0
>> >>
>> >> though I expected
>> >>
>> >> root, 1
>> >> |--operand: MINUS_EXPR, 1
>> >> |----operand: PLUS_EXPR, 1
>> >> |------operand: true, 1
>> >> |--------operand: true, 1
>> >> |----------operand: match(1), 1
>> >> |------------simplify_0, 0
>> >>
>> >> that is, I wonder where the extra "true" comes from.
>> > Thanks, fixed it in the current patch.
>>
>> Thanks.
>>
>> >>
>> >>
>> >> For
>> >>
>> >> (match_and_simplify
>> >>   (MINUS_EXPR @2 (PLUS_EXPR@2 @0 @1))
>> >>   @1)
>> >>
>> >> I get
>> >>
>> >> root, 1
>> >> |--operand: MINUS_EXPR, 1
>> >> |----operand: true, 1
>> >> |------operand: match(1), 1
>> >> |--------operand: PLUS_EXPR, 1
>> >> |----------operand: true, 1
>> >> |------------operand: true, 1
>> >> |--------------simplify_0, 0
>> >>
>> >> which looks good to me.
>> >>
>> >> There is still a fallthru for all match failures but the DT should ensure
>> >> that once any of the checks is false we can terminate - that is,
>> >> we never have to backtrack.  Sth simple like
>> >>
>> >> --- genmatch.c.orig     2014-06-16 12:57:38.401890454 +0200
>> >> +++ genmatch.c  2014-06-16 12:58:03.451888730 +0200
>> >> @@ -816,6 +816,7 @@
>> >>    unsigned i;
>> >>    for (i = 0; i < kids.length (); ++i)
>> >>      kids[i]->gen_gimple (f);
>> >> +  fprintf (f, "return false;\n");
>> >>
>> >>
>> >>    for (i = 0; i < n_braces; ++i)
>> >>      fprintf (f, "}\n");
>> >>
>> >> So overall I think we are ok sofar and don't need major changes in
>> >> the algorithm.
>> >>
>> >> I'd say add the missing call support and we're good to go ripping out
>> >> the non-decision tree path.
>> >>
>> >> I'm happy to do some of the refactoring that I'd like to see myself
>> >> so you can concentrate on pattern implementing for phase 2.  But
>> >> feel free to do some of it yourself.
>> >>
>> >> > Small point: I was wondering if it's a good idea to slightly change
>> >> > the syntax of pattern to sth like:
>> >> > match-expression -> transform  ?
>> >> > eg:
>> >> > (minus (plus @0 @1) @1) -> @0
>> >> > Looks smaller -:)
>> >>
>> >> Well, I suppose we stay with what we have here.
>> > The attached patch, adds support for built-in functions, and fixes
>> > insertion bug in decision tree.
>> > The insertion in decision tree is carried out during preorder traversal
>> > of AST (insert_operand), so it avoids generating preorder traversal in
>> > vector (removed walk_operand_preorder and
>> > lower_capture). For now have put (parent, pos, preorder_level) in
>> > separate struct operand_info, and added instance
>> > of this struct to operand (struct operand_info opinfo). operand_info
>> > is computed during preorder traversal
>> > (insert_operand), so parsing routines are not concerned with it.
>> > Eventually we should probably move
>> > matching code on decision tree nodes. For convenience of tracking
>> > patterns, I have numbered them in match.pd.
>>
>> Ok.
>>
>> > * Testing
>> > Total patterns in match.pd - 58
>> > Total test cases: 4 (match-1.c), 32 (match-decision-tree.c), match-2.c
>> > is screwed.
>>
>> How is it screwed?  I see it all pass ...
> The regexes are not written correctly.
> Multiple patterns have same regex in scan-tree-dump, so even if a
> particular test-case fails in isolation,
> it shows PASS when placed with other tests that are known to PASS.

Ah ... bummer.  Probably a good opportunity to split the testcase
into multiple files.

>> > Out of 22 remaining patterns:
>> > Not supported yet (require GENERIC support or special handling): 31
>> > (convert), 33, 34, 35 (realpart/imagpart), 37 (cond)
>> > Not able to write test-cases: 2, 16, 31, 38
>>
>> Sth like
>>
>> char *foo (char *p)
>> {
>>   int i = 0;
>>   return p + i;
>> }
>>
>> for 2) and using -fdump-tree-ccp1-details and scanning the
>> ccp1 dump for "Match-and-simplified definition of _4 to p_3(D)"
>> (ok, that's a quite non-informative dump message and we should
>> improve it ... ok, changed now to "Match-and-simplified p_3(D) + _2 to p_3(D)")
>>
>> 16) is expected (it would be possible to write a testcase but I'm not sure
>> we want to retain that pattern).  31) has a testcases in gcc.dg/pr58742-[123].c
>> At some point (well, maybe now ...) we want to remove those patterns
>> we implemented in match.pd from the manual code in tree-ssa-forwprop.c
>> so we don't see "false" passing of testcases written for them.
>> For 38) I have no idea how to get a FMA_EXPR with integer types ... probably
>> the pattern (and the corresponding code in fold-const.c) is "dead".
>
> There's a serious flaw in the previous patch.
> For these two (match) expressions:
> (minus @0 @1)
> (minus negate @1)
>
> AST1:   minus - @0 - @1
> AST2:   minus - negate - @1
>
> the decision tree is:
>              minus
>              /       \
>           negate  true
>             |           |
>            true      true
>
> However, the way it's implemented, negate's parent (AST2's minus), is
> *not* present in the decision tree (because the minus of AST1 is
> present in decision tree, and both minus nodes compare equal). Because
> both minus nodes have same opinfo contents (pos, level), it "works". A
> change to opinfo contents, which is different for both minus nodes,
> would break it. This is rather ugly.

Oops.

> I guess we first need to decouple operand_info from AST.
>
> Approach 1:
> We have struct operand_info, which stores whatever information is
> required to generate code for that operand.
> Keep that in dt_operand, and add a "parent" node that points to the
> decision tree node that the AST parent is mapped to.
> We are not relying anymore on parent in AST, but on the decision tree
> node, the parent is mapped to,
> which is same for equal comparing AST nodes.
>
> struct dt_operand
> {
>   operand *op;
>   operand_info opinfo;
>   dt_operand *parent;
> };
>
> and pass opinfo to code-generators in AST.
>
> struct operand {
>   ...
>   virtual unsigned gen_gimple_match_dt (FILE *, const char *opname,
> const operand_info&);
> };
>
> Approach 2:
> Keep separate representation of decision tree from AST.
> This would require mirroring some AST classes (dt_predicate, dt_expr, etc.).
> But the code-gen for matching is off the decision tree, and only
> transform code-gen
> is off the AST.
>
> Sth like:
> struct dt_operand
> {
>   operand *op;
>   operand_info opinfo;
>   dt_operand *parent;
>
>   virtual void gen_gimple (FILE *)  = 0;  // generate matching code
> };
>
> struct dt_expr: public dt_operand
> {
>   virtual void gen_gimple (FILE *);
> };
>
> struct dt_pred: public dt_operand
> {
>   virtual void gen_gimple (FILE *);
> };
>
> struct dt_true: ...
> struct dt_match ...

I like approach 2 more but I wonder if we really need to subclass
dt_operand.  I think that the actual code-gen is easier to follow
if we do sth like

dt_operand::gen_gimple ()
{
  switch (op->op_type)
    {
    case OP_EXPR:
...

not sure why I thought that using virtual methods is a good design
for the matching part.

> * GENERIC code-gen.
> Walk the expression node twice:
> (expr-code operand0 operand1)
>
> if (TREE_CODE (o<preorder level>) == SSA_NAME)
>   {
>     gimple def_stmt<preorder level> = SSA_NAME_DEF_STMT (o<preorder level>);
>     if (is_gimple_assign (def_stmt<level>) && gimple_assign_rhs_code
> (def_stmt<level>) == expr-code)
>       {
>            // generate code for children and get child with gimple_assign_rhs
>       }
>   }
> else if (TREE_CODE (o<preorder level>) == expr-code)
>   {
>           // generate code for children and get child with TREE_OPERAND
>   }
>
> However this duplicates the code of operands.

Yeah, for very deep DTs this could badly explode exponentially ...

> Maybe we can get children of expression when we generate code for
> expr-node and store it in a "temps" array
> and then assign element of temps array to o<operand-level> when we
> generate code for operand-node.
> This is because at expr-node we don't know the preorder level of the
> child, else,
> we would have done - o<level> = gimple_assign_rhs() or o<level> =
> TREE_OPERAND ()
>
> tree temps[level-max][3]; // 3 is max number of operands an expression can have
> Keeping it 2d array, to avoid value getting overwritten by an inner expression.
> level-max  = level of AST that is greater than level of all other
> AST's. (or maybe we can assign a value which shall be a sufficient
> upper-bound like 4 for captures).
>
> example:
> consider binary expression with two operands:
>
> if (TREE_CODE (o<expr-level>) == SSA_NAME)
>   {
>      gimple def_stmt<expr-level> = SSA_NAME_DEF_STMT (o<expr-level>);
>      if (is_gimple_assign (def_stmt<expr-level>) &&
> gimple_assign_rhs_code (def_stmt<expr-level>) == expr-code)
>         {
>            temps[expr-level][0] = gimple_assign_rhs1 (def_stmt<expr-level>);
>            temps[expr-level][1] = gimple_assign_rhs2 (def_stmt<expr-level>);
>         }
>   }
> else if (TREE_CODE o<level> == expr-code)
>   {
>      temps[expr-level][0] = TREE_OPERAND (o<expr-level>, 0);
>      temps[expr-level][1] = TREE_OPERAND (o<expr-level>, 1);
>   }
> else
>     goto L0;   // gimple/generic variant's don't match go for next
> "sibling" pattern
>
> if (do_valueize (temps[expr-level][0]))
>   if (do_valueize (temps[expr-level][1]))
>     {
>        tree o<operand-1 level> = temps[expr-level][0];  // instead of
> o<operand-1 level> = gimple_assign_rhs1 ();
>        // generate code for operand-1
>
>            tree o<operand-2 level> = temps[expr-level][1];
>            // generate code for operand-2
>
>                <simplify>
>                return true;
>     }
>
> L0:
> // next pattern

Hmm.  Actually we know exactly when we want to match GENERIC
and when we want to match SSA GIMPLE.  We want to match
GENERIC when we want to match REALPART_EXPR, IMAGPART_EXPR,
VIEW_CONVERT_EXPR and BIT_FIELD_REF _or_ when the parent(!)
matched for COND_EXPR and we are looking at its first operand
(yeah, I know ...).

So we can decide at code-gen time what code to emit.

Richard.

> Thanks and Regards,
> Prathamesh
>
>>
>> Thanks,
>> Richard.
>>
>> > I will add test-cases for remaining patterns shortly.
>> >
>> > Thanks and Regards,
>> > Prathamesh
>> >>
>> >> Thanks,
>> >> Richard.
>> >>
>> >> > Thanks and Regards
>> >> > Prathamesh
>> >> >>
>> >> >> Richard.
>> >> >>
>> >> >>>and for the commutative variant:
>> >> >>>(plus (negate@0 @1) @0) S
>> >> >>>
>> >> >>>the decision tree would be the following: ?
>> >> >>>plus - negate - true - true - match (3) - simplify
>> >> >>>
>> >> >>>Thanks and Regards,
>> >> >>>Prathamesh
>> >> >>>>
>> >> >>>> Richard.
>> >> >>>>
>> >> >>>>>> Richard.
>> >> >>>>>>
>> >> >>>>>>>> There are also opportunities to optimize the generated code, but
>> >> >>>>>>>> basic correctness first I guess.
>> >> >>>>>>>>
>> >> >>>>>>>> I suppose we have to work a bit on the capture stuff.
>> >> >>>>>>>>
>> >> >>>>>>>> Btw, you can easily play with the code generator by doing inside
>> >> >>>>>>>> the gcc build directory
>> >> >>>>>>>>
>> >> >>>>>>>> obj/gcc> build/genmatch test.pd > test.c
>> >> >>>>>>>>
>> >> >>>>>>>> with a small test.pd. I used the following for the above
>> >> >>>examples:
>> >> >>>>>>>>
>> >> >>>>>>>> (match_and_simplify
>> >> >>>>>>>>   (MINUS_EXPR (PLUS_EXPR @0 @1) @0)
>> >> >>>>>>>>   @1)
>> >> >>>>>>>> (match_and_simplify
>> >> >>>>>>>>   (MINUS_EXPR (PLUS_EXPR @1 @0) @0)
>> >> >>>>>>>>   @1)
>> >> >>>>>>
>> >> >>>>>>>> Richard.
>> >> >>>>>>>>
>> >> >>>>>>>>>> I will change this to have capture per pattern
>> >> >>>>>>>>>> tree captures1[4] = {};  // for pattern-1
>> >> >>>>>>>>>> tree captures2[4] = {};
>> >> >>>>>>>>>
>> >> >>>>>>>>> Hmm, is this the matching captures issue I mentioned?  Btw, I
>> >> >>>see
>> >> >>>>>>>>> you do
>> >> >>>>>>>>>
>> >> >>>>>>>>> +void
>> >> >>>>>>>>> +walk_operand_preorder(vec<operand *>& operands, operand *op)
>> >> >>>>>>>>> +{
>> >> >>>>>>>>> +  if (op->type == operand::OP_CAPTURE || op->type ==
>> >> >>>>>>>>> operand::OP_PREDICATE || op->type == operand::OP_C_EXPR)
>> >> >>>>>>>>> +    {
>> >> >>>>>>>>> +      operands.safe_push (op);
>> >> >>>>>>>>> +      return;
>> >> >>>>>>>>> +    }
>> >> >>>>>>>>>
>> >> >>>>>>>>> but that leaves captured expressions as a single operand?
>> >> >>>>>>>>>
>> >> >>>>>>>>> (plus (minus@1 @2 @3) @2)
>> >> >>>>>>>>>
>> >> >>>>>>>>> would have a decision tree
>> >> >>>>>>>>>
>> >> >>>>>>>>>  plus -> minus -> @2
>> >> >>>>>>>>>
>> >> >>>>>>>>> correct?
>> >> >>>>>>>>>
>> >> >>>>>>>>>> d) Matching multiple patterns.
>> >> >>>>>>>>>> Code for patterns with same match, but different transforms is
>> >> >>>>>>>>>> generated as follows:
>> >> >>>>>>>>>> code for match operand.
>> >> >>>>>>>>>> if (if-expr of pattern-1)
>> >> >>>>>>>>>> {
>> >> >>>>>>>>>>   code for result of pattern-1
>> >> >>>>>>>>>>   return true;
>> >> >>>>>>>>>> }
>> >> >>>>>>>>>> if (if-expr of pattern-2)
>> >> >>>>>>>>>> {
>> >> >>>>>>>>>>   code for result of pattern-2
>> >> >>>>>>>>>>   return true;
>> >> >>>>>>>>>> }
>> >> >>>>>>>>>
>> >> >>>>>>>>> good.
>> >> >>>>>>>>>
>> >> >>>>>>>>>> ...
>> >> >>>>>>>>>> Should we emit a warning for patterns that have same match
>> >> >>>operand but
>> >> >>>>>>>>>> no if-expr and no manual transform ?
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> for eg:
>> >> >>>>>>>>>> (match_and_simplify
>> >> >>>>>>>>>>   (plus (minus @0 @1) @1)
>> >> >>>>>>>>>>   @0
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> (match_and_simplify
>> >> >>>>>>>>>>   (plus (minus @0 @1) @1)
>> >> >>>>>>>>>>   @1  // just for illustration
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> Since the matching is ambiguous (same match, no if-expr, no
>> >> >>>manual
>> >> >>>>>>>>>> transform).
>> >> >>>>>>>>>
>> >> >>>>>>>>> Yeah, I suppose we should.
>> >> >>>>>>>>>
>> >> >>>>>>>>>> we are left to choose between result of pattern-1 and result of
>> >> >>>>>>>>>> pattern-2.
>> >> >>>>>>>>>> We can emit warning and choose result of pattern-1 (first-match
>> >> >>>rule
>> >> >>>>>>>>>> as in flex).
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> e) Non-matching captures:
>> >> >>>>>>>>>> Haven't thought about this yet.
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> * Should we add "negative" predicates that match only if the
>> >> >>>predicate
>> >> >>>>>>>>>> fails ?
>> >> >>>>>>>>>> for eg:
>> >> >>>>>>>>>> (match_and_simplify
>> >> >>>>>>>>>>   trunc_mod integer_zerop@0 !integer_zerop)
>> >> >>>>>>>>>>   @0)
>> >> >>>>>>>>>
>> >> >>>>>>>>> well, there could simply be a integer_not_zerop predicate.
>> >> >>>>>>>>>
>> >> >>>>>>>>>> * Testing
>> >> >>>>>>>>>> Sorry to bring this up again, but I am still not clear what
>> >> >>>regex to
>> >> >>>>>>>>>> write in scan-tree-dump.
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> Suppose we have these two patterns in match.pd:
>> >> >>>>>>>>>> /* (x + y) - y -> x */
>> >> >>>>>>>>>> (match_and_simplify
>> >> >>>>>>>>>>   (minus (plus @0 @1) @1)
>> >> >>>>>>>>>>   @0)
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> /* (x - y) + y -> x */
>> >> >>>>>>>>>> (match_and_simplify
>> >> >>>>>>>>>>   (plus (minus @0 @1) @1)
>> >> >>>>>>>>>>   @0)
>> >> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*=
>> >> >>>>>>>>>> x_\\d\+\\(D\\)"
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> I have following test-cases:
>> >> >>>>>>>>>> int f1(int x, int y)
>> >> >>>>>>>>>> {
>> >> >>>>>>>>>>   int t1 = x + y;
>> >> >>>>>>>>>>   return t1 - y;
>> >> >>>>>>>>>> }
>> >> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*=
>> >> >>>>>>>>>> x_\\d\+\\(D\\)"
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> int f2(int x, int y)
>> >> >>>>>>>>>> {
>> >> >>>>>>>>>>   int t1 = x - y;
>> >> >>>>>>>>>>   return t1 + y;
>> >> >>>>>>>>>> }
>> >> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*=
>> >> >>>>>>>>>> x_\\d\+\\(D\\)"
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> both the test-cases have same regex.
>> >> >>>>>>>>>> Tested in isolation f1 passes (first pattern if fired) and f2
>> >> >>>fails
>> >> >>>>>>>>>> (second pattern doesn't fire, it does after
>> >> >>>>>>>>>> adding it's commutative variant, but that's irrelevant for this
>> >> >>>case).
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> However when both test-cases are put in one file both the test
>> >> >>>cases
>> >> >>>>>>>>>> PASS.
>> >> >>>>>>>>>> I think that's because both of them have same regex:
>> >> >>>\[^\n\r\]*=
>> >> >>>>>>>>>> x_\\d\+\\(D\\)
>> >> >>>>>>>>>> so in f1 and f2's regex both match the dump for f1 function in
>> >> >>>>>>>>>> forwprop dump file:
>> >> >>>>>>>>>> "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\)
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> As a quick hack i rewrote f1 and f2 as:
>> >> >>>>>>>>>> int f1(int x, int y)
>> >> >>>>>>>>>> {
>> >> >>>>>>>>>>   int t1 = x + y;
>> >> >>>>>>>>>>   int f1_val = t1 - y;
>> >> >>>>>>>>>>   return f1_val;
>> >> >>>>>>>>>> }
>> >> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to f1_val_\\d\+ =
>> >> >>>>>>>>>> x_\\d\+\\(D\\)"
>> >> >>>>>>>>>>
>> >> >>>>>>>>>> int f2(int x, int y)
>> >> >>>>>>>>>> {
>> >> >>>>>>>>>>   int t1 = x - y;
>> >> >>>>>>>>>>   int f2_val = t1 + y;
>> >> >>>>>>>>>>   return f2_val;
>> >> >>>>>>>>>> }
>> >> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to f2_val_\\d\+ =
>> >> >>>>>>>>>> x_\\d\+\\(D\\)"
>> >> >>>>>>>>>> so both f1 and f2's scan-tree-dump have different regexes.
>> >> >>>>>>>>>> and f2's regex does not match dump of f1's function.
>> >> >>>>>>>>>> This matches all patterns in match-decision-tree.c however this
>> >> >>>is not
>> >> >>>>>>>>>> ideal,
>> >> >>>>>>>>>> since it does not check for matching dump across newlines.
>> >> >>>>>>>>>> Could you suggest a better way ?
>> >> >>>>>>>>>
>> >> >>>>>>>>> There isn't a good better way (the others explicitely do _not_
>> >> >>>match
>> >> >>>>>>>>> against
>> >> >>>>>>>>> a newline - see the ^ in the \[\] group).  Well, apart from
>> >> >>>splitting
>> >> >>>>>>>>> the testcase
>> >> >>>>>>>>> into multiple files of course.
>> >> >>>>>>>>>
>> >> >>>>>>>>> Richard.
>> >> >>>>>>>>>
>> >> >>>>>>>>>> Thanks and Regards,
>> >> >>>>>>>>>> Prathamesh
>> >> >>>>>>>>>>>
>> >> >>>>>>>>>>> Thanks,
>> >> >>>>>>>>>>> Richard.
>> >> >>>>>>>>>>>
>> >> >>>>>>>>>>>>> Thanks and Regards,
>> >> >>>>>>>>>>>>> Prathamesh
>> >> >>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>> Richard.
>> >> >>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> * Code generation.
>> >> >>>>>>>>>>>>>>> Code shall be generated by walking the decision tree.
>> >> >>>>>>>>>>>>>>> The way it's constructed, there's no difference between
>> >> >>>code
>> >> >>>>>>>>>>>>>>> generation
>> >> >>>>>>>>>>>>>>> for "matching" and code generation for "transform". For
>> >> >>>>>>>>>>>>>>> non-simplificaton
>> >> >>>>>>>>>>>>>>> operands, "matching" code is generated, and for
>> >> >>>"simplification"
>> >> >>>>>>>>>>>>>>> operands,
>> >> >>>>>>>>>>>>>>> "transform" code is generated. The tree shall be walked
>> >> >>>twice,
>> >> >>>>>>>>>>>>>>> once to generate GIMPLE code and second time for GENERIC.
>> >> >>>>>>>>>>>>>>> For simplicity, I currently return false whenever there's
>> >> >>>a fail
>> >> >>>>>>>>>>>>>>> in match,
>> >> >>>>>>>>>>>>>>> instead of trying to match the next pattern.
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> Code-gen for capture - same as capture::gen_gimple_match.
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> Code-gen for predicate -  I haven't added support for
>> >> >>>predicate
>> >> >>>>>>>>>>>>>>> in
>> >> >>>>>>>>>>>>>>> decision tree yet, but I guess that would be the same as
>> >> >>>>>>>>>>>>>>> predicate::gen_gimple_match
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> Code-gen for expr.
>> >> >>>>>>>>>>>>>>> There are two types of code-gen for expr.
>> >> >>>>>>>>>>>>>>> The patch generates following code:
>> >> >>>>>>>>>>>>>>> Type 1 - expr is child of root node.
>> >> >>>>>>>>>>>>>>> the only code that gets generated is (in
>> >> >>>>>>>>>>>>>>> decision_tree::gen_gimple):
>> >> >>>>>>>>>>>>>>> if (code == <expr code>)
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>> tree captures[4] = {}
>> >> >>>>>>>>>>>>>>> <generated code for children>
>> >> >>>>>>>>>>>>>>> }
>> >> >>>>>>>>>>>>>>> This is similar to generating matching code in
>> >> >>>>>>>>>>>>>>> write_nary_simplifiers.
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> Type 2 - expr_1 is a child of another expr_0 node.
>> >> >>>>>>>>>>>>>>> The code gets generated as follows (dt_expr::gen_gimple):
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>> gimple def_stmt = SSA_NAME_DEF_STMT (op);
>> >> >>>>>>>>>>>>>>> if (is_gimple_assign (def_stmt)
>> >> >>>>>>>>>>>>>>>     && gimple_assign_rhs_code (def_stmt) == <expr_1-code>)
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>> tree op = gimple_assign_rhs1 (def_stmt);
>> >> >>>>>>>>>>>>>>> if (valueize && TREE_CODE (op) == SSA_NAME)
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>>   op = valueize (op);
>> >> >>>>>>>>>>>>>>>   if (!op) return false;
>> >> >>>>>>>>>>>>>>> }
>> >> >>>>>>>>>>>>>>> <code-gen for children of expr_1 node>
>> >> >>>>>>>>>>>>>>> }
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> Example:
>> >> >>>>>>>>>>>>>>> (negate (negate @0))
>> >> >>>>>>>>>>>>>>> S1
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> (negate (bit_not @0))
>> >> >>>>>>>>>>>>>>> S2
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> decision tree:
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>>                 dummy/root
>> >> >>>>>>>>>>>>>>>                         |
>> >> >>>>>>>>>>>>>>>            NEGATE_EXPR
>> >> >>>>>>>>>>>>>>>              /                  \
>> >> >>>>>>>>>>>>>>>      BIT_NOT           NEGATE_EXPR
>> >> >>>>>>>>>>>>>>>            |                         |
>> >> >>>>>>>>>>>>>>>          @0                     @0
>> >> >>>>>>>>>>>>>>>            |                         |
>> >> >>>>>>>>>>>>>>>          S1                      S2
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> // code-gen for NEGATE_EXPR (child of root):
>> >> >>>>>>>>>>>>>>> if (code == NEGATE_EXPR)
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>> tree captures[4] = {};
>> >> >>>>>>>>>>>>>>> // code gen for BIT_NOT_EXPR
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>> gimple def_stmt = SSA_NAME_DEF_STMT (op0);
>> >> >>>>>>>>>>>>>>> if (is_gimple_assign (def_stmt)
>> >> >>>>>>>>>>>>>>>     && gimple_assign_rhs_code (def_stmt) == BIT_NOT_EXPR)
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>> tree op = gimple_assign_rhs1 (def_stmt);
>> >> >>>>>>>>>>>>>>> if (valueize && TREE_CODE (op) == SSA_NAME)
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>>   op = valueize (op);
>> >> >>>>>>>>>>>>>>>   if (!op) return false;
>> >> >>>>>>>>>>>>>>> }
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> // code-gen for @0, child of BIT_NOT_EXPR
>> >> >>>>>>>>>>>>>>> if (!captures[0])
>> >> >>>>>>>>>>>>>>>   captures[0] = op;
>> >> >>>>>>>>>>>>>>> else if (captures[0] != op)
>> >> >>>>>>>>>>>>>>>   return false;
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> // code-gen for S1, child of @0
>> >> >>>>>>>>>>>>>>> < same as code generated by .gen_gimple_transform >
>> >> >>>>>>>>>>>>>>> return true;
>> >> >>>>>>>>>>>>>>> }
>> >> >>>>>>>>>>>>>>> // code gen for inner NEGATE_EXPR
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>> gimple def_stmt = SSA_NAME_DEF_STMT (op0);
>> >> >>>>>>>>>>>>>>> if (is_gimple_assign (def_stmt)
>> >> >>>>>>>>>>>>>>>     && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR)
>> >> >>>>>>>>>>>>>>> <rest similar to the BIT_NOT case>
>> >> >>>>>>>>>>>>>>> }
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> The following gets duplicated with the patch:
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>> gimple_def_stmt = SSA_NAME_DEF_STMT (op0);
>> >> >>>>>>>>>>>>>>> if (TREE_CODE (op0) != SSA_NAME)
>> >> >>>>>>>>>>>>>>>   return false;
>> >> >>>>>>>>>>>>>>> if (is_gimple_assign (def_stmt)
>> >> >>>>>>>>>>>>>>>     && gimple_assign_rhs_code (def_stmt) == <expr-code>)
>> >> >>>>>>>>>>>>>>> ...
>> >> >>>>>>>>>>>>>>> }
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> Improving code-gen for expr:
>> >> >>>>>>>>>>>>>>> "gimple def_stmt = ..." and "if (TREE_CODE (op0)" get
>> >> >>>duplicated,
>> >> >>>>>>>>>>>>>>> while they could be factored out, similar to this:
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>> gimple def_stmt = SSA_NAME_DEF_STMT (op0);
>> >> >>>>>>>>>>>>>>> if (TREE_CODE (op0) != SSA_NAME)
>> >> >>>>>>>>>>>>>>>   return false;
>> >> >>>>>>>>>>>>>>> if (!is_gimple_assign (def_stmt))
>> >> >>>>>>>>>>>>>>>   return false;
>> >> >>>>>>>>>>>>>>> if (gimple_assign_rhs_code (def_stmt) == BIT_NOT_EXPR)
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>>   // code-gen for BIT_NOT_EXPR subtree
>> >> >>>>>>>>>>>>>>> }
>> >> >>>>>>>>>>>>>>> else if (gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR)
>> >> >>>>>>>>>>>>>>> {
>> >> >>>>>>>>>>>>>>>   // code-gen for NEGATE_EXPR subtree
>> >> >>>>>>>>>>>>>>> }
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> For factoring "gimple def_stmt ..." and "if (TREE_CODE
>> >> >>>(op0) !=
>> >> >>>>>>>>>>>>>>> SSA_NAME"
>> >> >>>>>>>>>>>>>>> we could have that generated at the parent of expr's node
>> >> >>>rather
>> >> >>>>>>>>>>>>>>> than
>> >> >>>>>>>>>>>>>>> at expr. However that would be incorrect for cases where
>> >> >>>not all
>> >> >>>>>>>>>>>>>>> children
>> >> >>>>>>>>>>>>>>> of a node are expressions:
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> Example:
>> >> >>>>>>>>>>>>>>> // patterns only for illustration
>> >> >>>>>>>>>>>>>>> (negate (bit_not @0))
>> >> >>>>>>>>>>>>>>> (negate @0)
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>>                    root
>> >> >>>>>>>>>>>>>>>                      |
>> >> >>>>>>>>>>>>>>>                   negate
>> >> >>>>>>>>>>>>>>>                     /       \
>> >> >>>>>>>>>>>>>>>                 bit_not   @0
>> >> >>>>>>>>>>>>>>>                     |
>> >> >>>>>>>>>>>>>>>                   @0
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> we cannot have the above code generated at negate,
>> >> >>>>>>>>>>>>>>> since it's not applicable negate's 2nd child (@0).
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> This can be done by grouping together children that are
>> >> >>>>>>>>>>>>>>> expressions.
>> >> >>>>>>>>>>>>>>> However the patch does not do that.
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> * Code-gen for simplification operand
>> >> >>>>>>>>>>>>>>> This involves code-gen for ifexpr and result of pattern.
>> >> >>>>>>>>>>>>>>> Calls gen_gimple_transform of ifexpr and result
>> >> >>>>>>>>>>>>>>> (dt_simplify::gen_gimple)
>> >> >>>>>>>>>>>>>>> So this is really code-gen off AST
>> >> >>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>> Right (modulo replacing captures with their replacements).
>> >> >>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> * Matching multiple patterns
>> >> >>>>>>>>>>>>>>> A pattern has following parts: match, ifexpr and result.
>> >> >>>>>>>>>>>>>>> If pattern fails in match operand, I guess we can safely
>> >> >>>return
>> >> >>>>>>>>>>>>>>> false ?
>> >> >>>>>>>>>>>>>>> We "club" together patterns that have same match operand,
>> >> >>>>>>>>>>>>>>> and use goto, if one of them fails in their
>> >> >>>(ifexpr/result) and
>> >> >>>>>>>>>>>>>>> then goto the
>> >> >>>>>>>>>>>>>>> (ifexpr/result) of the next operand.
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> Example:
>> >> >>>>>>>>>>>>>>> /* x & 0 -> 0 */
>> >> >>>>>>>>>>>>>>> (match_and_simplify
>> >> >>>>>>>>>>>>>>>   (bit_and @0 @1)
>> >> >>>>>>>>>>>>>>>   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && (@1 ==
>> >> >>>>>>>>>>>>>>> integer_zero_node))
>> >> >>>>>>>>>>>>>>>   { integer_zero_node; })
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> /* x & -1 -> x */
>> >> >>>>>>>>>>>>>>> (match_and_simplify
>> >> >>>>>>>>>>>>>>>   (bit_and @0 @1)
>> >> >>>>>>>>>>>>>>>   if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
>> >> >>>>>>>>>>>>>>>      && (@1 == integer_minus_one_node)
>> >> >>>>>>>>>>>>>>>   @0)
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> For both patterns match is same.
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> Decision Tree:
>> >> >>>>>>>>>>>>>>>                 bit_and
>> >> >>>>>>>>>>>>>>>                 /        \
>> >> >>>>>>>>>>>>>>>              @0      @1
>> >> >>>>>>>>>>>>>>>                            |
>> >> >>>>>>>>>>>>>>>                         S1,  S2
>> >> >>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>> I think it's worth adding a diagnostic to genmach whenever
>> >> >>>exactly
>> >> >>>>>>>>>>>>>> same matches appear.  But I'd say generally we'd support
>> >> >>>this
>> >> >>>>>>>>>>>>>> by testing the ifexpr of the next pattern.
>> >> >>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> S1 represents <ifexpr, result> of pattern-1, and S2
>> >> >>>represents
>> >> >>>>>>>>>>>>>>> <ifexpr, result>
>> >> >>>>>>>>>>>>>>> of pattern-2 respectively.
>> >> >>>>>>>>>>>>>>> S1, S2 would be stored as children of @1 (the last operand
>> >> >>>of
>> >> >>>>>>>>>>>>>>> n-ary operator),
>> >> >>>>>>>>>>>>>>> in dt_operand::kids vector.
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> The code would be generated as:
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> matching code.
>> >> >>>>>>>>>>>>>>> if (! pattern-1 ifexpr condition)
>> >> >>>>>>>>>>>>>>>   goto simplify2;  // next pattern with the same "match"
>> >> >>>operand.
>> >> >>>>>>>>>>>>>>> transform code for pattern 1
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> simplify2:
>> >> >>>>>>>>>>>>>>> if (! pattern-2 ifexpr condition)
>> >> >>>>>>>>>>>>>>>   return false;  // last pattern
>> >> >>>>>>>>>>>>>>> transform code for pattern 2.
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> If matching itself fails, that is neither of the decisions
>> >> >>>get
>> >> >>>>>>>>>>>>>>> matched,
>> >> >>>>>>>>>>>>>>> I believe we can then return false as it cannot match any
>> >> >>>other
>> >> >>>>>>>>>>>>>>> pattern ?
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> * patterns needing hacks like cond_expr or GENERIC support
>> >> >>>>>>>>>>>>>>> I haven't given thought to this yet. I suppose we can look
>> >> >>>to
>> >> >>>>>>>>>>>>>>> handle
>> >> >>>>>>>>>>>>>>> these after adding support for GENERIC. Instead of
>> >> >>>generating
>> >> >>>>>>>>>>>>>>> GENERIC
>> >> >>>>>>>>>>>>>>> matching in
>> >> >>>>>>>>>>>>>>> gimple_match_and_simplify, could we then call
>> >> >>>>>>>>>>>>>>> generic_match_and_simplify from
>> >> >>>>>>>>>>>>>>> within gimple_match_and_simplify ?
>> >> >>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>> Yes (that's what's currently done btw).
>> >> >>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> * Tests
>> >> >>>>>>>>>>>>>>> The patch transformed the following patterns:
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> (match_and_simplify
>> >> >>>>>>>>>>>>>>>   (negate (bit_not @0))
>> >> >>>>>>>>>>>>>>>   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
>> >> >>>>>>>>>>>>>>>   (plus @0 { build_int_cst (TREE_TYPE (@0)), 1); }))
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> (match_and_simplify
>> >> >>>>>>>>>>>>>>>   (negate (negate @0))
>> >> >>>>>>>>>>>>>>>   @0)
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> I have attached test-case I tried it with (negate.c)
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> * Conclusion
>> >> >>>>>>>>>>>>>>> Does it sound reasonable ? I am going to be re-writing the
>> >> >>>>>>>>>>>>>>> decision tree from scratch, but is the basic idea fine ?
>> >> >>>Or should
>> >> >>>>>>>>>>>>>>> we
>> >> >>>>>>>>>>>>>>> take a different approach ?
>> >> >>>>>>>>>>>>>>>
>> >> >>>>>>>>>>>>>>> Thanks and Regards,
>> >> >>>>>>>>>>>>>>> Prathamesh
>> >> >>>>>>
>> >> >>
>> >> >>