150397Sobrien/* Alias analysis for GNU C 2169689Skan Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 3117395Skan Free Software Foundation, Inc. 450397Sobrien Contributed by John Carr (jfc@mit.edu). 550397Sobrien 690075SobrienThis file is part of GCC. 750397Sobrien 890075SobrienGCC is free software; you can redistribute it and/or modify it under 990075Sobrienthe terms of the GNU General Public License as published by the Free 1090075SobrienSoftware Foundation; either version 2, or (at your option) any later 1190075Sobrienversion. 1250397Sobrien 1390075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1490075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1590075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1690075Sobrienfor more details. 1750397Sobrien 1850397SobrienYou should have received a copy of the GNU General Public License 1990075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 20169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 21169689Skan02110-1301, USA. */ 2250397Sobrien 2350397Sobrien#include "config.h" 2450397Sobrien#include "system.h" 25132718Skan#include "coretypes.h" 26132718Skan#include "tm.h" 2750397Sobrien#include "rtl.h" 2890075Sobrien#include "tree.h" 2990075Sobrien#include "tm_p.h" 3090075Sobrien#include "function.h" 31169689Skan#include "alias.h" 32169689Skan#include "emit-rtl.h" 3350397Sobrien#include "regs.h" 3450397Sobrien#include "hard-reg-set.h" 3590075Sobrien#include "basic-block.h" 3650397Sobrien#include "flags.h" 3752284Sobrien#include "output.h" 3850397Sobrien#include "toplev.h" 3990075Sobrien#include "cselib.h" 4052284Sobrien#include "splay-tree.h" 4190075Sobrien#include "ggc.h" 4290075Sobrien#include "langhooks.h" 43132718Skan#include "timevar.h" 44117395Skan#include "target.h" 45132718Skan#include "cgraph.h" 46132718Skan#include "varray.h" 47169689Skan#include "tree-pass.h" 48169689Skan#include "ipa-type-escape.h" 4950397Sobrien 50169689Skan/* The aliasing API provided here solves related but different problems: 51169689Skan 52169689Skan Say there exists (in c) 53169689Skan 54169689Skan struct X { 55169689Skan struct Y y1; 56169689Skan struct Z z2; 57169689Skan } x1, *px1, *px2; 58169689Skan 59169689Skan struct Y y2, *py; 60169689Skan struct Z z2, *pz; 61169689Skan 62169689Skan 63169689Skan py = &px1.y1; 64169689Skan px2 = &x1; 65169689Skan 66169689Skan Consider the four questions: 67169689Skan 68169689Skan Can a store to x1 interfere with px2->y1? 69169689Skan Can a store to x1 interfere with px2->z2? 70169689Skan (*px2).z2 71169689Skan Can a store to x1 change the value pointed to by with py? 72169689Skan Can a store to x1 change the value pointed to by with pz? 73169689Skan 74169689Skan The answer to these questions can be yes, yes, yes, and maybe. 75169689Skan 76169689Skan The first two questions can be answered with a simple examination 77169689Skan of the type system. If structure X contains a field of type Y then 78169689Skan a store thru a pointer to an X can overwrite any field that is 79169689Skan contained (recursively) in an X (unless we know that px1 != px2). 80169689Skan 81169689Skan The last two of the questions can be solved in the same way as the 82169689Skan first two questions but this is too conservative. The observation 83169689Skan is that in some cases analysis we can know if which (if any) fields 84169689Skan are addressed and if those addresses are used in bad ways. This 85169689Skan analysis may be language specific. In C, arbitrary operations may 86169689Skan be applied to pointers. However, there is some indication that 87169689Skan this may be too conservative for some C++ types. 88169689Skan 89169689Skan The pass ipa-type-escape does this analysis for the types whose 90169689Skan instances do not escape across the compilation boundary. 91169689Skan 92169689Skan Historically in GCC, these two problems were combined and a single 93169689Skan data structure was used to represent the solution to these 94169689Skan problems. We now have two similar but different data structures, 95169689Skan The data structure to solve the last two question is similar to the 96169689Skan first, but does not contain have the fields in it whose address are 97169689Skan never taken. For types that do escape the compilation unit, the 98169689Skan data structures will have identical information. 99169689Skan*/ 100169689Skan 10152284Sobrien/* The alias sets assigned to MEMs assist the back-end in determining 10252284Sobrien which MEMs can alias which other MEMs. In general, two MEMs in 10390075Sobrien different alias sets cannot alias each other, with one important 10490075Sobrien exception. Consider something like: 10552284Sobrien 106132718Skan struct S { int i; double d; }; 10752284Sobrien 10852284Sobrien a store to an `S' can alias something of either type `int' or type 10952284Sobrien `double'. (However, a store to an `int' cannot alias a `double' 11052284Sobrien and vice versa.) We indicate this via a tree structure that looks 11152284Sobrien like: 112169689Skan struct S 113169689Skan / \ 11452284Sobrien / \ 115169689Skan |/_ _\| 116169689Skan int double 11752284Sobrien 11890075Sobrien (The arrows are directed and point downwards.) 11990075Sobrien In this situation we say the alias set for `struct S' is the 12090075Sobrien `superset' and that those for `int' and `double' are `subsets'. 12152284Sobrien 12290075Sobrien To see whether two alias sets can point to the same memory, we must 12390075Sobrien see if either alias set is a subset of the other. We need not trace 124132718Skan past immediate descendants, however, since we propagate all 12590075Sobrien grandchildren up one level. 12690075Sobrien 12752284Sobrien Alias set zero is implicitly a superset of all other alias sets. 12852284Sobrien However, this is no actual entry for alias set zero. It is an 12952284Sobrien error to attempt to explicitly construct a subset of zero. */ 13052284Sobrien 131132718Skanstruct alias_set_entry GTY(()) 13290075Sobrien{ 13352284Sobrien /* The alias set number, as stored in MEM_ALIAS_SET. */ 13490075Sobrien HOST_WIDE_INT alias_set; 13552284Sobrien 13652284Sobrien /* The children of the alias set. These are not just the immediate 137132718Skan children, but, in fact, all descendants. So, if we have: 13852284Sobrien 139117395Skan struct T { struct S s; float f; } 14052284Sobrien 14152284Sobrien continuing our example above, the children here will be all of 14252284Sobrien `int', `double', `float', and `struct S'. */ 143132718Skan splay_tree GTY((param1_is (int), param2_is (int))) children; 14452284Sobrien 14590075Sobrien /* Nonzero if would have a child of zero: this effectively makes this 14690075Sobrien alias set the same as alias set zero. */ 14790075Sobrien int has_zero_child; 148132718Skan}; 149132718Skantypedef struct alias_set_entry *alias_set_entry; 15050397Sobrien 151132718Skanstatic int rtx_equal_for_memref_p (rtx, rtx); 152132718Skanstatic rtx find_symbolic_term (rtx); 153132718Skanstatic int memrefs_conflict_p (int, rtx, int, rtx, HOST_WIDE_INT); 154132718Skanstatic void record_set (rtx, rtx, void *); 155132718Skanstatic int base_alias_check (rtx, rtx, enum machine_mode, 156132718Skan enum machine_mode); 157132718Skanstatic rtx find_base_value (rtx); 158132718Skanstatic int mems_in_disjoint_alias_sets_p (rtx, rtx); 159132718Skanstatic int insert_subset_children (splay_tree_node, void*); 160132718Skanstatic tree find_base_decl (tree); 161132718Skanstatic alias_set_entry get_alias_set_entry (HOST_WIDE_INT); 162132718Skanstatic rtx fixed_scalar_and_varying_struct_p (rtx, rtx, rtx, rtx, 163132718Skan int (*) (rtx, int)); 164132718Skanstatic int aliases_everything_p (rtx); 165132718Skanstatic bool nonoverlapping_component_refs_p (tree, tree); 166132718Skanstatic tree decl_for_component_ref (tree); 167132718Skanstatic rtx adjust_offset_for_component_ref (tree, rtx); 168132718Skanstatic int nonoverlapping_memrefs_p (rtx, rtx); 169169689Skanstatic int write_dependence_p (rtx, rtx, int); 170117395Skan 171132718Skanstatic void memory_modified_1 (rtx, rtx, void *); 172169689Skanstatic void record_alias_subset (HOST_WIDE_INT, HOST_WIDE_INT); 17390075Sobrien 17450397Sobrien/* Set up all info needed to perform alias analysis on memory references. */ 17550397Sobrien 17690075Sobrien/* Returns the size in bytes of the mode of X. */ 17750397Sobrien#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X))) 17850397Sobrien 17950397Sobrien/* Returns nonzero if MEM1 and MEM2 do not alias because they are in 18052284Sobrien different alias sets. We ignore alias sets in functions making use 18152284Sobrien of variable arguments because the va_arg macros on some systems are 18252284Sobrien not legal ANSI C. */ 18352284Sobrien#define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \ 18452284Sobrien mems_in_disjoint_alias_sets_p (MEM1, MEM2) 18550397Sobrien 18650397Sobrien/* Cap the number of passes we make over the insns propagating alias 18790075Sobrien information through set chains. 10 is a completely arbitrary choice. */ 18850397Sobrien#define MAX_ALIAS_LOOP_PASSES 10 189117395Skan 19050397Sobrien/* reg_base_value[N] gives an address to which register N is related. 19150397Sobrien If all sets after the first add or subtract to the current value 19250397Sobrien or otherwise modify it so it does not point to a different top level 19350397Sobrien object, reg_base_value[N] is equal to the address part of the source 19450397Sobrien of the first set. 19550397Sobrien 19650397Sobrien A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS 19750397Sobrien expressions represent certain special values: function arguments and 198117395Skan the stack, frame, and argument pointers. 19950397Sobrien 20090075Sobrien The contents of an ADDRESS is not normally used, the mode of the 20190075Sobrien ADDRESS determines whether the ADDRESS is a function argument or some 20290075Sobrien other special value. Pointer equality, not rtx_equal_p, determines whether 20390075Sobrien two ADDRESS expressions refer to the same base address. 20490075Sobrien 20590075Sobrien The only use of the contents of an ADDRESS is for determining if the 20690075Sobrien current function performs nonlocal memory memory references for the 20790075Sobrien purposes of marking the function as a constant function. */ 20890075Sobrien 209169689Skanstatic GTY(()) VEC(rtx,gc) *reg_base_value; 21090075Sobrienstatic rtx *new_reg_base_value; 21190075Sobrien 212132718Skan/* We preserve the copy of old array around to avoid amount of garbage 213132718Skan produced. About 8% of garbage produced were attributed to this 214132718Skan array. */ 215169689Skanstatic GTY((deletable)) VEC(rtx,gc) *old_reg_base_value; 216132718Skan 217117395Skan/* Static hunks of RTL used by the aliasing code; these are initialized 218117395Skan once per function to avoid unnecessary RTL allocations. */ 219117395Skanstatic GTY (()) rtx static_reg_base_value[FIRST_PSEUDO_REGISTER]; 220117395Skan 221169689Skan#define REG_BASE_VALUE(X) \ 222169689Skan (REGNO (X) < VEC_length (rtx, reg_base_value) \ 223169689Skan ? VEC_index (rtx, reg_base_value, REGNO (X)) : 0) 22450397Sobrien 22590075Sobrien/* Vector indexed by N giving the initial (unchanging) value known for 226132718Skan pseudo-register N. This array is initialized in init_alias_analysis, 227132718Skan and does not change until end_alias_analysis is called. */ 228132718Skanstatic GTY((length("reg_known_value_size"))) rtx *reg_known_value; 22950397Sobrien 23050397Sobrien/* Indicates number of valid entries in reg_known_value. */ 231132718Skanstatic GTY(()) unsigned int reg_known_value_size; 23250397Sobrien 23350397Sobrien/* Vector recording for each reg_known_value whether it is due to a 23450397Sobrien REG_EQUIV note. Future passes (viz., reload) may replace the 23550397Sobrien pseudo with the equivalent expression and so we account for the 23690075Sobrien dependences that would be introduced if that happens. 23790075Sobrien 23890075Sobrien The REG_EQUIV notes created in assign_parms may mention the arg 23990075Sobrien pointer, and there are explicit insns in the RTL that modify the 24090075Sobrien arg pointer. Thus we must ensure that such insns don't get 24190075Sobrien scheduled across each other because that would invalidate the 24290075Sobrien REG_EQUIV notes. One could argue that the REG_EQUIV notes are 24390075Sobrien wrong, but solving the problem in the scheduler will likely give 24490075Sobrien better code, so we do it here. */ 245132718Skanstatic bool *reg_known_equiv_p; 24650397Sobrien 24750397Sobrien/* True when scanning insns from the start of the rtl to the 24850397Sobrien NOTE_INSN_FUNCTION_BEG note. */ 249117395Skanstatic bool copying_arguments; 25050397Sobrien 251169689SkanDEF_VEC_P(alias_set_entry); 252169689SkanDEF_VEC_ALLOC_P(alias_set_entry,gc); 253169689Skan 25452284Sobrien/* The splay-tree used to store the various alias set entries. */ 255169689Skanstatic GTY (()) VEC(alias_set_entry,gc) *alias_sets; 25690075Sobrien 25752284Sobrien/* Returns a pointer to the alias set entry for ALIAS_SET, if there is 25852284Sobrien such an entry, or NULL otherwise. */ 25952284Sobrien 260132718Skanstatic inline alias_set_entry 261132718Skanget_alias_set_entry (HOST_WIDE_INT alias_set) 26252284Sobrien{ 263169689Skan return VEC_index (alias_set_entry, alias_sets, alias_set); 26452284Sobrien} 26552284Sobrien 26690075Sobrien/* Returns nonzero if the alias sets for MEM1 and MEM2 are such that 26790075Sobrien the two MEMs cannot alias each other. */ 26852284Sobrien 269132718Skanstatic inline int 270132718Skanmems_in_disjoint_alias_sets_p (rtx mem1, rtx mem2) 27152284Sobrien{ 27252284Sobrien/* Perform a basic sanity check. Namely, that there are no alias sets 27352284Sobrien if we're not using strict aliasing. This helps to catch bugs 27452284Sobrien whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or 27552284Sobrien where a MEM is allocated in some way other than by the use of 27652284Sobrien gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to 27752284Sobrien use alias sets to indicate that spilled registers cannot alias each 27852284Sobrien other, we might need to remove this check. */ 279169689Skan gcc_assert (flag_strict_aliasing 280169689Skan || (!MEM_ALIAS_SET (mem1) && !MEM_ALIAS_SET (mem2))); 28152284Sobrien 28290075Sobrien return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), MEM_ALIAS_SET (mem2)); 28390075Sobrien} 28490075Sobrien 28590075Sobrien/* Insert the NODE into the splay tree given by DATA. Used by 28690075Sobrien record_alias_subset via splay_tree_foreach. */ 28790075Sobrien 28890075Sobrienstatic int 289132718Skaninsert_subset_children (splay_tree_node node, void *data) 29090075Sobrien{ 29190075Sobrien splay_tree_insert ((splay_tree) data, node->key, node->value); 29290075Sobrien 29390075Sobrien return 0; 29490075Sobrien} 29590075Sobrien 29690075Sobrien/* Return 1 if the two specified alias sets may conflict. */ 29790075Sobrien 29890075Sobrienint 299132718Skanalias_sets_conflict_p (HOST_WIDE_INT set1, HOST_WIDE_INT set2) 30090075Sobrien{ 30190075Sobrien alias_set_entry ase; 30290075Sobrien 30390075Sobrien /* If have no alias set information for one of the operands, we have 30490075Sobrien to assume it can alias anything. */ 30590075Sobrien if (set1 == 0 || set2 == 0 30690075Sobrien /* If the two alias sets are the same, they may alias. */ 30790075Sobrien || set1 == set2) 30890075Sobrien return 1; 30990075Sobrien 31090075Sobrien /* See if the first alias set is a subset of the second. */ 31190075Sobrien ase = get_alias_set_entry (set1); 31290075Sobrien if (ase != 0 31390075Sobrien && (ase->has_zero_child 31490075Sobrien || splay_tree_lookup (ase->children, 31590075Sobrien (splay_tree_key) set2))) 31690075Sobrien return 1; 31790075Sobrien 31890075Sobrien /* Now do the same, but with the alias sets reversed. */ 31990075Sobrien ase = get_alias_set_entry (set2); 32090075Sobrien if (ase != 0 32190075Sobrien && (ase->has_zero_child 32290075Sobrien || splay_tree_lookup (ase->children, 32390075Sobrien (splay_tree_key) set1))) 32490075Sobrien return 1; 32590075Sobrien 32690075Sobrien /* The two alias sets are distinct and neither one is the 32790075Sobrien child of the other. Therefore, they cannot alias. */ 32890075Sobrien return 0; 32990075Sobrien} 33090075Sobrien 331169689Skan/* Return 1 if the two specified alias sets might conflict, or if any subtype 332169689Skan of these alias sets might conflict. */ 333169689Skan 33490075Sobrienint 335169689Skanalias_sets_might_conflict_p (HOST_WIDE_INT set1, HOST_WIDE_INT set2) 33690075Sobrien{ 337169689Skan if (set1 == 0 || set2 == 0 || set1 == set2) 338169689Skan return 1; 33990075Sobrien 34090075Sobrien return 0; 34190075Sobrien} 342169689Skan 34390075Sobrien 34490075Sobrien/* Return 1 if any MEM object of type T1 will always conflict (using the 34590075Sobrien dependency routines in this file) with any MEM object of type T2. 34690075Sobrien This is used when allocating temporary storage. If T1 and/or T2 are 34790075Sobrien NULL_TREE, it means we know nothing about the storage. */ 34890075Sobrien 34990075Sobrienint 350132718Skanobjects_must_conflict_p (tree t1, tree t2) 35190075Sobrien{ 352117395Skan HOST_WIDE_INT set1, set2; 353117395Skan 35490075Sobrien /* If neither has a type specified, we don't know if they'll conflict 35590075Sobrien because we may be using them to store objects of various types, for 35690075Sobrien example the argument and local variables areas of inlined functions. */ 35790075Sobrien if (t1 == 0 && t2 == 0) 35852284Sobrien return 0; 35952284Sobrien 36090075Sobrien /* If they are the same type, they must conflict. */ 36190075Sobrien if (t1 == t2 36290075Sobrien /* Likewise if both are volatile. */ 36390075Sobrien || (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2))) 36490075Sobrien return 1; 36552284Sobrien 366117395Skan set1 = t1 ? get_alias_set (t1) : 0; 367117395Skan set2 = t2 ? get_alias_set (t2) : 0; 36852284Sobrien 369117395Skan /* Otherwise they conflict if they have no alias set or the same. We 370117395Skan can't simply use alias_sets_conflict_p here, because we must make 371117395Skan sure that every subtype of t1 will conflict with every subtype of 372117395Skan t2 for which a pair of subobjects of these respective subtypes 373117395Skan overlaps on the stack. */ 374117395Skan return set1 == 0 || set2 == 0 || set1 == set2; 37552284Sobrien} 37690075Sobrien 37790075Sobrien/* T is an expression with pointer type. Find the DECL on which this 37890075Sobrien expression is based. (For example, in `a[i]' this would be `a'.) 37990075Sobrien If there is no such DECL, or a unique decl cannot be determined, 38090075Sobrien NULL_TREE is returned. */ 38152284Sobrien 38290075Sobrienstatic tree 383132718Skanfind_base_decl (tree t) 38490075Sobrien{ 385169689Skan tree d0, d1; 38652284Sobrien 38790075Sobrien if (t == 0 || t == error_mark_node || ! POINTER_TYPE_P (TREE_TYPE (t))) 38890075Sobrien return 0; 38990075Sobrien 390169689Skan /* If this is a declaration, return it. If T is based on a restrict 391169689Skan qualified decl, return that decl. */ 392169689Skan if (DECL_P (t)) 393169689Skan { 394169689Skan if (TREE_CODE (t) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (t)) 395169689Skan t = DECL_GET_RESTRICT_BASE (t); 396169689Skan return t; 397169689Skan } 39890075Sobrien 39990075Sobrien /* Handle general expressions. It would be nice to deal with 40090075Sobrien COMPONENT_REFs here. If we could tell that `a' and `b' were the 40190075Sobrien same, then `a->f' and `b->f' are also the same. */ 40290075Sobrien switch (TREE_CODE_CLASS (TREE_CODE (t))) 40390075Sobrien { 404169689Skan case tcc_unary: 40590075Sobrien return find_base_decl (TREE_OPERAND (t, 0)); 40690075Sobrien 407169689Skan case tcc_binary: 40890075Sobrien /* Return 0 if found in neither or both are the same. */ 40990075Sobrien d0 = find_base_decl (TREE_OPERAND (t, 0)); 41090075Sobrien d1 = find_base_decl (TREE_OPERAND (t, 1)); 41190075Sobrien if (d0 == d1) 41290075Sobrien return d0; 41390075Sobrien else if (d0 == 0) 41490075Sobrien return d1; 41590075Sobrien else if (d1 == 0) 41690075Sobrien return d0; 41790075Sobrien else 41890075Sobrien return 0; 41990075Sobrien 42090075Sobrien default: 42190075Sobrien return 0; 42290075Sobrien } 42390075Sobrien} 42490075Sobrien 425169689Skan/* Return true if all nested component references handled by 426169689Skan get_inner_reference in T are such that we should use the alias set 427169689Skan provided by the object at the heart of T. 42890075Sobrien 429169689Skan This is true for non-addressable components (which don't have their 430169689Skan own alias set), as well as components of objects in alias set zero. 431169689Skan This later point is a special case wherein we wish to override the 432169689Skan alias set used by the component, but we don't have per-FIELD_DECL 433169689Skan assignable alias sets. */ 434169689Skan 435169689Skanbool 436169689Skancomponent_uses_parent_alias_set (tree t) 43752284Sobrien{ 438169689Skan while (1) 439169689Skan { 440169689Skan /* If we're at the end, it vacuously uses its own alias set. */ 441169689Skan if (!handled_component_p (t)) 442169689Skan return false; 44352284Sobrien 444169689Skan switch (TREE_CODE (t)) 445169689Skan { 446169689Skan case COMPONENT_REF: 447169689Skan if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1))) 448169689Skan return true; 449169689Skan break; 45090075Sobrien 451169689Skan case ARRAY_REF: 452169689Skan case ARRAY_RANGE_REF: 453169689Skan if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0)))) 454169689Skan return true; 455169689Skan break; 45690075Sobrien 457169689Skan case REALPART_EXPR: 458169689Skan case IMAGPART_EXPR: 459169689Skan break; 46090075Sobrien 461169689Skan default: 462169689Skan /* Bitfields and casts are never addressable. */ 463169689Skan return true; 464169689Skan } 465169689Skan 466169689Skan t = TREE_OPERAND (t, 0); 467169689Skan if (get_alias_set (TREE_TYPE (t)) == 0) 468169689Skan return true; 469169689Skan } 47052284Sobrien} 47152284Sobrien 47290075Sobrien/* Return the alias set for T, which may be either a type or an 47390075Sobrien expression. Call language-specific routine for help, if needed. */ 47490075Sobrien 47590075SobrienHOST_WIDE_INT 476132718Skanget_alias_set (tree t) 47790075Sobrien{ 47890075Sobrien HOST_WIDE_INT set; 47990075Sobrien 48090075Sobrien /* If we're not doing any alias analysis, just assume everything 48190075Sobrien aliases everything else. Also return 0 if this or its type is 48290075Sobrien an error. */ 48390075Sobrien if (! flag_strict_aliasing || t == error_mark_node 48490075Sobrien || (! TYPE_P (t) 48590075Sobrien && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node))) 48690075Sobrien return 0; 48790075Sobrien 48890075Sobrien /* We can be passed either an expression or a type. This and the 48990075Sobrien language-specific routine may make mutually-recursive calls to each other 49090075Sobrien to figure out what to do. At each juncture, we see if this is a tree 49190075Sobrien that the language may need to handle specially. First handle things that 49290075Sobrien aren't types. */ 49390075Sobrien if (! TYPE_P (t)) 49490075Sobrien { 49590075Sobrien tree inner = t; 49690075Sobrien 49790075Sobrien /* Remove any nops, then give the language a chance to do 49890075Sobrien something with this tree before we look at it. */ 49990075Sobrien STRIP_NOPS (t); 500169689Skan set = lang_hooks.get_alias_set (t); 50190075Sobrien if (set != -1) 50290075Sobrien return set; 50390075Sobrien 50490075Sobrien /* First see if the actual object referenced is an INDIRECT_REF from a 505169689Skan restrict-qualified pointer or a "void *". */ 506169689Skan while (handled_component_p (inner)) 50790075Sobrien { 508169689Skan inner = TREE_OPERAND (inner, 0); 50990075Sobrien STRIP_NOPS (inner); 51090075Sobrien } 51190075Sobrien 51290075Sobrien /* Check for accesses through restrict-qualified pointers. */ 513169689Skan if (INDIRECT_REF_P (inner)) 51490075Sobrien { 51590075Sobrien tree decl = find_base_decl (TREE_OPERAND (inner, 0)); 51690075Sobrien 51790075Sobrien if (decl && DECL_POINTER_ALIAS_SET_KNOWN_P (decl)) 51890075Sobrien { 51990075Sobrien /* If we haven't computed the actual alias set, do it now. */ 52090075Sobrien if (DECL_POINTER_ALIAS_SET (decl) == -2) 52190075Sobrien { 522132718Skan tree pointed_to_type = TREE_TYPE (TREE_TYPE (decl)); 523132718Skan 52490075Sobrien /* No two restricted pointers can point at the same thing. 52590075Sobrien However, a restricted pointer can point at the same thing 52690075Sobrien as an unrestricted pointer, if that unrestricted pointer 52790075Sobrien is based on the restricted pointer. So, we make the 52890075Sobrien alias set for the restricted pointer a subset of the 52990075Sobrien alias set for the type pointed to by the type of the 53090075Sobrien decl. */ 53190075Sobrien HOST_WIDE_INT pointed_to_alias_set 532132718Skan = get_alias_set (pointed_to_type); 53390075Sobrien 53490075Sobrien if (pointed_to_alias_set == 0) 53590075Sobrien /* It's not legal to make a subset of alias set zero. */ 536132718Skan DECL_POINTER_ALIAS_SET (decl) = 0; 537132718Skan else if (AGGREGATE_TYPE_P (pointed_to_type)) 538132718Skan /* For an aggregate, we must treat the restricted 539132718Skan pointer the same as an ordinary pointer. If we 540132718Skan were to make the type pointed to by the 541132718Skan restricted pointer a subset of the pointed-to 542132718Skan type, then we would believe that other subsets 543132718Skan of the pointed-to type (such as fields of that 544132718Skan type) do not conflict with the type pointed to 545169689Skan by the restricted pointer. */ 546132718Skan DECL_POINTER_ALIAS_SET (decl) 547132718Skan = pointed_to_alias_set; 54890075Sobrien else 54990075Sobrien { 55090075Sobrien DECL_POINTER_ALIAS_SET (decl) = new_alias_set (); 551117395Skan record_alias_subset (pointed_to_alias_set, 552117395Skan DECL_POINTER_ALIAS_SET (decl)); 55390075Sobrien } 55490075Sobrien } 55590075Sobrien 55690075Sobrien /* We use the alias set indicated in the declaration. */ 55790075Sobrien return DECL_POINTER_ALIAS_SET (decl); 55890075Sobrien } 55990075Sobrien 56090075Sobrien /* If we have an INDIRECT_REF via a void pointer, we don't 561169689Skan know anything about what that might alias. Likewise if the 562169689Skan pointer is marked that way. */ 563169689Skan else if (TREE_CODE (TREE_TYPE (inner)) == VOID_TYPE 564169689Skan || (TYPE_REF_CAN_ALIAS_ALL 565169689Skan (TREE_TYPE (TREE_OPERAND (inner, 0))))) 56690075Sobrien return 0; 56790075Sobrien } 56890075Sobrien 56990075Sobrien /* Otherwise, pick up the outermost object that we could have a pointer 570169689Skan to, processing conversions as above. */ 571169689Skan while (component_uses_parent_alias_set (t)) 57290075Sobrien { 573169689Skan t = TREE_OPERAND (t, 0); 57490075Sobrien STRIP_NOPS (t); 57590075Sobrien } 57690075Sobrien 57790075Sobrien /* If we've already determined the alias set for a decl, just return 57890075Sobrien it. This is necessary for C++ anonymous unions, whose component 57990075Sobrien variables don't look like union members (boo!). */ 58090075Sobrien if (TREE_CODE (t) == VAR_DECL 581169689Skan && DECL_RTL_SET_P (t) && MEM_P (DECL_RTL (t))) 58290075Sobrien return MEM_ALIAS_SET (DECL_RTL (t)); 58390075Sobrien 58490075Sobrien /* Now all we care about is the type. */ 58590075Sobrien t = TREE_TYPE (t); 58690075Sobrien } 58790075Sobrien 58890075Sobrien /* Variant qualifiers don't affect the alias set, so get the main 58990075Sobrien variant. If this is a type with a known alias set, return it. */ 59090075Sobrien t = TYPE_MAIN_VARIANT (t); 59190075Sobrien if (TYPE_ALIAS_SET_KNOWN_P (t)) 59290075Sobrien return TYPE_ALIAS_SET (t); 59390075Sobrien 59490075Sobrien /* See if the language has special handling for this type. */ 595169689Skan set = lang_hooks.get_alias_set (t); 59690075Sobrien if (set != -1) 59790075Sobrien return set; 59890075Sobrien 59990075Sobrien /* There are no objects of FUNCTION_TYPE, so there's no point in 60090075Sobrien using up an alias set for them. (There are, of course, pointers 60190075Sobrien and references to functions, but that's different.) */ 60290075Sobrien else if (TREE_CODE (t) == FUNCTION_TYPE) 60390075Sobrien set = 0; 604102780Skan 605102780Skan /* Unless the language specifies otherwise, let vector types alias 606102780Skan their components. This avoids some nasty type punning issues in 607102780Skan normal usage. And indeed lets vectors be treated more like an 608102780Skan array slice. */ 609102780Skan else if (TREE_CODE (t) == VECTOR_TYPE) 610102780Skan set = get_alias_set (TREE_TYPE (t)); 611102780Skan 61290075Sobrien else 61390075Sobrien /* Otherwise make a new alias set for this type. */ 61490075Sobrien set = new_alias_set (); 61590075Sobrien 61690075Sobrien TYPE_ALIAS_SET (t) = set; 61790075Sobrien 61890075Sobrien /* If this is an aggregate type, we must record any component aliasing 61990075Sobrien information. */ 62090075Sobrien if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE) 62190075Sobrien record_component_aliases (t); 62290075Sobrien 62390075Sobrien return set; 62490075Sobrien} 62590075Sobrien 62690075Sobrien/* Return a brand-new alias set. */ 62790075Sobrien 62890075SobrienHOST_WIDE_INT 629132718Skannew_alias_set (void) 63090075Sobrien{ 63190075Sobrien if (flag_strict_aliasing) 632132718Skan { 633169689Skan if (alias_sets == 0) 634169689Skan VEC_safe_push (alias_set_entry, gc, alias_sets, 0); 635169689Skan VEC_safe_push (alias_set_entry, gc, alias_sets, 0); 636169689Skan return VEC_length (alias_set_entry, alias_sets) - 1; 637132718Skan } 63890075Sobrien else 63990075Sobrien return 0; 64090075Sobrien} 64190075Sobrien 642132718Skan/* Indicate that things in SUBSET can alias things in SUPERSET, but that 643132718Skan not everything that aliases SUPERSET also aliases SUBSET. For example, 644132718Skan in C, a store to an `int' can alias a load of a structure containing an 645132718Skan `int', and vice versa. But it can't alias a load of a 'double' member 646132718Skan of the same structure. Here, the structure would be the SUPERSET and 647132718Skan `int' the SUBSET. This relationship is also described in the comment at 648132718Skan the beginning of this file. 64952284Sobrien 650132718Skan This function should be called only once per SUPERSET/SUBSET pair. 651132718Skan 65252284Sobrien It is illegal for SUPERSET to be zero; everything is implicitly a 65352284Sobrien subset of alias set zero. */ 65452284Sobrien 655169689Skanstatic void 656132718Skanrecord_alias_subset (HOST_WIDE_INT superset, HOST_WIDE_INT subset) 65752284Sobrien{ 65852284Sobrien alias_set_entry superset_entry; 65952284Sobrien alias_set_entry subset_entry; 66052284Sobrien 66190075Sobrien /* It is possible in complex type situations for both sets to be the same, 66290075Sobrien in which case we can ignore this operation. */ 66390075Sobrien if (superset == subset) 66490075Sobrien return; 66590075Sobrien 666169689Skan gcc_assert (superset); 66752284Sobrien 66852284Sobrien superset_entry = get_alias_set_entry (superset); 669117395Skan if (superset_entry == 0) 67052284Sobrien { 67152284Sobrien /* Create an entry for the SUPERSET, so that we have a place to 67252284Sobrien attach the SUBSET. */ 673132718Skan superset_entry = ggc_alloc (sizeof (struct alias_set_entry)); 67452284Sobrien superset_entry->alias_set = superset; 675117395Skan superset_entry->children 676132718Skan = splay_tree_new_ggc (splay_tree_compare_ints); 67790075Sobrien superset_entry->has_zero_child = 0; 678169689Skan VEC_replace (alias_set_entry, alias_sets, superset, superset_entry); 67990075Sobrien } 68052284Sobrien 68190075Sobrien if (subset == 0) 68290075Sobrien superset_entry->has_zero_child = 1; 68390075Sobrien else 68490075Sobrien { 68590075Sobrien subset_entry = get_alias_set_entry (subset); 68690075Sobrien /* If there is an entry for the subset, enter all of its children 68790075Sobrien (if they are not already present) as children of the SUPERSET. */ 688117395Skan if (subset_entry) 68990075Sobrien { 69090075Sobrien if (subset_entry->has_zero_child) 69190075Sobrien superset_entry->has_zero_child = 1; 69290075Sobrien 69390075Sobrien splay_tree_foreach (subset_entry->children, insert_subset_children, 69490075Sobrien superset_entry->children); 69590075Sobrien } 69690075Sobrien 69790075Sobrien /* Enter the SUBSET itself as a child of the SUPERSET. */ 698117395Skan splay_tree_insert (superset_entry->children, 69990075Sobrien (splay_tree_key) subset, 0); 70052284Sobrien } 70190075Sobrien} 70252284Sobrien 70390075Sobrien/* Record that component types of TYPE, if any, are part of that type for 70490075Sobrien aliasing purposes. For record types, we only record component types 70590075Sobrien for fields that are marked addressable. For array types, we always 70690075Sobrien record the component types, so the front end should not call this 70790075Sobrien function if the individual component aren't addressable. */ 70852284Sobrien 70990075Sobrienvoid 710132718Skanrecord_component_aliases (tree type) 71190075Sobrien{ 71290075Sobrien HOST_WIDE_INT superset = get_alias_set (type); 71390075Sobrien tree field; 71490075Sobrien 71590075Sobrien if (superset == 0) 71690075Sobrien return; 71790075Sobrien 71890075Sobrien switch (TREE_CODE (type)) 71990075Sobrien { 72090075Sobrien case ARRAY_TYPE: 72190075Sobrien if (! TYPE_NONALIASED_COMPONENT (type)) 72290075Sobrien record_alias_subset (superset, get_alias_set (TREE_TYPE (type))); 72390075Sobrien break; 72490075Sobrien 72590075Sobrien case RECORD_TYPE: 72690075Sobrien case UNION_TYPE: 72790075Sobrien case QUAL_UNION_TYPE: 728132718Skan /* Recursively record aliases for the base classes, if there are any. */ 729169689Skan if (TYPE_BINFO (type)) 730117395Skan { 731117395Skan int i; 732169689Skan tree binfo, base_binfo; 733169689Skan 734169689Skan for (binfo = TYPE_BINFO (type), i = 0; 735169689Skan BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) 736169689Skan record_alias_subset (superset, 737169689Skan get_alias_set (BINFO_TYPE (base_binfo))); 738117395Skan } 73990075Sobrien for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field)) 74090075Sobrien if (TREE_CODE (field) == FIELD_DECL && ! DECL_NONADDRESSABLE_P (field)) 74190075Sobrien record_alias_subset (superset, get_alias_set (TREE_TYPE (field))); 74290075Sobrien break; 74390075Sobrien 74490075Sobrien case COMPLEX_TYPE: 74590075Sobrien record_alias_subset (superset, get_alias_set (TREE_TYPE (type))); 74690075Sobrien break; 74790075Sobrien 74890075Sobrien default: 74990075Sobrien break; 75090075Sobrien } 75152284Sobrien} 75252284Sobrien 75390075Sobrien/* Allocate an alias set for use in storing and reading from the varargs 75490075Sobrien spill area. */ 75590075Sobrien 756132718Skanstatic GTY(()) HOST_WIDE_INT varargs_set = -1; 757132718Skan 75890075SobrienHOST_WIDE_INT 759132718Skanget_varargs_alias_set (void) 76090075Sobrien{ 761169689Skan#if 1 762169689Skan /* We now lower VA_ARG_EXPR, and there's currently no way to attach the 763169689Skan varargs alias set to an INDIRECT_REF (FIXME!), so we can't 764169689Skan consistently use the varargs alias set for loads from the varargs 765169689Skan area. So don't use it anywhere. */ 766169689Skan return 0; 767169689Skan#else 768132718Skan if (varargs_set == -1) 769132718Skan varargs_set = new_alias_set (); 77090075Sobrien 771132718Skan return varargs_set; 772169689Skan#endif 77390075Sobrien} 77490075Sobrien 77590075Sobrien/* Likewise, but used for the fixed portions of the frame, e.g., register 77690075Sobrien save areas. */ 77790075Sobrien 778132718Skanstatic GTY(()) HOST_WIDE_INT frame_set = -1; 779132718Skan 78090075SobrienHOST_WIDE_INT 781132718Skanget_frame_alias_set (void) 78290075Sobrien{ 783132718Skan if (frame_set == -1) 784132718Skan frame_set = new_alias_set (); 78590075Sobrien 786132718Skan return frame_set; 78790075Sobrien} 78890075Sobrien 78950397Sobrien/* Inside SRC, the source of a SET, find a base address. */ 79050397Sobrien 79150397Sobrienstatic rtx 792132718Skanfind_base_value (rtx src) 79350397Sobrien{ 79490075Sobrien unsigned int regno; 79596263Sobrien 79650397Sobrien switch (GET_CODE (src)) 79750397Sobrien { 79850397Sobrien case SYMBOL_REF: 79950397Sobrien case LABEL_REF: 80050397Sobrien return src; 80150397Sobrien 80250397Sobrien case REG: 80390075Sobrien regno = REGNO (src); 80490075Sobrien /* At the start of a function, argument registers have known base 80550397Sobrien values which may be lost later. Returning an ADDRESS 80650397Sobrien expression here allows optimization based on argument values 80750397Sobrien even when the argument registers are used for other purposes. */ 80890075Sobrien if (regno < FIRST_PSEUDO_REGISTER && copying_arguments) 80990075Sobrien return new_reg_base_value[regno]; 81050397Sobrien 81150397Sobrien /* If a pseudo has a known base value, return it. Do not do this 81296263Sobrien for non-fixed hard regs since it can result in a circular 81396263Sobrien dependency chain for registers which have values at function entry. 81450397Sobrien 81550397Sobrien The test above is not sufficient because the scheduler may move 81650397Sobrien a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */ 81796263Sobrien if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno]) 818169689Skan && regno < VEC_length (rtx, reg_base_value)) 819117395Skan { 820117395Skan /* If we're inside init_alias_analysis, use new_reg_base_value 821117395Skan to reduce the number of relaxation iterations. */ 822117395Skan if (new_reg_base_value && new_reg_base_value[regno] 823117395Skan && REG_N_SETS (regno) == 1) 824117395Skan return new_reg_base_value[regno]; 82550397Sobrien 826169689Skan if (VEC_index (rtx, reg_base_value, regno)) 827169689Skan return VEC_index (rtx, reg_base_value, regno); 828117395Skan } 829117395Skan 830122180Skan return 0; 83150397Sobrien 83250397Sobrien case MEM: 83350397Sobrien /* Check for an argument passed in memory. Only record in the 83450397Sobrien copying-arguments block; it is too hard to track changes 83550397Sobrien otherwise. */ 83650397Sobrien if (copying_arguments 83750397Sobrien && (XEXP (src, 0) == arg_pointer_rtx 83850397Sobrien || (GET_CODE (XEXP (src, 0)) == PLUS 83950397Sobrien && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx))) 84050397Sobrien return gen_rtx_ADDRESS (VOIDmode, src); 84150397Sobrien return 0; 84250397Sobrien 84350397Sobrien case CONST: 84450397Sobrien src = XEXP (src, 0); 84550397Sobrien if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS) 84650397Sobrien break; 84750397Sobrien 84890075Sobrien /* ... fall through ... */ 84990075Sobrien 85050397Sobrien case PLUS: 85150397Sobrien case MINUS: 85250397Sobrien { 85350397Sobrien rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1); 85450397Sobrien 85590075Sobrien /* If either operand is a REG that is a known pointer, then it 85690075Sobrien is the base. */ 85790075Sobrien if (REG_P (src_0) && REG_POINTER (src_0)) 85890075Sobrien return find_base_value (src_0); 85990075Sobrien if (REG_P (src_1) && REG_POINTER (src_1)) 86090075Sobrien return find_base_value (src_1); 86190075Sobrien 86250397Sobrien /* If either operand is a REG, then see if we already have 86350397Sobrien a known value for it. */ 86490075Sobrien if (REG_P (src_0)) 86550397Sobrien { 86650397Sobrien temp = find_base_value (src_0); 86790075Sobrien if (temp != 0) 86850397Sobrien src_0 = temp; 86950397Sobrien } 87050397Sobrien 87190075Sobrien if (REG_P (src_1)) 87250397Sobrien { 87350397Sobrien temp = find_base_value (src_1); 87490075Sobrien if (temp!= 0) 87550397Sobrien src_1 = temp; 87650397Sobrien } 87750397Sobrien 87890075Sobrien /* If either base is named object or a special address 87990075Sobrien (like an argument or stack reference), then use it for the 88090075Sobrien base term. */ 88190075Sobrien if (src_0 != 0 88290075Sobrien && (GET_CODE (src_0) == SYMBOL_REF 88390075Sobrien || GET_CODE (src_0) == LABEL_REF 88490075Sobrien || (GET_CODE (src_0) == ADDRESS 88590075Sobrien && GET_MODE (src_0) != VOIDmode))) 88690075Sobrien return src_0; 88750397Sobrien 88890075Sobrien if (src_1 != 0 88990075Sobrien && (GET_CODE (src_1) == SYMBOL_REF 89090075Sobrien || GET_CODE (src_1) == LABEL_REF 89190075Sobrien || (GET_CODE (src_1) == ADDRESS 89290075Sobrien && GET_MODE (src_1) != VOIDmode))) 89390075Sobrien return src_1; 89490075Sobrien 89590075Sobrien /* Guess which operand is the base address: 89650397Sobrien If either operand is a symbol, then it is the base. If 89750397Sobrien either operand is a CONST_INT, then the other is the base. */ 89890075Sobrien if (GET_CODE (src_1) == CONST_INT || CONSTANT_P (src_0)) 89950397Sobrien return find_base_value (src_0); 90090075Sobrien else if (GET_CODE (src_0) == CONST_INT || CONSTANT_P (src_1)) 90150397Sobrien return find_base_value (src_1); 90250397Sobrien 90350397Sobrien return 0; 90450397Sobrien } 90550397Sobrien 90650397Sobrien case LO_SUM: 90750397Sobrien /* The standard form is (lo_sum reg sym) so look only at the 90850397Sobrien second operand. */ 90950397Sobrien return find_base_value (XEXP (src, 1)); 91050397Sobrien 91150397Sobrien case AND: 91250397Sobrien /* If the second operand is constant set the base 91390075Sobrien address to the first operand. */ 91450397Sobrien if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0) 91550397Sobrien return find_base_value (XEXP (src, 0)); 91650397Sobrien return 0; 91750397Sobrien 91890075Sobrien case TRUNCATE: 91990075Sobrien if (GET_MODE_SIZE (GET_MODE (src)) < GET_MODE_SIZE (Pmode)) 92090075Sobrien break; 92190075Sobrien /* Fall through. */ 92250397Sobrien case HIGH: 92390075Sobrien case PRE_INC: 92490075Sobrien case PRE_DEC: 92590075Sobrien case POST_INC: 92690075Sobrien case POST_DEC: 92790075Sobrien case PRE_MODIFY: 92890075Sobrien case POST_MODIFY: 92950397Sobrien return find_base_value (XEXP (src, 0)); 93050397Sobrien 93196263Sobrien case ZERO_EXTEND: 93296263Sobrien case SIGN_EXTEND: /* used for NT/Alpha pointers */ 93396263Sobrien { 93496263Sobrien rtx temp = find_base_value (XEXP (src, 0)); 93596263Sobrien 936132718Skan if (temp != 0 && CONSTANT_P (temp)) 93796263Sobrien temp = convert_memory_address (Pmode, temp); 93896263Sobrien 93996263Sobrien return temp; 94096263Sobrien } 94196263Sobrien 94250397Sobrien default: 94350397Sobrien break; 94450397Sobrien } 94550397Sobrien 94650397Sobrien return 0; 94750397Sobrien} 94850397Sobrien 94950397Sobrien/* Called from init_alias_analysis indirectly through note_stores. */ 95050397Sobrien 95190075Sobrien/* While scanning insns to find base values, reg_seen[N] is nonzero if 95250397Sobrien register N has been set in this function. */ 95350397Sobrienstatic char *reg_seen; 95450397Sobrien 95550397Sobrien/* Addresses which are known not to alias anything else are identified 95650397Sobrien by a unique integer. */ 95750397Sobrienstatic int unique_id; 95850397Sobrien 95950397Sobrienstatic void 960132718Skanrecord_set (rtx dest, rtx set, void *data ATTRIBUTE_UNUSED) 96150397Sobrien{ 96290075Sobrien unsigned regno; 96350397Sobrien rtx src; 964132718Skan int n; 96550397Sobrien 966169689Skan if (!REG_P (dest)) 96750397Sobrien return; 96850397Sobrien 96950397Sobrien regno = REGNO (dest); 97050397Sobrien 971169689Skan gcc_assert (regno < VEC_length (rtx, reg_base_value)); 97290075Sobrien 973132718Skan /* If this spans multiple hard registers, then we must indicate that every 974132718Skan register has an unusable value. */ 975132718Skan if (regno < FIRST_PSEUDO_REGISTER) 976169689Skan n = hard_regno_nregs[regno][GET_MODE (dest)]; 977132718Skan else 978132718Skan n = 1; 979132718Skan if (n != 1) 980132718Skan { 981132718Skan while (--n >= 0) 982132718Skan { 983132718Skan reg_seen[regno + n] = 1; 984132718Skan new_reg_base_value[regno + n] = 0; 985132718Skan } 986132718Skan return; 987132718Skan } 988132718Skan 98950397Sobrien if (set) 99050397Sobrien { 99150397Sobrien /* A CLOBBER wipes out any old value but does not prevent a previously 99250397Sobrien unset register from acquiring a base address (i.e. reg_seen is not 99350397Sobrien set). */ 99450397Sobrien if (GET_CODE (set) == CLOBBER) 99550397Sobrien { 99650397Sobrien new_reg_base_value[regno] = 0; 99750397Sobrien return; 99850397Sobrien } 99950397Sobrien src = SET_SRC (set); 100050397Sobrien } 100150397Sobrien else 100250397Sobrien { 100350397Sobrien if (reg_seen[regno]) 100450397Sobrien { 100550397Sobrien new_reg_base_value[regno] = 0; 100650397Sobrien return; 100750397Sobrien } 100850397Sobrien reg_seen[regno] = 1; 100950397Sobrien new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode, 101050397Sobrien GEN_INT (unique_id++)); 101150397Sobrien return; 101250397Sobrien } 101350397Sobrien 1014169689Skan /* If this is not the first set of REGNO, see whether the new value 1015169689Skan is related to the old one. There are two cases of interest: 1016169689Skan 1017169689Skan (1) The register might be assigned an entirely new value 1018169689Skan that has the same base term as the original set. 1019169689Skan 1020169689Skan (2) The set might be a simple self-modification that 1021169689Skan cannot change REGNO's base value. 1022169689Skan 1023169689Skan If neither case holds, reject the original base value as invalid. 1024169689Skan Note that the following situation is not detected: 1025169689Skan 1026169689Skan extern int x, y; int *p = &x; p += (&y-&x); 1027169689Skan 102850397Sobrien ANSI C does not allow computing the difference of addresses 102950397Sobrien of distinct top level objects. */ 1030169689Skan if (new_reg_base_value[regno] != 0 1031169689Skan && find_base_value (src) != new_reg_base_value[regno]) 103250397Sobrien switch (GET_CODE (src)) 103350397Sobrien { 103450397Sobrien case LO_SUM: 103550397Sobrien case MINUS: 103650397Sobrien if (XEXP (src, 0) != dest && XEXP (src, 1) != dest) 103750397Sobrien new_reg_base_value[regno] = 0; 103850397Sobrien break; 103990075Sobrien case PLUS: 104090075Sobrien /* If the value we add in the PLUS is also a valid base value, 104190075Sobrien this might be the actual base value, and the original value 104290075Sobrien an index. */ 104390075Sobrien { 104490075Sobrien rtx other = NULL_RTX; 104590075Sobrien 104690075Sobrien if (XEXP (src, 0) == dest) 104790075Sobrien other = XEXP (src, 1); 104890075Sobrien else if (XEXP (src, 1) == dest) 104990075Sobrien other = XEXP (src, 0); 105090075Sobrien 105190075Sobrien if (! other || find_base_value (other)) 105290075Sobrien new_reg_base_value[regno] = 0; 105390075Sobrien break; 105490075Sobrien } 105550397Sobrien case AND: 105650397Sobrien if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT) 105750397Sobrien new_reg_base_value[regno] = 0; 105850397Sobrien break; 105950397Sobrien default: 106050397Sobrien new_reg_base_value[regno] = 0; 106150397Sobrien break; 106250397Sobrien } 106350397Sobrien /* If this is the first set of a register, record the value. */ 106450397Sobrien else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno]) 106550397Sobrien && ! reg_seen[regno] && new_reg_base_value[regno] == 0) 106650397Sobrien new_reg_base_value[regno] = find_base_value (src); 106750397Sobrien 106850397Sobrien reg_seen[regno] = 1; 106950397Sobrien} 107050397Sobrien 107190075Sobrien/* Clear alias info for a register. This is used if an RTL transformation 107290075Sobrien changes the value of a register. This is used in flow by AUTO_INC_DEC 107390075Sobrien optimizations. We don't need to clear reg_base_value, since flow only 107490075Sobrien changes the offset. */ 107590075Sobrien 107690075Sobrienvoid 1077132718Skanclear_reg_alias_info (rtx reg) 107890075Sobrien{ 107990075Sobrien unsigned int regno = REGNO (reg); 108090075Sobrien 1081132718Skan if (regno >= FIRST_PSEUDO_REGISTER) 1082132718Skan { 1083132718Skan regno -= FIRST_PSEUDO_REGISTER; 1084132718Skan if (regno < reg_known_value_size) 1085132718Skan { 1086132718Skan reg_known_value[regno] = reg; 1087132718Skan reg_known_equiv_p[regno] = false; 1088132718Skan } 1089132718Skan } 109090075Sobrien} 109190075Sobrien 1092132718Skan/* If a value is known for REGNO, return it. */ 1093132718Skan 1094169689Skanrtx 1095132718Skanget_reg_known_value (unsigned int regno) 1096132718Skan{ 1097132718Skan if (regno >= FIRST_PSEUDO_REGISTER) 1098132718Skan { 1099132718Skan regno -= FIRST_PSEUDO_REGISTER; 1100132718Skan if (regno < reg_known_value_size) 1101132718Skan return reg_known_value[regno]; 1102132718Skan } 1103132718Skan return NULL; 1104132718Skan} 1105132718Skan 1106132718Skan/* Set it. */ 1107132718Skan 1108132718Skanstatic void 1109132718Skanset_reg_known_value (unsigned int regno, rtx val) 1110132718Skan{ 1111132718Skan if (regno >= FIRST_PSEUDO_REGISTER) 1112132718Skan { 1113132718Skan regno -= FIRST_PSEUDO_REGISTER; 1114132718Skan if (regno < reg_known_value_size) 1115132718Skan reg_known_value[regno] = val; 1116132718Skan } 1117132718Skan} 1118132718Skan 1119132718Skan/* Similarly for reg_known_equiv_p. */ 1120132718Skan 1121132718Skanbool 1122132718Skanget_reg_known_equiv_p (unsigned int regno) 1123132718Skan{ 1124132718Skan if (regno >= FIRST_PSEUDO_REGISTER) 1125132718Skan { 1126132718Skan regno -= FIRST_PSEUDO_REGISTER; 1127132718Skan if (regno < reg_known_value_size) 1128132718Skan return reg_known_equiv_p[regno]; 1129132718Skan } 1130132718Skan return false; 1131132718Skan} 1132132718Skan 1133132718Skanstatic void 1134132718Skanset_reg_known_equiv_p (unsigned int regno, bool val) 1135132718Skan{ 1136132718Skan if (regno >= FIRST_PSEUDO_REGISTER) 1137132718Skan { 1138132718Skan regno -= FIRST_PSEUDO_REGISTER; 1139132718Skan if (regno < reg_known_value_size) 1140132718Skan reg_known_equiv_p[regno] = val; 1141132718Skan } 1142132718Skan} 1143132718Skan 1144132718Skan 114590075Sobrien/* Returns a canonical version of X, from the point of view alias 114690075Sobrien analysis. (For example, if X is a MEM whose address is a register, 114790075Sobrien and the register has a known value (say a SYMBOL_REF), then a MEM 114890075Sobrien whose address is the SYMBOL_REF is returned.) */ 114990075Sobrien 115090075Sobrienrtx 1151132718Skancanon_rtx (rtx x) 115250397Sobrien{ 115350397Sobrien /* Recursively look for equivalences. */ 1154169689Skan if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER) 115550397Sobrien { 1156132718Skan rtx t = get_reg_known_value (REGNO (x)); 1157132718Skan if (t == x) 1158132718Skan return x; 1159132718Skan if (t) 1160132718Skan return canon_rtx (t); 1161132718Skan } 1162132718Skan 1163132718Skan if (GET_CODE (x) == PLUS) 1164132718Skan { 116550397Sobrien rtx x0 = canon_rtx (XEXP (x, 0)); 116650397Sobrien rtx x1 = canon_rtx (XEXP (x, 1)); 116750397Sobrien 116850397Sobrien if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1)) 116950397Sobrien { 117050397Sobrien if (GET_CODE (x0) == CONST_INT) 117190075Sobrien return plus_constant (x1, INTVAL (x0)); 117250397Sobrien else if (GET_CODE (x1) == CONST_INT) 117390075Sobrien return plus_constant (x0, INTVAL (x1)); 117450397Sobrien return gen_rtx_PLUS (GET_MODE (x), x0, x1); 117550397Sobrien } 117650397Sobrien } 117790075Sobrien 117850397Sobrien /* This gives us much better alias analysis when called from 117950397Sobrien the loop optimizer. Note we want to leave the original 118050397Sobrien MEM alone, but need to return the canonicalized MEM with 118150397Sobrien all the flags with their original values. */ 1182169689Skan else if (MEM_P (x)) 118390075Sobrien x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0))); 118490075Sobrien 118550397Sobrien return x; 118650397Sobrien} 118750397Sobrien 118850397Sobrien/* Return 1 if X and Y are identical-looking rtx's. 1189132718Skan Expect that X and Y has been already canonicalized. 119050397Sobrien 119150397Sobrien We use the data in reg_known_value above to see if two registers with 119250397Sobrien different numbers are, in fact, equivalent. */ 119350397Sobrien 119450397Sobrienstatic int 1195132718Skanrtx_equal_for_memref_p (rtx x, rtx y) 119650397Sobrien{ 119790075Sobrien int i; 119890075Sobrien int j; 119990075Sobrien enum rtx_code code; 120090075Sobrien const char *fmt; 120150397Sobrien 120250397Sobrien if (x == 0 && y == 0) 120350397Sobrien return 1; 120450397Sobrien if (x == 0 || y == 0) 120550397Sobrien return 0; 120690075Sobrien 120750397Sobrien if (x == y) 120850397Sobrien return 1; 120950397Sobrien 121050397Sobrien code = GET_CODE (x); 121150397Sobrien /* Rtx's of different codes cannot be equal. */ 121250397Sobrien if (code != GET_CODE (y)) 121350397Sobrien return 0; 121450397Sobrien 121550397Sobrien /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. 121650397Sobrien (REG:SI x) and (REG:HI x) are NOT equivalent. */ 121750397Sobrien 121850397Sobrien if (GET_MODE (x) != GET_MODE (y)) 121950397Sobrien return 0; 122050397Sobrien 122190075Sobrien /* Some RTL can be compared without a recursive examination. */ 122290075Sobrien switch (code) 122390075Sobrien { 122490075Sobrien case REG: 122590075Sobrien return REGNO (x) == REGNO (y); 122650397Sobrien 122790075Sobrien case LABEL_REF: 122890075Sobrien return XEXP (x, 0) == XEXP (y, 0); 1229117395Skan 123090075Sobrien case SYMBOL_REF: 123190075Sobrien return XSTR (x, 0) == XSTR (y, 0); 123290075Sobrien 1233132718Skan case VALUE: 123490075Sobrien case CONST_INT: 123590075Sobrien case CONST_DOUBLE: 123690075Sobrien /* There's no need to compare the contents of CONST_DOUBLEs or 123790075Sobrien CONST_INTs because pointer equality is a good enough 123890075Sobrien comparison for these nodes. */ 123990075Sobrien return 0; 124090075Sobrien 124190075Sobrien default: 124290075Sobrien break; 124390075Sobrien } 124490075Sobrien 1245132718Skan /* canon_rtx knows how to handle plus. No need to canonicalize. */ 1246132718Skan if (code == PLUS) 124750397Sobrien return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)) 124850397Sobrien && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1))) 124950397Sobrien || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1)) 125050397Sobrien && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0)))); 1251132718Skan /* For commutative operations, the RTX match if the operand match in any 1252132718Skan order. Also handle the simple binary and unary cases without a loop. */ 1253169689Skan if (COMMUTATIVE_P (x)) 1254132718Skan { 1255132718Skan rtx xop0 = canon_rtx (XEXP (x, 0)); 1256132718Skan rtx yop0 = canon_rtx (XEXP (y, 0)); 1257132718Skan rtx yop1 = canon_rtx (XEXP (y, 1)); 1258132718Skan 1259132718Skan return ((rtx_equal_for_memref_p (xop0, yop0) 1260132718Skan && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1)) 1261132718Skan || (rtx_equal_for_memref_p (xop0, yop1) 1262132718Skan && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0))); 1263132718Skan } 1264169689Skan else if (NON_COMMUTATIVE_P (x)) 1265132718Skan { 1266132718Skan return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)), 1267132718Skan canon_rtx (XEXP (y, 0))) 1268132718Skan && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), 1269132718Skan canon_rtx (XEXP (y, 1)))); 1270132718Skan } 1271169689Skan else if (UNARY_P (x)) 1272132718Skan return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)), 1273132718Skan canon_rtx (XEXP (y, 0))); 127450397Sobrien 127550397Sobrien /* Compare the elements. If any pair of corresponding elements 127650397Sobrien fail to match, return 0 for the whole things. 127750397Sobrien 127850397Sobrien Limit cases to types which actually appear in addresses. */ 127950397Sobrien 128050397Sobrien fmt = GET_RTX_FORMAT (code); 128150397Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 128250397Sobrien { 128350397Sobrien switch (fmt[i]) 128450397Sobrien { 128550397Sobrien case 'i': 128650397Sobrien if (XINT (x, i) != XINT (y, i)) 128750397Sobrien return 0; 128850397Sobrien break; 128950397Sobrien 129050397Sobrien case 'E': 129150397Sobrien /* Two vectors must have the same length. */ 129250397Sobrien if (XVECLEN (x, i) != XVECLEN (y, i)) 129350397Sobrien return 0; 129450397Sobrien 129550397Sobrien /* And the corresponding elements must match. */ 129650397Sobrien for (j = 0; j < XVECLEN (x, i); j++) 1297132718Skan if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)), 1298132718Skan canon_rtx (XVECEXP (y, i, j))) == 0) 129950397Sobrien return 0; 130050397Sobrien break; 130150397Sobrien 130250397Sobrien case 'e': 1303132718Skan if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)), 1304132718Skan canon_rtx (XEXP (y, i))) == 0) 130550397Sobrien return 0; 130650397Sobrien break; 130750397Sobrien 130890075Sobrien /* This can happen for asm operands. */ 130990075Sobrien case 's': 131090075Sobrien if (strcmp (XSTR (x, i), XSTR (y, i))) 131190075Sobrien return 0; 131290075Sobrien break; 131390075Sobrien 131450397Sobrien /* This can happen for an asm which clobbers memory. */ 131550397Sobrien case '0': 131650397Sobrien break; 131750397Sobrien 131850397Sobrien /* It is believed that rtx's at this level will never 131950397Sobrien contain anything but integers and other rtx's, 132050397Sobrien except for within LABEL_REFs and SYMBOL_REFs. */ 132150397Sobrien default: 1322169689Skan gcc_unreachable (); 132350397Sobrien } 132450397Sobrien } 132550397Sobrien return 1; 132650397Sobrien} 132750397Sobrien 132850397Sobrien/* Given an rtx X, find a SYMBOL_REF or LABEL_REF within 132950397Sobrien X and return it, or return 0 if none found. */ 133050397Sobrien 133150397Sobrienstatic rtx 1332132718Skanfind_symbolic_term (rtx x) 133350397Sobrien{ 133490075Sobrien int i; 133590075Sobrien enum rtx_code code; 133690075Sobrien const char *fmt; 133750397Sobrien 133850397Sobrien code = GET_CODE (x); 133950397Sobrien if (code == SYMBOL_REF || code == LABEL_REF) 134050397Sobrien return x; 1341169689Skan if (OBJECT_P (x)) 134250397Sobrien return 0; 134350397Sobrien 134450397Sobrien fmt = GET_RTX_FORMAT (code); 134550397Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 134650397Sobrien { 134750397Sobrien rtx t; 134850397Sobrien 134950397Sobrien if (fmt[i] == 'e') 135050397Sobrien { 135150397Sobrien t = find_symbolic_term (XEXP (x, i)); 135250397Sobrien if (t != 0) 135350397Sobrien return t; 135450397Sobrien } 135550397Sobrien else if (fmt[i] == 'E') 135650397Sobrien break; 135750397Sobrien } 135850397Sobrien return 0; 135950397Sobrien} 136050397Sobrien 1361132718Skanrtx 1362132718Skanfind_base_term (rtx x) 136350397Sobrien{ 136490075Sobrien cselib_val *val; 136590075Sobrien struct elt_loc_list *l; 136690075Sobrien 136790075Sobrien#if defined (FIND_BASE_TERM) 136890075Sobrien /* Try machine-dependent ways to find the base term. */ 136990075Sobrien x = FIND_BASE_TERM (x); 137090075Sobrien#endif 137190075Sobrien 137250397Sobrien switch (GET_CODE (x)) 137350397Sobrien { 137450397Sobrien case REG: 137550397Sobrien return REG_BASE_VALUE (x); 137650397Sobrien 137790075Sobrien case TRUNCATE: 137890075Sobrien if (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (Pmode)) 1379117395Skan return 0; 138090075Sobrien /* Fall through. */ 138150397Sobrien case HIGH: 138250397Sobrien case PRE_INC: 138350397Sobrien case PRE_DEC: 138450397Sobrien case POST_INC: 138550397Sobrien case POST_DEC: 138690075Sobrien case PRE_MODIFY: 138790075Sobrien case POST_MODIFY: 138850397Sobrien return find_base_term (XEXP (x, 0)); 138950397Sobrien 139096263Sobrien case ZERO_EXTEND: 139196263Sobrien case SIGN_EXTEND: /* Used for Alpha/NT pointers */ 139296263Sobrien { 139396263Sobrien rtx temp = find_base_term (XEXP (x, 0)); 139496263Sobrien 1395132718Skan if (temp != 0 && CONSTANT_P (temp)) 139696263Sobrien temp = convert_memory_address (Pmode, temp); 139796263Sobrien 139896263Sobrien return temp; 139996263Sobrien } 140096263Sobrien 140190075Sobrien case VALUE: 140290075Sobrien val = CSELIB_VAL_PTR (x); 1403132718Skan if (!val) 1404132718Skan return 0; 140590075Sobrien for (l = val->locs; l; l = l->next) 140690075Sobrien if ((x = find_base_term (l->loc)) != 0) 140790075Sobrien return x; 140890075Sobrien return 0; 140990075Sobrien 141050397Sobrien case CONST: 141150397Sobrien x = XEXP (x, 0); 141250397Sobrien if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS) 141350397Sobrien return 0; 1414132718Skan /* Fall through. */ 141550397Sobrien case LO_SUM: 141650397Sobrien case PLUS: 141750397Sobrien case MINUS: 141850397Sobrien { 141952284Sobrien rtx tmp1 = XEXP (x, 0); 142052284Sobrien rtx tmp2 = XEXP (x, 1); 142152284Sobrien 142290075Sobrien /* This is a little bit tricky since we have to determine which of 142352284Sobrien the two operands represents the real base address. Otherwise this 142452284Sobrien routine may return the index register instead of the base register. 142552284Sobrien 142652284Sobrien That may cause us to believe no aliasing was possible, when in 142752284Sobrien fact aliasing is possible. 142852284Sobrien 142952284Sobrien We use a few simple tests to guess the base register. Additional 143052284Sobrien tests can certainly be added. For example, if one of the operands 143152284Sobrien is a shift or multiply, then it must be the index register and the 143252284Sobrien other operand is the base register. */ 1433117395Skan 143490075Sobrien if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2)) 143590075Sobrien return find_base_term (tmp2); 143690075Sobrien 143752284Sobrien /* If either operand is known to be a pointer, then use it 143852284Sobrien to determine the base term. */ 143990075Sobrien if (REG_P (tmp1) && REG_POINTER (tmp1)) 144052284Sobrien return find_base_term (tmp1); 144152284Sobrien 144290075Sobrien if (REG_P (tmp2) && REG_POINTER (tmp2)) 144352284Sobrien return find_base_term (tmp2); 144452284Sobrien 144552284Sobrien /* Neither operand was known to be a pointer. Go ahead and find the 144652284Sobrien base term for both operands. */ 144752284Sobrien tmp1 = find_base_term (tmp1); 144852284Sobrien tmp2 = find_base_term (tmp2); 144952284Sobrien 145052284Sobrien /* If either base term is named object or a special address 145152284Sobrien (like an argument or stack reference), then use it for the 145252284Sobrien base term. */ 145390075Sobrien if (tmp1 != 0 145452284Sobrien && (GET_CODE (tmp1) == SYMBOL_REF 145552284Sobrien || GET_CODE (tmp1) == LABEL_REF 145652284Sobrien || (GET_CODE (tmp1) == ADDRESS 145752284Sobrien && GET_MODE (tmp1) != VOIDmode))) 145852284Sobrien return tmp1; 145952284Sobrien 146090075Sobrien if (tmp2 != 0 146152284Sobrien && (GET_CODE (tmp2) == SYMBOL_REF 146252284Sobrien || GET_CODE (tmp2) == LABEL_REF 146352284Sobrien || (GET_CODE (tmp2) == ADDRESS 146452284Sobrien && GET_MODE (tmp2) != VOIDmode))) 146552284Sobrien return tmp2; 146652284Sobrien 146752284Sobrien /* We could not determine which of the two operands was the 146852284Sobrien base register and which was the index. So we can determine 146952284Sobrien nothing from the base alias check. */ 147052284Sobrien return 0; 147150397Sobrien } 147250397Sobrien 147350397Sobrien case AND: 147490075Sobrien if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) != 0) 147590075Sobrien return find_base_term (XEXP (x, 0)); 147650397Sobrien return 0; 147750397Sobrien 147850397Sobrien case SYMBOL_REF: 147950397Sobrien case LABEL_REF: 148050397Sobrien return x; 148150397Sobrien 148250397Sobrien default: 148350397Sobrien return 0; 148450397Sobrien } 148550397Sobrien} 148650397Sobrien 148750397Sobrien/* Return 0 if the addresses X and Y are known to point to different 148850397Sobrien objects, 1 if they might be pointers to the same object. */ 148950397Sobrien 149050397Sobrienstatic int 1491132718Skanbase_alias_check (rtx x, rtx y, enum machine_mode x_mode, 1492132718Skan enum machine_mode y_mode) 149350397Sobrien{ 149450397Sobrien rtx x_base = find_base_term (x); 149550397Sobrien rtx y_base = find_base_term (y); 149650397Sobrien 149750397Sobrien /* If the address itself has no known base see if a known equivalent 149850397Sobrien value has one. If either address still has no known base, nothing 149950397Sobrien is known about aliasing. */ 150050397Sobrien if (x_base == 0) 150150397Sobrien { 150250397Sobrien rtx x_c; 150390075Sobrien 150450397Sobrien if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x) 150550397Sobrien return 1; 150690075Sobrien 150750397Sobrien x_base = find_base_term (x_c); 150850397Sobrien if (x_base == 0) 150950397Sobrien return 1; 151050397Sobrien } 151150397Sobrien 151250397Sobrien if (y_base == 0) 151350397Sobrien { 151450397Sobrien rtx y_c; 151550397Sobrien if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y) 151650397Sobrien return 1; 151790075Sobrien 151850397Sobrien y_base = find_base_term (y_c); 151950397Sobrien if (y_base == 0) 152050397Sobrien return 1; 152150397Sobrien } 152250397Sobrien 152350397Sobrien /* If the base addresses are equal nothing is known about aliasing. */ 152450397Sobrien if (rtx_equal_p (x_base, y_base)) 152550397Sobrien return 1; 152650397Sobrien 1527117395Skan /* The base addresses of the read and write are different expressions. 152852284Sobrien If they are both symbols and they are not accessed via AND, there is 152952284Sobrien no conflict. We can bring knowledge of object alignment into play 153052284Sobrien here. For example, on alpha, "char a, b;" can alias one another, 153152284Sobrien though "char a; long b;" cannot. */ 153250397Sobrien if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS) 153350397Sobrien { 153452284Sobrien if (GET_CODE (x) == AND && GET_CODE (y) == AND) 153552284Sobrien return 1; 153652284Sobrien if (GET_CODE (x) == AND 153752284Sobrien && (GET_CODE (XEXP (x, 1)) != CONST_INT 153890075Sobrien || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1)))) 153952284Sobrien return 1; 154052284Sobrien if (GET_CODE (y) == AND 154152284Sobrien && (GET_CODE (XEXP (y, 1)) != CONST_INT 154290075Sobrien || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1)))) 154352284Sobrien return 1; 154452284Sobrien /* Differing symbols never alias. */ 154552284Sobrien return 0; 154650397Sobrien } 154750397Sobrien 154850397Sobrien /* If one address is a stack reference there can be no alias: 154950397Sobrien stack references using different base registers do not alias, 155050397Sobrien a stack reference can not alias a parameter, and a stack reference 155150397Sobrien can not alias a global. */ 155250397Sobrien if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode) 155350397Sobrien || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode)) 155450397Sobrien return 0; 155550397Sobrien 155650397Sobrien if (! flag_argument_noalias) 155750397Sobrien return 1; 155850397Sobrien 155950397Sobrien if (flag_argument_noalias > 1) 156050397Sobrien return 0; 156150397Sobrien 156290075Sobrien /* Weak noalias assertion (arguments are distinct, but may match globals). */ 156350397Sobrien return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode); 156450397Sobrien} 156550397Sobrien 156690075Sobrien/* Convert the address X into something we can use. This is done by returning 156790075Sobrien it unchanged unless it is a value; in the latter case we call cselib to get 156890075Sobrien a more useful rtx. */ 156990075Sobrien 157090075Sobrienrtx 1571132718Skanget_addr (rtx x) 157290075Sobrien{ 157390075Sobrien cselib_val *v; 157490075Sobrien struct elt_loc_list *l; 157590075Sobrien 157690075Sobrien if (GET_CODE (x) != VALUE) 157790075Sobrien return x; 157890075Sobrien v = CSELIB_VAL_PTR (x); 1579132718Skan if (v) 1580132718Skan { 1581132718Skan for (l = v->locs; l; l = l->next) 1582132718Skan if (CONSTANT_P (l->loc)) 1583132718Skan return l->loc; 1584132718Skan for (l = v->locs; l; l = l->next) 1585169689Skan if (!REG_P (l->loc) && !MEM_P (l->loc)) 1586132718Skan return l->loc; 1587132718Skan if (v->locs) 1588132718Skan return v->locs->loc; 1589132718Skan } 159090075Sobrien return x; 159190075Sobrien} 159290075Sobrien 159352284Sobrien/* Return the address of the (N_REFS + 1)th memory reference to ADDR 159452284Sobrien where SIZE is the size in bytes of the memory reference. If ADDR 159552284Sobrien is not modified by the memory reference then ADDR is returned. */ 159652284Sobrien 1597169689Skanstatic rtx 1598132718Skanaddr_side_effect_eval (rtx addr, int size, int n_refs) 159952284Sobrien{ 160052284Sobrien int offset = 0; 1601117395Skan 160252284Sobrien switch (GET_CODE (addr)) 160352284Sobrien { 160452284Sobrien case PRE_INC: 160552284Sobrien offset = (n_refs + 1) * size; 160652284Sobrien break; 160752284Sobrien case PRE_DEC: 160852284Sobrien offset = -(n_refs + 1) * size; 160952284Sobrien break; 161052284Sobrien case POST_INC: 161152284Sobrien offset = n_refs * size; 161252284Sobrien break; 161352284Sobrien case POST_DEC: 161452284Sobrien offset = -n_refs * size; 161552284Sobrien break; 161652284Sobrien 161752284Sobrien default: 161852284Sobrien return addr; 161952284Sobrien } 1620117395Skan 162152284Sobrien if (offset) 1622132718Skan addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0), 1623169689Skan GEN_INT (offset)); 162452284Sobrien else 162552284Sobrien addr = XEXP (addr, 0); 1626132718Skan addr = canon_rtx (addr); 162752284Sobrien 162852284Sobrien return addr; 162952284Sobrien} 163052284Sobrien 163150397Sobrien/* Return nonzero if X and Y (memory addresses) could reference the 163250397Sobrien same location in memory. C is an offset accumulator. When 163350397Sobrien C is nonzero, we are testing aliases between X and Y + C. 163450397Sobrien XSIZE is the size in bytes of the X reference, 163550397Sobrien similarly YSIZE is the size in bytes for Y. 1636132718Skan Expect that canon_rtx has been already called for X and Y. 163750397Sobrien 163850397Sobrien If XSIZE or YSIZE is zero, we do not know the amount of memory being 163950397Sobrien referenced (the reference was BLKmode), so make the most pessimistic 164050397Sobrien assumptions. 164150397Sobrien 164250397Sobrien If XSIZE or YSIZE is negative, we may access memory outside the object 164350397Sobrien being referenced as a side effect. This can happen when using AND to 164450397Sobrien align memory references, as is done on the Alpha. 164550397Sobrien 164650397Sobrien Nice to notice that varying addresses cannot conflict with fp if no 164750397Sobrien local variables had their addresses taken, but that's too hard now. */ 164850397Sobrien 164950397Sobrienstatic int 1650132718Skanmemrefs_conflict_p (int xsize, rtx x, int ysize, rtx y, HOST_WIDE_INT c) 165150397Sobrien{ 165290075Sobrien if (GET_CODE (x) == VALUE) 165390075Sobrien x = get_addr (x); 165490075Sobrien if (GET_CODE (y) == VALUE) 165590075Sobrien y = get_addr (y); 165650397Sobrien if (GET_CODE (x) == HIGH) 165750397Sobrien x = XEXP (x, 0); 165850397Sobrien else if (GET_CODE (x) == LO_SUM) 165950397Sobrien x = XEXP (x, 1); 166050397Sobrien else 1661132718Skan x = addr_side_effect_eval (x, xsize, 0); 166250397Sobrien if (GET_CODE (y) == HIGH) 166350397Sobrien y = XEXP (y, 0); 166450397Sobrien else if (GET_CODE (y) == LO_SUM) 166550397Sobrien y = XEXP (y, 1); 166650397Sobrien else 1667132718Skan y = addr_side_effect_eval (y, ysize, 0); 166850397Sobrien 166950397Sobrien if (rtx_equal_for_memref_p (x, y)) 167050397Sobrien { 167150397Sobrien if (xsize <= 0 || ysize <= 0) 167250397Sobrien return 1; 167350397Sobrien if (c >= 0 && xsize > c) 167450397Sobrien return 1; 167550397Sobrien if (c < 0 && ysize+c > 0) 167650397Sobrien return 1; 167750397Sobrien return 0; 167850397Sobrien } 167950397Sobrien 168050397Sobrien /* This code used to check for conflicts involving stack references and 168150397Sobrien globals but the base address alias code now handles these cases. */ 168250397Sobrien 168350397Sobrien if (GET_CODE (x) == PLUS) 168450397Sobrien { 168550397Sobrien /* The fact that X is canonicalized means that this 168650397Sobrien PLUS rtx is canonicalized. */ 168750397Sobrien rtx x0 = XEXP (x, 0); 168850397Sobrien rtx x1 = XEXP (x, 1); 168950397Sobrien 169050397Sobrien if (GET_CODE (y) == PLUS) 169150397Sobrien { 169250397Sobrien /* The fact that Y is canonicalized means that this 169350397Sobrien PLUS rtx is canonicalized. */ 169450397Sobrien rtx y0 = XEXP (y, 0); 169550397Sobrien rtx y1 = XEXP (y, 1); 169650397Sobrien 169750397Sobrien if (rtx_equal_for_memref_p (x1, y1)) 169850397Sobrien return memrefs_conflict_p (xsize, x0, ysize, y0, c); 169950397Sobrien if (rtx_equal_for_memref_p (x0, y0)) 170050397Sobrien return memrefs_conflict_p (xsize, x1, ysize, y1, c); 170150397Sobrien if (GET_CODE (x1) == CONST_INT) 170252284Sobrien { 170352284Sobrien if (GET_CODE (y1) == CONST_INT) 170452284Sobrien return memrefs_conflict_p (xsize, x0, ysize, y0, 170552284Sobrien c - INTVAL (x1) + INTVAL (y1)); 170652284Sobrien else 170752284Sobrien return memrefs_conflict_p (xsize, x0, ysize, y, 170852284Sobrien c - INTVAL (x1)); 170952284Sobrien } 171050397Sobrien else if (GET_CODE (y1) == CONST_INT) 171150397Sobrien return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1)); 171250397Sobrien 171350397Sobrien return 1; 171450397Sobrien } 171550397Sobrien else if (GET_CODE (x1) == CONST_INT) 171650397Sobrien return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1)); 171750397Sobrien } 171850397Sobrien else if (GET_CODE (y) == PLUS) 171950397Sobrien { 172050397Sobrien /* The fact that Y is canonicalized means that this 172150397Sobrien PLUS rtx is canonicalized. */ 172250397Sobrien rtx y0 = XEXP (y, 0); 172350397Sobrien rtx y1 = XEXP (y, 1); 172450397Sobrien 172550397Sobrien if (GET_CODE (y1) == CONST_INT) 172650397Sobrien return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1)); 172750397Sobrien else 172850397Sobrien return 1; 172950397Sobrien } 173050397Sobrien 173150397Sobrien if (GET_CODE (x) == GET_CODE (y)) 173250397Sobrien switch (GET_CODE (x)) 173350397Sobrien { 173450397Sobrien case MULT: 173550397Sobrien { 173650397Sobrien /* Handle cases where we expect the second operands to be the 173750397Sobrien same, and check only whether the first operand would conflict 173850397Sobrien or not. */ 173950397Sobrien rtx x0, y0; 174050397Sobrien rtx x1 = canon_rtx (XEXP (x, 1)); 174150397Sobrien rtx y1 = canon_rtx (XEXP (y, 1)); 174250397Sobrien if (! rtx_equal_for_memref_p (x1, y1)) 174350397Sobrien return 1; 174450397Sobrien x0 = canon_rtx (XEXP (x, 0)); 174550397Sobrien y0 = canon_rtx (XEXP (y, 0)); 174650397Sobrien if (rtx_equal_for_memref_p (x0, y0)) 174750397Sobrien return (xsize == 0 || ysize == 0 174850397Sobrien || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); 174950397Sobrien 175050397Sobrien /* Can't properly adjust our sizes. */ 175150397Sobrien if (GET_CODE (x1) != CONST_INT) 175250397Sobrien return 1; 175350397Sobrien xsize /= INTVAL (x1); 175450397Sobrien ysize /= INTVAL (x1); 175550397Sobrien c /= INTVAL (x1); 175650397Sobrien return memrefs_conflict_p (xsize, x0, ysize, y0, c); 175750397Sobrien } 175850397Sobrien 175950397Sobrien default: 176050397Sobrien break; 176150397Sobrien } 176250397Sobrien 176350397Sobrien /* Treat an access through an AND (e.g. a subword access on an Alpha) 1764117395Skan as an access with indeterminate size. Assume that references 176552284Sobrien besides AND are aligned, so if the size of the other reference is 176652284Sobrien at least as large as the alignment, assume no other overlap. */ 176750397Sobrien if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT) 176852284Sobrien { 176952284Sobrien if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1))) 177052284Sobrien xsize = -1; 1771132718Skan return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), ysize, y, c); 177252284Sobrien } 177350397Sobrien if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT) 177450397Sobrien { 177552284Sobrien /* ??? If we are indexing far enough into the array/structure, we 1776117395Skan may yet be able to determine that we can not overlap. But we 177750397Sobrien also need to that we are far enough from the end not to overlap 177852284Sobrien a following reference, so we do nothing with that for now. */ 177952284Sobrien if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1))) 178052284Sobrien ysize = -1; 1781132718Skan return memrefs_conflict_p (xsize, x, ysize, canon_rtx (XEXP (y, 0)), c); 178250397Sobrien } 178350397Sobrien 178450397Sobrien if (CONSTANT_P (x)) 178550397Sobrien { 178650397Sobrien if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT) 178750397Sobrien { 178850397Sobrien c += (INTVAL (y) - INTVAL (x)); 178950397Sobrien return (xsize <= 0 || ysize <= 0 179050397Sobrien || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); 179150397Sobrien } 179250397Sobrien 179350397Sobrien if (GET_CODE (x) == CONST) 179450397Sobrien { 179550397Sobrien if (GET_CODE (y) == CONST) 179650397Sobrien return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 179750397Sobrien ysize, canon_rtx (XEXP (y, 0)), c); 179850397Sobrien else 179950397Sobrien return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 180050397Sobrien ysize, y, c); 180150397Sobrien } 180250397Sobrien if (GET_CODE (y) == CONST) 180350397Sobrien return memrefs_conflict_p (xsize, x, ysize, 180450397Sobrien canon_rtx (XEXP (y, 0)), c); 180550397Sobrien 180650397Sobrien if (CONSTANT_P (y)) 180790075Sobrien return (xsize <= 0 || ysize <= 0 180850397Sobrien || (rtx_equal_for_memref_p (x, y) 180990075Sobrien && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)))); 181050397Sobrien 181150397Sobrien return 1; 181250397Sobrien } 181350397Sobrien return 1; 181450397Sobrien} 181550397Sobrien 181650397Sobrien/* Functions to compute memory dependencies. 181750397Sobrien 181850397Sobrien Since we process the insns in execution order, we can build tables 181950397Sobrien to keep track of what registers are fixed (and not aliased), what registers 182050397Sobrien are varying in known ways, and what registers are varying in unknown 182150397Sobrien ways. 182250397Sobrien 182350397Sobrien If both memory references are volatile, then there must always be a 182450397Sobrien dependence between the two references, since their order can not be 182550397Sobrien changed. A volatile and non-volatile reference can be interchanged 1826117395Skan though. 182750397Sobrien 182890075Sobrien A MEM_IN_STRUCT reference at a non-AND varying address can never 182990075Sobrien conflict with a non-MEM_IN_STRUCT reference at a fixed address. We 183090075Sobrien also must allow AND addresses, because they may generate accesses 183190075Sobrien outside the object being referenced. This is used to generate 183290075Sobrien aligned addresses from unaligned addresses, for instance, the alpha 183390075Sobrien storeqi_unaligned pattern. */ 183450397Sobrien 183550397Sobrien/* Read dependence: X is read after read in MEM takes place. There can 183650397Sobrien only be a dependence here if both reads are volatile. */ 183750397Sobrien 183850397Sobrienint 1839132718Skanread_dependence (rtx mem, rtx x) 184050397Sobrien{ 184150397Sobrien return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem); 184250397Sobrien} 184350397Sobrien 184452284Sobrien/* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and 184552284Sobrien MEM2 is a reference to a structure at a varying address, or returns 184652284Sobrien MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL 184752284Sobrien value is returned MEM1 and MEM2 can never alias. VARIES_P is used 184852284Sobrien to decide whether or not an address may vary; it should return 184990075Sobrien nonzero whenever variation is possible. 185090075Sobrien MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */ 1851117395Skan 185290075Sobrienstatic rtx 1853132718Skanfixed_scalar_and_varying_struct_p (rtx mem1, rtx mem2, rtx mem1_addr, 1854132718Skan rtx mem2_addr, 1855132718Skan int (*varies_p) (rtx, int)) 1856117395Skan{ 185790075Sobrien if (! flag_strict_aliasing) 185890075Sobrien return NULL_RTX; 185952284Sobrien 1860117395Skan if (MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2) 186190075Sobrien && !varies_p (mem1_addr, 1) && varies_p (mem2_addr, 1)) 186252284Sobrien /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a 186352284Sobrien varying address. */ 186452284Sobrien return mem1; 186552284Sobrien 1866117395Skan if (MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2) 186790075Sobrien && varies_p (mem1_addr, 1) && !varies_p (mem2_addr, 1)) 186852284Sobrien /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a 186952284Sobrien varying address. */ 187052284Sobrien return mem2; 187152284Sobrien 187252284Sobrien return NULL_RTX; 187352284Sobrien} 187452284Sobrien 187552284Sobrien/* Returns nonzero if something about the mode or address format MEM1 187652284Sobrien indicates that it might well alias *anything*. */ 187752284Sobrien 187852284Sobrienstatic int 1879132718Skanaliases_everything_p (rtx mem) 188052284Sobrien{ 188152284Sobrien if (GET_CODE (XEXP (mem, 0)) == AND) 1882169689Skan /* If the address is an AND, it's very hard to know at what it is 188352284Sobrien actually pointing. */ 188452284Sobrien return 1; 1885117395Skan 188652284Sobrien return 0; 188752284Sobrien} 188852284Sobrien 188990075Sobrien/* Return true if we can determine that the fields referenced cannot 189090075Sobrien overlap for any pair of objects. */ 189190075Sobrien 189290075Sobrienstatic bool 1893132718Skannonoverlapping_component_refs_p (tree x, tree y) 189490075Sobrien{ 189590075Sobrien tree fieldx, fieldy, typex, typey, orig_y; 189690075Sobrien 189790075Sobrien do 189890075Sobrien { 189990075Sobrien /* The comparison has to be done at a common type, since we don't 190090075Sobrien know how the inheritance hierarchy works. */ 190190075Sobrien orig_y = y; 190290075Sobrien do 190390075Sobrien { 190490075Sobrien fieldx = TREE_OPERAND (x, 1); 1905169689Skan typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx)); 190690075Sobrien 190790075Sobrien y = orig_y; 190890075Sobrien do 190990075Sobrien { 191090075Sobrien fieldy = TREE_OPERAND (y, 1); 1911169689Skan typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy)); 191290075Sobrien 191390075Sobrien if (typex == typey) 191490075Sobrien goto found; 191590075Sobrien 191690075Sobrien y = TREE_OPERAND (y, 0); 191790075Sobrien } 191890075Sobrien while (y && TREE_CODE (y) == COMPONENT_REF); 191990075Sobrien 192090075Sobrien x = TREE_OPERAND (x, 0); 192190075Sobrien } 192290075Sobrien while (x && TREE_CODE (x) == COMPONENT_REF); 192390075Sobrien /* Never found a common type. */ 192490075Sobrien return false; 192590075Sobrien 192690075Sobrien found: 192790075Sobrien /* If we're left with accessing different fields of a structure, 192890075Sobrien then no overlap. */ 192990075Sobrien if (TREE_CODE (typex) == RECORD_TYPE 193090075Sobrien && fieldx != fieldy) 193190075Sobrien return true; 193290075Sobrien 193390075Sobrien /* The comparison on the current field failed. If we're accessing 193490075Sobrien a very nested structure, look at the next outer level. */ 193590075Sobrien x = TREE_OPERAND (x, 0); 193690075Sobrien y = TREE_OPERAND (y, 0); 193790075Sobrien } 193890075Sobrien while (x && y 193990075Sobrien && TREE_CODE (x) == COMPONENT_REF 194090075Sobrien && TREE_CODE (y) == COMPONENT_REF); 1941117395Skan 194290075Sobrien return false; 194390075Sobrien} 194490075Sobrien 194590075Sobrien/* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */ 194690075Sobrien 194790075Sobrienstatic tree 1948132718Skandecl_for_component_ref (tree x) 194990075Sobrien{ 195090075Sobrien do 195190075Sobrien { 195290075Sobrien x = TREE_OPERAND (x, 0); 195390075Sobrien } 195490075Sobrien while (x && TREE_CODE (x) == COMPONENT_REF); 195590075Sobrien 195690075Sobrien return x && DECL_P (x) ? x : NULL_TREE; 195790075Sobrien} 195890075Sobrien 195990075Sobrien/* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the 196090075Sobrien offset of the field reference. */ 196190075Sobrien 196290075Sobrienstatic rtx 1963132718Skanadjust_offset_for_component_ref (tree x, rtx offset) 196490075Sobrien{ 196590075Sobrien HOST_WIDE_INT ioffset; 196690075Sobrien 196790075Sobrien if (! offset) 196890075Sobrien return NULL_RTX; 196990075Sobrien 197090075Sobrien ioffset = INTVAL (offset); 1971117395Skan do 197290075Sobrien { 1973169689Skan tree offset = component_ref_field_offset (x); 197490075Sobrien tree field = TREE_OPERAND (x, 1); 197590075Sobrien 1976169689Skan if (! host_integerp (offset, 1)) 197790075Sobrien return NULL_RTX; 1978169689Skan ioffset += (tree_low_cst (offset, 1) 197990075Sobrien + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1) 198090075Sobrien / BITS_PER_UNIT)); 198190075Sobrien 198290075Sobrien x = TREE_OPERAND (x, 0); 198390075Sobrien } 198490075Sobrien while (x && TREE_CODE (x) == COMPONENT_REF); 198590075Sobrien 198690075Sobrien return GEN_INT (ioffset); 198790075Sobrien} 198890075Sobrien 1989132718Skan/* Return nonzero if we can determine the exprs corresponding to memrefs 199090075Sobrien X and Y and they do not overlap. */ 199190075Sobrien 199290075Sobrienstatic int 1993132718Skannonoverlapping_memrefs_p (rtx x, rtx y) 199490075Sobrien{ 199590075Sobrien tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y); 199690075Sobrien rtx rtlx, rtly; 199790075Sobrien rtx basex, basey; 199890075Sobrien rtx moffsetx, moffsety; 199990075Sobrien HOST_WIDE_INT offsetx = 0, offsety = 0, sizex, sizey, tem; 200090075Sobrien 200190075Sobrien /* Unless both have exprs, we can't tell anything. */ 200290075Sobrien if (exprx == 0 || expry == 0) 200390075Sobrien return 0; 200490075Sobrien 200590075Sobrien /* If both are field references, we may be able to determine something. */ 200690075Sobrien if (TREE_CODE (exprx) == COMPONENT_REF 200790075Sobrien && TREE_CODE (expry) == COMPONENT_REF 200890075Sobrien && nonoverlapping_component_refs_p (exprx, expry)) 200990075Sobrien return 1; 201090075Sobrien 2011169689Skan 201290075Sobrien /* If the field reference test failed, look at the DECLs involved. */ 201390075Sobrien moffsetx = MEM_OFFSET (x); 201490075Sobrien if (TREE_CODE (exprx) == COMPONENT_REF) 201590075Sobrien { 2016169689Skan if (TREE_CODE (expry) == VAR_DECL 2017169689Skan && POINTER_TYPE_P (TREE_TYPE (expry))) 2018169689Skan { 2019169689Skan tree field = TREE_OPERAND (exprx, 1); 2020169689Skan tree fieldcontext = DECL_FIELD_CONTEXT (field); 2021169689Skan if (ipa_type_escape_field_does_not_clobber_p (fieldcontext, 2022169689Skan TREE_TYPE (field))) 2023169689Skan return 1; 2024169689Skan } 2025169689Skan { 2026169689Skan tree t = decl_for_component_ref (exprx); 2027169689Skan if (! t) 2028169689Skan return 0; 2029169689Skan moffsetx = adjust_offset_for_component_ref (exprx, moffsetx); 2030169689Skan exprx = t; 2031169689Skan } 203290075Sobrien } 2033169689Skan else if (INDIRECT_REF_P (exprx)) 2034110611Skan { 2035110611Skan exprx = TREE_OPERAND (exprx, 0); 2036110611Skan if (flag_argument_noalias < 2 2037110611Skan || TREE_CODE (exprx) != PARM_DECL) 2038110611Skan return 0; 2039110611Skan } 2040110611Skan 204190075Sobrien moffsety = MEM_OFFSET (y); 204290075Sobrien if (TREE_CODE (expry) == COMPONENT_REF) 204390075Sobrien { 2044169689Skan if (TREE_CODE (exprx) == VAR_DECL 2045169689Skan && POINTER_TYPE_P (TREE_TYPE (exprx))) 2046169689Skan { 2047169689Skan tree field = TREE_OPERAND (expry, 1); 2048169689Skan tree fieldcontext = DECL_FIELD_CONTEXT (field); 2049169689Skan if (ipa_type_escape_field_does_not_clobber_p (fieldcontext, 2050169689Skan TREE_TYPE (field))) 2051169689Skan return 1; 2052169689Skan } 2053169689Skan { 2054169689Skan tree t = decl_for_component_ref (expry); 2055169689Skan if (! t) 2056169689Skan return 0; 2057169689Skan moffsety = adjust_offset_for_component_ref (expry, moffsety); 2058169689Skan expry = t; 2059169689Skan } 206090075Sobrien } 2061169689Skan else if (INDIRECT_REF_P (expry)) 2062110611Skan { 2063110611Skan expry = TREE_OPERAND (expry, 0); 2064110611Skan if (flag_argument_noalias < 2 2065110611Skan || TREE_CODE (expry) != PARM_DECL) 2066110611Skan return 0; 2067110611Skan } 206890075Sobrien 206990075Sobrien if (! DECL_P (exprx) || ! DECL_P (expry)) 207090075Sobrien return 0; 207190075Sobrien 207290075Sobrien rtlx = DECL_RTL (exprx); 207390075Sobrien rtly = DECL_RTL (expry); 207490075Sobrien 207590075Sobrien /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they 207690075Sobrien can't overlap unless they are the same because we never reuse that part 207790075Sobrien of the stack frame used for locals for spilled pseudos. */ 2078169689Skan if ((!MEM_P (rtlx) || !MEM_P (rtly)) 207990075Sobrien && ! rtx_equal_p (rtlx, rtly)) 208090075Sobrien return 1; 208190075Sobrien 208290075Sobrien /* Get the base and offsets of both decls. If either is a register, we 208390075Sobrien know both are and are the same, so use that as the base. The only 208490075Sobrien we can avoid overlap is if we can deduce that they are nonoverlapping 208590075Sobrien pieces of that decl, which is very rare. */ 2086169689Skan basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx; 208790075Sobrien if (GET_CODE (basex) == PLUS && GET_CODE (XEXP (basex, 1)) == CONST_INT) 208890075Sobrien offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0); 208990075Sobrien 2090169689Skan basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly; 209190075Sobrien if (GET_CODE (basey) == PLUS && GET_CODE (XEXP (basey, 1)) == CONST_INT) 209290075Sobrien offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0); 209390075Sobrien 209490075Sobrien /* If the bases are different, we know they do not overlap if both 2095117395Skan are constants or if one is a constant and the other a pointer into the 209690075Sobrien stack frame. Otherwise a different base means we can't tell if they 209790075Sobrien overlap or not. */ 209890075Sobrien if (! rtx_equal_p (basex, basey)) 2099117395Skan return ((CONSTANT_P (basex) && CONSTANT_P (basey)) 2100117395Skan || (CONSTANT_P (basex) && REG_P (basey) 2101117395Skan && REGNO_PTR_FRAME_P (REGNO (basey))) 2102117395Skan || (CONSTANT_P (basey) && REG_P (basex) 2103117395Skan && REGNO_PTR_FRAME_P (REGNO (basex)))); 210490075Sobrien 2105169689Skan sizex = (!MEM_P (rtlx) ? (int) GET_MODE_SIZE (GET_MODE (rtlx)) 210690075Sobrien : MEM_SIZE (rtlx) ? INTVAL (MEM_SIZE (rtlx)) 210790075Sobrien : -1); 2108169689Skan sizey = (!MEM_P (rtly) ? (int) GET_MODE_SIZE (GET_MODE (rtly)) 210990075Sobrien : MEM_SIZE (rtly) ? INTVAL (MEM_SIZE (rtly)) : 211090075Sobrien -1); 211190075Sobrien 211290075Sobrien /* If we have an offset for either memref, it can update the values computed 211390075Sobrien above. */ 211490075Sobrien if (moffsetx) 211590075Sobrien offsetx += INTVAL (moffsetx), sizex -= INTVAL (moffsetx); 211690075Sobrien if (moffsety) 211790075Sobrien offsety += INTVAL (moffsety), sizey -= INTVAL (moffsety); 211890075Sobrien 211990075Sobrien /* If a memref has both a size and an offset, we can use the smaller size. 212090075Sobrien We can't do this if the offset isn't known because we must view this 212190075Sobrien memref as being anywhere inside the DECL's MEM. */ 212290075Sobrien if (MEM_SIZE (x) && moffsetx) 212390075Sobrien sizex = INTVAL (MEM_SIZE (x)); 212490075Sobrien if (MEM_SIZE (y) && moffsety) 212590075Sobrien sizey = INTVAL (MEM_SIZE (y)); 212690075Sobrien 212790075Sobrien /* Put the values of the memref with the lower offset in X's values. */ 212890075Sobrien if (offsetx > offsety) 212990075Sobrien { 213090075Sobrien tem = offsetx, offsetx = offsety, offsety = tem; 213190075Sobrien tem = sizex, sizex = sizey, sizey = tem; 213290075Sobrien } 213390075Sobrien 213490075Sobrien /* If we don't know the size of the lower-offset value, we can't tell 213590075Sobrien if they conflict. Otherwise, we do the test. */ 2136110611Skan return sizex >= 0 && offsety >= offsetx + sizex; 213790075Sobrien} 213890075Sobrien 213950397Sobrien/* True dependence: X is read after store in MEM takes place. */ 214050397Sobrien 214150397Sobrienint 2142132718Skantrue_dependence (rtx mem, enum machine_mode mem_mode, rtx x, 2143132718Skan int (*varies) (rtx, int)) 214450397Sobrien{ 214590075Sobrien rtx x_addr, mem_addr; 214690075Sobrien rtx base; 214750397Sobrien 214850397Sobrien if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 214950397Sobrien return 1; 215050397Sobrien 215196263Sobrien /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 215296263Sobrien This is used in epilogue deallocation functions. */ 215396263Sobrien if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 215496263Sobrien return 1; 215596263Sobrien if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 215696263Sobrien return 1; 2157169689Skan if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER 2158169689Skan || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER) 2159169689Skan return 1; 216096263Sobrien 216150397Sobrien if (DIFFERENT_ALIAS_SETS_P (x, mem)) 216250397Sobrien return 0; 216350397Sobrien 2164169689Skan /* Read-only memory is by definition never modified, and therefore can't 2165169689Skan conflict with anything. We don't expect to find read-only set on MEM, 2166169689Skan but stupid user tricks can produce them, so don't die. */ 2167169689Skan if (MEM_READONLY_P (x)) 216890075Sobrien return 0; 216990075Sobrien 217090075Sobrien if (nonoverlapping_memrefs_p (mem, x)) 217190075Sobrien return 0; 217290075Sobrien 217390075Sobrien if (mem_mode == VOIDmode) 217490075Sobrien mem_mode = GET_MODE (mem); 217590075Sobrien 217690075Sobrien x_addr = get_addr (XEXP (x, 0)); 217790075Sobrien mem_addr = get_addr (XEXP (mem, 0)); 217890075Sobrien 217990075Sobrien base = find_base_term (x_addr); 218090075Sobrien if (base && (GET_CODE (base) == LABEL_REF 218190075Sobrien || (GET_CODE (base) == SYMBOL_REF 218290075Sobrien && CONSTANT_POOL_ADDRESS_P (base)))) 218390075Sobrien return 0; 218490075Sobrien 218590075Sobrien if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode)) 218690075Sobrien return 0; 218790075Sobrien 218890075Sobrien x_addr = canon_rtx (x_addr); 218990075Sobrien mem_addr = canon_rtx (mem_addr); 219090075Sobrien 219190075Sobrien if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr, 219290075Sobrien SIZE_FOR_MODE (x), x_addr, 0)) 219390075Sobrien return 0; 219490075Sobrien 219590075Sobrien if (aliases_everything_p (x)) 219690075Sobrien return 1; 219790075Sobrien 219890075Sobrien /* We cannot use aliases_everything_p to test MEM, since we must look 219990075Sobrien at MEM_MODE, rather than GET_MODE (MEM). */ 220090075Sobrien if (mem_mode == QImode || GET_CODE (mem_addr) == AND) 220190075Sobrien return 1; 220290075Sobrien 220390075Sobrien /* In true_dependence we also allow BLKmode to alias anything. Why 220490075Sobrien don't we do this in anti_dependence and output_dependence? */ 220590075Sobrien if (mem_mode == BLKmode || GET_MODE (x) == BLKmode) 220690075Sobrien return 1; 220790075Sobrien 220890075Sobrien return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, 220990075Sobrien varies); 221090075Sobrien} 221190075Sobrien 221290075Sobrien/* Canonical true dependence: X is read after store in MEM takes place. 2213117395Skan Variant of true_dependence which assumes MEM has already been 2214117395Skan canonicalized (hence we no longer do that here). 2215117395Skan The mem_addr argument has been added, since true_dependence computed 221690075Sobrien this value prior to canonicalizing. */ 221790075Sobrien 221890075Sobrienint 2219132718Skancanon_true_dependence (rtx mem, enum machine_mode mem_mode, rtx mem_addr, 2220132718Skan rtx x, int (*varies) (rtx, int)) 222190075Sobrien{ 222290075Sobrien rtx x_addr; 222390075Sobrien 222490075Sobrien if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 222590075Sobrien return 1; 222690075Sobrien 222796263Sobrien /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 222896263Sobrien This is used in epilogue deallocation functions. */ 222996263Sobrien if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 223096263Sobrien return 1; 223196263Sobrien if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 223296263Sobrien return 1; 2233169689Skan if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER 2234169689Skan || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER) 2235169689Skan return 1; 223696263Sobrien 223790075Sobrien if (DIFFERENT_ALIAS_SETS_P (x, mem)) 223890075Sobrien return 0; 223990075Sobrien 2240169689Skan /* Read-only memory is by definition never modified, and therefore can't 2241169689Skan conflict with anything. We don't expect to find read-only set on MEM, 2242169689Skan but stupid user tricks can produce them, so don't die. */ 2243169689Skan if (MEM_READONLY_P (x)) 224450397Sobrien return 0; 224550397Sobrien 224690075Sobrien if (nonoverlapping_memrefs_p (x, mem)) 224790075Sobrien return 0; 224852284Sobrien 224990075Sobrien x_addr = get_addr (XEXP (x, 0)); 225090075Sobrien 225190075Sobrien if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode)) 225250397Sobrien return 0; 225350397Sobrien 225490075Sobrien x_addr = canon_rtx (x_addr); 225550397Sobrien if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr, 225650397Sobrien SIZE_FOR_MODE (x), x_addr, 0)) 225750397Sobrien return 0; 225850397Sobrien 225952284Sobrien if (aliases_everything_p (x)) 226052284Sobrien return 1; 226150397Sobrien 226290075Sobrien /* We cannot use aliases_everything_p to test MEM, since we must look 226352284Sobrien at MEM_MODE, rather than GET_MODE (MEM). */ 226452284Sobrien if (mem_mode == QImode || GET_CODE (mem_addr) == AND) 226552284Sobrien return 1; 226650397Sobrien 226752284Sobrien /* In true_dependence we also allow BLKmode to alias anything. Why 226852284Sobrien don't we do this in anti_dependence and output_dependence? */ 226952284Sobrien if (mem_mode == BLKmode || GET_MODE (x) == BLKmode) 227050397Sobrien return 1; 227150397Sobrien 227290075Sobrien return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, 227390075Sobrien varies); 227450397Sobrien} 227550397Sobrien 2276117395Skan/* Returns nonzero if a write to X might alias a previous read from 2277169689Skan (or, if WRITEP is nonzero, a write to) MEM. */ 227850397Sobrien 227952284Sobrienstatic int 2280169689Skanwrite_dependence_p (rtx mem, rtx x, int writep) 228150397Sobrien{ 228250397Sobrien rtx x_addr, mem_addr; 228352284Sobrien rtx fixed_scalar; 228490075Sobrien rtx base; 228550397Sobrien 228650397Sobrien if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 228750397Sobrien return 1; 228850397Sobrien 228996263Sobrien /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 229096263Sobrien This is used in epilogue deallocation functions. */ 229196263Sobrien if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 229296263Sobrien return 1; 229396263Sobrien if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 229496263Sobrien return 1; 2295169689Skan if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER 2296169689Skan || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER) 2297169689Skan return 1; 229896263Sobrien 229990075Sobrien if (DIFFERENT_ALIAS_SETS_P (x, mem)) 230090075Sobrien return 0; 230190075Sobrien 2302169689Skan /* A read from read-only memory can't conflict with read-write memory. */ 2303169689Skan if (!writep && MEM_READONLY_P (mem)) 2304169689Skan return 0; 230590075Sobrien 230690075Sobrien if (nonoverlapping_memrefs_p (x, mem)) 230750397Sobrien return 0; 230850397Sobrien 230990075Sobrien x_addr = get_addr (XEXP (x, 0)); 231090075Sobrien mem_addr = get_addr (XEXP (mem, 0)); 231150397Sobrien 231290075Sobrien if (! writep) 231390075Sobrien { 231490075Sobrien base = find_base_term (mem_addr); 231590075Sobrien if (base && (GET_CODE (base) == LABEL_REF 231690075Sobrien || (GET_CODE (base) == SYMBOL_REF 231790075Sobrien && CONSTANT_POOL_ADDRESS_P (base)))) 231890075Sobrien return 0; 231990075Sobrien } 232090075Sobrien 232190075Sobrien if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), 232290075Sobrien GET_MODE (mem))) 232350397Sobrien return 0; 232450397Sobrien 232590075Sobrien x_addr = canon_rtx (x_addr); 232690075Sobrien mem_addr = canon_rtx (mem_addr); 232750397Sobrien 232852284Sobrien if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr, 232952284Sobrien SIZE_FOR_MODE (x), x_addr, 0)) 233052284Sobrien return 0; 233152284Sobrien 2332117395Skan fixed_scalar 233390075Sobrien = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, 233490075Sobrien rtx_addr_varies_p); 233590075Sobrien 233652284Sobrien return (!(fixed_scalar == mem && !aliases_everything_p (x)) 233752284Sobrien && !(fixed_scalar == x && !aliases_everything_p (mem))); 233850397Sobrien} 233950397Sobrien 234052284Sobrien/* Anti dependence: X is written after read in MEM takes place. */ 234152284Sobrien 234252284Sobrienint 2343132718Skananti_dependence (rtx mem, rtx x) 234452284Sobrien{ 2345169689Skan return write_dependence_p (mem, x, /*writep=*/0); 234652284Sobrien} 234752284Sobrien 234850397Sobrien/* Output dependence: X is written after store in MEM takes place. */ 234950397Sobrien 235050397Sobrienint 2351132718Skanoutput_dependence (rtx mem, rtx x) 235250397Sobrien{ 2353169689Skan return write_dependence_p (mem, x, /*writep=*/1); 235450397Sobrien} 2355117395Skan 235650397Sobrien 235790075Sobrienvoid 2358132718Skaninit_alias_once (void) 235950397Sobrien{ 236090075Sobrien int i; 236150397Sobrien 236250397Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 236350397Sobrien /* Check whether this register can hold an incoming pointer 236450397Sobrien argument. FUNCTION_ARG_REGNO_P tests outgoing register 236590075Sobrien numbers, so translate if necessary due to register windows. */ 236650397Sobrien if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i)) 236750397Sobrien && HARD_REGNO_MODE_OK (i, Pmode)) 2368117395Skan static_reg_base_value[i] 2369117395Skan = gen_rtx_ADDRESS (VOIDmode, gen_rtx_REG (Pmode, i)); 237052284Sobrien 2371117395Skan static_reg_base_value[STACK_POINTER_REGNUM] 2372117395Skan = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx); 2373117395Skan static_reg_base_value[ARG_POINTER_REGNUM] 2374117395Skan = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx); 2375117395Skan static_reg_base_value[FRAME_POINTER_REGNUM] 2376117395Skan = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx); 2377117395Skan#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 2378117395Skan static_reg_base_value[HARD_FRAME_POINTER_REGNUM] 2379117395Skan = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx); 2380117395Skan#endif 2381132718Skan} 2382117395Skan 2383132718Skan/* Set MEMORY_MODIFIED when X modifies DATA (that is assumed 2384132718Skan to be memory reference. */ 2385132718Skanstatic bool memory_modified; 2386132718Skanstatic void 2387132718Skanmemory_modified_1 (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data) 2388132718Skan{ 2389169689Skan if (MEM_P (x)) 2390132718Skan { 2391132718Skan if (anti_dependence (x, (rtx)data) || output_dependence (x, (rtx)data)) 2392132718Skan memory_modified = true; 2393132718Skan } 239450397Sobrien} 239550397Sobrien 2396132718Skan 2397132718Skan/* Return true when INSN possibly modify memory contents of MEM 2398169689Skan (i.e. address can be modified). */ 2399132718Skanbool 2400132718Skanmemory_modified_in_insn_p (rtx mem, rtx insn) 2401132718Skan{ 2402132718Skan if (!INSN_P (insn)) 2403132718Skan return false; 2404132718Skan memory_modified = false; 2405132718Skan note_stores (PATTERN (insn), memory_modified_1, mem); 2406132718Skan return memory_modified; 2407132718Skan} 2408132718Skan 240990075Sobrien/* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE 241090075Sobrien array. */ 241190075Sobrien 241250397Sobrienvoid 2413132718Skaninit_alias_analysis (void) 241450397Sobrien{ 2415132718Skan unsigned int maxreg = max_reg_num (); 241650397Sobrien int changed, pass; 241790075Sobrien int i; 241890075Sobrien unsigned int ui; 241990075Sobrien rtx insn; 242050397Sobrien 2421132718Skan timevar_push (TV_ALIAS_ANALYSIS); 242250397Sobrien 2423132718Skan reg_known_value_size = maxreg - FIRST_PSEUDO_REGISTER; 2424132718Skan reg_known_value = ggc_calloc (reg_known_value_size, sizeof (rtx)); 2425132718Skan reg_known_equiv_p = xcalloc (reg_known_value_size, sizeof (bool)); 242650397Sobrien 2427169689Skan /* If we have memory allocated from the previous run, use it. */ 2428132718Skan if (old_reg_base_value) 2429169689Skan reg_base_value = old_reg_base_value; 243090075Sobrien 2431169689Skan if (reg_base_value) 2432169689Skan VEC_truncate (rtx, reg_base_value, 0); 243350397Sobrien 2434169689Skan VEC_safe_grow (rtx, gc, reg_base_value, maxreg); 2435169689Skan memset (VEC_address (rtx, reg_base_value), 0, 2436169689Skan sizeof (rtx) * VEC_length (rtx, reg_base_value)); 2437169689Skan 2438169689Skan new_reg_base_value = XNEWVEC (rtx, maxreg); 2439169689Skan reg_seen = XNEWVEC (char, maxreg); 2440169689Skan 244150397Sobrien /* The basic idea is that each pass through this loop will use the 244250397Sobrien "constant" information from the previous pass to propagate alias 244350397Sobrien information through another level of assignments. 244450397Sobrien 244550397Sobrien This could get expensive if the assignment chains are long. Maybe 244650397Sobrien we should throttle the number of iterations, possibly based on 244750397Sobrien the optimization level or flag_expensive_optimizations. 244850397Sobrien 244950397Sobrien We could propagate more information in the first pass by making use 245050397Sobrien of REG_N_SETS to determine immediately that the alias information 245150397Sobrien for a pseudo is "constant". 245250397Sobrien 245350397Sobrien A program with an uninitialized variable can cause an infinite loop 245450397Sobrien here. Instead of doing a full dataflow analysis to detect such problems 245550397Sobrien we just cap the number of iterations for the loop. 245650397Sobrien 245750397Sobrien The state of the arrays for the set chain in question does not matter 245850397Sobrien since the program has undefined behavior. */ 245950397Sobrien 246050397Sobrien pass = 0; 246150397Sobrien do 246250397Sobrien { 246350397Sobrien /* Assume nothing will change this iteration of the loop. */ 246450397Sobrien changed = 0; 246550397Sobrien 246650397Sobrien /* We want to assign the same IDs each iteration of this loop, so 246750397Sobrien start counting from zero each iteration of the loop. */ 246850397Sobrien unique_id = 0; 246950397Sobrien 247090075Sobrien /* We're at the start of the function each iteration through the 247150397Sobrien loop, so we're copying arguments. */ 2472117395Skan copying_arguments = true; 247350397Sobrien 247450397Sobrien /* Wipe the potential alias information clean for this pass. */ 2475132718Skan memset (new_reg_base_value, 0, maxreg * sizeof (rtx)); 247650397Sobrien 247750397Sobrien /* Wipe the reg_seen array clean. */ 2478132718Skan memset (reg_seen, 0, maxreg); 247950397Sobrien 248050397Sobrien /* Mark all hard registers which may contain an address. 248150397Sobrien The stack, frame and argument pointers may contain an address. 248250397Sobrien An argument register which can hold a Pmode value may contain 248350397Sobrien an address even if it is not in BASE_REGS. 248450397Sobrien 248550397Sobrien The address expression is VOIDmode for an argument and 248650397Sobrien Pmode for other registers. */ 248750397Sobrien 2488117395Skan memcpy (new_reg_base_value, static_reg_base_value, 2489117395Skan FIRST_PSEUDO_REGISTER * sizeof (rtx)); 249050397Sobrien 249150397Sobrien /* Walk the insns adding values to the new_reg_base_value array. */ 249250397Sobrien for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 249350397Sobrien { 249490075Sobrien if (INSN_P (insn)) 249550397Sobrien { 249650397Sobrien rtx note, set; 249790075Sobrien 249890075Sobrien#if defined (HAVE_prologue) || defined (HAVE_epilogue) 249990075Sobrien /* The prologue/epilogue insns are not threaded onto the 250090075Sobrien insn chain until after reload has completed. Thus, 250190075Sobrien there is no sense wasting time checking if INSN is in 250290075Sobrien the prologue/epilogue until after reload has completed. */ 250390075Sobrien if (reload_completed 250490075Sobrien && prologue_epilogue_contains (insn)) 250590075Sobrien continue; 250690075Sobrien#endif 250790075Sobrien 250850397Sobrien /* If this insn has a noalias note, process it, Otherwise, 2509169689Skan scan for sets. A simple set will have no side effects 2510169689Skan which could change the base value of any other register. */ 251150397Sobrien 251250397Sobrien if (GET_CODE (PATTERN (insn)) == SET 251390075Sobrien && REG_NOTES (insn) != 0 251490075Sobrien && find_reg_note (insn, REG_NOALIAS, NULL_RTX)) 251590075Sobrien record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL); 251650397Sobrien else 251790075Sobrien note_stores (PATTERN (insn), record_set, NULL); 251850397Sobrien 251950397Sobrien set = single_set (insn); 252050397Sobrien 252150397Sobrien if (set != 0 2522169689Skan && REG_P (SET_DEST (set)) 252390075Sobrien && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER) 252450397Sobrien { 252590075Sobrien unsigned int regno = REGNO (SET_DEST (set)); 252690075Sobrien rtx src = SET_SRC (set); 2527132718Skan rtx t; 252890075Sobrien 252990075Sobrien if (REG_NOTES (insn) != 0 253090075Sobrien && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0 253190075Sobrien && REG_N_SETS (regno) == 1) 253290075Sobrien || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0) 253390075Sobrien && GET_CODE (XEXP (note, 0)) != EXPR_LIST 253490075Sobrien && ! rtx_varies_p (XEXP (note, 0), 1) 2535132718Skan && ! reg_overlap_mentioned_p (SET_DEST (set), 2536132718Skan XEXP (note, 0))) 253790075Sobrien { 2538132718Skan set_reg_known_value (regno, XEXP (note, 0)); 2539132718Skan set_reg_known_equiv_p (regno, 2540132718Skan REG_NOTE_KIND (note) == REG_EQUIV); 254190075Sobrien } 254290075Sobrien else if (REG_N_SETS (regno) == 1 254390075Sobrien && GET_CODE (src) == PLUS 2544169689Skan && REG_P (XEXP (src, 0)) 2545132718Skan && (t = get_reg_known_value (REGNO (XEXP (src, 0)))) 254690075Sobrien && GET_CODE (XEXP (src, 1)) == CONST_INT) 254790075Sobrien { 2548132718Skan t = plus_constant (t, INTVAL (XEXP (src, 1))); 2549132718Skan set_reg_known_value (regno, t); 2550132718Skan set_reg_known_equiv_p (regno, 0); 255190075Sobrien } 255290075Sobrien else if (REG_N_SETS (regno) == 1 255390075Sobrien && ! rtx_varies_p (src, 1)) 255490075Sobrien { 2555132718Skan set_reg_known_value (regno, src); 2556132718Skan set_reg_known_equiv_p (regno, 0); 255790075Sobrien } 255850397Sobrien } 255950397Sobrien } 2560169689Skan else if (NOTE_P (insn) 256150397Sobrien && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG) 2562117395Skan copying_arguments = false; 256350397Sobrien } 256450397Sobrien 256550397Sobrien /* Now propagate values from new_reg_base_value to reg_base_value. */ 2566169689Skan gcc_assert (maxreg == (unsigned int) max_reg_num()); 2567169689Skan 2568132718Skan for (ui = 0; ui < maxreg; ui++) 256950397Sobrien { 257052284Sobrien if (new_reg_base_value[ui] 2571169689Skan && new_reg_base_value[ui] != VEC_index (rtx, reg_base_value, ui) 2572132718Skan && ! rtx_equal_p (new_reg_base_value[ui], 2573169689Skan VEC_index (rtx, reg_base_value, ui))) 257450397Sobrien { 2575169689Skan VEC_replace (rtx, reg_base_value, ui, new_reg_base_value[ui]); 257650397Sobrien changed = 1; 257750397Sobrien } 257850397Sobrien } 257950397Sobrien } 258050397Sobrien while (changed && ++pass < MAX_ALIAS_LOOP_PASSES); 258150397Sobrien 258250397Sobrien /* Fill in the remaining entries. */ 2583132718Skan for (i = 0; i < (int)reg_known_value_size; i++) 258450397Sobrien if (reg_known_value[i] == 0) 2585132718Skan reg_known_value[i] = regno_reg_rtx[i + FIRST_PSEUDO_REGISTER]; 258650397Sobrien 258750397Sobrien /* Simplify the reg_base_value array so that no register refers to 258850397Sobrien another register, except to special registers indirectly through 258950397Sobrien ADDRESS expressions. 259050397Sobrien 259150397Sobrien In theory this loop can take as long as O(registers^2), but unless 259250397Sobrien there are very long dependency chains it will run in close to linear 259350397Sobrien time. 259450397Sobrien 259550397Sobrien This loop may not be needed any longer now that the main loop does 259650397Sobrien a better job at propagating alias information. */ 259750397Sobrien pass = 0; 259850397Sobrien do 259950397Sobrien { 260050397Sobrien changed = 0; 260150397Sobrien pass++; 2602132718Skan for (ui = 0; ui < maxreg; ui++) 260350397Sobrien { 2604169689Skan rtx base = VEC_index (rtx, reg_base_value, ui); 2605169689Skan if (base && REG_P (base)) 260650397Sobrien { 260752284Sobrien unsigned int base_regno = REGNO (base); 260852284Sobrien if (base_regno == ui) /* register set from itself */ 2609169689Skan VEC_replace (rtx, reg_base_value, ui, 0); 261050397Sobrien else 2611169689Skan VEC_replace (rtx, reg_base_value, ui, 2612169689Skan VEC_index (rtx, reg_base_value, base_regno)); 261350397Sobrien changed = 1; 261450397Sobrien } 261550397Sobrien } 261650397Sobrien } 261750397Sobrien while (changed && pass < MAX_ALIAS_LOOP_PASSES); 261850397Sobrien 261990075Sobrien /* Clean up. */ 262090075Sobrien free (new_reg_base_value); 262150397Sobrien new_reg_base_value = 0; 262290075Sobrien free (reg_seen); 262350397Sobrien reg_seen = 0; 2624132718Skan timevar_pop (TV_ALIAS_ANALYSIS); 262550397Sobrien} 262650397Sobrien 262750397Sobrienvoid 2628132718Skanend_alias_analysis (void) 262950397Sobrien{ 2630132718Skan old_reg_base_value = reg_base_value; 2631169689Skan ggc_free (reg_known_value); 263250397Sobrien reg_known_value = 0; 263390075Sobrien reg_known_value_size = 0; 2634132718Skan free (reg_known_equiv_p); 263590075Sobrien reg_known_equiv_p = 0; 263650397Sobrien} 2637117395Skan 2638117395Skan#include "gt-alias.h" 2639