Match-and-simplify and COND_EXPR
Richard Biener
rguenther@suse.de
Tue Nov 11 12:34:00 GMT 2014
On Tue, 11 Nov 2014, Richard Biener wrote:
> On Mon, 10 Nov 2014, Andrew Pinski wrote:
>
> > On Fri, Nov 7, 2014 at 2:23 AM, Richard Biener <rguenther@suse.de> wrote:
> > > On Thu, 6 Nov 2014, Andrew Pinski wrote:
> > >
> > >> On Thu, Nov 6, 2014 at 2:40 AM, Richard Biener <rguenther@suse.de> wrote:
> > >> > On Thu, 6 Nov 2014, Richard Biener wrote:
> > >> >
> > >> >> On Wed, 5 Nov 2014, Andrew Pinski wrote:
> > >> >>
> > >> >> > Hi,
> > >> >> > I was trying to hook up tree-ssa-phiopt to match-and-simplify using
> > >> >> > either gimple_build (or rather using gimple_simplify depending on if
> > >> >> > we want to produce cond_expr for conditional move). I ran into a
> > >> >> > problem.
> > >> >> > With the pattern below:
> > >> >> > /* a ? 0 : 1 -> a if 0 and 1 are integral types. */
> > >> >> > (simplify
> > >> >> > (cond_expr @0 integer_zerop integer_onep)
> > >> >> > (if (INTEGRAL_TYPE_P (type))
> > >> >> > (convert @0)))
> > >> >>
> > >> >> Ok, so you are capturing a GENERIC expr here but nothing knows that.
> > >> >> It would work if you'd do (ugh)
> > >> >>
> > >> >> (for op (lt le eq ne ge gt)
> > >> >> (simplify
> > >> >> (cond_expr (op @0 @1) integer_zerop integer_onep)
> > >> >> (if (INTEGRAL_TYPE_P (type))
> > >> >> (convert (op @0 @1)))))
> > >> >> (simplify
> > >> >> (cond_expr SSA_NAME@0 integer_zerop integer_onep)
> > >> >> (if (INTEGRAL_TYPE_P (type))
> > >> >> (convert @0))))
> > >> >>
> > >> >> as a workaround. To make your version work will require (quite)
> > >> >> some special-casing in the code generator or maybe the resimplify
> > >> >> helper. Let me see if I can cook up a "simple" fix.
> > >> >
> > >> > Sth like below (for the real fix this has to be replicated in
> > >> > all gimple_resimplifyN functions). I'm missing a testcase
> > >> > where the pattern would apply (and not be already folded by fold),
> > >> > so I didn't check if it actually works.
> > >>
> > >> You do need to check if seq is NULL though as gimple_build depends on
> > >> seq not being NULL. But otherwise yes this works for me.
> > >
> > > Ok, here is a better and more complete fix. The optimization
> > > whether a captured expression may be a GENERIC condition isn't
> > > implemented so a lot of checks are emitted right now. Also
> > > if gimple_build would fail this terminates the whole matching
> > > process, not just matching of the current pattern (failing "late"
> > > isn't supported with the style of code we emit - well, without
> > > adding ugly gotos and labels).
> > >
> > > At least it avoids splitting up conditions if substituted into
> > > a COND_EXPR, so simplifications of COND_EXPRs in-place (w/o seq)
> > > should still work.
> > >
> > > Can you check whether this works for you?
> >
> > This works for most cases but does not work for things like:
> > /* a != b ? a : b -> a */
> > (simplify
> > (cond_expr (ne @0 @1) @0 @1)
> > @0)
> >
> > In gimple_simplify after it matches COND_EXPR. It does not look into
> > the operand 0 to see if it matches NE_EXPR, it just sees if it was a
> > SSA_NAME. In this case I was trying to do a simple replacement of
> > value_replacement in tree-ssa-phiopt.c.
>
> Yeah - I hoped you wouldn't notice. It's not too difficult to fix.
> Still this ugly ambiguity in the GIMPLE IL is bad and I wonder if
> it is better to finally fix it with
>
> Index: gcc/gimple-expr.c
> ===================================================================
> --- gcc/gimple-expr.c (revision 216973)
> +++ gcc/gimple-expr.c (working copy)
> @@ -641,10 +641,7 @@ is_gimple_lvalue (tree t)
> bool
> is_gimple_condexpr (tree t)
> {
> - return (is_gimple_val (t) || (COMPARISON_CLASS_P (t)
> - && !tree_could_throw_p (t)
> - && is_gimple_val (TREE_OPERAND (t, 0))
> - && is_gimple_val (TREE_OPERAND (t, 1))));
> + return is_gimple_val (t);
> }
>
> /* Return true if T is a gimple address. */
>
> I expect mostly fallout from passes building [VEC_]COND_EXPRs and
> not gimplifying it and of course missed optimizations from the
> vectorizer which will likely now try to vectorize the separate
> comparisons in some maybe odd way (not sure).
>
> I did this experiment once but didn't finish it. Too bad :/
>
> > But for my purpose right now this is sufficient and will be posting a
> > patch which does not remove things from tree-ssa-phiopt.c just yet.
>
> Fair enough. I suppose for GCC 5 I will need to deal with the odd
> GIMPLE IL. At least I can consider it a "bug" and thus fix this
> during stage3 ;)
Well. Like the following which creates the expected code for
(simplify
(cond_expr (eq @0 @1) @0 @1)
@1)
I'll install this on the branch and work on the other patch to
clean it up a bit.
Richard.
2014-11-11 Richard Biener <rguenther@suse.de>
* genmatch.c (struct expr): Add is_generic member.
(cmp_operand): Also compare is_generic flag.
(dt_operand::gen_gimple_expr): If is_generic is set force
the GENERIC code-path.
(lower_cond): New functions.
(lower): Call lower_cond.
(main): Pass gimple flag to lower.
Index: gcc/genmatch.c
===================================================================
--- gcc/genmatch.c (revision 217279)
+++ gcc/genmatch.c (working copy)
@@ -438,7 +438,8 @@ struct expr : public operand
{
expr (id_base *operation_, bool is_commutative_ = false)
: operand (OP_EXPR), operation (operation_),
- ops (vNULL), expr_type (NULL), is_commutative (is_commutative_) {}
+ ops (vNULL), expr_type (NULL), is_commutative (is_commutative_),
+ is_generic (false) {}
void append_op (operand *op) { ops.safe_push (op); }
/* The operator and its operands. */
id_base *operation;
@@ -448,6 +449,8 @@ struct expr : public operand
/* Whether the operation is to be applied commutatively. This is
later lowered to two separate patterns. */
bool is_commutative;
+ /* Whether the expression is expected to be in GENERIC form. */
+ bool is_generic;
virtual void gen_transform (FILE *f, const char *, bool, int,
const char *, dt_operand ** = 0);
};
@@ -842,6 +845,106 @@ lower_opt_convert (simplify *s, vec<simp
}
}
+/* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
+ GENERIC and a GIMPLE variant. */
+
+static vec<operand *>
+lower_cond (operand *o)
+{
+ vec<operand *> ro = vNULL;
+
+ if (capture *c = dyn_cast<capture *> (o))
+ {
+ if (c->what)
+ {
+ vec<operand *> lop = vNULL;
+ lop = lower_cond (c->what);
+
+ for (unsigned i = 0; i < lop.length (); ++i)
+ ro.safe_push (new capture (c->where, lop[i]));
+ return ro;
+ }
+ }
+
+ expr *e = dyn_cast<expr *> (o);
+ if (!e || e->ops.length () == 0)
+ {
+ ro.safe_push (o);
+ return ro;
+ }
+
+ vec< vec<operand *> > ops_vector = vNULL;
+ for (unsigned i = 0; i < e->ops.length (); ++i)
+ ops_vector.safe_push (lower_cond (e->ops[i]));
+
+ auto_vec< vec<operand *> > result;
+ auto_vec<operand *> v (e->ops.length ());
+ v.quick_grow_cleared (e->ops.length ());
+ cartesian_product (ops_vector, result, v, 0);
+
+ for (unsigned i = 0; i < result.length (); ++i)
+ {
+ expr *ne = new expr (e->operation);
+ for (unsigned j = 0; j < result[i].length (); ++j)
+ ne->append_op (result[i][j]);
+ ro.safe_push (ne);
+ /* If this is a COND with a captured expression or an
+ expression with two operands then also match a GENERIC
+ form on the compare. */
+ if ((*e->operation == COND_EXPR
+ || *e->operation == VEC_COND_EXPR)
+ && ((is_a <capture *> (e->ops[0])
+ && as_a <capture *> (e->ops[0])->what
+ && is_a <expr *> (as_a <capture *> (e->ops[0])->what)
+ && as_a <expr *>
+ (as_a <capture *> (e->ops[0])->what)->ops.length () == 2)
+ || (is_a <expr *> (e->ops[0])
+ && as_a <expr *> (e->ops[0])->ops.length () == 2)))
+ {
+ expr *ne = new expr (e->operation);
+ for (unsigned j = 0; j < result[i].length (); ++j)
+ ne->append_op (result[i][j]);
+ if (capture *c = dyn_cast <capture *> (ne->ops[0]))
+ {
+ expr *ocmp = as_a <expr *> (c->what);
+ expr *cmp = new expr (ocmp->operation);
+ for (unsigned j = 0; j < ocmp->ops.length (); ++j)
+ cmp->append_op (ocmp->ops[j]);
+ cmp->is_generic = true;
+ ne->ops[0] = new capture (c->where, cmp);
+ }
+ else
+ {
+ expr *ocmp = as_a <expr *> (ne->ops[0]);
+ expr *cmp = new expr (ocmp->operation);
+ for (unsigned j = 0; j < ocmp->ops.length (); ++j)
+ cmp->append_op (ocmp->ops[j]);
+ cmp->is_generic = true;
+ ne->ops[0] = cmp;
+ }
+ ro.safe_push (ne);
+ }
+ }
+
+ return ro;
+}
+
+/* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
+ GENERIC and a GIMPLE variant. */
+
+static void
+lower_cond (simplify *s, vec<simplify *>& simplifiers)
+{
+ vec<operand *> matchers = lower_cond (s->match);
+ for (unsigned i = 0; i < matchers.length (); ++i)
+ {
+ simplify *ns = new simplify (matchers[i], s->match_location,
+ s->result, s->result_location, s->ifexpr_vec,
+ s->for_vec, s->capture_ids);
+ simplifiers.safe_push (ns);
+ }
+}
+
/* In AST operand O replace operator ID with operator WITH. */
operand *
@@ -937,19 +1040,27 @@ lower_for (simplify *sin, vec<simplify *
/* Lower the AST for everything in SIMPLIFIERS. */
static void
-lower (vec<simplify *>& simplifiers)
+lower (vec<simplify *>& simplifiers, bool gimple)
{
- auto_vec<simplify *> out_simplifiers0;
+ auto_vec<simplify *> out_simplifiers;
for (unsigned i = 0; i < simplifiers.length (); ++i)
- lower_opt_convert (simplifiers[i], out_simplifiers0);
+ lower_opt_convert (simplifiers[i], out_simplifiers);
+
+ simplifiers.truncate (0);
+ for (unsigned i = 0; i < out_simplifiers.length (); ++i)
+ lower_commutative (out_simplifiers[i], simplifiers);
+
+ out_simplifiers.truncate (0);
+ if (gimple)
+ for (unsigned i = 0; i < simplifiers.length (); ++i)
+ lower_cond (simplifiers[i], out_simplifiers);
+ else
+ out_simplifiers.safe_splice (simplifiers);
- auto_vec<simplify *> out_simplifiers1;
- for (unsigned i = 0; i < out_simplifiers0.length (); ++i)
- lower_commutative (out_simplifiers0[i], out_simplifiers1);
simplifiers.truncate (0);
- for (unsigned i = 0; i < out_simplifiers1.length (); ++i)
- lower_for (out_simplifiers1[i], simplifiers);
+ for (unsigned i = 0; i < out_simplifiers.length (); ++i)
+ lower_for (out_simplifiers[i], simplifiers);
}
@@ -1069,7 +1180,8 @@ cmp_operand (operand *o1, operand *o2)
{
expr *e1 = static_cast<expr *>(o1);
expr *e2 = static_cast<expr *>(o2);
- return e1->operation == e2->operation;
+ return (e1->operation == e2->operation
+ && e1->is_generic == e2->is_generic);
}
else
return false;
@@ -1617,7 +1729,8 @@ dt_operand::gen_gimple_expr (FILE *f)
if (id->kind == id_base::CODE)
{
- if (*id == REALPART_EXPR || *id == IMAGPART_EXPR
+ if (e->is_generic
+ || *id == REALPART_EXPR || *id == IMAGPART_EXPR
|| *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
{
/* ??? If this is a memory operation we can't (and should not)
@@ -3387,7 +3500,7 @@ add_operator (CONVERT2, "CONVERT2", "tcc
for (unsigned i = 0; i < p.user_predicates.length (); ++i)
{
predicate_id *pred = p.user_predicates[i];
- lower (pred->matchers);
+ lower (pred->matchers, gimple);
if (verbose)
for (unsigned i = 0; i < pred->matchers.length (); ++i)
@@ -3404,7 +3517,7 @@ add_operator (CONVERT2, "CONVERT2", "tcc
}
/* Lower the main simplifiers and generate code for them. */
- lower (p.simplifiers);
+ lower (p.simplifiers, gimple);
if (verbose)
for (unsigned i = 0; i < p.simplifiers.length (); ++i)
More information about the Gcc
mailing list