On 6/11/14, Richard Biener <richard.guent...@gmail.com> wrote:
> On Wed, Jun 11, 2014 at 12:53 PM, Richard Biener
> <richard.guent...@gmail.com> wrote:
>> On Wed, Jun 11, 2014 at 10:51 AM, Richard Biener
>> <richard.guent...@gmail.com> wrote:
>>> On Tue, Jun 10, 2014 at 1:57 PM, Richard Biener
>>> <richard.guent...@gmail.com> wrote:
>>>> On Tue, Jun 10, 2014 at 1:06 PM, Prathamesh Kulkarni
>>>> <bilbotheelffri...@gmail.com> wrote:
>>>>> On Fri, Jun 6, 2014 at 7:18 PM, Richard Biener
>>>>> <richard.guent...@gmail.com> wrote:
>>>>>> On Fri, Jun 6, 2014 at 12:02 PM, Richard Biener
>>>>>> <richard.guent...@gmail.com> wrote:
>>>>>>> On Fri, Jun 6, 2014 at 11:02 AM, Prathamesh Kulkarni
>>>>>>> <bilbotheelffri...@gmail.com> wrote:
>>>>>>>> On Mon, Jun 2, 2014 at 6:14 PM, Richard Biener
>>>>>>>> <richard.guent...@gmail.com> wrote:
>>>>>>>>> On Mon, Jun 2, 2014 at 1:16 PM, Prathamesh Kulkarni
>>>>>>>>> <bilbotheelffri...@gmail.com> wrote:
>>>>>>>>>> I have few questions regarding genmatch:
>>>>>>>>>>
>>>>>>>>>> a) Why is 4 hard-coded here: ?
>>>>>>>>>> in write_nary_simplifiers:
>>>>>>>>>> fprintf (f, " tree captures[4] = {};\n");
>>>>>>>>>
>>>>>>>>> Magic number (this must be big enough for all cases ...).
>>>>>>>>> Honestly
>>>>>>>>> this should be improved (but requires another scan over the matcher
>>>>>>>>> IL
>>>>>>>>> to figure out the max N used in @N).
>>>>>>>>>
>>>>>>>>>> b) Should we add syntax for a symbol to denote multiple operators
>>>>>>>>>> ?
>>>>>>>>>> For exampleim in simplify_rotate:
>>>>>>>>>> (X << CNT1) OP (X >> CNT2) with OP being +, |, ^ (CNT1 + CNT2 ==
>>>>>>>>>> bitsize of type of X).
>>>>>>>>>
>>>>>>>>> Something to enhance the IL with, yes. I'd say we support
>>>>>>>>>
>>>>>>>>> (define_op additive PLUS_EXPR MINUS_EXPR POINTER_PLUS_EXPR)
>>>>>>>>>
>>>>>>>>> thus,
>>>>>>>>>
>>>>>>>>> (define_op <operator-name> op...)
>>>>>>>>>
>>>>>>>>>> c) Remove for parsing capture in parse_expr since we reject
>>>>>>>>>> outermost
>>>>>>>>>> captured expressions ?
>>>>>>>>>
>>>>>>>>> but parse_expr is also used for inner expressions, no?
>>>>>>>>>
>>>>>>>>> (plus (minus@2 @0 @1) @3)
>>>>>>>>>
>>>>>>>>> should still work
>>>>>>>>>
>>>>>>>>>> d) I am not able to follow this comment in match.pd:
>>>>>>>>>> /* Patterns required to avoid SCCVN testsuite regressions. */
>>>>>>>>>>
>>>>>>>>>> /* (x >> 31) & 1 -> (x >> 31). Folding in fold-const is more
>>>>>>>>>> complicated here, it does
>>>>>>>>>> Fold (X << C1) & C2 into (X << C1) & (C2 | ((1 << C1) - 1))
>>>>>>>>>> (X >> C1) & C2 into (X >> C1) & (C2 | ~((type) -1 >> C1))
>>>>>>>>>> if the new mask might be further optimized. */
>>>>>>>>>> (match_and_simplify
>>>>>>>>>> (bit_and (rshift@0 @1 INTEGER_CST_P@2) integer_onep)
>>>>>>>>>> if (compare_tree_int (@2, TYPE_PRECISION (TREE_TYPE (@1)) - 1)
>>>>>>>>>> == 0)
>>>>>>>>>> @0)
>>>>>>>>>
>>>>>>>>> The comment is literally copied from the case I extracted the
>>>>>>>>> (simplified) variant from fold-const.c. See lines 11961-12056 in
>>>>>>>>> fold-const.c.
>>>>>>>>> It'll be a challenge to implement the equivalent in a pattern ;)
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Decision Tree.
>>>>>>>>>> I have tried to come up with a prototype for decision tree
>>>>>>>>>> (patch attached).
>>>>>>>>>> For simplicity, it handles patterns involving only unary operators
>>>>>>>>>> and
>>>>>>>>>> no predicates
>>>>>>>>>> and returns false when the pattern fails to match (no goto to
>>>>>>>>>> match
>>>>>>>>>> another pattern).
>>>>>>>>>> I meant to post it only for illustration, and I have not really
>>>>>>>>>> paid
>>>>>>>>>> attention to code quality (bad formatting, memory leaks, etc.).
>>>>>>>>>>
>>>>>>>>>> * Basic Idea
>>>>>>>>>> A pattern consists of following parts: match, ifexpr and result.
>>>>>>>>>> Let's call <ifexpr, result> as "simplification" operand.
>>>>>>>>>> The common prefix between different match operands would be
>>>>>>>>>> represented
>>>>>>>>>> by same nodes in the decision tree.
>>>>>>>>>>
>>>>>>>>>> Example:
>>>>>>>>>> (negate (bit_not @0))
>>>>>>>>>> S1
>>>>>>>>>>
>>>>>>>>>> (negate (negate @0))
>>>>>>>>>> S2
>>>>>>>>>>
>>>>>>>>>> S1, S2 denote simplifications for the above patterns
>>>>>>>>>> respectively.
>>>>>>>>>>
>>>>>>>>>> The decision tree would look something like
>>>>>>>>>> (that's the way it gets constructed with the patch):
>>>>>>>>>>
>>>>>>>>>> dummy/root
>>>>>>>>>> |
>>>>>>>>>> NEGATE_EXPR
>>>>>>>>>> / \
>>>>>>>>>> BIT_NOT NEGATE_EXPR
>>>>>>>>>> | |
>>>>>>>>>> @0 @0
>>>>>>>>>> | |
>>>>>>>>>> S1 S2
>>>>>>>>>>
>>>>>>>>>> a) The children of an internal node are number of decisions that
>>>>>>>>>> can be taken at that node. In the above case it's 2 for outer
>>>>>>>>>> NEGATE_EXPR.
>>>>>>>>>> b) Simplification operand represents leaves of the decision tree
>>>>>>>>>> c) Instead of having list of heads, I have added one dummy node,
>>>>>>>>>> and heads become children of these dummy root node.
>>>>>>>>>> d) Code-gen for non-simplification operands involves generating,
>>>>>>>>>> "matching" code and for simplification operands involves
>>>>>>>>>> generating
>>>>>>>>>> "transform" code
>>>>>>>>>>
>>>>>>>>>> * Overall Flow:
>>>>>>>>>> I guess we would build the decision tree from the AST.
>>>>>>>>>> So the flow would be like:
>>>>>>>>>> source -> struct simplify (match, ifexpr, result) -> decision tree
>>>>>>>>>> -> c code.
>>>>>>>>>>
>>>>>>>>>> Something like (in main):
>>>>>>>>>> decision_tree dt;
>>>>>>>>>> while (there is another pattern)
>>>>>>>>>> {
>>>>>>>>>> simplify *s = parse_match_and_simplify ();
>>>>>>>>>> insert s into decision tree;
>>>>>>>>>> };
>>>>>>>>>> So parsing routines are concerned with parsing and building the
>>>>>>>>>> AST (operand),
>>>>>>>>>> and not with the decision tree. Is that fine ?
>>>>>>>>>
>>>>>>>>> Yes, that's good.
>>>>>>>>>
>>>>>>>>>> * Representation of decision tree.
>>>>>>>>>> A decision tree would need a way to represent language constructs
>>>>>>>>>> like capture, predicate, etc. so in some ways it would be similar
>>>>>>>>>> to AST.
>>>>>>>>>> It
>>>>>>>>>> In the patch, I have created the following heirarchy:
>>>>>>>>>> dt_operand: represents a general base "operand" of in decision
>>>>>>>>>> tree
>>>>>>>>>> dt_expr: for representing expression. Expression contains
>>>>>>>>>> operation
>>>>>>>>>> to be performed (e_operation).
>>>>>>>>>> dt_capture: analogous to capture.
>>>>>>>>>> dt_simplify: for representing "simplification" operand.
>>>>>>>>>> simplification consists of ifexpr and result
>>>>>>>>>> dt_head: to represent "dummy" root. Maybe a separate class is not
>>>>>>>>>> needed.
>>>>>>>>>>
>>>>>>>>>> * Constructing decision tree from AST
>>>>>>>>>> The algorithm i have used is similar to inserting string in a
>>>>>>>>>> trie
>>>>>>>>>> outlined here: http://en.wikipedia.org/wiki/Trie
>>>>>>>>>> The difference shall be to traverse AST depth-first rather than
>>>>>>>>>> traversing the string.
>>>>>>>>>> Apart from that I guess it would be the same (naturally find and
>>>>>>>>>> compare operations would be different).
>>>>>>>>>> I haven't given much thought about this. Currently, I construct
>>>>>>>>>> decision tree for only patterns with unary operators in an
>>>>>>>>>> ugly way by "flattening" the AST by walking it in pre-order and
>>>>>>>>>> storing the nodes in vector in the order they are visited
>>>>>>>>>>
>>>>>>>>>> So to construct decision tree from the following AST:
>>>>>>>>>> negate
>>>>>>>>>> |
>>>>>>>>>> bit_not
>>>>>>>>>> |
>>>>>>>>>> @0
>>>>>>>>>>
>>>>>>>>>> AST is flattened by walking in preorder (by walk_operand_preorder)
>>>>>>>>>> and stored
>>>>>>>>>> as: [ expr, expr, capture ]
>>>>>>>>>> and this vector is used to construct decision tree.
>>>>>>>>>> I did it as a "quick and dirty" way, it has to be changed.
>>>>>>>>>> And it won't work for patterns with n-ary operators.
>>>>>>>>>>
>>>>>>>>>> We should visit each node of AST in preorder, and add that node
>>>>>>>>>> during traversal to decision tree. I am not yet clear on way of
>>>>>>>>>> doing that.
>>>>>>>>>>
>>>>>>>>>> * Comparing operands
>>>>>>>>>> How do we compare operands ? We shall need to do this while
>>>>>>>>>> inserting
>>>>>>>>>> in decision tree, since if the operand is already inserted we do
>>>>>>>>>> not create
>>>>>>>>>> a new node.
>>>>>>>>>> In the patch (cmp_operand), I have used following rules:
>>>>>>>>>> a) if types not equal, they are clearly not equal.
>>>>>>>>>> b) if type is expr, compare operation->op->id
>>>>>>>>>> c) if type is capture, compare the number.
>>>>>>>>>> d) for predicate, compare on ident ?
>>>>>>>>>>
>>>>>>>>>> * Representing patterns with n-ary operators.
>>>>>>>>>> Consider following two match operands:
>>>>>>>>>> (plus (minus @0 @1) @1)
>>>>>>>>>> (plus (negate @0) @1)
>>>>>>>>>>
>>>>>>>>>> In decision tree, it would be represented as:
>>>>>>>>>>
>>>>>>>>>> *********plus*********
>>>>>>>>>> / \ / \
>>>>>>>>>> minus @1 negate @1
>>>>>>>>>> / \ |
>>>>>>>>>> @0 @1 @0
>>>>>>>>>>
>>>>>>>>>> plus has got 4 children - (minus @0 @1), @1, (negate @0), @1.
>>>>>>>>>> However (minus @0 @1) and @1 are not separate "decisions", but
>>>>>>>>>> children of plus within the same expression.
>>>>>>>>>>
>>>>>>>>>> For calculating number of decisions at an expression node:
>>>>>>>>>> number of decisions = number of children / arity of operator.
>>>>>>>>>> in the above case, number of decision = 4 / 2 = 2
>>>>>>>>>>
>>>>>>>>>> For other cases, for instance capture node (the children would be
>>>>>>>>>> simplification operand),
>>>>>>>>>> number of decisions = number of children.
>>>>>>>>>
>>>>>>>>> Hmm. I think it should be only two children from the plus,
>>>>>>>>> as pre-order for the first pattern is for example
>>>>>>>>> [plus minus @0 @1 @1] so you'd have
>>>>>>>>>
>>>>>>>>> plus
>>>>>>>>> / \
>>>>>>>>> minus negate
>>>>>>>>> | |
>>>>>>>>> @0 @0
>>>>>>>>> | |
>>>>>>>>> @1 @1
>>>>>>>>> |
>>>>>>>>> @1
>>>>>>>>>
>>>>>>>>> instead?
>>>>>>>>>
>>>>>>>>> Note that you probably have to deal with non-matching capture
>>>>>>>>> IDs by re-writing them on-the-fly. That is, the two
>>>>>>>>> pre-oder traversals [plus minus @1 ...] and [plus minus @0 ...]
>>>>>>>>> should commonize with renaming the non-matching capture
>>>>>>>>> somehow.
>>>>>>>> Um, could you please elaborate on that (non-matching capture ?),
>>>>>>>> I am not sure if I understood it fully, thanks.
>>>>>>>
>>>>>>> I'm worried about
>>>>>>>
>>>>>>> (plus (minus@1 @2 @3) @2)
>>>>>>>
>>>>>>> vs.
>>>>>>>
>>>>>>> (plus (minus @1 @2) @1)
>>>>>>>
>>>>>>> (just made-up examples, of course). Here we'd like to
>>>>>>> commonize the path checking for (plus (minus ...) ... but
>>>>>>> of course we can't easily process the captures at that point
>>>>>>> as the first has two captures (it captures the minus itself while
>>>>>>> the 2nd doesn't) and the captures that are at the same position
>>>>>>> use different indexes. To finally match the minus we have to
>>>>>>> verify that in one case @2 == @2 and in the other case that
>>>>>>> @1 == @1.
>>>>>>>
>>>>>>> Re-numbering capture indexes in pre-order would improve things
>>>>>>> for the case where capture positions are in the same places but
>>>>>>> the indexes do not match. It won't handle the above case
>>>>>>> of course.
>>>>> Thanks, I understand it now -:)
>>>>
>>>> I suppose that it would be best (in the end) to not insert the
>>>> captures into the decision tree separately but leave them
>>>> "combined" and then only after the decision tree is fully built
>>>> decide on re-numbering. And treat those that are required for
>>>> the matching process differently (those that assert that two
>>>> ops are equal).
>>>>
>>>> I think we can defer the issue to later.
>>>>
>>>>>>>
>>>>>>>> I have attached patch for patterns with binary operators (in
>>>>>>>> principle
>>>>>>>> should work for n-ary operators,
>>>>>>>> but have only tested upto 2), that creates decision tree for
>>>>>>>> patterns (excluding predicates, and multiple matching). I don't
>>>>>>>> intend
>>>>>>>> to commit this (contains many hacks!).
>>>>>>>>
>>>>>>>> * Constructing decision tree from AST
>>>>>>>> We can define our decision tree to store prefixes of preorder
>>>>>>>> traversals of diffferent AST.
>>>>>>>> Insertion happens as follows (decision_tree::insert)
>>>>>>>> a) Get preorder traversal of AST into vector.
>>>>>>>> b) Insert AST nodes from vector into decision tree.
>>>>>>>> Currently, I obtain preorder traversal into a vector. We can later
>>>>>>>> change it to compute
>>>>>>>> next preorder successor lazily.
>>>>>>>
>>>>>>> Just make the code easy to understand, optimizing it should be
>>>>>>> secondary.
>>>>>>>
>>>>>>>> * Code-gen
>>>>>>>> For n-ary operators, the patch generates code as follows:
>>>>>>>> if (code == <expr code>)
>>>>>>>> {
>>>>>>>> match operand 0
>>>>>>>> match operand 1
>>>>>>>> ....
>>>>>>>> match operand n-1
>>>>>>>> transform
>>>>>>>> return true;
>>>>>>>> }
>>>>>>>>
>>>>>>>> * Adding parent, level, pos fields to AST (operand).
>>>>>>>> One change (hack), I have made to code-gen, is naming of operands
>>>>>>>> that are
>>>>>>>> assigned to gimple_assign_rhs in code-gen of expressions.
>>>>>>>> I am not sure if this is really needed.
>>>>>>>>
>>>>>>>> in AST, we have following representation for expressions:
>>>>>>>> expr-
>>>>>>>> / \
>>>>>>>> left right
>>>>>>>> operand operand
>>>>>>>>
>>>>>>>> code-gen off AST (expr::gen_gimple_match) produces code like:
>>>>>>>> {
>>>>>>>> tree op = gimple_assign_rhs1 (def_stmt);
>>>>>>>> // code-gen for left operand
>>>>>>>> }
>>>>>>>> {
>>>>>>>> tree op = gimple_assign_rhs2 (def_stmt);
>>>>>>>> // code-gen for right operand
>>>>>>>> }
>>>>>>>>
>>>>>>>> We can do this since, in expr::gen_gimple_match, we call
>>>>>>>> left_operand->gen_gimple_match,
>>>>>>>> come back to expr::gen_gimple_match (after
>>>>>>>> left_operand->gen_gimple_match() returns), and
>>>>>>>> then call right_operand->gen_gimple_match().
>>>>>>>>
>>>>>>>> However in decision tree, the expression gets represented as
>>>>>>>> follows:
>>>>>>>> expr
>>>>>>>> |
>>>>>>>> left-operand
>>>>>>>> |
>>>>>>>> right-operand
>>>>>>>>
>>>>>>>> dt_expr::gen_gimple calls left_operand->gen_gimple, which calls
>>>>>>>> right_operand->gen_gimple,
>>>>>>>> so we return to dt_expr::gen_gimple, after code is generated for
>>>>>>>> the
>>>>>>>> whole subtree of expr.
>>>>>>>>
>>>>>>>> So I assign operands at the start before generating code for the
>>>>>>>> subtree:
>>>>>>>> tree op00 = gimple_assign_rhs1 (def_stmt);
>>>>>>>> tree op10 = gimple_assign_rhs2 (def_stmt);
>>>>>>>> <code for left-operand>
>>>>>>>> <code for right-operand>
>>>>>>>> each of the operands know their positions, so they know which
>>>>>>>> operand
>>>>>>>> to use (get_op_name()).
>>>>>>>> the names are generated as:
>>>>>>>> op<position><level>, position = index of operand in it's parent's
>>>>>>>> expr's vector (vec<operand *> ops).
>>>>>>>> level: level of AST, at which the operand is stored.
>>>>>>>>
>>>>>>>> For this I added three fields to operand (unsigned pos, and
>>>>>>>> unsigned
>>>>>>>> level, operand *parent), and accordingly
>>>>>>>> made changes to expr::append_op. In a way this is abusing the AST.
>>>>>>>> This probably works (works with test-cases i tried), but I don't
>>>>>>>> like it much.
>>>>>>>
>>>>>>> The naming is ok, but indeed it doesn't feel very clean. Somehow
>>>>>>> this
>>>>>>> belongs to the decision tree instead... (but then you need to lookup
>>>>>>> the decision tree operand info from code-gen which happens off the
>>>>>>> AST...).
>>>>>>>
>>>>>>>> * Order of matching.
>>>>>>>> Currently the order of matching operands is strictly 0, 1, .. n - 1
>>>>>>>> for n-ary operator.
>>>>>>>> However this might not be the best choice.
>>>>>>>>
>>>>>>>> For example, consider following patterns:
>>>>>>>> (operator op1 op) S1
>>>>>>>> (operator op2 op) S2
>>>>>>>>
>>>>>>>> Both have common operator, and 1st common operand, they differ in
>>>>>>>> 0th operand.
>>>>>>>> With patch, the code generated is:
>>>>>>>> if (code == <expr-code>)
>>>>>>>> {
>>>>>>>> match op1
>>>>>>>> match op
>>>>>>>> S1
>>>>>>>>
>>>>>>>> match op2
>>>>>>>> match op
>>>>>>>> S2
>>>>>>>> }
>>>>>>>>
>>>>>>>> A better ordering would be to match the 1st operand and then
>>>>>>>> respective 0th operands of both patterns:
>>>>>>>>
>>>>>>>> if (code == <expr-code>
>>>>>>>> {
>>>>>>>> match op
>>>>>>>> match op1
>>>>>>>> S1
>>>>>>>> match op0
>>>>>>>> S2
>>>>>>>> }
>>>>>>>>
>>>>>>>> This complicates insertion into decision tree.
>>>>>>>
>>>>>>> I'd say we leave "optimizing" the decision tree to a later stage -
>>>>>>> it's a global
>>>>>>> optimization problem after all (I believe you can't do optimally with
>>>>>>> just
>>>>>>> looking at the present decision tree and the AST you want to
>>>>>>> insert).
>>>>>>>
>>>>>>>> * hack: only one generated gimple_match_and_simplify function
>>>>>>>> In the patch, I generate code for gimple_match_and_simplify with 3
>>>>>>>> operands version (op0, op1, op2)
>>>>>>>> and the other two (unary and binary versions), call it with
>>>>>>>> NULL_TREE
>>>>>>>> for extra operands.
>>>>>>>> I will soon change that.
>>>>>>>>
>>>>>>>> * Testing patterns.
>>>>>>>> I think I have written most of the test-cases wrongly in match-2.c
>>>>>>>> For example this test-case doesn't match
>>>>>>>> (i haven't checked in "fix testsuite fallout" patch, so this might
>>>>>>>> not be true
>>>>>>>> anymore)
>>>>>>>>
>>>>>>>> (match_and_simplify
>>>>>>>> plus (minus @0 @1) @1)
>>>>>>>> @0)
>>>>>>>>
>>>>>>>> for this test-case:
>>>>>>>> /* (x - y) + y -> x */
>>>>>>>> int f6(int x, int y)
>>>>>>>> {
>>>>>>>> int t1 = x - y;
>>>>>>>> return t1 + y;
>>>>>>>> }
>>>>>>>> /* { dg-final { scan-tree-dump "gimple_match_and_simplified to
>>>>>>>> \[^\n\r\]*= x_\\d\+\\(D\\)" "forwprop1" } } */
>>>>>>>>
>>>>>>>> I get following output (tree-forwprop-details):
>>>>>>>>
>>>>>>>> ;; Function f6 (f, funcdef_no=0, decl_uid=1744, symbol_order=0)
>>>>>>>>
>>>>>>>> gimple_match_and_simplified to _4 = y_2(D) + t1_3;
>>>>>>>> f (int x, int y)
>>>>>>>> {
>>>>>>>> int t1;
>>>>>>>> int _4;
>>>>>>>>
>>>>>>>> <bb 2>:
>>>>>>>> t1_3 = x_1(D) - y_2(D);
>>>>>>>> _4 = x_1(D);
>>>>>>>> return _4;
>>>>>>>>
>>>>>>>> }
>>>>>>>>
>>>>>>>> Shouldn't it show: gimple_match_and_simplified to _4 = x_1(D)
>>>>>>>> instead ?
>>>>>>>
>>>>>>> Yeah. I suppose you hit the issue that we don't commutate patterns,
>>>>>>> so try with a commutated pattern inserted.
>>>>>>>
>>>>>>>> The issue is this test-case fails in isolation, however it passes
>>>>>>>> when
>>>>>>>> it is placed with other
>>>>>>>> test cases that PASS and have same regex in scan-tree-dump as this
>>>>>>>> test-case:
>>>>>>>> scan-tree-dump "gimple_match_and_simplified to \[^\n\r\]*=
>>>>>>>> x_\\d\+\\(D\\)"
>>>>>>>>
>>>>>>>> Summary:
>>>>>>>> I think we need to (at-least) deal with following problems for
>>>>>>>> decision tree:
>>>>>>>
>>>>>>> I have to leave for a while now, I'll come back later and have a
>>>>>>> detailed
>>>>>>> look at the patch to try answer the questions below.
>>>>>>
>>>>>> Now for the remainder.
>>>>>>
>>>>>>>> a) Representation and construction of decision tree from AST -
>>>>>>>> We do this by storing prefixes of preorder traversals of AST in
>>>>>>>> decision tree. Do we finalize on that ?
>>>>>>
>>>>>> Yes.
>>>>>>
>>>>>>>> b) Order of operand matching
>>>>>>
>>>>>> I think that's the same as a) - the visiting order of the AST
>>>>>> determines
>>>>>> the order of operand matching.
>>>>>>
>>>>>>>> c) Generating patterns for built-in functions (I guess this will be
>>>>>>>> similar to expr-gen).
>>>>>>
>>>>>> It should really be transparent.
>>>>>>
>>>>>>>> d) Multiple matching patterns
>>>>>>
>>>>>> The decision tree phase leaves us with a sequence of
>>>>>>
>>>>>> if (if-expr of pattern1)
>>>>>> transform-pattern1
>>>>>> else (if-expr of pattern2)
>>>>>> transform-pattern2
>>>>>> ...
>>>>>>
>>>>>> etc. thus that part should be basically unchanged (only the match
>>>>>> part is driven by a decision tree).
>>>>>>
>>>>>>>> e) Commutative ops
>>>>>>
>>>>>> I'd do these as a pass over the AST of each pattern, duplicating
>>>>>> patterns.
>>>>>>
>>>>>> Btw, I see you mirror the AST structure with
>>>>>> dt_{node,operand,expr,...}.
>>>>>> It seems to me that you can simply stick an AST operand * into
>>>>>> dt_node and be done with just having dt_node? That is, the AST
>>>>>> operand refered to contains all necessary information already.
>>>>>>
>>>>>>>>
>>>>>>>> Pattern Enhancements:
>>>>>>>> Some of these were already discussed, I am jotting them here:
>>>>>>>> a) Symbol for multiple operators
>>>>>>>> b) grouping patterns by ifexpr
>>>>>>>> c) should we have MATCH_FAILED or FAIL to explicitly denote failure
>>>>>>>> in
>>>>>>>> manual transform (c_expr) ?
>>>>>>>> d) making operators to be commutative.
>>>>>>
>>>>>> I'd say d) would be really nice to have. Either with a grammar
>>>>>> extension to say which expression should have commutation applied
>>>>>> to (for example: (plus! (minus @1 @2) @2) would say that the
>>>>>> operands of plus should be commutated), or with a simple heuristic.
>>>>>> I'd say explicitly specifying is better.
>>>>>>
>>>>>> a) will probably be needed to avoid pattern explosion. But similar to
>>>>>> d)
>>>>>> I'd do it as a pre-pass on the AST, duplicating the patterns. It's
>>>>>> also a good question how to define its semantic. The mode-iterators
>>>>>> that the machine description supports would suggest we do instead
>>>>>> sth like
>>>>>>
>>>>>> (for OP in (plus minus mult)
>>>>>> (match_and_simplify
>>>>>> (OP @1 integer_zerop)
>>>>>> ....))
>>>>>>
>>>>>> c) should be easy, I'm going to try sth like that - also setting
>>>>>> temporaries
>>>>>> from the ifexpr and re-using them in the result like
>>>>>>
>>>>>> (match_and_simplify
>>>>>> (plus @1 @2)
>>>>>> if (INTEGRAL_TYPE_P (TREE_TYPE (@2))
>>>>>> && find_better_ops (&@3, &@4, @1, @2))
>>>>>> (plus @3 @4))
>>>>>>
>>>>>> which also requires us to scan the AST for the highest capture index
>>>>>> (a good thing anyway, given my hack to statically set the size of
>>>>>> the captures array ;))
>>>>>>
>>>>>> b) I'm not sure it's worth the trouble (apart from doing less typing
>>>>>> in match.pd). We're probably going to have GENERIC defined
>>>>>> when creating the generic routines and GIMPLE when creating
>>>>>> the gimple routines so we can easily disable patterns for one or
>>>>>> the other by doing
>>>>>>
>>>>>> #ifdef GIMPLE
>>>>>> (match_and_simplify
>>>>>> ...)
>>>>>> #endif
>>>>>>
>>>>>>>> Once the decision tree is done, I can try working on these.
>>>>>>>> Till Sunday, I will attempt to have another prototype, that covers
>>>>>>>> most of the patterns in match.pd
>>>>>>>> (except for cond_expr, and those requiring GENERIC support), and
>>>>>>>> accompanying correct test-case
>>>>>>>> for each pattern. And next-week start working on a fair patch.
>>>>>>
>>>>>> Sounds good.
>>>>> I have attached a patch, that fires most of the patterns from match.pd
>>>>> except for those that include
>>>>> non-matching capture or require GENERIC support, and added a test-case
>>>>> match-decision-tree.c
>>>>> (fires around 33 patterns).
>>>>>
>>>>> * Representation of decision tree:
>>>>> I clubbed dt_capture, dt_predicate, dt_expr into dt_operand, and added
>>>>> new gen_gimple_match() function in AST
>>>>> to generates matching code. dt_operand contains operand *op as member,
>>>>> and merely calls op->gen_gimple_match.
>>>>> (that's the intent anyway, in the patch, i needed to put some hacks to
>>>>> get it working).
>>>>> In the patch, i have kept: dt_node, dt_operand (dt_node), dt_simplify
>>>>> (dt_node), to separate matching operand
>>>>> from simplification (ifexpr, result).
>>>>>
>>>>> * Constructing decision tree from AST
>>>>> Same as previous patch, stores prefixes of preorder traversals of AST.
>>>>> decision_tree::print() pretty-prints the decision tree.
>>>>>
>>>>> I hope we won't need to change much up-to this point in the patch.
>>>>>
>>>>> * Code-gen
>>>>> code gen of (operator op0 op1 ..opN) simplify takes the following
>>>>> form:
>>>>> if (code == <expr code>)
>>>>> {
>>>>> match op0
>>>>> match op1
>>>>> ...
>>>>> match opN
>>>>> simplify
>>>>> return true;
>>>>> }
>>>>>
>>>>> a) Scope of temporaries (the ones that are assigned to
>>>>> gimple_assign_rhsX):
>>>>> for code-gen of expressions off the AST, we create a temporary:
>>>>>
>>>>> {
>>>>> tree op = gimple_assign_rhsX ();
>>>>> generate code for X'th operand
>>>>> }
>>>>>
>>>>> In the decision tree, an expression can only directly access it's 1st
>>>>> operand (since it's preorder traversal).
>>>>> So I decided to first create all temporaries and then generate code
>>>>> for operands:
>>>>>
>>>>> {
>>>>> tree op0 = gimple_assign_rhs1 ();
>>>>> tree op1 = gimple_assign_rhs2 ();
>>>>> tree opX-1 = gimple_assign_rhsX ();
>>>>>
>>>>> code for matching 0th operand
>>>>> code for matching 1st operand
>>>>> ...
>>>>> code for matching Nth operand
>>>>> }
>>>>>
>>>>> Unfortunately, this creates a problem if the operand itself is an
>>>>> expression,
>>>>> since it's temporaries would also be named op0, op1 ... they would
>>>>> shadow the outer op0, op1 .. temporaries.
>>>>> So we need distinct names for each temporary (for all temps within one
>>>>> pattern).
>>>>> The temporary name is created by:
>>>>> op<position of child operand><level of tree>;
>>>>> and each child of AST knows it's position and level, so it can
>>>>> correctly access it's temp.
>>>>> This requires adding members operand *parent, unsigned pos, unsigned
>>>>> level to struct operand.
>>>>> I have done it this way in the patch, however it doesn't feel clean, I
>>>>> will try to see if we can change this.
>>>>>
>>>>> b) Short-ranged gotos
>>>>> consider: (negate @0) S1
>>>>> The code is generated as (with the patch):
>>>>>
>>>>> if (code == PLUS)
>>>>> {
>>>>> if (!captures [0])
>>>>> {
>>>>> captures[0] = op0;
>>>>> goto L0;
>>>>> }
>>>>> else if (captures[0] == op0)
>>>>> {
>>>>> L0:
>>>>> // simplification code S1
>>>>> return true;
>>>>> }
>>>>> }
>>>>>
>>>>> Instead of:
>>>>> if (!captures[0])
>>>>> captures[0] = op0;
>>>>> else if (captures[0] != op0)
>>>>> goto L0;
>>>>>
>>>>> // Simplification code S1
>>>>> return true;
>>>>>
>>>>> L0: // match next pattern
>>>>>
>>>>> Generating code the former way is more easier, since location of label
>>>>> immediately follows
>>>>> capture code (if (!captures[0]) ...). In the latter case, I probably
>>>>> need to store label name in the sibling's node in
>>>>> the decision tree and then retrieve that.
>>>>> Similarly for valueize (expr::gen_valueize).
>>>>
>>>> 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
> <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>.
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
I suppose pattern-1 would always match (even with earlier code gen.
> 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
>
