From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 119586 invoked by alias); 13 Oct 2016 08:29:58 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 118983 invoked by uid 89); 13 Oct 2016 08:29:58 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.1 required=5.0 tests=BAYES_05,KAM_ASCII_DIVIDERS,RP_MATCHES_RCVD,SPF_PASS autolearn=no version=3.3.2 spammy=boils, prevailing, peek, Duplicate X-HELO: mx2.suse.de Received: from mx2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 13 Oct 2016 08:29:48 +0000 Received: from relay2.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 0ACBEACB6 for ; Thu, 13 Oct 2016 08:29:46 +0000 (UTC) Date: Thu, 13 Oct 2016 08:29:00 -0000 From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: Re: [PATCH] Fix PR77826 In-Reply-To: Message-ID: References: User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-SW-Source: 2016-10/txt/msg00983.txt.bz2 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 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 @@. (parser::parse_capture): Parse @@ 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 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 (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 (n1))->op, (as_a (n2))->op); else if (n1->type == dt_node::DT_MATCH) - return ((as_a (n1))->match_dop - == (as_a (n2))->match_dop); + return (((as_a (n1))->match_dop + == (as_a (n2))->match_dop) + && ((as_a (n1))->value_match + == (as_a (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 (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 active_ifs; vec > 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 > cpts) +{ + if (! op) + return; + + if (capture *c = dyn_cast (op)) + { + cpts[c->where].safe_push (c); + walk_captures (c->what, cpts); + } + else if (expr *e = dyn_cast (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 > 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 @__@1 and @1 into @__. */ + 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).