On June 13, 2014 11:48:13 PM CEST, Prathamesh Kulkarni
<bilbotheelffri...@gmail.com> wrote:
>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
You could also do
Plus - true - match(1) - negate - true
To avoid doing two things in one node.
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
>>>>
