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