On Thu, Jun 12, 2014 at 4:26 PM, Richard Biener
<richard.guent...@gmail.com> wrote:
> On Wed, Jun 11, 2014 at 4:09 PM, Prathamesh Kulkarni
> <bilbotheelffri...@gmail.com> wrote:
>> On 6/11/14, Richard Biener <richard.guent...@gmail.com> wrote:
>>> On Wed, Jun 11, 2014 at 12:53 PM, Richard Biener
>>> <richard.guent...@gmail.com> wrote:
>>>> On Wed, Jun 11, 2014 at 10:51 AM, Richard Biener
>>>> <richard.guent...@gmail.com> wrote:
>>>>> On Tue, Jun 10, 2014 at 1:57 PM, Richard Biener
>>>>> <richard.guent...@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
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
>>>
