On Tue, Mar 11, 2014 at 12:20 PM, Richard Biener
<richard.guent...@gmail.com> wrote:
> 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.
There are two meta-bugs (that link specific ones) for this area:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15459 and
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19986
Richard.
> 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
