From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 6242 invoked by alias); 14 Mar 2014 15:31:12 -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 6225 invoked by uid 89); 14 Mar 2014 15:31:11 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.5 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-ob0-f181.google.com Received: from mail-ob0-f181.google.com (HELO mail-ob0-f181.google.com) (209.85.214.181) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Fri, 14 Mar 2014 15:31:08 +0000 Received: by mail-ob0-f181.google.com with SMTP id wp4so2657562obc.26 for ; Fri, 14 Mar 2014 08:31:06 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.60.44.8 with SMTP id a8mr7292315oem.19.1394811066338; Fri, 14 Mar 2014 08:31:06 -0700 (PDT) Received: by 10.183.16.164 with HTTP; Fri, 14 Mar 2014 08:31:06 -0700 (PDT) In-Reply-To: References: Date: Fri, 14 Mar 2014 15:31:00 -0000 Message-ID: Subject: Re: [gsoc 2014] moving fold-const patterns to gimple From: Prathamesh Kulkarni To: Richard Biener Cc: gcc Content-Type: multipart/mixed; boundary=001a11c2e45823d80a04f492c2e1 X-IsSubscribed: yes X-SW-Source: 2014-03/txt/msg00208.txt.bz2 --001a11c2e45823d80a04f492c2e1 Content-Type: text/plain; charset=ISO-8859-1 Content-length: 13341 On Thu, Mar 13, 2014 at 4:44 PM, Richard Biener wrote: > On Tue, Mar 11, 2014 at 12:20 PM, Richard Biener > wrote: >> 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. > > There are two meta-bugs (that link specific ones) for this area: > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15459 and > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19986 > Hi Richard, Thanks for pointing out the links. I will try and solve the mentioned bugs I had a look at PR 14753 (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753) from the first link. I have tried to implement those transforms (attached patch, stage-1 compiled). I have written the transforms to operate on GENERIC. Is that correct ? The patterns mentioned in the links were: a) (X >> CST1) >= CST2 -> X >= CST2 << CST1 however, an expression Y >= CST gets folded to Y > CST - 1 so the transform I wrote: (X >> CST1) > CST2 -> X > CST2 << CST1 b) (X & ~CST) == 0 -> X <= CST However ~CST gets folded. so the transform I wrote: (X & CST) == 0 -> X <= ~CST (~CST is folded by calling fold_unary) After applying the patch, I got this output for the test-case in the PR (169t.optimized): ;; Function foo (foo, funcdef_no=0, decl_uid=1745, symbol_order=0) foo (unsigned int a) { : if (a_1(D) > 8) goto ; else goto ; : bar (); : return; } ;; Function baz (baz, funcdef_no=1, decl_uid=1748, symbol_order=1) baz (unsigned int a) { : if (a_1(D) <= 7) goto ; else goto ; : bar (); : return; } I have two very fundamental doubts: a) It appears to me that folding is performed at all levels: GENERIC (fold-const), GIMPLE (gimple-fold) and RTL (simplify-rtx). Is that because, lowering IR may introduce opportunities for folding ? So it is needed to be performed at each level ? Also since RTL expansion is semi-automatic (by that I mean custom C code used in .md files to construct RTL), the RTL insns may require folding ? b) Why do we want to target GENERIC too ? If I understand correctly, currently gimple folding is done by genericizing (fold_stmt) ? Why not move off folding entirely to GIMPLE ? This shall probably be an issue, when front-ends (C for example) require to perform constant folding (for example expression in case statement), so the required expression needs to be gimplified for evaluation. So by generating both GENERIC and GIMPLE from a meta-description, we avoid the cost of genericizing (as it's currently done), and gimplifying an expression for evaluation (if all folding is moved to gimple) ? Or have I completely missed the point here ? Regarding the proposal, I have the following tentative timeline in my mind: Present - May 18: Get familiar with folding patterns (in fold-const, tree-ssa-forwprop), solve bugs mentioned in the links, start moving simple patterns to match.pd May 19 - June 27: a) Implement pattern matching using decision tree. b) Support generating gimple and generic patterns (gimple_match_and_simplify, generic_match_and_simplify) c) Basic identities (for example the ones in fold_binary_loc:case PLUS_EXPR and similar) for all types. d) fold_comparison patterns and fold_binary handling of comparison codes. June 28 - July 16: e) Patterns from tree-ssa-forwprop July 16 - August 11: f) Patterns from fold-const.c August 12 - August 18: Fixing bugs, documentation, testing. Also I would like to put somewhere "extending meta-description", if required for writing patterns. I would like to put "extending the meta-description", if it would be needed while writing patterns. I assume it shall take time to move most of patterns from tree-ssa-forwprop and fold-const so I put them as single tasks in respective time periods. If time permits, I would do more. I am ready to commit 60-65 hours per week for the project. I shall get a draft of the proposal ready within a couple of days. Thanks and Regards, Prathamesh > Richard. > >> 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 --001a11c2e45823d80a04f492c2e1 Content-Type: text/x-patch; charset=US-ASCII; name="14753.patch" Content-Disposition: attachment; filename="14753.patch" Content-Transfer-Encoding: base64 X-Attachment-Id: f_hsrmd7j70 Content-length: 2270 SW5kZXg6IGdjYy9mb2xkLWNvbnN0LmMKPT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PQotLS0gZ2NjL2ZvbGQtY29uc3QuYwkocmV2aXNpb24gMjA4NTM5KQorKysg Z2NjL2ZvbGQtY29uc3QuYwkod29ya2luZyBjb3B5KQpAQCAtNjgsNiArNjgs NyBAQCBhbG9uZyB3aXRoIEdDQzsgc2VlIHRoZSBmaWxlIENPUFlJTkczLgog I2luY2x1ZGUgImdpbXBsaWZ5LmgiCiAjaW5jbHVkZSAidHJlZS1kZmEuaCIK ICNpbmNsdWRlICJoYXNoLXRhYmxlLmgiICAvKiBSZXF1aXJlZCBmb3IgRU5B QkxFX0ZPTERfQ0hFQ0tJTkcuICAqLworI2luY2x1ZGUgInRyZWUtcHJldHR5 LXByaW50LmgiCiAKIC8qIE5vbnplcm8gaWYgd2UgYXJlIGZvbGRpbmcgY29u c3RhbnRzIGluc2lkZSBhbiBpbml0aWFsaXplcjsgemVybwogICAgb3RoZXJ3 aXNlLiAgKi8KQEAgLTk2OTgsNiArOTY5OSwzMyBAQCBmb2xkX2NvbXBhcmlz b24gKGxvY2F0aW9uX3QgbG9jLCBlbnVtIHRyCiAJCQkJICAgICAgIGZvbGRf Y29udmVydF9sb2MgKGxvYywgY21wX3R5cGUsIGFyZzEpKSk7CiAgICAgfQog CisgIC8qIEZvbGQgKFggPj4gQ1NUMSkgPiBDU1QyIC0+IFggPiBDU1QyIDw8 IENTVDEgKi8gCisgIGlmIChUUkVFX0NPREUgKGFyZzApID09IFJTSElGVF9F WFBSICYmIGNvZGUgPT0gR1RfRVhQUikKKyAgICB7CisgICAgICB0cmVlIHZh ciA9IFRSRUVfT1BFUkFORCAoYXJnMCwgMCk7CisgICAgICB0cmVlIGNzdDEg PSBUUkVFX09QRVJBTkQgKGFyZzAsIDEpOworICAgICAgaWYgKChUUkVFX0NP REUgKGNzdDEpID09IElOVEVHRVJfQ1NUIHx8IFRSRUVfQ09ERSAoYXJnMSkg PT0gVkVDVE9SX0NTVCkKKwkgICYmIChUUkVFX0NPREUgKGFyZzEpID09IElO VEVHRVJfQ1NUIHx8IFRSRUVfQ09ERSAoYXJnMSkgPT0gVkVDVE9SX0NTVCkp CisJcmV0dXJuIGZvbGRfYnVpbGQyX2xvYyAobG9jLCBHVF9FWFBSLCB0eXBl LCB2YXIsIAorCQkJCWZvbGRfY29udmVydF9sb2MgKGxvYywgVFJFRV9UWVBF ICh2YXIpLAorCQkJCQkJICBpbnRfY29uc3RfYmlub3AgKExTSElGVF9FWFBS LCBjc3QxLCBhcmcxKSkpOworICAgIH0KKworICAvKiBGb2xkIChYICYgQ1NU KSA9PSAwIC0+IFggPD0gfkNTVCAqLworICBpZiAoVFJFRV9DT0RFIChhcmcw KSA9PSBCSVRfQU5EX0VYUFIgJiYgY29kZSA9PSBFUV9FWFBSICYmIGludGVn ZXJfemVyb3AgKGFyZzEpKQorICAgIHsgCisgICAgICB0cmVlIHZhciA9IFRS RUVfT1BFUkFORCAoYXJnMCwgMCk7CisgICAgICB0cmVlIGNzdCA9IFRSRUVf T1BFUkFORCAoYXJnMCwgMSk7CisgICAgICB0cmVlIGJpdF9ub3RfZXhwcjsg CisKKyAgICAgIGlmIChUUkVFX0NPREUgKGNzdCkgPT0gSU5URUdFUl9DU1Qg fHwgVFJFRV9DT0RFIChjc3QpID09IFZFQ1RPUl9DU1QpCisgICAgICAgIHsK KyAgICAgICAgICBiaXRfbm90X2V4cHIgPSBmb2xkX3VuYXJ5IChCSVRfTk9U X0VYUFIsIFRSRUVfVFlQRSAoY3N0KSwgY3N0KTsgIAorCSAgcmV0dXJuIGZv bGRfYnVpbGQyX2xvYyAobG9jLCBMRV9FWFBSLCB0eXBlLCB2YXIsCisJCQkJ ICBmb2xkX2NvbnZlcnRfbG9jIChsb2MsIFRSRUVfVFlQRSAodmFyKSwgYml0 X25vdF9leHByKSk7CisJfQorICAgIH0KKyAgCiAgIHJldHVybiBOVUxMX1RS RUU7CiB9CiAK --001a11c2e45823d80a04f492c2e1--