--- gcc/testsuite/gcc.dg/tree-ssa/20040517-1.c (/mirror/gcc-trunk) (revision 473) +++ gcc/testsuite/gcc.dg/tree-ssa/20040517-1.c (/local/gcc-clean) (revision 473) @@ -17,5 +17,6 @@ void bar (void) malloc functions may clobber global memory. Only the function result does not alias any other pointer. Hence, we must have a VDEF for a before and after the call to foo(). */ -/* { dg-final { scan-tree-dump-times "V_MAY_DEF" 2 "alias1"} } */ +/* { dg-final { scan-tree-dump-times "V_MAY_DEF" 1 "alias1"} } */ +/* { dg-final { scan-tree-dump-times "V_MUST_DEF" 1 "alias1"} } */ /* { dg-final { cleanup-tree-dump "alias1" } } */ --- gcc/testsuite/gcc.dg/tree-ssa/pr26421.c (/mirror/gcc-trunk) (revision 473) +++ gcc/testsuite/gcc.dg/tree-ssa/pr26421.c (/local/gcc-clean) (revision 473) @@ -16,5 +16,6 @@ int foo(void) return a.i; } -/* { dg-final { scan-tree-dump-times "V_MAY_DEF" 2 "alias1" } } */ +/* { dg-final { scan-tree-dump-times "V_MAY_DEF" 1 "alias1" } } */ +/* { dg-final { scan-tree-dump-times "V_MUST_DEF" 1 "alias1" } } */ /* { dg-final { cleanup-tree-dump "alias1" } } */ --- gcc/testsuite/gcc.dg/tree-ssa/20031015-1.c (/mirror/gcc-trunk) (revision 473) +++ gcc/testsuite/gcc.dg/tree-ssa/20031015-1.c (/local/gcc-clean) (revision 473) @@ -14,5 +14,5 @@ main(void) } /* The V_*_DEF comes from the initial assignment and the asm. */ -/* { dg-final { scan-tree-dump-times "_DEF" 3 "alias1" } } */ +/* { dg-final { scan-tree-dump-times "_DEF" 2 "alias1" } } */ /* { dg-final { cleanup-tree-dump "alias1" } } */ --- gcc/tree-ssa-alias.c (/mirror/gcc-trunk) (revision 473) +++ gcc/tree-ssa-alias.c (/local/gcc-clean) (revision 473) @@ -646,16 +646,14 @@ compute_may_aliases (void) not needed anymore. */ setup_pointers_and_addressables (ai); - /* Compute flow-sensitive, points-to based aliasing for all the name - memory tags. Note that this pass needs to be done before flow - insensitive analysis because it uses the points-to information - gathered before to mark call-clobbered symbol tags. */ - compute_flow_sensitive_aliasing (ai); - /* Compute type-based flow-insensitive aliasing for all the type memory tags. */ compute_flow_insensitive_aliasing (ai); + /* Compute flow-sensitive, points-to based aliasing for all the name + memory tags. */ + compute_flow_sensitive_aliasing (ai); + /* Compute call clobbering information. */ compute_call_clobbered (ai); @@ -1121,6 +1119,7 @@ compute_flow_sensitive_aliasing (struct EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi) { add_may_alias (pi->name_mem_tag, referenced_var (j)); + if (j != DECL_UID (v_ann->symbol_mem_tag)) add_may_alias (v_ann->symbol_mem_tag, referenced_var (j)); } } --- gcc/alias.c (/mirror/gcc-trunk) (revision 473) +++ gcc/alias.c (/local/gcc-clean) (revision 473) @@ -293,6 +293,26 @@ insert_subset_children (splay_tree_node return 0; } +/* Return true if the first alias set is a subset of the second. */ + +bool +alias_set_subset_of (HOST_WIDE_INT set1, HOST_WIDE_INT set2) +{ + alias_set_entry ase; + + /* Everything is a subset of the "aliases everything" set. */ + if (set2 == 0) + return true; + + /* Otherwise, check if set1 is a subset of set2. */ + ase = get_alias_set_entry (set2); + if (ase != 0 + && (splay_tree_lookup (ase->children, + (splay_tree_key) set1))) + return true; + return false; +} + /* Return 1 if the two specified alias sets may conflict. */ int --- gcc/alias.h (/mirror/gcc-trunk) (revision 473) +++ gcc/alias.h (/local/gcc-clean) (revision 473) @@ -25,6 +25,7 @@ extern HOST_WIDE_INT new_alias_set (void extern HOST_WIDE_INT get_varargs_alias_set (void); extern HOST_WIDE_INT get_frame_alias_set (void); extern bool component_uses_parent_alias_set (tree); +extern bool alias_set_subset_of (HOST_WIDE_INT, HOST_WIDE_INT); /* This alias set can be used to force a memory to conflict with all other memories, creating a barrier across which no memory reference --- gcc/tree-ssa.c (/mirror/gcc-trunk) (revision 473) +++ gcc/tree-ssa.c (/local/gcc-clean) (revision 473) @@ -488,131 +488,6 @@ err: internal_error ("verify_flow_sensitive_alias_info failed"); } -DEF_VEC_P (bitmap); -DEF_VEC_ALLOC_P (bitmap,heap); - -/* Verify that all name tags have different points to sets. - This algorithm takes advantage of the fact that every variable with the - same name tag must have the same points-to set. - So we check a single variable for each name tag, and verify that its - points-to set is different from every other points-to set for other name - tags. - - Additionally, given a pointer P_i with name tag NMT and symbol tag - SMT, this function verified the alias set of SMT is a superset of - the alias set of NMT. */ - -static void -verify_name_tags (void) -{ - size_t i; - size_t j; - bitmap first, second; - VEC(tree,heap) *name_tag_reps = NULL; - VEC(bitmap,heap) *pt_vars_for_reps = NULL; - bitmap type_aliases = BITMAP_ALLOC (NULL); - - /* First we compute the name tag representatives and their points-to sets. */ - for (i = 0; i < num_ssa_names; i++) - { - struct ptr_info_def *pi; - tree smt, ptr = ssa_name (i); - - if (ptr == NULL_TREE) - continue; - - pi = SSA_NAME_PTR_INFO (ptr); - - if (!TREE_VISITED (ptr) - || !POINTER_TYPE_P (TREE_TYPE (ptr)) - || !pi - || !pi->name_mem_tag - || TREE_VISITED (pi->name_mem_tag)) - continue; - - TREE_VISITED (pi->name_mem_tag) = 1; - - if (pi->pt_vars == NULL) - continue; - - VEC_safe_push (tree, heap, name_tag_reps, ptr); - VEC_safe_push (bitmap, heap, pt_vars_for_reps, pi->pt_vars); - - /* Verify that alias set of PTR's symbol tag is a superset of the - alias set of PTR's name tag. */ - smt = var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag; - if (smt) - { - size_t i; - VEC(tree,gc) *aliases = var_ann (smt)->may_aliases; - tree alias; - - bitmap_clear (type_aliases); - for (i = 0; VEC_iterate (tree, aliases, i, alias); i++) - bitmap_set_bit (type_aliases, DECL_UID (alias)); - - /* When grouping, we may have added PTR's symbol tag into the - alias set of PTR's name tag. To prevent a false - positive, pretend that SMT is in its own alias set. */ - bitmap_set_bit (type_aliases, DECL_UID (smt)); - - if (bitmap_equal_p (type_aliases, pi->pt_vars)) - continue; - - if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars)) - { - error ("alias set of a pointer's symbol tag should be a superset of the corresponding name tag"); - debug_variable (smt); - debug_variable (pi->name_mem_tag); - goto err; - } - } - } - - /* Now compare all the representative bitmaps with all other representative - bitmaps, to verify that they are all different. */ - for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++) - { - for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++) - { - if (bitmap_equal_p (first, second)) - { - error ("two different pointers with identical points-to sets but different name tags"); - debug_variable (VEC_index (tree, name_tag_reps, j)); - goto err; - } - } - } - - /* Lastly, clear out the visited flags. */ - for (i = 0; i < num_ssa_names; i++) - { - if (ssa_name (i)) - { - tree ptr = ssa_name (i); - struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); - if (!TREE_VISITED (ptr) - || !POINTER_TYPE_P (TREE_TYPE (ptr)) - || !pi - || !pi->name_mem_tag) - continue; - TREE_VISITED (pi->name_mem_tag) = 0; - } - } - - /* We do not have to free the bitmaps or trees in the vectors, as - they are not owned by us. */ - VEC_free (bitmap, heap, pt_vars_for_reps); - VEC_free (tree, heap, name_tag_reps); - BITMAP_FREE (type_aliases); - return; - -err: - debug_variable (VEC_index (tree, name_tag_reps, i)); - internal_error ("verify_name_tags failed"); -} - - /* Verify the consistency of call clobbering information. */ static void verify_call_clobbering (void) @@ -659,7 +534,6 @@ static void verify_alias_info (void) { verify_flow_sensitive_alias_info (); - verify_name_tags (); verify_call_clobbering (); verify_flow_insensitive_alias_info (); } --- gcc/Makefile.in (/mirror/gcc-trunk) (revision 473) +++ gcc/Makefile.in (/local/gcc-clean) (revision 473) @@ -1837,7 +1837,7 @@ stor-layout.o : stor-layout.c $(CONFIG_H tree-ssa-structalias.o: tree-ssa-structalias.c tree-ssa-structalias.h \ $(SYSTEM_H) $(CONFIG_H) $(GGC_H) $(TREE_H) $(TREE_FLOW_H) \ $(TM_H) coretypes.h $(CGRAPH_H) tree-pass.h $(TIMEVAR_H) \ - gt-tree-ssa-structalias.h $(PARAMS_H) + gt-tree-ssa-structalias.h $(PARAMS_H) $(ALIAS_H) tree-ssa.o : tree-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h $(DIAGNOSTIC_H) \ toplev.h $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h \ --- gcc/tree-ssa-structalias.c (/mirror/gcc-trunk) (revision 473) +++ gcc/tree-ssa-structalias.c (/local/gcc-clean) (revision 473) @@ -51,6 +51,7 @@ Foundation, Inc., 51 Franklin Street, Fi #include "params.h" #include "tree-ssa-structalias.h" #include "cgraph.h" +#include "alias.h" /* The idea behind this analyzer is to generate set constraints from the program, then solve the resulting constraints in order to generate the @@ -72,9 +73,10 @@ Foundation, Inc., 51 Franklin Street, Fi of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at http://citeseer.ist.psu.edu/heintze01ultrafast.html - There are three types of constraint expressions, DEREF, ADDRESSOF, and - SCALAR. Each constraint expression consists of a constraint type, - a variable, and an offset. + There are three types of real constraint expressions, DEREF, + ADDRESSOF, and SCALAR. There is one type of fake constraint + expression, called INCLUDES. Each constraint expression consists + of a constraint type, a variable, and an offset. SCALAR is a constraint expression type used to represent x, whether it appears on the LHS or the RHS of a statement. @@ -82,6 +84,10 @@ Foundation, Inc., 51 Franklin Street, Fi it appears on the LHS or the RHS of a statement. ADDRESSOF is a constraint expression used to represent &x, whether it appears on the LHS or the RHS of a statement. + INCLUDES is a constraint expression type used to represent just a + setting of a bit in the points-to set without having the address + taken. It exists mainly for abstraction sake, and is used for + initializing fake variables like the ESCAPED_VARS set. Each pointer variable in the program is assigned an integer id, and each field of a structure variable is assigned an integer id as well. @@ -252,6 +258,10 @@ struct variable_info /* Points-to set for this variable. */ bitmap solution; + /* Finished points-to set for this variable (IE what is returned + from find_what_p_points_to. */ + bitmap finished_solution; + /* Variable ids represented by this node. */ bitmap variables; @@ -320,16 +330,6 @@ static varinfo_t var_integer; static tree integer_tree; static unsigned int integer_id; -/* Variable that represents escaped variables. This is used to give - incoming pointer variables a better set than ANYTHING. */ -static varinfo_t var_escaped_vars; -static tree escaped_vars_tree; -static unsigned int escaped_vars_id; - -/* Variable that represents non-local variables before we expand it to - one for each type. */ -static unsigned int nonlocal_vars_id; - /* Lookup a heap var for FROM, and return it if we find one. */ static tree @@ -383,13 +383,14 @@ new_var_info (tree t, unsigned int id, c ret->has_union = false; ret->solution = BITMAP_ALLOC (&ptabitmap_obstack); ret->variables = BITMAP_ALLOC (&ptabitmap_obstack); + ret->finished_solution = NULL; ret->complex = NULL; ret->next = NULL; ret->collapsed_to = NULL; return ret; } -typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type; +typedef enum {SCALAR, DEREF, ADDRESSOF, INCLUDES} constraint_expr_type; /* An expression that appears in a constraint. */ @@ -445,7 +446,6 @@ struct constraint_graph typedef struct constraint_graph *constraint_graph_t; static constraint_graph_t graph; -static int graph_size; /* Create a new constraint consisting of LHS and RHS expressions. */ @@ -476,9 +476,13 @@ dump_constraint (FILE *file, constraint_ fprintf (file, "&"); else if (c->rhs.type == DEREF) fprintf (file, "*"); + else if (c->rhs.type == INCLUDES) + fprintf (file, "{"); fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name); if (c->rhs.offset != 0) fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset); + if (c->rhs.type == INCLUDES) + fprintf (file, "}"); fprintf (file, "\n"); } @@ -868,6 +872,7 @@ build_constraint_graph (void) { int i = 0; constraint_t c; + int graph_size; graph = XNEW (struct constraint_graph); graph_size = VEC_length (varinfo_t, varmap) + 1; @@ -893,7 +898,7 @@ build_constraint_graph (void) if (!(get_varinfo (lhsvar)->is_special_var)) insert_into_complex (rhsvar, c); } - else if (rhs.type == ADDRESSOF) + else if (rhs.type == ADDRESSOF || rhs.type == INCLUDES) { /* x = &y */ bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar); @@ -993,18 +998,24 @@ scc_visit (constraint_graph_t graph, str } -/* Collapse two variables into one variable. */ +/* Collapse two variables into one variable, merging solutions if + requested. */ static void -collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from) +collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from, + bool merge_solutions) { bitmap tosol, fromsol; + merge_graph_nodes (graph, to, from); condense_varmap_nodes (to, from); + if (merge_solutions) + { tosol = get_varinfo (to)->solution; fromsol = get_varinfo (from)->solution; bitmap_ior_into (tosol, fromsol); - merge_graph_nodes (graph, to, from); + BITMAP_FREE (fromsol); + } if (valid_graph_edge (graph, to, to)) { @@ -1014,9 +1025,6 @@ collapse_nodes (constraint_graph_t graph bitmap_clear_bit (graph->succs[to], to); } } - BITMAP_FREE (fromsol); - get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken; - get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target; } @@ -1071,8 +1079,7 @@ process_unification_queue (constraint_gr else stats.unified_vars_static++; bitmap_ior_into (tmp, get_varinfo (tounify)->solution); - merge_graph_nodes (graph, n, tounify); - condense_varmap_nodes (n, tounify); + collapse_nodes (graph, n, tounify, false); if (update_changed && TEST_BIT (changed, tounify)) { @@ -1577,7 +1584,7 @@ perform_var_substitution (constraint_gra { /* Found an equivalence */ get_varinfo (i)->node = root; - collapse_nodes (graph, root, i); + collapse_nodes (graph, root, i, true); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Collapsing %s into %s\n", get_varinfo (i)->name, @@ -1843,7 +1850,7 @@ get_constraint_exp_from_ssa_var (tree t) say it points to readonly memory instead. */ if (cexpr.var == anything_id && TREE_READONLY (t)) { - cexpr.type = ADDRESSOF; + cexpr.type = INCLUDES; cexpr.var = readonly_id; } @@ -1863,17 +1870,26 @@ process_constraint (constraint_t t) gcc_assert (rhs.var < VEC_length (varinfo_t, varmap)); gcc_assert (lhs.var < VEC_length (varinfo_t, varmap)); + gcc_assert (lhs.type != INCLUDES); + if (lhs.type == DEREF) get_varinfo (lhs.var)->directly_dereferenced = true; if (rhs.type == DEREF) get_varinfo (rhs.var)->directly_dereferenced = true; + if (!use_field_sensitive) + { + t->rhs.offset = 0; + t->lhs.offset = 0; + } + /* ANYTHING == ANYTHING is pointless. */ if (lhs.var == anything_id && rhs.var == anything_id) return; /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */ - else if (lhs.var == anything_id && lhs.type == ADDRESSOF) + else if (lhs.var == anything_id + && (lhs.type == INCLUDES || lhs.type == ADDRESSOF)) { rhs = t->lhs; t->lhs = t->rhs; @@ -1904,9 +1920,6 @@ process_constraint (constraint_t t) varinfo_t vi; gcc_assert (rhs.offset == 0); - /* No need to mark address taken simply because of escaped vars - constraints. */ - if (lhs.var != escaped_vars_id) for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next) vi->address_taken = true; @@ -2090,21 +2104,6 @@ do_deref (VEC (ce_s, heap) **constraints } } -/* Create a nonlocal variable of TYPE to represent nonlocals we can - alias. */ - -static tree -create_nonlocal_var (tree type) -{ - tree nonlocal = create_tmp_var_raw (type, "NONLOCAL"); - - if (gimple_referenced_vars (cfun)) - add_referenced_var (nonlocal); - - DECL_EXTERNAL (nonlocal) = 1; - return nonlocal; -} - /* Given a tree T, return the constraint expression for it. */ static void @@ -2232,14 +2231,14 @@ get_constraint_for (tree t, VEC (ce_s, h vi = get_varinfo (temp.var); vi->is_artificial_var = 1; vi->is_heap_var = 1; - temp.type = ADDRESSOF; + temp.type = INCLUDES; temp.offset = 0; VEC_safe_push (ce_s, heap, *results, &temp); return; } else { - temp.var = escaped_vars_id; + temp.var = anything_id; temp.type = SCALAR; temp.offset = 0; VEC_safe_push (ce_s, heap, *results, &temp); @@ -2810,7 +2809,8 @@ update_alias_info (tree stmt, struct ali /* If the statement makes a function call, assume that pointer OP will be dereferenced in a store operation inside the called function. */ - if (get_call_expr_in (stmt)) + if (get_call_expr_in (stmt) + || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL) { bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var)); pi->is_dereferenced = 1; @@ -3388,9 +3388,9 @@ push_fields_onto_fieldstack (tree type, return count; } -/* Create a constraint from ESCAPED_VARS variable to VI. */ +/* Create a constraint from ANYTHING variable to VI. */ static void -make_constraint_from_escaped (varinfo_t vi) +make_constraint_from_anything (varinfo_t vi) { struct constraint_expr lhs, rhs; @@ -3398,24 +3398,9 @@ make_constraint_from_escaped (varinfo_t lhs.offset = 0; lhs.type = SCALAR; - rhs.var = escaped_vars_id; + rhs.var = anything_id; rhs.offset = 0; - rhs.type = SCALAR; - process_constraint (new_constraint (lhs, rhs)); -} - -/* Create a constraint to the ESCAPED_VARS variable from constraint - expression RHS. */ - -static void -make_constraint_to_escaped (struct constraint_expr rhs) -{ - struct constraint_expr lhs; - - lhs.var = escaped_vars_id; - lhs.offset = 0; - lhs.type = SCALAR; - + rhs.type = INCLUDES; process_constraint (new_constraint (lhs, rhs)); } @@ -3569,59 +3554,6 @@ check_for_overlaps (VEC (fieldoff_s,heap return false; } -/* This function is called through walk_tree to walk global - initializers looking for constraints we need to add to the - constraint list. */ - -static tree -find_global_initializers (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, - void *viv) -{ - varinfo_t vi = (varinfo_t)viv; - tree t = *tp; - - switch (TREE_CODE (t)) - { - /* Dereferences and addressofs are the only important things - here, and i don't even remember if dereferences are legal - here in initializers. */ - case INDIRECT_REF: - case ADDR_EXPR: - { - struct constraint_expr *c; - size_t i; - - VEC(ce_s, heap) *rhsc = NULL; - get_constraint_for (t, &rhsc); - for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) - { - struct constraint_expr lhs; - - lhs.var = vi->id; - lhs.type = SCALAR; - lhs.offset = 0; - process_constraint (new_constraint (lhs, *c)); - } - - VEC_free (ce_s, heap, rhsc); - } - break; - case VAR_DECL: - /* We might not have walked this because we skip - DECL_EXTERNALs during the initial scan. */ - if (gimple_referenced_vars (cfun)) - { - get_var_ann (t); - if (referenced_var_check_and_insert (t)) - mark_sym_for_renaming (t); - } - break; - default: - break; - } - return NULL_TREE; -} - /* Create a varinfo structure for NAME and DECL, and add it to VARMAP. This will also create any varinfo structures necessary for fields of DECL. */ @@ -3679,27 +3611,7 @@ create_variable_info_for (tree decl, con insert_id_for_tree (vi->decl, index); VEC_safe_push (varinfo_t, heap, varmap, vi); if (is_global && (!flag_whole_program || !in_ipa_mode)) - { - make_constraint_from_escaped (vi); - - /* If the variable can't be aliased, there is no point in - putting it in the set of nonlocal vars. */ - if (may_be_aliased (vi->decl)) - { - struct constraint_expr rhs; - rhs.var = index; - rhs.type = ADDRESSOF; - rhs.offset = 0; - make_constraint_to_escaped (rhs); - } - - if (TREE_CODE (decl) != FUNCTION_DECL && DECL_INITIAL (decl)) - { - walk_tree_without_duplicates (&DECL_INITIAL (decl), - find_global_initializers, - (void *)vi); - } - } + make_constraint_from_anything (vi); stats.total_vars++; if (use_field_sensitive @@ -3779,20 +3691,7 @@ create_variable_info_for (tree decl, con insert_into_field_list (vi, newvi); VEC_safe_push (varinfo_t, heap, varmap, newvi); if (is_global && (!flag_whole_program || !in_ipa_mode)) - { - /* If the variable can't be aliased, there is no point in - putting it in the set of nonlocal vars. */ - if (may_be_aliased (vi->decl)) - { - struct constraint_expr rhs; - - rhs.var = newindex; - rhs.type = ADDRESSOF; - rhs.offset = 0; - make_constraint_to_escaped (rhs); - } - make_constraint_from_escaped (newvi); - } + make_constraint_from_anything (newvi); stats.total_vars++; } @@ -3810,12 +3709,20 @@ dump_solution_for_var (FILE *file, unsig unsigned int i; bitmap_iterator bi; + if (vi->node != var) + { + varinfo_t vipt = get_varinfo (vi->node); + fprintf (file, "%s = same as %s\n", vi->name, vipt->name); + } + else + { fprintf (file, "%s = { ", vi->name); EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi) { fprintf (file, "%s ", get_varinfo (i)->name); } fprintf (file, "}\n"); + } } /* Print the points-to solution for VAR to stdout. */ @@ -3834,9 +3741,8 @@ intra_create_variable_infos (void) { tree t; struct constraint_expr lhs, rhs; - varinfo_t nonlocal_vi; - /* For each incoming pointer argument arg, ARG = ESCAPED_VARS or a + /* For each incoming pointer argument arg, ARG = ANYTHING or a dummy variable if flag_argument_noalias > 2. */ for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t)) { @@ -3877,7 +3783,7 @@ intra_create_variable_infos (void) vi->is_artificial_var = 1; vi->is_heap_var = 1; rhs.var = id; - rhs.type = ADDRESSOF; + rhs.type = INCLUDES; rhs.offset = 0; for (p = get_varinfo (lhs.var); p; p = p->next) { @@ -3889,32 +3795,9 @@ intra_create_variable_infos (void) else { for (p = get_varinfo (arg_id); p; p = p->next) - make_constraint_from_escaped (p); + make_constraint_from_anything (p); } } - if (!gimple_nonlocal_all (cfun)) - cfun->gimple_df->nonlocal_all = create_nonlocal_var (void_type_node); - - /* Create variable info for the nonlocal var if it does not - exist. */ - nonlocal_vars_id = create_variable_info_for (gimple_nonlocal_all (cfun), - get_name (gimple_nonlocal_all - (cfun))); - nonlocal_vi = get_varinfo (nonlocal_vars_id); - nonlocal_vi->is_artificial_var = 1; - nonlocal_vi->is_heap_var = 1; - nonlocal_vi->is_unknown_size_var = 1; - nonlocal_vi->directly_dereferenced = true; - - rhs.var = nonlocal_vars_id; - rhs.type = ADDRESSOF; - rhs.offset = 0; - - lhs.var = escaped_vars_id; - lhs.type = SCALAR; - lhs.offset = 0; - - process_constraint (new_constraint (lhs, rhs)); } /* Set bits in INTO corresponding to the variable uids in solution set @@ -3928,7 +3811,7 @@ set_uids_in_ptset (tree ptr, bitmap into unsigned int i; bitmap_iterator bi; subvar_t sv; - unsigned HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr)); + HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr)); EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi) { @@ -3985,8 +3868,123 @@ set_uids_in_ptset (tree ptr, bitmap into static bool have_alias_info = false; +/* The list of SMT's that are in use by our pointer variables. This + is the set of SMT's for all pointers that can point to anything. */ +static bitmap used_smts; + +/* Due to the ordering of points-to set calculation and SMT + calculation being a bit co-dependent, we can't just calculate SMT + used info whenever we want, we have to calculate it around the time + that find_what_p_points_to is called. */ +static bool used_smt_calculated; + +/* Mark which SMT's are in use by points-to anything variables. */ + +static void +set_used_smts (void) +{ + int i; + varinfo_t vi; + used_smts = BITMAP_ALLOC (&ptabitmap_obstack); + + for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); i++) + { + tree var = vi->decl; + tree smt; + bitmap_iterator bi; + unsigned int j; + var_ann_t va; + struct ptr_info_def *pi = NULL; + + if (TREE_CODE (vi->decl) == SSA_NAME) + pi = SSA_NAME_PTR_INFO (var); + + /* Skip the special variables and those without their own + solution set. */ + if (vi->is_special_var || vi->node != vi->id || !SSA_VAR_P (var) + || (pi && !pi->is_dereferenced) + || (DECL_P (var) && !may_be_aliased (var))) + continue; + + if (TREE_CODE (var) == SSA_NAME) + var = SSA_NAME_VAR (var); + + va = var_ann (var); + if (!va) + continue; + + smt = va->symbol_mem_tag; + if (smt) + { + EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi) + { + if (get_varinfo (j)->is_artificial_var) + { + bitmap_set_bit (used_smts, DECL_UID (smt)); + break; + } + } + } + } + used_smt_calculated = true; +} + +/* Merge the necessary SMT's into the solution set for VI, which is + P's varinfo. This involves merging all SMT's that are a subset of + the SMT necessary for P. */ + +static void +merge_smts_into (tree p, varinfo_t vi) +{ + unsigned int i; + bitmap_iterator bi; + tree smt; + VEC(tree, gc) *aliases; + tree var = p; + + if (TREE_CODE (p) == SSA_NAME) + var = SSA_NAME_VAR (p); + + smt = var_ann (var)->symbol_mem_tag; + if (smt) + { + HOST_WIDE_INT smtset = get_alias_set (TREE_TYPE (smt)); + + /* Need to set the SMT subsets first before this + will work properly. */ + bitmap_set_bit (vi->finished_solution, DECL_UID (smt)); + EXECUTE_IF_SET_IN_BITMAP (used_smts, 0, i, bi) + { + tree newsmt = referenced_var (i); + tree newsmttype = TREE_TYPE (newsmt); + + if (alias_set_subset_of (get_alias_set (newsmttype), + smtset)) + bitmap_set_bit (vi->finished_solution, i); + } + + aliases = var_ann (smt)->may_aliases; + if (aliases) + { + size_t k; + tree al; + for (k = 0; VEC_iterate (tree, aliases, k, al); k++) + bitmap_set_bit (vi->finished_solution, + DECL_UID (al)); + } + } +} + /* Given a pointer variable P, fill in its points-to set, or return - false if we can't. */ + false if we can't. + Rather than return false for variables that point-to anything, we + instead find the corresponding SMT, and merge in it's aliases. In + addition to these aliases, we also set the bits for the SMT's + themselves and their subsets, as SMT's are still in use by + non-SSA_NAME's, and pruning may eliminate every one of their + aliases. In such a case, if we did not include the right set of + SMT's in the points-to set of the variable, we'd end up with + statements that do not conflict but should. */ bool find_what_p_points_to (tree p) @@ -4026,6 +4024,10 @@ find_what_p_points_to (tree p) struct ptr_info_def *pi = get_ptr_info (p); unsigned int i; bitmap_iterator bi; + bool was_pt_anything = false; + + if (!pi->is_dereferenced) + return false; /* This variable may have been collapsed, let's get the real variable. */ @@ -4045,23 +4047,44 @@ find_what_p_points_to (tree p) if (vi->id == nothing_id) pi->pt_null = 1; else if (vi->id == anything_id) - pi->pt_anything = 1; + was_pt_anything = 1; else if (vi->id == readonly_id) - pi->pt_anything = 1; + was_pt_anything = 1; else if (vi->id == integer_id) - pi->pt_anything = 1; + was_pt_anything = 1; else if (vi->is_heap_var) pi->pt_global_mem = 1; } } - if (pi->pt_anything) - return false; + /* Share the final set of variables between the SSA_NAME + pointer infos for collapsed nodes that are collapsed to + non-special variables. This is because special vars have + no real types associated with them, so while we know the + pointers are equivalent to them, we need to generate the + solution separately since it will include SMT's from the + original non-collapsed variable. */ + if (!vi->is_special_var && vi->finished_solution) + { + pi->pt_vars = vi->finished_solution; + } + else + { + vi->finished_solution = BITMAP_GGC_ALLOC (); - if (!pi->pt_vars) - pi->pt_vars = BITMAP_GGC_ALLOC (); + /* Instead of using pt_anything, we instead merge in the SMT + aliases for the underlying SMT. */ + if (was_pt_anything) + { + if (!used_smt_calculated) + set_used_smts (); + merge_smts_into (p, vi); + pi->pt_global_mem = 1; - set_uids_in_ptset (vi->decl, pi->pt_vars, vi->solution); + } + set_uids_in_ptset (vi->decl, vi->finished_solution, vi->solution); + pi->pt_vars = vi->finished_solution; + } if (bitmap_empty_p (pi->pt_vars)) pi->pt_vars = NULL; @@ -4152,7 +4175,7 @@ init_base_vars (void) lhs.type = SCALAR; lhs.var = anything_id; lhs.offset = 0; - rhs.type = ADDRESSOF; + rhs.type = INCLUDES; rhs.var = anything_id; rhs.offset = 0; var_anything->address_taken = true; @@ -4183,7 +4206,7 @@ init_base_vars (void) lhs.type = SCALAR; lhs.var = readonly_id; lhs.offset = 0; - rhs.type = ADDRESSOF; + rhs.type = INCLUDES; rhs.var = anything_id; rhs.offset = 0; @@ -4208,33 +4231,10 @@ init_base_vars (void) lhs.type = SCALAR; lhs.var = integer_id; lhs.offset = 0; - rhs.type = ADDRESSOF; + rhs.type = INCLUDES; rhs.var = anything_id; rhs.offset = 0; process_constraint (new_constraint (lhs, rhs)); - - /* Create the ESCAPED_VARS variable used to represent variables that - escape this function. */ - escaped_vars_tree = create_tmp_var_raw (void_type_node, "ESCAPED_VARS"); - var_escaped_vars = new_var_info (escaped_vars_tree, 4, "ESCAPED_VARS", 4); - insert_id_for_tree (escaped_vars_tree, 4); - var_escaped_vars->is_artificial_var = 1; - var_escaped_vars->size = ~0; - var_escaped_vars->fullsize = ~0; - var_escaped_vars->offset = 0; - var_escaped_vars->next = NULL; - escaped_vars_id = 4; - VEC_safe_push (varinfo_t, heap, varmap, var_escaped_vars); - - /* ESCAPED_VARS = *ESCAPED_VARS */ - lhs.type = SCALAR; - lhs.var = escaped_vars_id; - lhs.offset = 0; - rhs.type = DEREF; - rhs.var = escaped_vars_id; - rhs.offset = 0; - process_constraint (new_constraint (lhs, rhs)); - } /* Initialize things necessary to perform PTA */ @@ -4257,105 +4257,6 @@ init_alias_vars (void) init_base_vars (); } -/* Given a statement STMT, generate necessary constraints to - escaped_vars for the escaping variables. */ - -static void -find_escape_constraints (tree stmt) -{ - enum escape_type stmt_escape_type = is_escape_site (stmt); - tree rhs; - VEC(ce_s, heap) *rhsc = NULL; - struct constraint_expr *c; - size_t i; - - if (stmt_escape_type == NO_ESCAPE) - return; - - if (TREE_CODE (stmt) == RETURN_EXPR) - { - /* Returns are either bare, with an embedded MODIFY_EXPR, or - just a plain old expression. */ - if (!TREE_OPERAND (stmt, 0)) - return; - if (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) - rhs = TREE_OPERAND (TREE_OPERAND (stmt, 0), 1); - else - rhs = TREE_OPERAND (stmt, 0); - - get_constraint_for (rhs, &rhsc); - for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) - make_constraint_to_escaped (*c); - VEC_free (ce_s, heap, rhsc); - return; - } - else if (TREE_CODE (stmt) == ASM_EXPR) - { - /* Whatever the inputs of the ASM are, escape. */ - tree arg; - - for (arg = ASM_INPUTS (stmt); arg; arg = TREE_CHAIN (arg)) - { - rhsc = NULL; - get_constraint_for (TREE_VALUE (arg), &rhsc); - for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) - make_constraint_to_escaped (*c); - VEC_free (ce_s, heap, rhsc); - } - return; - } - else if (TREE_CODE (stmt) == CALL_EXPR - || (TREE_CODE (stmt) == MODIFY_EXPR - && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)) - { - /* Calls cause all of the arguments passed in to escape. */ - tree arg; - - if (TREE_CODE (stmt) == MODIFY_EXPR) - stmt = TREE_OPERAND (stmt, 1); - for (arg = TREE_OPERAND (stmt, 1); arg; arg = TREE_CHAIN (arg)) - { - if (POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arg)))) - { - rhsc = NULL; - get_constraint_for (TREE_VALUE (arg), &rhsc); - for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) - make_constraint_to_escaped (*c); - VEC_free (ce_s, heap, rhsc); - } - } - return; - } - else - { - gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR); - } - - gcc_assert (stmt_escape_type == ESCAPE_BAD_CAST - || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL - || stmt_escape_type == ESCAPE_UNKNOWN); - rhs = TREE_OPERAND (stmt, 1); - - /* Look through casts for the real escaping variable. - Constants don't really escape, so ignore them. - Otherwise, whatever escapes must be on our RHS. */ - if (TREE_CODE (rhs) == NOP_EXPR - || TREE_CODE (rhs) == CONVERT_EXPR - || TREE_CODE (rhs) == NON_LVALUE_EXPR) - { - get_constraint_for (TREE_OPERAND (rhs, 0), &rhsc); - } - else if (CONSTANT_CLASS_P (rhs)) - return; - else - { - get_constraint_for (rhs, &rhsc); - } - for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) - make_constraint_to_escaped (*c); - VEC_free (ce_s, heap, rhsc); -} - /* Create points-to sets for the current function. See the comments at the start of the file for an algorithmic overview. */ @@ -4394,7 +4295,6 @@ compute_points_to_sets (struct alias_inf tree stmt = bsi_stmt (bsi); find_func_aliases (stmt); - find_escape_constraints (stmt); /* Update various related attributes like escaped addresses, pointer dereferences for loads and stores. This is used when creating name tags and alias @@ -4424,6 +4324,8 @@ compute_points_to_sets (struct alias_inf solve_graph (graph); + used_smt_calculated = false; + if (dump_file) dump_sa_points_to_info (dump_file); @@ -4447,13 +4349,8 @@ delete_points_to_sets (void) VEC_free (constraint_t, heap, constraints); for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++) - { - /* Nonlocal vars may add more varinfos. */ - if (i >= graph_size) - break; - VEC_free (constraint_t, heap, v->complex); - } + free (graph->preds); free (graph->succs); free (graph); @@ -4495,7 +4392,7 @@ ipa_pta_execute (void) { varinfo_t fi = get_varinfo (varid); for (; fi; fi = fi->next) - make_constraint_from_escaped (fi); + make_constraint_from_anything (fi); } } } @@ -4561,6 +4458,7 @@ ipa_pta_execute (void) fprintf (dump_file, "\nSolving graph:\n"); solve_graph (graph); + set_used_smts (); if (dump_file) dump_sa_points_to_info (dump_file); @@ -4593,13 +4492,11 @@ init_alias_heapvars (void) { heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq, NULL); - cfun->gimple_df->nonlocal_all = NULL_TREE; } void delete_alias_heapvars (void) { - cfun->gimple_df->nonlocal_all = NULL_TREE; htab_delete (heapvar_for_stmt); } --- gcc/tree-ssa-operands.c (/mirror/gcc-trunk) (revision 473) +++ gcc/tree-ssa-operands.c (/local/gcc-clean) (revision 473) @@ -1056,11 +1056,6 @@ access_can_touch_variable (tree ref, tre if (alias == gimple_global_var (cfun)) return true; - /* We cannot prune nonlocal aliases because they are not type - specific. */ - if (alias == gimple_nonlocal_all (cfun)) - return true; - /* If ALIAS is an SFT, it can't be touched if the offset and size of the access is not overlapping with the SFT offset and size. This is only true if we are accessing through a pointer Property changes on: ___________________________________________________________________ Name: svk:merge +138bc75d-0d04-0410-961f-82ee72b054a4:/trunk:119495 +23c3ee16-a423-49b3-8738-b114dc1aabb6:/local/gcc-pta-dev:259 +7dca8dba-45c1-47dc-8958-1a7301c5ed47:/local-gcc/md-constraint:113709 +f367781f-d768-471e-ba66-e306e17dff77:/local/gen-rework-20060122:110130