* [gsoc 2014] moving fold-const patterns to gimple
@ 2014-03-02 20:13 Prathamesh Kulkarni
2014-03-03 10:02 ` Richard Biener
0 siblings, 1 reply; 22+ messages in thread
From: Prathamesh Kulkarni @ 2014-03-02 20:13 UTC (permalink / raw)
To: gcc, ktietz70
[-- Attachment #1: Type: text/plain, Size: 2566 bytes --]
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.
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.
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
[-- Attachment #2: bit_not_expr.patch --]
[-- Type: text/x-patch, Size: 2757 bytes --]
Index: gcc/fold-const.c
===================================================================
--- gcc/fold-const.c (revision 208111)
+++ gcc/fold-const.c (working copy)
@@ -8313,6 +8313,7 @@ fold_unary_loc (location_t loc, enum tre
return NULL_TREE;
case BIT_NOT_EXPR:
+ return NULL_TREE;
if (TREE_CODE (arg0) == INTEGER_CST)
return fold_not_const (arg0, type);
else if (TREE_CODE (arg0) == BIT_NOT_EXPR)
Index: gcc/gimple-fold.c
===================================================================
--- gcc/gimple-fold.c (revision 208111)
+++ gcc/gimple-fold.c (working copy)
@@ -352,6 +352,68 @@ maybe_fold_reference (tree expr, bool is
return NULL_TREE;
}
+static tree
+fold_not_const (const_tree arg0, tree type)
+{
+ double_int val;
+
+ gcc_assert (TREE_CODE (arg0) == INTEGER_CST);
+
+ val = ~tree_to_double_int (arg0);
+ return force_fit_type_double (type, val, 0, TREE_OVERFLOW (arg0));
+}
+
+static tree
+fold_gimple_bit_not_expr (gimple_stmt_iterator *si)
+{
+ gimple stmt = gsi_stmt (*si);
+ tree rhs = gimple_assign_rhs1 (stmt);
+ tree result = NULL_TREE;
+ enum tree_code code = TREE_CODE (rhs);
+ tree type = gimple_expr_type (stmt);
+ gimple_stmt_iterator temp_iter;
+
+ if (code == INTEGER_CST)
+ return fold_not_const (rhs, type);
+
+ temp_iter = *si;
+ gsi_prev (&temp_iter);
+ gimple prev = gsi_stmt (temp_iter);
+
+ if (prev)
+ {
+ if (gimple_code (prev) != GIMPLE_ASSIGN)
+ return NULL_TREE;
+
+ switch (gimple_assign_rhs_code (prev))
+ {
+ case BIT_NOT_EXPR: // x = ~~y => x = y
+ if (gimple_assign_lhs (prev) == rhs)
+ {
+ result = gimple_assign_rhs1 (prev);
+ gsi_remove (&temp_iter, true);
+ return result;
+ }
+ return NULL_TREE;
+
+ case NEGATE_EXPR: // x = ~-y => x = y - 1
+ if (INTEGRAL_TYPE_P (type))
+ {
+ result = fold_build2 (MINUS_EXPR, type,
+ fold_convert (type, gimple_assign_rhs1 (prev)),
+ build_int_cst (type, 1));
+ gsi_remove (&temp_iter, true);
+ return result;
+ }
+ return NULL_TREE;
+
+ default:
+ return NULL_TREE;
+ }
+ }
+
+ return NULL_TREE;
+}
/* Attempt to fold an assignment statement pointed-to by SI. Returns a
replacement rhs for the statement or NULL_TREE if no simplification
@@ -458,8 +520,10 @@ fold_gimple_assign (gimple_stmt_iterator
case GIMPLE_UNARY_RHS:
{
tree rhs = gimple_assign_rhs1 (stmt);
-
- result = fold_unary_loc (loc, subcode, gimple_expr_type (stmt), rhs);
+ if (subcode == BIT_NOT_EXPR)
+ result = fold_gimple_bit_not_expr (si);
+ else
+ result = fold_unary_loc (loc, subcode, gimple_expr_type (stmt), rhs);
if (result)
{
/* If the operation was a conversion do _not_ mark a
^ permalink raw reply [flat|nested] 22+ messages in thread* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-02 20:13 [gsoc 2014] moving fold-const patterns to gimple Prathamesh Kulkarni @ 2014-03-03 10:02 ` Richard Biener 2014-03-06 12:11 ` Prathamesh Kulkarni 0 siblings, 1 reply; 22+ messages in thread From: Richard Biener @ 2014-03-03 10:02 UTC (permalink / raw) To: Prathamesh Kulkarni; +Cc: gcc, Kai Tietz On Sun, Mar 2, 2014 at 9:13 PM, Prathamesh Kulkarni <bilbotheelffriend@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). 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-03 10:02 ` Richard Biener @ 2014-03-06 12:11 ` Prathamesh Kulkarni 2014-03-06 12:43 ` Richard Biener 0 siblings, 1 reply; 22+ messages in thread From: Prathamesh Kulkarni @ 2014-03-06 12:11 UTC (permalink / raw) To: Richard Biener, gcc [-- Attachment #1: Type: text/plain, Size: 6094 bytes --] On Mon, Mar 3, 2014 at 3:32 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Sun, Mar 2, 2014 at 9:13 PM, Prathamesh Kulkarni > <bilbotheelffriend@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)) 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? 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 [-- Attachment #2: genmatch.patch --] [-- Type: text/x-patch, Size: 16661 bytes --] Index: gcc/genmatch.c =================================================================== --- gcc/genmatch.c (revision 0) +++ gcc/genmatch.c (working copy) @@ -0,0 +1,610 @@ + +/* Grammar + + capture = '@' number + op = predicate | expr [capture] + match = 'define_match' name expr + c_expr = '{' ... '}' + genexpr = '(' code genop... ')' + genop = capture | genexpr | c_expr + transform = 'define_match_and_transform' name expr genop + + Match (A + B) - B + (define_match plusminus + (PLUS_EXPR (MINUS_EXPR integral_op_p@0 @1) @1)) + + Match and simplify (A + B) - B -> A + (define_match_and_simplify foo + (PLUS_EXPR (MINUS_EXPR integral_op_p@0 @1) @1) + @0) + + Match and simplify (CST + A) + CST to CST' + A + (define_match_and_simplify bar + (PLUS_EXPR INTEGER_CST_P@0 (PLUS_EXPR @1 INTEGER_CST_P@2)) + (PLUS_EXPR { int_const_binop (PLUS_EXPR, captures[0], captures[2]); } @1)) +*/ + +#include "bconfig.h" +#include "system.h" +#include "coretypes.h" +#include <cpplib.h> +#include "errors.h" +#include "hashtab.h" +#include "vec.h" + +enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR, OP_COND }; + +struct operand { + operand (enum op_type type_) : type (type_) {} + enum op_type type; + virtual void gen_gimple_match (FILE *f, const char *) = 0; + virtual void gen_gimple_transform (FILE *f) = 0; +}; + +struct predicate : public operand +{ + predicate (const char *ident_) : operand (OP_PREDICATE), ident (ident_) {} + const char *ident; + virtual void gen_gimple_match (FILE *f, const char *); + virtual void gen_gimple_transform (FILE *) { gcc_unreachable (); } +}; + +struct expr : public operand +{ + expr (const char *operation_) + : operand (OP_EXPR), operation (operation_), num_ops (0) {} + void append_op (operand *op) { ops[num_ops++] = op; } + const char *operation; + unsigned num_ops; + operand *ops[4]; + virtual void gen_gimple_match (FILE *f, const char *); + virtual void gen_gimple_transform (FILE *f); +}; + +struct c_expr : public operand +{ + c_expr (const char *code_) + : operand (OP_EXPR), code (code_) {} + const char *code; + virtual void gen_gimple_match (FILE *, const char *) { gcc_unreachable (); } + virtual void gen_gimple_transform (FILE *f); +}; + +struct capture : public operand +{ + capture (const char *where_, operand *what_) + : operand (OP_CAPTURE), where (where_), what (what_) {} + const char *where; + operand *what; + virtual void gen_gimple_match (FILE *f, const char *); + virtual void gen_gimple_transform (FILE *f); +}; + +struct condition_pair { + condition_pair (struct predicate *pred_, struct operand *op_, struct capture *capt_) + : pred (pred_), op (op_), capt (capt_) {} + struct predicate *pred; + struct operand *op; + struct capture *capt; +}; + +struct condition : public operand +{ + condition (const vec<struct condition_pair>& conds_) + : operand (OP_COND), conds (conds_) {} + vec<struct condition_pair> conds; + virtual void gen_gimple_match (FILE *f, const char *c) {} + virtual void gen_gimple_transform (FILE *f); +}; + +struct match { + match (const char *name_, struct operand *op_); + const char *name; + struct operand *op; + void gen_gimple_match (FILE *f); + virtual void gen_gimple (FILE *f) { gen_gimple_match (f); } +}; + +struct simplify : public match { + simplify (const char *name_, struct operand *op_, struct operand *op2_) + : match (name_, op_), op2 (op2_) {} + struct operand *op2; + virtual void gen_gimple (FILE *f); +}; + +match::match (const char *name_, operand *op_) +{ + name = name_; + op = op_; +} + +void +predicate::gen_gimple_match (FILE *f, const char *op) +{ + fprintf (f, "if (!%s (%s)) return false;\n", ident, op); +} + +void +expr::gen_gimple_match (FILE *f, const char *name) +{ + fprintf (f, "{\n"); + fprintf (f, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", name); + fprintf (f, "if (is_gimple_assign (def_stmt)\n" + "\t&& gimple_assign_rhs_code (def_stmt) == %s)\n", operation); + fprintf (f, " {\n"); + fprintf (f, "gcc_assert (gimple_num_ops (def_stmt) == %d + 1);\n", num_ops); + for (unsigned i = 0; i < num_ops; ++i) + { + fprintf (f, " {\n"); + fprintf (f, " tree op = gimple_assign_rhs%d (def_stmt);\n", i + 1); + fprintf (f, " if (valueize && TREE_CODE (op) == SSA_NAME)\n"); + fprintf (f, " {\n"); + fprintf (f, " op = valueize (op);\n"); + fprintf (f, " if (!op) return false;\n"); + fprintf (f, " }\n"); + ops[i]->gen_gimple_match (f, "op"); + fprintf (f, " }\n"); + } + fprintf (f, "}\n"); + fprintf (f, "}\n"); +} + +void +expr::gen_gimple_transform (FILE *f) +{ + fprintf (f, "({\n"); + fprintf (f, " if (!seq) return NULL_TREE;\n"); + fprintf (f, " tree ops[%d];\n", num_ops); + for (unsigned i = 0; i < num_ops; ++i) + { + fprintf (f, " ops[%u] = ", i); + ops[i]->gen_gimple_transform (f); + fprintf (f, ";\n"); + } + fprintf (f, " tree res = make_ssa_name (TREE_TYPE (ops[0]), NULL);\n" + " gimple stmt = gimple_build_assign_with_ops (%s, res", + operation); + for (unsigned i = 0; i < num_ops; ++i) + fprintf (f, ", ops[%u]", i); + fprintf (f, ");\n"); + fprintf (f, " gimple_seq_add_stmt_without_update (seq, stmt);\n"); + fprintf (f, " res;\n"); + fprintf (f, "})"); +} + +void +c_expr::gen_gimple_transform (FILE *f) +{ + fputs (code, f); +} + +void +capture::gen_gimple_transform (FILE *f) +{ + fprintf (f, "captures[%s]", this->where); +} + +void +capture::gen_gimple_match (FILE *f, const char *op) +{ + if (this->what) + this->what->gen_gimple_match (f, op); + fprintf (f, "if (!captures[%s])\n" + " captures[%s] = %s;\n" + "else if (captures[%s] != %s)\n" + " return false;", this->where, this->where, op, this->where, op); +} + + + +void +match::gen_gimple_match (FILE *f) +{ + fprintf (f, "bool\nmatch_%s (tree name, tree *captures, tree (*valueize)(tree))\n" + "{\n", this->name); + this->op->gen_gimple_match (f, "name"); + fprintf (f, " return true;\n"); + fprintf (f, "}\n"); +} + +void +condition::gen_gimple_transform (FILE *f) +{ + unsigned i; + unsigned len = this->conds.length (); + + fprintf (f, "({ tree op = NULL_TREE;\n"); + + fprintf (f, "if (%s (", this->conds[0].pred->ident); + this->conds[0].capt->gen_gimple_transform (f); + fprintf (f, "))"); + fprintf (f, "op = "); + this->conds[0].op->gen_gimple_transform (f); + fprintf (f, ";\n"); + + for (i = 1; i < len; i++) + { + fprintf (f, "else if (%s (", this->conds[i].pred->ident); + this->conds[i].capt->gen_gimple_transform (f); + fprintf (f, "))"); + fprintf (f, "op = "); + this->conds[i].op->gen_gimple_transform (f); + fprintf (f, ";\n"); + } + fprintf (f, "op;})\n"); +} + +void +simplify::gen_gimple (FILE *f) +{ + fprintf (f, "static "); + this->gen_gimple_match (f); + fprintf (f, "static tree\n" + "simplify_%s (tree name, gimple_seq *seq, tree (*valueize)(tree))\n" + "{\n", this->name); + fprintf (f, " tree captures[4] = {};\n" + " if (!match_%s (name, captures, valueize)) return NULL_TREE;\n", + this->name); + fprintf (f, " return "); + this->op2->gen_gimple_transform (f); + fprintf (f, ";\n}\n"); +} + +static const cpp_token * +next (cpp_reader *r) +{ + const cpp_token *token; + do + { + token = cpp_get_token (r); + } + while (token->type == CPP_PADDING + && token->type != CPP_EOF); +#if 0 + /* DEBUG */ + if (token->type != CPP_EOF) + printf ("got token '%s'\n", cpp_token_as_text (r, token)); +#endif + return token; +} + +static const cpp_token * +peek (cpp_reader *r) +{ + const cpp_token *token; + unsigned i = 0; + do + { + token = cpp_peek_token (r, i++); + } + while (token->type == CPP_PADDING); +#if 0 + /* DEBUG */ + if (token->type != CPP_EOF) + printf ("next token '%s'\n", cpp_token_as_text (r, token)); +#endif + return token; +} + +static bool +is_ident (const cpp_token *token, const char *id) +{ + return strcmp ((const char *)CPP_HASHNODE (token->val.node.node)->ident.str, + id) == 0; +} + +static size_t +round_alloc_size (size_t s) +{ + return s; +} + + +static const cpp_token * +expect (cpp_reader *r, enum cpp_ttype tk) +{ + const cpp_token *token = next (r); + if (token->type != tk) + fatal ("error: expected %s, got %s", + cpp_type2name (tk, 0), cpp_type2name (token->type, 0)); + + return token; +} + +static void +eat_token (cpp_reader *r, enum cpp_ttype tk) +{ + expect (r, tk); +} + +const char * +get_string (cpp_reader *r) +{ + const cpp_token *token = expect (r, CPP_STRING); + return (const char *)token->val.str.text; +} + +const char * +get_ident (cpp_reader *r) +{ + const cpp_token *token = expect (r, CPP_NAME); + return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str; +} + +const char * +get_number (cpp_reader *r) +{ + const cpp_token *token = expect (r, CPP_NUMBER); + return (const char *)token->val.str.text; +} + +static const char * +parse_operation (cpp_reader *r) +{ + return get_ident (r); +} + +static struct operand * parse_op (cpp_reader *r); + +/* Parse + expr = operation op... */ +static struct operand * +parse_expr (cpp_reader *r) +{ + expr *e = new expr (parse_operation (r)); + do + { + const cpp_token *token = peek (r); + if (token->type == CPP_CLOSE_PAREN) + return e; + e->append_op (parse_op (r)); + } + while (1); + return e; +} + +static struct operand * +parse_capture (cpp_reader *r, operand *op) +{ + eat_token (r, CPP_ATSIGN); + return new capture (get_number (r), op); +} + + +static operand * +parse_c_expr (cpp_reader *r) +{ + /* ??? Use an obstack to build the string. */ + const cpp_token *token; + char *code; + struct obstack ob; + + obstack_init (&ob); + obstack_grow (&ob, "({", 2); + + do + { + token = next (r); + char *tk = (char *)cpp_token_as_text (r, token); + + if (token->flags & PREV_WHITE) + obstack_grow (&ob, " ", 1); + if (tk[0] == '@' && tk[1] == '\0') + { + const char *num = get_number(r); + obstack_grow (&ob, "captures[", strlen ("captures[")); + obstack_grow (&ob, num, strlen (num)); + obstack_grow (&ob, "]", 1); + } + else + obstack_grow (&ob, tk, strlen (tk)); + } + while (token->type != CPP_CLOSE_BRACE); +// code = (char *)xmalloc (code, strlen (code) + 1 + 1); + obstack_grow0 (&ob, ")", 1); + code = xstrdup ((const char *) obstack_finish (&ob)); + obstack_free (&ob, obstack_finish (&ob)); + return new c_expr (code); + +} + +/* Parse + op = predicate | ( expr ) */ + +static struct operand * +parse_op (cpp_reader *r) +{ + const cpp_token *token = peek (r); + struct operand *op = NULL; + if (token->type == CPP_OPEN_PAREN) + { + eat_token (r, CPP_OPEN_PAREN); + op = parse_expr (r); + eat_token (r, CPP_CLOSE_PAREN); + } + else if (token->type == CPP_OPEN_BRACE) + { + eat_token (r, CPP_OPEN_BRACE); + op = parse_c_expr (r); + } + else if (token->type == CPP_NAME) + op = new predicate (get_ident (r)); + else if (token->type == CPP_ATSIGN) + op = parse_capture (r, op); + else + fatal ("expected expression or predicate"); + + token = peek (r); + if (token->type == CPP_ATSIGN + && !(token->flags & PREV_WHITE)) + op = parse_capture (r, op); + + return op; +} + +/* + * opcond: cond | op + * cond: '[' cond-list ']' + * cond-list: condition | + cond-list condition + * condition: '(' predicate capture operand ')' + */ + +static struct operand * +parse_condition_or_op (cpp_reader *r) +{ + const cpp_token *token = peek (r); + struct operand *op = NULL; + vec<struct condition_pair> conds = vNULL; + + if (token->type == CPP_OPEN_SQUARE) + { + eat_token (r, CPP_OPEN_SQUARE); + do + { + eat_token (r, CPP_OPEN_PAREN); + struct predicate *pred = new predicate (get_ident (r)); + struct capture *capt = (struct capture *) parse_capture (r, NULL); + struct operand *result = parse_op (r); + struct condition_pair c(pred, result, capt); + conds.safe_push (c); + eat_token (r, CPP_CLOSE_PAREN); + + token = peek (r); + if (token->type == CPP_CLOSE_SQUARE) + { + eat_token (r, CPP_CLOSE_SQUARE); + break; + } + } + while (1); + op = new condition (conds); + } + else + op = parse_op (r); + + return op; +} + +/* Parse + (define_match "<ident>" + <op>) */ + +static match * +parse_match (cpp_reader *r) +{ + return new match (get_ident (r), parse_op (r)); +} + +/* Parse + (define_match_and_simplify "<ident>" + <op> <op>) */ + +static simplify * +parse_match_and_simplify (cpp_reader *r) +{ + return new simplify (get_ident (r), parse_op (r), parse_condition_or_op (r)); +} + +static void +write_gimple (FILE *f, vec<match *>& matchers, vec<simplify *>& simplifiers) +{ + fprintf (f, +"#include \"config.h\"\n" +"#include \"system.h\"\n" +"#include \"coretypes.h\"\n" +"#include \"tree.h\"\n" +"#include \"stringpool.h\"\n" +"#include \"flags.h\"\n" +"#include \"function.h\"\n" +"#include \"basic-block.h\"\n" +"#include \"tree-ssa-alias.h\"\n" +"#include \"internal-fn.h\"\n" +"#include \"gimple-expr.h\"\n" +"#include \"is-a.h\"\n" +"#include \"gimple.h\"\n" +"#include \"gimple-ssa.h\"\n" +"#include \"tree-ssanames.h\"\n" +"\n" +"#define INTEGER_CST_P(node) TREE_CODE(node) == INTEGER_CST\n" +"#define integral_op_p(node) INTEGRAL_TYPE_P(TREE_TYPE(node))\n" +"\n"); + + /* Write matchers and simplifiers. */ + for (unsigned i = 0; i < matchers.length (); ++i) + matchers[i]->gen_gimple (f); + for (unsigned i = 0; i < simplifiers.length (); ++i) + simplifiers[i]->gen_gimple (f); + + /* Write the catch-all simplifier. */ + fprintf (f, "tree\ngimple_match_and_simplify (tree name, gimple_seq *seq, tree (*valueize)(tree))\n" + "{\n" + " tree res;\n"); + for (unsigned i = 0; i < simplifiers.length (); ++i) + fprintf (f, " res = simplify_%s (name, seq, valueize);\n" + " if (res) return res;\n", simplifiers[i]->name); + fprintf (f, " return NULL_TREE;\n" + "}\n"); +} + +int main(int argc, char **argv) +{ + cpp_reader *r; + const cpp_token *token; + struct line_maps *line_table; + + progname = "genmatch"; + + if (argc != 2) + return 1; + + line_table = XCNEW (struct line_maps); + linemap_init (line_table); + line_table->reallocator = xrealloc; + line_table->round_alloc_size = round_alloc_size; + + r = cpp_create_reader (CLK_GNUC99, NULL, line_table); + + if (!cpp_read_main_file (r, argv[1])) + return 1; + +#if 0 + do + { + const cpp_token *token = cpp_get_token (r); + fprintf (stdout, "'%s'\n", cpp_token_as_text (r, token)); + } + while (token->type != CPP_EOF); +#endif + + vec<match *> matchers = vNULL; + vec<simplify *> simplifiers = vNULL; + + do + { + token = peek (r); + if (token->type == CPP_EOF) + break; + + /* All clauses start with '('. */ + eat_token (r, CPP_OPEN_PAREN); + + token = next (r); + if (is_ident (token, "define_match")) + matchers.safe_push (parse_match (r)); + else if (is_ident (token, "define_match_and_simplify")) + simplifiers.safe_push (parse_match_and_simplify (r)); + else + exit (1); + + eat_token (r, CPP_CLOSE_PAREN); + } + while (1); + + write_gimple (stdout, matchers, simplifiers); + + cpp_finish (r, NULL); + cpp_destroy (r); + + return 0; +} Index: gcc/match.pd =================================================================== --- gcc/match.pd (revision 0) +++ gcc/match.pd (working copy) @@ -0,0 +1,30 @@ +/* Match (A - B) + B only. */ +(define_match plusminus + (PLUS_EXPR (MINUS_EXPR integral_op_p@0 @1) @1)) + +/* Match and simplify (A - B) + B -> A. */ +(define_match_and_simplify foo + (PLUS_EXPR (MINUS_EXPR integral_op_p@0 @1) @1) + @0) + +/* 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); }) + +/* Match and simplify (CST + A) + CST to CST' + A. */ +(define_match_and_simplify bar + (PLUS_EXPR INTEGER_CST_P@0 (PLUS_EXPR @1 INTEGER_CST_P@2)) + (PLUS_EXPR { int_const_binop (PLUS_EXPR, captures[0], captures[2]); } @1)) + +/* 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) + ]) + ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-06 12:11 ` Prathamesh Kulkarni @ 2014-03-06 12:43 ` Richard Biener 2014-03-06 18:17 ` Prathamesh Kulkarni 0 siblings, 1 reply; 22+ messages in thread From: Richard Biener @ 2014-03-06 12:43 UTC (permalink / raw) To: Prathamesh Kulkarni; +Cc: gcc [-- Attachment #1: Type: text/plain, Size: 7889 bytes --] On Thu, Mar 6, 2014 at 1:11 PM, Prathamesh Kulkarni <bilbotheelffriend@gmail.com> wrote: > On Mon, Mar 3, 2014 at 3:32 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Sun, Mar 2, 2014 at 9:13 PM, Prathamesh Kulkarni >> <bilbotheelffriend@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, 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 [-- Attachment #2: genmatch --] [-- Type: application/octet-stream, Size: 63945 bytes --] Index: gcc/Makefile.in =================================================================== *** gcc/Makefile.in.orig 2014-03-06 12:36:04.817482308 +0100 --- gcc/Makefile.in 2014-03-06 12:39:26.689468409 +0100 *************** BUILD_LIBS = $(BUILD_LIBIBERTY) *** 1024,1030 **** BUILD_RTL = build/rtl.o build/read-rtl.o build/ggc-none.o \ build/vec.o build/min-insn-modes.o build/gensupport.o \ ! build/print-rtl.o BUILD_MD = build/read-md.o BUILD_ERRORS = build/errors.o --- 1024,1030 ---- BUILD_RTL = build/rtl.o build/read-rtl.o build/ggc-none.o \ build/vec.o build/min-insn-modes.o build/gensupport.o \ ! build/print-rtl.o build/hash-table.o BUILD_MD = build/read-md.o BUILD_ERRORS = build/errors.o *************** OBJS = \ *** 1236,1241 **** --- 1236,1242 ---- gimple-iterator.o \ gimple-fold.o \ gimple-low.o \ + gimple-match.o \ gimple-pretty-print.o \ gimple-ssa-isolate-paths.o \ gimple-ssa-strength-reduction.o \ *************** MOSTLYCLEANFILES = insn-flags.h insn-con *** 1504,1510 **** insn-output.c insn-recog.c insn-emit.c insn-extract.c insn-peep.c \ insn-attr.h insn-attr-common.h insn-attrtab.c insn-dfatab.c \ insn-latencytab.c insn-opinit.c insn-opinit.h insn-preds.c insn-constants.h \ ! tm-preds.h tm-constrs.h checksum-options \ tree-check.h min-insn-modes.c insn-modes.c insn-modes.h \ genrtl.h gt-*.h gtype-*.h gtype-desc.c gtyp-input.list \ xgcc$(exeext) cpp$(exeext) \ --- 1505,1511 ---- insn-output.c insn-recog.c insn-emit.c insn-extract.c insn-peep.c \ insn-attr.h insn-attr-common.h insn-attrtab.c insn-dfatab.c \ insn-latencytab.c insn-opinit.c insn-opinit.h insn-preds.c insn-constants.h \ ! tm-preds.h tm-constrs.h checksum-options gimple-match.c \ tree-check.h min-insn-modes.c insn-modes.c insn-modes.h \ genrtl.h gt-*.h gtype-*.h gtype-desc.c gtyp-input.list \ xgcc$(exeext) cpp$(exeext) \ *************** $(common_out_object_file): $(common_out_ *** 2018,2024 **** .PRECIOUS: insn-config.h insn-flags.h insn-codes.h insn-constants.h \ insn-emit.c insn-recog.c insn-extract.c insn-output.c insn-peep.c \ insn-attr.h insn-attr-common.h insn-attrtab.c insn-dfatab.c \ ! insn-latencytab.c insn-preds.c # Dependencies for the md file. The first time through, we just assume # the md file itself and the generated dependency file (in order to get --- 2019,2025 ---- .PRECIOUS: insn-config.h insn-flags.h insn-codes.h insn-constants.h \ insn-emit.c insn-recog.c insn-extract.c insn-output.c insn-peep.c \ insn-attr.h insn-attr-common.h insn-attrtab.c insn-dfatab.c \ ! insn-latencytab.c insn-preds.c gimple-match.c # Dependencies for the md file. The first time through, we just assume # the md file itself and the generated dependency file (in order to get *************** s-tm-texi: build/genhooks$(build_exeext) *** 2227,2232 **** --- 2228,2242 ---- false; \ fi + gimple-match.c: s-match; @true + + s-match: build/genmatch$(build_exeext) $(srcdir)/match.pd + $(RUN_GEN) build/genmatch$(build_exeext) $(srcdir)/match.pd \ + > tmp-gimple-match.c + $(SHELL) $(srcdir)/../move-if-change tmp-gimple-match.c \ + gimple-match.c + $(STAMP) s-match + GTFILES = $(CPP_ID_DATA_H) $(srcdir)/input.h $(srcdir)/coretypes.h \ $(host_xm_file_list) \ $(tm_file_list) $(HASHTAB_H) $(SPLAY_TREE_H) $(srcdir)/bitmap.h \ *************** build/rtl.o: rtl.c $(BCONFIG_H) coretype *** 2373,2378 **** --- 2383,2390 ---- $(RTL_H) $(GGC_H) errors.h build/vec.o : vec.c $(BCONFIG_H) $(SYSTEM_H) coretypes.h $(VEC_H) \ $(GGC_H) toplev.h $(DIAGNOSTIC_CORE_H) + build/hash-table.o : hash-table.c $(BCONFIG_H) $(SYSTEM_H) coretypes.h \ + $(HASH_TABLE_H) $(GGC_H) toplev.h $(DIAGNOSTIC_CORE_H) build/gencondmd.o : build/gencondmd.c $(BCONFIG_H) $(SYSTEM_H) \ coretypes.h $(GTM_H) insn-constants.h \ $(filter-out insn-flags.h, $(RTL_H) $(TM_P_H) $(FUNCTION_H) $(REGS_H) \ *************** build/genhooks.o : genhooks.c $(TARGET_D *** 2469,2474 **** --- 2481,2488 ---- $(COMMON_TARGET_DEF) $(BCONFIG_H) $(SYSTEM_H) errors.h build/genmddump.o : genmddump.c $(RTL_BASE_H) $(BCONFIG_H) $(SYSTEM_H) \ coretypes.h $(GTM_H) errors.h $(READ_MD_H) gensupport.h + build/genmatch.o : genmatch.c $(BCONFIG_H) $(SYSTEM_H) \ + coretypes.h errors.h # Compile the programs that generate insn-* from the machine description. # They are compiled with $(COMPILER_FOR_BUILD), and associated libraries, *************** genprogerr = $(genprogmd) genrtl modes g *** 2489,2498 **** $(genprogerr:%=build/gen%$(build_exeext)): $(BUILD_ERRORS) # Remaining build programs. ! genprog = $(genprogerr) check checksum condmd # These programs need libs over and above what they get from the above list. build/genautomata$(build_exeext) : BUILD_LIBS += -lm # These programs are not linked with the MD reader. build/gengtype$(build_exeext) : build/gengtype-lex.o build/gengtype-parse.o \ --- 2503,2514 ---- $(genprogerr:%=build/gen%$(build_exeext)): $(BUILD_ERRORS) # Remaining build programs. ! genprog = $(genprogerr) check checksum condmd match # These programs need libs over and above what they get from the above list. build/genautomata$(build_exeext) : BUILD_LIBS += -lm + build/genmatch$(build_exeext) : BUILD_LIBS += $(CPPLIB) $(LIBIBERTY) \ + $(BUILD_ERRORS) build/vec.o build/hash-table.o # These programs are not linked with the MD reader. build/gengtype$(build_exeext) : build/gengtype-lex.o build/gengtype-parse.o \ Index: gcc/genmatch.c =================================================================== *** /dev/null 1970-01-01 00:00:00.000000000 +0000 --- gcc/genmatch.c 2014-03-06 13:04:18.576365694 +0100 *************** *** 0 **** --- 1,954 ---- + + /* Grammar + + capture = '@' number + op = predicate | expr [capture] + match = 'define_match' name expr + c_expr = '{' ... '}' + genexpr = '(' code genop... ')' + genop = capture | genexpr | c_expr + transform = 'define_match_and_transform' name expr genop + + Match (A + B) - B + (define_match plusminus + (PLUS_EXPR (MINUS_EXPR integral_op_p@0 @1) @1)) + + Match and simplify (A + B) - B -> A + (define_match_and_simplify foo + (PLUS_EXPR (MINUS_EXPR integral_op_p@0 @1) @1) + @0) + + Match and simplify (CST + A) + CST to CST' + A + (define_match_and_simplify bar + (PLUS_EXPR INTEGER_CST_P@0 (PLUS_EXPR @1 INTEGER_CST_P@2)) + (PLUS_EXPR { int_const_binop (PLUS_EXPR, captures[0], captures[2]); } @1)) + */ + + #include "bconfig.h" + #include <new> + #include "system.h" + #include "coretypes.h" + #include <cpplib.h> + #include "errors.h" + #include "hashtab.h" + #include "hash-table.h" + #include "vec.h" + + + #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM, + enum tree_code { + #include "tree.def" + MAX_TREE_CODES + }; + #undef DEFTREECODE + + #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM, + enum built_in_function { + #include "builtins.def" + END_BUILTINS + }; + #undef DEF_BUILTIN + + /* Hashtable of known pattern operators. This is pre-seeded from + all known tree codes and all known builtin function ids. */ + + struct p_operator_base : typed_free_remove<p_operator_base> + { + enum p_kind { CODE, FN } kind; + + p_operator_base (p_kind, const char *); + + hashval_t hashval; + const char *id; + + /* hash_table support. */ + typedef p_operator_base value_type; + typedef p_operator_base compare_type; + static inline hashval_t hash (const value_type *); + static inline int equal (const value_type *, const compare_type *); + }; + inline hashval_t + p_operator_base::hash (const value_type *op) + { + return op->hashval; + } + inline int + p_operator_base::equal (const value_type *op1, + const compare_type *op2) + { + return (op1->hashval == op2->hashval + && strcmp (op1->id, op2->id) == 0); + } + + static hash_table<p_operator_base> operators; + + p_operator_base::p_operator_base (p_kind kind_, const char *id_) + { + kind = kind_; + id = id_; + hashval = htab_hash_string (id); + } + + struct p_operator : public p_operator_base + { + p_operator (enum tree_code code_, const char *id_, unsigned nargs_) + : p_operator_base (p_operator_base::CODE, id_), + code (code_), nargs (nargs_) {} + enum tree_code code; + unsigned nargs; + }; + struct p_fncall : public p_operator_base + { + p_fncall (enum built_in_function fn_, const char *id_, unsigned nargs_) + : p_operator_base (p_operator_base::FN, id_), + fn (fn_), nargs (nargs_) {} + enum built_in_function fn; + unsigned nargs; + }; + + static void + add_operator (enum tree_code code, const char *id, + const char *tcc, unsigned nargs) + { + if (strcmp (tcc, "tcc_unary") != 0 + && strcmp (tcc, "tcc_binary") != 0 + && strcmp (tcc, "tcc_comparison") != 0 + && strcmp (tcc, "tcc_expression") != 0 + /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */ + && strcmp (tcc, "tcc_reference") != 0) + return; + p_operator *op = new p_operator (code, id, nargs); + p_operator_base **slot = operators.find_slot_with_hash (op, op->hashval, INSERT); + if (*slot) + fatal ("duplicate operator definition"); + *slot = op; + } + + + /* The predicate expression tree structure. */ + + struct e_operation { + e_operation (const char *id); + p_operator_base *op; + }; + + e_operation::e_operation (const char *id) + { + p_operator_base tem (p_operator_base::CODE, id); + op = operators.find_with_hash (&tem, tem.hashval); + if (op) + return; + + /* Try all-uppercase. */ + char *id2 = xstrdup (id); + for (unsigned i = 0; i < strlen (id2); ++i) + id2[i] = TOUPPER (id2[i]); + new (&tem) p_operator_base (p_operator_base::CODE, id2); + op = operators.find_with_hash (&tem, tem.hashval); + if (op) + { + free (id2); + return; + } + + /* Try _EXPR appended. */ + id2 = (char *)xrealloc (id2, strlen (id2) + sizeof ("_EXPR") + 1); + strcat (id2, "_EXPR"); + new (&tem) p_operator_base (p_operator_base::CODE, id2); + op = operators.find_with_hash (&tem, tem.hashval); + if (op) + { + free (id2); + return; + } + + fatal ("expected operator, got %s", id); + } + + enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR }; + + struct operand { + operand (enum op_type type_) : type (type_) {} + enum op_type type; + virtual void gen_gimple_match (FILE *f, const char *, const char * = NULL) = 0; + virtual void gen_gimple_transform (FILE *f, const char * = NULL) = 0; + }; + + struct predicate : public operand + { + predicate (const char *ident_) : operand (OP_PREDICATE), ident (ident_) {} + const char *ident; + virtual void gen_gimple_match (FILE *f, const char *, const char *); + virtual void gen_gimple_transform (FILE *, const char *) { gcc_unreachable (); } + }; + + struct expr : public operand + { + expr (e_operation *operation_) + : operand (OP_EXPR), operation (operation_), num_ops (0) {} + void append_op (operand *op) { ops[num_ops++] = op; } + e_operation *operation; + unsigned num_ops; + operand *ops[4]; + virtual void gen_gimple_match (FILE *f, const char *, const char *); + virtual void gen_gimple_transform (FILE *f, const char *); + }; + + struct c_expr : public operand + { + c_expr (const char *code_) + : operand (OP_EXPR), code (code_) {} + const char *code; + virtual void gen_gimple_match (FILE *, const char *, const char *) { gcc_unreachable (); } + virtual void gen_gimple_transform (FILE *f, const char *); + }; + + struct capture : public operand + { + capture (const char *where_, operand *what_) + : operand (OP_CAPTURE), where (where_), what (what_) {} + const char *where; + operand *what; + virtual void gen_gimple_match (FILE *f, const char *, const char *); + virtual void gen_gimple_transform (FILE *f, const char *); + }; + + struct match { + match (const char *name_, struct operand *op_); + const char *name; + struct operand *op; + void gen_gimple_match (FILE *f); + virtual void gen_gimple (FILE *f) { gen_gimple_match (f); } + }; + + struct simplify : public match { + simplify (const char *name_, + struct operand *match_, struct operand *ifexpr_, + struct operand *result_) + : match (name_, match_), ifexpr (ifexpr_), result (result_) {} + struct operand *ifexpr; + struct operand *result; + virtual void gen_gimple (FILE *f); + }; + + match::match (const char *name_, operand *op_) + { + name = name_; + op = op_; + } + + static void + gen_gimple_match_fail (FILE *f, const char *label) + { + if (!label) + fprintf (f, "return NULL_TREE;\n"); + else + fprintf (f, "goto %s;\n", label); + } + + void + predicate::gen_gimple_match (FILE *f, const char *op, const char *label) + { + fprintf (f, "if (!%s (%s)) ", ident, op); + gen_gimple_match_fail (f, label); + } + + void + expr::gen_gimple_match (FILE *f, const char *name, const char *label) + { + if (operation->op->kind == p_operator_base::CODE) + { + p_operator *op = static_cast <p_operator *> (operation->op); + fprintf (f, "{\n"); + fprintf (f, "if (TREE_CODE (%s) != SSA_NAME) ", name); + gen_gimple_match_fail (f, label); + fprintf (f, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", name); + fprintf (f, "if (!is_gimple_assign (def_stmt)\n" + " || gimple_assign_rhs_code (def_stmt) != %s) ", op->id); + gen_gimple_match_fail (f, label); + if (op->code == REALPART_EXPR + || op->code == IMAGPART_EXPR + || op->code == VIEW_CONVERT_EXPR + || op->code == BIT_FIELD_REF) + { + fprintf (f, " tree rhs = gimple_assign_rhs1 (def_stmt);\n"); + for (unsigned i = 0; i < num_ops; ++i) + { + fprintf (f, " {\n"); + fprintf (f, " tree op = TREE_OPERAND (rhs, %d);\n", i); + fprintf (f, " if (valueize && TREE_CODE (op) == SSA_NAME)\n"); + fprintf (f, " {\n"); + fprintf (f, " op = valueize (op);\n"); + fprintf (f, " if (!op) "); + gen_gimple_match_fail (f, label); + fprintf (f, " }\n"); + ops[i]->gen_gimple_match (f, "op", label); + fprintf (f, " }\n"); + } + } + else + { + for (unsigned i = 0; i < num_ops; ++i) + { + fprintf (f, " {\n"); + fprintf (f, " tree op = gimple_assign_rhs%d (def_stmt);\n", i + 1); + fprintf (f, " if (valueize && TREE_CODE (op) == SSA_NAME)\n"); + fprintf (f, " {\n"); + fprintf (f, " op = valueize (op);\n"); + fprintf (f, " if (!op) "); + gen_gimple_match_fail (f, label); + fprintf (f, " }\n"); + ops[i]->gen_gimple_match (f, "op", label); + fprintf (f, " }\n"); + } + } + fprintf (f, "}\n"); + } + else + /* FIXME - implement call support. */ + gcc_unreachable (); + } + + void + expr::gen_gimple_transform (FILE *f, const char *label) + { + fprintf (f, "({\n"); + fprintf (f, " if (!seq) "); + gen_gimple_match_fail (f, label); + fprintf (f, " tree ops[%d];\n", num_ops); + for (unsigned i = 0; i < num_ops; ++i) + { + fprintf (f, " ops[%u] = ", i); + ops[i]->gen_gimple_transform (f, label); + fprintf (f, ";\n"); + } + fprintf (f, " gimple_build (seq, UNKNOWN_LOCATION, %s, TREE_TYPE (ops[0])", + operation->op->id); + for (unsigned i = 0; i < num_ops; ++i) + fprintf (f, ", ops[%u]", i); + fprintf (f, ", valueize);\n"); + fprintf (f, "})"); + } + + void + c_expr::gen_gimple_transform (FILE *f, const char *) + { + fputs (code, f); + } + + void + capture::gen_gimple_transform (FILE *f, const char *) + { + fprintf (f, "captures[%s]", this->where); + } + + void + capture::gen_gimple_match (FILE *f, const char *op, const char *label) + { + if (this->what) + this->what->gen_gimple_match (f, op, label); + fprintf (f, "if (!captures[%s])\n" + " captures[%s] = %s;\n" + "else if (captures[%s] != %s)\n", + this->where, this->where, op, this->where, op); + gen_gimple_match_fail (f, label); + } + + + + void + match::gen_gimple_match (FILE *f) + { + fprintf (f, "bool\nmatch_%s (tree name, tree *captures, tree (*valueize)(tree))\n" + "{\n", this->name); + this->op->gen_gimple_match (f, "name"); + fprintf (f, " return true;\n"); + fprintf (f, "}\n"); + } + + + void + simplify::gen_gimple (FILE *f) + { + fprintf (f, "static "); + this->gen_gimple_match (f); + fprintf (f, "static tree\n" + "simplify_%s (tree name, gimple_seq *seq, tree (*valueize)(tree))\n" + "{\n", this->name); + fprintf (f, " tree captures[4] = {};\n" + " if (!match_%s (name, captures, valueize)) return NULL_TREE;\n", + this->name); + if (ifexpr) + { + fprintf (f, " if (!"); + this->ifexpr->gen_gimple_transform (f); + fprintf (f, ") return NULL_TREE;\n"); + } + fprintf (f, " return "); + this->result->gen_gimple_transform (f); + fprintf (f, ";\n}\n"); + } + + static const cpp_token * + next (cpp_reader *r) + { + const cpp_token *token; + do + { + token = cpp_get_token (r); + } + while (token->type == CPP_PADDING + && token->type != CPP_EOF); + #if 0 + /* DEBUG */ + if (token->type != CPP_EOF) + printf ("got token '%s'\n", cpp_token_as_text (r, token)); + #endif + return token; + } + + static const cpp_token * + peek (cpp_reader *r) + { + const cpp_token *token; + unsigned i = 0; + do + { + token = cpp_peek_token (r, i++); + } + while (token->type == CPP_PADDING); + #if 0 + /* DEBUG */ + if (token->type != CPP_EOF) + printf ("next token '%s'\n", cpp_token_as_text (r, token)); + #endif + return token; + } + + static bool + is_ident (const cpp_token *token, const char *id) + { + return strcmp ((const char *)CPP_HASHNODE (token->val.node.node)->ident.str, + id) == 0; + } + + static size_t + round_alloc_size (size_t s) + { + return s; + } + + + static const cpp_token * + expect (cpp_reader *r, enum cpp_ttype tk) + { + const cpp_token *token = next (r); + if (token->type != tk) + fatal ("error: expected %s, got %s", + cpp_type2name (tk, 0), cpp_type2name (token->type, 0)); + + return token; + } + + static void + eat_token (cpp_reader *r, enum cpp_ttype tk) + { + expect (r, tk); + } + + const char * + get_string (cpp_reader *r) + { + const cpp_token *token = expect (r, CPP_STRING); + return (const char *)token->val.str.text; + } + + const char * + get_ident (cpp_reader *r) + { + const cpp_token *token = expect (r, CPP_NAME); + return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str; + } + + const char * + get_number (cpp_reader *r) + { + const cpp_token *token = expect (r, CPP_NUMBER); + return (const char *)token->val.str.text; + } + + static e_operation * + parse_operation (cpp_reader *r) + { + return new e_operation (get_ident (r)); + } + + static struct operand * parse_op (cpp_reader *r); + + static struct operand * + parse_capture (cpp_reader *r, operand *op) + { + eat_token (r, CPP_ATSIGN); + return new capture (get_number (r), op); + } + + /* Parse + expr = (operation[capture] op...) */ + static struct operand * + parse_expr (cpp_reader *r) + { + expr *e = new expr (parse_operation (r)); + const cpp_token *token = peek (r); + operand *op; + if (token->type == CPP_ATSIGN + && !(token->flags & PREV_WHITE)) + op = parse_capture (r, e); + else if (token->type == CPP_COLON + && !(token->flags & PREV_WHITE)) + fatal ("not implemented: predicates on expressions"); + else + op = e; + do + { + const cpp_token *token = peek (r); + if (token->type == CPP_CLOSE_PAREN) + return op; + e->append_op (parse_op (r)); + } + while (1); + return op; + } + + /* Parse [({] .... [})] literally recording everything as string and only + replacing captures. */ + + static operand * + parse_c_expr (cpp_reader *r, cpp_ttype start) + { + /* ??? Use an obstack to build the string. */ + const cpp_token *token; + cpp_ttype end; + unsigned opencnt; + char *code; + eat_token (r, start); + if (start == CPP_OPEN_PAREN) + { + code = xstrdup ("("); + end = CPP_CLOSE_PAREN; + } + else if (start == CPP_OPEN_BRACE) + { + code = xstrdup ("({"); + end = CPP_CLOSE_BRACE; + } + else + gcc_unreachable (); + opencnt = 1; + do + { + token = next (r); + + /* Replace captures for code-gen. */ + if (token->type == CPP_ATSIGN) + { + const cpp_token *n = peek (r); + if (n->type == CPP_NUMBER + && !(n->flags & PREV_WHITE)) + { + code = (char *)xrealloc (code, strlen (code) + + strlen ("captures[") + 4); + if (token->flags & PREV_WHITE) + strcat (code, " "); + strcat (code, "captures["); + strcat (code, get_number (r)); + strcat (code, "]"); + continue; + } + } + + /* Count brace pairs to find the end of the expr to match. */ + if (token->type == start) + opencnt++; + else if (token->type == end + && --opencnt == 0) + break; + + /* Output the token as string. */ + char *tk = (char *)cpp_token_as_text (r, token); + code = (char *)xrealloc (code, strlen (code) + strlen (tk) + 2); + if (token->flags & PREV_WHITE) + strcat (code, " "); + strcat (code, tk); + } + while (1); + if (end == CPP_CLOSE_PAREN) + { + code = (char *)xrealloc (code, strlen (code) + 1 + 1); + strcat (code, ")"); + } + else if (end == CPP_CLOSE_BRACE) + { + code = (char *)xrealloc (code, strlen (code) + 1 + 2); + strcat (code, "})"); + } + else + gcc_unreachable (); + return new c_expr (code); + } + + /* Parse + op = predicate | ( expr ) */ + + static struct operand * + parse_op (cpp_reader *r) + { + const cpp_token *token = peek (r); + struct operand *op = NULL; + if (token->type == CPP_OPEN_PAREN) + { + eat_token (r, CPP_OPEN_PAREN); + op = parse_expr (r); + eat_token (r, CPP_CLOSE_PAREN); + } + else if (token->type == CPP_OPEN_BRACE) + { + op = parse_c_expr (r, CPP_OPEN_BRACE); + } + else + { + /* Remaining ops are either empty or predicates */ + if (token->type == CPP_NAME) + { + op = new predicate (get_ident (r)); + token = peek (r); + if (token->flags & PREV_WHITE) + return op; + } + else if (token->type != CPP_COLON + && token->type != CPP_ATSIGN) + fatal ("expected expression or predicate"); + /* optionally followed by a capture and a predicate. */ + if (token->type == CPP_COLON) + fatal ("not implemented: predicate on leaf operand"); + if (token->type == CPP_ATSIGN) + op = parse_capture (r, op); + } + + return op; + } + + /* Parse + (define_match "<ident>" + <op>) */ + + static match * + parse_match (cpp_reader *r) + { + return new match (get_ident (r), parse_op (r)); + } + + /* Parse + (define_match_and_simplify "<ident>" + <op> <op>) */ + + static simplify * + parse_match_and_simplify (cpp_reader *r) + { + const cpp_token *token = peek (r); + const char *id; + if (token->type == CPP_NAME) + id = get_ident (r); + else + { + static int cnt; + char *tem; + asprintf (&tem, "anon_%d", ++cnt); + id = tem; + } + struct operand *match = parse_op (r); + token = peek (r); + /* Conditional if (....) */ + struct operand *ifexpr = NULL; + if (token->type == CPP_NAME) + { + const char *tem = get_ident (r); + if (strcmp (tem, "if") != 0) + fatal ("expected 'if' or expression"); + ifexpr = parse_c_expr (r, CPP_OPEN_PAREN); + } + return new simplify (id, match, ifexpr, parse_op (r)); + } + + static void + write_nary_simplifiers (FILE *f, vec<simplify *>& simplifiers, unsigned n) + { + unsigned label_cnt = 1; + + fprintf (f, "tree\ngimple_match_and_simplify (enum tree_code code, tree type"); + for (unsigned i = 0; i < n; ++i) + fprintf (f, ", tree op%d", i); + fprintf (f, ", gimple_seq *seq, tree (*valueize)(tree))\n"); + fprintf (f, "{\n"); + for (unsigned i = 0; i < simplifiers.length (); ++i) + { + simplify *s = simplifiers[i]; + /* ??? This means we can't capture the outermost expression. */ + if (s->op->type != OP_EXPR) + continue; + expr *e = static_cast <expr *> (s->op); + if (e->operation->op->kind != p_operator_base::CODE + || e->num_ops != n) + continue; + char fail_label[16]; + snprintf (fail_label, 16, "fail%d", label_cnt++); + fprintf (f, " if (code == %s)\n", e->operation->op->id); + fprintf (f, " {\n"); + fprintf (f, " tree captures[4] = {};\n"); + for (unsigned j = 0; j < n; ++j) + { + char op[4] = "op0"; + op[2] = '0' + j; + e->ops[j]->gen_gimple_match (f, op, fail_label); + } + if (s->ifexpr) + { + fprintf (f, " if (!"); + s->ifexpr->gen_gimple_transform (f, fail_label); + fprintf (f, ") goto %s;", fail_label); + } + fprintf (f, " return "); + s->result->gen_gimple_transform (f, fail_label); + fprintf (f, ";\n"); + fprintf (f, " }\n"); + fprintf (f, "%s:\n", fail_label); + } + fprintf (f, " return NULL_TREE;\n"); + fprintf (f, "}\n\n"); + } + + static void + write_gimple (FILE *f, vec<match *>& matchers, vec<simplify *>& simplifiers) + { + unsigned label_cnt = 1; + + fprintf (f, + "#include \"config.h\"\n" + "#include \"system.h\"\n" + "#include \"coretypes.h\"\n" + "#include \"tree.h\"\n" + "#include \"stringpool.h\"\n" + "#include \"flags.h\"\n" + "#include \"function.h\"\n" + "#include \"basic-block.h\"\n" + "#include \"tree-ssa-alias.h\"\n" + "#include \"internal-fn.h\"\n" + "#include \"gimple-expr.h\"\n" + "#include \"is-a.h\"\n" + "#include \"gimple.h\"\n" + "#include \"gimple-ssa.h\"\n" + "#include \"tree-ssanames.h\"\n" + "#include \"gimple-fold.h\"\n" + "\n" + "#define INTEGER_CST_P(node) (TREE_CODE(node) == INTEGER_CST)\n" + "#define integral_op_p(node) INTEGRAL_TYPE_P(TREE_TYPE(node))\n" + "\n"); + + #if 0 + /* Write matchers and simplifiers. */ + for (unsigned i = 0; i < matchers.length (); ++i) + matchers[i]->gen_gimple (f); + for (unsigned i = 0; i < simplifiers.length (); ++i) + simplifiers[i]->gen_gimple (f); + #endif + + /* Explode matchers even more, optionally giving the SSA name defining + the exploded expression? That way we can capture it. + Provide exploded transform result to avoid a temporary SSA name + and stmt for example for gimple_cond folding. */ + + write_nary_simplifiers (f, simplifiers, 1); + write_nary_simplifiers (f, simplifiers, 2); + write_nary_simplifiers (f, simplifiers, 3); + + #if 0 + /* Write unary matcher. */ + fprintf (f, "tree\ngimple_match_and_simplify (enum tree_code code, tree type, tree op0, gimple_seq *seq, tree (*valueize)(tree))\n"); + fprintf (f, "{\n"); + for (unsigned i = 0; i < simplifiers.length (); ++i) + { + simplify *s = simplifiers[i]; + /* ??? This means we can't capture the outermost expression. */ + if (s->op->type != OP_EXPR) + continue; + expr *e = static_cast <expr *> (s->op); + if (e->operation->op->kind != p_operator_base::CODE + || e->num_ops != 1) + continue; + char fail_label[16]; + snprintf (fail_label, 16, "fail%d", label_cnt++); + fprintf (f, " if (code == %s)\n", e->operation->op->id); + fprintf (f, " {\n"); + fprintf (f, " tree captures[4] = {};\n"); + e->ops[0]->gen_gimple_match (f, "op0", fail_label); + if (s->ifexpr) + { + fprintf (f, " if (!"); + s->ifexpr->gen_gimple_transform (f, fail_label); + fprintf (f, ") goto %s;", fail_label); + } + fprintf (f, " return "); + s->result->gen_gimple_transform (f, fail_label); + fprintf (f, ";\n"); + fprintf (f, " }\n"); + fprintf (f, "%s:\n", fail_label); + } + fprintf (f, " return NULL_TREE;\n"); + fprintf (f, "}\n\n"); + + /* Write binary matcher. */ + fprintf (f, "tree\ngimple_match_and_simplify (enum tree_code code, tree type, tree op0, tree op1, gimple_seq *seq, tree (*valueize)(tree))\n"); + fprintf (f, "{\n"); + for (unsigned i = 0; i < simplifiers.length (); ++i) + { + simplify *s = simplifiers[i]; + /* ??? This means we can't capture the outermost expression. */ + if (s->op->type != OP_EXPR) + continue; + expr *e = static_cast <expr *> (s->op); + if (e->operation->op->kind != p_operator_base::CODE + || e->num_ops != 2) + continue; + char fail_label[16]; + snprintf (fail_label, 16, "fail%d", label_cnt++); + fprintf (f, " if (code == %s)\n", e->operation->op->id); + fprintf (f, " {\n"); + fprintf (f, " tree captures[4] = {};\n"); + e->ops[0]->gen_gimple_match (f, "op0", fail_label); + e->ops[1]->gen_gimple_match (f, "op1", fail_label); + if (s->ifexpr) + { + fprintf (f, " if (!"); + s->ifexpr->gen_gimple_transform (f, fail_label); + fprintf (f, ") goto %s;", fail_label); + } + fprintf (f, " return "); + s->result->gen_gimple_transform (f, fail_label); + fprintf (f, ";\n"); + fprintf (f, " }\n"); + fprintf (f, "%s:\n", fail_label); + } + fprintf (f, " return NULL_TREE;\n"); + fprintf (f, "}\n\n"); + + /* Write ternary matcher. */ + fprintf (f, "tree\ngimple_match_and_simplify (enum tree_code code, tree type, tree op0, tree op1, tree op2, gimple_seq *seq, tree (*valueize)(tree))\n"); + fprintf (f, "{\n"); + for (unsigned i = 0; i < simplifiers.length (); ++i) + { + simplify *s = simplifiers[i]; + /* ??? This means we can't capture the outermost expression. */ + if (s->op->type != OP_EXPR) + continue; + expr *e = static_cast <expr *> (s->op); + if (e->operation->op->kind != p_operator_base::CODE + || e->num_ops != 3) + continue; + char fail_label[16]; + snprintf (fail_label, 16, "fail%d", label_cnt++); + fprintf (f, " if (code == %s)\n", e->operation->op->id); + fprintf (f, " {\n"); + fprintf (f, " tree captures[4] = {};\n"); + e->ops[0]->gen_gimple_match (f, "op0", fail_label); + e->ops[1]->gen_gimple_match (f, "op1", fail_label); + e->ops[1]->gen_gimple_match (f, "op2", fail_label); + if (s->ifexpr) + { + fprintf (f, " if (!"); + s->ifexpr->gen_gimple_transform (f, fail_label); + fprintf (f, ") goto %s;", fail_label); + } + fprintf (f, " return "); + s->result->gen_gimple_transform (f, fail_label); + fprintf (f, ";\n"); + fprintf (f, " }\n"); + fprintf (f, "%s:\n", fail_label); + } + fprintf (f, " return NULL_TREE;\n"); + fprintf (f, "}\n\n"); + #endif + } + + int main(int argc, char **argv) + { + cpp_reader *r; + const cpp_token *token; + struct line_maps *line_table; + + progname = "genmatch"; + + if (argc != 2) + return 1; + + line_table = XCNEW (struct line_maps); + linemap_init (line_table); + line_table->reallocator = xrealloc; + line_table->round_alloc_size = round_alloc_size; + + r = cpp_create_reader (CLK_GNUC99, NULL, line_table); + + if (!cpp_read_main_file (r, argv[1])) + return 1; + + /* Pre-seed operators. */ + operators.create (1024); + #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \ + add_operator (SYM, # SYM, # TYPE, NARGS); + #define END_OF_BASE_TREE_CODES + #include "tree.def" + #undef END_OF_BASE_TREE_CODES + #undef DEFTREECODE + + #if 0 + do + { + const cpp_token *token = cpp_get_token (r); + fprintf (stdout, "'%s'\n", cpp_token_as_text (r, token)); + } + while (token->type != CPP_EOF); + #endif + + vec<match *> matchers = vNULL; + vec<simplify *> simplifiers = vNULL; + + do + { + token = peek (r); + if (token->type == CPP_EOF) + break; + + /* All clauses start with '('. */ + eat_token (r, CPP_OPEN_PAREN); + + token = next (r); + #if 0 + /* Disabled for now. */ + if (is_ident (token, "match")) + matchers.safe_push (parse_match (r)); + else + #endif + if (is_ident (token, "match_and_simplify")) + simplifiers.safe_push (parse_match_and_simplify (r)); + else + exit (1); + + eat_token (r, CPP_CLOSE_PAREN); + } + while (1); + + write_gimple (stdout, matchers, simplifiers); + + cpp_finish (r, NULL); + cpp_destroy (r); + + return 0; + } Index: gcc/gimple-fold.c =================================================================== *** gcc/gimple-fold.c.orig 2014-03-06 12:36:04.817482308 +0100 --- gcc/gimple-fold.c 2014-03-06 13:23:58.987284424 +0100 *************** rewrite_to_defined_overflow (gimple stmt *** 3623,3625 **** --- 3623,3920 ---- return stmts; } + + + /* Match and simplify on the defining statement of NAME using VALUEIZE + if not NULL to valueize SSA names in expressions. NAME is expected + to be valueized already. Appends statements for complex expression + results to SEQ or fails if that would be required and SEQ is NULL. + Returns the simplified value (which might be defined by stmts in + SEQ) or NULL_TREE if no simplification was possible. */ + + tree + gimple_match_and_simplify (tree name, gimple_seq *seq, tree (*valueize)(tree)) + { + if (TREE_CODE (name) != SSA_NAME) + return NULL_TREE; + + gimple stmt = SSA_NAME_DEF_STMT (name); + if (is_gimple_assign (stmt)) + { + enum tree_code code = gimple_assign_rhs_code (stmt); + tree type = TREE_TYPE (gimple_assign_lhs (stmt)); + switch (gimple_assign_rhs_class (stmt)) + { + case GIMPLE_SINGLE_RHS: + if (code == REALPART_EXPR + || code == IMAGPART_EXPR + || code == VIEW_CONVERT_EXPR) + { + tree op0 = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); + if (valueize && TREE_CODE (op0) == SSA_NAME) + { + op0 = valueize (op0); + if (!op0) + return NULL_TREE; + } + return gimple_match_and_simplify (code, type, op0, + seq, valueize); + } + else if (code == BIT_FIELD_REF) + { + tree rhs1 = gimple_assign_rhs1 (stmt); + tree op0 = TREE_OPERAND (rhs1, 0); + if (valueize && TREE_CODE (op0) == SSA_NAME) + { + op0 = valueize (op0); + if (!op0) + return NULL_TREE; + } + return gimple_match_and_simplify (code, type, op0, + TREE_OPERAND (rhs1, 1), + TREE_OPERAND (rhs1, 2), + seq, valueize); + } + break; + case GIMPLE_UNARY_RHS: + { + tree rhs1 = gimple_assign_rhs1 (stmt); + if (valueize && TREE_CODE (rhs1) == SSA_NAME) + { + rhs1 = valueize (rhs1); + if (!rhs1) + return NULL_TREE; + } + return gimple_match_and_simplify (code, type, rhs1, + seq, valueize); + } + case GIMPLE_BINARY_RHS: + { + tree rhs1 = gimple_assign_rhs1 (stmt); + if (valueize && TREE_CODE (rhs1) == SSA_NAME) + { + rhs1 = valueize (rhs1); + if (!rhs1) + return NULL_TREE; + } + tree rhs2 = gimple_assign_rhs2 (stmt); + if (valueize && TREE_CODE (rhs2) == SSA_NAME) + { + rhs2 = valueize (rhs2); + if (!rhs2) + return NULL_TREE; + } + return gimple_match_and_simplify (code, type, rhs1, rhs2, + seq, valueize); + } + case GIMPLE_TERNARY_RHS: + { + tree rhs1 = gimple_assign_rhs1 (stmt); + if (valueize && TREE_CODE (rhs1) == SSA_NAME) + { + rhs1 = valueize (rhs1); + if (!rhs1) + return NULL_TREE; + } + tree rhs2 = gimple_assign_rhs2 (stmt); + if (valueize && TREE_CODE (rhs2) == SSA_NAME) + { + rhs2 = valueize (rhs2); + if (!rhs2) + return NULL_TREE; + } + tree rhs3 = gimple_assign_rhs3 (stmt); + if (valueize && TREE_CODE (rhs3) == SSA_NAME) + { + rhs3 = valueize (rhs3); + if (!rhs3) + return NULL_TREE; + } + return gimple_match_and_simplify (code, type, rhs1, rhs2, rhs3, + seq, valueize); + } + default: + gcc_unreachable (); + } + } + + /* ??? GIMPLE_CALL handling to be implemented. */ + + return NULL_TREE; + } + + /* Match and simplify on *GSI and replace that with the simplified stmt + sequence. */ + + bool + gimple_match_and_simplify (gimple_stmt_iterator *gsi, tree (*valueize)(tree)) + { + gimple stmt = gsi_stmt (*gsi); + if (gimple_has_lhs (stmt)) + { + tree lhs = gimple_get_lhs (stmt); + if (TREE_CODE (lhs) != SSA_NAME) + return false; + + gimple_seq seq = NULL; + tree res = gimple_match_and_simplify (lhs, &seq, valueize); + if (!res) + return false; + if (gimple_seq_empty_p (seq)) + { + if (is_gimple_assign (stmt)) + { + gimple_assign_set_rhs_from_tree (gsi, res); + update_stmt (gsi_stmt (*gsi)); + return true; + } + gimple tem = gimple_build_assign (lhs, res); + gsi_replace (gsi, tem, false); + return true; + } + else + { + /* ??? That's not really in-place operation - we can avoid + allocating the last stmt of the sequence, or at least + the SSA name for the result. */ + gimple_stmt_iterator si = gsi_last (seq); + gimple new_stmt = gsi_stmt (si); + gsi_remove (&si, false); + gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT); + release_ssa_name (gimple_get_lhs (new_stmt)); + gimple_assign_set_lhs (new_stmt, lhs); + gsi_replace (gsi, new_stmt, false); + return true; + } + } + + /* ??? Handle for example GIMPLE_CONDs. */ + + return false; + } + + /* Build the expression CODE OP0 of type TYPE with location LOC, + simplifying it first if possible using VALUEIZE if not NULL. + OP0 is expected to be valueized already. Returns the built + expression value and appends statements possibly defining it + to SEQ. */ + + tree + gimple_build (gimple_seq *seq, location_t loc, + enum tree_code code, tree type, tree op0, + tree (*valueize)(tree)) + { + if (CONSTANT_CLASS_P (op0)) + { + tree res = fold_unary_to_constant (code, type, op0); + gcc_assert (res != NULL_TREE); + return res; + } + + tree res = gimple_match_and_simplify (code, type, op0, seq, valueize); + if (!res) + { + res = make_ssa_name (type, NULL); + gimple stmt; + if (code == REALPART_EXPR + || code == IMAGPART_EXPR + || code == VIEW_CONVERT_EXPR) + stmt = gimple_build_assign_with_ops (code, res, + build1 (code, type, + op0), NULL_TREE); + else + stmt = gimple_build_assign_with_ops (code, res, op0, NULL_TREE); + gimple_set_location (stmt, loc); + gimple_seq_add_stmt_without_update (seq, stmt); + } + return res; + } + + /* Build the expression OP0 CODE OP1 of type TYPE with location LOC, + simplifying it first if possible using VALUEIZE if not NULL. + OP0 and OP1 are expected to be valueized already. Returns the built + expression value and appends statements possibly defining it + to SEQ. */ + + tree + gimple_build (gimple_seq *seq, location_t loc, + enum tree_code code, tree type, tree op0, tree op1, + tree (*valueize)(tree)) + { + if (CONSTANT_CLASS_P (op0) && CONSTANT_CLASS_P (op1)) + { + tree res = fold_binary_to_constant (code, type, op0, op1); + gcc_assert (res != NULL_TREE); + return res; + } + + /* Canonicalize operand order both for matching and fallback stmt + generation. */ + if (commutative_tree_code (code) + && tree_swap_operands_p (op0, op1, false)) + { + tree tem = op0; + op0 = op1; + op1 = tem; + } + + tree res = gimple_match_and_simplify (code, type, op0, op1, seq, valueize); + if (!res) + { + res = make_ssa_name (type, NULL); + gimple stmt = gimple_build_assign_with_ops (code, res, op0, op1); + gimple_set_location (stmt, loc); + gimple_seq_add_stmt_without_update (seq, stmt); + } + return res; + } + + + /* Build the expression (CODE OP0 OP1 OP2) of type TYPE with location LOC, + simplifying it first if possible using VALUEIZE if not NULL. + OP0, OP1 and OP2 are expected to be valueized already. Returns the built + expression value and appends statements possibly defining it + to SEQ. */ + + tree + gimple_build (gimple_seq *seq, location_t loc, + enum tree_code code, tree type, tree op0, tree op1, tree op2, + tree (*valueize)(tree)) + { + if (CONSTANT_CLASS_P (op0) && CONSTANT_CLASS_P (op1) + && CONSTANT_CLASS_P (op2)) + { + tree res = fold_ternary/*_to_constant */ (code, type, op0, op1, op2); + gcc_assert (res != NULL_TREE && CONSTANT_CLASS_P (res)); + return res; + } + + /* Canonicalize operand order both for matching and fallback stmt + generation. */ + if (commutative_ternary_tree_code (code) + && tree_swap_operands_p (op0, op1, false)) + { + tree tem = op0; + op0 = op1; + op1 = tem; + } + + tree res = gimple_match_and_simplify (code, type, op0, op1, op2, + seq, valueize); + if (!res) + { + res = make_ssa_name (type, NULL); + gimple stmt; + if (code == BIT_FIELD_REF) + stmt = gimple_build_assign_with_ops (code, res, + build3 (BIT_FIELD_REF, type, + op0, op1, op2), + NULL_TREE); + else + stmt = gimple_build_assign_with_ops (code, res, op0, op1, op2); + gimple_set_location (stmt, loc); + gimple_seq_add_stmt_without_update (seq, stmt); + } + return res; + } + Index: gcc/match.pd =================================================================== *** /dev/null 1970-01-01 00:00:00.000000000 +0000 --- gcc/match.pd 2014-03-06 13:25:18.051278981 +0100 *************** *** 0 **** --- 1,129 ---- + /* Transforms formerly done by tree-ssa-forwprop.c:associate_plusminus */ + + /* ??? Have match_and_simplify groups guarded with common + predicates on the outermost type? */ + + /* Contract negates. + ??? !TYPE_SATURATING condition missing. */ + (match_and_simplify + (PLUS_EXPR @0 (NEGATE_EXPR @1)) + /* Ugh, free form mixed in ... ;) Want (if ...) instead? */ + if (!TYPE_SATURATING (TREE_TYPE (@0))) + (MINUS_EXPR @0 @1)) + (match_and_simplify + /* ??? Allow (MINUS:!TYPE_SATURATING @0 (NEGATE @1)), thus + type predicates on operands? Thus also :INTEGRAL_TYPE_P + or @0:INTEGRAL_TYPE_P? */ + (MINUS @0 (NEGATE @1)) + (PLUS @0 @1)) + (match_and_simplify + (plus@2 (negate @0) @1) + if (!TYPE_SATURATING (TREE_TYPE (@2))) + (minus @1 @0)) + + /* Change to even more free-form like + + simplify (plus@2 (negate @0) @1) + if (!TYPE_SATURATING (TREE_TYPE (@2))) + to (minus @1 @0) + + so only patterns are lispy, the rest not? */ + + /* Match patterns that allow contracting a plus-minus pair + irrespective of overflow issues. + ??? !TYPE_SATURATING condition missing. + ??? !FLOAT_TYPE_P && !FIXED_POINT_TYPE_P condition missing + because of saturation to +-Inf. */ + + /* (A +- B) - A -> +-B. */ + (match_and_simplify + (MINUS_EXPR (PLUS_EXPR @0 @1) @0) + if (!TYPE_SATURATING (TREE_TYPE (@0)) + && !FLOAT_TYPE_P (TREE_TYPE (@0)) && !FIXED_POINT_TYPE_P (TREE_TYPE (@0))) + @1) + (match_and_simplify + (MINUS_EXPR (MINUS_EXPR @0 @1) @0) + (NEGATE_EXPR @1)) + /* (A +- B) -+ B -> A. */ + (match_and_simplify + (MINUS_EXPR (PLUS_EXPR @0 @1) @1) + @0) + (match_and_simplify + (PLUS_EXPR (MINUS_EXPR @0 @1) @1) + @0) + /* (CST +- A) +- CST -> CST' +- A. */ + /* match_and_simplify handles constant folding for us so we can + implement these as re-association patterns. + Watch out for operand order and constant canonicalization + we do! A - CST -> A + -CST, CST + A -> A + CST. */ + (match_and_simplify + (PLUS_EXPR (PLUS_EXPR @0 INTEGER_CST_P@1) INTEGER_CST_P@2) + (PLUS_EXPR @0 (PLUS_EXPR @1 @2))) + (match_and_simplify + (PLUS_EXPR (MINUS_EXPR INTEGER_CST_P@0 @1) INTEGER_CST_P@2) + (MINUS_EXPR (PLUS_EXPR @0 @2) @1)) + /* TODO: + (A +- CST) +- CST -> A +- CST + ~A + A -> -1 + ~A + 1 -> -A + A - (A +- B) -> -+ B + A +- (B +- A) -> +- B + CST +- (CST +- A) -> CST +- A + CST +- (A +- CST) -> CST +- A + A + ~A -> -1 + (T)(P + A) - (T)P -> (T)A + */ + + + /* Patterns required to avoid SCCVN testsuite regressions. */ + + /* (x >> 31) & 1 -> (x >> 31). Folding in fold-const is more + complicated here, it does + Fold (X << C1) & C2 into (X << C1) & (C2 | ((1 << C1) - 1)) + (X >> C1) & C2 into (X >> C1) & (C2 | ~((type) -1 >> C1)) + if the new mask might be further optimized. */ + (match_and_simplify + (bit_and (rshift@0 @1 INTEGER_CST_P@2) integer_onep) + if (compare_tree_int (@2, TYPE_PRECISION (TREE_TYPE (@1)) - 1) == 0) + @0) + + /* COMPLEX_EXPR and REALPART/IMAGPART_EXPR cancellations. */ + (match_and_simplify + (complex (realpart @0) (imagpart @0)) + @0) + (match_and_simplify + (realpart (complex @0 @1)) + @0) + (match_and_simplify + (imagpart (complex @0 @1)) + @1) + + /* One unary pattern. */ + + /* fold_negate_exprs convert - (~A) to A + 1. */ + (match_and_simplify + (negate (bit_not @0)) + if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) + (plus @0 { build_int_cst (TREE_TYPE (@0), 1); } )) + + /* One ternary pattern. */ + + /* Due to COND_EXPRs weirdness in GIMPLE the following won't work + without some hacks in the code generator. */ + (match_and_simplify + (cond (bit_not @0) @1 @2) + (cond @0 @2 @1)) + + /* match-and-simplify handles constant folding so we + can just do the decomposition here. */ + (match_and_simplify + (fma INTEGER_CST_P@0 INTEGER_CST_P@1 @3) + (plus (mult @0 @1) @3)) + + /* ????s + + We cannot reasonably match vector CONSTRUCTORs or vector constants + without using special predicates. Nor can we reasonably generate + variable-length stuff with pattern expressions. + + */ Index: gcc/gimple-fold.h =================================================================== *** gcc/gimple-fold.h.orig 2014-03-06 12:36:04.817482308 +0100 --- gcc/gimple-fold.h 2014-03-06 12:39:26.694468409 +0100 *************** extern tree gimple_fold_indirect_ref (tr *** 46,49 **** --- 46,105 ---- extern bool arith_code_with_undefined_signed_overflow (tree_code); extern gimple_seq rewrite_to_defined_overflow (gimple); + /* gimple_build, functionally matching fold_buildN, outputs stmts + int the provided sequence, matching and simplifying them on-the-fly. + Supposed to replace force_gimple_operand (fold_buildN (...), ...). */ + tree gimple_build (gimple_seq *, location_t, + enum tree_code, tree, tree, + tree (*valueize) (tree) = NULL); + inline tree + gimple_build (gimple_seq *seq, + enum tree_code code, tree type, tree op0) + { + return gimple_build (seq, UNKNOWN_LOCATION, code, type, op0); + } + tree gimple_build (gimple_seq *, location_t, + enum tree_code, tree, tree, tree, + tree (*valueize) (tree) = NULL); + inline tree + gimple_build (gimple_seq *seq, + enum tree_code code, tree type, tree op0, tree op1) + { + return gimple_build (seq, UNKNOWN_LOCATION, code, type, op0, op1); + } + tree gimple_build (gimple_seq *, location_t, + enum tree_code, tree, tree, tree, tree, + tree (*valueize) (tree) = NULL); + inline tree + gimple_build (gimple_seq *seq, + enum tree_code code, tree type, tree op0, tree op1, tree op2) + { + return gimple_build (seq, UNKNOWN_LOCATION, code, type, op0, op1, op2); + } + + /* ??? Forward from gimple-expr.h. */ + extern bool useless_type_conversion_p (tree, tree); + + inline tree + gimple_convert (gimple_seq *seq, tree type, tree op) + { + if (useless_type_conversion_p (type, TREE_TYPE (op))) + return op; + return gimple_build (seq, NOP_EXPR, type, op); + } + + bool gimple_match_and_simplify (gimple_stmt_iterator *, tree (*)(tree)); + + /* Add gimple_seq_discard (gimple_seq *) that releases defs of all stmts + in the sequence. */ + + /* In gimple-match.c. */ + tree gimple_match_and_simplify (tree, gimple_seq *, tree (*)(tree)); + tree gimple_match_and_simplify (enum tree_code, tree, tree, + gimple_seq *, tree (*)(tree)); + tree gimple_match_and_simplify (enum tree_code, tree, tree, tree, + gimple_seq *, tree (*)(tree)); + tree gimple_match_and_simplify (enum tree_code, tree, tree, tree, tree, + gimple_seq *, tree (*)(tree)); + #endif /* GCC_GIMPLE_FOLD_H */ Index: gcc/tree-ssa-sccvn.c =================================================================== *** gcc/tree-ssa-sccvn.c.orig 2014-03-06 12:36:04.817482308 +0100 --- gcc/tree-ssa-sccvn.c 2014-03-06 12:39:26.696468408 +0100 *************** try_to_simplify (gimple stmt) *** 3344,3378 **** if (code == SSA_NAME) return NULL_TREE; ! /* First try constant folding based on our current lattice. */ tem = gimple_fold_stmt_to_constant_1 (stmt, vn_valueize); if (tem && (TREE_CODE (tem) == SSA_NAME || is_gimple_min_invariant (tem))) return tem; ! /* If that didn't work try combining multiple statements. */ ! switch (TREE_CODE_CLASS (code)) ! { ! case tcc_reference: ! /* Fallthrough for some unary codes that can operate on registers. */ ! if (!(code == REALPART_EXPR ! || code == IMAGPART_EXPR ! || code == VIEW_CONVERT_EXPR ! || code == BIT_FIELD_REF)) ! break; ! /* We could do a little more with unary ops, if they expand ! into binary ops, but it's debatable whether it is worth it. */ ! case tcc_unary: ! return simplify_unary_expression (stmt); ! ! case tcc_comparison: ! case tcc_binary: ! return simplify_binary_expression (stmt); ! ! default: ! break; ! } return NULL_TREE; } --- 3344,3366 ---- if (code == SSA_NAME) return NULL_TREE; ! /* First try constant folding based on our current lattice. ! ??? Should be subsumed by gimple_match_and_simplify. */ tem = gimple_fold_stmt_to_constant_1 (stmt, vn_valueize); if (tem && (TREE_CODE (tem) == SSA_NAME || is_gimple_min_invariant (tem))) return tem; ! /* If that didn't work try combining multiple statements. ! ??? Handle multiple stmts being generated by storing ! at most one in VN_INFO->expr? But then we'd have to ! transparently support materializing temporary SSA names ! created by gimple_match_and_simplify - or we never value-number ! to them. */ ! if (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME) ! return gimple_match_and_simplify (gimple_assign_lhs (stmt), ! NULL, vn_valueize); return NULL_TREE; } Index: gcc/hash-table.c =================================================================== *** gcc/hash-table.c.orig 2014-03-06 12:36:04.817482308 +0100 --- gcc/hash-table.c 2014-03-06 12:39:26.696468408 +0100 *************** along with GCC; see the file COPYING3. *** 22,28 **** --- 22,32 ---- /* This file implements a typed hash table. The implementation borrows from libiberty's hashtab. */ + #ifdef GENERATOR_FILE + #include "bconfig.h" + #else #include "config.h" + #endif #include "system.h" #include "coretypes.h" #include "hash-table.h" Index: gcc/tree-ssa-forwprop.c =================================================================== *** gcc/tree-ssa-forwprop.c.orig 2014-03-06 12:36:04.817482308 +0100 --- gcc/tree-ssa-forwprop.c 2014-03-06 12:39:26.698468408 +0100 *************** simplify_mult (gimple_stmt_iterator *gsi *** 3569,3574 **** --- 3569,3592 ---- return false; } + + + /* Primitive "lattice" function for gimple_match_and_simplify to discard + matches on names whose definition contains abnormal SSA names. */ + + static tree + fwprop_ssa_val (tree name) + { + if (TREE_CODE (name) == SSA_NAME + /* ??? Fails for tem = name - name then. */ + && (!has_single_use (name) + || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name) + || (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI + && stmt_references_abnormal_ssa_name (SSA_NAME_DEF_STMT (name))))) + return NULL_TREE; + return name; + } + /* Main entry point for the forward propagation and statement combine optimizer. */ *************** ssa_forward_propagate_and_combine (void) *** 3681,3686 **** --- 3699,3719 ---- /* Mark stmt as potentially needing revisiting. */ gimple_set_plf (stmt, GF_PLF_1, false); + if (gimple_match_and_simplify (&gsi, fwprop_ssa_val)) + { + stmt = gsi_stmt (gsi); + if (maybe_clean_or_replace_eh_stmt (stmt, stmt) + && gimple_purge_dead_eh_edges (bb)) + cfg_changed = true; + changed = true; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "gimple_match_and_simplified to "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + } + + if (!changed) switch (gimple_code (stmt)) { case GIMPLE_ASSIGN: Index: gcc/tree-ssa-pre.c =================================================================== *** gcc/tree-ssa-pre.c.orig 2014-03-06 12:36:04.817482308 +0100 --- gcc/tree-ssa-pre.c 2014-03-06 12:39:26.698468408 +0100 *************** create_component_ref_by_pieces_1 (basic_ *** 2551,2559 **** { case CALL_EXPR: { ! tree folded, sc = NULL_TREE; ! unsigned int nargs = 0; ! tree fn, *args; if (TREE_CODE (currop->op0) == FUNCTION_DECL) fn = currop->op0; else --- 2551,2558 ---- { case CALL_EXPR: { ! tree sc = NULL_TREE; ! tree fn; if (TREE_CODE (currop->op0) == FUNCTION_DECL) fn = currop->op0; else *************** create_component_ref_by_pieces_1 (basic_ *** 2566,2588 **** if (!sc) return NULL_TREE; } ! args = XNEWVEC (tree, ref->operands.length () - 1); while (*operand < ref->operands.length ()) { ! args[nargs] = create_component_ref_by_pieces_1 (block, ref, ! operand, stmts); ! if (!args[nargs]) return NULL_TREE; ! nargs++; } ! folded = build_call_array (currop->type, ! (TREE_CODE (fn) == FUNCTION_DECL ! ? build_fold_addr_expr (fn) : fn), ! nargs, args); ! free (args); if (sc) ! CALL_EXPR_STATIC_CHAIN (folded) = sc; ! return folded; } case MEM_REF: --- 2565,2595 ---- if (!sc) return NULL_TREE; } ! auto_vec<tree> args (ref->operands.length () - 1); while (*operand < ref->operands.length ()) { ! tree arg = create_component_ref_by_pieces_1 (block, ! ref, operand, stmts); ! if (!arg) return NULL_TREE; ! args.quick_push (arg); } ! gimple call; ! call = gimple_build_call_vec ((TREE_CODE (fn) == FUNCTION_DECL ! ? build_fold_addr_expr (fn) : fn), args); if (sc) ! gimple_call_set_chain (call, sc); ! tree forcedname = make_ssa_name (currop->type, NULL); ! gimple_call_set_lhs (call, forcedname); ! gimple_seq_add_stmt_without_update (stmts, call); ! bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname)); ! VN_INFO_GET (forcedname)->valnum = forcedname; ! VN_INFO (forcedname)->value_id = get_next_value_id (); ! pre_expr nameexpr = get_or_alloc_expr_for_name (forcedname); ! add_to_value (VN_INFO (forcedname)->value_id, nameexpr); ! bitmap_value_replace_in_set (NEW_SETS (block), nameexpr); ! bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr); ! return forcedname; } case MEM_REF: *************** create_expression_by_pieces (basic_block *** 2896,2907 **** if (nary->opcode == POINTER_PLUS_EXPR) { if (i == 0) ! genop[i] = fold_convert (nary->type, genop[i]); else if (i == 1) ! genop[i] = convert_to_ptrofftype (genop[i]); } else ! genop[i] = fold_convert (TREE_TYPE (nary->op[i]), genop[i]); } if (nary->opcode == CONSTRUCTOR) { --- 2903,2915 ---- if (nary->opcode == POINTER_PLUS_EXPR) { if (i == 0) ! genop[i] = gimple_convert (&forced_stmts, nary->type, genop[i]); else if (i == 1) ! genop[i] = gimple_convert (&forced_stmts, sizetype, genop[i]); } else ! genop[i] = gimple_convert (&forced_stmts, ! TREE_TYPE (nary->op[i]), genop[i]); } if (nary->opcode == CONSTRUCTOR) { *************** create_expression_by_pieces (basic_block *** 2915,2930 **** switch (nary->length) { case 1: ! folded = fold_build1 (nary->opcode, nary->type, ! genop[0]); break; case 2: ! folded = fold_build2 (nary->opcode, nary->type, ! genop[0], genop[1]); break; case 3: ! folded = fold_build3 (nary->opcode, nary->type, ! genop[0], genop[1], genop[2]); break; default: gcc_unreachable (); --- 2923,2938 ---- switch (nary->length) { case 1: ! folded = gimple_build (&forced_stmts, nary->opcode, nary->type, ! genop[0]); break; case 2: ! folded = gimple_build (&forced_stmts, nary->opcode, nary->type, ! genop[0], genop[1]); break; case 3: ! folded = gimple_build (&forced_stmts, nary->opcode, nary->type, ! genop[0], genop[1], genop[2]); break; default: gcc_unreachable (); *************** create_expression_by_pieces (basic_block *** 2936,2950 **** gcc_unreachable (); } ! if (!useless_type_conversion_p (exprtype, TREE_TYPE (folded))) ! folded = fold_convert (exprtype, folded); ! ! /* Force the generated expression to be a sequence of GIMPLE ! statements. ! We have to call unshare_expr because force_gimple_operand may ! modify the tree we pass to it. */ ! folded = force_gimple_operand (unshare_expr (folded), &forced_stmts, ! false, NULL); /* If we have any intermediate expressions to the value sets, add them to the value sets and chain them in the instruction stream. */ --- 2944,2950 ---- gcc_unreachable (); } ! folded = gimple_convert (&forced_stmts, exprtype, folded); /* If we have any intermediate expressions to the value sets, add them to the value sets and chain them in the instruction stream. */ *************** insert_into_preds_of_block (basic_block *** 3144,3187 **** /* Constants may not have the right type, fold_convert should give us back a constant with the right type. */ tree constant = PRE_EXPR_CONSTANT (eprime); ! if (!useless_type_conversion_p (type, TREE_TYPE (constant))) { ! tree builtexpr = fold_convert (type, constant); ! if (!is_gimple_min_invariant (builtexpr)) { ! tree forcedexpr = force_gimple_operand (builtexpr, ! &stmts, true, ! NULL); ! if (!is_gimple_min_invariant (forcedexpr)) { ! if (forcedexpr != builtexpr) ! { ! VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime); ! VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime); ! } ! if (stmts) ! { ! gimple_stmt_iterator gsi; ! gsi = gsi_start (stmts); ! for (; !gsi_end_p (gsi); gsi_next (&gsi)) ! { ! gimple stmt = gsi_stmt (gsi); ! tree lhs = gimple_get_lhs (stmt); ! if (TREE_CODE (lhs) == SSA_NAME) ! bitmap_set_bit (inserted_exprs, ! SSA_NAME_VERSION (lhs)); ! gimple_set_plf (stmt, NECESSARY, false); ! } ! gsi_insert_seq_on_edge (pred, stmts); ! } ! avail[pred->dest_idx] ! = get_or_alloc_expr_for_name (forcedexpr); } } ! else ! avail[pred->dest_idx] ! = get_or_alloc_expr_for_constant (builtexpr); } } else if (eprime->kind == NAME) { --- 3144,3174 ---- /* Constants may not have the right type, fold_convert should give us back a constant with the right type. */ tree constant = PRE_EXPR_CONSTANT (eprime); ! tree forcedexpr = gimple_convert (&stmts, type, constant); ! if (!is_gimple_min_invariant (forcedexpr)) { ! VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime); ! VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime); ! if (!gimple_seq_empty_p (stmts)) { ! gimple_stmt_iterator gsi; ! gsi = gsi_start (stmts); ! for (; !gsi_end_p (gsi); gsi_next (&gsi)) { ! gimple stmt = gsi_stmt (gsi); ! tree lhs = gimple_get_lhs (stmt); ! if (TREE_CODE (lhs) == SSA_NAME) ! bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (lhs)); ! gimple_set_plf (stmt, NECESSARY, false); } + gsi_insert_seq_on_edge (pred, stmts); } ! avail[pred->dest_idx] ! = get_or_alloc_expr_for_name (forcedexpr); } + else + avail[pred->dest_idx] + = get_or_alloc_expr_for_constant (forcedexpr); } else if (eprime->kind == NAME) { *************** insert_into_preds_of_block (basic_block *** 3190,3226 **** our IL requires all operands of a phi node have the same type. */ tree name = PRE_EXPR_NAME (eprime); ! if (!useless_type_conversion_p (type, TREE_TYPE (name))) { ! tree builtexpr; ! tree forcedexpr; ! builtexpr = fold_convert (type, name); ! forcedexpr = force_gimple_operand (builtexpr, ! &stmts, true, ! NULL); ! ! if (forcedexpr != name) ! { ! VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum; ! VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id; ! } ! ! if (stmts) { ! gimple_stmt_iterator gsi; ! gsi = gsi_start (stmts); ! for (; !gsi_end_p (gsi); gsi_next (&gsi)) ! { ! gimple stmt = gsi_stmt (gsi); ! tree lhs = gimple_get_lhs (stmt); ! if (TREE_CODE (lhs) == SSA_NAME) ! bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (lhs)); ! gimple_set_plf (stmt, NECESSARY, false); ! } ! gsi_insert_seq_on_edge (pred, stmts); } ! avail[pred->dest_idx] = get_or_alloc_expr_for_name (forcedexpr); } } } /* If we didn't want a phi node, and we made insertions, we still have --- 3177,3203 ---- our IL requires all operands of a phi node have the same type. */ tree name = PRE_EXPR_NAME (eprime); ! tree forcedexpr = gimple_convert (&stmts, type, name); ! if (forcedexpr != name) { ! VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum; ! VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id; ! } ! if (!gimple_seq_empty_p (stmts)) ! { ! gimple_stmt_iterator gsi; ! gsi = gsi_start (stmts); ! for (; !gsi_end_p (gsi); gsi_next (&gsi)) { ! gimple stmt = gsi_stmt (gsi); ! tree lhs = gimple_get_lhs (stmt); ! if (TREE_CODE (lhs) == SSA_NAME) ! bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (lhs)); ! gimple_set_plf (stmt, NECESSARY, false); } ! gsi_insert_seq_on_edge (pred, stmts); } + avail[pred->dest_idx] = get_or_alloc_expr_for_name (forcedexpr); } } /* If we didn't want a phi node, and we made insertions, we still have ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-06 12:43 ` Richard Biener @ 2014-03-06 18:17 ` Prathamesh Kulkarni 2014-03-07 9:08 ` Richard Biener 0 siblings, 1 reply; 22+ messages in thread From: Prathamesh Kulkarni @ 2014-03-06 18:17 UTC (permalink / raw) To: Richard Biener; +Cc: gcc On Thu, Mar 6, 2014 at 6:13 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Thu, Mar 6, 2014 at 1:11 PM, Prathamesh Kulkarni > <bilbotheelffriend@gmail.com> wrote: >> On Mon, Mar 3, 2014 at 3:32 PM, Richard Biener >> <richard.guenther@gmail.com> wrote: >>> On Sun, Mar 2, 2014 at 9:13 PM, Prathamesh Kulkarni >>> <bilbotheelffriend@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. > 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-06 18:17 ` Prathamesh Kulkarni @ 2014-03-07 9:08 ` Richard Biener 2014-03-10 18:29 ` Prathamesh Kulkarni 0 siblings, 1 reply; 22+ messages in thread From: Richard Biener @ 2014-03-07 9:08 UTC (permalink / raw) To: Prathamesh Kulkarni; +Cc: gcc On Thu, Mar 6, 2014 at 7:17 PM, Prathamesh Kulkarni <bilbotheelffriend@gmail.com> wrote: > On Thu, Mar 6, 2014 at 6:13 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Thu, Mar 6, 2014 at 1:11 PM, Prathamesh Kulkarni >> <bilbotheelffriend@gmail.com> wrote: >>> On Mon, Mar 3, 2014 at 3:32 PM, Richard Biener >>> <richard.guenther@gmail.com> wrote: >>>> On Sun, Mar 2, 2014 at 9:13 PM, Prathamesh Kulkarni >>>> <bilbotheelffriend@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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-07 9:08 ` Richard Biener @ 2014-03-10 18:29 ` Prathamesh Kulkarni 2014-03-11 11:20 ` Richard Biener 0 siblings, 1 reply; 22+ messages in thread From: Prathamesh Kulkarni @ 2014-03-10 18:29 UTC (permalink / raw) To: Richard Biener; +Cc: gcc On Fri, Mar 7, 2014 at 2:38 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Thu, Mar 6, 2014 at 7:17 PM, Prathamesh Kulkarni > <bilbotheelffriend@gmail.com> wrote: >> On Thu, Mar 6, 2014 at 6:13 PM, Richard Biener >> <richard.guenther@gmail.com> wrote: >>> On Thu, Mar 6, 2014 at 1:11 PM, Prathamesh Kulkarni >>> <bilbotheelffriend@gmail.com> wrote: >>>> On Mon, Mar 3, 2014 at 3:32 PM, Richard Biener >>>> <richard.guenther@gmail.com> wrote: >>>>> On Sun, Mar 2, 2014 at 9:13 PM, Prathamesh Kulkarni >>>>> <bilbotheelffriend@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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-10 18:29 ` Prathamesh Kulkarni @ 2014-03-11 11:20 ` Richard Biener 2014-03-13 11:14 ` Richard Biener 0 siblings, 1 reply; 22+ messages in thread From: Richard Biener @ 2014-03-11 11:20 UTC (permalink / raw) To: Prathamesh Kulkarni; +Cc: gcc On Mon, Mar 10, 2014 at 7:29 PM, Prathamesh Kulkarni <bilbotheelffriend@gmail.com> 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 <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 ? 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 <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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-11 11:20 ` Richard Biener @ 2014-03-13 11:14 ` Richard Biener 2014-03-14 15:31 ` Prathamesh Kulkarni 0 siblings, 1 reply; 22+ messages in thread From: Richard Biener @ 2014-03-13 11:14 UTC (permalink / raw) To: Prathamesh Kulkarni; +Cc: gcc On Tue, Mar 11, 2014 at 12:20 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Mon, Mar 10, 2014 at 7:29 PM, Prathamesh Kulkarni > <bilbotheelffriend@gmail.com> 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 <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 ? > > 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 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 <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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-13 11:14 ` Richard Biener @ 2014-03-14 15:31 ` Prathamesh Kulkarni 2014-03-14 15:35 ` Prathamesh Kulkarni ` (2 more replies) 0 siblings, 3 replies; 22+ messages in thread From: Prathamesh Kulkarni @ 2014-03-14 15:31 UTC (permalink / raw) To: Richard Biener; +Cc: gcc [-- Attachment #1: Type: text/plain, Size: 13341 bytes --] On Thu, Mar 13, 2014 at 4:44 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Tue, Mar 11, 2014 at 12:20 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Mon, Mar 10, 2014 at 7:29 PM, Prathamesh Kulkarni >> <bilbotheelffriend@gmail.com> 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 <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 ? >> >> 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) { <bb 2>: if (a_1(D) > 8) goto <bb 3>; else goto <bb 4>; <bb 3>: bar (); <bb 4>: return; } ;; Function baz (baz, funcdef_no=1, decl_uid=1748, symbol_order=1) baz (unsigned int a) { <bb 2>: if (a_1(D) <= 7) goto <bb 3>; else goto <bb 4>; <bb 3>: bar (); <bb 4>: 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 <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 [-- Attachment #2: 14753.patch --] [-- Type: text/x-patch, Size: 1674 bytes --] Index: gcc/fold-const.c =================================================================== --- gcc/fold-const.c (revision 208539) +++ gcc/fold-const.c (working copy) @@ -68,6 +68,7 @@ along with GCC; see the file COPYING3. #include "gimplify.h" #include "tree-dfa.h" #include "hash-table.h" /* Required for ENABLE_FOLD_CHECKING. */ +#include "tree-pretty-print.h" /* Nonzero if we are folding constants inside an initializer; zero otherwise. */ @@ -9698,6 +9699,33 @@ fold_comparison (location_t loc, enum tr fold_convert_loc (loc, cmp_type, arg1))); } + /* Fold (X >> CST1) > CST2 -> X > CST2 << CST1 */ + if (TREE_CODE (arg0) == RSHIFT_EXPR && code == GT_EXPR) + { + tree var = TREE_OPERAND (arg0, 0); + tree cst1 = TREE_OPERAND (arg0, 1); + if ((TREE_CODE (cst1) == INTEGER_CST || TREE_CODE (arg1) == VECTOR_CST) + && (TREE_CODE (arg1) == INTEGER_CST || TREE_CODE (arg1) == VECTOR_CST)) + return fold_build2_loc (loc, GT_EXPR, type, var, + fold_convert_loc (loc, TREE_TYPE (var), + int_const_binop (LSHIFT_EXPR, cst1, arg1))); + } + + /* Fold (X & CST) == 0 -> X <= ~CST */ + if (TREE_CODE (arg0) == BIT_AND_EXPR && code == EQ_EXPR && integer_zerop (arg1)) + { + tree var = TREE_OPERAND (arg0, 0); + tree cst = TREE_OPERAND (arg0, 1); + tree bit_not_expr; + + if (TREE_CODE (cst) == INTEGER_CST || TREE_CODE (cst) == VECTOR_CST) + { + bit_not_expr = fold_unary (BIT_NOT_EXPR, TREE_TYPE (cst), cst); + return fold_build2_loc (loc, LE_EXPR, type, var, + fold_convert_loc (loc, TREE_TYPE (var), bit_not_expr)); + } + } + return NULL_TREE; } ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-14 15:31 ` Prathamesh Kulkarni @ 2014-03-14 15:35 ` Prathamesh Kulkarni 2014-03-14 15:55 ` Marc Glisse 2014-03-14 17:16 ` Richard Biener 2 siblings, 0 replies; 22+ messages in thread From: Prathamesh Kulkarni @ 2014-03-14 15:35 UTC (permalink / raw) To: Richard Biener; +Cc: gcc On Fri, Mar 14, 2014 at 9:01 PM, Prathamesh Kulkarni <bilbotheelffriend@gmail.com> wrote: > On Thu, Mar 13, 2014 at 4:44 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Tue, Mar 11, 2014 at 12:20 PM, Richard Biener >> <richard.guenther@gmail.com> wrote: >>> On Mon, Mar 10, 2014 at 7:29 PM, Prathamesh Kulkarni >>> <bilbotheelffriend@gmail.com> 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 <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 ? >>> >>> 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) > { > <bb 2>: > if (a_1(D) > 8) > goto <bb 3>; > else > goto <bb 4>; > > <bb 3>: > bar (); > > <bb 4>: > return; > > } > > ;; Function baz (baz, funcdef_no=1, decl_uid=1748, symbol_order=1) > > baz (unsigned int a) > { > <bb 2>: > if (a_1(D) <= 7) > goto <bb 3>; > else > goto <bb 4>; > > <bb 3>: > bar (); > > <bb 4>: > 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. Sorry, that got accidentally repeated. > 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 <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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-14 15:31 ` Prathamesh Kulkarni 2014-03-14 15:35 ` Prathamesh Kulkarni @ 2014-03-14 15:55 ` Marc Glisse 2014-03-14 16:37 ` Prathamesh Kulkarni 2014-03-14 17:16 ` Richard Biener 2 siblings, 1 reply; 22+ messages in thread From: Marc Glisse @ 2014-03-14 15:55 UTC (permalink / raw) To: Prathamesh Kulkarni; +Cc: Richard Biener, gcc On Fri, 14 Mar 2014, Prathamesh Kulkarni wrote: > 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. Why not directly gimple or the .pd file? > 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 That's not the same, try X=1, CST1=1, CST2=0. > b) (X & ~CST) == 0 -> X <= CST Uh, that can't be true for all constants, only some with a very specific shape (7 is 2^3-1). -- Marc Glisse ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-14 15:55 ` Marc Glisse @ 2014-03-14 16:37 ` Prathamesh Kulkarni 2014-03-14 17:54 ` Marc Glisse 0 siblings, 1 reply; 22+ messages in thread From: Prathamesh Kulkarni @ 2014-03-14 16:37 UTC (permalink / raw) To: marc.glisse, gcc; +Cc: Richard Biener On Fri, Mar 14, 2014 at 9:25 PM, Marc Glisse <marc.glisse@inria.fr> wrote: > On Fri, 14 Mar 2014, Prathamesh Kulkarni wrote: > >> 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. > > > Why not directly gimple or the .pd file? > > >> 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 > > > That's not the same, try X=1, CST1=1, CST2=0. Ah yes. Shall following be correct ? (X >> CST1) > CST2 -> X > ( (CST2 + 1) << CST1 ) - 1 Works correctly for X=1, CST1 = 1, CST2 = 0 (X >> CST1) > CST2 => (X >> CST1) >= (CST2 + 1) // this pattern is mentioned in PR => X >= (CST2 + 1) << CST1 => X > ((CST2 + 1) << CST1) - 1 > > >> b) (X & ~CST) == 0 -> X <= CST > > > Uh, that can't be true for all constants, only some with a very specific > shape (7 is 2^3-1). Agreed. Shall the pattern be folded if CST is 2^(n-1) ? > > -- > Marc Glisse ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-14 16:37 ` Prathamesh Kulkarni @ 2014-03-14 17:54 ` Marc Glisse 0 siblings, 0 replies; 22+ messages in thread From: Marc Glisse @ 2014-03-14 17:54 UTC (permalink / raw) To: Prathamesh Kulkarni; +Cc: gcc, Richard Biener On Fri, 14 Mar 2014, Prathamesh Kulkarni wrote: > On Fri, Mar 14, 2014 at 9:25 PM, Marc Glisse <marc.glisse@inria.fr> wrote: >> On Fri, 14 Mar 2014, Prathamesh Kulkarni wrote: >> >>> 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 >> >> That's not the same, try X=1, CST1=1, CST2=0. > Ah yes. Shall following be correct ? > (X >> CST1) > CST2 -> X > ( (CST2 + 1) << CST1 ) - 1 > Works correctly for X=1, CST1 = 1, CST2 = 0 Looks better. Though there is still the case where the new constant overflows, in which case we can fold the comparison to false. >>> b) (X & ~CST) == 0 -> X <= CST >> >> Uh, that can't be true for all constants, only some with a very specific >> shape (7 is 2^3-1). > Agreed. Shall the pattern be folded if CST is 2^(n-1) ? Wrong parentheses. And I didn't really think about it, so that may not be the right test. I think it would be a good idea to write, in comments, next to each non-trivial transformation, a short "proof" (at least some form of explanation). It would help people re-reading it later see quickly why the conditions are what they are. -- Marc Glisse ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-14 15:31 ` Prathamesh Kulkarni 2014-03-14 15:35 ` Prathamesh Kulkarni 2014-03-14 15:55 ` Marc Glisse @ 2014-03-14 17:16 ` Richard Biener 2014-03-16 12:21 ` Prathamesh Kulkarni 2 siblings, 1 reply; 22+ messages in thread From: Richard Biener @ 2014-03-14 17:16 UTC (permalink / raw) To: Prathamesh Kulkarni; +Cc: gcc On Fri, Mar 14, 2014 at 4:31 PM, Prathamesh Kulkarni <bilbotheelffriend@gmail.com> wrote: > On Thu, Mar 13, 2014 at 4:44 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Tue, Mar 11, 2014 at 12:20 PM, Richard Biener >> <richard.guenther@gmail.com> wrote: >>> On Mon, Mar 10, 2014 at 7:29 PM, Prathamesh Kulkarni >>> <bilbotheelffriend@gmail.com> 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 <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 ? >>> >>> 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 ? If that means you wrote a pattern for genmatch then yes. The transforms should then in the end operate both on GENERIC and GIMPLE. > 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) Good. > 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) > { > <bb 2>: > if (a_1(D) > 8) > goto <bb 3>; > else > goto <bb 4>; > > <bb 3>: > bar (); > > <bb 4>: > return; > > } > > ;; Function baz (baz, funcdef_no=1, decl_uid=1748, symbol_order=1) > > baz (unsigned int a) > { > <bb 2>: > if (a_1(D) <= 7) > goto <bb 3>; > else > goto <bb 4>; > > <bb 3>: > bar (); > > <bb 4>: > return; > > } Note that to test whether the transform applies when we are still in GENERIC (thus before gimplification) the testcase needs to see the whole expression in a single statemtent (like the testcases in the bugreport are written). To verify it also applies on GIMPLE while making sure it isn't simplified earlier on GENERIC you should separate the to simplify pattern to separate statements like for example void foo (unsigned int a) { /* This one is equivalent to a >= (3 << 2). */ int tem = a >> 2; if (tem >= 3) bar (); } then fold-const.c will not be able to simplify it but a later GIMPLE pass like forwprop should be able to do that. > 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? It's more because each optimization pass may introduce opportunities for folding and we have optimization passes on GIMPLE and RTL. And the frontends that operate on GENERIC (C and C++ for example) need fold-const.c to fold constant initializers like for 'const int i = a - a'. > So it is needed > to be performed at each level ? Yes. The goal with writing patterns for genmatch is that we need to write them only once for GENERIC and GIMPLE (targeting RTL at the same time is much harder). > 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 ? The .md files are actually only used for instruction selection and RTL expansion. Folding opportunities arise due to weaknesses in RTL expansion and RTL optimization passes exposing new opportunities. RTL actually has a similar pass like GIMPLE forwprop - it's 'combine' that combines and simplifies up to four RTL instructions to try matching more complex instructions from the .md descriptions. > b) Why do we want to target GENERIC too ? To not regress and to avoid duplicating code when implementing transforms that fold-const.c currently does on the GIMPLE level. > If I understand correctly, currently gimple folding is done by > genericizing (fold_stmt) ? Indeed most of the folding we do on GIMPLE happens by building GENERIC, feeding that to fold-const.c and re-gimplifying the result. That's super-ugly (and not exactly cheap either). In tree-ssa-forwprop there are the beginnings of a real "GIMPLE folder" but pattern matching manually on GIMPLE is awkward and we'd have to duplicate the actual simplifications on GENERIC and GIMPLE - the goal with genmatch is to be able to write each transform only once and get the GENERIC and GIMPLE folder created automatically. > 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 ? No, that's entirely correct. > 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. Yeah, I'd leave some spare time for that in the May 19 - June 27 time frame - I guess that d) may run into some limitations. > 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. Please also add some time to amend the testsuite - most GENERIC folding in fold-const.c should have a testcase already (ok, that's a bit optimistic), testcases for folding happening on GIMPLE are rare. Ideally there should be testcases for the GENERIC and GIMPLE part for each pattern you add (testcases that the pattern applies). > I shall get a draft of > the proposal ready within a couple of days. Thanks, Richard. > 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 <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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-14 17:16 ` Richard Biener @ 2014-03-16 12:21 ` Prathamesh Kulkarni 2014-03-17 8:52 ` Richard Biener 0 siblings, 1 reply; 22+ messages in thread From: Prathamesh Kulkarni @ 2014-03-16 12:21 UTC (permalink / raw) To: Richard Biener; +Cc: gcc [-- Attachment #1: Type: text/plain, Size: 17582 bytes --] On Fri, Mar 14, 2014 at 10:46 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Fri, Mar 14, 2014 at 4:31 PM, Prathamesh Kulkarni > <bilbotheelffriend@gmail.com> wrote: >> On Thu, Mar 13, 2014 at 4:44 PM, Richard Biener >> <richard.guenther@gmail.com> wrote: >>> On Tue, Mar 11, 2014 at 12:20 PM, Richard Biener >>> <richard.guenther@gmail.com> wrote: >>>> On Mon, Mar 10, 2014 at 7:29 PM, Prathamesh Kulkarni >>>> <bilbotheelffriend@gmail.com> 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 <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 ? >>>> >>>> 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 ? > > If that means you wrote a pattern for genmatch then yes. The transforms > should then in the end operate both on GENERIC and GIMPLE. > >> 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) > > Good. > >> 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) >> { >> <bb 2>: >> if (a_1(D) > 8) >> goto <bb 3>; >> else >> goto <bb 4>; >> >> <bb 3>: >> bar (); >> >> <bb 4>: >> return; >> >> } >> >> ;; Function baz (baz, funcdef_no=1, decl_uid=1748, symbol_order=1) >> >> baz (unsigned int a) >> { >> <bb 2>: >> if (a_1(D) <= 7) >> goto <bb 3>; >> else >> goto <bb 4>; >> >> <bb 3>: >> bar (); >> >> <bb 4>: >> return; >> >> } > > Note that to test whether the transform applies when we are still > in GENERIC (thus before gimplification) the testcase needs > to see the whole expression in a single statemtent (like the > testcases in the bugreport are written). To verify it also applies > on GIMPLE while making sure it isn't simplified earlier on GENERIC > you should separate the to simplify pattern to separate statements like > for example > > void > foo (unsigned int a) > { > /* This one is equivalent to a >= (3 << 2). */ > int tem = a >> 2; > if (tem >= 3) > bar (); > } > > then fold-const.c will not be able to simplify it but a later GIMPLE > pass like forwprop should be able to do that. > >> 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? > > It's more because each optimization pass may introduce opportunities > for folding and we have optimization passes on GIMPLE and RTL. > And the frontends that operate on GENERIC (C and C++ for example) > need fold-const.c to fold constant initializers like for 'const int i = a - a'. > >> So it is needed >> to be performed at each level ? > > Yes. The goal with writing patterns for genmatch is that we need to > write them only once for GENERIC and GIMPLE (targeting RTL at > the same time is much harder). > >> 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 ? > > The .md files are actually only used for instruction selection and RTL > expansion. Folding opportunities arise due to weaknesses in RTL > expansion and RTL optimization passes exposing new opportunities. > RTL actually has a similar pass like GIMPLE forwprop - it's 'combine' > that combines and simplifies up to four RTL instructions to try matching > more complex instructions from the .md descriptions. > >> b) Why do we want to target GENERIC too ? > > To not regress and to avoid duplicating code when implementing > transforms that fold-const.c currently does on the GIMPLE level. > >> If I understand correctly, currently gimple folding is done by >> genericizing (fold_stmt) ? > > Indeed most of the folding we do on GIMPLE happens by building > GENERIC, feeding that to fold-const.c and re-gimplifying the result. > That's super-ugly (and not exactly cheap either). In tree-ssa-forwprop > there are the beginnings of a real "GIMPLE folder" but pattern matching > manually on GIMPLE is awkward and we'd have to duplicate the actual > simplifications on GENERIC and GIMPLE - the goal with genmatch > is to be able to write each transform only once and get the GENERIC > and GIMPLE folder created automatically. > >> 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 ? > > No, that's entirely correct. > >> 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. > > Yeah, I'd leave some spare time for that in the May 19 - June 27 > time frame - I guess that d) may run into some limitations. > >> 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. > > Please also add some time to amend the testsuite - most GENERIC > folding in fold-const.c should have a testcase already (ok, that's a bit > optimistic), testcases for folding happening on GIMPLE are rare. > > Ideally there should be testcases for the GENERIC and GIMPLE part for > each pattern you add (testcases that the pattern applies). > >> I shall get a draft of >> the proposal ready within a couple of days. > In c_expr::c_expr, shouldn't OP_C_EXPR be passed to operand constructor instead of OP_EXPR ? This caused segfault for patterns when "simplification" operand was only c_expr (patch attached). * genmatch.c (c_expr::c_expr): use OP_C_EXPR instead of OP_EXPR in call to operand constructor. Thanks and Regards, Prathamesh > Thanks, > Richard. > >> 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 <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 [-- Attachment #2: foo.patch --] [-- Type: text/x-patch, Size: 538 bytes --] Index: gcc/genmatch.c =================================================================== --- gcc/genmatch.c (revision 208605) +++ gcc/genmatch.c (working copy) @@ -191,7 +191,7 @@ struct expr : public operand struct c_expr : public operand { c_expr (const char *code_) - : operand (OP_EXPR), code (code_) {} + : operand (OP_C_EXPR), code (code_) {} const char *code; virtual void gen_gimple_match (FILE *, const char *, const char *) { gcc_unreachable (); } virtual void gen_gimple_transform (FILE *f, const char *); ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-16 12:21 ` Prathamesh Kulkarni @ 2014-03-17 8:52 ` Richard Biener 2014-03-18 8:13 ` Prathamesh Kulkarni [not found] ` <CAJXstsD0Y=vBxw9QveOU3O3jhQgbYkxj_iyfje=AFypHEmK9gA@mail.gmail.com> 0 siblings, 2 replies; 22+ messages in thread From: Richard Biener @ 2014-03-17 8:52 UTC (permalink / raw) To: Prathamesh Kulkarni; +Cc: gcc On Sun, Mar 16, 2014 at 1:21 PM, Prathamesh Kulkarni <bilbotheelffriend@gmail.com> wrote: > In c_expr::c_expr, shouldn't OP_C_EXPR be passed to operand > constructor instead of OP_EXPR ? Indeed - I have committed the fix. Thanks, Richard. > This caused segfault for patterns when "simplification" operand was > only c_expr (patch attached). > > * genmatch.c (c_expr::c_expr): use OP_C_EXPR instead of OP_EXPR in > call to operand constructor. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-17 8:52 ` Richard Biener @ 2014-03-18 8:13 ` Prathamesh Kulkarni 2014-03-19 0:27 ` Maxim Kuvyrkov [not found] ` <CAJXstsD0Y=vBxw9QveOU3O3jhQgbYkxj_iyfje=AFypHEmK9gA@mail.gmail.com> 1 sibling, 1 reply; 22+ messages in thread From: Prathamesh Kulkarni @ 2014-03-18 8:13 UTC (permalink / raw) To: Richard Biener; +Cc: gcc On Mon, Mar 17, 2014 at 2:22 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Sun, Mar 16, 2014 at 1:21 PM, Prathamesh Kulkarni > <bilbotheelffriend@gmail.com> wrote: >> In c_expr::c_expr, shouldn't OP_C_EXPR be passed to operand >> constructor instead of OP_EXPR ? > > Indeed - I have committed the fix. > My earlier mail got rejected (maybe because I attached pdf ?), by mailer daemon, sorry for the double post. I have uploaded the proposal here: https://drive.google.com/file/d/0B7zFk-y3DFiHa1Nkdzh6TFZpVFE/edit?usp=sharing I would be grateful to receive your feedback. Thanks and Regards, Prathamesh > Thanks, > Richard. > >> This caused segfault for patterns when "simplification" operand was >> only c_expr (patch attached). >> >> * genmatch.c (c_expr::c_expr): use OP_C_EXPR instead of OP_EXPR in >> call to operand constructor. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-18 8:13 ` Prathamesh Kulkarni @ 2014-03-19 0:27 ` Maxim Kuvyrkov 0 siblings, 0 replies; 22+ messages in thread From: Maxim Kuvyrkov @ 2014-03-19 0:27 UTC (permalink / raw) To: Prathamesh Kulkarni; +Cc: Richard Biener, gcc On Mar 18, 2014, at 9:13 PM, Prathamesh Kulkarni <bilbotheelffriend@gmail.com> wrote: > On Mon, Mar 17, 2014 at 2:22 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Sun, Mar 16, 2014 at 1:21 PM, Prathamesh Kulkarni >> <bilbotheelffriend@gmail.com> wrote: >>> In c_expr::c_expr, shouldn't OP_C_EXPR be passed to operand >>> constructor instead of OP_EXPR ? >> >> Indeed - I have committed the fix. >> > My earlier mail got rejected (maybe because I attached pdf ?), > by mailer daemon, sorry for the double post. > I have uploaded the proposal here: > https://drive.google.com/file/d/0B7zFk-y3DFiHa1Nkdzh6TFZpVFE/edit?usp=sharing > I would be grateful to receive your feedback. Prathamesh, I will let Richard to comment on the proposal contents, but make sure you have formally applied on the GSoC website and uploaded some version of your proposal by end of Thursday (only 2 days left!). You will be able to update details of the proposal later. Thank you, -- Maxim Kuvyrkov www.linaro.org ^ permalink raw reply [flat|nested] 22+ messages in thread
[parent not found: <CAJXstsD0Y=vBxw9QveOU3O3jhQgbYkxj_iyfje=AFypHEmK9gA@mail.gmail.com>]
* Re: [gsoc 2014] moving fold-const patterns to gimple [not found] ` <CAJXstsD0Y=vBxw9QveOU3O3jhQgbYkxj_iyfje=AFypHEmK9gA@mail.gmail.com> @ 2014-03-19 9:43 ` Richard Biener 2014-03-20 20:52 ` Prathamesh Kulkarni 0 siblings, 1 reply; 22+ messages in thread From: Richard Biener @ 2014-03-19 9:43 UTC (permalink / raw) To: Prathamesh Kulkarni; +Cc: gcc On Tue, Mar 18, 2014 at 9:04 AM, Prathamesh Kulkarni <bilbotheelffriend@gmail.com> wrote: > On Mon, Mar 17, 2014 at 2:22 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Sun, Mar 16, 2014 at 1:21 PM, Prathamesh Kulkarni >> <bilbotheelffriend@gmail.com> wrote: >>> In c_expr::c_expr, shouldn't OP_C_EXPR be passed to operand >>> constructor instead of OP_EXPR ? >> >> Indeed - I have committed the fix. >> > Hi, I have attached an initial draft of my proposal. > I would be grateful to receive your feedback. Ok, I had a look at the proposal and it is mostly fine. I'd be more specific on the deliverables, specifically 1) genmatch - program to read meta description and generate code to simplify GENERIC and GIMPLE according to the pattern descriptions using an algorithm not linear in the number of patterns 2) add patterns matched by tree-ssa-forwprop.c (and thus patterns in fold-const.c it depends on) to the meta-description and perform the simplifications of tree-ssa-forwprop.c in terms of the simplification API You will figure out that there are possibly a lot of patterns in fold-const.c that forwprop depends on (I know mainly of all the comparison simplifications). For the Timeline I'd move e) as a sub-task of f) to June 28 - July 16, eventually just dividing the weeks of July 17 - August 11 to that and the following task. That is, the overall deliverable should be a tree-ssa-forwprop.c that is (mostly) implemented in terms of patterns, ready for commit to trunk during stage1. As for targeting GENERIC, useful testing coverage of that path will come from for example re-writing fold-const.c:fold_comparison using the GENERIC API of the pattern simplifier. The devil will be in the details (as always) ;) As Maxim said - make sure to register your proposal in-time, you can always improve on it later. Thanks, Richard. > Thanks and Regards, > Prathamesh >> Thanks, >> Richard. >> >>> This caused segfault for patterns when "simplification" operand was >>> only c_expr (patch attached). >>> >>> * genmatch.c (c_expr::c_expr): use OP_C_EXPR instead of OP_EXPR in >>> call to operand constructor. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-19 9:43 ` Richard Biener @ 2014-03-20 20:52 ` Prathamesh Kulkarni 2014-03-21 9:49 ` Richard Biener 0 siblings, 1 reply; 22+ messages in thread From: Prathamesh Kulkarni @ 2014-03-20 20:52 UTC (permalink / raw) To: Richard Biener; +Cc: gcc On Wed, Mar 19, 2014 at 3:13 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Tue, Mar 18, 2014 at 9:04 AM, Prathamesh Kulkarni > <bilbotheelffriend@gmail.com> wrote: >> On Mon, Mar 17, 2014 at 2:22 PM, Richard Biener >> <richard.guenther@gmail.com> wrote: >>> On Sun, Mar 16, 2014 at 1:21 PM, Prathamesh Kulkarni >>> <bilbotheelffriend@gmail.com> wrote: >>>> In c_expr::c_expr, shouldn't OP_C_EXPR be passed to operand >>>> constructor instead of OP_EXPR ? >>> >>> Indeed - I have committed the fix. >>> >> Hi, I have attached an initial draft of my proposal. >> I would be grateful to receive your feedback. > > Ok, I had a look at the proposal and it is mostly fine. I'd be more specific > on the deliverables, specifically > > 1) genmatch - program to read meta description and generate code to > simplify GENERIC and GIMPLE according to the pattern descriptions > using an algorithm not linear in the number of patterns > > 2) add patterns matched by tree-ssa-forwprop.c (and thus patterns > in fold-const.c it depends on) to the meta-description and perform > the simplifications of tree-ssa-forwprop.c in terms of the simplification API > > You will figure out that there are possibly a lot of patterns in fold-const.c > that forwprop depends on (I know mainly of all the comparison simplifications). > > For the Timeline I'd move e) as a sub-task of f) to June 28 - July 16, > eventually just dividing the weeks of July 17 - August 11 to that and > the following task. > > That is, the overall deliverable should be a tree-ssa-forwprop.c that is > (mostly) implemented in terms of patterns, ready for commit to trunk > during stage1. > > As for targeting GENERIC, useful testing coverage of that path will > come from for example re-writing fold-const.c:fold_comparison using > the GENERIC API of the pattern simplifier. > > The devil will be in the details (as always) ;) > > As Maxim said - make sure to register your proposal in-time, you > can always improve on it later. > Thanks for the feedback. I have uploaded it: http://www.google-melange.com/gsoc/proposal/public/google/gsoc2014/prathamesh3492/5629499534213120 Would you like to suggest any further changes ? There are a few formatting glitches, I am fixing those. Could you help me point out how to write test-cases for transforms ? For example: /* Fold ~A + 1 -> -A */ (match_and_simplify (PLUS_EXPR (BIT_NOT_EXPR @0) @1) if (@1 == integer_one_node) (NEGATE_EXPR @0)) Is the following test-case correctly written ? /* { dg-do compile } */ /* { dg-options "-O -fdump-tree-forwprop" } */ int foo (int x) { int temp1 = ~x; int temp2 = temp1 + 1; return temp2; } /* { dg-final { scan-tree-dump "temp* = -x*(D)" "forwprop1" } } */ Shall that be (somewhat) correct ? (Unfortunately, I cannot check if I have written the test-case correctly, because I am in the middle of a bootstrap build. Is there a way to run test-cases on only stage-1 compiler ? I tried make check-cc1 RUNTESTFLAGS=dg.exp=tree-ssa/match-2.c but that did not work). forwprop output is: ;; Function foo (foo, funcdef_no=0, decl_uid=1743, symbol_order=0) gimple_match_and_simplified to temp2_3 = -x_1(D); foo (int x) { int temp2; int temp1; <bb 2>: temp1_2 = ~x_1(D); temp2_3 = -x_1(D); temp2_4 = temp2_3; return temp2_4; } Thanks and Regards, Prathamesh > Thanks, > Richard. > >> Thanks and Regards, >> Prathamesh >>> Thanks, >>> Richard. >>> >>>> This caused segfault for patterns when "simplification" operand was >>>> only c_expr (patch attached). >>>> >>>> * genmatch.c (c_expr::c_expr): use OP_C_EXPR instead of OP_EXPR in >>>> call to operand constructor. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [gsoc 2014] moving fold-const patterns to gimple 2014-03-20 20:52 ` Prathamesh Kulkarni @ 2014-03-21 9:49 ` Richard Biener 0 siblings, 0 replies; 22+ messages in thread From: Richard Biener @ 2014-03-21 9:49 UTC (permalink / raw) To: Prathamesh Kulkarni; +Cc: gcc On Thu, Mar 20, 2014 at 9:52 PM, Prathamesh Kulkarni <bilbotheelffriend@gmail.com> wrote: > On Wed, Mar 19, 2014 at 3:13 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Tue, Mar 18, 2014 at 9:04 AM, Prathamesh Kulkarni >> <bilbotheelffriend@gmail.com> wrote: >>> On Mon, Mar 17, 2014 at 2:22 PM, Richard Biener >>> <richard.guenther@gmail.com> wrote: >>>> On Sun, Mar 16, 2014 at 1:21 PM, Prathamesh Kulkarni >>>> <bilbotheelffriend@gmail.com> wrote: >>>>> In c_expr::c_expr, shouldn't OP_C_EXPR be passed to operand >>>>> constructor instead of OP_EXPR ? >>>> >>>> Indeed - I have committed the fix. >>>> >>> Hi, I have attached an initial draft of my proposal. >>> I would be grateful to receive your feedback. >> >> Ok, I had a look at the proposal and it is mostly fine. I'd be more specific >> on the deliverables, specifically >> >> 1) genmatch - program to read meta description and generate code to >> simplify GENERIC and GIMPLE according to the pattern descriptions >> using an algorithm not linear in the number of patterns >> >> 2) add patterns matched by tree-ssa-forwprop.c (and thus patterns >> in fold-const.c it depends on) to the meta-description and perform >> the simplifications of tree-ssa-forwprop.c in terms of the simplification API >> >> You will figure out that there are possibly a lot of patterns in fold-const.c >> that forwprop depends on (I know mainly of all the comparison simplifications). >> >> For the Timeline I'd move e) as a sub-task of f) to June 28 - July 16, >> eventually just dividing the weeks of July 17 - August 11 to that and >> the following task. >> >> That is, the overall deliverable should be a tree-ssa-forwprop.c that is >> (mostly) implemented in terms of patterns, ready for commit to trunk >> during stage1. >> >> As for targeting GENERIC, useful testing coverage of that path will >> come from for example re-writing fold-const.c:fold_comparison using >> the GENERIC API of the pattern simplifier. >> >> The devil will be in the details (as always) ;) >> >> As Maxim said - make sure to register your proposal in-time, you >> can always improve on it later. >> > Thanks for the feedback. I have uploaded it: > http://www.google-melange.com/gsoc/proposal/public/google/gsoc2014/prathamesh3492/5629499534213120 > Would you like to suggest any further changes ? > There are a few formatting glitches, I am fixing those. > > Could you help me point out how to write test-cases for transforms ? > For example: > /* Fold ~A + 1 -> -A */ > (match_and_simplify > (PLUS_EXPR (BIT_NOT_EXPR @0) @1) > if (@1 == integer_one_node) > (NEGATE_EXPR @0)) > > Is the following test-case correctly written ? > /* { dg-do compile } */ > /* { dg-options "-O -fdump-tree-forwprop" } */ > > int foo (int x) > { > int temp1 = ~x; > int temp2 = temp1 + 1; > return temp2; > } > > /* { dg-final { scan-tree-dump "temp* = -x*(D)" "forwprop1" } } */ > Shall that be (somewhat) correct ? Yes, though the pattern to scan for may be somewhat fragile (generally avoid using '*' there but use \[^\n\r\]* to avoid getting false matches across newlines). > (Unfortunately, I cannot check if I have written the test-case correctly, > because I am in the middle of a bootstrap build. > Is there a way to run test-cases on only stage-1 compiler ? > I tried make check-cc1 RUNTESTFLAGS=dg.exp=tree-ssa/match-2.c but that > did not work). I usually do development on a separate build directory that I configure like CFLAGS=-g CXXFLAGS=-g /src/configure --disable-bootstrap make CFLAGS=-g CXXFLAGS=-g then I can test incremental changes by in gcc/ doing > make cc1 > make check-gcc RUNTESTFLAGS="tree-ssa.exp=match-2.c" Richard. > forwprop output is: > ;; Function foo (foo, funcdef_no=0, decl_uid=1743, symbol_order=0) > > gimple_match_and_simplified to temp2_3 = -x_1(D); > foo (int x) > { > int temp2; > int temp1; > > <bb 2>: > temp1_2 = ~x_1(D); > temp2_3 = -x_1(D); > temp2_4 = temp2_3; > return temp2_4; > > } > > Thanks and Regards, > Prathamesh > >> Thanks, >> Richard. >> >>> Thanks and Regards, >>> Prathamesh >>>> Thanks, >>>> Richard. >>>> >>>>> This caused segfault for patterns when "simplification" operand was >>>>> only c_expr (patch attached). >>>>> >>>>> * genmatch.c (c_expr::c_expr): use OP_C_EXPR instead of OP_EXPR in >>>>> call to operand constructor. ^ permalink raw reply [flat|nested] 22+ messages in thread
end of thread, other threads:[~2014-03-21 9:49 UTC | newest]
Thread overview: 22+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-03-02 20:13 [gsoc 2014] moving fold-const patterns to gimple Prathamesh Kulkarni
2014-03-03 10:02 ` Richard Biener
2014-03-06 12:11 ` Prathamesh Kulkarni
2014-03-06 12:43 ` Richard Biener
2014-03-06 18:17 ` Prathamesh Kulkarni
2014-03-07 9:08 ` Richard Biener
2014-03-10 18:29 ` Prathamesh Kulkarni
2014-03-11 11:20 ` Richard Biener
2014-03-13 11:14 ` Richard Biener
2014-03-14 15:31 ` Prathamesh Kulkarni
2014-03-14 15:35 ` Prathamesh Kulkarni
2014-03-14 15:55 ` Marc Glisse
2014-03-14 16:37 ` Prathamesh Kulkarni
2014-03-14 17:54 ` Marc Glisse
2014-03-14 17:16 ` Richard Biener
2014-03-16 12:21 ` Prathamesh Kulkarni
2014-03-17 8:52 ` Richard Biener
2014-03-18 8:13 ` Prathamesh Kulkarni
2014-03-19 0:27 ` Maxim Kuvyrkov
[not found] ` <CAJXstsD0Y=vBxw9QveOU3O3jhQgbYkxj_iyfje=AFypHEmK9gA@mail.gmail.com>
2014-03-19 9:43 ` Richard Biener
2014-03-20 20:52 ` Prathamesh Kulkarni
2014-03-21 9:49 ` Richard Biener
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).