[GSoC] decision tree first steps
Prathamesh Kulkarni
bilbotheelffriend@gmail.com
Mon Jun 16 22:21:00 GMT 2014
On Mon, Jun 16, 2014 at 4:45 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Mon, Jun 16, 2014 at 1:07 AM, Prathamesh Kulkarni
> <bilbotheelffriend@gmail.com> wrote:
> > On Sat, Jun 14, 2014 at 12:43 PM, Richard Biener
> > <richard.guenther@gmail.com> wrote:
> > I have attached patch that tries to implement decision tree using the
> > above algorithm.
> > (haven't done for built-in function yet, but that would be similar to
> > expr, so i guess no new issues may come up
> > for that).
>
> Great.
>
> > * AST representation
> > Added two more classes to AST - true_operand and match_operand to
> > represent "true" and "match" operands
> > respectively. captures are built during parsing, and are "lowered" to
> > either true_operand or match_operand
> > while inserting AST operands in decision tree (lower_capture).
>
> Hmm, ok. I'd have made them decision tree node classes instead,
> but it's a matter of taste I guess.
>
> + // or maybe keep a parallel bool indexes_empty array instead of
> using capture_max to denote "not seen" ?
> + for (unsigned i = 0; i < capture_max; ++i)
> + indexes[i] = level_max;
>
> using a special value is fine.
>
> > * Mapping capture index to preorder level
> > dt_simplify::indexes (unsigned *indexes) provides mapping from capture
> > index -> level.
> > eg: indexes[1] = 2 represent @1 is at level 2 in preorder traversal of AST.
> >
> > * true_operand is always placed as last child of the decision tree
> > node during insertion (dt_node::append_node),
> > since we want to process that last (if all other decisions fail).
>
> right.
>
> > * Code gen
> > Unfortunately, the patch still contains hacks for code-gen.
> > One such hack is adding three fields - (parent, preorder_level, pos) to operand.
> > They should really be part of decision tree, but since code-gen happens off AST,
> > I needed to place them there.
> > For removing that, I am thinking to put information required for
> > code-gen in another struct (say operand_info?)
> > struct operand_info
> > {
> > operand *op;
> > unsigned pos;
> > operand *parent;
> > unsigned preorder_level;
> > };
>
> Eventually you can just pass the info to the code-generators as extra
> arguments? That is, I would get rid of the AST methods for generating
> the matching code and just do everything in the DT traversal. That is,
> find a better abstraction here.
>
> > a) The metadata of operand (pos, parent, preorder_level) can be
> > computed during preorder_traversal
> > in walk_operand_preorder.
> > b) Stick operand_info into decision tree (dt_operand) instead of operand.
> > Is that fine ?
>
> Yes, that would work, but as code-gen off the DT should be quite
> simple I'd rather not complicate things with too much C++ abstraction
> (yeah, it's probably my fault to introduce it in the first place).
>
> > Code-gen for operands is slightly changed.
> > the temporary is created at expression's operand node rather than at
> > the expression's node itself.
> > Each operand knows it's name.
> >
> > It's name is computed as follows (dt_operand::gen_gimple):
> > opname = op<pos> (if operand's parent is root).
> > or opname = o<preorder level of parent node> if operand's parent is
> > true_operand or match_operand
> > or opname = gimple_assign_rhs <pos+1>(def_stmt<preorder level of
> > parent node>); // if operand's parent is non-root expr
> > for built-in functions it would be:
> > or opname = gimple_call_arg (def_stmt<preorder level of parent node>, <pos>);
>
> Hmm, in code-gen I see
>
> if (code == MINUS_EXPR)
> {
> {
> tree o1 = op0;
> if (TREE_CODE (o1) == SSA_NAME)
> {
> gimple def_stmt1 = SSA_NAME_DEF_STMT (o1);
> if (is_gimple_assign (def_stmt1) &&
> gimple_assign_rhs_code (def_stmt1) == PLUS_EXPR)
> {
> ...
> }
> }
> }
> {
> tree o1 = op0;
> if (TREE_CODE (o1) == SSA_NAME)
> {
> gimple def_stmt1 = SSA_NAME_DEF_STMT (o1);
> if (is_gimple_assign (def_stmt1) &&
> gimple_assign_rhs_code (def_stmt1) == MINUS_EXPR)
> {
> ...
>
> for the DT part
>
> root, 2
> |--operand: MINUS_EXPR, 2
> |----operand: PLUS_EXPR, 1
> ...
> |----operand: MINUS_EXPR, 1
> ...
>
> but I would have expected the preamble for the inner
> PLUS_EXPR/MINUS_EXPR check to be unified. Thus
>
> if (code == MINUS_EXPR)
> {
> tree o1 = op0;
> if (TREE_CODE (op1) == SSA_NAME)
> {
> gimple def_stmt1 = SSA_NAME_DEF_STMT (o1);
> if (is_gimple_assign (def_stmt1))
> {
> if (gimple_assign_rhs_code (def_stmt1) == PLUS_EXPR)
> {
> ...
> }
> else if (gimple_assign_rhs_code (def_stmt) == MINUS_EXPR)
> {
> ...
> }
>
> That means a better factoring of code-generation would be necessary,
> with possibly sorting the kids array after operand kind.
>
>
> > * Added do_valueize () in gimple-match-head.c. the generated code
> > calls do_valueize to valueize theopereand.
> > This make code-gen simpler (no goto).
>
> Good.
>
> > Example:
> > for the pattern:
> > (match_and_simplify
> > (minus (plus @0 @1) @1)
> > @0)
> >
> > it produces following code (literally taken from gimple-match.c after
> > running thru indent):
> > http://pastebin.com/EaFHZMAF
> >
> > For non-matching captures (capt->what->type == operand::OP_EXPR), I
> > tested with few
> > bogus patterns, unfortunately I don't know how to write test-cases for
> > these patterns present in match.pd
> > involving non-matching captures:
> >
> > /* The following is simplification done by gimple_fold_stmt_to_constant_1
> > to aid propagation engines, producing is_gimple_min_invariants from
> > invariant_addr + cst. It may not be generally wanted
> > (builtin-object-size) and thus may want to be restricted to 'simple'
> > forms like &mem-ref or &decl. */
> > (match_and_simplify
> > (pointer_plus (addr@2 @0) INTEGER_CST_P@1)
> > if (is_gimple_min_invariant (@2))
> > {
> > HOST_WIDE_INT off;
> > tree base = get_addr_base_and_unit_offset (@0, &off);
> > off += tree_to_uhwi (@1);
> > /* Now with that we should be able to simply write
> > (addr (mem_ref (addr @base) (plus @off @1))) */
> > build1 (ADDR_EXPR, type,
> > build2 (MEM_REF, TREE_TYPE (TREE_TYPE (@2)),
> > build_fold_addr_expr (base),
> > build_int_cst (ptr_type_node, off)));
> > })
> >
> >
> > * Patterns requiring GENERIC support like cond_expr
> > I am not sure about how to handle these patterns. I was thinking about
> > handling them after we have
> > GENERIC code generation in place.
>
> Yeah, though handling GENERIC for matching is as simple as
> emitting the code check twice, the 2nd check off the an else
> from the if (TREE_CODE (op) == SSA_NAME). That is,
> arrange for expr::gen_gimple_match_dt to emit
>
> if (TREE_CODE (...) == SSA_NAME)
> {
> gimple def_stmt = SSA_NAME_DEF_STMT (...);
> if (is_gimple_assign (def_stmt) && gimple_assign_rhs_code
> (def_stmt) == <code>)
> {
> ....
> }
> else (TREE_CODE (...) == <code>)
> {
> ....
> }
>
> which would require some refactoring in the generator. As for refactoring
> it I'd not hook the gen_gimple_match_dt off the AST operands but
> inline it in the decision tree traversal routine - that also makes the
> commoning above easier.
Thanks, I shall get started on this.
>
> Btw, I checked what we generate for (bogus)
>
> (match_and_simplify
> (MINUS_EXPR (PLUS_EXPR@2 @0 @1) @2)
> @1)
>
> and the DT looks like
>
> root, 1
> |--operand: MINUS_EXPR, 1
> |----operand: true, 1
> |------operand: PLUS_EXPR, 1
> |--------operand: true, 1
> |----------operand: true, 1
> |------------operand: match(1), 1
> |--------------simplify_0, 0
>
> though I expected
>
> root, 1
> |--operand: MINUS_EXPR, 1
> |----operand: PLUS_EXPR, 1
> |------operand: true, 1
> |--------operand: true, 1
> |----------operand: match(1), 1
> |------------simplify_0, 0
>
> that is, I wonder where the extra "true" comes from.
Thanks, fixed it in the current patch.
>
>
> For
>
> (match_and_simplify
> (MINUS_EXPR @2 (PLUS_EXPR@2 @0 @1))
> @1)
>
> I get
>
> root, 1
> |--operand: MINUS_EXPR, 1
> |----operand: true, 1
> |------operand: match(1), 1
> |--------operand: PLUS_EXPR, 1
> |----------operand: true, 1
> |------------operand: true, 1
> |--------------simplify_0, 0
>
> which looks good to me.
>
> There is still a fallthru for all match failures but the DT should ensure
> that once any of the checks is false we can terminate - that is,
> we never have to backtrack. Sth simple like
>
> --- genmatch.c.orig 2014-06-16 12:57:38.401890454 +0200
> +++ genmatch.c 2014-06-16 12:58:03.451888730 +0200
> @@ -816,6 +816,7 @@
> unsigned i;
> for (i = 0; i < kids.length (); ++i)
> kids[i]->gen_gimple (f);
> + fprintf (f, "return false;\n");
>
>
> for (i = 0; i < n_braces; ++i)
> fprintf (f, "}\n");
>
> So overall I think we are ok sofar and don't need major changes in
> the algorithm.
>
> I'd say add the missing call support and we're good to go ripping out
> the non-decision tree path.
>
> I'm happy to do some of the refactoring that I'd like to see myself
> so you can concentrate on pattern implementing for phase 2. But
> feel free to do some of it yourself.
>
> > Small point: I was wondering if it's a good idea to slightly change
> > the syntax of pattern to sth like:
> > match-expression -> transform ?
> > eg:
> > (minus (plus @0 @1) @1) -> @0
> > Looks smaller -:)
>
> Well, I suppose we stay with what we have here.
The attached patch, adds support for built-in functions, and fixes
insertion bug in decision tree.
The insertion in decision tree is carried out during preorder traversal
of AST (insert_operand), so it avoids generating preorder traversal in
vector (removed walk_operand_preorder and
lower_capture). For now have put (parent, pos, preorder_level) in
separate struct operand_info, and added instance
of this struct to operand (struct operand_info opinfo). operand_info
is computed during preorder traversal
(insert_operand), so parsing routines are not concerned with it.
Eventually we should probably move
matching code on decision tree nodes. For convenience of tracking
patterns, I have numbered them in match.pd.
* Testing
Total patterns in match.pd - 58
Total test cases: 4 (match-1.c), 32 (match-decision-tree.c), match-2.c
is screwed.
Out of 22 remaining patterns:
Not supported yet (require GENERIC support or special handling): 31
(convert), 33, 34, 35 (realpart/imagpart), 37 (cond)
Not able to write test-cases: 2, 16, 31, 38
I will add test-cases for remaining patterns shortly.
Thanks and Regards,
Prathamesh
>
> Thanks,
> Richard.
>
> > Thanks and Regards
> > Prathamesh
> >>
> >> Richard.
> >>
> >>>and for the commutative variant:
> >>>(plus (negate@0 @1) @0) S
> >>>
> >>>the decision tree would be the following: ?
> >>>plus - negate - true - true - match (3) - simplify
> >>>
> >>>Thanks and Regards,
> >>>Prathamesh
> >>>>
> >>>> Richard.
> >>>>
> >>>>>> Richard.
> >>>>>>
> >>>>>>>> There are also opportunities to optimize the generated code, but
> >>>>>>>> basic correctness first I guess.
> >>>>>>>>
> >>>>>>>> I suppose we have to work a bit on the capture stuff.
> >>>>>>>>
> >>>>>>>> Btw, you can easily play with the code generator by doing inside
> >>>>>>>> the gcc build directory
> >>>>>>>>
> >>>>>>>> obj/gcc> build/genmatch test.pd > test.c
> >>>>>>>>
> >>>>>>>> with a small test.pd. I used the following for the above
> >>>examples:
> >>>>>>>>
> >>>>>>>> (match_and_simplify
> >>>>>>>> (MINUS_EXPR (PLUS_EXPR @0 @1) @0)
> >>>>>>>> @1)
> >>>>>>>> (match_and_simplify
> >>>>>>>> (MINUS_EXPR (PLUS_EXPR @1 @0) @0)
> >>>>>>>> @1)
> >>>>>>
> >>>>>>>> Richard.
> >>>>>>>>
> >>>>>>>>>> I will change this to have capture per pattern
> >>>>>>>>>> tree captures1[4] = {}; // for pattern-1
> >>>>>>>>>> tree captures2[4] = {};
> >>>>>>>>>
> >>>>>>>>> Hmm, is this the matching captures issue I mentioned? Btw, I
> >>>see
> >>>>>>>>> you do
> >>>>>>>>>
> >>>>>>>>> +void
> >>>>>>>>> +walk_operand_preorder(vec<operand *>& operands, operand *op)
> >>>>>>>>> +{
> >>>>>>>>> + if (op->type == operand::OP_CAPTURE || op->type ==
> >>>>>>>>> operand::OP_PREDICATE || op->type == operand::OP_C_EXPR)
> >>>>>>>>> + {
> >>>>>>>>> + operands.safe_push (op);
> >>>>>>>>> + return;
> >>>>>>>>> + }
> >>>>>>>>>
> >>>>>>>>> but that leaves captured expressions as a single operand?
> >>>>>>>>>
> >>>>>>>>> (plus (minus@1 @2 @3) @2)
> >>>>>>>>>
> >>>>>>>>> would have a decision tree
> >>>>>>>>>
> >>>>>>>>> plus -> minus -> @2
> >>>>>>>>>
> >>>>>>>>> correct?
> >>>>>>>>>
> >>>>>>>>>> d) Matching multiple patterns.
> >>>>>>>>>> Code for patterns with same match, but different transforms is
> >>>>>>>>>> generated as follows:
> >>>>>>>>>> code for match operand.
> >>>>>>>>>> if (if-expr of pattern-1)
> >>>>>>>>>> {
> >>>>>>>>>> code for result of pattern-1
> >>>>>>>>>> return true;
> >>>>>>>>>> }
> >>>>>>>>>> if (if-expr of pattern-2)
> >>>>>>>>>> {
> >>>>>>>>>> code for result of pattern-2
> >>>>>>>>>> return true;
> >>>>>>>>>> }
> >>>>>>>>>
> >>>>>>>>> good.
> >>>>>>>>>
> >>>>>>>>>> ...
> >>>>>>>>>> Should we emit a warning for patterns that have same match
> >>>operand but
> >>>>>>>>>> no if-expr and no manual transform ?
> >>>>>>>>>>
> >>>>>>>>>> for eg:
> >>>>>>>>>> (match_and_simplify
> >>>>>>>>>> (plus (minus @0 @1) @1)
> >>>>>>>>>> @0
> >>>>>>>>>>
> >>>>>>>>>> (match_and_simplify
> >>>>>>>>>> (plus (minus @0 @1) @1)
> >>>>>>>>>> @1 // just for illustration
> >>>>>>>>>>
> >>>>>>>>>> Since the matching is ambiguous (same match, no if-expr, no
> >>>manual
> >>>>>>>>>> transform).
> >>>>>>>>>
> >>>>>>>>> Yeah, I suppose we should.
> >>>>>>>>>
> >>>>>>>>>> we are left to choose between result of pattern-1 and result of
> >>>>>>>>>> pattern-2.
> >>>>>>>>>> We can emit warning and choose result of pattern-1 (first-match
> >>>rule
> >>>>>>>>>> as in flex).
> >>>>>>>>>>
> >>>>>>>>>> e) Non-matching captures:
> >>>>>>>>>> Haven't thought about this yet.
> >>>>>>>>>>
> >>>>>>>>>> * Should we add "negative" predicates that match only if the
> >>>predicate
> >>>>>>>>>> fails ?
> >>>>>>>>>> for eg:
> >>>>>>>>>> (match_and_simplify
> >>>>>>>>>> trunc_mod integer_zerop@0 !integer_zerop)
> >>>>>>>>>> @0)
> >>>>>>>>>
> >>>>>>>>> well, there could simply be a integer_not_zerop predicate.
> >>>>>>>>>
> >>>>>>>>>> * Testing
> >>>>>>>>>> Sorry to bring this up again, but I am still not clear what
> >>>regex to
> >>>>>>>>>> write in scan-tree-dump.
> >>>>>>>>>>
> >>>>>>>>>> Suppose we have these two patterns in match.pd:
> >>>>>>>>>> /* (x + y) - y -> x */
> >>>>>>>>>> (match_and_simplify
> >>>>>>>>>> (minus (plus @0 @1) @1)
> >>>>>>>>>> @0)
> >>>>>>>>>>
> >>>>>>>>>> /* (x - y) + y -> x */
> >>>>>>>>>> (match_and_simplify
> >>>>>>>>>> (plus (minus @0 @1) @1)
> >>>>>>>>>> @0)
> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*=
> >>>>>>>>>> x_\\d\+\\(D\\)"
> >>>>>>>>>>
> >>>>>>>>>> I have following test-cases:
> >>>>>>>>>> int f1(int x, int y)
> >>>>>>>>>> {
> >>>>>>>>>> int t1 = x + y;
> >>>>>>>>>> return t1 - y;
> >>>>>>>>>> }
> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*=
> >>>>>>>>>> x_\\d\+\\(D\\)"
> >>>>>>>>>>
> >>>>>>>>>> int f2(int x, int y)
> >>>>>>>>>> {
> >>>>>>>>>> int t1 = x - y;
> >>>>>>>>>> return t1 + y;
> >>>>>>>>>> }
> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*=
> >>>>>>>>>> x_\\d\+\\(D\\)"
> >>>>>>>>>>
> >>>>>>>>>> both the test-cases have same regex.
> >>>>>>>>>> Tested in isolation f1 passes (first pattern if fired) and f2
> >>>fails
> >>>>>>>>>> (second pattern doesn't fire, it does after
> >>>>>>>>>> adding it's commutative variant, but that's irrelevant for this
> >>>case).
> >>>>>>>>>>
> >>>>>>>>>> However when both test-cases are put in one file both the test
> >>>cases
> >>>>>>>>>> PASS.
> >>>>>>>>>> I think that's because both of them have same regex:
> >>>\[^\n\r\]*=
> >>>>>>>>>> x_\\d\+\\(D\\)
> >>>>>>>>>> so in f1 and f2's regex both match the dump for f1 function in
> >>>>>>>>>> forwprop dump file:
> >>>>>>>>>> "gimple_match_and_simplified to \[^\n\r\]*= x_\\d\+\\(D\\)
> >>>>>>>>>>
> >>>>>>>>>> As a quick hack i rewrote f1 and f2 as:
> >>>>>>>>>> int f1(int x, int y)
> >>>>>>>>>> {
> >>>>>>>>>> int t1 = x + y;
> >>>>>>>>>> int f1_val = t1 - y;
> >>>>>>>>>> return f1_val;
> >>>>>>>>>> }
> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to f1_val_\\d\+ =
> >>>>>>>>>> x_\\d\+\\(D\\)"
> >>>>>>>>>>
> >>>>>>>>>> int f2(int x, int y)
> >>>>>>>>>> {
> >>>>>>>>>> int t1 = x - y;
> >>>>>>>>>> int f2_val = t1 + y;
> >>>>>>>>>> return f2_val;
> >>>>>>>>>> }
> >>>>>>>>>> scan-tree-dump "gimple_match_and_simplified to f2_val_\\d\+ =
> >>>>>>>>>> x_\\d\+\\(D\\)"
> >>>>>>>>>> so both f1 and f2's scan-tree-dump have different regexes.
> >>>>>>>>>> and f2's regex does not match dump of f1's function.
> >>>>>>>>>> This matches all patterns in match-decision-tree.c however this
> >>>is not
> >>>>>>>>>> ideal,
> >>>>>>>>>> since it does not check for matching dump across newlines.
> >>>>>>>>>> Could you suggest a better way ?
> >>>>>>>>>
> >>>>>>>>> There isn't a good better way (the others explicitely do _not_
> >>>match
> >>>>>>>>> against
> >>>>>>>>> a newline - see the ^ in the \[\] group). Well, apart from
> >>>splitting
> >>>>>>>>> the testcase
> >>>>>>>>> into multiple files of course.
> >>>>>>>>>
> >>>>>>>>> Richard.
> >>>>>>>>>
> >>>>>>>>>> Thanks and Regards,
> >>>>>>>>>> Prathamesh
> >>>>>>>>>>>
> >>>>>>>>>>> Thanks,
> >>>>>>>>>>> Richard.
> >>>>>>>>>>>
> >>>>>>>>>>>>> Thanks and Regards,
> >>>>>>>>>>>>> Prathamesh
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> Richard.
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> * Code generation.
> >>>>>>>>>>>>>>> Code shall be generated by walking the decision tree.
> >>>>>>>>>>>>>>> The way it's constructed, there's no difference between
> >>>code
> >>>>>>>>>>>>>>> generation
> >>>>>>>>>>>>>>> for "matching" and code generation for "transform". For
> >>>>>>>>>>>>>>> non-simplificaton
> >>>>>>>>>>>>>>> operands, "matching" code is generated, and for
> >>>"simplification"
> >>>>>>>>>>>>>>> operands,
> >>>>>>>>>>>>>>> "transform" code is generated. The tree shall be walked
> >>>twice,
> >>>>>>>>>>>>>>> once to generate GIMPLE code and second time for GENERIC.
> >>>>>>>>>>>>>>> For simplicity, I currently return false whenever there's
> >>>a fail
> >>>>>>>>>>>>>>> in match,
> >>>>>>>>>>>>>>> instead of trying to match the next pattern.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Code-gen for capture - same as capture::gen_gimple_match.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Code-gen for predicate - I haven't added support for
> >>>predicate
> >>>>>>>>>>>>>>> in
> >>>>>>>>>>>>>>> decision tree yet, but I guess that would be the same as
> >>>>>>>>>>>>>>> predicate::gen_gimple_match
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Code-gen for expr.
> >>>>>>>>>>>>>>> There are two types of code-gen for expr.
> >>>>>>>>>>>>>>> The patch generates following code:
> >>>>>>>>>>>>>>> Type 1 - expr is child of root node.
> >>>>>>>>>>>>>>> the only code that gets generated is (in
> >>>>>>>>>>>>>>> decision_tree::gen_gimple):
> >>>>>>>>>>>>>>> if (code == <expr code>)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> tree captures[4] = {}
> >>>>>>>>>>>>>>> <generated code for children>
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>> This is similar to generating matching code in
> >>>>>>>>>>>>>>> write_nary_simplifiers.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Type 2 - expr_1 is a child of another expr_0 node.
> >>>>>>>>>>>>>>> The code gets generated as follows (dt_expr::gen_gimple):
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> gimple def_stmt = SSA_NAME_DEF_STMT (op);
> >>>>>>>>>>>>>>> if (is_gimple_assign (def_stmt)
> >>>>>>>>>>>>>>> && gimple_assign_rhs_code (def_stmt) == <expr_1-code>)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> tree op = gimple_assign_rhs1 (def_stmt);
> >>>>>>>>>>>>>>> if (valueize && TREE_CODE (op) == SSA_NAME)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> op = valueize (op);
> >>>>>>>>>>>>>>> if (!op) return false;
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>> <code-gen for children of expr_1 node>
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Example:
> >>>>>>>>>>>>>>> (negate (negate @0))
> >>>>>>>>>>>>>>> S1
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> (negate (bit_not @0))
> >>>>>>>>>>>>>>> S2
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> decision tree:
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> dummy/root
> >>>>>>>>>>>>>>> |
> >>>>>>>>>>>>>>> NEGATE_EXPR
> >>>>>>>>>>>>>>> / \
> >>>>>>>>>>>>>>> BIT_NOT NEGATE_EXPR
> >>>>>>>>>>>>>>> | |
> >>>>>>>>>>>>>>> @0 @0
> >>>>>>>>>>>>>>> | |
> >>>>>>>>>>>>>>> S1 S2
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> // code-gen for NEGATE_EXPR (child of root):
> >>>>>>>>>>>>>>> if (code == NEGATE_EXPR)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> tree captures[4] = {};
> >>>>>>>>>>>>>>> // code gen for BIT_NOT_EXPR
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> gimple def_stmt = SSA_NAME_DEF_STMT (op0);
> >>>>>>>>>>>>>>> if (is_gimple_assign (def_stmt)
> >>>>>>>>>>>>>>> && gimple_assign_rhs_code (def_stmt) == BIT_NOT_EXPR)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> tree op = gimple_assign_rhs1 (def_stmt);
> >>>>>>>>>>>>>>> if (valueize && TREE_CODE (op) == SSA_NAME)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> op = valueize (op);
> >>>>>>>>>>>>>>> if (!op) return false;
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> // code-gen for @0, child of BIT_NOT_EXPR
> >>>>>>>>>>>>>>> if (!captures[0])
> >>>>>>>>>>>>>>> captures[0] = op;
> >>>>>>>>>>>>>>> else if (captures[0] != op)
> >>>>>>>>>>>>>>> return false;
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> // code-gen for S1, child of @0
> >>>>>>>>>>>>>>> < same as code generated by .gen_gimple_transform >
> >>>>>>>>>>>>>>> return true;
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>> // code gen for inner NEGATE_EXPR
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> gimple def_stmt = SSA_NAME_DEF_STMT (op0);
> >>>>>>>>>>>>>>> if (is_gimple_assign (def_stmt)
> >>>>>>>>>>>>>>> && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR)
> >>>>>>>>>>>>>>> <rest similar to the BIT_NOT case>
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> The following gets duplicated with the patch:
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> gimple_def_stmt = SSA_NAME_DEF_STMT (op0);
> >>>>>>>>>>>>>>> if (TREE_CODE (op0) != SSA_NAME)
> >>>>>>>>>>>>>>> return false;
> >>>>>>>>>>>>>>> if (is_gimple_assign (def_stmt)
> >>>>>>>>>>>>>>> && gimple_assign_rhs_code (def_stmt) == <expr-code>)
> >>>>>>>>>>>>>>> ...
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Improving code-gen for expr:
> >>>>>>>>>>>>>>> "gimple def_stmt = ..." and "if (TREE_CODE (op0)" get
> >>>duplicated,
> >>>>>>>>>>>>>>> while they could be factored out, similar to this:
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> gimple def_stmt = SSA_NAME_DEF_STMT (op0);
> >>>>>>>>>>>>>>> if (TREE_CODE (op0) != SSA_NAME)
> >>>>>>>>>>>>>>> return false;
> >>>>>>>>>>>>>>> if (!is_gimple_assign (def_stmt))
> >>>>>>>>>>>>>>> return false;
> >>>>>>>>>>>>>>> if (gimple_assign_rhs_code (def_stmt) == BIT_NOT_EXPR)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> // code-gen for BIT_NOT_EXPR subtree
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>> else if (gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR)
> >>>>>>>>>>>>>>> {
> >>>>>>>>>>>>>>> // code-gen for NEGATE_EXPR subtree
> >>>>>>>>>>>>>>> }
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> For factoring "gimple def_stmt ..." and "if (TREE_CODE
> >>>(op0) !=
> >>>>>>>>>>>>>>> SSA_NAME"
> >>>>>>>>>>>>>>> we could have that generated at the parent of expr's node
> >>>rather
> >>>>>>>>>>>>>>> than
> >>>>>>>>>>>>>>> at expr. However that would be incorrect for cases where
> >>>not all
> >>>>>>>>>>>>>>> children
> >>>>>>>>>>>>>>> of a node are expressions:
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Example:
> >>>>>>>>>>>>>>> // patterns only for illustration
> >>>>>>>>>>>>>>> (negate (bit_not @0))
> >>>>>>>>>>>>>>> (negate @0)
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> root
> >>>>>>>>>>>>>>> |
> >>>>>>>>>>>>>>> negate
> >>>>>>>>>>>>>>> / \
> >>>>>>>>>>>>>>> bit_not @0
> >>>>>>>>>>>>>>> |
> >>>>>>>>>>>>>>> @0
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> we cannot have the above code generated at negate,
> >>>>>>>>>>>>>>> since it's not applicable negate's 2nd child (@0).
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> This can be done by grouping together children that are
> >>>>>>>>>>>>>>> expressions.
> >>>>>>>>>>>>>>> However the patch does not do that.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> * Code-gen for simplification operand
> >>>>>>>>>>>>>>> This involves code-gen for ifexpr and result of pattern.
> >>>>>>>>>>>>>>> Calls gen_gimple_transform of ifexpr and result
> >>>>>>>>>>>>>>> (dt_simplify::gen_gimple)
> >>>>>>>>>>>>>>> So this is really code-gen off AST
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> Right (modulo replacing captures with their replacements).
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> * Matching multiple patterns
> >>>>>>>>>>>>>>> A pattern has following parts: match, ifexpr and result.
> >>>>>>>>>>>>>>> If pattern fails in match operand, I guess we can safely
> >>>return
> >>>>>>>>>>>>>>> false ?
> >>>>>>>>>>>>>>> We "club" together patterns that have same match operand,
> >>>>>>>>>>>>>>> and use goto, if one of them fails in their
> >>>(ifexpr/result) and
> >>>>>>>>>>>>>>> then goto the
> >>>>>>>>>>>>>>> (ifexpr/result) of the next operand.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Example:
> >>>>>>>>>>>>>>> /* x & 0 -> 0 */
> >>>>>>>>>>>>>>> (match_and_simplify
> >>>>>>>>>>>>>>> (bit_and @0 @1)
> >>>>>>>>>>>>>>> if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) && (@1 ==
> >>>>>>>>>>>>>>> integer_zero_node))
> >>>>>>>>>>>>>>> { integer_zero_node; })
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> /* x & -1 -> x */
> >>>>>>>>>>>>>>> (match_and_simplify
> >>>>>>>>>>>>>>> (bit_and @0 @1)
> >>>>>>>>>>>>>>> if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
> >>>>>>>>>>>>>>> && (@1 == integer_minus_one_node)
> >>>>>>>>>>>>>>> @0)
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> For both patterns match is same.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Decision Tree:
> >>>>>>>>>>>>>>> bit_and
> >>>>>>>>>>>>>>> / \
> >>>>>>>>>>>>>>> @0 @1
> >>>>>>>>>>>>>>> |
> >>>>>>>>>>>>>>> S1, S2
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> I think it's worth adding a diagnostic to genmach whenever
> >>>exactly
> >>>>>>>>>>>>>> same matches appear. But I'd say generally we'd support
> >>>this
> >>>>>>>>>>>>>> by testing the ifexpr of the next pattern.
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> S1 represents <ifexpr, result> of pattern-1, and S2
> >>>represents
> >>>>>>>>>>>>>>> <ifexpr, result>
> >>>>>>>>>>>>>>> of pattern-2 respectively.
> >>>>>>>>>>>>>>> S1, S2 would be stored as children of @1 (the last operand
> >>>of
> >>>>>>>>>>>>>>> n-ary operator),
> >>>>>>>>>>>>>>> in dt_operand::kids vector.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> The code would be generated as:
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> matching code.
> >>>>>>>>>>>>>>> if (! pattern-1 ifexpr condition)
> >>>>>>>>>>>>>>> goto simplify2; // next pattern with the same "match"
> >>>operand.
> >>>>>>>>>>>>>>> transform code for pattern 1
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> simplify2:
> >>>>>>>>>>>>>>> if (! pattern-2 ifexpr condition)
> >>>>>>>>>>>>>>> return false; // last pattern
> >>>>>>>>>>>>>>> transform code for pattern 2.
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> If matching itself fails, that is neither of the decisions
> >>>get
> >>>>>>>>>>>>>>> matched,
> >>>>>>>>>>>>>>> I believe we can then return false as it cannot match any
> >>>other
> >>>>>>>>>>>>>>> pattern ?
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> * patterns needing hacks like cond_expr or GENERIC support
> >>>>>>>>>>>>>>> I haven't given thought to this yet. I suppose we can look
> >>>to
> >>>>>>>>>>>>>>> handle
> >>>>>>>>>>>>>>> these after adding support for GENERIC. Instead of
> >>>generating
> >>>>>>>>>>>>>>> GENERIC
> >>>>>>>>>>>>>>> matching in
> >>>>>>>>>>>>>>> gimple_match_and_simplify, could we then call
> >>>>>>>>>>>>>>> generic_match_and_simplify from
> >>>>>>>>>>>>>>> within gimple_match_and_simplify ?
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>> Yes (that's what's currently done btw).
> >>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> * Tests
> >>>>>>>>>>>>>>> The patch transformed the following patterns:
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> (match_and_simplify
> >>>>>>>>>>>>>>> (negate (bit_not @0))
> >>>>>>>>>>>>>>> if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
> >>>>>>>>>>>>>>> (plus @0 { build_int_cst (TREE_TYPE (@0)), 1); }))
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> (match_and_simplify
> >>>>>>>>>>>>>>> (negate (negate @0))
> >>>>>>>>>>>>>>> @0)
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> I have attached test-case I tried it with (negate.c)
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> * Conclusion
> >>>>>>>>>>>>>>> Does it sound reasonable ? I am going to be re-writing the
> >>>>>>>>>>>>>>> decision tree from scratch, but is the basic idea fine ?
> >>>Or should
> >>>>>>>>>>>>>>> we
> >>>>>>>>>>>>>>> take a different approach ?
> >>>>>>>>>>>>>>>
> >>>>>>>>>>>>>>> Thanks and Regards,
> >>>>>>>>>>>>>>> Prathamesh
> >>>>>>
> >>
> >>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dt4.patch
Type: text/x-patch
Size: 33689 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20140616/60ed24e7/attachment.bin>
More information about the Gcc
mailing list