On Mon, Mar 10, 2014 at 7:29 PM, Prathamesh Kulkarni
<bilbotheelffri...@gmail.com> wrote:
> Hi Richard,
> Sorry for the late reply. I would like to have few clarifications
> regarding the following points:
>
> a) Pattern matching: Currently, gimple_match_and_simplify() matches
> patterns one-by-one. Could we use a decision tree to do the matching
> instead (similar to insn-recog.c) ?
> For the moment, let's consider pattern matching on only unary
> expressions without valueize and predicates:
> pattern 1: (negate (negate @0))
> pattern 2: (negate (bit_not @0))
>
> from the two AST's corresponding to patterns (match::op), we can build
> a decision tree:
> Some-thing similar to:
> NEGATE_EXPR
> NEGATE_EXPR BIT_NOT_EXPR
>
> and then generate code corresponding to this decision tree in gimple-match.c
> so the generated code should look something similar to:
>
> tree
> gimple_match_and_simplify (enum tree_code code, tree type, tree op0,
> gimple_seq *seq, tree (*valueize)(tree))
> {
> if (code == NEGATE_EXPR)
> {
> tree captures[4] = {};
> if (TREE_CODE (op0) != SSA_NAME)
> return NULL_TREE;
> gimple def_stmt = SSA_NAM_DEF_STMT (op0);
> if (!is_gimple_assign (def_stmt))
> return NULL_TREE;
> tree op = gimple_assign_rhs1 (def_stmt);
> if (gimple_assign_rhs_code (op) == NEGATE_EXPR)
> {
> /* pattern (negate (negate @0)) matched */
> }
> else if (gimple_assign_rhs_code (op) == BIT_NOT_EXPR)
> {
> /* pattern (negate (bit_not_expr @0)) matched */
> }
> else
> return NULL_TREE;
> }
> else
> return NULL_TREE;
> }
>
> For commutative ops, the pattern can be duplicated by walking the
> children of the node in reverse order.
> (I am not exactly clear so far about representing binary operators in a
> decision
> tree) Is this the right way to go ? I shall try to shortly post a patch that
> implements this.
Yes, that's the way to go (well, I'd even use a switch ()).
> b) Targeting GENERIC, separating AST from gimple/generic:
> For generating a GENERIC pattern should there be another pattern
> something like match_and_simplify_generic ?
Yes, there is an existing API in GCC for this that operates on GENERIC.
It's fold_unary_loc, fold_binary_loc, fold_ternary_loc. The interface
the GENERIC match_and_simplify variant provides should match
that one.
> Currently, the AST data structures (operand, expr, etc.)
> are tied to gimple (gen_gimple_match, gen_gimple_transform).
> We could also have similar functions: gen_generic_match,
> gen_generic_transform for generating GENERIC ?
Yeah, but I'm not sure if keeping the (virtual) methods for generating
code makes much sense with a rewritten code generator.
> Instead will it be better if we separate the AST
> from target IR (generic/gimple) and make simplify a visitor on AST
> (make simplify
> abstract class, with simplify_generic and simplify_gimple visitor
> classes that generate corresponding IR code) ?
Yes. Keep in mind the current state of genmatch.c is "quick hack
to make playing with the API side and with patterns possible" ;)
> c) Shall it be a good idea in define_match <name> <pattern>, for
> name to act as a substitute for pattern (similar to flex pattern
> definitions), so the name can be used in bigger patterns ?
Maybe, I suppose we'll see when adding more patterns.
> d) This is silly, but maybe use constants to denote corresponding tree nodes ?
> for example instead of { build_int_cst (integer_type_node, 0); }, one
> could directly write 0, to denote a INTEGER_CST node with value 0.
Yes, that might be possible - though it will require more knowledge
in the pattern matcher (you also want to match '0'?) and the code
generator.
> e) There was a mention on the thread, regarding testing of patterns
> integrated into DSL. I wasn't able to understand that clearly. Could
> you explain that briefly ?
DSL? Currently I'd say it would be nice to make sure each pattern
is triggered by at least one GCC testcase - this requires looking
at a particular pass dump (that of forwprop or ccp are probably most suitable
as they are run very early). I mentioned the possibility to do offline
(thus not with C testcases) testing but that would require some tool
to do that and it would be correctness testing (some automatic proof
generation tool - ISTR academics have this kind of stuff). But that was
just an idea.
> Regarding gsoc proposal, I would like to align it on the following points:
> a) Pattern matching using decision tree
good.
> b) Generate GIMPLE folding patterns (tree-ssa-forwprop,
> tree-ssa-sccvn, gimple-fold)
I'd narrow it down a bit, you can optionally do more if time permits.
I'd say
0) add basic arithmetic identities (x + 0, x * 1, x / 1, etc., correctly
for all types - you can look into fold-const.c which handles all of them)
1) target as much as possible of the existing transforms in forwprop
2) pieces of fold-const.c: most interesting user is
gimple_fold_stmt_to_constant_1 (used by CCP and SCCVN and maybe
others)
3) fold-const.c's fold_comparison (and fold_binary parts handling
comparison codes), this is also necessary for quite important parts of
forwprop
> c) Generate GENERIC folding patterns (fold-const)
> Is that fine ? I would like to hear about any changes that you feel should be
> made.
This isn't easily distinguishable from b), instead we might want to
c) Remove parts of fold-const.c that can be subsumed by the GENERIC
variant of the folding patterns
> I have been mostly experimenting with the patch, by adding few patterns
> from tree-ssa-forwprop, and shall try to do pattern matching by a decision
> tree.
> Is there anything else you would like to suggest that
> can help me get comfortable with the code-base and the project-idea and
> could possibly help me strengthen my proposal ?
Nothing off my head right now - there is always bugzilla to look for
missed optimization bugs.
I've created svn//gcc.gnu.org/svn/gcc/branches/match-and-simplify now
and committed my current patch state. I've used gcc/ChangeLog.mas
to log changes to the branch.
Thanks,
Richard.
> Thanks and Regards,
> Prathamesh
>>
>> Richard.
>>
>>>> Thanks,
>>>> Richard.
>>>>
>>>>> I have a fluent grasp on C and working knowledge of flex, bison, C++,
>>>>> POSIX api, binutils and shell scripting (bash),
>>>>> I have been through most of dragon book, built an interpreter
>>>>> for a "c-like" language and a C-code generator for a toy language
>>>>> similar to python.
>>>>>
>>>>> As far as gcc goes, I had attended IIT Bombay gcc workshop 2013:
>>>>> http://www.cse.iitb.ac.in/grc/gcc-workshop-13/
>>>>> and have been through the online docs.
>>>>>
>>>>> I have a couple of one-liner patches committed:
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg00490.html
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg01144.html
>>>>>
>>>>> A few pending patches:
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg00143.html
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg00143.html
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg01220.html
>>>>> http://gcc.gnu.org/ml/gcc/2014-01/msg00268.html
>>>>>
>>>>> and a couple of rejected ones:
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg00957.html
>>>>> http://gcc.gnu.org/ml/gcc-patches/2014-02/msg01366.html
>>>>>
>>>>> Please do let me know what you think.
>>>>>
>>>>> Thanks and Regards,
>>>>> Prathamesh
>>>>>
>>>>>> Richard.
>>>>>>
>>>>>>> On the following test-case:
>>>>>>> int main()
>>>>>>> {
>>>>>>> int a, b, c;
>>>>>>> a = ~~~~b;
>>>>>>> c = ~-a;
>>>>>>> return 0;
>>>>>>> }
>>>>>>>
>>>>>>> The following GIMPLE is generated:
>>>>>>> main ()
>>>>>>> gimple_bind <
>>>>>>> int D.1748;
>>>>>>> int D.1749;
>>>>>>> int D.1750;
>>>>>>> int D.1751;
>>>>>>> int D.1752;
>>>>>>> int a;
>>>>>>> int b;
>>>>>>> int c;
>>>>>>>
>>>>>>> gimple_assign <var_decl, D.1749, b, NULL, NULL>
>>>>>>> gimple_assign <var_decl, a, D.1749, NULL, NULL>
>>>>>>> gimple_assign <plus_expr, c, a, -1, NULL>
>>>>>>> gimple_assign <integer_cst, D.1752, 0, NULL, NULL>
>>>>>>> gimple_return <D.1752>
>>>>>>>>
>>>>>>>
>>>>>>> The patch generates two tuples for a = ~~~~b,
>>>>>>> where only one is needed, and extra temporaries, which
>>>>>>> are not removed after the folding. How should I go about
>>>>>>> removing that (should I worry about that since subsequent passes,
>>>>>>> shall remove those ?)
>>>>>>>
>>>>>>> b) Some front-ends, C, for example, requires constant folding in
>>>>>>> certain places,
>>>>>>> like case statement. If constant folding is completely moved off to
>>>>>>> gimple,
>>>>>>> how shall this be handled ? Shall we gimplify the expression
>>>>>>> immediately if
>>>>>>> it's required to be evaluated ?
>>>>>>>
>>>>>>> Thanks and Regards,
>>>>>>> Prathamesh
