Re: [gsoc 2014] moving fold-const patterns to gimple

[Prathamesh Kulkarni <bilbotheelffriend@gmail.com>]

On Thu, Mar 6, 2014 at 6:13 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, Mar 6, 2014 at 1:11 PM, Prathamesh Kulkarni
> <bilbotheelffriend@gmail.com> wrote:
>> On Mon, Mar 3, 2014 at 3:32 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Sun, Mar 2, 2014 at 9:13 PM, Prathamesh Kulkarni
>>> <bilbotheelffriend@gmail.com> wrote:
>>>> Hi, I am an undergraduate student at University of Pune, India, and would
>>>> like to work on moving folding patterns from fold-const.c to gimple.
>>>
>>> I've seen the entry on our GSoC project page and edited it to discourage
>>> people from working on that line.  See
>>>
>>> http://gcc.gnu.org/ml/gcc/2014-02/msg00516.html
>>>
>>> for why.  I think that open-coding the transforms isn't maintainable
>>> in the long run.
>>>
>>>> If I understand correctly, constant folding is done on GENERIC (by
>>>> routines in fold-const.c), and then GENERIC is lowered to GIMPLE. The
>>>> purpose of this project,
>>>> is to have constant folding to be performed on GIMPLE instead (in
>>>> gimple-fold.c?)
>>>>
>>>> I have a few elementary questions to ask:
>>>>
>>>> a) A contrived example:
>>>> Consider a C expression, a = ~0 (assume a is int)
>>>> In GENERIC, this would roughly be represented as:
>>>> modify_expr<var_decl "a", <bit_not_expr<integer_cst 0>>>
>>>> this gets folded to:
>>>> modify_expr<var_decl "a", integer_cst -1>
>>>> and the corresponding gimple tuple generated is (-fdump-tree-gimple-raw):
>>>> gimple_assign <integer_cst, x, -1, NULL, NULL>
>>>>
>>>> So, instead of folding performed on GENERIC, it should be
>>>> done on GIMPLE.
>>>> So a tuple like the following should be generated by gimplification:
>>>> <bit_not_expr, a, 0, NULL, NULL>
>>>> and folded to (by call to fold_stmt):
>>>> <integer_cst, a, -1, NUL, NULL>
>>>> Is this the expected behavior ?
>>>>
>>>> I have attached a rough/incomplete patch (only stage1 compiled cc1), that
>>>> does the following foldings on bit_not_expr:
>>>> a) ~ INTEGER_CST => folded
>>>> b) ~~x => x
>>>> c) ~(-x) => x - 1
>>>> (For the moment, I put case BIT_NOT_EXPR: return NULL_TREE
>>>> in fold_unary_loc to avoid folding in GENERIC on bit_not_expr)
>>>>
>>>> Is the patch going in the correct direction ? Or have I completely missed
>>>> the point here ? I would be grateful to receive suggestions, and start working
>>>> on a fair patch.
>>>
>>> I think you implement what was suggested by Kai (and previously
>>> by me and Andrew, before I changed my mind).
>>>
>> Hi Richard,
>> Thanks for your reply and for pointing me out to this thread
>> http://gcc.gnu.org/ml/gcc/2014-02/msg00516.html
>>
>> I agree it's better to generate patterns from a meta-description
>> instead of hand-coding, and the idea seems interesting to me.
>>
>> I was playing around with the patch and did few trivial modifications
>> (please find the patch attached):
>> a) use obstack in parse_c_expr.
>>
>> b) use @ inside c code, instead of directly writing captures
>> (like $<num> in bison):
>> example:
>> /* Match and simplify CST + CST to CST'.  */
>> (define_match_and_simplify baz
>>   (PLUS_EXPR INTEGER_CST_P@0 INTEGER_CST_P@1)
>>   { int_const_binop (PLUS_EXPR, @0, @1); })
>>
>> c) Not sure if this is a good idea, conditional matching.
>> for example:
>> /* match (A * B) and simplify to
>>  * B if integer_zerop B is true ( A * 0 => 0)
>>  * A if integer_onep B is true  (A * 1 => A)
>>  */
>> (define_match_and_simplify multexpr
>>   (MULT_EXPR integral_op_p@0 integral_op_p@1)
>>   [
>>     (integer_zerop@1 @1)
>>     (integer_onep@1  @0)
>>   ])
>> Maybe condition can be generalized to be any operand instead of
>> testing predicate on capture operand ?
>>
>> I would be grateful to receive some direction for working on this project.
>> From the thread, I see a few possibilities:
>> a) Moving patterns from tree-ssa-forwprop
>> b) Extending the DSL (handle commutative operators, conditionally
>> enabling patterns ?)
>> c) Targeting GENERIC (Generating patterns in fold-const.c from the
>> description ?)
>> d) This is a bit silly, but maybe perform more error checking ?
>> for example the following pattern is currently accepted:
>> (define_match px
>>   (PLUS_EXPR @0 @1 @2))
>
> Note that I'm currently still hacking on this (see attachment for what
> I have right now).  The grammar is still in flux but I'd like to keep it
> simple for now (so no conditional replacement).
>
> I have changed quite some bits so d) should be easily possible
> now and I've done b) from your list as well.
>
> For the moment I'm trying to see whether the design is sound,
> especially the GCC-side APIs.  I hope to finish this this week
> (fingers crossing), and also settle on the syntax (see variants in
> the .pd).
>
> As for opening this up for a GSOC project to "finish" or work on
> that's a good idea.  In addition to a) Moving patterns from tree-ssa-forwprop
> which I think is the place where its easiest to plug this in without
> regressions it would be nice if you could work on e) Generate a
> state machine for the matching part, instead of trying one pattern
> after each other (see how insn-recog.c is produced).  I hope to
> cleanup the parser AST implementation a bit so that b) handling
> of commutative ops is possible as a pattern-duplication step.
> I've already added the ability to conditionally enable patterns.
> Doing c) would also be nice - another target besides the patterns
> in forwprop is the simplifications done by fold_comparison
> (and fold_binary on comparison ops) - because forwprop depends
> on those.
>
>> I wanted to apply to gsoc for this project and I was wondering if you
>> would you be willing to mentor me if I did?
>
> Sure.  I'd say e) and doing the related (commutative) AST ops
> would qualify best.  Not sure if mechanically moving patterns
> would qualify alone.
>
Thanks, I am eager to work on it. I shall get back within
a couple of days, with something to show.
Thanks once again.
> 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