From patchwork Tue Sep 16 13:30:56 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 390069 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 8604814012E for ; Tue, 16 Sep 2014 23:34:49 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=lpFyKPB29NEuoLofG/WRtbow51MmEQzzuxYoYr7XhaLoQ7kypDTrh xhpfL7wF+8PkQClvTEApvnv5zqESIBuVBf+RoDI9TTrW8bTgtorauJKKssfQfMs4 Nv7C2iUSG1L1BT6fh7Iyb78Xir+QryL6Ob7sc0fytcvIIjjLFSKkB0= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=sKYej6r7+YYXr9K6LIVhYx/KQXs=; b=xFzKoNiiUqmgWp5avsc3 2vlMohBELt+7fjhbOmfIxusxHZ79i9jRiNaQBrfRmCWO7UstnrHMxxaCkqqus1Xh mwVNaMtT4MTMVNPoAQ7AHSB2t01EpR/2tUwfLwTM2V+msfLMz3hUsvXswFKWwElD Iee9x7igdyefEkELjx/3B5Q= Received: (qmail 12219 invoked by alias); 16 Sep 2014 13:34:39 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 12206 invoked by uid 89); 16 Sep 2014 13:34:38 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.6 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx2.suse.de Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Tue, 16 Sep 2014 13:34:35 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 6F9E0AD75 for ; Tue, 16 Sep 2014 13:34:32 +0000 (UTC) Date: Tue, 16 Sep 2014 15:30:56 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH][match-and-simplify] User defined predicates Message-ID: User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 The following adds the ability to write predicates using patterns with an example following negate_expr_p which already has a use in comparison folding (via its if c-expr). The syntax is as follows: (match negate_expr_p INTEGER_CST (if (TYPE_OVERFLOW_WRAPS (type) || may_negate_without_overflow_p (t)))) (match negate_expr_p (bit_not @0) (if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_WRAPS (type)))) (match negate_expr_p FIXED_CST) (match negate_expr_p (negate @0)) ... that is, you write '(match ' instead of '(simplify' and then follow with a pattern and optional conditionals. There should be no transform pattern (unchecked yet). Multiple matches for the same simply add to what is recognized as . The predicate is applied to a single 'tree' operand and looks up SSA defs and utilizes the optional valueize hook. Currently both GENERIC and GIMPLE variants result in name-mangling and the proptotypes (unprototyped anywhere) bool tree_negate_expr_p (tree t); bool gimple_negate_expr_p (tree t, tree (*valueize)(tree) = NULL); The predicate implementations simply use a separate decision tree. I plan to follow this up with the ability to specify custom operators like (match widen_mult (mult (convert @0) (convert @1)) (if (TYPE_PRECISION (TREE_TYPE (@0)) < TYPE_PRECISION (type)) (widen_mult @0 @1))) and the ability to use that in (simplify (convert (widen_mult @0 @1)) (if (TYPE_PRECISION (TREE_TYPE (@0)) == TYPE_PRECISION (type)) (mult @0 @1))) the generated APIs would then be sth like bool gimple_wide_mult (tree t, tree *captures, tree (*valueize)(tree) = NULL); thus receive @0 and @1 in the captures array. This may help factoring out stuff in the patterns itself and it addresses the desire to use the pattern-matching engine from say tree-vect-patterns.c. Bootstrap and regtest ongoing on x86_64-unknown-linux-gnu. Comments? (syntax bike-shedding?) Thanks, Richard. 2014-09-16 Richard Biener * genmatch.c (struct predicate_id): Add matchers member. (add_predicate): Return added predicate. (dt_node::gen_gimple_kids, dt_node::gen_generic_kids): Relocate from ... (dt_operand::gen_gimple_kids, dt_node::gen_generic_kids): ... here. (check_no_user_id): Guard against NULL result. (dt_operand::get_name): Handle NULL parent. (dt_operand::gen_opname): Likewise. (dt_operand::gen_predicate): Mangle user-defined predicates. (dt_operand::gen_generic): Adjust. (dt_operand::gen_gimple): Likewise. (dt_simplify::gen): Guard against NULL result. (write_predicate): New function. (write_header): Only write header, not split out c-exprs. (parse_simplify): Move identifier handling out, handle "empty" result. (parse_pattern): Parse (match ...). Drop optional identifier from (simplify...). (lower): New function, split out from ... (main): ... here. Generate code for all user-defined predicates. * match.pd (negate_expr_p): Implement as predicate. * match-comparison.pd: Use negate_expr_p predicate. Index: gcc/genmatch.c =================================================================== --- gcc/genmatch.c (revision 215297) +++ gcc/genmatch.c (working copy) @@ -188,9 +188,13 @@ struct fn_id : public id_base enum built_in_function fn; }; +struct simplify; + struct predicate_id : public id_base { - predicate_id (const char *id_) : id_base (id_base::PREDICATE, id_) {} + predicate_id (const char *id_) + : id_base (id_base::PREDICATE, id_), matchers (vNULL) {} + vec matchers; }; template<> @@ -217,7 +221,7 @@ is_a_helper ::test (id_b return id->kind == id_base::PREDICATE; } -static void +static predicate_id * add_predicate (const char *id) { predicate_id *p = new predicate_id (id); @@ -225,6 +229,7 @@ add_predicate (const char *id) if (*slot) fatal ("duplicate id definition"); *slot = p; + return p; } static void @@ -461,6 +466,9 @@ struct dt_node virtual void gen_gimple (FILE *) {} virtual void gen_generic (FILE *) {} + + void gen_gimple_kids (FILE *); + void gen_generic_kids (FILE *); }; struct dt_operand: public dt_node @@ -475,7 +483,7 @@ struct dt_operand: public dt_node virtual void gen_gimple (FILE *); virtual void gen_generic (FILE *); - unsigned gen_predicate (FILE *, const char *); + unsigned gen_predicate (FILE *, const char *, bool); unsigned gen_match_op (FILE *, const char *); unsigned gen_gimple_expr (FILE *); @@ -483,9 +491,6 @@ struct dt_operand: public dt_node char *get_name (char *); void gen_opname (char *, unsigned); - - void gen_gimple_kids (FILE *); - void gen_generic_kids (FILE *); }; @@ -901,7 +906,8 @@ void check_no_user_id (simplify *s) { check_no_user_id (s->match); - check_no_user_id (s->result); + if (s->result) + check_no_user_id (s->result); } bool @@ -1386,7 +1392,9 @@ decision_tree::print (FILE *f) char * dt_operand::get_name (char *name) { - if (parent->level == 1) + if (!parent) + sprintf (name, "t"); + else if (parent->level == 1) sprintf (name, "op%u", pos); else if (parent->type == dt_node::DT_MATCH) return parent->get_name (name); @@ -1398,15 +1406,28 @@ dt_operand::get_name (char *name) void dt_operand::gen_opname (char *name, unsigned pos) { - sprintf (name, "o%u%u", level, pos); + if (!parent) + sprintf (name, "op%u", pos); + else + sprintf (name, "o%u%u", level, pos); } unsigned -dt_operand::gen_predicate (FILE *f, const char *opname) +dt_operand::gen_predicate (FILE *f, const char *opname, bool gimple) { predicate *p = as_a (op); - fprintf (f, "if (%s (%s))\n", p->p->id, opname); + if (p->p->matchers.exists ()) + { + /* If this is a predicate generated from a pattern mangle its + name and pass on the valueize hook. */ + if (gimple) + fprintf (f, "if (gimple_%s (%s, valueize))\n", p->p->id, opname); + else + fprintf (f, "if (tree_%s (%s))\n", p->p->id, opname); + } + else + fprintf (f, "if (%s (%s))\n", p->p->id, opname); fprintf (f, "{\n"); return 1; } @@ -1489,7 +1510,7 @@ dt_operand::gen_generic_expr (FILE *f, c } void -dt_operand::gen_gimple_kids (FILE *f) +dt_node::gen_gimple_kids (FILE *f) { vec gimple_exprs = vNULL; vec generic_exprs = vNULL; @@ -1636,7 +1657,7 @@ dt_operand::gen_gimple (FILE *f) switch (op->type) { case operand::OP_PREDICATE: - n_braces = gen_predicate (f, opname); + n_braces = gen_predicate (f, opname, true); break; case operand::OP_EXPR: @@ -1672,7 +1693,7 @@ dt_operand::gen_generic (FILE *f) switch (op->type) { case operand::OP_PREDICATE: - n_braces = gen_predicate (f, opname); + n_braces = gen_predicate (f, opname, false); break; case operand::OP_EXPR: @@ -1698,7 +1719,7 @@ dt_operand::gen_generic (FILE *f) } void -dt_operand::gen_generic_kids (FILE *f) +dt_node::gen_generic_kids (FILE *f) { bool any = false; for (unsigned j = 0; j < kids.length (); ++j) @@ -1857,7 +1878,12 @@ dt_simplify::gen (FILE *f, bool gimple) output_line_directive (f, s->result_location, true); fprintf (f, ", %%s:%%d\\n\", __FILE__, __LINE__);\n"); - if (gimple) + if (!s->result) + { + /* If there is no result then this is a predicate implementation. */ + fprintf (f, "return true;\n"); + } + else if (gimple) { if (s->result->type == operand::OP_EXPR) { @@ -2035,6 +2061,30 @@ decision_tree::gen_generic (FILE *f) } } +void +write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple) +{ + fprintf (f, "\nbool\n" + "%s%s (tree t%s)\n" + "{\n", gimple ? "gimple_" : "tree_", p->id, + gimple ? ", tree (*valueize)(tree) = NULL" : ""); + /* Conveniently make 'type' available. */ + fprintf (f, "tree type = TREE_TYPE (t);\n"); + + if (!gimple) + { + fprintf (f, "if (TREE_SIDE_EFFECTS (t)) return false;\n"); + dt.root->gen_generic_kids (f); + } + else + { + dt.root->gen_gimple_kids (f); + } + + fprintf (f, "return false;\n" + "}\n"); +} + static void outline_c_exprs (FILE *f, struct operand *op) @@ -2071,17 +2121,13 @@ outline_c_exprs (FILE *f, struct operand } static void -write_header (FILE *f, vec& simplifiers, const char *head) +write_header (FILE *f, const char *head) { fprintf (f, "/* Generated automatically by the program `genmatch' from\n"); fprintf (f, " a IL pattern matching and simplification description. */\n"); /* Include the header instead of writing it awkwardly quoted here. */ fprintf (f, "\n#include \"%s\"\n", head); - - /* Outline complex C expressions to helper functions. */ - for (unsigned i = 0; i < simplifiers.length (); ++i) - outline_c_exprs (stdout, simplifiers[i]->result); } @@ -2412,38 +2458,44 @@ copy_reverse (vec v) and fill SIMPLIFIERS with the results. */ static void -parse_simplify (cpp_reader *r, source_location match_location, +parse_simplify (cpp_reader *r, const char *id, source_location match_location, vec& simplifiers) { - const cpp_token *token = peek (r); - const char *id; - if (token->type == CPP_NAME) - id = get_ident (r); - else - { - static int cnt; - char *tem; - asprintf (&tem, "anon_%d", ++cnt); - id = tem; - } const cpp_token *loc = peek (r); struct operand *match = parse_op (r); if (match->type != operand::OP_EXPR) fatal_at (loc, "expected uncaptured expression"); - token = peek (r); + const cpp_token *token = peek (r); + + /* If this if is immediately closed then it is part of a predicate + definition. Push it. */ + if (token->type == CPP_CLOSE_PAREN) + { + simplifiers.safe_push + (new simplify (id, match, match_location, NULL, token->src_loc)); + return; + } auto_vec ifexprs; while (1) { if (token->type == CPP_OPEN_PAREN) { + source_location paren_loc = token->src_loc; eat_token (r, CPP_OPEN_PAREN); if (peek_ident (r, "if")) { eat_ident (r, "if"); ifexprs.safe_push (if_or_with (parse_c_expr (r, CPP_OPEN_PAREN), token->src_loc, false)); + /* If this if is immediately closed then it contains a + manual matcher or is part of a predicate definition. + Push it. */ + if (peek (r)->type == CPP_CLOSE_PAREN) + simplifiers.safe_push + (new simplify (id, match, match_location, NULL, + paren_loc, copy_reverse (ifexprs))); } else if (peek_ident (r, "with")) { @@ -2661,7 +2713,21 @@ parse_pattern (cpp_reader *r, vecsrc_loc, simplifiers); + parse_simplify (r, NULL, token->src_loc, simplifiers); + else if (strcmp (id, "match") == 0) + { + const char *name = get_ident (r); + id_base *id = get_operator (name); + predicate_id *p; + if (!id) + p = add_predicate (name); + else if ((p = dyn_cast (id))) + ; + else + fatal_at (token, "cannot add a match to a non-predicate ID"); + parse_simplify (r, name, token->src_loc, p->matchers); + /* ??? Sanity check the added "simplifiers". */ + } else if (strcmp (id, "for") == 0) parse_for (r, token->src_loc, simplifiers); else if (strcmp (id, "if") == 0) @@ -2674,6 +2740,23 @@ parse_pattern (cpp_reader *r, vec +lower (vec simplifiers) +{ + for (unsigned i = 0; i < simplifiers.length (); ++i) + check_no_user_id (simplifiers[i]); + + vec out_simplifiers0 = vNULL; + for (unsigned i = 0; i < simplifiers.length (); ++i) + lower_opt_convert (simplifiers[i], out_simplifiers0); + + vec out_simplifiers = vNULL; + for (unsigned i = 0; i < out_simplifiers0.length (); ++i) + lower_commutative (out_simplifiers0[i], out_simplifiers); + + return out_simplifiers; +} + int main(int argc, char **argv) { @@ -2746,16 +2829,39 @@ add_operator (CONVERT2, "CONVERT2", "tcc token = next (r); } - for (unsigned i = 0; i < simplifiers.length (); ++i) - check_no_user_id (simplifiers[i]); + if (gimple) + write_header (stdout, "gimple-match-head.c"); + else + write_header (stdout, "generic-match-head.c"); - vec out_simplifiers0 = vNULL; - for (unsigned i = 0; i < simplifiers.length (); ++i) - lower_opt_convert (simplifiers[i], out_simplifiers0); + /* Go over all predicates defined with patterns and perform + lowering and code generation. */ + for (hash_table::iterator iter = operators->begin (); + iter != operators->end (); ++iter) + { + id_base *id = *iter; + if (predicate_id *p = dyn_cast (id)) + if (p->matchers.exists ()) + { + vec matchers = lower (p->matchers); + p->matchers = matchers; - vec out_simplifiers = vNULL; - for (unsigned i = 0; i < out_simplifiers0.length (); ++i) - lower_commutative (out_simplifiers0[i], out_simplifiers); + if (verbose) + for (unsigned i = 0; i < matchers.length (); ++i) + print_matches (matchers[i]); + + decision_tree dt; + for (unsigned i = 0; i < matchers.length (); ++i) + dt.insert (matchers[i], i); + + if (verbose) + dt.print (stderr); + + write_predicate (stdout, p, dt, gimple); + } + } + + vec out_simplifiers = lower (simplifiers); if (verbose) for (unsigned i = 0; i < out_simplifiers.length (); ++i) @@ -2768,16 +2874,14 @@ add_operator (CONVERT2, "CONVERT2", "tcc if (verbose) dt.print (stderr); + /* Outline complex C expressions to helper functions. */ + for (unsigned i = 0; i < out_simplifiers.length (); ++i) + outline_c_exprs (stdout, out_simplifiers[i]->result); + if (gimple) - { - write_header (stdout, out_simplifiers, "gimple-match-head.c"); - dt.gen_gimple (stdout); - } + dt.gen_gimple (stdout); else - { - write_header (stdout, out_simplifiers, "generic-match-head.c"); - dt.gen_generic (stdout); - } + dt.gen_generic (stdout); cpp_finish (r, NULL); cpp_destroy (r); Index: gcc/match-comparison.pd =================================================================== --- gcc/match-comparison.pd (revision 215297) +++ gcc/match-comparison.pd (working copy) @@ -18,10 +18,9 @@ (for op (eq ne) /* -exp op CST is exp op -CST. */ (simplify - (op (negate @0) INTEGER_CST@1) /* ??? fix fold-const to use negate_expr_p */ - (if (negate_expr_p (@1)) - (op @0 (negate @1)))) + (op (negate @0) negate_expr_p@1) + (op @0 (negate @1))) /* X ^ C1 == C2 is X == (C1 ^ C2). */ (simplify (op (bit_xor @0 INTEGER_CST@1) INTEGER_CST@2) Index: gcc/match.pd =================================================================== --- gcc/match.pd (revision 215297) +++ gcc/match.pd (working copy) @@ -30,6 +30,45 @@ (define_predicates CONSTANT_CLASS_P) +/* Simple example for a user-defined predicate - modeled after + fold-const.c:negate_expr_p. */ +(match negate_expr_p + INTEGER_CST + (if (TYPE_OVERFLOW_WRAPS (type) + || may_negate_without_overflow_p (t)))) +(match negate_expr_p + (bit_not @0) + (if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_WRAPS (type)))) +(match negate_expr_p + FIXED_CST) +(match negate_expr_p + (negate @0)) +(match negate_expr_p + REAL_CST + (if (REAL_VALUE_NEGATIVE (TREE_REAL_CST (t))))) +/* ??? For VECTOR_CST and COMPLEX_CST we don't have an easy way + to express the recursion (in the match pattern). Recursing + in the if expression causes us to refer to the fold-const.c:negate_expr_p + predicate as predicates are not "replaced" (mangled) in c-exprs. */ +(match negate_expr_p + /* -(A + B) -> (-A) - B. */ + /* -(A + B) -> (-B) - A. */ + (plus:c negate_expr_p @0) + (if (!HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type)) + && !HONOR_SIGNED_ZEROS (TYPE_MODE (type))))) +(match negate_expr_p + (minus @0 @1) + (if (!HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type)) + && !HONOR_SIGNED_ZEROS (TYPE_MODE (type))))) +/* ??? To be continued. Match up with actual simplifications! */ +/* ??? Unfortunately combining the predicate definition with + the actual simplification isn't possible. Would be a special-case + for negate_expr_p anyway. + (simplify + (negate (match negate_expr_p (....)) + anyone? */ + + /* tree-ssa/ifc-pr44710.c requires a < b ? c : d to fold to 1. ??? probably runs into issue of recursive folding of a < b op0. */ /* tree-ssa/ssa-ccp-16.c wants to fold "hello"[i_2] to 0