From d8903b30e16fb86408db4bcc57db09817d59b290 Mon Sep 17 00:00:00 2001 From: Diego Novillo Date: Fri, 9 Jul 2004 15:12:48 +0000 Subject: [PATCH] tree-dfa.c (dump_variable): If the variable is a pointer SSA_NAME, also dump its points-to information. * tree-dfa.c (dump_variable): If the variable is a pointer SSA_NAME, also dump its points-to information. * tree-flow.h (struct ptr_info_def): Add field is_dereferenced. (dump_points_to_info_for): Declare. (debug_points_to_info_for): Declare. * tree-optimize.c (init_tree_optimization_passes): Add a second alias analysis pass after DOM2. Move pass_del_pta to a later spot. * tree-ssa-alias.c (compute_points_to_and_addr_escape): Do not create a name tags when we find a dereferenced pointer. Just mark the pointer dereferenced. (collect_points_to_info_for): Move code to clear points-to information to create_name_tags. (create_name_tags): New function. (compute_flow_sensitive_aliasing): Call it. (setup_pointers_and_addressables): Mark type tags for renaming here instead of ... (create_memory_tag): ... here. (merge_pointed_to_info): Do not merge PT_MALLOC attributes. (dump_points_to_info_for): Declare extern. (debug_points_to_info_for): New function. From-SVN: r84377 --- gcc/ChangeLog | 25 +++++ gcc/tree-dfa.c | 10 +- gcc/tree-flow.h | 5 + gcc/tree-optimize.c | 3 +- gcc/tree-ssa-alias.c | 232 ++++++++++++++++++++++++++++++++----------- 5 files changed, 213 insertions(+), 62 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index c4c785e8d9f..db3debc2589 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,28 @@ +2004-07-09 Diego Novillo + + * tree-dfa.c (dump_variable): If the variable is a pointer + SSA_NAME, also dump its points-to information. + * tree-flow.h (struct ptr_info_def): Add field + is_dereferenced. + (dump_points_to_info_for): Declare. + (debug_points_to_info_for): Declare. + * tree-optimize.c (init_tree_optimization_passes): Add a + second alias analysis pass after DOM2. + Move pass_del_pta to a later spot. + * tree-ssa-alias.c (compute_points_to_and_addr_escape): Do not + create a name tags when we find a dereferenced pointer. Just + mark the pointer dereferenced. + (collect_points_to_info_for): Move code to clear points-to + information to create_name_tags. + (create_name_tags): New function. + (compute_flow_sensitive_aliasing): Call it. + (setup_pointers_and_addressables): Mark type tags for renaming + here instead of ... + (create_memory_tag): ... here. + (merge_pointed_to_info): Do not merge PT_MALLOC attributes. + (dump_points_to_info_for): Declare extern. + (debug_points_to_info_for): New function. + 2004-07-09 Paolo Bonzini * config/arc/arc.md: Switch to DFA-based scheduler description. diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c index 99f998f9c1d..7eab7c6687e 100644 --- a/gcc/tree-dfa.c +++ b/gcc/tree-dfa.c @@ -534,6 +534,13 @@ void dump_variable (FILE *file, tree var) { var_ann_t ann; + + if (TREE_CODE (var) == SSA_NAME) + { + if (POINTER_TYPE_P (TREE_TYPE (var))) + dump_points_to_info_for (file, var); + var = SSA_NAME_VAR (var); + } if (var == NULL_TREE) { @@ -542,9 +549,6 @@ dump_variable (FILE *file, tree var) } print_generic_expr (file, var, dump_flags); - - if (TREE_CODE (var) == SSA_NAME) - var = SSA_NAME_VAR (var); ann = var_ann (var); diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 102b6ea5f04..cc2cb16830d 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -59,6 +59,9 @@ struct ptr_info_def GTY(()) /* Nonzero if the value of this pointer escapes the current function. */ unsigned int value_escapes_p : 1; + /* Nonzero if this pointer is dereferenced. */ + unsigned int is_dereferenced : 1; + /* Set of variables that this pointer may point to. */ bitmap pt_vars; @@ -550,6 +553,8 @@ extern void dump_alias_info (FILE *); extern void debug_alias_info (void); extern void dump_points_to_info (FILE *); extern void debug_points_to_info (void); +extern void dump_points_to_info_for (FILE *, tree); +extern void debug_points_to_info_for (tree); /* Call-back function for walk_use_def_chains(). At each reaching definition, a function with this prototype is called. */ diff --git a/gcc/tree-optimize.c b/gcc/tree-optimize.c index 750c7af7b4f..aa65ab93c22 100644 --- a/gcc/tree-optimize.c +++ b/gcc/tree-optimize.c @@ -294,7 +294,6 @@ init_tree_optimization_passes (void) NEXT_PASS (pass_may_alias); NEXT_PASS (pass_tail_recursion); NEXT_PASS (pass_ch); - NEXT_PASS (pass_del_pta); NEXT_PASS (pass_profile); NEXT_PASS (pass_lower_complex); NEXT_PASS (pass_sra); @@ -303,6 +302,7 @@ init_tree_optimization_passes (void) NEXT_PASS (DUP_PASS (pass_redundant_phi)); NEXT_PASS (DUP_PASS (pass_dce)); NEXT_PASS (pass_dse); + NEXT_PASS (DUP_PASS (pass_may_alias)); NEXT_PASS (DUP_PASS (pass_forwprop)); NEXT_PASS (DUP_PASS (pass_phiopt)); NEXT_PASS (pass_ccp); @@ -320,6 +320,7 @@ init_tree_optimization_passes (void) NEXT_PASS (pass_tail_calls); NEXT_PASS (pass_late_warn_uninitialized); NEXT_PASS (pass_warn_function_return); + NEXT_PASS (pass_del_pta); NEXT_PASS (pass_del_ssa); NEXT_PASS (pass_nrv); NEXT_PASS (pass_remove_useless_vars); diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index 3cf27ae6a6b..cc0a00a559b 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -432,21 +432,9 @@ collect_points_to_info_for (struct alias_info *ai, tree ptr) if (!bitmap_bit_p (ai->ssa_names_visited, SSA_NAME_VERSION (ptr))) { - struct ptr_info_def *pi; - bitmap_set_bit (ai->ssa_names_visited, SSA_NAME_VERSION (ptr)); walk_use_def_chains (ptr, collect_points_to_info_r, ai); - VARRAY_PUSH_TREE (ai->processed_ptrs, ptr); - - /* If we could not determine where PTR was pointing to, clear all the - other points-to information. */ - pi = SSA_NAME_PTR_INFO (ptr); - if (pi->pt_anything) - { - pi->pt_malloc = 0; - pi->pt_vars = NULL; - } } } @@ -609,15 +597,12 @@ compute_points_to_and_addr_escape (struct alias_info *ai) if (ptr_is_dereferenced_by (op, stmt, &is_store)) { /* If we found OP to point to a set of variables or - malloc, then create a name memory tag for it. This - gives more precise aliasing information, which helps - the optimizers. - - FIXME: Cycles in the SSA web and the lack of SSA - information for structures will prevent the creation - of name tags. Find ways around this limitation. */ + malloc, then mark it as being dereferenced. In a + subsequent pass, dereferenced pointers that point + to a set of variables will be assigned a name tag + to alias all the variables OP points to. */ if (pi->pt_malloc || pi->pt_vars) - pi->name_mem_tag = get_nmt_for (op); + pi->is_dereferenced = 1; /* Keep track of how many time we've dereferenced each pointer. Again, we don't need to grow @@ -695,6 +680,92 @@ compute_points_to_and_addr_escape (struct alias_info *ai) } +/* Create name tags for all the pointers that have been dereferenced. + We only create a name tag for a pointer P if P is found to point to + a set of variables (so that we can alias them to *P) or if it is + the result of a call to malloc (which means that P cannot point to + anything else nor alias any other variable). + + If two pointers P and Q point to the same set of variables, they + are assigned the same name tag. */ + +static void +create_name_tags (struct alias_info *ai) +{ + size_t i; + + for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++) + { + 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; + + /* If PTR points to a set of variables, check if we don't + have another pointer Q with the same points-to set before + creating a tag. If so, use Q's tag instead of creating a + new one. + + This is important for not creating unnecessary symbols + and also for copy propagation. If we ever need to + propagate PTR into Q or vice-versa, we would run into + 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); + struct ptr_info_def *qi = SSA_NAME_PTR_INFO (q); + + if (qi + && qi->pt_vars + && qi->name_mem_tag + && bitmap_equal_p (pi->pt_vars, qi->pt_vars)) + { + pi->name_mem_tag = qi->name_mem_tag; + break; + } + } + + if (pi->name_mem_tag == NULL_TREE) + pi->name_mem_tag = get_nmt_for (ptr); + } + else if (pi->pt_malloc) + { + /* Otherwise, create a unique name tag for this pointer. */ + pi->name_mem_tag = get_nmt_for (ptr); + } + else + { + /* Only pointers that may point to malloc or other variables + may receive a name tag. If the pointer does not point to + a known spot, we should use type tags. */ + abort (); + } + + /* Mark the new name tag for renaming. */ + bitmap_set_bit (vars_to_rename, var_ann (pi->name_mem_tag)->uid); + } +} + + + /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for the name memory tag (NMT) associated with P_i. If P_i escapes, then its name tag and the variables it points-to are call-clobbered. Finally, if @@ -708,6 +779,8 @@ compute_flow_sensitive_aliasing (struct alias_info *ai) { size_t i; + create_name_tags (ai); + for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++) { size_t j; @@ -1173,10 +1246,10 @@ setup_pointers_and_addressables (struct alias_info *ai) tree var = referenced_var (i); var_ann_t v_ann = var_ann (var); - /* Name memory tags already have flow-sensitive aliasing information, so - they need not be processed by compute_may_aliases. Similarly, - type memory tags are already accounted for when we process their - associated pointer. */ + /* Name memory tags already have flow-sensitive aliasing + information, so they need not be processed by + compute_may_aliases. Similarly, type memory tags are already + accounted for when we process their associated pointer. */ if (v_ann->mem_tag_kind != NOT_A_TAG) continue; @@ -1192,8 +1265,9 @@ setup_pointers_and_addressables (struct alias_info *ai) && v_ann->mem_tag_kind == NOT_A_TAG && !needs_to_live_in_memory (var)) { - /* The address of VAR is not needed, remove the addressable bit, - so that it can be optimized as a regular variable. */ + /* The address of VAR is not needed, remove the + addressable bit, so that it can be optimized as a + regular variable. */ mark_non_addressable (var); /* Since VAR is now a regular GIMPLE register, we will need @@ -1227,12 +1301,18 @@ setup_pointers_and_addressables (struct alias_info *ai) tree tag = v_ann->type_mem_tag; var_ann_t t_ann; - /* If pointer VAR still doesn't have a memory tag associated with it, - create it now or re-use an existing one. */ + /* 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); t_ann = var_ann (tag); + /* The type tag will need to be renamed into SSA afterwards. + Note that we cannot do this inside get_tmt_for because + aliasing may run multiple times and we only create type + tags the first time. */ + bitmap_set_bit (vars_to_rename, t_ann->uid); + /* Associate the tag with pointer VAR. */ v_ann->type_mem_tag = tag; @@ -1548,7 +1628,32 @@ merge_pointed_to_info (struct alias_info *ai, tree dest, tree orig) if (orig_pi) { dest_pi->pt_anything |= orig_pi->pt_anything; - dest_pi->pt_malloc |= orig_pi->pt_malloc; + + /* 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: + + P_i = malloc (); + ... + P_j = P_i + X; + + P_j would be marked as PT_MALLOC, which is wrong because + PT_MALLOC implies that the pointer may not point to another + variable. + + FIXME 1: Subsequent analysis may determine that P_j + cannot alias anything else, but we are being conservative + here. + + FIXME 2: If the merging comes from a copy assignment, we + ought to merge PT_MALLOC, but then both pointers would end up + getting different name tags because create_name_tags is not + smart enough to determine that the two come from the same + 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) { @@ -1559,9 +1664,9 @@ merge_pointed_to_info (struct alias_info *ai, tree dest, tree orig) } else bitmap_a_or_b (dest_pi->pt_vars, - dest_pi->pt_vars, - orig_pi->pt_vars); - } + dest_pi->pt_vars, + orig_pi->pt_vars); + } } } @@ -1821,9 +1926,8 @@ create_memory_tag (tree type, bool is_type_tag) ann->mem_tag_kind = (is_type_tag) ? TYPE_TAG : NAME_TAG; ann->type_mem_tag = NULL_TREE; - /* Add the tag to the symbol table and mark it for renaming. */ + /* Add the tag to the symbol table. */ add_referenced_tmp_var (tag); - bitmap_set_bit (vars_to_rename, ann->uid); return tag; } @@ -2030,7 +2134,7 @@ get_ptr_info (tree t) /* Dump points-to information for SSA_NAME PTR into FILE. */ -static void +void dump_points_to_info_for (FILE *file, tree ptr) { struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); @@ -2038,41 +2142,53 @@ dump_points_to_info_for (FILE *file, tree ptr) fprintf (file, "Pointer "); print_generic_expr (file, ptr, dump_flags); - if (pi == NULL) - return; - - if (pi->name_mem_tag) + if (pi) { - fprintf (file, ", name memory tag: "); - print_generic_expr (file, pi->name_mem_tag, dump_flags); - } + if (pi->name_mem_tag) + { + fprintf (file, ", name memory tag: "); + print_generic_expr (file, pi->name_mem_tag, dump_flags); + } - if (pi->value_escapes_p) - fprintf (file, ", its value escapes"); + if (pi->is_dereferenced) + fprintf (file, ", is dereferenced"); - if (pi->pt_anything) - fprintf (file, ", points-to anything"); + if (pi->value_escapes_p) + fprintf (file, ", its value escapes"); - if (pi->pt_malloc) - fprintf (file, ", points-to malloc"); + if (pi->pt_anything) + fprintf (file, ", points-to anything"); - if (pi->pt_vars) - { - unsigned ix; + if (pi->pt_malloc) + fprintf (file, ", points-to malloc"); - fprintf (file, ", points-to vars: { "); - EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, - { - print_generic_expr (file, referenced_var (ix), dump_flags); - fprintf (file, " "); - }); - fprintf (file, "}"); + if (pi->pt_vars) + { + unsigned ix; + + fprintf (file, ", points-to vars: { "); + EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, + { + print_generic_expr (file, referenced_var (ix), dump_flags); + fprintf (file, " "); + }); + fprintf (file, "}"); + } } fprintf (file, "\n"); } +/* Dump points-to information for VAR into stderr. */ + +void +debug_points_to_info_for (tree var) +{ + dump_points_to_info_for (stderr, var); +} + + /* Dump points-to information into FILE. NOTE: This function is slow, as it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */ -- 2.30.2