+
+/* 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. */