match.pd: Remove superfluous :c.

2017-07-28  Richard Biener  <rguenther@suse.de>

	* match.pd: Remove superfluous :c.
	* genmatch.c (simplify::id): Add member.
	(lower_commutative, lower_opt_convert, lower_cond, lower_for):
	Copy id.
	(current_id): New global.
	(dt_node::parent): Move from ...
	(dt_operand::parent): ... here.  Add for_id member.
	(is_a_helper <dt_operand *>::test): DT_TRUE is also a dt_operand.
	(decision_tree::find_node): Relax order requirement when
	merging DT_TRUE nodes to ones inbetween the current simplify
	and the one we try to merge with.  Add diagnostic whenever
	we need to enforce pattern order by not merging.
	(decision_tree::insert): Set current_id.
	(decision_tree::print_node): Dump parent node and for_id.
	(parser::last_id): Add member.
	(parser::push_simplify): Assign unique id.
	(parser::parser): Initialize last_id.

From-SVN: r250664

1 files changed, 87 insertions, 36 deletions

diff --git a/gcc/genmatch.c b/gcc/genmatch.c
index 6564a1a..9da911a 100644
--- a/gcc/genmatch.c
+++ b/gcc/genmatch.c
@@ -793,13 +793,17 @@ struct simplify
 {
   enum simplify_kind { SIMPLIFY, MATCH };
 
-  simplify (simplify_kind kind_, operand *match_, operand *result_,
-	    vec<vec<user_id *> > for_vec_, cid_map_t *capture_ids_)
-      : kind (kind_), match (match_), result (result_),
+  simplify (simplify_kind kind_, unsigned id_, operand *match_,
+	    operand *result_, vec<vec<user_id *> > for_vec_,
+	    cid_map_t *capture_ids_)
+      : kind (kind_), id (id_), match (match_), result (result_),
       for_vec (for_vec_), for_subst_vec (vNULL),
       capture_ids (capture_ids_), capture_max (capture_ids_->elements () - 1) {}
 
   simplify_kind kind;
+  /* ID.  This is kept to easily associate related simplifies expanded
+     from the same original one.  */
+  unsigned id;
   /* The expression that is matched against the GENERIC or GIMPLE IL.  */
   operand *match;
   /* For a (simplify ...) an expression with ifs and withs with the expression
@@ -1008,7 +1012,7 @@ lower_commutative (simplify *s, vec<simplify *>& simplifiers)
   vec<operand *> matchers = commutate (s->match, s->for_vec);
   for (unsigned i = 0; i < matchers.length (); ++i)
     {
-      simplify *ns = new simplify (s->kind, matchers[i], s->result,
+      simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
 				   s->for_vec, s->capture_ids);
       simplifiers.safe_push (ns);
     }
@@ -1137,7 +1141,7 @@ lower_opt_convert (simplify *s, vec<simplify *>& simplifiers)
   vec<operand *> matchers = lower_opt_convert (s->match);
   for (unsigned i = 0; i < matchers.length (); ++i)
     {
-      simplify *ns = new simplify (s->kind, matchers[i], s->result,
+      simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
 				   s->for_vec, s->capture_ids);
       simplifiers.safe_push (ns);
     }
@@ -1238,7 +1242,7 @@ lower_cond (simplify *s, vec<simplify *>& simplifiers)
   vec<operand *> matchers = lower_cond (s->match);
   for (unsigned i = 0; i < matchers.length (); ++i)
     {
-      simplify *ns = new simplify (s->kind, matchers[i], s->result,
+      simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
 				   s->for_vec, s->capture_ids);
       simplifiers.safe_push (ns);
     }
@@ -1453,7 +1457,7 @@ lower_for (simplify *sin, vec<simplify *>& simplifiers)
 	      if (skip)
 		continue;
 
-	      simplify *ns = new simplify (s->kind, match_op, result_op,
+	      simplify *ns = new simplify (s->kind, s->id, match_op, result_op,
 					   vNULL, s->capture_ids);
 	      ns->for_subst_vec.safe_splice (s->for_subst_vec);
 	      if (result_op
@@ -1527,8 +1531,11 @@ struct sinfo_hashmap_traits : simple_hashmap_traits<pointer_hash<dt_simplify>,
 typedef hash_map<void * /* unused */, sinfo *, sinfo_hashmap_traits>
   sinfo_map_t;
 
+/* Current simplifier ID we are processing during insertion into the
+   decision tree.  */
+static unsigned current_id;
 
-/* Decision tree base class, used for DT_TRUE and DT_NODE.  */
+/* Decision tree base class, used for DT_NODE.  */
 
 struct dt_node
 {
@@ -1536,6 +1543,7 @@ struct dt_node
 
   enum dt_type type;
   unsigned level;
+  dt_node *parent;
   vec<dt_node *> kids;
 
   /* Statistics.  */
@@ -1543,12 +1551,14 @@ struct dt_node
   unsigned total_size;
   unsigned max_level;
 
-  dt_node (enum dt_type type_): type (type_), level (0), kids (vNULL) {}
+  dt_node (enum dt_type type_, dt_node *parent_)
+    : type (type_), level (0), parent (parent_), kids (vNULL) {}
 
   dt_node *append_node (dt_node *);
-  dt_node *append_op (operand *, dt_node *parent = 0, unsigned pos = 0);
-  dt_node *append_true_op (dt_node *parent = 0, unsigned pos = 0);
-  dt_node *append_match_op (dt_operand *, dt_node *parent = 0, unsigned pos = 0);
+  dt_node *append_op (operand *, dt_node *parent, unsigned pos);
+  dt_node *append_true_op (operand *, dt_node *parent, unsigned pos);
+  dt_node *append_match_op (operand *, dt_operand *, dt_node *parent,
+			    unsigned pos);
   dt_node *append_simplify (simplify *, unsigned, dt_operand **);
 
   virtual void gen (FILE *, int, bool) {}
@@ -1561,20 +1571,20 @@ struct dt_node
   void analyze (sinfo_map_t &);
 };
 
-/* Generic decision tree node used for DT_OPERAND and DT_MATCH.  */
+/* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE.  */
 
 struct dt_operand : public dt_node
 {
   operand *op;
   dt_operand *match_dop;
-  dt_operand *parent;
   unsigned pos;
   bool value_match;
+  unsigned for_id;
 
   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_), value_match (false) {}
+	      dt_operand *parent_, unsigned pos_)
+      : dt_node (type, parent_), op (op_), match_dop (match_dop_),
+      pos (pos_), value_match (false), for_id (current_id) {}
 
   void gen (FILE *, int, bool);
   unsigned gen_predicate (FILE *, int, const char *, bool);
@@ -1597,7 +1607,7 @@ struct dt_simplify : public dt_node
   sinfo *info;
 
   dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
-	: dt_node (DT_SIMPLIFY), s (s_), pattern_no (pattern_no_),
+	: dt_node (DT_SIMPLIFY, NULL), s (s_), pattern_no (pattern_no_),
 	  indexes (indexes_), info (NULL)  {}
 
   void gen_1 (FILE *, int, bool, operand *);
@@ -1610,7 +1620,8 @@ inline bool
 is_a_helper <dt_operand *>::test (dt_node *n)
 {
   return (n->type == dt_node::DT_OPERAND
-	  || n->type == dt_node::DT_MATCH);
+	  || n->type == dt_node::DT_MATCH
+	  || n->type == dt_node::DT_TRUE);
 }
 
 template<>
@@ -1633,7 +1644,7 @@ struct decision_tree
   void gen (FILE *f, bool gimple);
   void print (FILE *f = stderr);
 
-  decision_tree () { root = new dt_node (dt_node::DT_NODE); }
+  decision_tree () { root = new dt_node (dt_node::DT_NODE, NULL); }
 
   static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes,
 				  unsigned pos = 0, dt_node *parent = 0);
@@ -1703,15 +1714,48 @@ decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
       && !ops.is_empty ()
       && ops.last ()->type == dt_node::DT_TRUE)
     return ops.last ();
+  dt_operand *true_node = NULL;
   for (int i = ops.length () - 1; i >= 0; --i)
     {
       /* But we can't merge across DT_TRUE nodes as they serve as
          pattern order barriers to make sure that patterns apply
 	 in order of appearance in case multiple matches are possible.  */
       if (ops[i]->type == dt_node::DT_TRUE)
-	return NULL;
+	{
+	  if (! true_node
+	      || as_a <dt_operand *> (ops[i])->for_id > true_node->for_id)
+	    true_node = as_a <dt_operand *> (ops[i]);
+	}
       if (decision_tree::cmp_node (ops[i], p))
-	return ops[i];
+	{
+	  /* Unless we are processing the same pattern or the blocking
+	     pattern is before the one we are going to merge with.  */
+	  if (true_node
+	      && true_node->for_id != current_id
+	      && true_node->for_id > as_a <dt_operand *> (ops[i])->for_id)
+	    {
+	      if (verbose >= 1)
+		{
+		  source_location p_loc = 0;
+		  if (p->type == dt_node::DT_OPERAND)
+		    p_loc = as_a <dt_operand *> (p)->op->location;
+		  source_location op_loc = 0;
+		  if (ops[i]->type == dt_node::DT_OPERAND)
+		    op_loc = as_a <dt_operand *> (ops[i])->op->location;
+		  source_location true_loc = 0;
+		  true_loc = true_node->op->location;
+		  warning_at (p_loc,
+			      "failed to merge decision tree node");
+		  warning_at (op_loc,
+			      "with the following");
+		  warning_at (true_loc,
+			      "because of the following which serves as ordering "
+			      "barrier");
+		}
+	      return NULL;
+	    }
+	  return ops[i];
+	}
     }
   return NULL;
 }
@@ -1747,20 +1791,21 @@ dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
 /* Append a DT_TRUE decision tree node.  */
 
 dt_node *
-dt_node::append_true_op (dt_node *parent, unsigned pos)
+dt_node::append_true_op (operand *op, dt_node *parent, unsigned pos)
 {
   dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
-  dt_operand *n = new dt_operand (DT_TRUE, 0, 0, parent_, pos);
+  dt_operand *n = new dt_operand (DT_TRUE, op, 0, parent_, pos);
   return append_node (n);
 }
 
 /* Append a DT_MATCH decision tree node.  */
 
 dt_node *
-dt_node::append_match_op (dt_operand *match_dop, dt_node *parent, unsigned pos)
+dt_node::append_match_op (operand *op, dt_operand *match_dop,
+			  dt_node *parent, unsigned pos)
 {
   dt_operand *parent_ = as_a<dt_operand *> (parent);
-  dt_operand *n = new dt_operand (DT_MATCH, 0, match_dop, parent_, pos);
+  dt_operand *n = new dt_operand (DT_MATCH, op, match_dop, parent_, pos);
   return append_node (n);
 }
 
@@ -1839,7 +1884,7 @@ decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
 	    q = insert_operand (p, c->what, indexes, pos, parent);
 	  else
 	    {
-	      q = elm = p->append_true_op (parent, pos);
+	      q = elm = p->append_true_op (o, parent, pos);
 	      goto at_assert_elm;
 	    }
 	  // get to the last capture
@@ -1853,19 +1898,19 @@ decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
 	      unsigned cc_index = c->where;
 	      dt_operand *match_op = indexes[cc_index];
 
-	      dt_operand temp (dt_node::DT_TRUE, 0, 0);
+	      dt_operand temp (dt_node::DT_TRUE, 0, 0, 0, 0);
 	      elm = decision_tree::find_node (p->kids, &temp);
 
 	      if (elm == 0)
 		{
-		  dt_operand temp (dt_node::DT_MATCH, 0, match_op);
+		  dt_operand temp (dt_node::DT_MATCH, 0, match_op, 0, 0);
 		  temp.value_match = c->value_match;
 		  elm = decision_tree::find_node (p->kids, &temp);
 		}
 	    }
 	  else
 	    {
-	      dt_operand temp (dt_node::DT_OPERAND, c->what, 0);
+	      dt_operand temp (dt_node::DT_OPERAND, c->what, 0, 0, 0);
 	      elm = decision_tree::find_node (p->kids, &temp);
 	    }
 
@@ -1878,7 +1923,7 @@ at_assert_elm:
 	}
       else
 	{
-	  p = p->append_match_op (indexes[capt_index], parent, pos);
+	  p = p->append_match_op (o, 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);
@@ -1903,6 +1948,7 @@ at_assert_elm:
 void
 decision_tree::insert (struct simplify *s, unsigned pattern_no)
 {
+  current_id = s->id;
   dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1);
   dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
   p->append_simplify (s, pattern_no, indexes);
@@ -1938,9 +1984,12 @@ decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
 	    fprintf (f, "%p, ", (void *) s->indexes[i]);
 	  fprintf (f, " } ");
 	}
+      if (is_a <dt_operand *> (p))
+	fprintf (f, " [%u]", as_a <dt_operand *> (p)->for_id);
     }
 
-  fprintf (stderr, " (%p), %u, %u\n", (void *) p, p->level, p->kids.length ());
+  fprintf (stderr, " (%p, %p), %u, %u\n",
+	   (void *) p, (void *) p->parent, p->level, p->kids.length ());
 
   for (unsigned i = 0; i < p->kids.length (); ++i)
     decision_tree::print_node (p->kids[i], f, indent + 2);
@@ -2572,12 +2621,12 @@ capture::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
 char *
 dt_operand::get_name (char *name)
 {
-  if (!parent)
+  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);
+    return as_a <dt_operand *> (parent)->get_name (name);
   else
     sprintf (name, "o%u%u", parent->level, pos);
   return name;
@@ -2588,7 +2637,7 @@ dt_operand::get_name (char *name)
 void
 dt_operand::gen_opname (char *name, unsigned pos)
 {
-  if (!parent)
+  if (! parent)
     sprintf (name, "op%u", pos);
   else
     sprintf (name, "o%u%u", level, pos);
@@ -3819,6 +3868,7 @@ private:
   vec<user_id *> oper_lists;
 
   cid_map_t *capture_ids;
+  unsigned last_id;
 
 public:
   vec<simplify *> simplifiers;
@@ -4314,7 +4364,7 @@ parser::push_simplify (simplify::simplify_kind kind,
     active_fors.safe_push (oper_lists);
 
   simplifiers.safe_push
-    (new simplify (kind, match, result,
+    (new simplify (kind, last_id++, match, result,
 		   active_fors.copy (), capture_ids));
 
   if (!oper_lists.is_empty ())
@@ -4879,6 +4929,7 @@ parser::parser (cpp_reader *r_)
   capture_ids = NULL;
   user_predicates = vNULL;
   parsing_match_operand = false;
+  last_id = 0;
 
   const cpp_token *token = next ();
   while (token->type != CPP_EOF)