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

[Richard Biener <richard dot guenther at gmail dot com>]

On Thu, Mar 6, 2014 at 7:17 PM, Prathamesh Kulkarni
<bilbotheelffriend@gmail.com> wrote:
> 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.

You can certainly experiment a bit, but I'm still in hacking mode
so anything you produce now will conflict with changes I am doing.
So eventually you want to wait a bit until I settled with the internal
interfacing ;)

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