[tree-ssa] Improve usage of .GLOBAL_VAR [patch]
Diego Novillo
dnovillo@redhat.com
Thu Sep 4 15:29:00 GMT 2003
Up until now, we used to model call-clobbering semantics using a unique
artificial symbol called .GLOBAL_VAR. The idea is that at every
call-site, a new SSA name for .GLOBAL_VAR is created. References to
call-clobbered variables are turned into references to .GLOBAL_VAR.
The scheme works well in terms of compile time performance, but globbing
all those symbols to .GLOBAL_VAR ties up the optimizers because
references to any call-clobbered symbol turns into a reference to
.GLOBAL_VAR.
With this patch, we only resort to using .GLOBAL_VAR if the number of
call sites and call-clobbered variables is large than certain
threshold. I chose a threshold based on a typical bootstrap cycle
(including all target libraries). That could certainly be changed later
on.
This exposed a few alias bugs that were masked by our use of
.GLOBAL_VAR. I added two new tests for that.
The patch also contains a minor fix to places where we traverse all the
blocks sequentially. We should always be using FOR_EACH_BB for that.
Bootstrapped and tested x86 and amd64.
Diego.
* tree-cfg.c (remove_stmt): Also invalidate the statement's code
when removing annotations.
(cleanup_tree_cfg): Traverse basic blocks with FOR_EACH_BB.
(remove_useless_stmts_and_vars): Likewise.
* tree-ssa-dom.c (tree_ssa_dominator_optimize): Likewise.
* tree-ssa.c (rewrite_into_ssa): Likewise.
* tree-dfa.c (remove_all_phi_nodes_for): Make sure that the new
list of PHI nodes is NULL-terminated.
Add sanity checks to make sure all the PHI nodes for variables to
rename are gone.
* tree-dfa.c (struct walk_state): Add field 'num_calls'.
(add_call_clobber_ops): New local function.
(add_call_read_ops): New local function.
(get_expr_operands): Call them.
(add_stmt_operand): Call-clobbered variables are always added to
virtual operands.
(find_referenced_vars): If the number of call-clobbered variables
and number of call sites is larger than a certain threshold, group
all call-clobbered variables under .GLOBAL_VAR.
(find_vars_r): Count the number of call sites.
Don't add .GLOBAL_VAR to the list of referenced variables.
(add_referenced_var): If the addressable variable is an array,
register alias set of the type of the elements, not the type of the
array.
* tree-ssa-dom.c (mark_new_vars_to_rename): Rename from
find_new_vars_to_rename. Update all users.
Before scanning the statement for new operands, mark the existing
virtual operands to be renamed again.
(optimize_stmt): Also check for newly exposed variables when doing
redundancy elimination.
* tree-ssa.c (rewrite_into_ssa): Don't abort when rename_count is
greater than 2. Simply stop trying at 3.
(prepare_operand_for_rename): New function.
(mark_def_sites): Call it.
(rewrite_stmt): Don't check if the operand is an SSA_NAME before
calling rewrite_operand.
(rewrite_operand): Don't abort if the operand was already an
SSA_NAME. Ignore it.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.156
diff -d -c -p -r1.1.4.156 tree-cfg.c
*** tree-cfg.c 1 Sep 2003 15:47:13 -0000 1.1.4.156
--- tree-cfg.c 4 Sep 2003 13:37:11 -0000
*************** cleanup_tree_cfg (void)
*** 1444,1453 ****
no longer valid. */
if (n_basic_blocks != orig_n_basic_blocks)
{
! int i;
!
! for (i = 0; i < n_basic_blocks; i++)
! clear_dom_children (BASIC_BLOCK (i));
}
timevar_pop (TV_TREE_CLEANUP_CFG);
--- 1444,1453 ----
no longer valid. */
if (n_basic_blocks != orig_n_basic_blocks)
{
! basic_block bb;
!
! FOR_EACH_BB (bb)
! clear_dom_children (bb);
}
timevar_pop (TV_TREE_CLEANUP_CFG);
*************** remove_useless_stmts_and_vars (tree *fir
*** 1760,1775 ****
static void
remove_unreachable_blocks (void)
{
! int i;
find_unreachable_blocks ();
/* Remove unreachable blocks in reverse. That will expose more unnecessary
COMPOUND_EXPRs that we can remove. */
! for (i = n_basic_blocks - 1; i >= 0; i--)
{
- basic_block bb = BASIC_BLOCK (i);
-
/* The block may have been removed in a previous iteration if it was
inside an unreachable control structure. */
if (bb == NULL || bb->index == INVALID_BLOCK)
--- 1760,1773 ----
static void
remove_unreachable_blocks (void)
{
! basic_block bb;
find_unreachable_blocks ();
/* Remove unreachable blocks in reverse. That will expose more unnecessary
COMPOUND_EXPRs that we can remove. */
! FOR_EACH_BB_REVERSE (bb)
{
/* The block may have been removed in a previous iteration if it was
inside an unreachable control structure. */
if (bb == NULL || bb->index == INVALID_BLOCK)
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.152
diff -d -c -p -r1.1.4.152 tree-dfa.c
*** tree-dfa.c 1 Sep 2003 15:47:14 -0000 1.1.4.152
--- tree-dfa.c 4 Sep 2003 13:37:14 -0000
*************** struct walk_state
*** 96,101 ****
--- 96,105 ----
/* Hash table used to avoid adding the same variable more than once. */
htab_t vars_found;
+
+ /* Number of CALL_EXPRs found. Used to determine whether to group all
+ call-clobbered variables into .GLOBAL_VAR. */
+ int num_calls;
};
*************** static bool may_access_global_mem_p (tre
*** 129,134 ****
--- 133,140 ----
static void add_def (tree *, tree);
static void add_use (tree *, tree);
static void add_vdef (tree, tree, voperands_t);
+ static void add_call_clobber_ops (tree, voperands_t);
+ static void add_call_read_ops (tree, voperands_t);
static void add_stmt_operand (tree *, tree, int, voperands_t);
static void add_immediate_use (tree, tree);
static tree find_vars_r (tree *, int *, void *);
*************** get_expr_operands (tree stmt, tree *expr
*** 440,459 ****
if (num_call_clobbered_vars > 0)
{
if (!(call_flags & (ECF_CONST | ECF_PURE | ECF_NORETURN)))
! {
! /* Functions that are not const, pure or never return may
! clobber call-clobbered variables. Add a VDEF for
! .GLOBAL_VAR. */
! stmt_ann (stmt)->makes_clobbering_call = true;
! add_stmt_operand (&global_var, stmt, opf_force_vop|opf_is_def,
! prev_vops);
! }
else if (!(call_flags & (ECF_CONST | ECF_NORETURN)))
! {
! /* Otherwise, if the function is not pure, it may reference
! memory. Add a VUSE for .GLOBAL_VAR. */
! add_stmt_operand (&global_var, stmt, opf_force_vop, prev_vops);
! }
}
return;
--- 446,454 ----
if (num_call_clobbered_vars > 0)
{
if (!(call_flags & (ECF_CONST | ECF_PURE | ECF_NORETURN)))
! add_call_clobber_ops (stmt, prev_vops);
else if (!(call_flags & (ECF_CONST | ECF_NORETURN)))
! add_call_read_ops (stmt, prev_vops);
}
return;
*************** add_stmt_operand (tree *var_p, tree stmt
*** 589,598 ****
return;
}
! /* Globals, local statics and variables referenced in VA_ARG_EXPR are
! always accessed using virtual operands. */
if (decl_function_context (sym) == 0
|| TREE_STATIC (sym)
|| v_ann->is_in_va_arg_expr)
flags |= opf_force_vop;
--- 584,594 ----
return;
}
! /* Globals, call-clobbered, local statics and variables referenced in
! VA_ARG_EXPR are always accessed using virtual operands. */
if (decl_function_context (sym) == 0
|| TREE_STATIC (sym)
+ || v_ann->is_call_clobbered
|| v_ann->is_in_va_arg_expr)
flags |= opf_force_vop;
*************** add_vuse (tree var, tree stmt, voperands
*** 844,849 ****
--- 840,897 ----
}
+ /* Add clobbering definitions for .GLOBAL_VAR or for each of the call
+ clobbered variables in the function. */
+
+ static void
+ add_call_clobber_ops (tree stmt, voperands_t prev_vops)
+ {
+ /* Functions that are not const, pure or never return may clobber
+ call-clobbered variables. */
+ stmt_ann (stmt)->makes_clobbering_call = true;
+
+ /* If we had created .GLOBAL_VAR earlier, use it. Otherwise, add a VDEF
+ operand for every call clobbered variable. See add_referenced_var for
+ the heuristic used to decide whether to create .GLOBAL_VAR or not. */
+ if (global_var)
+ add_stmt_operand (&global_var, stmt, opf_force_vop|opf_is_def, prev_vops);
+ else
+ {
+ size_t i;
+
+ for (i = 0; i < num_call_clobbered_vars; i++)
+ {
+ tree var = call_clobbered_var (i);
+ add_stmt_operand (&var, stmt, opf_force_vop|opf_is_def, prev_vops);
+ }
+ }
+ }
+
+
+ /* Add VUSE operands for .GLOBAL_VAR or all call clobbered variables in the
+ function. */
+
+ static void
+ add_call_read_ops (tree stmt, voperands_t prev_vops)
+ {
+ /* Otherwise, if the function is not pure, it may reference memory. Add
+ a VUSE for .GLOBAL_VAR if it has been created. Otherwise, add a VUSE
+ for each call-clobbered variable. See add_referenced_var for the
+ heuristic used to decide whether to create .GLOBAL_VAR. */
+ if (global_var)
+ add_stmt_operand (&global_var, stmt, opf_force_vop, prev_vops);
+ else
+ {
+ size_t i;
+
+ for (i = 0; i < num_call_clobbered_vars; i++)
+ {
+ tree var = call_clobbered_var (i);
+ add_stmt_operand (&var, stmt, opf_force_vop, prev_vops);
+ }
+ }
+ }
+
/* Create a new PHI node for variable VAR at basic block BB. */
tree
*************** remove_all_phi_nodes_for (sbitmap vars)
*** 1027,1054 ****
FOR_EACH_BB (bb)
{
/* Build a new PHI list for BB without variables in VARS. */
! tree phi, new_phi_list, tmp;
bb_ann_t ann = bb_ann (bb);
! tmp = new_phi_list = NULL_TREE;
for (phi = ann->phi_nodes; phi; phi = TREE_CHAIN (phi))
{
tree var = SSA_NAME_VAR (PHI_RESULT (phi));
! /* If the PHI node is for a variable in VARS, skip it. */
! if (TEST_BIT (vars, var_ann (var)->uid))
! continue;
!
! if (new_phi_list == NULL_TREE)
! new_phi_list = tmp = phi;
! else
{
! TREE_CHAIN (tmp) = phi;
! tmp = phi;
}
}
ann->phi_nodes = new_phi_list;
}
}
--- 1075,1114 ----
FOR_EACH_BB (bb)
{
/* Build a new PHI list for BB without variables in VARS. */
! tree phi, new_phi_list, last_phi;
bb_ann_t ann = bb_ann (bb);
! last_phi = new_phi_list = NULL_TREE;
for (phi = ann->phi_nodes; phi; phi = TREE_CHAIN (phi))
{
tree var = SSA_NAME_VAR (PHI_RESULT (phi));
! /* Only add PHI nodes for variables not in VARS. */
! if (!TEST_BIT (vars, var_ann (var)->uid))
{
! if (new_phi_list == NULL_TREE)
! new_phi_list = last_phi = phi;
! else
! {
! TREE_CHAIN (last_phi) = phi;
! last_phi = phi;
! }
}
}
+ /* Make sure the last node in the new list has no successors. */
+ if (last_phi)
+ TREE_CHAIN (last_phi) = NULL_TREE;
ann->phi_nodes = new_phi_list;
+
+ #if defined ENABLE_CHECKING
+ for (phi = ann->phi_nodes; phi; phi = TREE_CHAIN (phi))
+ {
+ tree var = SSA_NAME_VAR (PHI_RESULT (phi));
+ if (TEST_BIT (vars, var_ann (var)->uid))
+ abort ();
+ }
+ #endif
}
}
*************** find_referenced_vars (tree fndecl)
*** 1826,1831 ****
--- 1886,1925 ----
walk_state.is_not_gimple = 0;
}
+ /* Determine whether to use .GLOBAL_VAR to model call clobber semantics.
+ At every call site, we need to emit VDEF expressions.
+
+ One approach is to group all call-clobbered variables into a single
+ representative that is used as an alias of every call-clobbered
+ variable (.GLOBAL_VAR). This works well, but it ties the optimizer
+ hands because references to any call clobbered variable is a reference
+ to .GLOBAL_VAR.
+
+ The second approach is to emit a clobbering VDEF for every
+ call-clobbered variable at call sites. This is the preferred way in
+ terms of optimization opportunities but it may create too many
+ VDEF operands if there are many call clobbered variables and function
+ calls in the function.
+
+ To decide whether or not to use .GLOBAL_VAR we multiply the number of
+ function calls found by the number of call-clobbered variables. If
+ that product is beyond a certain threshold, we use .GLOBAL_VAR.
+
+ FIXME: This heuristic should be improved. One idea is to use several
+ .GLOBAL_VARs of different types instead of a single one. The
+ thresholds have been derived from a typical bootstrap cycle including
+ all target libraries. Compile times were found to take 1% more
+ compared to using .GLOBAL_VAR. */
+ {
+ const int n_calls = 2500;
+ const size_t n_clobbers = 200;
+
+ if (walk_state.num_calls * num_call_clobbered_vars < n_calls * n_clobbers)
+ global_var = NULL_TREE;
+ else if (global_var)
+ add_referenced_var (global_var, &walk_state);
+ }
+
htab_delete (vars_found);
}
*************** find_vars_r (tree *tp, int *walk_subtree
*** 2349,2355 ****
if (TREE_CODE (t) == CALL_EXPR && walk_state->is_not_gimple == 0)
{
tree op;
! int call_flags = get_call_flags (t);
for (op = TREE_OPERAND (t, 1); op; op = TREE_CHAIN (op))
{
--- 2443,2450 ----
if (TREE_CODE (t) == CALL_EXPR && walk_state->is_not_gimple == 0)
{
tree op;
!
! walk_state->num_calls++;
for (op = TREE_OPERAND (t, 1); op; op = TREE_CHAIN (op))
{
*************** find_vars_r (tree *tp, int *walk_subtree
*** 2362,2376 ****
}
}
if (global_var == NULL_TREE)
create_global_var ();
-
- /* If the function may clobber globals and addressable locals,
- consider this call as a store operation to .GLOBAL_VAR. */
- if (!(call_flags & (ECF_CONST | ECF_PURE | ECF_NORETURN)))
- walk_state->is_store = 1;
- add_referenced_var (global_var, walk_state);
- walk_state->is_store = 0;
}
return NULL_TREE;
--- 2457,2466 ----
}
}
+ /* Note that we may undo this creation after all the variables and
+ call sites have been found. See find_referenced_vars. */
if (global_var == NULL_TREE)
create_global_var ();
}
return NULL_TREE;
*************** add_referenced_var (tree var, struct wal
*** 2436,2442 ****
struct alias_map_d *alias_map;
alias_map = ggc_alloc (sizeof (*alias_map));
alias_map->var = var;
! alias_map->set = get_alias_set (var);
VARRAY_PUSH_GENERIC_PTR (addressable_vars, alias_map);
}
--- 2526,2536 ----
struct alias_map_d *alias_map;
alias_map = ggc_alloc (sizeof (*alias_map));
alias_map->var = var;
!
! if (TREE_CODE (TREE_TYPE (var)) == ARRAY_TYPE)
! alias_map->set = get_alias_set (TREE_TYPE (TREE_TYPE (var)));
! else
! alias_map->set = get_alias_set (var);
VARRAY_PUSH_GENERIC_PTR (addressable_vars, alias_map);
}
*************** add_referenced_var (tree var, struct wal
*** 2509,2515 ****
}
! /* Return the memory tag associated to pointer P. */
static tree
get_memory_tag_for (tree ptr)
--- 2603,2609 ----
}
! /* Return the memory tag associated to pointer PTR. */
static tree
get_memory_tag_for (tree ptr)
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.31
diff -d -c -p -r1.1.2.31 tree-ssa-dom.c
*** tree-ssa-dom.c 25 Aug 2003 22:24:10 -0000 1.1.2.31
--- tree-ssa-dom.c 4 Sep 2003 13:37:19 -0000
*************** static int avail_expr_eq (const void *,
*** 95,101 ****
static void htab_statistics (FILE *, htab_t);
static void record_cond_is_false (tree, varray_type *, htab_t);
static void record_cond_is_true (tree, varray_type *, htab_t);
! static void find_new_vars_to_rename (tree, sbitmap);
/* Optimize function FNDECL based on the dominator tree. This does
simple const/copy propagation and redundant expression elimination using
--- 95,101 ----
static void htab_statistics (FILE *, htab_t);
static void record_cond_is_false (tree, varray_type *, htab_t);
static void record_cond_is_true (tree, varray_type *, htab_t);
! static void mark_new_vars_to_rename (tree, sbitmap);
/* Optimize function FNDECL based on the dominator tree. This does
simple const/copy propagation and redundant expression elimination using
*************** tree_ssa_dominator_optimize (tree fndecl
*** 149,155 ****
blocks. */
do
{
! int i;
/* Optimize the dominator tree. */
optimize_block (ENTRY_BLOCK_PTR, NULL, 0, vars_to_rename);
--- 149,155 ----
blocks. */
do
{
! basic_block bb;
/* Optimize the dominator tree. */
optimize_block (ENTRY_BLOCK_PTR, NULL, 0, vars_to_rename);
*************** tree_ssa_dominator_optimize (tree fndecl
*** 169,190 ****
found_unreachable = false;
! for (i = 0; i < n_basic_blocks; i++)
! {
! basic_block bb = BASIC_BLOCK (i);
!
! if (! (bb->flags & BB_REACHABLE))
! {
! /* If a previous iteration determined this block was
! unreachable, then just ignore the block. */
! if (bitmap_bit_p (unreachable_bitmap, bb->index))
! continue;
! found_unreachable = true;
! bitmap_set_bit (unreachable_bitmap, bb->index);
! remove_phi_nodes_and_edges_for_unreachable_block (bb);
! }
! }
}
while (found_unreachable);
--- 169,186 ----
found_unreachable = false;
! FOR_EACH_BB (bb)
! if (! (bb->flags & BB_REACHABLE))
! {
! /* If a previous iteration determined this block was
! unreachable, then just ignore the block. */
! if (bitmap_bit_p (unreachable_bitmap, bb->index))
! continue;
! found_unreachable = true;
! bitmap_set_bit (unreachable_bitmap, bb->index);
! remove_phi_nodes_and_edges_for_unreachable_block (bb);
! }
}
while (found_unreachable);
*************** optimize_block (basic_block bb, tree par
*** 584,590 ****
{
tree stmt = VARRAY_TOP_TREE (stmts_to_rescan);
VARRAY_POP (stmts_to_rescan);
! find_new_vars_to_rename (stmt, vars_to_rename);
}
}
--- 580,586 ----
{
tree stmt = VARRAY_TOP_TREE (stmts_to_rescan);
VARRAY_POP (stmts_to_rescan);
! mark_new_vars_to_rename (stmt, vars_to_rename);
}
}
*************** optimize_stmt (block_stmt_iterator si, v
*** 879,884 ****
--- 875,884 ----
if (TREE_CODE (cached_lhs) == SSA_NAME)
fixup_var_scope (cached_lhs, stmt_ann (stmt)->scope);
+ else if (TREE_CODE (cached_lhs) == ADDR_EXPR
+ || (POINTER_TYPE_P (TREE_TYPE (*expr_p))
+ && is_unchanging_value (cached_lhs)))
+ may_have_exposed_new_symbols = true;
*expr_p = cached_lhs;
ann->modified = 1;
*************** avail_expr_eq (const void *p1, const voi
*** 1513,1559 ****
}
! /* Scan STMT for operands, if any new exposed symbols are found (i.e.,
! operands that are not in SSA form), add those symbols to the bitmap
VARS_TO_RENAME. */
static void
! find_new_vars_to_rename (tree stmt, sbitmap vars_to_rename)
{
varray_type ops;
size_t i;
- void **slot;
- bool found_new_symbols = false;
! /* Before scanning for new operands check if STMT wasn't cached in
! AVAIL_EXPRS. If so, we may need to replace or remove it afterwards
! because we are about to modify the STMT's hash value. */
! slot = htab_find_slot (avail_exprs, stmt, NO_INSERT);
! /* Force an operand scan. */
modify_stmt (stmt);
get_stmt_operands (stmt);
ops = def_ops (stmt);
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
! tree *def_p = VARRAY_GENERIC_PTR (ops, i);
! if (DECL_P (*def_p))
! {
! SET_BIT (vars_to_rename, var_ann (*def_p)->uid);
! found_new_symbols = true;
! }
}
ops = use_ops (stmt);
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
! tree *use_p = VARRAY_GENERIC_PTR (ops, i);
! if (DECL_P (*use_p))
! {
! SET_BIT (vars_to_rename, var_ann (*use_p)->uid);
! found_new_symbols = true;
! }
}
ops = vdef_ops (stmt);
--- 1513,1570 ----
}
! /* Add all the variables found in STMT's operands to the bitmap
VARS_TO_RENAME. */
static void
! mark_new_vars_to_rename (tree stmt, sbitmap vars_to_rename)
{
varray_type ops;
size_t i;
! /* Before re-scanning the statement for operands, mark the existing
! virtual operands to be renamed again. We do this because when new
! symbols are exposed, the virtual operands that were here before
! because of aliasing will probably be removed by the call to
! get_stmt_operand. Therefore, we need to flag them to be renamed
! beforehand. */
! ops = vdef_ops (stmt);
! for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
! {
! tree var = VDEF_RESULT (VARRAY_TREE (ops, i));
! if (!DECL_P (var))
! var = SSA_NAME_VAR (var);
! SET_BIT (vars_to_rename, var_ann (var)->uid);
! }
! ops = vuse_ops (stmt);
! for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
! {
! tree var = VARRAY_TREE (ops, i);
! if (!DECL_P (var))
! var = SSA_NAME_VAR (var);
! SET_BIT (vars_to_rename, var_ann (var)->uid);
! }
!
! /* Now force an operand re-scan on the statement and mark any newly
! exposed variables. */
modify_stmt (stmt);
get_stmt_operands (stmt);
ops = def_ops (stmt);
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
! tree *var_p = VARRAY_GENERIC_PTR (ops, i);
! if (DECL_P (*var_p))
! SET_BIT (vars_to_rename, var_ann (*var_p)->uid);
}
ops = use_ops (stmt);
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
! tree *var_p = VARRAY_GENERIC_PTR (ops, i);
! if (DECL_P (*var_p))
! SET_BIT (vars_to_rename, var_ann (*var_p)->uid);
}
ops = vdef_ops (stmt);
*************** find_new_vars_to_rename (tree stmt, sbit
*** 1561,1570 ****
{
tree var = VDEF_RESULT (VARRAY_TREE (ops, i));
if (DECL_P (var))
! {
! SET_BIT (vars_to_rename, var_ann (var)->uid);
! found_new_symbols = true;
! }
}
ops = vuse_ops (stmt);
--- 1572,1578 ----
{
tree var = VDEF_RESULT (VARRAY_TREE (ops, i));
if (DECL_P (var))
! SET_BIT (vars_to_rename, var_ann (var)->uid);
}
ops = vuse_ops (stmt);
*************** find_new_vars_to_rename (tree stmt, sbit
*** 1572,1590 ****
{
tree var = VARRAY_TREE (ops, i);
if (DECL_P (var))
! {
! SET_BIT (vars_to_rename, var_ann (var)->uid);
! found_new_symbols = true;
! }
! }
!
! /* If we found new exposed symbols, we have to remove the statement from
! the hash table as it is no longer valid. Otherwise, re-insert it for
! future use. */
! if (slot)
! {
! htab_clear_slot (avail_exprs, slot);
! slot = htab_find_slot (avail_exprs, stmt, INSERT);
! *slot = (void *) stmt;
}
}
--- 1580,1585 ----
{
tree var = VARRAY_TREE (ops, i);
if (DECL_P (var))
! SET_BIT (vars_to_rename, var_ann (var)->uid);
}
}
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.122
diff -d -c -p -r1.1.4.122 tree-ssa.c
*** tree-ssa.c 26 Aug 2003 18:24:20 -0000 1.1.4.122
--- tree-ssa.c 4 Sep 2003 13:37:21 -0000
*************** static void mark_def_sites (sbitmap);
*** 145,150 ****
--- 145,151 ----
static void compute_global_livein (varray_type);
static void set_def_block (tree, basic_block);
static void set_livein_block (tree, basic_block);
+ static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
static void insert_phi_nodes (bitmap *, sbitmap);
static void insert_phis_for_deferred_variables (varray_type);
static void rewrite_block (basic_block);
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 276,281 ****
--- 277,283 ----
sbitmap globals;
dominance_info idom;
int i, rename_count;
+ basic_block bb;
timevar_push (TV_TREE_SSA_OTHER);
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 309,318 ****
/* Initialize dominance frontier and immediate dominator bitmaps. */
dfs = (bitmap *) xmalloc (n_basic_blocks * sizeof (bitmap *));
! for (i = 0; i < n_basic_blocks; i++)
{
! dfs[i] = BITMAP_XMALLOC ();
! clear_dom_children (BASIC_BLOCK (i));
}
/* Compute immediate dominators. */
--- 311,320 ----
/* Initialize dominance frontier and immediate dominator bitmaps. */
dfs = (bitmap *) xmalloc (n_basic_blocks * sizeof (bitmap *));
! FOR_EACH_BB (bb)
{
! dfs[bb->index] = BITMAP_XMALLOC ();
! clear_dom_children (bb);
}
/* Compute immediate dominators. */
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 346,351 ****
--- 348,361 ----
if (dump_file && (dump_flags & TDF_DETAILS))
dump_function_to_file (fndecl, dump_file, dump_flags);
+ /* Sanity check. It's possible for the dominator optimizer to expose
+ new symbols more than once, but we don't want to spend an eternity
+ repeating this cycle. FIXME: The threshold 3 was found by trial
+ and error. In a bootstrap+test cycle it is only used in
+ gcc.c-torture/execute/930718-1.c. */
+ if (rename_count++ >= 3)
+ break;
+
/* Now optimize all the basic blocks in the program. */
sbitmap_zero (vars_to_rename);
if (flag_tree_dom)
*************** rewrite_into_ssa (tree fndecl, sbitmap v
*** 365,374 ****
sbitmap_zero (globals);
}
}
-
- /* Sanity check. We should not iterate more than twice. */
- if (rename_count++ >= 2)
- abort ();
}
while (sbitmap_first_set_bit (vars_to_rename) >= 0);
--- 375,380 ----
*************** compute_global_livein (varray_type def_m
*** 515,523 ****
BITMAP_XFREE (in_worklist);
}
! /* Look for variable references in every block of the flowgraph, compute
! aliasing information and collect definition sites for every variable.
!
Return a bitmap for the set of referenced variables which are
"nonlocal", ie those which are live across block boundaries.
This information is used to reduce the number of PHI nodes
--- 521,527 ----
BITMAP_XFREE (in_worklist);
}
! /* Collect definition sites for every variable in the function.
Return a bitmap for the set of referenced variables which are
"nonlocal", ie those which are live across block boundaries.
This information is used to reduce the number of PHI nodes
*************** mark_def_sites (sbitmap globals)
*** 544,550 ****
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
varray_type ops;
! size_t i;
tree stmt;
stmt = bsi_stmt (si);
--- 548,554 ----
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
varray_type ops;
! size_t i, uid;
tree stmt;
stmt = bsi_stmt (si);
*************** mark_def_sites (sbitmap globals)
*** 555,573 ****
ops = use_ops (stmt);
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
! tree *use = VARRAY_GENERIC_PTR (ops, i);
! size_t uid;
!
! /* Ignore variables that have been renamed already. */
! if (TREE_CODE (*use) == SSA_NAME)
! continue;
!
! uid = var_ann (*use)->uid;
! if (! TEST_BIT (kills, uid))
{
SET_BIT (globals, uid);
! set_livein_block (*use, bb);
}
}
--- 559,571 ----
ops = use_ops (stmt);
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
! tree *use_p = VARRAY_GENERIC_PTR (ops, i);
! if (prepare_operand_for_rename (use_p, &uid)
! && !TEST_BIT (kills, uid))
{
SET_BIT (globals, uid);
! set_livein_block (*use_p, bb);
}
}
*************** mark_def_sites (sbitmap globals)
*** 575,593 ****
ops = vuse_ops (stmt);
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
! tree use = VARRAY_TREE (ops, i);
! size_t uid;
!
! /* Ignore variables that have been renamed already. */
! if (TREE_CODE (use) == SSA_NAME)
! continue;
!
! uid = var_ann (use)->uid;
! if (! TEST_BIT (kills, uid))
{
SET_BIT (globals, uid);
! set_livein_block (use, bb);
}
}
--- 573,585 ----
ops = vuse_ops (stmt);
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
! tree *use_p = &VARRAY_TREE (ops, i);
! if (prepare_operand_for_rename (use_p, &uid)
! && !TEST_BIT (kills, uid))
{
SET_BIT (globals, uid);
! set_livein_block (*use_p, bb);
}
}
*************** mark_def_sites (sbitmap globals)
*** 600,632 ****
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
tree vdef = VARRAY_TREE (ops, i);
- tree vdef_op = VDEF_OP (vdef);
- size_t uid;
-
- /* Ignore variables that have been renamed already. */
- if (TREE_CODE (vdef_op) == SSA_NAME)
- continue;
! uid = var_ann (vdef_op)->uid;
!
! set_def_block (VDEF_RESULT (vdef), bb);
! if (!TEST_BIT (kills, uid))
{
! SET_BIT (globals, uid);
! set_livein_block (vdef_op, bb);
}
}
! /* Now process the definition made by this statement. If the
! definition has been renamed already, do nothing. */
ops = def_ops (stmt);
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
tree *def_p = VARRAY_GENERIC_PTR (ops, i);
! if (TREE_CODE (*def_p) != SSA_NAME)
{
set_def_block (*def_p, bb);
! SET_BIT (kills, var_ann (*def_p)->uid);
}
}
}
--- 592,621 ----
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
tree vdef = VARRAY_TREE (ops, i);
! if (prepare_operand_for_rename (&VDEF_OP (vdef), &uid))
{
! VDEF_RESULT (vdef) = VDEF_OP (vdef);
!
! set_def_block (VDEF_RESULT (vdef), bb);
! if (!TEST_BIT (kills, uid))
! {
! SET_BIT (globals, uid);
! set_livein_block (VDEF_OP (vdef), bb);
! }
}
}
! /* Now process the definition made by this statement. */
ops = def_ops (stmt);
for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
{
tree *def_p = VARRAY_GENERIC_PTR (ops, i);
!
! if (prepare_operand_for_rename (def_p, &uid))
{
set_def_block (*def_p, bb);
! SET_BIT (kills, uid);
}
}
}
*************** set_livein_block (tree var, basic_block
*** 688,693 ****
--- 677,706 ----
}
+ /* If the operand pointed by OP_P needs to be renamed, strip away SSA_NAME
+ wrappers (if needed) and return true. The unique ID for the operand's
+ variable will be stored in *UID_P. */
+
+ static bool
+ prepare_operand_for_rename (tree *op_p, size_t *uid_p)
+ {
+ tree var = (TREE_CODE (*op_p) != SSA_NAME) ? *op_p : SSA_NAME_VAR (*op_p);
+ *uid_p = var_ann (var)->uid;
+
+ /* Ignore variables that don't need to be renamed. */
+ if (!TEST_BIT (vars_to_rename, *uid_p))
+ return false;
+
+ /* The variable needs to be renamed. If it already had an
+ SSA_NAME, strip it off. This way, the SSA rename pass
+ doesn't need to deal with existing SSA names. */
+ if (TREE_CODE (*op_p) == SSA_NAME)
+ *op_p = var;
+
+ return true;
+ }
+
+
/* Insert PHI nodes at the dominance frontier of blocks with variable
definitions. DFS contains the dominance frontier information for the
flowgraph.
*************** rewrite_stmt (block_stmt_iterator si, va
*** 2036,2058 ****
/* Step 1. Rewrite USES and VUSES in the statement. */
for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
! {
! tree *op_p = VARRAY_GENERIC_PTR (uses, i);
! if (TREE_CODE (*op_p) != SSA_NAME)
! rewrite_operand (op_p);
! }
/* Rewrite virtual uses in the statement. */
for (i = 0; vuses && i < VARRAY_ACTIVE_SIZE (vuses); i++)
! if (TREE_CODE (VARRAY_TREE (vuses, i)) != SSA_NAME)
! rewrite_operand (&(VARRAY_TREE (vuses, i)));
/* Step 2. Register the statement's DEF and VDEF operands. */
for (i = 0; defs && i < VARRAY_ACTIVE_SIZE (defs); i++)
{
tree *def_p = VARRAY_GENERIC_PTR (defs, i);
if (TREE_CODE (*def_p) != SSA_NAME)
*def_p = make_ssa_name (*def_p, stmt);
register_new_def (SSA_NAME_VAR (*def_p), *def_p, block_defs_p);
}
--- 2049,2070 ----
/* Step 1. Rewrite USES and VUSES in the statement. */
for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
! rewrite_operand ((tree *) VARRAY_GENERIC_PTR (uses, i));
/* Rewrite virtual uses in the statement. */
for (i = 0; vuses && i < VARRAY_ACTIVE_SIZE (vuses); i++)
! rewrite_operand (&VARRAY_TREE (vuses, i));
/* Step 2. Register the statement's DEF and VDEF operands. */
for (i = 0; defs && i < VARRAY_ACTIVE_SIZE (defs); i++)
{
tree *def_p = VARRAY_GENERIC_PTR (defs, i);
+
if (TREE_CODE (*def_p) != SSA_NAME)
*def_p = make_ssa_name (*def_p, stmt);
+
+ /* FIXME: We shouldn't be registering new defs if the variable
+ doesn't need to be renamed. */
register_new_def (SSA_NAME_VAR (*def_p), *def_p, block_defs_p);
}
*************** rewrite_stmt (block_stmt_iterator si, va
*** 2061,2072 ****
{
tree vdef = VARRAY_TREE (vdefs, i);
! if (TREE_CODE (VDEF_OP (vdef)) != SSA_NAME)
! rewrite_operand (&(VDEF_OP (vdef)));
if (TREE_CODE (VDEF_RESULT (vdef)) != SSA_NAME)
VDEF_RESULT (vdef) = make_ssa_name (VDEF_RESULT (vdef), stmt);
register_new_def (SSA_NAME_VAR (VDEF_RESULT (vdef)),
VDEF_RESULT (vdef), block_defs_p);
}
--- 2073,2085 ----
{
tree vdef = VARRAY_TREE (vdefs, i);
! rewrite_operand (&(VDEF_OP (vdef)));
if (TREE_CODE (VDEF_RESULT (vdef)) != SSA_NAME)
VDEF_RESULT (vdef) = make_ssa_name (VDEF_RESULT (vdef), stmt);
+ /* FIXME: We shouldn't be registering new defs if the variable
+ doesn't need to be renamed. */
register_new_def (SSA_NAME_VAR (VDEF_RESULT (vdef)),
VDEF_RESULT (vdef), block_defs_p);
}
*************** set_is_used (tree t)
*** 2084,2100 ****
/* Replace the operand pointed by OP_P with its immediate reaching
! definition. IS_REAL_OPERAND is true when this is a USE operand. */
static inline void
rewrite_operand (tree *op_p)
{
! #if defined ENABLE_CHECKING
! if (TREE_CODE (*op_p) == SSA_NAME)
! abort ();
! #endif
!
! *op_p = get_reaching_def (*op_p);
}
--- 2097,2109 ----
/* Replace the operand pointed by OP_P with its immediate reaching
! definition. */
static inline void
rewrite_operand (tree *op_p)
{
! if (TREE_CODE (*op_p) != SSA_NAME)
! *op_p = get_reaching_def (*op_p);
}
Index: testsuite/gcc.c-torture/execute/20030828-1.c
===================================================================
RCS file: testsuite/gcc.c-torture/execute/20030828-1.c
diff -N testsuite/gcc.c-torture/execute/20030828-1.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.c-torture/execute/20030828-1.c 4 Sep 2003 13:37:36 -0000
***************
*** 0 ****
--- 1,18 ----
+ const int *p;
+
+ int bar (void)
+ {
+ return *p + 1;
+ }
+
+ main ()
+ {
+ /* Variable 'i' is never used but it's aliased to a global pointer. The
+ alias analyzer was not considering that 'i' may be used in the call to
+ bar(). */
+ const int i = 5;
+ p = &i;
+ if (bar() != 6)
+ abort ();
+ exit (0);
+ }
Index: testsuite/gcc.c-torture/execute/20030828-2.c
===================================================================
RCS file: testsuite/gcc.c-torture/execute/20030828-2.c
diff -N testsuite/gcc.c-torture/execute/20030828-2.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.c-torture/execute/20030828-2.c 4 Sep 2003 13:37:36 -0000
***************
*** 0 ****
--- 1,28 ----
+ struct rtx_def
+ {
+ int code;
+ };
+
+ main()
+ {
+ int tmp[2];
+ struct rtx_def *r, s;
+ int *p, *q;
+
+ /* The alias analyzer was creating the same memory tag for r, p and q
+ because 'struct rtx_def *' is type-compatible with 'int *'. However,
+ the alias set of 'int[2]' is not the same as 'int *', so variable
+ 'tmp' was deemed not aliased with anything. */
+ r = &s;
+ r->code = 39;
+
+ /* If 'r' wasn't declared, then q and tmp would have had the same memory
+ tag. */
+ p = tmp;
+ q = p + 1;
+ *q = 0;
+ tmp[1] = 39;
+ if (*q != 39)
+ abort ();
+ exit (0);
+ }
More information about the Gcc-patches
mailing list