This is the mail archive of the
`gcc@gcc.gnu.org`
mailing list for the GCC project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*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 16:12:02 +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>

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 >>>> >> >>>>>> >>>> >> >> >>>> >> >>

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. */ @@ -559,6 +560,648 @@ capture::gen_gimple_match (FILE *f, cons } + +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 +print_flattened_operand (operand *o, FILE *f = stderr) +{ + 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 *); + + 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) +{ + return decision_tree::print_node (root, f); +} + +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"); +} + +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) + { + char child_opname[20]; + sprintf (child_opname, "t%u", temps[i]); + fprintf (f, "%s = gimple_call_arg (def_stmt, %u);\n", child_opname, i); + fprintf (f, "if (do_valueize (valueize, %s))\n", 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", temps[i]); + fprintf (f, "%s = gimple_assign_rhs%u (def_stmt);\n", child_opname, i + 1); + fprintf (f, "if (do_valueize (valueize, %s))\n", child_opname); + fprintf (f, "{\n"); + } +} + +unsigned +dt_operand::gen_gimple_expr (FILE *f, const char *opname) +{ + unsigned i; + expr *e = static_cast<expr *> (op); + + for (i = 0; i < e->ops.length (); ++i) + { + fprintf (f, "tree t%u = NULL_TREE;\n", dt_operand::temp_count); + temps.safe_push (temp_count); + temp_count++; + } + + 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", temps[i]); + fprintf (f, "%s = TREE_OPERAND (%s, %u);\n", child_opname, opname, i); + fprintf (f, "if (do_valueize (valueize, %s))\n", 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", temps[i]); + fprintf (f, "%s = CALL_EXPR_ARG (%s, %u);\n", child_opname, opname, i); + fprintf (f, "if (do_valueize (valueize, %s))\n", child_opname); + fprintf (f, "{\n"); + } +} + +unsigned +dt_operand::gen_generic_expr (FILE *f, const char *opname) +{ + unsigned i; + expr *e = static_cast<expr *> (op); + + for (i = 0; i < e->ops.length (); ++i) + { + fprintf (f, "tree t%u = NULL_TREE;\n", dt_operand::temp_count); + temps.safe_push (temp_count); + temp_count++; + } + + gen_generic_expr_expr (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); + } + 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 ("); + s->ifexpr->gen_gimple_transform (f, fail_label, NULL); + fprintf (f, ")\n"); + fprintf (f, "{\n"); + } +// output_line_directive (f, s->result_location); + + if (s->result->type == operand::OP_EXPR) + { + 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]; + snprintf (dest, 32, " res_ops[%d]", j); + e->ops[j]->gen_gimple_transform (f, fail_label, dest); + } + /* 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, " + "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"); + } + else + gcc_unreachable (); + + 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, "}\n"); +} + + static void write_nary_simplifiers (FILE *f, vec<simplify *>& simplifiers, unsigned n) { @@ -713,9 +1356,11 @@ write_gimple (FILE *f, vec<simplify *>& for (unsigned i = 0; i < simplifiers.length (); ++i) outline_c_exprs (stdout, simplifiers[i]->result); +#if 0 write_nary_simplifiers (f, simplifiers, 1); write_nary_simplifiers (f, simplifiers, 2); write_nary_simplifiers (f, simplifiers, 3); +#endif } @@ -1043,7 +1688,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; +}

**Follow-Ups**:**Re: [GSoC] decision tree first steps***From:*Prathamesh Kulkarni

**References**:**[GSoC] decision tree first steps***From:*Prathamesh Kulkarni

**Re: [GSoC] decision tree first steps***From:*Richard Biener

**Re: [GSoC] decision tree first steps***From:*Prathamesh Kulkarni

**Re: [GSoC] decision tree first steps***From:*Richard Biener

**Re: [GSoC] decision tree first steps***From:*Richard Biener

**Re: [GSoC] decision tree first steps***From:*Prathamesh Kulkarni

**Re: [GSoC] decision tree first steps***From:*Richard Biener

**Re: [GSoC] decision tree first steps***From:*Richard Biener

**Re: [GSoC] decision tree first steps***From:*Richard Biener

**Re: [GSoC] decision tree first steps***From:*Richard Biener

**Re: [GSoC] decision tree first steps***From:*Prathamesh Kulkarni

**Re: [GSoC] decision tree first steps***From:*Richard Biener

**Re: [GSoC] decision tree first steps***From:*Prathamesh Kulkarni

**Re: [GSoC] decision tree first steps***From:*Richard Biener

**Re: [GSoC] decision tree first steps***From:*Prathamesh Kulkarni

**Re: [GSoC] decision tree first steps***From:*Richard Biener

**Re: [GSoC] decision tree first steps***From:*Prathamesh Kulkarni

**Re: [GSoC] decision tree first steps***From:*Richard Biener

**Re: [GSoC] decision tree first steps***From:*Prathamesh Kulkarni

**Re: [GSoC] decision tree first steps***From:*Richard Biener

**Re: [GSoC] decision tree first steps***From:*Prathamesh Kulkarni

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |