#include "tree-flow.h"
#include "tree-inline.h"
#include "tree-pass.h"
-#include "tree-ssa-structalias.h"
#include "convert.h"
#include "params.h"
#include "ipa-type-escape.h"
#include "vecprim.h"
#include "pointer-set.h"
#include "alloc-pool.h"
+#include "tree-ssa-alias.h"
-/* Broad overview of how aliasing works:
-
- First we compute points-to sets, which is done in
- tree-ssa-structalias.c
-
- During points-to set constraint finding, a bunch of little bits of
- information is collected.
- This is not done because it is necessary for points-to, but because
- points-to has to walk every statement anyway. The function performing
- this collecting is update_alias_info.
-
- Bits update_alias_info collects include:
- 1. Directly escaping variables and variables whose value escapes
- (using is_escape_site). This is the set of variables and values that
- escape prior to transitive closure of the clobbers.
- 2. The set of variables dereferenced on the LHS (into
- dereferenced_ptr_stores)
- 3. The set of variables dereferenced on the RHS (into
- dereferenced_ptr_loads)
- 4. The set of all pointers we saw.
- 5. The number of loads and stores for each variable
- 6. The number of statements touching memory
- 7. The set of address taken variables.
-
-
- #1 is computed by a combination of is_escape_site, and counting the
- number of uses/deref operators. This function properly accounts for
- situations like &ptr->field, which is *not* a dereference.
-
- After points-to sets are computed, the sets themselves still
- contain points-to specific variables, such as a variable that says
- the pointer points to anything, a variable that says the pointer
- points to readonly memory, etc.
-
- These are eliminated in a later phase, as we will see.
-
- The rest of the phases are located in tree-ssa-alias.c
-
- The next phase after points-to set computation is called
- "setup_pointers_and_addressables"
-
- This pass does 3 main things:
-
- 1. All variables that can have TREE_ADDRESSABLE removed safely (IE
- non-globals whose address is not taken), have TREE_ADDRESSABLE
- removed.
- 2. All variables that may be aliased (which is the set of addressable
- variables and globals) at all, are marked for renaming, and have
- symbol memory tags created for them.
- 3. All variables which are stored into have their SMT's added to
- written vars.
-
-
- After this function is run, all variables that will ever have an
- SMT, have one, though its aliases are not filled in.
-
- The next phase is to compute flow-insensitive aliasing, which in
- our case, is a misnomer. it is really computing aliasing that
- requires no transitive closure to be correct. In particular, it
- uses stack vs non-stack, TBAA, etc, to determine whether two
- symbols could *ever* alias . This phase works by going through all
- the pointers we collected during update_alias_info, and for every
- addressable variable in the program, seeing if they alias. If so,
- the addressable variable is added to the symbol memory tag for the
- pointer.
-
- As part of this, we handle symbol memory tags that conflict but
- have no aliases in common, by forcing them to have a symbol in
- common (through unioning alias sets or adding one as an alias of
- the other), or by adding one as an alias of another. The case of
- conflicts with no aliases in common occurs mainly due to aliasing
- we cannot see. In particular, it generally means we have a load
- through a pointer whose value came from outside the function.
- Without an addressable symbol to point to, they would get the wrong
- answer.
-
- After flow insensitive aliasing is computed, we compute name tags
- (called compute_flow_sensitive_info). We walk each pointer we
- collected and see if it has a usable points-to set. If so, we
- generate a name tag using that pointer, and make an alias bitmap for
- it. Name tags are shared between all things with the same alias
- bitmap. The alias bitmap will be translated from what points-to
- computed. In particular, the "anything" variable in points-to will be
- transformed into a pruned set of SMT's and their aliases that
- compute_flow_insensitive_aliasing computed.
- Note that since 4.3, every pointer that points-to computed a solution for
- will get a name tag (whereas before 4.3, only those whose set did
- *not* include the anything variable would). At the point where name
- tags are all assigned, symbol memory tags are dead, and could be
- deleted, *except* on global variables. Global variables still use
- symbol memory tags as of right now.
-
- After name tags are computed, the set of clobbered variables is
- transitively closed. In particular, we compute the set of clobbered
- variables based on the initial set of clobbers, plus the aliases of
- pointers which either escape, or have their value escape.
-
- After this, maybe_create_global_var is run, which handles a corner
- case where we have no call clobbered variables, but have pure and
- non-pure functions.
-
- Staring at this function, I now remember it is a hack for the fact
- that we do not mark all globals in the program as call clobbered for a
- function unless they are actually used in that function. Instead, we
- only mark the set that is actually clobbered. As a result, you can
- end up with situations where you have no call clobbered vars set.
-
- After maybe_create_global_var, we set pointers with the REF_ALL flag
- to have alias sets that include all clobbered
- memory tags and variables.
-
- After this, memory partitioning is computed (by the function
- compute_memory_partitions) and alias sets are reworked accordingly.
-
- Lastly, we delete partitions with no symbols, and clean up after
- ourselves. */
-
-
-/* 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. */
- VEC(tree,heap) *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;
-
- /* Pointers that have been used in an indirect load/store operation. */
- struct pointer_set_t *dereferenced_ptrs;
-};
-
-
-/* Structure to map a variable to its alias set. */
-struct alias_map_d
-{
- /* Variable and its alias set. */
- tree var;
- alias_set_type set;
-};
-
-
-/* Counters used to display statistics on alias analysis. */
-struct alias_stats_d
-{
- unsigned int alias_queries;
- unsigned int alias_mayalias;
- unsigned int alias_noalias;
- unsigned int simple_queries;
- unsigned int simple_resolved;
- unsigned int tbaa_queries;
- unsigned int tbaa_resolved;
- unsigned int structnoaddress_queries;
- unsigned int structnoaddress_resolved;
-};
-
-
-/* Local variables. */
-static struct alias_stats_d alias_stats;
-static bitmap_obstack alias_bitmap_obstack;
-
-/* Local functions. */
-static void compute_flow_insensitive_aliasing (struct alias_info *);
-static void dump_alias_stats (FILE *);
-static tree create_memory_tag (tree type, bool is_type_tag);
-static tree get_smt_for (tree, struct alias_info *);
-static tree get_nmt_for (tree);
-static void add_may_alias (tree, tree);
-static struct alias_info *init_alias_info (void);
-static void delete_alias_info (struct alias_info *);
-static void compute_flow_sensitive_aliasing (struct alias_info *);
-static void setup_pointers_and_addressables (struct alias_info *);
-static void update_alias_info (struct alias_info *);
-static void create_global_var (void);
-static void maybe_create_global_var (void);
-static void set_pt_anything (tree);
-
-void debug_mp_info (VEC(mem_sym_stats_t,heap) *);
-
-static alloc_pool mem_sym_stats_pool;
-
-/* Return memory reference stats for symbol VAR. Create a new slot in
- cfun->gimple_df->mem_sym_stats if needed. */
-
-static struct mem_sym_stats_d *
-get_mem_sym_stats_for (tree var)
-{
- void **slot;
- struct mem_sym_stats_d *stats;
- struct pointer_map_t *map = gimple_mem_ref_stats (cfun)->mem_sym_stats;
-
- gcc_assert (map);
-
- slot = pointer_map_insert (map, var);
- if (*slot == NULL)
- {
- stats = (struct mem_sym_stats_d *) pool_alloc (mem_sym_stats_pool);
- memset (stats, 0, sizeof (*stats));
- stats->var = var;
- *slot = (void *) stats;
- }
- else
- stats = (struct mem_sym_stats_d *) *slot;
-
- return stats;
-}
-
-
-/* Return memory reference statistics for variable VAR in function FN.
- This is computed by alias analysis, but it is not kept
- incrementally up-to-date. So, these stats are only accurate if
- pass_may_alias has been run recently. If no alias information
- exists, this function returns NULL. */
-
-static mem_sym_stats_t
-mem_sym_stats (struct function *fn, tree var)
-{
- void **slot;
- struct pointer_map_t *stats_map = gimple_mem_ref_stats (fn)->mem_sym_stats;
-
- if (stats_map == NULL)
- return NULL;
-
- slot = pointer_map_contains (stats_map, var);
- if (slot == NULL)
- return NULL;
-
- return (mem_sym_stats_t) *slot;
-}
-
-
-/* Set MPT to be the memory partition associated with symbol SYM. */
-
-static inline void
-set_memory_partition (tree sym, tree mpt)
-{
-#if defined ENABLE_CHECKING
- if (mpt)
- gcc_assert (TREE_CODE (mpt) == MEMORY_PARTITION_TAG
- && !is_gimple_reg (sym));
-#endif
-
- var_ann (sym)->mpt = mpt;
- if (mpt)
- {
- if (MPT_SYMBOLS (mpt) == NULL)
- MPT_SYMBOLS (mpt) = BITMAP_ALLOC (&alias_bitmap_obstack);
-
- bitmap_set_bit (MPT_SYMBOLS (mpt), DECL_UID (sym));
-
- /* MPT inherits the call-clobbering attributes from SYM. */
- if (is_call_clobbered (sym))
- {
- MTAG_GLOBAL (mpt) = 1;
- mark_call_clobbered (mpt, ESCAPE_IS_GLOBAL);
- }
- }
-}
-
-
-/* Mark variable VAR as being non-addressable. */
-
-static void
-mark_non_addressable (tree var)
-{
- tree mpt;
-
- if (!TREE_ADDRESSABLE (var))
- return;
-
- mpt = memory_partition (var);
-
- clear_call_clobbered (var);
- TREE_ADDRESSABLE (var) = 0;
-
- if (mpt)
- {
- /* Note that it's possible for a symbol to have an associated
- MPT and the MPT have a NULL empty set. During
- init_alias_info, all MPTs get their sets cleared out, but the
- symbols still point to the old MPTs that used to hold them.
- This is done so that compute_memory_partitions can now which
- symbols are losing or changing partitions and mark them for
- renaming. */
- if (MPT_SYMBOLS (mpt))
- bitmap_clear_bit (MPT_SYMBOLS (mpt), DECL_UID (var));
- set_memory_partition (var, NULL_TREE);
- }
-}
-
-
-/* qsort comparison function to sort type/name tags by DECL_UID. */
-
-static int
-sort_tags_by_id (const void *pa, const void *pb)
-{
- const_tree const a = *(const_tree const *)pa;
- const_tree const b = *(const_tree const *)pb;
-
- return DECL_UID (a) - DECL_UID (b);
-}
-
-/* Initialize WORKLIST to contain those memory tags that are marked call
- clobbered. Initialized WORKLIST2 to contain the reasons these
- memory tags escaped. */
-
-static void
-init_transitive_clobber_worklist (VEC (tree, heap) **worklist,
- VEC (int, heap) **worklist2,
- bitmap on_worklist)
-{
- referenced_var_iterator rvi;
- tree curr;
-
- FOR_EACH_REFERENCED_VAR (curr, rvi)
- {
- if (MTAG_P (curr) && is_call_clobbered (curr))
- {
- VEC_safe_push (tree, heap, *worklist, curr);
- VEC_safe_push (int, heap, *worklist2,
- var_ann (curr)->escape_mask);
- bitmap_set_bit (on_worklist, DECL_UID (curr));
- }
- }
-}
-
-/* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if
- ALIAS is not already marked call clobbered, and is a memory
- tag. */
-
-static void
-add_to_worklist (tree alias, VEC (tree, heap) **worklist,
- VEC (int, heap) **worklist2, int reason,
- bitmap on_worklist)
-{
- if (MTAG_P (alias) && !is_call_clobbered (alias)
- && !bitmap_bit_p (on_worklist, DECL_UID (alias)))
- {
- VEC_safe_push (tree, heap, *worklist, alias);
- VEC_safe_push (int, heap, *worklist2, reason);
- bitmap_set_bit (on_worklist, DECL_UID (alias));
- }
-}
-
-/* Mark aliases of TAG as call clobbered, and place any tags on the
- alias list that were not already call clobbered on WORKLIST. */
-
-static void
-mark_aliases_call_clobbered (tree tag, VEC (tree, heap) **worklist,
- VEC (int, heap) **worklist2, bitmap on_worklist)
-{
- bitmap aliases;
- bitmap_iterator bi;
- unsigned int i;
- tree entry;
- var_ann_t ta = var_ann (tag);
-
- if (!MTAG_P (tag))
- return;
- aliases = may_aliases (tag);
- if (!aliases)
- return;
-
- EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
- {
- entry = referenced_var (i);
- /* If you clobber one part of a structure, you
- clobber the entire thing. While this does not make
- the world a particularly nice place, it is necessary
- in order to allow C/C++ tricks that involve
- pointer arithmetic to work. */
- if (!unmodifiable_var_p (entry))
- {
- add_to_worklist (entry, worklist, worklist2, ta->escape_mask,
- on_worklist);
- mark_call_clobbered (entry, ta->escape_mask);
- }
- }
-}
-
-/* Tags containing global vars need to be marked as global.
- Tags containing call clobbered vars need to be marked as call
- clobbered. */
-
-static void
-compute_tag_properties (void)
-{
- referenced_var_iterator rvi;
- tree tag;
- bool changed = true;
- VEC (tree, heap) *taglist = NULL;
-
- FOR_EACH_REFERENCED_VAR (tag, rvi)
- {
- if (!MTAG_P (tag))
- continue;
- VEC_safe_push (tree, heap, taglist, tag);
- }
-
- /* We sort the taglist by DECL_UID, for two reasons.
- 1. To get a sequential ordering to make the bitmap accesses
- faster.
- 2. Because of the way we compute aliases, it's more likely that
- an earlier tag is included in a later tag, and this will reduce
- the number of iterations.
-
- If we had a real tag graph, we would just topo-order it and be
- done with it. */
- qsort (VEC_address (tree, taglist),
- VEC_length (tree, taglist),
- sizeof (tree),
- sort_tags_by_id);
-
- /* Go through each tag not marked as global, and if it aliases
- global vars, mark it global.
-
- If the tag contains call clobbered vars, mark it call
- clobbered.
-
- This loop iterates because tags may appear in the may-aliases
- list of other tags when we group. */
-
- while (changed)
- {
- unsigned int k;
-
- changed = false;
- for (k = 0; VEC_iterate (tree, taglist, k, tag); k++)
- {
- bitmap ma;
- bitmap_iterator bi;
- unsigned int i;
- tree entry;
- bool tagcc = is_call_clobbered (tag);
- bool tagglobal = MTAG_GLOBAL (tag);
-
- if (tagcc && tagglobal)
- continue;
-
- ma = may_aliases (tag);
- if (!ma)
- continue;
-
- EXECUTE_IF_SET_IN_BITMAP (ma, 0, i, bi)
- {
- entry = referenced_var (i);
- /* Call clobbered entries cause the tag to be marked
- call clobbered. */
- if (!tagcc && is_call_clobbered (entry))
- {
- mark_call_clobbered (tag, var_ann (entry)->escape_mask);
- tagcc = true;
- changed = true;
- }
-
- /* Global vars cause the tag to be marked global. */
- if (!tagglobal && is_global_var (entry))
- {
- MTAG_GLOBAL (tag) = true;
- changed = true;
- tagglobal = true;
- }
-
- /* Early exit once both global and cc are set, since the
- loop can't do any more than that. */
- if (tagcc && tagglobal)
- break;
- }
- }
- }
- VEC_free (tree, heap, taglist);
-}
-
-/* Set up the initial variable clobbers, call-uses and globalness.
- When this function completes, only tags whose aliases need to be
- clobbered will be set clobbered. Tags clobbered because they
- contain call clobbered vars are handled in compute_tag_properties. */
-
-static void
-set_initial_properties (struct alias_info *ai)
-{
- unsigned int i;
- referenced_var_iterator rvi;
- tree var;
- tree ptr;
- bool any_pt_anything = false;
- enum escape_type pt_anything_mask = 0;
-
- FOR_EACH_REFERENCED_VAR (var, rvi)
- {
- if (is_global_var (var))
- {
- if (!unmodifiable_var_p (var))
- mark_call_clobbered (var, ESCAPE_IS_GLOBAL);
- }
- else if (TREE_CODE (var) == PARM_DECL
- && gimple_default_def (cfun, var)
- && POINTER_TYPE_P (TREE_TYPE (var)))
- {
- tree def = gimple_default_def (cfun, var);
- get_ptr_info (def)->value_escapes_p = 1;
- get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM;
- }
- }
-
- if (!clobber_what_escaped ())
- {
- any_pt_anything = true;
- pt_anything_mask |= ESCAPE_TO_CALL;
- }
-
- compute_call_used_vars ();
-
- for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
- {
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
- tree tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
-
- /* A pointer that only escapes via a function return does not
- add to the call clobber or call used solution.
- To exclude ESCAPE_TO_PURE_CONST we would need to track
- call used variables separately or compute those properly
- in the operand scanner. */
- if (pi->value_escapes_p
- && pi->escape_mask & ~ESCAPE_TO_RETURN)
- {
- /* If PTR escapes then its associated memory tags and
- pointed-to variables are call-clobbered. */
- if (pi->name_mem_tag)
- mark_call_clobbered (pi->name_mem_tag, pi->escape_mask);
-
- if (tag)
- mark_call_clobbered (tag, pi->escape_mask);
- }
-
- /* If the name tag is call clobbered, so is the symbol tag
- associated with the base VAR_DECL. */
- if (pi->name_mem_tag
- && tag
- && is_call_clobbered (pi->name_mem_tag))
- mark_call_clobbered (tag, pi->escape_mask);
-
- /* Name tags and symbol tags that we don't know where they point
- to, might point to global memory, and thus, are clobbered.
-
- FIXME: This is not quite right. They should only be
- clobbered if value_escapes_p is true, regardless of whether
- they point to global memory or not.
- So removing this code and fixing all the bugs would be nice.
- It is the cause of a bunch of clobbering. */
- if ((pi->pt_global_mem || pi->pt_anything)
- && pi->memory_tag_needed && pi->name_mem_tag)
- {
- mark_call_clobbered (pi->name_mem_tag, ESCAPE_IS_GLOBAL);
- MTAG_GLOBAL (pi->name_mem_tag) = true;
- }
-
- if ((pi->pt_global_mem || pi->pt_anything)
- && pi->memory_tag_needed
- && tag)
- {
- mark_call_clobbered (tag, ESCAPE_IS_GLOBAL);
- MTAG_GLOBAL (tag) = true;
- }
- }
-
- /* If a pt_anything pointer escaped we need to mark all addressable
- variables call clobbered. */
- if (any_pt_anything)
- {
- bitmap_iterator bi;
- unsigned int j;
-
- EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun), 0, j, bi)
- {
- tree var = referenced_var (j);
- if (!unmodifiable_var_p (var))
- mark_call_clobbered (var, pt_anything_mask);
- }
- }
-}
-
-/* Compute which variables need to be marked call clobbered because
- their tag is call clobbered, and which tags need to be marked
- global because they contain global variables. */
-
-static void
-compute_call_clobbered (struct alias_info *ai)
-{
- VEC (tree, heap) *worklist = NULL;
- VEC (int,heap) *worklist2 = NULL;
- bitmap on_worklist;
-
- timevar_push (TV_CALL_CLOBBER);
- on_worklist = BITMAP_ALLOC (NULL);
-
- set_initial_properties (ai);
- init_transitive_clobber_worklist (&worklist, &worklist2, on_worklist);
- while (VEC_length (tree, worklist) != 0)
- {
- tree curr = VEC_pop (tree, worklist);
- int reason = VEC_pop (int, worklist2);
-
- bitmap_clear_bit (on_worklist, DECL_UID (curr));
- mark_call_clobbered (curr, reason);
- mark_aliases_call_clobbered (curr, &worklist, &worklist2, on_worklist);
- }
- VEC_free (tree, heap, worklist);
- VEC_free (int, heap, worklist2);
- BITMAP_FREE (on_worklist);
- compute_tag_properties ();
- timevar_pop (TV_CALL_CLOBBER);
-}
-
-
-/* Dump memory partition information to FILE. */
-
-static void
-dump_memory_partitions (FILE *file)
-{
- unsigned i, npart;
- unsigned long nsyms;
- tree mpt;
-
- fprintf (file, "\nMemory partitions\n\n");
- for (i = 0, npart = 0, nsyms = 0;
- VEC_iterate (tree, gimple_ssa_operands (cfun)->mpt_table, i, mpt);
- i++)
- {
- if (mpt)
- {
- bitmap syms = MPT_SYMBOLS (mpt);
- unsigned long n = (syms) ? bitmap_count_bits (syms) : 0;
-
- fprintf (file, "#%u: ", i);
- print_generic_expr (file, mpt, 0);
- fprintf (file, ": %lu elements: ", n);
- dump_decl_set (file, syms);
- npart++;
- nsyms += n;
- }
- }
-
- fprintf (file, "\n%u memory partitions holding %lu symbols\n", npart, nsyms);
-}
-
-
-/* Dump memory partition information to stderr. */
-
-void
-debug_memory_partitions (void)
-{
- dump_memory_partitions (stderr);
-}
-
-
-/* Return true if memory partitioning is required given the memory
- reference estimates in STATS. */
-
-static inline bool
-need_to_partition_p (struct mem_ref_stats_d *stats)
-{
- long num_vops = stats->num_vuses + stats->num_vdefs;
- long avg_vops = CEIL (num_vops, stats->num_mem_stmts);
- return (num_vops > (long) MAX_ALIASED_VOPS
- && avg_vops > (long) AVG_ALIASED_VOPS);
-}
-
-
-/* Count the actual number of virtual operators in CFUN. Note that
- this is only meaningful after virtual operands have been populated,
- so it should be invoked at the end of compute_may_aliases.
-
- The number of virtual operators are stored in *NUM_VDEFS_P and
- *NUM_VUSES_P, the number of partitioned symbols in
- *NUM_PARTITIONED_P and the number of unpartitioned symbols in
- *NUM_UNPARTITIONED_P.
-
- If any of these pointers is NULL the corresponding count is not
- computed. */
-
-static void
-count_mem_refs (long *num_vuses_p, long *num_vdefs_p,
- long *num_partitioned_p, long *num_unpartitioned_p)
-{
- gimple_stmt_iterator gsi;
- basic_block bb;
- long num_vdefs, num_vuses, num_partitioned, num_unpartitioned;
- referenced_var_iterator rvi;
- tree sym;
-
- num_vuses = num_vdefs = num_partitioned = num_unpartitioned = 0;
-
- if (num_vuses_p || num_vdefs_p)
- FOR_EACH_BB (bb)
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple stmt = gsi_stmt (gsi);
- if (gimple_references_memory_p (stmt))
- {
- num_vuses += NUM_SSA_OPERANDS (stmt, SSA_OP_VUSE);
- num_vdefs += NUM_SSA_OPERANDS (stmt, SSA_OP_VDEF);
- }
- }
-
- if (num_partitioned_p || num_unpartitioned_p)
- FOR_EACH_REFERENCED_VAR (sym, rvi)
- {
- if (is_gimple_reg (sym))
- continue;
-
- if (memory_partition (sym))
- num_partitioned++;
- else
- num_unpartitioned++;
- }
-
- if (num_vdefs_p)
- *num_vdefs_p = num_vdefs;
-
- if (num_vuses_p)
- *num_vuses_p = num_vuses;
-
- if (num_partitioned_p)
- *num_partitioned_p = num_partitioned;
-
- if (num_unpartitioned_p)
- *num_unpartitioned_p = num_unpartitioned;
-}
-
-
-/* The list is sorted by increasing partitioning score (PSCORE).
- This score is computed such that symbols with high scores are
- those that are least likely to be partitioned. Given a symbol
- MP->VAR, PSCORE(S) is the result of the following weighted sum
-
- PSCORE(S) = FW * 64 + FR * 32
- + DW * 16 + DR * 8
- + IW * 4 + IR * 2
- + NO_ALIAS
-
- where
-
- FW Execution frequency of writes to S
- FR Execution frequency of reads from S
- DW Number of direct writes to S
- DR Number of direct reads from S
- IW Number of indirect writes to S
- IR Number of indirect reads from S
- NO_ALIAS State of the NO_ALIAS* flags
-
- The basic idea here is that symbols that are frequently
- written-to in hot paths of the code are the last to be considered
- for partitioning. */
-
-static inline long
-mem_sym_score (mem_sym_stats_t mp)
-{
- return mp->frequency_writes * 64 + mp->frequency_reads * 32
- + mp->num_direct_writes * 16 + mp->num_direct_reads * 8
- + mp->num_indirect_writes * 4 + mp->num_indirect_reads * 2
- + var_ann (mp->var)->noalias_state;
-}
-
-
-/* Dump memory reference stats for function CFUN to FILE. */
-
-void
-dump_mem_ref_stats (FILE *file)
-{
- long actual_num_vuses, actual_num_vdefs;
- long num_partitioned, num_unpartitioned;
- struct mem_ref_stats_d *stats;
-
- stats = gimple_mem_ref_stats (cfun);
-
- count_mem_refs (&actual_num_vuses, &actual_num_vdefs, &num_partitioned,
- &num_unpartitioned);
-
- fprintf (file, "\nMemory reference statistics for %s\n\n",
- lang_hooks.decl_printable_name (current_function_decl, 2));
-
- fprintf (file, "Number of memory statements: %ld\n",
- stats->num_mem_stmts);
- fprintf (file, "Number of call sites: %ld\n",
- stats->num_call_sites);
- fprintf (file, "Number of pure/const call sites: %ld\n",
- stats->num_pure_const_call_sites);
- fprintf (file, "Number of asm sites: %ld\n",
- stats->num_asm_sites);
- fprintf (file, "Estimated number of loads: %ld (%ld/stmt)\n",
- stats->num_vuses,
- (stats->num_mem_stmts)
- ? CEIL (stats->num_vuses, stats->num_mem_stmts)
- : 0);
- fprintf (file, "Actual number of loads: %ld (%ld/stmt)\n",
- actual_num_vuses,
- (stats->num_mem_stmts)
- ? CEIL (actual_num_vuses, stats->num_mem_stmts)
- : 0);
-
- if (actual_num_vuses > stats->num_vuses + (stats->num_vuses / 25))
- fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n");
-
- fprintf (file, "Estimated number of stores: %ld (%ld/stmt)\n",
- stats->num_vdefs,
- (stats->num_mem_stmts)
- ? CEIL (stats->num_vdefs, stats->num_mem_stmts)
- : 0);
- fprintf (file, "Actual number of stores: %ld (%ld/stmt)\n",
- actual_num_vdefs,
- (stats->num_mem_stmts)
- ? CEIL (actual_num_vdefs, stats->num_mem_stmts)
- : 0);
-
- if (actual_num_vdefs > stats->num_vdefs + (stats->num_vdefs / 25))
- fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n");
-
- fprintf (file, "Partitioning thresholds: MAX = %d AVG = %d "
- "(%sNEED TO PARTITION)\n", MAX_ALIASED_VOPS, AVG_ALIASED_VOPS,
- stats->num_mem_stmts && need_to_partition_p (stats) ? "" : "NO ");
- fprintf (file, "Number of partitioned symbols: %ld\n", num_partitioned);
- fprintf (file, "Number of unpartitioned symbols: %ld\n", num_unpartitioned);
-}
-
-
-/* Dump memory reference stats for function FN to stderr. */
-
-void
-debug_mem_ref_stats (void)
-{
- dump_mem_ref_stats (stderr);
-}
-
-
-/* Dump memory reference stats for variable VAR to FILE. */
-
-static void
-dump_mem_sym_stats (FILE *file, tree var)
-{
- mem_sym_stats_t stats = mem_sym_stats (cfun, var);
-
- if (stats == NULL)
- return;
-
- fprintf (file, "read frequency: %6ld, write frequency: %6ld, "
- "direct reads: %3ld, direct writes: %3ld, "
- "indirect reads: %4ld, indirect writes: %4ld, symbol: ",
- stats->frequency_reads, stats->frequency_writes,
- stats->num_direct_reads, stats->num_direct_writes,
- stats->num_indirect_reads, stats->num_indirect_writes);
- print_generic_expr (file, stats->var, 0);
- fprintf (file, ", tags: ");
- dump_decl_set (file, stats->parent_tags);
-}
-
-
-/* Dump memory reference stats for variable VAR to stderr. */
-
-void
-debug_mem_sym_stats (tree var)
-{
- dump_mem_sym_stats (stderr, var);
-}
-
-/* Dump memory reference stats for variable VAR to FILE. For use
- of tree-dfa.c:dump_variable. */
-
-void
-dump_mem_sym_stats_for_var (FILE *file, tree var)
-{
- mem_sym_stats_t stats = mem_sym_stats (cfun, var);
-
- if (stats == NULL)
- return;
-
- fprintf (file, ", score: %ld", mem_sym_score (stats));
- fprintf (file, ", direct reads: %ld", stats->num_direct_reads);
- fprintf (file, ", direct writes: %ld", stats->num_direct_writes);
- fprintf (file, ", indirect reads: %ld", stats->num_indirect_reads);
- fprintf (file, ", indirect writes: %ld", stats->num_indirect_writes);
-}
-
-/* Dump memory reference stats for all memory symbols to FILE. */
-
-static void
-dump_all_mem_sym_stats (FILE *file)
-{
- referenced_var_iterator rvi;
- tree sym;
-
- FOR_EACH_REFERENCED_VAR (sym, rvi)
- {
- if (is_gimple_reg (sym))
- continue;
-
- dump_mem_sym_stats (file, sym);
- }
-}
-
-
-/* Dump memory reference stats for all memory symbols to stderr. */
-
-void
-debug_all_mem_sym_stats (void)
-{
- dump_all_mem_sym_stats (stderr);
-}
-
-
-/* Dump the MP_INFO array to FILE. */
-
-static void
-dump_mp_info (FILE *file, VEC(mem_sym_stats_t,heap) *mp_info)
-{
- unsigned i;
- mem_sym_stats_t mp_p;
-
- for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
- if (!mp_p->partitioned_p)
- dump_mem_sym_stats (file, mp_p->var);
-}
-
-
-/* Dump the MP_INFO array to stderr. */
-
-void
-debug_mp_info (VEC(mem_sym_stats_t,heap) *mp_info)
-{
- dump_mp_info (stderr, mp_info);
-}
-
-
-/* Update memory reference stats for symbol VAR in statement STMT.
- NUM_DIRECT_READS and NUM_DIRECT_WRITES specify the number of times
- that VAR is read/written in STMT (indirect reads/writes are not
- recorded by this function, see compute_memory_partitions). */
-
-void
-update_mem_sym_stats_from_stmt (tree var, gimple stmt, long num_direct_reads,
- long num_direct_writes)
-{
- mem_sym_stats_t stats;
-
- gcc_assert (num_direct_reads >= 0 && num_direct_writes >= 0);
-
- stats = get_mem_sym_stats_for (var);
-
- stats->num_direct_reads += num_direct_reads;
- stats->frequency_reads += ((long) gimple_bb (stmt)->frequency
- * num_direct_reads);
-
- stats->num_direct_writes += num_direct_writes;
- stats->frequency_writes += ((long) gimple_bb (stmt)->frequency
- * num_direct_writes);
-}
-
-
-/* Given two MP_INFO entries MP1 and MP2, return -1 if MP1->VAR should
- be partitioned before MP2->VAR, 0 if they are the same or 1 if
- MP1->VAR should be partitioned after MP2->VAR. */
-
-static inline int
-compare_mp_info_entries (mem_sym_stats_t mp1, mem_sym_stats_t mp2)
-{
- long pscore1 = mem_sym_score (mp1);
- long pscore2 = mem_sym_score (mp2);
-
- if (pscore1 < pscore2)
- return -1;
- else if (pscore1 > pscore2)
- return 1;
- else
- return DECL_UID (mp1->var) - DECL_UID (mp2->var);
-}
-
-
-/* Comparison routine for qsort. The list is sorted by increasing
- partitioning score (PSCORE). This score is computed such that
- symbols with high scores are those that are least likely to be
- partitioned. */
-
-static int
-mp_info_cmp (const void *p, const void *q)
-{
- mem_sym_stats_t e1 = *((const mem_sym_stats_t *) p);
- mem_sym_stats_t e2 = *((const mem_sym_stats_t *) q);
- return compare_mp_info_entries (e1, e2);
-}
-
-
-/* Sort the array of reference counts used to compute memory partitions.
- Elements are sorted in ascending order of execution frequency and
- descending order of virtual operators needed. */
-
-static inline void
-sort_mp_info (VEC(mem_sym_stats_t,heap) *list)
-{
- unsigned num = VEC_length (mem_sym_stats_t, list);
-
- if (num < 2)
- return;
-
- if (num == 2)
- {
- if (compare_mp_info_entries (VEC_index (mem_sym_stats_t, list, 0),
- VEC_index (mem_sym_stats_t, list, 1)) > 0)
- {
- /* Swap elements if they are in the wrong order. */
- mem_sym_stats_t tmp = VEC_index (mem_sym_stats_t, list, 0);
- VEC_replace (mem_sym_stats_t, list, 0,
- VEC_index (mem_sym_stats_t, list, 1));
- VEC_replace (mem_sym_stats_t, list, 1, tmp);
- }
-
- return;
- }
-
- /* There are 3 or more elements, call qsort. */
- qsort (VEC_address (mem_sym_stats_t, list),
- VEC_length (mem_sym_stats_t, list),
- sizeof (mem_sym_stats_t),
- mp_info_cmp);
-}
-
-
-/* Return the memory partition tag (MPT) associated with memory
- symbol SYM. */
-
-static tree
-get_mpt_for (tree sym)
-{
- tree mpt;
-
- /* Don't create a new tag unnecessarily. */
- mpt = memory_partition (sym);
- if (mpt == NULL_TREE)
- {
- mpt = create_tag_raw (MEMORY_PARTITION_TAG, TREE_TYPE (sym), "MPT");
- TREE_ADDRESSABLE (mpt) = 0;
- add_referenced_var (mpt);
- VEC_safe_push (tree, heap, gimple_ssa_operands (cfun)->mpt_table, mpt);
- gcc_assert (MPT_SYMBOLS (mpt) == NULL);
- set_memory_partition (sym, mpt);
- }
-
- return mpt;
-}
-
-
-/* Add MP_P->VAR to a memory partition and return the partition. */
-
-static tree
-find_partition_for (mem_sym_stats_t mp_p)
-{
- unsigned i;
- VEC(tree,heap) *mpt_table;
- tree mpt;
-
- mpt_table = gimple_ssa_operands (cfun)->mpt_table;
- mpt = NULL_TREE;
-
- /* Find an existing partition for MP_P->VAR. */
- for (i = 0; VEC_iterate (tree, mpt_table, i, mpt); i++)
- {
- mem_sym_stats_t mpt_stats;
-
- /* If MPT does not have any symbols yet, use it. */
- if (MPT_SYMBOLS (mpt) == NULL)
- break;
-
- /* Otherwise, see if MPT has common parent tags with MP_P->VAR,
- but avoid grouping clobbered variables with non-clobbered
- variables (otherwise, this tends to creates a single memory
- partition because other call-clobbered variables may have
- common parent tags with non-clobbered ones). */
- mpt_stats = get_mem_sym_stats_for (mpt);
- if (mp_p->parent_tags
- && mpt_stats->parent_tags
- && is_call_clobbered (mpt) == is_call_clobbered (mp_p->var)
- && bitmap_intersect_p (mpt_stats->parent_tags, mp_p->parent_tags))
- break;
-
- /* If no common parent tags are found, see if both MPT and
- MP_P->VAR are call-clobbered. */
- if (is_call_clobbered (mpt) && is_call_clobbered (mp_p->var))
- break;
- }
-
- if (mpt == NULL_TREE)
- mpt = get_mpt_for (mp_p->var);
- else
- set_memory_partition (mp_p->var, mpt);
-
- mp_p->partitioned_p = true;
-
- mark_sym_for_renaming (mp_p->var);
- mark_sym_for_renaming (mpt);
-
- return mpt;
-}
-
-
-/* Rewrite the alias set for TAG to use the newly created partitions.
- If TAG is NULL, rewrite the set of call-clobbered variables.
- NEW_ALIASES is a scratch bitmap to build the new set of aliases for
- TAG. */
-
-static void
-rewrite_alias_set_for (tree tag, bitmap new_aliases)
-{
- bitmap_iterator bi;
- unsigned i;
- tree mpt, sym;
-
- EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, i, bi)
- {
- sym = referenced_var (i);
- mpt = memory_partition (sym);
- if (mpt)
- bitmap_set_bit (new_aliases, DECL_UID (mpt));
- else
- bitmap_set_bit (new_aliases, DECL_UID (sym));
- }
-
- /* Rebuild the may-alias array for TAG. */
- bitmap_copy (MTAG_ALIASES (tag), new_aliases);
-}
-
-
-/* Determine how many virtual operands can be saved by partitioning
- MP_P->VAR into MPT. When a symbol S is thrown inside a partition
- P, every virtual operand that used to reference S will now
- reference P. Whether it reduces the number of virtual operands
- depends on:
-
- 1- Direct references to S are never saved. Instead of the virtual
- operand to S, we will now have a virtual operand to P.
-
- 2- Indirect references to S are reduced only for those memory tags
- holding S that already had other symbols partitioned into P.
- For instance, if a memory tag T has the alias set { a b S c },
- the first time we partition S into P, the alias set will become
- { a b P c }, so no virtual operands will be saved. However, if
- we now partition symbol 'c' into P, then the alias set for T
- will become { a b P }, so we will be saving one virtual operand
- for every indirect reference to 'c'.
-
- 3- Is S is call-clobbered, we save as many virtual operands as
- call/asm sites exist in the code, but only if other
- call-clobbered symbols have been grouped into P. The first
- call-clobbered symbol that we group does not produce any
- savings.
-
- MEM_REF_STATS points to CFUN's memory reference information. */
-
-static void
-estimate_vop_reduction (struct mem_ref_stats_d *mem_ref_stats,
- mem_sym_stats_t mp_p, tree mpt)
-{
- unsigned i;
- bitmap_iterator bi;
- mem_sym_stats_t mpt_stats;
-
- /* We should only get symbols with indirect references here. */
- gcc_assert (mp_p->num_indirect_reads > 0 || mp_p->num_indirect_writes > 0);
-
- /* Note that the only statistics we keep for MPT is the set of
- parent tags to know which memory tags have had alias members
- partitioned, and the indicator has_call_clobbered_vars.
- Reference counts are not important for MPT. */
- mpt_stats = get_mem_sym_stats_for (mpt);
-
- /* Traverse all the parent tags for MP_P->VAR. For every tag T, if
- partition P is already grouping aliases of T, then reduce the
- number of virtual operands by the number of direct references
- to T. */
- if (mp_p->parent_tags)
- {
- if (mpt_stats->parent_tags == NULL)
- mpt_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack);
-
- EXECUTE_IF_SET_IN_BITMAP (mp_p->parent_tags, 0, i, bi)
- {
- if (bitmap_bit_p (mpt_stats->parent_tags, i))
- {
- /* Partition MPT is already partitioning symbols in the
- alias set for TAG. This means that we are now saving
- 1 virtual operand for every direct reference to TAG. */
- tree tag = referenced_var (i);
- mem_sym_stats_t tag_stats = mem_sym_stats (cfun, tag);
- mem_ref_stats->num_vuses -= tag_stats->num_direct_reads;
- mem_ref_stats->num_vdefs -= tag_stats->num_direct_writes;
- }
- else
- {
- /* This is the first symbol in tag I's alias set that is
- being grouped under MPT. We will not save any
- virtual operands this time, but record that MPT is
- grouping a symbol from TAG's alias set so that the
- next time we get the savings. */
- bitmap_set_bit (mpt_stats->parent_tags, i);
- }
- }
- }
-
- /* If MP_P->VAR is call-clobbered, and MPT is already grouping
- call-clobbered symbols, then we will save as many virtual
- operands as asm/call sites there are. */
- if (is_call_clobbered (mp_p->var))
- {
- if (mpt_stats->has_call_clobbered_vars)
- mem_ref_stats->num_vdefs -= mem_ref_stats->num_call_sites
- + mem_ref_stats->num_asm_sites;
- else
- mpt_stats->has_call_clobbered_vars = true;
- }
-}
-
-
-/* Helper for compute_memory_partitions. Transfer reference counts
- from pointers to their pointed-to sets. Counters for pointers were
- computed by update_alias_info. MEM_REF_STATS points to CFUN's
- memory reference information. */
-
-static void
-update_reference_counts (struct mem_ref_stats_d *mem_ref_stats)
-{
- unsigned i;
- bitmap_iterator bi;
- mem_sym_stats_t sym_stats;
-
- for (i = 1; i < num_ssa_names; i++)
- {
- tree ptr;
- struct ptr_info_def *pi;
-
- ptr = ssa_name (i);
- if (ptr
- && POINTER_TYPE_P (TREE_TYPE (ptr))
- && (pi = SSA_NAME_PTR_INFO (ptr)) != NULL
- && pi->memory_tag_needed)
- {
- unsigned j;
- bitmap_iterator bj;
- tree tag;
- mem_sym_stats_t ptr_stats, tag_stats;
-
- /* If PTR has flow-sensitive points-to information, use
- PTR's name tag, otherwise use the symbol tag associated
- with PTR's symbol. */
- if (pi->name_mem_tag)
- tag = pi->name_mem_tag;
- else
- tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
-
- ptr_stats = get_mem_sym_stats_for (ptr);
- tag_stats = get_mem_sym_stats_for (tag);
-
- /* TAG has as many direct references as dereferences we
- found for its parent pointer. */
- tag_stats->num_direct_reads += ptr_stats->num_direct_reads;
- tag_stats->num_direct_writes += ptr_stats->num_direct_writes;
-
- /* All the dereferences of pointer PTR are considered direct
- references to PTR's memory tag (TAG). In turn,
- references to TAG will become virtual operands for every
- symbol in TAG's alias set. So, for every symbol ALIAS in
- TAG's alias set, add as many indirect references to ALIAS
- as direct references there are for TAG. */
- if (MTAG_ALIASES (tag))
- EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, j, bj)
- {
- tree alias = referenced_var (j);
- sym_stats = get_mem_sym_stats_for (alias);
-
- /* All the direct references to TAG are indirect references
- to ALIAS. */
- sym_stats->num_indirect_reads += ptr_stats->num_direct_reads;
- sym_stats->num_indirect_writes += ptr_stats->num_direct_writes;
- sym_stats->frequency_reads += ptr_stats->frequency_reads;
- sym_stats->frequency_writes += ptr_stats->frequency_writes;
-
- /* Indicate that TAG is one of ALIAS's parent tags. */
- if (sym_stats->parent_tags == NULL)
- sym_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack);
- bitmap_set_bit (sym_stats->parent_tags, DECL_UID (tag));
- }
- }
- }
-
- /* Call-clobbered symbols are indirectly written at every
- call/asm site. */
- EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
- {
- tree sym = referenced_var (i);
- sym_stats = get_mem_sym_stats_for (sym);
- sym_stats->num_indirect_writes += mem_ref_stats->num_call_sites
- + mem_ref_stats->num_asm_sites;
- }
-
- /* Addressable symbols are indirectly written at some ASM sites.
- Since only ASM sites that clobber memory actually affect
- addressable symbols, this is an over-estimation. */
- EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun), 0, i, bi)
- {
- tree sym = referenced_var (i);
- sym_stats = get_mem_sym_stats_for (sym);
- sym_stats->num_indirect_writes += mem_ref_stats->num_asm_sites;
- }
-}
-
-
-/* Helper for compute_memory_partitions. Add all memory symbols to
- *MP_INFO_P and compute the initial estimate for the total number of
- virtual operands needed. MEM_REF_STATS points to CFUN's memory
- reference information. On exit, *TAGS_P will contain the list of
- memory tags whose alias set need to be rewritten after
- partitioning. */
-
-static void
-build_mp_info (struct mem_ref_stats_d *mem_ref_stats,
- VEC(mem_sym_stats_t,heap) **mp_info_p,
- VEC(tree,heap) **tags_p)
-{
- tree var;
- referenced_var_iterator rvi;
-
- FOR_EACH_REFERENCED_VAR (var, rvi)
- {
- mem_sym_stats_t sym_stats;
- tree old_mpt;
-
- /* We are only interested in memory symbols other than MPTs. */
- if (is_gimple_reg (var) || TREE_CODE (var) == MEMORY_PARTITION_TAG)
- continue;
-
- /* Collect memory tags into the TAGS array so that we can
- rewrite their alias sets after partitioning. */
- if (MTAG_P (var) && MTAG_ALIASES (var))
- VEC_safe_push (tree, heap, *tags_p, var);
-
- /* Since we are going to re-compute partitions, any symbols that
- used to belong to a partition must be detached from it and
- marked for renaming. */
- if ((old_mpt = memory_partition (var)) != NULL)
- {
- mark_sym_for_renaming (old_mpt);
- set_memory_partition (var, NULL_TREE);
- mark_sym_for_renaming (var);
- }
-
- sym_stats = get_mem_sym_stats_for (var);
-
- /* Add VAR's reference info to MP_INFO. Note that the only
- symbols that make sense to partition are those that have
- indirect references. If a symbol S is always directly
- referenced, partitioning it will not reduce the number of
- virtual operators. The only symbols that are profitable to
- partition are those that belong to alias sets and/or are
- call-clobbered. */
- if (sym_stats->num_indirect_reads > 0
- || sym_stats->num_indirect_writes > 0)
- VEC_safe_push (mem_sym_stats_t, heap, *mp_info_p, sym_stats);
-
- /* Update the number of estimated VOPS. Note that direct
- references to memory tags are always counted as indirect
- references to their alias set members, so if a memory tag has
- aliases, do not count its direct references to avoid double
- accounting. */
- if (!MTAG_P (var) || !MTAG_ALIASES (var))
- {
- mem_ref_stats->num_vuses += sym_stats->num_direct_reads;
- mem_ref_stats->num_vdefs += sym_stats->num_direct_writes;
- }
-
- mem_ref_stats->num_vuses += sym_stats->num_indirect_reads;
- mem_ref_stats->num_vdefs += sym_stats->num_indirect_writes;
- }
-}
-
-
-/* Compute memory partitions. A memory partition (MPT) is an
- arbitrary grouping of memory symbols, such that references to one
- member of the group is considered a reference to all the members of
- the group.
-
- As opposed to alias sets in memory tags, the grouping into
- partitions is completely arbitrary and only done to reduce the
- number of virtual operands. The only rule that needs to be
- observed when creating memory partitions is that given two memory
- partitions MPT.i and MPT.j, they must not contain symbols in
- common.
-
- Memory partitions are used when putting the program into Memory-SSA
- form. In particular, in Memory-SSA PHI nodes are not computed for
- individual memory symbols. They are computed for memory
- partitions. This reduces the amount of PHI nodes in the SSA graph
- at the expense of precision (i.e., it makes unrelated stores affect
- each other).
-
- However, it is possible to increase precision by changing this
- partitioning scheme. For instance, if the partitioning scheme is
- such that get_mpt_for is the identity function (that is,
- get_mpt_for (s) = s), this will result in ultimate precision at the
- expense of huge SSA webs.
-
- At the other extreme, a partitioning scheme that groups all the
- symbols in the same set results in minimal SSA webs and almost
- total loss of precision.
-
- There partitioning heuristic uses three parameters to decide the
- order in which symbols are processed. The list of symbols is
- sorted so that symbols that are more likely to be partitioned are
- near the top of the list:
-
- - Execution frequency. If a memory references is in a frequently
- executed code path, grouping it into a partition may block useful
- transformations and cause sub-optimal code generation. So, the
- partition heuristic tries to avoid grouping symbols with high
- execution frequency scores. Execution frequency is taken
- directly from the basic blocks where every reference is made (see
- update_mem_sym_stats_from_stmt), which in turn uses the
- profile guided machinery, so if the program is compiled with PGO
- enabled, more accurate partitioning decisions will be made.
-
- - Number of references. Symbols with few references in the code,
- are partitioned before symbols with many references.
-
- - NO_ALIAS attributes. Symbols with any of the NO_ALIAS*
- attributes are partitioned after symbols marked MAY_ALIAS.
-
- Once the list is sorted, the partitioning proceeds as follows:
-
- 1- For every symbol S in MP_INFO, create a new memory partition MP,
- if necessary. To avoid memory partitions that contain symbols
- from non-conflicting alias sets, memory partitions are
- associated to the memory tag that holds S in its alias set. So,
- when looking for a memory partition for S, the memory partition
- associated with one of the memory tags holding S is chosen. If
- none exists, a new one is created.
-
- 2- Add S to memory partition MP.
-
- 3- Reduce by 1 the number of VOPS for every memory tag holding S.
-
- 4- If the total number of VOPS is less than MAX_ALIASED_VOPS or the
- average number of VOPS per statement is less than
- AVG_ALIASED_VOPS, stop. Otherwise, go to the next symbol in the
- list. */
-
-static void
-compute_memory_partitions (void)
-{
- tree tag;
- unsigned i;
- mem_sym_stats_t mp_p;
- VEC(mem_sym_stats_t,heap) *mp_info;
- bitmap new_aliases;
- VEC(tree,heap) *tags;
- struct mem_ref_stats_d *mem_ref_stats;
- int prev_max_aliased_vops;
-
- mem_ref_stats = gimple_mem_ref_stats (cfun);
- gcc_assert (mem_ref_stats->num_vuses == 0 && mem_ref_stats->num_vdefs == 0);
-
- if (mem_ref_stats->num_mem_stmts == 0)
- return;
-
- timevar_push (TV_MEMORY_PARTITIONING);
-
- mp_info = NULL;
- tags = NULL;
- prev_max_aliased_vops = MAX_ALIASED_VOPS;
-
- /* Since we clearly cannot lower the number of virtual operators
- below the total number of memory statements in the function, we
- may need to adjust MAX_ALIASED_VOPS beforehand. */
- if (MAX_ALIASED_VOPS < mem_ref_stats->num_mem_stmts)
- MAX_ALIASED_VOPS = mem_ref_stats->num_mem_stmts;
-
- /* Update reference stats for all the pointed-to variables and
- memory tags. */
- update_reference_counts (mem_ref_stats);
-
- /* Add all the memory symbols to MP_INFO. */
- build_mp_info (mem_ref_stats, &mp_info, &tags);
-
- /* No partitions required if we are below the threshold. */
- if (!need_to_partition_p (mem_ref_stats))
- {
- if (dump_file)
- fprintf (dump_file, "\nMemory partitioning NOT NEEDED for %s\n",
- get_name (current_function_decl));
- goto done;
- }
-
- /* Sort the MP_INFO array so that symbols that should be partitioned
- first are near the top of the list. */
- sort_mp_info (mp_info);
-
- if (dump_file)
- {
- fprintf (dump_file, "\nMemory partitioning NEEDED for %s\n\n",
- get_name (current_function_decl));
- fprintf (dump_file, "Memory symbol references before partitioning:\n");
- dump_mp_info (dump_file, mp_info);
- }
-
- /* Create partitions for variables in MP_INFO until we have enough
- to lower the total number of VOPS below MAX_ALIASED_VOPS or if
- the average number of VOPS per statement is below
- AVG_ALIASED_VOPS. */
- for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
- {
- tree mpt;
-
- /* If we are below the threshold, stop. */
- if (!need_to_partition_p (mem_ref_stats))
- break;
-
- mpt = find_partition_for (mp_p);
- estimate_vop_reduction (mem_ref_stats, mp_p, mpt);
- }
-
- /* After partitions have been created, rewrite alias sets to use
- them instead of the original symbols. This way, if the alias set
- was computed as { a b c d e f }, and the subset { b e f } was
- grouped into partition MPT.3, then the new alias set for the tag
- will be { a c d MPT.3 }.
-
- Note that this is not strictly necessary. The operand scanner
- will always check if a symbol belongs to a partition when adding
- virtual operands. However, by reducing the size of the alias
- sets to be scanned, the work needed inside the operand scanner is
- significantly reduced. */
- new_aliases = BITMAP_ALLOC (&alias_bitmap_obstack);
-
- for (i = 0; VEC_iterate (tree, tags, i, tag); i++)
- {
- rewrite_alias_set_for (tag, new_aliases);
- bitmap_clear (new_aliases);
- }
-
- BITMAP_FREE (new_aliases);
-
- if (dump_file)
- {
- fprintf (dump_file, "\nMemory symbol references after partitioning:\n");
- dump_mp_info (dump_file, mp_info);
- }
-
-done:
- /* Free allocated memory. */
- VEC_free (mem_sym_stats_t, heap, mp_info);
- VEC_free (tree, heap, tags);
-
- MAX_ALIASED_VOPS = prev_max_aliased_vops;
-
- timevar_pop (TV_MEMORY_PARTITIONING);
-}
-
-/* Compute may-alias information for every variable referenced in function
- FNDECL.
-
- Alias analysis proceeds in 3 main phases:
-
- 1- Points-to and escape analysis.
-
- This phase walks the use-def chains in the SSA web looking for three
- things:
-
- * Assignments of the form P_i = &VAR
- * Assignments of the form P_i = malloc()
- * Pointers and ADDR_EXPR that escape the current function.
-
- The concept of 'escaping' is the same one used in the Java world. When
- a pointer or an ADDR_EXPR escapes, it means that it has been exposed
- outside of the current function. So, assignment to global variables,
- function arguments and returning a pointer are all escape sites, as are
- conversions between pointers and integers.
-
- This is where we are currently limited. Since not everything is renamed
- into SSA, we lose track of escape properties when a pointer is stashed
- inside a field in a structure, for instance. In those cases, we are
- assuming that the pointer does escape.
-
- We use escape analysis to determine whether a variable is
- call-clobbered. Simply put, if an ADDR_EXPR escapes, then the variable
- is call-clobbered. If a pointer P_i escapes, then all the variables
- pointed-to by P_i (and its memory tag) also escape.
-
- 2- Compute flow-sensitive aliases
-
- We have two classes of memory tags. Memory tags associated with the
- pointed-to data type of the pointers in the program. These tags are
- called "symbol memory tag" (SMT). The other class are those associated
- with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that
- when adding operands for an INDIRECT_REF *P_i, we will first check
- whether P_i has a name tag, if it does we use it, because that will have
- more precise aliasing information. Otherwise, we use the standard symbol
- tag.
-
- In this phase, we go through all the pointers we found in points-to
- analysis and create alias sets for the name memory tags associated with
- each pointer P_i. If P_i escapes, we mark call-clobbered the variables
- it points to and its tag.
-
-
- 3- Compute flow-insensitive aliases
-
- This pass will compare the alias set of every symbol memory tag and
- every addressable variable found in the program. Given a symbol
- memory tag SMT and an addressable variable V. If the alias sets of
- SMT and V conflict (as computed by may_alias_p), then V is marked
- as an alias tag and added to the alias set of SMT.
-
- For instance, consider the following function:
-
- foo (int i)
- {
- int *p, a, b;
-
- if (i > 10)
- p = &a;
- else
- p = &b;
-
- *p = 3;
- a = b + 2;
- return *p;
- }
-
- After aliasing analysis has finished, the symbol memory tag for pointer
- 'p' will have two aliases, namely variables 'a' and 'b'. Every time
- pointer 'p' is dereferenced, we want to mark the operation as a
- potential reference to 'a' and 'b'.
-
- foo (int i)
- {
- int *p, a, b;
-
- if (i_2 > 10)
- p_4 = &a;
- else
- p_6 = &b;
- # p_1 = PHI <p_4(1), p_6(2)>;
-
- # a_7 = VDEF <a_3>;
- # b_8 = VDEF <b_5>;
- *p_1 = 3;
-
- # a_9 = VDEF <a_7>
- # VUSE <b_8>
- a_9 = b_8 + 2;
-
- # VUSE <a_9>;
- # VUSE <b_8>;
- return *p_1;
- }
-
- In certain cases, the list of may aliases for a pointer may grow too
- large. This may cause an explosion in the number of virtual operands
- inserted in the code. Resulting in increased memory consumption and
- compilation time.
-
- When the number of virtual operands needed to represent aliased
- loads and stores grows too large (configurable with option --param
- max-aliased-vops and --param avg-aliased-vops), alias sets are
- grouped to avoid severe compile-time slow downs and memory
- consumption. See compute_memory_partitions. */
-
-unsigned int
-compute_may_aliases (void)
-{
- struct alias_info *ai;
-
- timevar_push (TV_TREE_MAY_ALIAS);
-
- memset (&alias_stats, 0, sizeof (alias_stats));
-
- /* Initialize aliasing information. */
- ai = init_alias_info ();
-
- /* For each pointer P_i, determine the sets of variables that P_i may
- point-to. For every addressable variable V, determine whether the
- 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_sets ();
-
- /* 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 (ai);
-
- /* Collect all pointers and addressable variables, compute alias sets,
- create memory tags for pointers and promote variables whose address is
- not needed anymore. */
- setup_pointers_and_addressables (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);
-
- /* If the program makes no reference to global variables, but it
- contains a mixture of pure and non-pure functions, then we need
- to create use-def and def-def links between these functions to
- avoid invalid transformations on them. */
- maybe_create_global_var ();
-
- /* Compute memory partitions for every memory variable. */
- compute_memory_partitions ();
-
- /* Remove partitions with no symbols. Partitions may end up with an
- empty MPT_SYMBOLS set if a previous round of alias analysis
- needed to partition more symbols. Since we don't need those
- partitions anymore, remove them to free up the space. */
- {
- tree mpt;
- unsigned i;
- VEC(tree,heap) *mpt_table;
-
- mpt_table = gimple_ssa_operands (cfun)->mpt_table;
- i = 0;
- while (i < VEC_length (tree, mpt_table))
- {
- mpt = VEC_index (tree, mpt_table, i);
- if (MPT_SYMBOLS (mpt) == NULL)
- VEC_unordered_remove (tree, mpt_table, i);
- else
- i++;
- }
- }
-
- /* Populate all virtual operands and newly promoted register operands. */
- {
- gimple_stmt_iterator gsi;
- basic_block bb;
- FOR_EACH_BB (bb)
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- update_stmt_if_modified (gsi_stmt (gsi));
- }
-
- /* Debugging dumps. */
- if (dump_file)
- {
- dump_mem_ref_stats (dump_file);
- dump_alias_info (dump_file);
- dump_points_to_info (dump_file);
-
- if (dump_flags & TDF_STATS)
- dump_alias_stats (dump_file);
-
- if (dump_flags & TDF_DETAILS)
- dump_referenced_vars (dump_file);
- }
-
- /* Deallocate memory used by aliasing data structures. */
- delete_alias_info (ai);
-
- if (need_ssa_update_p ())
- update_ssa (TODO_update_ssa);
-
- timevar_pop (TV_TREE_MAY_ALIAS);
-
- return 0;
-}
-
-/* Data structure used to count the number of dereferences to PTR
- inside an expression. */
-struct count_ptr_d
-{
- tree ptr;
- unsigned num_stores;
- unsigned num_loads;
-};
-
-
-/* Helper for count_uses_and_derefs. Called by walk_tree to look for
- (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */
-
-static tree
-count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
-{
- struct walk_stmt_info *wi_p = (struct walk_stmt_info *) data;
- struct count_ptr_d *count_p = (struct count_ptr_d *) wi_p->info;
-
- /* Do not walk inside ADDR_EXPR nodes. In the expression &ptr->fld,
- pointer 'ptr' is *not* dereferenced, it is simply used to compute
- the address of 'fld' as 'ptr + offsetof(fld)'. */
- if (TREE_CODE (*tp) == ADDR_EXPR)
- {
- *walk_subtrees = 0;
- return NULL_TREE;
- }
-
- if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
- {
- if (wi_p->is_lhs)
- count_p->num_stores++;
- else
- count_p->num_loads++;
- }
-
- return NULL_TREE;
-}
-
-
-/* Count the number of direct and indirect uses for pointer PTR in
- statement STMT. The number of direct uses is stored in
- *NUM_USES_P. Indirect references are counted separately depending
- on whether they are store or load operations. The counts are
- stored in *NUM_STORES_P and *NUM_LOADS_P. */
-
-void
-count_uses_and_derefs (tree ptr, gimple stmt, unsigned *num_uses_p,
- unsigned *num_loads_p, unsigned *num_stores_p)
-{
- ssa_op_iter i;
- tree use;
-
- *num_uses_p = 0;
- *num_loads_p = 0;
- *num_stores_p = 0;
-
- /* Find out the total number of uses of PTR in STMT. */
- FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
- if (use == ptr)
- (*num_uses_p)++;
-
- /* Now count the number of indirect references to PTR. This is
- truly awful, but we don't have much choice. There are no parent
- pointers inside INDIRECT_REFs, so an expression like
- '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
- find all the indirect and direct uses of x_1 inside. The only
- shortcut we can take is the fact that GIMPLE only allows
- INDIRECT_REFs inside the expressions below. */
- if (is_gimple_assign (stmt)
- || gimple_code (stmt) == GIMPLE_RETURN
- || gimple_code (stmt) == GIMPLE_ASM
- || is_gimple_call (stmt))
- {
- struct walk_stmt_info wi;
- struct count_ptr_d count;
-
- count.ptr = ptr;
- count.num_stores = 0;
- count.num_loads = 0;
-
- memset (&wi, 0, sizeof (wi));
- wi.info = &count;
- walk_gimple_op (stmt, count_ptr_derefs, &wi);
-
- *num_stores_p = count.num_stores;
- *num_loads_p = count.num_loads;
- }
-
- gcc_assert (*num_uses_p >= *num_loads_p + *num_stores_p);
-}
-
-/* Remove memory references stats for function FN. */
-
-void
-delete_mem_ref_stats (struct function *fn)
-{
- if (gimple_mem_ref_stats (fn)->mem_sym_stats)
- {
- free_alloc_pool (mem_sym_stats_pool);
- pointer_map_destroy (gimple_mem_ref_stats (fn)->mem_sym_stats);
- }
- gimple_mem_ref_stats (fn)->mem_sym_stats = NULL;
-}
-
-
-/* Initialize memory reference stats. */
-
-static void
-init_mem_ref_stats (void)
-{
- struct mem_ref_stats_d *mem_ref_stats = gimple_mem_ref_stats (cfun);
-
- mem_sym_stats_pool = create_alloc_pool ("Mem sym stats",
- sizeof (struct mem_sym_stats_d),
- 100);
- memset (mem_ref_stats, 0, sizeof (struct mem_ref_stats_d));
- mem_ref_stats->mem_sym_stats = pointer_map_create ();
-}
-
-
-/* Helper for init_alias_info. Reset existing aliasing information. */
-
-static void
-reset_alias_info (void)
-{
- referenced_var_iterator rvi;
- tree var;
- unsigned i;
- bitmap active_nmts, all_nmts;
-
- /* Clear the set of addressable variables. We do not need to clear
- the TREE_ADDRESSABLE bit on every symbol because we are going to
- re-compute addressability here. */
- bitmap_clear (gimple_addressable_vars (cfun));
-
- active_nmts = BITMAP_ALLOC (&alias_bitmap_obstack);
- all_nmts = BITMAP_ALLOC (&alias_bitmap_obstack);
-
- /* Clear flow-insensitive alias information from each symbol. */
- FOR_EACH_REFERENCED_VAR (var, rvi)
- {
- if (is_gimple_reg (var))
- continue;
-
- if (MTAG_P (var))
- MTAG_ALIASES (var) = NULL;
-
- /* Memory partition information will be computed from scratch. */
- if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
- MPT_SYMBOLS (var) = NULL;
-
- /* Collect all the name tags to determine if we have any
- orphaned that need to be removed from the IL. A name tag
- will be orphaned if it is not associated with any active SSA
- name. */
- if (TREE_CODE (var) == NAME_MEMORY_TAG)
- bitmap_set_bit (all_nmts, DECL_UID (var));
-
- /* Since we are about to re-discover call-clobbered
- variables, clear the call-clobbered flag. */
- clear_call_clobbered (var);
- }
-
- /* There should be no call-clobbered variable left. */
- gcc_assert (bitmap_empty_p (gimple_call_clobbered_vars (cfun)));
-
- /* Clear the call-used variables. */
- bitmap_clear (gimple_call_used_vars (cfun));
-
- /* Clear flow-sensitive points-to information from each SSA name. */
- for (i = 1; i < num_ssa_names; i++)
- {
- tree name = ssa_name (i);
-
- if (!name || !POINTER_TYPE_P (TREE_TYPE (name)))
- continue;
-
- if (SSA_NAME_PTR_INFO (name))
- {
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
-
- /* Clear all the flags but keep the name tag to
- avoid creating new temporaries unnecessarily. If
- this pointer is found to point to a subset or
- superset of its former points-to set, then a new
- tag will need to be created in create_name_tags. */
- pi->pt_anything = 0;
- pi->pt_null = 0;
- pi->value_escapes_p = 0;
- pi->memory_tag_needed = 0;
- pi->is_dereferenced = 0;
- if (pi->pt_vars)
- bitmap_clear (pi->pt_vars);
-
- /* Add NAME's name tag to the set of active tags. */
- if (pi->name_mem_tag)
- bitmap_set_bit (active_nmts, DECL_UID (pi->name_mem_tag));
- }
- }
-
- /* Name memory tags that are no longer associated with an SSA name
- are considered stale and should be removed from the IL. All the
- name tags that are in the set ALL_NMTS but not in ACTIVE_NMTS are
- considered stale and marked for renaming. */
- bitmap_and_compl_into (all_nmts, active_nmts);
- mark_set_for_renaming (all_nmts);
-
- BITMAP_FREE (all_nmts);
- BITMAP_FREE (active_nmts);
-}
-
-
-/* Initialize the data structures used for alias analysis. */
-
-static struct alias_info *
-init_alias_info (void)
-{
- struct alias_info *ai;
- referenced_var_iterator rvi;
- tree var;
- static bool alias_bitmap_obstack_initialized;
-
- ai = XCNEW (struct alias_info);
- ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
- sbitmap_zero (ai->ssa_names_visited);
- ai->processed_ptrs = VEC_alloc (tree, heap, 50);
- ai->dereferenced_ptrs = pointer_set_create ();
-
- /* Clear out all memory reference stats. */
- init_mem_ref_stats ();
-
- /* If aliases have been computed before, clear existing information. */
- if (gimple_aliases_computed_p (cfun))
- reset_alias_info ();
- else
- {
- /* If this is the first time we compute aliasing information,
- every non-register symbol will need to be put into SSA form
- (the initial SSA form only operates on GIMPLE registers). */
- FOR_EACH_REFERENCED_VAR (var, rvi)
- if (!is_gimple_reg (var))
- mark_sym_for_renaming (var);
- }
-
- /* Next time, we will need to reset alias information. */
- cfun->gimple_df->aliases_computed_p = true;
- if (alias_bitmap_obstack_initialized)
- bitmap_obstack_release (&alias_bitmap_obstack);
- bitmap_obstack_initialize (&alias_bitmap_obstack);
- alias_bitmap_obstack_initialized = true;
-
- return ai;
-}
-
-
-/* Deallocate memory used by alias analysis. */
-
-static void
-delete_alias_info (struct alias_info *ai)
-{
- size_t i;
-
- sbitmap_free (ai->ssa_names_visited);
-
- VEC_free (tree, heap, ai->processed_ptrs);
-
- for (i = 0; i < ai->num_addressable_vars; i++)
- free (ai->addressable_vars[i]);
- free (ai->addressable_vars);
-
- for (i = 0; i < ai->num_pointers; i++)
- free (ai->pointers[i]);
- free (ai->pointers);
-
- pointer_set_destroy (ai->dereferenced_ptrs);
- free (ai);
-
- delete_mem_ref_stats (cfun);
- delete_points_to_sets ();
-}
-
-
-/* Used for hashing to identify pointer infos with identical
- pt_vars bitmaps. */
-
-static int
-eq_ptr_info (const void *p1, const void *p2)
-{
- const struct ptr_info_def *n1 = (const struct ptr_info_def *) p1;
- const struct ptr_info_def *n2 = (const struct ptr_info_def *) p2;
- return bitmap_equal_p (n1->pt_vars, n2->pt_vars);
-}
-
-static hashval_t
-ptr_info_hash (const void *p)
-{
- const struct ptr_info_def *n = (const struct ptr_info_def *) p;
- return bitmap_hash (n->pt_vars);
-}
-
-
-/* Create name tags for all the pointers that have been dereferenced.
- We only create a name tag for a pointer P if P is found to point to
- a set of variables (so that we can alias them to *P) or if it is
- the result of a call to malloc (which means that P cannot point to
- anything else nor alias any other variable).
-
- If two pointers P and Q point to the same set of variables, they
- are assigned the same name tag. */
-
-static void
-create_name_tags (void)
-{
- size_t i;
- VEC (tree, heap) *with_ptvars = NULL;
- tree ptr;
- htab_t ptr_hash;
-
- /* Collect the list of pointers with a non-empty points to set. */
- for (i = 1; i < num_ssa_names; i++)
- {
- tree ptr = ssa_name (i);
- struct ptr_info_def *pi;
-
- if (!ptr
- || !POINTER_TYPE_P (TREE_TYPE (ptr))
- || !SSA_NAME_PTR_INFO (ptr))
- continue;
-
- pi = SSA_NAME_PTR_INFO (ptr);
-
- if (pi->pt_anything || !pi->memory_tag_needed)
- {
- /* No name tags for pointers that have not been
- dereferenced or point to an arbitrary location. */
- pi->name_mem_tag = NULL_TREE;
- continue;
- }
-
- /* Set pt_anything on the pointers without pt_vars filled in so
- that they are assigned a symbol tag. */
- if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
- VEC_safe_push (tree, heap, with_ptvars, ptr);
- else
- set_pt_anything (ptr);
- }
-
- /* If we didn't find any pointers with pt_vars set, we're done. */
- if (!with_ptvars)
- return;
-
- ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL);
-
- /* Now go through the pointers with pt_vars, and find a name tag
- with the same pt_vars as this pointer, or create one if one
- doesn't exist. */
- for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++)
- {
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
- tree old_name_tag = pi->name_mem_tag;
- struct ptr_info_def **slot;
-
- /* If PTR points to a set of variables, check if we don't
- have another pointer Q with the same points-to set before
- creating a tag. If so, use Q's tag instead of creating a
- new one.
-
- This is important for not creating unnecessary symbols
- and also for copy propagation. If we ever need to
- propagate PTR into Q or vice-versa, we would run into
- problems if they both had different name tags because
- they would have different SSA version numbers (which
- would force us to take the name tags in and out of SSA). */
- slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT);
- if (*slot)
- pi->name_mem_tag = (*slot)->name_mem_tag;
- else
- {
- *slot = pi;
-
- /* If we didn't find a pointer with the same points-to set
- as PTR, create a new name tag if needed. */
- if (pi->name_mem_tag == NULL_TREE)
- pi->name_mem_tag = get_nmt_for (ptr);
- }
-
- /* If the new name tag computed for PTR is different than
- the old name tag that it used to have, then the old tag
- needs to be removed from the IL, so we mark it for
- renaming. */
- if (old_name_tag && old_name_tag != pi->name_mem_tag)
- mark_sym_for_renaming (old_name_tag);
-
- /* Inherit volatility from the pointed-to type. */
- TREE_THIS_VOLATILE (pi->name_mem_tag)
- |= TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
-
- /* Mark the new name tag for renaming. */
- mark_sym_for_renaming (pi->name_mem_tag);
- }
-
- htab_delete (ptr_hash);
-
- VEC_free (tree, heap, with_ptvars);
-}
-
-
-/* Union the alias set SET into the may-aliases for TAG. */
-
-static void
-union_alias_set_into (tree tag, bitmap set)
-{
- bitmap ma = MTAG_ALIASES (tag);
-
- if (bitmap_empty_p (set))
- return;
-
- if (!ma)
- ma = MTAG_ALIASES (tag) = BITMAP_ALLOC (&alias_bitmap_obstack);
- bitmap_ior_into (ma, set);
-}
-
-
-/* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
- the name memory tag (NMT) associated with P_i. If P_i escapes, then its
- name tag and the variables it points-to are call-clobbered. Finally, if
- P_i escapes and we could not determine where it points to, then all the
- variables in the same alias set as *P_i are marked call-clobbered. This
- is necessary because we must assume that P_i may take the address of any
- variable in the same alias set. */
-
-static void
-compute_flow_sensitive_aliasing (struct alias_info *ai)
-{
- size_t i;
- tree ptr;
-
- timevar_push (TV_FLOW_SENSITIVE);
-
- for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
- {
- if (!find_what_p_points_to (ptr))
- set_pt_anything (ptr);
- }
-
- create_name_tags ();
-
- for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
- {
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
-
- /* Set up aliasing information for PTR's name memory tag (if it has
- one). Note that only pointers that have been dereferenced will
- have a name memory tag. */
- if (pi->name_mem_tag && pi->pt_vars)
- {
- if (!bitmap_empty_p (pi->pt_vars))
- union_alias_set_into (pi->name_mem_tag, pi->pt_vars);
- }
- }
- timevar_pop (TV_FLOW_SENSITIVE);
-}
-
-
-/* Return TRUE if at least one symbol in TAG2's alias set is also
- present in TAG1's alias set. */
-
-static bool
-have_common_aliases_p (bitmap tag1aliases, bitmap tag2aliases)
-{
+/* Broad overview of how alias analysis on gimple works:
- /* This is the old behavior of have_common_aliases_p, which is to
- return false if both sets are empty, or one set is and the other
- isn't. */
- if (tag1aliases == NULL || tag2aliases == NULL)
- return false;
-
- return bitmap_intersect_p (tag1aliases, tag2aliases);
-}
-
-/* Compute type-based alias sets. Traverse all the pointers and
- addressable variables found in setup_pointers_and_addressables.
-
- For every pointer P in AI->POINTERS and addressable variable V in
- AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's symbol
- memory tag (SMT) if their alias sets conflict. V is then marked as
- an aliased symbol so that the operand scanner knows that statements
- containing V have aliased operands. */
-
-static void
-compute_flow_insensitive_aliasing (struct alias_info *ai)
-{
- referenced_var_iterator rvi;
- tree var;
- size_t i;
-
- timevar_push (TV_FLOW_INSENSITIVE);
- /* For every pointer P, determine which addressable variables may alias
- with P's symbol memory tag. */
- for (i = 0; i < ai->num_pointers; i++)
- {
- size_t j;
- struct alias_map_d *p_map = ai->pointers[i];
- tree tag = symbol_mem_tag (p_map->var);
- tree var;
-
- for (j = 0; j < ai->num_addressable_vars; j++)
- {
- struct alias_map_d *v_map;
- var_ann_t v_ann;
-
- v_map = ai->addressable_vars[j];
- var = v_map->var;
- v_ann = var_ann (var);
-
- /* We used to skip variables that have never been written to
- if the memory tag has been never written to directly (or
- either of them were call clobbered). This is not enough
- though, as this misses writes through the tags aliases.
- So, for correctness we need to include any aliased
- variable here. */
-
- if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false))
- {
- /* Add VAR to TAG's may-aliases set. */
- add_may_alias (tag, var);
- }
- }
- }
-
- /* Since this analysis is based exclusively on symbols, it fails to
- handle cases where two pointers P and Q have different memory
- tags with conflicting alias set numbers but no aliased symbols in
- common.
-
- For example, suppose that we have two memory tags SMT.1 and SMT.2
- such that
-
- may-aliases (SMT.1) = { a }
- may-aliases (SMT.2) = { b }
-
- and the alias set number of SMT.1 conflicts with that of SMT.2.
- Since they don't have symbols in common, loads and stores from
- SMT.1 and SMT.2 will seem independent of each other, which will
- lead to the optimizers making invalid transformations (see
- testsuite/gcc.c-torture/execute/pr15262-[12].c).
-
- To avoid this problem, we do a final traversal of AI->POINTERS
- looking for pairs of pointers that have no aliased symbols in
- common and yet have conflicting alias set numbers. */
- for (i = 0; i < ai->num_pointers; i++)
- {
- size_t j;
- struct alias_map_d *p_map1 = ai->pointers[i];
- tree tag1 = symbol_mem_tag (p_map1->var);
- bitmap may_aliases1 = MTAG_ALIASES (tag1);
-
- for (j = 0; j < ai->num_pointers; j++)
- {
- struct alias_map_d *p_map2 = ai->pointers[j];
- tree tag2 = symbol_mem_tag (p_map2->var);
- bitmap may_aliases2 = may_aliases (tag2);
-
- /* By convention tags don't alias themselves. */
- if (tag1 == tag2)
- continue;
-
- /* If the pointers may not point to each other, do nothing. */
- if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
- continue;
-
- /* The two pointers may alias each other. If they already have
- symbols in common, do nothing. */
- if (have_common_aliases_p (may_aliases1, may_aliases2))
- continue;
-
- add_may_alias (tag1, tag2);
- }
- }
-
- /* We have to add all HEAP variables to all SMTs aliases bitmaps.
- As we don't know which effective type the HEAP will have we cannot
- do better here and we need the conflicts with obfuscated pointers
- (a simple (*(int[n] *)ptr)[i] will do, with ptr from a VLA array
- allocation). */
- for (i = 0; i < ai->num_pointers; i++)
- {
- struct alias_map_d *p_map = ai->pointers[i];
- tree tag = symbol_mem_tag (p_map->var);
-
- FOR_EACH_REFERENCED_VAR (var, rvi)
- {
- if (var_ann (var)->is_heapvar)
- add_may_alias (tag, var);
- }
- }
-
- timevar_pop (TV_FLOW_INSENSITIVE);
-}
-
-
-/* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS. */
-
-static void
-create_alias_map_for (tree var, struct alias_info *ai)
-{
- struct alias_map_d *alias_map;
- alias_map = XCNEW (struct alias_map_d);
- alias_map->var = var;
- alias_map->set = get_alias_set (var);
- ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
-}
-
-
-/* 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_1 (gimple stmt, struct alias_info *ai)
-{
- bitmap addr_taken;
- use_operand_p use_p;
- ssa_op_iter iter;
- bool stmt_dereferences_ptr_p;
- enum escape_type stmt_escape_type = is_escape_site (stmt);
- struct mem_ref_stats_d *mem_ref_stats = gimple_mem_ref_stats (cfun);
-
- stmt_dereferences_ptr_p = false;
-
- if (stmt_escape_type == ESCAPE_TO_CALL
- || stmt_escape_type == ESCAPE_TO_PURE_CONST)
- {
- mem_ref_stats->num_call_sites++;
- if (stmt_escape_type == ESCAPE_TO_PURE_CONST)
- mem_ref_stats->num_pure_const_call_sites++;
- }
- else if (stmt_escape_type == ESCAPE_TO_ASM)
- mem_ref_stats->num_asm_sites++;
-
- /* Mark all the variables whose address are taken by the statement. */
- addr_taken = gimple_addresses_taken (stmt);
- if (addr_taken)
- bitmap_ior_into (gimple_addressable_vars (cfun), addr_taken);
-
- /* If we have a call or an assignment, see if the lhs contains
- a local decl that requires not to be a gimple register. */
- if (gimple_code (stmt) == GIMPLE_ASSIGN
- || gimple_code (stmt) == GIMPLE_CALL)
- {
- tree lhs = gimple_get_lhs (stmt);
- /* A plain decl does not need it set. */
- if (lhs && handled_component_p (lhs))
- {
- tree var = get_base_address (lhs);
- if (DECL_P (var)
- /* We are not going to mess with RESULT_DECL anyway. */
- && TREE_CODE (var) != RESULT_DECL
- && is_gimple_reg_type (TREE_TYPE (var)))
- bitmap_set_bit (gimple_addressable_vars (cfun), DECL_UID (var));
- }
- }
-
- /* Process each operand use. 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;
- unsigned num_uses, num_loads, num_stores;
-
- 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)
- {
- bitmap addressable_vars = gimple_addressable_vars (cfun);
-
- gcc_assert (gimple_code (stmt) == GIMPLE_PHI);
- gcc_assert (addressable_vars);
-
- /* 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 (they may occur in PHI node arguments). */
- if (TREE_CODE (op) != SSA_NAME)
- continue;
-
- var = SSA_NAME_VAR (op);
- v_ann = var_ann (var);
-
- /* The base variable of an SSA name must be a GIMPLE register, and thus
- it cannot be aliased. */
- gcc_assert (!may_be_aliased (var));
+ Statements clobbering or using memory are linked through the
+ virtual operand factored use-def chain. The virtual operand
+ is unique per function, its symbol is accessible via gimple_vop (cfun).
+ Virtual operands are used for efficiently walking memory statements
+ in the gimple IL and are useful for things like value-numbering as
+ a generation count for memory references.
- /* 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));
- VEC_safe_push (tree, heap, 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 (gimple_code (stmt) == GIMPLE_PHI)
- continue;
+ SSA_NAME pointers may have associated points-to information
+ accessible via the SSA_NAME_PTR_INFO macro. Flow-insensitive
+ points-to information is (re-)computed by the TODO_rebuild_alias
+ pass manager todo. Points-to information is also used for more
+ precise tracking of call-clobbered and call-used variables and
+ related disambiguations.
- /* 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_loads, &num_stores);
-
- /* For directly dereferenced pointers we can apply
- TBAA-pruning to their points-to set. We may not count the
- implicit dereferences &PTR->FLD here. */
- if (num_loads + num_stores > 0)
- pi->is_dereferenced = 1;
-
- /* Handle a corner case involving address expressions of the
- form '&PTR->FLD'. The problem with these expressions is that
- they do not represent a dereference of PTR. However, if some
- other transformation propagates them into an INDIRECT_REF
- expression, we end up with '*(&PTR->FLD)' which is folded
- into 'PTR->FLD'.
-
- So, if the original code had no other dereferences of PTR,
- the aliaser will not create memory tags for it, and when
- &PTR->FLD gets propagated to INDIRECT_REF expressions, the
- memory operations will receive no VDEF/VUSE operands.
-
- One solution would be to have count_uses_and_derefs consider
- &PTR->FLD a dereference of PTR. But that is wrong, since it
- is not really a dereference but an offset calculation.
-
- What we do here is to recognize these special ADDR_EXPR
- nodes. Since these expressions are never GIMPLE values (they
- are not GIMPLE invariants), they can only appear on the RHS
- of an assignment and their base address is always an
- INDIRECT_REF expression. */
- if (is_gimple_assign (stmt)
- && gimple_assign_rhs_code (stmt) == ADDR_EXPR
- && !is_gimple_val (gimple_assign_rhs1 (stmt)))
- {
- /* If the RHS if of the form &PTR->FLD and PTR == OP, then
- this represents a potential dereference of PTR. */
- tree rhs = gimple_assign_rhs1 (stmt);
- tree base = get_base_address (TREE_OPERAND (rhs, 0));
- if (TREE_CODE (base) == INDIRECT_REF
- && TREE_OPERAND (base, 0) == op)
- num_loads++;
- }
+ This file contains functions for disambiguating memory references,
+ the so called alias-oracle and tools for walking of the gimple IL.
- if (num_loads + num_stores > 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->memory_tag_needed = 1;
+ The main alias-oracle entry-points are
- /* ??? For always executed direct dereferences we can
- apply TBAA-pruning to their escape set. */
+ bool stmt_may_clobber_ref_p (gimple, tree)
- /* Mark OP as being dereferenced. */
- pointer_set_insert (ai->dereferenced_ptrs, var);
+ This function queries if a statement may invalidate (parts of)
+ the memory designated by the reference tree argument.
- /* Update the frequency estimate for all the dereferences of
- pointer OP. */
- update_mem_sym_stats_from_stmt (op, stmt, num_loads, num_stores);
+ bool ref_maybe_used_by_stmt_p (gimple, tree)
- /* Indicate that STMT contains pointer dereferences. */
- stmt_dereferences_ptr_p = true;
- }
+ This function queries if a statement may need (parts of) the
+ memory designated by the reference tree argument.
- if (stmt_escape_type != NO_ESCAPE && num_loads + num_stores < 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;
- pi->escape_mask |= stmt_escape_type;
-
- /* If the statement makes a function call, assume
- that pointer OP will be dereferenced in a store
- operation inside the called function. */
- if (is_gimple_call (stmt)
- || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
- {
- pointer_set_insert (ai->dereferenced_ptrs, var);
- pi->memory_tag_needed = 1;
- }
- }
- }
+ There are variants of these functions that only handle the call
+ part of a statement, call_may_clobber_ref_p and ref_maybe_used_by_call_p.
+ Note that these do not disambiguate against a possible call lhs.
- if (gimple_code (stmt) == GIMPLE_PHI)
- return;
+ bool refs_may_alias_p (tree, tree)
- /* Mark stored variables in STMT as being written to and update the
- memory reference stats for all memory symbols referenced by STMT. */
- if (gimple_references_memory_p (stmt))
- {
- unsigned i;
- bitmap_iterator bi;
-
- mem_ref_stats->num_mem_stmts++;
-
- /* Notice that we only update memory reference stats for symbols
- loaded and stored by the statement if the statement does not
- contain pointer dereferences and it is not a call/asm site.
- This is to avoid double accounting problems when creating
- memory partitions. After computing points-to information,
- pointer dereference statistics are used to update the
- reference stats of the pointed-to variables, so here we
- should only update direct references to symbols.
-
- Indirect references are not updated here for two reasons: (1)
- The first time we compute alias information, the sets
- LOADED/STORED are empty for pointer dereferences, (2) After
- partitioning, LOADED/STORED may have references to
- partitions, not the original pointed-to variables. So, if we
- always counted LOADED/STORED here and during partitioning, we
- would count many symbols more than once.
-
- This does cause some imprecision when a statement has a
- combination of direct symbol references and pointer
- dereferences (e.g., MEMORY_VAR = *PTR) or if a call site has
- memory symbols in its argument list, but these cases do not
- occur so frequently as to constitute a serious problem. */
- if (!stmt_dereferences_ptr_p
- && stmt_escape_type != ESCAPE_TO_CALL
- && stmt_escape_type != ESCAPE_TO_PURE_CONST
- && stmt_escape_type != ESCAPE_TO_ASM)
- {
- if (gimple_stored_syms (stmt))
- EXECUTE_IF_SET_IN_BITMAP (gimple_stored_syms (stmt), 0, i, bi)
- update_mem_sym_stats_from_stmt (referenced_var (i), stmt, 0, 1);
+ This function tries to disambiguate two reference trees.
- if (gimple_loaded_syms (stmt))
- EXECUTE_IF_SET_IN_BITMAP (gimple_loaded_syms (stmt), 0, i, bi)
- update_mem_sym_stats_from_stmt (referenced_var (i), stmt, 1, 0);
- }
- }
-}
+ bool ptr_deref_may_alias_global_p (tree)
-/* Update various related attributes like escaped addresses,
- pointer dereferences for loads and stores. This is used
- when creating name tags and alias sets. */
+ This function queries if dereferencing a pointer variable may
+ alias global memory.
-static void
-update_alias_info (struct alias_info *ai)
-{
- basic_block bb;
+ More low-level disambiguators are available and documented in
+ this file. Low-level disambiguators dealing with points-to
+ information are in tree-ssa-structalias.c. */
- FOR_EACH_BB (bb)
- {
- gimple_stmt_iterator gsi;
- gimple phi;
- for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- phi = gsi_stmt (gsi);
- if (is_gimple_reg (PHI_RESULT (phi)))
- update_alias_info_1 (phi, ai);
- }
+/* Query statistics for the different low-level disambiguators.
+ A high-level query may trigger multiple of them. */
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- update_alias_info_1 (gsi_stmt (gsi), ai);
- }
-}
+static struct {
+ unsigned HOST_WIDE_INT refs_may_alias_p_may_alias;
+ unsigned HOST_WIDE_INT refs_may_alias_p_no_alias;
+ unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_may_alias;
+ unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_no_alias;
+ unsigned HOST_WIDE_INT call_may_clobber_ref_p_may_alias;
+ unsigned HOST_WIDE_INT call_may_clobber_ref_p_no_alias;
+} alias_stats;
-/* Create memory tags for all the dereferenced pointers and build the
- ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias
- sets. Based on the address escape and points-to information collected
- earlier, this pass will also clear the TREE_ADDRESSABLE flag from those
- variables whose address is not needed anymore. */
+void
+dump_alias_stats (FILE *s)
+{
+ fprintf (s, "\nAlias oracle query stats:\n");
+ fprintf (s, " refs_may_alias_p: "
+ HOST_WIDE_INT_PRINT_DEC" disambiguations, "
+ HOST_WIDE_INT_PRINT_DEC" queries\n",
+ alias_stats.refs_may_alias_p_no_alias,
+ alias_stats.refs_may_alias_p_no_alias
+ + alias_stats.refs_may_alias_p_may_alias);
+ fprintf (s, " ref_maybe_used_by_call_p: "
+ HOST_WIDE_INT_PRINT_DEC" disambiguations, "
+ HOST_WIDE_INT_PRINT_DEC" queries\n",
+ alias_stats.ref_maybe_used_by_call_p_no_alias,
+ alias_stats.refs_may_alias_p_no_alias
+ + alias_stats.ref_maybe_used_by_call_p_may_alias);
+ fprintf (s, " call_may_clobber_ref_p: "
+ HOST_WIDE_INT_PRINT_DEC" disambiguations, "
+ HOST_WIDE_INT_PRINT_DEC" queries\n",
+ alias_stats.call_may_clobber_ref_p_no_alias,
+ alias_stats.call_may_clobber_ref_p_no_alias
+ + alias_stats.call_may_clobber_ref_p_may_alias);
+}
+
+
+/* Return true, if dereferencing PTR may alias with a global variable. */
-static void
-setup_pointers_and_addressables (struct alias_info *ai)
+bool
+ptr_deref_may_alias_global_p (tree ptr)
{
- size_t num_addressable_vars, num_pointers;
- referenced_var_iterator rvi;
- tree var;
- VEC (tree, heap) *varvec = NULL;
- safe_referenced_var_iterator srvi;
-
- /* Size up the arrays ADDRESSABLE_VARS and POINTERS. */
- num_addressable_vars = num_pointers = 0;
-
- FOR_EACH_REFERENCED_VAR (var, rvi)
- {
- if (may_be_aliased (var))
- num_addressable_vars++;
-
- if (POINTER_TYPE_P (TREE_TYPE (var)))
- {
- /* Since we don't keep track of volatile variables, assume that
- these pointers are used in indirect store operations. */
- if (TREE_THIS_VOLATILE (var))
- pointer_set_insert (ai->dereferenced_ptrs, var);
-
- num_pointers++;
- }
- }
-
- /* Create ADDRESSABLE_VARS and POINTERS. Note that these arrays are
- always going to be slightly bigger than we actually need them
- because some TREE_ADDRESSABLE variables will be marked
- non-addressable below and only pointers with unique symbol tags are
- going to be added to POINTERS. */
- ai->addressable_vars = XCNEWVEC (struct alias_map_d *, num_addressable_vars);
- ai->pointers = XCNEWVEC (struct alias_map_d *, num_pointers);
- ai->num_addressable_vars = 0;
- ai->num_pointers = 0;
-
- FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi)
- {
- /* Name memory tags already have flow-sensitive aliasing
- information, so they need not be processed by
- compute_flow_insensitive_aliasing. Similarly, symbol memory
- tags are already accounted for when we process their
- associated pointer.
-
- Structure fields, on the other hand, have to have some of this
- information processed for them, but it's pointless to mark them
- non-addressable (since they are fake variables anyway). */
- if (MTAG_P (var))
- continue;
-
- /* Remove the ADDRESSABLE flag from every addressable variable whose
- address is not needed anymore. This is caused by the propagation
- 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))
- {
- if (!bitmap_bit_p (gimple_addressable_vars (cfun), DECL_UID (var))
- && TREE_CODE (var) != RESULT_DECL
- && !is_global_var (var))
- {
- bool okay_to_mark = true;
-
- /* Since VAR is now a regular GIMPLE register, we will need
- to rename VAR into SSA afterwards. */
- mark_sym_for_renaming (var);
-
- /* The address of VAR is not needed, remove the
- addressable bit, so that it can be optimized as a
- regular variable. */
- if (okay_to_mark)
- {
- /* The memory partition holding VAR will no longer
- contain VAR, and statements referencing it will need
- to be updated. */
- if (memory_partition (var))
- mark_sym_for_renaming (memory_partition (var));
-
- mark_non_addressable (var);
- }
- }
- }
-
- /* Global variables and addressable locals may be aliased. Create an
- entry in ADDRESSABLE_VARS for VAR. */
- if (may_be_aliased (var))
- {
- create_alias_map_for (var, ai);
- mark_sym_for_renaming (var);
- }
-
- /* Add pointer variables that have been dereferenced to the POINTERS
- array and create a symbol memory tag for them. */
- if (POINTER_TYPE_P (TREE_TYPE (var)))
- {
- if (pointer_set_contains (ai->dereferenced_ptrs, var))
- {
- tree tag, old_tag;
- var_ann_t t_ann;
-
- /* If pointer VAR still doesn't have a memory tag
- associated with it, create it now or re-use an
- existing one. */
- tag = get_smt_for (var, ai);
- t_ann = var_ann (tag);
-
- /* The symbol tag will need to be renamed into SSA
- afterwards. Note that we cannot do this inside
- get_smt_for because aliasing may run multiple times
- and we only create symbol tags the first time. */
- mark_sym_for_renaming (tag);
-
- /* Similarly, if pointer VAR used to have another type
- tag, we will need to process it in the renamer to
- remove the stale virtual operands. */
- old_tag = symbol_mem_tag (var);
- if (old_tag)
- mark_sym_for_renaming (old_tag);
-
- /* Associate the tag with pointer VAR. */
- set_symbol_mem_tag (var, tag);
- }
- else
- {
- /* The pointer has not been dereferenced. If it had a
- symbol memory tag, remove it and mark the old tag for
- renaming to remove it out of the IL. */
- tree tag = symbol_mem_tag (var);
- if (tag)
- {
- mark_sym_for_renaming (tag);
- set_symbol_mem_tag (var, NULL_TREE);
- }
- }
- }
- }
+ struct ptr_info_def *pi;
- VEC_free (tree, heap, varvec);
-}
+ /* If we end up with a pointer constant here that may point
+ to global memory. */
+ if (TREE_CODE (ptr) != SSA_NAME)
+ return true;
+ pi = SSA_NAME_PTR_INFO (ptr);
-/* Determine whether to use .GLOBAL_VAR to model call clobbering
- semantics. If the function makes no references to global
- variables and contains at least one call to a non-pure function,
- then we need to mark the side-effects of the call using .GLOBAL_VAR
- to represent all possible global memory referenced by the callee. */
+ /* If we do not have points-to information for this variable,
+ we have to punt. */
+ if (!pi)
+ return true;
-static void
-maybe_create_global_var (void)
-{
- /* No need to create it, if we have one already. */
- if (gimple_global_var (cfun) == NULL_TREE)
- {
- struct mem_ref_stats_d *stats = gimple_mem_ref_stats (cfun);
-
- /* Create .GLOBAL_VAR if there are no call-clobbered
- variables and the program contains a mixture of pure/const
- and regular function calls. This is to avoid the problem
- described in PR 20115:
-
- int X;
- int func_pure (void) { return X; }
- int func_non_pure (int a) { X += a; }
- int foo ()
- {
- int a = func_pure ();
- func_non_pure (a);
- a = func_pure ();
- return a;
- }
-
- Since foo() has no call-clobbered variables, there is
- no relationship between the calls to func_pure and
- func_non_pure. Since func_pure has no side-effects, value
- numbering optimizations elide the second call to func_pure.
- So, if we have some pure/const and some regular calls in the
- program we create .GLOBAL_VAR to avoid missing these
- relations. */
- if (bitmap_empty_p (gimple_call_clobbered_vars (cfun))
- && stats->num_call_sites > 0
- && stats->num_pure_const_call_sites > 0
- && stats->num_call_sites > stats->num_pure_const_call_sites)
- create_global_var ();
- }
+ return pt_solution_includes_global (&pi->pt);
}
+/* Return true if dereferencing PTR may alias DECL. */
-/* Return TRUE if pointer PTR may point to variable VAR.
-
- MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR
- This is needed because when checking for type conflicts we are
- interested in the alias set of the memory location pointed-to by
- PTR. The alias set of PTR itself is irrelevant.
-
- VAR_ALIAS_SET is the alias set for VAR. */
-
-bool
-may_alias_p (tree ptr, alias_set_type mem_alias_set,
- tree var, alias_set_type var_alias_set,
- bool alias_set_only)
+static bool
+ptr_deref_may_alias_decl_p (tree ptr, tree decl)
{
- tree mem;
-
- alias_stats.alias_queries++;
- alias_stats.simple_queries++;
-
- /* By convention, a variable cannot alias itself. */
- mem = symbol_mem_tag (ptr);
- if (mem == var)
- {
- alias_stats.alias_noalias++;
- alias_stats.simple_resolved++;
- return false;
- }
-
- /* If -fargument-noalias-global is > 2, pointer arguments may
- not point to anything else. */
- if (flag_argument_noalias > 2 && TREE_CODE (ptr) == PARM_DECL)
- {
- alias_stats.alias_noalias++;
- alias_stats.simple_resolved++;
- return false;
- }
-
- /* If -fargument-noalias-global is > 1, pointer arguments may
- not point to global variables. */
- if (flag_argument_noalias > 1 && is_global_var (var)
- && TREE_CODE (ptr) == PARM_DECL)
- {
- alias_stats.alias_noalias++;
- alias_stats.simple_resolved++;
- return false;
- }
-
- /* If the pointed to memory has alias set zero, or the pointer
- is ref-all, or the pointer decl is marked that no TBAA is to
- be applied, the MEM can alias VAR. */
- if (mem_alias_set == 0
- || DECL_POINTER_ALIAS_SET (ptr) == 0
- || TYPE_REF_CAN_ALIAS_ALL (TREE_TYPE (ptr))
- || DECL_NO_TBAA_P (ptr))
- {
- alias_stats.alias_mayalias++;
- alias_stats.simple_resolved++;
- return true;
- }
-
- gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG);
-
- alias_stats.tbaa_queries++;
-
- /* If the alias sets don't conflict then MEM cannot alias VAR. */
- if (mem_alias_set != var_alias_set
- && !alias_set_subset_of (mem_alias_set, var_alias_set))
- {
- alias_stats.alias_noalias++;
- alias_stats.tbaa_resolved++;
- return false;
- }
-
- /* If VAR is a record or union type, PTR cannot point into VAR
- unless there is some explicit address operation in the
- program that can reference a field of the type pointed-to by
- PTR. This also assumes that the types of both VAR and PTR
- are contained within the compilation unit, and that there is
- no fancy addressing arithmetic associated with any of the
- types involved. */
- if (mem_alias_set != 0 && var_alias_set != 0)
- {
- tree ptr_type = TREE_TYPE (ptr);
- tree var_type = TREE_TYPE (var);
-
- /* The star count is -1 if the type at the end of the
- pointer_to chain is not a record or union type. */
- if (!alias_set_only &&
- 0 /* FIXME tuples ipa_type_escape_star_count_of_interesting_type (var_type) >= 0*/)
- {
- int ptr_star_count = 0;
-
- /* ipa_type_escape_star_count_of_interesting_type is a
- little too restrictive for the pointer type, need to
- allow pointers to primitive types as long as those
- types cannot be pointers to everything. */
- while (POINTER_TYPE_P (ptr_type))
- {
- /* Strip the *s off. */
- ptr_type = TREE_TYPE (ptr_type);
- ptr_star_count++;
- }
-
- /* There does not appear to be a better test to see if
- the pointer type was one of the pointer to everything
- types. */
- if (ptr_star_count > 0)
- {
- alias_stats.structnoaddress_queries++;
- if (ipa_type_escape_field_does_not_clobber_p (var_type,
- TREE_TYPE (ptr)))
- {
- alias_stats.structnoaddress_resolved++;
- alias_stats.alias_noalias++;
- return false;
- }
- }
- else if (ptr_star_count == 0)
- {
- /* If PTR_TYPE was not really a pointer to type, it cannot
- alias. */
- alias_stats.structnoaddress_queries++;
- alias_stats.structnoaddress_resolved++;
- alias_stats.alias_noalias++;
- return false;
- }
- }
- }
+ struct ptr_info_def *pi;
- alias_stats.alias_mayalias++;
- return true;
-}
+ /* ??? During SCCVN/PRE we can end up with *&x during valueizing
+ operands. Likewise we can end up with dereferencing constant
+ pointers. Just bail out in these cases for now. */
+ if (TREE_CODE (ptr) == ADDR_EXPR
+ || TREE_CODE (ptr) == INTEGER_CST)
+ return true;
-/* Return true, if PTR may point to a global variable. */
+ gcc_assert (TREE_CODE (ptr) == SSA_NAME
+ && (TREE_CODE (decl) == VAR_DECL
+ || TREE_CODE (decl) == PARM_DECL
+ || TREE_CODE (decl) == RESULT_DECL));
-bool
-may_point_to_global_var (tree ptr)
-{
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
+ /* Non-aliased variables can not be pointed to. */
+ if (!may_be_aliased (decl))
+ return false;
- /* If we do not have points-to information for this variable,
- we have to punt. */
- if (!pi
- || !pi->name_mem_tag)
+ /* If we do not have useful points-to information for this pointer
+ we cannot disambiguate anything else. */
+ pi = SSA_NAME_PTR_INFO (ptr);
+ if (!pi)
return true;
- /* The name memory tag is marked as global variable if the points-to
- set contains a global variable. */
- return is_global_var (pi->name_mem_tag);
+ return pt_solution_includes (&pi->pt, decl);
}
-/* Add ALIAS to the set of variables that may alias VAR. */
+/* Return true if dereferenced PTR1 and PTR2 may alias. */
-static void
-add_may_alias (tree var, tree alias)
+static bool
+ptr_derefs_may_alias_p (tree ptr1, tree ptr2)
{
- /* 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
-
- /* VAR must be a symbol or a name tag. */
- gcc_assert (TREE_CODE (var) == SYMBOL_MEMORY_TAG
- || TREE_CODE (var) == NAME_MEMORY_TAG);
-
- if (MTAG_ALIASES (var) == NULL)
- MTAG_ALIASES (var) = BITMAP_ALLOC (&alias_bitmap_obstack);
-
- bitmap_set_bit (MTAG_ALIASES (var), DECL_UID (alias));
-}
+ struct ptr_info_def *pi1, *pi2;
+ /* ??? During SCCVN/PRE we can end up with *&x during valueizing
+ operands. Likewise we can end up with dereferencing constant
+ pointers. Just bail out in these cases for now. */
+ if (TREE_CODE (ptr1) == ADDR_EXPR
+ || TREE_CODE (ptr1) == INTEGER_CST
+ || TREE_CODE (ptr2) == ADDR_EXPR
+ || TREE_CODE (ptr2) == INTEGER_CST)
+ return true;
-/* Mark pointer PTR as pointing to an arbitrary memory location. */
+ gcc_assert (TREE_CODE (ptr1) == SSA_NAME
+ && TREE_CODE (ptr2) == SSA_NAME);
-static void
-set_pt_anything (tree ptr)
-{
- struct ptr_info_def *pi = get_ptr_info (ptr);
+ /* We may end up with two empty points-to solutions for two same pointers.
+ In this case we still want to say both pointers alias, so shortcut
+ that here. */
+ if (ptr1 == ptr2)
+ return true;
- pi->pt_anything = 1;
- /* Anything includes global memory. */
- pi->pt_global_mem = 1;
- pi->pt_vars = NULL;
+ /* If we do not have useful points-to information for either pointer
+ we cannot disambiguate anything else. */
+ pi1 = SSA_NAME_PTR_INFO (ptr1);
+ pi2 = SSA_NAME_PTR_INFO (ptr2);
+ if (!pi1 || !pi2)
+ return true;
- /* The pointer used to have a name tag, but we now found it pointing
- to an arbitrary location. The name tag needs to be renamed and
- disassociated from PTR. */
- if (pi->name_mem_tag)
- {
- mark_sym_for_renaming (pi->name_mem_tag);
- pi->name_mem_tag = NULL_TREE;
- }
+ return pt_solutions_intersect (&pi1->pt, &pi2->pt);
}
-
/* 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:
if (lhs == NULL_TREE)
return ESCAPE_UNKNOWN;
- if (gimple_assign_cast_p (stmt))
- {
- tree from = TREE_TYPE (gimple_assign_rhs1 (stmt));
- tree to = TREE_TYPE (lhs);
-
- /* If the RHS is a conversion between a pointer and an integer, the
- pointer escapes since we can't track the integer. */
- if (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to))
- return ESCAPE_BAD_CAST;
- }
-
- /* If the LHS is an SSA name, it can't possibly represent a non-local
- memory store. */
- if (TREE_CODE (lhs) == SSA_NAME)
- return NO_ESCAPE;
-
- /* If the LHS is a non-global decl, it isn't a non-local memory store.
- If the LHS escapes, the RHS escape is dealt with in the PTA solver. */
- if (DECL_P (lhs)
- && !is_global_var (lhs))
- return NO_ESCAPE;
-
- /* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a
- local variables we cannot be sure if it will escape, because we
- don't have information about objects not in SSA form. Need to
- implement something along the lines of
-
- J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P.
- Midkiff, ``Escape analysis for java,'' in Proceedings of the
- Conference on Object-Oriented Programming Systems, Languages, and
- Applications (OOPSLA), pp. 1-19, 1999. */
- return ESCAPE_STORED_IN_GLOBAL;
- }
- else if (gimple_code (stmt) == GIMPLE_RETURN)
- return ESCAPE_TO_RETURN;
-
- return NO_ESCAPE;
-}
-
-/* Create a new memory tag of type TYPE.
- Does NOT push it into the current binding. */
-
-tree
-create_tag_raw (enum tree_code code, tree type, const char *prefix)
-{
- tree tmp_var;
-
- tmp_var = build_decl (code, create_tmp_var_name (prefix), type);
-
- /* Memory tags are always writable and non-static. */
- TREE_READONLY (tmp_var) = 0;
- TREE_STATIC (tmp_var) = 0;
-
- /* It doesn't start out global. */
- MTAG_GLOBAL (tmp_var) = 0;
- TREE_USED (tmp_var) = 1;
-
- return tmp_var;
-}
-
-/* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag
- is considered to represent all the pointers whose pointed-to types are
- in the same alias set class. Otherwise, the tag represents a single
- SSA_NAME pointer variable. */
-
-static tree
-create_memory_tag (tree type, bool is_type_tag)
-{
- tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG,
- type, (is_type_tag) ? "SMT" : "NMT");
-
- /* By default, memory tags are local variables. Alias analysis will
- determine whether they should be considered globals. */
- DECL_CONTEXT (tag) = current_function_decl;
-
- /* Memory tags are by definition addressable. */
- TREE_ADDRESSABLE (tag) = 1;
-
- set_symbol_mem_tag (tag, NULL_TREE);
-
- /* Add the tag to the symbol table. */
- add_referenced_var (tag);
-
- return tag;
-}
-
-
-/* Create a name memory tag to represent a specific SSA_NAME pointer P_i.
- This is used if P_i has been found to point to a specific set of
- variables or to a non-aliased memory location like the address returned
- by malloc functions. */
-
-static tree
-get_nmt_for (tree ptr)
-{
- struct ptr_info_def *pi = get_ptr_info (ptr);
- tree tag = pi->name_mem_tag;
-
- if (tag == NULL_TREE)
- tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false);
- return tag;
-}
-
-
-/* Return the symbol memory tag associated to pointer PTR. A memory
- tag is an artificial variable that represents the memory location
- pointed-to by PTR. It is used to model the effects of pointer
- de-references on addressable variables.
-
- AI points to the data gathered during alias analysis. This
- function populates the array AI->POINTERS. */
-
-static tree
-get_smt_for (tree ptr, struct alias_info *ai)
-{
- size_t i;
- tree tag;
- tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
- alias_set_type tag_set;
-
- /* Get the alias set to be used for the pointed-to memory. If that
- differs from what we would get from looking at the type adjust
- the tag_type to void to make sure we get a proper alias set from
- just looking at the SMT we create. */
- tag_set = get_alias_set (tag_type);
- if (TYPE_REF_CAN_ALIAS_ALL (TREE_TYPE (ptr))
- /* This is overly conservative but we do not want to assign
- restrict alias sets here (which if they are not assigned
- are -2 but still "known"). */
- || DECL_POINTER_ALIAS_SET_KNOWN_P (ptr))
- {
- tag_set = 0;
- tag_type = void_type_node;
- }
-
- /* To avoid creating unnecessary memory tags, only create one memory tag
- per alias set class. Note that it may be tempting to group
- memory tags based on conflicting alias sets instead of
- equivalence. That would be wrong because alias sets are not
- necessarily transitive (as demonstrated by the libstdc++ test
- 23_containers/vector/cons/4.cc). Given three alias sets A, B, C
- such that conflicts (A, B) == true and conflicts (A, C) == true,
- it does not necessarily follow that conflicts (B, C) == true. */
- for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
- {
- struct alias_map_d *curr = ai->pointers[i];
- tree curr_tag = symbol_mem_tag (curr->var);
- if (tag_set == curr->set)
- {
- tag = curr_tag;
- break;
- }
- }
-
- /* If VAR cannot alias with any of the existing memory tags, create a new
- tag for PTR and add it to the POINTERS array. */
- if (tag == NULL_TREE)
- {
- struct alias_map_d *alias_map;
-
- /* If PTR did not have a symbol tag already, create a new SMT.*
- artificial variable representing the memory location
- pointed-to by PTR. */
- tag = symbol_mem_tag (ptr);
- if (tag == NULL_TREE
- || tag_set != get_alias_set (tag))
- tag = create_memory_tag (tag_type, true);
-
- /* Add PTR to the POINTERS array. Note that we are not interested in
- PTR's alias set. Instead, we cache the alias set for the memory that
- PTR points to. */
- alias_map = XCNEW (struct alias_map_d);
- alias_map->var = ptr;
- alias_map->set = tag_set;
- ai->pointers[ai->num_pointers++] = alias_map;
- }
-
- /* If the pointed-to type is volatile, so is the tag. */
- TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type);
-
- /* Make sure that the symbol tag has the same alias set as the
- pointed-to type or at least accesses through the pointer will
- alias that set. The latter can happen after the vectorizer
- created pointers of vector type. */
- gcc_assert (tag_set == get_alias_set (tag)
- || alias_set_subset_of (tag_set, get_alias_set (tag)));
-
- return tag;
-}
+ if (gimple_assign_cast_p (stmt))
+ {
+ tree from = TREE_TYPE (gimple_assign_rhs1 (stmt));
+ tree to = TREE_TYPE (lhs);
+ /* If the RHS is a conversion between a pointer and an integer, the
+ pointer escapes since we can't track the integer. */
+ if (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to))
+ return ESCAPE_BAD_CAST;
+ }
-/* Create GLOBAL_VAR, an artificial global variable to act as a
- representative of all the variables that may be clobbered by function
- calls. */
+ /* If the LHS is an SSA name, it can't possibly represent a non-local
+ memory store. */
+ if (TREE_CODE (lhs) == SSA_NAME)
+ return NO_ESCAPE;
-static void
-create_global_var (void)
-{
- tree global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
- void_type_node);
- DECL_ARTIFICIAL (global_var) = 1;
- TREE_READONLY (global_var) = 0;
- DECL_EXTERNAL (global_var) = 1;
- TREE_STATIC (global_var) = 1;
- TREE_USED (global_var) = 1;
- DECL_CONTEXT (global_var) = NULL_TREE;
- TREE_THIS_VOLATILE (global_var) = 0;
- TREE_ADDRESSABLE (global_var) = 0;
-
- create_var_ann (global_var);
- mark_call_clobbered (global_var, ESCAPE_UNKNOWN);
- add_referenced_var (global_var);
- mark_sym_for_renaming (global_var);
- cfun->gimple_df->global_var = global_var;
-}
+ /* If the LHS is a non-global decl, it isn't a non-local memory store.
+ If the LHS escapes, the RHS escape is dealt with in the PTA solver. */
+ if (DECL_P (lhs)
+ && !is_global_var (lhs))
+ return NO_ESCAPE;
+ /* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a
+ local variables we cannot be sure if it will escape, because we
+ don't have information about objects not in SSA form. Need to
+ implement something along the lines of
-/* Dump alias statistics on FILE. */
+ J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P.
+ Midkiff, ``Escape analysis for java,'' in Proceedings of the
+ Conference on Object-Oriented Programming Systems, Languages, and
+ Applications (OOPSLA), pp. 1-19, 1999. */
+ return ESCAPE_STORED_IN_GLOBAL;
+ }
+ else if (gimple_code (stmt) == GIMPLE_RETURN)
+ return ESCAPE_TO_RETURN;
-static void
-dump_alias_stats (FILE *file)
-{
- const char *funcname
- = lang_hooks.decl_printable_name (current_function_decl, 2);
- fprintf (file, "\nAlias statistics for %s\n\n", funcname);
- fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries);
- fprintf (file, "Total alias mayalias results:\t%u\n",
- alias_stats.alias_mayalias);
- fprintf (file, "Total alias noalias results:\t%u\n",
- alias_stats.alias_noalias);
- fprintf (file, "Total simple queries:\t%u\n",
- alias_stats.simple_queries);
- fprintf (file, "Total simple resolved:\t%u\n",
- alias_stats.simple_resolved);
- fprintf (file, "Total TBAA queries:\t%u\n",
- alias_stats.tbaa_queries);
- fprintf (file, "Total TBAA resolved:\t%u\n",
- alias_stats.tbaa_resolved);
- fprintf (file, "Total non-addressable structure type queries:\t%u\n",
- alias_stats.structnoaddress_queries);
- fprintf (file, "Total non-addressable structure type resolved:\t%u\n",
- alias_stats.structnoaddress_resolved);
+ return NO_ESCAPE;
}
-
+
/* Dump alias information on FILE. */
referenced_var_iterator rvi;
tree var;
- fprintf (file, "\nAlias information for %s\n\n", funcname);
-
- dump_memory_partitions (file);
-
- fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname);
+ fprintf (file, "\n\nAlias information for %s\n\n", funcname);
fprintf (file, "Aliased symbols\n\n");
dump_variable (file, var);
}
- fprintf (file, "\nDereferenced pointers\n\n");
-
- FOR_EACH_REFERENCED_VAR (var, rvi)
- if (symbol_mem_tag (var))
- dump_variable (file, var);
-
- fprintf (file, "\nSymbol memory tags\n\n");
-
- FOR_EACH_REFERENCED_VAR (var, rvi)
- {
- if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
- dump_variable (file, var);
- }
-
- fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname);
+ fprintf (file, "\n\nFlow-insensitive points-to information for %s\n\n", funcname);
- fprintf (file, "SSA_NAME pointers\n\n");
for (i = 1; i < num_ssa_names; i++)
{
tree ptr = ssa_name (i);
struct ptr_info_def *pi;
- if (ptr == NULL_TREE)
+ if (ptr == NULL_TREE
+ || SSA_NAME_IN_FREE_LIST (ptr))
continue;
pi = SSA_NAME_PTR_INFO (ptr);
- if (!SSA_NAME_IN_FREE_LIST (ptr)
- && pi
- && pi->name_mem_tag)
+ if (pi)
dump_points_to_info_for (file, ptr);
}
- fprintf (file, "\nName memory tags\n\n");
-
- FOR_EACH_REFERENCED_VAR (var, rvi)
- {
- if (TREE_CODE (var) == NAME_MEMORY_TAG)
- dump_variable (file, var);
- }
-
fprintf (file, "\n");
}
if (pi == NULL)
{
pi = GGC_CNEW (struct ptr_info_def);
+ pt_solution_reset (&pi->pt);
SSA_NAME_PTR_INFO (t) = pi;
}
if (pi)
{
- if (pi->name_mem_tag)
- {
- fprintf (file, ", name memory tag: ");
- print_generic_expr (file, pi->name_mem_tag, dump_flags);
- }
-
- if (pi->is_dereferenced)
- fprintf (file, ", is dereferenced");
- else if (pi->memory_tag_needed)
- fprintf (file, ", is dereferenced in call");
+ if (pi->pt.anything)
+ fprintf (file, ", points-to anything");
- if (pi->value_escapes_p)
- fprintf (file, ", its value escapes");
+ if (pi->pt.nonlocal)
+ fprintf (file, ", points-to non-local");
- if (pi->pt_anything)
- fprintf (file, ", points-to anything");
+ if (pi->pt.escaped)
+ fprintf (file, ", points-to escaped");
- if (pi->pt_null)
+ if (pi->pt.null)
fprintf (file, ", points-to NULL");
- if (pi->pt_vars)
+ if (pi->pt.vars)
{
fprintf (file, ", points-to vars: ");
- dump_decl_set (file, pi->pt_vars);
+ dump_decl_set (file, pi->pt.vars);
+ if (pi->pt.vars_contains_global)
+ fprintf (file, " (includes global vars)");
}
}
dump_points_to_info_for (stderr, var);
}
+/* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
+ purpose of TBAA. Return 0 if they are distinct and -1 if we cannot
+ decide. */
-/* Dump points-to information into FILE. NOTE: This function is slow, as
- it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */
+static inline int
+same_type_for_tbaa (tree type1, tree type2)
+{
+ type1 = TYPE_MAIN_VARIANT (type1);
+ type2 = TYPE_MAIN_VARIANT (type2);
-void
-dump_points_to_info (FILE *file ATTRIBUTE_UNUSED)
+ /* If we would have to do structural comparison bail out. */
+ if (TYPE_STRUCTURAL_EQUALITY_P (type1)
+ || TYPE_STRUCTURAL_EQUALITY_P (type2))
+ return -1;
+
+ /* Compare the canonical types. */
+ if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
+ return 1;
+
+ /* ??? Array types are not properly unified in all cases as we have
+ spurious changes in the index types for example. Removing this
+ causes all sorts of problems with the Fortran frontend. */
+ if (TREE_CODE (type1) == ARRAY_TYPE
+ && TREE_CODE (type2) == ARRAY_TYPE)
+ return -1;
+
+ /* The types are known to be not equal. */
+ return 0;
+}
+
+/* Determine if the two component references REF1 and REF2 which are
+ based on access types TYPE1 and TYPE2 and of which at least one is based
+ on an indirect reference may alias. */
+
+static bool
+nonaliasing_component_refs_p (tree ref1, tree type1,
+ HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
+ tree ref2, tree type2,
+ HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2)
+{
+ /* If one reference is a component references through pointers try to find a
+ common base and apply offset based disambiguation. This handles
+ for example
+ struct A { int i; int j; } *q;
+ struct B { struct A a; int k; } *p;
+ disambiguating q->i and p->a.j. */
+ tree *refp;
+ int same_p;
+
+ /* Now search for the type1 in the access path of ref2. This
+ would be a common base for doing offset based disambiguation on. */
+ /* Skip the outermost ref - we would have caught that earlier. */
+ refp = &TREE_OPERAND (ref2, 0);
+ while (handled_component_p (*refp)
+ && same_type_for_tbaa (TREE_TYPE (*refp), type1) == 0)
+ refp = &TREE_OPERAND (*refp, 0);
+ same_p = same_type_for_tbaa (TREE_TYPE (*refp), type1);
+ /* If we couldn't compare types we have to bail out. */
+ if (same_p == -1)
+ return true;
+ else if (same_p == 1)
+ {
+ HOST_WIDE_INT offadj, sztmp, msztmp;
+ get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
+ offset2 -= offadj;
+ return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
+ }
+ /* If we didn't find a common base, try the other way around. */
+ refp = &TREE_OPERAND (ref1, 0);
+ while (handled_component_p (*refp)
+ && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0)
+ refp = &TREE_OPERAND (*refp, 0);
+ same_p = same_type_for_tbaa (TREE_TYPE (*refp), type2);
+ /* If we couldn't compare types we have to bail out. */
+ if (same_p == -1)
+ return true;
+ else if (same_p == 1)
+ {
+ HOST_WIDE_INT offadj, sztmp, msztmp;
+ get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
+ offset1 -= offadj;
+ return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
+ }
+ /* If we have two type access paths B1.path1 and B2.path2 they may
+ only alias if either B1 is in B2.path2 or B2 is in B1.path1. */
+ return false;
+}
+
+/* Return true if two memory references based on the variables BASE1
+ and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1[ and
+ [OFFSET2, OFFSET2 + MAX_SIZE2[ may alias. */
+
+static bool
+decl_refs_may_alias_p (tree base1,
+ HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
+ tree base2,
+ HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2)
{
- basic_block bb;
- gimple_stmt_iterator si;
- ssa_op_iter iter;
- const char *fname =
- lang_hooks.decl_printable_name (current_function_decl, 2);
- referenced_var_iterator rvi;
- tree var;
+ gcc_assert (SSA_VAR_P (base1) && SSA_VAR_P (base2));
- fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname);
+ /* If both references are based on different variables, they cannot alias. */
+ if (!operand_equal_p (base1, base2, 0))
+ return false;
- /* First dump points-to information for the default definitions of
- pointer variables. This is necessary because default definitions are
- not part of the code. */
- FOR_EACH_REFERENCED_VAR (var, rvi)
+ /* If both references are based on the same variable, they cannot alias if
+ the accesses do not overlap. */
+ return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
+}
+
+/* Return true if an indirect reference based on *PTR1 constrained
+ to [OFFSET1, OFFSET1 + MAX_SIZE1[ may alias a variable based on BASE2
+ constrained to [OFFSET2, OFFSET2 + MAX_SIZE2[. *PTR1 and BASE2 have
+ the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
+ in which case they are computed on-demand. REF1 and REF2
+ if non-NULL are the complete memory reference trees. */
+
+static bool
+indirect_ref_may_alias_decl_p (tree ref1, tree ptr1,
+ HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
+ alias_set_type base1_alias_set,
+ tree ref2, tree base2,
+ HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2,
+ alias_set_type base2_alias_set)
+{
+ /* If only one reference is based on a variable, they cannot alias if
+ the pointer access is beyond the extent of the variable access.
+ (the pointer base cannot validly point to an offset less than zero
+ of the variable).
+ They also cannot alias if the pointer may not point to the decl. */
+ if (max_size2 != -1
+ && !ranges_overlap_p (offset1, max_size1, 0, offset2 + max_size2))
+ return false;
+ if (!ptr_deref_may_alias_decl_p (ptr1, base2))
+ return false;
+
+ /* Disambiguations that rely on strict aliasing rules follow. */
+ if (!flag_strict_aliasing)
+ return true;
+
+ /* If the alias set for a pointer access is zero all bets are off. */
+ if (base1_alias_set == -1)
+ base1_alias_set = get_deref_alias_set (ptr1);
+ if (base1_alias_set == 0)
+ return true;
+ if (base2_alias_set == -1)
+ base2_alias_set = get_alias_set (base2);
+
+ /* If both references are through the same type, they do not alias
+ if the accesses do not overlap. This does extra disambiguation
+ for mixed/pointer accesses but requires strict aliasing. */
+ if (same_type_for_tbaa (TREE_TYPE (TREE_TYPE (ptr1)),
+ TREE_TYPE (base2)) == 1)
+ return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
+
+ /* The only way to access a variable is through a pointer dereference
+ of the same alias set or a subset of it. */
+ if (base1_alias_set != base2_alias_set
+ && !alias_set_subset_of (base1_alias_set, base2_alias_set))
+ return false;
+
+ /* Do access-path based disambiguation. */
+ if (ref1 && ref2
+ && handled_component_p (ref1)
+ && handled_component_p (ref2))
+ return nonaliasing_component_refs_p (ref1, TREE_TYPE (TREE_TYPE (ptr1)),
+ offset1, max_size1,
+ ref2, TREE_TYPE (base2),
+ offset2, max_size2);
+
+ return true;
+}
+
+/* Return true if two indirect references based on *PTR1
+ and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1[ and
+ [OFFSET2, OFFSET2 + MAX_SIZE2[ may alias. *PTR1 and *PTR2 have
+ the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
+ in which case they are computed on-demand. REF1 and REF2
+ if non-NULL are the complete memory reference trees. */
+
+static bool
+indirect_refs_may_alias_p (tree ref1, tree ptr1,
+ HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1,
+ alias_set_type base1_alias_set,
+ tree ref2, tree ptr2,
+ HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2,
+ alias_set_type base2_alias_set)
+{
+ /* If both bases are based on pointers they cannot alias if they may not
+ point to the same memory object or if they point to the same object
+ and the accesses do not overlap. */
+ if (operand_equal_p (ptr1, ptr2, 0))
+ return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
+ if (!ptr_derefs_may_alias_p (ptr1, ptr2))
+ return false;
+
+ /* Disambiguations that rely on strict aliasing rules follow. */
+ if (!flag_strict_aliasing)
+ return true;
+
+ /* If the alias set for a pointer access is zero all bets are off. */
+ if (base1_alias_set == -1)
+ base1_alias_set = get_deref_alias_set (ptr1);
+ if (base1_alias_set == 0)
+ return true;
+ if (base2_alias_set == -1)
+ base2_alias_set = get_deref_alias_set (ptr2);
+ if (base2_alias_set == 0)
+ return true;
+
+ /* If both references are through the same type, they do not alias
+ if the accesses do not overlap. This does extra disambiguation
+ for mixed/pointer accesses but requires strict aliasing. */
+ if (same_type_for_tbaa (TREE_TYPE (TREE_TYPE (ptr1)),
+ TREE_TYPE (TREE_TYPE (ptr2))) == 1)
+ return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
+
+ /* Do type-based disambiguation. */
+ if (base1_alias_set != base2_alias_set
+ && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
+ return false;
+
+ /* Do access-path based disambiguation. */
+ if (ref1 && ref2
+ && handled_component_p (ref1)
+ && handled_component_p (ref2))
+ return nonaliasing_component_refs_p (ref1, TREE_TYPE (TREE_TYPE (ptr1)),
+ offset1, max_size1,
+ ref2, TREE_TYPE (TREE_TYPE (ptr2)),
+ offset2, max_size2);
+
+ return true;
+}
+
+/* Return true, if the two memory references REF1 and REF2 may alias. */
+
+static bool
+refs_may_alias_p_1 (tree ref1, tree ref2)
+{
+ tree base1, base2;
+ HOST_WIDE_INT offset1 = 0, offset2 = 0;
+ HOST_WIDE_INT size1 = -1, size2 = -1;
+ HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
+ bool var1_p, var2_p, ind1_p, ind2_p;
+
+ gcc_assert ((SSA_VAR_P (ref1)
+ || handled_component_p (ref1)
+ || INDIRECT_REF_P (ref1)
+ || TREE_CODE (ref1) == TARGET_MEM_REF)
+ && (SSA_VAR_P (ref2)
+ || handled_component_p (ref2)
+ || INDIRECT_REF_P (ref2)
+ || TREE_CODE (ref2) == TARGET_MEM_REF));
+
+ /* Defer to TBAA if possible. */
+ if (flag_strict_aliasing
+ && !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2)))
+ return false;
+
+ /* If one reference is a TARGET_MEM_REF weird things are allowed. */
+ if (TREE_CODE (ref1) == TARGET_MEM_REF
+ || TREE_CODE (ref2) == TARGET_MEM_REF)
+ return true;
+
+ /* Decompose the references into their base objects and the access. */
+ base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1);
+ base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &max_size2);
+
+ /* We can end up with registers or constants as bases for example from
+ *D.1663_44 = VIEW_CONVERT_EXPR<struct DB_LSN>(__tmp$B0F64_59);
+ which is seen as a struct copy. */
+ if (TREE_CODE (base1) == SSA_NAME
+ || CONSTANT_CLASS_P (base1)
+ || TREE_CODE (base2) == SSA_NAME
+ || CONSTANT_CLASS_P (base2))
+ return false;
+
+ var1_p = SSA_VAR_P (base1);
+ var2_p = SSA_VAR_P (base2);
+ ind1_p = INDIRECT_REF_P (base1);
+ ind2_p = INDIRECT_REF_P (base2);
+ if (var1_p && var2_p)
+ return decl_refs_may_alias_p (base1, offset1, max_size1,
+ base2, offset2, max_size2);
+ else if (var1_p && ind2_p)
+ return indirect_ref_may_alias_decl_p (ref2, TREE_OPERAND (base2, 0),
+ offset2, max_size2, -1,
+ ref1, base1,
+ offset1, max_size1, -1);
+ else if (ind1_p && var2_p)
+ return indirect_ref_may_alias_decl_p (ref1, TREE_OPERAND (base1, 0),
+ offset1, max_size1, -1,
+ ref2, base2,
+ offset2, max_size2, -1);
+ else if (ind1_p && ind2_p)
+ return indirect_refs_may_alias_p (ref1, TREE_OPERAND (base1, 0),
+ offset1, max_size1, -1,
+ ref2, TREE_OPERAND (base2, 0),
+ offset2, max_size2, -1);
+
+ gcc_unreachable ();
+}
+
+bool
+refs_may_alias_p (tree ref1, tree ref2)
+{
+ bool res = refs_may_alias_p_1 (ref1, ref2);
+ if (res)
+ ++alias_stats.refs_may_alias_p_may_alias;
+ else
+ ++alias_stats.refs_may_alias_p_no_alias;
+ return res;
+}
+
+
+/* If the call CALL may use the memory reference REF return true,
+ otherwise return false. */
+
+static bool
+ref_maybe_used_by_call_p_1 (gimple call, tree ref)
+{
+ tree base;
+ unsigned i;
+ int flags = gimple_call_flags (call);
+
+ /* Const functions without a static chain do not implicitly use memory. */
+ if (!gimple_call_chain (call)
+ && (flags & (ECF_CONST|ECF_NOVOPS)))
+ goto process_args;
+
+ /* If the reference is not based on a decl give up.
+ ??? Handle indirect references by intersecting the call-used
+ solution with that of the pointer. */
+ base = get_base_address (ref);
+ if (!base
+ || !DECL_P (base))
+ return true;
+
+ /* Check if base is a global static variable that is not read
+ by the function. */
+ if (TREE_CODE (base) == VAR_DECL
+ && TREE_STATIC (base)
+ && !TREE_PUBLIC (base))
{
- if (POINTER_TYPE_P (TREE_TYPE (var)))
- {
- tree def = gimple_default_def (cfun, var);
- if (def)
- dump_points_to_info_for (file, def);
- }
+ tree callee = gimple_call_fndecl (call);
+ bitmap not_read;
+
+ if (callee != NULL_TREE
+ && (not_read
+ = ipa_reference_get_not_read_global (cgraph_node (callee)))
+ && bitmap_bit_p (not_read, DECL_UID (base)))
+ goto process_args;
}
- /* Dump points-to information for every pointer defined in the program. */
- FOR_EACH_BB (bb)
+ /* If the base variable is call-used or call-clobbered then
+ it may be used. */
+ if (flags & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS))
{
- for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
- {
- gimple phi = gsi_stmt (si);
- tree ptr = PHI_RESULT (phi);
- if (POINTER_TYPE_P (TREE_TYPE (ptr)))
- dump_points_to_info_for (file, ptr);
- }
+ if (is_call_used (base))
+ return true;
+ }
+ else
+ {
+ if (is_call_clobbered (base))
+ return true;
+ }
+
+ /* Inspect call arguments for passed-by-value aliases. */
+process_args:
+ for (i = 0; i < gimple_call_num_args (call); ++i)
+ {
+ tree op = gimple_call_arg (call, i);
+
+ if (TREE_CODE (op) == EXC_PTR_EXPR
+ || TREE_CODE (op) == FILTER_EXPR)
+ continue;
+
+ if (TREE_CODE (op) == WITH_SIZE_EXPR)
+ op = TREE_OPERAND (op, 0);
- for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
- {
- gimple stmt = gsi_stmt (si);
- tree def;
- FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
- if (TREE_CODE (def) == SSA_NAME
- && POINTER_TYPE_P (TREE_TYPE (def)))
- dump_points_to_info_for (file, def);
- }
+ if (TREE_CODE (op) != SSA_NAME
+ && !is_gimple_min_invariant (op)
+ && refs_may_alias_p (op, ref))
+ return true;
}
- fprintf (file, "\n");
+ return false;
+}
+
+static bool
+ref_maybe_used_by_call_p (gimple call, tree ref)
+{
+ bool res = ref_maybe_used_by_call_p_1 (call, ref);
+ if (res)
+ ++alias_stats.ref_maybe_used_by_call_p_may_alias;
+ else
+ ++alias_stats.ref_maybe_used_by_call_p_no_alias;
+ return res;
}
-/* Dump points-to info pointed to by PTO into STDERR. */
+/* If the statement STMT may use the memory reference REF return
+ true, otherwise return false. */
-void
-debug_points_to_info (void)
+bool
+ref_maybe_used_by_stmt_p (gimple stmt, tree ref)
{
- dump_points_to_info (stderr);
+ if (is_gimple_assign (stmt))
+ {
+ tree rhs;
+
+ /* All memory assign statements are single. */
+ if (!gimple_assign_single_p (stmt))
+ return false;
+
+ rhs = gimple_assign_rhs1 (stmt);
+ if (is_gimple_reg (rhs)
+ || is_gimple_min_invariant (rhs)
+ || gimple_assign_rhs_code (stmt) == CONSTRUCTOR)
+ return false;
+
+ return refs_may_alias_p (rhs, ref);
+ }
+ else if (is_gimple_call (stmt))
+ return ref_maybe_used_by_call_p (stmt, ref);
+
+ return true;
}
-/* Dump to FILE the list of variables that may be aliasing VAR. */
+/* If the call in statement CALL may clobber the memory reference REF
+ return true, otherwise return false. */
-void
-dump_may_aliases_for (FILE *file, tree var)
+static bool
+call_may_clobber_ref_p_1 (gimple call, tree ref)
{
- bitmap aliases;
-
- aliases = MTAG_ALIASES (var);
- if (aliases)
+ tree base;
+
+ /* If the call is pure or const it cannot clobber anything. */
+ if (gimple_call_flags (call)
+ & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS))
+ return false;
+
+ base = get_base_address (ref);
+ if (!base)
+ return true;
+
+ if (TREE_CODE (base) == SSA_NAME
+ || CONSTANT_CLASS_P (base))
+ return false;
+
+ /* Check if base is a global static variable that is not written
+ by the function. */
+ if (TREE_CODE (base) == VAR_DECL
+ && TREE_STATIC (base)
+ && !TREE_PUBLIC (base))
{
- bitmap_iterator bi;
- unsigned int i;
- tree al;
+ tree callee = gimple_call_fndecl (call);
+ bitmap not_written;
- fprintf (file, "{ ");
- EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
- {
- al = referenced_var (i);
- print_generic_expr (file, al, dump_flags);
- fprintf (file, " ");
- }
- fprintf (file, "}");
+ if (callee != NULL_TREE
+ && (not_written
+ = ipa_reference_get_not_written_global (cgraph_node (callee)))
+ && bitmap_bit_p (not_written, DECL_UID (base)))
+ return false;
}
-}
+ if (DECL_P (base))
+ return is_call_clobbered (base);
-/* Dump to stderr the list of variables that may be aliasing VAR. */
+ return true;
+}
-void
-debug_may_aliases_for (tree var)
+static bool
+call_may_clobber_ref_p (gimple call, tree ref)
{
- dump_may_aliases_for (stderr, var);
+ bool res = call_may_clobber_ref_p_1 (call, ref);
+ if (res)
+ ++alias_stats.call_may_clobber_ref_p_may_alias;
+ else
+ ++alias_stats.call_may_clobber_ref_p_no_alias;
+ return res;
}
-/* Return true if VAR may be aliased. */
+
+/* If the statement STMT may clobber the memory reference REF return true,
+ otherwise return false. */
bool
-may_be_aliased (tree var)
+stmt_may_clobber_ref_p (gimple stmt, tree ref)
{
- /* Obviously. */
- if (TREE_ADDRESSABLE (var))
- return true;
+ if (is_gimple_call (stmt))
+ {
+ tree lhs = gimple_call_lhs (stmt);
+ if (lhs
+ && !is_gimple_reg (lhs)
+ && refs_may_alias_p (ref, lhs))
+ return true;
- /* Globally visible variables can have their addresses taken by other
- translation units. */
- if (MTAG_P (var)
- && MTAG_GLOBAL (var))
- return true;
- else if (!MTAG_P (var)
- && (DECL_EXTERNAL (var) || TREE_PUBLIC (var)))
+ return call_may_clobber_ref_p (stmt, ref);
+ }
+ else if (is_gimple_assign (stmt))
+ return refs_may_alias_p (ref, gimple_assign_lhs (stmt));
+ else if (gimple_code (stmt) == GIMPLE_ASM)
return true;
- /* Automatic variables can't have their addresses escape any other
- way. This must be after the check for global variables, as
- extern declarations do not have TREE_STATIC set. */
- if (!TREE_STATIC (var))
- return false;
-
return false;
}
-/* The following is based on code in add_stmt_operand to ensure that the
- same defs/uses/vdefs/vuses will be found after replacing a reference
- to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value
- is the address of var. Return a memtag for the ptr, after adding the
- proper may_aliases to it (which are the aliases of var, if it has any,
- or var itself). */
+static tree get_continuation_for_phi (gimple, tree, bitmap *);
-static tree
-add_may_alias_for_new_tag (tree tag, tree var)
+/* Walk the virtual use-def chain of VUSE until hitting the virtual operand
+ TARGET or a statement clobbering the memory reference REF in which
+ case false is returned. The walk starts with VUSE, one argument of PHI. */
+
+static bool
+maybe_skip_until (gimple phi, tree target, tree ref, tree vuse, bitmap *visited)
{
- bitmap aliases = NULL;
-
- if (MTAG_P (var))
- aliases = may_aliases (var);
+ if (!*visited)
+ *visited = BITMAP_ALLOC (NULL);
- /* Case 1: |aliases| == 1 */
- if (aliases
- && bitmap_single_bit_set_p (aliases))
+ bitmap_set_bit (*visited, SSA_NAME_VERSION (PHI_RESULT (phi)));
+
+ /* Walk until we hit the target. */
+ while (vuse != target)
{
- tree ali = referenced_var (bitmap_first_set_bit (aliases));
- if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG)
- return ali;
+ gimple def_stmt = SSA_NAME_DEF_STMT (vuse);
+ /* Recurse for PHI nodes. */
+ if (gimple_code (def_stmt) == GIMPLE_PHI)
+ {
+ /* An already visited PHI node ends the walk successfully. */
+ if (bitmap_bit_p (*visited, SSA_NAME_VERSION (PHI_RESULT (def_stmt))))
+ return true;
+ vuse = get_continuation_for_phi (def_stmt, ref, visited);
+ if (!vuse)
+ return false;
+ continue;
+ }
+ /* A clobbering statement or the end of the IL ends it failing. */
+ else if (gimple_nop_p (def_stmt)
+ || stmt_may_clobber_ref_p (def_stmt, ref))
+ return false;
+ vuse = gimple_vuse (def_stmt);
}
+ return true;
+}
- /* Case 2: |aliases| == 0 */
- if (aliases == NULL)
- add_may_alias (tag, var);
- else
+/* Starting from a PHI node for the virtual operand of the memory reference
+ REF find a continuation virtual operand that allows to continue walking
+ statements dominating PHI skipping only statements that cannot possibly
+ clobber REF. Returns NULL_TREE if no suitable virtual operand can
+ be found. */
+
+static tree
+get_continuation_for_phi (gimple phi, tree ref, bitmap *visited)
+{
+ unsigned nargs = gimple_phi_num_args (phi);
+
+ /* Through a single-argument PHI we can simply look through. */
+ if (nargs == 1)
+ return PHI_ARG_DEF (phi, 0);
+
+ /* For two arguments try to skip non-aliasing code until we hit
+ the phi argument definition that dominates the other one. */
+ if (nargs == 2)
{
- /* Case 3: |aliases| > 1 */
- union_alias_set_into (tag, aliases);
+ tree arg0 = PHI_ARG_DEF (phi, 0);
+ tree arg1 = PHI_ARG_DEF (phi, 1);
+ gimple def0 = SSA_NAME_DEF_STMT (arg0);
+ gimple def1 = SSA_NAME_DEF_STMT (arg1);
+
+ if (arg0 == arg1)
+ return arg0;
+ else if (gimple_nop_p (def0)
+ || (!gimple_nop_p (def1)
+ && dominated_by_p (CDI_DOMINATORS,
+ gimple_bb (def1), gimple_bb (def0))))
+ {
+ if (maybe_skip_until (phi, arg0, ref, arg1, visited))
+ return arg0;
+ }
+ else if (gimple_nop_p (def1)
+ || dominated_by_p (CDI_DOMINATORS,
+ gimple_bb (def0), gimple_bb (def1)))
+ {
+ if (maybe_skip_until (phi, arg1, ref, arg0, visited))
+ return arg1;
+ }
}
- return tag;
+
+ return NULL_TREE;
}
-/* Create a new symbol tag for PTR. Construct the may-alias list of
- this type tag so that it has the aliasing of VAR according to the
- location accessed by EXPR.
+/* Based on the memory reference REF and its virtual use VUSE call
+ WALKER for each virtual use that is equivalent to VUSE, including VUSE
+ itself. That is, for each virtual use for which its defining statement
+ does not clobber REF.
- Note, the set of aliases represented by the new symbol tag are not
- marked for renaming. */
+ WALKER is called with REF, the current virtual use and DATA. If
+ WALKER returns non-NULL the walk stops and its result is returned.
+ At the end of a non-successful walk NULL is returned.
-void
-new_type_alias (tree ptr, tree var, tree expr)
+ TODO: Cache the vector of equivalent vuses per ref, vuse pair. */
+
+void *
+walk_non_aliased_vuses (tree ref, tree vuse,
+ void *(*walker)(tree, tree, void *), void *data)
{
- tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
- tree tag;
- tree ali = NULL_TREE;
- HOST_WIDE_INT offset, size, maxsize;
- tree ref;
+ bitmap visited = NULL;
+ void *res;
+
+ timevar_push (TV_ALIAS_STMT_WALK);
+
+ do
+ {
+ gimple def_stmt;
- gcc_assert (symbol_mem_tag (ptr) == NULL_TREE);
- gcc_assert (!MTAG_P (var));
+ /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
+ res = (*walker) (ref, vuse, data);
+ if (res)
+ break;
- ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
- gcc_assert (ref);
+ def_stmt = SSA_NAME_DEF_STMT (vuse);
+ if (gimple_nop_p (def_stmt))
+ break;
+ else if (gimple_code (def_stmt) == GIMPLE_PHI)
+ vuse = get_continuation_for_phi (def_stmt, ref, &visited);
+ else
+ {
+ if (stmt_may_clobber_ref_p (def_stmt, ref))
+ break;
+ vuse = gimple_vuse (def_stmt);
+ }
+ }
+ while (vuse);
- tag = create_memory_tag (tag_type, true);
- set_symbol_mem_tag (ptr, tag);
+ if (visited)
+ BITMAP_FREE (visited);
- ali = add_may_alias_for_new_tag (tag, var);
+ timevar_pop (TV_ALIAS_STMT_WALK);
- set_symbol_mem_tag (ptr, ali);
- MTAG_GLOBAL (tag) = is_global_var (var);
+ return res;
}
-/* Reset the call_clobbered flags on our referenced vars. In
- theory, this only needs to be done for globals. */
+/* Based on the memory reference REF call WALKER for each vdef which
+ defining statement may clobber REF, starting with VDEF. If REF
+ is NULL_TREE, each defining statement is visited.
+
+ WALKER is called with REF, the current vdef and DATA. If WALKER
+ returns true the walk is stopped, otherwise it continues.
+
+ At PHI nodes walk_aliased_vdefs forks into one walk for reach
+ PHI argument (but only one walk continues on merge points), the
+ return value is true if any of the walks was successful.
+
+ The function returns the number of statements walked. */
static unsigned int
-reset_cc_flags (void)
+walk_aliased_vdefs_1 (tree ref, tree vdef,
+ bool (*walker)(tree, tree, void *), void *data,
+ bitmap *visited, unsigned int cnt)
{
- tree var;
- referenced_var_iterator rvi;
+ do
+ {
+ gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
- FOR_EACH_REFERENCED_VAR (var, rvi)
- var_ann (var)->call_clobbered = false;
- return 0;
+ if (*visited
+ && !bitmap_set_bit (*visited, SSA_NAME_VERSION (vdef)))
+ return cnt;
+
+ if (gimple_nop_p (def_stmt))
+ return cnt;
+ else if (gimple_code (def_stmt) == GIMPLE_PHI)
+ {
+ unsigned i;
+ if (!*visited)
+ *visited = BITMAP_ALLOC (NULL);
+ for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
+ cnt += walk_aliased_vdefs_1 (ref, gimple_phi_arg_def (def_stmt, i),
+ walker, data, visited, 0);
+ return cnt;
+ }
+
+ /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */
+ cnt++;
+ if ((!ref
+ || stmt_may_clobber_ref_p (def_stmt, ref))
+ && (*walker) (ref, vdef, data))
+ return cnt;
+
+ vdef = gimple_vuse (def_stmt);
+ }
+ while (1);
}
-struct gimple_opt_pass pass_reset_cc_flags =
-{
- {
- GIMPLE_PASS,
- NULL, /* name */
- NULL, /* gate */
- reset_cc_flags, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- 0, /* tv_id */
- PROP_referenced_vars |PROP_cfg, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- 0 /* todo_flags_finish */
- }
-};
-
-
-/* A dummy pass to cause aliases to be computed via TODO_rebuild_alias. */
-
-struct gimple_opt_pass pass_build_alias =
+unsigned int
+walk_aliased_vdefs (tree ref, tree vdef,
+ bool (*walker)(tree, tree, void *), void *data,
+ bitmap *visited)
{
- {
- GIMPLE_PASS,
- "alias", /* name */
- NULL, /* gate */
- NULL, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- 0, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- PROP_alias, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */
- }
-};
+ bitmap local_visited = NULL;
+ unsigned int ret;
+
+ timevar_push (TV_ALIAS_STMT_WALK);
+
+ ret = walk_aliased_vdefs_1 (ref, vdef, walker, data,
+ visited ? visited : &local_visited, 0);
+ if (local_visited)
+ BITMAP_FREE (local_visited);
+
+ timevar_pop (TV_ALIAS_STMT_WALK);
+
+ return ret;
+}
+
OSDN Git Service
