[PATCH][match-and-simplify] 2nd try handling TREE_SIDE_EFFECTS

[Richard Biener <rguenther at suse dot de>]

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  <rguenther@suse.de>

	* 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<cinfo> 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 <expr *> (s->result))
+	  && is_a <predicate_id *> (e->operation)))
+    {
+      force_no_side_effects = -1;
+      return;
+    }
+
+  info.safe_grow_cleared (s->capture_max + 1);
+  e = as_a <expr *> (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 <c_expr *>(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 <capture *> (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 <expr *> (c->what))
+	{
+	  info[c->where].expr_p = true;
+	  walk_match (c->what, toplevel_arg, conditional_p);
+	}
+    }
+  else if (expr *e = dyn_cast <expr *> (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 <predicate *> (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 <capture *> (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 <expr *> (c->what))
+	{
+	  info[c->where].cse_p = true;
+	  walk_result (c->what, true);
+	}
+    }
+  else if (expr *e = dyn_cast <expr *> (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 <c_expr *> (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 <expr *> (s->result))
+	   && is_a <predicate_id *> (e->operation)))
+    {
+      for (unsigned i = 0; i < as_a <expr *> (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 <expr *> (result);
-	  bool is_predicate = is_a <predicate_id *> (e->operation);
+	  is_predicate = is_a <predicate_id *> (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 <predicate_id *> (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++)