This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [GSoC] decision tree first steps


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]