RFC: expand from SSA form (2/2)
Michael Matz
matz@suse.de
Mon Apr 13 20:55:00 GMT 2009
Hi,
and this is the cleanup patch, removing all the if (0) things and
commented out cruft and dead functions.
One nice thing is that we also don't need the partition number in the var
annotation anymore.
This also fixes some bugs where we access sometimes iterate until
num_ssanames+1, where in reality the ssa name versions lie in
[1, num_ssanames). We now can also rely on the fact that all variables
for a partition are SSA_NAMEs.
Ignore the compact_ssa_names() routine, it's from an attempt to get rid
also of the view on top of the partitioning (at least during expand).
Ciao,
Michael.
--
Index: gcc/tree-ssa-coalesce.c
===================================================================
*** gcc.orig/tree-ssa-coalesce.c
--- gcc/tree-ssa-coalesce.c
*************** create_outofssa_var_map (coalesce_list_p
*** 974,980 ****
used_in_virtual_ops = BITMAP_ALLOC (NULL);
#endif
! map = init_var_map (num_ssa_names + 1);
FOR_EACH_BB (bb)
{
--- 974,980 ----
used_in_virtual_ops = BITMAP_ALLOC (NULL);
#endif
! map = init_var_map (num_ssa_names);
FOR_EACH_BB (bb)
{
*************** create_outofssa_var_map (coalesce_list_p
*** 1126,1133 ****
first = NULL_TREE;
for (i = 1; i < num_ssa_names; i++)
{
! var = map->partition_to_var[i];
! if (var != NULL_TREE)
{
/* Add coalesces between all the result decls. */
if (TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
--- 1126,1133 ----
first = NULL_TREE;
for (i = 1; i < num_ssa_names; i++)
{
! var = ssa_name (i);
! if (var != NULL_TREE && is_gimple_reg (var))
{
/* Add coalesces between all the result decls. */
if (TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
*************** create_outofssa_var_map (coalesce_list_p
*** 1148,1154 ****
/* Mark any default_def variables as being in the coalesce list
since they will have to be coalesced with the base variable. If
not marked as present, they won't be in the coalesce view. */
! if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var)
bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
}
}
--- 1148,1155 ----
/* Mark any default_def variables as being in the coalesce list
since they will have to be coalesced with the base variable. If
not marked as present, they won't be in the coalesce view. */
! if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var
! && !has_zero_uses (var))
bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
}
}
*************** eq_ssa_name_by_var (const void *p1, cons
*** 1329,1335 ****
extern var_map
coalesce_ssa_name (void)
{
- unsigned num, x;
tree_live_info_p liveinfo;
ssa_conflicts_p graph;
coalesce_list_p cl;
--- 1330,1335 ----
*************** coalesce_ssa_name (void)
*** 1406,1436 ****
/* First, coalesce all live on entry variables to their base variable.
This will ensure the first use is coming from the correct location. */
- num = num_var_partitions (map);
- for (x = 0 ; x < num; x++)
- {
- tree var = partition_to_var (map, x);
- tree root;
-
- if (TREE_CODE (var) != SSA_NAME)
- continue;
-
- root = SSA_NAME_VAR (var);
- if (gimple_default_def (cfun, root) == var)
- {
- /* This root variable should have not already been assigned
- to another partition which is not coalesced with this one. */
- gcc_assert (!var_ann (root)->out_of_ssa_tag);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- print_exprs (dump_file, "Must coalesce ", var,
- " with the root variable ", root, ".\n");
- }
- change_partition_var (map, root, x);
- }
- }
-
if (dump_file && (dump_flags & TDF_DETAILS))
dump_var_map (dump_file, map);
--- 1406,1411 ----
Index: gcc/tree-ssa-copyrename.c
===================================================================
*** gcc.orig/tree-ssa-copyrename.c
--- gcc/tree-ssa-copyrename.c
*************** rename_ssa_copies (void)
*** 291,297 ****
else
debug = NULL;
! map = init_var_map (num_ssa_names + 1);
FOR_EACH_BB (bb)
{
--- 291,297 ----
else
debug = NULL;
! map = init_var_map (num_ssa_names);
FOR_EACH_BB (bb)
{
*************** rename_ssa_copies (void)
*** 339,350 ****
/* Now one more pass to make all elements of a partition share the same
root variable. */
! for (x = 1; x <= num_ssa_names; x++)
{
part_var = partition_to_var (map, x);
if (!part_var)
continue;
! var = map->partition_to_var[x];
if (debug)
{
if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
--- 339,350 ----
/* Now one more pass to make all elements of a partition share the same
root variable. */
! for (x = 1; x < num_ssa_names; x++)
{
part_var = partition_to_var (map, x);
if (!part_var)
continue;
! var = ssa_name (x);
if (debug)
{
if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
Index: gcc/tree-ssa-live.h
===================================================================
*** gcc.orig/tree-ssa-live.h
--- gcc/tree-ssa-live.h
*************** typedef struct _var_map
*** 60,68 ****
int *partition_to_view;
int *view_to_partition;
- /* Mapping of partition numbers to variables. */
- tree *partition_to_var;
-
/* Current number of partitions in var_map based on the current view. */
unsigned int num_partitions;
--- 60,65 ----
*************** typedef struct _var_map
*** 80,87 ****
} *var_map;
- /* Partition number of a non ssa-name variable. */
- #define VAR_ANN_PARTITION(ann) (ann->partition)
/* Index to the basevar table of a non ssa-name variable. */
#define VAR_ANN_BASE_INDEX(ann) (ann->base_index)
--- 77,82 ----
*************** extern var_map init_var_map (int);
*** 93,99 ****
extern void delete_var_map (var_map);
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 partition_view_normal (var_map, bool);
extern void partition_view_bitmap (var_map, bitmap, bool);
#ifdef ENABLE_CHECKING
--- 88,93 ----
*************** num_var_partitions (var_map map)
*** 116,125 ****
static inline tree
partition_to_var (var_map map, int i)
{
if (map->view_to_partition)
i = map->view_to_partition[i];
i = partition_find (map->var_partition, i);
! return map->partition_to_var[i];
}
--- 110,121 ----
static inline tree
partition_to_var (var_map map, int i)
{
+ tree name;
if (map->view_to_partition)
i = map->view_to_partition[i];
i = partition_find (map->var_partition, i);
! name = ssa_name (i);
! return name;
}
*************** version_to_var (var_map map, int version
*** 146,168 ****
static inline int
var_to_partition (var_map map, tree var)
{
- var_ann_t ann;
int part;
! if (TREE_CODE (var) == SSA_NAME)
! {
! part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
! if (map->partition_to_view)
! part = map->partition_to_view[part];
! }
! else
! {
! ann = var_ann (var);
! if (ann && ann->out_of_ssa_tag)
! part = VAR_ANN_PARTITION (ann);
! else
! part = NO_PARTITION;
! }
return part;
}
--- 142,153 ----
static inline int
var_to_partition (var_map map, tree var)
{
int part;
! gcc_assert (TREE_CODE (var) == SSA_NAME);
! part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
! if (map->partition_to_view)
! part = map->partition_to_view[part];
return part;
}
*************** num_basevars (var_map map)
*** 207,223 ****
partitions may be filtered out by a view later. */
static inline void
! register_ssa_partition (var_map map, tree ssa_var)
{
- int version;
-
#if defined ENABLE_CHECKING
register_ssa_partition_check (ssa_var);
#endif
-
- version = SSA_NAME_VERSION (ssa_var);
- if (map->partition_to_var[version] == NULL_TREE)
- map->partition_to_var[version] = ssa_var;
}
--- 192,202 ----
partitions may be filtered out by a view later. */
static inline void
! register_ssa_partition (var_map map ATTRIBUTE_UNUSED, tree ssa_var)
{
#if defined ENABLE_CHECKING
register_ssa_partition_check (ssa_var);
#endif
}
Index: gcc/tree-ssa-ter.c
===================================================================
*** gcc.orig/tree-ssa-ter.c
--- gcc/tree-ssa-ter.c
*************** free_temp_expr_table (temp_expr_table_p
*** 225,231 ****
unsigned x;
for (x = 0; x <= num_var_partitions (t->map); x++)
gcc_assert (!t->kill_list[x]);
! for (x = 0; x < num_ssa_names + 1; x++)
{
gcc_assert (t->expr_decl_uids[x] == NULL);
gcc_assert (t->partition_dependencies[x] == NULL);
--- 225,231 ----
unsigned x;
for (x = 0; x <= num_var_partitions (t->map); x++)
gcc_assert (!t->kill_list[x]);
! for (x = 0; x < num_ssa_names; x++)
{
gcc_assert (t->expr_decl_uids[x] == NULL);
gcc_assert (t->partition_dependencies[x] == NULL);
Index: gcc/tree-ssa-live.c
===================================================================
*** gcc.orig/tree-ssa-live.c
--- gcc/tree-ssa-live.c
*************** init_var_map (int size)
*** 136,144 ****
map = (var_map) xmalloc (sizeof (struct _var_map));
map->var_partition = partition_new (size);
- map->partition_to_var
- = (tree *)xmalloc (size * sizeof (tree));
- memset (map->partition_to_var, 0, size * sizeof (tree));
map->partition_to_view = NULL;
map->view_to_partition = NULL;
--- 136,141 ----
*************** void
*** 157,163 ****
delete_var_map (var_map map)
{
var_map_base_fini (map);
- free (map->partition_to_var);
partition_delete (map->var_partition);
if (map->partition_to_view)
free (map->partition_to_view);
--- 154,159 ----
*************** int
*** 175,215 ****
var_union (var_map map, tree var1, tree var2)
{
int p1, p2, p3;
! tree root_var = NULL_TREE;
! tree other_var = NULL_TREE;
/* This is independent of partition_to_view. If partition_to_view is
on, then whichever one of these partitions is absorbed will never have a
dereference into the partition_to_view array any more. */
! if (TREE_CODE (var1) == SSA_NAME)
! p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
! else
! {
! p1 = var_to_partition (map, var1);
! if (map->view_to_partition)
! p1 = map->view_to_partition[p1];
! root_var = var1;
! }
!
! if (TREE_CODE (var2) == SSA_NAME)
! p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
! else
! {
! p2 = var_to_partition (map, var2);
! if (map->view_to_partition)
! p2 = map->view_to_partition[p2];
!
! /* If there is no root_var set, or it's not a user variable, set the
! root_var to this one. */
! if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var)))
! {
! other_var = root_var;
! root_var = var2;
! }
! else
! other_var = var2;
! }
gcc_assert (p1 != NO_PARTITION);
gcc_assert (p2 != NO_PARTITION);
--- 171,186 ----
var_union (var_map map, tree var1, tree var2)
{
int p1, p2, p3;
!
! gcc_assert (TREE_CODE (var1) == SSA_NAME);
! gcc_assert (TREE_CODE (var2) == SSA_NAME);
/* This is independent of partition_to_view. If partition_to_view is
on, then whichever one of these partitions is absorbed will never have a
dereference into the partition_to_view array any more. */
! p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
! p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
gcc_assert (p1 != NO_PARTITION);
gcc_assert (p2 != NO_PARTITION);
*************** var_union (var_map map, tree var1, tree
*** 222,232 ****
if (map->partition_to_view)
p3 = map->partition_to_view[p3];
- if (root_var)
- change_partition_var (map, root_var, p3);
- if (other_var)
- change_partition_var (map, other_var, p3);
-
return p3;
}
--- 193,198 ----
*************** partition_view_init (var_map map)
*** 278,284 ****
for (x = 0; x < map->partition_size; x++)
{
tmp = partition_find (map->var_partition, x);
! if (map->partition_to_var[tmp] != NULL_TREE && !bitmap_bit_p (used, tmp))
bitmap_set_bit (used, tmp);
}
--- 244,252 ----
for (x = 0; x < map->partition_size; x++)
{
tmp = partition_find (map->var_partition, x);
! if (ssa_name (tmp) != NULL_TREE && is_gimple_reg (ssa_name (tmp))
! && (!has_zero_uses (ssa_name (tmp))
! || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp))))
bitmap_set_bit (used, tmp);
}
*************** partition_view_fini (var_map map, bitmap
*** 297,303 ****
{
bitmap_iterator bi;
unsigned count, i, x, limit;
- tree var;
gcc_assert (selected);
--- 265,270 ----
*************** partition_view_fini (var_map map, bitmap
*** 317,327 ****
{
map->partition_to_view[x] = i;
map->view_to_partition[i] = x;
- var = map->partition_to_var[x];
- /* If any one of the members of a partition is not an SSA_NAME, make
- sure it is the representative. */
- if (TREE_CODE (var) != SSA_NAME)
- change_partition_var (map, var, i);
i++;
}
gcc_assert (i == count);
--- 284,289 ----
*************** partition_view_bitmap (var_map map, bitm
*** 379,404 ****
}
- /* This function is used to change the representative variable in MAP for VAR's
- partition to a regular non-ssa variable. This allows partitions to be
- mapped back to real variables. */
-
- void
- change_partition_var (var_map map, tree var, int part)
- {
- var_ann_t ann;
-
- return;
- gcc_assert (TREE_CODE (var) != SSA_NAME);
-
- ann = var_ann (var);
- ann->out_of_ssa_tag = 1;
- VAR_ANN_PARTITION (ann) = part;
- if (map->view_to_partition)
- map->partition_to_var[map->view_to_partition[part]] = var;
- }
-
-
static inline void mark_all_vars_used (tree *, void *data);
/* Helper function for mark_all_vars_used, called via walk_tree. */
--- 341,346 ----
*************** dump_var_map (FILE *f, var_map map)
*** 1104,1110 ****
else
p = x;
! if (map->partition_to_var[p] == NULL_TREE)
continue;
t = 0;
--- 1046,1052 ----
else
p = x;
! if (ssa_name (p) == NULL_TREE)
continue;
t = 0;
Index: gcc/tree-flow.h
===================================================================
*** gcc.orig/tree-flow.h
--- gcc/tree-flow.h
*************** struct var_ann_d GTY(())
*** 209,218 ****
{
struct tree_ann_common_d common;
- /* Used by the out of SSA pass to determine whether this variable has
- been seen yet or not. */
- unsigned out_of_ssa_tag : 1;
-
/* Used when building base variable structures in a var_map. */
unsigned base_var_processed : 1;
--- 209,214 ----
*************** struct var_ann_d GTY(())
*** 234,243 ****
information on each attribute. */
ENUM_BITFIELD (noalias_state) noalias_state : 2;
- /* Used when going out of SSA form to indicate which partition this
- variable represents storage for. */
- unsigned partition;
-
/* Used by var_map for the base index of ssa base variables. */
unsigned base_index;
--- 230,235 ----
Index: gcc/tree-outof-ssa.c
===================================================================
*** gcc.orig/tree-outof-ssa.c
--- gcc/tree-outof-ssa.c
*************** typedef struct _elim_graph {
*** 86,139 ****
} *elim_graph;
- /* Create a temporary variable based on the type of variable T. Use T's name
- as the prefix. */
-
- static tree
- create_temp (tree t)
- {
- tree tmp;
- const char *name = NULL;
- tree type;
-
- if (TREE_CODE (t) == SSA_NAME)
- t = SSA_NAME_VAR (t);
-
- gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL);
-
- type = TREE_TYPE (t);
- tmp = DECL_NAME (t);
- if (tmp)
- name = IDENTIFIER_POINTER (tmp);
-
- if (name == NULL)
- name = "temp";
- tmp = create_tmp_var (type, name);
-
- if (DECL_DEBUG_EXPR_IS_FROM (t) && DECL_DEBUG_EXPR (t))
- {
- SET_DECL_DEBUG_EXPR (tmp, DECL_DEBUG_EXPR (t));
- DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
- }
- else if (!DECL_IGNORED_P (t))
- {
- SET_DECL_DEBUG_EXPR (tmp, t);
- DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
- }
- DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
- DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t);
- DECL_GIMPLE_REG_P (tmp) = DECL_GIMPLE_REG_P (t);
- add_referenced_var (tmp);
-
- /* We should never have copied variables in non-automatic storage
- or variables that have their address taken. So it is pointless
- to try to copy call-clobber state here. */
- gcc_assert (!may_be_aliased (t) && !is_global_var (t));
-
- return tmp;
- }
-
-
/* Insert a copy instruction from partition SRC to DEST onto edge E. */
static void
--- 86,91 ----
*************** eliminate_phi (edge e, elim_graph g)
*** 595,648 ****
}
- /* Take the ssa-name var_map MAP, and assign real variables to each
- partition. */
-
- static void
- assign_vars (var_map map)
- {
- int x, num;
- tree var, root;
- var_ann_t ann;
-
- num = num_var_partitions (map);
- for (x = 0; x < num; x++)
- {
- var = partition_to_var (map, x);
- if (TREE_CODE (var) != SSA_NAME)
- {
- ann = var_ann (var);
- /* It must already be coalesced. */
- gcc_assert (ann->out_of_ssa_tag == 1);
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "partition %d already has variable ", x);
- print_generic_expr (dump_file, var, TDF_SLIM);
- fprintf (dump_file, " assigned to it.\n");
- }
- }
- else
- {
- root = SSA_NAME_VAR (var);
- ann = var_ann (root);
- /* If ROOT is already associated, create a new one. */
- if (ann->out_of_ssa_tag)
- {
- root = create_temp (root);
- ann = var_ann (root);
- }
- /* ROOT has not been coalesced yet, so use it. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Partition %d is assigned to var ", x);
- print_generic_stmt (dump_file, root, TDF_SLIM);
- }
- change_partition_var (map, root, x);
- }
- }
- }
-
-
/* Replace use operand P with whatever variable it has been rewritten to based
on the partitions in MAP. EXPR is an optional expression vector over SSA
versions which is used to replace P with an expression instead of a variable.
--- 547,552 ----
*************** eliminate_useless_phis (void)
*** 797,802 ****
--- 701,739 ----
}
+ static void
+ compact_ssa_names (void)
+ {
+ unsigned i, j;
+ j = 1;
+ for (i = 1; i < num_ssa_names; i++)
+ {
+ tree name = ssa_name (i);
+ if (!name || !is_gimple_reg (name))
+ {
+ if (name)
+ {
+ release_ssa_name (name);
+ }
+ continue;
+ }
+ if (j != i)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "SSA version %u becomes %u\n",
+ SSA_NAME_VERSION (name), j);
+ }
+ SSA_NAME_VERSION (name) = j;
+ VEC_replace (tree, SSANAMES (cfun),
+ SSA_NAME_VERSION (name), name);
+ }
+ j++;
+ }
+ if (j != num_ssa_names)
+ VEC_truncate (tree, SSANAMES (cfun), j);
+ }
+
/* 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
*************** eliminate_useless_phis (void)
*** 804,824 ****
variable. */
static void
! rewrite_trees (var_map map, gimple *values)
{
- elim_graph g;
- basic_block bb;
- gimple_stmt_iterator gsi;
- edge e;
- gimple_seq phi;
- bool changed;
-
#ifdef ENABLE_CHECKING
/* Search for PHIs where the destination has no partition, but one
or more arguments has a partition. This should not happen and can
create incorrect code. */
FOR_EACH_BB (bb)
{
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple phi = gsi_stmt (gsi);
--- 741,756 ----
variable. */
static void
! rewrite_trees (var_map map)
{
#ifdef ENABLE_CHECKING
+ basic_block bb;
/* Search for PHIs where the destination has no partition, but one
or more arguments has a partition. This should not happen and can
create incorrect code. */
FOR_EACH_BB (bb)
{
+ gimple_stmt_iterator gsi;
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple phi = gsi_stmt (gsi);
*************** rewrite_trees (var_map map, gimple *valu
*** 844,931 ****
}
}
#endif
-
- /* Replace PHI nodes with any required copies. */
- g = new_elim_graph (map->num_partitions);
- g->map = map;
- FOR_EACH_BB (bb)
- {
- if (0)
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
- {
- gimple stmt = gsi_stmt (gsi);
- use_operand_p use_p, copy_use_p;
- def_operand_p def_p;
- bool remove = false, is_copy = false;
- int num_uses = 0;
- ssa_op_iter iter;
-
- changed = false;
-
- if (gimple_assign_copy_p (stmt))
- is_copy = true;
-
- copy_use_p = NULL_USE_OPERAND_P;
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
- {
- if (replace_use_variable (map, use_p, values))
- changed = true;
- copy_use_p = use_p;
- num_uses++;
- }
-
- if (num_uses != 1)
- is_copy = false;
-
- def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
-
- if (def_p != NULL)
- {
- /* Mark this stmt for removal if it is the list of replaceable
- expressions. */
- if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))])
- remove = true;
- else
- {
- if (replace_def_variable (map, def_p, NULL))
- changed = true;
- /* If both SSA_NAMEs coalesce to the same variable,
- mark the now redundant copy for removal. */
- if (is_copy)
- {
- gcc_assert (copy_use_p != NULL_USE_OPERAND_P);
- if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p))
- remove = true;
- }
- }
- }
- else
- FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
- if (replace_def_variable (map, def_p, NULL))
- changed = true;
-
- /* Remove any stmts marked for removal. */
- if (remove)
- gsi_remove (&gsi, true);
- else
- {
- if (changed)
- if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
- gimple_purge_dead_eh_edges (bb);
- gsi_next (&gsi);
- }
- }
-
- phi = phi_nodes (bb);
- if (0 && phi)
- {
- edge_iterator ei;
- FOR_EACH_EDGE (e, ei, bb->preds)
- eliminate_phi (e, g);
- }
- }
-
- delete_elim_graph (g);
}
void
--- 776,781 ----
*************** expand_phi_nodes (struct ssaexpand *sa)
*** 944,1455 ****
}
- /* These are the local work structures used to determine the best place to
- insert the copies that were placed on edges by the SSA->normal pass.. */
- static VEC(edge,heap) *edge_leader;
- static VEC(gimple_seq,heap) *stmt_list;
- static bitmap leader_has_match = NULL;
- static edge leader_match = NULL;
-
-
- /* Pass this function to make_forwarder_block so that all the edges with
- matching PENDING_STMT lists to 'curr_stmt_list' get redirected. E is the
- edge to test for a match. */
-
- static inline bool
- same_stmt_list_p (edge e)
- {
- return (e->aux == (PTR) leader_match) ? true : false;
- }
-
-
- /* Return TRUE if S1 and S2 are equivalent copies. */
-
- static inline bool
- identical_copies_p (const_gimple s1, const_gimple s2)
- {
- #ifdef ENABLE_CHECKING
- gcc_assert (is_gimple_assign (s1));
- gcc_assert (is_gimple_assign (s2));
- gcc_assert (DECL_P (gimple_assign_lhs (s1)));
- gcc_assert (DECL_P (gimple_assign_lhs (s2)));
- #endif
-
- if (gimple_assign_lhs (s1) != gimple_assign_lhs (s2))
- return false;
-
- if (gimple_assign_rhs1 (s1) != gimple_assign_rhs1 (s2))
- return false;
-
- return true;
- }
-
-
- /* Compare the PENDING_STMT list for edges E1 and E2. Return true if the lists
- contain the same sequence of copies. */
-
- static inline bool
- identical_stmt_lists_p (const_edge e1, const_edge e2)
- {
- gimple_seq t1 = PENDING_STMT (e1);
- gimple_seq t2 = PENDING_STMT (e2);
- gimple_stmt_iterator gsi1, gsi2;
-
- for (gsi1 = gsi_start (t1), gsi2 = gsi_start (t2);
- !gsi_end_p (gsi1) && !gsi_end_p (gsi2);
- gsi_next (&gsi1), gsi_next (&gsi2))
- {
- if (!identical_copies_p (gsi_stmt (gsi1), gsi_stmt (gsi2)))
- break;
- }
-
- if (!gsi_end_p (gsi1) || !gsi_end_p (gsi2))
- return false;
-
- return true;
- }
-
-
- /* Allocate data structures used in analyze_edges_for_bb. */
-
- static void
- init_analyze_edges_for_bb (void)
- {
- edge_leader = VEC_alloc (edge, heap, 25);
- stmt_list = VEC_alloc (gimple_seq, heap, 25);
- leader_has_match = BITMAP_ALLOC (NULL);
- }
-
-
- /* Free data structures used in analyze_edges_for_bb. */
-
- static void
- fini_analyze_edges_for_bb (void)
- {
- VEC_free (edge, heap, edge_leader);
- VEC_free (gimple_seq, heap, stmt_list);
- BITMAP_FREE (leader_has_match);
- }
-
- /* A helper function to be called via walk_tree. Return DATA if it is
- contained in subtree TP. */
-
- static tree
- contains_tree_r (tree * tp, int *walk_subtrees, void *data)
- {
- if (*tp == data)
- {
- *walk_subtrees = 0;
- return (tree) data;
- }
- else
- return NULL_TREE;
- }
-
- /* A threshold for the number of insns contained in the latch block.
- It is used to prevent blowing the loop with too many copies from
- the latch. */
- #define MAX_STMTS_IN_LATCH 2
-
- /* Return TRUE if the stmts on SINGLE-EDGE can be moved to the
- body of the loop. This should be permitted only if SINGLE-EDGE is a
- single-basic-block latch edge and thus cleaning the latch will help
- to create a single-basic-block loop. Otherwise return FALSE. */
-
- static bool
- process_single_block_loop_latch (edge single_edge)
- {
- gimple_seq stmts;
- basic_block b_exit, b_pheader, b_loop = single_edge->src;
- edge_iterator ei;
- edge e;
- gimple_stmt_iterator gsi, gsi_exit;
- gimple_stmt_iterator tsi;
- tree expr;
- gimple stmt;
- unsigned int count = 0;
-
- if (single_edge == NULL || (single_edge->dest != single_edge->src)
- || (EDGE_COUNT (b_loop->succs) != 2)
- || (EDGE_COUNT (b_loop->preds) != 2))
- return false;
-
- /* Get the stmts on the latch edge. */
- stmts = PENDING_STMT (single_edge);
-
- /* Find the successor edge which is not the latch edge. */
- FOR_EACH_EDGE (e, ei, b_loop->succs)
- if (e->dest != b_loop)
- break;
-
- b_exit = e->dest;
-
- /* Check that the exit block has only the loop as a predecessor,
- and that there are no pending stmts on that edge as well. */
- if (EDGE_COUNT (b_exit->preds) != 1 || PENDING_STMT (e))
- return false;
-
- /* Find the predecessor edge which is not the latch edge. */
- FOR_EACH_EDGE (e, ei, b_loop->preds)
- if (e->src != b_loop)
- break;
-
- b_pheader = e->src;
-
- if (b_exit == b_pheader || b_exit == b_loop || b_pheader == b_loop)
- return false;
-
- gsi_exit = gsi_after_labels (b_exit);
-
- /* Get the last stmt in the loop body. */
- gsi = gsi_last_bb (single_edge->src);
- stmt = gsi_stmt (gsi);
-
- if (gimple_code (stmt) != GIMPLE_COND)
- return false;
-
-
- expr = build2 (gimple_cond_code (stmt), boolean_type_node,
- gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
- /* Iterate over the insns on the latch and count them. */
- for (tsi = gsi_start (stmts); !gsi_end_p (tsi); gsi_next (&tsi))
- {
- gimple stmt1 = gsi_stmt (tsi);
- tree var;
-
- count++;
- /* Check that the condition does not contain any new definition
- created in the latch as the stmts from the latch intended
- to precede it. */
- if (gimple_code (stmt1) != GIMPLE_ASSIGN)
- return false;
- var = gimple_assign_lhs (stmt1);
- if (TREE_THIS_VOLATILE (var)
- || TYPE_VOLATILE (TREE_TYPE (var))
- || walk_tree (&expr, contains_tree_r, var, NULL))
- return false;
- }
- /* Check that the latch does not contain more than MAX_STMTS_IN_LATCH
- insns. The purpose of this restriction is to prevent blowing the
- loop with too many copies from the latch. */
- if (count > MAX_STMTS_IN_LATCH)
- return false;
-
- /* Apply the transformation - clean up the latch block:
-
- var = something;
- L1:
- x1 = expr;
- if (cond) goto L2 else goto L3;
- L2:
- var = x1;
- goto L1
- L3:
- ...
-
- ==>
-
- var = something;
- L1:
- x1 = expr;
- tmp_var = var;
- var = x1;
- if (cond) goto L1 else goto L2;
- L2:
- var = tmp_var;
- ...
- */
- for (tsi = gsi_start (stmts); !gsi_end_p (tsi); gsi_next (&tsi))
- {
- gimple stmt1 = gsi_stmt (tsi);
- tree var, tmp_var;
- gimple copy;
-
- /* Create a new variable to load back the value of var in case
- we exit the loop. */
- var = gimple_assign_lhs (stmt1);
- tmp_var = create_temp (var);
- copy = gimple_build_assign (tmp_var, var);
- set_is_used (tmp_var);
- gsi_insert_before (&gsi, copy, GSI_SAME_STMT);
- copy = gimple_build_assign (var, tmp_var);
- gsi_insert_before (&gsi_exit, copy, GSI_SAME_STMT);
- }
-
- PENDING_STMT (single_edge) = 0;
- /* Insert the new stmts to the loop body. */
- gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
-
- if (dump_file)
- fprintf (dump_file,
- "\nCleaned-up latch block of loop with single BB: %d\n\n",
- single_edge->dest->index);
-
- return true;
- }
-
- /* Look at all the incoming edges to block BB, and decide where the best place
- to insert the stmts on each edge are, and perform those insertions. */
-
- static void
- analyze_edges_for_bb (basic_block bb)
- {
- edge e;
- edge_iterator ei;
- int count;
- unsigned int x;
- bool have_opportunity;
- gimple_stmt_iterator gsi;
- gimple stmt;
- edge single_edge = NULL;
- bool is_label;
- edge leader;
-
- count = 0;
-
- /* Blocks which contain at least one abnormal edge cannot use
- make_forwarder_block. Look for these blocks, and commit any PENDING_STMTs
- found on edges in these block. */
- have_opportunity = true;
- FOR_EACH_EDGE (e, ei, bb->preds)
- if (e->flags & EDGE_ABNORMAL)
- {
- have_opportunity = false;
- break;
- }
-
- if (!have_opportunity)
- {
- FOR_EACH_EDGE (e, ei, bb->preds)
- if (PENDING_STMT (e))
- gsi_commit_one_edge_insert (e, NULL);
- return;
- }
-
- /* Find out how many edges there are with interesting pending stmts on them.
- Commit the stmts on edges we are not interested in. */
- FOR_EACH_EDGE (e, ei, bb->preds)
- {
- if (PENDING_STMT (e))
- {
- gcc_assert (!(e->flags & EDGE_ABNORMAL));
- if (e->flags & EDGE_FALLTHRU)
- {
- gsi = gsi_start_bb (e->src);
- if (!gsi_end_p (gsi))
- {
- stmt = gsi_stmt (gsi);
- gsi_next (&gsi);
- gcc_assert (stmt != NULL);
- is_label = (gimple_code (stmt) == GIMPLE_LABEL);
- /* Punt if it has non-label stmts, or isn't local. */
- if (!is_label
- || DECL_NONLOCAL (gimple_label_label (stmt))
- || !gsi_end_p (gsi))
- {
- gsi_commit_one_edge_insert (e, NULL);
- continue;
- }
- }
- }
- single_edge = e;
- count++;
- }
- }
-
- /* If there aren't at least 2 edges, no sharing will happen. */
- if (count < 2)
- {
- if (single_edge)
- {
- /* Add stmts to the edge unless processed specially as a
- single-block loop latch edge. */
- if (!process_single_block_loop_latch (single_edge))
- gsi_commit_one_edge_insert (single_edge, NULL);
- }
- return;
- }
-
- /* Ensure that we have empty worklists. */
- #ifdef ENABLE_CHECKING
- gcc_assert (VEC_length (edge, edge_leader) == 0);
- gcc_assert (VEC_length (gimple_seq, stmt_list) == 0);
- gcc_assert (bitmap_empty_p (leader_has_match));
- #endif
-
- /* Find the "leader" block for each set of unique stmt lists. Preference is
- given to FALLTHRU blocks since they would need a GOTO to arrive at another
- block. The leader edge destination is the block which all the other edges
- with the same stmt list will be redirected to. */
- have_opportunity = false;
- FOR_EACH_EDGE (e, ei, bb->preds)
- {
- if (PENDING_STMT (e))
- {
- bool found = false;
-
- /* Look for the same stmt list in edge leaders list. */
- for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
- {
- if (identical_stmt_lists_p (leader, e))
- {
- /* Give this edge the same stmt list pointer. */
- PENDING_STMT (e) = NULL;
- e->aux = leader;
- bitmap_set_bit (leader_has_match, x);
- have_opportunity = found = true;
- break;
- }
- }
-
- /* If no similar stmt list, add this edge to the leader list. */
- if (!found)
- {
- VEC_safe_push (edge, heap, edge_leader, e);
- VEC_safe_push (gimple_seq, heap, stmt_list, PENDING_STMT (e));
- }
- }
- }
-
- /* If there are no similar lists, just issue the stmts. */
- if (!have_opportunity)
- {
- for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
- gsi_commit_one_edge_insert (leader, NULL);
- VEC_truncate (edge, edge_leader, 0);
- VEC_truncate (gimple_seq, stmt_list, 0);
- bitmap_clear (leader_has_match);
- return;
- }
-
- if (dump_file)
- fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
- bb->index);
-
- /* For each common list, create a forwarding block and issue the stmt's
- in that block. */
- for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
- if (bitmap_bit_p (leader_has_match, x))
- {
- edge new_edge;
- gimple_stmt_iterator gsi;
- gimple_seq curr_stmt_list;
-
- leader_match = leader;
-
- /* The tree_* cfg manipulation routines use the PENDING_EDGE field
- for various PHI manipulations, so it gets cleared when calls are
- made to make_forwarder_block(). So make sure the edge is clear,
- and use the saved stmt list. */
- PENDING_STMT (leader) = NULL;
- leader->aux = leader;
- curr_stmt_list = VEC_index (gimple_seq, stmt_list, x);
-
- new_edge = make_forwarder_block (leader->dest, same_stmt_list_p,
- NULL);
- bb = new_edge->dest;
- if (dump_file)
- {
- fprintf (dump_file, "Splitting BB %d for Common stmt list. ",
- leader->dest->index);
- fprintf (dump_file, "Original block is now BB%d.\n", bb->index);
- print_gimple_seq (dump_file, curr_stmt_list, 0, TDF_VOPS);
- }
-
- FOR_EACH_EDGE (e, ei, new_edge->src->preds)
- {
- e->aux = NULL;
- if (dump_file)
- fprintf (dump_file, " Edge (%d->%d) lands here.\n",
- e->src->index, e->dest->index);
- }
-
- gsi = gsi_last_bb (leader->dest);
- gsi_insert_seq_after (&gsi, curr_stmt_list, GSI_NEW_STMT);
-
- leader_match = NULL;
- /* We should never get a new block now. */
- }
- else
- {
- PENDING_STMT (leader) = VEC_index (gimple_seq, stmt_list, x);
- gsi_commit_one_edge_insert (leader, NULL);
- }
-
-
- /* Clear the working data structures. */
- VEC_truncate (edge, edge_leader, 0);
- VEC_truncate (gimple_seq, stmt_list, 0);
- bitmap_clear (leader_has_match);
- }
-
-
- /* This function will analyze the insertions which were performed on edges,
- and decide whether they should be left on that edge, or whether it is more
- efficient to emit some subset of them in a single block. All stmts are
- inserted somewhere. */
-
- static void
- perform_edge_inserts (void)
- {
- basic_block bb;
-
- if (dump_file)
- fprintf(dump_file, "Analyzing Edge Insertions.\n");
-
- /* analyze_edges_for_bb calls make_forwarder_block, which tries to
- incrementally update the dominator information. Since we don't
- need dominator information after this pass, go ahead and free the
- dominator information. */
- free_dominance_info (CDI_DOMINATORS);
- free_dominance_info (CDI_POST_DOMINATORS);
-
- /* Allocate data structures used in analyze_edges_for_bb. */
- init_analyze_edges_for_bb ();
-
- FOR_EACH_BB (bb)
- analyze_edges_for_bb (bb);
-
- analyze_edges_for_bb (EXIT_BLOCK_PTR);
-
- /* Free data structures used in analyze_edges_for_bb. */
- fini_analyze_edges_for_bb ();
-
- #ifdef ENABLE_CHECKING
- {
- edge_iterator ei;
- edge e;
- FOR_EACH_BB (bb)
- {
- FOR_EACH_EDGE (e, ei, bb->preds)
- {
- if (PENDING_STMT (e))
- error (" Pending stmts not issued on PRED edge (%d, %d)\n",
- e->src->index, e->dest->index);
- }
- FOR_EACH_EDGE (e, ei, bb->succs)
- {
- if (PENDING_STMT (e))
- error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
- e->src->index, e->dest->index);
- }
- }
- FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
- {
- if (PENDING_STMT (e))
- error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
- e->src->index, e->dest->index);
- }
- FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
- {
- if (PENDING_STMT (e))
- error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
- e->src->index, e->dest->index);
- }
- }
- #endif
- }
-
/* Remove the ssa-names in the current function and translate them into normal
compiler variables. PERFORM_TER is true if Temporary Expression Replacement
--- 794,799 ----
*************** perform_edge_inserts (void)
*** 1458,1467 ****
static void
remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
{
- basic_block bb;
gimple *values = NULL;
var_map map;
- gimple_stmt_iterator gsi;
elim_graph g;
map = coalesce_ssa_name ();
--- 802,809 ----
*************** remove_ssa_form (bool perform_ter, struc
*** 1483,1515 ****
dump_replaceable_exprs (dump_file, values);
}
! /* Assign real variables to the partitions now. */
! if (0)
! assign_vars (map);
!
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, "After Base variable replacement:\n");
! dump_var_map (dump_file, map);
! }
!
! rewrite_trees (map, values);
!
! if (0 && values)
! free (values);
!
! /* Remove PHI nodes which have been translated back to real variables. */
! if (0)
! FOR_EACH_BB (bb)
! for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
! remove_phi_node (&gsi, true);
!
! /* If any copies were inserted on edges, analyze and insert them now. */
! if (0)
! perform_edge_inserts ();
!
! if (0)
! delete_var_map (map);
sa->map = map;
sa->values = values;
--- 825,831 ----
dump_replaceable_exprs (dump_file, values);
}
! rewrite_trees (map);
sa->map = map;
sa->values = values;
*************** rewrite_out_of_ssa (struct ssaexpand *sa
*** 1630,1635 ****
--- 946,953 ----
copies into the loop itself. */
insert_backedge_copies ();
+ if (0)
+ compact_ssa_names ();
/* Eliminate PHIs which are of no use, such as virtual or dead phis. */
eliminate_useless_phis ();
*************** rewrite_out_of_ssa (struct ssaexpand *sa
*** 1642,1676 ****
if (dump_file && (dump_flags & TDF_DETAILS))
gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
- if (0)
- cfun->gimple_df->in_ssa_p = false;
return 0;
}
-
-
- /* Define the parameters of the out of SSA pass. */
-
- #if 0
- struct gimple_opt_pass pass_del_ssa =
- {
- {
- GIMPLE_PASS,
- "optimized", /* name */
- NULL, /* gate */
- rewrite_out_of_ssa, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_TREE_SSA_TO_NORMAL, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- /* ??? If TER is enabled, we also kill gimple. */
- PROP_ssa, /* properties_destroyed */
- TODO_verify_ssa | TODO_verify_flow
- | TODO_verify_stmts, /* todo_flags_start */
- TODO_dump_func
- | TODO_ggc_collect
- | TODO_remove_unused_locals /* todo_flags_finish */
- }
- };
- #endif
--- 960,964 ----
Index: gcc/ssaexpand.h
===================================================================
*** gcc.orig/ssaexpand.h
--- gcc/ssaexpand.h
*************** get_rtx_for_ssa_name (tree exp)
*** 39,44 ****
--- 39,45 ----
int p = partition_find (SA.map->var_partition, SSA_NAME_VERSION (exp));
if (SA.map->partition_to_view)
p = SA.map->partition_to_view[p];
+ gcc_assert (p != NO_PARTITION);
return SA.partition_to_pseudo[p];
}
More information about the Gcc-patches
mailing list