From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 3505 invoked by alias); 23 Oct 2014 13:16:18 -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 3420 invoked by uid 89); 23 Oct 2014 13:16:18 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.9 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; Thu, 23 Oct 2014 13:16:14 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id DA242ACC4 for ; Thu, 23 Oct 2014 13:16:10 +0000 (UTC) Date: Thu, 23 Oct 2014 13:19:00 -0000 From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH][match-and-simplify] 2nd try handling TREE_SIDE_EFFECTS Message-ID: User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-SW-Source: 2014-10/txt/msg02401.txt.bz2 This is a second attempt - it fixes the bugs in the previous one and handles falling back or not separately for the incoming arguments. What we handle too conservatively right now is non-captured leafs and captured expressions that are substituted into the result. Both result in the incoming arguments that mention the respective leaf / non-capture to be forced side-effect free. Bootstrapped on x86_64-unknown-linux-gnu, testing in progress. Richard. 2014-10-23 Richard Biener * genmatch.c (capture_info): New class. (capture_info::capture_info): New constructor. (capture_info::walk_match): New method. (capture_info::walk_result): New method. (capture_info::walk_c_expr): New method. (dt_simplify::gen): Handle preserving side-effects for GENERIC code generation. (decision_tree::gen_generic): Do not reject operands with TREE_SIDE_EFFECTS. Index: gcc/genmatch.c =================================================================== --- gcc/genmatch.c (revision 216549) +++ gcc/genmatch.c (working copy) @@ -1861,6 +1861,166 @@ dt_operand::gen (FILE *f, bool gimple) fprintf (f, "}\n"); } + +/* For GENERIC we have to take care of wrapping multiple-used + expressions with side-effects in save_expr and preserve side-effects + of expressions with omit_one_operand. Analyze captures in + match, result and with expressions and perform early-outs + on the outermost match expression operands for cases we cannot + handle. */ + +struct capture_info +{ + capture_info (simplify *s); + void walk_match (operand *o, unsigned toplevel_arg, bool); + void walk_result (operand *o, bool); + void walk_c_expr (c_expr *); + + struct cinfo + { + bool expr_p; + bool cse_p; + bool force_no_side_effects_p; + unsigned long toplevel_msk; + int result_use_count; + }; + + auto_vec info; + unsigned long force_no_side_effects; +}; + +/* Analyze captures in S. */ + +capture_info::capture_info (simplify *s) +{ + expr *e; + if (!s->result + || ((e = dyn_cast (s->result)) + && is_a (e->operation))) + { + force_no_side_effects = -1; + return; + } + + info.safe_grow_cleared (s->capture_max + 1); + e = as_a (s->match); + for (unsigned i = 0; i < e->ops.length (); ++i) + walk_match (e->ops[i], i, false); + + walk_result (s->result, false); + + for (unsigned i = 0; i < s->ifexpr_vec.length (); ++i) + if (s->ifexpr_vec[i].is_with) + walk_c_expr (as_a (s->ifexpr_vec[i].cexpr)); +} + +/* Analyze captures in the match expression piece O. */ + +void +capture_info::walk_match (operand *o, unsigned toplevel_arg, bool conditional_p) +{ + if (capture *c = dyn_cast (o)) + { + info[c->where].toplevel_msk |= 1 << toplevel_arg; + info[c->where].force_no_side_effects_p |= conditional_p; + /* Mark expr (non-leaf) captures and recurse. */ + if (c->what + && is_a (c->what)) + { + info[c->where].expr_p = true; + walk_match (c->what, toplevel_arg, conditional_p); + } + } + else if (expr *e = dyn_cast (o)) + { + for (unsigned i = 0; i < e->ops.length (); ++i) + { + bool cond_p = conditional_p; + if (i == 0 + && *e->operation == COND_EXPR) + cond_p = true; + else if (*e->operation == TRUTH_ANDIF_EXPR + || *e->operation == TRUTH_ORIF_EXPR) + cond_p = true; + walk_match (e->ops[i], toplevel_arg, cond_p); + } + } + else if (is_a (o)) + { + /* Mark non-captured leafs toplevel arg for checking. */ + force_no_side_effects |= 1 << toplevel_arg; + } + else + gcc_unreachable (); +} + +/* Analyze captures in the result expression piece O. */ + +void +capture_info::walk_result (operand *o, bool conditional_p) +{ + if (capture *c = dyn_cast (o)) + { + info[c->where].result_use_count++; + /* If we substitute an expression capture we don't know + which captures this will end up using (well, we don't + compute that). Force the uses to be side-effect free + which means forcing the toplevels that reach the + expression side-effect free. */ + if (info[c->where].expr_p) + force_no_side_effects |= info[c->where].toplevel_msk; + /* Mark CSE capture capture uses as forced to have + no side-effects. */ + if (c->what + && is_a (c->what)) + { + info[c->where].cse_p = true; + walk_result (c->what, true); + } + } + else if (expr *e = dyn_cast (o)) + { + for (unsigned i = 0; i < e->ops.length (); ++i) + { + bool cond_p = conditional_p; + if (i == 0 + && *e->operation == COND_EXPR) + cond_p = true; + else if (*e->operation == TRUTH_ANDIF_EXPR + || *e->operation == TRUTH_ORIF_EXPR) + cond_p = true; + walk_result (e->ops[i], cond_p); + } + } + else if (c_expr *e = dyn_cast (o)) + walk_c_expr (e); + else + gcc_unreachable (); +} + +/* Look for captures in the C expr E. */ + +void +capture_info::walk_c_expr (c_expr *e) +{ + /* Give up for C exprs mentioning captures. */ + for (unsigned i = 0; i < e->code.length (); ++i) + if (e->code[i].type == CPP_ATSIGN + && (e->code[i+1].type == CPP_NUMBER + || e->code[i+1].type == CPP_NAME) + && !(e->code[i+1].flags & PREV_WHITE)) + { + const cpp_token *n = &e->code[i+1]; + const char *id; + if (n->type == CPP_NUMBER) + id = (const char *)n->val.str.text; + else + id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str; + info[(*e->capture_ids)[id]].force_no_side_effects_p = true; + } +} + + /* Generate code for the '(if ...)', '(with ..)' and actual transform step of a '(simplify ...)' or '(match ...)'. This handles everything that is not part of the decision tree (simplify->match). */ @@ -1929,6 +2089,33 @@ dt_simplify::gen (FILE *f, bool gimple) n_braces++; } + /* Analyze captures and perform early-outs on the incoming arguments + that cover cases we cannot handle. */ + capture_info cinfo (s); + expr *e; + if (!gimple + && s->result + && !((e = dyn_cast (s->result)) + && is_a (e->operation))) + { + for (unsigned i = 0; i < as_a (s->match)->ops.length (); ++i) + if (cinfo.force_no_side_effects & (1 << i)) + fprintf (f, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i); + for (int i = 0; i <= s->capture_max; ++i) + if (cinfo.info[i].cse_p) + ; + else if (cinfo.info[i].force_no_side_effects_p + && (cinfo.info[i].toplevel_msk + & cinfo.force_no_side_effects) == 0) + fprintf (f, "if (TREE_SIDE_EFFECTS (captures[%d])) " + "return NULL_TREE;\n", i); + else if ((cinfo.info[i].toplevel_msk + & cinfo.force_no_side_effects) != 0) + /* Mark capture as having no side-effects if we had to verify + that via forced toplevel operand checks. */ + cinfo.info[i].force_no_side_effects_p = true; + } + fprintf (f, "if (dump_file && (dump_flags & TDF_DETAILS)) " "fprintf (dump_file, \"Applying pattern "); output_line_directive (f, s->result_location, true); @@ -1983,10 +2170,22 @@ dt_simplify::gen (FILE *f, bool gimple) } else /* GENERIC */ { + bool is_predicate = false; if (result->type == operand::OP_EXPR) { expr *e = as_a (result); - bool is_predicate = is_a (e->operation); + is_predicate = is_a (e->operation); + /* Search for captures used multiple times in the result expression + and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */ + if (!is_predicate) + for (int i = 0; i < s->capture_max + 1; ++i) + { + if (!cinfo.info[i].force_no_side_effects_p + && cinfo.info[i].result_use_count > 1) + fprintf (f, " if (TREE_SIDE_EFFECTS (captures[%d]))\n" + " captures[%d] = save_expr (captures[%d]);\n", + i, i, i); + } for (unsigned j = 0; j < e->ops.length (); ++j) { char dest[32]; @@ -2004,22 +2203,23 @@ dt_simplify::gen (FILE *f, bool gimple) ? NULL : "TREE_TYPE (res_op0)"); e->ops[j]->gen_transform (f, dest, false, 1, optype, indexes); } - if (is_a (e->operation)) + if (is_predicate) fprintf (f, "return true;\n"); else { + fprintf (f, " tree res;\n"); /* Re-fold the toplevel result. Use non_lvalue to build NON_LVALUE_EXPRs so they get properly ignored when in GIMPLE form. */ if (*e->operation == NON_LVALUE_EXPR) - fprintf (f, " return non_lvalue_loc (loc, res_op0);\n"); + fprintf (f, " res = non_lvalue_loc (loc, res_op0);\n"); else { if (e->operation->kind == id_base::CODE) - fprintf (f, " return fold_build%d_loc (loc, %s, type", + fprintf (f, " res = fold_build%d_loc (loc, %s, type", e->ops.length (), e->operation->id); else - fprintf (f, " return build_call_expr_loc " + fprintf (f, " res = build_call_expr_loc " "(loc, builtin_decl_implicit (%s), %d", e->operation->id, e->ops.length()); for (unsigned j = 0; j < e->ops.length (); ++j) @@ -2030,13 +2230,29 @@ dt_simplify::gen (FILE *f, bool gimple) } else if (result->type == operand::OP_CAPTURE || result->type == operand::OP_C_EXPR) + { fprintf (f, " tree res;\n"); s->result->gen_transform (f, " res", false, 1, "type", indexes); - fprintf (f, " return res;\n"); } else gcc_unreachable (); + if (!is_predicate) + { + /* Search for captures not used in the result expression and dependent + on TREE_SIDE_EFFECTS emit omit_one_operand. */ + for (int i = 0; i < s->capture_max + 1; ++i) + { + if (!cinfo.info[i].force_no_side_effects_p + && !cinfo.info[i].expr_p + && cinfo.info[i].result_use_count == 0) + fprintf (f, " if (TREE_SIDE_EFFECTS (captures[%d]))\n" + " res = build2_loc (loc, COMPOUND_EXPR, type," + " fold_ignored_result (captures[%d]), res);\n", + i, i); + } + fprintf (f, " return res;\n"); + } } for (unsigned i = 0; i < n_braces; ++i) @@ -2107,18 +2323,6 @@ decision_tree::gen_generic (FILE *f) fprintf (f, ")\n"); fprintf (f, "{\n"); - /* ??? For now reject all simplifications on operands with - side-effects as we are not prepared to properly wrap - omitted parts with omit_one_operand and friends. In - principle we can do that automagically for a subset of - transforms (and only reject the remaining cases). - This fixes for example gcc.c-torture/execute/20050131-1.c. */ - fprintf (f, "if ((op0 && TREE_SIDE_EFFECTS (op0))"); - for (unsigned i = 1; i < n; ++i) - fprintf (f, "|| (op%d && TREE_SIDE_EFFECTS (op%d))", i, i); - fprintf (f, ")\n" - " return NULL_TREE;\n"); - fprintf (f, "switch (code)\n" "{\n"); for (unsigned i = 0; i < root->kids.length (); i++)