Re: [GSoC] decision tree first steps

[Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>]

On Mon, Jun 16, 2014 at 4:45 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Mon, Jun 16, 2014 at 1:07 AM, Prathamesh Kulkarni
> <bilbotheelffriend@gmail.com> wrote:
> > On Sat, Jun 14, 2014 at 12:43 PM, Richard Biener
> > <richard.guenther@gmail.com> wrote:
> > I have attached patch that tries to implement decision tree using the
> > above algorithm.
> > (haven't done for built-in function yet, but that would be similar to
> > expr, so i guess no new issues may come up
> > for that).
>
> Great.
>
> > * AST representation
> > Added two more classes to AST - true_operand and match_operand to
> > represent "true" and "match" operands
> > respectively. captures are built during parsing, and are "lowered" to
> > either true_operand or match_operand
> > while inserting AST operands in decision tree (lower_capture).
>
> Hmm, ok.  I'd have made them decision tree node classes instead,
> but it's a matter of taste I guess.
>
> +      // or maybe keep a parallel bool indexes_empty array instead of
> using capture_max to denote "not seen" ?
> +      for (unsigned i = 0; i < capture_max; ++i)
> +       indexes[i] = level_max;
>
> using a special value is fine.
>
> > * Mapping capture index to preorder level
> > dt_simplify::indexes (unsigned *indexes) provides mapping from capture
> > index -> level.
> > eg: indexes[1] = 2 represent @1 is at level 2 in preorder traversal of AST.
> >
> > * true_operand is always placed as last child of the decision tree
> > node during insertion (dt_node::append_node),
> > since we want to process that last (if all other decisions fail).
>
> right.
>
> > * Code gen
> > Unfortunately, the patch still contains hacks for code-gen.
> > One such hack is adding three fields - (parent, preorder_level, pos) to operand.
> > They should really be part of decision tree, but since code-gen happens off AST,
> > I needed to place them there.
> > For removing that, I am thinking to put information required for
> > code-gen in another struct (say operand_info?)
> > struct operand_info
> > {
> >   operand *op;
> >   unsigned pos;
> >   operand *parent;
> >   unsigned preorder_level;
> > };
>
> Eventually you can just pass the info to the code-generators as extra
> arguments?  That is, I would get rid of the AST methods for generating
> the matching code and just do everything in the DT traversal.  That is,
> find a better abstraction here.
>
> > a) The metadata of operand (pos, parent, preorder_level) can be
> > computed during preorder_traversal
> > in walk_operand_preorder.
> > b) Stick operand_info into decision tree (dt_operand) instead of operand.
> > Is that fine ?
>
> Yes, that would work, but as code-gen off the DT should be quite
> simple I'd rather not complicate things with too much C++ abstraction
> (yeah, it's probably my fault to introduce it in the first place).
>
> > Code-gen for operands is slightly changed.
> > the temporary is created at expression's operand node rather than at
> > the expression's node itself.
> > Each operand knows it's name.
> >
> > It's name is computed as follows (dt_operand::gen_gimple):
> > opname = op<pos> (if operand's parent is root).
> > or opname = o<preorder level of parent node> if operand's parent is
> > true_operand or match_operand
> > or opname = gimple_assign_rhs <pos+1>(def_stmt<preorder level of
> > parent node>); // if operand's parent is non-root expr
> > for built-in functions it would be:
> > or opname = gimple_call_arg (def_stmt<preorder level of parent node>, <pos>);
>
> Hmm, in code-gen I see
>
>   if (code == MINUS_EXPR)
>     {
>         {
>           tree o1 = op0;
>           if (TREE_CODE (o1) == SSA_NAME)
>             {
>               gimple def_stmt1 = SSA_NAME_DEF_STMT (o1);
>               if (is_gimple_assign (def_stmt1) &&
> gimple_assign_rhs_code (def_stmt1) == PLUS_EXPR)
>                 {
> ...
>                 }
>             }
>         }
>         {
>           tree o1 = op0;
>           if (TREE_CODE (o1) == SSA_NAME)
>             {
>               gimple def_stmt1 = SSA_NAME_DEF_STMT (o1);
>               if (is_gimple_assign (def_stmt1) &&
> gimple_assign_rhs_code (def_stmt1) == MINUS_EXPR)
>                 {
> ...
>
> for the DT part
>
> root, 2
> |--operand: MINUS_EXPR, 2
> |----operand: PLUS_EXPR, 1
> ...
> |----operand: MINUS_EXPR, 1
> ...
>
> but I would have expected the preamble for the inner
> PLUS_EXPR/MINUS_EXPR check to be unified.  Thus
>
> if (code == MINUS_EXPR)
>   {
>     tree o1 = op0;
>     if (TREE_CODE (op1) == SSA_NAME)
>       {
>          gimple def_stmt1 = SSA_NAME_DEF_STMT (o1);
>          if (is_gimple_assign (def_stmt1))
>            {
>               if (gimple_assign_rhs_code (def_stmt1) == PLUS_EXPR)
>                 {
> ...
>                 }
>               else if (gimple_assign_rhs_code (def_stmt) == MINUS_EXPR)
>                 {
> ...
>                 }
>
> That means a better factoring of code-generation would be necessary,
> with possibly sorting the kids array after operand kind.
>
>
> > * Added do_valueize () in gimple-match-head.c. the generated code
> > calls do_valueize to valueize theopereand.
> > This make code-gen simpler (no goto).
>
> Good.
>
> > Example:
> > for the pattern:
> > (match_and_simplify
> >   (minus (plus @0 @1) @1)
> >   @0)
> >
> > it produces following code (literally taken from gimple-match.c after
> > running thru indent):
> > http://pastebin.com/EaFHZMAF
> >
> > For non-matching captures (capt->what->type == operand::OP_EXPR), I
> > tested with few
> > bogus patterns, unfortunately I don't know how to write test-cases for
> > these patterns present in match.pd
> > involving non-matching captures:
> >
> > /* The following is simplification done by gimple_fold_stmt_to_constant_1
> >    to aid propagation engines, producing is_gimple_min_invariants from
> >    invariant_addr + cst.  It may not be generally wanted
> >    (builtin-object-size) and thus may want to be restricted to 'simple'
> >    forms like &mem-ref or &decl.  */
> > (match_and_simplify
> >   (pointer_plus (addr@2 @0) INTEGER_CST_P@1)
> >   if (is_gimple_min_invariant (@2))
> >   {
> >     HOST_WIDE_INT off;
> >     tree base = get_addr_base_and_unit_offset (@0, &off);
> >     off += tree_to_uhwi (@1);
> >     /* Now with that we should be able to simply write
> >        (addr (mem_ref (addr @base) (plus @off @1)))  */
> >     build1 (ADDR_EXPR, type,
> >             build2 (MEM_REF, TREE_TYPE (TREE_TYPE (@2)),
> >                     build_fold_addr_expr (base),
> >                     build_int_cst (ptr_type_node, off)));
> >   })
> >
> >
> > * Patterns requiring GENERIC support like cond_expr
> > I am not sure about how to handle these patterns. I was thinking about
> > handling them after we have
> > GENERIC code generation in place.
>
> Yeah, though handling GENERIC for matching is as simple as
> emitting the code check twice, the 2nd check off the an else
> from the if (TREE_CODE (op) == SSA_NAME).  That is,
> arrange for expr::gen_gimple_match_dt to emit
>
>    if (TREE_CODE (...) == SSA_NAME)
>      {
>         gimple def_stmt = SSA_NAME_DEF_STMT (...);
>         if (is_gimple_assign (def_stmt) && gimple_assign_rhs_code
> (def_stmt) == <code>)
>           {
>   ....
>      }
>    else (TREE_CODE (...) == <code>)
>      {
>   ....
>      }
>
> which would require some refactoring in the generator.  As for refactoring
> it I'd not hook the gen_gimple_match_dt off the AST operands but
> inline it in the decision tree traversal routine - that also makes the
> commoning above easier.
Thanks, I shall get started on this.
>
> Btw, I checked what we generate for (bogus)
>
> (match_and_simplify
>   (MINUS_EXPR (PLUS_EXPR@2 @0 @1) @2)
>   @1)
>
> and the DT looks like
>
> root, 1
> |--operand: MINUS_EXPR, 1
> |----operand: true, 1
> |------operand: PLUS_EXPR, 1
> |--------operand: true, 1
> |----------operand: true, 1
> |------------operand: match(1), 1
> |--------------simplify_0, 0
>
> though I expected
>
> root, 1
> |--operand: MINUS_EXPR, 1
> |----operand: PLUS_EXPR, 1
> |------operand: true, 1
> |--------operand: true, 1
> |----------operand: match(1), 1
> |------------simplify_0, 0
>
> that is, I wonder where the extra "true" comes from.
Thanks, fixed it in the current patch.
>
>
> For
>
> (match_and_simplify
>   (MINUS_EXPR @2 (PLUS_EXPR@2 @0 @1))
>   @1)
>
> I get
>
> root, 1
> |--operand: MINUS_EXPR, 1
> |----operand: true, 1
> |------operand: match(1), 1
> |--------operand: PLUS_EXPR, 1
> |----------operand: true, 1
> |------------operand: true, 1
> |--------------simplify_0, 0
>
> which looks good to me.
>
> There is still a fallthru for all match failures but the DT should ensure
> that once any of the checks is false we can terminate - that is,
> we never have to backtrack.  Sth simple like
>
> --- genmatch.c.orig     2014-06-16 12:57:38.401890454 +0200
> +++ genmatch.c  2014-06-16 12:58:03.451888730 +0200
> @@ -816,6 +816,7 @@
>    unsigned i;
>    for (i = 0; i < kids.length (); ++i)
>      kids[i]->gen_gimple (f);
> +  fprintf (f, "return false;\n");
>
>
>    for (i = 0; i < n_braces; ++i)
>      fprintf (f, "}\n");
>
> So overall I think we are ok sofar and don't need major changes in
> the algorithm.
>
> I'd say add the missing call support and we're good to go ripping out
> the non-decision tree path.
>
> I'm happy to do some of the refactoring that I'd like to see myself
> so you can concentrate on pattern implementing for phase 2.  But
> feel free to do some of it yourself.
>
> > Small point: I was wondering if it's a good idea to slightly change
> > the syntax of pattern to sth like:
> > match-expression -> transform  ?
> > eg:
> > (minus (plus @0 @1) @1) -> @0
> > Looks smaller -:)
>
> Well, I suppose we stay with what we have here.
The attached patch, adds support for built-in functions, and fixes
insertion bug in decision tree.
The insertion in decision tree is carried out during preorder traversal
of AST (insert_operand), so it avoids generating preorder traversal in
vector (removed walk_operand_preorder and
lower_capture). For now have put (parent, pos, preorder_level) in
separate struct operand_info, and added instance
of this struct to operand (struct operand_info opinfo). operand_info
is computed during preorder traversal
(insert_operand), so parsing routines are not concerned with it.
Eventually we should probably move
matching code on decision tree nodes. For convenience of tracking
patterns, I have numbered them in match.pd.

* Testing
Total patterns in match.pd - 58
Total test cases: 4 (match-1.c), 32 (match-decision-tree.c), match-2.c
is screwed.

Out of 22 remaining patterns:
Not supported yet (require GENERIC support or special handling): 31
(convert), 33, 34, 35 (realpart/imagpart), 37 (cond)
Not able to write test-cases: 2, 16, 31, 38
I will add test-cases for remaining patterns shortly.

Thanks and Regards,
Prathamesh
>
> Thanks,
> Richard.
>
> > Thanks and Regards
> > Prathamesh
> >>
> >> Richard.
> >>
> >>>and for the commutative variant:
> >>>(plus (negate@0 @1) @0) S
> >>>
> >>>the decision tree would be the following: ?
> >>>plus - negate - true - true - match (3) - simplify
> >>>
> >>>Thanks and Regards,
> >>>Prathamesh
> >>>>
> >>>> Richard.
> >>>>
> >>>>>> Richard.
> >>>>>>
> >>>>>>>> There are also opportunities to optimize the generated code, but
> >>>>>>>> basic correctness first I guess.
> >>>>>>>>
> >>>>>>>> I suppose we have to work a bit on the capture stuff.
> >>>>>>>>
> >>>>>>>> Btw, you can easily play with the code generator by doing inside
> >>>>>>>> the gcc build directory
> >>>>>>>>
> >>>>>>>> obj/gcc> build/genmatch test.pd > test.c
> >>>>>>>>
> >>>>>>>> with a small test.pd. I used the following for the above
> >>>examples:
> >>>>>>>>
> >>>>>>>> (match_and_simplify
> >>>>>>>>   (MINUS_EXPR (PLUS_EXPR @0 @1) @0)
> >>>>>>>>   @1)
> >>>>>>>> (match_and_simplify
> >>>>>>>>   (MINUS_EXPR (PLUS_EXPR @1 @0) @0)
> >>>>>>>>   @1)
> >>>>>>
> >>>>>>>> Richard.
> >>>>>>>>
> >>>>>>>>>> I will change this to have capture per pattern
> >>>>>>>>>> tree captures1[4] = {};  // for pattern-1
> >>>>>>>>>> tree captures2[4] = {};
> >>>>>>>>>
> >>>>>>>>> Hmm, is this the matching captures issue I mentioned?  Btw, I
> >>>see
> >>>>>>>>> you do
> >>>>>>>>>
> >>>>>>>>> +void
> >>>>>>>>> +walk_operand_preorder(vec<operand *>& operands, operand *op)
> >>>>>>>>> +{
> >>>>>>>>> +  if (op->type == operand::OP_CAPTURE || op->type ==
> >>>>>>>>> operand::OP_PREDICATE || op->type == operand::OP_C_EXPR)
> >>>>>>>>> +    {
> >>>>>>>>> +      operands.safe_push (op);
> >>>>>>>>> +      return;
> >>>>>>>>> +    }
> >>>>>>>>>
> >>>>>>>>> but that leaves captured expressions as a single operand?
> >>>>>>>>>
> >>>>>>>>> (plus (minus@1 @2 @3) @2)
> >>>>>>>>>
> >>>>>>>>> would have a decision tree
> >>>>>>>>>
> >>>>>>>>>  plus -> minus -> @2
> >>>>>>>>>
> >>>>>>>>> correct?
> >>>>>>>>>
> >>>>>>>>>> d) Matching multiple patterns.
> >>>>>>>>>> Code for patterns with same match, but different transforms is
> >>>>>>>>>> generated as follows:
> >>>>>>>>>> code for match operand.
> >>>>>>>>>> if (if-expr of pattern-1)
> >>>>>>>>>> {
> >>>>>>>>>>   code for result of pattern-1
> >>>>>>>>>>   return true;
> >>>>>>>>>> }
> >>>>>>>>>> if (if-expr of pattern-2)
> >>>>>>>>>> {
> >>>>>>>>>>   code for result of pattern-2
> >>>>>>>>>>   return true;
> >>>>>>>>>> }
> >>>>>>>>>
> >>>>>>>>> good.
> >>>>>>>>>
> >>>>>>>>>> ...
> >>>>>>>>>> Should we emit a warning for patterns that have same match
> >>>operand but
> >>>>>>>>>> no if-expr and no manual transform ?
> >>>>>>>>>>
> >>>>>>>>>> for eg:
> >>>>>>>>>> (match_and_simplify
> >>>>>>>>>>   (plus (minus @0 @1) @1)
> >>>>>>>>>>   @0
> >>>>>>>>>>
> >>>>>>>>>> (match_and_simplify
> >>>>>>>>>>   (plus (minus @0 @1) @1)
> >>>>>>>>>>   @1  // just for illustration
> >>>>>>>>>>
> >>>>>>>>>> Since the matching is ambiguous (same match, no if-expr, no
> >>>manual
> >>>>>>>>>> transform).
> >>>>>>>>>
> >>>>>>>>> Yeah, I suppose we should.
> >>>>>>>>>
> >>>>>>>>>> we are left to choose between result of pattern-1 and result of
> >>>>>>>>>> pattern-2.
> >>>>>>>>>> We can emit warning and choose result of pattern-1 (first-match
> >>>rule
> >>>>>>>>>> as in flex).
> >>>>>>>>>>
> >>>>>>>>>> e) Non-matching captures:
> >>>>>>>>>> Haven't thought about this yet.
> >>>>>>>>>>
> >>>>>>>>>> * Should we add "negative" predicates that match only if the
> >>>predicate
> >>>>>>>>>> fails ?
> >>>>>>>>>> for eg:
> >>>>>>>>>> (match_and_simplify
> >>>>>>>>>>   trunc_mod integer_zerop@0 !integer_zerop)
> >>>>>>>>>>   @0)
> >>>>>>>>>
> >>>>>>>>> well, there could simply be a integer_not_zerop predicate.
> >>>>>>>>>
> >>>>>>>>>> * Testing
> >>>>>>>>>> Sorry to bring this up again, but I am still not clear what
> >>>regex to
> >>>>>>>>>> write in scan-tree-dump.
> >>>>>>>>>>
> >>>>>>>>>> Suppose we have these two patterns in match.pd:
> >>>>>>>>>> /* (x + y) - y -> x */
> >>>>>>>>>> (match_and_simplify
> >>>>>>>>>>   (minus (plus @0 @1) @1)
> >>>>>>>>>>   @0)
> >>>>>>>>>>
> >>>>>>>>>> /* (x - y) + y -> x */
> >>>>>>>>>> (match_and_simplify
> >>>>>>>>>>   (plus (minus @0 @1) @1)
> >>>>>>>>>>   @0)
> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*=
> >>>>>>>>>> x_\\d\+\\(D\\)"
> >>>>>>>>>>
> >>>>>>>>>> I have following test-cases:
> >>>>>>>>>> int f1(int x, int y)
> >>>>>>>>>> {
> >>>>>>>>>>   int t1 = x + y;
> >>>>>>>>>>   return t1 - y;
> >>>>>>>>>> }
> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*=
> >>>>>>>>>> x_\\d\+\\(D\\)"
> >>>>>>>>>>
> >>>>>>>>>> int f2(int x, int y)
> >>>>>>>>>> {
> >>>>>>>>>>   int t1 = x - y;
> >>>>>>>>>>   return t1 + y;
> >>>>>>>>>> }
> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*=
> >>>>>>>>>> x_\\d\+\\(D\\)"
> >>>>>>>>>>
> >>>>>>>>>> both the test-cases have same regex.
> >>>>>>>>>> Tested in isolation f1 passes (first pattern if fired) and f2
> >>>fails
> >>>>>>>>>> (second pattern doesn't fire, it does after
> >>>>>>>>>> adding it's commutative variant, but that's irrelevant for this
> >>>case).
> >>>>>>>>>>
> >>>>>>>>>> However when both test-cases are put in one file both the test
> >>>cases
> >>>>>>>>>> PASS.
> >>>>>>>>>> I think that's because both of them have same regex:
> >>>\[^\n\r\]*=
> >>>>>>>>>> x_\\d\+\\(D\\)
> >>>>>>>>>> so in f1 and f2's regex both match the dump for f1 function in
> >>>>>>>>>> forwprop dump file:
> >>>>>>>>>> "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\)
> >>>>>>>>>>
> >>>>>>>>>> As a quick hack i rewrote f1 and f2 as:
> >>>>>>>>>> int f1(int x, int y)
> >>>>>>>>>> {
> >>>>>>>>>>   int t1 = x + y;
> >>>>>>>>>>   int f1_val = t1 - y;
> >>>>>>>>>>   return f1_val;
> >>>>>>>>>> }
> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to f1_val_\\d\+ =
> >>>>>>>>>> x_\\d\+\\(D\\)"
> >>>>>>>>>>
> >>>>>>>>>> int f2(int x, int y)
> >>>>>>>>>> {
> >>>>>>>>>>   int t1 = x - y;
> >>>>>>>>>>   int f2_val = t1 + y;
> >>>>>>>>>>   return f2_val;
> >>>>>>>>>> }
> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to f2_val_\\d\+ =
> >>>>>>>>>> x_\\d\+\\(D\\)"
> >>>>>>>>>> so both f1 and f2's scan-tree-dump have different regexes.
> >>>>>>>>>> and f2's regex does not match dump of f1's function.
> >>>>>>>>>> This matches all patterns in match-decision-tree.c however this
> >>>is not
> >>>>>>>>>> ideal,
> >>>>>>>>>> since it does not check for matching dump across newlines.
> >>>>>>>>>> Could you suggest a better way ?
> >>>>>>>>>
> >>>>>>>>> There isn't a good better way (the others explicitely do _not_
> >>>match
> >>>>>>>>> against
> >>>>>>>>> a newline - see the ^ in the \[\] group).  Well, apart from
> >>>splitting
> >>>>>>>>> the testcase
> >>>>>>>>> into multiple files of course.
> >>>>>>>>>
> >>>>>>>>> Richard.
> >>>>>>>>>
> >>>>>>>>>> Thanks and Regards,
> >>>>>>>>>> Prathamesh
> >>>>>>>>>>>
> >>>>>>>>>>> Thanks,
> >>>>>>>>>>> Richard.
> >>>>>>>>>>>
> >>>>>>>>>>>>> Thanks and Regards,
> >>>>>>>>>>>>> Prathamesh
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> Richard.
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> * Code generation.
> >>>>>>>>>>>>>>> Code shall be generated by walking the decision tree.
> >>>>>>>>>>>>>>> The way it's constructed, there's no difference between
> >>>code
> >>>>>>>>>>>>>>> generation
> >>>>>>>>>>>>>>> for "matching" and code generation for "transform". For
> >>>>>>>>>>>>>>> non-simplificaton
> >>>>>>>>>>>>>>> operands, "matching" code is generated, and for
> >>>"simplification"
> >>>>>>>>>>>>>>> operands,
> >>>>>>>>>>>>>>> "transform" code is generated. The tree shall be walked
> >>>twice,
> >>>>>>>>>>>>>>> once to generate GIMPLE code and second time for GENERIC.
> >>>>>>>>>>>>>>> For simplicity, I currently return false whenever there's
> >>>a fail
> >>>>>>>>>>>>>>> in match,
> >>>>>>>>>>>>>>> instead of trying to match the next pattern.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Code-gen for capture - same as capture::gen_gimple_match.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Code-gen for predicate -  I haven't added support for
> >>>predicate
> >>>>>>>>>>>>>>> in
> >>>>>>>>>>>>>>> decision tree yet, but I guess that would be the same as
> >>>>>>>>>>>>>>> predicate::gen_gimple_match
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Code-gen for expr.
> >>>>>>>>>>>>>>> There are two types of code-gen for expr.
> >>>>>>>>>>>>>>> The patch generates following code:
> >>>>>>>>>>>>>>> Type 1 - expr is child of root node.
> >>>>>>>>>>>>>>> the only code that gets generated is (in
> >>>>>>>>>>>>>>> decision_tree::gen_gimple):
> >>>>>>>>>>>>>>> if (code == <expr code>)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> tree captures[4] = {}
> >>>>>>>>>>>>>>> <generated code for children>
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>> This is similar to generating matching code in
> >>>>>>>>>>>>>>> write_nary_simplifiers.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Type 2 - expr_1 is a child of another expr_0 node.
> >>>>>>>>>>>>>>> The code gets generated as follows (dt_expr::gen_gimple):
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> gimple def_stmt = SSA_NAME_DEF_STMT (op);
> >>>>>>>>>>>>>>> if (is_gimple_assign (def_stmt)
> >>>>>>>>>>>>>>>     && gimple_assign_rhs_code (def_stmt) == <expr_1-code>)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> tree op = gimple_assign_rhs1 (def_stmt);
> >>>>>>>>>>>>>>> if (valueize && TREE_CODE (op) == SSA_NAME)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>>   op = valueize (op);
> >>>>>>>>>>>>>>>   if (!op) return false;
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>> <code-gen for children of expr_1 node>
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Example:
> >>>>>>>>>>>>>>> (negate (negate @0))
> >>>>>>>>>>>>>>> S1
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> (negate (bit_not @0))
> >>>>>>>>>>>>>>> S2
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> decision tree:
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>>                 dummy/root
> >>>>>>>>>>>>>>>                         |
> >>>>>>>>>>>>>>>            NEGATE_EXPR
> >>>>>>>>>>>>>>>              /                  \
> >>>>>>>>>>>>>>>      BIT_NOT           NEGATE_EXPR
> >>>>>>>>>>>>>>>            |                         |
> >>>>>>>>>>>>>>>          @0                     @0
> >>>>>>>>>>>>>>>            |                         |
> >>>>>>>>>>>>>>>          S1                      S2
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> // code-gen for NEGATE_EXPR (child of root):
> >>>>>>>>>>>>>>> if (code == NEGATE_EXPR)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> tree captures[4] = {};
> >>>>>>>>>>>>>>> // code gen for BIT_NOT_EXPR
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> gimple def_stmt = SSA_NAME_DEF_STMT (op0);
> >>>>>>>>>>>>>>> if (is_gimple_assign (def_stmt)
> >>>>>>>>>>>>>>>     && gimple_assign_rhs_code (def_stmt) == BIT_NOT_EXPR)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> tree op = gimple_assign_rhs1 (def_stmt);
> >>>>>>>>>>>>>>> if (valueize && TREE_CODE (op) == SSA_NAME)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>>   op = valueize (op);
> >>>>>>>>>>>>>>>   if (!op) return false;
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> // code-gen for @0, child of BIT_NOT_EXPR
> >>>>>>>>>>>>>>> if (!captures[0])
> >>>>>>>>>>>>>>>   captures[0] = op;
> >>>>>>>>>>>>>>> else if (captures[0] != op)
> >>>>>>>>>>>>>>>   return false;
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> // code-gen for S1, child of @0
> >>>>>>>>>>>>>>> < same as code generated by .gen_gimple_transform >
> >>>>>>>>>>>>>>> return true;
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>> // code gen for inner NEGATE_EXPR
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> gimple def_stmt = SSA_NAME_DEF_STMT (op0);
> >>>>>>>>>>>>>>> if (is_gimple_assign (def_stmt)
> >>>>>>>>>>>>>>>     && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR)
> >>>>>>>>>>>>>>> <rest similar to the BIT_NOT case>
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> The following gets duplicated with the patch:
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> gimple_def_stmt = SSA_NAME_DEF_STMT (op0);
> >>>>>>>>>>>>>>> if (TREE_CODE (op0) != SSA_NAME)
> >>>>>>>>>>>>>>>   return false;
> >>>>>>>>>>>>>>> if (is_gimple_assign (def_stmt)
> >>>>>>>>>>>>>>>     && gimple_assign_rhs_code (def_stmt) == <expr-code>)
> >>>>>>>>>>>>>>> ...
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Improving code-gen for expr:
> >>>>>>>>>>>>>>> "gimple def_stmt = ..." and "if (TREE_CODE (op0)" get
> >>>duplicated,
> >>>>>>>>>>>>>>> while they could be factored out, similar to this:
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> gimple def_stmt = SSA_NAME_DEF_STMT (op0);
> >>>>>>>>>>>>>>> if (TREE_CODE (op0) != SSA_NAME)
> >>>>>>>>>>>>>>>   return false;
> >>>>>>>>>>>>>>> if (!is_gimple_assign (def_stmt))
> >>>>>>>>>>>>>>>   return false;
> >>>>>>>>>>>>>>> if (gimple_assign_rhs_code (def_stmt) == BIT_NOT_EXPR)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>>   // code-gen for BIT_NOT_EXPR subtree
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>> else if (gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>>   // code-gen for NEGATE_EXPR subtree
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> For factoring "gimple def_stmt ..." and "if (TREE_CODE
> >>>(op0) !=
> >>>>>>>>>>>>>>> SSA_NAME"
> >>>>>>>>>>>>>>> we could have that generated at the parent of expr's node
> >>>rather
> >>>>>>>>>>>>>>> than
> >>>>>>>>>>>>>>> at expr. However that would be incorrect for cases where
> >>>not all
> >>>>>>>>>>>>>>> children
> >>>>>>>>>>>>>>> of a node are expressions:
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Example:
> >>>>>>>>>>>>>>> // patterns only for illustration
> >>>>>>>>>>>>>>> (negate (bit_not @0))
> >>>>>>>>>>>>>>> (negate @0)
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>>                    root
> >>>>>>>>>>>>>>>                      |
> >>>>>>>>>>>>>>>                   negate
> >>>>>>>>>>>>>>>                     /       \
> >>>>>>>>>>>>>>>                 bit_not   @0
> >>>>>>>>>>>>>>>                     |
> >>>>>>>>>>>>>>>                   @0
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> we cannot have the above code generated at negate,
> >>>>>>>>>>>>>>> since it's not applicable negate's 2nd child (@0).
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> This can be done by grouping together children that are
> >>>>>>>>>>>>>>> expressions.
> >>>>>>>>>>>>>>> However the patch does not do that.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> * Code-gen for simplification operand
> >>>>>>>>>>>>>>> This involves code-gen for ifexpr and result of pattern.
> >>>>>>>>>>>>>>> Calls gen_gimple_transform of ifexpr and result
> >>>>>>>>>>>>>>> (dt_simplify::gen_gimple)
> >>>>>>>>>>>>>>> So this is really code-gen off AST
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> Right (modulo replacing captures with their replacements).
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> * Matching multiple patterns
> >>>>>>>>>>>>>>> A pattern has following parts: match, ifexpr and result.
> >>>>>>>>>>>>>>> If pattern fails in match operand, I guess we can safely
> >>>return
> >>>>>>>>>>>>>>> false ?
> >>>>>>>>>>>>>>> We "club" together patterns that have same match operand,
> >>>>>>>>>>>>>>> and use goto, if one of them fails in their
> >>>(ifexpr/result) and
> >>>>>>>>>>>>>>> then goto the
> >>>>>>>>>>>>>>> (ifexpr/result) of the next operand.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Example:
> >>>>>>>>>>>>>>> /* x & 0 -> 0 */
> >>>>>>>>>>>>>>> (match_and_simplify
> >>>>>>>>>>>>>>>   (bit_and @0 @1)
> >>>>>>>>>>>>>>>   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && (@1 ==
> >>>>>>>>>>>>>>> integer_zero_node))
> >>>>>>>>>>>>>>>   { integer_zero_node; })
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> /* x & -1 -> x */
> >>>>>>>>>>>>>>> (match_and_simplify
> >>>>>>>>>>>>>>>   (bit_and @0 @1)
> >>>>>>>>>>>>>>>   if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
> >>>>>>>>>>>>>>>      && (@1 == integer_minus_one_node)
> >>>>>>>>>>>>>>>   @0)
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> For both patterns match is same.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Decision Tree:
> >>>>>>>>>>>>>>>                 bit_and
> >>>>>>>>>>>>>>>                 /        \
> >>>>>>>>>>>>>>>              @0      @1
> >>>>>>>>>>>>>>>                            |
> >>>>>>>>>>>>>>>                         S1,  S2
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> I think it's worth adding a diagnostic to genmach whenever
> >>>exactly
> >>>>>>>>>>>>>> same matches appear.  But I'd say generally we'd support
> >>>this
> >>>>>>>>>>>>>> by testing the ifexpr of the next pattern.
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> S1 represents <ifexpr, result> of pattern-1, and S2
> >>>represents
> >>>>>>>>>>>>>>> <ifexpr, result>
> >>>>>>>>>>>>>>> of pattern-2 respectively.
> >>>>>>>>>>>>>>> S1, S2 would be stored as children of @1 (the last operand
> >>>of
> >>>>>>>>>>>>>>> n-ary operator),
> >>>>>>>>>>>>>>> in dt_operand::kids vector.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> The code would be generated as:
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> matching code.
> >>>>>>>>>>>>>>> if (! pattern-1 ifexpr condition)
> >>>>>>>>>>>>>>>   goto simplify2;  // next pattern with the same "match"
> >>>operand.
> >>>>>>>>>>>>>>> transform code for pattern 1
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> simplify2:
> >>>>>>>>>>>>>>> if (! pattern-2 ifexpr condition)
> >>>>>>>>>>>>>>>   return false;  // last pattern
> >>>>>>>>>>>>>>> transform code for pattern 2.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> If matching itself fails, that is neither of the decisions
> >>>get
> >>>>>>>>>>>>>>> matched,
> >>>>>>>>>>>>>>> I believe we can then return false as it cannot match any
> >>>other
> >>>>>>>>>>>>>>> pattern ?
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> * patterns needing hacks like cond_expr or GENERIC support
> >>>>>>>>>>>>>>> I haven't given thought to this yet. I suppose we can look
> >>>to
> >>>>>>>>>>>>>>> handle
> >>>>>>>>>>>>>>> these after adding support for GENERIC. Instead of
> >>>generating
> >>>>>>>>>>>>>>> GENERIC
> >>>>>>>>>>>>>>> matching in
> >>>>>>>>>>>>>>> gimple_match_and_simplify, could we then call
> >>>>>>>>>>>>>>> generic_match_and_simplify from
> >>>>>>>>>>>>>>> within gimple_match_and_simplify ?
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> Yes (that's what's currently done btw).
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> * Tests
> >>>>>>>>>>>>>>> The patch transformed the following patterns:
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> (match_and_simplify
> >>>>>>>>>>>>>>>   (negate (bit_not @0))
> >>>>>>>>>>>>>>>   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
> >>>>>>>>>>>>>>>   (plus @0 { build_int_cst (TREE_TYPE (@0)), 1); }))
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> (match_and_simplify
> >>>>>>>>>>>>>>>   (negate (negate @0))
> >>>>>>>>>>>>>>>   @0)
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> I have attached test-case I tried it with (negate.c)
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> * Conclusion
> >>>>>>>>>>>>>>> Does it sound reasonable ? I am going to be re-writing the
> >>>>>>>>>>>>>>> decision tree from scratch, but is the basic idea fine ?
> >>>Or should
> >>>>>>>>>>>>>>> we
> >>>>>>>>>>>>>>> take a different approach ?
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Thanks and Regards,
> >>>>>>>>>>>>>>> Prathamesh
> >>>>>>
> >>
> >>

Index: gcc/genmatch.c
===================================================================
--- gcc/genmatch.c	(revision 211502)
+++ gcc/genmatch.c	(working copy)
@@ -29,7 +29,8 @@ along with GCC; see the file COPYING3.
 #include "hashtab.h"
 #include "hash-table.h"
 #include "vec.h"
-
+#include <stdlib.h>
+#include <limits.h>
 
 /* libccp helpers.  */
 
@@ -200,21 +201,39 @@ add_builtin (enum built_in_function code
 
 
 /* The predicate expression tree structure.  */
+struct operand;
+
+struct operand_info {
+  operand *parent;
+  unsigned pos;
+  unsigned preorder_level;
+
+  operand_info (operand *parent_ = 0, unsigned pos_ = 0, unsigned preorder_level_ = 0)
+	: parent (parent_), pos (pos_), preorder_level (preorder_level_) {}
+};
 
 struct operand {
-  enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR };
-  operand (enum op_type type_) : type (type_) {}
+  enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR, OP_TRUE, OP_MATCH };
+  operand (enum op_type type_) : type (type_) {} 
   enum op_type type;
-  virtual void gen_gimple_match (FILE *f, const char *, const char * = NULL) = 0;
+
+  operand_info opinfo;
+
+  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;
+
+  virtual unsigned gen_gimple_match_dt (FILE *f, const char *) = 0; 
 };
 
+
 struct predicate : public operand
 {
   predicate (const char *ident_) : operand (OP_PREDICATE), ident (ident_) {}
   const char *ident;
   virtual void gen_gimple_match (FILE *f, const char *, const char *);
   virtual void gen_gimple_transform (FILE *, const char *, const char *) { gcc_unreachable (); }
+
+  virtual unsigned gen_gimple_match_dt (FILE *f, const char *);
 };
 
 struct e_operation {
@@ -232,6 +251,8 @@ struct expr : public operand
   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 *);
+
+  virtual unsigned gen_gimple_match_dt (FILE *f, const char *);
 };
 
 struct c_expr : public operand
@@ -245,6 +266,8 @@ struct c_expr : public operand
   char *fname;
   virtual void gen_gimple_match (FILE *, const char *, const char *) { gcc_unreachable (); }
   virtual void gen_gimple_transform (FILE *f, const char *, const char *);
+
+  virtual unsigned gen_gimple_match_dt (FILE *f, const char *) { gcc_unreachable (); }
 };
 
 struct capture : public operand
@@ -255,8 +278,28 @@ struct capture : public operand
   operand *what;
   virtual void gen_gimple_match (FILE *f, const char *, const char *);
   virtual void gen_gimple_transform (FILE *f, const char *, const char *);
+
+  virtual unsigned gen_gimple_match_dt (FILE *f, const char *) { gcc_unreachable (); }
 };
 
+struct true_operand: public operand
+{
+  true_operand (): operand (OP_TRUE) {}
+  virtual void gen_gimple_match (FILE *f, const char *, const char *) {}
+  virtual void gen_gimple_transform (FILE *f, const char *, const char *) { gcc_unreachable (); }
+
+  virtual unsigned gen_gimple_match_dt (FILE *f, const char *);
+};
+
+struct match_operand: public operand
+{
+  unsigned index; 
+  match_operand (unsigned index_): operand (OP_MATCH), index (index_) {}
+  virtual void gen_gimple_match (FILE *f, const char *, const char *) {}
+  virtual void gen_gimple_transform (FILE *f, const char *, const char *) { gcc_unreachable (); }
+
+  virtual unsigned gen_gimple_match_dt (FILE *f, const char *);
+};
 
 e_operation::e_operation (const char *id)
 {
@@ -316,7 +359,7 @@ static void
 gen_gimple_match_fail (FILE *f, const char *label)
 {
   if (!label)
-    fprintf (f, "return NULL_TREE;\n");
+    fprintf (f, "return false;\n");
   else
     fprintf (f, "goto %s;\n", label);
 }
@@ -558,6 +601,459 @@ capture::gen_gimple_match (FILE *f, cons
   gen_gimple_match_fail (f, label);
 }
 
+unsigned
+predicate::gen_gimple_match_dt (FILE *f, const char *opname) 
+{
+  fprintf (f, "if (%s (%s))\n", ident, opname);
+  fprintf (f, "{\n");
+  return 1;
+}
+
+unsigned
+expr::gen_gimple_match_dt (FILE *f, const char *opname)
+{
+  fprintf (f, "if (TREE_CODE (%s) == SSA_NAME)\n", opname);
+  fprintf (f, "{\n");
+  fprintf (f, "gimple def_stmt%u = SSA_NAME_DEF_STMT (%s);\n", opinfo.preorder_level, opname);
+
+  if (operation->op->kind == id_base::CODE)
+    fprintf (f, "if (is_gimple_assign (def_stmt%u) && gimple_assign_rhs_code (def_stmt%u) == %s)\n",
+	     opinfo.preorder_level, opinfo.preorder_level, operation->op->id);
+
+  else
+    {
+      fn_id *fop = static_cast<fn_id *>(operation->op);
+      fprintf (f, "if (gimple_call_builtin_p (def_stmt%u, %s))\n", opinfo.preorder_level, fop->id);
+    }
+
+  fprintf (f, "{\n");
+  return 2;
+}
+
+unsigned
+true_operand::gen_gimple_match_dt (FILE *f, const char *opname)
+{
+  return 0;
+}
+
+unsigned
+match_operand::gen_gimple_match_dt (FILE *f, const char *opname)
+{
+  fprintf (f, "if (%s == o%u)\n", opname, index);
+  fprintf (f, "{\n");
+  return 1;
+}
+
+void
+print_flattened_operand (operand *o, FILE *f = stderr)
+{
+  if (o->type == operand::OP_CAPTURE)
+    fprintf (f, "@%s", (static_cast<capture *>(o))->where);
+  else if (o->type == operand::OP_PREDICATE)
+    fprintf (f, "%s", (static_cast<predicate *>(o))->ident);
+  else if (o->type == operand::OP_EXPR)
+    {
+      expr *e = static_cast <expr *>(o);
+      fprintf (f, "%s", e->operation->op->id);
+    }
+  else if (o->type == operand::OP_C_EXPR)
+    fprintf (f, "c_expr");
+  else if (o->type == operand::OP_TRUE)
+    fprintf (f, "true");
+  else if (o->type == operand::OP_MATCH)
+    {
+      match_operand *m = static_cast<match_operand *> (o);
+      fprintf (f, "match(%u)", m->index);
+    }
+  else
+    {
+      fprintf (stderr, "o->type = %u\n", o->type);
+      gcc_unreachable ();
+    }
+}
+
+
+struct dt_node
+{
+  enum dt_type { DT_NODE, DT_OPERAND, DT_SIMPLIFY };
+  vec<dt_node *> kids;
+  enum dt_type type;
+
+  dt_node (enum dt_type type_): kids (vNULL), type (type_) {} 
+  virtual void gen_gimple (FILE *f);
+
+  dt_node *append_node (dt_node *); 
+  dt_node *append_op(operand *);
+};
+
+struct dt_operand: public dt_node
+{
+  operand *op;
+  const char *opname;  
+
+  dt_operand (operand *op_, const char *opname_ = 0): dt_node(dt_node::DT_OPERAND), op (op_), opname (opname_) {}
+  virtual void gen_gimple (FILE *f);
+};
+
+struct dt_simplify: public dt_node
+{
+  operand *ifexpr;
+  operand *result;
+
+  static const unsigned capture_max = 4;
+  static const unsigned level_max = UINT_MAX;
+  unsigned indexes[capture_max];
+
+  dt_simplify (operand *ifexpr_, operand *result_, unsigned pn_): dt_node(dt_node::DT_SIMPLIFY), 
+	       ifexpr (ifexpr_), result (result_), pattern_no (pn_)
+    {
+      // or maybe keep a parallel bool indexes_empty array instead of using capture_max to denote "not seen" ?
+      for (unsigned i = 0; i < capture_max; ++i)
+	indexes[i] = level_max;
+    }
+
+  virtual void gen_gimple (FILE *f);
+  unsigned pattern_no;
+};
+
+static bool
+has_true_operand (dt_node *p)
+{
+  return p->type == dt_node::DT_OPERAND && (static_cast<dt_operand *>(p))->op->type == operand::OP_TRUE;
+}
+
+struct decision_tree
+{
+  dt_node *root;
+  dt_node *root2;
+
+  decision_tree() { root = new dt_node (dt_node::DT_NODE); root2 = new dt_node (dt_node::DT_NODE); }
+  void gen_gimple (FILE *f);
+  void insert (struct simplify *s, unsigned);
+  void print (FILE *f = stderr);
+};
+
+void
+print_dt_node (dt_node *p, FILE *f = stderr, unsigned indent = 0)
+{
+  if (p->type == dt_node::DT_NODE)
+    fprintf (f, "root");
+  else
+    {
+      fprintf (f, "|");
+      for (unsigned i = 0; i < indent; i++)
+	fprintf (f, "-");
+
+      if (p->type == dt_node::DT_OPERAND)
+	{
+	  fprintf (f, "operand: ");
+	  print_flattened_operand ((static_cast<dt_operand *>(p))->op, f);
+	}
+      else if (p->type == dt_node::DT_SIMPLIFY)
+	fprintf (f, "simplify_%u", ((static_cast<dt_simplify *>(p))->pattern_no));
+    }      
+
+  fprintf (stderr, ", %u\n", p->kids.length ());
+
+  for (unsigned i = 0; i < p->kids.length (); ++i)
+    print_dt_node (p->kids[i], f, indent + 2);
+}
+
+void
+decision_tree::print (FILE *f)
+{
+  print_dt_node (root, f);
+}
+
+void
+dt_node::gen_gimple (FILE *f)
+{}
+
+void
+dt_operand::gen_gimple (FILE *f)
+{
+  bool put_brace = false;
+  fprintf (f, "{\n");
+
+  char opname[128];
+  sprintf (opname, "o%u", op->opinfo.preorder_level);
+
+  print_flattened_operand (op); putc ('\n', stderr);
+
+  if (op->opinfo.parent->opinfo.parent == 0)
+    fprintf (f, "tree %s = op%u;\n", opname, op->opinfo.pos);
+  else if (op->opinfo.parent->type == operand::OP_TRUE || op->opinfo.parent->type == operand::OP_MATCH)
+    {
+      fprintf (f, "tree %s = o%u;\n", opname, op->opinfo.parent->opinfo.preorder_level);
+      fprintf (f, "{\n");
+      put_brace = true;
+    }
+  else if (op->opinfo.parent->type == operand::OP_EXPR)
+    {
+      expr *e = static_cast<expr *>(op->opinfo.parent);
+      if (e->operation->op->kind == id_base::CODE)
+	fprintf (f, "tree %s = gimple_assign_rhs%u (def_stmt%u);\n", opname, op->opinfo.pos + 1, op->opinfo.parent->opinfo.preorder_level);
+      else
+	fprintf (f, "tree %s = gimple_call_arg (def_stmt%u, %u);\n", opname, op->opinfo.parent->opinfo.preorder_level, op->opinfo.pos);
+
+      fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", opname, opname);
+      fprintf (f, "{\n");
+      put_brace = true;
+    }
+  else
+    gcc_unreachable ();
+
+  unsigned n_braces = op->gen_gimple_match_dt (f, opname);
+  unsigned i;
+  for (i = 0; i < kids.length (); ++i)
+    kids[i]->gen_gimple (f);
+
+  for (i = 0; i < n_braces; ++i)
+    fprintf (f, "}\n");
+
+  if (put_brace)
+    fprintf (f, "}\n");
+
+  fprintf (f, "}\n");
+}
+
+void
+dt_simplify::gen_gimple (FILE *f)
+{
+  dt_simplify *s = this;
+
+ char *fail_label = 0;
+
+  fprintf (f, "/* simplify %u */\n", pattern_no);
+
+  fprintf (f, "{\n");
+  fprintf (f, "tree captures[4] = {};\n");
+
+  for (unsigned i = 0; i < dt_simplify::capture_max; ++i)
+    if (indexes[i] != dt_simplify::level_max) 
+      fprintf (f, "captures[%u] = o%u;\n", i, indexes[i]); 
+
+ if (s->ifexpr)
+	{
+//	  output_line_directive (f, s->ifexpr_location);
+	  fprintf (f, "if (");
+	  s->ifexpr->gen_gimple_transform (f, fail_label, NULL);
+	  fprintf (f, ")\n");
+	  fprintf (f, "{\n");
+	}
+//      output_line_directive (f, s->result_location);
+
+      if (s->result->type == operand::OP_EXPR)
+	{
+	  expr *e = static_cast <expr *> (s->result);
+	  fprintf (f, "*res_code = %s;\n", e->operation->op->id);
+	  for (unsigned j = 0; j < e->ops.length (); ++j)
+	    {
+	      char dest[32];
+	      snprintf (dest, 32, "  res_ops[%d]", j);
+	      e->ops[j]->gen_gimple_transform (f, fail_label, dest);
+	    }
+	  /* Re-fold the toplevel result.  It's basically an embedded
+	     gimple_build w/o actually building the stmt.  */
+	  fprintf (f, "gimple_resimplify%d (seq, res_code, type, "
+		   "res_ops, valueize);\n", e->ops.length ());
+	}
+      else if (s->result->type == operand::OP_CAPTURE
+	       || s->result->type == operand::OP_C_EXPR)
+	{
+	  s->result->gen_gimple_transform (f, fail_label,
+					   "res_ops[0]");
+	  fprintf (f, "*res_code = TREE_CODE (res_ops[0]);\n");
+	}
+      else
+	gcc_unreachable ();
+
+      fprintf (f, "return true;\n");
+      if (s->ifexpr)
+	fprintf (f, "}\n");
+
+  fprintf (f, "}\n");
+}
+    
+
+void
+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");
+
+  for (unsigned i = 0; i < root->kids.length (); i++)
+    {
+      dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
+      expr *e = static_cast<expr *>(dop->op);
+
+      if (i)
+        fprintf (f, "else ");
+      fprintf (f, "if (code == %s)\n", e->operation->op->id);
+      fprintf (f, "{\n");
+
+      for (unsigned j = 0; j < dop->kids.length (); ++j)
+	dop->kids[j]->gen_gimple (f);
+
+      fprintf (f, "}\n");
+    }
+
+  fprintf (f, "return false;\n");
+  fprintf (f, "}\n");
+}
+
+
+bool
+cmp_operand (operand *o1, operand *o2)
+{
+  if (!o1 || !o2 || o1->type != o2->type)
+    return false;
+
+  if (o1->type == operand::OP_PREDICATE)
+    {
+      predicate *p1 = static_cast<predicate *>(o1);
+      predicate *p2 = static_cast<predicate *>(o2);
+      return strcmp (p1->ident, p2->ident) == 0;
+    }
+  else if (o1->type == operand::OP_EXPR)
+    {
+      expr *e1 = static_cast<expr *>(o1);
+      expr *e2 = static_cast<expr *>(o2);
+      return strcmp (e1->operation->op->id, e2->operation->op->id) == 0;
+    }
+  else if (o1->type == operand::OP_TRUE)
+    return true;
+  else if (o1->type == operand::OP_MATCH)
+    {
+      match_operand *m1 = static_cast<match_operand *> (o1);
+      match_operand *m2 = static_cast<match_operand *> (o2);
+      return m1->index == m2->index;
+    }
+  else
+    return false;
+}
+  
+dt_node *
+find_operand (vec<dt_node *>& ops, operand *op)
+{
+  for (unsigned i = 0; i < ops.length (); ++i)
+    {
+      if (ops[i]->type != dt_node::DT_OPERAND)
+	continue;
+      operand *o = (static_cast<dt_operand *> (ops[i]))->op;
+      if (cmp_operand (o, op))
+	return ops[i];
+    }
+    
+  return 0;
+}
+
+dt_node *
+dt_node::append_node (dt_node *n)
+{
+  dt_node *kid;
+
+  kids.safe_push (n);
+  unsigned len = kids.length ();
+
+  /* ensure that "true" operand is always the last child */
+  if (len == 1)
+    return kids[len - 1];
+  if (has_true_operand (kids[len - 2]))
+  {
+    dt_node *temp;
+    temp = kids[len - 2];
+    kids[len - 2] = kids[len - 1];
+    kids[len - 1] = temp;
+    return kids[len - 2];
+  }
+  return kids[len - 1];
+}
+
+dt_node *
+dt_node::append_op (operand *op)
+{
+  dt_node *kid;
+
+  kid = find_operand (kids, op);
+  if (kid)
+    return kid;
+
+  return append_node (new dt_operand (op));
+}
+
+unsigned
+insert_operand (dt_node *&p, operand *o, unsigned *indexes, operand *parent = 0, unsigned pos = 0, unsigned preorder_level = 0)
+{
+  operand_info opinfo (parent, pos, preorder_level);
+
+  if (o->type == operand::OP_CAPTURE)
+    {
+      /* FIXME: since the capture is lowered, should it now be freed ? */
+      capture *c = static_cast<capture *> (o);
+      unsigned capt_index = atoi (c->where);
+     
+      operand *op;
+      if (indexes[capt_index] == dt_simplify::level_max)
+	{
+	  indexes[capt_index] = preorder_level;
+	  if (c->what)
+	    return insert_operand (p, c->what, indexes, parent, pos, preorder_level);
+	  op = new true_operand ();
+	  op->opinfo = opinfo;
+	  p = p->append_op (op);
+	  return preorder_level + 1;
+	}
+      else
+	{
+	  op = new match_operand (indexes[capt_index]);
+          op->opinfo = opinfo;
+          p = p->append_op (op);
+	  if (c->what)
+	    return insert_operand (p, c->what, indexes, op, 0, preorder_level + 1);
+	  else
+	    return preorder_level + 1;
+	}
+    }
+
+  o->opinfo = opinfo;
+  p = p->append_op (o); 
+  
+  if (o->type == operand::OP_EXPR)
+    {
+      expr *e = static_cast<expr *> (o);
+      for (unsigned i = 0; i < e->ops.length (); ++i)
+	preorder_level = insert_operand (p, e->ops[i], indexes, e, i, preorder_level + 1);
+    }
+
+  return preorder_level;
+}
+
+void
+decision_tree::insert (struct simplify *s, unsigned pattern_no)
+{
+  dt_simplify *ds = new dt_simplify (s->ifexpr, s->result, pattern_no);
+  dt_node *p = root;
+  insert_operand (p, s->match, ds->indexes);
+  p->append_node (ds);
+}
 
 static void
 write_nary_simplifiers (FILE *f, vec<simplify *>& simplifiers, unsigned n)
@@ -713,9 +1209,11 @@ write_gimple (FILE *f, vec<simplify *>&
   for (unsigned i = 0; i < simplifiers.length (); ++i)
     outline_c_exprs (stdout, simplifiers[i]->result);
 
+#if 0
   write_nary_simplifiers (f, simplifiers, 1);
   write_nary_simplifiers (f, simplifiers, 2);
   write_nary_simplifiers (f, simplifiers, 3);
+#endif
 }
 
 
@@ -1043,8 +1541,13 @@ main(int argc, char **argv)
     }
   while (1);
 
+  decision_tree dt;
+  for (unsigned i = 0; i < simplifiers.length (); ++i)
+    dt.insert (simplifiers[i], i);
+  dt.print ();
+  
   write_gimple (stdout, simplifiers);
-
+  dt.gen_gimple (stdout);
   cpp_finish (r, NULL);
   cpp_destroy (r);
 
Index: gcc/gimple-match-head.c
===================================================================
--- gcc/gimple-match-head.c	(revision 211502)
+++ gcc/gimple-match-head.c	(working copy)
@@ -706,3 +706,10 @@ gimple_match_and_simplify (gimple_stmt_i
   return true;
 }
 
+static tree 
+do_valueize (tree (*valueize)(tree), tree op)
+{
+  if (valueize && TREE_CODE (op) == SSA_NAME)
+    return valueize (op);
+  return op;
+}
Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 211502)
+++ gcc/match.pd	(working copy)
@@ -22,53 +22,69 @@ along with GCC; see the file COPYING3.
 <http://www.gnu.org/licenses/>.  */
 
 /* Simple constant foldings to substitute gimple_fold_stmt_to_constant_2.  */
+
+// 1) x + 0 -> x
 (match_and_simplify
   (plus @0 integer_zerop)
   @0)
+// 2) x pointerplus 0 -> x 
 (match_and_simplify
   (pointer_plus @0 integer_zerop)
   @0)
+// 3) x - 0 -> x
 (match_and_simplify
   (minus @0 integer_zerop)
   @0)
+// 4) x - x -> 0
 (match_and_simplify
   (minus @0 @0)
   { build_zero_cst (type); })
+// 5) x * 0 -> 0
 (match_and_simplify
   (mult @0 integer_zerop@1)
   @1)
+// 6) x * 1 -> x
 (match_and_simplify
   (mult @0 integer_onep)
   @0)
 /* Make sure to preserve divisions by zero.  This is the reason why
    we don't simplify x / x to 1 or 0 / x to 0.  */
+// 7) x / 1 -> x
 (match_and_simplify
   (trunc_div @0 integer_onep)
   @0)
+// 8) x % 1 -> 0
 (match_and_simplify
   (trunc_mod @0 integer_onep)
   { build_zero_cst (type); })
 /* Same applies to modulo operations, but fold is inconsistent here
    and simplifies 0 % x to 0.  */
+// 9) 0 % x -> 0 
 (match_and_simplify
   (trunc_mod integer_zerop@0 @1)
   if (!integer_zerop (@1))
   @0)
+// 10)
 (match_and_simplify
   (bit_ior @0 integer_zerop)
   @0)
+// 11)
 (match_and_simplify
   (bit_ior @0 integer_all_onesp@1)
   @1)
+// 12)
 (match_and_simplify
   (bit_and @0 integer_all_onesp)
   @0)
+//13)
 (match_and_simplify
   (bit_and @0 integer_zerop@1)
   @1)
+//14)
 (match_and_simplify
   (bit_xor @0 integer_zerop)
   @0)
+//15)
 (match_and_simplify
   (bit_xor @0 @0)
   { build_zero_cst (type); })
@@ -86,6 +102,7 @@ along with GCC; see the file COPYING3.
    invariant_addr + cst.  It may not be generally wanted
    (builtin-object-size) and thus may want to be restricted to 'simple'
    forms like &mem-ref or &decl.  */
+// 16)
 (match_and_simplify
   (pointer_plus (addr@2 @0) INTEGER_CST_P@1)
   if (is_gimple_min_invariant (@2))
@@ -108,14 +125,19 @@ along with GCC; see the file COPYING3.
    predicates on the outermost type?  */
 
 /* Contract negates.  */
+// 17) x + (-y) -> x - y
 (match_and_simplify
   (plus @0 (negate @1))
   if (!TYPE_SATURATING (type))
   (minus @0 @1))
+
+// 18) x - (-y) -> y + x
 (match_and_simplify
   (minus @0 (negate @1))
   if (!TYPE_SATURATING (type))
   (plus @0 @1))
+
+// 19) (-x) + y -> y - x
 (match_and_simplify
   (plus (negate @0) @1)
   if (!TYPE_SATURATING (type))
@@ -136,18 +158,22 @@ to (minus @1 @0)
    because of saturation to +-Inf.  */
 
 /* (A +- B) - A -> +-B.  */
+// 20)
 (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)
+// 21)
 (match_and_simplify
   (MINUS_EXPR (MINUS_EXPR @0 @1) @0)
   (NEGATE_EXPR @1))
 /* (A +- B) -+ B -> A.  */
+// 22)
 (match_and_simplify
   (MINUS_EXPR (PLUS_EXPR @0 @1) @1)
   @0)
+// 23)
 (match_and_simplify
   (PLUS_EXPR (MINUS_EXPR @0 @1) @1)
   @0)
@@ -156,9 +182,11 @@ to (minus @1 @0)
    implement these as re-association patterns.
    Watch out for operand order and constant canonicalization
    we do!  A - CST -> A + -CST, CST + A -> A + CST.  */
+// 24)
 (match_and_simplify
   (PLUS_EXPR (PLUS_EXPR @0 INTEGER_CST_P@1) INTEGER_CST_P@2)
   (PLUS_EXPR @0 (PLUS_EXPR @1 @2)))
+// 25)
 (match_and_simplify
   (PLUS_EXPR (MINUS_EXPR INTEGER_CST_P@0 @1) INTEGER_CST_P@2)
   (MINUS_EXPR (PLUS_EXPR @0 @2) @1))
@@ -175,29 +203,36 @@ to (minus @1 @0)
  */
 
 /* ~A + A -> -1 */
+// 26
 (match_and_simplify
   (plus (bit_not @0) @0)
   { build_all_ones_cst (type); })
+
+// 27)
 (match_and_simplify
   (plus @0 (bit_not @0))
   { build_all_ones_cst (type); })
 
 /* ~A + 1 -> -A */
+// 28
 (match_and_simplify
   (plus (bit_not @0) integer_onep)
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   (negate @0)) 
 
 /* A - (A +- B) -> -+ B */
+// 29
 (match_and_simplify
   (minus @0 (plus @0 @1))
   (negate @0))
 
+// 30
 (match_and_simplify
   (minus @0 (minus @0 @1))
   @1)
 
 /* (T)(P + A) - (T)P -> (T) A */
+// 31
 (match_and_simplify
   (minus (convert (pointer_plus @0 @1))
 	 (convert @0))
@@ -210,18 +245,24 @@ to (minus @1 @0)
      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.  */
+// 32
 (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)
 
 /* COMPLEX_EXPR and REALPART/IMAGPART_EXPR cancellations.  */
+// 33
 (match_and_simplify
   (complex (realpart @0) (imagpart @0))
   @0)
+
+// 34
 (match_and_simplify
   (realpart (complex @0 @1))
   @0)
+
+// 35
 (match_and_simplify
   (imagpart (complex @0 @1))
   @1)
@@ -229,6 +270,7 @@ to (minus @1 @0)
 /* One unary pattern.  */
 
 /* fold_negate_exprs convert - (~A) to A + 1.  */
+// 36
 (match_and_simplify
   (negate (bit_not @0))
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
@@ -238,38 +280,51 @@ to (minus @1 @0)
 
 /* Due to COND_EXPRs weirdness in GIMPLE the following won't work
    without some hacks in the code generator.  */
+// 37
 (match_and_simplify
   (cond (bit_not @0) @1 @2)
   (cond @0 @2 @1))
 
 /* match-and-simplify handles constant folding so we
    can just do the decomposition here.  */
+// 38
 (match_and_simplify
   (fma INTEGER_CST_P@0 INTEGER_CST_P@1 @3)
   (plus (mult @0 @1) @3))
 
 /* One builtin function to atom.  */
+// 39
 (match_and_simplify
   (BUILT_IN_SQRT (mult @0 @0))
   @0)
 /* One builtin function to builtin function.  */
+// 40
 (match_and_simplify
   (BUILT_IN_CABS (complex @0 real_zerop))
   (BUILT_IN_FABS @0))
+// 41
 (match_and_simplify
   (BUILT_IN_CABS (complex real_zerop @0))
   (BUILT_IN_FABS @0))
+
 /* One builtin function to expr.  */
+// 42
 (match_and_simplify
   (BUILT_IN_CABS (complex @0 @0))
   (mult (BUILT_IN_FABS @0) { build_real (TREE_TYPE (@0), real_value_truncate (TYPE_MODE (TREE_TYPE (@0)), dconst_sqrt2 ())); }))
+
 /* One nested fn.  */
+// 43
 (match_and_simplify
   (mult (BUILT_IN_POW @0 @1) @0)
   (BUILT_IN_POW @0 (PLUS_EXPR @1 { build_one_cst (TREE_TYPE (@1)); })))
+
+// 44
 (match_and_simplify
   (mult @0 (BUILT_IN_POW @0 @1))
   (BUILT_IN_POW @0 (PLUS_EXPR @1 { build_one_cst (TREE_TYPE (@1)); })))
+
+// 45
 (match_and_simplify
   (BUILT_IN_POW @0 REAL_CST_P@1)
   /* This needs to be conditionalized on flag_unsafe_math_optimizations,
@@ -298,77 +353,85 @@ to (minus @1 @0)
 */
 
 /* x & x -> x */
+// 46
 (match_and_simplify
   (bit_and @0 @0)
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   @0)
 
 /* x & ~x -> 0 */
+// 47
 (match_and_simplify
   (bit_and @0 (bit_not @0))
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   { build_int_cst (type, 0); })
 
 /* ~x & ~y -> ~(x | y) */
+// 48
 (match_and_simplify
   (bit_and (bit_not @0) (bit_not @1))
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   (bit_not (bit_ior @0 @1)))
 
 /* ~x | ~y -> ~(x & y) */
+// 49
 (match_and_simplify
   (bit_ior (bit_not @0) (bit_not @1))
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   (bit_not (bit_and @0 @1)))
 
 /* x & (~x | y) -> y & x */
+// 50
 (match_and_simplify
   (bit_and @0 (bit_ior (bit_not @0) @1))
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   (bit_and @1 @0))
 
 /* (x | CST1) & CST2 -> (x & CST2) | (CST1 & CST2) */
+// 51
 (match_and_simplify
   (bit_and (bit_ior @0 INTEGER_CST_P@1) INTEGER_CST_P@2)
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   (bit_ior (bit_and @0 @2) (bit_and @1 @2)))
 
 /* x ^ ~0 -> ~x */
+// 52
 (match_and_simplify
   (bit_xor @0 integer_all_onesp@1)
   (bit_not @0))
 
 /* (x | y) & x -> x */
+// 53
 (match_and_simplify
   (bit_and (bit_ior @0 @1) @0)
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   @0)
 
-/* (x & y) | x -> x */
+/* 54) (x & y) | x -> x */
 (match_and_simplify
   (bit_ior (bit_and @0 @1) @0)
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   @0)
 
-/* (~x | y) & x -> x & y */
+/* 55) (~x | y) & x -> x & y */
 (match_and_simplify
   (bit_and (bit_ior (bit_not @0) @1) @0)
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   (bit_and @0 @1))
 
-/* (~x & y) | x -> x | y */
+/* 56) (~x & y) | x -> x | y */
 (match_and_simplify
   (bit_ior (bit_and (bit_not @0) @1) @0)
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   (bit_ior @0 @1))
 
-/* ~~x -> x */
+/* 57) ~~x -> x */
 (match_and_simplify
   (bit_not (bit_not @0))
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
   @0)
 
-/* ((a & b) & ~a) -> 0 */
+/* 58) ((a & b) & ~a) -> 0 */
 (match_and_simplify
   (bit_and (bit_and @0 @1) (bit_not @0))
   if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
Index: gcc/testsuite/gcc.dg/tree-ssa/match-decision-tree.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/match-decision-tree.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/match-decision-tree.c	(working copy)
@@ -0,0 +1,303 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-ccp-details -fdump-tree-forwprop-details" }  */
+
+/* x + 0 -> x */
+int c1(int x)
+{
+  int t1 = 0;
+  int c1_val = x + t1;
+  return c1_val;
+}
+/* { dg-final { scan-tree-dump "Match-and-simplified definition of c1_val_\\d\+ to x_\\d\+\\(D\\)" "ccp1" } } */ 
+
+/* x - 0 -> x */ 
+int c3(int x)
+{
+  int t1 = 0;
+  int c3_val = x - t1;  
+  return c3_val;
+}
+/* { dg-final { scan-tree-dump "Match-and-simplified definition of c3_val_\\d\+ to x_\\d\+\\(D\\)" "ccp1" } } */
+
+int c4(int x)
+{
+  int t1 = x;
+  int c4_val = x - t1;
+  return c4_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to c4_val_\\d\+ = 0" "forwprop1" } } */
+
+/* x * 0 -> 0 */
+int c5(int x)
+{
+  int t1 = 0;
+  int c5_val = x * t1;
+  return c5_val;
+}
+/* { dg-final { scan-tree-dump "Match-and-simplified definition of c5_val_\\d\+ to 0" "ccp1" } } */
+
+/* x * 1 -> x */
+int c6(int x)
+{
+  int t1 = 1;
+  int c6_val = x * t1;
+  return c6_val;
+}
+/* { dg-final { scan-tree-dump "Match-and-simplified definition of c6_val_\\d\+ to x_\\d\+\\(D\\)" "ccp1" } } */
+
+/* x / 1 -> x */
+int c7(int x)
+{
+  int t1 = 1;
+  int c7_val = x / t1;
+  return c7_val;
+}
+/* { dg-final { scan-tree-dump "Match-and-simplified definition of c7_val_\\d\+ to x_\\d\+\\(D\\)" "ccp1" } } */
+
+/* x % 1 -> 0 */
+int c8(int x)
+{
+  int t1 = 1;
+  int c8_val = x % t1;
+  return c8_val;
+}
+/* { dg-final { scan-tree-dump "Match-and-simplified definition of c8_val_\\d\+ to 0" "ccp1" } } */
+
+/* x | 0 -> x */
+int c9(int x)
+{
+  int t1 = 0;
+  int c9_val = x | t1;
+  return c9_val;
+}
+/* { dg-final { scan-tree-dump "Match-and-simplified definition of c9_val_\\d\+ to x_\\d\+\\(D\\)" "ccp1" } } */
+
+/* x | -1 -> -1 */
+int c10(int x)
+{
+  int t1 = -1;
+  int c10_val = x | t1;
+  return c10_val;
+}
+/* { dg-final { scan-tree-dump "Match-and-simplified definition of c10_val_\\d\+ to -1" "ccp1" } } */
+
+/* x & -1 -> x */
+int c11(int x)
+{
+  int t1 = -1;
+  int c11_val = x & t1;
+  return c11_val;
+}
+/* { dg-final { scan-tree-dump "Match-and-simplified definition of c11_val_\\d\+ to x_\\d\+\\(D\\)" "ccp1" } } */
+
+/* x & 0 -> 0 */
+int c12(int x)
+{
+  int t1 = 0;
+  int c12_val = x & t1;
+  return c12_val;
+}
+/* { dg-final { scan-tree-dump "Match-and-simplified definition of c12_val_\\d\+ to 0" "ccp1" } } */
+
+/* x ^ 0 -> x */
+int c13(int x)
+{
+  int t1 = 0;
+  int c13_val = x ^ t1;
+  return c13_val;
+}
+/* { dg-final { scan-tree-dump "Match-and-simplified definition of c13_val_\\d\+ to x_\\d\+\\(D\\)" "ccp1" } } */
+
+int c14(int x)
+{
+  int t1 = x;
+  int c14_val = x ^ t1;
+  return c14_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to c14_val_\\d\+ = 0" "forwprop1" } } */
+
+/* x + (-y) -> x - y */
+int f1(int x, int y)
+{
+  int t1 = -y;
+  int f1_val = x + t1;
+  return f1_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f1_val_\\d\+ = x_\\d\+\\(D\\) - y_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* x - (-y) -> y + x */
+int f2(int x, int y)
+{
+  int t1 = -y;
+  int f2_val = x - t1;
+  return f2_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f2_val_\\d\+ = y_\\d\+\\(D\\) \\+ x_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* (x + y) - x -> y */
+int f3(int x, int y)
+{
+  int t1 = x + y;
+  int f3_val = t1 - x;
+  return f3_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f3_val_\\d\+ = y_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* (x - y) - x -> -y */
+int f4(int x, int y)
+{
+  int t1 = x - y;
+  int f4_val = t1 - x;
+  return f4_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f4_val_\\d\+ = -y_\\d\+\\(D\\)" "forwprop1" } } */ 
+
+/* (x + y) - y -> x */
+int f5(int x, int y)
+{
+  int t1 = x + y;
+  int f5_val = t1 - y;
+  return f5_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f5_val_\\d\+ = x_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* disabled (x - y) + y -> x */
+int f6(int x, int y)
+{
+  int t1 = x - y;
+  int f6_val = t1 + y;
+  return f6_val;
+}
+
+/* (x + cst1) + cst2 -> x + (cst1 + cst2) */
+int f7(int x)
+{
+  int t1 = x + 3;
+  int f7_val = t1 + 4;
+  return f7_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f7_val_\\d\+ = x_\\d\+\\(D\\) \\+ 7" "forwprop1" } } */ 
+
+/* (cst1 - x) + cst2 -> (cst1 + cst2) - x */
+int f8(int x)
+{
+  int t1 = 3 - x;
+  int f8_val = t1 + 4;
+  return f8_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f8_val_\\d\+ = 7 - x_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* -(~x) -> x + 1 */
+int f10(int x)
+{
+  int t1 = ~x;
+  int f10_val = -t1;
+  return f10_val; 
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f10_val_\\d\+ = x_\\d\+\\(D\\) \\+ 1" "forwprop1" } } */
+
+/* x + ~x -> -1 */
+int f11(int x)
+{
+  int t1 = ~x;
+  int f11_val = t1 + x;
+  return f11_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f11_val_\\d\+ = -1" "forwprop1" } } */
+
+/* ~x + 1 -> -x */
+int f12(int x)
+{
+  int t1 = ~x;
+  int f12_val = t1 + 1;
+  return f12_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f12_val_\\d\+ = -x_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* x & x -> x */
+int f15(int x)
+{
+  int t1 = x;
+  int f15_val = t1 & x;
+  return f15_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f15_val_\\d\+ = x_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* x & ~x -> 0 */
+int f16(int x)
+{
+  int t1 = ~x;
+  int f16_val = t1 & x;
+  return f16_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f16_val_\\d\+ = 0" "forwprop1" } } */
+
+/* x ^ x -> 0 */
+int f17(int x)
+{
+  int t1 = x;
+  int f17_val = t1 ^ x;
+  return f17_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f17_val_\\d\+ = 0" "forwprop1" } } */
+
+/* ~~x -> 0 */
+int f18(int x)
+{
+  int t1 = ~x;
+  int f18_val = ~t1;
+  return f18_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f18_val_\\d\+ = x_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* (x | y) & x -> x */
+int f19(int x, int y)
+{
+  int t1 = x | y;
+  int f19_val = t1 & x;
+  return f19_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f19_val_\\d\+ = x_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* (x & y) | x -> x */
+int f20(int x, int y)
+{
+  int t1 = x & y;
+  int f20_val = t1 | x;
+  return f20_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f20_val_\\d\+ = x_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* (~x & y) | x -> x | y */
+int f21(int x, int y)
+{
+  int t1 = ~x;
+  int t2 = t1 & y;
+  int f21_val = t2 | x;
+  return f21_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f21_val_\\d\+ = x_\\d\+\\(D\\) | y_\\d\+\\(D\\)" "forwprop1" } } */
+
+/* (~x | y) & x -> x & y */
+int f22(int x, int y)
+{
+  int t1 = ~x;
+  int t2 = t1 | y;
+  int f22_val = t2 & x;
+  return f22_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f22_val_\\d\+ = x_\\d\+\\(D\\) & y_\\d\+\\(D\\)" "forwprop1" } } */
+
+/*  ((x & y) & ~x) & ~y -> 0 */
+int f23(int x, int y)
+{
+  int t1 = x & y;
+  int t2 = ~x;
+  int t3 = t1 & t2;
+  int t4 = ~y;
+  int f23_val = t3 & t4;
+  return f23_val;
+}
+/* { dg-final { scan-tree-dump "gimple_match_and_simplified to f23_val_\\d\+ = 0" "forwprop1" } } */
+
+/* { dg-final { cleanup-tree-dump "forwprop2" } } */