New TER code.

2006-12-08  Andrew MacLeod  <amacleod@redhat.com>

	* Makefile.in: Add new file tree-ssa-ter.c.
	* tree-outof-ssa.c (struct temp_expr_table_d, new_temp_expr_table, 
	free_temp_expr_table, add_value_to_version_list, 
	add_value_to_partition_list, remove_value_from_partition_list, 
	add_dependence, check_replaceable, finish_expr, mark_replaceable, 
	kill_expr, kill_virtual_exprs, find_replaceable_in_bb, 
	find_replaceable_exprs, dump_replaceable_exprs): Move to tree-ssa-ter.c.
	* tree-ssa-live.h (find_replaceable_exprs, dump_replaceable_exprs): Add
	prototypes.
	* tree-ssa-ter.c: New file using code moved from tree-outof-ssa.c.
	(struct value_expr_d): Remove.
	(struct temp_expr_table_d): Rename fields, add explicit vector of
	replaceable expressions instead of sharing. Change value_expr_p's to 
	bitmap.  Delete free_list.
	(new_temp_expr_table): Rename fields, count number of ssa_names in
	each partition.
	(free_temp_expr_table): Rename field, free new fields.
	(new_value_expr, free_value_expr, find_value_in_list, add_value_to_list,
	add_info_to_list, remove_value_from_list): Delete.
	(version_to_be_replaced_p): New. Is an ssa-name replaceable?
	(make_dependent_on_partition): New. Set bit in version list, allocating
	a bitmap if need be.
	(add_to_partition_kill_list): New.  Set bit in the partition list,
	allocating a bitmap if need be.
	(remove_from_partition_kill_list): New.  Remove a bit from the
	partition list, free the bitmap if it is empty.
	(add_dependence): Use renamed field, cleanup. Don't add a dependence
	on partitions with only one member.
	(is_replaceable_p): New.  Split out replaceability check from 
	check_replaceable.
	(process_replaceable): New. Replacement code split from 
	check_replaceable.
	(check_replaceable): Removed.
	(finished_with_expr): Renamed from finish_expr.
	(kill_expr): Use renamed fields. Less parameters.
	(kill_virtual_exprs): Less parameters.
	(mark_replaceable): Use renamed fields.
	(find_replaceable_in_bb): Use renamed fields, cleanup.
	(find_replaceable_exprs): Use renamed routines, cleanup.
	(dump_replaceable_exprs): don;t go past end of ssa_names list.
	(debug_ter): New.  Debug routine to dump state.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@119657 138bc75d-0d04-0410-961f-82ee72b054a4

5 files changed, 801 insertions, 605 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 704a4931511..dbd4e8aec3c 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,46 @@
+2006-12-08  Andrew MacLeod  <amacleod@redhat.com>
+
+	* Makefile.in: Add new file tree-ssa-ter.c.
+	* tree-outof-ssa.c (struct temp_expr_table_d, new_temp_expr_table, 
+	free_temp_expr_table, add_value_to_version_list, 
+	add_value_to_partition_list, remove_value_from_partition_list, 
+	add_dependence, check_replaceable, finish_expr, mark_replaceable, 
+	kill_expr, kill_virtual_exprs, find_replaceable_in_bb, 
+	find_replaceable_exprs, dump_replaceable_exprs): Move to tree-ssa-ter.c.
+	* tree-ssa-live.h (find_replaceable_exprs, dump_replaceable_exprs): Add
+	prototypes.
+	* tree-ssa-ter.c: New file using code moved from tree-outof-ssa.c.
+	(struct value_expr_d): Remove.
+	(struct temp_expr_table_d): Rename fields, add explicit vector of
+	replaceable expressions instead of sharing.  Change value_expr_p's to 
+	bitmap.  Delete free_list.
+	(new_temp_expr_table): Rename fields, count number of ssa_names in
+	each partition.
+	(free_temp_expr_table): Rename field, free new fields.
+	(new_value_expr, free_value_expr, find_value_in_list, add_value_to_list,
+	add_info_to_list, remove_value_from_list): Delete.
+	(version_to_be_replaced_p): New.  Is an ssa-name replaceable?
+	(make_dependent_on_partition): New.  Set bit in version list, allocating
+	a bitmap if need be.
+	(add_to_partition_kill_list): New.  Set bit in the partition list,
+	allocating a bitmap if need be.
+	(remove_from_partition_kill_list): New.  Remove a bit from the
+	partition list, free the bitmap if it is empty.
+	(add_dependence): Use renamed field, cleanup.  Don't add a dependence
+	on partitions with only one member.
+	(is_replaceable_p): New.  Split out replaceability check from 
+	check_replaceable.
+	(process_replaceable): New.  Code split from check_replaceable.
+	(check_replaceable): Removed.
+	(finished_with_expr): Renamed from finish_expr.
+	(kill_expr): Use renamed fields and less parameters.
+	(kill_virtual_exprs): Less parameters.
+	(mark_replaceable): Use renamed fields.
+	(find_replaceable_in_bb): Use renamed fields, cleanup.
+	(find_replaceable_exprs): Use renamed routines, cleanup.
+	(dump_replaceable_exprs): Don't go past end of ssa_names list.
+	(debug_ter): New.  Debug routine to dump state.
+
 2006-12-08  Bernd Schmidt  <bernd.schmidt@analog.com>
 
 	* config/bfin/bfin.c (effective_address_32bit_p): Return true for
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 76e29b01fac..bf954ebab88 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -975,7 +975,7 @@ C_OBJS = c-lang.o stub-objc.o $(C_AND_OBJC_OBJS)
 OBJS-common = \
  double-int.o tree-chrec.o tree-scalar-evolution.o tree-data-ref.o	   \
  tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o  \
- gimplify.o tree-pretty-print.o tree-into-ssa.o				   \
+ gimplify.o tree-pretty-print.o tree-into-ssa.o tree-ssa-ter.o		   \
  tree-outof-ssa.o tree-ssa-ccp.o tree-vn.o tree-ssa-uncprop.o		   \
  tree-ssa-dce.o  tree-ssa-copy.o tree-nrv.o tree-ssa-copyrename.o	   \
  tree-ssa-pre.o tree-ssa-live.o tree-ssa-operands.o tree-ssa-alias.o       \
@@ -1850,6 +1850,12 @@ tree-into-ssa.o : tree-into-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
    langhooks.h domwalk.h tree-pass.h $(GGC_H) $(PARAMS_H) $(BASIC_BLOCK_H) \
    bitmap.h $(CFGLOOP_H) $(FLAGS_H) hard-reg-set.h $(HASHTAB_H) \
    $(TREE_GIMPLE_H) $(TREE_INLINE_H) $(VARRAY_H) vecprim.h
+tree-ssa-ter.o : tree-ssa-ter.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
+   $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h $(DIAGNOSTIC_H) \
+   $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
+   langhooks.h tree-pass.h $(TREE_SSA_LIVE_H) $(BASIC_BLOCK_H) bitmap.h \
+   $(FLAGS_H) $(GGC_H) hard-reg-set.h $(HASHTAB_H) $(TREE_GIMPLE_H) \
+   $(TREE_INLINE_H) $(VARRAY_H) toplev.h vecprim.h
 tree-outof-ssa.o : tree-outof-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
    $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h $(DIAGNOSTIC_H) \
    $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c
index 279934d98e6..5edea642805 100644
--- a/gcc/tree-outof-ssa.c
+++ b/gcc/tree-outof-ssa.c
@@ -1121,610 +1121,6 @@ eliminate_virtual_phis (void)
 }
 
 
-/* Temporary Expression Replacement (TER)
-
-   Replace SSA version variables during out-of-ssa with their defining
-   expression if there is only one use of the variable.
-
-   A pass is made through the function, one block at a time.  No cross block
-   information is tracked.
-
-   Variables which only have one use, and whose defining stmt is considered
-   a replaceable expression (see check_replaceable) are entered into 
-   consideration by adding a list of dependent partitions to the version_info
-   vector for that ssa_name_version.  This information comes from the partition
-   mapping for each USE.  At the same time, the partition_dep_list vector for 
-   these partitions have this version number entered into their lists.
-
-   When the use of a replaceable ssa_variable is encountered, the dependence
-   list in version_info[] is moved to the "pending_dependence" list in case
-   the current expression is also replaceable. (To be determined later in 
-   processing this stmt.) version_info[] for the version is then updated to 
-   point to the defining stmt and the 'replaceable' bit is set.
-
-   Any partition which is defined by a statement 'kills' any expression which
-   is dependent on this partition.  Every ssa version in the partitions' 
-   dependence list is removed from future consideration.
-
-   All virtual references are lumped together.  Any expression which is
-   dependent on any virtual variable (via a VUSE) has a dependence added
-   to the special partition defined by VIRTUAL_PARTITION.
-
-   Whenever a V_MAY_DEF is seen, all expressions dependent this 
-   VIRTUAL_PARTITION are removed from consideration.
-
-   At the end of a basic block, all expression are removed from consideration
-   in preparation for the next block.  
-   
-   The end result is a vector over SSA_NAME_VERSION which is passed back to
-   rewrite_out_of_ssa.  As the SSA variables are being rewritten, instead of
-   replacing the SSA_NAME tree element with the partition it was assigned, 
-   it is replaced with the RHS of the defining expression.  */
-
-
-/* Dependency list element.  This can contain either a partition index or a
-   version number, depending on which list it is in.  */
-
-typedef struct value_expr_d 
-{
-  int value;
-  struct value_expr_d *next;
-} *value_expr_p;
-
-
-/* Temporary Expression Replacement (TER) table information.  */
-
-typedef struct temp_expr_table_d 
-{
-  var_map map;
-  void **version_info;
-  bitmap *expr_vars;
-  value_expr_p *partition_dep_list;
-  bitmap replaceable;
-  bool saw_replaceable;
-  int virtual_partition;
-  bitmap partition_in_use;
-  value_expr_p free_list;
-  value_expr_p pending_dependence;
-} *temp_expr_table_p;
-
-/* Used to indicate a dependency on V_MAY_DEFs.  */
-#define VIRTUAL_PARTITION(table)	(table->virtual_partition)
-
-static temp_expr_table_p new_temp_expr_table (var_map);
-static tree *free_temp_expr_table (temp_expr_table_p);
-static inline value_expr_p new_value_expr (temp_expr_table_p);
-static inline void free_value_expr (temp_expr_table_p, value_expr_p);
-static inline value_expr_p find_value_in_list (value_expr_p, int, 
-					       value_expr_p *);
-static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int);
-static inline void add_info_to_list (temp_expr_table_p, value_expr_p *, 
-				     value_expr_p);
-static value_expr_p remove_value_from_list (value_expr_p *, int);
-static void add_dependence (temp_expr_table_p, int, tree);
-static bool check_replaceable (temp_expr_table_p, tree);
-static void finish_expr (temp_expr_table_p, int, bool);
-static void mark_replaceable (temp_expr_table_p, tree);
-static inline void kill_expr (temp_expr_table_p, int, bool);
-static inline void kill_virtual_exprs (temp_expr_table_p, bool);
-static void find_replaceable_in_bb (temp_expr_table_p, basic_block);
-static tree *find_replaceable_exprs (var_map);
-static void dump_replaceable_exprs (FILE *, tree *);
-
-
-/* Create a new TER table for MAP.  */
-
-static temp_expr_table_p
-new_temp_expr_table (var_map map)
-{
-  temp_expr_table_p t;
-
-  t = XNEW (struct temp_expr_table_d);
-  t->map = map;
-
-  t->version_info = XCNEWVEC (void *, num_ssa_names + 1);
-  t->expr_vars = XCNEWVEC (bitmap, num_ssa_names + 1);
-  t->partition_dep_list = XCNEWVEC (value_expr_p,
-                                    num_var_partitions (map) + 1);
-
-  t->replaceable = BITMAP_ALLOC (NULL);
-  t->partition_in_use = BITMAP_ALLOC (NULL);
-
-  t->saw_replaceable = false;
-  t->virtual_partition = num_var_partitions (map);
-  t->free_list = NULL;
-  t->pending_dependence = NULL;
-
-  return t;
-}
-
-
-/* Free TER table T.  If there are valid replacements, return the expression 
-   vector.  */
-
-static tree *
-free_temp_expr_table (temp_expr_table_p t)
-{
-  value_expr_p p;
-  tree *ret = NULL;
-  unsigned i;
-
-#ifdef ENABLE_CHECKING
-  unsigned x;
-  for (x = 0; x <= num_var_partitions (t->map); x++)
-    gcc_assert (!t->partition_dep_list[x]);
-#endif
-
-  while ((p = t->free_list))
-    {
-      t->free_list = p->next;
-      free (p);
-    }
-
-  BITMAP_FREE (t->partition_in_use);
-  BITMAP_FREE (t->replaceable);
-
-  for (i = 0; i <= num_ssa_names; i++)
-    if (t->expr_vars[i])
-      BITMAP_FREE (t->expr_vars[i]);
-  free (t->expr_vars);
-
-  free (t->partition_dep_list);
-  if (t->saw_replaceable)
-    ret = (tree *)t->version_info;
-  else
-    free (t->version_info);
-  
-  free (t);
-  return ret;
-}
-
-
-/* Allocate a new value list node. Take it from the free list in TABLE if 
-   possible.  */
-
-static inline value_expr_p
-new_value_expr (temp_expr_table_p table)
-{
-  value_expr_p p;
-  if (table->free_list)
-    {
-      p = table->free_list;
-      table->free_list = p->next;
-    }
-  else
-    p = (value_expr_p) xmalloc (sizeof (struct value_expr_d));
-
-  return p;
-}
-
-
-/* Add value list node P to the free list in TABLE.  */
-
-static inline void
-free_value_expr (temp_expr_table_p table, value_expr_p p)
-{
-  p->next = table->free_list;
-  table->free_list = p;
-}
-
-
-/* Find VALUE if it's in LIST.  Return a pointer to the list object if found,  
-   else return NULL.  If LAST_PTR is provided, it will point to the previous 
-   item upon return, or NULL if this is the first item in the list.  */
-
-static inline value_expr_p
-find_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr)
-{
-  value_expr_p curr;
-  value_expr_p last = NULL;
-
-  for (curr = list; curr; last = curr, curr = curr->next)
-    {
-      if (curr->value == value)
-        break;
-    }
-  if (last_ptr)
-    *last_ptr = last;
-  return curr;
-}
-
-
-/* Add VALUE to LIST, if it isn't already present.  TAB is the expression 
-   table */
-
-static inline void
-add_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value)
-{
-  value_expr_p info;
-
-  if (!find_value_in_list (*list, value, NULL))
-    {
-      info = new_value_expr (tab);
-      info->value = value;
-      info->next = *list;
-      *list = info;
-    }
-}
-
-
-/* Add value node INFO if it's value isn't already in LIST.  Free INFO if
-   it is already in the list. TAB is the expression table.  */
-
-static inline void
-add_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info)
-{
-  if (find_value_in_list (*list, info->value, NULL))
-    free_value_expr (tab, info);
-  else
-    {
-      info->next = *list;
-      *list = info;
-    }
-}
-
-
-/* Look for VALUE in LIST.  If found, remove it from the list and return it's 
-   pointer.  */
-
-static value_expr_p
-remove_value_from_list (value_expr_p *list, int value)
-{
-  value_expr_p info, last;
-
-  info = find_value_in_list (*list, value, &last);
-  if (!info)
-    return NULL;
-  if (!last)
-    *list = info->next;
-  else
-    last->next = info->next;
- 
-  return info;
-}
-
-
-/* Add a dependency between the def of ssa VERSION and VAR.  If VAR is 
-   replaceable by an expression, add a dependence each of the elements of the 
-   expression.  These are contained in the pending list.  TAB is the
-   expression table.  */
-
-static void
-add_dependence (temp_expr_table_p tab, int version, tree var)
-{
-  int i, x;
-  value_expr_p info;
-
-  i = SSA_NAME_VERSION (var);
-  if (bitmap_bit_p (tab->replaceable, i))
-    {
-      /* This variable is being substituted, so use whatever dependences
-         were queued up when we marked this as replaceable earlier.  */
-      while ((info = tab->pending_dependence))
-        {
-	  tab->pending_dependence = info->next;
-	  /* Get the partition this variable was dependent on. Reuse this
-	     object to represent the current  expression instead.  */
-	  x = info->value;
-	  info->value = version;
-	  add_info_to_list (tab, &(tab->partition_dep_list[x]), info);
-          add_value_to_list (tab, 
-			     (value_expr_p *)&(tab->version_info[version]), x);
-	  bitmap_set_bit (tab->partition_in_use, x);
-	}
-    }
-  else
-    {
-      i = var_to_partition (tab->map, var);
-      gcc_assert (i != NO_PARTITION);
-      add_value_to_list (tab, &(tab->partition_dep_list[i]), version);
-      add_value_to_list (tab, 
-			 (value_expr_p *)&(tab->version_info[version]), i);
-      bitmap_set_bit (tab->partition_in_use, i);
-    }
-}
-
-
-/* Check if expression STMT is suitable for replacement in table TAB.  If so, 
-   create an expression entry.  Return true if this stmt is replaceable.  */
-
-static bool
-check_replaceable (temp_expr_table_p tab, tree stmt)
-{
-  tree var, def, basevar;
-  int version;
-  ssa_op_iter iter;
-  tree call_expr;
-  bitmap def_vars, use_vars;
-
-  if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
-    return false;
-  
-  /* Punt if there is more than 1 def, or more than 1 use.  */
-  def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
-  if (!def)
-    return false;
-
-  if (num_imm_uses (def) != 1)
-    return false;
-
-  /* There must be no V_MAY_DEFS or V_MUST_DEFS.  */
-  if (!(ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF))))
-    return false;
-
-  /* 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))))
-    return false;
-
-  /* Calls to functions with side-effects cannot be replaced.  */
-  if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE)
-    {
-      int call_flags = call_expr_flags (call_expr);
-      if (TREE_SIDE_EFFECTS (call_expr)
-	  && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
-	return false;
-    }
-
-  version = SSA_NAME_VERSION (def);
-  basevar = SSA_NAME_VAR (def);
-  def_vars = BITMAP_ALLOC (NULL);
-  bitmap_set_bit (def_vars, DECL_UID (basevar));
-
-  /* Add this expression to the dependency list for each use partition.  */
-  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
-    {
-      add_dependence (tab, version, var);
-
-      use_vars = tab->expr_vars[SSA_NAME_VERSION (var)];
-      if (use_vars)
-	bitmap_ior_into (def_vars, use_vars);
-    }
-  tab->expr_vars[version] = def_vars;
-
-  /* If there are VUSES, add a dependence on virtual defs.  */
-  if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
-    {
-      add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]), 
-			 VIRTUAL_PARTITION (tab));
-      add_value_to_list (tab, 
-			 &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]), 
-			 version);
-      bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
-    }
-
-  return true;
-}
-
-
-/* This function will remove the expression for VERSION from replacement 
-   consideration.n table TAB  If 'replace' is true, it is marked as 
-   replaceable, otherwise not.  */
-
-static void
-finish_expr (temp_expr_table_p tab, int version, bool replace)
-{
-  value_expr_p info, tmp;
-  int partition;
-
-  /* Remove this expression from its dependent lists.  The partition dependence
-     list is retained and transfered later to whomever uses this version.  */
-  for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
-    {
-      partition = info->value;
-      gcc_assert (tab->partition_dep_list[partition]);
-      tmp = remove_value_from_list (&(tab->partition_dep_list[partition]), 
-				    version);
-      gcc_assert (tmp);
-      free_value_expr (tab, tmp);
-      /* Only clear the bit when the dependency list is emptied via 
-         a replacement. Otherwise kill_expr will take care of it.  */
-      if (!(tab->partition_dep_list[partition]) && replace)
-        bitmap_clear_bit (tab->partition_in_use, partition);
-      tmp = info->next;
-      if (!replace)
-        free_value_expr (tab, info);
-    }
-
-  if (replace)
-    {
-      tab->saw_replaceable = true;
-      bitmap_set_bit (tab->replaceable, version);
-    }
-  else
-    {
-      gcc_assert (!bitmap_bit_p (tab->replaceable, version));
-      tab->version_info[version] = NULL;
-    }
-}
-
-
-/* Mark the expression associated with VAR as replaceable, and enter
-   the defining stmt into the version_info table TAB.  */
-
-static void
-mark_replaceable (temp_expr_table_p tab, tree var)
-{
-  value_expr_p info;
-  int version = SSA_NAME_VERSION (var);
-  finish_expr (tab, version, true);
-
-  /* Move the dependence list to the pending list.  */
-  if (tab->version_info[version])
-    {
-      info = (value_expr_p) tab->version_info[version]; 
-      for ( ; info->next; info = info->next)
-	continue;
-      info->next = tab->pending_dependence;
-      tab->pending_dependence = (value_expr_p)tab->version_info[version];
-    }
-
-  tab->version_info[version] = SSA_NAME_DEF_STMT (var);
-}
-
-
-/* This function marks any expression in TAB which is dependent on PARTITION
-   as NOT replaceable.  CLEAR_BIT is used to determine whether partition_in_use
-   should have its bit cleared.  Since this routine can be called within an
-   EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared.  */
-
-static inline void
-kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
-{
-  value_expr_p ptr;
-
-  /* Mark every active expr dependent on this var as not replaceable.  */
-  while ((ptr = tab->partition_dep_list[partition]) != NULL)
-    finish_expr (tab, ptr->value, false);
-
-  if (clear_bit)
-    bitmap_clear_bit (tab->partition_in_use, partition);
-}
-
-
-/* This function kills all expressions in TAB which are dependent on virtual 
-   DEFs.  CLEAR_BIT determines whether partition_in_use gets cleared.  */
-
-static inline void
-kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit)
-{
-  kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit);
-}
-
-
-/* This function processes basic block BB, and looks for variables which can
-   be replaced by their expressions.  Results are stored in 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;
-  int partition;
-  var_map map = tab->map;
-  value_expr_p p;
-  ssa_op_iter iter;
-
-  for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
-    {
-      stmt = bsi_stmt (bsi);
-      ann = stmt_ann (stmt);
-
-      /* Determine if this stmt finishes an existing expression.  */
-      FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
-	{
-	  unsigned ver = SSA_NAME_VERSION (use);
-
-	  if (tab->version_info[ver])
-	    {
-	      bool same_root_var = false;
-	      ssa_op_iter iter2;
-	      bitmap vars = tab->expr_vars[ver];
-
-	      /* See if the root variables are the same.  If they are, we
-		 do not want to do the replacement to avoid problems with
-		 code size, see PR tree-optimization/17549.  */
-	      FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
-		{
-		  if (bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def))))
-		    {
-		      same_root_var = true;
-		      break;
-		    }
-		}
-
-	      /* Mark expression as replaceable unless stmt is volatile
-		 or DEF sets the same root variable as STMT.  */
-	      if (!ann->has_volatile_ops && !same_root_var)
-		mark_replaceable (tab, use);
-	      else
-		finish_expr (tab, ver, false);
-	    }
-	}
-      
-      /* Next, see if this stmt kills off an active expression.  */
-      FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
-	{
-	  partition = var_to_partition (map, def);
-	  if (partition != NO_PARTITION && tab->partition_dep_list[partition])
-	    kill_expr (tab, partition, true);
-	}
-
-      /* Now see if we are creating a new expression or not.  */
-      if (!ann->has_volatile_ops)
-	check_replaceable (tab, stmt);
-
-      /* Free any unused dependency lists.  */
-      while ((p = tab->pending_dependence))
-	{
-	  tab->pending_dependence = p->next;
-	  free_value_expr (tab, p);
-	}
-
-      /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand.  */
-      if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
-        kill_virtual_exprs (tab, true);
-    }
-}
-
-
-/* This function is the driver routine for replacement of temporary expressions
-   in the SSA->normal phase, operating on MAP.  If there are replaceable 
-   expressions, a table is returned which maps SSA versions to the 
-   expressions they should be replaced with.  A NULL_TREE indicates no 
-   replacement should take place.  If there are no replacements at all, 
-   NULL is returned by the function, otherwise an expression vector indexed
-   by SSA_NAME version numbers.  */
-
-static tree *
-find_replaceable_exprs (var_map map)
-{
-  basic_block bb;
-  unsigned i;
-  temp_expr_table_p table;
-  tree *ret;
-
-  table = new_temp_expr_table (map);
-  FOR_EACH_BB (bb)
-    {
-      bitmap_iterator bi;
-
-      find_replaceable_in_bb (table, bb);
-      EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
-        {
-	  kill_expr (table, i, false);
-	}
-    }
-
-  ret = free_temp_expr_table (table);
-  return ret;
-}
-
-
-/* Dump TER expression table EXPR to file F.  */
-
-static void
-dump_replaceable_exprs (FILE *f, tree *expr)
-{
-  tree stmt, var;
-  int x;
-  fprintf (f, "\nReplacing Expressions\n");
-  for (x = 0; x < (int)num_ssa_names + 1; x++)
-    if (expr[x])
-      {
-        stmt = expr[x];
-	var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
-	gcc_assert (var != NULL_TREE);
-	print_generic_expr (f, var, TDF_SLIM);
-	fprintf (f, " replace with --> ");
-	print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
-	fprintf (f, "\n");
-      }
-  fprintf (f, "\n");
-}
-
-
 /* This function will rewrite the current program using the variable mapping
    found in MAP.  If the replacement vector VALUES is provided, any 
    occurrences of partitions with non-null entries in the vector will be 
diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h
index b4dd5e3a2be..19c708922e8 100644
--- a/gcc/tree-ssa-live.h
+++ b/gcc/tree-ssa-live.h
@@ -586,5 +586,9 @@ extern conflict_graph build_tree_conflict_graph (tree_live_info_p, tpa_p,
 extern void coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map,
 				  coalesce_list_p cl, FILE *);
 
+/* From tree-ssa-ter.c  */
+extern tree *find_replaceable_exprs (var_map);
+extern void dump_replaceable_exprs (FILE *, tree *);
+
 
 #endif /* _TREE_SSA_LIVE_H  */
diff --git a/gcc/tree-ssa-ter.c b/gcc/tree-ssa-ter.c
new file mode 100644
index 00000000000..2bd58cc38f2
--- /dev/null
+++ b/gcc/tree-ssa-ter.c
@@ -0,0 +1,747 @@
+/* Routines for performing Temporary Expression Replacement (TER) in SSA trees.
+   Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod  <amacleod@redhat.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA.  */
+
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "flags.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "ggc.h"
+#include "langhooks.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "output.h"
+#include "expr.h"
+#include "function.h"
+#include "diagnostic.h"
+#include "bitmap.h"
+#include "tree-flow.h"
+#include "tree-gimple.h"
+#include "tree-inline.h"
+#include "varray.h"
+#include "timevar.h"
+#include "hashtab.h"
+#include "tree-dump.h"
+#include "tree-ssa-live.h"
+#include "tree-pass.h"
+#include "toplev.h"
+#include "vecprim.h"
+
+
+/* Temporary Expression Replacement (TER)
+
+   Replace SSA version variables during out-of-ssa with their defining
+   expression if there is only one use of the variable.  
+
+   This pass is required in order for the RTL expansion pass to see larger
+   chunks of code.  This allows it to make better choices on RTL pattern
+   selection.  When expand is rewritten and merged with out-of-ssa, and
+   understands SSA, this should be eliminated.  
+
+   A pass is made through the function, one block at a time.  No cross block
+   information is tracked.
+
+   Variables which only have one use, and whose defining stmt is considered
+   a replaceable expression (see is_replaceable_p) are tracked to see whether
+   they can be replaced at their use location.  
+   
+   n_12 = C * 10
+   a_2 = b_5 + 6
+   v_9 = a_2 * n_12
+
+   if there are the only use of n_12 and a_2, TER will substitute in their
+   expressions in v_9, and end up with:
+
+   v_9 = (b_5 + 6) * (C * 10)
+
+   which will then have the ssa_name assigned to regular variables, and the
+   resulting code which will be passed ot the expander looks something like:
+
+   v = (b + 6) * (C * 10)
+
+   
+   This requires ensuring that none of the variables used by the expression 
+   change between the def point and where it is used.  Furthermore, if any 
+   of the ssa_names used in this expression are themselves replaceable, we 
+   have to ensure none of that expressions' arguments change either.  
+   Although SSA_NAMES themselves don't change, this pass is performed after 
+   coalescing has coalesced different SSA_NAMES together, so there could be a 
+   definition of an SSA_NAME which is coalesced with a use that causes a
+   problem.  ie
+   
+   PHI b_5 = <b_8(2), b_14(1)>
+   <...>
+   a_2 = b_5 + 6
+   b_8 = c_4 + 4
+   v_9 = a_2 * n_12
+   <...>
+
+   If b_5, b_8 and b_14 are all colaesced together...
+   The expression b_5 + 6 CANNOT replace the use in the statement defining v_9
+   because b_8 is in fact killing the value of b_5 since they share a partition
+   and will be assigned the same memory or regster location.
+   
+   TER implements this but stepping through the instructions in a block and
+   tracking potential expressions for replacement, and the paritions they are
+   dependent on.  Expressions are represented by the SSA_NAME_VERSION of the
+   DEF on the LHS of a GIMPLE_MODIFY_STMT and the expression is the RHS.
+
+   When a stmt is determined to be a possible replacement expression, the
+   following steps are taken:
+
+   EXPR_DECL_UID bitmap is allocated and set to the base variable UID of the 
+   def and any uses in the expression.  non-NULL means the expression is being 
+   tracked.  The UID's themselves are used to prevent TER substitution into
+   accumulating sequences.
+   ie
+   x = x + y
+   x = x + z
+   x = x + w
+   etc.
+   this can result in very large expressions which don't accomplish anything
+   see PR tree-optimization/17549.  
+
+   PARTITION_DEPENDENCIES is another bitmap array, and it has a bit set for any 
+   partition which is used in the expression.  This is primarily used to remove
+   an expression from the partition kill lists when a decision is made whether
+   to replace it or not.  This is indexed by ssa version number as well, and
+   indicates a partition number.  virtual operands are not tracked individually,
+   but they are summarized by an artifical partition called VIRTUAL_PARTITION.
+   This means a MAY or MUST def will kill *ALL* expressions that are dependant
+   on a virtual operand.
+   Note that the EXPR_DECL_UID and this bitmap represent very similar 
+   information, but the info in one is not easy to obtain from the other.
+
+   KILL_LIST is yet another bitmap array, this time it is indexed by partition
+   number, and represents a list of active expressions which will will no 
+   longer be valid if a definition into this partition takes place.
+
+   PARTITION_IN_USE is simply a bitmap which is used to track which partitions
+   currently have sokmething in their kill list.  This is used at the end of 
+   a block to clear out the KILL_LIST bitmaps at the end of each block.
+
+   NEW_REPLACEABLE_DEPENDENCIES is used as a temporary place to store 
+   dependencies which will be reused by the current defintion. ALl the uses
+   on an expression are processed before anything else is done. If a use is
+   determined to be a replaceable expression AND the current stmt is also going
+   to be replaceable, all the dependencies of this replaceable use will be
+   picked up by the current stmt's expression. Rather than recreate them, they
+   are simply copied here and then copied into the new expression when it is
+   processed.
+
+   a_2 = b_5 + 6
+   v_8 = a_2 + c_4
+
+   a_2's expression 'b_5 + 6' is determined to be replaceable at the use 
+   location. It is dependent on the partition 'b_5' is in. This is cached into
+   the NEW_REPLACEABLE_DEPENDENCIES bitmap. and when v_8 is examined for
+   replaceablility, it is a candidate, and it is dependent on the partition 
+   b_5 is in *NOT* a_2, as well as c_4's partition.
+
+   if v_8 is also replaceable:
+
+   x_9 = v_8 * 5
+
+   x_9 is dependent on partitions b_5, and c_4
+   
+   if a statement is found which has either of those partitions written to 
+   before x_9 is used, then x_9 itself is NOT replaceable.  */
+
+
+/* Temporary Expression Replacement (TER) table information.  */
+
+typedef struct temp_expr_table_d 
+{
+  var_map map;
+  bitmap *partition_dependencies;	/* Partitions expr is dependent on.  */
+  tree *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;		/* Psuedo partition for virtual ops.  */
+  bitmap partition_in_use;		/* Partitions with kill entires.  */
+  bitmap new_replaceable_dependencies;	/* Holding place for pending dep's.  */
+  int *num_in_part;			/* # of ssa_names in a partition.  */
+} *temp_expr_table_p;
+
+/* Used to indicate a dependency on V_MAY_DEFs.  */
+#define VIRTUAL_PARTITION(table)	(table->virtual_partition)
+
+#ifdef ENABLE_CHECKING
+extern void debug_ter (FILE *, temp_expr_table_p);
+#endif
+
+
+/* Create a new TER table for MAP.  */
+
+static temp_expr_table_p
+new_temp_expr_table (var_map map)
+{
+  temp_expr_table_p t;
+  unsigned x;
+
+  t = XNEW (struct temp_expr_table_d);
+  t->map = map;
+
+  t->partition_dependencies = XCNEWVEC (bitmap, num_ssa_names + 1);
+  t->expr_decl_uids = XCNEWVEC (bitmap, num_ssa_names + 1);
+  t->kill_list = XCNEWVEC (bitmap, num_var_partitions (map) + 1);
+
+  t->partition_in_use = BITMAP_ALLOC (NULL);
+
+  t->virtual_partition = num_var_partitions (map);
+  t->new_replaceable_dependencies = BITMAP_ALLOC (NULL);
+
+  t->replaceable_expressions = NULL;
+  t->num_in_part = XCNEWVEC (int, num_var_partitions (map));
+  for (x = 1; x < num_ssa_names; x++)
+    {
+      int p;
+      tree name = ssa_name (x);
+      if (!name)
+        continue;
+      p = var_to_partition (map, name);
+      if (p != NO_PARTITION)
+        t->num_in_part[p]++;
+    }
+
+  return t;
+}
+
+
+/* Free TER table T.  If there are valid replacements, return the expression 
+   vector.  */
+
+static tree *
+free_temp_expr_table (temp_expr_table_p t)
+{
+  tree *ret = NULL;
+  unsigned i;
+
+#ifdef ENABLE_CHECKING
+  unsigned x;
+  for (x = 0; x <= num_var_partitions (t->map); x++)
+    gcc_assert (!t->kill_list[x]);
+#endif
+
+  BITMAP_FREE (t->partition_in_use);
+
+  for (i = 0; i <= num_ssa_names; i++)
+    if (t->expr_decl_uids[i])
+      BITMAP_FREE (t->expr_decl_uids[i]);
+  free (t->expr_decl_uids);
+
+  free (t->kill_list);
+  free (t->partition_dependencies);
+
+  if (t->replaceable_expressions)
+    ret = t->replaceable_expressions;
+
+  free (t);
+  return ret;
+}
+
+
+/* Return TRUE if VERSION is to be replaced by an expression in TAB.  */
+
+static inline bool
+version_to_be_replaced_p (temp_expr_table_p tab, int version)
+{
+  if (!tab->replaceable_expressions)
+    return false;
+  return tab->replaceable_expressions[version] != NULL_TREE;
+}
+
+
+/* Add partition P to the list if partititons VERSION is dependent on.  TAB is 
+   the expression table */
+
+static inline void
+make_dependent_on_partition (temp_expr_table_p tab, int version, int p)
+{
+  if (!tab->partition_dependencies[version])
+    tab->partition_dependencies[version] = BITMAP_ALLOC (NULL);
+
+  bitmap_set_bit (tab->partition_dependencies[version], p);
+}
+
+
+/* Add VER to the kill list for P.  TAB is the expression table */
+
+static inline void
+add_to_partition_kill_list (temp_expr_table_p tab, int p, int ver)
+{
+  if (!tab->kill_list[p])
+    {
+      tab->kill_list[p] = BITMAP_ALLOC (NULL);
+      bitmap_set_bit (tab->partition_in_use, p);
+    }
+  bitmap_set_bit (tab->kill_list[p], ver);
+}
+
+
+/* Remove VER from the partition kill list for P.  TAB is the expression 
+   table.  */
+
+static inline void 
+remove_from_partition_kill_list (temp_expr_table_p tab, int p, int version)
+{
+#ifdef ENABLE_CHECKING
+  gcc_assert (tab->kill_list[p]);
+#endif
+  bitmap_clear_bit (tab->kill_list[p], version);
+  if (bitmap_empty_p (tab->kill_list[p]))
+    {
+      bitmap_clear_bit (tab->partition_in_use, p);
+      BITMAP_FREE (tab->kill_list[p]);
+    }
+}
+
+
+/* Add a dependency between the def of ssa VERSION and VAR.  If VAR is 
+   replaceable by an expression, add a dependence each of the elements of the 
+   expression.  These are contained in the new_replaceable list.  TAB is the
+   expression table.  */
+
+static void
+add_dependence (temp_expr_table_p tab, int version, tree var)
+{
+  int i;
+  bitmap_iterator bi;
+  unsigned x;
+
+  i = SSA_NAME_VERSION (var);
+  if (version_to_be_replaced_p (tab, i))
+    {
+      if (!bitmap_empty_p (tab->new_replaceable_dependencies))
+        {
+	  /* Version will now be killed by a write to any partition the 
+	     substituted expression would have been killed by.  */
+	  EXECUTE_IF_SET_IN_BITMAP (tab->new_replaceable_dependencies, 0, x, bi)
+	    add_to_partition_kill_list (tab, x, version);
+
+	  /* Rather than set partition_dependencies and in_use lists bit by 
+	     bit, simply OR in the new_replaceable_dependencies bits.  */
+	  if (!tab->partition_dependencies[version])
+	    tab->partition_dependencies[version] = BITMAP_ALLOC (NULL);
+	  bitmap_ior_into (tab->partition_dependencies[version], 
+			   tab->new_replaceable_dependencies);
+	  bitmap_ior_into (tab->partition_in_use, 
+			   tab->new_replaceable_dependencies);
+	  /* It is only necessary to add these once.  */
+	  bitmap_clear (tab->new_replaceable_dependencies);
+	}
+    }
+  else
+    {
+      i = var_to_partition (tab->map, var);
+#ifdef ENABLE_CHECKING
+      gcc_assert (i != NO_PARTITION);
+      gcc_assert (tab->num_in_part[i] != 0);
+#endif
+      /* Only dependencies on ssa_names which are coalesced with something need
+         to be tracked.  Partitions with containing only a single SSA_NAME
+	 *cannot* have their value changed.  */
+      if (tab->num_in_part[i] > 1)
+        {
+	  add_to_partition_kill_list (tab, i, version);
+	  make_dependent_on_partition (tab, version, i);
+	}
+    }
+}
+
+
+/* Return TRUE if expression STMT is suitable for replacement.  */
+
+static inline bool
+is_replaceable_p (tree stmt)
+{
+  tree call_expr;
+  use_operand_p use_p;
+  tree def, use_stmt;
+
+  /* Only consider modify stmts.  */
+  if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
+    return false;
+
+  /* Punt if there is more than 1 def.  */
+  def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
+  if (!def)
+    return false;
+
+  /* Only consider definitions which have a single use.  */
+  if (!single_imm_use (def, &use_p, &use_stmt))
+    return false;
+
+  /* If the use isn't in this block, it wont be replaced either.  */
+  if (bb_for_stmt (use_stmt) != bb_for_stmt (stmt))
+    return false;
+
+  /* Used in this block, but at the TOP of the block, not the end.  */
+  if (TREE_CODE (use_stmt) == PHI_NODE)
+    return false;
+
+  /* There must be no V_MAY_DEFS or V_MUST_DEFS.  */
+  if (!(ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF))))
+    return false;
+
+  /* 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))))
+    return false;
+
+  /* Calls to functions with side-effects cannot be replaced.  */
+  if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE)
+    {
+      int call_flags = call_expr_flags (call_expr);
+      if (TREE_SIDE_EFFECTS (call_expr)
+	  && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
+	return false;
+    }
+
+  /* Leave any stmt with voltile operands alone as well.  */
+  if (stmt_ann (stmt)->has_volatile_ops)
+    return false;
+  
+
+  return true;
+}
+
+
+/* This function will remove the expression for VERSION from replacement 
+   consideration in table TAB.  If FREE_EXPR is true, then remove the 
+   expression from consideration as well by freeing the decl uid bitmap.  */
+
+static void
+finished_with_expr (temp_expr_table_p tab, int version, bool free_expr)
+{
+  unsigned i;
+  bitmap_iterator bi;
+
+  /* Remove this expression from its dependent lists.  The partition dependence
+     list is retained and transfered later to whomever uses this version.  */
+  if (tab->partition_dependencies[version])
+    {
+      EXECUTE_IF_SET_IN_BITMAP (tab->partition_dependencies[version], 0, i, bi)
+	remove_from_partition_kill_list (tab, i, version);
+      BITMAP_FREE (tab->partition_dependencies[version]);
+    }
+  if (free_expr)
+    BITMAP_FREE (tab->expr_decl_uids[version]);
+}
+
+
+/* Create an expression entry fora replaceable expression.  */
+
+static void 
+process_replaceable (temp_expr_table_p tab, tree stmt)
+{
+  tree var, def, basevar;
+  int version;
+  ssa_op_iter iter;
+  bitmap def_vars, use_vars;
+
+#ifdef ENABLE_CHECKING
+  gcc_assert (is_replaceable_p (stmt));
+#endif
+
+  def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
+  version = SSA_NAME_VERSION (def);
+  basevar = SSA_NAME_VAR (def);
+  def_vars = BITMAP_ALLOC (NULL);
+
+  bitmap_set_bit (def_vars, DECL_UID (basevar));
+
+  /* Add this expression to the dependency list for each use partition.  */
+  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+    {
+      int var_version = SSA_NAME_VERSION (var);
+
+      use_vars = tab->expr_decl_uids[var_version];
+      add_dependence (tab, version, var);
+      if (use_vars)
+        {
+	  bitmap_ior_into (def_vars, use_vars);
+	  BITMAP_FREE (tab->expr_decl_uids[var_version]);
+	}
+      else
+	bitmap_set_bit (def_vars, DECL_UID (SSA_NAME_VAR (var)));
+    }
+  tab->expr_decl_uids[version] = def_vars;
+
+  /* If there are VUSES, add a dependence on virtual defs.  */
+  if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
+    {
+      make_dependent_on_partition (tab, version, VIRTUAL_PARTITION (tab));
+      add_to_partition_kill_list (tab, VIRTUAL_PARTITION (tab), version);
+    }
+}
+
+
+/* This function removes any expression in TAB which is dependent on PARTITION
+   from consideration, making it not replaceable.  */
+
+static inline void
+kill_expr (temp_expr_table_p tab, int partition)
+{
+  unsigned version;
+
+  /* Mark every active expr dependent on this var as not replaceable.  
+     finished_with_expr can modify the bitmap, so we can't execute over it.  */
+  while (tab->kill_list[partition])
+    {
+      version = bitmap_first_set_bit (tab->kill_list[partition]);
+      finished_with_expr (tab, version, true);
+    }
+
+#ifdef ENABLE_CHECKING
+  gcc_assert (!tab->kill_list[partition]);
+#endif
+}
+
+
+/* This function kills all expressions in TAB which are dependent on virtual 
+   partitions.  */
+
+static inline void
+kill_virtual_exprs (temp_expr_table_p tab)
+{
+  kill_expr (tab, VIRTUAL_PARTITION (tab));
+}
+
+
+/* Mark the expression associated with VAR as replaceable, and enter
+   the defining stmt into the partition_dependencies table TAB.  if
+   MORE_REPLACING is true, accumulate the pending partition dependencies.  */
+
+static void
+mark_replaceable (temp_expr_table_p tab, tree var, bool more_replacing)
+{
+  int version = SSA_NAME_VERSION (var);
+
+  /* Move the dependence list to the pending listpending.  */
+  if (more_replacing && tab->partition_dependencies[version])
+    bitmap_ior_into (tab->new_replaceable_dependencies, 
+		     tab->partition_dependencies[version]);
+
+  finished_with_expr (tab, version, !more_replacing);
+
+  /* Set the replaceable expression.  */
+  if (!tab->replaceable_expressions)
+    tab->replaceable_expressions = XCNEWVEC (tree, num_ssa_names + 1);
+  tab->replaceable_expressions[version] = SSA_NAME_DEF_STMT (var);
+}
+
+
+/* This function processes basic block BB, and looks for variables which can
+   be replaced by their expressions.  Results are stored in the table 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;
+  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))
+    {
+      stmt = bsi_stmt (bsi);
+      ann = stmt_ann (stmt);
+
+      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)
+	{
+	  unsigned ver = SSA_NAME_VERSION (use);
+
+	  /* If this use is a potential replacement variable, process it.  */
+	  if (tab->expr_decl_uids[ver])
+	    {
+	      bool same_root_var = false;
+	      ssa_op_iter iter2;
+	      bitmap vars = tab->expr_decl_uids[ver];
+
+	      /* See if the root variables are the same.  If they are, we
+		 do not want to do the replacement to avoid problems with
+		 code size, see PR tree-optimization/17549.  */
+	      if (!bitmap_empty_p (vars))
+		FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
+		  {
+		    if (bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def))))
+		      {
+			same_root_var = true;
+			break;
+		      }
+		  }
+
+	      /* 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)
+		finished_with_expr (tab, ver, true);
+	      else
+		mark_replaceable (tab, use, stmt_replaceable);
+	    }
+	}
+      
+      /* Next, see if this stmt kills off an active expression.  */
+      FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
+	{
+	  partition = var_to_partition (map, def);
+	  if (partition != NO_PARTITION && tab->kill_list[partition])
+	    kill_expr (tab, partition);
+	}
+
+      /* Now see if we are creating a new expression or not.  */
+      if (stmt_replaceable)
+	process_replaceable (tab, stmt);
+
+      /* Free any unused dependency lists.  */
+      bitmap_clear (tab->new_replaceable_dependencies);
+
+      /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand,
+	 including the current stmt.  */
+      if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
+        kill_virtual_exprs (tab);
+    }
+}
+
+
+/* This function is the driver routine for replacement of temporary expressions
+   in the SSA->normal phase, operating on MAP.  If there are replaceable 
+   expressions, a table is returned which maps SSA versions to the 
+   expressions they should be replaced with.  A NULL_TREE indicates no 
+   replacement should take place.  If there are no replacements at all, 
+   NULL is returned by the function, otherwise an expression vector indexed
+   by SSA_NAME version numbers.  */
+
+extern tree *
+find_replaceable_exprs (var_map map)
+{
+  basic_block bb;
+  temp_expr_table_p table;
+  tree *ret;
+
+  table = new_temp_expr_table (map);
+  FOR_EACH_BB (bb)
+    {
+      find_replaceable_in_bb (table, bb);
+      gcc_assert (bitmap_empty_p (table->partition_in_use));
+
+#ifdef ENABLE_CHECKING
+      {
+	unsigned i;
+	/* Make sure all the tables have been cleared out.  */
+	for (i = 0; i < num_ssa_names + 1; i++)
+	  {
+	    gcc_assert (table->partition_dependencies[i] == NULL);
+	    gcc_assert (table->expr_decl_uids[i] == NULL);
+	    if (i < num_var_partitions (map))
+	      gcc_assert (table->kill_list[i] == NULL);
+	  }
+      }
+#endif
+    }
+
+  ret = free_temp_expr_table (table);
+  return ret;
+}
+
+
+/* Dump TER expression table EXPR to file F.  */
+
+extern void
+dump_replaceable_exprs (FILE *f, tree *expr)
+{
+  tree stmt, var;
+  int x;
+
+  fprintf (f, "\nReplacing Expressions\n");
+  for (x = 0; x < (int)num_ssa_names; x++)
+    if (expr[x])
+      {
+        stmt = expr[x];
+	var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
+	gcc_assert (var != NULL_TREE);
+	print_generic_expr (f, var, TDF_SLIM);
+	fprintf (f, " replace with --> ");
+	print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
+	fprintf (f, "\n");
+      }
+  fprintf (f, "\n");
+}
+
+
+#ifdef ENABLE_CHECKING
+/* Dump the status of the various tables in the expression table.  This is used
+   exclusively to debug TER.  F is the place to send debug info and T is the
+   table being debugged.  */
+
+extern void
+debug_ter (FILE *f, temp_expr_table_p t)
+{
+  unsigned x, y;
+  bitmap_iterator bi;
+
+  fprintf (f, "\nDumping current state of TER\n virtual partition = %d\n", 
+	   VIRTUAL_PARTITION (t));
+  if (t->replaceable_expressions)
+    dump_replaceable_exprs (f, t->replaceable_expressions);
+  fprintf (f, "Currently tracking the following expressions:\n");
+
+  for (x = 1; x < num_ssa_names; x++)
+    if (t->expr_decl_uids[x])
+      {
+        print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
+        fprintf (f, " dep-parts : ");
+	if (t->partition_dependencies[x] 
+	    && !bitmap_empty_p (t->partition_dependencies[x]))
+	  {
+	    EXECUTE_IF_SET_IN_BITMAP (t->partition_dependencies[x], 0, y, bi)
+	      fprintf (f, "P%d ",y);
+	  }
+	fprintf (stderr, "   basedecls: ");
+	EXECUTE_IF_SET_IN_BITMAP (t->expr_decl_uids[x], 0, y, bi)
+	  fprintf (f, "%d ",y);
+	fprintf (stderr, "\n");
+      }
+
+  bitmap_print (f, t->partition_in_use, "Partitions in use ", 
+		"\npartition KILL lists:\n");
+
+  for (x = 0; x <= num_var_partitions (t->map); x++)
+    if (t->kill_list[x])
+      {
+        fprintf (f, "Partition %d : ", x);
+	EXECUTE_IF_SET_IN_BITMAP (t->kill_list[x], 0, y, bi)
+	  fprintf (f, "_%d ",y);
+      }
+
+  fprintf (f, "\n----------\n");
+}
+#endif