X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-alias.c;h=14733675262aac3bc2b24165e427c869297e2095;hb=50cb26651222ea939e524cd25a5bde2b152f8ce2;hp=1607c71257a206e8c9ecc7c5874533a6923c9c6d;hpb=d0fb9d56515b7c0b372f02cb505a830e5b0599e2;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index 1607c71257a..14733675262 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -1,12 +1,13 @@ /* Alias analysis for trees. - Copyright (C) 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 + Free Software Foundation, Inc. Contributed by Diego Novillo 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) +the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, @@ -15,9 +16,8 @@ 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. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -36,3227 +36,1444 @@ Boston, MA 02110-1301, USA. */ #include "function.h" #include "diagnostic.h" #include "tree-dump.h" -#include "tree-gimple.h" +#include "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" +#include "alloc-pool.h" +#include "tree-ssa-alias.h" -/* Obstack used to hold grouping bitmaps and other temporary bitmaps used by - aliasing */ -static bitmap_obstack alias_obstack; +/* Broad overview of how alias analysis on gimple works: -/* 'true' after aliases have been computed (see compute_may_aliases). */ -bool aliases_computed_p; + Statements clobbering or using memory are linked through the + virtual operand factored use-def chain. The virtual operand + is unique per function, its symbol is accessible via gimple_vop (cfun). + Virtual operands are used for efficiently walking memory statements + in the gimple IL and are useful for things like value-numbering as + a generation count for memory references. -/* 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); - } - } -} + SSA_NAME pointers may have associated points-to information + accessible via the SSA_NAME_PTR_INFO macro. Flow-insensitive + points-to information is (re-)computed by the TODO_rebuild_alias + pass manager todo. Points-to information is also used for more + precise tracking of call-clobbered and call-used variables and + related disambiguations. -/* Tags containing global vars need to be marked as global. - Tags containing call clobbered vars need to be marked as call - clobbered. */ + This file contains functions for disambiguating memory references, + the so called alias-oracle and tools for walking of the gimple IL. -static void -compute_tag_properties (void) -{ - referenced_var_iterator rvi; - tree tag; - bool changed = true; - VEC (tree, heap) *taglist = NULL; + The main alias-oracle entry-points are - 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; + bool stmt_may_clobber_ref_p (gimple, tree) - 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 ; - - # a_7 = V_MAY_DEF ; - # b_8 = V_MAY_DEF ; - *p_1 = 3; - - # a_9 = V_MAY_DEF - # VUSE - a_9 = b_8 + 2; - - # VUSE ; - # VUSE ; - 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); - - /* Determine if we need to enable alias grouping. */ - if (ai->total_alias_vops >= MAX_ALIASED_VOPS) - group_aliases (ai); - - /* Compute call clobbering information. */ - compute_call_clobbered (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); + This function queries if a statement may invalidate (parts of) + the memory designated by the reference tree argument. - if (!name || !POINTER_TYPE_P (TREE_TYPE (name))) - continue; + bool ref_maybe_used_by_stmt_p (gimple, tree) - 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 (); -} - -/* 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; - - /* 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; - - /* 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); - size_t j; - tree ptr2; - tree old_name_tag = pi->name_mem_tag; - - /* 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). */ - for (j = 0; j < i && VEC_iterate (tree, with_ptvars, j, ptr2); j++) - { - struct ptr_info_def *qi = SSA_NAME_PTR_INFO (ptr2); - - if (bitmap_equal_p (pi->pt_vars, qi->pt_vars)) - { - pi->name_mem_tag = qi->name_mem_tag; - break; - } - } - - /* 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); - } - - 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; - - /* 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. */ - for (j = i + 1; j < ai->num_pointers; j++) - { - bitmap 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; - } - } - - /* 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 - p_5->field = 0 - ... Several modifications to SMT.20 ... - # VUSE - 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; + This function queries if a statement may need (parts of) the + memory designated by the reference tree argument. - /* 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; + There are variants of these functions that only handle the call + part of a statement, call_may_clobber_ref_p and ref_maybe_used_by_call_p. + Note that these do not disambiguate against a possible call lhs. - /* Since VAR is now a regular GIMPLE register, we will need - to rename VAR into SSA afterwards. */ - mark_sym_for_renaming (var); + bool refs_may_alias_p (tree, tree) - /* 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); - } - } + This function tries to disambiguate two reference trees. - /* 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); - } - } + bool ptr_deref_may_alias_global_p (tree) - /* 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); - } + This function queries if dereferencing a pointer variable may + alias global memory. - /* 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); -} + More low-level disambiguators are available and documented in + this file. Low-level disambiguators dealing with points-to + information are in tree-ssa-structalias.c. */ -/* 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. +/* Query statistics for the different low-level disambiguators. + A high-level query may trigger multiple of them. */ - 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. +static struct { + unsigned HOST_WIDE_INT refs_may_alias_p_may_alias; + unsigned HOST_WIDE_INT refs_may_alias_p_no_alias; + unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_may_alias; + unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_no_alias; + unsigned HOST_WIDE_INT call_may_clobber_ref_p_may_alias; + unsigned HOST_WIDE_INT call_may_clobber_ref_p_no_alias; +} alias_stats; - 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. +void +dump_alias_stats (FILE *s) +{ + fprintf (s, "\nAlias oracle query stats:\n"); + fprintf (s, " refs_may_alias_p: " + HOST_WIDE_INT_PRINT_DEC" disambiguations, " + HOST_WIDE_INT_PRINT_DEC" queries\n", + alias_stats.refs_may_alias_p_no_alias, + alias_stats.refs_may_alias_p_no_alias + + alias_stats.refs_may_alias_p_may_alias); + fprintf (s, " ref_maybe_used_by_call_p: " + HOST_WIDE_INT_PRINT_DEC" disambiguations, " + HOST_WIDE_INT_PRINT_DEC" queries\n", + alias_stats.ref_maybe_used_by_call_p_no_alias, + alias_stats.refs_may_alias_p_no_alias + + alias_stats.ref_maybe_used_by_call_p_may_alias); + fprintf (s, " call_may_clobber_ref_p: " + HOST_WIDE_INT_PRINT_DEC" disambiguations, " + HOST_WIDE_INT_PRINT_DEC" queries\n", + alias_stats.call_may_clobber_ref_p_no_alias, + alias_stats.call_may_clobber_ref_p_no_alias + + alias_stats.call_may_clobber_ref_p_may_alias); +} - 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. */ +/* Return true, if dereferencing PTR may alias with a global variable. */ -static void -maybe_create_global_var (struct alias_info *ai) +bool +ptr_deref_may_alias_global_p (tree ptr) { - 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++; - } + struct ptr_info_def *pi; - /* 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 (); - } + /* If we end up with a pointer constant here that may point + to global memory. */ + if (TREE_CODE (ptr) != SSA_NAME) + return true; - /* 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); + pi = SSA_NAME_PTR_INFO (ptr); - /* 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); - } -} + /* If we do not have points-to information for this variable, + we have to punt. */ + if (!pi) + return true; + /* ??? This does not use TBAA to prune globals ptr may not access. */ + return pt_solution_includes_global (&pi->pt); +} -/* 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. */ +/* Return true if dereferencing PTR may alias DECL. + The caller is responsible for applying TBAA to see if PTR + may access DECL at all. */ 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) +ptr_deref_may_alias_decl_p (tree ptr, tree decl) { - tree mem; + struct ptr_info_def *pi; - alias_stats.alias_queries++; - alias_stats.simple_queries++; + gcc_assert ((TREE_CODE (ptr) == SSA_NAME + || TREE_CODE (ptr) == ADDR_EXPR + || TREE_CODE (ptr) == INTEGER_CST) + && (TREE_CODE (decl) == VAR_DECL + || TREE_CODE (decl) == PARM_DECL + || TREE_CODE (decl) == RESULT_DECL)); - /* 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; - } + /* Non-aliased variables can not be pointed to. */ + if (!may_be_aliased (decl)) + 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) + /* ADDR_EXPR pointers either just offset another pointer or directly + specify the pointed-to set. */ + if (TREE_CODE (ptr) == ADDR_EXPR) { - alias_stats.alias_noalias++; - alias_stats.simple_resolved++; - return false; + tree base = get_base_address (TREE_OPERAND (ptr, 0)); + if (base + && INDIRECT_REF_P (base)) + ptr = TREE_OPERAND (base, 0); + else if (base + && SSA_VAR_P (base)) + return operand_equal_p (base, decl, 0); + else if (base + && CONSTANT_CLASS_P (base)) + return false; + else + return true; } - /* 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; - } + /* We can end up with dereferencing constant pointers. + Just bail out in this case. */ + if (TREE_CODE (ptr) == INTEGER_CST) + return true; - /* If either MEM or VAR is a read-only global and the other one - isn't, then PTR cannot point to VAR. */ - if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var)) - || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem))) - { - alias_stats.alias_noalias++; - alias_stats.simple_resolved++; - return false; - } + /* If we do not have useful points-to information for this pointer + we cannot disambiguate anything else. */ + pi = SSA_NAME_PTR_INFO (ptr); + if (!pi) + return true; - gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG); + return pt_solution_includes (&pi->pt, decl); +} - alias_stats.tbaa_queries++; +/* Return true if dereferenced PTR1 and PTR2 may alias. + The caller is responsible for applying TBAA to see if accesses + through PTR1 and PTR2 may conflict at all. */ - /* 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; - } +static bool +ptr_derefs_may_alias_p (tree ptr1, tree ptr2) +{ + struct ptr_info_def *pi1, *pi2; - /* 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. */ + gcc_assert ((TREE_CODE (ptr1) == SSA_NAME + || TREE_CODE (ptr1) == ADDR_EXPR + || TREE_CODE (ptr1) == INTEGER_CST) + && (TREE_CODE (ptr2) == SSA_NAME + || TREE_CODE (ptr2) == ADDR_EXPR + || TREE_CODE (ptr2) == INTEGER_CST)); - if ((mem_alias_set != 0) && (var_alias_set != 0)) + /* ADDR_EXPR pointers either just offset another pointer or directly + specify the pointed-to set. */ + if (TREE_CODE (ptr1) == ADDR_EXPR) { - 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; - } - } + tree base = get_base_address (TREE_OPERAND (ptr1, 0)); + if (base + && INDIRECT_REF_P (base)) + ptr1 = TREE_OPERAND (base, 0); + else if (base + && SSA_VAR_P (base)) + return ptr_deref_may_alias_decl_p (ptr2, base); + else + return true; + } + if (TREE_CODE (ptr2) == ADDR_EXPR) + { + tree base = get_base_address (TREE_OPERAND (ptr2, 0)); + if (base + && INDIRECT_REF_P (base)) + ptr2 = TREE_OPERAND (base, 0); + else if (base + && SSA_VAR_P (base)) + return ptr_deref_may_alias_decl_p (ptr1, base); + else + return true; } - alias_stats.alias_mayalias++; - return true; -} + /* We can end up with dereferencing constant pointers. + Just bail out in this case. */ + if (TREE_CODE (ptr1) == INTEGER_CST + || TREE_CODE (ptr2) == INTEGER_CST) + return true; + + /* We may end up with two empty points-to solutions for two same pointers. + In this case we still want to say both pointers alias, so shortcut + that here. */ + if (ptr1 == ptr2) + return true; + + /* If we do not have useful points-to information for either pointer + we cannot disambiguate anything else. */ + pi1 = SSA_NAME_PTR_INFO (ptr1); + pi2 = SSA_NAME_PTR_INFO (ptr2); + if (!pi1 || !pi2) + return true; + /* ??? This does not use TBAA to prune decls from the intersection + that not both pointers may access. */ + return pt_solutions_intersect (&pi1->pt, &pi2->pt); +} -/* Add ALIAS to the set of variables that may alias VAR. */ +/* Return true if dereferencing PTR may alias *REF. + The caller is responsible for applying TBAA to see if PTR + may access *REF at all. */ -static void -add_may_alias (tree var, tree alias) +static bool +ptr_deref_may_alias_ref_p_1 (tree ptr, ao_ref *ref) { - 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; -} + tree base = ao_ref_base (ref); + if (INDIRECT_REF_P (base)) + return ptr_derefs_may_alias_p (ptr, TREE_OPERAND (base, 0)); + else if (SSA_VAR_P (base)) + return ptr_deref_may_alias_decl_p (ptr, base); -/* Replace alias I in the alias sets of VAR with NEW_ALIAS. */ + return true; +} -static void -replace_may_alias (tree var, size_t i, tree new_alias) +static bool +ptr_deref_may_alias_ref_p (tree ptr, tree ref) { - var_ann_t v_ann = var_ann (var); - VEC_replace (tree, v_ann->may_aliases, i, new_alias); + ao_ref r; + ao_ref_init (&r, ref); + return ptr_deref_may_alias_ref_p_1 (ptr, &r); } -/* Mark pointer PTR as pointing to an arbitrary memory location. */ +/* Dump alias information on FILE. */ -static void -set_pt_anything (tree ptr) +void +dump_alias_info (FILE *file) { - struct ptr_info_def *pi = get_ptr_info (ptr); + size_t i; + const char *funcname + = lang_hooks.decl_printable_name (current_function_decl, 2); + referenced_var_iterator rvi; + tree var; - pi->pt_anything = 1; - pi->pt_vars = NULL; + fprintf (file, "\n\nAlias information for %s\n\n", funcname); - /* 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) + fprintf (file, "Aliased symbols\n\n"); + + FOR_EACH_REFERENCED_VAR (var, rvi) { - mark_sym_for_renaming (pi->name_mem_tag); - pi->name_mem_tag = NULL_TREE; + if (may_be_aliased (var)) + dump_variable (file, var); } -} + fprintf (file, "\nCall clobber information\n"); -/* 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: + fprintf (file, "\nESCAPED"); + dump_points_to_solution (file, &cfun->gimple_df->escaped); + fprintf (file, "\nCALLUSED"); + dump_points_to_solution (file, &cfun->gimple_df->callused); - 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. + fprintf (file, "\n\nFlow-insensitive points-to information\n\n"); - AI points to the alias information collected so far. - - Return the type of escape site found, if we found one, or NO_ESCAPE - if none. */ - -enum escape_type -is_escape_site (tree stmt, struct alias_info *ai) -{ - tree call = get_call_expr_in (stmt); - if (call != NULL_TREE) + for (i = 1; i < num_ssa_names; i++) { - ai->num_calls_found++; - - if (!TREE_SIDE_EFFECTS (call)) - { - ai->num_pure_const_calls_found++; - return ESCAPE_TO_PURE_CONST; - } + tree ptr = ssa_name (i); + struct ptr_info_def *pi; + + if (ptr == NULL_TREE + || SSA_NAME_IN_FREE_LIST (ptr)) + continue; - return ESCAPE_TO_CALL; + pi = SSA_NAME_PTR_INFO (ptr); + if (pi) + dump_points_to_info_for (file, ptr); } - 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; + fprintf (file, "\n"); +} - 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; +/* Dump alias information on stderr. */ - return NO_ESCAPE; +void +debug_alias_info (void) +{ + dump_alias_info (stderr); } -/* 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; +/* Return the alias information associated with pointer T. It creates a + new instance if none existed. */ - /* Make the type of the variable writable. */ - new_type = build_type_variant (type, 0, 0); - TYPE_ATTRIBUTES (new_type) = TYPE_ATTRIBUTES (type); +struct ptr_info_def * +get_ptr_info (tree t) +{ + struct ptr_info_def *pi; - tmp_var = build_decl (code, create_tmp_var_name (prefix), - type); - /* Make the variable writable. */ - TREE_READONLY (tmp_var) = 0; + gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); - /* It doesn't start out global. */ - MTAG_GLOBAL (tmp_var) = 0; - TREE_STATIC (tmp_var) = 0; - TREE_USED (tmp_var) = 1; + pi = SSA_NAME_PTR_INFO (t); + if (pi == NULL) + { + pi = GGC_CNEW (struct ptr_info_def); + pt_solution_reset (&pi->pt); + SSA_NAME_PTR_INFO (t) = pi; + } - return tmp_var; + return pi; } -/* 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. */ +/* Dump the points-to set *PT into FILE. */ -static tree -create_memory_tag (tree type, bool is_type_tag) +void +dump_points_to_solution (FILE *file, struct pt_solution *pt) { - var_ann_t ann; - tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG, - type, (is_type_tag) ? "SMT" : "NMT"); + if (pt->anything) + fprintf (file, ", points-to anything"); - /* By default, memory tags are local variables. Alias analysis will - determine whether they should be considered globals. */ - DECL_CONTEXT (tag) = current_function_decl; + if (pt->nonlocal) + fprintf (file, ", points-to non-local"); - /* Memory tags are by definition addressable. */ - TREE_ADDRESSABLE (tag) = 1; + if (pt->escaped) + fprintf (file, ", points-to escaped"); - ann = get_var_ann (tag); - ann->symbol_mem_tag = NULL_TREE; + if (pt->null) + fprintf (file, ", points-to NULL"); - /* Add the tag to the symbol table. */ - add_referenced_var (tag); - - return tag; + if (pt->vars) + { + fprintf (file, ", points-to vars: "); + dump_decl_set (file, pt->vars); + if (pt->vars_contains_global) + fprintf (file, " (includes global vars)"); + } } +/* Dump points-to information for SSA_NAME PTR into FILE. */ -/* 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) +void +dump_points_to_info_for (FILE *file, tree ptr) { - struct ptr_info_def *pi = get_ptr_info (ptr); - tree tag = pi->name_mem_tag; + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); - if (tag == NULL_TREE) - tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false); - return tag; -} + print_generic_expr (file, ptr, dump_flags); + if (pi) + dump_points_to_solution (file, &pi->pt); + else + fprintf (file, ", points-to anything"); -/* 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. */ + fprintf (file, "\n"); +} -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; - } +/* Dump points-to information for VAR into stderr. */ - /* 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; - } - } +void +debug_points_to_info_for (tree var) +{ + dump_points_to_info_for (stderr, var); +} - /* 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; - } +/* Initializes the alias-oracle reference representation *R from REF. */ - /* If the pointed-to type is volatile, so is the tag. */ - TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type); +void +ao_ref_init (ao_ref *r, tree ref) +{ + r->ref = ref; + r->base = NULL_TREE; + r->offset = 0; + r->size = -1; + r->max_size = -1; + r->ref_alias_set = -1; + r->base_alias_set = -1; +} - /* Make sure that the symbol tag has the same alias set as the - pointed-to type. */ - gcc_assert (tag_set == get_alias_set (tag)); +/* Returns the base object of the memory reference *REF. */ - return tag; +tree +ao_ref_base (ao_ref *ref) +{ + if (ref->base) + return ref->base; + ref->base = get_ref_base_and_extent (ref->ref, &ref->offset, &ref->size, + &ref->max_size); + return ref->base; } +/* Returns the base object alias set of the memory reference *REF. */ -/* 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) +static alias_set_type ATTRIBUTE_UNUSED +ao_ref_base_alias_set (ao_ref *ref) { - 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); + if (ref->base_alias_set != -1) + return ref->base_alias_set; + ref->base_alias_set = get_alias_set (ao_ref_base (ref)); + return ref->base_alias_set; } +/* Returns the reference alias set of the memory reference *REF. */ -/* Dump alias statistics on FILE. */ - -static void -dump_alias_stats (FILE *file) +alias_set_type +ao_ref_alias_set (ao_ref *ref) { - 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); + if (ref->ref_alias_set != -1) + return ref->ref_alias_set; + ref->ref_alias_set = get_alias_set (ref->ref); + return ref->ref_alias_set; } - -/* Dump alias information on FILE. */ +/* Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the + purpose of TBAA. Return 0 if they are distinct and -1 if we cannot + decide. */ -void -dump_alias_info (FILE *file) +static inline int +same_type_for_tbaa (tree type1, tree type2) { - 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); + type1 = TYPE_MAIN_VARIANT (type1); + type2 = TYPE_MAIN_VARIANT (type2); - fprintf (file, "Aliased symbols\n\n"); - - FOR_EACH_REFERENCED_VAR (var, rvi) - { - if (may_be_aliased (var)) - dump_variable (file, var); - } + /* If we would have to do structural comparison bail out. */ + if (TYPE_STRUCTURAL_EQUALITY_P (type1) + || TYPE_STRUCTURAL_EQUALITY_P (type2)) + return -1; - fprintf (file, "\nDereferenced pointers\n\n"); + /* Compare the canonical types. */ + if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2)) + return 1; - FOR_EACH_REFERENCED_VAR (var, rvi) - { - var_ann_t ann = var_ann (var); - if (ann->symbol_mem_tag) - dump_variable (file, var); - } + /* ??? Array types are not properly unified in all cases as we have + spurious changes in the index types for example. Removing this + causes all sorts of problems with the Fortran frontend. */ + if (TREE_CODE (type1) == ARRAY_TYPE + && TREE_CODE (type2) == ARRAY_TYPE) + return -1; - fprintf (file, "\nSymbol memory tags\n\n"); - - FOR_EACH_REFERENCED_VAR (var, rvi) - { - if (TREE_CODE (var) == SYMBOL_MEMORY_TAG) - dump_variable (file, var); - } + /* The types are known to be not equal. */ + return 0; +} - fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname); +/* Determine if the two component references REF1 and REF2 which are + based on access types TYPE1 and TYPE2 and of which at least one is based + on an indirect reference may alias. */ - fprintf (file, "SSA_NAME pointers\n\n"); - for (i = 1; i < num_ssa_names; i++) +static bool +nonaliasing_component_refs_p (tree ref1, tree type1, + HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1, + tree ref2, tree type2, + HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2) +{ + /* If one reference is a component references through pointers try to find a + common base and apply offset based disambiguation. This handles + for example + struct A { int i; int j; } *q; + struct B { struct A a; int k; } *p; + disambiguating q->i and p->a.j. */ + tree *refp; + int same_p; + + /* Now search for the type1 in the access path of ref2. This + would be a common base for doing offset based disambiguation on. */ + refp = &ref2; + while (handled_component_p (*refp) + && same_type_for_tbaa (TREE_TYPE (*refp), type1) == 0) + refp = &TREE_OPERAND (*refp, 0); + same_p = same_type_for_tbaa (TREE_TYPE (*refp), type1); + /* If we couldn't compare types we have to bail out. */ + if (same_p == -1) + return true; + else if (same_p == 1) { - 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); + HOST_WIDE_INT offadj, sztmp, msztmp; + get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp); + offset2 -= offadj; + return ranges_overlap_p (offset1, max_size1, offset2, max_size2); } - - fprintf (file, "\nName memory tags\n\n"); - - FOR_EACH_REFERENCED_VAR (var, rvi) + /* If we didn't find a common base, try the other way around. */ + refp = &ref1; + while (handled_component_p (*refp) + && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0) + refp = &TREE_OPERAND (*refp, 0); + same_p = same_type_for_tbaa (TREE_TYPE (*refp), type2); + /* If we couldn't compare types we have to bail out. */ + if (same_p == -1) + return true; + else if (same_p == 1) { - if (TREE_CODE (var) == NAME_MEMORY_TAG) - dump_variable (file, var); + HOST_WIDE_INT offadj, sztmp, msztmp; + get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp); + offset1 -= offadj; + return ranges_overlap_p (offset1, max_size1, offset2, max_size2); } - - fprintf (file, "\n"); + /* If we have two type access paths B1.path1 and B2.path2 they may + only alias if either B1 is in B2.path2 or B2 is in B1.path1. */ + return false; } +/* Return true if two memory references based on the variables BASE1 + and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1[ and + [OFFSET2, OFFSET2 + MAX_SIZE2[ may alias. */ -/* Dump alias information on stderr. */ - -void -debug_alias_info (void) +static bool +decl_refs_may_alias_p (tree base1, + HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1, + tree base2, + HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2) { - dump_alias_info (stderr); + gcc_assert (SSA_VAR_P (base1) && SSA_VAR_P (base2)); + + /* If both references are based on different variables, they cannot alias. */ + if (!operand_equal_p (base1, base2, 0)) + return false; + + /* If both references are based on the same variable, they cannot alias if + the accesses do not overlap. */ + return ranges_overlap_p (offset1, max_size1, offset2, max_size2); } +/* Return true if an indirect reference based on *PTR1 constrained + to [OFFSET1, OFFSET1 + MAX_SIZE1[ may alias a variable based on BASE2 + constrained to [OFFSET2, OFFSET2 + MAX_SIZE2[. *PTR1 and BASE2 have + the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1 + in which case they are computed on-demand. REF1 and REF2 + if non-NULL are the complete memory reference trees. */ -/* Return the alias information associated with pointer T. It creates a - new instance if none existed. */ +static bool +indirect_ref_may_alias_decl_p (tree ref1, tree ptr1, + HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1, + alias_set_type base1_alias_set, + tree ref2, tree base2, + HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2, + alias_set_type base2_alias_set) +{ + /* If only one reference is based on a variable, they cannot alias if + the pointer access is beyond the extent of the variable access. + (the pointer base cannot validly point to an offset less than zero + of the variable). + They also cannot alias if the pointer may not point to the decl. */ + if (max_size2 != -1 + && !ranges_overlap_p (offset1, max_size1, 0, offset2 + max_size2)) + return false; + if (!ptr_deref_may_alias_decl_p (ptr1, base2)) + return false; -struct ptr_info_def * -get_ptr_info (tree t) -{ - struct ptr_info_def *pi; + /* Disambiguations that rely on strict aliasing rules follow. */ + if (!flag_strict_aliasing) + return true; - gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); + /* If the alias set for a pointer access is zero all bets are off. */ + if (base1_alias_set == -1) + base1_alias_set = get_deref_alias_set (ptr1); + if (base1_alias_set == 0) + return true; + if (base2_alias_set == -1) + base2_alias_set = get_alias_set (base2); + + /* If both references are through the same type, they do not alias + if the accesses do not overlap. This does extra disambiguation + for mixed/pointer accesses but requires strict aliasing. */ + if (same_type_for_tbaa (TREE_TYPE (TREE_TYPE (ptr1)), + TREE_TYPE (base2)) == 1) + return ranges_overlap_p (offset1, max_size1, offset2, max_size2); + + /* The only way to access a variable is through a pointer dereference + of the same alias set or a subset of it. */ + if (base1_alias_set != base2_alias_set + && !alias_set_subset_of (base1_alias_set, base2_alias_set)) + return false; - 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; - } + /* Do access-path based disambiguation. */ + if (ref1 && ref2 + && handled_component_p (ref1) + && handled_component_p (ref2)) + return nonaliasing_component_refs_p (ref1, TREE_TYPE (TREE_TYPE (ptr1)), + offset1, max_size1, + ref2, TREE_TYPE (base2), + offset2, max_size2); - return pi; + return true; } +/* Return true if two indirect references based on *PTR1 + and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1[ and + [OFFSET2, OFFSET2 + MAX_SIZE2[ may alias. *PTR1 and *PTR2 have + the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1 + in which case they are computed on-demand. REF1 and REF2 + if non-NULL are the complete memory reference trees. */ + +static bool +indirect_refs_may_alias_p (tree ref1, tree ptr1, + HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1, + alias_set_type base1_alias_set, + tree ref2, tree ptr2, + HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2, + alias_set_type base2_alias_set) +{ + /* If both bases are based on pointers they cannot alias if they may not + point to the same memory object or if they point to the same object + and the accesses do not overlap. */ + if (operand_equal_p (ptr1, ptr2, 0)) + return ranges_overlap_p (offset1, max_size1, offset2, max_size2); + if (!ptr_derefs_may_alias_p (ptr1, ptr2)) + return false; -/* Dump points-to information for SSA_NAME PTR into FILE. */ + /* Disambiguations that rely on strict aliasing rules follow. */ + if (!flag_strict_aliasing) + return true; -void -dump_points_to_info_for (FILE *file, tree ptr) -{ - struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); + /* If the alias set for a pointer access is zero all bets are off. */ + if (base1_alias_set == -1) + base1_alias_set = get_deref_alias_set (ptr1); + if (base1_alias_set == 0) + return true; + if (base2_alias_set == -1) + base2_alias_set = get_deref_alias_set (ptr2); + if (base2_alias_set == 0) + return true; - print_generic_expr (file, ptr, dump_flags); + /* If both references are through the same type, they do not alias + if the accesses do not overlap. This does extra disambiguation + for mixed/pointer accesses but requires strict aliasing. */ + if (same_type_for_tbaa (TREE_TYPE (TREE_TYPE (ptr1)), + TREE_TYPE (TREE_TYPE (ptr2))) == 1) + return ranges_overlap_p (offset1, max_size1, offset2, max_size2); - if (pi) - { - if (pi->name_mem_tag) - { - fprintf (file, ", name memory tag: "); - print_generic_expr (file, pi->name_mem_tag, dump_flags); - } + /* Do type-based disambiguation. */ + if (base1_alias_set != base2_alias_set + && !alias_sets_conflict_p (base1_alias_set, base2_alias_set)) + return false; - if (pi->is_dereferenced) - fprintf (file, ", is dereferenced"); + /* Do access-path based disambiguation. */ + if (ref1 && ref2 + && handled_component_p (ref1) + && handled_component_p (ref2)) + return nonaliasing_component_refs_p (ref1, TREE_TYPE (TREE_TYPE (ptr1)), + offset1, max_size1, + ref2, TREE_TYPE (TREE_TYPE (ptr2)), + offset2, max_size2); - if (pi->value_escapes_p) - fprintf (file, ", its value escapes"); + return true; +} - if (pi->pt_anything) - fprintf (file, ", points-to anything"); +/* Return true, if the two memory references REF1 and REF2 may alias. */ - if (pi->pt_null) - fprintf (file, ", points-to NULL"); +static bool +refs_may_alias_p_1 (ao_ref *ref1, ao_ref *ref2, bool tbaa_p) +{ + tree base1, base2; + HOST_WIDE_INT offset1 = 0, offset2 = 0; + HOST_WIDE_INT size1 = -1, size2 = -1; + HOST_WIDE_INT max_size1 = -1, max_size2 = -1; + bool var1_p, var2_p, ind1_p, ind2_p; + alias_set_type set; + + gcc_assert ((!ref1->ref + || SSA_VAR_P (ref1->ref) + || handled_component_p (ref1->ref) + || INDIRECT_REF_P (ref1->ref) + || TREE_CODE (ref1->ref) == TARGET_MEM_REF) + && (!ref2->ref + || SSA_VAR_P (ref2->ref) + || handled_component_p (ref2->ref) + || INDIRECT_REF_P (ref2->ref) + || TREE_CODE (ref2->ref) == TARGET_MEM_REF)); + + /* Decompose the references into their base objects and the access. */ + base1 = ao_ref_base (ref1); + offset1 = ref1->offset; + size1 = ref1->size; + max_size1 = ref1->max_size; + base2 = ao_ref_base (ref2); + offset2 = ref2->offset; + size2 = ref2->size; + max_size2 = ref2->max_size; + + /* We can end up with registers or constants as bases for example from + *D.1663_44 = VIEW_CONVERT_EXPR(__tmp$B0F64_59); + which is seen as a struct copy. */ + if (TREE_CODE (base1) == SSA_NAME + || TREE_CODE (base2) == SSA_NAME + || is_gimple_min_invariant (base1) + || is_gimple_min_invariant (base2)) + return false; - if (pi->pt_vars) - { - unsigned ix; - bitmap_iterator bi; + /* Defer to simple offset based disambiguation if we have + references based on two decls. Do this before defering to + TBAA to handle must-alias cases in conformance with the + GCC extension of allowing type-punning through unions. */ + var1_p = SSA_VAR_P (base1); + var2_p = SSA_VAR_P (base2); + if (var1_p && var2_p) + return decl_refs_may_alias_p (base1, offset1, max_size1, + base2, offset2, max_size2); + + /* First defer to TBAA if possible. */ + if (tbaa_p + && flag_strict_aliasing + && !alias_sets_conflict_p (ao_ref_alias_set (ref1), + ao_ref_alias_set (ref2))) + return false; - 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, "}"); - } - } + /* If one reference is a TARGET_MEM_REF weird things are allowed. Still + TBAA disambiguation based on the access type is possible, so bail + out only after that check. */ + if ((ref1->ref && TREE_CODE (ref1->ref) == TARGET_MEM_REF) + || (ref2->ref && TREE_CODE (ref2->ref) == TARGET_MEM_REF)) + return true; - fprintf (file, "\n"); + /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators. */ + ind1_p = INDIRECT_REF_P (base1); + ind2_p = INDIRECT_REF_P (base2); + set = tbaa_p ? -1 : 0; + if (var1_p && ind2_p) + return indirect_ref_may_alias_decl_p (ref2->ref, TREE_OPERAND (base2, 0), + offset2, max_size2, set, + ref1->ref, base1, + offset1, max_size1, set); + else if (ind1_p && var2_p) + return indirect_ref_may_alias_decl_p (ref1->ref, TREE_OPERAND (base1, 0), + offset1, max_size1, set, + ref2->ref, base2, + offset2, max_size2, set); + else if (ind1_p && ind2_p) + return indirect_refs_may_alias_p (ref1->ref, TREE_OPERAND (base1, 0), + offset1, max_size1, set, + ref2->ref, TREE_OPERAND (base2, 0), + offset2, max_size2, set); + + gcc_unreachable (); } +bool +refs_may_alias_p (tree ref1, tree ref2) +{ + ao_ref r1, r2; + bool res; + ao_ref_init (&r1, ref1); + ao_ref_init (&r2, ref2); + res = refs_may_alias_p_1 (&r1, &r2, true); + if (res) + ++alias_stats.refs_may_alias_p_may_alias; + else + ++alias_stats.refs_may_alias_p_no_alias; + return res; +} -/* Dump points-to information for VAR into stderr. */ +/* Returns true if there is a anti-dependence for the STORE that + executes after the LOAD. */ -void -debug_points_to_info_for (tree var) +bool +refs_anti_dependent_p (tree load, tree store) { - dump_points_to_info_for (stderr, var); + ao_ref r1, r2; + ao_ref_init (&r1, load); + ao_ref_init (&r2, store); + return refs_may_alias_p_1 (&r1, &r2, false); } +/* Returns true if there is a output dependence for the stores + STORE1 and STORE2. */ + +bool +refs_output_dependent_p (tree store1, tree store2) +{ + ao_ref r1, r2; + ao_ref_init (&r1, store1); + ao_ref_init (&r2, store2); + return refs_may_alias_p_1 (&r1, &r2, false); +} -/* Dump points-to information into FILE. NOTE: This function is slow, as - it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */ +/* If the call CALL may use the memory reference REF return true, + otherwise return false. */ -void -dump_points_to_info (FILE *file) +static bool +ref_maybe_used_by_call_p_1 (gimple call, tree ref) { - 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; + tree base, callee; + unsigned i; + int flags = gimple_call_flags (call); - fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname); + /* Const functions without a static chain do not implicitly use memory. */ + if (!gimple_call_chain (call) + && (flags & (ECF_CONST|ECF_NOVOPS))) + goto process_args; - /* 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) + base = get_base_address (ref); + if (!base) + return true; + + /* If the reference is based on a decl that is not aliased the call + cannot possibly use it. */ + if (DECL_P (base) + && !may_be_aliased (base) + /* But local statics can be used through recursion. */ + && !is_global_var (base)) + goto process_args; + + callee = gimple_call_fndecl (call); + + /* Handle those builtin functions explicitly that do not act as + escape points. See tree-ssa-structalias.c:find_func_aliases + for the list of builtins we might need to handle here. */ + if (callee != NULL_TREE + && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL) + switch (DECL_FUNCTION_CODE (callee)) + { + /* All the following functions clobber memory pointed to by + their first argument. */ + case BUILT_IN_STRCPY: + case BUILT_IN_STRNCPY: + case BUILT_IN_BCOPY: + case BUILT_IN_MEMCPY: + case BUILT_IN_MEMMOVE: + case BUILT_IN_MEMPCPY: + case BUILT_IN_STPCPY: + case BUILT_IN_STPNCPY: + case BUILT_IN_STRCAT: + case BUILT_IN_STRNCAT: + { + tree src = gimple_call_arg (call, 1); + return ptr_deref_may_alias_ref_p (src, ref); + } + /* The following builtins do not read from memory. */ + case BUILT_IN_FREE: + case BUILT_IN_MEMSET: + case BUILT_IN_FREXP: + case BUILT_IN_FREXPF: + case BUILT_IN_FREXPL: + case BUILT_IN_GAMMA_R: + case BUILT_IN_GAMMAF_R: + case BUILT_IN_GAMMAL_R: + case BUILT_IN_LGAMMA_R: + case BUILT_IN_LGAMMAF_R: + case BUILT_IN_LGAMMAL_R: + case BUILT_IN_MODF: + case BUILT_IN_MODFF: + case BUILT_IN_MODFL: + case BUILT_IN_REMQUO: + case BUILT_IN_REMQUOF: + case BUILT_IN_REMQUOL: + case BUILT_IN_SINCOS: + case BUILT_IN_SINCOSF: + case BUILT_IN_SINCOSL: + return false; + + default: + /* Fallthru to general call handling. */; + } + + /* Check if base is a global static variable that is not read + by the function. */ + if (TREE_CODE (base) == VAR_DECL + && TREE_STATIC (base) + && !TREE_PUBLIC (base)) + { + bitmap not_read; + + if (callee != NULL_TREE + && (not_read + = ipa_reference_get_not_read_global (cgraph_node (callee))) + && bitmap_bit_p (not_read, DECL_UID (base))) + goto process_args; + } + + /* If the base variable is call-used or call-clobbered then + it may be used. */ + if (flags & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS)) { - if (POINTER_TYPE_P (TREE_TYPE (var))) + if (DECL_P (base)) + { + if (is_call_used (base)) + return true; + } + else if (INDIRECT_REF_P (base) + && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) { - tree def = default_def (var); - if (def) - dump_points_to_info_for (file, def); + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0)); + if (!pi) + return true; + + if (pt_solution_includes_global (&pi->pt) + || pt_solutions_intersect (&cfun->gimple_df->callused, &pi->pt) + || pt_solutions_intersect (&cfun->gimple_df->escaped, &pi->pt)) + return true; } + else + return true; } - - /* Dump points-to information for every pointer defined in the program. */ - FOR_EACH_BB (bb) + else { - tree phi; - - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + if (DECL_P (base)) { - tree ptr = PHI_RESULT (phi); - if (POINTER_TYPE_P (TREE_TYPE (ptr))) - dump_points_to_info_for (file, ptr); + if (is_call_clobbered (base)) + return true; } + else if (INDIRECT_REF_P (base) + && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) + { + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0)); + if (!pi) + return true; - 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); - } + if (pt_solution_includes_global (&pi->pt) + || pt_solutions_intersect (&cfun->gimple_df->escaped, &pi->pt)) + return true; + } + else + return true; } - fprintf (file, "\n"); -} + /* Inspect call arguments for passed-by-value aliases. */ +process_args: + for (i = 0; i < gimple_call_num_args (call); ++i) + { + tree op = gimple_call_arg (call, i); + if (TREE_CODE (op) == EXC_PTR_EXPR + || TREE_CODE (op) == FILTER_EXPR) + continue; -/* Dump points-to info pointed to by PTO into STDERR. */ + if (TREE_CODE (op) == WITH_SIZE_EXPR) + op = TREE_OPERAND (op, 0); -void -debug_points_to_info (void) + if (TREE_CODE (op) != SSA_NAME + && !is_gimple_min_invariant (op) + && refs_may_alias_p (op, ref)) + return true; + } + + return false; +} + +static bool +ref_maybe_used_by_call_p (gimple call, tree ref) { - dump_points_to_info (stderr); + bool res = ref_maybe_used_by_call_p_1 (call, ref); + if (res) + ++alias_stats.ref_maybe_used_by_call_p_may_alias; + else + ++alias_stats.ref_maybe_used_by_call_p_no_alias; + return res; } -/* Dump 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); +/* If the statement STMT may use the memory reference REF return + true, otherwise return false. */ - aliases = var_ann (var)->may_aliases; - if (aliases) +bool +ref_maybe_used_by_stmt_p (gimple stmt, tree ref) +{ + if (is_gimple_assign (stmt)) { - 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, "}"); - } -} + tree rhs; + + /* All memory assign statements are single. */ + if (!gimple_assign_single_p (stmt)) + return false; + rhs = gimple_assign_rhs1 (stmt); + if (is_gimple_reg (rhs) + || is_gimple_min_invariant (rhs) + || gimple_assign_rhs_code (stmt) == CONSTRUCTOR) + return false; -/* Dump to stderr the list of variables that may be aliasing VAR. */ + return refs_may_alias_p (rhs, ref); + } + else if (is_gimple_call (stmt)) + return ref_maybe_used_by_call_p (stmt, ref); -void -debug_may_aliases_for (tree var) -{ - dump_may_aliases_for (stderr, var); + return true; } -/* Return true if VAR may be aliased. */ +/* If the call in statement CALL may clobber the memory reference REF + return true, otherwise return false. */ -bool -may_be_aliased (tree var) +static bool +call_may_clobber_ref_p_1 (gimple call, ao_ref *ref) { - /* Obviously. */ - if (TREE_ADDRESSABLE (var)) - return true; + tree base; + tree callee; - /* Globally visible variables can have their addresses taken by other - translation units. */ + /* If the call is pure or const it cannot clobber anything. */ + if (gimple_call_flags (call) + & (ECF_PURE|ECF_CONST|ECF_LOOPING_CONST_OR_PURE|ECF_NOVOPS)) + return false; - if (MTAG_P (var) - && (MTAG_GLOBAL (var) || TREE_PUBLIC (var))) - return true; - else if (!MTAG_P (var) - && (DECL_EXTERNAL (var) || TREE_PUBLIC (var))) + base = ao_ref_base (ref); + if (!base) 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)) + if (TREE_CODE (base) == SSA_NAME + || CONSTANT_CLASS_P (base)) 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) + /* If the reference is based on a decl that is not aliased the call + cannot possibly clobber it. */ + if (DECL_P (base) + && !may_be_aliased (base) + /* But local non-readonly statics can be modified through recursion + or the call may implement a threading barrier which we must + treat as may-def. */ + && (TREE_READONLY (base) + || !is_global_var (base))) return false; - if (decl_function_context (var) == current_function_decl) - return false; - - return true; -} + callee = gimple_call_fndecl (call); -/* 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; + /* Handle those builtin functions explicitly that do not act as + escape points. See tree-ssa-structalias.c:find_func_aliases + for the list of builtins we might need to handle here. */ + if (callee != NULL_TREE + && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL) + switch (DECL_FUNCTION_CODE (callee)) + { + /* All the following functions clobber memory pointed to by + their first argument. */ + case BUILT_IN_STRCPY: + case BUILT_IN_STRNCPY: + case BUILT_IN_BCOPY: + case BUILT_IN_MEMCPY: + case BUILT_IN_MEMMOVE: + case BUILT_IN_MEMPCPY: + case BUILT_IN_STPCPY: + case BUILT_IN_STPNCPY: + case BUILT_IN_STRCAT: + case BUILT_IN_STRNCAT: + { + tree dest = gimple_call_arg (call, 0); + return ptr_deref_may_alias_ref_p_1 (dest, ref); + } + /* Freeing memory kills the pointed-to memory. More importantly + the call has to serve as a barrier for moving loads and stores + across it. Same is true for memset. */ + case BUILT_IN_FREE: + case BUILT_IN_MEMSET: + { + tree ptr = gimple_call_arg (call, 0); + return ptr_deref_may_alias_ref_p_1 (ptr, ref); + } + case BUILT_IN_GAMMA_R: + case BUILT_IN_GAMMAF_R: + case BUILT_IN_GAMMAL_R: + case BUILT_IN_LGAMMA_R: + case BUILT_IN_LGAMMAF_R: + case BUILT_IN_LGAMMAL_R: + { + tree out = gimple_call_arg (call, 1); + if (ptr_deref_may_alias_ref_p_1 (out, ref)) + return true; + if (flag_errno_math) + break; + return false; + } + case BUILT_IN_FREXP: + case BUILT_IN_FREXPF: + case BUILT_IN_FREXPL: + case BUILT_IN_MODF: + case BUILT_IN_MODFF: + case BUILT_IN_MODFL: + { + tree out = gimple_call_arg (call, 1); + return ptr_deref_may_alias_ref_p_1 (out, ref); + } + case BUILT_IN_REMQUO: + case BUILT_IN_REMQUOF: + case BUILT_IN_REMQUOL: + { + tree out = gimple_call_arg (call, 2); + if (ptr_deref_may_alias_ref_p_1 (out, ref)) + return true; + if (flag_errno_math) + break; + return false; + } + case BUILT_IN_SINCOS: + case BUILT_IN_SINCOSF: + case BUILT_IN_SINCOSL: + { + tree sin = gimple_call_arg (call, 1); + tree cos = gimple_call_arg (call, 2); + return (ptr_deref_may_alias_ref_p_1 (sin, ref) + || ptr_deref_may_alias_ref_p_1 (cos, ref)); + } + default: + /* Fallthru to general call handling. */; + } - if (var_ann (sym)->is_aliased) + /* Check if base is a global static variable that is not written + by the function. */ + if (callee != NULL_TREE + && TREE_CODE (base) == VAR_DECL + && TREE_STATIC (base) + && !TREE_PUBLIC (base)) { - aliases = var_ann (tag)->may_aliases; + bitmap not_written; - if (aliases == NULL) + if ((not_written + = ipa_reference_get_not_written_global (cgraph_node (callee))) + && bitmap_bit_p (not_written, DECL_UID (base))) 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; + if (DECL_P (base)) + return is_call_clobbered (base); + else if (INDIRECT_REF_P (base) + && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) + { + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (TREE_OPERAND (base, 0)); + if (!pi) + return true; - for (i = 0; VEC_iterate (tree, aliases, i, al); i++) - if (al == tag) - return true; + return (pt_solution_includes_global (&pi->pt) + || pt_solutions_intersect (&cfun->gimple_df->escaped, &pi->pt)); } - return false; + return true; } +static bool ATTRIBUTE_UNUSED +call_may_clobber_ref_p (gimple call, tree ref) +{ + bool res; + ao_ref r; + ao_ref_init (&r, ref); + res = call_may_clobber_ref_p_1 (call, &r); + if (res) + ++alias_stats.call_may_clobber_ref_p_may_alias; + else + ++alias_stats.call_may_clobber_ref_p_no_alias; + return res; +} -/* Create a new symbol tag for PTR. Construct the may-alias list of this type - tag so that it has the aliasing of VAR. - Note, the set of aliases represented by the new symbol tag are not marked - for renaming. */ +/* If the statement STMT may clobber the memory reference REF return true, + otherwise return false. */ -void -new_type_alias (tree ptr, tree var) +bool +stmt_may_clobber_ref_p_1 (gimple stmt, ao_ref *ref) { - var_ann_t p_ann = var_ann (ptr); - tree tag_type = TREE_TYPE (TREE_TYPE (ptr)); - var_ann_t v_ann = var_ann (var); - tree tag; - subvar_t svars; - - gcc_assert (p_ann->symbol_mem_tag == NULL_TREE); - gcc_assert (!MTAG_P (var)); - - /* 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; - - tag = create_memory_tag (tag_type, true); - p_ann->symbol_mem_tag = tag; - - for (sv = svars; sv; sv = sv->next) - add_may_alias (tag, sv->var); - } - else + if (is_gimple_call (stmt)) { - /* 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. */ - VEC(tree, gc) *aliases = v_ann->may_aliases; - - if ((aliases != NULL) - && (VEC_length (tree, aliases) == 1)) + tree lhs = gimple_call_lhs (stmt); + if (lhs + && !is_gimple_reg (lhs)) { - tree ali = VEC_index (tree, aliases, 0); - - if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG) - { - p_ann->symbol_mem_tag = ali; - return; - } + ao_ref r; + ao_ref_init (&r, lhs); + if (refs_may_alias_p_1 (ref, &r, true)) + return true; } - tag = create_memory_tag (tag_type, true); - p_ann->symbol_mem_tag = tag; - - if (aliases == NULL) - add_may_alias (tag, var); - else - { - unsigned i; - tree al; - - for (i = 0; VEC_iterate (tree, aliases, i, al); i++) - add_may_alias (tag, al); - } - } + return call_may_clobber_ref_p_1 (stmt, ref); + } + else if (is_gimple_assign (stmt)) + { + ao_ref r; + ao_ref_init (&r, gimple_assign_lhs (stmt)); + return refs_may_alias_p_1 (ref, &r, true); + } + else if (gimple_code (stmt) == GIMPLE_ASM) + return true; - TREE_READONLY (tag) = TREE_READONLY (var); - MTAG_GLOBAL (tag) = is_global_var (var); + return false; } - - -/* 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) +bool +stmt_may_clobber_ref_p (gimple stmt, tree ref) { - 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); + ao_ref r; + ao_ref_init (&r, ref); + return stmt_may_clobber_ref_p_1 (stmt, &r); } -/* 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; -} +static tree get_continuation_for_phi (gimple, ao_ref *, bitmap *); -/* Free a used part map element. */ +/* Walk the virtual use-def chain of VUSE until hitting the virtual operand + TARGET or a statement clobbering the memory reference REF in which + case false is returned. The walk starts with VUSE, one argument of PHI. */ -static void -free_used_part_map (void *item) +static bool +maybe_skip_until (gimple phi, tree target, ao_ref *ref, + tree vuse, bitmap *visited) { - free (((struct used_part_map *)item)->to); - free (item); -} + if (!*visited) + *visited = BITMAP_ALLOC (NULL); -/* Lookup a used_part structure for a UID. */ + bitmap_set_bit (*visited, SSA_NAME_VERSION (PHI_RESULT (phi))); -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; + /* Walk until we hit the target. */ + while (vuse != target) + { + gimple def_stmt = SSA_NAME_DEF_STMT (vuse); + /* Recurse for PHI nodes. */ + if (gimple_code (def_stmt) == GIMPLE_PHI) + { + /* An already visited PHI node ends the walk successfully. */ + if (bitmap_bit_p (*visited, SSA_NAME_VERSION (PHI_RESULT (def_stmt)))) + return true; + vuse = get_continuation_for_phi (def_stmt, ref, visited); + if (!vuse) + return false; + continue; + } + /* A clobbering statement or the end of the IL ends it failing. */ + else if (gimple_nop_p (def_stmt) + || stmt_may_clobber_ref_p_1 (def_stmt, ref)) + return false; + vuse = gimple_vuse (def_stmt); + } + return true; } -/* 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; -} +/* Starting from a PHI node for the virtual operand of the memory reference + REF find a continuation virtual operand that allows to continue walking + statements dominating PHI skipping only statements that cannot possibly + clobber REF. Returns NULL_TREE if no suitable virtual operand can + be found. */ +static tree +get_continuation_for_phi (gimple phi, ao_ref *ref, bitmap *visited) +{ + unsigned nargs = gimple_phi_num_args (phi); -/* Given a variable uid, UID, get or create the entry in the used portions - table for the variable. */ + /* Through a single-argument PHI we can simply look through. */ + if (nargs == 1) + return PHI_ARG_DEF (phi, 0); -static used_part_t -get_or_create_used_part_for (size_t uid) -{ - used_part_t up; - if ((up = up_lookup (uid)) == NULL) + /* For two arguments try to skip non-aliasing code until we hit + the phi argument definition that dominates the other one. */ + if (nargs == 2) { - up = XCNEW (struct used_part); - up->minused = INT_MAX; - up->maxused = 0; - up->explicit_uses = false; - up->implicit_uses = false; - up->write_only = true; + tree arg0 = PHI_ARG_DEF (phi, 0); + tree arg1 = PHI_ARG_DEF (phi, 1); + gimple def0 = SSA_NAME_DEF_STMT (arg0); + gimple def1 = SSA_NAME_DEF_STMT (arg1); + + if (arg0 == arg1) + return arg0; + else if (gimple_nop_p (def0) + || (!gimple_nop_p (def1) + && dominated_by_p (CDI_DOMINATORS, + gimple_bb (def1), gimple_bb (def0)))) + { + if (maybe_skip_until (phi, arg0, ref, arg1, visited)) + return arg0; + } + else if (gimple_nop_p (def1) + || dominated_by_p (CDI_DOMINATORS, + gimple_bb (def0), gimple_bb (def1))) + { + if (maybe_skip_until (phi, arg1, ref, arg0, visited)) + return arg1; + } } - return up; + return NULL_TREE; } +/* Based on the memory reference REF and its virtual use VUSE call + WALKER for each virtual use that is equivalent to VUSE, including VUSE + itself. That is, for each virtual use for which its defining statement + does not clobber REF. -/* 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; -} + WALKER is called with REF, the current virtual use and DATA. If + WALKER returns non-NULL the walk stops and its result is returned. + At the end of a non-successful walk NULL is returned. + TRANSLATE if non-NULL is called with a pointer to REF, the virtual + use which definition is a statement that may clobber REF and DATA. + If TRANSLATE returns (void *)-1 the walk stops and NULL is returned. + If TRANSLATE returns non-NULL the walk stops and its result is returned. + If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed + to adjust REF and *DATA to make that valid. -/* Given an aggregate VAR, create the subvariables that represent its - fields. */ + TODO: Cache the vector of equivalent vuses per ref, vuse pair. */ -static void -create_overlap_variables_for (tree var) +void * +walk_non_aliased_vuses (ao_ref *ref, tree vuse, + void *(*walker)(ao_ref *, tree, void *), + void *(*translate)(ao_ref *, tree, void *), void *data) { - VEC(fieldoff_s,heap) *fieldstack = NULL; - used_part_t up; - size_t uid = DECL_UID (var); + bitmap visited = NULL; + void *res; - up = up_lookup (uid); - if (!up - || up->write_only) - return; + timevar_push (TV_ALIAS_STMT_WALK); - push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL); - if (VEC_length (fieldoff_s, fieldstack) != 0) + do { - 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++; - } + gimple def_stmt; - /* 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); + /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */ + res = (*walker) (ref, vuse, data); + if (res) + break; - for (i = VEC_length (fieldoff_s, fieldstack); - VEC_iterate (fieldoff_s, fieldstack, --i, fo);) + def_stmt = SSA_NAME_DEF_STMT (vuse); + if (gimple_nop_p (def_stmt)) + break; + else if (gimple_code (def_stmt) == GIMPLE_PHI) + vuse = get_continuation_for_phi (def_stmt, ref, &visited); + else { - 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) + if (stmt_may_clobber_ref_p_1 (def_stmt, ref)) { - 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"); + if (!translate) + break; + res = (*translate) (ref, vuse, data); + /* Failed lookup and translation. */ + if (res == (void *)-1) + { + res = NULL; + break; + } + /* Lookup succeeded. */ + else if (res != NULL) + break; + /* Translation succeeded, continue walking. */ } - - lastfotype = currfotype; - lastfooffset = fo->offset; - lastfosize = fosize; - *subvars = sv; + vuse = gimple_vuse (def_stmt); } + } + while (vuse); - /* 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. + if (visited) + BITMAP_FREE (visited); - 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); - } + timevar_pop (TV_ALIAS_STMT_WALK); - VEC_free (fieldoff_s, heap, fieldstack); + return res; } -/* 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. */ +/* Based on the memory reference REF call WALKER for each vdef which + defining statement may clobber REF, starting with VDEF. If REF + is NULL_TREE, each defining statement is visited. -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)); + WALKER is called with REF, the current vdef and DATA. If WALKER + returns true the walk is stopped, otherwise it continues. - 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; -} + At PHI nodes walk_aliased_vdefs forks into one walk for reach + PHI argument (but only one walk continues on merge points), the + return value is true if any of the walks was successful. -/* Create structure field variables for structures used in this function. */ + The function returns the number of statements walked. */ static unsigned int -create_structure_vars (void) +walk_aliased_vdefs_1 (tree ref, tree vdef, + bool (*walker)(tree, tree, void *), void *data, + bitmap *visited, unsigned int cnt) { - 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) + do { - block_stmt_iterator bsi; - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + gimple def_stmt = SSA_NAME_DEF_STMT (vdef); + + if (*visited + && !bitmap_set_bit (*visited, SSA_NAME_VERSION (vdef))) + return cnt; + + if (gimple_nop_p (def_stmt)) + return cnt; + else if (gimple_code (def_stmt) == GIMPLE_PHI) { - walk_tree_without_duplicates (bsi_stmt_ptr (bsi), - find_used_portions, - NULL); + unsigned i; + if (!*visited) + *visited = BITMAP_ALLOC (NULL); + for (i = 0; i < gimple_phi_num_args (def_stmt); ++i) + cnt += walk_aliased_vdefs_1 (ref, gimple_phi_arg_def (def_stmt, i), + walker, data, visited, 0); + return cnt; } + + /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */ + cnt++; + if ((!ref + || stmt_may_clobber_ref_p (def_stmt, ref)) + && (*walker) (ref, vdef, data)) + return cnt; + + vdef = gimple_vuse (def_stmt); } - 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; + while (1); } -static bool -gate_structure_vars (void) +unsigned int +walk_aliased_vdefs (tree ref, tree vdef, + bool (*walker)(tree, tree, void *), void *data, + bitmap *visited) { - return flag_tree_salias != 0; -} + bitmap local_visited = NULL; + unsigned int ret; -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. */ + timevar_push (TV_ALIAS_STMT_WALK); -static unsigned int -reset_cc_flags (void) -{ - tree var; - referenced_var_iterator rvi; + ret = walk_aliased_vdefs_1 (ref, vdef, walker, data, + visited ? visited : &local_visited, 0); + if (local_visited) + BITMAP_FREE (local_visited); - FOR_EACH_REFERENCED_VAR (var, rvi) - DECL_CALL_CLOBBERED (var) = false; - return 0; + timevar_pop (TV_ALIAS_STMT_WALK); + + return ret; } -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 */ -};