On Fri, Mar 7, 2014 at 2:38 PM, Richard Biener <richard.guent...@gmail.com> wrote: > 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 ;) 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. b) Targeting GENERIC, separating AST from gimple/generic: For generating a GENERIC pattern should there be another pattern something like match_and_simplify_generic ? 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 ? 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) ? c) Shall it be a good idea in define_match <name> <pattern>, for name to act as a substitute for pattern (similar to flex pattern definitions), so the name can be used in bigger 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. 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 ? Regarding gsoc proposal, I would like to align it on the following points: a) Pattern matching using decision tree b) Generate GIMPLE folding patterns (tree-ssa-forwprop, tree-ssa-sccvn, gimple-fold) c) Generate GENERIC folding patterns (fold-const) Is that fine ? I would like to hear about any changes that you feel should be made. 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 ? 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 <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