On Wed, 12 Oct 2016, Richard Biener wrote:
> On Wed, 12 Oct 2016, Marc Glisse wrote:
>
> > On Wed, 12 Oct 2016, Richard Biener wrote:
> >
> > > So with doing the same on GENERIC I hit
> > >
> > > FAIL: g++.dg/cpp1y/constexpr-array4.C -std=c++14 (test for excess errors)
> > >
> > > with the pattern
> > >
> > > /* (T)(P + A) - (T)P -> (T) A */
> > > (for add (plus pointer_plus)
> > > (simplify
> > > (minus (convert (add @0 @1))
> > > (convert @0))
> >
> > Ah, grep missed that one because it is on 2 lines :-(
> >
> > > ...
> > > (convert @1))))
> > >
> > >
> > > no longer applying to
> > >
> > > (long int) ((int *) &ar + 12) - (long int) &ar
> > >
> > > because while (int *) &ar is equal to (long int) &ar (operand_equal_p
> > > does STRIP_NOPS) they obviously do not have the same type.
> >
> > I believe we are comparing (int *) &ar to &ar, not to (long int) &ar. But
> > yes,
> > indeed.
> >
> > > So on GENERIC we have to consider that we feed operand_equal_p with
> > > non-ATOMs (arbitrary expressions). The pattern above is "safe" as it
> > > doesn't reference @0 in the result (not sure if we should take advantage
> > > of
> > > that in genmatch).
> >
> > Since we are in the process of defining an
> > operand_equal_for_(generic|gimple)_match_p, we could tweak it to check the
> > type only for INTEGER_CST, or to still STRIP_NOPS, or similar.
> >
> > Or we could remain very strict and refine the pattern, allowing a convert on
> > the pointer (we might want to split the plus and pointer_plus versions then,
> > for clarity). There are not many optimizations that are mandated by
> > front-ends
> > and for which this is an issue.
> >
> > > The other FAILs with doing the same on GENERIC are
> > >
> > > FAIL: g++.dg/gomp/declare-simd-3.C -std=gnu++11 (test for excess errors)
> > > FAIL: g++.dg/torture/pr71448.C -O0 (test for excess errors)
> > > FAIL: g++.dg/vect/simd-clone-6.cc -std=c++11 (test for excess errors)
> > >
> > > the simd ones are 'warning: ignoring large linear step' and the pr71448.C
> > > case is very similar to the above.
> >
> > Yes, I expect they all come from the same 1 or 2 transformations.
> >
> > > > > > If we stick to the old behavior, maybe we could have some genmatch
> > > > > > magic to help with the constant capture weirdness. With matching
> > > > > > captures, we could select which operand (among those supposed to be
> > > > > > equivalent) is actually captured more cleverly, either with an
> > > > > > explicit marker, or by giving priority to the one that is not
> > > > > > immediatly below convert? in the pattern.
> > > > >
> > > > > This route is a difficult one to take
> > > >
> > > > The simplest version I was thinking about was @0 for a true capture, and
> > > > @@0
> > > > for something that just has to be checked for equality with @0.
> > >
> > > Hmm, ok. So you'd have @@0 having to match @0 and we'd get the @0 for
> > > the result in a reliable way? Sounds like a reasonable idea, I'll see
> > > how that works out (we could auto-detect '@@' if the capture is not
> > > used in the result, see above).
> >
> > It probably doesn't bring much compared to the @0@4 syntax you were
> > suggesting below, so if that is easier...
>
> Will figure that out ...
>
> > > > > -- what would be possible is to
> > > > > capture a specific operand. Like allow one to write
> > > > >
> > > > > (op (op @0@4 @1) (op @0@3 @2))
> > > > >
> > > > > and thus actually have three "names" for @0. We have this internally
> > > > > already when you write
> > > > >
> > > > > (convert?@0 @1)
> > > > >
> > > > > for the case where there is no conversion. @0 and @1 are the same
> > > > > in this case.
> > > >
> > > > Looks nice and convenient (assuming lax constant matching).
> > >
> > > Yes, w/o lax matching it has of course little value.
> > >
> > > > > Not sure if this helps enough cases.
> > > >
> > > > IIRC, in all cases where we had trouble with operand_equal_p, chosing
> > > > which
> > > > operand to capture would have solved the issue.
> > >
> > > Yes. We'd still need to actually catch all those cases...
> >
> > Being forced to chose which operand we capture (say with @ vs @@, making 2
> > occurences of @0 a syntax error) might help, but it would also require
> > updating many patterns for which this was never an issue (easy but boring).
>
> We can even have today
>
> (plus (minus @0 @1) (plus @0 @2) @0)
>
> thus three matching @0. Now if we have @@ telling to use value equality
> rather than "node equality" _and_ making the @@ select the canonical
> operand to choose then we'd have at most one @@ per ID. Somewhat tricky
> but not impossible to implement I think.
So here it is. It allows us to remove the operand_equal_p hacks:
@@ -334,11 +334,8 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
/* X - (X / Y) * Y is the same as X % Y. */
(simplify
- (minus (convert1? @2) (convert2? (mult:c (trunc_div @0 @1) @1)))
- /* We cannot use matching captures here, since in the case of
- constants we really want the type of @0, not @2. */
- (if (operand_equal_p (@0, @2, 0)
- && (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type)))
+ (minus (convert1? @0) (convert2? (mult:c (trunc_div @@0 @@1) @1)))
+ (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
(convert (trunc_mod @0 @1))))
The patch introduces '@@' captures which do two things - first they
change the comparison used for matching back to operand_equal_p
only (thus perform "value-matching"), second the @@ capture denotes
the specific operand that should be refered to in the result
section (ifs and result expressions).
When we face (plus @0 @1) (convert? @@0) for example this is lowered
to (plus @__2 @1) (convert? @__2@0) marking the @__2 match for
value handling.
I modified the patterns you identified and the ones I did and
removed the operand_equal_p uses where possible.
I did not implement the auto-guessing idea as I usually like
to be more explicit here.
Bootstrap and regtest running on x86_64-unknown-linux-gnu.
Richard.
2016-10-13 Richard Biener <rguent...@suse.de>
PR middle-end/77826
* genmatch.c (struct capture): Add value_match member.
(commutate): Preserve value_match.
(lower_opt_convert): Likewise.
(lower_cond): Likewise.
(replace_id): Likewise.
(struct dt_operand): Add value_match member.
(decision_tree::cmp_node): Compare it.
(decision_tree::insert_operand): Honor it when finding and
when appending a DT_MATCH.
(dt_operand::gen_match_op): Generate a type check after
operand_equal_p if ! value_match for both GENERIC and GIMPLE.
(parser::get_internal_capture_id): New helper.
(parser::finish_match_operand): New function lowering @@<id>.
(parser::parse_capture): Parse @@<id> as value-match.
(parser::parse_expr): Use get_internal_capture_id.
(parser::parse_simplify): Call finish_match_operand.
(walk_captures): New helper.
* match.pd (X - (X / Y) * Y -> X % Y): Use value-matching instead
of operand_equal_p.
((X /[ex] A) * A -> X): Likewise.
((X | Y) ^ X -> Y & ~ X): Handle constants properly by using
convert[12] and value-matching.
((A | B) & (A | C) -> A | (B & C)): Likewise.
((X | Y) | Y -> X | Y): Likewise.
((X ^ Y) ^ Y -> X): Likewise.
(A - (A & B) -> ~B & A): Likewise.
((T)(P + A) - (T)P -> (T) A): Likewise.
((T)P - (T)(P + A) -> -(T) A): Likewise.
((T)(P + A) - (T)(P + B) -> (T)A - (T)B): Likewise.
* doc/match-and-simplify.texi: Amend capture section.
Index: gcc/genmatch.c
===================================================================
--- gcc/genmatch.c (revision 241085)
+++ gcc/genmatch.c (working copy)
@@ -693,10 +693,15 @@ struct c_expr : public operand
struct capture : public operand
{
- capture (source_location loc, unsigned where_, operand *what_)
- : operand (OP_CAPTURE, loc), where (where_), what (what_) {}
+ capture (source_location loc, unsigned where_, operand *what_, bool value_)
+ : operand (OP_CAPTURE, loc), where (where_), value_match (value_),
+ what (what_) {}
/* Identifier index for the value. */
unsigned where;
+ /* Whether in a match of two operands the compare should be for
+ equal values rather than equal atoms (boils down to a type
+ check or not). */
+ bool value_match;
/* The captured value. */
operand *what;
virtual void gen_transform (FILE *f, int, const char *, bool, int,
@@ -895,7 +900,8 @@ commutate (operand *op, vec<vec<user_id
vec<operand *> v = commutate (c->what, for_vec);
for (unsigned i = 0; i < v.length (); ++i)
{
- capture *nc = new capture (c->location, c->where, v[i]);
+ capture *nc = new capture (c->location, c->where, v[i],
+ c->value_match);
ret.safe_push (nc);
}
return ret;
@@ -1013,7 +1019,8 @@ lower_opt_convert (operand *o, enum tree
{
if (c->what)
return new capture (c->location, c->where,
- lower_opt_convert (c->what, oper, to_oper, strip));
+ lower_opt_convert (c->what, oper, to_oper, strip),
+ c->value_match);
else
return c;
}
@@ -1146,7 +1153,8 @@ lower_cond (operand *o)
lop = lower_cond (c->what);
for (unsigned i = 0; i < lop.length (); ++i)
- ro.safe_push (new capture (c->location, c->where, lop[i]));
+ ro.safe_push (new capture (c->location, c->where, lop[i],
+ c->value_match));
return ro;
}
}
@@ -1196,7 +1204,8 @@ lower_cond (operand *o)
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->location, c->where, cmp);
+ ne->ops[0] = new capture (c->location, c->where, cmp,
+ c->value_match);
}
else
{
@@ -1275,7 +1284,7 @@ replace_id (operand *o, user_id *id, id_
if (!c->what)
return c;
return new capture (c->location, c->where,
- replace_id (c->what, id, with));
+ replace_id (c->what, id, with), c->value_match);
}
else if (expr *e = dyn_cast<expr *> (o))
{
@@ -1554,11 +1563,12 @@ struct dt_operand : public dt_node
dt_operand *match_dop;
dt_operand *parent;
unsigned pos;
+ bool value_match;
dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
dt_operand *parent_ = 0, unsigned pos_ = 0)
: dt_node (type), op (op_), match_dop (match_dop_),
- parent (parent_), pos (pos_) {}
+ parent (parent_), pos (pos_), value_match (false) {}
void gen (FILE *, int, bool);
unsigned gen_predicate (FILE *, int, const char *, bool);
@@ -1670,8 +1680,10 @@ decision_tree::cmp_node (dt_node *n1, dt
return cmp_operand ((as_a<dt_operand *> (n1))->op,
(as_a<dt_operand *> (n2))->op);
else if (n1->type == dt_node::DT_MATCH)
- return ((as_a<dt_operand *> (n1))->match_dop
- == (as_a<dt_operand *> (n2))->match_dop);
+ return (((as_a<dt_operand *> (n1))->match_dop
+ == (as_a<dt_operand *> (n2))->match_dop)
+ && ((as_a<dt_operand *> (n1))->value_match
+ == (as_a<dt_operand *> (n2))->value_match));
return false;
}
@@ -1841,6 +1853,7 @@ decision_tree::insert_operand (dt_node *
if (elm == 0)
{
dt_operand temp (dt_node::DT_MATCH, 0, match_op);
+ temp.value_match = c->value_match;
elm = decision_tree::find_node (p->kids, &temp);
}
}
@@ -1860,6 +1873,7 @@ at_assert_elm:
else
{
p = p->append_match_op (indexes[capt_index], parent, pos);
+ as_a <dt_operand *>(p)->value_match = c->value_match;
if (c->what)
return insert_operand (p, c->what, indexes, 0, p);
else
@@ -2591,18 +2613,18 @@ dt_operand::gen_predicate (FILE *f, int
a capture-match. */
unsigned
-dt_operand::gen_match_op (FILE *f, int indent, const char *opname, bool gimple)
+dt_operand::gen_match_op (FILE *f, int indent, const char *opname, bool)
{
char match_opname[20];
match_dop->get_name (match_opname);
- if (gimple)
+ if (value_match)
+ fprintf_indent (f, indent, "if (%s == %s || operand_equal_p (%s, %s,
0))\n",
+ opname, match_opname, opname, match_opname);
+ else
fprintf_indent (f, indent, "if (%s == %s || (operand_equal_p (%s, %s, 0) "
"&& types_match (%s, %s)))\n",
opname, match_opname, opname, match_opname,
opname, match_opname);
- else
- fprintf_indent (f, indent, "if (%s == %s || operand_equal_p (%s, %s,
0))\n",
- opname, match_opname, opname, match_opname);
fprintf_indent (f, indent + 2, "{\n");
return 1;
}
@@ -3731,6 +3767,8 @@ private:
const cpp_token *eat_ident (const char *);
const char *get_number ();
+ unsigned get_internal_capture_id ();
+
id_base *parse_operation ();
operand *parse_capture (operand *, bool);
operand *parse_expr ();
@@ -3750,6 +3788,8 @@ private:
void parse_predicates (source_location);
void parse_operator_list (source_location);
+ void finish_match_operand (operand *);
+
cpp_reader *r;
vec<c_expr *> active_ifs;
vec<vec<user_id *> > active_fors;
@@ -3886,6 +3926,21 @@ parser::get_number ()
return (const char *)token->val.str.text;
}
+/* Return a capture ID that can be used internally. */
+
+unsigned
+parser::get_internal_capture_id ()
+{
+ unsigned newid = capture_ids->elements ();
+ /* Big enough for a 32-bit UINT_MAX plus prefix. */
+ char id[13];
+ bool existed;
+ sprintf (id, "__%u", newid);
+ capture_ids->get_or_insert (xstrdup (id), &existed);
+ if (existed)
+ fatal ("reserved capture id '%s' already used", id);
+ return newid;
+}
/* Record an operator-list use for transparent for handling. */
@@ -3967,6 +4022,16 @@ parser::parse_capture (operand *op, bool
source_location src_loc = eat_token (CPP_ATSIGN)->src_loc;
const cpp_token *token = peek ();
const char *id = NULL;
+ bool value_match = false;
+ /* For matches parse @@ as a value-match denoting the prevailing operand. */
+ if (token->type == CPP_ATSIGN
+ && ! (token->flags & PREV_WHITE)
+ && parsing_match_operand)
+ {
+ eat_token (CPP_ATSIGN);
+ token = peek ();
+ value_match = true;
+ }
if (token->type == CPP_NUMBER)
id = get_number ();
else if (token->type == CPP_NAME)
@@ -3982,7 +4047,7 @@ parser::parse_capture (operand *op, bool
fatal_at (src_loc, "unknown capture id");
num = next_id;
}
- return new capture (src_loc, num, op);
+ return new capture (src_loc, num, op, value_match);
}
/* Parse an expression
@@ -4062,15 +4127,8 @@ parser::parse_expr ()
op = parse_capture (e, false);
else if (force_capture)
{
- unsigned num = capture_ids->elements ();
- /* Big enough for a 32-bit UINT_MAX plus prefix. */
- char id[13];
- bool existed;
- sprintf (id, "__%u", num);
- capture_ids->get_or_insert (xstrdup (id), &existed);
- if (existed)
- fatal_at (token, "reserved capture id '%s' already used", id);
- op = new capture (token->src_loc, num, e);
+ unsigned num = get_internal_capture_id ();
+ op = new capture (token->src_loc, num, e, false);
}
else
op = e;
@@ -4384,6 +4449,7 @@ parser::parse_simplify (simplify::simpli
const cpp_token *loc = peek ();
parsing_match_operand = true;
struct operand *match = parse_op ();
+ finish_match_operand (match);
parsing_match_operand = false;
if (match->type == operand::OP_CAPTURE && !matcher)
fatal_at (loc, "outermost expression cannot be captured");
@@ -4724,6 +4790,69 @@ parser::parse_pattern ()
eat_token (CPP_CLOSE_PAREN);
}
+/* Helper for finish_match_operand, collecting captures of OP in CPTS
+ recursively. */
+
+static void
+walk_captures (operand *op, vec<vec<capture *> > cpts)
+{
+ if (! op)
+ return;
+
+ if (capture *c = dyn_cast <capture *> (op))
+ {
+ cpts[c->where].safe_push (c);
+ walk_captures (c->what, cpts);
+ }
+ else if (expr *e = dyn_cast <expr *> (op))
+ for (unsigned i = 0; i < e->ops.length (); ++i)
+ walk_captures (e->ops[i], cpts);
+}
+
+/* Finish up OP which is a match operand. */
+
+void
+parser::finish_match_operand (operand *op)
+{
+ /* Look for matching captures, diagnose mis-uses of @@ and apply
+ early lowering and distribution of value_match. */
+ auto_vec<vec<capture *> > cpts;
+ cpts.safe_grow_cleared (capture_ids->elements ());
+ walk_captures (op, cpts);
+ for (unsigned i = 0; i < cpts.length (); ++i)
+ {
+ capture *value_match = NULL;
+ for (unsigned j = 0; j < cpts[i].length (); ++j)
+ {
+ if (cpts[i][j]->value_match)
+ {
+ if (value_match)
+ fatal_at (cpts[i][j]->location, "duplicate @@");
+ value_match = cpts[i][j];
+ }
+ }
+ if (cpts[i].length () == 1 && value_match)
+ fatal_at (value_match->location, "@@ without a matching capture");
+ if (value_match)
+ {
+ /* Duplicate prevailing capture with the existing ID, create
+ a fake ID and rewrite all captures to use it. This turns
+ @@1 into @__<newid>@1 and @1 into @__<newid>. */
+ value_match->what = new capture (value_match->location,
+ value_match->where,
+ value_match->what, false);
+ /* Create a fake ID and rewrite all captures to use it. */
+ unsigned newid = get_internal_capture_id ();
+ for (unsigned j = 0; j < cpts[i].length (); ++j)
+ {
+ cpts[i][j]->where = newid;
+ cpts[i][j]->value_match = true;
+ }
+ }
+ cpts[i].release ();
+ }
+}
+
/* Main entry of the parser. Repeatedly parse outer control structures. */
parser::parser (cpp_reader *r_)
Index: gcc/match.pd
===================================================================
--- gcc/match.pd (revision 241085)
+++ gcc/match.pd (working copy)
@@ -334,11 +334,8 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
/* X - (X / Y) * Y is the same as X % Y. */
(simplify
- (minus (convert1? @2) (convert2? (mult:c (trunc_div @0 @1) @1)))
- /* We cannot use matching captures here, since in the case of
- constants we really want the type of @0, not @2. */
- (if (operand_equal_p (@0, @2, 0)
- && (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type)))
+ (minus (convert1? @0) (convert2? (mult:c (trunc_div @@0 @@1) @1)))
+ (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
(convert (trunc_mod @0 @1))))
/* Optimize TRUNC_MOD_EXPR by a power of two into a BIT_AND_EXPR,
@@ -714,7 +711,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
/* (X | Y) ^ X -> Y & ~ X*/
(simplify
- (bit_xor:c (convert? (bit_ior:c @0 @1)) (convert? @0))
+ (bit_xor:c (convert1? (bit_ior:c @@0 @1)) (convert2? @0))
(if (tree_nop_conversion_p (type, TREE_TYPE (@0)))
(convert (bit_and @1 (bit_not @0)))))
@@ -747,7 +744,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(for op (bit_and bit_ior bit_xor)
rop (bit_ior bit_and bit_and)
(simplify
- (op (convert? (rop:c @0 @1)) (convert? (rop:c @0 @2)))
+ (op (convert? (rop:c @@0 @1)) (convert? (rop:c @0 @2)))
(if (tree_nop_conversion_p (type, TREE_TYPE (@1))
&& tree_nop_conversion_p (type, TREE_TYPE (@2)))
(rop (convert @0) (op (convert @1) (convert @2))))))
@@ -757,11 +754,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(X | Y) | Y -> X | Y */
(for op (bit_and bit_ior)
(simplify
- (op:c (convert?@2 (op:c @0 @1)) (convert? @1))
+ (op:c (convert1?@2 (op:c @0 @@1)) (convert2? @1))
@2))
/* (X ^ Y) ^ Y -> X */
(simplify
- (bit_xor:c (convert? (bit_xor:c @0 @1)) (convert? @1))
+ (bit_xor:c (convert1? (bit_xor:c @0 @@1)) (convert2? @1))
(convert @0))
/* (X & Y) & (X & Z) -> (X & Y) & Z
(X | Y) | (X | Z) -> (X | Y) | Z */
@@ -991,7 +988,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
/* Fold A - (A & B) into ~B & A. */
(simplify
- (minus (convert? @0) (convert?:s (bit_and:cs @0 @1)))
+ (minus (convert1? @0) (convert2?:s (bit_and:cs @@0 @1)))
(if (tree_nop_conversion_p (type, TREE_TYPE (@0))
&& tree_nop_conversion_p (type, TREE_TYPE (@1)))
(convert (bit_and (bit_not @1) @0))))
@@ -1206,7 +1203,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
/* (T)(P + A) - (T)P -> (T) A */
(for add (plus pointer_plus)
(simplify
- (minus (convert (add @0 @1))
+ (minus (convert (add @@0 @1))
(convert @0))
(if (element_precision (type) <= element_precision (TREE_TYPE (@1))
/* For integer types, if A has a smaller type
@@ -1231,7 +1228,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(for add (plus pointer_plus)
(simplify
(minus (convert @0)
- (convert (add @0 @1)))
+ (convert (add @@0 @1)))
(if (element_precision (type) <= element_precision (TREE_TYPE (@1))
/* For integer types, if A has a smaller type
than T the result depends on the possible
@@ -1254,7 +1251,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
/* (T)(P + A) - (T)(P + B) -> (T)A - (T)B */
(for add (plus pointer_plus)
(simplify
- (minus (convert (add @0 @1))
+ (minus (convert (add @@0 @1))
(convert (add @0 @2)))
(if (element_precision (type) <= element_precision (TREE_TYPE (@1))
/* For integer types, if A has a smaller type
@@ -1781,11 +1800,8 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
/* (X /[ex] A) * A -> X. */
(simplify
- (mult (convert1? (exact_div @0 @1)) (convert2? @2))
- /* We cannot use matching captures here, since in the case of
- constants we don't see the second conversion. */
- (if (operand_equal_p (@1, @2, 0))
- (convert @0)))
+ (mult (convert1? (exact_div @0 @@1)) (convert2? @1))
+ (convert @0))
/* Canonicalization of binary operations. */
Index: gcc/doc/match-and-simplify.texi
===================================================================
--- gcc/doc/match-and-simplify.texi (revision 241085)
+++ gcc/doc/match-and-simplify.texi (working copy)
@@ -110,7 +110,11 @@ are @code{@@} followed by a number or an
@end smallexample
In this example @code{@@0} is mentioned twice which constrains the matched
-expression to have two equal operands. This example also introduces
+expression to have two equal operands. Usually matches are constraint
+to equal types. If operands may be constants and conversions are involved
+matching by value might be preferred in which case use @code{@@@@0} to
+denote a by value match and the specific operand you want to refer to
+in the result part. This example also introduces
operands written in C code. These can be used in the expression
replacements and are supposed to evaluate to a tree node which has to
be a valid GIMPLE operand (so you cannot generate expressions in C code).
