This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [GSoC] decision tree first steps


On Sat, Jun 14, 2014 at 12:43 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On June 13, 2014 11:48:13 PM CEST, Prathamesh Kulkarni <bilbotheelffriend@gmail.com> wrote:
>>On Thu, Jun 12, 2014 at 4:26 PM, Richard Biener
>><richard.guenther@gmail.com> wrote:
>>> On Wed, Jun 11, 2014 at 4:09 PM, Prathamesh Kulkarni
>>> <bilbotheelffriend@gmail.com> wrote:
>>>> On 6/11/14, Richard Biener <richard.guenther@gmail.com> wrote:
>>>>> On Wed, Jun 11, 2014 at 12:53 PM, Richard Biener
>>>>> <richard.guenther@gmail.com> wrote:
>>>>>> On Wed, Jun 11, 2014 at 10:51 AM, Richard Biener
>>>>>> <richard.guenther@gmail.com> wrote:
>>>>>>> On Tue, Jun 10, 2014 at 1:57 PM, Richard Biener
>>>>>>> <richard.guenther@gmail.com> wrote:
>>> [...snip...]
>>>>>>>> But then why not generate
>>>>>>>>
>>>>>>>>   if (!captures[0]
>>>>>>>>       || captures[0] == op0)
>>>>>>>>     {
>>>>>>>>       captures[0] = op0;
>>>>>>>>       // simplification code S1
>>>>>>>>       return true;
>>>>>>>>     }
>>>>>>>>
>>>>>>>> and go without label and goto?  Or did I miss something?
>>>>>>>>
>>>>>>>>> c) Shared captures between all patterns:
>>>>>>>>> In the patch all patterns share the capture array tree
>>captures[4] =
>>>>>>>>> {}
>>>>>>>>> (since all match patterns get interleaved in generated code off
>>>>>>>>> decision tree).
>>>>>>>>> This requires extra code to be generated to make sure captures
>>are
>>>>>>>>> correctly restored for another pattern.
>>>>>>>
>>>>>>> Btw, I see that you back-track the decision tree.  That is, for
>>>>>>>
>>>>>>> root
>>>>>>> |--operand: MINUS_EXPR
>>>>>>> |----operand: PLUS_EXPR
>>>>>>> |------operand: @0
>>>>>>> |--------operand: @1
>>>>>>> |----------operand: @0
>>>>>>> |------------simplify
>>>>>>> |----------operand: @1
>>>>>>> |------------simplify
>>>>>>>
>>>>>>> you do
>>>>>>>
>>>>>>>   if (code == MINUS_EXPR)
>>>>>>>     {
>>>>>>>       tree captures[4] = {};
>>>>>>>       if (TREE_CODE (op0) == SSA_NAME)
>>>>>>>         {
>>>>>>>           gimple def_stmt = SSA_NAME_DEF_STMT (op0);
>>>>>>>           if (is_gimple_assign (def_stmt) &&
>>gimple_assign_rhs_code
>>>>>>> (def_stmt) == PLUS_EXPR)
>>>>>>>             {
>>>>>>>               tree op01 = gimple_assign_rhs1 (def_stmt);
>>>>>>>               if (valueize && TREE_CODE (op01) == SSA_NAME)
>>>>>>>                 op01 = valueize (op01);
>>>>>>>               else
>>>>>>>                 goto L0;
>>>>>>>               if (op01)
>>>>>>>                 {
>>>>>>> L0:
>>>>>>>                   tree op11 = gimple_assign_rhs2 (def_stmt);
>>>>>>>                   if (valueize && TREE_CODE (op11) == SSA_NAME)
>>>>>>>                     op11 = valueize (op11);
>>>>>>>                   else
>>>>>>>                     goto L1;
>>>>>>>                   if (op11)
>>>>>>>                     {
>>>>>>> L1:
>>>>>>>                       tree captures_0 = captures[0];
>>>>>>>                       if (!captures[0])
>>>>>>>                         {
>>>>>>>                           captures[0] = op01;
>>>>>>>                           goto L2;
>>>>>>>                         }
>>>>>>>                       else if (captures[0] == op01)
>>>>>>>                         {
>>>>>>> L2:
>>>>>>>                           tree captures_1 = captures[1];
>>>>>>>                           if (!captures[1])
>>>>>>>                             {
>>>>>>>                               captures[1] = op11;
>>>>>>>                               goto L3;
>>>>>>>                             }
>>>>>>>                           else if (captures[1] == op11)
>>>>>>>                             {
>>>>>>> L3:
>>>>>>>                               tree captures_2 = captures[0];
>>>>>>>                               if (!captures[0])
>>>>>>>                                 {
>>>>>>>                                   captures[0] = op1;
>>>>>>>                                   goto L4;
>>>>>>>                                 }
>>>>>>>                               else if (captures[0] == op1)
>>>>>>>                                 {
>>>>>>> L4:
>>>>>>>                                   res_ops[0] = captures[1];
>>>>>>>                                   *res_code = TREE_CODE
>>(res_ops[0]);
>>>>>>>                                   return true;
>>>>>>>                                 }
>>>>>>>                               captures [0] = captures_2;
>>>>>>>                               tree captures_3 = captures[1];
>>>>>>>                               if (!captures[1])
>>>>>>>                                 {
>>>>>>>                                   captures[1] = op1;
>>>>>>>                                   goto L5;
>>>>>>>                                 }
>>>>>>>                               else if (captures[1] == op1)
>>>>>>>                                 {
>>>>>>> L5:
>>>>>>>                                   res_ops[0] = captures[0];
>>>>>>>                                   *res_code = TREE_CODE
>>(res_ops[0]);
>>>>>>>                                   return true;
>>>>>>>                                 }
>>>>>>>                               captures [1] = captures_3;
>>>>>>>                             }
>>>>>>>                           captures [1] = captures_1;
>>>>>>>                         }
>>>>>>>                       captures [0] = captures_0;
>>>>>>>                     }
>>>>>>>                 }
>>>>>>>             }
>>>>>>>         }
>>>>>>>
>>>>>>> but if you processed all children of a decision tree node and
>>didn't
>>>>>>> hit one of the simplifies (which return true) then you know
>>nothing
>>>>>>> else will match and you can just return false.  That early out
>>seems
>>>>>>> to be missing completely and we fall through processing all
>>siblings
>>>>>>> of the parents.
>>>>>>>
>>>>>>> But maybe I am missing something?  I see that if I make capture
>>>>>>> IDs not matching that we'd miss to detect things then (as a
>>>>>>> "first" capture always "matches").
>>>>>>>
>>>>>>> root
>>>>>>> |--operand: MINUS_EXPR
>>>>>>> |----operand: PLUS_EXPR
>>>>>>> |------operand: @0
>>>>>>> |--------operand: @1
>>>>>>> |----------operand: @0
>>>>>>> |------------simplify
>>>>>>> |------operand: @1
>>>>>>> |--------operand: @0
>>>>>>> |----------operand: @0
>>>>>>> |------------simplify
>>>>>>>
>>>>>>> So I suppose we really have to distinguish "first" captures from
>>>>>>> "matching" captures, basically not treating the "first" ones as
>>>>>>> nodes of the decision tree and only populating the capture
>>>>>>> array once we hit the code generation part of a pattern (well,
>>>>>>> or the if-expr).
>>>>>>
>>>>>> It's probably a good idea to pre-parse the AST to classify
>>>>>> captures and matches differently.  Given for example
>>>>>>
>>>>>> (plus @0 (minus@0 @1 @2))
>>>>>>
>>>>>> this would say (well, if we support this), that the plus has two
>>>>>> "same" operands (on GIMPLE the "same" valueized SSA name)
>>>>>> and that this operand is defined by a (minus @1 @2).  But with
>>>>>> the current operator ordering in the decision tree we'd meet
>>>>>> the no-op capture first and the match in an odd position.
>>>>>>
>>>>>> In the RTL machine description the matches are more explicit
>>>>>> like
>>>>>>
>>>>>> (plus (match @0) (minus@0 @1 @2))
>>>>>>
>>>>>> so maybe we want to auto-detect those and rewrite the AST.
>>>>>> Just distinguish between capture-def and capture-ref, where
>>>>>> expression captures are always -def but leafs may be -refs as
>>well.
>>>>>>
>>>>>> In the decision tree builder we'd "ignore" -defs and only make
>>>>>> -refs explicit (and the -refs would need to "materialize" the
>>-defs
>>>>>> just like the ifexpr or transform stage).
>>>>>>
>>>>>> So I'd say add a flag to struct capture telling whether it's a ref
>>>>>> and compute that via an AST traversal (that should then error
>>>>>> for invalid refs).
>>>>>>
>>>>>> In the decision tree I'd keep a vector of operand * and record
>>>>>> a name of a temporary the operand can be accessed via
>>>>>> (in case any of the AST operands represented by the decision tree
>>>>>> node has a capture associated).
>>>>>>
>>>>>> You'd still have "empty" leaf captures that would then only record
>>>>>> the value into a temporary.
>>>>>>
>>>>>> Eventually you need a back-ref to the decision tree node for
>>>>>> each capture when you insert a new AST traversal so you
>>>>>> can decide whether a match (a capture-ref) refers to the same
>>>>>> decision tree node or not.
>>>>>>
>>>>>> Richard.
>>>>>
>>>>> Ok, let me re-phrase after some more thinking and talking with
>>>>> a collegue.
>>>>>
>>>>> When you do the AST traversal computing the array of AST operands *
>>>>> you'd initialize book-keeping like the following
>>>>>
>>>>>  for operand in AST do
>>>>>    if (operand is a capture)
>>>>>     {
>>>>>       if (this capture index was not yet seen)
>>>>>         {
>>>>>           record for this pattern (in its simplify node created at
>>the
>>>>>           decision tree leaf) that the capture index refers to the
>>>>>           operand with the current index
>>>>>           if (capture has a sub-expression)
>>>>>             recurse
>>>>>           else
>>>>>             insert "true" op (matches everything)
>>>>>         }
>>>>>       else
>>>>>         {
>>>>>           generate a decision tree node that matches the decision
>>>>>           tree index of the capture
>>>>>           recurse
>>>>>         }
>>>>>     }
>>>>>   else
>>>>>     record op and recurse
>>>>>
>>>>> So when you generate code you implicitely capture all operands
>>>>> in automatic variables named like 'captureN' with 'N' being the
>>>>> current level of the decision tree (the index of the operand array
>>>>> from the AST walk).  Once you hit a 'match-X' node you
>>>>> simply match against the operand from the refered to decision
>>>>> tree index.
>>>>>
>>>>> Once you reach the ifexpr point you populate the operands[] array
>>>>> from the side-information you initialized in the AST traversal and
>>>>> the automatic variables initialized from the decision tree walk.
>>>>>
>>>>> So
>>>>>
>>>>> (plus (minus@2 @1 @3) @2)
>>>>>
>>>>> would have the decision tree
>>>>>
>>>>> plus - minus - 'true' - 'true' - match(1) - simplify
>>>>>
>>>>> and the generated code would look like (simplified)
>>>>>
>>>>>   [can't capture outermost expr]
>>>>>   if (code == plus)
>>>>>     {
>>>>>       op1 = gimple_assign_rhs1 (plus-stmt);
>>>>>       if (TREE_CODE (op1) == minus)
>>>>>         {
>>>>>           op2 = gimple_assign_rhs1 (minus-stmt);
>>>>>           if (true)
>>>>>             {
>>>>>               op3 = gimple_assign_rhs2 (minus-stmt);
>>>>>               if (true)
>>>>>                 {
>>>>>                    op4 = gimple_assign_rhs2 (plus-stmt);
>>>>>                    if (op4 == op1)
>>>>>                      {
>>>>>                         operands[0] = op2;
>>>>>                         operands[1] = op1;
>>>>>                         operands[2] = op3;
>>>> Did you mean captures ?
>>>> captures[0] = op2;
>>>> captures[1] = op1;
>>>> captures[2] = op3
>>>
>>> Yes, of course.
>>>
>>>>>                         <simplify>
>>>>>
>>>>> where the 'true' cases would be matched last (as "else") in case
>>there
>>>>> are multiplie choices here if you'd have also
>>>>>
>>>>> (plus @1 (minus @2 @3))
>>>>>
>>>>> the decision tree would become
>>>>>
>>>>> plus - minus - 'true' - 'true' - match(1) - simplify
>>>>>         \
>>>>>           'true' - minus - 'true' - 'true' - simplify
>>>>>
>>>> Thanks, I will get started on this. Today I added a patch that
>>handles
>>>> "matching-captures" but does not commonize, I am not not posting
>>since
>>>> it's of no
>>>> use now. The above algorithm will also get rid of generating
>>temporary
>>>> as op<pos><level>.
>>>
>>> Indeed.  Note that it probably makes sense to do all the bookkeeping
>>> setup in the decision tree insertion - splitting parts to the AST
>>traversal
>>> that builds the linear operand vector probably just complicates
>>things.
>>>
>>>> suppose these are patterns:
>>>> (plus @0 @1) S1
>>>> (plus @1 @0) S2
>>>>
>>>> then how would be decision tree represented as ?
>>>>
>>>> plus - true - true - S1
>>>>                         \
>>>>                           S2
>>>
>>> Yes.
>>>
>>>> I suppose pattern-1 would always match (even with earlier code gen.
>>>
>>> Yes.  We might emit a warning if we detect such a case.
>>>
>>> Note that if we have
>>>
>>>   plus - true - S1
>>>           \
>>>             minus.... - S2
>>>           \
>>>             mult...  - S3
>>>
>>> then the code for the children of the plus node looks like
>>>
>>>     if (sub-code == minus)
>>>     else if (sub-code == mult)
>>>     else /*  if (true)  */
>>>        S1;
>>>
>>> so a 'true' case has to be always processed last.
>>For the pattern (made-up):
>>(plus @0 (negate@0 @1)) S
>>
>>the decision-tree would look like the following: ?
>>plus - true - negate - true - match (1) - simplify
>>match (1) matches @0
>
> You could also do
>
> Plus - true - match(1) - negate - true
>
> To avoid doing two things in one node.
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).

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

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

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

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 ?

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

* Added do_valueize () in gimple-match-head.c. the generated code
calls do_valueize to valueize theopereand.
This make code-gen simpler (no goto).

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.

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 -:)

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.  */
 
@@ -202,19 +203,29 @@ add_builtin (enum built_in_function code
 /* The predicate expression tree structure.  */
 
 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_), parent (0), pos (0), preorder_level (0) {} 
   enum op_type type;
-  virtual void gen_gimple_match (FILE *f, const char *, const char * = NULL) = 0;
+
+  operand *parent;
+  unsigned pos;
+  unsigned preorder_level;
+
+  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 {
@@ -227,11 +238,13 @@ struct expr : public operand
 {
   expr (e_operation *operation_)
     : operand (OP_EXPR), operation (operation_), ops (vNULL) {}
-  void append_op (operand *op) { ops.safe_push (op); }
+  void append_op (operand *op) { ops.safe_push (op); op->parent = this; op->pos = ops.length() - 1; }
   e_operation *operation;
   vec<operand *> ops;
   virtual void gen_gimple_match (FILE *f, const char *, const char *);
   virtual void gen_gimple_transform (FILE *f, const char *, const char *);
+
+  virtual unsigned gen_gimple_match_dt (FILE *f, const char *);
 };
 
 struct c_expr : public operand
@@ -245,6 +258,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 +270,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 +351,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 +593,493 @@ 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", preorder_level, opname);
+
+  fprintf (f, "if (is_gimple_assign (def_stmt%u) && gimple_assign_rhs_code (def_stmt%u) == %s)\n",
+	   preorder_level, preorder_level, operation->op->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 ();
+    }
+}
+
+
+void
+walk_operand_preorder(vec<operand *>& operands, operand *op)
+{
+  operands.safe_push (op);
+  if (op->type == operand::OP_EXPR)
+    {
+      expr *e = static_cast<expr *>(op);
+      for (unsigned i = 0; i < e->ops.length(); ++i)
+        walk_operand_preorder (operands, e->ops[i]);
+    }
+  else if (op->type == operand::OP_CAPTURE)
+    {
+      capture *capt = static_cast<capture *>(op);
+      if (capt->what)
+	{
+	  capt->what->parent = capt;
+	  capt->what->pos = 0;
+	  walk_operand_preorder (operands, capt->what);
+	}
+    }
+}
+
+static operand *
+operand_get_what (operand *op)
+{
+  if (op->type == operand::OP_CAPTURE)
+    {
+      capture *c = static_cast<capture *>(op);
+      return c->what;
+    }
+  return 0;
+}
+
+
+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;
+
+  decision_tree() { root = 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)
+{
+  fprintf (f, "{\n");
+
+  char opname[128];
+  sprintf (opname, "o%u", op->preorder_level);
+
+  print_flattened_operand (op); putc ('\n', stderr);
+
+  if (op->parent->parent == 0)
+    fprintf (f, "tree %s = op%u;\n", opname, op->pos);
+  else if (op->parent->type == operand::OP_TRUE || op->parent->type == operand::OP_MATCH)
+    {
+      fprintf (stderr, "supriya\n");
+      fprintf (f, "tree %s = o%u;\n", opname, op->parent->preorder_level);
+      fprintf (f, "{\n");
+    }
+  else 
+    {
+      fprintf (f, "tree %s = gimple_assign_rhs%u (def_stmt%u);\n", opname, op->pos + 1, op->parent->preorder_level);
+      fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", opname, opname);
+      fprintf (f, "{\n");
+    }
+
+  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 (op->parent->parent || op->parent->type == operand::OP_TRUE || op->parent->type == operand::OP_MATCH)
+    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));
+}
+
+/* lower capture to  match_operand or true_operand */
+
+static operand * 
+lower_capture (operand *op, unsigned level, unsigned *indexes)
+{
+  if (op->type != operand::OP_CAPTURE)
+    return op;
+
+  capture *c = static_cast<capture *> (op);
+  unsigned capt_index = atoi (c->where);
+  operand *o;  
+
+  print_flattened_operand (op);
+  fprintf (stderr, "\n");
+
+  if (indexes[capt_index] == dt_simplify::level_max)
+    {
+      indexes[capt_index] = level;
+      fprintf (stderr, "set indexes[%u] to %u\n", capt_index, level);
+      o = new true_operand();
+    }
+  else
+    {
+      fprintf (stderr, "indexes[%u] == %u\n", capt_index, indexes[capt_index]);
+      o = new match_operand (indexes[capt_index]);
+    }
+  o->pos = c->pos;
+  o->parent = c->parent;
+
+  if (c->what)
+    c->what->parent = o;
+
+  return o;
+}
+
+dt_node *
+insert_operand (dt_node *p, operand *o, unsigned *indexes) 
+{
+  unsigned i;
+  operand *op;
+  vec<operand *> operands = vNULL;
+ 
+  walk_operand_preorder (operands, o);
+
+  fprintf (stderr, "[\n");
+  for (i = 0; i < operands.length (); ++i)
+    {
+      print_flattened_operand (operands[i]);
+      putc ('\n', stderr);
+    }
+  fprintf (stderr, "]\n");
+
+  for (i = 0; i < operands.length (); ++i)
+    {
+      op = lower_capture (operands[i], i, indexes);
+      op->preorder_level = i;
+      p = p->append_op (op);
+    }
+
+  return p;
+}
+
+void
+decision_tree::insert (struct simplify *s, unsigned pattern_no)
+{
+  if (s->match->type != operand::OP_EXPR)
+    return;
+
+  dt_simplify *ds = new dt_simplify (s->ifexpr, s->result, pattern_no);
+  dt_node *p = insert_operand (root, s->match, ds->indexes);
+  p->append_node (ds);
+}
 
 static void
 write_nary_simplifiers (FILE *f, vec<simplify *>& simplifiers, unsigned n)
@@ -713,9 +1235,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 +1567,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/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. fails because it's commutative variant is not present (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" } } */

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