This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[GSoC] remove unnecessary temporaries


Hi,
   This patch attempts to generate temporaries only when required.

I have changed generation of operand names. All children of an expr-node
are assigned at expr-node itself.
Names are generated as follows at expr-node:
o<level><child-pos> = rhs;
where level is level of the expr-node in decision tree.
This is done by dt_operand::gen_opname.

Names are referred to as follows at child-node:
o<parent-level><pos>.
This is done by dt_operand::get_name.

To do this, I changed the type of indexes array in dt_simplify to
array of dt_operand *, so that each element points to the
decision-tree node, instead of storing it's level.

* genmatch.c (operand::gen_gimple_transform): Remove 2nd argument.
    (predicate::gen_gimple_transform): Likewise.
    (expr::gen_gimple_transform): Likewise.
    (c_expr::gen_gimple_transform): Likewise.
    (capture::gen_gimple_transform): Likewise.
    (dt_simplify::indexes): Change type to array of dt_operand *
    (dt_simplify::dt_simplify): change type of 3rd argument to dt_operand **
    (dt_simplify::gen_gimple): Remove 2nd argument in call to

.gen_gimple_transform()
    (dt_operand::get_name): New member function.
    (dt_operand::gen_opname): New member function.
    (dt_operand::match_dop): New member.
    (dt_operand::temps): Remove.
    (dt_operand::temp_count): Likewise.
    (dt_operand::m_level): Likewise.
    (dt_operand::dt_operand): Change type of 2nd argument to dt_operand *
    (dt_operand::gen_gimple): Call get_name for getting operand name.
    (dt_operand::gen_gimple_expr_fn): Replace call to sprintf,
       by get_name (opname).
    (dt_operand::gen_gimple_expr_expr): Likwise.
    (dt_operand::gen_generic_expr_expr): Likewise.
    (dt_operand::gen_generic_expr_fn): Likewise
    (decision_tree::insert_operand): Change type of 3rd argument to
dt_operand**.
    (dt_node::append_simplify): Likewise.

Thanks and Regards,
Prathamesh
Index: gcc/genmatch.c
===================================================================
--- gcc/genmatch.c	(revision 211920)
+++ gcc/genmatch.c	(working copy)
@@ -200,18 +200,20 @@ add_builtin (enum built_in_function code
 
 /* The predicate expression tree structure.  */
 
+struct dt_operand;
+
 struct operand {
   enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR };
   operand (enum op_type type_) : type (type_) {}
   enum op_type type;
-  virtual void gen_gimple_transform (FILE *f, const char *, const char *) = 0;
+  virtual void gen_gimple_transform (FILE *f, const char *) = 0;
 };
 
 struct predicate : public operand
 {
   predicate (const char *ident_) : operand (OP_PREDICATE), ident (ident_) {}
   const char *ident;
-  virtual void gen_gimple_transform (FILE *, const char *, const char *) { gcc_unreachable (); }
+  virtual void gen_gimple_transform (FILE *, const char *) { gcc_unreachable (); }
 };
 
 struct e_operation {
@@ -228,7 +230,7 @@ struct expr : public operand
   void append_op (operand *op) { ops.safe_push (op); }
   e_operation *operation;
   vec<operand *> ops;
-  virtual void gen_gimple_transform (FILE *f, const char *, const char *);
+  virtual void gen_gimple_transform (FILE *f, const char *);
 };
 
 struct c_expr : public operand
@@ -240,7 +242,7 @@ struct c_expr : public operand
   vec<cpp_token> code;
   unsigned nr_stmts;
   char *fname;
-  virtual void gen_gimple_transform (FILE *f, const char *, const char *);
+  virtual void gen_gimple_transform (FILE *f, const char *);
 };
 
 struct capture : public operand
@@ -249,7 +251,7 @@ struct capture : public operand
       : operand (OP_CAPTURE), where (where_), what (what_) {}
   const char *where;
   operand *what;
-  virtual void gen_gimple_transform (FILE *f, const char *, const char *);
+  virtual void gen_gimple_transform (FILE *f, const char *);
 };
 
 
@@ -305,6 +307,86 @@ struct simplify {
   source_location result_location;
 };
 
+struct dt_node
+{
+  enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
+
+  enum dt_type type;
+  unsigned level;
+  vec<dt_node *> kids;
+
+  dt_node (enum dt_type type_): type (type_), level (0), 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_simplify (simplify *, unsigned, dt_operand **); 
+
+  virtual void gen_gimple (FILE *) {}
+};
+
+struct dt_operand: public dt_node
+{
+  operand *op;
+  dt_operand *match_dop;
+  dt_operand *parent;
+  unsigned pos;
+ 
+  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_) {} 
+
+  virtual void gen_gimple (FILE *);
+  unsigned gen_gimple_predicate (FILE *, const char *);
+  unsigned gen_gimple_match_op (FILE *, const char *);
+
+  unsigned gen_gimple_expr (FILE *, const char *);
+  void gen_gimple_expr_expr (FILE *, expr *);
+  void gen_gimple_expr_fn (FILE *, expr *);
+
+  unsigned gen_generic_expr (FILE *, const char *);
+  void gen_generic_expr_expr (FILE *, expr *, const char *);
+  void gen_generic_expr_fn (FILE *, expr *, const char *);
+
+  char *get_name (char *);
+  void gen_opname (char *, unsigned);
+};
+
+
+struct dt_simplify: public dt_node
+{
+  static const unsigned level_max = UINT_MAX;
+  static const unsigned capture_max = 4;
+  simplify *s; 
+  unsigned pattern_no;
+  dt_operand *indexes[capture_max]; 
+  
+  dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
+	: dt_node (DT_SIMPLIFY), s (s_), pattern_no (pattern_no_)
+  {
+    for (unsigned i = 0; i < capture_max; ++i)
+      indexes[i] = indexes_[i];
+  }
+
+  virtual void gen_gimple (FILE *f);
+};
+
+struct decision_tree
+{
+  dt_node *root;
+  
+  void insert (struct simplify *, unsigned); 
+  void gen_gimple (FILE *f = stderr);
+  void print (FILE *f = stderr);
+
+  decision_tree () { root = new dt_node (dt_node::DT_NODE); }
+
+  static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes, unsigned pos = 0, dt_node *parent = 0);
+  static dt_node *find_node (vec<dt_node *>&, dt_node *);
+  static bool cmp_node (dt_node *, dt_node *);
+  static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
+};
+
 void
 print_operand (operand *o, FILE *f = stderr, bool flattened = false)
 {
@@ -453,15 +535,15 @@ commutate (operand *op)
 /* Code gen off the AST.  */
 
 void
-expr::gen_gimple_transform (FILE *f, const char *label, const char *dest)
+expr::gen_gimple_transform (FILE *f, const char *dest)
 {
   fprintf (f, "{\n");
-  fprintf (f, "  tree ops[%d], res;\n", ops.length ());
+  fprintf (f, "  tree ops[%u], res;\n", ops.length ());
   for (unsigned i = 0; i < ops.length (); ++i)
     {
       char dest[32];
       snprintf (dest, 32, "  ops[%u]", i);
-      ops[i]->gen_gimple_transform (f, label, dest);
+      ops[i]->gen_gimple_transform (f, dest);
     }
   /* ???  Have another helper that is like gimple_build but may
      fail if seq == NULL.  */
@@ -485,7 +567,7 @@ expr::gen_gimple_transform (FILE *f, con
 }
 
 void
-c_expr::gen_gimple_transform (FILE *f, const char *, const char *dest)
+c_expr::gen_gimple_transform (FILE *f, const char *dest)
 {
   /* If this expression has an outlined function variant, call it.  */
   if (fname)
@@ -532,13 +615,11 @@ c_expr::gen_gimple_transform (FILE *f, c
 }
 
 void
-capture::gen_gimple_transform (FILE *f, const char *, const char *dest)
+capture::gen_gimple_transform (FILE *f, const char *dest)
 {
-  fprintf (f, "%s = captures[%s];\n", dest, this->where);
+  fprintf (f, "%s = captures[%s];\n", dest, where); 
 }
 
-
-
 bool
 cmp_operand (operand *o1, operand *o2)
 {
@@ -561,85 +642,6 @@ cmp_operand (operand *o1, operand *o2)
     return false;
 }
 
-struct dt_node
-{
-  enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
-
-  enum dt_type type;
-  unsigned level;
-  vec<dt_node *> kids;
-
-  dt_node (enum dt_type type_): type (type_), level (0), 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 (unsigned, dt_node *parent = 0, unsigned pos = 0);
-  dt_node *append_simplify (simplify *, unsigned, unsigned *); 
-
-  virtual void gen_gimple (FILE *) {}
-};
-
-struct dt_operand: public dt_node
-{
-  operand *op;
-  unsigned m_level; // for match
-  dt_operand *parent;
-  unsigned pos;
-  vec<unsigned> temps;
-  static unsigned temp_count;
- 
-  dt_operand (enum dt_type type, operand *op_, unsigned m_level_, dt_operand *parent_ = 0, unsigned pos_ = 0)
-	: dt_node (type), op (op_), m_level (m_level_), parent (parent_), pos (pos_), temps (vNULL) {}
-
-  virtual void gen_gimple (FILE *);
-  unsigned gen_gimple_predicate (FILE *, const char *);
-  unsigned gen_gimple_match_op (FILE *, const char *);
-
-  unsigned gen_gimple_expr (FILE *, const char *);
-  void gen_gimple_expr_expr (FILE *, expr *);
-  void gen_gimple_expr_fn (FILE *, expr *);
-
-  unsigned gen_generic_expr (FILE *, const char *);
-  void gen_generic_expr_expr (FILE *, expr *, const char *);
-  void gen_generic_expr_fn (FILE *, expr *, const char *);
-};
-
-unsigned dt_operand::temp_count = 0;
-
-struct dt_simplify: public dt_node
-{
-  static const unsigned level_max = UINT_MAX;
-  static const unsigned capture_max = 4;
-  simplify *s; 
-  unsigned pattern_no;
-  unsigned indexes[capture_max]; 
-  
-  dt_simplify (simplify *s_, unsigned pattern_no_, unsigned *indexes_)
-	: dt_node (DT_SIMPLIFY), s (s_), pattern_no (pattern_no_)
-  {
-    for (unsigned i = 0; i < capture_max; ++i)
-      indexes[i] = indexes_[i];
-  }
-
-  virtual void gen_gimple (FILE *f);
-};
-
-struct decision_tree
-{
-  dt_node *root;
-  
-  void insert (struct simplify *, unsigned);
-  void gen_gimple (FILE *f = stderr);
-  void print (FILE *f = stderr);
-
-  decision_tree () { root = new dt_node (dt_node::DT_NODE); }
-
-  static dt_node *insert_operand (dt_node *, operand *, unsigned *indexes, unsigned pos = 0, dt_node *parent = 0);
-  static dt_node *find_node (vec<dt_node *>&, dt_node *);
-  static bool cmp_node (dt_node *, dt_node *);
-  static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
-};
 
 bool
 decision_tree::cmp_node (dt_node *n1, dt_node *n2)
@@ -654,7 +656,7 @@ decision_tree::cmp_node (dt_node *n1, dt
     return cmp_operand ((static_cast<dt_operand *> (n1))->op, (static_cast<dt_operand *> (n2))->op);
 
   else if (n1->type == dt_node::DT_MATCH)
-    return (static_cast<dt_operand *> (n1))->m_level == (static_cast<dt_operand *> (n2))->m_level;
+    return (static_cast<dt_operand *> (n1))->match_dop == (static_cast<dt_operand *> (n2))->match_dop;
 
   else
     return false;
@@ -721,10 +723,10 @@ dt_node::append_true_op (dt_node *parent
 }
 
 dt_node *
-dt_node::append_match_op (unsigned m_level, dt_node *parent, unsigned pos)
+dt_node::append_match_op (dt_operand *match_dop, dt_node *parent, unsigned pos)
 {
   dt_operand *parent_ = static_cast<dt_operand *> (parent);
-  dt_node *n = new dt_operand (DT_MATCH, 0, m_level, parent_, pos);
+  dt_node *n = new dt_operand (DT_MATCH, 0, match_dop, parent_, pos);
   dt_node *p = append_node (n);
 
   if (p != n)
@@ -734,33 +736,37 @@ dt_node::append_match_op (unsigned m_lev
 }
 
 dt_node *
-dt_node::append_simplify (simplify *s, unsigned pattern_no, unsigned *indexes) 
+dt_node::append_simplify (simplify *s, unsigned pattern_no, dt_operand **indexes) 
 {
   dt_node *n = new dt_simplify (s, pattern_no, indexes);
   return append_node (n);
 }
 
 dt_node *
-decision_tree::insert_operand (dt_node *p, operand *o, unsigned *indexes, unsigned pos, dt_node *parent) 
+decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes, unsigned pos, dt_node *parent) 
 {
-  dt_node *q;
+  dt_node *q, *elm;
 
   if (o->type == operand::OP_CAPTURE)
     {
       capture *c = static_cast<capture *> (o);
       unsigned capt_index = atoi (c->where);
 
-      if (indexes[capt_index] == dt_simplify::level_max)
+      if (indexes[capt_index] == 0)
 	{
-	  indexes[capt_index] = p->level + 1;
-
 	  if (c->what)
-	    return insert_operand (p, c->what, indexes, pos, parent);
-	  else
 	    {
-	      p = p->append_true_op (parent, pos);
-	      return p;
+	      q = insert_operand (p, c->what, indexes, pos, parent);
+	      dt_node *temp = new dt_operand (dt_node::DT_OPERAND, c->what, 0);
+	      elm = decision_tree::find_node (p->kids, temp);
+	      free (temp);
 	    }
+	  else
+	    q = elm = p->append_true_op (parent, pos);
+
+	  gcc_assert (elm->type == dt_node::DT_TRUE || elm->type == dt_node::DT_OPERAND || elm->type == dt_node::DT_MATCH);
+	  indexes[capt_index] = static_cast<dt_operand *> (elm);
+	  return q;
 	}
       else
 	{
@@ -787,7 +793,7 @@ decision_tree::insert_operand (dt_node *
 void
 decision_tree::insert (struct simplify *s, unsigned pattern_no)
 {
-  unsigned indexes[dt_simplify::capture_max];
+  dt_operand *indexes[dt_simplify::capture_max];
 
   for (unsigned i = 0; i < s->matchers.length (); ++i)
     {
@@ -795,7 +801,7 @@ decision_tree::insert (struct simplify *
 	continue;
 
       for (unsigned j = 0; j < dt_simplify::capture_max; ++j)
-	indexes[j] = dt_simplify::level_max;
+	indexes[j] = 0; 
 
       dt_node *p = decision_tree::insert_operand (root, s->matchers[i], indexes);
       p->append_simplify (s, pattern_no, indexes);
@@ -821,13 +827,13 @@ decision_tree::print_node (dt_node *p, F
       else if (p->type == dt_node::DT_TRUE)
 	fprintf (f, "true");
       else if (p->type == dt_node::DT_MATCH)
-	fprintf (f, "match (%u)", ((static_cast<dt_operand *>(p))->m_level));
+	fprintf (f, "match (%p)", (void *) ((static_cast<dt_operand *>(p))->match_dop));
       else if (p->type == dt_node::DT_SIMPLIFY)
 	{
 	  dt_simplify *s = static_cast<dt_simplify *> (p);
 	  fprintf (f, "simplify_%u { ", s->pattern_no); 
 	  for (unsigned i = 0; i < dt_simplify::capture_max; ++i)
-	    fprintf (f, "%u, ", s->indexes[i]);
+	    fprintf (f, "%p, ", (void *) s->indexes[i]);
 	  fprintf (f, " } "); 
 	}
     }      
@@ -855,6 +861,24 @@ write_fn_prototype (FILE *f, unsigned n)
   fprintf (f, ", code_helper *res_code, tree *res_ops, gimple_seq *seq, tree (*valueize)(tree))\n");
 }
 
+char *
+dt_operand::get_name (char *name)
+{
+  if (parent->level == 1)
+    sprintf (name, "op%u", pos);
+  else if (parent->type == dt_node::DT_MATCH)
+    return parent->get_name (name); 
+  else
+    sprintf (name, "o%u%u", parent->level, pos);
+  return name;
+}
+
+void
+dt_operand::gen_opname (char *name, unsigned pos)
+{
+  sprintf (name, "o%u%u", level, pos);
+}
+
 unsigned
 dt_operand::gen_gimple_predicate (FILE *f, const char *opname)
 {
@@ -868,7 +892,9 @@ dt_operand::gen_gimple_predicate (FILE *
 unsigned
 dt_operand::gen_gimple_match_op (FILE *f, const char *opname)
 {
-  fprintf (f, "if (%s == o%u)\n", opname, m_level);
+  char match_opname[20];
+  match_dop->get_name (match_opname);
+  fprintf (f, "if (%s == %s)\n", opname, match_opname);
   fprintf (f, "{\n");
   return 1;
 }
@@ -885,8 +911,7 @@ dt_operand::gen_gimple_expr_fn (FILE *f,
   for (unsigned i = 0; i < n_ops; ++i)
     {
       char child_opname[20];
-      sprintf (child_opname, "t%u", dt_operand::temp_count);
-      temps.safe_push (dt_operand::temp_count++);
+      gen_opname (child_opname, i); 
 
       fprintf (f, "tree %s = gimple_call_arg (def_stmt, %u);\n", child_opname, i);
       fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", child_opname, child_opname);
@@ -912,8 +937,7 @@ dt_operand::gen_gimple_expr_expr (FILE *
   for (unsigned i = 0; i < n_ops; ++i)
     {
       char child_opname[20];
-      sprintf (child_opname, "t%u", dt_operand::temp_count);
-      temps.safe_push (dt_operand::temp_count++);
+      gen_opname (child_opname, i); 
 
       fprintf (f, "tree %s = gimple_assign_rhs%u (def_stmt);\n", child_opname, i + 1);
       fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", child_opname, child_opname);
@@ -947,8 +971,7 @@ dt_operand::gen_generic_expr_expr (FILE
   for (unsigned i = 0; i < n_ops; ++i)
     {
       char child_opname[20];
-      sprintf (child_opname, "t%u", dt_operand::temp_count);
-      temps.safe_push (dt_operand::temp_count++);
+      gen_opname (child_opname, i);
 
       fprintf (f, "tree %s = TREE_OPERAND (%s, %u);\n", child_opname, opname, i);
       fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", child_opname, child_opname);
@@ -973,8 +996,7 @@ dt_operand::gen_generic_expr_fn (FILE *f
   for (unsigned i = 0; i < n_ops; ++i)
     {
       char child_opname[20];
-      sprintf (child_opname, "t%u", dt_operand::temp_count);
-      temps.safe_push (dt_operand::temp_count++);
+      gen_opname (child_opname, i);
 
       fprintf (f, "tree %s = CALL_EXPR_ARG (%s, %u);\n", child_opname, opname, i);
       fprintf (f, "if ((%s = do_valueize (valueize, %s)) != 0)\n", child_opname, child_opname);
@@ -994,20 +1016,10 @@ void
 dt_operand::gen_gimple (FILE *f)
 {
   char opname[20];
-  sprintf (opname, "o%u", level);
-  
+  get_name (opname); 
 
   fprintf (f, "{\n");
 
-  if (parent->parent == 0)
-    fprintf (f, "tree %s = op%u;\n", opname, pos);
-  else if (parent->type == dt_node::DT_MATCH)
-    fprintf (f, "tree %s = o%u;\n", opname, parent->level);
-  else if (parent->type == dt_node::DT_OPERAND && parent->op->type == operand::OP_EXPR) 
-    fprintf (f, "tree %s = t%u;\n", opname, parent->temps[pos]);
-  else
-    gcc_unreachable ();
-
   unsigned n_braces = 0;
  
   if (type == DT_OPERAND)
@@ -1062,7 +1074,6 @@ dt_operand::gen_gimple (FILE *f)
 void
 dt_simplify::gen_gimple (FILE *f)
 {
-  char *fail_label = 0;
 
   fprintf (f, "/* simplify %u */\n", pattern_no);
 
@@ -1070,14 +1082,17 @@ dt_simplify::gen_gimple (FILE *f)
   fprintf (f, "tree captures[4] = {};\n");
 
   for (unsigned i = 0; i < dt_simplify::capture_max; ++i)
-    if (indexes[i] != dt_simplify::level_max) 
-      fprintf (f, "captures[%u] = o%u;\n", i, indexes[i]); 
+    if (indexes[i])
+      {
+	char opname[20];
+	fprintf (f, "captures[%u] = %s;\n", i, indexes[i]->get_name (opname));
+      }
 
   if (s->ifexpr)
 	{
 	  output_line_directive (f, s->ifexpr_location);
 	  fprintf (f, "if (");
-	  s->ifexpr->gen_gimple_transform (f, fail_label, NULL);
+	  s->ifexpr->gen_gimple_transform (f, NULL);
 	  fprintf (f, ")\n");
 	  fprintf (f, "{\n");
 	}
@@ -1091,7 +1106,7 @@ dt_simplify::gen_gimple (FILE *f)
 	    {
 	      char dest[32];
 	      snprintf (dest, 32, "  res_ops[%d]", j);
-	      e->ops[j]->gen_gimple_transform (f, fail_label, dest);
+	      e->ops[j]->gen_gimple_transform (f, dest);
 	    }
 	  /* Re-fold the toplevel result.  It's basically an embedded
 	     gimple_build w/o actually building the stmt.  */
@@ -1101,7 +1116,7 @@ dt_simplify::gen_gimple (FILE *f)
       else if (s->result->type == operand::OP_CAPTURE
 	       || s->result->type == operand::OP_C_EXPR)
 	{
-	  s->result->gen_gimple_transform (f, fail_label,
+	  s->result->gen_gimple_transform (f,
 					   "res_ops[0]");
 	  fprintf (f, "*res_code = TREE_CODE (res_ops[0]);\n");
 	}

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]