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


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

Re: [GSoC] decision tree first steps


On Mon, Jun 23, 2014 at 5:58 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Jun 23, 2014 at 1:51 PM, Prathamesh Kulkarni
> <bilbotheelffriend@gmail.com> wrote:
>> 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.
>
> Great.
>
>> 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.
>
> Looks good.
>
>> 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
>
> Can you shortly explain what is missing?
Oh I meant re-factoring/formatting changes for
decision-tree and gimple match-and-simplify code-gen.
>
>> b) GIMPLE match-and-simplify code generation
>> mostly done
>
> Likewise?
>
>> 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.
>
> Yep.  Most of the changes required for doing this on GIMPLE where
> required is in maybe_push_res_to_seq (if we ever create a REALPART
> or IMAGPART or BIT_FIELD_REF in the transform stage - the COND_EXPR
> handling should already work, just not optimally).
>
> If you are talking about full GENERIC support for fold-const.c replacement
> then this requires some more work and I'd like to at least implement the
> API side with some quick draft for genmatch.c
Yeah I was talking about full GENERIC support, although having GENERIC support
for the four cases (realpart/imagpart/view_convert/bit_field_ref),
would be nice first.
Sorry to be blunt, but how do we um start ?
I guess the generated generic_match_and_simplify () functions would
have prototype identical to
fold_unary, fold_binary ?
So we start by generating generic_match_and_simplify prototype
(similar to gimple_match_and_simplify in write_fn_prototype)
and by generating GENERIC simplification by adding .gen_generic_match
() on AST operands ?
code-gen for captures, c_expr would remain the same, I guess only expr
code-gen would be different.
>
>> 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.
>
> Yeah.
>
>> 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 can see that not having this kind of support will make writing patterns
> for comparison folding quite repetitive.  The for-style would more closely
> match how we'd implement support for this - parse the contained
> match-and-simplify with a (temporary) 'op' operator added and then
> duplicate it with replacing it.
>
> So I'd go for the iterator style which also makes
>
> (for op in plus, minus
>   (match_and_simplify
>     (op (op @0 @1) @2)
>     S))
>
> unambiguous compared to
>
>  (match_and_simplify
>    (plus|minus (plus|minus @0 @1) @2)
>    S)
>
> and I'd leave out the ',' in delimiting the ops to iterate over.
>
>> I could then start with phase-2, with pattern implementation from 1st July.
>
> Sounds fine to me though f) may really come in parallel to implement
> patterns as its best to see how it's used to see whether the idea works
> well.
>
> Richard.
>
>> 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 Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]