Re: [GSoC] decision tree first steps

[Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>]

On Mon, Jun 23, 2014 at 3:38 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Jun 23, 2014 at 10:26 AM, Prathamesh Kulkarni
> <bilbotheelffriend@gmail.com> wrote:
>> On Thu, Jun 19, 2014 at 7:53 PM, Prathamesh Kulkarni
>> <bilbotheelffriend@gmail.com> wrote:
>>> On Thu, Jun 19, 2014 at 4:12 PM, Prathamesh Kulkarni
>>> <bilbotheelffriend@gmail.com> wrote:
>>>> On Thu, Jun 19, 2014 at 2:37 PM, Prathamesh Kulkarni
>>>> <bilbotheelffriend@gmail.com> wrote:
>
> Replying to the last mail in the thread.
>
>>>>> The attached patch separates decision tree from AST, (removes the
>>>>> "parent bug") and attempts to
>>>>> add support for special case patterns requiring GENERIC (however it
>>>>> fails one test in match-1.c, I am looking
>>>>> into that). Code-gen for matching is off the decision tree and
>>>>> code-gen for transform is off the AST.
>>>>>
>>>>> * Representation of decision tree
>>>>> dt_operand is used for representing AST operand / true / match in the
>>>>> decision tree,
>>>>> dt_operand::parent points to the decision tree node, the AST parent is
>>>>> mapped to, not the pre-order predecessor.
>>>>> dt_operand::pos gives the operand number (0th operand, 1st operand,
>>>>> etc. of parent etc.)
>>>>> I have also clubbed true and match in the same class, because true
>>>>> does not require additional fields,
>>>>> and match has only one additional field (unsigned m_level).
>>>>>
>>>>> For the following pairs of (bogus) patterns:
>>>>> (plus @0 (bit_not@2 @1))
>>>>> (plus @1 (bit_not@3 @0))
>>>>>
>>>>> It builds following decision tree:
>>>>> (type, address, level, n_kids)
>>>>>
>>>>> root (0x1513550), 0, 1
>>>>> |--PLUS_EXPR (0x1502370), 1, 1
>>>>> |----true (0x15023f0), 2, 1
>>>>> |------BIT_NOT_EXPR (0x1502470), 3, 1
>>>>> |--------true (0x15024f0), 4, 2
>>>>> |----------simplify_0 { 2, 4, 3, 4294967295,  }  (0x1512540), 5, 0
>>>>> |----------simplify_1 { 4, 2, 4294967295, 3,  }  (0x15125c0), 5, 0
>>>>>
>>>>> and for the following pairs of (bogus) patterns:
>>>>> (plus (minus@0 @1 @2) @3)
>>>>> (plus (minus @0 @1) @2)
>>>>>
>>>>> It builds following tree:
>>>>> root (0x10e2520), 0, 1
>>>>> |--PLUS_EXPR (0x10d1370), 1, 1
>>>>> |----MINUS_EXPR (0x10d13f0), 2, 1
>>>>> |------true (0x10d1470), 3, 1
>>>>> |--------true (0x10d14f0), 4, 1
>>>>> |----------true (0x10e1540), 5, 2
>>>>> |------------simplify_0 { 2, 3, 4, 5,  }  (0x10e15c0), 6, 0
>>>>> |------------simplify_1 { 3, 4, 5, 4294967295,  }  (0x10e1640), 6, 0
>>>>>
>>>>> Is that correct ?
>
> Yes, that looks correct.
>
>>>>> * Code-gen
>>>>> The code-gen is mostly same, with following changes:
>>>>>
>>>>> a) Generation of expressions:
>>>>> At expr-node, the children are immediately assigned in temporaries
>>>>> (t0, t1 ,...),
>>>>> and when we come at child node, the temporary is assigned to child
>>>>> node (o<level> = t<count>).
>>>>> Temporary names are stored in dt_operand::temps vector.
>>>>>
>>>>> b) Is the following condition correct  (considering for convert) ?:
>>>>>
>>>>> if (is_gimple_assign (def_stmt) &&
>>>>>     (gimple_assign_rhs_code (def_stmt) == <expr-code>
>>>>>     || CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))))
>>>>>  {
>>>>>      // generated code for operands
>>>>>  }
>>>> oops, that's only for CONVERT_EXPR and NOP_EXPR.
>>>> Fixed in the current patch
>
> Looking at dt8.patch it still seems wrong:
>
> +  if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR)
> +    fprintf (f, "if (is_gimple_assign (def_stmt) &&\n"
> +                "   (gimple_assign_rhs_code (def_stmt) == %s\n"
> +               "   || CONVERT_EXPR_CODE_P (gimple_assign_rhs_code
> (def_stmt))))\n", op_id->id);
>
> should be simply generate
>
>   if (is_gimple_assign (def_stmt) && CONVERT_EXPR_CODE_P
> (gimple_assign_rhs_code (def_stmt)))
>
> that is, the == %s check is superfluous.
Thanks, removed it.
>
>>> This patch fixes some more mistakes of the previous patch, and removes
>>> .gen_gimple_match functions.
>
> Good.  Btw, the patch doesn't apply on the unpatched svn branch for me
> (maybe because I applied the commutative patch with some adjustments).
> Can you re-diff it for me so I can apply it?
>
>>> It now passes all tests from match-1.c
>>> The test-case was failing because I didn't generate valueize code correctly.
>>> It should have been:
>>> if ((t<count> = do_valueize (valueize, t<count>)) != 0)
>>> and the code getting generated was:
>>> if (do_valueize (valueize, t<count>))
>>>
>>> This patch supports all the patterns in match.pd. What changes would I
>>> need to make to make it a commit-ready patch ?
>
> I'm looking through the patch right now.
>
>> Added line directives in this patch.
>> I am not sure where to output line directives for match operands
>> since, they are interleaved in the decision tree.
>> I put line directives of respecitve patterns,on top of
>> if (code == <expr-code>), for all patterns having root as <expr-code>
>
> I think the match part cannot be easily annotated with line-directives
> (as you found out).  I'd simply not emit any - it should be easy enough
> to back-track from the ifexpr and code-gen line-directives.
> So simply remove them again.
Removed.
>
> @@ -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>
>
> those headers should already be included via system.h (in general
> system headers need to be included by system.h).
Removed.
>
> Otherwise the patch looks good to commit.
>
> So please re-diff it for me (you can include the capture_max and
> checking patch if it's inconvenient to send without it).
>
> Btw, is your copyright assignment processed?
Yes.

I have kept .gen_gimple_match () functions for now in this patch.
I am not sure how to write the Change-Log for structs. Is the following fine ?

* genmatch.c (print_operand): Add additional default argument bool
flattened = false
    (cmp_operand): New function to compare operands.
    (dt_node): New struct.
    (dt_operand): New struct.
    (dt_simplify): New struct.
    (decision_tree): New struct.
    (write_fn_prototype): New function to write
gimple_match_and_simplify prototype.

* gimple-match-head.c (do_valueize): New function.

I would like to extend phase-1 upto 30th June, and attempt to have
these tasks completed
before beginning phase-2:

a) Decision tree to represent patterns
mostly done

b) GIMPLE match-and-simplify code generation
mostly done

c) GENERIC match-and-simplify code-generation
We have support for generating GENERIC matching code
(dt_operand::gen_generic_expr),
but not for generating GENERIC transforms.

d) Add test case for remaining patterns in match.pd
Around 20-25 patterns don't have test-cases. I plan to spend some-time
this week writing test-cases,
which I guess would be good for testing the decision tree

e) Commutative variants of expression
mostly done.

f) Syntax for denoting multiple operators
example: (plus|minus @0 @1)
or
(for op in plus, minus
  (match_and_simplify
    (op @0 @1)
    S))

as short-hand for
(plus @0 @1)
(minus @0 @1)

I could then start with phase-2, with pattern implementation from 1st July.

Thanks and Regards,
Prathamesh

>
> Thanks,
> Richard.
>
>
>> Thanks and Regards,
>> Prathamesh
>>
>>>
>>> Thanks and Regards,
>>> Prathamesh
>>>
>>>>
>>>> Thanks and Regards,
>>>> Prathamesh
>>>>>
>>>>> Example:
>>>>> For the pattern:
>>>>> (match_and_simplify
>>>>>   (minus (plus @0 @1) @1)
>>>>>   @0)
>>>>>
>>>>> It generated following code: http://pastebin.com/5QdCiZNi
>>>>>
>>>>> c) REALPART_EXPR / IMAGPART_EXPR / VIEW_CONVERT_EXPR / BIT_FIELD_REF:
>>>>> For these patterns, we generate GENERIC instead of GIMPLE to obtain operands ?
>>>>>
>>>>> Example:
>>>>> for the pattern:
>>>>> (match_and_simplify
>>>>>   (complex (realpart @0) (imagpart @0))
>>>>>   @0)
>>>>>
>>>>> it generated following code: http://pastebin.com/qXjEavDu
>>>>>
>>>>> d) COND_EXPR
>>>>> We generate GENERIC for 1st operand of COND_EXPR and not for the other
>>>>> operands (2nd, 3rd).
>>>>> Is that correct ?
>>>>>
>>>>> for the pattern:
>>>>> (match_and_simplify
>>>>>   (cond (bit_not @0) @1 @2)
>>>>>   (cond @0 @2 @1))
>>>>>
>>>>> it generates following code: http://pastebin.com/vL1dcb2E
>>>>>
>>>>> * GENERIC code generation.
>>>>> So far we are generating code for match-and-simplify on gimple.
>>>>> How do we start with GENERIC code-gen ?
>>>>>
>>>>> a) generate in gimple-match.c (or keep a different generic-match.c) ?
>>>>> b) Interface to GENERIC match_and_simplify - I guess it would be same as
>>>>> fold_binary / fold_unary ?
>>>>> c) We already have matching code in place for GENERIC
>>>>> (dt_operand::gen_generic_expr),
>>>>> we shall need to add code for generating GENERIC transforms.
>>>>>
>>>>> Thanks and Regards,
>>>>> Prathamesh
>>>>>
>>>>>>
>>>>>> Richard.
>>>>>>
>>>>>>> Thanks and Regards,
>>>>>>> Prathamesh
>>>>>>>
>>>>>>>>
>>>>>>>> Thanks,
>>>>>>>> Richard.
>>>>>>>>
>>>>>>>> > 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 211888)
+++ gcc/genmatch.c	(working copy)
@@ -30,7 +30,6 @@ along with GCC; see the file COPYING3.
 #include "hash-table.h"
 #include "vec.h"
 
-
 /* libccp helpers.  */
 
 static struct line_maps *line_table;
@@ -312,16 +311,16 @@ struct simplify {
 };
 
 void
-print_operand (operand *o, FILE *f = stderr)
+print_operand (operand *o, FILE *f = stderr, bool flattened = false)
 {
   if (o->type == operand::OP_CAPTURE)
     {
       capture *c = static_cast<capture *> (o);
       fprintf (f, "@%s", (static_cast<capture *> (o))->where);
-      if (c->what)
+      if (c->what && flattened == false) 
 	{
 	  putc (':', f);
-	  print_operand (c->what, f);
+	  print_operand (c->what, f, flattened);
 	  putc (' ', f);
 	}
     }
@@ -335,14 +334,17 @@ print_operand (operand *o, FILE *f = std
   else if (o->type == operand::OP_EXPR)
     {
       expr *e = static_cast<expr *> (o);
-      fprintf (f, "(%s ", e->operation->op->id);
+      fprintf (f, "(%s", e->operation->op->id);
 
-      for (unsigned i = 0; i < e->ops.length (); ++i)
+      if (flattened == false)
 	{
-	  print_operand (e->ops[i], f);
 	  putc (' ', f);
+	  for (unsigned i = 0; i < e->ops.length (); ++i)
+	    {
+	      print_operand (e->ops[i], f, flattened);
+	      putc (' ', f);
+	    }
 	}
-
       putc (')', f);
     }
 
@@ -702,6 +704,620 @@ capture::gen_gimple_match (FILE *f, cons
 }
 
 
+
+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
+    return false;
+}
+
+struct dt_node
+{
+  enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
+
+  enum dt_type type;
+  unsigned level;
+  vec<dt_node *> kids;
+
+  dt_node (enum dt_type type_): type (type_), level (0), kids (vNULL) {} 
+  
+  dt_node *append_node (dt_node *); 
+  dt_node *append_op (operand *, dt_node *parent = 0, unsigned pos = 0); 
+  dt_node *append_true_op (dt_node *parent = 0, unsigned pos = 0);
+  dt_node *append_match_op (unsigned, dt_node *parent = 0, unsigned pos = 0);
+  dt_node *append_simplify (simplify *, unsigned, unsigned *); 
+
+  virtual void gen_gimple (FILE *) {}
+};
+
+struct dt_operand: public dt_node
+{
+  operand *op;
+  unsigned m_level; // for match
+  dt_operand *parent;
+  unsigned pos;
+  vec<unsigned> temps;
+  static unsigned temp_count;
+ 
+  dt_operand (enum dt_type type, operand *op_, unsigned m_level_, dt_operand *parent_ = 0, unsigned pos_ = 0)
+	: dt_node (type), op (op_), m_level (m_level_), parent (parent_), pos (pos_), temps (vNULL) {}
+
+  virtual void gen_gimple (FILE *);
+  unsigned gen_gimple_predicate (FILE *, const char *);
+  unsigned gen_gimple_match_op (FILE *, const char *);
+
+  unsigned gen_gimple_expr (FILE *, const char *);
+  void gen_gimple_expr_expr (FILE *, expr *);
+  void gen_gimple_expr_fn (FILE *, expr *);
+
+  unsigned gen_generic_expr (FILE *, const char *);
+  void gen_generic_expr_expr (FILE *, expr *, const char *);
+  void gen_generic_expr_fn (FILE *, expr *, const char *);
+};
+
+unsigned dt_operand::temp_count = 0;
+
+struct dt_simplify: public dt_node
+{
+  static const unsigned level_max = UINT_MAX;
+  static const unsigned capture_max = 4;
+  simplify *s; 
+  unsigned pattern_no;
+  unsigned indexes[capture_max]; 
+  
+  dt_simplify (simplify *s_, unsigned pattern_no_, unsigned *indexes_)
+	: dt_node (DT_SIMPLIFY), s (s_), pattern_no (pattern_no_)
+  {
+    for (unsigned i = 0; i < capture_max; ++i)
+      indexes[i] = indexes_[i];
+  }
+
+  virtual void gen_gimple (FILE *f);
+};
+
+struct decision_tree
+{
+  dt_node *root;
+  
+  void insert (struct simplify *, unsigned);
+  void gen_gimple (FILE *f = stderr);
+  void print (FILE *f = stderr);
+
+  decision_tree () { root = new dt_node (dt_node::DT_NODE); }
+
+  static dt_node *insert_operand (dt_node *, operand *, unsigned *indexes, unsigned pos = 0, dt_node *parent = 0);
+  static dt_node *find_node (vec<dt_node *>&, dt_node *);
+  static bool cmp_node (dt_node *, dt_node *);
+  static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
+};
+
+bool
+decision_tree::cmp_node (dt_node *n1, dt_node *n2)
+{
+  if (!n1 || !n2 || n1->type != n2->type)
+    return false;
+
+  if (n1 == n2 || n1->type == dt_node::DT_TRUE)
+    return true;
+
+  if (n1->type == dt_node::DT_OPERAND)
+    return cmp_operand ((static_cast<dt_operand *> (n1))->op, (static_cast<dt_operand *> (n2))->op);
+
+  else if (n1->type == dt_node::DT_MATCH)
+    return (static_cast<dt_operand *> (n1))->m_level == (static_cast<dt_operand *> (n2))->m_level;
+
+  else
+    return false;
+}
+
+dt_node *
+decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
+{
+  for (unsigned i = 0; i < ops.length (); ++i)
+    if (decision_tree::cmp_node (ops[i], p))
+      return ops[i]; 
+  
+  return 0;
+}
+
+dt_node *
+dt_node::append_node (dt_node *n)
+{
+  dt_node *kid;
+
+  kid = decision_tree::find_node (kids, n);
+  if (kid)
+    return kid;
+
+  kids.safe_push (n);
+  n->level = this->level + 1;
+
+  unsigned len = kids.length ();
+
+  if (len > 1 && kids[len - 2]->type == dt_node::DT_TRUE)
+    {
+      dt_node *p = kids[len - 2];
+      kids[len - 2] = kids[len - 1];
+      kids[len - 1] = p;
+    }
+
+  return n;
+}
+
+dt_node *
+dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
+{
+  dt_operand *parent_ = static_cast<dt_operand *> (parent);
+  dt_node *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
+  dt_node *p = append_node (n);
+
+  if (p != n)
+    free (n);
+
+  return p; 
+}
+
+dt_node *
+dt_node::append_true_op (dt_node *parent, unsigned pos)
+{
+  dt_operand *parent_ = static_cast<dt_operand *> (parent);
+  dt_node *n = new dt_operand (DT_TRUE, 0, 0, parent_, pos);
+  dt_node *p = append_node (n);
+
+  if (p != n)
+    free (n);
+
+  return p;
+}
+
+dt_node *
+dt_node::append_match_op (unsigned m_level, dt_node *parent, unsigned pos)
+{
+  dt_operand *parent_ = static_cast<dt_operand *> (parent);
+  dt_node *n = new dt_operand (DT_MATCH, 0, m_level, parent_, pos);
+  dt_node *p = append_node (n);
+
+  if (p != n)
+    free (n);
+
+  return p;
+}
+
+dt_node *
+dt_node::append_simplify (simplify *s, unsigned pattern_no, unsigned *indexes) 
+{
+  dt_node *n = new dt_simplify (s, pattern_no, indexes);
+  return append_node (n);
+}
+
+dt_node *
+decision_tree::insert_operand (dt_node *p, operand *o, unsigned *indexes, unsigned pos, dt_node *parent) 
+{
+  dt_node *q;
+
+  if (o->type == operand::OP_CAPTURE)
+    {
+      capture *c = static_cast<capture *> (o);
+      unsigned capt_index = atoi (c->where);
+
+      if (indexes[capt_index] == dt_simplify::level_max)
+	{
+	  indexes[capt_index] = p->level + 1;
+
+	  if (c->what)
+	    return insert_operand (p, c->what, indexes, pos, parent);
+	  else
+	    {
+	      p = p->append_true_op (parent, pos);
+	      return p;
+	    }
+	}
+      else
+	{
+	  p = p->append_match_op (indexes[capt_index], parent, pos);
+	  if (c->what)
+	    return insert_operand (p, c->what, indexes, 0, p);
+	  else
+	    return p;
+	}
+    }
+  p = p->append_op (o, parent, pos);
+  q = p;
+
+  if (o->type == operand::OP_EXPR)
+    {
+      expr *e = static_cast<expr *> (o);
+      for (unsigned i = 0; i < e->ops.length (); ++i)
+	q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p);		
+    }
+
+  return q;
+}
+
+void
+decision_tree::insert (struct simplify *s, unsigned pattern_no)
+{
+  unsigned indexes[dt_simplify::capture_max];
+
+  for (unsigned i = 0; i < s->matchers.length (); ++i)
+    {
+      if (s->matchers[i]->type != operand::OP_EXPR)
+	continue;
+
+      for (unsigned j = 0; j < dt_simplify::capture_max; ++j)
+	indexes[j] = dt_simplify::level_max;
+
+      dt_node *p = decision_tree::insert_operand (root, s->matchers[i], indexes);
+      p->append_simplify (s, pattern_no, indexes);
+    }            
+}
+
+void
+decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
+{
+  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)
+	{
+	  dt_operand *dop = static_cast<dt_operand *>(p);
+	  print_operand (dop->op, f, true); 
+	} 
+      else if (p->type == dt_node::DT_TRUE)
+	fprintf (f, "true");
+      else if (p->type == dt_node::DT_MATCH)
+	fprintf (f, "match (%u)", ((static_cast<dt_operand *>(p))->m_level));
+      else if (p->type == dt_node::DT_SIMPLIFY)
+	{
+	  dt_simplify *s = static_cast<dt_simplify *> (p);
+	  fprintf (f, "simplify_%u { ", s->pattern_no); 
+	  for (unsigned i = 0; i < dt_simplify::capture_max; ++i)
+	    fprintf (f, "%u, ", s->indexes[i]);
+	  fprintf (f, " } "); 
+	}
+    }      
+
+  fprintf (stderr, " (%p), %u, %u\n", (void *) p, p->level, p->kids.length ());
+
+  for (unsigned i = 0; i < p->kids.length (); ++i)
+    decision_tree::print_node (p->kids[i], f, indent + 2);
+}
+
+
+void
+decision_tree::print (FILE *f)
+{
+  return decision_tree::print_node (root, f);
+}
+
+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");
+}
+
+unsigned
+dt_operand::gen_gimple_predicate (FILE *f, const char *opname)
+{
+  predicate *p = static_cast<predicate *> (op);
+
+  fprintf (f, "if (%s (%s))\n", p->ident, opname);
+  fprintf (f, "{\n");
+  return 1;
+}
+
+unsigned
+dt_operand::gen_gimple_match_op (FILE *f, const char *opname)
+{
+  fprintf (f, "if (%s == o%u)\n", opname, m_level);
+  fprintf (f, "{\n");
+  return 1;
+}
+
+void
+dt_operand::gen_gimple_expr_fn (FILE *f, expr *e)
+{
+  unsigned n_ops = e->ops.length ();
+
+  fn_id *op = static_cast <fn_id *> (e->operation->op);
+  fprintf (f, "if (gimple_call_builtin_p (def_stmt, %s))\n", op->id);
+  fprintf (f, "{\n");
+
+  for (unsigned i = 0; i < n_ops; ++i)
+    {
+      char child_opname[20];
+      sprintf (child_opname, "t%u", dt_operand::temp_count);
+      temps.safe_push (dt_operand::temp_count++);
+
+      fprintf (f, "tree %s = gimple_call_arg (def_stmt, %u);\n", child_opname, i);
+      fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", child_opname, child_opname);
+      fprintf (f, "{\n");
+    } 
+}
+
+void
+dt_operand::gen_gimple_expr_expr (FILE *f, expr *e)
+{
+  unsigned n_ops = e->ops.length (); 
+
+  operator_id *op_id = static_cast <operator_id *> (e->operation->op);
+  
+  if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR)
+    fprintf (f, "if (is_gimple_assign (def_stmt)\n"
+	        "    && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))");
+  else
+    fprintf (f, "if (is_gimple_assign (def_stmt) && gimple_assign_rhs_code (def_stmt) == %s)\n", op_id->id);
+
+  fprintf (f, "{\n");
+  
+  for (unsigned i = 0; i < n_ops; ++i)
+    {
+      char child_opname[20];
+      sprintf (child_opname, "t%u", dt_operand::temp_count);
+      temps.safe_push (dt_operand::temp_count++);
+
+      fprintf (f, "tree %s = gimple_assign_rhs%u (def_stmt);\n", child_opname, i + 1);
+      fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", child_opname, child_opname);
+      fprintf (f, "{\n");
+    }      
+} 
+
+unsigned
+dt_operand::gen_gimple_expr (FILE *f, const char *opname)
+{
+  unsigned i;
+  expr *e = static_cast<expr *> (op);
+
+  fprintf (f, "if (TREE_CODE (%s) == SSA_NAME)\n", opname);
+  fprintf (f, "{\n");
+  
+  fprintf (f, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", opname);
+  (e->operation->op->kind == id_base::CODE) ? gen_gimple_expr_expr (f, e) : gen_gimple_expr_fn (f, e);
+
+  return e->ops.length () + 2;
+}
+
+
+void
+dt_operand::gen_generic_expr_expr (FILE *f, expr *e, const char *opname)
+{
+  unsigned n_ops = e->ops.length ();
+
+  fprintf (f, "if (TREE_CODE (%s) == %s)\n", opname, e->operation->op->id);
+  fprintf (f, "{\n");
+
+  for (unsigned i = 0; i < n_ops; ++i)
+    {
+      char child_opname[20];
+      sprintf (child_opname, "t%u", dt_operand::temp_count);
+      temps.safe_push (dt_operand::temp_count++);
+
+      fprintf (f, "tree %s = TREE_OPERAND (%s, %u);\n", child_opname, opname, i);
+      fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", child_opname, child_opname);
+      fprintf (f, "{\n");
+    }
+}   
+
+void
+dt_operand::gen_generic_expr_fn (FILE *f, expr *e, const char *opname)
+{
+  unsigned n_ops = e->ops.length ();
+  fn_id *op = static_cast <fn_id *> (e->operation->op);
+
+  fprintf (f, "if (TREE_CODE (%s) == CALL_EXPR\n"
+               "    && TREE_CODE (CALL_EXPR_FN (%s)) == ADDR_EXPR\n"
+               "    && TREE_CODE (TREE_OPERAND (CALL_EXPR_FN (%s), 0)) == FUNCTION_DECL\n"
+               "    && DECL_BUILT_IN_CLASS (TREE_OPERAND (CALL_EXPR_FN (%s), 0)) == BUILT_IN_NORMAL\n"
+               "    && DECL_FUNCTION_CODE (TREE_OPERAND (CALL_EXPR_FN (%s), 0)) == %s)\n",
+               opname, opname, opname, opname, opname, op->id);
+  fprintf (f, "  {\n");
+
+  for (unsigned i = 0; i < n_ops; ++i)
+    {
+      char child_opname[20];
+      sprintf (child_opname, "t%u", dt_operand::temp_count);
+      temps.safe_push (dt_operand::temp_count++);
+
+      fprintf (f, "tree %s = CALL_EXPR_ARG (%s, %u);\n", child_opname, opname, i);
+      fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", child_opname, child_opname);
+      fprintf (f, "{\n");
+    }
+}
+
+unsigned
+dt_operand::gen_generic_expr (FILE *f, const char *opname)
+{
+  unsigned i;
+  expr *e = static_cast<expr *> (op);
+  (e->operation->op->kind == id_base::CODE) ? gen_generic_expr_expr (f, e, opname) : gen_generic_expr_fn (f, e, opname);
+  return e->ops.length () + 1;
+}
+
+void
+dt_operand::gen_gimple (FILE *f)
+{
+  char opname[20];
+  sprintf (opname, "o%u", level);
+  
+
+  fprintf (f, "{\n");
+
+  if (parent->parent == 0)
+    fprintf (f, "tree %s = op%u;\n", opname, pos);
+  else if (parent->type == dt_node::DT_MATCH)
+    fprintf (f, "tree %s = o%u;\n", opname, parent->level);
+  else if (parent->type == dt_node::DT_OPERAND && parent->op->type == operand::OP_EXPR) 
+    fprintf (f, "tree %s = t%u;\n", opname, parent->temps[pos]);
+  else
+    gcc_unreachable ();
+
+  unsigned n_braces = 0;
+ 
+  if (type == DT_OPERAND)
+    switch (op->type)
+      {
+	case operand::OP_PREDICATE:
+	  n_braces = gen_gimple_predicate (f, opname);
+	  break;
+
+	case operand::OP_EXPR:
+	{
+	  expr *e = static_cast<expr *> (op);
+  	  operator_id *op_id = static_cast <operator_id *> (e->operation->op);
+	  enum tree_code code = op_id->code;
+
+	  if (code == REALPART_EXPR || code == IMAGPART_EXPR || code == VIEW_CONVERT_EXPR || code == BIT_FIELD_REF)
+	    n_braces = gen_generic_expr (f, opname);
+
+	  // check for cond_expr, 0th operand -> generic
+	  else if (parent->type == dt_node::DT_OPERAND && parent->op->type == operand::OP_EXPR)
+	    {
+	      e = static_cast<expr *> (parent->op);
+	      op_id = static_cast <operator_id *> (e->operation->op);
+	      n_braces = (op_id->code == COND_EXPR && pos == 0) ? gen_generic_expr (f, opname) : gen_gimple_expr (f, opname);
+	    }
+	  else
+	    n_braces = gen_gimple_expr (f, opname);
+	}
+	  break;
+
+	default:
+	  gcc_unreachable ();
+      }
+  else if (type == DT_TRUE)
+    ;
+  else if (type == DT_MATCH)
+    n_braces = gen_gimple_match_op (f, opname);
+  else
+    gcc_unreachable ();
+
+  unsigned i;
+
+  for (i = 0; i < kids.length (); ++i)
+    kids[i]->gen_gimple (f);
+
+  for (i = 0; i < n_braces; ++i)
+    fprintf (f, "}\n");
+  
+  fprintf (f, "}\n");
+}
+
+void
+dt_simplify::gen_gimple (FILE *f)
+{
+  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
+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");
+}
+
+
 static void
 write_nary_simplifiers (FILE *f, vec<simplify *>& simplifiers, unsigned n)
 {
@@ -861,9 +1477,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
 }
 
 
@@ -1219,7 +1837,14 @@ main(int argc, char **argv)
   for (unsigned i = 0; i < simplifiers.length (); ++i)
     print_matches (simplifiers[i]);
 
+  decision_tree dt;
+  for (unsigned i = 0; i < simplifiers.length (); ++i)
+    dt.insert (simplifiers[i], i);
+
+  dt.print (stderr);
+ 
   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 211888)
+++ 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;
+}