On Mon, Jun 16, 2014 at 1:07 AM, Prathamesh Kulkarni
<bilbotheelffri...@gmail.com> wrote:
> On Sat, Jun 14, 2014 at 12:43 PM, Richard Biener
> <richard.guent...@gmail.com> wrote:
> I have attached patch that tries to implement decision tree using the
> above algorithm.
> (haven't done for built-in function yet, but that would be similar to
> expr, so i guess no new issues may come up
> for that).
Great.
> * AST representation
> Added two more classes to AST - true_operand and match_operand to
> represent "true" and "match" operands
> respectively. captures are built during parsing, and are "lowered" to
> either true_operand or match_operand
> while inserting AST operands in decision tree (lower_capture).
Hmm, ok. I'd have made them decision tree node classes instead,
but it's a matter of taste I guess.
+ // or maybe keep a parallel bool indexes_empty array instead of
using capture_max to denote "not seen" ?
+ for (unsigned i = 0; i < capture_max; ++i)
+ indexes[i] = level_max;
using a special value is fine.
> * Mapping capture index to preorder level
> dt_simplify::indexes (unsigned *indexes) provides mapping from capture
> index -> level.
> eg: indexes[1] = 2 represent @1 is at level 2 in preorder traversal of AST.
>
> * true_operand is always placed as last child of the decision tree
> node during insertion (dt_node::append_node),
> since we want to process that last (if all other decisions fail).
right.
> * Code gen
> Unfortunately, the patch still contains hacks for code-gen.
> One such hack is adding three fields - (parent, preorder_level, pos) to
> operand.
> They should really be part of decision tree, but since code-gen happens off
> AST,
> I needed to place them there.
> For removing that, I am thinking to put information required for
> code-gen in another struct (say operand_info?)
> struct operand_info
> {
> operand *op;
> unsigned pos;
> operand *parent;
> unsigned preorder_level;
> };
Eventually you can just pass the info to the code-generators as extra
arguments? That is, I would get rid of the AST methods for generating
the matching code and just do everything in the DT traversal. That is,
find a better abstraction here.
> a) The metadata of operand (pos, parent, preorder_level) can be
> computed during preorder_traversal
> in walk_operand_preorder.
> b) Stick operand_info into decision tree (dt_operand) instead of operand.
> Is that fine ?
Yes, that would work, but as code-gen off the DT should be quite
simple I'd rather not complicate things with too much C++ abstraction
(yeah, it's probably my fault to introduce it in the first place).
> Code-gen for operands is slightly changed.
> the temporary is created at expression's operand node rather than at
> the expression's node itself.
> Each operand knows it's name.
>
> It's name is computed as follows (dt_operand::gen_gimple):
> opname = op<pos> (if operand's parent is root).
> or opname = o<preorder level of parent node> if operand's parent is
> true_operand or match_operand
> or opname = gimple_assign_rhs <pos+1>(def_stmt<preorder level of
> parent node>); // if operand's parent is non-root expr
> for built-in functions it would be:
> or opname = gimple_call_arg (def_stmt<preorder level of parent node>, <pos>);
Hmm, in code-gen I see
if (code == MINUS_EXPR)
{
{
tree o1 = op0;
if (TREE_CODE (o1) == SSA_NAME)
{
gimple def_stmt1 = SSA_NAME_DEF_STMT (o1);
if (is_gimple_assign (def_stmt1) &&
gimple_assign_rhs_code (def_stmt1) == PLUS_EXPR)
{
...
}
}
}
{
tree o1 = op0;
if (TREE_CODE (o1) == SSA_NAME)
{
gimple def_stmt1 = SSA_NAME_DEF_STMT (o1);
if (is_gimple_assign (def_stmt1) &&
gimple_assign_rhs_code (def_stmt1) == MINUS_EXPR)
{
...
for the DT part
root, 2
|--operand: MINUS_EXPR, 2
|----operand: PLUS_EXPR, 1
...
|----operand: MINUS_EXPR, 1
...
but I would have expected the preamble for the inner
PLUS_EXPR/MINUS_EXPR check to be unified. Thus
if (code == MINUS_EXPR)
{
tree o1 = op0;
if (TREE_CODE (op1) == SSA_NAME)
{
gimple def_stmt1 = SSA_NAME_DEF_STMT (o1);
if (is_gimple_assign (def_stmt1))
{
if (gimple_assign_rhs_code (def_stmt1) == PLUS_EXPR)
{
...
}
else if (gimple_assign_rhs_code (def_stmt) == MINUS_EXPR)
{
...
}
That means a better factoring of code-generation would be necessary,
with possibly sorting the kids array after operand kind.
> * Added do_valueize () in gimple-match-head.c. the generated code
> calls do_valueize to valueize theopereand.
> This make code-gen simpler (no goto).
Good.
> Example:
> for the pattern:
> (match_and_simplify
> (minus (plus @0 @1) @1)
> @0)
>
> it produces following code (literally taken from gimple-match.c after
> running thru indent):
> http://pastebin.com/EaFHZMAF
>
> For non-matching captures (capt->what->type == operand::OP_EXPR), I
> tested with few
> bogus patterns, unfortunately I don't know how to write test-cases for
> these patterns present in match.pd
> involving non-matching captures:
>
> /* The following is simplification done by gimple_fold_stmt_to_constant_1
> to aid propagation engines, producing is_gimple_min_invariants from
> invariant_addr + cst. It may not be generally wanted
> (builtin-object-size) and thus may want to be restricted to 'simple'
> forms like &mem-ref or &decl. */
> (match_and_simplify
> (pointer_plus (addr@2 @0) INTEGER_CST_P@1)
> if (is_gimple_min_invariant (@2))
> {
> HOST_WIDE_INT off;
> tree base = get_addr_base_and_unit_offset (@0, &off);
> off += tree_to_uhwi (@1);
> /* Now with that we should be able to simply write
> (addr (mem_ref (addr @base) (plus @off @1))) */
> build1 (ADDR_EXPR, type,
> build2 (MEM_REF, TREE_TYPE (TREE_TYPE (@2)),
> build_fold_addr_expr (base),
> build_int_cst (ptr_type_node, off)));
> })
>
>
> * 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.
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.
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.
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
>>>>>>
>>
>>
