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]

Re: [GSoC] decision tree first steps


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

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]