genmatch.c (struct sinfo, [...]): New hash-map to record equivalent transforms.

2015-08-03  Richard Biener  <rguenther@suse.de>

	* genmatch.c (struct sinfo, struct sinfo_hashmap_traits, sinfo_map_t):
	New hash-map to record equivalent transforms.
	(dt_node::analyze): Populate the equivalent transforms hash-map.
	(dt_simplify::info): Add reference to hash-map entry.
	(dt_simplify::gen): If we have split out a function for the
	transform, generate a call to it.
	(sinfo_hashmap_traits::hash): New function.
	(compare_op): New helper function for ...
	(sinfo_hashmap_traits::equal_keys): ... this new function.
	(decision_tree::gen): Split out common equivalent transforms
	into functions.

From-SVN: r226490

2 files changed, 222 insertions, 6 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 7e64648..3a3012a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,19 @@
 2015-08-03  Richard Biener  <rguenther@suse.de>
 
+	* genmatch.c (struct sinfo, struct sinfo_hashmap_traits, sinfo_map_t):
+	New hash-map to record equivalent transforms.
+	(dt_node::analyze): Populate the equivalent transforms hash-map.
+	(dt_simplify::info): Add reference to hash-map entry.
+	(dt_simplify::gen): If we have split out a function for the
+	transform, generate a call to it.
+	(sinfo_hashmap_traits::hash): New function.
+	(compare_op): New helper function for ...
+	(sinfo_hashmap_traits::equal_keys): ... this new function.
+	(decision_tree::gen): Split out common equivalent transforms
+	into functions.
+
+2015-08-03  Richard Biener  <rguenther@suse.de>
+
 	* gimple-fold.c (fold_gimple_assign): Remove folding of
 	the comparison in COND_EXPRs.
 
diff --git a/gcc/genmatch.c b/gcc/genmatch.c
index 0579449..a1bc410 100644
--- a/gcc/genmatch.c
+++ b/gcc/genmatch.c
@@ -1220,6 +1220,29 @@ lower (vec<simplify *>& simplifiers, bool gimple)
    matching code.  It represents the 'match' expression of all
    simplifies and has those as its leafs.  */
 
+struct dt_simplify;
+
+/* A hash-map collecting semantically equivalent leafs in the decision
+   tree for splitting out to separate functions.  */
+struct sinfo
+{
+  dt_simplify *s;
+
+  const char *fname;
+  unsigned cnt;
+};
+
+struct sinfo_hashmap_traits : simple_hashmap_traits <pointer_hash <dt_simplify> >
+{
+  static inline hashval_t hash (const key_type &);
+  static inline bool equal_keys (const key_type &, const key_type &);
+  template <typename T> static inline void remove (T &) {}
+};
+
+typedef hash_map<void * /* unused */, sinfo *, sinfo_hashmap_traits>
+  sinfo_map_t;
+
+
 /* Decision tree base class, used for DT_TRUE and DT_NODE.  */
 
 struct dt_node
@@ -1250,7 +1273,7 @@ struct dt_node
 		   vec<dt_operand *>, vec<dt_operand *>, vec<dt_operand *>,
 		   vec<dt_operand *>, vec<dt_operand *>, vec<dt_node *>);
 
-  void analyze ();
+  void analyze (sinfo_map_t &);
 };
 
 /* Generic decision tree node used for DT_OPERAND and DT_MATCH.  */
@@ -1285,10 +1308,11 @@ struct dt_simplify : public dt_node
   simplify *s;
   unsigned pattern_no;
   dt_operand **indexes;
+  sinfo *info;
 
   dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
 	: dt_node (DT_SIMPLIFY), s (s_), pattern_no (pattern_no_),
-	  indexes (indexes_)  {}
+	  indexes (indexes_), info (NULL)  {}
 
   void gen_1 (FILE *, int, bool, operand *);
   void gen (FILE *f, int, bool);
@@ -1303,6 +1327,16 @@ is_a_helper <dt_operand *>::test (dt_node *n)
 	  || n->type == dt_node::DT_MATCH);
 }
 
+template<>
+template<>
+inline bool
+is_a_helper <dt_simplify *>::test (dt_node *n)
+{
+  return n->type == dt_node::DT_SIMPLIFY;
+}
+
+
+
 /* A container for the actual decision tree.  */
 
 struct decision_tree
@@ -1455,7 +1489,7 @@ dt_node::append_simplify (simplify *s, unsigned pattern_no,
 /* Analyze the node and its children.  */
 
 void
-dt_node::analyze ()
+dt_node::analyze (sinfo_map_t &map)
 {
   num_leafs = 0;
   total_size = 1;
@@ -1463,13 +1497,27 @@ dt_node::analyze ()
 
   if (type == DT_SIMPLIFY)
     {
+      /* Populate the map of equivalent simplifies.  */
+      dt_simplify *s = as_a <dt_simplify *> (this);
+      bool existed;
+      sinfo *&si = map.get_or_insert (s, &existed);
+      if (!existed)
+	{
+	  si = new sinfo;
+	  si->s = s;
+	  si->cnt = 1;
+	  si->fname = NULL;
+	}
+      else
+	si->cnt++;
+      s->info = si;
       num_leafs = 1;
       return;
     }
 
   for (unsigned i = 0; i < kids.length (); ++i)
     {
-      kids[i]->analyze ();
+      kids[i]->analyze (map);
       num_leafs += kids[i]->num_leafs;
       total_size += kids[i]->total_size;
       max_level = MAX (max_level, kids[i]->max_level);
@@ -2986,25 +3034,179 @@ dt_simplify::gen (FILE *f, int indent, bool gimple)
 			i, indexes[i]->get_name (opname));
       }
 
-  gen_1 (f, indent, gimple, s->result);
+  /* If we have a split-out function for the actual transform, call it.  */
+  if (info && info->fname)
+    {
+      if (gimple)
+	{
+	  fprintf_indent (f, indent, "if (%s (res_code, res_ops, seq, "
+			  "valueize, type, captures))\n", info->fname);
+	  fprintf_indent (f, indent, "  return true;\n");
+	}
+      else
+	{
+	  fprintf_indent (f, indent, "tree res = %s (loc, type",
+			  info->fname);
+	  for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
+	    fprintf (f, ", op%d", i);
+	  fprintf (f, ", captures);\n");
+	  fprintf_indent (f, indent, "if (res) return res;\n");
+	}
+    }
+  else
+    gen_1 (f, indent, gimple, s->result);
 
   indent -= 2;
   fprintf_indent (f, indent, "}\n");
 }
 
+
+/* Hash function for finding equivalent transforms.  */
+
+hashval_t
+sinfo_hashmap_traits::hash (const key_type &v)
+{
+  /* Only bother to compare those originating from the same source pattern.  */
+  return v->s->result->location;
+}
+
+/* Compare function for finding equivalent transforms.  */
+
+static bool
+compare_op (operand *o1, simplify *s1, operand *o2, simplify *s2)
+{
+  if (o1->type != o2->type)
+    return false;
+
+  switch (o1->type)
+    {
+    case operand::OP_IF:
+      {
+	if_expr *if1 = as_a <if_expr *> (o1);
+	if_expr *if2 = as_a <if_expr *> (o2);
+	/* ???  Properly compare c-exprs.  */
+	if (if1->cond != if2->cond)
+	  return false;
+	if (!compare_op (if1->trueexpr, s1, if2->trueexpr, s2))
+	  return false;
+	if (if1->falseexpr != if2->falseexpr
+	    || (if1->falseexpr
+		&& !compare_op (if1->falseexpr, s1, if2->falseexpr, s2)))
+	  return false;
+	return true;
+      }
+    case operand::OP_WITH:
+      {
+	with_expr *with1 = as_a <with_expr *> (o1);
+	with_expr *with2 = as_a <with_expr *> (o2);
+	if (with1->with != with2->with)
+	  return false;
+	return compare_op (with1->subexpr, s1, with2->subexpr, s2);
+      }
+    default:;
+    }
+
+  /* We've hit a result.  Time to compare capture-infos - this is required
+     in addition to the conservative pointer-equivalency of the result IL.  */
+  capture_info cinfo1 (s1, o1, true);
+  capture_info cinfo2 (s2, o2, true);
+
+  if (cinfo1.force_no_side_effects != cinfo2.force_no_side_effects
+      || cinfo1.info.length () != cinfo2.info.length ())
+    return false;
+
+  for (unsigned i = 0; i < cinfo1.info.length (); ++i)
+    {
+      if (cinfo1.info[i].expr_p != cinfo2.info[i].expr_p
+	  || cinfo1.info[i].cse_p != cinfo2.info[i].cse_p
+	  || (cinfo1.info[i].force_no_side_effects_p
+	      != cinfo2.info[i].force_no_side_effects_p)
+	  || cinfo1.info[i].force_single_use != cinfo2.info[i].force_single_use
+	  || cinfo1.info[i].cond_expr_cond_p != cinfo2.info[i].cond_expr_cond_p
+	  /* toplevel_msk is an optimization */
+	  || cinfo1.info[i].result_use_count != cinfo2.info[i].result_use_count
+	  || cinfo1.info[i].same_as != cinfo2.info[i].same_as
+	  /* the pointer back to the capture is for diagnostics only */)
+	return false;
+    }
+
+  /* ???  Deep-compare the actual result.  */
+  return o1 == o2;
+}
+
+bool
+sinfo_hashmap_traits::equal_keys (const key_type &v,
+				  const key_type &candidate)
+{
+  return compare_op (v->s->result, v->s, candidate->s->result, candidate->s);
+}
+
+
 /* Main entry to generate code for matching GIMPLE IL off the decision
    tree.  */
 
 void
 decision_tree::gen (FILE *f, bool gimple)
 {
-  root->analyze ();
+  sinfo_map_t si;
+
+  root->analyze (si);
 
   fprintf (stderr, "%s decision tree has %u leafs, maximum depth %u and "
 	   "a total number of %u nodes\n",
 	   gimple ? "GIMPLE" : "GENERIC", 
 	   root->num_leafs, root->max_level, root->total_size);
 
+  /* First split out the transform part of equal leafs.  */
+  unsigned rcnt = 0;
+  unsigned fcnt = 1;
+  for (sinfo_map_t::iterator iter = si.begin ();
+       iter != si.end (); ++iter)
+    {
+      sinfo *s = (*iter).second;
+      /* Do not split out single uses.  */
+      if (s->cnt <= 1)
+	continue;
+
+      rcnt += s->cnt - 1;
+      if (verbose >= 1)
+	{
+	  fprintf (stderr, "found %u uses of", s->cnt);
+	  output_line_directive (stderr, s->s->s->result->location);
+	}
+
+      /* Generate a split out function with the leaf transform code.  */
+      s->fname = xasprintf ("%s_simplify_%u", gimple ? "gimple" : "generic",
+			    fcnt++);
+      if (gimple)
+	fprintf (f, "\nstatic bool\n"
+		 "%s (code_helper *res_code, tree *res_ops,\n"
+		 "                 gimple_seq *seq, tree (*valueize)(tree) "
+		 "ATTRIBUTE_UNUSED,\n"
+		 "                 tree ARG_UNUSED (type), tree *ARG_UNUSED "
+		 "(captures))\n",
+		 s->fname);
+      else
+	{
+	  fprintf (f, "\nstatic tree\n"
+		   "%s (location_t ARG_UNUSED (loc), tree ARG_UNUSED (type),\n",
+		   (*iter).second->fname);
+	  for (unsigned i = 0;
+	       i < as_a <expr *>(s->s->s->match)->ops.length (); ++i)
+	    fprintf (f, " tree ARG_UNUSED (op%d),", i);
+	  fprintf (f, " tree *captures)\n");
+	}
+
+      fprintf (f, "{\n");
+      s->s->gen_1 (f, 2, gimple, s->s->s->result);
+      if (gimple)
+	fprintf (f, "  return false;\n");
+      else
+	fprintf (f, "  return NULL_TREE;\n");
+      fprintf (f, "}\n");
+    }
+  fprintf (stderr, "removed %u duplicate tails\n", rcnt);
+
   for (unsigned n = 1; n <= 3; ++n)
     {
       /* First generate split-out functions.  */