On Thu, Mar 6, 2014 at 7:17 PM, Prathamesh Kulkarni <bilbotheelffri...@gmail.com> wrote: > On Thu, Mar 6, 2014 at 6:13 PM, Richard Biener > <richard.guent...@gmail.com> wrote: >> On Thu, Mar 6, 2014 at 1:11 PM, Prathamesh Kulkarni >> <bilbotheelffri...@gmail.com> wrote: >>> On Mon, Mar 3, 2014 at 3:32 PM, Richard Biener >>> <richard.guent...@gmail.com> wrote: >>>> On Sun, Mar 2, 2014 at 9:13 PM, Prathamesh Kulkarni >>>> <bilbotheelffri...@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