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*: Fri, 6 Jun 2014 14:32:50 +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>

On Mon, Jun 2, 2014 at 6:14 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Mon, Jun 2, 2014 at 1:16 PM, Prathamesh Kulkarni > <bilbotheelffriend@gmail.com> wrote: >> I have few questions regarding genmatch: >> >> a) Why is 4 hard-coded here: ? >> in write_nary_simplifiers: >> fprintf (f, " tree captures[4] = {};\n"); > > Magic number (this must be big enough for all cases ...). Honestly > this should be improved (but requires another scan over the matcher IL > to figure out the max N used in @N). > >> b) Should we add syntax for a symbol to denote multiple operators ? >> For exampleim in simplify_rotate: >> (X << CNT1) OP (X >> CNT2) with OP being +, |, ^ (CNT1 + CNT2 == >> bitsize of type of X). > > Something to enhance the IL with, yes. I'd say we support > > (define_op additive PLUS_EXPR MINUS_EXPR POINTER_PLUS_EXPR) > > thus, > > (define_op <operator-name> op...) > >> c) Remove for parsing capture in parse_expr since we reject outermost >> captured expressions ? > > but parse_expr is also used for inner expressions, no? > > (plus (minus@2 @0 @1) @3) > > should still work > >> d) I am not able to follow this comment in match.pd: >> /* Patterns required to avoid SCCVN testsuite regressions. */ >> >> /* (x >> 31) & 1 -> (x >> 31). Folding in fold-const is more >> complicated here, it does >> Fold (X << C1) & C2 into (X << C1) & (C2 | ((1 << C1) - 1)) >> (X >> C1) & C2 into (X >> C1) & (C2 | ~((type) -1 >> C1)) >> if the new mask might be further optimized. */ >> (match_and_simplify >> (bit_and (rshift@0 @1 INTEGER_CST_P@2) integer_onep) >> if (compare_tree_int (@2, TYPE_PRECISION (TREE_TYPE (@1)) - 1) == 0) >> @0) > > The comment is literally copied from the case I extracted the > (simplified) variant from fold-const.c. See lines 11961-12056 in fold-const.c. > It'll be a challenge to implement the equivalent in a pattern ;) > >> >> Decision Tree. >> I have tried to come up with a prototype for decision tree (patch attached). >> For simplicity, it handles patterns involving only unary operators and >> no predicates >> and returns false when the pattern fails to match (no goto to match >> another pattern). >> I meant to post it only for illustration, and I have not really paid >> attention to code quality (bad formatting, memory leaks, etc.). >> >> * Basic Idea >> A pattern consists of following parts: match, ifexpr and result. >> Let's call <ifexpr, result> as "simplification" operand. >> The common prefix between different match operands would be represented >> by same nodes in the decision tree. >> >> Example: >> (negate (bit_not @0)) >> S1 >> >> (negate (negate @0)) >> S2 >> >> S1, S2 denote simplifications for the above patterns respectively. >> >> The decision tree would look something like >> (that's the way it gets constructed with the patch): >> >> dummy/root >> | >> NEGATE_EXPR >> / \ >> BIT_NOT NEGATE_EXPR >> | | >> @0 @0 >> | | >> S1 S2 >> >> a) The children of an internal node are number of decisions that >> can be taken at that node. In the above case it's 2 for outer NEGATE_EXPR. >> b) Simplification operand represents leaves of the decision tree >> c) Instead of having list of heads, I have added one dummy node, >> and heads become children of these dummy root node. >> d) Code-gen for non-simplification operands involves generating, >> "matching" code and for simplification operands involves generating >> "transform" code >> >> * Overall Flow: >> I guess we would build the decision tree from the AST. >> So the flow would be like: >> source -> struct simplify (match, ifexpr, result) -> decision tree -> c code. >> >> Something like (in main): >> decision_tree dt; >> while (there is another pattern) >> { >> simplify *s = parse_match_and_simplify (); >> insert s into decision tree; >> }; >> So parsing routines are concerned with parsing and building the AST (operand), >> and not with the decision tree. Is that fine ? > > Yes, that's good. > >> * Representation of decision tree. >> A decision tree would need a way to represent language constructs >> like capture, predicate, etc. so in some ways it would be similar to AST. >> It >> In the patch, I have created the following heirarchy: >> dt_operand: represents a general base "operand" of in decision tree >> dt_expr: for representing expression. Expression contains operation >> to be performed (e_operation). >> dt_capture: analogous to capture. >> dt_simplify: for representing "simplification" operand. >> simplification consists of ifexpr and result >> dt_head: to represent "dummy" root. Maybe a separate class is not needed. >> >> * Constructing decision tree from AST >> The algorithm i have used is similar to inserting string in a trie >> outlined here: http://en.wikipedia.org/wiki/Trie >> The difference shall be to traverse AST depth-first rather than >> traversing the string. >> Apart from that I guess it would be the same (naturally find and >> compare operations would be different). >> I haven't given much thought about this. Currently, I construct >> decision tree for only patterns with unary operators in an >> ugly way by "flattening" the AST by walking it in pre-order and >> storing the nodes in vector in the order they are visited >> >> So to construct decision tree from the following AST: >> negate >> | >> bit_not >> | >> @0 >> >> AST is flattened by walking in preorder (by walk_operand_preorder) and stored >> as: [ expr, expr, capture ] >> and this vector is used to construct decision tree. >> I did it as a "quick and dirty" way, it has to be changed. >> And it won't work for patterns with n-ary operators. >> >> We should visit each node of AST in preorder, and add that node >> during traversal to decision tree. I am not yet clear on way of doing that. >> >> * Comparing operands >> How do we compare operands ? We shall need to do this while inserting >> in decision tree, since if the operand is already inserted we do not create >> a new node. >> In the patch (cmp_operand), I have used following rules: >> a) if types not equal, they are clearly not equal. >> b) if type is expr, compare operation->op->id >> c) if type is capture, compare the number. >> d) for predicate, compare on ident ? >> >> * Representing patterns with n-ary operators. >> Consider following two match operands: >> (plus (minus @0 @1) @1) >> (plus (negate @0) @1) >> >> In decision tree, it would be represented as: >> >> *********plus********* >> / \ / \ >> minus @1 negate @1 >> / \ | >> @0 @1 @0 >> >> plus has got 4 children - (minus @0 @1), @1, (negate @0), @1. >> However (minus @0 @1) and @1 are not separate "decisions", but >> children of plus within the same expression. >> >> For calculating number of decisions at an expression node: >> number of decisions = number of children / arity of operator. >> in the above case, number of decision = 4 / 2 = 2 >> >> For other cases, for instance capture node (the children would be >> simplification operand), >> number of decisions = number of children. > > Hmm. I think it should be only two children from the plus, > as pre-order for the first pattern is for example > [plus minus @0 @1 @1] so you'd have > > plus > / \ > minus negate > | | > @0 @0 > | | > @1 @1 > | > @1 > > instead? > > Note that you probably have to deal with non-matching capture > IDs by re-writing them on-the-fly. That is, the two > pre-oder traversals [plus minus @1 ...] and [plus minus @0 ...] > should commonize with renaming the non-matching capture > somehow. Um, could you please elaborate on that (non-matching capture ?), I am not sure if I understood it fully, thanks. I have attached patch for patterns with binary operators (in principle should work for n-ary operators, but have only tested upto 2), that creates decision tree for patterns (excluding predicates, and multiple matching). I don't intend to commit this (contains many hacks!). * Constructing decision tree from AST We can define our decision tree to store prefixes of preorder traversals of diffferent AST. Insertion happens as follows (decision_tree::insert) a) Get preorder traversal of AST into vector. b) Insert AST nodes from vector into decision tree. Currently, I obtain preorder traversal into a vector. We can later change it to compute next preorder successor lazily. * Code-gen For n-ary operators, the patch generates code as follows: if (code == <expr code>) { match operand 0 match operand 1 .... match operand n-1 transform return true; } * Adding parent, level, pos fields to AST (operand). One change (hack), I have made to code-gen, is naming of operands that are assigned to gimple_assign_rhs in code-gen of expressions. I am not sure if this is really needed. in AST, we have following representation for expressions: expr- / \ left right operand operand code-gen off AST (expr::gen_gimple_match) produces code like: { tree op = gimple_assign_rhs1 (def_stmt); // code-gen for left operand } { tree op = gimple_assign_rhs2 (def_stmt); // code-gen for right operand } We can do this since, in expr::gen_gimple_match, we call left_operand->gen_gimple_match, come back to expr::gen_gimple_match (after left_operand->gen_gimple_match() returns), and then call right_operand->gen_gimple_match(). However in decision tree, the expression gets represented as follows: expr | left-operand | right-operand dt_expr::gen_gimple calls left_operand->gen_gimple, which calls right_operand->gen_gimple, so we return to dt_expr::gen_gimple, after code is generated for the whole subtree of expr. So I assign operands at the start before generating code for the subtree: tree op00 = gimple_assign_rhs1 (def_stmt); tree op10 = gimple_assign_rhs2 (def_stmt); <code for left-operand> <code for right-operand> each of the operands know their positions, so they know which operand to use (get_op_name()). the names are generated as: op<position><level>, position = index of operand in it's parent's expr's vector (vec<operand *> ops). level: level of AST, at which the operand is stored. For this I added three fields to operand (unsigned pos, and unsigned level, operand *parent), and accordingly made changes to expr::append_op. In a way this is abusing the AST. This probably works (works with test-cases i tried), but I don't like it much. * Order of matching. Currently the order of matching operands is strictly 0, 1, .. n - 1 for n-ary operator. However this might not be the best choice. For example, consider following patterns: (operator op1 op) S1 (operator op2 op) S2 Both have common operator, and 1st common operand, they differ in 0th operand. With patch, the code generated is: if (code == <expr-code>) { match op1 match op S1 match op2 match op S2 } A better ordering would be to match the 1st operand and then respective 0th operands of both patterns: if (code == <expr-code> { match op match op1 S1 match op0 S2 } This complicates insertion into decision tree. * hack: only one generated gimple_match_and_simplify function In the patch, I generate code for gimple_match_and_simplify with 3 operands version (op0, op1, op2) and the other two (unary and binary versions), call it with NULL_TREE for extra operands. I will soon change that. * Testing patterns. I think I have written most of the test-cases wrongly in match-2.c For example this test-case doesn't match (i haven't checked in "fix testsuite fallout" patch, so this might not be true anymore) (match_and_simplify plus (minus @0 @1) @1) @0) for this test-case: /* (x - y) + y -> x */ int f6(int x, int y) { int t1 = x - y; return t1 + y; } /* { dg-final { scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\)" "forwprop1" } } */ I get following output (tree-forwprop-details): ;; Function f6 (f, funcdef_no=0, decl_uid=1744, symbol_order=0) gimple_match_and_simplified to _4 = y_2(D) + t1_3; f (int x, int y) { int t1; int _4; <bb 2>: t1_3 = x_1(D) - y_2(D); _4 = x_1(D); return _4; } Shouldn't it show: gimple_match_and_simplified to _4 = x_1(D) instead ? The issue is this test-case fails in isolation, however it passes when it is placed with other test cases that PASS and have same regex in scan-tree-dump as this test-case: scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\)" Summary: I think we need to (at-least) deal with following problems for decision tree: a) Representation and construction of decision tree from AST - We do this by storing prefixes of preorder traversals of AST in decision tree. Do we finalize on that ? b) Order of operand matching c) Generating patterns for built-in functions (I guess this will be similar to expr-gen). d) Multiple matching patterns e) Commutative ops Pattern Enhancements: Some of these were already discussed, I am jotting them here: a) Symbol for multiple operators b) grouping patterns by ifexpr c) should we have MATCH_FAILED or FAIL to explicitly denote failure in manual transform (c_expr) ? d) making operators to be commutative. Once the decision tree is done, I can try working on these. Till Sunday, I will attempt to have another prototype, that covers most of the patterns in match.pd (except for cond_expr, and those requiring GENERIC support), and accompanying correct test-case for each pattern. And next-week start working on a fair patch. 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 211234) +++ gcc/genmatch.c (working copy) @@ -157,10 +157,17 @@ add_builtin (enum built_in_function code 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; + operand *parent; + unsigned pos; + unsigned level; + + operand (enum op_type type_) : type (type_), parent (0), pos (0), level (0) {} + 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; + }; struct predicate : public operand @@ -181,9 +188,10 @@ struct expr : public operand { expr (e_operation *operation_) : operand (OP_EXPR), operation (operation_), ops (vNULL) {} - void append_op (operand *op) { ops.safe_push (op); } + void append_op (operand *op) { ops.safe_push (op); op->parent = this; op->pos = this->ops.length() - 1; op->level = this->level + 1; } 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 *); }; @@ -257,6 +265,358 @@ struct simplify { }; +struct dt_node +{ + enum dt_type { DT_CAPTURE, DT_EXPR, DT_ROOT, DT_SIMPLIFY }; + enum dt_type type; + vec<dt_node *> kids; + + dt_node (enum dt_type type_): type (type_), kids (vNULL) {} + virtual void gen_gimple(FILE *f) = 0; +}; + +struct dt_operand: public dt_node +{ + operand *op; + unsigned pos; + + dt_operand (operand *op_, enum dt_type type_): dt_node (type_), op (op_) {} + virtual void gen_gimple(FILE *f) = 0; +}; + +struct dt_expr: public dt_operand +{ + dt_expr (expr *expr_): dt_operand (expr_, DT_EXPR) {} + virtual void gen_gimple (FILE *f); +}; + +struct dt_capture: public dt_operand +{ + dt_capture (capture *capt_): dt_operand (capt_, DT_CAPTURE) {} + virtual void gen_gimple (FILE *f); +}; + +struct dt_simplify: public dt_node +{ + operand *ifexpr; + operand *result; + + dt_simplify (operand *ifexpr_, operand *result_): dt_node (DT_SIMPLIFY), ifexpr (ifexpr_), result (result_) {} + virtual void gen_gimple (FILE *f); +}; + +struct dt_root: public dt_node +{ + dt_root (): dt_node (DT_ROOT) {} + virtual void gen_gimple (FILE *f) {} +}; + +struct decision_tree +{ + dt_root *root; + static unsigned counter; + + decision_tree() { root = new dt_root(); } + void print (FILE *f = stderr); + void gen_gimple (FILE *f); + void insert (struct simplify *); + +}; +unsigned decision_tree::counter=0; + +void print_operand (FILE *, operand *); + +void +print_dt_node (dt_node *p, FILE *f = stderr) +{ + + if (p->type == dt_node::DT_CAPTURE) + fprintf (f, "@%s\n", ((static_cast<capture *>((static_cast <dt_operand *>(p))->op)))->where); + + else if (p->type == dt_node::DT_EXPR) + { + expr *e = (static_cast<expr *>((static_cast<dt_operand *>(p))->op)); + fprintf (f, "%s\n", e->operation->op->id); + } + + else if (p->type == dt_node::DT_ROOT) + fprintf (f, "root\n"); + + else if (p->type == dt_node::DT_SIMPLIFY) + fprintf (f, "simplify\n"); + + if (p->kids == vNULL) + fprintf (f, "null\n"); + + for (unsigned i = 0; i < p->kids.length(); ++i) + print_dt_node (p->kids[i], f); +} + +void decision_tree::print (FILE *f) +{ + print_dt_node (root, f); +} + + +dt_operand * +operand_to_dt_operand (operand *o) +{ + if (o->type == operand::OP_CAPTURE) + return new dt_capture (static_cast<capture *>(o)); + else if (o->type == operand::OP_EXPR) + return new dt_expr (static_cast<expr *>(o)); + else + { + fprintf (stderr, "unexpected type %u\n", (unsigned) o->type); + gcc_unreachable (); + } +} + +bool +cmp_operand (dt_node *node, operand *o) +{ + if (node->type == dt_node::DT_EXPR && o->type == operand::OP_EXPR) + { + expr *e1 = static_cast<expr *>((static_cast<dt_expr *>(node))->op); + expr *e2 = static_cast<expr *>(o); + return strcmp (e1->operation->op->id, e2->operation->op->id) == 0; + } + + else if (node->type == dt_node::DT_CAPTURE && o->type == operand::OP_CAPTURE) + { + capture *c1 = static_cast<capture *>((static_cast<dt_capture *>(node))->op); + capture *c2 = static_cast<capture *>(o); + return strcmp (c1->where, c2->where) == 0; + } + + return false; +} + +dt_node * +find_operand (vec<dt_node *>& ops, operand *o) +{ + for (unsigned i = 0; i < ops.length(); i++) + if (cmp_operand (ops[i], o)) + return ops[i]; + + return 0; +} + +void +decision_tree::insert (struct simplify *s) +{ +// print_operand (stderr, s->match); + + if (s->match->type != operand::OP_EXPR) + return; + + void walk_operand_preorder (vec<operand *>&, operand *); + + expr *e = static_cast<expr *>(s->match); + vec<operand *> operands = vNULL; + walk_operand_preorder (operands, e); + + unsigned i; + dt_node *p, *kid = 0; + + for (i = 0, p = root; i < operands.length() && (kid = find_operand (p->kids, operands[i])) != 0; p = kid, ++i) + ; + + if (kid == 0) + { + for (; i < operands.length(); i++) + { + p->kids.safe_push (operand_to_dt_operand (operands[i])); + p = p->kids[p->kids.length() - 1]; + } + } + + p->kids.safe_push (new dt_simplify (s->ifexpr, s->result)); +} + + +void +get_op_name (operand *op, char *name) +{ + operand *o = op->parent; + if (o->level) + sprintf (name, "op%d%d", op->pos, o->level); + else + sprintf (name, "op%d", op->pos); +} + +void +dt_capture::gen_gimple (FILE *f) +{ + char name[128]; + get_op_name (op, name); + capture *capt = static_cast<capture *>(op); + char capture_label[128]; + sprintf (capture_label, "L%u", decision_tree::counter++); + + fprintf (f, "if (!captures[%s])\n{\ncaptures[%s] = %s;\n goto %s;\n}\n", capt->where, capt->where, name, capture_label); + fprintf (f, "else if (captures[%s] == %s)\n{\n%s:\n", capt->where, name, capture_label); + + for (unsigned i = 0; i < kids.length(); i++) + kids[i]->gen_gimple (f); + + fprintf (f, "}\n"); + fprintf (f, "captures [%s] = NULL_TREE;\n", capt->where); +} + +void +dt_expr::gen_gimple (FILE *f) +{ + char name[128]; + + get_op_name (op, name); + expr *e = static_cast<expr *>(op); + + fprintf (f, "{\n" + " if (TREE_CODE (%s) == SSA_NAME)\n{\n" + " gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n" + " if (is_gimple_assign (def_stmt) && gimple_assign_rhs_code (def_stmt) == %s)\n{\n", + name, name, e->operation->op->id); + + char num[128]; + unsigned i; + + for (i = 0; i < e->ops.length (); i++) + { + sprintf (num, "op%d%d", e->ops[i]->pos, e->level); + fprintf (f, " tree %s = gimple_assign_rhs%d (def_stmt);\n", num, i + 1); + fprintf (f, "if (valueize && TREE_CODE (%s) == SSA_NAME)\n", num); + fprintf (f, "{\n"); + fprintf (f, " %s = valueize (%s);\n", num, num); + fprintf (f, " if (!%s) return false;\n", num); + fprintf (f, "}\n"); + } + + for (i = 0; i < kids.length(); i++) + kids[i]->gen_gimple (f); + + fprintf (f, "}\n}\n}\n"); +} + +void +dt_simplify::gen_gimple(FILE *f) +{ + dt_simplify *s = this; + char *fail_label = 0; + + if (s->ifexpr) + { + fprintf (f, " if (!("); + s->ifexpr->gen_gimple_transform (f, fail_label, NULL); + fprintf (f, ")) return false;"); + } + if (s->result->type == operand::OP_EXPR) + { + expr *e; + 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"); +} + +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"); +} + +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"); + + fprintf (stderr, "root->kids.len = %u\n", root->kids.length ()); + for (unsigned i = 0; i < root->kids.length (); i++) + { + dt_expr *dt_e = static_cast <dt_expr *>(root->kids[i]); + expr *e = static_cast <expr *>(dt_e->op); + fprintf (f, "if (code == %s)\n{\ntree captures[4] = {};\n", e->operation->op->id); + + for (unsigned j = 0; j < dt_e->kids.length(); j++) + dt_e->kids[j]->gen_gimple (f); + + fprintf (f, "}\n"); + } + + fprintf (f, "return false;\n}\n"); +} + + +/* walk operand AST in preorder and store visited nodes in operands vector + * FIXME: temporary hack, remove later + */ + +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; + } + + else if (op->type == operand::OP_EXPR) + { + operands.safe_push (op); + expr *e = static_cast<expr *>(op); + for (unsigned i = 0; i < e->ops.length(); ++i) + walk_operand_preorder (operands, e->ops[i]); + } + else + gcc_unreachable (); +} + +void +print_operand (FILE *f, operand *o) +{ + fprintf (f, "%p, %d, ", (void *) o, o->pos); + if (o->type == operand::OP_CAPTURE) + fprintf (f, "@%s\n", (static_cast<capture *>(o))->where); + else if (o->type == operand::OP_EXPR) + { + expr *e = static_cast <expr *>(o); + fprintf (f, "%s\n", e->operation->op->id); + + for (unsigned i = 0; i < e->ops.length (); i++) + print_operand (f, e->ops[i]); + } +} /* Code gen off the AST. */ @@ -653,9 +1013,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 } @@ -992,6 +1354,7 @@ main(int argc, char **argv) #undef DEF_BUILTIN vec<simplify *> simplifiers = vNULL; + decision_tree dt; do { @@ -1004,7 +1367,11 @@ main(int argc, char **argv) const char *id = get_ident (r); if (strcmp (id, "match_and_simplify") == 0) - simplifiers.safe_push (parse_match_and_simplify (r)); + { + simplify *s = parse_match_and_simplify (r); + dt.insert (s); + simplifiers.safe_push (s); + } else fatal_at (token, "expected 'match_and_simplify'"); @@ -1012,8 +1379,9 @@ main(int argc, char **argv) } while (1); + dt.print(); write_gimple (stdout, simplifiers); - + dt.gen_gimple (stdout); cpp_finish (r, NULL); cpp_destroy (r); Index: gcc/match.pd =================================================================== --- gcc/match.pd (revision 211234) +++ gcc/match.pd (working copy) @@ -21,6 +21,63 @@ You should have received a copy of the G along with GCC; see the file COPYING3. If not see <http://www.gnu.org/licenses/>. */ +/* -(-x) -> x */ +(match_and_simplify + (negate (negate @0)) + @0) + +/* (A +- B) - A -> +-B. */ +(match_and_simplify + (MINUS_EXPR (PLUS_EXPR @0 @1) @0) + if (!TYPE_SATURATING (TREE_TYPE (@0)) + && !FLOAT_TYPE_P (TREE_TYPE (@0)) && !FIXED_POINT_TYPE_P (TREE_TYPE (@0))) + @1) + +/* (x - y) - x -> -y */ +(match_and_simplify + (minus (minus @0 @1) @0) + (negate @1)) + +/* x - (-y) -> y + x */ +(match_and_simplify + (minus @0 (negate @1)) + if (!TYPE_SATURATING (type)) + (plus @0 @1)) + +/* x - (x + y) -> -y */ +(match_and_simplify + (minus @0 (plus @0 @1)) + (negate @1)) + +/* x - (x - y) -> y */ +(match_and_simplify + (minus @0 (minus @0 @1)) + @1) + +/* x & x -> x */ +(match_and_simplify + (bit_and @0 @0) + if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) + @0) + +/* x & ~x -> 0 */ +(match_and_simplify + (bit_and @0 (bit_not @0)) + if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) + { build_int_cst (type, 0); }) + +/* ((x & y) & ~x) -> 0 */ +(match_and_simplify + (bit_and (bit_and @0 @1) (bit_not @0)) + if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) + { build_int_cst (type, 0); }) + +/* x ^ x -> 0 */ +(match_and_simplify + (bit_xor @0 @0) + { build_int_cst (type, 0); }) + +#if 0 /* Simple constant foldings to substitute gimple_fold_stmt_to_constant_2. */ (match_and_simplify (plus @0 integer_zerop) @@ -386,3 +443,4 @@ to (minus @1 @0) variable-length stuff with pattern expressions. */ +#endif

/* --x -> x */ int f1(int x) { int t1 = -x; return -t1; } /* x + y - x -> y */ int f2(int x, int y) { int t1 = x + y; return t1 - x; } /* (x - y) - x -> -y */ int f3(int x, int y) { int t1 = x - y; return t1 - x; } /* x - (-y) -> y + x */ int f4(int x, int y) { int t1 = -y; return x - t1; } /* x - (x + y) -> -y */ int f5(int x, int y) { int t1 = x + y; return x - t1; } /* x - (x - y) -> y */ int f6(int x, int y) { int t1 = x - y; return x - t1; } /* x & x -> x */ int f7 (int x) { int t1 = x; return x & t1; } /* x & ~x -> 0 */ int f8 (int x) { int t1 = ~x; return x & t1; } /* (x & y) & ~x -> 0 */ int f9 (int x, int y) { int t1 = x & y; int t2 = ~x; return t1 & t2; } /* x ^ x -> 0 */ int f10 (int x) { int t1 = x; return t1 ^ x; }

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

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

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

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

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