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 Thu, Jun 12, 2014 at 4:26 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> 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.
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

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


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