On Mon, Jun 2, 2014 at 6:14 PM, Richard Biener
<richard.guent...@gmail.com> wrote:
> On Mon, Jun 2, 2014 at 1:16 PM, Prathamesh Kulkarni
> <bilbotheelffri...@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;
}
