[GSoC] decision tree first steps

[Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>]

I have few questions regarding genmatch:

a) Why is 4 hard-coded here: ?
in write_nary_simplifiers:
 fprintf (f, "      tree captures[4] = {};\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).

c) Remove for parsing capture in parse_expr since we reject outermost
captured expressions ?

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)


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 ?

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

* 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

* 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

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 ?

* 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 211017)
+++ gcc/genmatch.c	(working copy)
@@ -252,8 +252,358 @@ struct simplify {
   struct operand *result;
 };
 
+/* 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)
+    return;
+
+  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)
+    {
+      expr *e = static_cast<expr *>(op);
+      operand *o = new expr (e->operation);
+      operands.safe_push (o);
+      for (unsigned i = 0; i < e->ops.length(); ++i)
+        walk_operand_preorder (operands, e->ops[i]);
+    }
+  else
+    gcc_unreachable ();
+}
+
+void
+print_operand (operand *op)
+{
+  if (!op)
+    return;
+
+  if (op->type == operand::OP_CAPTURE)
+    fprintf (stderr, "capture: %s\n", (static_cast<capture *>(op))->where);
+  else if (op->type == operand::OP_PREDICATE)
+    fprintf (stderr, "predicate: %s\n", (static_cast<predicate *>(op))->ident);
+  else if (op->type == operand::OP_C_EXPR)
+    fprintf (stderr, "c_expr: %s\n", (static_cast<c_expr *>(op))->code);
+  else if (op->type == operand::OP_EXPR)
+    {
+      expr *e = static_cast<expr *>(op);
+      fprintf (stderr, "expr: %s\n", e->operation->op->id);
+      for (unsigned i = 0; i < e->ops.length(); ++i)
+	print_operand (e->ops[i]);
+    }
+}
+
+struct dt_operand {
+  enum dt_type { DT_EXPR, DT_CAPTURE, DT_HEAD, DT_SIMPLIFY };
+  enum dt_type type;
+  vec<dt_operand *> kids;
+  
+  dt_operand (enum dt_type type_): type (type_), kids (vNULL) {}
+  void append_op (dt_operand *op) { kids.safe_push (op); }
+  virtual void gen_gimple(FILE *, const char *) = 0;
+};
+
+struct dt_expr: public dt_operand
+{
+  e_operation *operation;
+  dt_expr (e_operation *operation_): dt_operand (DT_EXPR), operation (operation_) {}
+  virtual void gen_gimple(FILE *, const char *); 
+};
+
+struct dt_capture: public dt_operand
+{
+  const char *where;
+  dt_capture (const char *where_): dt_operand (DT_CAPTURE), where (where_) {}
+  virtual void gen_gimple(FILE *, const char *); 
+};
+
+struct dt_head: public dt_operand
+{
+  dt_head(): dt_operand (DT_HEAD) {}
+  virtual void gen_gimple(FILE *, const char *) {}
+};
+
+struct dt_simplify: public dt_operand
+{
+  operand *ifexpr;
+  operand *result;
+
+  dt_simplify (operand *ifexpr_, operand *result_): dt_operand (DT_SIMPLIFY), ifexpr (ifexpr_), result (result_) {}
+  virtual void gen_gimple(FILE *, const char *); 
+};
+
+void
+dt_expr::gen_gimple (FILE *f, const char *name)
+{
+  fprintf (f, "if (TREE_CODE (%s) != SSA_NAME)\n", name);
+  fprintf (f, "  return false;\n");
+
+  fprintf (f, "{\n");
+  fprintf (f, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", name);
+  fprintf (f, "if (is_gimple_assign (def_stmt) && gimple_assign_rhs_code(def_stmt) == %s )\n", operation->op->id);
+  fprintf (f, "{\n"); 
+
+  unsigned i;
+  for (i = 0; i < kids.length(); i++)
+    {
+	      fprintf (f, "{\n");
+	      fprintf (f, "tree op = gimple_assign_rhs1 (def_stmt);\n", i + 1);
+	      fprintf (f, "if (valueize && TREE_CODE (op) == SSA_NAME)\n");
+	      fprintf (f, "{\n");
+	      fprintf (f, "  op = valueize (op);\n");
+	      fprintf (f, "  if (!op) return false;\n");
+//	      gen_gimple_match_fail (f, label);
+	      fprintf (f, "}\n");
+	      kids[i]->gen_gimple (f, "op");
+	      fprintf (f, "}\n");
+    }
+  fprintf (f, "}\n}\n");
+}
+
+void
+dt_capture::gen_gimple (FILE *f, const char *op) 
+{
+  fprintf (f, "if (!captures[%s])\n"
+	   "  captures[%s] = %s;\n"
+	   "else if (captures[%s] != %s) return false;\n",
+	   this->where, this->where, op, this->where, op);
+//  gen_gimple_match_fail (f, 0); 
+
+  for (unsigned i = 0; i < kids.length (); i++)
+    kids[i]->gen_gimple (f, op);
+}
+
+void
+dt_simplify::gen_gimple (FILE *f, const char *)
+{
+  if (ifexpr)
+    {
+      fprintf (f, "  if (!");
+      ifexpr->gen_gimple_transform (f, 0);
+      fprintf (f, ") return false;\n");
+    }
+
+  if (result->type == operand::OP_EXPR)
+    {
+	  expr *e;
+	  e = static_cast<expr *>(result);
+	  fprintf (f, "   *res_code = %s;\n", e->operation->op->id);
+	  for (unsigned j = 0; j < e->ops.length (); ++j)
+	    {
+	      fprintf (f, "  res_ops[%d] = ", j);
+	      e->ops[j]->gen_gimple_transform (f, 0); 
+	      fprintf (f, ";\n");
+	    }
+	  /* 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 (result->type == operand::OP_CAPTURE
+	     || result->type == operand::OP_C_EXPR)
+	{
+	  fprintf (f, "      res_ops[0] = ");
+	  result->gen_gimple_transform (f, 0);
+	  fprintf (f, ";\n");
+	  fprintf (f, "      *res_code = TREE_CODE (res_ops[0]);\n");
+	}
+    else
+	gcc_unreachable ();
+  
+   fprintf (f, "return true;\n");
+}
 
 
+dt_operand *
+operand_to_dt_operand (operand *op)
+{
+  if (op->type == operand::OP_CAPTURE)
+    return new dt_capture ((static_cast<capture *>(op))->where);
+  else if (op->type == operand::OP_EXPR)
+    return new dt_expr ((static_cast<expr *>(op))->operation);
+  else
+    gcc_unreachable ();
+}
+
+struct decision_tree
+{
+  dt_head root;
+  
+  decision_tree() {}
+  void insert(struct simplify *);
+  void print(FILE *);
+  void gen_gimple (FILE *);
+  void print_dt_node (FILE *, dt_operand *);
+};
+
+void
+decision_tree::print_dt_node (FILE *fp, dt_operand *op)
+{
+  unsigned i;
+  
+  if (op->type == dt_operand::DT_EXPR)
+    fprintf (fp, "dt_expr: %s\n", (static_cast<dt_expr *>(op))->operation->op->id);
+  else if (op->type == dt_operand::DT_CAPTURE)
+    fprintf (fp, "dt_capture: %s\n", (static_cast<dt_capture *>(op))->where);
+  else if (op->type == dt_operand::DT_HEAD)
+    ;
+  else if (op->type == dt_operand::DT_SIMPLIFY)
+    {
+      fprintf (fp, "dt_simplify:\n");
+      dt_simplify *s = static_cast<dt_simplify *>(op);
+      if (s->ifexpr)
+	{
+	  fprintf (fp, "ifexpr:\n");
+	  print_operand (s->ifexpr);
+	}
+      if (s->result)
+	{
+	  fprintf (fp, "result:\n");
+	  print_operand (s->result);
+	}
+    }      
+  else
+    gcc_unreachable ();
+
+  if (op->kids.length() == 0) // base case
+    {
+      fprintf (stderr, "null\n");
+      return;
+    }
+  for (i = 0; i < op->kids.length(); i++) 
+    print_dt_node (fp, op->kids[i]);
+}
+
+void
+decision_tree::print (FILE *fp)
+{
+  print_dt_node (fp, &root);
+} 
+
+static bool
+dt_operand_equal_p (dt_operand *op1, dt_operand *op2)
+{
+  if (op1->type != op2->type)
+    return false;
+
+  if (op1->type == dt_operand::DT_EXPR)
+    {
+      dt_expr *e1 = static_cast<dt_expr *>(op1);
+      dt_expr *e2 = static_cast<dt_expr *>(op2);
+      if (!strcmp (e1->operation->op->id, e2->operation->op->id))
+	return true;
+      else
+	return false;
+    }
+  // captures ???
+  else if (op1->type == dt_operand::DT_CAPTURE)
+    {
+      dt_capture *capt1 = static_cast<dt_capture *>(op1);
+      dt_capture *capt2 = static_cast<dt_capture *>(op2);
+      if (!strcmp (capt1->where, capt2->where))
+	return true;
+      else
+	return false;
+    }
+  return false;
+}
+
+dt_operand *find_operand (vec<dt_operand *>& ops, operand *op)
+{
+  dt_operand *dt_op = operand_to_dt_operand (op);
+  unsigned i;
+ 
+  if (ops == vNULL)
+    return 0;
+
+  for (i = 0; i < ops.length(); i++)
+    if (dt_operand_equal_p (ops[i], dt_op))
+      return ops[i];
+
+  return 0;
+}
+
+void
+decision_tree::insert (struct simplify *s)
+{
+  // ??? s->match->type should always be OP_EXPR ? should we have this mandated during parsing ?
+  if (s->match->type != operand::OP_EXPR)
+    return;
+ 
+  expr *e = static_cast<expr *>(s->match);
+  vec<operand *> operands = vNULL;
+  walk_operand_preorder (operands, e);
+
+  dt_operand *p, *kid = 0, *prev = &root;
+  unsigned i;
+
+  for (i = 0, p = &root; i < operands.length() && (kid = find_operand (p->kids, operands[i])) != 0; prev = p, 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
+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, 2);
+  fprintf (f, "{ return false; }\n\n");
+
+  write_fn_prototype (f, 3);
+  fprintf (f, "{ return false; }\n\n");
+
+  write_fn_prototype (f, 1);
+  fprintf (f, "{\n");
+  
+  unsigned i;
+  dt_operand *dt_op;
+
+  fprintf (stderr, "root.kids.length = %u\n", root.kids.length());
+  for (i = 0; i < root.kids.length (); i++)
+    {
+      dt_op = root.kids[i];
+      if (dt_op->type != dt_operand::DT_EXPR)
+	continue;
+      dt_expr *e = static_cast<dt_expr *>(dt_op);
+      fprintf (f, "if (code == %s)\n{\n", e->operation->op->id);
+      fprintf (f, "tree captures[4] = {};\n");
+
+      // FIXME: works (hopefully!) only for patterns involving unary operators
+      char op[4] = "op0";
+      for (unsigned j = 0; j < e->kids.length(); j++)
+	e->kids[j]->gen_gimple (f, op);
+      fprintf (f, "}\n");
+    }
+
+  fprintf (f, "return false;\n}\n");
+}
+
 /* Code gen off the AST.  */
 
 static void
@@ -538,9 +888,11 @@ write_gimple (FILE *f, vec<simplify *>&
   /* Include the header instead of writing it awkwardly quoted here.  */
   fprintf (f, "#include \"gimple-match-head.c\"\n\n");
 
+#if 0
   write_nary_simplifiers (f, simplifiers, 1);
   write_nary_simplifiers (f, simplifiers, 2);
   write_nary_simplifiers (f, simplifiers, 3);
+#endif
 }
 
 
@@ -907,6 +1259,8 @@ main(int argc, char **argv)
 #undef DEF_BUILTIN
 
   vec<simplify *> simplifiers = vNULL;
+  decision_tree dt;
+  struct simplify *s;
 
   do
     {
@@ -919,7 +1273,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));
+	{
+	  s = parse_match_and_simplify (r);
+	  simplifiers.safe_push (s);
+	  dt.insert (s);
+	}
       else
 	fatal_at (token, "expected 'match_and_simplify'");
 
@@ -927,7 +1285,9 @@ main(int argc, char **argv)
     }
   while (1);
 
+//  dt.print (stderr);
   write_gimple (stdout, simplifiers);
+  dt.gen_gimple (stdout);
 
   cpp_finish (r, NULL);
   cpp_destroy (r);
Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 211017)
+++ gcc/match.pd	(working copy)
@@ -21,6 +21,21 @@ You should have received a copy of the G
 along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
 
+(match_and_simplify
+  (negate (negate @0))
+  @0)
+
+(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
+  (bit_not (bit_not @0))
+  if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
+  @0)
+
+#if 0
 /* Transforms formerly done by tree-ssa-forwprop.c:associate_plusminus  */
 
 /* ???  Have match_and_simplify groups guarded with common
@@ -196,3 +211,4 @@ to (minus @1 @0)
    variable-length stuff with pattern expressions.
 
  */
+#endif

int f1(int x)
{
  int t1 = -x;
  return -t1;
}

int f2(int x)
{
  int t1 = ~x;
  return -t1;
}

int f3(int x)
{
  int t1 = ~x;
  return ~t1;
}