On Mon, Jun 23, 2014 at 10:26 AM, Prathamesh Kulkarni
<bilbotheelffri...@gmail.com> wrote:
> On Thu, Jun 19, 2014 at 7:53 PM, Prathamesh Kulkarni
> <bilbotheelffri...@gmail.com> wrote:
>> On Thu, Jun 19, 2014 at 4:12 PM, Prathamesh Kulkarni
>> <bilbotheelffri...@gmail.com> wrote:
>>> On Thu, Jun 19, 2014 at 2:37 PM, Prathamesh Kulkarni
>>> <bilbotheelffri...@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.
>> 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.
@@ -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).
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?
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
>>>>>>> >> >>>>>>
>>>>>>> >> >>
>>>>>>> >> >>
