re PR target/77826 (ICE in decompose, at wide-int.h:928 w/ -m64 -O2 and above)

2016-10-13  Richard Biener  <rguenther@suse.de>

	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 @@<id>.
	(parser::parse_capture): Parse @@<id> 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.

From-SVN: r241108

1 files changed, 125 insertions, 25 deletions

diff --git a/gcc/genmatch.c b/gcc/genmatch.c
index de03d34..fc4f598 100644
--- a/gcc/genmatch.c
+++ b/gcc/genmatch.c
@@ -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<vec<user_id *> > &for_vec)
       vec<operand *> 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_code oper,
     {
       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_base *with)
       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<expr *> (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_node *n2)
     return cmp_operand ((as_a<dt_operand *> (n1))->op,
 			(as_a<dt_operand *> (n2))->op);
   else if (n1->type == dt_node::DT_MATCH)
-    return ((as_a<dt_operand *> (n1))->match_dop
-	    == (as_a<dt_operand *> (n2))->match_dop);
+    return (((as_a<dt_operand *> (n1))->match_dop
+	     == (as_a<dt_operand *> (n2))->match_dop)
+	    && ((as_a<dt_operand *> (n1))->value_match
+		== (as_a<dt_operand *> (n2))->value_match));
   return false;
 }
 
@@ -1841,6 +1853,7 @@ decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
 	      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 <dt_operand *>(p)->value_match = c->value_match;
 	  if (c->what)
 	    return insert_operand (p, c->what, indexes, 0, p);
 	  else
@@ -2591,18 +2605,18 @@ dt_operand::gen_predicate (FILE *f, int indent, const char *opname, bool gimple)
    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 +3745,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 +3766,8 @@ private:
   void parse_predicates (source_location);
   void parse_operator_list (source_location);
 
+  void finish_match_operand (operand *);
+
   cpp_reader *r;
   vec<c_expr *> active_ifs;
   vec<vec<user_id *> > active_fors;
@@ -3886,6 +3904,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 +4000,16 @@ parser::parse_capture (operand *op, bool require_existing)
   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 +4025,7 @@ parser::parse_capture (operand *op, bool require_existing)
 	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 +4105,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 +4420,7 @@ parser::parse_simplify (simplify::simplify_kind kind,
   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 +4761,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<vec<capture *> > cpts)
+{
+  if (! op)
+    return;
+
+  if (capture *c = dyn_cast <capture *> (op))
+    {
+      cpts[c->where].safe_push (c);
+      walk_captures (c->what, cpts);
+    }
+  else if (expr *e = dyn_cast <expr *> (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<vec<capture *> > 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 @__<newid>@1 and @1 into @__<newid>.  */
+	  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_)