diff options
| -rw-r--r-- | gcc/ChangeLog | 84 | ||||
| -rw-r--r-- | gcc/Makefile.in | 2 | ||||
| -rw-r--r-- | gcc/passes.c | 4 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 4 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c | 6 | ||||
| -rw-r--r-- | gcc/tree-cfg.c | 7 | ||||
| -rw-r--r-- | gcc/tree-dfa.c | 41 | ||||
| -rw-r--r-- | gcc/tree-flow-inline.h | 16 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 26 | ||||
| -rw-r--r-- | gcc/tree-gimple.c | 9 | ||||
| -rw-r--r-- | gcc/tree-pass.h | 2 | ||||
| -rw-r--r-- | gcc/tree-ssa-alias.c | 692 | ||||
| -rw-r--r-- | gcc/tree-ssa-copy.c | 57 | ||||
| -rw-r--r-- | gcc/tree-ssa-operands.c | 88 | ||||
| -rw-r--r-- | gcc/tree-ssa-operands.h | 2 | ||||
| -rw-r--r-- | gcc/tree-ssa-structalias.c | 650 | ||||
| -rw-r--r-- | gcc/tree-ssa-structalias.h | 60 | ||||
| -rw-r--r-- | gcc/tree-ssa.c | 3 |
18 files changed, 818 insertions, 935 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index f6a729a..2217625 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,87 @@ +2005-07-09 Diego Novillo <dnovillo@redhat.com> + + * Makefile.in (tree-ssa-alias.o): Depend on tree-ssa-structalias.h + * tree-cfg.c (CHECK_OP): Only test for is_gimple_val. + * tree-dfa.c (dump_subvars_for): New. + (debug_subvars_for): New. + (dump_variable): Show subvariables if VAR has them. + * tree-flow-inline.h (get_subvar_at): New. + (overlap_subvar): Change offset and size to unsigned HOST_WIDE_INT. + * tree-flow.h (struct ptr_info_def): Remove field pt_malloc. + Update all users. + (struct subvar): Change fields offset and size to unsigned + HOST_WIDE_INT. + (dump_subvars_for): Declare. + (debug_subvars_for): Declare. + (get_subvar_at): Declare. + (okay_component_ref_for_subvars): Change 2nd and 3rd argument + to unsigned HOST_WIDE_INT *. + (overlap_subvar): Likewise. + * tree-gimple.c (is_gimple_reg): Always return false for + SFTs and memory tags. + * tree-pass.h (pass_build_pta, pass_del_pta): Remove. + Update all callers. + * tree-ssa-alias.c: Include tree-ssa-structalias.h. + (compute_may_aliases): Call compute_points_to_sets. + (collect_points_to_info_for): Remove. + (compute_points_to_and_addr_escape): Remove. + (delete_alias_info): Call delete_points_to_sets. + (compute_flow_sensitive_aliasing): If the call to + find_what_p_points_to returns false, call set_pt_anything. + (add_may_alias): Set TREE_ADDRESSABLE when adding a new alias. + (set_pt_anything): Clear pi->pt_vars. + (set_pt_malloc): Remove. + (merge_pointed_to_info): Remove. + (add_pointed_to_expr): Remove. + (add_pointed_to_var): Remove. + (collect_points_to_info_r): Remove. + (is_escape_site): Make extern. + (create_sft): New. + (create_overlap_variables_for): Call it. + * tree-ssa-copy.c (merge_alias_info): Never merge + flow-sensitive alias information. + * tree-ssa-operands.c (get_expr_operands): Adjust variables + offset and size to be unsigned HOST_WIDE_INT. + (add_to_addressable_set): Rename from note_addressable. + Set TREE_ADDRESSABLE as the variables are added to the set. + Update all users. + (add_stmt_operand): Do not try to micro-optimize unmodifiable + operands into VUSEs when adding V_MAY_DEFs for members in an + alias set. + * tree-ssa-operands.h (add_to_addressable_set): Declare. + * tree-ssa-structalias.c: Include tree-ssa-structalias.h last. + (struct variable_info): Add bitfield is_heap_var. + (var_anyoffset, anyoffset_tree, anyoffset_id): Declare. + (new_var_info): Initialize is_heap_var. + (get_constraint_for): Add HEAP variables to the symbol table. + Mark them with is_heap_var. + (update_alias_info): New. Taken mostly from the old + compute_points_to_and_addr_escape. + (handle_ptr_arith): New. + (find_func_aliases): Call update_alias_info. + Call handle_ptr_info for tcc_binary expressions. + Call mark_stmt_modified. + (create_variable_info_for): If DECL has subvars, do not create + variables for its subvars. Always add all the fields. + (set_uids_in_ptset): If the solution includes ANYOFFSET and + SFTs, then add all the SFTs of the structure. + If VI->DECL is an aggregate with subvariables, add the SFT at + VI->OFFSET. + (find_what_p_points_to): If VI is an artificial variable, + translate to bitfields in SSA_NAME_PTR_INFO. + If the solution is empty, set pi->pt_vars to NULL + (init_base_vars): Create ANYOFFSET. + (compute_points_to_sets): Rename from create_alias_vars. + Make extern. + (pass_build_pta): Remove. + (delete_points_to_sets): Rename from delete_alias_vars. + (pass_del_pta): Remove. + * tree-ssa-structalias.h (struct alias_info): Move from + tree-ssa-alias.h. + (NUM_REFERENCES, NUM_REFERENCES_CLEAR, NUM_REFERENCES_INC, + NUM_REFERENCES_SET): Likewise. + (compute_points_to_sets, delete_points_to_sets): Declare. + 2005-07-09 Richard Henderson <rth@redhat.com> * config/alpha/alpha.c (emit_insxl, alpha_expand_compare_and_swap_12, diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 244643c..1c70c7a 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1895,7 +1895,7 @@ tree-ssa-alias.o : tree-ssa-alias.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) tree-inline.h $(FLAGS_H) \ function.h $(TIMEVAR_H) convert.h $(TM_H) coretypes.h langhooks.h \ $(TREE_DUMP_H) tree-pass.h $(PARAMS_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) \ - hard-reg-set.h $(TREE_GIMPLE_H) vec.h + hard-reg-set.h $(TREE_GIMPLE_H) vec.h tree-ssa-structalias.h tree-ssa-reassoc.o : tree-ssa-reassoc.c $(TREE_FLOW_H) $(CONFIG_H) \ $(SYSTEM_H) $(TREE_H) $(GGC_H) $(DIAGNOSTIC_H) errors.h $(TIMEVAR_H) \ $(TM_H) coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H) tree-iterator.h\ diff --git a/gcc/passes.c b/gcc/passes.c index abc44e4..04c60a5 100644 --- a/gcc/passes.c +++ b/gcc/passes.c @@ -471,10 +471,8 @@ init_optimization_passes (void) NEXT_PASS (pass_referenced_vars); NEXT_PASS (pass_create_structure_vars); NEXT_PASS (pass_build_ssa); - NEXT_PASS (pass_build_pta); NEXT_PASS (pass_may_alias); NEXT_PASS (pass_return_slot); - NEXT_PASS (pass_del_pta); NEXT_PASS (pass_rename_ssa_copies); NEXT_PASS (pass_early_warn_uninitialized); @@ -490,9 +488,7 @@ init_optimization_passes (void) NEXT_PASS (pass_dominator); NEXT_PASS (pass_phiopt); - NEXT_PASS (pass_build_pta); NEXT_PASS (pass_may_alias); - NEXT_PASS (pass_del_pta); NEXT_PASS (pass_tail_recursion); NEXT_PASS (pass_profile); NEXT_PASS (pass_ch); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 9a982a7..96d0a0b 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2005-07-09 Diego Novillo <dnovillo@redhat.com> + + * gcc.dg/tree-ssa/pta-fp.c: Use -fdump-tree-alias1. + 2005-07-09 Richard Henderson <rth@redhat.com> * lib/target-supports.exp (check_effective_target_sync_char_short): diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c b/gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c index e835399..4cebcbb 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-pta1" } */ +/* { dg-options "-O2 -fdump-tree-alias1" } */ extern double cos (double); extern double sin (double); double f(double a) @@ -22,5 +22,5 @@ double f(double a) } /* The points-to set of the final function pointer should be "sin cos" */ -/* { dg-final { scan-tree-dump-times "sin cos" 1 "pta1"} } */ -/* { dg-final { cleanup-tree-dump "pta1" } } */ +/* { dg-final { scan-tree-dump-times "sin cos" 1 "alias1"} } */ +/* { dg-final { cleanup-tree-dump "alias1" } } */ diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index bfbf5a5..dd8ad08 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -3083,12 +3083,9 @@ verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED) if (TYPE_P (t)) *walk_subtrees = 0; - /* Check operand N for being valid GIMPLE and give error MSG if not. - We check for constants explicitly since they are not considered - gimple invariants if they overflowed. */ + /* Check operand N for being valid GIMPLE and give error MSG if not. */ #define CHECK_OP(N, MSG) \ - do { if (!CONSTANT_CLASS_P (TREE_OPERAND (t, N)) \ - && !is_gimple_val (TREE_OPERAND (t, N))) \ + do { if (!is_gimple_val (TREE_OPERAND (t, N))) \ { error (MSG); return TREE_OPERAND (t, N); }} while (0) switch (TREE_CODE (t)) diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c index 5cfbe1c..f065f5d 100644 --- a/gcc/tree-dfa.c +++ b/gcc/tree-dfa.c @@ -254,6 +254,37 @@ debug_referenced_vars (void) } +/* Dump sub-variables for VAR to FILE. */ + +void +dump_subvars_for (FILE *file, tree var) +{ + subvar_t sv = get_subvars_for_var (var); + + if (!sv) + return; + + fprintf (file, "{ "); + + for (; sv; sv = sv->next) + { + print_generic_expr (file, sv->var, dump_flags); + fprintf (file, " "); + } + + fprintf (file, "}"); +} + + +/* Dumb sub-variables for VAR to stderr. */ + +void +debug_subvars_for (tree var) +{ + dump_subvars_for (stderr, var); +} + + /* Dump variable VAR and its may-aliases to FILE. */ void @@ -316,6 +347,12 @@ dump_variable (FILE *file, tree var) dump_may_aliases_for (file, var); } + if (get_subvars_for_var (var)) + { + fprintf (file, ", sub-vars: "); + dump_subvars_for (file, var); + } + fprintf (file, "\n"); } @@ -741,8 +778,8 @@ find_new_referenced_vars (tree *stmt_p) size, in bits, of REF inside the return value. */ tree -okay_component_ref_for_subvars (tree ref, HOST_WIDE_INT *poffset, - HOST_WIDE_INT *psize) +okay_component_ref_for_subvars (tree ref, unsigned HOST_WIDE_INT *poffset, + unsigned HOST_WIDE_INT *psize) { tree result = NULL; HOST_WIDE_INT bitsize; diff --git a/gcc/tree-flow-inline.h b/gcc/tree-flow-inline.h index 13f94ac..4874c77 100644 --- a/gcc/tree-flow-inline.h +++ b/gcc/tree-flow-inline.h @@ -1444,6 +1444,20 @@ get_subvars_for_var (tree var) return subvars; } +/* Return the subvariable of VAR at offset OFFSET. */ + +static inline tree +get_subvar_at (tree var, unsigned HOST_WIDE_INT offset) +{ + subvar_t sv; + + for (sv = get_subvars_for_var (var); sv; sv = sv->next) + if (sv->offset == offset) + return sv->var; + + return NULL_TREE; +} + /* Return true if V is a tree that we can have subvars for. Normally, this is any aggregate type, however, due to implementation limitations ATM, we exclude array types as well. */ @@ -1461,7 +1475,7 @@ var_can_have_subvars (tree v) *EXACT will be set to true upon return. */ static inline bool -overlap_subvar (HOST_WIDE_INT offset, HOST_WIDE_INT size, +overlap_subvar (unsigned HOST_WIDE_INT offset, unsigned HOST_WIDE_INT size, subvar_t sv, bool *exact) { /* There are three possible cases of overlap. diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 773a76f..c28de1c8 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -71,9 +71,6 @@ struct ptr_info_def GTY(()) is pointing to. */ unsigned int pt_anything : 1; - /* Nonzero if this pointer is the result of a call to malloc. */ - unsigned int pt_malloc : 1; - /* Nonzero if the value of this pointer escapes the current function. */ unsigned int value_escapes_p : 1; @@ -160,19 +157,22 @@ enum mem_tag_kind { /* This variable represents a structure field. */ STRUCT_FIELD }; + struct subvar; typedef struct subvar *subvar_t; /* This structure represents a fake sub-variable for a structure field. */ - struct subvar GTY(()) { - /* Fake variable name */ + /* Fake variable. */ tree var; + /* Offset inside structure. */ - HOST_WIDE_INT offset; - /* Size of field. */ - HOST_WIDE_INT size; + unsigned HOST_WIDE_INT offset; + + /* Size of the field. */ + unsigned HOST_WIDE_INT size; + /* Next subvar for this structure. */ subvar_t next; }; @@ -552,6 +552,8 @@ extern void debug_referenced_vars (void); extern void dump_referenced_vars (FILE *); extern void dump_variable (FILE *, tree); extern void debug_variable (tree); +extern void dump_subvars_for (FILE *, tree); +extern void debug_subvars_for (tree); extern tree get_virtual_var (tree); extern void add_referenced_tmp_var (tree); extern void mark_new_vars_to_rename (tree); @@ -578,11 +580,13 @@ extern void add_type_alias (tree, tree); extern void new_type_alias (tree, tree); extern void count_uses_and_derefs (tree, tree, unsigned *, unsigned *, bool *); static inline subvar_t get_subvars_for_var (tree); +static inline tree get_subvar_at (tree, unsigned HOST_WIDE_INT); static inline bool ref_contains_array_ref (tree); -extern tree okay_component_ref_for_subvars (tree, HOST_WIDE_INT *, - HOST_WIDE_INT *); +extern tree okay_component_ref_for_subvars (tree, unsigned HOST_WIDE_INT *, + unsigned HOST_WIDE_INT *); static inline bool var_can_have_subvars (tree); -static inline bool overlap_subvar (HOST_WIDE_INT, HOST_WIDE_INT, +static inline bool overlap_subvar (unsigned HOST_WIDE_INT, + unsigned HOST_WIDE_INT, subvar_t, bool *); /* Call-back function for walk_use_def_chains(). At each reaching diff --git a/gcc/tree-gimple.c b/gcc/tree-gimple.c index 2a62aeb..284f577 100644 --- a/gcc/tree-gimple.c +++ b/gcc/tree-gimple.c @@ -268,6 +268,8 @@ is_gimple_reg_type (tree type) bool is_gimple_reg (tree t) { + var_ann_t ann; + if (TREE_CODE (t) == SSA_NAME) t = SSA_NAME_VAR (t); @@ -305,9 +307,16 @@ is_gimple_reg (tree t) if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE) return DECL_COMPLEX_GIMPLE_REG_P (t); + /* Some compiler temporaries are created to be used exclusively in + virtual operands (currently memory tags and sub-variables). + These variables should never be considered GIMPLE registers. */ + if (DECL_ARTIFICIAL (t) && (ann = var_ann (t)) != NULL) + return ann->mem_tag_kind == NOT_A_TAG; + return true; } + /* Returns true if T is a GIMPLE formal temporary variable. */ bool diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 80f4a05..d420b1b 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -276,8 +276,6 @@ extern struct tree_opt_pass pass_store_ccp; extern struct tree_opt_pass pass_store_copy_prop; extern struct tree_opt_pass pass_vrp; extern struct tree_opt_pass pass_create_structure_vars; -extern struct tree_opt_pass pass_build_pta; -extern struct tree_opt_pass pass_del_pta; extern struct tree_opt_pass pass_uncprop; extern struct tree_opt_pass pass_return_slot; extern struct tree_opt_pass pass_reassoc; diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index 39d9fde..f55e2d2 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -40,19 +40,12 @@ Boston, MA 02110-1301, USA. */ #include "tree-flow.h" #include "tree-inline.h" #include "tree-pass.h" +#include "tree-ssa-structalias.h" #include "convert.h" #include "params.h" #include "vec.h" #include "bitmap.h" -/* Keep track of how many times each pointer has been dereferenced in - the program using the aux variable. This is used by the alias - grouping heuristic in compute_flow_insensitive_aliasing. */ -#define NUM_REFERENCES(ANN) ((size_t)((ANN)->common.aux)) -#define NUM_REFERENCES_CLEAR(ANN) ((ANN)->common.aux) = 0 -#define NUM_REFERENCES_INC(ANN) (ANN)->common.aux = (void*) (((size_t)((ANN)->common.aux)) + 1) -#define NUM_REFERENCES_SET(ANN, VAL) (ANN)->common.aux = (void*) ((void *)(VAL)) - /* Obstack used to hold grouping bitmaps and other temporary bitmaps used by aliasing */ static bitmap_obstack alias_obstack; @@ -83,51 +76,6 @@ struct alias_map_d }; -/* Alias information used by compute_may_aliases and its helpers. */ -struct alias_info -{ - /* SSA names visited while collecting points-to information. If bit I - is set, it means that SSA variable with version I has already been - visited. */ - sbitmap ssa_names_visited; - - /* Array of SSA_NAME pointers processed by the points-to collector. */ - varray_type processed_ptrs; - - /* Variables whose address is still needed. */ - bitmap addresses_needed; - - /* ADDRESSABLE_VARS contains all the global variables and locals that - have had their address taken. */ - struct alias_map_d **addressable_vars; - size_t num_addressable_vars; - - /* POINTERS contains all the _DECL pointers with unique memory tags - that have been referenced in the program. */ - struct alias_map_d **pointers; - size_t num_pointers; - - /* Number of function calls found in the program. */ - size_t num_calls_found; - - /* Number of const/pure function calls found in the program. */ - size_t num_pure_const_calls_found; - - /* Total number of virtual operands that will be needed to represent - all the aliases of all the pointers found in the program. */ - long total_alias_vops; - - /* Variables that have been written to. */ - bitmap written_vars; - - /* Pointers that have been used in an indirect store operation. */ - bitmap dereferenced_ptrs_store; - - /* Pointers that have been used in an indirect load operation. */ - bitmap dereferenced_ptrs_load; -}; - - /* Counters used to display statistics on alias analysis. */ struct alias_stats_d { @@ -155,18 +103,12 @@ 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 *); static void compute_flow_sensitive_aliasing (struct alias_info *); static void setup_pointers_and_addressables (struct alias_info *); -static bool collect_points_to_info_r (tree, tree, void *); -static bool is_escape_site (tree, struct alias_info *); -static void add_pointed_to_var (struct alias_info *, tree, tree); static void create_global_var (void); -static void collect_points_to_info_for (struct alias_info *, tree); static void maybe_create_global_var (struct alias_info *ai); static void group_aliases (struct alias_info *); static void set_pt_anything (tree ptr); -static void set_pt_malloc (tree ptr); /* Global declarations. */ @@ -315,7 +257,7 @@ compute_may_aliases (void) address of V escapes the current function, making V call-clobbered (i.e., whether &V is stored in a global variable or if its passed as a function call argument). */ - compute_points_to_and_addr_escape (ai); + compute_points_to_sets (ai); /* Collect all pointers and addressable variables, compute alias sets, create memory tags for pointers and promote variables whose address is @@ -506,7 +448,6 @@ init_alias_info (void) ai->ssa_names_visited = sbitmap_alloc (num_ssa_names); sbitmap_zero (ai->ssa_names_visited); VARRAY_TREE_INIT (ai->processed_ptrs, 50, "processed_ptrs"); - ai->addresses_needed = BITMAP_ALLOC (&alias_obstack); ai->written_vars = BITMAP_ALLOC (&alias_obstack); ai->dereferenced_ptrs_store = BITMAP_ALLOC (&alias_obstack); ai->dereferenced_ptrs_load = BITMAP_ALLOC (&alias_obstack); @@ -564,7 +505,6 @@ init_alias_info (void) 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->pt_null = 0; pi->value_escapes_p = 0; pi->is_dereferenced = 0; @@ -592,7 +532,6 @@ delete_alias_info (struct alias_info *ai) sbitmap_free (ai->ssa_names_visited); ai->processed_ptrs = NULL; - BITMAP_FREE (ai->addresses_needed); for (i = 0; i < ai->num_addressable_vars; i++) free (ai->addressable_vars[i]); @@ -613,171 +552,9 @@ delete_alias_info (struct alias_info *ai) BITMAP_FREE (ai->dereferenced_ptrs_store); BITMAP_FREE (ai->dereferenced_ptrs_load); bitmap_obstack_release (&alias_obstack); - free (ai); -} - -/* Walk use-def chains for pointer PTR to determine what variables is PTR - pointing to. */ - -static void -collect_points_to_info_for (struct alias_info *ai, tree ptr) -{ - gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr))); - - if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (ptr))) - { - SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (ptr)); - walk_use_def_chains (ptr, collect_points_to_info_r, ai, true); - VARRAY_PUSH_TREE (ai->processed_ptrs, ptr); - } -} - -/* Traverse use-def links for all the pointers in the program to collect - address escape and points-to information. - - This is loosely based on the same idea described in R. Hasti and S. - Horwitz, ``Using static single assignment form to improve - flow-insensitive pointer analysis,'' in SIGPLAN Conference on - Programming Language Design and Implementation, pp. 97-105, 1998. */ - -static void -compute_points_to_and_addr_escape (struct alias_info *ai) -{ - basic_block bb; - unsigned i; - tree op; - ssa_op_iter iter; - - timevar_push (TV_TREE_PTA); - - FOR_EACH_BB (bb) - { - block_stmt_iterator si; - - for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) - { - bitmap addr_taken; - tree stmt = bsi_stmt (si); - bool stmt_escapes_p = is_escape_site (stmt, ai); - bitmap_iterator bi; - - /* Mark all the variables whose address are taken by the - statement. Note that this will miss all the addresses taken - in PHI nodes (those are discovered while following the use-def - chains). */ - addr_taken = addresses_taken (stmt); - if (addr_taken) - EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi) - { - tree var = referenced_var (i); - bitmap_set_bit (ai->addresses_needed, DECL_UID (var)); - if (stmt_escapes_p) - mark_call_clobbered (var); - } - - FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) - { - tree var = SSA_NAME_VAR (op); - var_ann_t v_ann = var_ann (var); - struct ptr_info_def *pi; - bool is_store; - unsigned num_uses, num_derefs; - - /* If the operand's variable may be aliased, keep track - of how many times we've referenced it. This is used - for alias grouping in compute_flow_sensitive_aliasing. - Note that we don't need to grow AI->NUM_REFERENCES - because we are processing regular variables, not - memory tags (the array's initial size is set to - NUM_REFERENCED_VARS). */ - if (may_be_aliased (var)) - NUM_REFERENCES_INC (v_ann); - - if (!POINTER_TYPE_P (TREE_TYPE (op))) - continue; - - collect_points_to_info_for (ai, op); - - pi = SSA_NAME_PTR_INFO (op); - count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, - &is_store); - - if (num_derefs > 0) - { - /* Mark OP as 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. */ - pi->is_dereferenced = 1; - - /* Keep track of how many time we've dereferenced each - pointer. */ - NUM_REFERENCES_INC (v_ann); - - /* If this is a store operation, mark OP as being - dereferenced to store, otherwise mark it as being - dereferenced to load. */ - if (is_store) - bitmap_set_bit (ai->dereferenced_ptrs_store, - DECL_UID (var)); - else - bitmap_set_bit (ai->dereferenced_ptrs_load, - DECL_UID (var)); - } - - if (stmt_escapes_p && num_derefs < num_uses) - { - /* If STMT is an escape point and STMT contains at - least one direct use of OP, then the value of OP - escapes and so the pointed-to variables need to - be marked call-clobbered. */ - pi->value_escapes_p = 1; - - /* 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)) - { - bitmap_set_bit (ai->dereferenced_ptrs_store, - DECL_UID (var)); - pi->is_dereferenced = 1; - } - } - } - - /* Update reference counter for definitions to any - potentially aliased variable. This is used in the alias - grouping heuristics. */ - FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) - { - tree var = SSA_NAME_VAR (op); - var_ann_t ann = var_ann (var); - bitmap_set_bit (ai->written_vars, DECL_UID (var)); - if (may_be_aliased (var)) - NUM_REFERENCES_INC (ann); - - if (POINTER_TYPE_P (TREE_TYPE (op))) - collect_points_to_info_for (ai, op); - } - - /* Mark variables in V_MAY_DEF operands as being written to. */ - FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS) - { - tree var = DECL_P (op) ? op : SSA_NAME_VAR (op); - bitmap_set_bit (ai->written_vars, DECL_UID (var)); - } - - /* After promoting variables and computing aliasing we will - need to re-scan most statements. FIXME: Try to minimize the - number of statements re-scanned. It's not really necessary to - re-scan *all* statements. */ - mark_stmt_modified (stmt); - } - } - - timevar_pop (TV_TREE_PTA); + delete_points_to_sets (); } @@ -863,16 +640,10 @@ create_name_tags (void) if (old_name_tag && old_name_tag != pi->name_mem_tag) mark_sym_for_renaming (old_name_tag); } - 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. */ + /* If the pointer does not point to a known spot, we should + use type tags. */ set_pt_anything (ptr); continue; } @@ -902,11 +673,8 @@ compute_flow_sensitive_aliasing (struct alias_info *ai) 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 (pi->pt_anything || pi->pt_vars == NULL) - { - find_what_p_points_to (ptr); - } + if (!find_what_p_points_to (ptr)) + set_pt_anything (ptr); } create_name_tags (); @@ -931,9 +699,7 @@ compute_flow_sensitive_aliasing (struct alias_info *ai) if (pi->pt_vars) EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi) - { - mark_call_clobbered (referenced_var (j)); - } + mark_call_clobbered (referenced_var (j)); } /* Set up aliasing information for PTR's name memory tag (if it has @@ -1009,9 +775,9 @@ compute_flow_insensitive_aliasing (struct alias_info *ai) So we first check the call_clobbered status of the tag and variable before querying the bitmap. */ tag_stored_p = is_call_clobbered (tag) - || bitmap_bit_p (ai->written_vars, DECL_UID (tag)); + || bitmap_bit_p (ai->written_vars, DECL_UID (tag)); var_stored_p = is_call_clobbered (var) - || bitmap_bit_p (ai->written_vars, DECL_UID (var)); + || bitmap_bit_p (ai->written_vars, DECL_UID (var)); if (!tag_stored_p && !var_stored_p) continue; @@ -1126,7 +892,7 @@ compute_flow_insensitive_aliasing (struct alias_info *ai) } if (dump_file) - fprintf (dump_file, "%s: Total number of aliased vops: %ld\n", + fprintf (dump_file, "\n%s: Total number of aliased vops: %ld\n", get_name (current_function_decl), ai->total_alias_vops); @@ -1458,9 +1224,9 @@ setup_pointers_and_addressables (struct alias_info *ai) of ADDR_EXPR constants into INDIRECT_REF expressions and the removal of dead pointer assignments done by the early scalar cleanup passes. */ - if (TREE_ADDRESSABLE (var) && v_ann->mem_tag_kind != STRUCT_FIELD) + if (TREE_ADDRESSABLE (var)) { - if (!bitmap_bit_p (ai->addresses_needed, DECL_UID (var)) + if (!bitmap_bit_p (addressable_vars, DECL_UID (var)) && TREE_CODE (var) != RESULT_DECL && !is_global_var (var)) { @@ -1470,6 +1236,9 @@ setup_pointers_and_addressables (struct alias_info *ai) to rename VAR into SSA afterwards. */ mark_sym_for_renaming (var); + /* If VAR can have sub-variables, and any of its + sub-variables has its address taken, then we cannot + remove the addressable flag from VAR. */ if (var_can_have_subvars (var) && (svars = get_subvars_for_var (var))) { @@ -1477,8 +1246,7 @@ setup_pointers_and_addressables (struct alias_info *ai) for (sv = svars; sv; sv = sv->next) { - if (bitmap_bit_p (ai->addresses_needed, - DECL_UID (sv->var))) + if (bitmap_bit_p (addressable_vars, DECL_UID (sv->var))) okay_to_mark = false; mark_sym_for_renaming (sv->var); } @@ -1490,22 +1258,6 @@ setup_pointers_and_addressables (struct alias_info *ai) if (okay_to_mark) mark_non_addressable (var); } - else - { - /* Add the variable to the set of addressables. Mostly - used when scanning operands for ASM_EXPRs that - clobber memory. In those cases, we need to clobber - all call-clobbered variables and all addressables. */ - bitmap_set_bit (addressable_vars, DECL_UID (var)); - if (var_can_have_subvars (var) - && (svars = get_subvars_for_var (var))) - { - subvar_t sv; - for (sv = svars; sv; sv = sv->next) - bitmap_set_bit (addressable_vars, DECL_UID (sv->var)); - } - - } } /* Global variables and addressable locals may be aliased. Create an @@ -1562,10 +1314,9 @@ setup_pointers_and_addressables (struct alias_info *ai) references of TAG. Since TAG can be associated with several pointers, add the dereferences of VAR to the TAG. */ - NUM_REFERENCES_SET (t_ann, - NUM_REFERENCES (t_ann) + - NUM_REFERENCES (v_ann)); + NUM_REFERENCES (t_ann) + + NUM_REFERENCES (v_ann)); } else { @@ -1783,8 +1534,16 @@ add_may_alias (tree var, tree alias) var_ann_t v_ann = get_var_ann (var); var_ann_t a_ann = get_var_ann (alias); + /* Don't allow self-referential aliases. */ gcc_assert (var != alias); + /* ALIAS must be addressable if it's being added to an alias set. */ +#if 1 + TREE_ADDRESSABLE (alias) = 1; +#else + gcc_assert (may_be_aliased (alias)); +#endif + if (v_ann->may_aliases == NULL) VARRAY_TREE_INIT (v_ann->may_aliases, 2, "aliases"); @@ -1836,7 +1595,7 @@ 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; /* 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 @@ -1849,341 +1608,6 @@ set_pt_anything (tree ptr) } -/* 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 different pointers DEST and ORIG. Merge the points-to - information in ORIG into DEST. AI contains all the alias - information collected up to this point. */ - -static void -merge_pointed_to_info (struct alias_info *ai, tree dest, tree orig) -{ - struct ptr_info_def *dest_pi, *orig_pi; - - gcc_assert (dest != orig); - - /* Make sure we have points-to information for ORIG. */ - collect_points_to_info_for (ai, orig); - - dest_pi = get_ptr_info (dest); - orig_pi = SSA_NAME_PTR_INFO (orig); - - if (orig_pi) - { - gcc_assert (orig_pi != dest_pi); - - /* 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, however we currently do not - handle cases of more than one pointer pointing to the same - malloc'd area. - - FIXME: If the merging comes from an expression that preserves - the PT_MALLOC attribute (copy assignment, address - arithmetic), 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 || orig_pi->pt_anything) - set_pt_anything (dest); - - dest_pi->pt_null |= orig_pi->pt_null; - - if (!dest_pi->pt_anything - && orig_pi->pt_vars - && !bitmap_empty_p (orig_pi->pt_vars)) - { - if (dest_pi->pt_vars == NULL) - { - dest_pi->pt_vars = BITMAP_GGC_ALLOC (); - bitmap_copy (dest_pi->pt_vars, orig_pi->pt_vars); - } - else - bitmap_ior_into (dest_pi->pt_vars, orig_pi->pt_vars); - } - } - else - set_pt_anything (dest); -} - - -/* Add EXPR to the list of expressions pointed-to by PTR. */ - -static void -add_pointed_to_expr (struct alias_info *ai, tree ptr, tree expr) -{ - if (TREE_CODE (expr) == WITH_SIZE_EXPR) - expr = TREE_OPERAND (expr, 0); - - get_ptr_info (ptr); - - if (TREE_CODE (expr) == CALL_EXPR - && (call_expr_flags (expr) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))) - { - /* If EXPR is a malloc-like call, then the area pointed to PTR - is guaranteed to not alias with anything else. */ - set_pt_malloc (ptr); - } - else if (TREE_CODE (expr) == ADDR_EXPR) - { - /* Found P_i = ADDR_EXPR */ - add_pointed_to_var (ai, ptr, expr); - } - else if (TREE_CODE (expr) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (expr))) - { - /* Found P_i = Q_j. */ - merge_pointed_to_info (ai, ptr, expr); - } - else if (TREE_CODE (expr) == PLUS_EXPR || TREE_CODE (expr) == MINUS_EXPR) - { - /* Found P_i = PLUS_EXPR or P_i = MINUS_EXPR */ - tree op0 = TREE_OPERAND (expr, 0); - tree op1 = TREE_OPERAND (expr, 1); - - /* Both operands may be of pointer type. FIXME: Shouldn't - we just expect PTR + OFFSET always? */ - if (POINTER_TYPE_P (TREE_TYPE (op0)) - && TREE_CODE (op0) != INTEGER_CST) - { - if (TREE_CODE (op0) == SSA_NAME) - merge_pointed_to_info (ai, ptr, op0); - else if (TREE_CODE (op0) == ADDR_EXPR) - add_pointed_to_var (ai, ptr, op0); - else - set_pt_anything (ptr); - } - - if (POINTER_TYPE_P (TREE_TYPE (op1)) - && TREE_CODE (op1) != INTEGER_CST) - { - if (TREE_CODE (op1) == SSA_NAME) - merge_pointed_to_info (ai, ptr, op1); - else if (TREE_CODE (op1) == ADDR_EXPR) - add_pointed_to_var (ai, ptr, op1); - else - set_pt_anything (ptr); - } - - /* Neither operand is a pointer? VAR can be pointing anywhere. - FIXME: Shouldn't we asserting here? If we get here, we found - PTR = INT_CST + INT_CST, which should not be a valid pointer - expression. */ - if (!(POINTER_TYPE_P (TREE_TYPE (op0)) - && TREE_CODE (op0) != INTEGER_CST) - && !(POINTER_TYPE_P (TREE_TYPE (op1)) - && TREE_CODE (op1) != INTEGER_CST)) - set_pt_anything (ptr); - } - else if (integer_zerop (expr)) - { - /* EXPR is the NULL pointer. Mark PTR as pointing to NULL. */ - SSA_NAME_PTR_INFO (ptr)->pt_null = 1; - } - else - { - /* If we can't recognize the expression, assume that PTR may - point anywhere. */ - set_pt_anything (ptr); - } -} - - -/* If VALUE is of the form &DECL, add DECL to the set of variables - pointed-to by PTR. Otherwise, add VALUE as a pointed-to expression by - PTR. AI points to the collected alias information. */ - -static void -add_pointed_to_var (struct alias_info *ai, tree ptr, tree value) -{ - struct ptr_info_def *pi = get_ptr_info (ptr); - tree pt_var = NULL_TREE; - HOST_WIDE_INT offset, size; - tree addrop; - size_t uid; - tree ref; - subvar_t svars; - - gcc_assert (TREE_CODE (value) == ADDR_EXPR); - - addrop = TREE_OPERAND (value, 0); - if (REFERENCE_CLASS_P (addrop)) - pt_var = get_base_address (addrop); - else - pt_var = addrop; - - /* If this is a component_ref, see if we can get a smaller number of - variables to take the address of. */ - if (TREE_CODE (addrop) == COMPONENT_REF - && (ref = okay_component_ref_for_subvars (addrop, &offset ,&size))) - { - subvar_t sv; - svars = get_subvars_for_var (ref); - - uid = DECL_UID (pt_var); - - if (pi->pt_vars == NULL) - pi->pt_vars = BITMAP_GGC_ALLOC (); - /* If the variable is a global, mark the pointer as pointing to - global memory (which will make its tag a global variable). */ - if (is_global_var (pt_var)) - pi->pt_global_mem = 1; - - for (sv = svars; sv; sv = sv->next) - { - if (overlap_subvar (offset, size, sv, NULL)) - { - bitmap_set_bit (pi->pt_vars, DECL_UID (sv->var)); - bitmap_set_bit (ai->addresses_needed, DECL_UID (sv->var)); - } - } - } - else if (pt_var && SSA_VAR_P (pt_var)) - { - - uid = DECL_UID (pt_var); - - if (pi->pt_vars == NULL) - pi->pt_vars = BITMAP_GGC_ALLOC (); - - /* If this is an aggregate, we may have subvariables for it that need - to be pointed to. */ - if (var_can_have_subvars (pt_var) - && (svars = get_subvars_for_var (pt_var))) - { - subvar_t sv; - for (sv = svars; sv; sv = sv->next) - { - uid = DECL_UID (sv->var); - bitmap_set_bit (ai->addresses_needed, uid); - bitmap_set_bit (pi->pt_vars, uid); - } - } - else - { - bitmap_set_bit (ai->addresses_needed, uid); - bitmap_set_bit (pi->pt_vars, uid); - } - - /* If the variable is a global, mark the pointer as pointing to - global memory (which will make its tag a global variable). */ - if (is_global_var (pt_var)) - pi->pt_global_mem = 1; - } -} - - -/* Callback for walk_use_def_chains to gather points-to information from the - SSA web. - - VAR is an SSA variable or a GIMPLE expression. - - STMT is the statement that generates the SSA variable or, if STMT is a - PHI_NODE, VAR is one of the PHI arguments. - - DATA is a pointer to a structure of type ALIAS_INFO. */ - -static bool -collect_points_to_info_r (tree var, tree stmt, void *data) -{ - struct alias_info *ai = (struct alias_info *) data; - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Visiting use-def links for "); - print_generic_expr (dump_file, var, dump_flags); - fprintf (dump_file, "\n"); - } - - switch (TREE_CODE (stmt)) - { - case RETURN_EXPR: - gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR); - stmt = TREE_OPERAND (stmt, 0); - /* FALLTHRU */ - - case MODIFY_EXPR: - { - tree rhs = TREE_OPERAND (stmt, 1); - STRIP_NOPS (rhs); - add_pointed_to_expr (ai, var, rhs); - break; - } - - case ASM_EXPR: - /* Pointers defined by __asm__ statements can point anywhere. */ - set_pt_anything (var); - break; - - case NOP_EXPR: - if (IS_EMPTY_STMT (stmt)) - { - tree decl = SSA_NAME_VAR (var); - - if (TREE_CODE (decl) == PARM_DECL) - add_pointed_to_expr (ai, var, decl); - else if (DECL_INITIAL (decl)) - add_pointed_to_expr (ai, var, DECL_INITIAL (decl)); - else - add_pointed_to_expr (ai, var, decl); - } - break; - - case 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); - - switch (TREE_CODE (var)) - { - case ADDR_EXPR: - add_pointed_to_var (ai, lhs, var); - break; - - case SSA_NAME: - /* Avoid unnecessary merges. */ - if (lhs != var) - merge_pointed_to_info (ai, lhs, var); - break; - - default: - gcc_assert (is_gimple_min_invariant (var)); - add_pointed_to_expr (ai, lhs, var); - break; - } - break; - } - - default: - gcc_unreachable (); - } - - return false; -} - - /* Return true if STMT is an "escape" site from the current function. Escape sites those statements which might expose the address of a variable outside the current function. STMT is an escape site iff: @@ -2195,7 +1619,7 @@ collect_points_to_info_r (tree var, tree stmt, void *data) AI points to the alias information collected so far. */ -static bool +bool is_escape_site (tree stmt, struct alias_info *ai) { tree call = get_call_expr_in (stmt); @@ -2271,9 +1695,7 @@ create_memory_tag (tree type, bool is_type_tag) determine whether they should be considered globals. */ DECL_CONTEXT (tag) = current_function_decl; - /* Memory tags are by definition addressable. This also prevents - is_gimple_ref frome confusing memory tags with optimizable - variables. */ + /* Memory tags are by definition addressable. */ TREE_ADDRESSABLE (tag) = 1; ann = get_var_ann (tag); @@ -2304,7 +1726,6 @@ get_nmt_for (tree ptr) /* If PTR is a PARM_DECL, it points to a global variable or malloc, then its name tag should be considered a global variable. */ if (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL - || pi->pt_malloc || pi->pt_global_mem) mark_call_clobbered (tag); @@ -2560,9 +1981,6 @@ dump_points_to_info_for (FILE *file, tree ptr) if (pi->pt_anything) fprintf (file, ", points-to anything"); - if (pi->pt_malloc) - fprintf (file, ", points-to malloc"); - if (pi->pt_null) fprintf (file, ", points-to NULL"); @@ -2978,6 +2396,33 @@ get_or_create_used_part_for (size_t uid) } +/* Create and return a structure sub-variable for field FIELD of + variable VAR. */ + +static tree +create_sft (tree var, tree field) +{ + var_ann_t ann; + tree subvar = create_tmp_var_raw (TREE_TYPE (field), "SFT"); + + /* We need to copy the various flags from VAR to SUBVAR, so that + they are is_global_var iff the original variable was. */ + DECL_CONTEXT (subvar) = DECL_CONTEXT (var); + DECL_EXTERNAL (subvar) = DECL_EXTERNAL (var); + TREE_PUBLIC (subvar) = TREE_PUBLIC (var); + TREE_STATIC (subvar) = TREE_STATIC (var); + TREE_READONLY (subvar) = TREE_READONLY (var); + + /* Add the new variable to REFERENCED_VARS. */ + ann = get_var_ann (subvar); + ann->mem_tag_kind = STRUCT_FIELD; + ann->type_mem_tag = NULL; + add_referenced_tmp_var (subvar); + + return subvar; +} + + /* Given an aggregate VAR, create the subvariables that represent its fields. */ @@ -3067,7 +2512,6 @@ create_overlap_variables_for (tree var) { subvar_t sv; HOST_WIDE_INT fosize; - var_ann_t ann; tree currfotype; fosize = TREE_INT_CST_LOW (DECL_SIZE (fo->field)); @@ -3088,7 +2532,8 @@ create_overlap_variables_for (tree var) sv->offset = fo->offset; sv->size = fosize; sv->next = *subvars; - sv->var = create_tmp_var_raw (TREE_TYPE (fo->field), "SFT"); + sv->var = create_sft (var, fo->field); + if (dump_file) { fprintf (dump_file, "structure field tag %s created for var %s", @@ -3100,25 +2545,6 @@ create_overlap_variables_for (tree var) fprintf (dump_file, "\n"); } - /* We need to copy the various flags from var to sv->var, so that - they are is_global_var iff the original variable was. */ - - DECL_EXTERNAL (sv->var) = DECL_EXTERNAL (var); - TREE_PUBLIC (sv->var) = TREE_PUBLIC (var); - TREE_STATIC (sv->var) = TREE_STATIC (var); - TREE_READONLY (sv->var) = TREE_READONLY (var); - - /* Like other memory tags, these need to be marked addressable to - keep is_gimple_reg from thinking they are real. */ - TREE_ADDRESSABLE (sv->var) = 1; - - DECL_CONTEXT (sv->var) = DECL_CONTEXT (var); - - ann = get_var_ann (sv->var); - ann->mem_tag_kind = STRUCT_FIELD; - ann->type_mem_tag = NULL; - add_referenced_tmp_var (sv->var); - lastfotype = currfotype; lastfooffset = fo->offset; lastfosize = fosize; diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c index 7111960..28b19d9 100644 --- a/gcc/tree-ssa-copy.c +++ b/gcc/tree-ssa-copy.c @@ -188,7 +188,9 @@ merge_alias_info (tree orig, tree new) #endif /* Synchronize the type tags. If both pointers had a tag and they - are different, then something has gone wrong. */ + are different, then something has gone wrong. Type tags can + always be merged because they are flow insensitive, all the SSA + names of the same base DECL share the same type tag. */ if (new_ann->type_mem_tag == NULL_TREE) new_ann->type_mem_tag = orig_ann->type_mem_tag; else if (orig_ann->type_mem_tag == NULL_TREE) @@ -196,32 +198,41 @@ merge_alias_info (tree orig, tree new) else gcc_assert (new_ann->type_mem_tag == orig_ann->type_mem_tag); - /* Synchronize the name tags. If NEW did not have a name tag, get - it from ORIG. This happens when NEW is a compiler generated - temporary which still hasn't had its points-to information filled - in. */ - if (SSA_NAME_PTR_INFO (orig)) + /* Check that flow-sensitive information is compatible. Notice that + we may not merge flow-sensitive information here. This function + is called when propagating equivalences dictated by the IL, like + a copy operation P_i = Q_j, and from equivalences dictated by + control-flow, like if (P_i == Q_j). + + In the former case, P_i and Q_j are equivalent in every block + dominated by the assignment, so their flow-sensitive information + is always the same. However, in the latter case, the pointers + P_i and Q_j are only equivalent in one of the sub-graphs out of + the predicate, so their flow-sensitive information is not the + same in every block dominated by the predicate. + + Since we cannot distinguish one case from another in this + function, we can only make sure that if P_i and Q_j have + flow-sensitive information, they should be compatible. */ + if (SSA_NAME_PTR_INFO (orig) && SSA_NAME_PTR_INFO (new)) { struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig); struct ptr_info_def *new_ptr_info = SSA_NAME_PTR_INFO (new); - if (new_ptr_info == NULL) - duplicate_ssa_name_ptr_info (new, orig_ptr_info); - else if (orig_ptr_info->name_mem_tag - && new_ptr_info->name_mem_tag - && orig_ptr_info->pt_vars - && new_ptr_info->pt_vars) - { - /* Note that pointer NEW may actually have a different set - of pointed-to variables. However, since NEW is being - copy-propagated into ORIG, it must always be true that - the pointed-to set for pointer NEW is the same, or a - subset, of the pointed-to set for pointer ORIG. If this - isn't the case, we shouldn't have been able to do the - propagation of NEW into ORIG. */ - gcc_assert (bitmap_intersect_p (new_ptr_info->pt_vars, - orig_ptr_info->pt_vars)); - } + /* Note that pointer NEW and ORIG may actually have different + pointed-to variables (e.g., PR 18291 represented in + testsuite/gcc.c-torture/compile/pr18291.c). However, since + NEW is being copy-propagated into ORIG, it must always be + true that the pointed-to set for pointer NEW is the same, or + a subset, of the pointed-to set for pointer ORIG. If this + isn't the case, we shouldn't have been able to do the + propagation of NEW into ORIG. */ + if (orig_ptr_info->name_mem_tag + && new_ptr_info->name_mem_tag + && orig_ptr_info->pt_vars + && new_ptr_info->pt_vars) + gcc_assert (bitmap_intersect_p (new_ptr_info->pt_vars, + orig_ptr_info->pt_vars)); } } diff --git a/gcc/tree-ssa-operands.c b/gcc/tree-ssa-operands.c index f090024..34c0992 100644 --- a/gcc/tree-ssa-operands.c +++ b/gcc/tree-ssa-operands.c @@ -32,7 +32,6 @@ Boston, MA 02110-1301, USA. */ #include "ggc.h" #include "timevar.h" #include "toplev.h" - #include "langhooks.h" /* This file contains the code required to manage the operands cache of the @@ -148,7 +147,6 @@ static bool ops_active = false; static GTY (()) struct ssa_operand_memory_d *operand_memory = NULL; static unsigned operand_memory_index; -static void note_addressable (tree, stmt_ann_t); static void get_expr_operands (tree, tree *, int); static void get_asm_expr_operands (tree); static void get_indirect_ref_operands (tree, tree, int); @@ -1310,7 +1308,7 @@ get_expr_operands (tree stmt, tree *expr_p, int flags) case IMAGPART_EXPR: { tree ref; - HOST_WIDE_INT offset, size; + unsigned HOST_WIDE_INT offset, size; /* This component ref becomes an access to all of the subvariables it can touch, if we can determine that, but *NOT* the real one. If we can't determine which fields we could touch, the recursion @@ -1515,8 +1513,8 @@ get_asm_expr_operands (tree stmt) if (!allows_reg && allows_mem) { tree t = get_base_address (TREE_VALUE (link)); - if (t && DECL_P (t)) - note_addressable (t, s_ann); + if (t && DECL_P (t) && s_ann) + add_to_addressable_set (t, &s_ann->addresses_taken); } get_expr_operands (stmt, &TREE_VALUE (link), opf_is_def); @@ -1534,8 +1532,8 @@ get_asm_expr_operands (tree stmt) if (!allows_reg && allows_mem) { tree t = get_base_address (TREE_VALUE (link)); - if (t && DECL_P (t)) - note_addressable (t, s_ann); + if (t && DECL_P (t) && s_ann) + add_to_addressable_set (t, &s_ann->addresses_taken); } get_expr_operands (stmt, &TREE_VALUE (link), 0); @@ -1688,7 +1686,10 @@ get_tmr_operands (tree stmt, tree expr, int flags) flags &= ~opf_kill_def; if (TMR_SYMBOL (expr)) - note_addressable (TMR_SYMBOL (expr), stmt_ann (stmt)); + { + stmt_ann_t ann = stmt_ann (stmt); + add_to_addressable_set (TMR_SYMBOL (expr), &ann->addresses_taken); + } if (tag) add_stmt_operand (&tag, stmt_ann (stmt), flags); @@ -1757,9 +1758,9 @@ add_stmt_operand (tree *var_p, stmt_ann_t s_ann, int flags) /* If the operand is an ADDR_EXPR, add its operand to the list of variables that have had their address taken in this statement. */ - if (TREE_CODE (var) == ADDR_EXPR) + if (TREE_CODE (var) == ADDR_EXPR && s_ann) { - note_addressable (TREE_OPERAND (var, 0), s_ann); + add_to_addressable_set (TREE_OPERAND (var, 0), &s_ann->addresses_taken); return; } @@ -1861,35 +1862,17 @@ add_stmt_operand (tree *var_p, stmt_ann_t s_ann, int flags) if (flags & opf_is_def) { - bool added_may_defs_p = false; - /* If the variable is also an alias tag, add a virtual operand for it, otherwise we will miss representing references to the members of the variable's alias set. This fixes the bug in gcc.c-torture/execute/20020503-1.c. */ if (v_ann->is_alias_tag) - { - added_may_defs_p = true; - append_v_may_def (var); - } + append_v_may_def (var); for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++) - { - /* While VAR may be modifiable, some of its aliases - may not be. If that's the case, we don't really - need to add them a V_MAY_DEF for them. */ - tree alias = VARRAY_TREE (aliases, i); - - if (unmodifiable_var_p (alias)) - append_vuse (alias); - else - { - append_v_may_def (alias); - added_may_defs_p = true; - } - } + append_v_may_def (VARRAY_TREE (aliases, i)); - if (s_ann && added_may_defs_p) + if (s_ann) s_ann->makes_aliased_stores = 1; } else @@ -1910,40 +1893,51 @@ add_stmt_operand (tree *var_p, stmt_ann_t s_ann, int flags) } -/* Record that VAR had its address taken in the statement with annotations - S_ANN. */ +/* Add the base address of REF to the set *ADDRESSES_TAKEN. If + *ADDRESSES_TAKEN is NULL, a new set is created. REF may be + a single variable whose address has been taken or any other valid + GIMPLE memory reference (structure reference, array, etc). If the + base address of REF is a decl that has sub-variables, also add all + of its sub-variables. */ -static void -note_addressable (tree var, stmt_ann_t s_ann) +void +add_to_addressable_set (tree ref, bitmap *addresses_taken) { + tree var; subvar_t svars; - if (!s_ann) - return; - + gcc_assert (addresses_taken); + /* Note that it is *NOT OKAY* to use the target of a COMPONENT_REF - as the only thing we take the address of. - See PR 21407 and the ensuing mailing list discussion. */ - - var = get_base_address (var); + as the only thing we take the address of. If VAR is a structure, + taking the address of a field means that the whole structure may + be referenced using pointer arithmetic. See PR 21407 and the + ensuing mailing list discussion. */ + var = get_base_address (ref); if (var && SSA_VAR_P (var)) { - if (s_ann->addresses_taken == NULL) - s_ann->addresses_taken = BITMAP_GGC_ALLOC (); + if (*addresses_taken == NULL) + *addresses_taken = BITMAP_GGC_ALLOC (); - if (var_can_have_subvars (var) && (svars = get_subvars_for_var (var))) { subvar_t sv; for (sv = svars; sv; sv = sv->next) - bitmap_set_bit (s_ann->addresses_taken, DECL_UID (sv->var)); + { + bitmap_set_bit (*addresses_taken, DECL_UID (sv->var)); + TREE_ADDRESSABLE (sv->var) = 1; + } } else - bitmap_set_bit (s_ann->addresses_taken, DECL_UID (var)); + { + bitmap_set_bit (*addresses_taken, DECL_UID (var)); + TREE_ADDRESSABLE (var) = 1; + } } } + /* Add clobbering definitions for .GLOBAL_VAR or for each of the call clobbered variables in the function. */ diff --git a/gcc/tree-ssa-operands.h b/gcc/tree-ssa-operands.h index 99233fc..c1ec365 100644 --- a/gcc/tree-ssa-operands.h +++ b/gcc/tree-ssa-operands.h @@ -170,6 +170,8 @@ extern bool ssa_ro_call_cache_valid; extern bool ssa_operands_active (void); +extern void add_to_addressable_set (tree, bitmap *); + enum ssa_op_iter_type { ssa_op_iter_none = 0, ssa_op_iter_tree, diff --git a/gcc/tree-ssa-structalias.c b/gcc/tree-ssa-structalias.c index efa2238..7ec5270 100644 --- a/gcc/tree-ssa-structalias.c +++ b/gcc/tree-ssa-structalias.c @@ -26,7 +26,6 @@ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA #include "ggc.h" #include "obstack.h" #include "bitmap.h" -#include "tree-ssa-structalias.h" #include "flags.h" #include "rtl.h" #include "tm_p.h" @@ -49,6 +48,7 @@ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA #include "timevar.h" #include "alloc-pool.h" #include "splay-tree.h" +#include "tree-ssa-structalias.h" /* The idea behind this analyzer is to generate set constraints from the program, then solve the resulting constraints in order to generate the @@ -223,6 +223,9 @@ struct variable_info /* True for variables that have unions somewhere in them. */ unsigned int has_union:1; + /* True if this is a heap variable. */ + unsigned int is_heap_var:1; + /* Points-to set for this variable. */ bitmap solution; @@ -270,6 +273,12 @@ static varinfo_t var_integer; static tree integer_tree; static unsigned int integer_id; +/* Variable that represents arbitrary offsets into an object. Used to + represent pointer arithmetic, which may not legally escape the + bounds of an object. */ +static varinfo_t var_anyoffset; +static tree anyoffset_tree; +static unsigned int anyoffset_id; /* Return a new variable info structure consisting for a variable named NAME, and using constraint graph node NODE. */ @@ -286,6 +295,7 @@ new_var_info (tree t, unsigned int id, const char *name, unsigned int node) ret->address_taken = false; ret->indirect_target = false; ret->is_artificial_var = false; + ret->is_heap_var = false; ret->is_unknown_size_var = false; ret->solution = BITMAP_ALLOC (&ptabitmap_obstack); bitmap_clear (ret->solution); @@ -941,8 +951,11 @@ build_constraint_graph (void) constraint_t c; graph = ggc_alloc (sizeof (struct constraint_graph)); - graph->succs = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->succs)); - graph->preds = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->preds)); + graph->succs = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) + * sizeof (*graph->succs)); + graph->preds = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) + * sizeof (*graph->preds)); + for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) { struct constraint_expr lhs = c->lhs; @@ -983,6 +996,8 @@ build_constraint_graph (void) } } } + + /* Changed variables on the last iteration. */ static unsigned int changed_count; static sbitmap changed; @@ -2137,11 +2152,18 @@ get_constraint_for (tree t) &ANYTHING added. */ if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)) { - tree heapvar = create_tmp_var_raw (ptr_type_node, "HEAP"); + varinfo_t vi; + tree heapvar; + + heapvar = create_tmp_var_raw (ptr_type_node, "HEAP"); + DECL_EXTERNAL (heapvar) = 1; + add_referenced_tmp_var (heapvar); temp.var = create_variable_info_for (heapvar, alias_get_name (heapvar)); - get_varinfo (temp.var)->is_artificial_var = 1; + vi = get_varinfo (temp.var); + vi->is_artificial_var = 1; + vi->is_heap_var = 1; temp.type = ADDRESSOF; temp.offset = 0; return temp; @@ -2191,9 +2213,11 @@ get_constraint_for (tree t) /* Cast from non-pointer to pointers are bad news for us. Anything else, we see through */ - if (!(POINTER_TYPE_P (TREE_TYPE (t)) && - ! POINTER_TYPE_P (TREE_TYPE (op)))) + if (!(POINTER_TYPE_P (TREE_TYPE (t)) + && ! POINTER_TYPE_P (TREE_TYPE (op)))) return get_constraint_for (op); + + /* FALLTHRU */ } default: { @@ -2467,81 +2491,300 @@ ref_contains_indirect_ref (tree ref) } -/* Tree walker that is the heart of the aliasing infrastructure. - TP is a pointer to the current tree. - WALK_SUBTREES specifies whether to continue traversing subtrees or - not. - Returns NULL_TREE when we should stop. - - This function is the main part of the constraint builder. It - walks the trees, calling the appropriate building functions - to process various statements. */ +/* Update related alias information kept in AI. This is used when + building name tags, alias sets and deciding grouping heuristics. + STMT is the statement to process. This function also updates + ADDRESSABLE_VARS. */ + +static void +update_alias_info (tree stmt, struct alias_info *ai) +{ + bitmap addr_taken; + use_operand_p use_p; + def_operand_p def_p; + ssa_op_iter iter; + bool stmt_escapes_p = is_escape_site (stmt, ai); + + /* Mark all the variables whose address are taken by the statement. */ + addr_taken = addresses_taken (stmt); + if (addr_taken) + { + bitmap_ior_into (addressable_vars, addr_taken); + + /* If STMT is an escape point, all the addresses taken by it are + call-clobbered. */ + if (stmt_escapes_p) + { + bitmap_iterator bi; + unsigned i; + + EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi) + mark_call_clobbered (referenced_var (i)); + } + } + + /* Process each operand use. If an operand may be aliased, keep + track of how many times it's being used. For pointers, determine + whether they are dereferenced by the statement, or whether their + value escapes, etc. */ + FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) + { + tree op, var; + var_ann_t v_ann; + struct ptr_info_def *pi; + bool is_store; + unsigned num_uses, num_derefs; + + op = USE_FROM_PTR (use_p); + + /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it + to the set of addressable variables. */ + if (TREE_CODE (op) == ADDR_EXPR) + { + gcc_assert (TREE_CODE (stmt) == PHI_NODE); + + /* PHI nodes don't have annotations for pinning the set + of addresses taken, so we collect them here. + + FIXME, should we allow PHI nodes to have annotations + so that they can be treated like regular statements? + Currently, they are treated as second-class + statements. */ + add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars); + continue; + } + + /* Ignore constants. */ + if (TREE_CODE (op) != SSA_NAME) + continue; + + var = SSA_NAME_VAR (op); + v_ann = var_ann (var); + + /* If the operand's variable may be aliased, keep track of how + many times we've referenced it. This is used for alias + grouping in compute_flow_insensitive_aliasing. */ + if (may_be_aliased (var)) + NUM_REFERENCES_INC (v_ann); + + /* We are only interested in pointers. */ + if (!POINTER_TYPE_P (TREE_TYPE (op))) + continue; + + pi = get_ptr_info (op); + + /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */ + if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op))) + { + SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)); + VARRAY_PUSH_TREE (ai->processed_ptrs, op); + } + + /* If STMT is a PHI node, then it will not have pointer + dereferences and it will not be an escape point. */ + if (TREE_CODE (stmt) == PHI_NODE) + continue; + + /* Determine whether OP is a dereferenced pointer, and if STMT + is an escape point, whether OP escapes. */ + count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store); + + if (num_derefs > 0) + { + /* Mark OP as 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. */ + pi->is_dereferenced = 1; + + /* Keep track of how many time we've dereferenced each + pointer. */ + NUM_REFERENCES_INC (v_ann); + + /* If this is a store operation, mark OP as being + dereferenced to store, otherwise mark it as being + dereferenced to load. */ + if (is_store) + bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var)); + else + bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var)); + } + + if (stmt_escapes_p && num_derefs < num_uses) + { + /* If STMT is an escape point and STMT contains at + least one direct use of OP, then the value of OP + escapes and so the pointed-to variables need to + be marked call-clobbered. */ + pi->value_escapes_p = 1; + + /* 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)) + { + bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var)); + pi->is_dereferenced = 1; + } + } + } + + /* Update reference counter for definitions to any potentially + aliased variable. This is used in the alias grouping heuristics. */ + FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, iter, SSA_OP_ALL_DEFS) + { + tree op = DEF_FROM_PTR (def_p); + tree var = SSA_NAME_VAR (op); + var_ann_t ann = var_ann (var); + bitmap_set_bit (ai->written_vars, DECL_UID (var)); + if (may_be_aliased (var)) + NUM_REFERENCES_INC (ann); + } +} + + +/* Handle pointer arithmetic EXPR when creating aliasing constraints. + Expressions of the type PTR + CST can be handled in two ways: + + 1- If the constraint for PTR is ADDRESSOF for a non-structure + variable, then we can use it directly because adding or + subtracting a constant may not alter the original ADDRESSOF + constraing (i.e., pointer arithmetic may not legally go outside + an object's boundaries). + + 2- If the constraint for PTR is ADDRESSOF for a structure variable, + then if CST is a compile-time constant that can be used as an + offset, we can determine which sub-variable will be pointed-to + by the expression. + + Return true if the expression is handled. For any other kind of + expression, return false so that each operand can be added as a + separate constraint by the caller. */ + +static bool +handle_ptr_arith (struct constraint_expr lhs, tree expr) +{ + tree op0, op1; + struct constraint_expr base, offset; + + if (TREE_CODE (expr) != PLUS_EXPR) + return false; + + op0 = TREE_OPERAND (expr, 0); + op1 = TREE_OPERAND (expr, 1); + + base = get_constraint_for (op0); + + offset.var = anyoffset_id; + offset.type = ADDRESSOF; + offset.offset = 0; + + process_constraint (new_constraint (lhs, base)); + process_constraint (new_constraint (lhs, offset)); + + return true; +} + + +/* Walk statement T setting up aliasing constraints according to the + references found in T. This function is the main part of the + constraint builder. AI points to auxiliary alias information used + when building alias sets and computing alias grouping heuristics. */ static void -find_func_aliases (tree t) +find_func_aliases (tree t, struct alias_info *ai) { struct constraint_expr lhs, rhs; - switch (TREE_CODE (t)) - { - case PHI_NODE: - { - int i; - /* Only care about pointers and structures containing - pointers. */ - if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t))) - || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t)))) - { - lhs = get_constraint_for (PHI_RESULT (t)); - for (i = 0; i < PHI_NUM_ARGS (t); i++) - { - rhs = get_constraint_for (PHI_ARG_DEF (t, i)); - process_constraint (new_constraint (lhs, rhs)); - } - } - } - break; + /* Update various related attributes like escaped addresses, pointer + dereferences for loads and stores. This is used when creating + name tags and alias sets. */ + update_alias_info (t, ai); - case MODIFY_EXPR: - { - tree lhsop = TREE_OPERAND (t, 0); - tree rhsop = TREE_OPERAND (t, 1); - int i; + /* Now build constraints expressions. */ + if (TREE_CODE (t) == PHI_NODE) + { + /* Only care about pointers and structures containing + pointers. */ + if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t))) + || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t)))) + { + int i; - if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) - && AGGREGATE_TYPE_P (TREE_TYPE (rhsop))) - { - do_structure_copy (lhsop, rhsop); - } - else - { - /* Only care about operations with pointers, structures - containing pointers, dereferences, and call - expressions. */ - if (POINTER_TYPE_P (TREE_TYPE (lhsop)) - || AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) - || ref_contains_indirect_ref (lhsop) - || TREE_CODE (rhsop) == CALL_EXPR) - { - lhs = get_constraint_for (lhsop); - switch (TREE_CODE_CLASS (TREE_CODE (rhsop))) - { - /* RHS that consist of unary operations, - exceptional types, or bare decls/constants, get - handled directly by get_constraint_for. */ + lhs = get_constraint_for (PHI_RESULT (t)); + for (i = 0; i < PHI_NUM_ARGS (t); i++) + { + rhs = get_constraint_for (PHI_ARG_DEF (t, i)); + process_constraint (new_constraint (lhs, rhs)); + } + } + } + else if (TREE_CODE (t) == MODIFY_EXPR) + { + tree lhsop = TREE_OPERAND (t, 0); + tree rhsop = TREE_OPERAND (t, 1); + int i; + + if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) + && AGGREGATE_TYPE_P (TREE_TYPE (rhsop))) + { + do_structure_copy (lhsop, rhsop); + } + else + { + /* Only care about operations with pointers, structures + containing pointers, dereferences, and call expressions. */ + if (POINTER_TYPE_P (TREE_TYPE (lhsop)) + || AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) + || ref_contains_indirect_ref (lhsop) + || TREE_CODE (rhsop) == CALL_EXPR) + { + lhs = get_constraint_for (lhsop); + switch (TREE_CODE_CLASS (TREE_CODE (rhsop))) + { + /* RHS that consist of unary operations, + exceptional types, or bare decls/constants, get + handled directly by get_constraint_for. */ case tcc_reference: case tcc_declaration: case tcc_constant: case tcc_exceptional: case tcc_expression: case tcc_unary: - { - rhs = get_constraint_for (rhsop); - process_constraint (new_constraint (lhs, rhs)); - } + { + rhs = get_constraint_for (rhsop); + process_constraint (new_constraint (lhs, rhs)); + + /* When taking the address of an aggregate + type, from the LHS we can access any field + of the RHS. */ + if (rhs.type == ADDRESSOF + && rhs.var > anything_id + && AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (rhsop)))) + { + rhs.var = anyoffset_id; + rhs.type = ADDRESSOF; + rhs.offset = 0; + process_constraint (new_constraint (lhs, rhs)); + } + } break; - /* Otherwise, walk each operand. */ + case tcc_binary: + { + /* For pointer arithmetic of the form + PTR + CST, we can simply use PTR's + constraint because pointer arithmetic is + not allowed to go out of bounds. */ + if (handle_ptr_arith (lhs, rhsop)) + break; + } + /* FALLTHRU */ + + /* Otherwise, walk each operand. Notice that we + can't use the operand interface because we need + to process expressions other than simple operands + (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */ default: for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++) { @@ -2549,15 +2792,16 @@ find_func_aliases (tree t) rhs = get_constraint_for (op); process_constraint (new_constraint (lhs, rhs)); } - } - } - } - } - break; - - default: - break; + } + } + } } + + /* After promoting variables and computing aliasing we will + need to re-scan most statements. FIXME: Try to minimize the + number of statements re-scanned. It's not really necessary to + re-scan *all* statements. */ + mark_stmt_modified (t); } @@ -2718,12 +2962,12 @@ create_variable_info_for (tree decl, const char *name) tree decltype = TREE_TYPE (decl); bool notokay = false; bool hasunion; - subvar_t svars; bool is_global = DECL_P (decl) ? is_global_var (decl) : false; VEC (fieldoff_s,heap) *fieldstack = NULL; - hasunion = TREE_CODE (decltype) == UNION_TYPE || TREE_CODE (decltype) == QUAL_UNION_TYPE; + hasunion = TREE_CODE (decltype) == UNION_TYPE + || TREE_CODE (decltype) == QUAL_UNION_TYPE; if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion) { push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion); @@ -2733,62 +2977,6 @@ create_variable_info_for (tree decl, const char *name) notokay = true; } } - - /* If this variable already has subvars, just create the variables for the - subvars and we are done. - NOTE: This assumes things haven't generated uses of previously - unused structure fields. */ - if (use_field_sensitive - && !notokay - && var_can_have_subvars (decl) - && var_ann (decl) - && (svars = get_subvars_for_var (decl))) - { - subvar_t sv; - varinfo_t base = NULL; - unsigned int firstindex = index; - - for (sv = svars; sv; sv = sv->next) - { - /* For debugging purposes, this will print the names of the - fields as "<var>.<offset>.<size>" - This is only for debugging purposes. */ -#define PRINT_LONG_NAMES -#ifdef PRINT_LONG_NAMES - char *tempname; - const char *newname; - - asprintf (&tempname, - "%s." HOST_WIDE_INT_PRINT_DEC "." HOST_WIDE_INT_PRINT_DEC, - alias_get_name (decl), sv->offset, sv->size); - newname = ggc_strdup (tempname); - free (tempname); - vi = new_var_info (sv->var, index, newname, index); -#else - vi = new_var_info (sv->var, index, alias_get_name (sv->var), index); -#endif - vi->decl = sv->var; - vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype)); - vi->size = sv->size; - vi->offset = sv->offset; - if (!base) - { - base = vi; - insert_id_for_tree (decl, index); - } - else - { - insert_into_field_list (base, vi); - } - insert_id_for_tree (sv->var, index); - VEC_safe_push (varinfo_t, gc, varmap, vi); - if (is_global) - make_constraint_to_anything (vi); - index++; - - } - return firstindex; - } /* If the variable doesn't have subvars, we may end up needing to @@ -2935,7 +3123,6 @@ intra_create_variable_infos (void) lhs.type = SCALAR; lhs.var = create_variable_info_for (t, alias_get_name (t)); - get_varinfo (lhs.var)->is_artificial_var = true; rhs.var = anything_id; rhs.type = ADDRESSOF; rhs.offset = 0; @@ -2958,30 +3145,67 @@ set_uids_in_ptset (bitmap into, bitmap from) { unsigned int i; bitmap_iterator bi; + bool found_anyoffset = false; + subvar_t sv; EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi) { varinfo_t vi = get_varinfo (i); + + /* If we find ANYOFFSET in the solution and the solution + includes SFTs for some structure, then all the SFTs in that + structure will need to be added to the alias set. */ + if (vi->id == anyoffset_id) + { + found_anyoffset = true; + continue; + } + + /* The only artificial variables that are allowed in a may-alias + set are heap variables. */ + if (vi->is_artificial_var && !vi->is_heap_var) + continue; - /* Variables containing unions may need to be converted to their - SFT's, because SFT's can have unions and we cannot. */ if (vi->has_union && get_subvars_for_var (vi->decl) != NULL) { - subvar_t svars = get_subvars_for_var (vi->decl); - subvar_t sv; - for (sv = svars; sv; sv = sv->next) + /* Variables containing unions may need to be converted to + their SFT's, because SFT's can have unions and we cannot. */ + for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next) bitmap_set_bit (into, DECL_UID (sv->var)); } - /* We may end up with labels in the points-to set because people - take their address, and they are _DECL's. */ else if (TREE_CODE (vi->decl) == VAR_DECL - || TREE_CODE (vi->decl) == PARM_DECL) - bitmap_set_bit (into, DECL_UID (vi->decl)); - - + || TREE_CODE (vi->decl) == PARM_DECL) + { + if (found_anyoffset + && var_can_have_subvars (vi->decl) + && get_subvars_for_var (vi->decl)) + { + /* If ANYOFFSET is in the solution set and VI->DECL is + an aggregate variable with sub-variables, then any of + the SFTs inside VI->DECL may have been accessed. Add + all the sub-vars for VI->DECL. */ + for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next) + bitmap_set_bit (into, DECL_UID (sv->var)); + } + else if (var_can_have_subvars (vi->decl) + && get_subvars_for_var (vi->decl)) + { + /* If VI->DECL is an aggregate for which we created + SFTs, add the SFT corresponding to VI->OFFSET. */ + tree sft = get_subvar_at (vi->decl, vi->offset); + bitmap_set_bit (into, DECL_UID (sft)); + } + else + { + /* Otherwise, just add VI->DECL to the alias set. */ + bitmap_set_bit (into, DECL_UID (vi->decl)); + } + } } } -static int have_alias_info = false; + + +static bool have_alias_info = false; /* Given a pointer variable P, fill in its points-to set, or return false if we can't. */ @@ -2990,8 +3214,10 @@ bool find_what_p_points_to (tree p) { unsigned int id = 0; + if (!have_alias_info) return false; + if (lookup_id_for_tree (p, &id)) { varinfo_t vi = get_varinfo (id); @@ -2999,14 +3225,15 @@ find_what_p_points_to (tree p) if (vi->is_artificial_var) return false; - /* See if this is a field or a structure */ + /* See if this is a field or a structure. */ if (vi->size != vi->fullsize) { + /* Nothing currently asks about structure fields directly, + but when they do, we need code here to hand back the + points-to set. */ if (!var_can_have_subvars (vi->decl) || get_subvars_for_var (vi->decl) == NULL) return false; - /* Nothing currently asks about structure fields directly, but when - they do, we need code here to hand back the points-to set. */ } else { @@ -3018,21 +3245,45 @@ find_what_p_points_to (tree p) variable. */ vi = get_varinfo (vi->node); - /* Make sure there aren't any artificial vars in the points to set. - XXX: Note that we need to translate our heap variables to - something. */ + /* Translate artificial variables into SSA_NAME_PTR_INFO + attributes. */ EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) { - if (get_varinfo (i)->is_artificial_var) - return false; + varinfo_t vi = get_varinfo (i); + + if (vi->is_artificial_var) + { + /* FIXME. READONLY should be handled better so that + flow insensitive aliasing can disregard writeable + aliases. */ + if (vi->id == nothing_id) + pi->pt_null = 1; + else if (vi->id == anything_id) + pi->pt_anything = 1; + else if (vi->id == readonly_id) + pi->pt_anything = 1; + else if (vi->id == integer_id) + pi->pt_anything = 1; + else if (vi->is_heap_var) + pi->pt_global_mem = 1; + } } - pi->pt_anything = false; + + if (pi->pt_anything) + return false; + if (!pi->pt_vars) pi->pt_vars = BITMAP_GGC_ALLOC (); + set_uids_in_ptset (pi->pt_vars, vi->solution); + + if (bitmap_empty_p (pi->pt_vars)) + pi->pt_vars = NULL; + return true; } } + return false; } @@ -3053,7 +3304,7 @@ dump_sa_points_to_info (FILE *outfile) { unsigned int i; - fprintf (outfile, "\nPoints-to information\n\n"); + fprintf (outfile, "\nPoints-to sets\n\n"); if (dump_flags & TDF_STATS) { @@ -3124,6 +3375,7 @@ init_base_vars (void) rhs.var = anything_id; rhs.offset = 0; var_anything->address_taken = true; + /* This specifically does not use process_constraint because process_constraint ignores all anything = anything constraints, since all but this one are redundant. */ @@ -3177,17 +3429,44 @@ init_base_vars (void) rhs.var = anything_id; rhs.offset = 0; process_constraint (new_constraint (lhs, rhs)); + + /* Create the ANYOFFSET variable, used to represent an arbitrary offset + inside an object. This is similar to ANYTHING, but less drastic. + It means that the pointer can point anywhere inside an object, + but not outside of it. */ + anyoffset_tree = create_tmp_var_raw (void_type_node, "ANYOFFSET"); + anyoffset_id = 4; + var_anyoffset = new_var_info (anyoffset_tree, anyoffset_id, "ANYOFFSET", + anyoffset_id); + insert_id_for_tree (anyoffset_tree, anyoffset_id); + var_anyoffset->is_artificial_var = 1; + var_anyoffset->size = ~0; + var_anyoffset->offset = 0; + var_anyoffset->next = NULL; + var_anyoffset->fullsize = ~0; + VEC_safe_push (varinfo_t, gc, varmap, var_anyoffset); + + /* ANYOFFSET points to ANYOFFSET. */ + lhs.type = SCALAR; + lhs.var = anyoffset_id; + lhs.offset = 0; + rhs.type = ADDRESSOF; + rhs.var = anyoffset_id; + rhs.offset = 0; + process_constraint (new_constraint (lhs, rhs)); } /* Create points-to sets for the current function. See the comments at the start of the file for an algorithmic overview. */ -static void -create_alias_vars (void) +void +compute_points_to_sets (struct alias_info *ai) { basic_block bb; - + + timevar_push (TV_TREE_PTA); + init_alias_vars (); constraint_pool = create_alloc_pool ("Constraint pool", @@ -3201,7 +3480,7 @@ create_alias_vars (void) varmap = VEC_alloc (varinfo_t, gc, 8); id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free); memset (&stats, 0, sizeof (stats)); - + init_base_vars (); intra_create_variable_infos (); @@ -3214,28 +3493,29 @@ create_alias_vars (void) for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) if (is_gimple_reg (PHI_RESULT (phi))) - find_func_aliases (phi); + find_func_aliases (phi, ai); for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - find_func_aliases (bsi_stmt (bsi)); + find_func_aliases (bsi_stmt (bsi), ai); } build_constraint_graph (); if (dump_file) { - fprintf (dump_file, "Constraints:\n"); + fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n"); dump_constraints (dump_file); } if (dump_file) - fprintf (dump_file, "Collapsing static cycles and doing variable substitution:\n"); + fprintf (dump_file, "\nCollapsing static cycles and doing variable " + "substitution:\n"); find_and_collapse_graph_cycles (graph, false); perform_var_substitution (graph); if (dump_file) - fprintf (dump_file, "Solving graph:\n"); + fprintf (dump_file, "\nSolving graph:\n"); solve_graph (graph); @@ -3243,30 +3523,15 @@ create_alias_vars (void) dump_sa_points_to_info (dump_file); have_alias_info = true; + + timevar_pop (TV_TREE_PTA); } -struct tree_opt_pass pass_build_pta = -{ - "pta", /* name */ - NULL, /* gate */ - create_alias_vars, /* execute */ - NULL, /* sub */ - NULL, /* next */ - 0, /* static_pass_number */ - TV_TREE_PTA, /* tv_id */ - PROP_cfg, /* properties_required */ - PROP_pta, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ - 0 /* letter */ -}; - /* Delete created points-to sets. */ -static void -delete_alias_vars (void) +void +delete_points_to_sets (void) { htab_delete (id_for_tree); free_alloc_pool (variable_info_pool); @@ -3275,20 +3540,3 @@ delete_alias_vars (void) bitmap_obstack_release (&ptabitmap_obstack); have_alias_info = false; } - -struct tree_opt_pass pass_del_pta = -{ - NULL, /* name */ - NULL, /* gate */ - delete_alias_vars, /* execute */ - NULL, /* sub */ - NULL, /* next */ - 0, /* static_pass_number */ - TV_TREE_PTA, /* tv_id */ - PROP_pta, /* properties_required */ - 0, /* properties_provided */ - PROP_pta, /* properties_destroyed */ - 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ - 0 /* letter */ -}; diff --git a/gcc/tree-ssa-structalias.h b/gcc/tree-ssa-structalias.h index a6241e5..ddabd6d 100644 --- a/gcc/tree-ssa-structalias.h +++ b/gcc/tree-ssa-structalias.h @@ -25,6 +25,66 @@ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA struct constraint; typedef struct constraint *constraint_t; +/* Alias information used by compute_may_aliases and its helpers. */ +struct alias_info +{ + /* SSA names visited while collecting points-to information. If bit I + is set, it means that SSA variable with version I has already been + visited. */ + sbitmap ssa_names_visited; + + /* Array of SSA_NAME pointers processed by the points-to collector. */ + varray_type processed_ptrs; + + /* ADDRESSABLE_VARS contains all the global variables and locals that + have had their address taken. */ + struct alias_map_d **addressable_vars; + size_t num_addressable_vars; + + /* POINTERS contains all the _DECL pointers with unique memory tags + that have been referenced in the program. */ + struct alias_map_d **pointers; + size_t num_pointers; + + /* Number of function calls found in the program. */ + size_t num_calls_found; + + /* Number of const/pure function calls found in the program. */ + size_t num_pure_const_calls_found; + + /* Array of counters to keep track of how many times each pointer has + been dereferenced in the program. This is used by the alias grouping + heuristic in compute_flow_insensitive_aliasing. */ + varray_type num_references; + + /* Total number of virtual operands that will be needed to represent + all the aliases of all the pointers found in the program. */ + long total_alias_vops; + + /* Variables that have been written to. */ + bitmap written_vars; + + /* Pointers that have been used in an indirect store operation. */ + bitmap dereferenced_ptrs_store; + + /* Pointers that have been used in an indirect load operation. */ + bitmap dereferenced_ptrs_load; +}; + +/* Keep track of how many times each pointer has been dereferenced in + the program using the aux variable. This is used by the alias + grouping heuristic in compute_flow_insensitive_aliasing. */ +#define NUM_REFERENCES(ANN) ((size_t)((ANN)->common.aux)) +#define NUM_REFERENCES_CLEAR(ANN) ((ANN)->common.aux) = 0 +#define NUM_REFERENCES_INC(ANN) (ANN)->common.aux = (void*) (((size_t)((ANN)->common.aux)) + 1) +#define NUM_REFERENCES_SET(ANN, VAL) (ANN)->common.aux = (void*) ((void *)(VAL)) + +/* In tree-ssa-alias.c. */ +bool is_escape_site (tree, struct alias_info *); + +/* In tree-ssa-structalias.c. */ +extern void compute_points_to_sets (struct alias_info *); +extern void delete_points_to_sets (void); extern void dump_constraint (FILE *, constraint_t); extern void dump_constraints (FILE *); extern void debug_constraint (constraint_t); diff --git a/gcc/tree-ssa.c b/gcc/tree-ssa.c index c88030d..ef892b5 100644 --- a/gcc/tree-ssa.c +++ b/gcc/tree-ssa.c @@ -467,10 +467,9 @@ verify_flow_sensitive_alias_info (void) } if (pi->name_mem_tag - && !pi->pt_malloc && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars))) { - error ("pointers with a memory tag, should have points-to sets or point to malloc"); + error ("pointers with a memory tag, should have points-to sets"); goto err; } |