From 81d080336384ece7e0f3996541093fb348b9f689 Mon Sep 17 00:00:00 2001 From: dnovillo Date: Thu, 22 Jul 2004 16:39:49 +0000 Subject: [PATCH] * tree-into-ssa.c (set_livein_block): Fix typo in comment. (rewrite_ssa_into_ssa): Start iterating over SSA names at 1. Release SSA names that have been re-renamed. * tree-phinodes.c (make_phi_node): Set same TREE_TYPE as the variable. * tree-ssa-alias.c (init_alias_info): If aliases have been computed before, clear existing alias information. (create_name_tags): Do no fixup PT_ANYTHING pointers. If the new name tag for a pointer is different than the one it had before, mark the old tag for renaming. (replace_may_alias): New function. (group_aliases): Call it. (setup_pointers_and_addressables): Always call get_tmt_for. (maybe_create_global_var): Don't create .GLOBAL_VAR more than once. (set_pt_anything): New local function. (set_pt_malloc): New local function. (merge_pointed_to_info): Don't merge pointed-to variables from the original pointer if the destination is pointing to an unknown location. (add_pointed_to_expr): Call set_pt_anything and set_pt_malloc. (add_pointed_to_var): Do not add a variable to the points-to set if the pointer is already pointing to anywhere. (collect_points_to_info_r): If the defining statement is a PHI node, only merge pointed-to information if the argument has already been visited. (get_tmt_for): Only create a new tag if the pointer didn't have one already. (dump_alias_info): Emit more information. (dump_points_to_info_for): Likewise. * tree-ssa-dom.c (redirect_edges_and_update_ssa_graph): Don't try to get the annotation of an SSA_NAME. * tree-ssa-operands.c (add_stmt_operand): Only check for empty alias sets when checking is enabled. * tree-ssa-pre.c (need_eh_cleanup): New local variable. (eliminate): Mark basic blocks that will need EH information cleaned up. (init_pre): Split ENTRY_BLOCK->0 if block 0 has more than one predecessor. Initialize need_eh_cleanup. (fini_pre): Call tree_purge_all_dead_eh_edges and cleanup_tree_cfg if needed. Free need_eh_cleanup. * tree-ssa.c (verify_ssa_name): New function. (verify_def): Call it. Re-arrange to avoid printing too many error messages. (verify_use): Likewise. (verify_phi_args): Likewise. (verify_flow_insensitive_alias_info): New function. (verify_flow_sensitive_alias_info): New function. (verify_alias_info): New function. (verify_ssa): Call verify_alias_info. Clear TREE_VISITED on all the SSA_NAMEs before scanning the program. Re-arrange to avoid printing too many error messages. * tree-ssanames.c (make_ssa_name): Clear SSA_NAME_IN_FREE_LIST. (release_ssa_name): Never release a default definition. (release_defs): New function. * tree.h: Declare it. * tree-ssa-dce.c (remove_dead_stmt): Call it. * tree-ssa.c (walk_use_def_chains_1): Add new argument IS_DFS. If true, do a depth-first search. Do a breadht-first search, otherwise. (walk_use_def_chains): Add new argument IS_DFS. Update all users. * tree-flow.h (walk_use_def_chains): Update prototype. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@85052 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 73 ++++++++ gcc/tree-flow.h | 2 +- gcc/tree-into-ssa.c | 16 +- gcc/tree-phinodes.c | 1 + gcc/tree-ssa-alias.c | 266 +++++++++++++++++++++++----- gcc/tree-ssa-dce.c | 1 + gcc/tree-ssa-dom.c | 14 +- gcc/tree-ssa-operands.c | 2 + gcc/tree-ssa-pre.c | 39 ++++- gcc/tree-ssa.c | 451 ++++++++++++++++++++++++++++++++++++------------ gcc/tree-ssanames.c | 33 ++++ gcc/tree.h | 2 + 12 files changed, 730 insertions(+), 170 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 05e5884e225..2b38a13387c 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,76 @@ +2004-07-22 Diego Novillo + + * tree-into-ssa.c (set_livein_block): Fix typo in comment. + (rewrite_ssa_into_ssa): Start iterating over SSA names at 1. + Release SSA names that have been re-renamed. + * tree-phinodes.c (make_phi_node): Set same TREE_TYPE as the + variable. + * tree-ssa-alias.c (init_alias_info): If aliases have been + computed before, clear existing alias information. + (create_name_tags): Do no fixup PT_ANYTHING pointers. + If the new name tag for a pointer is different than the one it + had before, mark the old tag for renaming. + (replace_may_alias): New function. + (group_aliases): Call it. + (setup_pointers_and_addressables): Always call get_tmt_for. + (maybe_create_global_var): Don't create .GLOBAL_VAR more than + once. + (set_pt_anything): New local function. + (set_pt_malloc): New local function. + (merge_pointed_to_info): Don't merge pointed-to variables from + the original pointer if the destination is pointing to an + unknown location. + (add_pointed_to_expr): Call set_pt_anything and set_pt_malloc. + (add_pointed_to_var): Do not add a variable to the points-to + set if the pointer is already pointing to anywhere. + (collect_points_to_info_r): If the defining statement is a PHI + node, only merge pointed-to information if the argument has + already been visited. + (get_tmt_for): Only create a new tag if the pointer didn't + have one already. + (dump_alias_info): Emit more information. + (dump_points_to_info_for): Likewise. + * tree-ssa-dom.c (redirect_edges_and_update_ssa_graph): Don't + try to get the annotation of an SSA_NAME. + * tree-ssa-operands.c (add_stmt_operand): Only check for empty + alias sets when checking is enabled. + * tree-ssa-pre.c (need_eh_cleanup): New local variable. + (eliminate): Mark basic blocks that will need + EH information cleaned up. + (init_pre): Split ENTRY_BLOCK->0 if block 0 has more than one + predecessor. + Initialize need_eh_cleanup. + (fini_pre): Call tree_purge_all_dead_eh_edges and + cleanup_tree_cfg if needed. + Free need_eh_cleanup. + * tree-ssa.c (verify_ssa_name): New function. + (verify_def): Call it. + Re-arrange to avoid printing too many error messages. + (verify_use): Likewise. + (verify_phi_args): Likewise. + (verify_flow_insensitive_alias_info): New function. + (verify_flow_sensitive_alias_info): New function. + (verify_alias_info): New function. + (verify_ssa): Call verify_alias_info. + Clear TREE_VISITED on all the SSA_NAMEs before scanning the + program. + Re-arrange to avoid printing too many error messages. + * tree-ssanames.c (make_ssa_name): Clear + SSA_NAME_IN_FREE_LIST. + (release_ssa_name): Never release a default definition. + (release_defs): New function. + * tree.h: Declare it. + * tree-ssa-dce.c (remove_dead_stmt): Call it. + +2004-07-22 Diego Novillo + + * tree-ssa.c (walk_use_def_chains_1): Add new argument IS_DFS. + If true, do a depth-first search. Do a breadht-first search, + otherwise. + (walk_use_def_chains): Add new argument IS_DFS. + Update all users. + * tree-flow.h (walk_use_def_chains): Update prototype. + 2004-07-22 Hans-Peter Nilsson * config/cris/cris.md: Tweak formatting. diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 4d9a18f10ca..dcde389b711 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -576,7 +576,7 @@ extern bool tree_ssa_useless_type_conversion_1 (tree, tree); extern void verify_ssa (void); extern void delete_tree_ssa (void); extern void register_new_def (tree, varray_type *); -extern void walk_use_def_chains (tree, walk_use_def_chains_fn, void *); +extern void walk_use_def_chains (tree, walk_use_def_chains_fn, void *, bool); extern void kill_redundant_phi_nodes (void); /* In tree-into-ssa.c */ diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c index 027a90b39f0..4d5992e2d56 100644 --- a/gcc/tree-into-ssa.c +++ b/gcc/tree-into-ssa.c @@ -608,7 +608,7 @@ set_livein_block (tree var, basic_block bb) /* If the use operand pointed to by OP_P needs to be renamed, then strip away any SSA_NAME wrapping the operand, set *UID_P to the underlying variable's uid, and return true. Otherwise return false. If the operand was an - SSA_NAME, change it to the stipped name. */ + SSA_NAME, change it to the stripped name. */ static bool prepare_use_operand_for_rename (use_operand_p op_p, size_t *uid_p) @@ -1822,9 +1822,8 @@ rewrite_ssa_into_ssa (bitmap names_to_rename) /* We no longer need this bitmap, clear and free it. */ sbitmap_free (mark_def_sites_global_data.kills); - for (i = 0; i < num_ssa_names; i++) - if (ssa_name (i)) - set_current_def (ssa_name (i), NULL_TREE); + for (i = 1; i < num_ssa_names; i++) + set_current_def (ssa_name (i), NULL_TREE); /* Insert PHI nodes at dominance frontiers of definition blocks. */ insert_phi_nodes (dfs, names_to_rename); @@ -1856,6 +1855,9 @@ rewrite_ssa_into_ssa (bitmap names_to_rename) /* Finalize the dominator walker. */ fini_walk_dominator_tree (&walk_data); + EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, + release_ssa_name (ssa_name (i))); + sbitmap_free (snames_to_rename); timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS); @@ -1874,16 +1876,16 @@ rewrite_ssa_into_ssa (bitmap names_to_rename) htab_delete (def_blocks); - for (i = 0; i < num_ssa_names; i++) + for (i = 1; i < num_ssa_names; i++) { name = ssa_name (i); - if (!name - || !SSA_NAME_AUX (name)) + if (!SSA_NAME_AUX (name)) continue; free (SSA_NAME_AUX (name)); SSA_NAME_AUX (name) = NULL; } + timevar_pop (TV_TREE_SSA_OTHER); } diff --git a/gcc/tree-phinodes.c b/gcc/tree-phinodes.c index dc2a2294e7f..3b54b08a40d 100644 --- a/gcc/tree-phinodes.c +++ b/gcc/tree-phinodes.c @@ -202,6 +202,7 @@ make_phi_node (tree var, int len) memset (phi, 0, size); TREE_SET_CODE (phi, PHI_NODE); PHI_ARG_CAPACITY (phi) = len; + TREE_TYPE (phi) = TREE_TYPE (var); if (TREE_CODE (var) == SSA_NAME) SET_PHI_RESULT (phi, var); else diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index ed4ffd993e3..bf11fe2c270 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -141,6 +141,7 @@ static tree create_memory_tag (tree type, bool is_type_tag); static tree get_tmt_for (tree, struct alias_info *); static tree get_nmt_for (tree); static void add_may_alias (tree, tree); +static void replace_may_alias (tree, size_t, tree); static struct alias_info *init_alias_info (void); static void delete_alias_info (struct alias_info *); static void compute_points_to_and_addr_escape (struct alias_info *); @@ -386,6 +387,73 @@ init_alias_info (void) ai->dereferenced_ptrs_store = BITMAP_XMALLOC (); ai->dereferenced_ptrs_load = BITMAP_XMALLOC (); + /* If aliases have been computed before, clear existing information. */ + if (aliases_computed_p) + { + size_t i; + + /* Clear the call-clobbered set. We are going to re-discover + call-clobbered variables. */ + EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, + { + tree var = referenced_var (i); + DECL_NEEDS_TO_LIVE_IN_MEMORY_INTERNAL (var) = 0; + + /* Variables that are intrinsically call-clobbered (globals, + local statics, etc) will not be marked by the aliasing + code, so we can't remove them from CALL_CLOBBERED_VARS. */ + if (!is_call_clobbered (var)) + bitmap_clear_bit (call_clobbered_vars, var_ann (var)->uid); + }); + + /* Similarly, clear the set of addressable variables. In this + case, we can just clear the set because addressability is + only computed here. */ + bitmap_clear (addressable_vars); + + /* Clear flow-insensitive alias information from each symbol. */ + for (i = 0; i < num_referenced_vars; i++) + { + var_ann_t ann = var_ann (referenced_var (i)); + + ann->is_alias_tag = 0; + if (ann->type_mem_tag) + { + var_ann_t tag_ann = var_ann (ann->type_mem_tag); + tag_ann->may_aliases = NULL; + bitmap_set_bit (vars_to_rename, tag_ann->uid); + } + } + + /* Clear flow-sensitive points-to information from each SSA name. */ + for (i = 1; i < num_ssa_names; i++) + { + tree name = ssa_name (i); + + if (!POINTER_TYPE_P (TREE_TYPE (name))) + continue; + + if (SSA_NAME_PTR_INFO (name)) + { + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name); + + /* Clear all the flags but keep the name tag to + avoid creating new temporaries unnecessarily. If + this pointer is found to point to a subset or + superset of its former points-to set, then a new + tag will need to be created in create_name_tags. */ + pi->pt_anything = 0; + pi->pt_malloc = 0; + pi->value_escapes_p = 0; + pi->is_dereferenced = 0; + if (pi->pt_vars) + bitmap_clear (pi->pt_vars); + if (pi->name_mem_tag) + var_ann (pi->name_mem_tag)->may_aliases = NULL; + } + } + } + return ai; } @@ -438,7 +506,7 @@ collect_points_to_info_for (struct alias_info *ai, tree ptr) if (!bitmap_bit_p (ai->ssa_names_visited, SSA_NAME_VERSION (ptr))) { bitmap_set_bit (ai->ssa_names_visited, SSA_NAME_VERSION (ptr)); - walk_use_def_chains (ptr, collect_points_to_info_r, ai); + walk_use_def_chains (ptr, collect_points_to_info_r, ai, true); VARRAY_PUSH_TREE (ai->processed_ptrs, ptr); } } @@ -704,22 +772,13 @@ create_name_tags (struct alias_info *ai) tree ptr = VARRAY_TREE (ai->processed_ptrs, i); struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); - /* If we could not determine where PTR was pointing to, clear - all the other points-to flags. */ - pi = SSA_NAME_PTR_INFO (ptr); - if (pi->pt_anything) - { - pi->pt_malloc = 0; - pi->pt_vars = NULL; - pi->is_dereferenced = 0; - } - if (!pi->is_dereferenced) continue; if (pi->pt_vars) { size_t j; + tree old_name_tag = pi->name_mem_tag; /* If PTR points to a set of variables, check if we don't have another pointer Q with the same points-to set before @@ -732,7 +791,6 @@ create_name_tags (struct alias_info *ai) problems if they both had different name tags because they would have different SSA version numbers (which would force us to take the name tags in and out of SSA). */ - pi->name_mem_tag = NULL_TREE; for (j = 0; j < i; j++) { tree q = VARRAY_TREE (ai->processed_ptrs, j); @@ -748,8 +806,17 @@ create_name_tags (struct alias_info *ai) } } + /* If we didn't find a pointer with the same points-to set + as PTR, create a new name tag if needed. */ if (pi->name_mem_tag == NULL_TREE) pi->name_mem_tag = get_nmt_for (ptr); + + /* If the new name tag computed for PTR is different than + the old name tag that it used to have, then the old tag + needs to be removed from the IL, so we mark it for + renaming. */ + if (old_name_tag && old_name_tag != pi->name_mem_tag) + bitmap_set_bit (vars_to_rename, var_ann (old_name_tag)->uid); } else if (pi->pt_malloc) { @@ -1160,11 +1227,14 @@ group_aliases (struct alias_info *ai) var_ann_t ann = var_ann (alias); if (ann->may_aliases) { + tree new_alias; + #if defined ENABLE_CHECKING if (VARRAY_ACTIVE_SIZE (ann->may_aliases) != 1) abort (); #endif - VARRAY_TREE (aliases, j) = VARRAY_TREE (ann->may_aliases, 0); + new_alias = VARRAY_TREE (ann->may_aliases, 0); + replace_may_alias (name_tag, j, new_alias); } } } @@ -1305,8 +1375,7 @@ setup_pointers_and_addressables (struct alias_info *ai) /* If pointer VAR still doesn't have a memory tag associated with it, create it now or re-use an existing one. */ - if (tag == NULL_TREE) - tag = get_tmt_for (var, ai); + tag = get_tmt_for (var, ai); t_ann = var_ann (tag); /* The type tag will need to be renamed into SSA afterwards. @@ -1410,6 +1479,10 @@ maybe_create_global_var (struct alias_info *ai) { size_t i, n_clobbered; + /* No need to create it, if we have one already. */ + if (global_var) + return; + /* Count all the call-clobbered variables. */ n_clobbered = 0; EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, n_clobbered++); @@ -1613,6 +1686,63 @@ add_may_alias (tree var, tree alias) } +/* Replace alias I in the alias sets of VAR with NEW_ALIAS. */ + +static void +replace_may_alias (tree var, size_t i, tree new_alias) +{ + var_ann_t v_ann = var_ann (var); + VARRAY_TREE (v_ann->may_aliases, i) = new_alias; + + /* If VAR is a call-clobbered variable, so is NEW_ALIAS. */ + if (is_call_clobbered (var)) + mark_call_clobbered (new_alias); + + /* Likewise. If NEW_ALIAS is call-clobbered, so is VAR. */ + else if (is_call_clobbered (new_alias)) + mark_call_clobbered (var); +} + + +/* Mark pointer PTR as pointing to an arbitrary memory location. */ + +static void +set_pt_anything (tree ptr) +{ + struct ptr_info_def *pi = get_ptr_info (ptr); + + pi->pt_anything = 1; + pi->pt_malloc = 0; + pi->pt_vars = NULL; + pi->is_dereferenced = 0; + + /* The pointer used to have a name tag, but we now found it pointing + to an arbitrary location. The name tag needs to be renamed and + disassociated from PTR. */ + if (pi->name_mem_tag) + { + bitmap_set_bit (vars_to_rename, var_ann (pi->name_mem_tag)->uid); + pi->name_mem_tag = NULL_TREE; + } +} + + +/* Mark pointer PTR as pointing to a malloc'd memory area. */ + +static void +set_pt_malloc (tree ptr) +{ + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); + + /* If the pointer has already been found to point to arbitrary + memory locations, it is unsafe to mark it as pointing to malloc. */ + if (pi->pt_anything) + return; + + pi->pt_malloc = 1; +} + + /* Given two pointers DEST and ORIG. Merge the points-to information in ORIG into DEST. AI is as in collect_points_to_info. */ @@ -1629,8 +1759,6 @@ merge_pointed_to_info (struct alias_info *ai, tree dest, tree orig) if (orig_pi) { - dest_pi->pt_anything |= orig_pi->pt_anything; - /* Notice that we never merge PT_MALLOC. This attribute is only true if the pointer is the result of a malloc() call. Otherwise, we can end up in this situation: @@ -1654,10 +1782,13 @@ merge_pointed_to_info (struct alias_info *ai, tree dest, tree orig) malloc call. Copy propagation before aliasing should cure this. */ dest_pi->pt_malloc = 0; - if (orig_pi->pt_malloc) - dest_pi->pt_anything = 1; - if (orig_pi->pt_vars) + if (orig_pi->pt_malloc || orig_pi->pt_anything) + set_pt_anything (dest); + + if (!dest_pi->pt_anything + && orig_pi->pt_vars + && bitmap_first_set_bit (orig_pi->pt_vars) >= 0) { if (dest_pi->pt_vars == NULL) { @@ -1678,8 +1809,6 @@ merge_pointed_to_info (struct alias_info *ai, tree dest, tree orig) static void add_pointed_to_expr (tree ptr, tree value) { - struct ptr_info_def *pi; - if (TREE_CODE (value) == WITH_SIZE_EXPR) value = TREE_OPERAND (value, 0); @@ -1690,18 +1819,20 @@ add_pointed_to_expr (tree ptr, tree value) abort (); #endif - pi = get_ptr_info (ptr); + get_ptr_info (ptr); /* If VALUE is the result of a malloc-like call, then the area pointed to PTR is guaranteed to not alias with anything else. */ if (TREE_CODE (value) == CALL_EXPR && (call_expr_flags (value) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))) - pi->pt_malloc = 1; + set_pt_malloc (ptr); else - pi->pt_anything = 1; + set_pt_anything (ptr); if (dump_file) { + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); + fprintf (dump_file, "Pointer "); print_generic_expr (dump_file, ptr, dump_flags); fprintf (dump_file, " points to "); @@ -1722,10 +1853,11 @@ add_pointed_to_expr (tree ptr, tree value) static void add_pointed_to_var (struct alias_info *ai, tree ptr, tree value) { + struct ptr_info_def *pi = get_ptr_info (ptr); + if (TREE_CODE (value) == ADDR_EXPR) { tree pt_var; - struct ptr_info_def *pi; size_t uid; pt_var = TREE_OPERAND (value, 0); @@ -1734,12 +1866,17 @@ add_pointed_to_var (struct alias_info *ai, tree ptr, tree value) if (pt_var && SSA_VAR_P (pt_var)) { - pi = get_ptr_info (ptr); uid = var_ann (pt_var)->uid; - if (pi->pt_vars == NULL) - pi->pt_vars = BITMAP_GGC_ALLOC (); - bitmap_set_bit (pi->pt_vars, uid); bitmap_set_bit (ai->addresses_needed, uid); + + /* If PTR has already been found to point anywhere, don't + add the variable to PTR's points-to set. */ + if (!pi->pt_anything) + { + if (pi->pt_vars == NULL) + pi->pt_vars = BITMAP_GGC_ALLOC (); + bitmap_set_bit (pi->pt_vars, uid); + } } else add_pointed_to_expr (ptr, value); @@ -1813,7 +1950,7 @@ collect_points_to_info_r (tree var, tree stmt, void *data) else if (TREE_CODE (stmt) == ASM_EXPR) { /* Pointers defined by __asm__ statements can point anywhere. */ - get_ptr_info (var)->pt_anything = 1; + set_pt_anything (var); } else if (IS_EMPTY_STMT (stmt)) { @@ -1828,12 +1965,19 @@ collect_points_to_info_r (tree var, tree stmt, void *data) } else if (TREE_CODE (stmt) == PHI_NODE) { + /* It STMT is a PHI node, then VAR is one of its arguments. The + variable that we are analyzing is the LHS of the PHI node. */ tree lhs = PHI_RESULT (stmt); if (is_gimple_min_invariant (var)) add_pointed_to_var (ai, lhs, var); else if (TREE_CODE (var) == SSA_NAME) - merge_pointed_to_info (ai, lhs, var); + { + if (bitmap_bit_p (ai->ssa_names_visited, SSA_NAME_VERSION (var))) + merge_pointed_to_info (ai, lhs, var); + else + set_pt_anything (lhs); + } else abort (); } @@ -2009,9 +2153,13 @@ get_tmt_for (tree ptr, struct alias_info *ai) { struct alias_map_d *alias_map; - /* Create a new MT.* artificial variable representing the memory - location pointed-to by PTR. */ - tag = create_memory_tag (tag_type, true); + /* If PTR did not have a type tag already, create a new TMT.* + artificial variable representing the memory location + pointed-to by PTR. */ + if (var_ann (ptr)->type_mem_tag == NULL_TREE) + tag = create_memory_tag (tag_type, true); + else + tag = var_ann (ptr)->type_mem_tag; /* Add PTR to the POINTERS array. Note that we are not interested in PTR's alias set. Instead, we cache the alias set for the memory that @@ -2086,16 +2234,53 @@ dump_alias_info (FILE *file) const char *funcname = lang_hooks.decl_printable_name (current_function_decl, 2); - fprintf (file, "\nAlias information for %s\n\n", funcname); + fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname); + + fprintf (file, "Aliased symbols\n\n"); + for (i = 0; i < num_referenced_vars; i++) + { + tree var = referenced_var (i); + if (may_be_aliased (var)) + dump_variable (file, var); + } + + fprintf (file, "\nDereferenced pointers\n\n"); + for (i = 0; i < num_referenced_vars; i++) + { + tree var = referenced_var (i); + var_ann_t ann = var_ann (var); + if (ann->type_mem_tag) + dump_variable (file, var); + } + + fprintf (file, "\nType memory tags\n\n"); + for (i = 0; i < num_referenced_vars; i++) + { + tree var = referenced_var (i); + var_ann_t ann = var_ann (var); + if (ann->mem_tag_kind == TYPE_TAG) + dump_variable (file, var); + } + + fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname); + + fprintf (file, "SSA_NAME pointers\n\n"); + for (i = 1; i < num_ssa_names; i++) + { + tree ptr = ssa_name (i); + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); + if (!SSA_NAME_IN_FREE_LIST (ptr) + && pi + && pi->name_mem_tag) + dump_points_to_info_for (file, ptr); + } + fprintf (file, "\nName memory tags\n\n"); for (i = 0; i < num_referenced_vars; i++) { tree var = referenced_var (i); var_ann_t ann = var_ann (var); - if (ann->may_aliases - || ann->type_mem_tag - || ann->is_alias_tag - || ann->mem_tag_kind != NOT_A_TAG) + if (ann->mem_tag_kind == NAME_TAG) dump_variable (file, var); } @@ -2144,7 +2329,6 @@ dump_points_to_info_for (FILE *file, tree ptr) { struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); - fprintf (file, "Pointer "); print_generic_expr (file, ptr, dump_flags); if (pi) diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c index 60287ce5c1c..1d3038fc60c 100644 --- a/gcc/tree-ssa-dce.c +++ b/gcc/tree-ssa-dce.c @@ -753,6 +753,7 @@ remove_dead_stmt (block_stmt_iterator *i, basic_block bb) } bsi_remove (i); + release_defs (t); } /* Print out removed statement statistics. */ diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index 90e11b76410..e1f30d4ed56 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -366,27 +366,30 @@ redirect_edges_and_update_ssa_graph (varray_type redirection_edges) defs = DEF_OPS (ann); for (j = 0; j < NUM_DEFS (defs); j++) { - tree op = SSA_NAME_VAR (DEF_OP (defs, j)); - bitmap_set_bit (vars_to_rename, var_ann (op)->uid); + tree op = DEF_OP (defs, j); + tree var = SSA_NAME_VAR (op); + bitmap_set_bit (vars_to_rename, var_ann (var)->uid); } v_may_defs = STMT_V_MAY_DEF_OPS (stmt); for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++) { tree op = V_MAY_DEF_RESULT (v_may_defs, j); - bitmap_set_bit (vars_to_rename, var_ann (op)->uid); + tree var = SSA_NAME_VAR (op); + bitmap_set_bit (vars_to_rename, var_ann (var)->uid); } v_must_defs = STMT_V_MUST_DEF_OPS (stmt); for (j = 0; j < NUM_V_MUST_DEFS (v_must_defs); j++) { tree op = V_MUST_DEF_OP (v_must_defs, j); - bitmap_set_bit (vars_to_rename, var_ann (op)->uid); + tree var = SSA_NAME_VAR (op); + bitmap_set_bit (vars_to_rename, var_ann (var)->uid); } } /* Finally, any variables in PHI nodes at our final destination - must also be taken our of SSA form. */ + must also be taken out of SSA form. */ for (phi = phi_nodes (tgt); phi; phi = PHI_CHAIN (phi)) { tree result = SSA_NAME_VAR (PHI_RESULT (phi)); @@ -528,6 +531,7 @@ redirect_edges_and_update_ssa_graph (varray_type redirection_edges) remove_phi_node (phi, NULL, bb); } } + BITMAP_XFREE (virtuals_to_rename); } diff --git a/gcc/tree-ssa-operands.c b/gcc/tree-ssa-operands.c index 7b9bb6db6ae..6f632e4447e 100644 --- a/gcc/tree-ssa-operands.c +++ b/gcc/tree-ssa-operands.c @@ -1386,8 +1386,10 @@ add_stmt_operand (tree *var_p, tree stmt, int flags, voperands_t prev_vops) /* The variable is aliased. Add its aliases to the virtual operands. */ +#if defined ENABLE_CHECKING if (VARRAY_ACTIVE_SIZE (aliases) == 0) abort (); +#endif if (flags & opf_is_def) { diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index a6943980229..d24ebc0b547 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -307,6 +307,10 @@ static alloc_pool binary_node_pool; static alloc_pool unary_node_pool; static alloc_pool reference_node_pool; +/* Set of blocks with statements that have had its EH information + cleaned up. */ +static bitmap need_eh_cleanup; + /* The phi_translate_table caches phi translations for a given expression and predecessor. */ @@ -1891,6 +1895,16 @@ eliminate (void) pre_stats.eliminations++; propagate_tree_value (rhs_p, sprime); modify_stmt (stmt); + + /* If we removed EH side effects from the statement, clean + its EH information. */ + if (maybe_clean_eh_stmt (stmt)) + { + bitmap_set_bit (need_eh_cleanup, + bb_for_stmt (stmt)->index); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Removed EH side effects.\n"); + } } } } @@ -1909,6 +1923,18 @@ init_pre (void) connect_infinite_loops_to_exit (); vn_init (); memset (&pre_stats, 0, sizeof (pre_stats)); + + /* If block 0 has more than one predecessor, it means that its PHI + nodes will have arguments coming from block -1. This creates + problems for several places in PRE that keep local arrays indexed + by block number. To prevent this, we split the edge coming from + ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number + different than -1 we wouldn't have to hack this. tree-ssa-dce.c + needs a similar change). */ + if (ENTRY_BLOCK_PTR->succ->dest->pred->pred_next) + if (!(ENTRY_BLOCK_PTR->succ->flags & EDGE_ABNORMAL)) + split_edge (ENTRY_BLOCK_PTR->succ); + FOR_ALL_BB (bb) bb->aux = xcalloc (1, sizeof (struct bb_value_sets)); @@ -1926,7 +1952,8 @@ init_pre (void) binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30); tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE)); unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30); - tsize = tree_size (build (COMPONENT_REF, void_type_node, NULL_TREE, NULL_TREE, NULL_TREE)); + tsize = tree_size (build (COMPONENT_REF, void_type_node, NULL_TREE, + NULL_TREE, NULL_TREE)); reference_node_pool = create_alloc_pool ("Reference tree nodes", tsize, 30); FOR_ALL_BB (bb) { @@ -1935,6 +1962,8 @@ init_pre (void) TMP_GEN (bb) = bitmap_set_new (); AVAIL_OUT (bb) = bitmap_set_new (); } + + need_eh_cleanup = BITMAP_XMALLOC (); } @@ -1962,6 +1991,14 @@ fini_pre (void) free_dominance_info (CDI_POST_DOMINATORS); vn_delete (); + + if (bitmap_first_set_bit (need_eh_cleanup) >= 0) + { + tree_purge_all_dead_eh_edges (need_eh_cleanup); + cleanup_tree_cfg (); + } + + BITMAP_XFREE (need_eh_cleanup); } diff --git a/gcc/tree-ssa.c b/gcc/tree-ssa.c index 35db41c26a2..6e92597f511 100644 --- a/gcc/tree-ssa.c +++ b/gcc/tree-ssa.c @@ -102,35 +102,68 @@ ssa_redirect_edge (edge e, basic_block dest) } -/* Return true if the definition of SSA_NAME at block BB is malformed. - - STMT is the statement where SSA_NAME is created. +/* Return true if SSA_NAME is malformed and mark it visited. - DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version - numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the - block in that array slot contains the definition of SSA_NAME. */ + IS_VIRTUAL is true if this SSA_NAME was found inside a virtual + operand. */ static bool -verify_def (basic_block bb, basic_block *definition_block, tree ssa_name, - tree stmt) +verify_ssa_name (tree ssa_name, bool is_virtual) { - bool err = false; + TREE_VISITED (ssa_name) = 1; if (TREE_CODE (ssa_name) != SSA_NAME) { error ("Expected an SSA_NAME object"); - debug_generic_stmt (ssa_name); - debug_generic_stmt (stmt); + return true; + } + + if (SSA_NAME_IN_FREE_LIST (ssa_name)) + { + error ("Found an SSA_NAME that had been released into the free pool"); + return true; + } + + if (is_virtual && is_gimple_reg (ssa_name)) + { + error ("Found a virtual definition for a GIMPLE register"); + return true; } + if (!is_virtual && !is_gimple_reg (ssa_name)) + { + error ("Found a real definition for a non-register"); + return true; + } + + return false; +} + + +/* Return true if the definition of SSA_NAME at block BB is malformed. + + STMT is the statement where SSA_NAME is created. + + DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME + version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, + it means that the block in that array slot contains the + definition of SSA_NAME. + + IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a + V_MUST_DEF. */ + +static bool +verify_def (basic_block bb, basic_block *definition_block, tree ssa_name, + tree stmt, bool is_virtual) +{ + if (verify_ssa_name (ssa_name, is_virtual)) + goto err; + if (definition_block[SSA_NAME_VERSION (ssa_name)]) { error ("SSA_NAME created in two different blocks %i and %i", definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index); - fprintf (stderr, "SSA_NAME: "); - debug_generic_stmt (ssa_name); - debug_generic_stmt (stmt); - err = true; + goto err; } definition_block[SSA_NAME_VERSION (ssa_name)] = bb; @@ -138,16 +171,22 @@ verify_def (basic_block bb, basic_block *definition_block, tree ssa_name, if (SSA_NAME_DEF_STMT (ssa_name) != stmt) { error ("SSA_NAME_DEF_STMT is wrong"); - fprintf (stderr, "SSA_NAME: "); - debug_generic_stmt (ssa_name); fprintf (stderr, "Expected definition statement:\n"); debug_generic_stmt (SSA_NAME_DEF_STMT (ssa_name)); fprintf (stderr, "\nActual definition statement:\n"); debug_generic_stmt (stmt); - err = true; + goto err; } - return err; + return false; + +err: + fprintf (stderr, "while verifying SSA_NAME "); + print_generic_expr (stderr, ssa_name, 0); + fprintf (stderr, " in statement\n"); + debug_generic_stmt (stmt); + + return true; } @@ -160,16 +199,22 @@ verify_def (basic_block bb, basic_block *definition_block, tree ssa_name, CHECK_ABNORMAL is true if the caller wants to check whether this use is flowing through an abnormal edge (only used when checking PHI - arguments). */ + arguments). + + IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a + V_MUST_DEF. */ static bool verify_use (basic_block bb, basic_block def_bb, tree ssa_name, - tree stmt, bool check_abnormal) + tree stmt, bool check_abnormal, bool is_virtual) { bool err = false; - if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))) - ; /* Nothing to do. */ + err = verify_ssa_name (ssa_name, is_virtual); + + if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name)) + && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name) + ; /* Default definitions have empty statements. Nothing to do. */ else if (!def_bb) { error ("Missing definition"); @@ -193,7 +238,7 @@ verify_use (basic_block bb, basic_block def_bb, tree ssa_name, if (err) { fprintf (stderr, "for SSA_NAME: "); - debug_generic_stmt (ssa_name); + debug_generic_expr (ssa_name); fprintf (stderr, "in statement:\n"); debug_generic_stmt (stmt); } @@ -229,8 +274,9 @@ verify_phi_args (tree phi, basic_block bb, basic_block *definition_block) e = PHI_ARG_EDGE (phi, i); if (TREE_CODE (op) == SSA_NAME) - err |= verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op, - phi, e->flags & EDGE_ABNORMAL); + err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op, + phi, e->flags & EDGE_ABNORMAL, + !is_gimple_reg (PHI_RESULT (phi))); if (e->dest != bb) { @@ -257,6 +303,7 @@ verify_phi_args (tree phi, basic_block bb, basic_block *definition_block) { fprintf (stderr, "PHI argument\n"); debug_generic_stmt (op); + goto error; } e->aux = (void *) 2; @@ -269,10 +316,12 @@ verify_phi_args (tree phi, basic_block bb, basic_block *definition_block) error ("No argument flowing through edge %d->%d\n", e->src->index, e->dest->index); err = true; + goto error; } e->aux = (void *) 0; } +error: if (err) { fprintf (stderr, "for PHI node\n"); @@ -284,18 +333,196 @@ verify_phi_args (tree phi, basic_block bb, basic_block *definition_block) } +static void +verify_flow_insensitive_alias_info (void) +{ + size_t i; + tree var; + bitmap visited = BITMAP_XMALLOC (); + + for (i = 0; i < num_referenced_vars; i++) + { + var_ann_t ann; + + var = referenced_var (i); + ann = var_ann (var); + + if (ann->mem_tag_kind == TYPE_TAG || ann->mem_tag_kind == NAME_TAG) + { + size_t j; + varray_type may_aliases = ann->may_aliases; + + for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++) + { + tree alias = VARRAY_TREE (may_aliases, j); + + bitmap_set_bit (visited, var_ann (alias)->uid); + + if (!may_be_aliased (alias)) + { + error ("Non-addressable variable inside an alias set."); + debug_variable (alias); + goto err; + } + } + } + } + + for (i = 0; i < num_referenced_vars; i++) + { + var_ann_t ann; + + var = referenced_var (i); + ann = var_ann (var); + + if (ann->mem_tag_kind == NOT_A_TAG + && ann->is_alias_tag + && !bitmap_bit_p (visited, ann->uid)) + { + error ("Addressable variable that is an alias tag but is not in any alias set."); + goto err; + } + } + + BITMAP_XFREE (visited); + return; + +err: + debug_variable (var); + internal_error ("verify_flow_insensitive_alias_info failed."); +} + + +static void +verify_flow_sensitive_alias_info (void) +{ + size_t i; + tree ptr; + + for (i = 1; i < num_ssa_names; i++) + { + var_ann_t ann; + struct ptr_info_def *pi; + + ptr = ssa_name (i); + ann = var_ann (SSA_NAME_VAR (ptr)); + pi = SSA_NAME_PTR_INFO (ptr); + + /* We only care for pointers that are actually referenced in the + program. */ + if (!TREE_VISITED (ptr) || !POINTER_TYPE_P (TREE_TYPE (ptr))) + continue; + + /* RESULT_DECL is special. If it's a GIMPLE register, then it + is only written-to only once in the return statement. + Otherwise, aggregate RESULT_DECLs may be written-to more than + once in virtual operands. */ + if (TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL + && is_gimple_reg (ptr)) + continue; + + if (pi == NULL) + continue; + + if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag) + { + error ("Dereferenced pointers should have a name or a type tag"); + goto err; + } + + if (pi->pt_anything && (pi->pt_malloc || pi->pt_vars)) + { + error ("Pointers that point to anything should not point to malloc or other vars"); + goto err; + } + + if (pi->pt_malloc && pi->pt_vars) + { + error ("Pointers pointing to malloc get a unique tag and cannot point to other vars"); + goto err; + } + + if (pi->name_mem_tag + && !pi->pt_malloc + && (pi->pt_vars == NULL + || bitmap_first_set_bit (pi->pt_vars) < 0)) + { + error ("Pointers with a memory tag, should have points-to sets or point to malloc"); + goto err; + } + + if (pi->value_escapes_p + && pi->name_mem_tag + && !is_call_clobbered (pi->name_mem_tag)) + { + error ("Pointer escapes but its name tag is not call-clobbered."); + goto err; + } + + if (pi->name_mem_tag && pi->pt_vars) + { + size_t j; + + for (j = i + 1; j < num_ssa_names; j++) + { + tree ptr2 = ssa_name (j); + struct ptr_info_def *pi2 = SSA_NAME_PTR_INFO (ptr2); + + if (!POINTER_TYPE_P (TREE_TYPE (ptr2))) + continue; + + if (pi2 + && pi2->name_mem_tag + && pi2->pt_vars + && bitmap_first_set_bit (pi2->pt_vars) >= 0 + && pi->name_mem_tag != pi2->name_mem_tag + && bitmap_equal_p (pi->pt_vars, pi2->pt_vars)) + { + error ("Two pointers with different name tags and identical points-to sets"); + debug_variable (ptr2); + goto err; + } + } + } + } + + return; + +err: + debug_variable (ptr); + internal_error ("verify_flow_sensitive_alias_info failed."); +} + + +/* Verify the consistency of aliasing information. */ + +static void +verify_alias_info (void) +{ + if (aliases_computed_p) + { + verify_flow_sensitive_alias_info (); + verify_flow_insensitive_alias_info (); + } +} + + /* Verify common invariants in the SSA web. TODO: verify the variable annotations. */ void verify_ssa (void) { - bool err = false; + size_t i; basic_block bb; basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block)); timevar_push (TV_TREE_SSA_VERIFY); + /* Keep track of SSA names present in the IL. */ + for (i = 1; i < num_ssa_names; i++) + TREE_VISITED (ssa_name (i)) = 0; + calculate_dominance_info (CDI_DOMINATORS); /* Verify and register all the SSA_NAME definitions found in the @@ -306,7 +533,9 @@ verify_ssa (void) block_stmt_iterator bsi; for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - err |= verify_def (bb, definition_block, PHI_RESULT (phi), phi); + if (verify_def (bb, definition_block, PHI_RESULT (phi), phi, + !is_gimple_reg (PHI_RESULT (phi)))) + goto err; for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) { @@ -323,47 +552,33 @@ verify_ssa (void) v_may_defs = V_MAY_DEF_OPS (ann); if (ann->makes_aliased_stores && NUM_V_MAY_DEFS (v_may_defs) == 0) - error ("Makes aliased stores, but no V_MAY_DEFS"); + { + error ("Statement makes aliased stores, but has no V_MAY_DEFS"); + debug_generic_stmt (stmt); + goto err; + } for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++) { tree op = V_MAY_DEF_RESULT (v_may_defs, j); - if (is_gimple_reg (op)) - { - error ("Found a virtual definition for a GIMPLE register"); - debug_generic_stmt (op); - debug_generic_stmt (stmt); - err = true; - } - err |= verify_def (bb, definition_block, op, stmt); + if (verify_def (bb, definition_block, op, stmt, true)) + goto err; } v_must_defs = STMT_V_MUST_DEF_OPS (stmt); for (j = 0; j < NUM_V_MUST_DEFS (v_must_defs); j++) { tree op = V_MUST_DEF_OP (v_must_defs, j); - if (is_gimple_reg (op)) - { - error ("Found a virtual must-def for a GIMPLE register"); - debug_generic_stmt (op); - debug_generic_stmt (stmt); - err = true; - } - err |= verify_def (bb, definition_block, op, stmt); + if (verify_def (bb, definition_block, op, stmt, true)) + goto err; } defs = DEF_OPS (ann); for (j = 0; j < NUM_DEFS (defs); j++) { tree op = DEF_OP (defs, j); - if (TREE_CODE (op) == SSA_NAME && !is_gimple_reg (op)) - { - error ("Found a real definition for a non-GIMPLE register"); - debug_generic_stmt (op); - debug_generic_stmt (stmt); - err = true; - } - err |= verify_def (bb, definition_block, op, stmt); + if (verify_def (bb, definition_block, op, stmt, false)) + goto err; } } } @@ -384,17 +599,16 @@ verify_ssa (void) { error ("AUX pointer initialized for edge %d->%d\n", e->src->index, e->dest->index); - err = true; + goto err; } } /* Verify the arguments for every PHI node in the block. */ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - err |= verify_phi_args (phi, bb, definition_block); - - /* Now verify all the uses and vuses in every statement of the block. + if (verify_phi_args (phi, bb, definition_block)) + goto err; - Remember, the RHS of a V_MAY_DEF is a use as well. */ + /* Now verify all the uses and vuses in every statement of the block. */ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) { tree stmt = bsi_stmt (bsi); @@ -408,58 +622,40 @@ verify_ssa (void) for (j = 0; j < NUM_VUSES (vuses); j++) { tree op = VUSE_OP (vuses, j); - - if (is_gimple_reg (op)) - { - error ("Found a virtual use for a GIMPLE register"); - debug_generic_stmt (op); - debug_generic_stmt (stmt); - err = true; - } - err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)], - op, stmt, false); + if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)], + op, stmt, false, true)) + goto err; } v_may_defs = V_MAY_DEF_OPS (ann); for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++) { tree op = V_MAY_DEF_OP (v_may_defs, j); - - if (is_gimple_reg (op)) - { - error ("Found a virtual use for a GIMPLE register"); - debug_generic_stmt (op); - debug_generic_stmt (stmt); - err = true; - } - err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)], - op, stmt, false); + if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)], + op, stmt, false, true)) + goto err; } uses = USE_OPS (ann); for (j = 0; j < NUM_USES (uses); j++) { tree op = USE_OP (uses, j); - - if (TREE_CODE (op) == SSA_NAME && !is_gimple_reg (op)) - { - error ("Found a real use of a non-GIMPLE register"); - debug_generic_stmt (op); - debug_generic_stmt (stmt); - err = true; - } - err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)], - op, stmt, false); + if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)], + op, stmt, false, false)) + goto err; } } } - free (definition_block); + /* Finally, verify alias information. */ + verify_alias_info (); + free (definition_block); timevar_pop (TV_TREE_SSA_VERIFY); + return; - if (err) - internal_error ("verify_ssa failed."); +err: + internal_error ("verify_ssa failed."); } @@ -598,12 +794,20 @@ tree_ssa_useless_type_conversion (tree expr) /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as - described in walk_use_def_chains. VISITED is a bitmap used to mark - visited SSA_NAMEs to avoid infinite loops. */ + described in walk_use_def_chains. + + VISITED is a bitmap used to mark visited SSA_NAMEs to avoid + infinite loops. + + IS_DFS is true if the caller wants to perform a depth-first search + when visiting PHI nodes. A DFS will visit each PHI argument and + call FN after each one. Otherwise, all the arguments are + visited first and then FN is called with each of the visited + arguments in a separate pass. */ static bool walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data, - bitmap visited) + bitmap visited, bool is_dfs) { tree def_stmt; @@ -617,49 +821,65 @@ walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data, if (TREE_CODE (def_stmt) != PHI_NODE) { /* If we reached the end of the use-def chain, call FN. */ - return (*fn) (var, def_stmt, data); + return fn (var, def_stmt, data); } else { int i; - /* Otherwise, follow use-def links out of each PHI argument and call - FN after visiting each one. */ + /* When doing a breadth-first search, call FN before following the + use-def links for each argument. */ + if (!is_dfs) + for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) + if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data)) + return true; + + /* Follow use-def links out of each PHI argument. */ for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) { tree arg = PHI_ARG_DEF (def_stmt, i); if (TREE_CODE (arg) == SSA_NAME - && walk_use_def_chains_1 (arg, fn, data, visited)) - return true; - - if ((*fn) (arg, def_stmt, data)) + && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs)) return true; } + + /* When doing a depth-first search, call FN after following the + use-def links for each argument. */ + if (is_dfs) + for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) + if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data)) + return true; } + return false; } -/* Walk use-def chains starting at the SSA variable VAR. Call function FN - at each reaching definition found. FN takes three arguments: VAR, its - defining statement (DEF_STMT) and a generic pointer to whatever state - information that FN may want to maintain (DATA). FN is able to stop the - walk by returning true, otherwise in order to continue the walk, FN - should return false. +/* Walk use-def chains starting at the SSA variable VAR. Call + function FN at each reaching definition found. FN takes three + arguments: VAR, its defining statement (DEF_STMT) and a generic + pointer to whatever state information that FN may want to maintain + (DATA). FN is able to stop the walk by returning true, otherwise + in order to continue the walk, FN should return false. Note, that if DEF_STMT is a PHI node, the semantics are slightly - different. For each argument ARG of the PHI node, this function will: + different. The first argument to FN is no longer the original + variable VAR, but the PHI argument currently being examined. If FN + wants to get at VAR, it should call PHI_RESULT (PHI). + + If IS_DFS is true, this function will: - 1- Walk the use-def chains for ARG. - 2- Call (*FN) (ARG, PHI, DATA). + 1- walk the use-def chains for all the PHI arguments, and, + 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments. + + If IS_DFS is false, the two steps above are done in reverse order + (i.e., a breadth-first search). */ - Note how the first argument to FN is no longer the original variable - VAR, but the PHI argument currently being examined. If FN wants to get - at VAR, it should call PHI_RESULT (PHI). */ void -walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data) +walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data, + bool is_dfs) { tree def_stmt; @@ -677,11 +897,12 @@ walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data) else { bitmap visited = BITMAP_XMALLOC (); - walk_use_def_chains_1 (var, fn, data, visited); + walk_use_def_chains_1 (var, fn, data, visited, is_dfs); BITMAP_XFREE (visited); } } + /* Replaces VAR with REPL in memory reference expression *X in statement STMT. */ diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index d4982706676..2785e530b3c 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -160,6 +160,7 @@ make_ssa_name (tree var, tree stmt) SSA_NAME_VAR (t) = var; SSA_NAME_DEF_STMT (t) = stmt; SSA_NAME_PTR_INFO (t) = NULL; + SSA_NAME_IN_FREE_LIST (t) = 0; return t; } @@ -176,6 +177,11 @@ make_ssa_name (tree var, tree stmt) void release_ssa_name (tree var) { + /* Never release the default definition for a symbol. It's a + special SSA name that should always exist once it's created. */ + if (var == var_ann (SSA_NAME_VAR (var))->default_def) + return; + /* release_ssa_name can be called multiple times on a single SSA_NAME. However, it should only end up on our free list one time. We keep a status bit in the SSA_NAME node itself to indicate it has @@ -216,4 +222,31 @@ duplicate_ssa_name (tree name, tree stmt) return new_name; } + +/* Release all the SSA_NAMEs created by STMT. */ + +void +release_defs (tree stmt) +{ + size_t i; + v_may_def_optype v_may_defs; + v_must_def_optype v_must_defs; + def_optype defs; + stmt_ann_t ann; + + ann = stmt_ann (stmt); + defs = DEF_OPS (ann); + v_may_defs = V_MAY_DEF_OPS (ann); + v_must_defs = V_MUST_DEF_OPS (ann); + + for (i = 0; i < NUM_DEFS (defs); i++) + release_ssa_name (DEF_OP (defs, i)); + + for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++) + release_ssa_name (V_MAY_DEF_RESULT (v_may_defs, i)); + + for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++) + release_ssa_name (V_MUST_DEF_OP (v_must_defs, i)); +} + #include "gt-tree-ssanames.h" diff --git a/gcc/tree.h b/gcc/tree.h index 41d967c3465..1962d72dff5 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -2647,6 +2647,8 @@ extern void fini_ssanames (void); extern tree make_ssa_name (tree, tree); extern tree duplicate_ssa_name (tree, tree); extern void release_ssa_name (tree); +extern void release_defs (tree); + #ifdef GATHER_STATISTICS extern void ssanames_print_statistics (void); #endif -- 2.11.4.GIT