From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23612 invoked by alias); 11 Mar 2014 11:20:23 -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 23601 invoked by uid 89); 11 Mar 2014 11:20:22 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.1 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-wi0-f176.google.com Received: from mail-wi0-f176.google.com (HELO mail-wi0-f176.google.com) (209.85.212.176) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Tue, 11 Mar 2014 11:20:20 +0000 Received: by mail-wi0-f176.google.com with SMTP id hr14so693372wib.3 for ; Tue, 11 Mar 2014 04:20:17 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.180.165.238 with SMTP id zb14mr2658980wib.51.1394536817199; Tue, 11 Mar 2014 04:20:17 -0700 (PDT) Received: by 10.194.62.111 with HTTP; Tue, 11 Mar 2014 04:20:17 -0700 (PDT) In-Reply-To: References: Date: Tue, 11 Mar 2014 11:20: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/msg00166.txt.bz2 On Mon, Mar 10, 2014 at 7:29 PM, Prathamesh Kulkarni wrote: > Hi Richard, > Sorry for the late reply. I would like to have few clarifications > regarding the following points: > > a) Pattern matching: Currently, gimple_match_and_simplify() matches > patterns one-by-one. Could we use a decision tree to do the matching > instead (similar to insn-recog.c) ? > For the moment, let's consider pattern matching on only unary > expressions without valueize and predicates: > pattern 1: (negate (negate @0)) > pattern 2: (negate (bit_not @0)) > > from the two AST's corresponding to patterns (match::op), we can build > a decision tree: > Some-thing similar to: > NEGATE_EXPR > NEGATE_EXPR BIT_NOT_EXPR > > and then generate code corresponding to this decision tree in gimple-match.c > so the generated code should look something similar to: > > tree > gimple_match_and_simplify (enum tree_code code, tree type, tree op0, > gimple_seq *seq, tree (*valueize)(tree)) > { > if (code == NEGATE_EXPR) > { > tree captures[4] = {}; > if (TREE_CODE (op0) != SSA_NAME) > return NULL_TREE; > gimple def_stmt = SSA_NAM_DEF_STMT (op0); > if (!is_gimple_assign (def_stmt)) > return NULL_TREE; > tree op = gimple_assign_rhs1 (def_stmt); > if (gimple_assign_rhs_code (op) == NEGATE_EXPR) > { > /* pattern (negate (negate @0)) matched */ > } > else if (gimple_assign_rhs_code (op) == BIT_NOT_EXPR) > { > /* pattern (negate (bit_not_expr @0)) matched */ > } > else > return NULL_TREE; > } > else > return NULL_TREE; > } > > For commutative ops, the pattern can be duplicated by walking the > children of the node in reverse order. > (I am not exactly clear so far about representing binary operators in a decision > tree) Is this the right way to go ? I shall try to shortly post a patch that > implements this. Yes, that's the way to go (well, I'd even use a switch ()). > b) Targeting GENERIC, separating AST from gimple/generic: > For generating a GENERIC pattern should there be another pattern > something like match_and_simplify_generic ? Yes, there is an existing API in GCC for this that operates on GENERIC. It's fold_unary_loc, fold_binary_loc, fold_ternary_loc. The interface the GENERIC match_and_simplify variant provides should match that one. > Currently, the AST data structures (operand, expr, etc.) > are tied to gimple (gen_gimple_match, gen_gimple_transform). > We could also have similar functions: gen_generic_match, > gen_generic_transform for generating GENERIC ? Yeah, but I'm not sure if keeping the (virtual) methods for generating code makes much sense with a rewritten code generator. > Instead will it be better if we separate the AST > from target IR (generic/gimple) and make simplify a visitor on AST > (make simplify > abstract class, with simplify_generic and simplify_gimple visitor > classes that generate corresponding IR code) ? Yes. Keep in mind the current state of genmatch.c is "quick hack to make playing with the API side and with patterns possible" ;) > c) Shall it be a good idea in define_match , for > name to act as a substitute for pattern (similar to flex pattern > definitions), so the name can be used in bigger patterns ? Maybe, I suppose we'll see when adding more patterns. > d) This is silly, but maybe use constants to denote corresponding tree nodes ? > for example instead of { build_int_cst (integer_type_node, 0); }, one > could directly write 0, to denote a INTEGER_CST node with value 0. Yes, that might be possible - though it will require more knowledge in the pattern matcher (you also want to match '0'?) and the code generator. > e) There was a mention on the thread, regarding testing of patterns > integrated into DSL. I wasn't able to understand that clearly. Could > you explain that briefly ? DSL? Currently I'd say it would be nice to make sure each pattern is triggered by at least one GCC testcase - this requires looking at a particular pass dump (that of forwprop or ccp are probably most suitable as they are run very early). I mentioned the possibility to do offline (thus not with C testcases) testing but that would require some tool to do that and it would be correctness testing (some automatic proof generation tool - ISTR academics have this kind of stuff). But that was just an idea. > Regarding gsoc proposal, I would like to align it on the following points: > a) Pattern matching using decision tree good. > b) Generate GIMPLE folding patterns (tree-ssa-forwprop, > tree-ssa-sccvn, gimple-fold) I'd narrow it down a bit, you can optionally do more if time permits. I'd say 0) add basic arithmetic identities (x + 0, x * 1, x / 1, etc., correctly for all types - you can look into fold-const.c which handles all of them) 1) target as much as possible of the existing transforms in forwprop 2) pieces of fold-const.c: most interesting user is gimple_fold_stmt_to_constant_1 (used by CCP and SCCVN and maybe others) 3) fold-const.c's fold_comparison (and fold_binary parts handling comparison codes), this is also necessary for quite important parts of forwprop > c) Generate GENERIC folding patterns (fold-const) > Is that fine ? I would like to hear about any changes that you feel should be > made. This isn't easily distinguishable from b), instead we might want to c) Remove parts of fold-const.c that can be subsumed by the GENERIC variant of the folding patterns > I have been mostly experimenting with the patch, by adding few patterns > from tree-ssa-forwprop, and shall try to do pattern matching by a decision tree. > Is there anything else you would like to suggest that > can help me get comfortable with the code-base and the project-idea and > could possibly help me strengthen my proposal ? Nothing off my head right now - there is always bugzilla to look for missed optimization bugs. I've created svn//gcc.gnu.org/svn/gcc/branches/match-and-simplify now and committed my current patch state. I've used gcc/ChangeLog.mas to log changes to the branch. Thanks, Richard. > Thanks and Regards, > Prathamesh >> >> 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