This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] TER : Temporary expression replacement checked in.
- From: Andrew MacLeod <amacleod at redhat dot com>
- To: gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: 14 Nov 2003 11:51:14 -0500
- Subject: [tree-ssa] TER : Temporary expression replacement checked in.
Finally. Im checking this in now. I had to add a change to
invert_truthvalue so that we didnt ignore a cast to BOOLEAN and proceed
on to an abort when the fodler gets something like
(_Bool)variable
GIMPLE temps which are used only once are replaced with their definingn
expression, if its safe to do so.
Generated code is cleaned up quite a bit, we have less spilling and
temporary variables. We're still short of mainline in a few cases, I am
looking at those next.
Other than that, this bootstrap, verifies, etc on x86. Its on by
default, but can be turned off with '-fno-tree-ter' if problems on other
architectures arise. Hopefully there won't be any. I will fix ASAP any
problems anyone encounters.
Andrew
2003-11-14 Andrew MacLeod <amacleod@redhat.com>
* common.opt (ftree-ter): Document new option.
* flags.h (flag_tree_ter): Add new flag.
* fold-const.c (invert_truthvalue): Don't ignore cast to BOOLEAN_TYPE.
* opts.c (decode_options): Option -ftree-ter defaults to on.
(common_handle_option): Add processing for flag_tree_ter.
* toplev.c (flag_tree_ter): Initialize to 0.
(lang_independent_options f_): Add -ftree-ter flag.
* tree-ssa-live.c (init_var_map): Initialize ref_count to 0.
(delete_var_map): Free ref count if allocated.
(register_ssa_partition): Add "is_use" parameter for reference counting.
(create_ssa_var_map): Add flag and code for calculating ref counts.
* tree-ssa-live.h (struct _var_map): Add ref_count field.
(SSA_VAR_MAP_REF_COUNT): Define flag.
(version_ref_count): Function to retreive ref_count.
* tree-ssa.c (replace_variable): If an expression vector is passed in,
use replacement expression instead of mapped variable when available.
(struct value_expr_d): New structure for value lists.
(struct temp_expr_table_d): Structure used to build an expression
replacement table.
(new_temp_expr_table): New. Create a new TER (Temporary Expression
Replacement) table.
(free_temp_expr_table): New. Free a TER table.
(new_value_expr): New. Allocate a value list element.
(free_value_expr): New. Free a value list element.
(find_value_in_list): New. Find a value in a list.
(add_value_to_list): New. Add a value to a list if not already present.
(remove_value_from_list): New. Remove a value from a list.
(add_dependance): New. Add a dependency to an expression.
(check_replaceable): New. Check if a stmt is a candidate for TER. Add
to active list and create dependancies if so.
(finish_expr): New. Remove an expression from TER consideration.
(mark_replaceable): New. Finish a TER expression as a valid replacement.
(kill_expr): New. Finish dependent TER expressions as not replaceable.
(kill_virtual_exprs): New. Finish any TER expressions dependent on a
virtual operand as not replaceable.
(find_replaceable_in_bb): New. Process a basic block for TER expression.
(find_replaceable_exprs): New. Entry point for TER expression finder.
(dump_replaceable_exprs): New. output list of replaceable expressions.
(rewrite_out_of_ssa): Build TER table if requested, and use it.
Index: common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.14.2.8
diff -c -p -r1.14.2.8 common.opt
*** common.opt 28 Oct 2003 14:56:10 -0000 1.14.2.8
--- common.opt 14 Nov 2003 16:17:52 -0000
*************** ftree-combine-temps
*** 723,728 ****
--- 723,732 ----
Common
Coalesce memory temporaries in the SSA->normal pass
+ ftree-ter
+ Common
+ Replace temporary expressions in the SSA->normal pass
+
ftree-dominator-opts
Common
Enable dominator optimizations
Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.86.2.37
diff -c -p -r1.86.2.37 flags.h
*** flags.h 28 Oct 2003 14:56:17 -0000 1.86.2.37
--- flags.h 14 Nov 2003 16:17:52 -0000
*************** extern int flag_tree_dce;
*** 731,736 ****
--- 731,739 ----
/* Enable SSA->normal pass memory location coalescing. */
extern int flag_tree_combine_temps;
+ /* Enable SSA->normal pass expression replacement. */
+ extern int flag_tree_ter;
+
/* Enable dominator optimizations while re-writing into SSA form. */
extern int flag_tree_dom;
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.213.2.62
diff -c -p -r1.213.2.62 fold-const.c
*** fold-const.c 13 Nov 2003 02:37:53 -0000 1.213.2.62
--- fold-const.c 14 Nov 2003 16:17:54 -0000
*************** invert_truthvalue (tree arg)
*** 2527,2532 ****
--- 2527,2535 ----
return invert_truthvalue (TREE_OPERAND (arg, 0));
case NOP_EXPR:
+ if (TREE_CODE (TREE_TYPE (arg)) == BOOLEAN_TYPE)
+ break;
+
case CONVERT_EXPR:
case FLOAT_EXPR:
return build1 (TREE_CODE (arg), type,
Index: opts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/opts.c,v
retrieving revision 1.31.2.16
diff -c -p -r1.31.2.16 opts.c
*** opts.c 13 Nov 2003 02:37:56 -0000 1.31.2.16
--- opts.c 14 Nov 2003 16:17:54 -0000
*************** decode_options (unsigned int argc, const
*** 538,543 ****
--- 538,544 ----
flag_tree_dom = 1;
flag_tree_must_alias = 1;
flag_tree_pre = 1;
+ flag_tree_ter = 1;
}
if (optimize >= 2)
*************** common_handle_option (size_t scode, cons
*** 1418,1423 ****
--- 1419,1428 ----
case OPT_ftree_combine_temps:
flag_tree_combine_temps = value;
+ break;
+
+ case OPT_ftree_ter:
+ flag_tree_ter = value;
break;
case OPT_ftree_dominator_opts:
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.654.2.74
diff -c -p -r1.654.2.74 toplev.c
*** toplev.c 13 Nov 2003 02:38:00 -0000 1.654.2.74
--- toplev.c 14 Nov 2003 16:17:55 -0000
*************** int flag_tree_must_alias = 0;
*** 1005,1010 ****
--- 1005,1013 ----
/* Enable SSA->normal pass memory location coalescing. */
int flag_tree_combine_temps = 0;
+ /* Enable SSA->normal pass expression replacement. */
+ int flag_tree_ter = 0;
+
/* Enable dominator optimizations while re-writing into SSA form. */
int flag_tree_dom = 0;
*************** static const lang_independent_options f_
*** 1208,1213 ****
--- 1211,1217 ----
{ "tree-dce", &flag_tree_dce, 1 },
{ "tree-dominator-opts", &flag_tree_dom, 1 },
{ "tree-combine-temps", &flag_tree_combine_temps, 1 },
+ { "tree-ter", &flag_tree_ter, 1 },
{ "tree-must-alias", &flag_tree_must_alias, 1 }
};
Index: tree-ssa-live.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-live.c,v
retrieving revision 1.1.2.24
diff -c -p -r1.1.2.24 tree-ssa-live.c
*** tree-ssa-live.c 12 Nov 2003 22:06:26 -0000 1.1.2.24
--- tree-ssa-live.c 14 Nov 2003 16:17:55 -0000
*************** static tree_live_info_p new_tree_live_in
*** 44,50 ****
static inline void set_if_valid (var_map, bitmap, tree);
static inline void add_livein_if_notdef (tree_live_info_p, bitmap,
tree, basic_block);
! static inline void register_ssa_partition (var_map, tree);
static inline void add_conflicts_if_valid (tpa_p, conflict_graph,
var_map, bitmap, tree);
static partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool);
--- 44,50 ----
static inline void set_if_valid (var_map, bitmap, tree);
static inline void add_livein_if_notdef (tree_live_info_p, bitmap,
tree, basic_block);
! static inline void register_ssa_partition (var_map, tree, bool);
static inline void add_conflicts_if_valid (tpa_p, conflict_graph,
var_map, bitmap, tree);
static partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool);
*************** init_var_map (int size)
*** 78,83 ****
--- 78,84 ----
map->compact_to_partition = NULL;
map->num_partitions = size;
map->partition_size = size;
+ map->ref_count = NULL;
return map;
}
*************** delete_var_map (var_map map)
*** 92,97 ****
--- 93,100 ----
free (map->partition_to_compact);
if (map->compact_to_partition)
free (map->compact_to_partition);
+ if (map->ref_count)
+ free (map->ref_count);
free (map);
}
*************** delete_var_map (var_map map)
*** 99,105 ****
manager. Any unregistered partitions may be compacted out later. */
static inline void
! register_ssa_partition (var_map map, tree ssa_var)
{
tree stmt, arg;
int version, i;
--- 102,108 ----
manager. Any unregistered partitions may be compacted out later. */
static inline void
! register_ssa_partition (var_map map, tree ssa_var, bool is_use)
{
tree stmt, arg;
int version, i;
*************** register_ssa_partition (var_map map, tre
*** 110,115 ****
--- 113,121 ----
#endif
version = SSA_NAME_VERSION (ssa_var);
+ if (is_use && map->ref_count)
+ map->ref_count[version]++;
+
if (map->partition_to_var[version] == NULL_TREE)
{
map->partition_to_var[SSA_NAME_VERSION (ssa_var)] = ssa_var;
*************** register_ssa_partition (var_map map, tre
*** 121,127 ****
{
arg = PHI_ARG_DEF (stmt, i);
if (phi_ssa_name_p (arg))
! register_ssa_partition (map, arg);
}
}
}
--- 127,133 ----
{
arg = PHI_ARG_DEF (stmt, i);
if (phi_ssa_name_p (arg))
! register_ssa_partition (map, arg, true);
}
}
}
*************** change_partition_var (var_map map, tree
*** 313,319 ****
need to have entries in the partition table. */
var_map
! create_ssa_var_map (void)
{
block_stmt_iterator bsi;
basic_block bb;
--- 319,325 ----
need to have entries in the partition table. */
var_map
! create_ssa_var_map (int flags)
{
block_stmt_iterator bsi;
basic_block bb;
*************** create_ssa_var_map (void)
*** 338,345 ****
--- 344,370 ----
sbitmap_zero (used_in_virtual_ops);
#endif
+ if (flags & SSA_VAR_MAP_REF_COUNT)
+ {
+ map->ref_count = (int *)xmalloc (((next_ssa_version + 1) * sizeof (int)));
+ memset (map->ref_count, 0, (next_ssa_version + 1) * sizeof (int));
+ }
+
FOR_EACH_BB (bb)
{
+ if (flags & SSA_VAR_MAP_REF_COUNT)
+ {
+ tree phi, arg;
+ int x;
+ for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (x = 0; x < PHI_NUM_ARGS (phi); x++)
+ {
+ arg = PHI_ARG_DEF (phi, x);
+ if (TREE_CODE (arg) == SSA_NAME)
+ map->ref_count[SSA_NAME_VERSION (arg)]++;
+ }
+ }
+
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
stmt = bsi_stmt (bsi);
*************** create_ssa_var_map (void)
*** 351,357 ****
for (x = 0; ops && x < VARRAY_ACTIVE_SIZE (ops); x++)
{
use = VARRAY_TREE_PTR (ops, x);
! register_ssa_partition (map, *use);
#if defined ENABLE_CHECKING
SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*use))->uid);
#endif
--- 376,382 ----
for (x = 0; ops && x < VARRAY_ACTIVE_SIZE (ops); x++)
{
use = VARRAY_TREE_PTR (ops, x);
! register_ssa_partition (map, *use, true);
#if defined ENABLE_CHECKING
SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*use))->uid);
#endif
*************** create_ssa_var_map (void)
*** 361,367 ****
for (x = 0; ops && x < VARRAY_ACTIVE_SIZE (ops); x++)
{
dest = VARRAY_TREE_PTR (ops, x);
! register_ssa_partition (map, *dest);
#if defined ENABLE_CHECKING
SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*dest))->uid);
#endif
--- 386,392 ----
for (x = 0; ops && x < VARRAY_ACTIVE_SIZE (ops); x++)
{
dest = VARRAY_TREE_PTR (ops, x);
! register_ssa_partition (map, *dest, false);
#if defined ENABLE_CHECKING
SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*dest))->uid);
#endif
Index: tree-ssa-live.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-live.h,v
retrieving revision 1.1.2.9
diff -c -p -r1.1.2.9 tree-ssa-live.h
*** tree-ssa-live.h 22 Oct 2003 20:28:25 -0000 1.1.2.9
--- tree-ssa-live.h 14 Nov 2003 16:17:55 -0000
*************** typedef struct _var_map
*** 41,46 ****
--- 41,49 ----
/* Original partition size. */
unsigned int partition_size;
+
+ /* Reference count, if required. */
+ int *ref_count;
} *var_map;
#define VAR_ANN_PARTITION(ann) (ann->partition)
*************** extern void delete_var_map (var_map);
*** 58,71 ****
extern void dump_var_map (FILE *, var_map);
extern int var_union (var_map, tree, tree);
extern void change_partition_var (var_map, tree, int);
- extern var_map create_ssa_var_map (void);
extern void compact_var_map (var_map, int);
static inline int num_var_partitions (var_map);
static inline tree var_to_partition_to_var (var_map, tree);
static inline tree partition_to_var (var_map, int);
static inline int var_to_partition (var_map, tree);
/* Number of partitions. */
static inline int
--- 61,76 ----
extern void dump_var_map (FILE *, var_map);
extern int var_union (var_map, tree, tree);
extern void change_partition_var (var_map, tree, int);
extern void compact_var_map (var_map, int);
static inline int num_var_partitions (var_map);
static inline tree var_to_partition_to_var (var_map, tree);
static inline tree partition_to_var (var_map, int);
static inline int var_to_partition (var_map, tree);
+ static inline int version_ref_count (var_map, tree);
+ #define SSA_VAR_MAP_REF_COUNT 0x01
+ extern var_map create_ssa_var_map (int);
/* Number of partitions. */
static inline int
*************** num_var_partitions (var_map map)
*** 74,79 ****
--- 79,94 ----
return map->num_partitions;
}
+ static inline int
+ version_ref_count (var_map map, tree ssa_var)
+ {
+ int version = SSA_NAME_VERSION (ssa_var);
+ #ifdef ENABLE_CHECKING
+ if (!map->ref_count)
+ abort ();
+ #endif
+ return map->ref_count[version];
+ }
/* Given a partition number, return the variable which represents that
partition. */
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.151
diff -c -p -r1.1.4.151 tree-ssa.c
*** tree-ssa.c 12 Nov 2003 23:33:07 -0000 1.1.4.151
--- tree-ssa.c 14 Nov 2003 16:17:56 -0000
*************** static void elim_create (elim_graph, int
*** 219,225 ****
static void eliminate_phi (edge, int, elim_graph);
static tree_live_info_p coalesce_ssa_name (var_map);
static void assign_vars (var_map);
! static void replace_variable (var_map, tree *);
static void eliminate_extraneous_phis (var_map);
static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p);
static void print_exprs (FILE *, const char *, tree, const char *, tree,
--- 219,225 ----
static void eliminate_phi (edge, int, elim_graph);
static tree_live_info_p coalesce_ssa_name (var_map);
static void assign_vars (var_map);
! static void replace_variable (var_map, tree *, tree *);
static void eliminate_extraneous_phis (var_map);
static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p);
static void print_exprs (FILE *, const char *, tree, const char *, tree,
*************** assign_vars (var_map map)
*** 1603,1613 ****
/* Replace *p with whatever variable it has been rewritten to. */
static inline void
! replace_variable (var_map map, tree *p)
{
tree new_var;
tree var = *p;
new_var = var_to_partition_to_var (map, var);
if (new_var)
{
--- 1603,1627 ----
/* Replace *p with whatever variable it has been rewritten to. */
static inline void
! replace_variable (var_map map, tree *p, tree *expr)
{
tree new_var;
tree var = *p;
+ /* Check if we are replacing this variable with an expression. */
+ if (expr)
+ {
+ int version = SSA_NAME_VERSION (*p);
+ if (expr[version])
+ {
+ tree new_expr = TREE_OPERAND (expr[version], 1);
+ *p = new_expr;
+ /* Clear the stmt's RHS, or GC might bite us. */
+ TREE_OPERAND (expr[version], 1) = NULL_TREE;
+ return;
+ }
+ }
+
new_var = var_to_partition_to_var (map, var);
if (new_var)
{
*************** coalesce_vars (var_map map, tree_live_in
*** 1743,1748 ****
--- 1757,2318 ----
}
+ /* 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 deteremined 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 VDEF 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. */
+
+ /* Dependancy 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;
+ 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 dependancy on VDEFs. */
+ #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_dependance (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. */
+ static temp_expr_table_p
+ new_temp_expr_table (var_map map)
+ {
+ temp_expr_table_p t;
+
+ t = (temp_expr_table_p) xmalloc (sizeof (struct temp_expr_table_d));
+ t->map = map;
+
+ t->version_info = xcalloc (next_ssa_version + 1, sizeof (void *));
+ t->partition_dep_list = xcalloc (num_var_partitions (map) + 1,
+ sizeof (value_expr_p));
+
+ t->replaceable = BITMAP_XMALLOC ();
+ t->partition_in_use = BITMAP_XMALLOC ();
+
+ t->saw_replaceable = false;
+ t->virtual_partition = num_var_partitions (map);
+ t->free_list = NULL;
+ t->pending_dependence = NULL;
+
+ return t;
+ }
+
+
+ /* Free a TER table. 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;
+
+ #ifdef ENABLE_CHECKING
+ int x;
+ for (x = 0; x <= num_var_partitions (t->map); x++)
+ if (t->partition_dep_list[x] != NULL)
+ abort();
+ #endif
+
+ while ((p = t->free_list))
+ {
+ t->free_list = p->next;
+ free (p);
+ }
+
+ BITMAP_XFREE (t->partition_in_use);
+ BITMAP_XFREE (t->replaceable);
+
+ 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 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 a value list node to the free list. */
+ 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 a specific value if its in a list. Return a pointer to the list
+ object if found. Return NULL if it isn't. 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 a value to a list, if it isn't already present. */
+ 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 a value node if it's value isn't already in the list. Free this node if
+ it is already in the list. */
+ 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 a value in a 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 dependancy between the def of an SSA version and the partitions each
+ use in the expression represent. */
+ static void
+ add_dependance (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);
+ #ifdef ENABLE_CHECKING
+ if (i== NO_PARTITION)
+ abort ();
+ #endif
+ 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 an expression is suitable for replacement. If so, create an
+ expression entry. Return true if this stmt is replaceable. */
+ static bool
+ check_replaceable (temp_expr_table_p tab, tree stmt)
+ {
+ stmt_ann_t ann;
+ varray_type ops, vuseops;
+ tree var, def;
+ int num_ops, version, i;
+ var_map map = tab->map;
+
+ if (TREE_CODE (stmt) != MODIFY_EXPR)
+ return false;
+
+ ann = stmt_ann (stmt);
+ ops = def_ops (ann);
+
+ /* Punt if there is more than 1 def, or more than 1 use. */
+ if (!ops || VARRAY_ACTIVE_SIZE (ops) != 1)
+ return false;
+ def = *VARRAY_TREE_PTR (ops, 0);
+ if (version_ref_count (map, def) != 1)
+ return false;
+
+ /* There must be no VDEFS. */
+ if (vdef_ops (ann) && VARRAY_ACTIVE_SIZE (vdef_ops (ann)) != 0)
+ return false;
+
+ /* Float expressions must go through memory if float-store is on. */
+ if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
+ return false;
+
+ ops = use_ops (ann);
+ num_ops = ops ? VARRAY_ACTIVE_SIZE (ops) : 0;
+ vuseops = vuse_ops (ann);
+
+ /* Any expression which has no virtual operands and no real operands
+ should have been propagated if its possible to do anythig with them.
+ If this happens here, it probably exists that way for a reason, so we
+ won't touch it. An example is:
+ b_4 = &tab
+ There are no virtual uses nor any real uses, so we just leave this
+ alone to be safe. */
+
+ if (num_ops == 0 && (!vuseops || VARRAY_ACTIVE_SIZE (vuseops) == 0))
+ return false;
+
+ version = SSA_NAME_VERSION (def);
+
+ /* Add this expression to the dependancy list for each use partition. */
+ for (i = 0; i < num_ops; i++)
+ {
+ var = *VARRAY_TREE_PTR (ops, i);
+ add_dependance (tab, version, var);
+ }
+
+ /* If there are VUSES, add a dependence on virtual defs. */
+ if (vuseops && VARRAY_ACTIVE_SIZE (vuseops) != 0)
+ {
+ 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 an expression from replacement consideration. 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 dependance
+ 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;
+ #ifdef ENABLE_CHECKING
+ if (tab->partition_dep_list[partition] == NULL)
+ abort ();
+ #endif
+ tmp = remove_value_from_list (&(tab->partition_dep_list[partition]),
+ version);
+ #ifdef ENABLE_CHECKING
+ if (!tmp)
+ abort ();
+ #endif
+ free_value_expr (tab, tmp);
+ /* Only clear the bit when the dependancy 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
+ {
+ #ifdef ENABLE_CHECKING
+ if (bitmap_bit_p (tab->replaceable, version))
+ abort ();
+ #endif
+ tab->version_info[version] = NULL;
+ }
+ }
+
+
+ /* Mark the expression associated with a variable as replaceable, and enter
+ the defining stmt into the version_info table. */
+ 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 finishes any expression which is dependent on this paritition
+ as NOT replaceable. clear_bit is used to determine whether partition_in_use
+ should have iuts bit cleared. Since this 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 dependant 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 which are dependant on virtual DEFs. */
+ 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 a basic block, and looks for variables which can
+ be replaced by their expressions. */
+ static void
+ find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
+ {
+ block_stmt_iterator bsi;
+ tree stmt, def;
+ stmt_ann_t ann;
+ int partition, num, i;
+ varray_type ops;
+ var_map map = tab->map;
+ value_expr_p p;
+
+ 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. */
+ ops = use_ops (ann);
+ num = (ops ? VARRAY_ACTIVE_SIZE (ops) : 0);
+ for (i = 0; i < num; i++)
+ {
+ def = *VARRAY_TREE_PTR (ops, i);
+ if (tab->version_info[SSA_NAME_VERSION (def)])
+ mark_replaceable (tab, def);
+ }
+
+ /* Next, see if this stmt kills off an active expression. */
+ ops = def_ops (ann);
+ num = (ops ? VARRAY_ACTIVE_SIZE (ops) : 0);
+ for (i = 0; i < num; i++)
+ {
+ def = *VARRAY_TREE_PTR (ops, i);
+ 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. */
+ check_replaceable (tab, stmt);
+
+ /* Free any unused dependancy lists. */
+ while ((p = tab->pending_dependence))
+ {
+ tab->pending_dependence = p->next;
+ free_value_expr (tab, p);
+ }
+
+ /* A VDEF kills any expression using a virtual operand. */
+ if (vdef_ops (ann) && VARRAY_ACTIVE_SIZE (vdef_ops (ann)) > 0)
+ kill_virtual_exprs (tab, true);
+ }
+ }
+
+
+ /* This function is the driver routine for replacement of temporary expressions
+ in the SSA->normal phase. 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. */
+ static tree *
+ find_replaceable_exprs (var_map map)
+ {
+ basic_block bb;
+ int i;
+ temp_expr_table_p table;
+ tree *ret;
+
+ table = new_temp_expr_table (map);
+ FOR_EACH_BB (bb)
+ {
+ find_replaceable_in_bb (table, bb);
+ EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i,
+ {
+ kill_expr (table, i, false);
+ });
+ }
+
+ ret = free_temp_expr_table (table);
+ return ret;
+ }
+
+
+ /* Dump the TER expression table. */
+ static void
+ dump_replaceable_exprs (FILE *f, tree *expr)
+ {
+ tree stmt, var;
+ int x;
+ fprintf (f, "\nReplacing Expressions\n");
+ for (x = 0; x < (int)next_ssa_version + 1; x++)
+ if (expr[x])
+ {
+ stmt = expr[x];
+ var = *VARRAY_TREE_PTR (def_ops (stmt_ann (stmt)), 0);
+ 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");
+ }
+
+
/* Take function FNDECL out of SSA form.
PHASE indicates which dump file from the DUMP_FILES array to use when
*************** rewrite_out_of_ssa (tree fndecl, enum tr
*** 1758,1763 ****
--- 2328,2335 ----
tree phi, next;
elim_graph g;
tree_live_info_p liveinfo;
+ tree *values = NULL;
+ int var_flags = 0;
timevar_push (TV_TREE_SSA_TO_NORMAL);
*************** rewrite_out_of_ssa (tree fndecl, enum tr
*** 1766,1772 ****
if (dump_file && (dump_flags & TDF_DETAILS))
dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
! map = create_ssa_var_map ();
eliminate_extraneous_phis (map);
/* Shrink the map to include only referenced variables. */
--- 2338,2346 ----
if (dump_file && (dump_flags & TDF_DETAILS))
dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
! if (flag_tree_ter)
! var_flags = SSA_VAR_MAP_REF_COUNT;
! map = create_ssa_var_map (var_flags);
eliminate_extraneous_phis (map);
/* Shrink the map to include only referenced variables. */
*************** rewrite_out_of_ssa (tree fndecl, enum tr
*** 1798,1803 ****
--- 2372,2384 ----
dump_var_map (dump_file, map);
}
+ if (flag_tree_ter)
+ {
+ values = find_replaceable_exprs (map);
+ if (values && dump_file && (dump_flags & TDF_DETAILS))
+ dump_replaceable_exprs (dump_file, values);
+ }
+
if (flag_tree_combine_temps && liveinfo)
{
coalesce_vars (map, liveinfo);
*************** rewrite_out_of_ssa (tree fndecl, enum tr
*** 1838,1862 ****
for (i = 0; i < num_uses; i++)
{
use_p = VARRAY_TREE_PTR (ops, i);
! replace_variable (map, use_p);
}
ops = def_ops (ann);
num_defs = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
! for (i = 0; i < num_defs; i++)
{
! tree *def_p = VARRAY_TREE_PTR (ops, i);
! *def_p = var_to_partition_to_var (map, *def_p);
! replace_variable (map, def_p);
!
! if (is_copy
! && num_uses == 1
! && use_p
! && def_p
! && (*def_p == *use_p))
remove = 1;
}
/* Remove copies of the form 'var = var'. */
if (remove)
--- 2419,2452 ----
for (i = 0; i < num_uses; i++)
{
use_p = VARRAY_TREE_PTR (ops, i);
! replace_variable (map, use_p, values);
}
ops = def_ops (ann);
num_defs = ((ops) ? VARRAY_ACTIVE_SIZE (ops) : 0);
! if (values && num_defs == 1)
{
! tree def = *VARRAY_TREE_PTR (ops, 0);
! tree val;
! val = values[SSA_NAME_VERSION (def)];
! if (val)
remove = 1;
}
+ if (!remove)
+ for (i = 0; i < num_defs; i++)
+ {
+ tree *def_p = VARRAY_TREE_PTR (ops, i);
+ *def_p = var_to_partition_to_var (map, *def_p);
+ replace_variable (map, def_p, NULL);
+
+ if (is_copy
+ && num_uses == 1
+ && use_p
+ && def_p
+ && (*def_p == *use_p))
+ remove = 1;
+ }
/* Remove copies of the form 'var = var'. */
if (remove)
*************** rewrite_out_of_ssa (tree fndecl, enum tr
*** 1879,1884 ****
--- 2469,2477 ----
}
delete_elim_graph (g);
+
+ if (values)
+ free (values);
/* If any copies were inserted on edges, actually insert them now. */
bsi_commit_edge_inserts (0, NULL);