diff mbox

match.pd and pattern ordering

Message ID alpine.LSU.2.20.1707281356090.10808@zhemvz.fhfr.qr
State New
Headers show

Commit Message

Richard Biener July 28, 2017, 12:10 p.m. UTC 
So I did an item from my TODO list, implemented a warning whenever
pattern ordering in match.pd prevents genmatch.c from merging nodes
in the decision tree (to avoid that it matches a pattern following
another that would eventually also match).

I noticed we're doing this a bit too conservatively, like for
the pattern itself (its variants generated from for, etc.) as well
as for patterns that preceede the one we are going to merge with.

So with the patch I added enough infrastructure to give sensible
warnings (initialize ->op for DT_TRUE, add a pattern UID).  I also
managed to sneak in some more cleanups.

This results in a few less nodes and a code size reduction, also
it indentifies one case of duplicate patterns (superfluous :c, fixed
with the patch).  An example of the warning is (you need to add -v
to genmatch):

/tmp/trunk/gcc/match.pd:677:12 warning: failed to merge decision tree node
 (bit_and (bit_not SSA_NAME@0) INTEGER_CST@1)
           ^
/tmp/trunk/gcc/match.pd:624:38 warning: with the following
 (bit_and:c (convert? @0) (convert? (bit_not @0)))
                                     ^
/tmp/trunk/gcc/match.pd:629:14 warning: because of the following which 
serves as ordering barrier
  (bit_and:c @0 (plus:s (lshift:s integer_onep @1) integer_minus_onep))
             ^

this case is because we have to try matching 629 first which matches more
genereally than 677.  The fact that the rest of the pattern wouldn't match
anyway isn't accounted for (so it's still too conservative).

A fix would be to move the pattern from 629 to before 624.

Improvement is (including the match.pd fix in both cases) from

GIMPLE decision tree has 2034 leafs, maximum depth 12 and a total number 
of 8257 nodes
removed 1196 duplicate tails

to

GIMPLE decision tree has 2066 leafs, maximum depth 12 and a total number 
of 8345 nodes
removed 1224 duplicate tails

There are 56 unique cases left where merging doesn't happen, down from 81.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Richard.

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.
diff mbox

Patch

Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 250649)
+++ gcc/match.pd	(working copy)
@@ -900,7 +900,7 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
    (X | Y) | (X | Z) -> (X | Y) | Z  */
 (for op (bit_and bit_ior)
  (simplify
-  (op:c (convert1?@3 (op:c@4 @0 @1)) (convert2?@5 (op:c@6 @0 @2)))
+  (op (convert1?@3 (op:c@4 @0 @1)) (convert2?@5 (op:c@6 @0 @2)))
   (if (tree_nop_conversion_p (type, TREE_TYPE (@1))
        && tree_nop_conversion_p (type, TREE_TYPE (@2)))
    (if (single_use (@5) && single_use (@6))
@@ -4178,3 +4178,25 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	 { CONSTRUCTOR_ELT (ctor, idx / k)->value; })
 	(BIT_FIELD_REF { CONSTRUCTOR_ELT (ctor, idx / k)->value; }
 		       @1 { bitsize_int ((idx % k) * width); })))))))))
+
+/* Simplify a bit extraction from a bit insertion for the cases with
+   the inserted element fully covering the extraction or the insertion
+   not touching the extraction.  */
+(simplify
+ (BIT_FIELD_REF (bit_insert @0 @1 @ipos) @rsize @rpos)
+ (with
+  {
+    unsigned HOST_WIDE_INT isize;
+    if (INTEGRAL_TYPE_P (TREE_TYPE (@1)))
+      isize = TYPE_PRECISION (TREE_TYPE (@1));
+    else
+      isize = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (@1)));
+  }
+  (switch
+   (if (wi::leu_p (@ipos, @rpos)
+        && wi::leu_p (wi::add (@rpos, @rsize), wi::add (@ipos, isize)))
+    (BIT_FIELD_REF @1 @rsize { wide_int_to_tree (bitsizetype,
+                                                 wi::sub (@rpos, @ipos)); }))
+   (if (wi::geu_p (@ipos, wi::add (@rpos, @rsize))
+        || wi::geu_p (@rpos, wi::add (@ipos, isize)))
+    (BIT_FIELD_REF @0 @rsize @rpos)))))
Index: gcc/genmatch.c
===================================================================
--- gcc/genmatch.c	(revision 250649)
+++ gcc/genmatch.c	(working copy)
@@ -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<simp
   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<simp
   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 *>
   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 *
 	      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_has
 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.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
 /* 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 *
 	    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 *
 	      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, F
 	    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 ind
 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::simplif
     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)