[GSoC] decision tree first steps
Prathamesh Kulkarni
bilbotheelffriend@gmail.com
Thu Jun 19 10:42:00 GMT 2014
On Thu, Jun 19, 2014 at 2:37 PM, Prathamesh Kulkarni
<bilbotheelffriend@gmail.com> wrote:
> On Wed, Jun 18, 2014 at 4:27 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> 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.
> The attached patch separates decision tree from AST, (removes the
> "parent bug") and attempts to
> add support for special case patterns requiring GENERIC (however it
> fails one test in match-1.c, I am looking
> into that). Code-gen for matching is off the decision tree and
> code-gen for transform is off the AST.
>
> * Representation of decision tree
> dt_operand is used for representing AST operand / true / match in the
> decision tree,
> dt_operand::parent points to the decision tree node, the AST parent is
> mapped to, not the pre-order predecessor.
> dt_operand::pos gives the operand number (0th operand, 1st operand,
> etc. of parent etc.)
> I have also clubbed true and match in the same class, because true
> does not require additional fields,
> and match has only one additional field (unsigned m_level).
>
> For the following pairs of (bogus) patterns:
> (plus @0 (bit_not@2 @1))
> (plus @1 (bit_not@3 @0))
>
> It builds following decision tree:
> (type, address, level, n_kids)
>
> root (0x1513550), 0, 1
> |--PLUS_EXPR (0x1502370), 1, 1
> |----true (0x15023f0), 2, 1
> |------BIT_NOT_EXPR (0x1502470), 3, 1
> |--------true (0x15024f0), 4, 2
> |----------simplify_0 { 2, 4, 3, 4294967295, } (0x1512540), 5, 0
> |----------simplify_1 { 4, 2, 4294967295, 3, } (0x15125c0), 5, 0
>
> and for the following pairs of (bogus) patterns:
> (plus (minus@0 @1 @2) @3)
> (plus (minus @0 @1) @2)
>
> It builds following tree:
> root (0x10e2520), 0, 1
> |--PLUS_EXPR (0x10d1370), 1, 1
> |----MINUS_EXPR (0x10d13f0), 2, 1
> |------true (0x10d1470), 3, 1
> |--------true (0x10d14f0), 4, 1
> |----------true (0x10e1540), 5, 2
> |------------simplify_0 { 2, 3, 4, 5, } (0x10e15c0), 6, 0
> |------------simplify_1 { 3, 4, 5, 4294967295, } (0x10e1640), 6, 0
>
> Is that correct ?
>
> * Code-gen
> The code-gen is mostly same, with following changes:
>
> a) Generation of expressions:
> At expr-node, the children are immediately assigned in temporaries
> (t0, t1 ,...),
> and when we come at child node, the temporary is assigned to child
> node (o<level> = t<count>).
> Temporary names are stored in dt_operand::temps vector.
>
> b) Is the following condition correct (considering for convert) ?:
>
> if (is_gimple_assign (def_stmt) &&
> (gimple_assign_rhs_code (def_stmt) == <expr-code>
> || CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))))
> {
> // generated code for operands
> }
oops, that's only for CONVERT_EXPR and NOP_EXPR.
Fixed in the current patch
Thanks and Regards,
Prathamesh
>
> Example:
> For the pattern:
> (match_and_simplify
> (minus (plus @0 @1) @1)
> @0)
>
> It generated following code: http://pastebin.com/5QdCiZNi
>
> c) REALPART_EXPR / IMAGPART_EXPR / VIEW_CONVERT_EXPR / BIT_FIELD_REF:
> For these patterns, we generate GENERIC instead of GIMPLE to obtain operands ?
>
> Example:
> for the pattern:
> (match_and_simplify
> (complex (realpart @0) (imagpart @0))
> @0)
>
> it generated following code: http://pastebin.com/qXjEavDu
>
> d) COND_EXPR
> We generate GENERIC for 1st operand of COND_EXPR and not for the other
> operands (2nd, 3rd).
> Is that correct ?
>
> for the pattern:
> (match_and_simplify
> (cond (bit_not @0) @1 @2)
> (cond @0 @2 @1))
>
> it generates following code: http://pastebin.com/vL1dcb2E
>
> * GENERIC code generation.
> So far we are generating code for match-and-simplify on gimple.
> How do we start with GENERIC code-gen ?
>
> a) generate in gimple-match.c (or keep a different generic-match.c) ?
> b) Interface to GENERIC match_and_simplify - I guess it would be same as
> fold_binary / fold_unary ?
> c) We already have matching code in place for GENERIC
> (dt_operand::gen_generic_expr),
> we shall need to add code for generating GENERIC transforms.
>
> Thanks and Regards,
> Prathamesh
>
>>
>> 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
>>>> >> >>>>>>
>>>> >> >>
>>>> >> >>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dt6.patch
Type: text/x-patch
Size: 19482 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20140619/8a0ceb86/attachment.bin>
More information about the Gcc
mailing list