From 7e015fcefe33eded9a565e7e2ad3da11952249ae Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Fri, 28 Nov 2014 08:57:43 +0000 Subject: [PATCH] re PR tree-optimization/64084 (match-and-simplify prefers complex matches) 2014-11-28 Richard Biener PR middle-end/64084 * genmatch.c (dt_node::gen_kids_1): New function, split out from dt_node::gen_kids. (decision_tree::cmp_node): DT_TRUE are generally not equal. (decision_tree::find_node): Treat DT_TRUE as barrier for node CSE on the same level. (dt_node::append_node): Do not keep DT_TRUE last. (dt_node::gen_kids): Emit code after each DT_TRUE node seen. * gcc.dg/tree-ssa/ssa-ccp-34.c: New testcase. * gcc.dg/tree-ssa/forwprop-31.c: Likewise. From-SVN: r218141 --- gcc/ChangeLog | 11 ++++ gcc/genmatch.c | 71 +++++++++++++++------ gcc/testsuite/ChangeLog | 6 ++ gcc/testsuite/gcc.dg/tree-ssa/forwprop-31.c | 16 +++++ gcc/testsuite/gcc.dg/tree-ssa/ssa-ccp-34.c | 12 ++++ 5 files changed, 97 insertions(+), 19 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/forwprop-31.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-ccp-34.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index fb2e30cb69f..a9e4eca79c5 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2014-11-28 Richard Biener + + PR middle-end/64084 + * genmatch.c (dt_node::gen_kids_1): New function, split out + from dt_node::gen_kids. + (decision_tree::cmp_node): DT_TRUE are generally not equal. + (decision_tree::find_node): Treat DT_TRUE as barrier for + node CSE on the same level. + (dt_node::append_node): Do not keep DT_TRUE last. + (dt_node::gen_kids): Emit code after each DT_TRUE node seen. + 2014-11-28 Ramana Radhakrishnan * config/arm/t-aprofile (MULTILIB_MATCHES): New entry for diff --git a/gcc/genmatch.c b/gcc/genmatch.c index fdd02a5358a..7cfd3544628 100644 --- a/gcc/genmatch.c +++ b/gcc/genmatch.c @@ -1098,6 +1098,9 @@ struct dt_node virtual void gen (FILE *, bool) {} void gen_kids (FILE *, bool); + void gen_kids_1 (FILE *, bool, + vec, vec, vec, + vec, vec, vec); }; /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */ @@ -1203,9 +1206,12 @@ decision_tree::cmp_node (dt_node *n1, dt_node *n2) if (!n1 || !n2 || n1->type != n2->type) return false; - if (n1 == n2 || n1->type == dt_node::DT_TRUE) + if (n1 == n2) return true; + if (n1->type == dt_node::DT_TRUE) + return false; + if (n1->type == dt_node::DT_OPERAND) return cmp_operand ((as_a (n1))->op, (as_a (n2))->op); @@ -1220,10 +1226,21 @@ decision_tree::cmp_node (dt_node *n1, dt_node *n2) dt_node * decision_tree::find_node (vec& ops, dt_node *p) { - for (unsigned i = 0; i < ops.length (); ++i) - if (decision_tree::cmp_node (ops[i], p)) - return ops[i]; - + /* We can merge adjacent DT_TRUE. */ + if (p->type == dt_node::DT_TRUE + && !ops.is_empty () + && ops.last ()->type == dt_node::DT_TRUE) + return ops.last (); + for (int i = ops.length () - 1; i >= 0; --i) + { + /* But we can't merge across DT_TRUE nodes as they serve as + pattern order barriers to make sure that patterns apply + in order of appearance in case multiple matches are possible. */ + if (ops[i]->type == dt_node::DT_TRUE) + return NULL; + if (decision_tree::cmp_node (ops[i], p)) + return ops[i]; + } return NULL; } @@ -1242,15 +1259,6 @@ dt_node::append_node (dt_node *n) kids.safe_push (n); n->level = this->level + 1; - unsigned len = kids.length (); - - if (len > 1 && kids[len - 2]->type == dt_node::DT_TRUE) - { - dt_node *p = kids[len - 2]; - kids[len - 2] = kids[len - 1]; - kids[len - 1] = p; - } - return n; } @@ -2006,7 +2014,6 @@ dt_node::gen_kids (FILE *f, bool gimple) auto_vec generic_fns; auto_vec preds; auto_vec others; - dt_node *true_operand = NULL; for (unsigned i = 0; i < kids.length (); ++i) { @@ -2044,11 +2051,40 @@ dt_node::gen_kids (FILE *f, bool gimple) || kids[i]->type == dt_node::DT_SIMPLIFY) others.safe_push (kids[i]); else if (kids[i]->type == dt_node::DT_TRUE) - true_operand = kids[i]; + { + /* A DT_TRUE operand serves as a barrier - generate code now + for what we have collected sofar. */ + gen_kids_1 (f, gimple, gimple_exprs, generic_exprs, + fns, generic_fns, preds, others); + /* And output the true operand itself. */ + kids[i]->gen (f, gimple); + gimple_exprs.truncate (0); + generic_exprs.truncate (0); + fns.truncate (0); + generic_fns.truncate (0); + preds.truncate (0); + others.truncate (0); + } else gcc_unreachable (); } + /* Generate code for the remains. */ + gen_kids_1 (f, gimple, gimple_exprs, generic_exprs, + fns, generic_fns, preds, others); +} + +/* Generate matching code for the children of the decision tree node. */ + +void +dt_node::gen_kids_1 (FILE *f, bool gimple, + vec gimple_exprs, + vec generic_exprs, + vec fns, + vec generic_fns, + vec preds, + vec others) +{ char buf[128]; char *kid_opname = buf; @@ -2200,9 +2236,6 @@ dt_node::gen_kids (FILE *f, bool gimple) for (unsigned i = 0; i < others.length (); ++i) others[i]->gen (f, gimple); - - if (true_operand) - true_operand->gen (f, gimple); } /* Generate matching code for the decision tree operand. */ diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 8c40dbd273f..4647a46595d 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2014-11-28 Richard Biener + + PR middle-end/64084 + * gcc.dg/tree-ssa/ssa-ccp-34.c: New testcase. + * gcc.dg/tree-ssa/forwprop-31.c: Likewise. + 2014-11-27 Richard Biener PR middle-end/64088 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-31.c b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-31.c new file mode 100644 index 00000000000..ddb376f5598 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-31.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fno-tree-ccp -fdump-tree-forwprop1" } */ + +int foo (int x) +{ + int y = 0; + int z = x + 1; + int w = z + y; /* becomes z */ + return w - z; /* becomes 0 */ +} + +/* The original y = 0 stmt is also retained. */ +/* { dg-final { scan-tree-dump-times "= 0;" 2 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "-" 0 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "\\+" 1 "forwprop1" } } */ +/* { dg-final { cleanup-tree-dump "forwprop1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ccp-34.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ccp-34.c new file mode 100644 index 00000000000..5d12beaf4cd --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ccp-34.c @@ -0,0 +1,12 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-ccp1" } */ + +int foo (int x) +{ + int y = 0; + int z = x + 1; + return z + y; +} + +/* { dg-final { scan-tree-dump-times "\\+" 1 "ccp1" } } */ +/* { dg-final { cleanup-tree-dump "ccp1" } } */ -- 2.30.2