[GSoC] decision tree first steps
Prathamesh Kulkarni
bilbotheelffriend@gmail.com
Sun Jun 15 23:08:00 GMT 2014
On Sat, Jun 14, 2014 at 12:43 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On June 13, 2014 11:48:13 PM CEST, Prathamesh Kulkarni <bilbotheelffriend@gmail.com> wrote:
>>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
>
> You could also do
>
> Plus - true - match(1) - negate - true
>
> To avoid doing two things in one node.
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).
* 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).
* 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).
* 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;
};
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 ?
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>);
* Added do_valueize () in gimple-match-head.c. the generated code
calls do_valueize to valueize theopereand.
This make code-gen simpler (no goto).
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.
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 -:)
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: dt3.patch
Type: text/x-patch
Size: 25337 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20140615/6bde71e6/attachment.bin>
More information about the Gcc
mailing list