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 Mon, Jun 23, 2014 at 3:01 PM, Prathamesh Kulkarni
<bilbotheelffriend@gmail.com> wrote:
> On Mon, Jun 23, 2014 at 5:58 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Mon, Jun 23, 2014 at 1:51 PM, Prathamesh Kulkarni
>> <bilbotheelffriend@gmail.com> wrote:
>>> On Mon, Jun 23, 2014 at 3:38 PM, Richard Biener
>>> <richard.guenther@gmail.com> wrote:
>>>> On Mon, Jun 23, 2014 at 10:26 AM, Prathamesh Kulkarni
>>>> <bilbotheelffriend@gmail.com> wrote:
>>>>> On Thu, Jun 19, 2014 at 7:53 PM, Prathamesh Kulkarni
>>>>> <bilbotheelffriend@gmail.com> wrote:
>>>>>> On Thu, Jun 19, 2014 at 4:12 PM, Prathamesh Kulkarni
>>>>>> <bilbotheelffriend@gmail.com> wrote:
>>>>>>> On Thu, Jun 19, 2014 at 2:37 PM, Prathamesh Kulkarni
>>>>>>> <bilbotheelffriend@gmail.com> wrote:
>>>>
>>>> Replying to the last mail in the thread.
>>>>
>>>>>>>> The attached patch separates decision tree from AST, (removes the
>>>>>>>> "parent bug") and attempts to
>>>>>>>> add support for special case patterns requiring GENERIC (however it
>>>>>>>> fails one test in match-1.c, I am looking
>>>>>>>> into that). Code-gen for matching is off the decision tree and
>>>>>>>> code-gen for transform is off the AST.
>>>>>>>>
>>>>>>>> * Representation of decision tree
>>>>>>>> dt_operand is used for representing AST operand / true / match in the
>>>>>>>> decision tree,
>>>>>>>> dt_operand::parent points to the decision tree node, the AST parent is
>>>>>>>> mapped to, not the pre-order predecessor.
>>>>>>>> dt_operand::pos gives the operand number (0th operand, 1st operand,
>>>>>>>> etc. of parent etc.)
>>>>>>>> I have also clubbed true and match in the same class, because true
>>>>>>>> does not require additional fields,
>>>>>>>> and match has only one additional field (unsigned m_level).
>>>>>>>>
>>>>>>>> For the following pairs of (bogus) patterns:
>>>>>>>> (plus @0 (bit_not@2 @1))
>>>>>>>> (plus @1 (bit_not@3 @0))
>>>>>>>>
>>>>>>>> It builds following decision tree:
>>>>>>>> (type, address, level, n_kids)
>>>>>>>>
>>>>>>>> root (0x1513550), 0, 1
>>>>>>>> |--PLUS_EXPR (0x1502370), 1, 1
>>>>>>>> |----true (0x15023f0), 2, 1
>>>>>>>> |------BIT_NOT_EXPR (0x1502470), 3, 1
>>>>>>>> |--------true (0x15024f0), 4, 2
>>>>>>>> |----------simplify_0 { 2, 4, 3, 4294967295,  }  (0x1512540), 5, 0
>>>>>>>> |----------simplify_1 { 4, 2, 4294967295, 3,  }  (0x15125c0), 5, 0
>>>>>>>>
>>>>>>>> and for the following pairs of (bogus) patterns:
>>>>>>>> (plus (minus@0 @1 @2) @3)
>>>>>>>> (plus (minus @0 @1) @2)
>>>>>>>>
>>>>>>>> It builds following tree:
>>>>>>>> root (0x10e2520), 0, 1
>>>>>>>> |--PLUS_EXPR (0x10d1370), 1, 1
>>>>>>>> |----MINUS_EXPR (0x10d13f0), 2, 1
>>>>>>>> |------true (0x10d1470), 3, 1
>>>>>>>> |--------true (0x10d14f0), 4, 1
>>>>>>>> |----------true (0x10e1540), 5, 2
>>>>>>>> |------------simplify_0 { 2, 3, 4, 5,  }  (0x10e15c0), 6, 0
>>>>>>>> |------------simplify_1 { 3, 4, 5, 4294967295,  }  (0x10e1640), 6, 0
>>>>>>>>
>>>>>>>> Is that correct ?
>>>>
>>>> Yes, that looks correct.
>>>>
>>>>>>>> * Code-gen
>>>>>>>> The code-gen is mostly same, with following changes:
>>>>>>>>
>>>>>>>> a) Generation of expressions:
>>>>>>>> At expr-node, the children are immediately assigned in temporaries
>>>>>>>> (t0, t1 ,...),
>>>>>>>> and when we come at child node, the temporary is assigned to child
>>>>>>>> node (o<level> = t<count>).
>>>>>>>> Temporary names are stored in dt_operand::temps vector.
>>>>>>>>
>>>>>>>> b) Is the following condition correct  (considering for convert) ?:
>>>>>>>>
>>>>>>>> if (is_gimple_assign (def_stmt) &&
>>>>>>>>     (gimple_assign_rhs_code (def_stmt) == <expr-code>
>>>>>>>>     || CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))))
>>>>>>>>  {
>>>>>>>>      // generated code for operands
>>>>>>>>  }
>>>>>>> oops, that's only for CONVERT_EXPR and NOP_EXPR.
>>>>>>> Fixed in the current patch
>>>>
>>>> Looking at dt8.patch it still seems wrong:
>>>>
>>>> +  if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR)
>>>> +    fprintf (f, "if (is_gimple_assign (def_stmt) &&\n"
>>>> +                "   (gimple_assign_rhs_code (def_stmt) == %s\n"
>>>> +               "   || CONVERT_EXPR_CODE_P (gimple_assign_rhs_code
>>>> (def_stmt))))\n", op_id->id);
>>>>
>>>> should be simply generate
>>>>
>>>>   if (is_gimple_assign (def_stmt) && CONVERT_EXPR_CODE_P
>>>> (gimple_assign_rhs_code (def_stmt)))
>>>>
>>>> that is, the == %s check is superfluous.
>>> Thanks, removed it.
>>>>
>>>>>> This patch fixes some more mistakes of the previous patch, and removes
>>>>>> .gen_gimple_match functions.
>>>>
>>>> Good.  Btw, the patch doesn't apply on the unpatched svn branch for me
>>>> (maybe because I applied the commutative patch with some adjustments).
>>>> Can you re-diff it for me so I can apply it?
>>>>
>>>>>> It now passes all tests from match-1.c
>>>>>> The test-case was failing because I didn't generate valueize code correctly.
>>>>>> It should have been:
>>>>>> if ((t<count> = do_valueize (valueize, t<count>)) != 0)
>>>>>> and the code getting generated was:
>>>>>> if (do_valueize (valueize, t<count>))
>>>>>>
>>>>>> This patch supports all the patterns in match.pd. What changes would I
>>>>>> need to make to make it a commit-ready patch ?
>>>>
>>>> I'm looking through the patch right now.
>>>>
>>>>> Added line directives in this patch.
>>>>> I am not sure where to output line directives for match operands
>>>>> since, they are interleaved in the decision tree.
>>>>> I put line directives of respecitve patterns,on top of
>>>>> if (code == <expr-code>), for all patterns having root as <expr-code>
>>>>
>>>> I think the match part cannot be easily annotated with line-directives
>>>> (as you found out).  I'd simply not emit any - it should be easy enough
>>>> to back-track from the ifexpr and code-gen line-directives.
>>>> So simply remove them again.
>>> Removed.
>>>>
>>>> @@ -29,7 +29,8 @@ along with GCC; see the file COPYING3.
>>>>  #include "hashtab.h"
>>>>  #include "hash-table.h"
>>>>  #include "vec.h"
>>>> -
>>>> +#include <stdlib.h>
>>>> +#include <limits.h>
>>>>
>>>> those headers should already be included via system.h (in general
>>>> system headers need to be included by system.h).
>>> Removed.
>>>>
>>>> Otherwise the patch looks good to commit.
>>>>
>>>> So please re-diff it for me (you can include the capture_max and
>>>> checking patch if it's inconvenient to send without it).
>>>>
>>>> Btw, is your copyright assignment processed?
>>> Yes.
>>
>> Great.
>>
>>> I have kept .gen_gimple_match () functions for now in this patch.
>>> I am not sure how to write the Change-Log for structs. Is the following fine ?
>>>
>>> * genmatch.c (print_operand): Add additional default argument bool
>>> flattened = false
>>>     (cmp_operand): New function to compare operands.
>>>     (dt_node): New struct.
>>>     (dt_operand): New struct.
>>>     (dt_simplify): New struct.
>>>     (decision_tree): New struct.
>>>     (write_fn_prototype): New function to write
>>> gimple_match_and_simplify prototype.
>>>
>>> * gimple-match-head.c (do_valueize): New function.
>>
>> Looks good.
>>
>>> I would like to extend phase-1 upto 30th June, and attempt to have
>>> these tasks completed
>>> before beginning phase-2:
>>>
>>> a) Decision tree to represent patterns
>>> mostly done
>>
>> Can you shortly explain what is missing?
> Oh I meant re-factoring/formatting changes for
> decision-tree and gimple match-and-simplify code-gen.
>>
>>> b) GIMPLE match-and-simplify code generation
>>> mostly done
>>
>> Likewise?
>>
>>> c) GENERIC match-and-simplify code-generation
>>> We have support for generating GENERIC matching code
>>> (dt_operand::gen_generic_expr),
>>> but not for generating GENERIC transforms.
>>
>> Yep.  Most of the changes required for doing this on GIMPLE where
>> required is in maybe_push_res_to_seq (if we ever create a REALPART
>> or IMAGPART or BIT_FIELD_REF in the transform stage - the COND_EXPR
>> handling should already work, just not optimally).
>>
>> If you are talking about full GENERIC support for fold-const.c replacement
>> then this requires some more work and I'd like to at least implement the
>> API side with some quick draft for genmatch.c
> Yeah I was talking about full GENERIC support, although having GENERIC support
> for the four cases (realpart/imagpart/view_convert/bit_field_ref),
> would be nice first.
> Sorry to be blunt, but how do we um start ?
> I guess the generated generic_match_and_simplify () functions would
> have prototype identical to
> fold_unary, fold_binary ?
> So we start by generating generic_match_and_simplify prototype
> (similar to gimple_match_and_simplify in write_fn_prototype)
> and by generating GENERIC simplification by adding .gen_generic_match
> () on AST operands ?
> code-gen for captures, c_expr would remain the same, I guess only expr
> code-gen would be different.

Yes, prototypes would be the same as fold_unary/fold_binary.  We'd have
no valueize callback and no def-stmt walking.  As for the code-gen
part we'd add gen_generic_transform methods and likely only expr
code-gen will be different.

I will have a look at this tomorrow and write a quick prototype (unless
you beat me on that).  Final expression building will need to use
the build[123] functions but we want to re-simplify by recursing to
ourselves similar to the GIMPLE part.

Btw, I've committed the DT patch and removed the non-DT code
as followup now.  Both committed.

Richard.


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