-/* 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. */
- {
- block_stmt_iterator bsi;
- basic_block bb;
- FOR_EACH_BB (bb)
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- update_stmt_if_modified (bsi_stmt (bsi));
- }
-
- /* 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);
- }
-
- /* Report strict aliasing violations. */
- strict_aliasing_warning_backend ();
-
- /* 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 count;
-};
-
-
-/* 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 count_ptr_d *count_p = (struct count_ptr_d *) data;
-
- /* 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)
- count_p->count++;
-
- 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, tree 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 (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
- || (TREE_CODE (stmt) == RETURN_EXPR
- && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
- || TREE_CODE (stmt) == ASM_EXPR
- || TREE_CODE (stmt) == CALL_EXPR)
- {
- tree lhs, rhs;
-
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
- {
- lhs = GIMPLE_STMT_OPERAND (stmt, 0);
- rhs = GIMPLE_STMT_OPERAND (stmt, 1);
- }
- else if (TREE_CODE (stmt) == RETURN_EXPR)
- {
- tree e = TREE_OPERAND (stmt, 0);
- lhs = GIMPLE_STMT_OPERAND (e, 0);
- rhs = GIMPLE_STMT_OPERAND (e, 1);
- }
- else if (TREE_CODE (stmt) == ASM_EXPR)
- {
- lhs = ASM_OUTPUTS (stmt);
- rhs = ASM_INPUTS (stmt);
- }
- else
- {
- lhs = NULL_TREE;
- rhs = stmt;
- }
-
- if (lhs
- && (TREE_CODE (lhs) == TREE_LIST
- || EXPR_P (lhs)
- || GIMPLE_STMT_P (lhs)))
- {
- struct count_ptr_d count;
- count.ptr = ptr;
- count.count = 0;
- walk_tree (&lhs, count_ptr_derefs, &count, NULL);
- *num_stores_p = count.count;
- }
-
- if (rhs
- && (TREE_CODE (rhs) == TREE_LIST
- || EXPR_P (rhs)
- || GIMPLE_STMT_P (rhs)))
- {
- struct count_ptr_d count;
- count.ptr = ptr;
- count.count = 0;
- walk_tree (&rhs, count_ptr_derefs, &count, NULL);
- *num_loads_p = count.count;
- }
- }
-
- 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;
-
- 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->written_vars = pointer_set_create ();
- ai->dereferenced_ptrs_store = pointer_set_create ();
- ai->dereferenced_ptrs_load = 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.elements != NULL)
- bitmap_obstack_release (&alias_bitmap_obstack);
- bitmap_obstack_initialize (&alias_bitmap_obstack);
-
- 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->written_vars);
- pointer_set_destroy (ai->dereferenced_ptrs_store);
- pointer_set_destroy (ai->dereferenced_ptrs_load);
- 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)
-{
-
- /* 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;
- bool tag_stored_p, var_stored_p;
-
- v_map = ai->addressable_vars[j];
- var = v_map->var;
- v_ann = var_ann (var);
-
- /* Skip memory tags and variables that have never been
- written to. We also need to check if the variables are
- call-clobbered because they may be overwritten by
- function calls. */
- tag_stored_p = pointer_set_contains (ai->written_vars, tag)
- || is_call_clobbered (tag);
- var_stored_p = pointer_set_contains (ai->written_vars, var)
- || is_call_clobbered (var);
- if (!tag_stored_p && !var_stored_p)
- continue;
-
- 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 (tree 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 = addresses_taken (stmt);
- if (addr_taken)
- bitmap_ior_into (gimple_addressable_vars (cfun), addr_taken);
-
- /* 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 (TREE_CODE (stmt) == PHI_NODE);
- 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));
-
- /* 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 (TREE_CODE (stmt) == PHI_NODE)
- continue;
-
- /* Determine whether OP is a dereferenced pointer, and if STMT
- is an escape point, whether OP escapes. */
- count_uses_and_derefs (op, stmt, &num_uses, &num_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 (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
- && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ADDR_EXPR
- && !is_gimple_val (GIMPLE_STMT_OPERAND (stmt, 1)))
- {
- /* If the RHS if of the form &PTR->FLD and PTR == OP, then
- this represents a potential dereference of PTR. */
- tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
- tree base = get_base_address (TREE_OPERAND (rhs, 0));
- if (TREE_CODE (base) == INDIRECT_REF
- && TREE_OPERAND (base, 0) == op)
- num_loads++;
- }
-
- 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;
-
- /* ??? For always executed direct dereferences we can
- apply TBAA-pruning to their escape set. */
-
- /* If this is a store operation, mark OP as being
- dereferenced to store, otherwise mark it as being
- dereferenced to load. */
- if (num_stores > 0)
- pointer_set_insert (ai->dereferenced_ptrs_store, var);
- else
- pointer_set_insert (ai->dereferenced_ptrs_load, var);
-
- /* Update the frequency estimate for all the dereferences of
- pointer OP. */
- update_mem_sym_stats_from_stmt (op, stmt, num_loads, num_stores);
-
- /* Indicate that STMT contains pointer dereferences. */
- stmt_dereferences_ptr_p = true;
- }
-
- 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 (get_call_expr_in (stmt)
- || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
- {
- pointer_set_insert (ai->dereferenced_ptrs_store, var);
- pi->memory_tag_needed = 1;
- }
- }
- }
-
- if (TREE_CODE (stmt) == PHI_NODE)
- return;
-
- /* Mark stored variables in STMT as being written to and update the
- memory reference stats for all memory symbols referenced by STMT. */
- if (stmt_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 (STORED_SYMS (stmt))
- EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi)
- {
- tree sym = referenced_var (i);
- pointer_set_insert (ai->written_vars, sym);
- if (!stmt_dereferences_ptr_p
- && stmt_escape_type != ESCAPE_TO_CALL
- && stmt_escape_type != ESCAPE_TO_PURE_CONST
- && stmt_escape_type != ESCAPE_TO_ASM)
- update_mem_sym_stats_from_stmt (sym, stmt, 0, 1);
- }
-
- if (!stmt_dereferences_ptr_p
- && LOADED_SYMS (stmt)
- && stmt_escape_type != ESCAPE_TO_CALL
- && stmt_escape_type != ESCAPE_TO_PURE_CONST
- && stmt_escape_type != ESCAPE_TO_ASM)
- EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt), 0, i, bi)
- update_mem_sym_stats_from_stmt (referenced_var (i), stmt, 1, 0);
- }
-}
-
-/* Update various related attributes like escaped addresses,
- pointer dereferences for loads and stores. This is used
- when creating name tags and alias sets. */
-
-static void
-update_alias_info (struct alias_info *ai)
-{
- basic_block bb;
-
- FOR_EACH_BB (bb)
- {
- block_stmt_iterator bsi;
- tree phi;
-
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- if (is_gimple_reg (PHI_RESULT (phi)))
- update_alias_info_1 (phi, ai);
-
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- update_alias_info_1 (bsi_stmt (bsi), ai);
- }
-}
-
-/* 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. */
-
-static void
-setup_pointers_and_addressables (struct alias_info *ai)
-{
- 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_store, 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_store, var)
- || pointer_set_contains (ai->dereferenced_ptrs_load, 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);
-
- /* If pointer VAR has been used in a store operation,
- then its memory tag must be marked as written-to. */
- if (pointer_set_contains (ai->dereferenced_ptrs_store, var))
- pointer_set_insert (ai->written_vars, 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);
- }
- }
- }
- }
-
- VEC_free (tree, heap, varvec);
-}
-
-
-/* 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. */
-
-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 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)
-{
- 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 either MEM or VAR is a read-only global and the other one
- isn't, then PTR cannot point to VAR. */
- if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var))
- || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem)))
- {
- 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
- && 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;
- }
- }
- }
-
- alias_stats.alias_mayalias++;
- return true;
-}
-
-/* Return true, if PTR may point to a global variable. */