From patchwork Tue Sep 23 11:02:16 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 392373 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 9695D14008B for ; Tue, 23 Sep 2014 21:06:10 +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=p7bNNVvWU42iNp2k9OjuOpZKn8sAaJVCQATYFhuknorAYaEKKH9tA fyW2rOBVmljDt3e8jEs13XHeANYnsDXIZpVDB4kvj4fwYnzyPCyPS2jjZJKXtIRW e2QIsjxonkXoapa+FI5ys7D3deXIQTyyqp5FnhunTwoZZsDr7bJbNs= 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=+aCKnoKgtaPOk3r04XdsunJ0J6o=; b=Q85JQIbPDYhPZnmRwrXr 8lawyxDW80rnYKd9c1UiCfGsT2HaABGtkiuiOC5L6ykdSP+ZtXAwnBJSdG0gwHx8 AT4lA5tsBYCrGMAMbZwXr7MjVXznCyvhchp8oz7plgXBS1NZzkqgiRofszqDWWMe 6mkmzIQe2pJq1dFL8lCAgD0= Received: (qmail 6425 invoked by alias); 23 Sep 2014 11:06:03 -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 6414 invoked by uid 89); 23 Sep 2014 11:06:03 -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, 23 Sep 2014 11:06:00 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 9DACAAD95 for ; Tue, 23 Sep 2014 11:05:57 +0000 (UTC) Date: Tue, 23 Sep 2014 13:02:16 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH][match-and-simplify] Add predicate expressions Message-ID: User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 As promised this allows you to define custom predicate expressions (or operators), like one modeled after tree-ssa-forwprop.c:lookup_logical_inverted_value: (match logical_inverted_value (bit_not truth_valued_p@0) (logical_inverted_value @0)) (match logical_inverted_value (eq @0 integer_zerop) (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) (logical_inverted_value @0))) (match logical_inverted_value (ne truth_valued_p@0 integer_onep) (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) (logical_inverted_value @0))) (match logical_inverted_value (bit_xor truth_valued_p@0 integer_onep) (logical_inverted_value @0)) which you can use as (logical_inverted_value ) anywhere in expressions you want to match, like for example /* X & !X -> 0. */ (simplify (bit_and @0 (logical_inverted_value @0)) { build_zero_cst (type); }) you can continue matching on the result, thus write (logical_inverted_value (plus @0 INTEGER_CST)) (doesn't make much sense for this example though). The result of logical_inverted_value is then matched against the expression. I noticed that parsing of 'for' and outer 'if's is broken with respect to all (match ...)es. The patch is big enough already, I'll try to fix that as followup ('if' is easy, 'for' is more interesting). As usage example I've taken the forwprop simplify_bitwise_binary_1 code. Note that code-generation using predicate expressions is worse than if you manually inline-expand all cases (and the generator doesn't yet inline-expand here - but it could, at least in theory). You can now write pattern-based IL matching for, say, vectorizer pattern detection and use it via the generated APIs that follows bool gimple_logical_inverted_value (tree t, tree *res_ops, tree (*valueize)(tree) = NULL); where res_ops[0] will contain the matched operands of the operation. Bootstrap and regtest in progress. Richard. 2014-09-23 Richard Biener * genmatch.c (struct predicate_id): Add nargs member. (struct simplify): Remove name member. (lower_commutative): Adjust. (lower_opt_convert): Likewise. (dt_node::gen_gimple_kids): Generate code for predicate expressions. (dt_node::gen_generic_kids): Likewise. (dt_simplify::gen): Likewise. (write_predicate_prototype): New function. (write_predicate): Adjust. (parse_simplify): Be less forgiving about errors, handle predicate expression definitions. (parse_pattern): Adjust. (main): Output prototypes for all predicates first. * match-bitwise.pd (X & !X -> 0, X | !X and X ^ !X -> 1): Implement using predicate expressions, more closely matching code in tree-ssa-forwprop.c. Index: gcc/genmatch.c =================================================================== --- gcc/genmatch.c (revision 215499) +++ gcc/genmatch.c (working copy) @@ -193,8 +193,9 @@ struct simplify; struct predicate_id : public id_base { predicate_id (const char *id_) - : id_base (id_base::PREDICATE, id_), matchers (vNULL) {} + : id_base (id_base::PREDICATE, id_), matchers (vNULL), nargs(-1) {} vec matchers; + int nargs; }; template<> @@ -433,14 +434,12 @@ struct if_or_with { }; struct simplify { - simplify (const char *name_, - operand *match_, source_location match_location_, + simplify (operand *match_, source_location match_location_, struct operand *result_, source_location result_location_, vec ifexpr_vec_ = vNULL) - : name (name_), match (match_), match_location (match_location_), + : match (match_), match_location (match_location_), result (result_), result_location (result_location_), ifexpr_vec (ifexpr_vec_) {} - const char *name; operand *match; source_location match_location; struct operand *result; @@ -682,7 +681,7 @@ lower_commutative (simplify *s, vec matchers = commutate (s->match); for (unsigned i = 0; i < matchers.length (); ++i) { - simplify *ns = new simplify (s->name, matchers[i], s->match_location, + simplify *ns = new simplify (matchers[i], s->match_location, s->result, s->result_location, s->ifexpr_vec); simplifiers.safe_push (ns); } @@ -810,7 +809,7 @@ lower_opt_convert (simplify *s, vec matchers = lower_opt_convert (s->match); for (unsigned i = 0; i < matchers.length (); ++i) { - simplify *ns = new simplify (s->name, matchers[i], s->match_location, + simplify *ns = new simplify (matchers[i], s->match_location, s->result, s->result_location, s->ifexpr_vec); simplifiers.safe_push (ns); } @@ -1512,10 +1511,11 @@ dt_operand::gen_generic_expr (FILE *f, c void dt_node::gen_gimple_kids (FILE *f) { - vec gimple_exprs = vNULL; - vec generic_exprs = vNULL; - vec fns = vNULL; - vec others = vNULL; + auto_vec gimple_exprs; + auto_vec generic_exprs; + auto_vec fns; + auto_vec preds; + auto_vec others; dt_node *true_operand = NULL; for (unsigned i = 0; i < kids.length (); ++i) { @@ -1527,6 +1527,8 @@ dt_node::gen_gimple_kids (FILE *f) generic_exprs.safe_push (op); else if (e->operation->op->kind == id_base::FN) fns.safe_push (op); + else if (e->operation->op->kind == id_base::PREDICATE) + preds.safe_push (op); else gimple_exprs.safe_push (op); } @@ -1638,6 +1640,25 @@ dt_node::gen_gimple_kids (FILE *f) fprintf (f, "default:;\n" "}\n"); + for (unsigned i = 0; i < preds.length (); ++i) + { + expr *e = as_a (preds[i]->op); + predicate_id *p = as_a (e->operation->op); + preds[i]->get_name (kid_opname); + fprintf (f, "tree %s_pops[%d];\n", kid_opname, p->nargs); + fprintf (f, "if (gimple_%s (%s, %s_pops, valueize))\n", p->id, + kid_opname, kid_opname); + fprintf (f, "{\n"); + for (int j = 0; j < p->nargs; ++j) + { + char child_opname[20]; + preds[i]->gen_opname (child_opname, j); + fprintf (f, "tree %s = %s_pops[%d];\n", child_opname, kid_opname, j); + } + preds[i]->gen_gimple_kids (f); + fprintf (f, "}\n"); + } + for (unsigned i = 0; i < others.length (); ++i) others[i]->gen_gimple (f); @@ -1721,6 +1742,10 @@ dt_operand::gen_generic (FILE *f) void dt_node::gen_generic_kids (FILE *f) { + auto_vec generic_exprs; + auto_vec fns; + auto_vec preds; + bool any = false; for (unsigned j = 0; j < kids.length (); ++j) { @@ -1729,7 +1754,23 @@ dt_node::gen_generic_kids (FILE *f) { dt_operand *kid = static_cast(node); if (kid->op->type == operand::OP_EXPR) - any = true; + { + expr *e = as_a (kid->op); + if (e->operation->op->kind == id_base::CODE) + { + generic_exprs.safe_push (kid); + any = true; + } + else if (e->operation->op->kind == id_base::FN) + { + fns.safe_push (kid); + any = true; + } + else if (e->operation->op->kind == id_base::PREDICATE) + preds.safe_push (kid); + else + gcc_unreachable (); + } } } @@ -1739,17 +1780,11 @@ dt_node::gen_generic_kids (FILE *f) static_cast (kids[0])->get_name (opname); fprintf (f, "switch (TREE_CODE (%s))\n" "{\n", opname); - for (unsigned j = 0; j < kids.length (); ++j) + for (unsigned j = 0; j < generic_exprs.length (); ++j) { - dt_node *node = kids[j]; - if (node->type != DT_OPERAND) - continue; - dt_operand *kid = static_cast(node); - if (kid->op->type != operand::OP_EXPR) - continue; - expr *e = static_cast (kid->op); - if (e->operation->op->kind != id_base::CODE) - continue; + dt_operand *kid = generic_exprs[j]; + expr *e = as_a (kid->op); + gcc_assert (e->operation->op->kind == id_base::CODE); /* ??? CONVERT */ fprintf (f, "case %s:\n" @@ -1760,17 +1795,11 @@ dt_node::gen_generic_kids (FILE *f) } bool first = true; - for (unsigned j = 0; j < kids.length (); ++j) + for (unsigned j = 0; j < fns.length (); ++j) { - dt_node *node = kids[j]; - if (node->type != DT_OPERAND) - continue; - dt_operand *kid = static_cast(node); - if (kid->op->type != operand::OP_EXPR) - continue; - expr *e = static_cast (kid->op); - if (e->operation->op->kind != id_base::FN) - continue; + dt_operand *kid = fns[j]; + expr *e = as_a (kid->op); + gcc_assert (e->operation->op->kind == id_base::FN); if (first) fprintf (f, "case CALL_EXPR:\n" @@ -1797,6 +1826,26 @@ dt_node::gen_generic_kids (FILE *f) "}\n"); } + for (unsigned i = 0; i < preds.length (); ++i) + { + expr *e = as_a (preds[i]->op); + predicate_id *p = as_a (e->operation->op); + char kid_opname[128]; + preds[i]->get_name (kid_opname); + fprintf (f, "tree %s_pops[%d];\n", kid_opname, p->nargs); + fprintf (f, "if (tree_%s (%s, %s_pops))\n", p->id, + kid_opname, kid_opname); + fprintf (f, "{\n"); + for (int j = 0; j < p->nargs; ++j) + { + char child_opname[20]; + preds[i]->gen_opname (child_opname, j); + fprintf (f, "tree %s = %s_pops[%d];\n", child_opname, kid_opname, j); + } + preds[i]->gen_generic_kids (f); + fprintf (f, "}\n"); + } + for (unsigned j = 0; j < kids.length (); ++j) { dt_node *node = kids[j]; @@ -1887,23 +1936,27 @@ dt_simplify::gen (FILE *f, bool gimple) { if (s->result->type == operand::OP_EXPR) { - expr *e = static_cast (s->result); - fprintf (f, "*res_code = %s;\n", e->operation->op->id); + expr *e = as_a (s->result); + bool is_predicate = is_a (e->operation->op); + if (!is_predicate) + fprintf (f, "*res_code = %s;\n", e->operation->op->id); for (unsigned j = 0; j < e->ops.length (); ++j) { char dest[32]; snprintf (dest, 32, " res_ops[%d]", j); const char *optype - = get_operand_type (e->operation->op, - "type", e->expr_type, - j == 0 - ? NULL : "TREE_TYPE (res_ops[0])"); + = get_operand_type (e->operation->op, + "type", e->expr_type, + j == 0 + ? NULL : "TREE_TYPE (res_ops[0])"); e->ops[j]->gen_transform (f, dest, true, 1, optype, indexes); } + /* Re-fold the toplevel result. It's basically an embedded gimple_build w/o actually building the stmt. */ - fprintf (f, "gimple_resimplify%d (seq, res_code, type, " - "res_ops, valueize);\n", e->ops.length ()); + if (!is_predicate) + fprintf (f, "gimple_resimplify%d (seq, res_code, type, " + "res_ops, valueize);\n", e->ops.length ()); } else if (s->result->type == operand::OP_CAPTURE || s->result->type == operand::OP_C_EXPR) @@ -1919,12 +1972,18 @@ dt_simplify::gen (FILE *f, bool gimple) { if (s->result->type == operand::OP_EXPR) { - expr *e = static_cast (s->result); + expr *e = as_a (s->result); + bool is_predicate = is_a (e->operation->op); for (unsigned j = 0; j < e->ops.length (); ++j) { - fprintf (f, " tree res_op%d;\n", j); char dest[32]; - snprintf (dest, 32, " res_op%d", j); + if (is_predicate) + snprintf (dest, 32, "res_ops[%d]", j); + else + { + fprintf (f, " tree res_op%d;\n", j); + snprintf (dest, 32, " res_op%d", j); + } const char *optype = get_operand_type (e->operation->op, "type", e->expr_type, @@ -1932,16 +1991,21 @@ dt_simplify::gen (FILE *f, bool gimple) ? NULL : "TREE_TYPE (res_op0)"); e->ops[j]->gen_transform (f, dest, false, 1, optype, indexes); } - /* Re-fold the toplevel result. */ - if (e->operation->op->kind == id_base::CODE) - fprintf (f, " return fold_build%d (%s, type", - e->ops.length (), e->operation->op->id); + if (is_a (e->operation->op)) + fprintf (f, "return true;\n"); else - fprintf (f, " return build_call_expr (builtin_decl_implicit (%s), %d", - e->operation->op->id, e->ops.length()); - for (unsigned j = 0; j < e->ops.length (); ++j) - fprintf (f, ", res_op%d", j); - fprintf (f, ");\n"); + { + /* Re-fold the toplevel result. */ + if (e->operation->op->kind == id_base::CODE) + fprintf (f, " return fold_build%d (%s, type", + e->ops.length (), e->operation->op->id); + else + fprintf (f, " return build_call_expr (builtin_decl_implicit (%s), %d", + e->operation->op->id, e->ops.length()); + for (unsigned j = 0; j < e->ops.length (); ++j) + fprintf (f, ", res_op%d", j); + fprintf (f, ");\n"); + } } else if (s->result->type == operand::OP_CAPTURE || s->result->type == operand::OP_C_EXPR) @@ -2062,12 +2126,22 @@ decision_tree::gen_generic (FILE *f) } void +write_predicate_prototype (FILE *f, predicate_id *p, bool gimple) +{ + fprintf (f, "bool %s%s (tree t%s%s);\n", + gimple ? "gimple_" : "tree_", p->id, + p->nargs > 0 ? ", tree *res_ops" : "", + gimple ? ", tree (*valueize)(tree) = NULL" : ""); +} + +void write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple) { fprintf (f, "\nbool\n" - "%s%s (tree t%s)\n" + "%s%s (tree t%s%s)\n" "{\n", gimple ? "gimple_" : "tree_", p->id, - gimple ? ", tree (*valueize)(tree) = NULL" : ""); + p->nargs > 0 ? ", tree *res_ops" : "", + gimple ? ", tree (*valueize)(tree)" : ""); /* Conveniently make 'type' available. */ fprintf (f, "tree type = TREE_TYPE (t);\n"); @@ -2458,13 +2532,16 @@ copy_reverse (vec v) and fill SIMPLIFIERS with the results. */ static void -parse_simplify (cpp_reader *r, const char *id, source_location match_location, - vec& simplifiers) +parse_simplify (cpp_reader *r, source_location match_location, + vec& simplifiers, predicate_id *matcher) { const cpp_token *loc = peek (r); struct operand *match = parse_op (r); - if (match->type != operand::OP_EXPR) - fatal_at (loc, "expected uncaptured expression"); + if (match->type == operand::OP_CAPTURE && !matcher) + fatal_at (loc, "outermost expression cannot be captured"); + if (match->type == operand::OP_EXPR + && is_a (as_a (match)->operation->op)) + fatal_at (loc, "outermost expression cannot be a predicate"); const cpp_token *token = peek (r); @@ -2472,8 +2549,14 @@ parse_simplify (cpp_reader *r, const cha definition. Push it. */ if (token->type == CPP_CLOSE_PAREN) { + if (!matcher) + fatal_at (token, "expected transform expression"); + else if (matcher->nargs > 0) + fatal_at (token, "expected match operand expression"); + if (matcher->nargs == -1) + matcher->nargs = 0; simplifiers.safe_push - (new simplify (id, match, match_location, NULL, token->src_loc)); + (new simplify (match, match_location, NULL, token->src_loc)); return; } @@ -2493,9 +2576,17 @@ parse_simplify (cpp_reader *r, const cha 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))); + { + if (!matcher) + fatal_at (token, "manual transform not implemented"); + else if (matcher->nargs > 0) + fatal_at (token, "expected match operand expression"); + if (matcher->nargs == -1) + matcher->nargs = 0; + simplifiers.safe_push + (new simplify (match, match_location, NULL, + paren_loc, copy_reverse (ifexprs))); + } } else if (peek_ident (r, "with")) { @@ -2507,8 +2598,20 @@ parse_simplify (cpp_reader *r, const cha } else { + operand *op = parse_expr (r); + if (matcher) + { + expr *e = dyn_cast (op); + if (!e) + fatal_at (token, "match operand expression cannot be captured"); + if (matcher->nargs == -1) + matcher->nargs = e->ops.length (); + if (matcher->nargs == 0 + || (unsigned) matcher->nargs != e->ops.length ()) + fatal_at (token, "match arity doesn't match"); + } simplifiers.safe_push - (new simplify (id, match, match_location, parse_expr (r), + (new simplify (match, match_location, op, token->src_loc, copy_reverse (ifexprs))); eat_token (r, CPP_CLOSE_PAREN); /* A "default" result closes the enclosing scope. */ @@ -2535,8 +2638,10 @@ parse_simplify (cpp_reader *r, const cha } else { + if (matcher) + fatal_at (token, "expected match operand expression"); simplifiers.safe_push - (new simplify (id, match, match_location, parse_op (r), + (new simplify (match, match_location, parse_op (r), token->src_loc, copy_reverse (ifexprs))); /* A "default" result closes the enclosing scope. */ if (ifexprs.length () > 0) @@ -2654,7 +2759,7 @@ parse_for (cpp_reader *r, source_locatio ifexpr_vec[k].cexpr = replace_id (ifexpr_vec[k].cexpr, user_ids[i], oper); } - simplify *ns = new simplify (s->name, match_op, s->match_location, + simplify *ns = new simplify (match_op, s->match_location, result_op, s->result_location, ifexpr_vec); simplifiers.safe_push (ns); } @@ -2713,7 +2818,7 @@ parse_pattern (cpp_reader *r, vecsrc_loc, simplifiers); + parse_simplify (r, token->src_loc, simplifiers, NULL); else if (strcmp (id, "match") == 0) { const char *name = get_ident (r); @@ -2725,8 +2830,7 @@ parse_pattern (cpp_reader *r, vecsrc_loc, p->matchers); - /* ??? Sanity check the added "simplifiers". */ + parse_simplify (r, token->src_loc, p->matchers, p); } else if (strcmp (id, "for") == 0) parse_for (r, token->src_loc, simplifiers); @@ -2839,6 +2943,15 @@ add_operator (CONVERT2, "CONVERT2", "tcc 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 ()) + /* ??? Write prototypes to some header? */ + write_predicate_prototype (stdout, p, gimple); + } + 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 ()) Index: gcc/match-bitwise.pd =================================================================== --- gcc/match-bitwise.pd (revision 215499) +++ gcc/match-bitwise.pd (working copy) @@ -65,6 +65,42 @@ along with GCC; see the file COPYING3. /* Try simple folding for X op !X, and X op X. From tree-ssa-forwprop.c:simplify_bitwise_binary_1. */ +/* tree-ssa-forwprop.c:truth_valued_ssa_name. */ +(match truth_valued_p + @0 + (if (INTEGRAL_TYPE_P (type) && TYPE_PRECISION (type) == 1))) +#if 0 +/* ??? for doesn't yet work for matchers. */ +(for op (lt le eq ne ge gt truth_and truth_andif truth_or truth_orif truth_xor) + (match truth_valued_p + (op @0 @1))) +#endif +(match truth_valued_p + (truth_not @0)) +(match logical_inverted_value + (bit_not truth_valued_p@0) + (logical_inverted_value @0)) +(match logical_inverted_value + (eq @0 integer_zerop) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) + (logical_inverted_value @0))) +(match logical_inverted_value + (ne truth_valued_p@0 integer_onep) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) + (logical_inverted_value @0))) +(match logical_inverted_value + (bit_xor truth_valued_p@0 integer_onep) + (logical_inverted_value @0)) +/* X & !X -> 0. */ +(simplify + (bit_and @0 (logical_inverted_value @0)) + { build_zero_cst (type); }) +/* X | !X and X ^ !X -> 1, , if X is truth-valued. */ +(for op (bit_ior bit_xor) + (simplify + (op truth_valued_p@0 (logical_inverted_value @0)) + { build_one_cst (type); })) +#if 0 /* x & x -> x, x | x -> x */ (for bitop (bit_and bit_ior) (simplify @@ -98,6 +134,7 @@ along with GCC; see the file COPYING3. (if (truth_valued_ssa_name (@0)) { bitop == BIT_AND ? build_zero_cst (type) : build_one_cst (type); })))) #endif +#endif (for bitop (bit_and bit_ior) rbitop (bit_ior bit_and)