[tuples] Convert TER

[Diego Novillo <dnovillo at google dot com>]

This patch converts TER to tuples and kills my original intent of not
merging gimple_to_tree() into mainline.  This function generates trees
out of GIMPLE so that they can be passed to the RTL expander.  It's
hideous, but converting the RTL expander to talk to GIMPLE directly is
going to be a significant job (we've been trying to do this for the
last 4 years, IIRC).

Bootstrapped and tested on x86_64.


Diego.


2008-06-27  Diego Novillo  <dnovillo@google.com>

	* cfgexpand.c (gimple_assign_rhs_to_tree): Factor out of ...
	(gimple_to_tree): ... here.
	Update comments referring to mainline merge.
	* tree-ssa-ter.c: Tuplify.
	* tree-outof-ssa.c (gimple_assign_rhs_to_tree): Declare.
	(replace_use_variable): Call it.
	(rewrite_trees): Tuplify.
	(remove_ssa_form): Call it.
	* gimple.h: Tidy some formatting.
	* ipa-struct-reorg.c: Include gimple.h
	* Makefile.in (ipa-struct-reorg.o): Add dependency on
	GIMPLE_H.

Index: cfgexpand.c
===================================================================
--- cfgexpand.c	(revision 137195)
+++ cfgexpand.c	(working copy)
@@ -42,6 +42,39 @@ along with GCC; see the file COPYING3.
 #include "value-prof.h"
 #include "target.h"

+/* Private function shared with tree-outof-ssa.c  */
+tree gimple_assign_rhs_to_tree (gimple);
+
+
+/* Return an expression tree corresponding to the RHS of GIMPLE
+   statement STMT.  */
+
+tree
+gimple_assign_rhs_to_tree (gimple stmt)
+{
+  tree t;
+  enum gimple_rhs_class class;
+
+  class = get_gimple_rhs_class (gimple_expr_code (stmt));
+
+  if (class == GIMPLE_BINARY_RHS)
+    t = build2 (gimple_assign_rhs_code (stmt),
+		TREE_TYPE (gimple_assign_lhs (stmt)),
+		gimple_assign_rhs1 (stmt),
+		gimple_assign_rhs2 (stmt));
+  else if (class == GIMPLE_UNARY_RHS)
+    t = build1 (gimple_assign_rhs_code (stmt),
+		TREE_TYPE (gimple_assign_lhs (stmt)),
+		gimple_assign_rhs1 (stmt));
+  else if (class == GIMPLE_SINGLE_RHS)
+    t = gimple_assign_rhs1 (stmt);
+  else
+    gcc_unreachable ();
+
+  return t;
+}
+
+
 /* Helper for gimple_to_tree.  Set EXPR_LOCATION for every expression
    inside *TP.  DATA is the location to set.  */

@@ -56,17 +89,13 @@ set_expr_location_r (tree *tp, int *ws A
 }


-/* FIXME tuples.  THIS IS A HACK.  DO NOT USE.
+/* FIXME tuples.  THIS IS A HACK.

    RTL expansion has traditionally been done on trees, so the
    transition to doing it on GIMPLE tuples is very invasive to the RTL
    expander.  To facilitate the transition, this function takes a
    GIMPLE tuple STMT and returns the same statement in the form of a
-   tree.
-
-   This mechanism is ONLY used during the transition and will not be
-   merged into mainline.  If you think you need this function for
-   other uses, you are most likely wrong.  */
+   tree.  */

 static tree
 gimple_to_tree (gimple stmt)
@@ -79,27 +108,9 @@ gimple_to_tree (gimple stmt)
   switch (gimple_code (stmt))
     {
     case GIMPLE_ASSIGN:
-      {
-	enum gimple_rhs_class class;
-	
-	class = get_gimple_rhs_class (gimple_assign_rhs_code (stmt));
-	if (class == GIMPLE_BINARY_RHS)
-	  t = build2 (gimple_assign_rhs_code (stmt),
-		      TREE_TYPE (gimple_assign_lhs (stmt)),
-		      gimple_assign_rhs1 (stmt),
-		      gimple_assign_rhs2 (stmt));
-	else if (class == GIMPLE_UNARY_RHS)
-	  t = build1 (gimple_assign_rhs_code (stmt),
-		      TREE_TYPE (gimple_assign_lhs (stmt)),
-		      gimple_assign_rhs1 (stmt));
-	else if (class == GIMPLE_SINGLE_RHS)
-	  t = gimple_assign_rhs1 (stmt);
-	else
-	  gcc_unreachable ();
-	
-	t =  build_gimple_modify_stmt (gimple_assign_lhs (stmt), t);
-      }
-    break;
+      t = gimple_assign_rhs_to_tree (stmt);
+      t = build_gimple_modify_stmt (gimple_assign_lhs (stmt), t);
+      break;
 	
     case GIMPLE_COND:
       t = build2 (gimple_cond_code (stmt), boolean_type_node,
Index: tree-ssa-live.h
===================================================================
--- tree-ssa-live.h	(revision 137195)
+++ tree-ssa-live.h	(working copy)
@@ -361,8 +361,8 @@ extern var_map coalesce_ssa_name (void);


 /* From tree-ssa-ter.c  */
-extern tree *find_replaceable_exprs (var_map);
-extern void dump_replaceable_exprs (FILE *, tree *);
+extern gimple *find_replaceable_exprs (var_map);
+extern void dump_replaceable_exprs (FILE *, gimple *);


 #endif /* _TREE_SSA_LIVE_H  */
Index: tree-ssa-ter.c
===================================================================
--- tree-ssa-ter.c	(revision 137195)
+++ tree-ssa-ter.c	(working copy)
@@ -32,8 +32,6 @@ along with GCC; see the file COPYING3.
 #include "tree-ssa-live.h"


-/* FIXME tuples.  */
-#if 0
 /* Temporary Expression Replacement (TER)

    Replace SSA version variables during out-of-ssa with their defining
@@ -160,7 +158,7 @@ typedef struct temp_expr_table_d
 {
   var_map map;
   bitmap *partition_dependencies;	/* Partitions expr is dependent on.  */
-  tree *replaceable_expressions;	/* Replacement expression table.  */
+  gimple *replaceable_expressions;	/* Replacement expression table.  */
   bitmap *expr_decl_uids;		/* Base uids of exprs.  */
   bitmap *kill_list;			/* Expr's killed by a partition.  */
   int virtual_partition;		/* Pseudo partition for virtual ops.  */
@@ -217,10 +215,10 @@ new_temp_expr_table (var_map map)
 /* Free TER table T.  If there are valid replacements, return the expression
    vector.  */

-static tree *
+static gimple *
 free_temp_expr_table (temp_expr_table_p t)
 {
-  tree *ret = NULL;
+  gimple *ret = NULL;
   unsigned i;

 #ifdef ENABLE_CHECKING
@@ -256,7 +254,7 @@ version_to_be_replaced_p (temp_expr_tabl
 {
   if (!tab->replaceable_expressions)
     return false;
-  return tab->replaceable_expressions[version] != NULL_TREE;
+  return tab->replaceable_expressions[version] != NULL;
 }


@@ -361,18 +359,18 @@ add_dependence (temp_expr_table_p tab, i
 /* Return TRUE if expression STMT is suitable for replacement.  */

 static inline bool
-is_replaceable_p (tree stmt)
+is_replaceable_p (gimple stmt)
 {
-  tree call_expr;
   use_operand_p use_p;
-  tree def, use_stmt;
+  tree def;
+  gimple use_stmt;

   /* Only consider modify stmts.  */
-  if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
+  if (!is_gimple_assign (stmt))
     return false;

   /* If the statement may throw an exception, it cannot be replaced.  */
-  if (tree_could_throw_p (stmt))
+  if (stmt_could_throw_p (stmt))
     return false;

   /* Punt if there is more than 1 def.  */
@@ -389,7 +387,7 @@ is_replaceable_p (tree stmt)
     return false;

   /* Used in this block, but at the TOP of the block, not the end.  */
-  if (TREE_CODE (use_stmt) == PHI_NODE)
+  if (gimple_code (use_stmt) == GIMPLE_PHI)
     return false;

   /* There must be no VDEFs.  */
@@ -398,21 +396,21 @@ is_replaceable_p (tree stmt)

   /* Float expressions must go through memory if float-store is on.  */
   if (flag_float_store
-      && FLOAT_TYPE_P (TREE_TYPE (GENERIC_TREE_OPERAND (stmt, 1))))
+      && FLOAT_TYPE_P (gimple_expr_type (stmt)))
     return false;

   /* An assignment with a register variable on the RHS is not
      replaceable.  */
-  if (TREE_CODE (GENERIC_TREE_OPERAND (stmt, 1)) == VAR_DECL
-      && DECL_HARD_REGISTER (GENERIC_TREE_OPERAND (stmt, 1)))
+  if (gimple_assign_rhs_code (stmt) == VAR_DECL
+      && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
     return false;

   /* No function calls can be replaced.  */
-  if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE)
+  if (gimple_code (stmt) == GIMPLE_CALL)
     return false;

   /* Leave any stmt with volatile operands alone as well.  */
-  if (stmt_ann (stmt)->has_volatile_ops)
+  if (gimple_has_volatile_ops (stmt))
     return false;


@@ -446,7 +444,7 @@ finished_with_expr (temp_expr_table_p ta
 /* Create an expression entry for a replaceable expression.  */

 static void
-process_replaceable (temp_expr_table_p tab, tree stmt)
+process_replaceable (temp_expr_table_p tab, gimple stmt)
 {
   tree var, def, basevar;
   int version;
@@ -540,7 +538,7 @@ mark_replaceable (temp_expr_table_p tab,

   /* Set the replaceable expression.  */
   if (!tab->replaceable_expressions)
-    tab->replaceable_expressions = XCNEWVEC (tree, num_ssa_names + 1);
+    tab->replaceable_expressions = XCNEWVEC (gimple, num_ssa_names + 1);
   tab->replaceable_expressions[version] = SSA_NAME_DEF_STMT (var);
 }

@@ -551,20 +549,20 @@ mark_replaceable (temp_expr_table_p tab,
 static void
 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
 {
-  block_stmt_iterator bsi;
-  tree stmt, def, use;
-  stmt_ann_t ann;
+  gimple_stmt_iterator bsi;
+  gimple stmt;
+  tree def, use;
   int partition;
   var_map map = tab->map;
   ssa_op_iter iter;
   bool stmt_replaceable;

-  for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
     {
-      stmt = bsi_stmt (bsi);
-      ann = stmt_ann (stmt);
+      stmt = gsi_stmt (bsi);

       stmt_replaceable = is_replaceable_p (stmt);
+
       /* Determine if this stmt finishes an existing expression.  */
       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 	{
@@ -593,7 +591,7 @@ find_replaceable_in_bb (temp_expr_table_
 	      /* Mark expression as replaceable unless stmt is volatile or the
 		 def variable has the same root variable as something in the
 		 substitution list.  */
-	      if (ann->has_volatile_ops || same_root_var)
+	      if (gimple_has_volatile_ops (stmt) || same_root_var)
 		finished_with_expr (tab, ver, true);
 	      else
 		mark_replaceable (tab, use, stmt_replaceable);
@@ -631,12 +629,12 @@ find_replaceable_in_bb (temp_expr_table_
    NULL is returned by the function, otherwise an expression vector indexed
    by SSA_NAME version numbers.  */

-extern tree *
+extern gimple *
 find_replaceable_exprs (var_map map)
 {
   basic_block bb;
   temp_expr_table_p table;
-  tree *ret;
+  gimple *ret;

   table = new_temp_expr_table (map);
   FOR_EACH_BB (bb)
@@ -666,23 +664,20 @@ find_replaceable_exprs (var_map map)

 /* Dump TER expression table EXPR to file F.  */

-extern void
-dump_replaceable_exprs (FILE *f, tree *expr)
+void
+dump_replaceable_exprs (FILE *f, gimple *expr)
 {
-  tree stmt, var;
-  int x;
+  tree var;
+  unsigned x;

   fprintf (f, "\nReplacing Expressions\n");
-  for (x = 0; x < (int)num_ssa_names; x++)
+  for (x = 0; x < num_ssa_names; x++)
     if (expr[x])
       {
-        stmt = expr[x];
-	var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
-	gcc_assert (var != NULL_TREE);
+	var = ssa_name (x);
 	print_generic_expr (f, var, TDF_SLIM);
 	fprintf (f, " replace with --> ");
-	print_generic_expr (f, GENERIC_TREE_OPERAND (stmt, 1),
-			    TDF_SLIM);
+	print_gimple_stmt (f, expr[x], 0, TDF_SLIM);
 	fprintf (f, "\n");
       }
   fprintf (f, "\n");
@@ -694,7 +689,7 @@ dump_replaceable_exprs (FILE *f, tree *e
    exclusively to debug TER.  F is the place to send debug info and T is the
    table being debugged.  */

-extern void
+void
 debug_ter (FILE *f, temp_expr_table_p t)
 {
   unsigned x, y;
@@ -737,4 +732,3 @@ debug_ter (FILE *f, temp_expr_table_p t)
   fprintf (f, "\n----------\n");
 }
 #endif
-#endif
Index: tree-outof-ssa.c
===================================================================
--- tree-outof-ssa.c	(revision 137195)
+++ tree-outof-ssa.c	(working copy)
@@ -34,6 +34,9 @@ along with GCC; see the file COPYING3.
 #include "tree-pass.h"
 #include "toplev.h"

+/* Private function shared with cfgexpand.c.  */
+tree gimple_assign_rhs_to_tree (gimple);
+
 /* Used to hold all the components required to do SSA PHI elimination.
    The node and pred/succ list is a simple linear list of nodes and
    edges represented as pairs of nodes.
@@ -550,7 +553,7 @@ assign_vars (var_map map)
    If the stmt is changed, return true.  */

 static inline bool
-replace_use_variable (var_map map, use_operand_p p, tree *expr)
+replace_use_variable (var_map map, use_operand_p p, gimple *expr)
 {
   tree new_var;
   tree var = USE_FROM_PTR (p);
@@ -561,11 +564,7 @@ replace_use_variable (var_map map, use_o
       int version = SSA_NAME_VERSION (var);
       if (expr[version])
         {
-	  tree new_expr = GIMPLE_STMT_OPERAND (expr[version], 1);
-	  SET_USE (p, new_expr);
-
-	  /* Clear the stmt's RHS, or GC might bite us.  */
-	  GIMPLE_STMT_OPERAND (expr[version], 1) = NULL_TREE;
+	  SET_USE (p, gimple_assign_rhs_to_tree (expr[version]));
 	  return true;
 	}
     }
@@ -656,7 +655,7 @@ eliminate_virtual_phis (void)
    variable.  */

 static void
-rewrite_trees (var_map map, tree *values)
+rewrite_trees (var_map map, gimple *values)
 {
   elim_graph g;
   basic_block bb;
@@ -1294,7 +1293,7 @@ static void
 remove_ssa_form (bool perform_ter)
 {
   basic_block bb;
-  tree *values = NULL;
+  gimple *values = NULL;
   var_map map;
   gimple_stmt_iterator gsi;

@@ -1312,15 +1311,9 @@ remove_ssa_form (bool perform_ter)

   if (perform_ter)
     {
-
-      /* FIXME tuples */
-#if 0
       values = find_replaceable_exprs (map);
       if (values && dump_file && (dump_flags & TDF_DETAILS))
 	dump_replaceable_exprs (dump_file, values);
-#else
-      values = NULL;
-#endif
     }

   /* Assign real variables to the partitions now.  */
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 137195)
+++ Makefile.in	(working copy)
@@ -2570,10 +2570,11 @@ ipa-type-escape.o : ipa-type-escape.c $(
    pointer-set.h $(GGC_H) $(IPA_TYPE_ESCAPE_H) $(IPA_UTILS_H) $(C_COMMON_H) \
    $(TREE_GIMPLE_H) $(CGRAPH_H) output.h $(FLAGS_H) tree-pass.h \
    $(DIAGNOSTIC_H) $(FUNCTION_H)
-ipa-struct-reorg.o: ipa-struct-reorg.c ipa-struct-reorg.h $(CONFIG_H)
$(SYSTEM_H) \
-   coretypes.h $(TM_H) $(RTL_H) $(TREE_H) $(FLAGS_H) output.h $(REGS_H) \
-   $(EXPR_H) $(FUNCTION_H) toplev.h $(GGC_H) $(TARGET_H) langhooks.h
$(COVERAGE_H) \
-   libfuncs.h gt-coverage.h $(HASHTAB_H) $(IPA_TYPE_ESCAPE_H)
+ipa-struct-reorg.o: ipa-struct-reorg.c ipa-struct-reorg.h $(CONFIG_H) \
+   $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) $(FLAGS_H) output.h \
+   $(REGS_H) $(EXPR_H) $(FUNCTION_H) toplev.h $(GGC_H) $(TARGET_H) \
+   langhooks.h $(COVERAGE_H) libfuncs.h gt-coverage.h $(HASHTAB_H) \
+   $(IPA_TYPE_ESCAPE_H) $(GIMPLE_H)

 coverage.o : coverage.c $(GCOV_IO_H) $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    $(TM_H) $(RTL_H) $(TREE_H) $(FLAGS_H) output.h $(REGS_H) $(EXPR_H) \
Index: gimple.h
===================================================================
--- gimple.h	(revision 137195)
+++ gimple.h	(working copy)
@@ -760,12 +760,17 @@ union gimple_statement_d GTY ((desc ("gi

 /* In gimple.c.  */
 gimple gimple_build_return (tree);
+
 gimple gimple_build_assign_stat (tree, tree MEM_STAT_DECL);
 #define gimple_build_assign(l,r) gimple_build_assign_stat (l, r MEM_STAT_INFO)
+
 void extract_ops_from_tree (tree, enum tree_code *, tree *, tree *);
-gimple gimple_build_assign_with_ops_stat (enum tree_code, tree, tree,
tree MEM_STAT_DECL);
+
+gimple gimple_build_assign_with_ops_stat (enum tree_code, tree, tree,
+					  tree MEM_STAT_DECL);
 #define gimple_build_assign_with_ops(c,o1,o2,o3) \
   gimple_build_assign_with_ops_stat (c, o1, o2, o3 MEM_STAT_INFO)
+
 gimple gimple_build_call_vec (tree, VEC(tree, heap) *);
 gimple gimple_build_call (tree, unsigned, ...);
 gimple gimple_build_call_from_tree (tree);
@@ -4273,14 +4278,14 @@ gimple_alloc_kind (enum gimple_code code
 {
   switch (code)
     {
-  case GIMPLE_ASSIGN:
-    return gimple_alloc_kind_assign;
-  case GIMPLE_PHI:
-    return gimple_alloc_kind_phi;
-  case GIMPLE_COND:
-    return gimple_alloc_kind_cond;
-  default:
-    return gimple_alloc_kind_rest;
+      case GIMPLE_ASSIGN:
+	return gimple_alloc_kind_assign;
+      case GIMPLE_PHI:
+	return gimple_alloc_kind_phi;
+      case GIMPLE_COND:
+	return gimple_alloc_kind_cond;
+      default:
+	return gimple_alloc_kind_rest;
     }
 }
 #endif /* GATHER_STATISTICS */
Index: ipa-struct-reorg.c
===================================================================
--- ipa-struct-reorg.c	(revision 137195)
+++ ipa-struct-reorg.c	(working copy)
@@ -55,6 +55,7 @@ Software Foundation, 59 Temple Place - S
 #include "ipa-type-escape.h"
 #include "tree-dump.h"
 #include "c-common.h"
+#include "gimple.h"

 /* This optimization implements structure peeling.