On Tue, Jun 17, 2014 at 12:21 AM, Prathamesh Kulkarni
<bilbotheelffri...@gmail.com> wrote:
> On Mon, Jun 16, 2014 at 4:45 PM, Richard Biener
> <richard.guent...@gmail.com> wrote:
>>
>> > * Patterns requiring GENERIC support like cond_expr
>> > I am not sure about how to handle these patterns. I was thinking about
>> > handling them after we have
>> > GENERIC code generation in place.
>>
>> Yeah, though handling GENERIC for matching is as simple as
>> emitting the code check twice, the 2nd check off the an else
>> from the if (TREE_CODE (op) == SSA_NAME). That is,
>> arrange for expr::gen_gimple_match_dt to emit
>>
>> if (TREE_CODE (...) == SSA_NAME)
>> {
>> gimple def_stmt = SSA_NAME_DEF_STMT (...);
>> if (is_gimple_assign (def_stmt) && gimple_assign_rhs_code
>> (def_stmt) == <code>)
>> {
>> ....
>> }
>> else (TREE_CODE (...) == <code>)
>> {
>> ....
>> }
>>
>> which would require some refactoring in the generator. As for refactoring
>> it I'd not hook the gen_gimple_match_dt off the AST operands but
>> inline it in the decision tree traversal routine - that also makes the
>> commoning above easier.
> Thanks, I shall get started on this.
Good. You also miss the special-casing of REALPART_EXPR,
IMAGPART_EXPR, VIEW_CONVERT_EXPR and BIT_FIELD_REF
operand extraction as you say below.
>>
>> Btw, I checked what we generate for (bogus)
>>
>> (match_and_simplify
>> (MINUS_EXPR (PLUS_EXPR@2 @0 @1) @2)
>> @1)
>>
>> and the DT looks like
>>
>> root, 1
>> |--operand: MINUS_EXPR, 1
>> |----operand: true, 1
>> |------operand: PLUS_EXPR, 1
>> |--------operand: true, 1
>> |----------operand: true, 1
>> |------------operand: match(1), 1
>> |--------------simplify_0, 0
>>
>> though I expected
>>
>> root, 1
>> |--operand: MINUS_EXPR, 1
>> |----operand: PLUS_EXPR, 1
>> |------operand: true, 1
>> |--------operand: true, 1
>> |----------operand: match(1), 1
>> |------------simplify_0, 0
>>
>> that is, I wonder where the extra "true" comes from.
> Thanks, fixed it in the current patch.
Thanks.
>>
>>
>> For
>>
>> (match_and_simplify
>> (MINUS_EXPR @2 (PLUS_EXPR@2 @0 @1))
>> @1)
>>
>> I get
>>
>> root, 1
>> |--operand: MINUS_EXPR, 1
>> |----operand: true, 1
>> |------operand: match(1), 1
>> |--------operand: PLUS_EXPR, 1
>> |----------operand: true, 1
>> |------------operand: true, 1
>> |--------------simplify_0, 0
>>
>> which looks good to me.
>>
>> There is still a fallthru for all match failures but the DT should ensure
>> that once any of the checks is false we can terminate - that is,
>> we never have to backtrack. Sth simple like
>>
>> --- genmatch.c.orig 2014-06-16 12:57:38.401890454 +0200
>> +++ genmatch.c 2014-06-16 12:58:03.451888730 +0200
>> @@ -816,6 +816,7 @@
>> unsigned i;
>> for (i = 0; i < kids.length (); ++i)
>> kids[i]->gen_gimple (f);
>> + fprintf (f, "return false;\n");
>>
>>
>> for (i = 0; i < n_braces; ++i)
>> fprintf (f, "}\n");
>>
>> So overall I think we are ok sofar and don't need major changes in
>> the algorithm.
>>
>> I'd say add the missing call support and we're good to go ripping out
>> the non-decision tree path.
>>
>> I'm happy to do some of the refactoring that I'd like to see myself
>> so you can concentrate on pattern implementing for phase 2. But
>> feel free to do some of it yourself.
>>
>> > Small point: I was wondering if it's a good idea to slightly change
>> > the syntax of pattern to sth like:
>> > match-expression -> transform ?
>> > eg:
>> > (minus (plus @0 @1) @1) -> @0
>> > Looks smaller -:)
>>
>> Well, I suppose we stay with what we have here.
> The attached patch, adds support for built-in functions, and fixes
> insertion bug in decision tree.
> The insertion in decision tree is carried out during preorder traversal
> of AST (insert_operand), so it avoids generating preorder traversal in
> vector (removed walk_operand_preorder and
> lower_capture). For now have put (parent, pos, preorder_level) in
> separate struct operand_info, and added instance
> of this struct to operand (struct operand_info opinfo). operand_info
> is computed during preorder traversal
> (insert_operand), so parsing routines are not concerned with it.
> Eventually we should probably move
> matching code on decision tree nodes. For convenience of tracking
> patterns, I have numbered them in match.pd.
Ok.
> * Testing
> Total patterns in match.pd - 58
> Total test cases: 4 (match-1.c), 32 (match-decision-tree.c), match-2.c
> is screwed.
How is it screwed? I see it all pass ...
> Out of 22 remaining patterns:
> Not supported yet (require GENERIC support or special handling): 31
> (convert), 33, 34, 35 (realpart/imagpart), 37 (cond)
> Not able to write test-cases: 2, 16, 31, 38
Sth like
char *foo (char *p)
{
int i = 0;
return p + i;
}
for 2) and using -fdump-tree-ccp1-details and scanning the
ccp1 dump for "Match-and-simplified definition of _4 to p_3(D)"
(ok, that's a quite non-informative dump message and we should
improve it ... ok, changed now to "Match-and-simplified p_3(D) + _2 to p_3(D)")
16) is expected (it would be possible to write a testcase but I'm not sure
we want to retain that pattern). 31) has a testcases in gcc.dg/pr58742-[123].c
At some point (well, maybe now ...) we want to remove those patterns
we implemented in match.pd from the manual code in tree-ssa-forwprop.c
so we don't see "false" passing of testcases written for them.
For 38) I have no idea how to get a FMA_EXPR with integer types ... probably
the pattern (and the corresponding code in fold-const.c) is "dead".
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
>> >>>>>>
>> >>
>> >>
