This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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,
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

Attachment: genmatch
Description: Binary data


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]