Currently the order in which patterns in match.pd match is pretty
random (well, it's deterministic of course). This is bad if there
are multiple possible matches such as in
z = x + 1;
w = z + 0;
where we have both z + 0 -> z and (x + 1) + 0 -> x + (1 + 0).
Currently the latter happens to be applied and thus we simplify to
z = x + 1;
w = x + 1;
which is bad for propagation engines which only handle constant
or SSA name results (and also either generates redundant code or leaves
dead code).
Thus the following patch makes sure that if there are multiple
matches possible then the pattern first appearing in match.pd
is chosen.
This slightly increases the number of instructions executed during
the matching in the worst case but is certainly the best course
of action here (other possibilities are to make the patterns
disjunct by disabling the latter for the + 0 case). At least
it matches how other generated matchers behave.
Bootstrap and regtest running on x86_64-unknown-linux-gnu.
Richard.
2014-11-27 Richard Biener <rguent...@suse.de>
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.
Index: gcc/genmatch.c
===================================================================
*** gcc/genmatch.c.orig 2014-11-14 12:13:31.029117775 +0100
--- gcc/genmatch.c 2014-11-27 15:03:24.085664272 +0100
*************** struct dt_node
*** 1098,1103 ****
--- 1098,1106 ----
virtual void gen (FILE *, bool) {}
void gen_kids (FILE *, bool);
+ void gen_kids_1 (FILE *, bool,
+ vec<dt_operand *>, vec<dt_operand *>, vec<dt_operand *>,
+ vec<dt_operand *>, vec<dt_operand *>, vec<dt_node *>);
};
/* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
*************** decision_tree::cmp_node (dt_node *n1, dt
*** 1203,1211 ****
if (!n1 || !n2 || n1->type != n2->type)
return false;
! if (n1 == n2 || n1->type == dt_node::DT_TRUE)
return true;
if (n1->type == dt_node::DT_OPERAND)
return cmp_operand ((as_a<dt_operand *> (n1))->op,
(as_a<dt_operand *> (n2))->op);
--- 1206,1217 ----
if (!n1 || !n2 || n1->type != n2->type)
return false;
! 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<dt_operand *> (n1))->op,
(as_a<dt_operand *> (n2))->op);
*************** decision_tree::cmp_node (dt_node *n1, dt
*** 1220,1229 ****
dt_node *
decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
{
! for (unsigned i = 0; i < ops.length (); ++i)
! if (decision_tree::cmp_node (ops[i], p))
! return ops[i];
!
return NULL;
}
--- 1226,1246 ----
dt_node *
decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
{
! /* 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;
}
*************** dt_node::append_node (dt_node *n)
*** 1242,1256 ****
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;
}
--- 1259,1264 ----
*************** dt_node::gen_kids (FILE *f, bool gimple)
*** 2006,2012 ****
auto_vec<dt_operand *> generic_fns;
auto_vec<dt_operand *> preds;
auto_vec<dt_node *> others;
- dt_node *true_operand = NULL;
for (unsigned i = 0; i < kids.length (); ++i)
{
--- 2014,2019 ----
*************** dt_node::gen_kids (FILE *f, bool gimple)
*** 2044,2054 ****
|| 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];
else
gcc_unreachable ();
}
char buf[128];
char *kid_opname = buf;
--- 2051,2090 ----
|| kids[i]->type == dt_node::DT_SIMPLIFY)
others.safe_push (kids[i]);
else if (kids[i]->type == dt_node::DT_TRUE)
! {
! /* 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<dt_operand *> gimple_exprs,
+ vec<dt_operand *> generic_exprs,
+ vec<dt_operand *> fns,
+ vec<dt_operand *> generic_fns,
+ vec<dt_operand *> preds,
+ vec<dt_node *> others)
+ {
char buf[128];
char *kid_opname = buf;
*************** dt_node::gen_kids (FILE *f, bool gimple)
*** 2200,2208 ****
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. */
--- 2236,2241 ----
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-ccp-34.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-ccp-34.c 2014-11-27 13:53:46.513808913
+0100
***************
*** 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" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/forwprop-31.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/forwprop-31.c 2014-11-27 15:27:20.654614533
+0100
***************
*** 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" } } */
