| /* Alias analysis for trees. |
| Copyright (C) 2004, 2005 Free Software Foundation, Inc. |
| Contributed by Diego Novillo <dnovillo@redhat.com> |
| |
| This file is part of GCC. |
| |
| GCC is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 2, or (at your option) |
| any later version. |
| |
| GCC is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING. If not, write to |
| the Free Software Foundation, 51 Franklin Street, Fifth Floor, |
| Boston, MA 02110-1301, USA. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "tm.h" |
| #include "tree.h" |
| #include "rtl.h" |
| #include "tm_p.h" |
| #include "hard-reg-set.h" |
| #include "basic-block.h" |
| #include "timevar.h" |
| #include "expr.h" |
| #include "ggc.h" |
| #include "langhooks.h" |
| #include "flags.h" |
| #include "function.h" |
| #include "diagnostic.h" |
| #include "tree-dump.h" |
| #include "tree-gimple.h" |
| #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 "vec.h" |
| #include "bitmap.h" |
| #include "vecprim.h" |
| #include "pointer-set.h" |
| |
| /* Obstack used to hold grouping bitmaps and other temporary bitmaps used by |
| aliasing */ |
| static bitmap_obstack alias_obstack; |
| |
| /* 'true' after aliases have been computed (see compute_may_aliases). */ |
| bool aliases_computed_p; |
| |
| /* Structure to map a variable to its alias set and keep track of the |
| virtual operands that will be needed to represent it. */ |
| struct alias_map_d |
| { |
| /* Variable and its alias set. */ |
| tree var; |
| HOST_WIDE_INT set; |
| |
| /* Total number of virtual operands that will be needed to represent |
| all the aliases of VAR. */ |
| long total_alias_vops; |
| |
| /* Nonzero if the aliases for this memory tag have been grouped |
| already. Used in group_aliases. */ |
| unsigned int grouped_p : 1; |
| |
| /* Set of variables aliased with VAR. This is the exact same |
| information contained in VAR_ANN (VAR)->MAY_ALIASES, but in |
| bitmap form to speed up alias grouping. */ |
| bitmap may_aliases; |
| }; |
| |
| |
| /* 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; |
| |
| /* Local functions. */ |
| static void compute_flow_insensitive_aliasing (struct alias_info *); |
| static void finalize_ref_all_pointers (struct alias_info *); |
| static void dump_alias_stats (FILE *); |
| static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT, bool); |
| static tree create_memory_tag (tree type, bool is_type_tag); |
| static tree get_tmt_for (tree, struct alias_info *); |
| static tree get_nmt_for (tree); |
| static void add_may_alias (tree, tree); |
| static void replace_may_alias (tree, size_t, tree); |
| static struct alias_info *init_alias_info (void); |
| static void delete_alias_info (struct alias_info *); |
| static void compute_flow_sensitive_aliasing (struct alias_info *); |
| static void setup_pointers_and_addressables (struct alias_info *); |
| static void create_global_var (void); |
| static void maybe_create_global_var (struct alias_info *ai); |
| static void group_aliases (struct alias_info *); |
| static void set_pt_anything (tree ptr); |
| |
| /* Global declarations. */ |
| |
| /* Call clobbered variables in the function. If bit I is set, then |
| REFERENCED_VARS (I) is call-clobbered. */ |
| bitmap call_clobbered_vars; |
| |
| /* Addressable variables in the function. If bit I is set, then |
| REFERENCED_VARS (I) has had its address taken. Note that |
| CALL_CLOBBERED_VARS and ADDRESSABLE_VARS are not related. An |
| addressable variable is not necessarily call-clobbered (e.g., a |
| local addressable whose address does not escape) and not all |
| call-clobbered variables are addressable (e.g., a local static |
| variable). */ |
| bitmap addressable_vars; |
| |
| /* When the program has too many call-clobbered variables and call-sites, |
| this variable is used to represent the clobbering effects of function |
| calls. In these cases, all the call clobbered variables in the program |
| are forced to alias this variable. This reduces compile times by not |
| having to keep track of too many V_MAY_DEF expressions at call sites. */ |
| tree global_var; |
| |
| /* qsort comparison function to sort type/name tags by DECL_UID. */ |
| |
| static int |
| sort_tags_by_id (const void *pa, const void *pb) |
| { |
| tree a = *(tree *)pa; |
| tree b = *(tree *)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) |
| { |
| 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); |
| } |
| } |
| } |
| |
| /* 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) |
| { |
| if (MTAG_P (alias) && !is_call_clobbered (alias)) |
| { |
| VEC_safe_push (tree, heap, *worklist, alias); |
| VEC_safe_push (int, heap, *worklist2, reason); |
| } |
| } |
| |
| /* 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) |
| { |
| unsigned int i; |
| VEC (tree, gc) *ma; |
| tree entry; |
| var_ann_t ta = var_ann (tag); |
| |
| if (!MTAG_P (tag)) |
| return; |
| ma = may_aliases (tag); |
| if (!ma) |
| return; |
| |
| for (i = 0; VEC_iterate (tree, ma, i, entry); i++) |
| { |
| if (!unmodifiable_var_p (entry)) |
| { |
| add_to_worklist (entry, worklist, worklist2, ta->escape_mask); |
| 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) || TREE_CODE (tag) == STRUCT_FIELD_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++) |
| { |
| VEC (tree, gc) *ma; |
| 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; |
| |
| for (i = 0; VEC_iterate (tree, ma, i, entry); 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 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; |
| |
| FOR_EACH_REFERENCED_VAR (var, rvi) |
| { |
| if (is_global_var (var) |
| && (!var_can_have_subvars (var) |
| || get_subvars_for_var (var) == NULL)) |
| { |
| if (!unmodifiable_var_p (var)) |
| mark_call_clobbered (var, ESCAPE_IS_GLOBAL); |
| } |
| else if (TREE_CODE (var) == PARM_DECL |
| && default_def (var) |
| && POINTER_TYPE_P (TREE_TYPE (var))) |
| { |
| tree def = default_def (var); |
| get_ptr_info (def)->value_escapes_p = 1; |
| get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM; |
| } |
| } |
| |
| for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++) |
| { |
| struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); |
| var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr)); |
| |
| if (pi->value_escapes_p) |
| { |
| /* 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 (v_ann->symbol_mem_tag) |
| mark_call_clobbered (v_ann->symbol_mem_tag, pi->escape_mask); |
| |
| if (pi->pt_vars) |
| { |
| bitmap_iterator bi; |
| unsigned int j; |
| EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi) |
| if (!unmodifiable_var_p (referenced_var (j))) |
| mark_call_clobbered (referenced_var (j), 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 |
| && v_ann->symbol_mem_tag |
| && is_call_clobbered (pi->name_mem_tag)) |
| mark_call_clobbered (v_ann->symbol_mem_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->is_dereferenced && 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->is_dereferenced |
| && v_ann->symbol_mem_tag) |
| { |
| mark_call_clobbered (v_ann->symbol_mem_tag, ESCAPE_IS_GLOBAL); |
| MTAG_GLOBAL (v_ann->symbol_mem_tag) = true; |
| } |
| } |
| } |
| |
| |
| /* This variable is set to true if we are updating the used alone |
| information for SMTs, or are in a pass that is going to break it |
| temporarily. */ |
| bool updating_used_alone; |
| |
| /* 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; |
| |
| set_initial_properties (ai); |
| init_transitive_clobber_worklist (&worklist, &worklist2); |
| while (VEC_length (tree, worklist) != 0) |
| { |
| tree curr = VEC_pop (tree, worklist); |
| int reason = VEC_pop (int, worklist2); |
| |
| mark_call_clobbered (curr, reason); |
| mark_aliases_call_clobbered (curr, &worklist, &worklist2); |
| } |
| VEC_free (tree, heap, worklist); |
| VEC_free (int, heap, worklist2); |
| compute_tag_properties (); |
| } |
| |
| |
| /* Helper for recalculate_used_alone. Return a conservatively correct |
| answer as to whether STMT may make a store on the LHS to SYM. */ |
| |
| static bool |
| lhs_may_store_to (tree stmt, tree sym ATTRIBUTE_UNUSED) |
| { |
| tree lhs = TREE_OPERAND (stmt, 0); |
| |
| lhs = get_base_address (lhs); |
| |
| if (!lhs) |
| return false; |
| |
| if (TREE_CODE (lhs) == SSA_NAME) |
| return false; |
| /* We could do better here by looking at the type tag of LHS, but it |
| is unclear whether this is worth it. */ |
| return true; |
| } |
| |
| /* Recalculate the used_alone information for SMTs . */ |
| |
| void |
| recalculate_used_alone (void) |
| { |
| VEC (tree, heap) *calls = NULL; |
| block_stmt_iterator bsi; |
| basic_block bb; |
| tree stmt; |
| size_t i; |
| referenced_var_iterator rvi; |
| tree var; |
| |
| /* First, reset all the SMT used alone bits to zero. */ |
| updating_used_alone = true; |
| FOR_EACH_REFERENCED_VAR (var, rvi) |
| if (TREE_CODE (var) == SYMBOL_MEMORY_TAG) |
| { |
| SMT_OLD_USED_ALONE (var) = SMT_USED_ALONE (var); |
| SMT_USED_ALONE (var) = 0; |
| } |
| |
| /* Walk all the statements. |
| Calls get put into a list of statements to update, since we will |
| need to update operands on them if we make any changes. |
| If we see a bare use of a SMT anywhere in a real virtual use or virtual |
| def, mark the SMT as used alone, and for renaming. */ |
| FOR_EACH_BB (bb) |
| { |
| for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) |
| { |
| bool iscall = false; |
| ssa_op_iter iter; |
| |
| stmt = bsi_stmt (bsi); |
| |
| if (TREE_CODE (stmt) == CALL_EXPR |
| || (TREE_CODE (stmt) == MODIFY_EXPR |
| && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)) |
| { |
| iscall = true; |
| VEC_safe_push (tree, heap, calls, stmt); |
| } |
| |
| FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, |
| SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS) |
| { |
| tree svar = var; |
| |
| if (TREE_CODE (var) == SSA_NAME) |
| svar = SSA_NAME_VAR (var); |
| |
| if (TREE_CODE (svar) == SYMBOL_MEMORY_TAG) |
| { |
| /* We only care about the LHS on calls. */ |
| if (iscall && !lhs_may_store_to (stmt, svar)) |
| continue; |
| |
| if (!SMT_USED_ALONE (svar)) |
| { |
| SMT_USED_ALONE (svar) = true; |
| |
| /* Only need to mark for renaming if it wasn't |
| used alone before. */ |
| if (!SMT_OLD_USED_ALONE (svar)) |
| mark_sym_for_renaming (svar); |
| } |
| } |
| } |
| } |
| } |
| |
| /* Update the operands on all the calls we saw. */ |
| if (calls) |
| { |
| for (i = 0; VEC_iterate (tree, calls, i, stmt); i++) |
| update_stmt (stmt); |
| } |
| |
| /* We need to mark SMT's that are no longer used for renaming so the |
| symbols go away, or else verification will be angry with us, even |
| though they are dead. */ |
| FOR_EACH_REFERENCED_VAR (var, rvi) |
| if (TREE_CODE (var) == SYMBOL_MEMORY_TAG) |
| { |
| if (SMT_OLD_USED_ALONE (var) && !SMT_USED_ALONE (var)) |
| mark_sym_for_renaming (var); |
| } |
| |
| VEC_free (tree, heap, calls); |
| updating_used_alone = false; |
| } |
| |
| /* 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 = V_MAY_DEF <a_3>; |
| # b_8 = V_MAY_DEF <b_5>; |
| *p_1 = 3; |
| |
| # a_9 = V_MAY_DEF <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}), alias sets are grouped to avoid severe |
| compile-time slow downs and memory consumption. See group_aliases. */ |
| |
| static unsigned int |
| compute_may_aliases (void) |
| { |
| struct alias_info *ai; |
| |
| 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 (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 flow-sensitive, points-to based aliasing for all the name |
| memory tags. Note that this pass needs to be done before flow |
| insensitive analysis because it uses the points-to information |
| gathered before to mark call-clobbered symbol tags. */ |
| compute_flow_sensitive_aliasing (ai); |
| |
| /* Compute type-based flow-insensitive aliasing for all the type |
| memory tags. */ |
| compute_flow_insensitive_aliasing (ai); |
| |
| /* Compute call clobbering information. */ |
| compute_call_clobbered (ai); |
| |
| /* Determine if we need to enable alias grouping. */ |
| if (ai->total_alias_vops >= MAX_ALIASED_VOPS) |
| group_aliases (ai); |
| |
| /* If the program has too many call-clobbered variables and/or function |
| calls, create .GLOBAL_VAR and use it to model call-clobbering |
| semantics at call sites. This reduces the number of virtual operands |
| considerably, improving compile times at the expense of lost |
| aliasing precision. */ |
| maybe_create_global_var (ai); |
| |
| /* If the program contains ref-all pointers, finalize may-alias information |
| for them. This pass needs to be run after call-clobbering information |
| has been computed. */ |
| if (ai->ref_all_symbol_mem_tag) |
| finalize_ref_all_pointers (ai); |
| |
| /* Debugging dumps. */ |
| if (dump_file) |
| { |
| dump_referenced_vars (dump_file); |
| if (dump_flags & TDF_STATS) |
| dump_alias_stats (dump_file); |
| dump_points_to_info (dump_file); |
| dump_alias_info (dump_file); |
| } |
| |
| /* Deallocate memory used by aliasing data structures. */ |
| delete_alias_info (ai); |
| |
| updating_used_alone = true; |
| { |
| 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)); |
| } |
| } |
| } |
| recalculate_used_alone (); |
| updating_used_alone = false; |
| return 0; |
| } |
| |
| |
| struct tree_opt_pass pass_may_alias = |
| { |
| "alias", /* name */ |
| NULL, /* gate */ |
| compute_may_aliases, /* execute */ |
| NULL, /* sub */ |
| NULL, /* next */ |
| 0, /* static_pass_number */ |
| TV_TREE_MAY_ALIAS, /* tv_id */ |
| PROP_cfg | PROP_ssa, /* properties_required */ |
| PROP_alias, /* properties_provided */ |
| 0, /* properties_destroyed */ |
| 0, /* todo_flags_start */ |
| TODO_dump_func | TODO_update_ssa |
| | TODO_ggc_collect | TODO_verify_ssa |
| | TODO_verify_stmts, /* todo_flags_finish */ |
| 0 /* letter */ |
| }; |
| |
| |
| /* 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 two counts are stored in *NUM_USES_P and |
| *NUM_DEREFS_P respectively. *IS_STORE_P is set to 'true' if at |
| least one of those dereferences is a store operation. */ |
| |
| void |
| count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p, |
| unsigned *num_derefs_p, bool *is_store) |
| { |
| ssa_op_iter i; |
| tree use; |
| |
| *num_uses_p = 0; |
| *num_derefs_p = 0; |
| *is_store = false; |
| |
| /* 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) == MODIFY_EXPR |
| || (TREE_CODE (stmt) == RETURN_EXPR |
| && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) |
| || TREE_CODE (stmt) == ASM_EXPR |
| || TREE_CODE (stmt) == CALL_EXPR) |
| { |
| tree lhs, rhs; |
| |
| if (TREE_CODE (stmt) == MODIFY_EXPR) |
| { |
| lhs = TREE_OPERAND (stmt, 0); |
| rhs = TREE_OPERAND (stmt, 1); |
| } |
| else if (TREE_CODE (stmt) == RETURN_EXPR) |
| { |
| tree e = TREE_OPERAND (stmt, 0); |
| lhs = TREE_OPERAND (e, 0); |
| rhs = TREE_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))) |
| { |
| struct count_ptr_d count; |
| count.ptr = ptr; |
| count.count = 0; |
| walk_tree (&lhs, count_ptr_derefs, &count, NULL); |
| *is_store = true; |
| *num_derefs_p = count.count; |
| } |
| |
| if (rhs && (TREE_CODE (rhs) == TREE_LIST || EXPR_P (rhs))) |
| { |
| struct count_ptr_d count; |
| count.ptr = ptr; |
| count.count = 0; |
| walk_tree (&rhs, count_ptr_derefs, &count, NULL); |
| *num_derefs_p += count.count; |
| } |
| } |
| |
| gcc_assert (*num_uses_p >= *num_derefs_p); |
| } |
| |
| /* 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; |
| |
| bitmap_obstack_initialize (&alias_obstack); |
| 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 = BITMAP_ALLOC (&alias_obstack); |
| ai->dereferenced_ptrs_store = BITMAP_ALLOC (&alias_obstack); |
| ai->dereferenced_ptrs_load = BITMAP_ALLOC (&alias_obstack); |
| |
| /* If aliases have been computed before, clear existing information. */ |
| if (aliases_computed_p) |
| { |
| unsigned i; |
| |
| /* Similarly, clear the set of addressable variables. In this |
| case, we can just clear the set because addressability is |
| only computed here. */ |
| bitmap_clear (addressable_vars); |
| |
| /* Clear flow-insensitive alias information from each symbol. */ |
| FOR_EACH_REFERENCED_VAR (var, rvi) |
| { |
| var_ann_t ann = var_ann (var); |
| |
| ann->is_aliased = 0; |
| ann->may_aliases = NULL; |
| NUM_REFERENCES_CLEAR (ann); |
| |
| /* Since we are about to re-discover call-clobbered |
| variables, clear the call-clobbered flag. Variables that |
| are intrinsically call-clobbered (globals, local statics, |
| etc) will not be marked by the aliasing code, so we can't |
| remove them from CALL_CLOBBERED_VARS. |
| |
| NB: STRUCT_FIELDS are still call clobbered if they are for |
| a global variable, so we *don't* clear their call clobberedness |
| just because they are tags, though we will clear it if they |
| aren't for global variables. */ |
| if (TREE_CODE (var) == NAME_MEMORY_TAG |
| || TREE_CODE (var) == SYMBOL_MEMORY_TAG |
| || !is_global_var (var)) |
| clear_call_clobbered (var); |
| } |
| |
| /* 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->is_dereferenced = 0; |
| if (pi->pt_vars) |
| bitmap_clear (pi->pt_vars); |
| } |
| } |
| } |
| |
| /* Next time, we will need to reset alias information. */ |
| aliases_computed_p = true; |
| |
| return ai; |
| } |
| |
| |
| /* Deallocate memory used by alias analysis. */ |
| |
| static void |
| delete_alias_info (struct alias_info *ai) |
| { |
| size_t i; |
| referenced_var_iterator rvi; |
| tree var; |
| |
| 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]); |
| |
| FOR_EACH_REFERENCED_VAR(var, rvi) |
| { |
| var_ann_t ann = var_ann (var); |
| NUM_REFERENCES_CLEAR (ann); |
| } |
| |
| free (ai->addressable_vars); |
| |
| for (i = 0; i < ai->num_pointers; i++) |
| free (ai->pointers[i]); |
| free (ai->pointers); |
| |
| BITMAP_FREE (ai->written_vars); |
| BITMAP_FREE (ai->dereferenced_ptrs_store); |
| BITMAP_FREE (ai->dereferenced_ptrs_load); |
| bitmap_obstack_release (&alias_obstack); |
| free (ai); |
| |
| 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->is_dereferenced) |
| { |
| /* 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); |
| |
| TREE_THIS_VOLATILE (pi->name_mem_tag) |
| |= TREE_THIS_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); |
| } |
| |
| |
| /* 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; |
| |
| 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++) |
| { |
| unsigned j; |
| struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); |
| var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr)); |
| bitmap_iterator bi; |
| |
| |
| /* 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) |
| EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi) |
| { |
| add_may_alias (pi->name_mem_tag, referenced_var (j)); |
| add_may_alias (v_ann->symbol_mem_tag, referenced_var (j)); |
| } |
| } |
| } |
| |
| |
| /* 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 alias tag so that the operand scanner knows that statements |
| containing V have aliased operands. */ |
| |
| static void |
| compute_flow_insensitive_aliasing (struct alias_info *ai) |
| { |
| size_t i; |
| |
| /* Initialize counter for the total number of virtual operands that |
| aliasing will introduce. When AI->TOTAL_ALIAS_VOPS goes beyond the |
| threshold set by --params max-alias-vops, we enable alias |
| grouping. */ |
| ai->total_alias_vops = 0; |
| |
| /* 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 = var_ann (p_map->var)->symbol_mem_tag; |
| var_ann_t tag_ann = var_ann (tag); |
| tree var; |
| |
| /* Call-clobbering information is not finalized yet at this point. */ |
| if (PTR_IS_REF_ALL (p_map->var)) |
| continue; |
| |
| p_map->total_alias_vops = 0; |
| p_map->may_aliases = BITMAP_ALLOC (&alias_obstack); |
| |
| /* Add any pre-existing may_aliases to the bitmap used to represent |
| TAG's alias set in case we need to group aliases. */ |
| for (j = 0; VEC_iterate (tree, tag_ann->may_aliases, j, var); ++j) |
| bitmap_set_bit (p_map->may_aliases, DECL_UID (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. |
| |
| Note this is effectively random accessing elements in |
| the sparse bitset, which can be highly inefficient. |
| So we first check the call_clobbered status of the |
| tag and variable before querying the bitmap. */ |
| tag_stored_p = is_call_clobbered (tag) |
| || bitmap_bit_p (ai->written_vars, DECL_UID (tag)); |
| var_stored_p = is_call_clobbered (var) |
| || bitmap_bit_p (ai->written_vars, DECL_UID (var)); |
| if (!tag_stored_p && !var_stored_p) |
| continue; |
| |
| if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false)) |
| { |
| size_t num_tag_refs, num_var_refs; |
| |
| num_tag_refs = NUM_REFERENCES (tag_ann); |
| num_var_refs = NUM_REFERENCES (v_ann); |
| |
| /* Add VAR to TAG's may-aliases set. */ |
| |
| /* We should never have a var with subvars here, because |
| they shouldn't get into the set of addressable vars */ |
| gcc_assert (!var_can_have_subvars (var) |
| || get_subvars_for_var (var) == NULL); |
| |
| add_may_alias (tag, var); |
| /* Update the bitmap used to represent TAG's alias set |
| in case we need to group aliases. */ |
| bitmap_set_bit (p_map->may_aliases, DECL_UID (var)); |
| |
| /* Update the total number of virtual operands due to |
| aliasing. Since we are adding one more alias to TAG's |
| may-aliases set, the total number of virtual operands due |
| to aliasing will be increased by the number of references |
| made to VAR and TAG (every reference to TAG will also |
| count as a reference to VAR). */ |
| ai->total_alias_vops += (num_var_refs + num_tag_refs); |
| p_map->total_alias_vops += (num_var_refs + num_tag_refs); |
| |
| |
| } |
| } |
| } |
| |
| /* 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 = var_ann (p_map1->var)->symbol_mem_tag; |
| bitmap may_aliases1 = p_map1->may_aliases; |
| |
| if (PTR_IS_REF_ALL (p_map1->var)) |
| continue; |
| |
| for (j = i + 1; j < ai->num_pointers; j++) |
| { |
| struct alias_map_d *p_map2 = ai->pointers[j]; |
| tree tag2 = var_ann (p_map2->var)->symbol_mem_tag; |
| bitmap may_aliases2 = p_map2->may_aliases; |
| |
| if (PTR_IS_REF_ALL (p_map2->var)) |
| 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 (bitmap_intersect_p (may_aliases1, may_aliases2)) |
| continue; |
| |
| if (!bitmap_empty_p (may_aliases2)) |
| { |
| unsigned int k; |
| bitmap_iterator bi; |
| |
| /* Add all the aliases for TAG2 into TAG1's alias set. |
| FIXME, update grouping heuristic counters. */ |
| EXECUTE_IF_SET_IN_BITMAP (may_aliases2, 0, k, bi) |
| add_may_alias (tag1, referenced_var (k)); |
| bitmap_ior_into (may_aliases1, may_aliases2); |
| } |
| else |
| { |
| /* Since TAG2 does not have any aliases of its own, add |
| TAG2 itself to the alias set of TAG1. */ |
| add_may_alias (tag1, tag2); |
| bitmap_set_bit (may_aliases1, DECL_UID (tag2)); |
| } |
| } |
| } |
| |
| if (dump_file) |
| fprintf (dump_file, "\n%s: Total number of aliased vops: %ld\n", |
| get_name (current_function_decl), |
| ai->total_alias_vops); |
| } |
| |
| |
| /* Finalize may-alias information for ref-all pointers. Traverse all |
| the addressable variables found in setup_pointers_and_addressables. |
| |
| If flow-sensitive alias analysis has attached a name memory tag to |
| a ref-all pointer, we will use it for the dereferences because that |
| will have more precise aliasing information. But if there is no |
| name tag, we will use a special symbol tag that aliases all the |
| call-clobbered addressable variables. */ |
| |
| static void |
| finalize_ref_all_pointers (struct alias_info *ai) |
| { |
| size_t i; |
| |
| if (global_var) |
| add_may_alias (ai->ref_all_symbol_mem_tag, global_var); |
| else |
| { |
| /* First add the real call-clobbered variables. */ |
| for (i = 0; i < ai->num_addressable_vars; i++) |
| { |
| tree var = ai->addressable_vars[i]->var; |
| if (is_call_clobbered (var)) |
| add_may_alias (ai->ref_all_symbol_mem_tag, var); |
| } |
| |
| /* Then add the call-clobbered pointer memory tags. See |
| compute_flow_insensitive_aliasing for the rationale. */ |
| for (i = 0; i < ai->num_pointers; i++) |
| { |
| tree ptr = ai->pointers[i]->var, tag; |
| if (PTR_IS_REF_ALL (ptr)) |
| continue; |
| tag = var_ann (ptr)->symbol_mem_tag; |
| if (is_call_clobbered (tag)) |
| add_may_alias (ai->ref_all_symbol_mem_tag, tag); |
| } |
| } |
| } |
| |
| |
| /* Comparison function for qsort used in group_aliases. */ |
| |
| static int |
| total_alias_vops_cmp (const void *p, const void *q) |
| { |
| const struct alias_map_d **p1 = (const struct alias_map_d **)p; |
| const struct alias_map_d **p2 = (const struct alias_map_d **)q; |
| long n1 = (*p1)->total_alias_vops; |
| long n2 = (*p2)->total_alias_vops; |
| |
| /* We want to sort in descending order. */ |
| return (n1 > n2 ? -1 : (n1 == n2) ? 0 : 1); |
| } |
| |
| /* Group all the aliases for TAG to make TAG represent all the |
| variables in its alias set. Update the total number |
| of virtual operands due to aliasing (AI->TOTAL_ALIAS_VOPS). This |
| function will make TAG be the unique alias tag for all the |
| variables in its may-aliases. So, given: |
| |
| may-aliases(TAG) = { V1, V2, V3 } |
| |
| This function will group the variables into: |
| |
| may-aliases(V1) = { TAG } |
| may-aliases(V2) = { TAG } |
| may-aliases(V2) = { TAG } */ |
| |
| static void |
| group_aliases_into (tree tag, bitmap tag_aliases, struct alias_info *ai) |
| { |
| unsigned int i; |
| var_ann_t tag_ann = var_ann (tag); |
| size_t num_tag_refs = NUM_REFERENCES (tag_ann); |
| bitmap_iterator bi; |
| |
| EXECUTE_IF_SET_IN_BITMAP (tag_aliases, 0, i, bi) |
| { |
| tree var = referenced_var (i); |
| var_ann_t ann = var_ann (var); |
| |
| /* Make TAG the unique alias of VAR. */ |
| ann->is_aliased = 0; |
| ann->may_aliases = NULL; |
| |
| /* Note that VAR and TAG may be the same if the function has no |
| addressable variables (see the discussion at the end of |
| setup_pointers_and_addressables). */ |
| if (var != tag) |
| add_may_alias (var, tag); |
| |
| /* Reduce total number of virtual operands contributed |
| by TAG on behalf of VAR. Notice that the references to VAR |
| itself won't be removed. We will merely replace them with |
| references to TAG. */ |
| ai->total_alias_vops -= num_tag_refs; |
| } |
| |
| /* We have reduced the number of virtual operands that TAG makes on |
| behalf of all the variables formerly aliased with it. However, |
| we have also "removed" all the virtual operands for TAG itself, |
| so we add them back. */ |
| ai->total_alias_vops += num_tag_refs; |
| |
| /* TAG no longer has any aliases. */ |
| tag_ann->may_aliases = NULL; |
| } |
| |
| |
| /* Group may-aliases sets to reduce the number of virtual operands due |
| to aliasing. |
| |
| 1- Sort the list of pointers in decreasing number of contributed |
| virtual operands. |
| |
| 2- Take the first entry in AI->POINTERS and revert the role of |
| the memory tag and its aliases. Usually, whenever an aliased |
| variable Vi is found to alias with a memory tag T, we add Vi |
| to the may-aliases set for T. Meaning that after alias |
| analysis, we will have: |
| |
| may-aliases(T) = { V1, V2, V3, ..., Vn } |
| |
| This means that every statement that references T, will get 'n' |
| virtual operands for each of the Vi tags. But, when alias |
| grouping is enabled, we make T an alias tag and add it to the |
| alias set of all the Vi variables: |
| |
| may-aliases(V1) = { T } |
| may-aliases(V2) = { T } |
| ... |
| may-aliases(Vn) = { T } |
| |
| This has two effects: (a) statements referencing T will only get |
| a single virtual operand, and, (b) all the variables Vi will now |
| appear to alias each other. So, we lose alias precision to |
| improve compile time. But, in theory, a program with such a high |
| level of aliasing should not be very optimizable in the first |
| place. |
| |
| 3- Since variables may be in the alias set of more than one |
| memory tag, the grouping done in step (2) needs to be extended |
| to all the memory tags that have a non-empty intersection with |
| the may-aliases set of tag T. For instance, if we originally |
| had these may-aliases sets: |
| |
| may-aliases(T) = { V1, V2, V3 } |
| may-aliases(R) = { V2, V4 } |
| |
| In step (2) we would have reverted the aliases for T as: |
| |
| may-aliases(V1) = { T } |
| may-aliases(V2) = { T } |
| may-aliases(V3) = { T } |
| |
| But note that now V2 is no longer aliased with R. We could |
| add R to may-aliases(V2), but we are in the process of |
| grouping aliases to reduce virtual operands so what we do is |
| add V4 to the grouping to obtain: |
| |
| may-aliases(V1) = { T } |
| may-aliases(V2) = { T } |
| may-aliases(V3) = { T } |
| may-aliases(V4) = { T } |
| |
| 4- If the total number of virtual operands due to aliasing is |
| still above the threshold set by max-alias-vops, go back to (2). */ |
| |
| static void |
| group_aliases (struct alias_info *ai) |
| { |
| size_t i; |
| tree ptr; |
| /* APPLE LOCAL 6070085 */ |
| bool more; |
| |
| /* Sort the POINTERS array in descending order of contributed |
| virtual operands. */ |
| qsort (ai->pointers, ai->num_pointers, sizeof (struct alias_map_d *), |
| total_alias_vops_cmp); |
| |
| /* For every pointer in AI->POINTERS, reverse the roles of its tag |
| and the tag's may-aliases set. */ |
| for (i = 0; i < ai->num_pointers; i++) |
| { |
| size_t j; |
| tree tag1 = var_ann (ai->pointers[i]->var)->symbol_mem_tag; |
| bitmap tag1_aliases = ai->pointers[i]->may_aliases; |
| |
| /* Skip tags that have been grouped already. */ |
| if (ai->pointers[i]->grouped_p) |
| continue; |
| |
| /* See if TAG1 had any aliases in common with other symbol tags. |
| If we find a TAG2 with common aliases with TAG1, add TAG2's |
| aliases into TAG1. */ |
| /* APPLE LOCAL begin 6070085 */ |
| do { |
| /* Repeat alias merging until changes converge. */ |
| more = false; |
| for (j = i + 1; j < ai->num_pointers; j++) |
| { |
| bitmap tag2_aliases; |
| |
| if (ai->pointers[j]->grouped_p) |
| continue; |
| |
| tag2_aliases = ai->pointers[j]->may_aliases; |
| |
| if (bitmap_intersect_p (tag1_aliases, tag2_aliases)) |
| { |
| tree tag2 = var_ann (ai->pointers[j]->var)->symbol_mem_tag; |
| |
| bitmap_ior_into (tag1_aliases, tag2_aliases); |
| |
| /* TAG2 does not need its aliases anymore. */ |
| bitmap_clear (tag2_aliases); |
| var_ann (tag2)->may_aliases = NULL; |
| |
| /* TAG1 is the unique alias of TAG2. */ |
| add_may_alias (tag2, tag1); |
| |
| ai->pointers[j]->grouped_p = true; |
| more = true; |
| } |
| } |
| } while (more); |
| /* APPLE LOCAL end 6070085 */ |
| |
| /* Now group all the aliases we collected into TAG1. */ |
| group_aliases_into (tag1, tag1_aliases, ai); |
| |
| /* If we've reduced total number of virtual operands below the |
| threshold, stop. */ |
| if (ai->total_alias_vops < MAX_ALIASED_VOPS) |
| break; |
| } |
| |
| /* Finally, all the variables that have been grouped cannot be in |
| the may-alias set of name memory tags. Suppose that we have |
| grouped the aliases in this code so that may-aliases(a) = SMT.20 |
| |
| p_5 = &a; |
| ... |
| # a_9 = V_MAY_DEF <a_8> |
| p_5->field = 0 |
| ... Several modifications to SMT.20 ... |
| # VUSE <a_9> |
| x_30 = p_5->field |
| |
| Since p_5 points to 'a', the optimizers will try to propagate 0 |
| into p_5->field, but that is wrong because there have been |
| modifications to 'SMT.20' in between. To prevent this we have to |
| replace 'a' with 'SMT.20' in the name tag of p_5. */ |
| for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++) |
| { |
| size_t j; |
| tree name_tag = SSA_NAME_PTR_INFO (ptr)->name_mem_tag; |
| VEC(tree,gc) *aliases; |
| tree alias; |
| |
| if (name_tag == NULL_TREE) |
| continue; |
| |
| aliases = var_ann (name_tag)->may_aliases; |
| for (j = 0; VEC_iterate (tree, aliases, j, alias); j++) |
| { |
| var_ann_t ann = var_ann (alias); |
| |
| if ((!MTAG_P (alias) |
| || TREE_CODE (alias) == STRUCT_FIELD_TAG) |
| && ann->may_aliases) |
| { |
| tree new_alias; |
| |
| gcc_assert (VEC_length (tree, ann->may_aliases) == 1); |
| |
| new_alias = VEC_index (tree, ann->may_aliases, 0); |
| replace_may_alias (name_tag, j, new_alias); |
| } |
| } |
| } |
| |
| if (dump_file) |
| fprintf (dump_file, |
| "%s: Total number of aliased vops after grouping: %ld%s\n", |
| get_name (current_function_decl), |
| ai->total_alias_vops, |
| (ai->total_alias_vops < 0) ? " (negative values are OK)" : ""); |
| } |
| |
| |
| /* 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; |
| } |
| |
| |
| /* 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 n_vars, 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)) |
| bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (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; |
| |
| /* Since we will be creating symbol memory tags within this loop, |
| cache the value of NUM_REFERENCED_VARS to avoid processing the |
| additional tags unnecessarily. */ |
| n_vars = num_referenced_vars; |
| |
| FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi) |
| { |
| var_ann_t v_ann = var_ann (var); |
| subvar_t svars; |
| |
| /* 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) && TREE_CODE (var) != STRUCT_FIELD_TAG) |
| 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 (addressable_vars, 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); |
| |
| /* If VAR can have sub-variables, and any of its |
| sub-variables has its address taken, then we cannot |
| remove the addressable flag from VAR. */ |
| if (var_can_have_subvars (var) |
| && (svars = get_subvars_for_var (var))) |
| { |
| subvar_t sv; |
| |
| for (sv = svars; sv; sv = sv->next) |
| { |
| if (bitmap_bit_p (addressable_vars, DECL_UID (sv->var))) |
| okay_to_mark = false; |
| mark_sym_for_renaming (sv->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) |
| 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) |
| && (!var_can_have_subvars (var) |
| || get_subvars_for_var (var) == NULL)) |
| { |
| 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 ((bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var)) |
| || bitmap_bit_p (ai->dereferenced_ptrs_load, DECL_UID (var)))) |
| { |
| tree 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_tmt_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_tmt_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. */ |
| if (v_ann->symbol_mem_tag) |
| mark_sym_for_renaming (v_ann->symbol_mem_tag); |
| |
| /* Associate the tag with pointer VAR. */ |
| v_ann->symbol_mem_tag = tag; |
| |
| /* If pointer VAR has been used in a store operation, |
| then its memory tag must be marked as written-to. */ |
| if (bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var))) |
| bitmap_set_bit (ai->written_vars, DECL_UID (tag)); |
| |
| /* All the dereferences of pointer VAR count as |
| references of TAG. Since TAG can be associated with |
| several pointers, add the dereferences of VAR to the |
| TAG. */ |
| NUM_REFERENCES_SET (t_ann, |
| NUM_REFERENCES (t_ann) |
| + NUM_REFERENCES (v_ann)); |
| } |
| 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. */ |
| var_ann_t ann = var_ann (var); |
| tree tag = ann->symbol_mem_tag; |
| if (tag) |
| { |
| mark_sym_for_renaming (tag); |
| ann->symbol_mem_tag = NULL_TREE; |
| } |
| } |
| } |
| } |
| VEC_free (tree, heap, varvec); |
| } |
| |
| |
| /* Determine whether to use .GLOBAL_VAR to model call clobbering semantics. At |
| every call site, we need to emit V_MAY_DEF expressions to represent the |
| clobbering effects of the call for variables whose address escapes the |
| current function. |
| |
| One approach is to group all call-clobbered variables into a single |
| representative that is used as an alias of every call-clobbered variable |
| (.GLOBAL_VAR). This works well, but it ties the optimizer hands because |
| references to any call clobbered variable is a reference to .GLOBAL_VAR. |
| |
| The second approach is to emit a clobbering V_MAY_DEF for every |
| call-clobbered variable at call sites. This is the preferred way in terms |
| of optimization opportunities but it may create too many V_MAY_DEF operands |
| if there are many call clobbered variables and function calls in the |
| function. |
| |
| To decide whether or not to use .GLOBAL_VAR we multiply the number of |
| function calls found by the number of call-clobbered variables. If that |
| product is beyond a certain threshold, as determined by the parameterized |
| values shown below, we use .GLOBAL_VAR. |
| |
| FIXME. This heuristic should be improved. One idea is to use several |
| .GLOBAL_VARs of different types instead of a single one. The thresholds |
| have been derived from a typical bootstrap cycle, including all target |
| libraries. Compile times were found increase by ~1% compared to using |
| .GLOBAL_VAR. */ |
| |
| static void |
| maybe_create_global_var (struct alias_info *ai) |
| { |
| unsigned i, n_clobbered; |
| bitmap_iterator bi; |
| |
| /* No need to create it, if we have one already. */ |
| if (global_var == NULL_TREE) |
| { |
| /* Count all the call-clobbered variables. */ |
| n_clobbered = 0; |
| EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) |
| { |
| n_clobbered++; |
| } |
| |
| /* If the number of virtual operands that would be needed to |
| model all the call-clobbered variables is larger than |
| GLOBAL_VAR_THRESHOLD, create .GLOBAL_VAR. |
| |
| Also 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 (ai->num_calls_found * n_clobbered >= (size_t) GLOBAL_VAR_THRESHOLD |
| || (n_clobbered == 0 |
| && ai->num_calls_found > 0 |
| && ai->num_pure_const_calls_found > 0 |
| && ai->num_calls_found > ai->num_pure_const_calls_found)) |
| create_global_var (); |
| } |
| |
| /* Mark all call-clobbered symbols for renaming. Since the initial |
| rewrite into SSA ignored all call sites, we may need to rename |
| .GLOBAL_VAR and the call-clobbered variables. */ |
| EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) |
| { |
| tree var = referenced_var (i); |
| |
| /* If the function has calls to clobbering functions and |
| .GLOBAL_VAR has been created, make it an alias for all |
| call-clobbered variables. */ |
| if (global_var && var != global_var) |
| { |
| add_may_alias (var, global_var); |
| gcc_assert (!get_subvars_for_var (var)); |
| } |
| |
| mark_sym_for_renaming (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. */ |
| |
| static bool |
| may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set, |
| tree var, HOST_WIDE_INT 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 = var_ann (ptr)->symbol_mem_tag; |
| 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; |
| } |
| |
| 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 (!alias_sets_conflict_p (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 operation explicit address operation in the |
| program that can reference a field of the ptr's dereferenced |
| type. 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 to |
| 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; |
| } |
| |
| |
| /* Add ALIAS to the set of variables that may alias VAR. */ |
| |
| static void |
| add_may_alias (tree var, tree alias) |
| { |
| size_t i; |
| var_ann_t v_ann = get_var_ann (var); |
| var_ann_t a_ann = get_var_ann (alias); |
| tree al; |
| |
| /* Don't allow self-referential aliases. */ |
| gcc_assert (var != alias); |
| |
| /* ALIAS must be addressable if it's being added to an alias set. */ |
| #if 1 |
| TREE_ADDRESSABLE (alias) = 1; |
| #else |
| gcc_assert (may_be_aliased (alias)); |
| #endif |
| |
| if (v_ann->may_aliases == NULL) |
| v_ann->may_aliases = VEC_alloc (tree, gc, 2); |
| |
| /* Avoid adding duplicates. */ |
| for (i = 0; VEC_iterate (tree, v_ann->may_aliases, i, al); i++) |
| if (alias == al) |
| return; |
| |
| VEC_safe_push (tree, gc, v_ann->may_aliases, alias); |
| a_ann->is_aliased = 1; |
| } |
| |
| |
| /* Replace alias I in the alias sets of VAR with NEW_ALIAS. */ |
| |
| static void |
| replace_may_alias (tree var, size_t i, tree new_alias) |
| { |
| var_ann_t v_ann = var_ann (var); |
| VEC_replace (tree, v_ann->may_aliases, i, new_alias); |
| } |
| |
| |
| /* Mark pointer PTR as pointing to an arbitrary memory location. */ |
| |
| static void |
| set_pt_anything (tree ptr) |
| { |
| struct ptr_info_def *pi = get_ptr_info (ptr); |
| |
| pi->pt_anything = 1; |
| pi->pt_vars = NULL; |
| |
| /* The pointer used to have a name tag, but we now found it pointing |
| to an arbitrary location. The name tag needs to be renamed and |
| disassociated from PTR. */ |
| if (pi->name_mem_tag) |
| { |
| mark_sym_for_renaming (pi->name_mem_tag); |
| pi->name_mem_tag = NULL_TREE; |
| } |
| } |
| |
| |
| /* 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: |
| |
| 1- STMT is a function call, or |
| 2- STMT is an __asm__ expression, or |
| 3- STMT is an assignment to a non-local variable, or |
| 4- STMT is a return statement. |
| |
| Return the type of escape site found, if we found one, or NO_ESCAPE |
| if none. */ |
| |
| enum escape_type |
| is_escape_site (tree stmt) |
| { |
| tree call = get_call_expr_in (stmt); |
| if (call != NULL_TREE) |
| { |
| if (!TREE_SIDE_EFFECTS (call)) |
| return ESCAPE_TO_PURE_CONST; |
| |
| return ESCAPE_TO_CALL; |
| } |
| else if (TREE_CODE (stmt) == ASM_EXPR) |
| return ESCAPE_TO_ASM; |
| else if (TREE_CODE (stmt) == MODIFY_EXPR) |
| { |
| tree lhs = TREE_OPERAND (stmt, 0); |
| |
| /* Get to the base of _REF nodes. */ |
| if (TREE_CODE (lhs) != SSA_NAME) |
| lhs = get_base_address (lhs); |
| |
| /* If we couldn't recognize the LHS of the assignment, assume that it |
| is a non-local store. */ |
| if (lhs == NULL_TREE) |
| return ESCAPE_UNKNOWN; |
| |
| if (TREE_CODE (TREE_OPERAND (stmt, 1)) == NOP_EXPR |
| || TREE_CODE (TREE_OPERAND (stmt, 1)) == CONVERT_EXPR |
| || TREE_CODE (TREE_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR) |
| { |
| tree from = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (stmt, 1), 0)); |
| tree to = TREE_TYPE (TREE_OPERAND (stmt, 1)); |
| |
| /* 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; |
| |
| /* Same if the RHS is a conversion between a regular pointer and a |
| ref-all pointer since we can't track the SMT of the former. */ |
| if (POINTER_TYPE_P (from) && !TYPE_REF_CAN_ALIAS_ALL (from) |
| && POINTER_TYPE_P (to) && TYPE_REF_CAN_ALIAS_ALL (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; |
| |
| /* 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 (TREE_CODE (stmt) == RETURN_EXPR) |
| return ESCAPE_TO_RETURN; |
| |
| return NO_ESCAPE; |
| } |
| |
| /* Create a new memory tag of type TYPE. |
| Does NOT push it into the current binding. */ |
| |
| static tree |
| create_tag_raw (enum tree_code code, tree type, const char *prefix) |
| { |
| tree tmp_var; |
| tree new_type; |
| |
| /* Make the type of the variable writable. */ |
| new_type = build_type_variant (type, 0, 0); |
| TYPE_ATTRIBUTES (new_type) = TYPE_ATTRIBUTES (type); |
| |
| tmp_var = build_decl (code, create_tmp_var_name (prefix), |
| type); |
| /* Make the variable writable. */ |
| TREE_READONLY (tmp_var) = 0; |
| |
| /* It doesn't start out global. */ |
| MTAG_GLOBAL (tmp_var) = 0; |
| TREE_STATIC (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) |
| { |
| var_ann_t ann; |
| 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; |
| |
| ann = get_var_ann (tag); |
| ann->symbol_mem_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_tmt_for (tree ptr, struct alias_info *ai) |
| { |
| size_t i; |
| tree tag; |
| tree tag_type = TREE_TYPE (TREE_TYPE (ptr)); |
| HOST_WIDE_INT tag_set = get_alias_set (tag_type); |
| |
| /* We use a unique memory tag for all the ref-all pointers. */ |
| if (PTR_IS_REF_ALL (ptr)) |
| { |
| if (!ai->ref_all_symbol_mem_tag) |
| ai->ref_all_symbol_mem_tag = create_memory_tag (void_type_node, true); |
| return ai->ref_all_symbol_mem_tag; |
| } |
| |
| /* 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 = var_ann (curr->var)->symbol_mem_tag; |
| 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. */ |
| if (var_ann (ptr)->symbol_mem_tag == NULL_TREE) |
| tag = create_memory_tag (tag_type, true); |
| else |
| tag = var_ann (ptr)->symbol_mem_tag; |
| |
| /* 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. */ |
| gcc_assert (tag_set == get_alias_set (tag)); |
| |
| return tag; |
| } |
| |
| |
| /* Create GLOBAL_VAR, an artificial global variable to act as a |
| representative of all the variables that may be clobbered by function |
| calls. */ |
| |
| static void |
| create_global_var (void) |
| { |
| 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); |
| } |
| |
| |
| /* Dump alias statistics on FILE. */ |
| |
| 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); |
| } |
| |
| |
| /* Dump alias information on FILE. */ |
| |
| void |
| dump_alias_info (FILE *file) |
| { |
| size_t i; |
| const char *funcname |
| = lang_hooks.decl_printable_name (current_function_decl, 2); |
| referenced_var_iterator rvi; |
| tree var; |
| |
| fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname); |
| |
| fprintf (file, "Aliased symbols\n\n"); |
| |
| FOR_EACH_REFERENCED_VAR (var, rvi) |
| { |
| if (may_be_aliased (var)) |
| dump_variable (file, var); |
| } |
| |
| fprintf (file, "\nDereferenced pointers\n\n"); |
| |
| FOR_EACH_REFERENCED_VAR (var, rvi) |
| { |
| var_ann_t ann = var_ann (var); |
| if (ann->symbol_mem_tag) |
| 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, "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) |
| continue; |
| |
| pi = SSA_NAME_PTR_INFO (ptr); |
| if (!SSA_NAME_IN_FREE_LIST (ptr) |
| && pi |
| && pi->name_mem_tag) |
| 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"); |
| } |
| |
| |
| /* Dump alias information on stderr. */ |
| |
| void |
| debug_alias_info (void) |
| { |
| dump_alias_info (stderr); |
| } |
| |
| |
| /* Return the alias information associated with pointer T. It creates a |
| new instance if none existed. */ |
| |
| struct ptr_info_def * |
| get_ptr_info (tree t) |
| { |
| struct ptr_info_def *pi; |
| |
| gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); |
| |
| pi = SSA_NAME_PTR_INFO (t); |
| if (pi == NULL) |
| { |
| pi = GGC_NEW (struct ptr_info_def); |
| memset ((void *)pi, 0, sizeof (*pi)); |
| SSA_NAME_PTR_INFO (t) = pi; |
| } |
| |
| return pi; |
| } |
| |
| |
| /* Dump points-to information for SSA_NAME PTR into FILE. */ |
| |
| void |
| dump_points_to_info_for (FILE *file, tree ptr) |
| { |
| struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); |
| |
| print_generic_expr (file, ptr, dump_flags); |
| |
| 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"); |
| |
| if (pi->value_escapes_p) |
| fprintf (file, ", its value escapes"); |
| |
| if (pi->pt_anything) |
| fprintf (file, ", points-to anything"); |
| |
| if (pi->pt_null) |
| fprintf (file, ", points-to NULL"); |
| |
| if (pi->pt_vars) |
| { |
| unsigned ix; |
| bitmap_iterator bi; |
| |
| fprintf (file, ", points-to vars: { "); |
| EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi) |
| { |
| print_generic_expr (file, referenced_var (ix), dump_flags); |
| fprintf (file, " "); |
| } |
| fprintf (file, "}"); |
| } |
| } |
| |
| fprintf (file, "\n"); |
| } |
| |
| |
| /* Dump points-to information for VAR into stderr. */ |
| |
| void |
| debug_points_to_info_for (tree var) |
| { |
| dump_points_to_info_for (stderr, var); |
| } |
| |
| |
| /* Dump points-to information into FILE. NOTE: This function is slow, as |
| it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */ |
| |
| void |
| dump_points_to_info (FILE *file) |
| { |
| basic_block bb; |
| block_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; |
| |
| fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname); |
| |
| /* 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 (POINTER_TYPE_P (TREE_TYPE (var))) |
| { |
| tree def = default_def (var); |
| if (def) |
| dump_points_to_info_for (file, def); |
| } |
| } |
| |
| /* Dump points-to information for every pointer defined in the program. */ |
| FOR_EACH_BB (bb) |
| { |
| tree phi; |
| |
| for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
| { |
| tree ptr = PHI_RESULT (phi); |
| if (POINTER_TYPE_P (TREE_TYPE (ptr))) |
| dump_points_to_info_for (file, ptr); |
| } |
| |
| for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) |
| { |
| tree stmt = bsi_stmt (si); |
| tree def; |
| FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) |
| if (POINTER_TYPE_P (TREE_TYPE (def))) |
| dump_points_to_info_for (file, def); |
| } |
| } |
| |
| fprintf (file, "\n"); |
| } |
| |
| |
| /* Dump points-to info pointed to by PTO into STDERR. */ |
| |
| void |
| debug_points_to_info (void) |
| { |
| dump_points_to_info (stderr); |
| } |
| |
| /* Dump to FILE the list of variables that may be aliasing VAR. */ |
| |
| void |
| dump_may_aliases_for (FILE *file, tree var) |
| { |
| VEC(tree, gc) *aliases; |
| |
| if (TREE_CODE (var) == SSA_NAME) |
| var = SSA_NAME_VAR (var); |
| |
| aliases = var_ann (var)->may_aliases; |
| if (aliases) |
| { |
| size_t i; |
| tree al; |
| fprintf (file, "{ "); |
| for (i = 0; VEC_iterate (tree, aliases, i, al); i++) |
| { |
| print_generic_expr (file, al, dump_flags); |
| fprintf (file, " "); |
| } |
| fprintf (file, "}"); |
| } |
| } |
| |
| |
| /* Dump to stderr the list of variables that may be aliasing VAR. */ |
| |
| void |
| debug_may_aliases_for (tree var) |
| { |
| dump_may_aliases_for (stderr, var); |
| } |
| |
| /* Return true if VAR may be aliased. */ |
| |
| bool |
| may_be_aliased (tree var) |
| { |
| /* Obviously. */ |
| if (TREE_ADDRESSABLE (var)) |
| return true; |
| |
| /* Globally visible variables can have their addresses taken by other |
| translation units. */ |
| |
| if (MTAG_P (var) |
| && (MTAG_GLOBAL (var) || TREE_PUBLIC (var))) |
| return true; |
| else if (!MTAG_P (var) |
| && (DECL_EXTERNAL (var) || TREE_PUBLIC (var))) |
| 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; |
| |
| /* If we're in unit-at-a-time mode, then we must have seen all occurrences |
| of address-of operators, and so we can trust TREE_ADDRESSABLE. Otherwise |
| we can only be sure the variable isn't addressable if it's local to the |
| current function. */ |
| if (flag_unit_at_a_time) |
| return false; |
| if (decl_function_context (var) == current_function_decl) |
| return false; |
| |
| return true; |
| } |
| |
| |
| /* Given two symbols return TRUE if one is in the alias set of the other. */ |
| bool |
| is_aliased_with (tree tag, tree sym) |
| { |
| size_t i; |
| VEC(tree,gc) *aliases; |
| tree al; |
| |
| if (var_ann (sym)->is_aliased) |
| { |
| aliases = var_ann (tag)->may_aliases; |
| |
| if (aliases == NULL) |
| return false; |
| |
| for (i = 0; VEC_iterate (tree, aliases, i, al); i++) |
| if (al == sym) |
| return true; |
| } |
| else |
| { |
| aliases = var_ann (sym)->may_aliases; |
| |
| if (aliases == NULL) |
| return false; |
| |
| for (i = 0; VEC_iterate (tree, aliases, i, al); i++) |
| if (al == tag) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| |
| /* Given two tags return TRUE if their may-alias sets intersect. */ |
| |
| bool |
| may_aliases_intersect (tree tag1, tree tag2) |
| { |
| struct pointer_set_t *set1 = pointer_set_create (); |
| unsigned i; |
| VEC(tree,gc) *may_aliases1 = may_aliases (tag1); |
| VEC(tree,gc) *may_aliases2 = may_aliases (tag2); |
| tree sym; |
| |
| /* Insert all the symbols from the first may-alias set into the |
| pointer-set. */ |
| for (i = 0; VEC_iterate (tree, may_aliases1, i, sym); i++) |
| pointer_set_insert (set1, sym); |
| |
| /* Go through the second may-alias set and check if it contains symbols that |
| are common with the first set. */ |
| for (i = 0; VEC_iterate (tree, may_aliases2, i, sym); i++) |
| if (pointer_set_contains (set1, sym)) |
| { |
| pointer_set_destroy (set1); |
| return true; |
| } |
| |
| pointer_set_destroy (set1); |
| 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 |
| add_may_alias_for_new_tag (tree tag, tree var) |
| { |
| var_ann_t v_ann = var_ann (var); |
| VEC(tree, gc) *aliases = v_ann->may_aliases; |
| |
| /* Case 1: |aliases| == 1 */ |
| if ((aliases != NULL) |
| && (VEC_length (tree, aliases) == 1)) |
| { |
| tree ali = VEC_index (tree, aliases, 0); |
| |
| if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG) |
| return ali; |
| } |
| |
| /* Case 2: |aliases| == 0 */ |
| if (aliases == NULL) |
| add_may_alias (tag, var); |
| else |
| { |
| /* Case 3: |aliases| > 1 */ |
| unsigned i; |
| tree al; |
| |
| for (i = 0; VEC_iterate (tree, aliases, i, al); i++) |
| add_may_alias (tag, al); |
| } |
| |
| return tag; |
| } |
| |
| /* Create a new symbol tag for PTR. Construct the may-alias list of this type |
| tag so that it has the aliasing of VAR, or of the relevant subvars of VAR |
| according to the location accessed by EXPR. |
| |
| Note, the set of aliases represented by the new symbol tag are not marked |
| for renaming. */ |
| |
| void |
| new_type_alias (tree ptr, tree var, tree expr) |
| { |
| var_ann_t p_ann = var_ann (ptr); |
| tree tag_type = TREE_TYPE (TREE_TYPE (ptr)); |
| tree tag; |
| subvar_t svars; |
| tree ali = NULL_TREE; |
| HOST_WIDE_INT offset, size, maxsize; |
| tree ref; |
| |
| gcc_assert (p_ann->symbol_mem_tag == NULL_TREE); |
| gcc_assert (!MTAG_P (var)); |
| |
| ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize); |
| gcc_assert (ref); |
| |
| tag = create_memory_tag (tag_type, true); |
| p_ann->symbol_mem_tag = tag; |
| |
| /* Add VAR to the may-alias set of PTR's new symbol tag. If VAR has |
| subvars, add the subvars to the tag instead of the actual var. */ |
| if (var_can_have_subvars (var) |
| && (svars = get_subvars_for_var (var))) |
| { |
| subvar_t sv; |
| VEC (tree, heap) *overlaps = NULL; |
| unsigned int len; |
| |
| for (sv = svars; sv; sv = sv->next) |
| { |
| bool exact; |
| |
| if (overlap_subvar (offset, maxsize, sv->var, &exact)) |
| VEC_safe_push (tree, heap, overlaps, sv->var); |
| } |
| len = VEC_length (tree, overlaps); |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, "\nnumber of overlapping subvars = %u\n", len); |
| gcc_assert (len); |
| |
| if (len == 1) |
| ali = add_may_alias_for_new_tag (tag, VEC_index (tree, overlaps, 0)); |
| else if (len > 1) |
| { |
| unsigned int k; |
| tree sv_var; |
| |
| for (k = 0; VEC_iterate (tree, overlaps, k, sv_var); k++) |
| { |
| ali = add_may_alias_for_new_tag (tag, sv_var); |
| |
| if (ali != tag) |
| { |
| /* Can happen only if 'Case 1' of add_may_alias_for_new_tag |
| took place. Since more than one svar was found, we add |
| 'ali' as one of the may_aliases of the new tag. */ |
| add_may_alias (tag, ali); |
| ali = tag; |
| } |
| } |
| } |
| } |
| else |
| ali = add_may_alias_for_new_tag (tag, var); |
| |
| p_ann->symbol_mem_tag = ali; |
| TREE_READONLY (tag) = TREE_READONLY (var); |
| MTAG_GLOBAL (tag) = is_global_var (var); |
| } |
| |
| /* This represents the used range of a variable. */ |
| |
| typedef struct used_part |
| { |
| HOST_WIDE_INT minused; |
| HOST_WIDE_INT maxused; |
| /* True if we have an explicit use/def of some portion of this variable, |
| even if it is all of it. i.e. a.b = 5 or temp = a.b. */ |
| bool explicit_uses; |
| /* True if we have an implicit use/def of some portion of this |
| variable. Implicit uses occur when we can't tell what part we |
| are referencing, and have to make conservative assumptions. */ |
| bool implicit_uses; |
| /* True if the structure is only written to or taken its address. */ |
| bool write_only; |
| } *used_part_t; |
| |
| /* An array of used_part structures, indexed by variable uid. */ |
| |
| static htab_t used_portions; |
| |
| struct used_part_map |
| { |
| unsigned int uid; |
| used_part_t to; |
| }; |
| |
| /* Return true if the uid in the two used part maps are equal. */ |
| |
| static int |
| used_part_map_eq (const void *va, const void *vb) |
| { |
| const struct used_part_map *a = (const struct used_part_map *) va; |
| const struct used_part_map *b = (const struct used_part_map *) vb; |
| return (a->uid == b->uid); |
| } |
| |
| /* Hash a from uid in a used_part_map. */ |
| |
| static unsigned int |
| used_part_map_hash (const void *item) |
| { |
| return ((const struct used_part_map *)item)->uid; |
| } |
| |
| /* Free a used part map element. */ |
| |
| static void |
| free_used_part_map (void *item) |
| { |
| free (((struct used_part_map *)item)->to); |
| free (item); |
| } |
| |
| /* Lookup a used_part structure for a UID. */ |
| |
| static used_part_t |
| up_lookup (unsigned int uid) |
| { |
| struct used_part_map *h, in; |
| in.uid = uid; |
| h = (struct used_part_map *) htab_find_with_hash (used_portions, &in, uid); |
| if (!h) |
| return NULL; |
| return h->to; |
| } |
| |
| /* Insert the pair UID, TO into the used part hashtable. */ |
| |
| static void |
| up_insert (unsigned int uid, used_part_t to) |
| { |
| struct used_part_map *h; |
| void **loc; |
| |
| h = XNEW (struct used_part_map); |
| h->uid = uid; |
| h->to = to; |
| loc = htab_find_slot_with_hash (used_portions, h, |
| uid, INSERT); |
| if (*loc != NULL) |
| free (*loc); |
| *(struct used_part_map **) loc = h; |
| } |
| |
| |
| /* Given a variable uid, UID, get or create the entry in the used portions |
| table for the variable. */ |
| |
| static used_part_t |
| get_or_create_used_part_for (size_t uid) |
| { |
| used_part_t up; |
| if ((up = up_lookup (uid)) == NULL) |
| { |
| up = XCNEW (struct used_part); |
| up->minused = INT_MAX; |
| up->maxused = 0; |
| up->explicit_uses = false; |
| up->implicit_uses = false; |
| up->write_only = true; |
| } |
| |
| return up; |
| } |
| |
| |
| /* Create and return a structure sub-variable for field type FIELD at |
| offset OFFSET, with size SIZE, of variable VAR. */ |
| |
| static tree |
| create_sft (tree var, tree field, unsigned HOST_WIDE_INT offset, |
| unsigned HOST_WIDE_INT size) |
| { |
| var_ann_t ann; |
| tree subvar = create_tag_raw (STRUCT_FIELD_TAG, field, "SFT"); |
| |
| /* We need to copy the various flags from VAR to SUBVAR, so that |
| they are is_global_var iff the original variable was. */ |
| DECL_CONTEXT (subvar) = DECL_CONTEXT (var); |
| MTAG_GLOBAL (subvar) = DECL_EXTERNAL (var); |
| TREE_PUBLIC (subvar) = TREE_PUBLIC (var); |
| TREE_STATIC (subvar) = TREE_STATIC (var); |
| TREE_READONLY (subvar) = TREE_READONLY (var); |
| TREE_ADDRESSABLE (subvar) = TREE_ADDRESSABLE (var); |
| |
| /* Add the new variable to REFERENCED_VARS. */ |
| ann = get_var_ann (subvar); |
| ann->symbol_mem_tag = NULL; |
| add_referenced_var (subvar); |
| SFT_PARENT_VAR (subvar) = var; |
| SFT_OFFSET (subvar) = offset; |
| SFT_SIZE (subvar) = size; |
| return subvar; |
| } |
| |
| |
| /* Given an aggregate VAR, create the subvariables that represent its |
| fields. */ |
| |
| static void |
| create_overlap_variables_for (tree var) |
| { |
| VEC(fieldoff_s,heap) *fieldstack = NULL; |
| used_part_t up; |
| size_t uid = DECL_UID (var); |
| |
| up = up_lookup (uid); |
| if (!up |
| || up->write_only) |
| return; |
| |
| push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL); |
| if (VEC_length (fieldoff_s, fieldstack) != 0) |
| { |
| subvar_t *subvars; |
| fieldoff_s *fo; |
| bool notokay = false; |
| int fieldcount = 0; |
| int i; |
| HOST_WIDE_INT lastfooffset = -1; |
| HOST_WIDE_INT lastfosize = -1; |
| tree lastfotype = NULL_TREE; |
| |
| /* Not all fields have DECL_SIZE set, and those that don't, we don't |
| know their size, and thus, can't handle. |
| The same is true of fields with DECL_SIZE that is not an integer |
| constant (such as variable sized fields). |
| Fields with offsets which are not constant will have an offset < 0 |
| We *could* handle fields that are constant sized arrays, but |
| currently don't. Doing so would require some extra changes to |
| tree-ssa-operands.c. */ |
| |
| for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) |
| { |
| if (!fo->size |
| || TREE_CODE (fo->size) != INTEGER_CST |
| || fo->offset < 0) |
| { |
| notokay = true; |
| break; |
| } |
| fieldcount++; |
| } |
| |
| /* The current heuristic we use is as follows: |
| If the variable has no used portions in this function, no |
| structure vars are created for it. |
| Otherwise, |
| If the variable has less than SALIAS_MAX_IMPLICIT_FIELDS, |
| we always create structure vars for them. |
| If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and |
| some explicit uses, we create structure vars for them. |
| If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and |
| no explicit uses, we do not create structure vars for them. |
| */ |
| |
| if (fieldcount >= SALIAS_MAX_IMPLICIT_FIELDS |
| && !up->explicit_uses) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Variable "); |
| print_generic_expr (dump_file, var, 0); |
| fprintf (dump_file, " has no explicit uses in this function, and is > SALIAS_MAX_IMPLICIT_FIELDS, so skipping\n"); |
| } |
| notokay = true; |
| } |
| |
| /* Bail out, if we can't create overlap variables. */ |
| if (notokay) |
| { |
| VEC_free (fieldoff_s, heap, fieldstack); |
| return; |
| } |
| |
| /* Otherwise, create the variables. */ |
| subvars = lookup_subvars_for_var (var); |
| |
| sort_fieldstack (fieldstack); |
| |
| for (i = VEC_length (fieldoff_s, fieldstack); |
| VEC_iterate (fieldoff_s, fieldstack, --i, fo);) |
| { |
| subvar_t sv; |
| HOST_WIDE_INT fosize; |
| tree currfotype; |
| |
| fosize = TREE_INT_CST_LOW (fo->size); |
| currfotype = fo->type; |
| |
| /* If this field isn't in the used portion, |
| or it has the exact same offset and size as the last |
| field, skip it. */ |
| |
| if (((fo->offset <= up->minused |
| && fo->offset + fosize <= up->minused) |
| || fo->offset >= up->maxused) |
| || (fo->offset == lastfooffset |
| && fosize == lastfosize |
| && currfotype == lastfotype)) |
| continue; |
| sv = GGC_NEW (struct subvar); |
| sv->next = *subvars; |
| sv->var = create_sft (var, fo->type, fo->offset, fosize); |
| |
| if (dump_file) |
| { |
| fprintf (dump_file, "structure field tag %s created for var %s", |
| get_name (sv->var), get_name (var)); |
| fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC, |
| SFT_OFFSET (sv->var)); |
| fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC, |
| SFT_SIZE (sv->var)); |
| fprintf (dump_file, "\n"); |
| } |
| |
| lastfotype = currfotype; |
| lastfooffset = fo->offset; |
| lastfosize = fosize; |
| *subvars = sv; |
| } |
| |
| /* Once we have created subvars, the original is no longer call |
| clobbered on its own. Its call clobbered status depends |
| completely on the call clobbered status of the subvars. |
| |
| add_referenced_var in the above loop will take care of |
| marking subvars of global variables as call clobbered for us |
| to start, since they are global as well. */ |
| clear_call_clobbered (var); |
| } |
| |
| VEC_free (fieldoff_s, heap, fieldstack); |
| } |
| |
| |
| /* Find the conservative answer to the question of what portions of what |
| structures are used by this statement. We assume that if we have a |
| component ref with a known size + offset, that we only need that part |
| of the structure. For unknown cases, or cases where we do something |
| to the whole structure, we assume we need to create fields for the |
| entire structure. */ |
| |
| static tree |
| find_used_portions (tree *tp, int *walk_subtrees, void *lhs_p) |
| { |
| switch (TREE_CODE (*tp)) |
| { |
| case MODIFY_EXPR: |
| /* Recurse manually here to track whether the use is in the |
| LHS of an assignment. */ |
| find_used_portions (&TREE_OPERAND (*tp, 0), walk_subtrees, tp); |
| return find_used_portions (&TREE_OPERAND (*tp, 1), walk_subtrees, NULL); |
| case REALPART_EXPR: |
| case IMAGPART_EXPR: |
| case COMPONENT_REF: |
| case ARRAY_REF: |
| { |
| HOST_WIDE_INT bitsize; |
| HOST_WIDE_INT bitmaxsize; |
| HOST_WIDE_INT bitpos; |
| tree ref; |
| ref = get_ref_base_and_extent (*tp, &bitpos, &bitsize, &bitmaxsize); |
| if (DECL_P (ref) |
| && var_can_have_subvars (ref) |
| && bitmaxsize != -1) |
| { |
| size_t uid = DECL_UID (ref); |
| used_part_t up; |
| |
| up = get_or_create_used_part_for (uid); |
| |
| if (bitpos <= up->minused) |
| up->minused = bitpos; |
| if ((bitpos + bitmaxsize >= up->maxused)) |
| up->maxused = bitpos + bitmaxsize; |
| |
| if (bitsize == bitmaxsize) |
| up->explicit_uses = true; |
| else |
| up->implicit_uses = true; |
| if (!lhs_p) |
| up->write_only = false; |
| up_insert (uid, up); |
| |
| *walk_subtrees = 0; |
| return NULL_TREE; |
| } |
| } |
| break; |
| /* This is here to make sure we mark the entire base variable as used |
| when you take its address. Because our used portion analysis is |
| simple, we aren't looking at casts or pointer arithmetic to see what |
| happens when you take the address. */ |
| case ADDR_EXPR: |
| { |
| tree var = get_base_address (TREE_OPERAND (*tp, 0)); |
| |
| if (var |
| && DECL_P (var) |
| && DECL_SIZE (var) |
| && var_can_have_subvars (var) |
| && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST) |
| { |
| used_part_t up; |
| size_t uid = DECL_UID (var); |
| |
| up = get_or_create_used_part_for (uid); |
| |
| up->minused = 0; |
| up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var)); |
| up->implicit_uses = true; |
| if (!lhs_p) |
| up->write_only = false; |
| |
| up_insert (uid, up); |
| *walk_subtrees = 0; |
| return NULL_TREE; |
| } |
| } |
| break; |
| case CALL_EXPR: |
| { |
| tree *arg; |
| for (arg = &TREE_OPERAND (*tp, 1); *arg; arg = &TREE_CHAIN (*arg)) |
| { |
| if (TREE_CODE (TREE_VALUE (*arg)) != ADDR_EXPR) |
| find_used_portions (&TREE_VALUE (*arg), walk_subtrees, NULL); |
| } |
| *walk_subtrees = 0; |
| return NULL_TREE; |
| } |
| case VAR_DECL: |
| case PARM_DECL: |
| case RESULT_DECL: |
| { |
| tree var = *tp; |
| if (DECL_SIZE (var) |
| && var_can_have_subvars (var) |
| && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST) |
| { |
| used_part_t up; |
| size_t uid = DECL_UID (var); |
| |
| up = get_or_create_used_part_for (uid); |
| |
| up->minused = 0; |
| up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var)); |
| up->implicit_uses = true; |
| |
| up_insert (uid, up); |
| *walk_subtrees = 0; |
| return NULL_TREE; |
| } |
| } |
| break; |
| |
| default: |
| break; |
| |
| } |
| return NULL_TREE; |
| } |
| |
| /* Create structure field variables for structures used in this function. */ |
| |
| static unsigned int |
| create_structure_vars (void) |
| { |
| basic_block bb; |
| safe_referenced_var_iterator rvi; |
| VEC (tree, heap) *varvec = NULL; |
| tree var; |
| |
| used_portions = htab_create (10, used_part_map_hash, used_part_map_eq, |
| free_used_part_map); |
| |
| FOR_EACH_BB (bb) |
| { |
| block_stmt_iterator bsi; |
| for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) |
| { |
| walk_tree_without_duplicates (bsi_stmt_ptr (bsi), |
| find_used_portions, |
| NULL); |
| } |
| } |
| FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, rvi) |
| { |
| /* The C++ FE creates vars without DECL_SIZE set, for some reason. */ |
| if (var |
| && DECL_SIZE (var) |
| && var_can_have_subvars (var) |
| && !MTAG_P (var) |
| && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST) |
| create_overlap_variables_for (var); |
| } |
| htab_delete (used_portions); |
| VEC_free (tree, heap, varvec); |
| return 0; |
| } |
| |
| static bool |
| gate_structure_vars (void) |
| { |
| return flag_tree_salias != 0; |
| } |
| |
| struct tree_opt_pass pass_create_structure_vars = |
| { |
| "salias", /* name */ |
| gate_structure_vars, /* gate */ |
| create_structure_vars, /* execute */ |
| NULL, /* sub */ |
| NULL, /* next */ |
| 0, /* static_pass_number */ |
| 0, /* tv_id */ |
| PROP_cfg, /* properties_required */ |
| 0, /* properties_provided */ |
| 0, /* properties_destroyed */ |
| 0, /* todo_flags_start */ |
| TODO_dump_func, /* todo_flags_finish */ |
| 0 /* letter */ |
| }; |
| |
| /* Reset the DECL_CALL_CLOBBERED flags on our referenced vars. In |
| theory, this only needs to be done for globals. */ |
| |
| static unsigned int |
| reset_cc_flags (void) |
| { |
| tree var; |
| referenced_var_iterator rvi; |
| |
| FOR_EACH_REFERENCED_VAR (var, rvi) |
| DECL_CALL_CLOBBERED (var) = false; |
| return 0; |
| } |
| |
| struct tree_opt_pass pass_reset_cc_flags = |
| { |
| 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 */ |
| 0 /* letter */ |
| }; |