From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 25633 invoked by alias); 7 Mar 2014 09:08:33 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 25620 invoked by uid 89); 7 Mar 2014 09:08:32 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.2 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-wg0-f45.google.com Received: from mail-wg0-f45.google.com (HELO mail-wg0-f45.google.com) (74.125.82.45) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Fri, 07 Mar 2014 09:08:30 +0000 Received: by mail-wg0-f45.google.com with SMTP id l18so4119839wgh.28 for ; Fri, 07 Mar 2014 01:08:26 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.194.178.8 with SMTP id cu8mr12587521wjc.77.1394183306783; Fri, 07 Mar 2014 01:08:26 -0800 (PST) Received: by 10.194.62.111 with HTTP; Fri, 7 Mar 2014 01:08:26 -0800 (PST) In-Reply-To: References: Date: Fri, 07 Mar 2014 09:08:00 -0000 Message-ID: Subject: Re: [gsoc 2014] moving fold-const patterns to gimple From: Richard Biener To: Prathamesh Kulkarni Cc: gcc Content-Type: text/plain; charset=ISO-8859-1 X-IsSubscribed: yes X-SW-Source: 2014-03/txt/msg00121.txt.bz2 On Thu, Mar 6, 2014 at 7:17 PM, Prathamesh Kulkarni wrote: > On Thu, Mar 6, 2014 at 6:13 PM, Richard Biener > wrote: >> On Thu, Mar 6, 2014 at 1:11 PM, Prathamesh Kulkarni >> wrote: >>> On Mon, Mar 3, 2014 at 3:32 PM, Richard Biener >>> wrote: >>>> On Sun, Mar 2, 2014 at 9:13 PM, Prathamesh Kulkarni >>>> 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>> >>>>> this gets folded to: >>>>> modify_expr >>>>> and the corresponding gimple tuple generated is (-fdump-tree-gimple-raw): >>>>> gimple_assign >>>>> >>>>> So, instead of folding performed on GENERIC, it should be >>>>> done on GIMPLE. >>>>> So a tuple like the following should be generated by gimplification: >>>>> >>>>> and folded to (by call to fold_stmt): >>>>> >>>>> 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 $ 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 >>>>> gimple_assign >>>>> gimple_assign >>>>> gimple_assign >>>>> gimple_return >>>>>> >>>>> >>>>> 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