This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: [GSoC] decision tree first steps
- From: Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>
- To: Richard Biener <richard dot guenther at gmail dot com>
- Cc: Diego Novillo <dnovillo at google dot com>, gcc <gcc at gcc dot gnu dot org>, Maxim Kuvyrkov <maxim dot kuvyrkov at linaro dot org>
- Date: Thu, 19 Jun 2014 19:53:00 +0530
- Subject: Re: [GSoC] decision tree first steps
- Authentication-results: sourceware.org; auth=none
- References: <CAJXstsAXoGY+hbH=LpVAB2MmV+6HnfZpQ7jbWkAN7MzQR7Qc+Q at mail dot gmail dot com> <CAFiYyc3gNw2DD=BZpSuXaN9W0HRO-kxBOvszBv0meWP3FnFgOA at mail dot gmail dot com> <CAJXstsCKMBdOVyNMYLTUqdxUg7Dih6C3o8hOrgTYXoAhBgW7Tg at mail dot gmail dot com> <CAFiYyc1cYbaRQTQyZuShu3q+PmEJ4A-E5ua4nYANDHNCJ9_fPQ at mail dot gmail dot com> <CAFiYyc3mfE8FvxVih4XbOJvpdEVSOATGeaVkhUvqighcjvgMsA at mail dot gmail dot com> <CAJXstsDzBCrLu0QYfuqwOXy5TEDdCbAR1CZicLpmXvQR+MLwGQ at mail dot gmail dot com> <CAFiYyc3tCV4xHDv7FJdEzwXiN4s4=zEcFYyx5jQnpL4hsyKQ_g at mail dot gmail dot com> <CAFiYyc1M85ofSmQcTiQkH24jH-fvR2qxVmvVMJOH-cfNg+MTqw at mail dot gmail dot com> <CAFiYyc17dJ4ex=LSF0b7NA3P1KoRRsoLBHr5ef_d9BaHuQ98Mg at mail dot gmail dot com> <CAFiYyc176_S7iXwTrq_a_drbY97=dEzg0NTGMZ9Z08PD+MAE5Q at mail dot gmail dot com> <CAJXstsBtu4ZadAF6+hkBf43hYHsCTZMCW51Q0vNE_0ek_irRgA at mail dot gmail dot com> <CAFiYyc22S5-m2U_EoYM1TLXERn1sYcX-NmOzgyWdkp9Tw2GFmg at mail dot gmail dot com> <CAJXstsCDQ6KRR+xi8vD=3-C=VfSCoDF_ab6bhZ7SRU9K+-f0pA at mail dot gmail dot com> <35e3244a-4455-489d-bb88-2709035c94b4 at email dot android dot com> <CAJXstsDMTn5_Yuio+Z=-DxB52qCZMEiCZOx3K_Kb3MRbE654Cg at mail dot gmail dot com> <CAFiYyc36-QBCuq5Si6b5+FYrGbQNTomveA=M5yF17wJqE7kCQw at mail dot gmail dot com> <CAJXstsC_ALPRKaAv=mEY4ODEyUdpryC0Bw3WTihgqQ7=q2v5xQ at mail dot gmail dot com> <CAFiYyc0a3iwagd_eLxg_WnP+UHjXc-P1_2htMoa43kmEWyMCXw at mail dot gmail dot com> <CAJXstsAA_hQMt78+bTNRfGU-f5SB5SN=B9SMbPfs8EmM7aB8kw at mail dot gmail dot com> <CAFiYyc1-1t8gA=MW6DaAojrO2vUusW-vvRM+dUW1YjsCYTfb7Q at mail dot gmail dot com> <CAJXstsAVwVrUpU0CB0XOoDSes27ZSsLv48bxOwjnO2VvDn=K8w at mail dot gmail dot com> <CAJXstsA+5=yCXJFkhQamTSb-=x2KLUSi9BdZRXyYDdqO6r7Wsg at mail dot gmail dot com>
On Thu, Jun 19, 2014 at 4:12 PM, Prathamesh Kulkarni
<bilbotheelffriend@gmail.com> wrote:
> 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
This patch fixes some more mistakes of the previous patch, and removes
.gen_gimple_match functions.
It now passes all tests from match-1.c
The test-case was failing because I didn't generate valueize code correctly.
It should have been:
if ((t<count> = do_valueize (valueize, t<count>)) != 0)
and the code getting generated was:
if (do_valueize (valueize, t<count>))
This patch supports all the patterns in match.pd. What changes would I
need to make to make it a commit-ready patch ?
Thanks and Regards,
Prathamesh
>
> 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
>>>>> >> >>>>>>
>>>>> >> >>
>>>>> >> >>
Index: gcc/genmatch.c
===================================================================
--- gcc/genmatch.c (revision 211732)
+++ gcc/genmatch.c (working copy)
@@ -29,7 +29,8 @@ along with GCC; see the file COPYING3.
#include "hashtab.h"
#include "hash-table.h"
#include "vec.h"
-
+#include <stdlib.h>
+#include <limits.h>
/* libccp helpers. */
@@ -205,7 +206,6 @@ struct operand {
enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR };
operand (enum op_type type_) : type (type_) {}
enum op_type type;
- virtual void gen_gimple_match (FILE *f, const char *, const char * = NULL) = 0;
virtual void gen_gimple_transform (FILE *f, const char *, const char *) = 0;
};
@@ -213,7 +213,6 @@ struct predicate : public operand
{
predicate (const char *ident_) : operand (OP_PREDICATE), ident (ident_) {}
const char *ident;
- virtual void gen_gimple_match (FILE *f, const char *, const char *);
virtual void gen_gimple_transform (FILE *, const char *, const char *) { gcc_unreachable (); }
};
@@ -230,7 +229,6 @@ struct expr : public operand
void append_op (operand *op) { ops.safe_push (op); }
e_operation *operation;
vec<operand *> ops;
- virtual void gen_gimple_match (FILE *f, const char *, const char *);
virtual void gen_gimple_transform (FILE *f, const char *, const char *);
};
@@ -243,7 +241,6 @@ struct c_expr : public operand
vec<cpp_token> code;
unsigned nr_stmts;
char *fname;
- virtual void gen_gimple_match (FILE *, const char *, const char *) { gcc_unreachable (); }
virtual void gen_gimple_transform (FILE *f, const char *, const char *);
};
@@ -253,7 +250,6 @@ struct capture : public operand
: operand (OP_CAPTURE), where (where_), what (what_) {}
const char *where;
operand *what;
- virtual void gen_gimple_match (FILE *f, const char *, const char *);
virtual void gen_gimple_transform (FILE *f, const char *, const char *);
};
@@ -322,145 +318,6 @@ gen_gimple_match_fail (FILE *f, const ch
}
void
-predicate::gen_gimple_match (FILE *f, const char *op, const char *label)
-{
- fprintf (f, "if (!%s (%s)) ", ident, op);
- gen_gimple_match_fail (f, label);
-}
-
-void
-expr::gen_gimple_match (FILE *f, const char *name, const char *label)
-{
- if (operation->op->kind == id_base::CODE)
- {
- operator_id *op = static_cast <operator_id *> (operation->op);
- /* The GIMPLE variant. */
- fprintf (f, "if (TREE_CODE (%s) == SSA_NAME)\n", name);
- fprintf (f, " {\n");
- fprintf (f, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", name);
- fprintf (f, "if (!is_gimple_assign (def_stmt)\n");
- if (op->code == NOP_EXPR
- || op->code == CONVERT_EXPR)
- fprintf (f, " || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))) ");
- else
- fprintf (f, " || gimple_assign_rhs_code (def_stmt) != %s) ", op->id);
- gen_gimple_match_fail (f, label);
- if (op->code == REALPART_EXPR
- || op->code == IMAGPART_EXPR
- || op->code == VIEW_CONVERT_EXPR
- || op->code == BIT_FIELD_REF)
- {
- fprintf (f, " tree rhs = gimple_assign_rhs1 (def_stmt);\n");
- for (unsigned i = 0; i < ops.length (); ++i)
- {
- fprintf (f, " {\n");
- fprintf (f, " tree op = TREE_OPERAND (rhs, %d);\n", i);
- fprintf (f, " if (valueize && TREE_CODE (op) == SSA_NAME)\n");
- fprintf (f, " {\n");
- fprintf (f, " op = valueize (op);\n");
- fprintf (f, " if (!op) ");
- gen_gimple_match_fail (f, label);
- fprintf (f, " }\n");
- ops[i]->gen_gimple_match (f, "op", label);
- fprintf (f, " }\n");
- }
- }
- else
- {
- for (unsigned i = 0; i < ops.length (); ++i)
- {
- fprintf (f, " {\n");
- fprintf (f, " tree op = gimple_assign_rhs%d (def_stmt);\n", i + 1);
- fprintf (f, " if (valueize && TREE_CODE (op) == SSA_NAME)\n");
- fprintf (f, " {\n");
- fprintf (f, " op = valueize (op);\n");
- fprintf (f, " if (!op) ");
- gen_gimple_match_fail (f, label);
- fprintf (f, " }\n");
- ops[i]->gen_gimple_match (f, "op", label);
- fprintf (f, " }\n");
- }
- }
- fprintf (f, " }\n");
- /* The GENERIC variant. */
- fprintf (f, "else if (TREE_CODE (%s) == %s)\n", name, op->id);
- fprintf (f, " {\n");
- for (unsigned i = 0; i < ops.length (); ++i)
- {
- fprintf (f, " {\n");
- fprintf (f, " tree op_ = %s;\n", name);
- fprintf (f, " tree op = TREE_OPERAND (op_, %d);\n", i);
- fprintf (f, " if (valueize && TREE_CODE (op) == SSA_NAME)\n");
- fprintf (f, " {\n");
- fprintf (f, " op = valueize (op);\n");
- fprintf (f, " if (!op) ");
- gen_gimple_match_fail (f, label);
- fprintf (f, " }\n");
- ops[i]->gen_gimple_match (f, "op", label);
- fprintf (f, " }\n");
- }
- fprintf (f, " }\n");
- fprintf (f, "else ");
- gen_gimple_match_fail (f, label);
- }
- else if (operation->op->kind == id_base::FN)
- {
- fn_id *op = static_cast <fn_id *> (operation->op);
- /* The GIMPLE variant. */
- fprintf (f, "if (TREE_CODE (%s) == SSA_NAME)\n", name);
- fprintf (f, " {\n");
- fprintf (f, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", name);
- fprintf (f, "if (!gimple_call_builtin_p (def_stmt, %s)) ", op->id);
- gen_gimple_match_fail (f, label);
- for (unsigned i = 0; i < ops.length (); ++i)
- {
- fprintf (f, " {\n");
- fprintf (f, " tree op = gimple_call_arg (def_stmt, %d);\n", i);
- fprintf (f, " if (valueize && TREE_CODE (op) == SSA_NAME)\n");
- fprintf (f, " {\n");
- fprintf (f, " op = valueize (op);\n");
- fprintf (f, " if (!op) ");
- gen_gimple_match_fail (f, label);
- fprintf (f, " }\n");
- ops[i]->gen_gimple_match (f, "op", label);
- fprintf (f, " }\n");
- }
- fprintf (f, " }\n");
- /* GENERIC handling for calls. */
- fprintf (f, "else if (TREE_CODE (%s) == CALL_EXPR\n"
- " && TREE_CODE (CALL_EXPR_FN (%s)) == ADDR_EXPR\n"
- " && TREE_CODE (TREE_OPERAND (CALL_EXPR_FN (%s), 0)) == FUNCTION_DECL\n"
- " && DECL_BUILT_IN_CLASS (TREE_OPERAND (CALL_EXPR_FN (%s), 0)) == BUILT_IN_NORMAL\n"
- " && DECL_FUNCTION_CODE (TREE_OPERAND (CALL_EXPR_FN (%s), 0)) == %s)\n",
- name, name, name, name, name, op->id);
- fprintf (f, " {\n");
- for (unsigned i = 0; i < ops.length (); ++i)
- {
- fprintf (f, " {\n");
- fprintf (f, " tree op = CALL_EXPR_ARG (%s, %d);\n", name, i);
- fprintf (f, " if (valueize && TREE_CODE (op) == SSA_NAME)\n");
- fprintf (f, " {\n");
- fprintf (f, " op = valueize (op);\n");
- fprintf (f, " if (!op) ");
- gen_gimple_match_fail (f, label);
- fprintf (f, " }\n");
- ops[i]->gen_gimple_match (f, "op", label);
- fprintf (f, " }\n");
- }
- fprintf (f, " }\n");
- fprintf (f, "else ");
- gen_gimple_match_fail (f, label);
- }
- /* ??? Specifically COND_EXPR could also match on CFG diamonds.
- (cond@3 @0 @1 @2) is
- if (@0) goto bb2;
- bb3:
- bb2:
- @3 = PHI <@1(2), @2(3)>
- */
-}
-
-void
expr::gen_gimple_transform (FILE *f, const char *label, const char *dest)
{
fprintf (f, "{\n");
@@ -546,63 +403,577 @@ capture::gen_gimple_transform (FILE *f,
fprintf (f, "%s = captures[%s];\n", dest, this->where);
}
+bool
+cmp_operand (operand *o1, operand *o2)
+{
+ if (!o1 || !o2 || o1->type != o2->type)
+ return false;
+
+ if (o1->type == operand::OP_PREDICATE)
+ {
+ predicate *p1 = static_cast<predicate *>(o1);
+ predicate *p2 = static_cast<predicate *>(o2);
+ return strcmp (p1->ident, p2->ident) == 0;
+ }
+ else if (o1->type == operand::OP_EXPR)
+ {
+ expr *e1 = static_cast<expr *>(o1);
+ expr *e2 = static_cast<expr *>(o2);
+ return strcmp (e1->operation->op->id, e2->operation->op->id) == 0;
+ }
+ else
+ return false;
+}
+
void
-capture::gen_gimple_match (FILE *f, const char *op, const char *label)
+print_flattened_operand (operand *o, FILE *f = stderr)
{
- if (this->what)
- this->what->gen_gimple_match (f, op, label);
- fprintf (f, "if (!captures[%s])\n"
- " captures[%s] = %s;\n"
- "else if (captures[%s] != %s)\n ",
- this->where, this->where, op, this->where, op);
- gen_gimple_match_fail (f, label);
+ if (o->type == operand::OP_CAPTURE)
+ fprintf (f, "@%s", (static_cast<capture *>(o))->where);
+ else if (o->type == operand::OP_PREDICATE)
+ fprintf (f, "%s", (static_cast<predicate *>(o))->ident);
+ else if (o->type == operand::OP_EXPR)
+ {
+ expr *e = static_cast <expr *>(o);
+ fprintf (f, "%s", e->operation->op->id);
+ }
+ else if (o->type == operand::OP_C_EXPR)
+ fprintf (f, "c_expr");
+ else
+ gcc_unreachable ();
}
+struct dt_node
+{
+ enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
+
+ enum dt_type type;
+ unsigned level;
+ vec<dt_node *> kids;
+
+ dt_node (enum dt_type type_): type (type_), level (0), kids (vNULL) {}
+
+ dt_node *append_node (dt_node *);
+ dt_node *append_op (operand *, dt_node *parent = 0, unsigned pos = 0);
+ dt_node *append_true_op (dt_node *parent = 0, unsigned pos = 0);
+ dt_node *append_match_op (unsigned, dt_node *parent = 0, unsigned pos = 0);
+ dt_node *append_simplify (operand *, operand *, unsigned, unsigned *);
-static void
-write_nary_simplifiers (FILE *f, vec<simplify *>& simplifiers, unsigned n)
+ virtual void gen_gimple (FILE *) {}
+};
+
+struct dt_operand: public dt_node
+{
+ operand *op;
+ unsigned m_level; // for match
+ dt_operand *parent;
+ unsigned pos;
+ vec<unsigned> temps;
+ static unsigned temp_count;
+
+ dt_operand (enum dt_type type, operand *op_, unsigned m_level_, dt_operand *parent_ = 0, unsigned pos_ = 0)
+ : dt_node (type), op (op_), m_level (m_level_), parent (parent_), pos (pos_), temps (vNULL) {}
+
+ virtual void gen_gimple (FILE *);
+ unsigned gen_gimple_predicate (FILE *, const char *);
+ unsigned gen_gimple_match_op (FILE *, const char *);
+
+ unsigned gen_gimple_expr (FILE *, const char *);
+ void gen_gimple_expr_expr (FILE *, expr *);
+ void gen_gimple_expr_fn (FILE *, expr *);
+
+ unsigned gen_generic_expr (FILE *, const char *);
+ void gen_generic_expr_expr (FILE *, expr *, const char *);
+ void gen_generic_expr_fn (FILE *, expr *, const char *);
+};
+
+unsigned dt_operand::temp_count = 0;
+
+struct dt_simplify: public dt_node
+{
+ static const unsigned level_max = UINT_MAX;
+ static const unsigned capture_max = 4;
+ operand *ifexpr;
+ operand *result;
+ unsigned pattern_no;
+ unsigned indexes[capture_max];
+
+ dt_simplify (operand *ifexpr_, operand *result_, unsigned pattern_no_, unsigned *indexes_)
+ : dt_node (DT_SIMPLIFY), ifexpr (ifexpr_), result (result_), pattern_no (pattern_no_)
+ {
+ for (unsigned i = 0; i < capture_max; ++i)
+ indexes[i] = indexes_[i];
+ }
+
+ virtual void gen_gimple (FILE *f);
+};
+
+struct decision_tree
+{
+ dt_node *root;
+
+ void insert (struct simplify *, unsigned);
+ void gen_gimple (FILE *f = stderr);
+ void print (FILE *f = stderr);
+
+ decision_tree () { root = new dt_node (dt_node::DT_NODE); }
+
+ static dt_node *insert_operand (dt_node *, operand *, unsigned *indexes, unsigned pos = 0, dt_node *parent = 0);
+ static dt_node *find_node (vec<dt_node *>&, dt_node *);
+ static bool cmp_node (dt_node *, dt_node *);
+ static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
+};
+
+bool
+decision_tree::cmp_node (dt_node *n1, dt_node *n2)
+{
+ if (!n1 || !n2 || n1->type != n2->type)
+ return false;
+
+ if (n1 == n2 || n1->type == dt_node::DT_TRUE)
+ return true;
+
+ if (n1->type == dt_node::DT_OPERAND)
+ return cmp_operand ((static_cast<dt_operand *> (n1))->op, (static_cast<dt_operand *> (n2))->op);
+
+ else if (n1->type == dt_node::DT_MATCH)
+ return (static_cast<dt_operand *> (n1))->m_level == (static_cast<dt_operand *> (n2))->m_level;
+
+ else
+ return false;
+}
+
+dt_node *
+decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
+{
+ for (unsigned i = 0; i < ops.length (); ++i)
+ if (decision_tree::cmp_node (ops[i], p))
+ return ops[i];
+
+ return 0;
+}
+
+dt_node *
+dt_node::append_node (dt_node *n)
+{
+ dt_node *kid;
+
+ kid = decision_tree::find_node (kids, n);
+ if (kid)
+ return kid;
+
+ kids.safe_push (n);
+ n->level = this->level + 1;
+
+ unsigned len = kids.length ();
+
+ if (len > 1 && kids[len - 2]->type == dt_node::DT_TRUE)
+ {
+ dt_node *p = kids[len - 2];
+ kids[len - 2] = kids[len - 1];
+ kids[len - 1] = p;
+ }
+
+ return n;
+}
+
+dt_node *
+dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
+{
+ dt_operand *parent_ = static_cast<dt_operand *> (parent);
+ dt_node *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
+ dt_node *p = append_node (n);
+
+ if (p != n)
+ free (n);
+
+ return p;
+}
+
+dt_node *
+dt_node::append_true_op (dt_node *parent, unsigned pos)
+{
+ dt_operand *parent_ = static_cast<dt_operand *> (parent);
+ dt_node *n = new dt_operand (DT_TRUE, 0, 0, parent_, pos);
+ dt_node *p = append_node (n);
+
+ if (p != n)
+ free (n);
+
+ return p;
+}
+
+dt_node *
+dt_node::append_match_op (unsigned m_level, dt_node *parent, unsigned pos)
+{
+ dt_operand *parent_ = static_cast<dt_operand *> (parent);
+ dt_node *n = new dt_operand (DT_MATCH, 0, m_level, parent_, pos);
+ dt_node *p = append_node (n);
+
+ if (p != n)
+ free (n);
+
+ return p;
+}
+
+dt_node *
+dt_node::append_simplify (operand *ifexpr, operand *result, unsigned pattern_no, unsigned *indexes)
+{
+ dt_node *n = new dt_simplify (ifexpr, result, pattern_no, indexes);
+ return append_node (n);
+}
+
+dt_node *
+decision_tree::insert_operand (dt_node *p, operand *o, unsigned *indexes, unsigned pos, dt_node *parent)
+{
+ dt_node *q;
+
+ if (o->type == operand::OP_CAPTURE)
+ {
+ capture *c = static_cast<capture *> (o);
+ unsigned capt_index = atoi (c->where);
+
+ if (indexes[capt_index] == dt_simplify::level_max)
+ {
+ indexes[capt_index] = p->level + 1;
+
+ if (c->what)
+ return insert_operand (p, c->what, indexes, pos, parent);
+ else
+ {
+ p = p->append_true_op (parent, pos);
+ return p;
+ }
+ }
+ else
+ {
+ p = p->append_match_op (indexes[capt_index], parent, pos);
+ if (c->what)
+ return insert_operand (p, c->what, indexes, 0, p);
+ else
+ return p;
+ }
+ }
+ p = p->append_op (o, parent, pos);
+ q = p;
+
+ if (o->type == operand::OP_EXPR)
+ {
+ expr *e = static_cast<expr *> (o);
+ for (unsigned i = 0; i < e->ops.length (); ++i)
+ q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p);
+ }
+
+ return q;
+}
+
+
+void
+decision_tree::insert (struct simplify *s, unsigned pattern_no)
+{
+ if (s->match->type != operand::OP_EXPR)
+ return;
+
+ unsigned indexes[dt_simplify::capture_max];
+
+ for (unsigned i = 0; i < dt_simplify::capture_max; ++i)
+ indexes[i] = dt_simplify::level_max;
+
+ dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
+ p->append_simplify (s->ifexpr, s->result, pattern_no, indexes);
+}
+
+void
+decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
+{
+ if (p->type == dt_node::DT_NODE)
+ fprintf (f, "root");
+ else
+ {
+ fprintf (f, "|");
+ for (unsigned i = 0; i < indent; i++)
+ fprintf (f, "-");
+
+ if (p->type == dt_node::DT_OPERAND)
+ {
+ dt_operand *dop = static_cast<dt_operand *>(p);
+ print_flattened_operand (dop->op, f);
+ }
+ else if (p->type == dt_node::DT_TRUE)
+ fprintf (f, "true");
+ else if (p->type == dt_node::DT_MATCH)
+ fprintf (f, "match (%u)", ((static_cast<dt_operand *>(p))->m_level));
+ else if (p->type == dt_node::DT_SIMPLIFY)
+ {
+ dt_simplify *s = static_cast<dt_simplify *> (p);
+ fprintf (f, "simplify_%u { ", s->pattern_no);
+ for (unsigned i = 0; i < dt_simplify::capture_max; ++i)
+ fprintf (f, "%u, ", s->indexes[i]);
+ fprintf (f, " } ");
+ }
+ }
+
+ fprintf (stderr, " (%p), %u, %u\n", (void *) p, p->level, p->kids.length ());
+
+ for (unsigned i = 0; i < p->kids.length (); ++i)
+ decision_tree::print_node (p->kids[i], f, indent + 2);
+}
+
+
+void
+decision_tree::print (FILE *f)
{
- unsigned label_cnt = 1;
+ return decision_tree::print_node (root, f);
+}
- fprintf (f, "\nstatic bool\n"
- "gimple_match_and_simplify (code_helper code, tree type");
+void
+write_fn_prototype (FILE *f, unsigned n)
+{
+ fprintf (f, "static bool\n"
+ "gimple_match_and_simplify (code_helper code, tree type");
for (unsigned i = 0; i < n; ++i)
fprintf (f, ", tree op%d", i);
- fprintf (f, ", code_helper *res_code, tree *res_ops, gimple_seq *seq, tree (*valueize)(tree))\n"
- "{\n");
- for (unsigned i = 0; i < simplifiers.length (); ++i)
+ fprintf (f, ", code_helper *res_code, tree *res_ops, gimple_seq *seq, tree (*valueize)(tree))\n");
+}
+
+unsigned
+dt_operand::gen_gimple_predicate (FILE *f, const char *opname)
+{
+ predicate *p = static_cast<predicate *> (op);
+
+ fprintf (f, "if (%s (%s))\n", p->ident, opname);
+ fprintf (f, "{\n");
+ return 1;
+}
+
+unsigned
+dt_operand::gen_gimple_match_op (FILE *f, const char *opname)
+{
+ fprintf (f, "if (%s == o%u)\n", opname, m_level);
+ fprintf (f, "{\n");
+ return 1;
+}
+
+void
+dt_operand::gen_gimple_expr_fn (FILE *f, expr *e)
+{
+ unsigned n_ops = e->ops.length ();
+
+ fn_id *op = static_cast <fn_id *> (e->operation->op);
+ fprintf (f, "if (gimple_call_builtin_p (def_stmt, %s))\n", op->id);
+ fprintf (f, "{\n");
+
+ for (unsigned i = 0; i < n_ops; ++i)
{
- simplify *s = simplifiers[i];
- /* ??? This means we can't capture the outermost expression. */
- if (s->match->type != operand::OP_EXPR)
- continue;
- expr *e = static_cast <expr *> (s->match);
- if (e->ops.length () != n)
- continue;
- char fail_label[16];
- snprintf (fail_label, 16, "fail%d", label_cnt++);
- output_line_directive (f, s->match_location);
- fprintf (f, " if (code == %s)\n", e->operation->op->id);
- fprintf (f, " {\n");
- fprintf (f, " tree captures[4] = {};\n");
- for (unsigned j = 0; j < n; ++j)
- {
- char op[4] = "op0";
- op[2] = '0' + j;
- e->ops[j]->gen_gimple_match (f, op, fail_label);
+ char child_opname[20];
+ sprintf (child_opname, "t%u", dt_operand::temp_count);
+ temps.safe_push (dt_operand::temp_count++);
+
+ fprintf (f, "tree %s = gimple_call_arg (def_stmt, %u);\n", child_opname, i);
+ fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", child_opname, child_opname);
+ fprintf (f, "{\n");
+ }
+}
+
+void
+dt_operand::gen_gimple_expr_expr (FILE *f, expr *e)
+{
+ unsigned n_ops = e->ops.length ();
+
+ operator_id *op_id = static_cast <operator_id *> (e->operation->op);
+
+ if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR)
+ fprintf (f, "if (is_gimple_assign (def_stmt) &&\n"
+ " (gimple_assign_rhs_code (def_stmt) == %s\n"
+ " || CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))))\n", op_id->id);
+ else
+ fprintf (f, "if (is_gimple_assign (def_stmt) && gimple_assign_rhs_code (def_stmt) == %s)\n", op_id->id);
+
+ fprintf (f, "{\n");
+
+ for (unsigned i = 0; i < n_ops; ++i)
+ {
+ char child_opname[20];
+ sprintf (child_opname, "t%u", dt_operand::temp_count);
+ temps.safe_push (dt_operand::temp_count++);
+
+ fprintf (f, "tree %s = gimple_assign_rhs%u (def_stmt);\n", child_opname, i + 1);
+ fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", child_opname, child_opname);
+ fprintf (f, "{\n");
+ }
+}
+
+unsigned
+dt_operand::gen_gimple_expr (FILE *f, const char *opname)
+{
+ unsigned i;
+ expr *e = static_cast<expr *> (op);
+
+ fprintf (f, "if (TREE_CODE (%s) == SSA_NAME)\n", opname);
+ fprintf (f, "{\n");
+
+ fprintf (f, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", opname);
+ (e->operation->op->kind == id_base::CODE) ? gen_gimple_expr_expr (f, e) : gen_gimple_expr_fn (f, e);
+
+ return e->ops.length () + 2;
+}
+
+void
+dt_operand::gen_generic_expr_expr (FILE *f, expr *e, const char *opname)
+{
+ unsigned n_ops = e->ops.length ();
+
+ fprintf (f, "if (TREE_CODE (%s) == %s)\n", opname, e->operation->op->id);
+ fprintf (f, "{\n");
+
+ for (unsigned i = 0; i < n_ops; ++i)
+ {
+ char child_opname[20];
+ sprintf (child_opname, "t%u", dt_operand::temp_count);
+ temps.safe_push (dt_operand::temp_count++);
+
+ fprintf (f, "tree %s = TREE_OPERAND (%s, %u);\n", child_opname, opname, i);
+ fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", child_opname, child_opname);
+ fprintf (f, "{\n");
+ }
+}
+
+void
+dt_operand::gen_generic_expr_fn (FILE *f, expr *e, const char *opname)
+{
+ unsigned n_ops = e->ops.length ();
+ fn_id *op = static_cast <fn_id *> (e->operation->op);
+
+ fprintf (f, "if (TREE_CODE (%s) == CALL_EXPR\n"
+ " && TREE_CODE (CALL_EXPR_FN (%s)) == ADDR_EXPR\n"
+ " && TREE_CODE (TREE_OPERAND (CALL_EXPR_FN (%s), 0)) == FUNCTION_DECL\n"
+ " && DECL_BUILT_IN_CLASS (TREE_OPERAND (CALL_EXPR_FN (%s), 0)) == BUILT_IN_NORMAL\n"
+ " && DECL_FUNCTION_CODE (TREE_OPERAND (CALL_EXPR_FN (%s), 0)) == %s)\n",
+ opname, opname, opname, opname, opname, op->id);
+ fprintf (f, " {\n");
+
+ for (unsigned i = 0; i < n_ops; ++i)
+ {
+ char child_opname[20];
+ sprintf (child_opname, "t%u", dt_operand::temp_count);
+ temps.safe_push (dt_operand::temp_count++);
+
+ fprintf (f, "tree %s = CALL_EXPR_ARG (%s, %u);\n", child_opname, opname, i);
+ fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", child_opname, child_opname);
+ fprintf (f, "{\n");
+ }
+}
+
+unsigned
+dt_operand::gen_generic_expr (FILE *f, const char *opname)
+{
+ unsigned i;
+ expr *e = static_cast<expr *> (op);
+ (e->operation->op->kind == id_base::CODE) ? gen_generic_expr_expr (f, e, opname) : gen_generic_expr_fn (f, e, opname);
+ return e->ops.length () + 1;
+}
+
+void
+dt_operand::gen_gimple (FILE *f)
+{
+ char opname[20];
+ sprintf (opname, "o%u", level);
+
+
+ fprintf (f, "{\n");
+
+ fprintf (stderr, "pos = %u\n", pos);
+
+ if (parent->parent == 0)
+ fprintf (f, "tree %s = op%u;\n", opname, pos);
+ else if (parent->type == dt_node::DT_MATCH)
+ fprintf (f, "tree %s = o%u;\n", opname, parent->level);
+ else if (parent->type == dt_node::DT_OPERAND && parent->op->type == operand::OP_EXPR)
+ fprintf (f, "tree %s = t%u;\n", opname, parent->temps[pos]);
+ else
+ gcc_unreachable ();
+
+ unsigned n_braces = 0;
+
+ if (type == DT_OPERAND)
+ switch (op->type)
+ {
+ case operand::OP_PREDICATE:
+ n_braces = gen_gimple_predicate (f, opname);
+ break;
+
+ case operand::OP_EXPR:
+ {
+ expr *e = static_cast<expr *> (op);
+ operator_id *op_id = static_cast <operator_id *> (e->operation->op);
+ enum tree_code code = op_id->code;
+
+ if (code == REALPART_EXPR || code == IMAGPART_EXPR || code == VIEW_CONVERT_EXPR || code == BIT_FIELD_REF)
+ n_braces = gen_generic_expr (f, opname);
+
+ // check for cond_expr, 0th operand -> generic
+ else if (parent->type == dt_node::DT_OPERAND && parent->op->type == operand::OP_EXPR)
+ {
+ e = static_cast<expr *> (parent->op);
+ op_id = static_cast <operator_id *> (e->operation->op);
+ n_braces = (op_id->code == COND_EXPR && pos == 0) ? gen_generic_expr (f, opname) : gen_gimple_expr (f, opname);
+ }
+ else
+ n_braces = gen_gimple_expr (f, opname);
}
- if (s->ifexpr)
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ else if (type == DT_TRUE)
+ ;
+ else if (type == DT_MATCH)
+ n_braces = gen_gimple_match_op (f, opname);
+ else
+ gcc_unreachable ();
+
+ unsigned i;
+
+ for (i = 0; i < kids.length (); ++i)
+ kids[i]->gen_gimple (f);
+
+ for (i = 0; i < n_braces; ++i)
+ fprintf (f, "}\n");
+
+ fprintf (f, "}\n");
+}
+
+void
+dt_simplify::gen_gimple (FILE *f)
+{
+ dt_simplify *s = this;
+
+ char *fail_label = 0;
+
+ fprintf (f, "/* simplify %u */\n", pattern_no);
+
+ fprintf (f, "{\n");
+ fprintf (f, "tree captures[4] = {};\n");
+
+ for (unsigned i = 0; i < dt_simplify::capture_max; ++i)
+ if (indexes[i] != dt_simplify::level_max)
+ fprintf (f, "captures[%u] = o%u;\n", i, indexes[i]);
+
+ if (s->ifexpr)
{
- output_line_directive (f, s->ifexpr_location);
- fprintf (f, " if (!(");
+// output_line_directive (f, s->ifexpr_location);
+ fprintf (f, "if (");
s->ifexpr->gen_gimple_transform (f, fail_label, NULL);
- fprintf (f, ")) goto %s;\n", fail_label);
+ fprintf (f, ")\n");
+ fprintf (f, "{\n");
}
- output_line_directive (f, s->result_location);
+// output_line_directive (f, s->result_location);
+
if (s->result->type == operand::OP_EXPR)
{
- e = static_cast <expr *> (s->result);
- fprintf (f, " *res_code = %s;\n", e->operation->op->id);
+ expr *e = static_cast <expr *> (s->result);
+ fprintf (f, "*res_code = %s;\n", e->operation->op->id);
for (unsigned j = 0; j < e->ops.length (); ++j)
{
char dest[32];
@@ -611,26 +982,61 @@ write_nary_simplifiers (FILE *f, vec<sim
}
/* Re-fold the toplevel result. It's basically an embedded
gimple_build w/o actually building the stmt. */
- fprintf (f, " gimple_resimplify%d (seq, res_code, type, "
+ fprintf (f, "gimple_resimplify%d (seq, res_code, type, "
"res_ops, valueize);\n", e->ops.length ());
}
else if (s->result->type == operand::OP_CAPTURE
|| s->result->type == operand::OP_C_EXPR)
{
s->result->gen_gimple_transform (f, fail_label,
- " res_ops[0]");
- fprintf (f, " *res_code = TREE_CODE (res_ops[0]);\n");
+ "res_ops[0]");
+ fprintf (f, "*res_code = TREE_CODE (res_ops[0]);\n");
}
else
gcc_unreachable ();
- fprintf (f, " return true;\n");
- fprintf (f, " }\n");
- fprintf (f, "%s:\n", fail_label);
+
+ fprintf (f, "return true;\n");
+ if (s->ifexpr)
+ fprintf (f, "}\n");
+
+ fprintf (f, "}\n");
+}
+
+
+
+void
+decision_tree::gen_gimple (FILE *f)
+{
+ write_fn_prototype (f, 1);
+ fprintf (f, "{ return gimple_match_and_simplify (code, type, op0, NULL_TREE, NULL_TREE, res_code, res_ops, seq, valueize); }\n\n");
+
+ write_fn_prototype (f, 2);
+ fprintf (f, "{ return gimple_match_and_simplify (code, type, op0, op1, NULL_TREE, res_code, res_ops, seq, valueize); }\n\n");
+
+ write_fn_prototype (f, 3);
+ fprintf (f, "{\n");
+
+ for (unsigned i = 0; i < root->kids.length (); i++)
+ {
+ dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
+ expr *e = static_cast<expr *>(dop->op);
+
+ if (i)
+ fprintf (f, "else ");
+ fprintf (f, "if (code == %s)\n", e->operation->op->id);
+ fprintf (f, "{\n");
+
+ for (unsigned j = 0; j < dop->kids.length (); ++j)
+ dop->kids[j]->gen_gimple (f);
+
+ fprintf (f, "}\n");
}
- fprintf (f, " return false;\n");
+
+ fprintf (f, "return false;\n");
fprintf (f, "}\n");
}
+
static void
outline_c_exprs (FILE *f, struct operand *op)
{
@@ -712,10 +1118,6 @@ write_gimple (FILE *f, vec<simplify *>&
/* Outline complex C expressions to helper functions. */
for (unsigned i = 0; i < simplifiers.length (); ++i)
outline_c_exprs (stdout, simplifiers[i]->result);
-
- write_nary_simplifiers (f, simplifiers, 1);
- write_nary_simplifiers (f, simplifiers, 2);
- write_nary_simplifiers (f, simplifiers, 3);
}
@@ -1043,7 +1445,14 @@ main(int argc, char **argv)
}
while (1);
+ decision_tree dt;
+ for (unsigned i = 0; i < simplifiers.length (); ++i)
+ dt.insert (simplifiers[i], i);
+
+ dt.print (stderr);
+
write_gimple (stdout, simplifiers);
+ dt.gen_gimple (stdout);
cpp_finish (r, NULL);
cpp_destroy (r);
Index: gcc/gimple-match-head.c
===================================================================
--- gcc/gimple-match-head.c (revision 211732)
+++ gcc/gimple-match-head.c (working copy)
@@ -706,3 +706,10 @@ gimple_match_and_simplify (gimple_stmt_i
return true;
}
+static tree
+do_valueize (tree (*valueize)(tree), tree op)
+{
+ if (valueize && TREE_CODE (op) == SSA_NAME)
+ return valueize (op);
+ return op;
+}