alias.c revision 122180
1134911Ssam/* Alias analysis for GNU C 2134911Ssam Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003 3134911Ssam Free Software Foundation, Inc. 4134911Ssam Contributed by John Carr (jfc@mit.edu). 5134911Ssam 6134911SsamThis file is part of GCC. 7134911Ssam 8134911SsamGCC is free software; you can redistribute it and/or modify it under 9134911Ssamthe terms of the GNU General Public License as published by the Free 10134911SsamSoftware Foundation; either version 2, or (at your option) any later 11134911Ssamversion. 12134911Ssam 13134911SsamGCC is distributed in the hope that it will be useful, but WITHOUT ANY 14134911SsamWARRANTY; without even the implied warranty of MERCHANTABILITY or 15134911SsamFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16134911Ssamfor more details. 17134911Ssam 18134911SsamYou should have received a copy of the GNU General Public License 19134911Ssamalong with GCC; see the file COPYING. If not, write to the Free 20134911SsamSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 21134911Ssam02111-1307, USA. */ 22134911Ssam 23134911Ssam#include "config.h" 24134911Ssam#include "system.h" 25134911Ssam#include "rtl.h" 26134911Ssam#include "tree.h" 27134911Ssam#include "tm_p.h" 28134911Ssam#include "function.h" 29134911Ssam#include "expr.h" 30134911Ssam#include "regs.h" 31134911Ssam#include "hard-reg-set.h" 32134911Ssam#include "basic-block.h" 33134911Ssam#include "flags.h" 34134911Ssam#include "output.h" 35134911Ssam#include "toplev.h" 36134911Ssam#include "cselib.h" 37134911Ssam#include "splay-tree.h" 38134911Ssam#include "ggc.h" 39134911Ssam#include "langhooks.h" 40134911Ssam#include "target.h" 41134911Ssam 42134911Ssam/* The alias sets assigned to MEMs assist the back-end in determining 43167755Ssam which MEMs can alias which other MEMs. In general, two MEMs in 44134911Ssam different alias sets cannot alias each other, with one important 45134911Ssam exception. Consider something like: 46134911Ssam 47134911Ssam struct S {int i; double d; }; 48134911Ssam 49134911Ssam a store to an `S' can alias something of either type `int' or type 50134911Ssam `double'. (However, a store to an `int' cannot alias a `double' 51134911Ssam and vice versa.) We indicate this via a tree structure that looks 52134911Ssam like: 53134911Ssam struct S 54134911Ssam / \ 55134911Ssam / \ 56134911Ssam |/_ _\| 57134911Ssam int double 58134911Ssam 59134911Ssam (The arrows are directed and point downwards.) 60134911Ssam In this situation we say the alias set for `struct S' is the 61134911Ssam `superset' and that those for `int' and `double' are `subsets'. 62134911Ssam 63134911Ssam To see whether two alias sets can point to the same memory, we must 64134911Ssam see if either alias set is a subset of the other. We need not trace 65134911Ssam past immediate descendents, however, since we propagate all 66134911Ssam grandchildren up one level. 67134911Ssam 68134911Ssam Alias set zero is implicitly a superset of all other alias sets. 69134911Ssam However, this is no actual entry for alias set zero. It is an 70134911Ssam error to attempt to explicitly construct a subset of zero. */ 71134911Ssam 72134911Ssamtypedef struct alias_set_entry 73134911Ssam{ 74134911Ssam /* The alias set number, as stored in MEM_ALIAS_SET. */ 75134911Ssam HOST_WIDE_INT alias_set; 76134911Ssam 77134911Ssam /* The children of the alias set. These are not just the immediate 78134911Ssam children, but, in fact, all descendents. So, if we have: 79134911Ssam 80134911Ssam struct T { struct S s; float f; } 81134911Ssam 82134911Ssam continuing our example above, the children here will be all of 83134911Ssam `int', `double', `float', and `struct S'. */ 84134911Ssam splay_tree children; 85134911Ssam 86134911Ssam /* Nonzero if would have a child of zero: this effectively makes this 87134911Ssam alias set the same as alias set zero. */ 88134911Ssam int has_zero_child; 89134911Ssam} *alias_set_entry; 90134911Ssam 91134911Ssamstatic int rtx_equal_for_memref_p PARAMS ((rtx, rtx)); 92134911Ssamstatic rtx find_symbolic_term PARAMS ((rtx)); 93134911Ssamrtx get_addr PARAMS ((rtx)); 94134911Ssamstatic int memrefs_conflict_p PARAMS ((int, rtx, int, rtx, 95134911Ssam HOST_WIDE_INT)); 96175979Smatteostatic void record_set PARAMS ((rtx, rtx, void *)); 97134911Ssamstatic rtx find_base_term PARAMS ((rtx)); 98134911Ssamstatic int base_alias_check PARAMS ((rtx, rtx, enum machine_mode, 99134911Ssam enum machine_mode)); 100134911Ssamstatic rtx find_base_value PARAMS ((rtx)); 101134911Ssamstatic int mems_in_disjoint_alias_sets_p PARAMS ((rtx, rtx)); 102134911Ssamstatic int insert_subset_children PARAMS ((splay_tree_node, void*)); 103134911Ssamstatic tree find_base_decl PARAMS ((tree)); 104134911Ssamstatic alias_set_entry get_alias_set_entry PARAMS ((HOST_WIDE_INT)); 105134911Ssamstatic rtx fixed_scalar_and_varying_struct_p PARAMS ((rtx, rtx, rtx, rtx, 106134911Ssam int (*) (rtx, int))); 107134911Ssamstatic int aliases_everything_p PARAMS ((rtx)); 108134911Ssamstatic bool nonoverlapping_component_refs_p PARAMS ((tree, tree)); 109134911Ssamstatic tree decl_for_component_ref PARAMS ((tree)); 110134911Ssamstatic rtx adjust_offset_for_component_ref PARAMS ((tree, rtx)); 111167755Ssamstatic int nonoverlapping_memrefs_p PARAMS ((rtx, rtx)); 112134911Ssamstatic int write_dependence_p PARAMS ((rtx, rtx, int)); 113134911Ssam 114134911Ssamstatic int nonlocal_mentioned_p_1 PARAMS ((rtx *, void *)); 115134911Ssamstatic int nonlocal_mentioned_p PARAMS ((rtx)); 116134911Ssamstatic int nonlocal_referenced_p_1 PARAMS ((rtx *, void *)); 117134911Ssamstatic int nonlocal_referenced_p PARAMS ((rtx)); 118134911Ssamstatic int nonlocal_set_p_1 PARAMS ((rtx *, void *)); 119134911Ssamstatic int nonlocal_set_p PARAMS ((rtx)); 120134911Ssam 121134911Ssam/* Set up all info needed to perform alias analysis on memory references. */ 122134911Ssam 123134911Ssam/* Returns the size in bytes of the mode of X. */ 124134911Ssam#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X))) 125134911Ssam 126134911Ssam/* Returns nonzero if MEM1 and MEM2 do not alias because they are in 127134911Ssam different alias sets. We ignore alias sets in functions making use 128134911Ssam of variable arguments because the va_arg macros on some systems are 129134911Ssam not legal ANSI C. */ 130134911Ssam#define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \ 131134911Ssam mems_in_disjoint_alias_sets_p (MEM1, MEM2) 132134911Ssam 133134911Ssam/* Cap the number of passes we make over the insns propagating alias 134134911Ssam information through set chains. 10 is a completely arbitrary choice. */ 135134911Ssam#define MAX_ALIAS_LOOP_PASSES 10 136134911Ssam 137158886Smr/* reg_base_value[N] gives an address to which register N is related. 138158886Smr If all sets after the first add or subtract to the current value 139158886Smr or otherwise modify it so it does not point to a different top level 140134911Ssam object, reg_base_value[N] is equal to the address part of the source 141134911Ssam of the first set. 142134911Ssam 143134911Ssam A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS 144134911Ssam expressions represent certain special values: function arguments and 145167755Ssam the stack, frame, and argument pointers. 146134911Ssam 147134911Ssam The contents of an ADDRESS is not normally used, the mode of the 148134911Ssam ADDRESS determines whether the ADDRESS is a function argument or some 149134911Ssam other special value. Pointer equality, not rtx_equal_p, determines whether 150134911Ssam two ADDRESS expressions refer to the same base address. 151134911Ssam 152134911Ssam The only use of the contents of an ADDRESS is for determining if the 153134911Ssam current function performs nonlocal memory memory references for the 154167755Ssam purposes of marking the function as a constant function. */ 155134911Ssam 156134911Ssamstatic GTY((length ("reg_base_value_size"))) rtx *reg_base_value; 157134911Ssamstatic rtx *new_reg_base_value; 158134911Ssamstatic unsigned int reg_base_value_size; /* size of reg_base_value array */ 159134911Ssam 160134911Ssam/* Static hunks of RTL used by the aliasing code; these are initialized 161134911Ssam once per function to avoid unnecessary RTL allocations. */ 162134911Ssamstatic GTY (()) rtx static_reg_base_value[FIRST_PSEUDO_REGISTER]; 163134911Ssam 164134911Ssam#define REG_BASE_VALUE(X) \ 165134911Ssam (REGNO (X) < reg_base_value_size \ 166134911Ssam ? reg_base_value[REGNO (X)] : 0) 167134911Ssam 168134911Ssam/* Vector of known invariant relationships between registers. Set in 169134911Ssam loop unrolling. Indexed by register number, if nonzero the value 170134911Ssam is an expression describing this register in terms of another. 171134911Ssam 172134911Ssam The length of this array is REG_BASE_VALUE_SIZE. 173134911Ssam 174134911Ssam Because this array contains only pseudo registers it has no effect 175134911Ssam after reload. */ 176134911Ssamstatic rtx *alias_invariant; 177134911Ssam 178134911Ssam/* Vector indexed by N giving the initial (unchanging) value known for 179134911Ssam pseudo-register N. This array is initialized in 180134911Ssam init_alias_analysis, and does not change until end_alias_analysis 181134911Ssam is called. */ 182134911Ssamrtx *reg_known_value; 183134911Ssam 184134911Ssam/* Indicates number of valid entries in reg_known_value. */ 185134911Ssamstatic unsigned int reg_known_value_size; 186134911Ssam 187134911Ssam/* Vector recording for each reg_known_value whether it is due to a 188134911Ssam REG_EQUIV note. Future passes (viz., reload) may replace the 189134911Ssam pseudo with the equivalent expression and so we account for the 190134911Ssam dependences that would be introduced if that happens. 191134911Ssam 192134911Ssam The REG_EQUIV notes created in assign_parms may mention the arg 193134911Ssam pointer, and there are explicit insns in the RTL that modify the 194134911Ssam arg pointer. Thus we must ensure that such insns don't get 195134911Ssam scheduled across each other because that would invalidate the 196134911Ssam REG_EQUIV notes. One could argue that the REG_EQUIV notes are 197134911Ssam wrong, but solving the problem in the scheduler will likely give 198134911Ssam better code, so we do it here. */ 199134911Ssamchar *reg_known_equiv_p; 200167755Ssam 201167755Ssam/* True when scanning insns from the start of the rtl to the 202167755Ssam NOTE_INSN_FUNCTION_BEG note. */ 203167755Ssamstatic bool copying_arguments; 204167755Ssam 205167755Ssam/* The splay-tree used to store the various alias set entries. */ 206167755Ssamstatic splay_tree alias_sets; 207167755Ssam 208167755Ssam/* Returns a pointer to the alias set entry for ALIAS_SET, if there is 209167755Ssam such an entry, or NULL otherwise. */ 210167755Ssam 211167755Ssamstatic alias_set_entry 212167755Ssamget_alias_set_entry (alias_set) 213167755Ssam HOST_WIDE_INT alias_set; 214167755Ssam{ 215167755Ssam splay_tree_node sn 216167755Ssam = splay_tree_lookup (alias_sets, (splay_tree_key) alias_set); 217167755Ssam 218167755Ssam return sn != 0 ? ((alias_set_entry) sn->value) : 0; 219167755Ssam} 220167755Ssam 221167755Ssam/* Returns nonzero if the alias sets for MEM1 and MEM2 are such that 222167755Ssam the two MEMs cannot alias each other. */ 223167755Ssam 224134911Ssamstatic int 225134911Ssammems_in_disjoint_alias_sets_p (mem1, mem2) 226134911Ssam rtx mem1; 227134911Ssam rtx mem2; 228134911Ssam{ 229134911Ssam#ifdef ENABLE_CHECKING 230134911Ssam/* Perform a basic sanity check. Namely, that there are no alias sets 231134911Ssam if we're not using strict aliasing. This helps to catch bugs 232134911Ssam whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or 233134911Ssam where a MEM is allocated in some way other than by the use of 234134911Ssam gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to 235134911Ssam use alias sets to indicate that spilled registers cannot alias each 236134911Ssam other, we might need to remove this check. */ 237134911Ssam if (! flag_strict_aliasing 238134911Ssam && (MEM_ALIAS_SET (mem1) != 0 || MEM_ALIAS_SET (mem2) != 0)) 239134911Ssam abort (); 240134911Ssam#endif 241134911Ssam 242134911Ssam return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), MEM_ALIAS_SET (mem2)); 243134911Ssam} 244134911Ssam 245134911Ssam/* Insert the NODE into the splay tree given by DATA. Used by 246140407Sphk record_alias_subset via splay_tree_foreach. */ 247134911Ssam 248134911Ssamstatic int 249134911Ssaminsert_subset_children (node, data) 250134911Ssam splay_tree_node node; 251167755Ssam void *data; 252134911Ssam{ 253134911Ssam splay_tree_insert ((splay_tree) data, node->key, node->value); 254134911Ssam 255134911Ssam return 0; 256134911Ssam} 257134911Ssam 258134911Ssam/* Return 1 if the two specified alias sets may conflict. */ 259134911Ssam 260134911Ssamint 261134911Ssamalias_sets_conflict_p (set1, set2) 262134911Ssam HOST_WIDE_INT set1, set2; 263134911Ssam{ 264134911Ssam alias_set_entry ase; 265134911Ssam 266134911Ssam /* If have no alias set information for one of the operands, we have 267134911Ssam to assume it can alias anything. */ 268134911Ssam if (set1 == 0 || set2 == 0 269134911Ssam /* If the two alias sets are the same, they may alias. */ 270134911Ssam || set1 == set2) 271134911Ssam return 1; 272134911Ssam 273167755Ssam /* See if the first alias set is a subset of the second. */ 274134911Ssam ase = get_alias_set_entry (set1); 275167755Ssam if (ase != 0 276134911Ssam && (ase->has_zero_child 277134911Ssam || splay_tree_lookup (ase->children, 278134911Ssam (splay_tree_key) set2))) 279134911Ssam return 1; 280134911Ssam 281134911Ssam /* Now do the same, but with the alias sets reversed. */ 282134911Ssam ase = get_alias_set_entry (set2); 283134911Ssam if (ase != 0 284134911Ssam && (ase->has_zero_child 285134911Ssam || splay_tree_lookup (ase->children, 286134911Ssam (splay_tree_key) set1))) 287134911Ssam return 1; 288134911Ssam 289134911Ssam /* The two alias sets are distinct and neither one is the 290134911Ssam child of the other. Therefore, they cannot alias. */ 291134911Ssam return 0; 292134911Ssam} 293134911Ssam 294134911Ssam/* Return 1 if TYPE is a RECORD_TYPE, UNION_TYPE, or QUAL_UNION_TYPE and has 295134911Ssam has any readonly fields. If any of the fields have types that 296134911Ssam contain readonly fields, return true as well. */ 297134911Ssam 298134911Ssamint 299134911Ssamreadonly_fields_p (type) 300134911Ssam tree type; 301134911Ssam{ 302134911Ssam tree field; 303134911Ssam 304134911Ssam if (TREE_CODE (type) != RECORD_TYPE && TREE_CODE (type) != UNION_TYPE 305134911Ssam && TREE_CODE (type) != QUAL_UNION_TYPE) 306167755Ssam return 0; 307134911Ssam 308134911Ssam for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field)) 309134911Ssam if (TREE_CODE (field) == FIELD_DECL 310134911Ssam && (TREE_READONLY (field) 311134911Ssam || readonly_fields_p (TREE_TYPE (field)))) 312134911Ssam return 1; 313134911Ssam 314134911Ssam return 0; 315134911Ssam} 316134911Ssam 317134911Ssam/* Return 1 if any MEM object of type T1 will always conflict (using the 318134911Ssam dependency routines in this file) with any MEM object of type T2. 319134911Ssam This is used when allocating temporary storage. If T1 and/or T2 are 320134911Ssam NULL_TREE, it means we know nothing about the storage. */ 321134911Ssam 322134911Ssamint 323134911Ssamobjects_must_conflict_p (t1, t2) 324134911Ssam tree t1, t2; 325134911Ssam{ 326134911Ssam HOST_WIDE_INT set1, set2; 327134911Ssam 328134911Ssam /* If neither has a type specified, we don't know if they'll conflict 329134911Ssam because we may be using them to store objects of various types, for 330134911Ssam example the argument and local variables areas of inlined functions. */ 331134911Ssam if (t1 == 0 && t2 == 0) 332134911Ssam return 0; 333134911Ssam 334134911Ssam /* If one or the other has readonly fields or is readonly, 335134911Ssam then they may not conflict. */ 336134911Ssam if ((t1 != 0 && readonly_fields_p (t1)) 337134911Ssam || (t2 != 0 && readonly_fields_p (t2)) 338134911Ssam || (t1 != 0 && lang_hooks.honor_readonly && TYPE_READONLY (t1)) 339134911Ssam || (t2 != 0 && lang_hooks.honor_readonly && TYPE_READONLY (t2))) 340134911Ssam return 0; 341134911Ssam 342134911Ssam /* If they are the same type, they must conflict. */ 343134911Ssam if (t1 == t2 344134911Ssam /* Likewise if both are volatile. */ 345134911Ssam || (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2))) 346134911Ssam return 1; 347134911Ssam 348134911Ssam set1 = t1 ? get_alias_set (t1) : 0; 349134911Ssam set2 = t2 ? get_alias_set (t2) : 0; 350134911Ssam 351134911Ssam /* Otherwise they conflict if they have no alias set or the same. We 352134911Ssam can't simply use alias_sets_conflict_p here, because we must make 353134911Ssam sure that every subtype of t1 will conflict with every subtype of 354134911Ssam t2 for which a pair of subobjects of these respective subtypes 355134911Ssam overlaps on the stack. */ 356134911Ssam return set1 == 0 || set2 == 0 || set1 == set2; 357134911Ssam} 358134911Ssam 359134911Ssam/* T is an expression with pointer type. Find the DECL on which this 360134911Ssam expression is based. (For example, in `a[i]' this would be `a'.) 361134911Ssam If there is no such DECL, or a unique decl cannot be determined, 362134911Ssam NULL_TREE is returned. */ 363134911Ssam 364134911Ssamstatic tree 365134911Ssamfind_base_decl (t) 366134911Ssam tree t; 367134911Ssam{ 368134911Ssam tree d0, d1, d2; 369134911Ssam 370134911Ssam if (t == 0 || t == error_mark_node || ! POINTER_TYPE_P (TREE_TYPE (t))) 371134911Ssam return 0; 372134911Ssam 373134911Ssam /* If this is a declaration, return it. */ 374134911Ssam if (TREE_CODE_CLASS (TREE_CODE (t)) == 'd') 375134911Ssam return t; 376134911Ssam 377134911Ssam /* Handle general expressions. It would be nice to deal with 378134911Ssam COMPONENT_REFs here. If we could tell that `a' and `b' were the 379134911Ssam same, then `a->f' and `b->f' are also the same. */ 380134911Ssam switch (TREE_CODE_CLASS (TREE_CODE (t))) 381134911Ssam { 382134911Ssam case '1': 383134911Ssam return find_base_decl (TREE_OPERAND (t, 0)); 384134911Ssam 385134911Ssam case '2': 386134911Ssam /* Return 0 if found in neither or both are the same. */ 387134911Ssam d0 = find_base_decl (TREE_OPERAND (t, 0)); 388134911Ssam d1 = find_base_decl (TREE_OPERAND (t, 1)); 389134911Ssam if (d0 == d1) 390134911Ssam return d0; 391134911Ssam else if (d0 == 0) 392134911Ssam return d1; 393134911Ssam else if (d1 == 0) 394134911Ssam return d0; 395134911Ssam else 396140407Sphk return 0; 397134911Ssam 398134911Ssam case '3': 399134911Ssam d0 = find_base_decl (TREE_OPERAND (t, 0)); 400134911Ssam d1 = find_base_decl (TREE_OPERAND (t, 1)); 401134911Ssam d2 = find_base_decl (TREE_OPERAND (t, 2)); 402134911Ssam 403134911Ssam /* Set any nonzero values from the last, then from the first. */ 404134911Ssam if (d1 == 0) d1 = d2; 405134911Ssam if (d0 == 0) d0 = d1; 406134911Ssam if (d1 == 0) d1 = d0; 407134911Ssam if (d2 == 0) d2 = d1; 408134911Ssam 409134911Ssam /* At this point all are nonzero or all are zero. If all three are the 410134911Ssam same, return it. Otherwise, return zero. */ 411134911Ssam return (d0 == d1 && d1 == d2) ? d0 : 0; 412134911Ssam 413134911Ssam default: 414134911Ssam return 0; 415134911Ssam } 416134911Ssam} 417134911Ssam 418134911Ssam/* Return 1 if all the nested component references handled by 419134911Ssam get_inner_reference in T are such that we can address the object in T. */ 420134911Ssam 421134911Ssamint 422134911Ssamcan_address_p (t) 423134911Ssam tree t; 424134911Ssam{ 425134911Ssam /* If we're at the end, it is vacuously addressable. */ 426134911Ssam if (! handled_component_p (t)) 427134911Ssam return 1; 428140407Sphk 429134911Ssam /* Bitfields are never addressable. */ 430134911Ssam else if (TREE_CODE (t) == BIT_FIELD_REF) 431134911Ssam return 0; 432134911Ssam 433134911Ssam /* Fields are addressable unless they are marked as nonaddressable or 434134911Ssam the containing type has alias set 0. */ 435134911Ssam else if (TREE_CODE (t) == COMPONENT_REF 436134911Ssam && ! DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)) 437134911Ssam && get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) != 0 438134911Ssam && can_address_p (TREE_OPERAND (t, 0))) 439134911Ssam return 1; 440134911Ssam 441134911Ssam /* Likewise for arrays. */ 442134911Ssam else if ((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF) 443134911Ssam && ! TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))) 444134911Ssam && get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) != 0 445134911Ssam && can_address_p (TREE_OPERAND (t, 0))) 446134911Ssam return 1; 447134911Ssam 448134911Ssam return 0; 449134911Ssam} 450134911Ssam 451134911Ssam/* Return the alias set for T, which may be either a type or an 452134911Ssam expression. Call language-specific routine for help, if needed. */ 453134911Ssam 454134911SsamHOST_WIDE_INT 455134911Ssamget_alias_set (t) 456134911Ssam tree t; 457134911Ssam{ 458134911Ssam HOST_WIDE_INT set; 459134911Ssam 460134911Ssam /* If we're not doing any alias analysis, just assume everything 461134911Ssam aliases everything else. Also return 0 if this or its type is 462134911Ssam an error. */ 463134911Ssam if (! flag_strict_aliasing || t == error_mark_node 464134911Ssam || (! TYPE_P (t) 465134911Ssam && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node))) 466134911Ssam return 0; 467134911Ssam 468134911Ssam /* We can be passed either an expression or a type. This and the 469134911Ssam language-specific routine may make mutually-recursive calls to each other 470134911Ssam to figure out what to do. At each juncture, we see if this is a tree 471134911Ssam that the language may need to handle specially. First handle things that 472134911Ssam aren't types. */ 473134911Ssam if (! TYPE_P (t)) 474134911Ssam { 475134911Ssam tree inner = t; 476134911Ssam tree placeholder_ptr = 0; 477134911Ssam 478134911Ssam /* Remove any nops, then give the language a chance to do 479134911Ssam something with this tree before we look at it. */ 480134911Ssam STRIP_NOPS (t); 481167755Ssam set = (*lang_hooks.get_alias_set) (t); 482134911Ssam if (set != -1) 483134911Ssam return set; 484134911Ssam 485134911Ssam /* First see if the actual object referenced is an INDIRECT_REF from a 486167755Ssam restrict-qualified pointer or a "void *". Replace 487167755Ssam PLACEHOLDER_EXPRs. */ 488167755Ssam while (TREE_CODE (inner) == PLACEHOLDER_EXPR 489167755Ssam || handled_component_p (inner)) 490167755Ssam { 491167755Ssam if (TREE_CODE (inner) == PLACEHOLDER_EXPR) 492134911Ssam inner = find_placeholder (inner, &placeholder_ptr); 493134911Ssam else 494134911Ssam inner = TREE_OPERAND (inner, 0); 495134911Ssam 496134911Ssam STRIP_NOPS (inner); 497134911Ssam } 498134911Ssam 499134911Ssam /* Check for accesses through restrict-qualified pointers. */ 500134911Ssam if (TREE_CODE (inner) == INDIRECT_REF) 501140407Sphk { 502134911Ssam tree decl = find_base_decl (TREE_OPERAND (inner, 0)); 503134911Ssam 504134911Ssam if (decl && DECL_POINTER_ALIAS_SET_KNOWN_P (decl)) 505134911Ssam { 506134911Ssam /* If we haven't computed the actual alias set, do it now. */ 507134911Ssam if (DECL_POINTER_ALIAS_SET (decl) == -2) 508134911Ssam { 509134911Ssam /* No two restricted pointers can point at the same thing. 510134911Ssam However, a restricted pointer can point at the same thing 511134911Ssam as an unrestricted pointer, if that unrestricted pointer 512134911Ssam is based on the restricted pointer. So, we make the 513134911Ssam alias set for the restricted pointer a subset of the 514134911Ssam alias set for the type pointed to by the type of the 515134911Ssam decl. */ 516134911Ssam HOST_WIDE_INT pointed_to_alias_set 517134911Ssam = get_alias_set (TREE_TYPE (TREE_TYPE (decl))); 518134911Ssam 519134911Ssam if (pointed_to_alias_set == 0) 520167755Ssam /* It's not legal to make a subset of alias set zero. */ 521134911Ssam ; 522134911Ssam else 523134911Ssam { 524134911Ssam DECL_POINTER_ALIAS_SET (decl) = new_alias_set (); 525134911Ssam record_alias_subset (pointed_to_alias_set, 526167755Ssam DECL_POINTER_ALIAS_SET (decl)); 527134911Ssam } 528134911Ssam } 529134911Ssam 530134911Ssam /* We use the alias set indicated in the declaration. */ 531134911Ssam return DECL_POINTER_ALIAS_SET (decl); 532134911Ssam } 533134911Ssam 534134911Ssam /* If we have an INDIRECT_REF via a void pointer, we don't 535134911Ssam know anything about what that might alias. */ 536134911Ssam else if (TREE_CODE (TREE_TYPE (inner)) == VOID_TYPE) 537134911Ssam return 0; 538134911Ssam } 539134911Ssam 540134911Ssam /* Otherwise, pick up the outermost object that we could have a pointer 541134911Ssam to, processing conversion and PLACEHOLDER_EXPR as above. */ 542134911Ssam placeholder_ptr = 0; 543134911Ssam while (TREE_CODE (t) == PLACEHOLDER_EXPR 544134911Ssam || (handled_component_p (t) && ! can_address_p (t))) 545167755Ssam { 546167755Ssam if (TREE_CODE (t) == PLACEHOLDER_EXPR) 547167755Ssam t = find_placeholder (t, &placeholder_ptr); 548134911Ssam else 549134911Ssam t = TREE_OPERAND (t, 0); 550134911Ssam 551134911Ssam STRIP_NOPS (t); 552134911Ssam } 553134911Ssam 554134911Ssam /* If we've already determined the alias set for a decl, just return 555134911Ssam it. This is necessary for C++ anonymous unions, whose component 556134911Ssam variables don't look like union members (boo!). */ 557134911Ssam if (TREE_CODE (t) == VAR_DECL 558134911Ssam && DECL_RTL_SET_P (t) && GET_CODE (DECL_RTL (t)) == MEM) 559134911Ssam return MEM_ALIAS_SET (DECL_RTL (t)); 560134911Ssam 561134911Ssam /* Now all we care about is the type. */ 562134911Ssam t = TREE_TYPE (t); 563134911Ssam } 564134911Ssam 565134911Ssam /* Variant qualifiers don't affect the alias set, so get the main 566134911Ssam variant. If this is a type with a known alias set, return it. */ 567134911Ssam t = TYPE_MAIN_VARIANT (t); 568134911Ssam if (TYPE_ALIAS_SET_KNOWN_P (t)) 569134911Ssam return TYPE_ALIAS_SET (t); 570134911Ssam 571134911Ssam /* See if the language has special handling for this type. */ 572134911Ssam set = (*lang_hooks.get_alias_set) (t); 573134911Ssam if (set != -1) 574134911Ssam return set; 575134911Ssam 576134911Ssam /* There are no objects of FUNCTION_TYPE, so there's no point in 577134911Ssam using up an alias set for them. (There are, of course, pointers 578134911Ssam and references to functions, but that's different.) */ 579134911Ssam else if (TREE_CODE (t) == FUNCTION_TYPE) 580134911Ssam set = 0; 581134911Ssam 582134911Ssam /* Unless the language specifies otherwise, let vector types alias 583134911Ssam their components. This avoids some nasty type punning issues in 584134911Ssam normal usage. And indeed lets vectors be treated more like an 585134911Ssam array slice. */ 586134911Ssam else if (TREE_CODE (t) == VECTOR_TYPE) 587134911Ssam set = get_alias_set (TREE_TYPE (t)); 588134911Ssam 589134911Ssam else 590134911Ssam /* Otherwise make a new alias set for this type. */ 591134911Ssam set = new_alias_set (); 592134911Ssam 593134911Ssam TYPE_ALIAS_SET (t) = set; 594134911Ssam 595134911Ssam /* If this is an aggregate type, we must record any component aliasing 596134911Ssam information. */ 597134911Ssam if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE) 598134911Ssam record_component_aliases (t); 599134911Ssam 600134911Ssam return set; 601134911Ssam} 602134911Ssam 603134911Ssam/* Return a brand-new alias set. */ 604134911Ssam 605134911SsamHOST_WIDE_INT 606134911Ssamnew_alias_set () 607134911Ssam{ 608134911Ssam static HOST_WIDE_INT last_alias_set; 609134911Ssam 610134911Ssam if (flag_strict_aliasing) 611134911Ssam return ++last_alias_set; 612134911Ssam else 613134911Ssam return 0; 614134911Ssam} 615134911Ssam 616134911Ssam/* Indicate that things in SUBSET can alias things in SUPERSET, but 617134911Ssam not vice versa. For example, in C, a store to an `int' can alias a 618134911Ssam structure containing an `int', but not vice versa. Here, the 619134911Ssam structure would be the SUPERSET and `int' the SUBSET. This 620134911Ssam function should be called only once per SUPERSET/SUBSET pair. 621134911Ssam 622134911Ssam It is illegal for SUPERSET to be zero; everything is implicitly a 623 subset of alias set zero. */ 624 625void 626record_alias_subset (superset, subset) 627 HOST_WIDE_INT superset; 628 HOST_WIDE_INT subset; 629{ 630 alias_set_entry superset_entry; 631 alias_set_entry subset_entry; 632 633 /* It is possible in complex type situations for both sets to be the same, 634 in which case we can ignore this operation. */ 635 if (superset == subset) 636 return; 637 638 if (superset == 0) 639 abort (); 640 641 superset_entry = get_alias_set_entry (superset); 642 if (superset_entry == 0) 643 { 644 /* Create an entry for the SUPERSET, so that we have a place to 645 attach the SUBSET. */ 646 superset_entry 647 = (alias_set_entry) xmalloc (sizeof (struct alias_set_entry)); 648 superset_entry->alias_set = superset; 649 superset_entry->children 650 = splay_tree_new (splay_tree_compare_ints, 0, 0); 651 superset_entry->has_zero_child = 0; 652 splay_tree_insert (alias_sets, (splay_tree_key) superset, 653 (splay_tree_value) superset_entry); 654 } 655 656 if (subset == 0) 657 superset_entry->has_zero_child = 1; 658 else 659 { 660 subset_entry = get_alias_set_entry (subset); 661 /* If there is an entry for the subset, enter all of its children 662 (if they are not already present) as children of the SUPERSET. */ 663 if (subset_entry) 664 { 665 if (subset_entry->has_zero_child) 666 superset_entry->has_zero_child = 1; 667 668 splay_tree_foreach (subset_entry->children, insert_subset_children, 669 superset_entry->children); 670 } 671 672 /* Enter the SUBSET itself as a child of the SUPERSET. */ 673 splay_tree_insert (superset_entry->children, 674 (splay_tree_key) subset, 0); 675 } 676} 677 678/* Record that component types of TYPE, if any, are part of that type for 679 aliasing purposes. For record types, we only record component types 680 for fields that are marked addressable. For array types, we always 681 record the component types, so the front end should not call this 682 function if the individual component aren't addressable. */ 683 684void 685record_component_aliases (type) 686 tree type; 687{ 688 HOST_WIDE_INT superset = get_alias_set (type); 689 tree field; 690 691 if (superset == 0) 692 return; 693 694 switch (TREE_CODE (type)) 695 { 696 case ARRAY_TYPE: 697 if (! TYPE_NONALIASED_COMPONENT (type)) 698 record_alias_subset (superset, get_alias_set (TREE_TYPE (type))); 699 break; 700 701 case RECORD_TYPE: 702 case UNION_TYPE: 703 case QUAL_UNION_TYPE: 704 /* Recursively record aliases for the base classes, if there are any */ 705 if (TYPE_BINFO (type) != NULL && TYPE_BINFO_BASETYPES (type) != NULL) 706 { 707 int i; 708 for (i = 0; i < TREE_VEC_LENGTH (TYPE_BINFO_BASETYPES (type)); i++) 709 { 710 tree binfo = TREE_VEC_ELT (TYPE_BINFO_BASETYPES (type), i); 711 record_alias_subset (superset, 712 get_alias_set (BINFO_TYPE (binfo))); 713 } 714 } 715 for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field)) 716 if (TREE_CODE (field) == FIELD_DECL && ! DECL_NONADDRESSABLE_P (field)) 717 record_alias_subset (superset, get_alias_set (TREE_TYPE (field))); 718 break; 719 720 case COMPLEX_TYPE: 721 record_alias_subset (superset, get_alias_set (TREE_TYPE (type))); 722 break; 723 724 default: 725 break; 726 } 727} 728 729/* Allocate an alias set for use in storing and reading from the varargs 730 spill area. */ 731 732HOST_WIDE_INT 733get_varargs_alias_set () 734{ 735 static HOST_WIDE_INT set = -1; 736 737 if (set == -1) 738 set = new_alias_set (); 739 740 return set; 741} 742 743/* Likewise, but used for the fixed portions of the frame, e.g., register 744 save areas. */ 745 746HOST_WIDE_INT 747get_frame_alias_set () 748{ 749 static HOST_WIDE_INT set = -1; 750 751 if (set == -1) 752 set = new_alias_set (); 753 754 return set; 755} 756 757/* Inside SRC, the source of a SET, find a base address. */ 758 759static rtx 760find_base_value (src) 761 rtx src; 762{ 763 unsigned int regno; 764 765 switch (GET_CODE (src)) 766 { 767 case SYMBOL_REF: 768 case LABEL_REF: 769 return src; 770 771 case REG: 772 regno = REGNO (src); 773 /* At the start of a function, argument registers have known base 774 values which may be lost later. Returning an ADDRESS 775 expression here allows optimization based on argument values 776 even when the argument registers are used for other purposes. */ 777 if (regno < FIRST_PSEUDO_REGISTER && copying_arguments) 778 return new_reg_base_value[regno]; 779 780 /* If a pseudo has a known base value, return it. Do not do this 781 for non-fixed hard regs since it can result in a circular 782 dependency chain for registers which have values at function entry. 783 784 The test above is not sufficient because the scheduler may move 785 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */ 786 if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno]) 787 && regno < reg_base_value_size) 788 { 789 /* If we're inside init_alias_analysis, use new_reg_base_value 790 to reduce the number of relaxation iterations. */ 791 if (new_reg_base_value && new_reg_base_value[regno] 792 && REG_N_SETS (regno) == 1) 793 return new_reg_base_value[regno]; 794 795 if (reg_base_value[regno]) 796 return reg_base_value[regno]; 797 } 798 799 return 0; 800 801 case MEM: 802 /* Check for an argument passed in memory. Only record in the 803 copying-arguments block; it is too hard to track changes 804 otherwise. */ 805 if (copying_arguments 806 && (XEXP (src, 0) == arg_pointer_rtx 807 || (GET_CODE (XEXP (src, 0)) == PLUS 808 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx))) 809 return gen_rtx_ADDRESS (VOIDmode, src); 810 return 0; 811 812 case CONST: 813 src = XEXP (src, 0); 814 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS) 815 break; 816 817 /* ... fall through ... */ 818 819 case PLUS: 820 case MINUS: 821 { 822 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1); 823 824 /* If either operand is a REG that is a known pointer, then it 825 is the base. */ 826 if (REG_P (src_0) && REG_POINTER (src_0)) 827 return find_base_value (src_0); 828 if (REG_P (src_1) && REG_POINTER (src_1)) 829 return find_base_value (src_1); 830 831 /* If either operand is a REG, then see if we already have 832 a known value for it. */ 833 if (REG_P (src_0)) 834 { 835 temp = find_base_value (src_0); 836 if (temp != 0) 837 src_0 = temp; 838 } 839 840 if (REG_P (src_1)) 841 { 842 temp = find_base_value (src_1); 843 if (temp!= 0) 844 src_1 = temp; 845 } 846 847 /* If either base is named object or a special address 848 (like an argument or stack reference), then use it for the 849 base term. */ 850 if (src_0 != 0 851 && (GET_CODE (src_0) == SYMBOL_REF 852 || GET_CODE (src_0) == LABEL_REF 853 || (GET_CODE (src_0) == ADDRESS 854 && GET_MODE (src_0) != VOIDmode))) 855 return src_0; 856 857 if (src_1 != 0 858 && (GET_CODE (src_1) == SYMBOL_REF 859 || GET_CODE (src_1) == LABEL_REF 860 || (GET_CODE (src_1) == ADDRESS 861 && GET_MODE (src_1) != VOIDmode))) 862 return src_1; 863 864 /* Guess which operand is the base address: 865 If either operand is a symbol, then it is the base. If 866 either operand is a CONST_INT, then the other is the base. */ 867 if (GET_CODE (src_1) == CONST_INT || CONSTANT_P (src_0)) 868 return find_base_value (src_0); 869 else if (GET_CODE (src_0) == CONST_INT || CONSTANT_P (src_1)) 870 return find_base_value (src_1); 871 872 return 0; 873 } 874 875 case LO_SUM: 876 /* The standard form is (lo_sum reg sym) so look only at the 877 second operand. */ 878 return find_base_value (XEXP (src, 1)); 879 880 case AND: 881 /* If the second operand is constant set the base 882 address to the first operand. */ 883 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0) 884 return find_base_value (XEXP (src, 0)); 885 return 0; 886 887 case TRUNCATE: 888 if (GET_MODE_SIZE (GET_MODE (src)) < GET_MODE_SIZE (Pmode)) 889 break; 890 /* Fall through. */ 891 case HIGH: 892 case PRE_INC: 893 case PRE_DEC: 894 case POST_INC: 895 case POST_DEC: 896 case PRE_MODIFY: 897 case POST_MODIFY: 898 return find_base_value (XEXP (src, 0)); 899 900 case ZERO_EXTEND: 901 case SIGN_EXTEND: /* used for NT/Alpha pointers */ 902 { 903 rtx temp = find_base_value (XEXP (src, 0)); 904 905#ifdef POINTERS_EXTEND_UNSIGNED 906 if (temp != 0 && CONSTANT_P (temp) && GET_MODE (temp) != Pmode) 907 temp = convert_memory_address (Pmode, temp); 908#endif 909 910 return temp; 911 } 912 913 default: 914 break; 915 } 916 917 return 0; 918} 919 920/* Called from init_alias_analysis indirectly through note_stores. */ 921 922/* While scanning insns to find base values, reg_seen[N] is nonzero if 923 register N has been set in this function. */ 924static char *reg_seen; 925 926/* Addresses which are known not to alias anything else are identified 927 by a unique integer. */ 928static int unique_id; 929 930static void 931record_set (dest, set, data) 932 rtx dest, set; 933 void *data ATTRIBUTE_UNUSED; 934{ 935 unsigned regno; 936 rtx src; 937 938 if (GET_CODE (dest) != REG) 939 return; 940 941 regno = REGNO (dest); 942 943 if (regno >= reg_base_value_size) 944 abort (); 945 946 if (set) 947 { 948 /* A CLOBBER wipes out any old value but does not prevent a previously 949 unset register from acquiring a base address (i.e. reg_seen is not 950 set). */ 951 if (GET_CODE (set) == CLOBBER) 952 { 953 new_reg_base_value[regno] = 0; 954 return; 955 } 956 src = SET_SRC (set); 957 } 958 else 959 { 960 if (reg_seen[regno]) 961 { 962 new_reg_base_value[regno] = 0; 963 return; 964 } 965 reg_seen[regno] = 1; 966 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode, 967 GEN_INT (unique_id++)); 968 return; 969 } 970 971 /* This is not the first set. If the new value is not related to the 972 old value, forget the base value. Note that the following code is 973 not detected: 974 extern int x, y; int *p = &x; p += (&y-&x); 975 ANSI C does not allow computing the difference of addresses 976 of distinct top level objects. */ 977 if (new_reg_base_value[regno]) 978 switch (GET_CODE (src)) 979 { 980 case LO_SUM: 981 case MINUS: 982 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest) 983 new_reg_base_value[regno] = 0; 984 break; 985 case PLUS: 986 /* If the value we add in the PLUS is also a valid base value, 987 this might be the actual base value, and the original value 988 an index. */ 989 { 990 rtx other = NULL_RTX; 991 992 if (XEXP (src, 0) == dest) 993 other = XEXP (src, 1); 994 else if (XEXP (src, 1) == dest) 995 other = XEXP (src, 0); 996 997 if (! other || find_base_value (other)) 998 new_reg_base_value[regno] = 0; 999 break; 1000 } 1001 case AND: 1002 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT) 1003 new_reg_base_value[regno] = 0; 1004 break; 1005 default: 1006 new_reg_base_value[regno] = 0; 1007 break; 1008 } 1009 /* If this is the first set of a register, record the value. */ 1010 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno]) 1011 && ! reg_seen[regno] && new_reg_base_value[regno] == 0) 1012 new_reg_base_value[regno] = find_base_value (src); 1013 1014 reg_seen[regno] = 1; 1015} 1016 1017/* Called from loop optimization when a new pseudo-register is 1018 created. It indicates that REGNO is being set to VAL. f INVARIANT 1019 is true then this value also describes an invariant relationship 1020 which can be used to deduce that two registers with unknown values 1021 are different. */ 1022 1023void 1024record_base_value (regno, val, invariant) 1025 unsigned int regno; 1026 rtx val; 1027 int invariant; 1028{ 1029 if (regno >= reg_base_value_size) 1030 return; 1031 1032 if (invariant && alias_invariant) 1033 alias_invariant[regno] = val; 1034 1035 if (GET_CODE (val) == REG) 1036 { 1037 if (REGNO (val) < reg_base_value_size) 1038 reg_base_value[regno] = reg_base_value[REGNO (val)]; 1039 1040 return; 1041 } 1042 1043 reg_base_value[regno] = find_base_value (val); 1044} 1045 1046/* Clear alias info for a register. This is used if an RTL transformation 1047 changes the value of a register. This is used in flow by AUTO_INC_DEC 1048 optimizations. We don't need to clear reg_base_value, since flow only 1049 changes the offset. */ 1050 1051void 1052clear_reg_alias_info (reg) 1053 rtx reg; 1054{ 1055 unsigned int regno = REGNO (reg); 1056 1057 if (regno < reg_known_value_size && regno >= FIRST_PSEUDO_REGISTER) 1058 reg_known_value[regno] = reg; 1059} 1060 1061/* Returns a canonical version of X, from the point of view alias 1062 analysis. (For example, if X is a MEM whose address is a register, 1063 and the register has a known value (say a SYMBOL_REF), then a MEM 1064 whose address is the SYMBOL_REF is returned.) */ 1065 1066rtx 1067canon_rtx (x) 1068 rtx x; 1069{ 1070 /* Recursively look for equivalences. */ 1071 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER 1072 && REGNO (x) < reg_known_value_size) 1073 return reg_known_value[REGNO (x)] == x 1074 ? x : canon_rtx (reg_known_value[REGNO (x)]); 1075 else if (GET_CODE (x) == PLUS) 1076 { 1077 rtx x0 = canon_rtx (XEXP (x, 0)); 1078 rtx x1 = canon_rtx (XEXP (x, 1)); 1079 1080 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1)) 1081 { 1082 if (GET_CODE (x0) == CONST_INT) 1083 return plus_constant (x1, INTVAL (x0)); 1084 else if (GET_CODE (x1) == CONST_INT) 1085 return plus_constant (x0, INTVAL (x1)); 1086 return gen_rtx_PLUS (GET_MODE (x), x0, x1); 1087 } 1088 } 1089 1090 /* This gives us much better alias analysis when called from 1091 the loop optimizer. Note we want to leave the original 1092 MEM alone, but need to return the canonicalized MEM with 1093 all the flags with their original values. */ 1094 else if (GET_CODE (x) == MEM) 1095 x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0))); 1096 1097 return x; 1098} 1099 1100/* Return 1 if X and Y are identical-looking rtx's. 1101 1102 We use the data in reg_known_value above to see if two registers with 1103 different numbers are, in fact, equivalent. */ 1104 1105static int 1106rtx_equal_for_memref_p (x, y) 1107 rtx x, y; 1108{ 1109 int i; 1110 int j; 1111 enum rtx_code code; 1112 const char *fmt; 1113 1114 if (x == 0 && y == 0) 1115 return 1; 1116 if (x == 0 || y == 0) 1117 return 0; 1118 1119 x = canon_rtx (x); 1120 y = canon_rtx (y); 1121 1122 if (x == y) 1123 return 1; 1124 1125 code = GET_CODE (x); 1126 /* Rtx's of different codes cannot be equal. */ 1127 if (code != GET_CODE (y)) 1128 return 0; 1129 1130 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. 1131 (REG:SI x) and (REG:HI x) are NOT equivalent. */ 1132 1133 if (GET_MODE (x) != GET_MODE (y)) 1134 return 0; 1135 1136 /* Some RTL can be compared without a recursive examination. */ 1137 switch (code) 1138 { 1139 case VALUE: 1140 return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y); 1141 1142 case REG: 1143 return REGNO (x) == REGNO (y); 1144 1145 case LABEL_REF: 1146 return XEXP (x, 0) == XEXP (y, 0); 1147 1148 case SYMBOL_REF: 1149 return XSTR (x, 0) == XSTR (y, 0); 1150 1151 case CONST_INT: 1152 case CONST_DOUBLE: 1153 /* There's no need to compare the contents of CONST_DOUBLEs or 1154 CONST_INTs because pointer equality is a good enough 1155 comparison for these nodes. */ 1156 return 0; 1157 1158 case ADDRESSOF: 1159 return (XINT (x, 1) == XINT (y, 1) 1160 && rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))); 1161 1162 default: 1163 break; 1164 } 1165 1166 /* For commutative operations, the RTX match if the operand match in any 1167 order. Also handle the simple binary and unary cases without a loop. */ 1168 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c') 1169 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)) 1170 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1))) 1171 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1)) 1172 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0)))); 1173 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2') 1174 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)) 1175 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1))); 1176 else if (GET_RTX_CLASS (code) == '1') 1177 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)); 1178 1179 /* Compare the elements. If any pair of corresponding elements 1180 fail to match, return 0 for the whole things. 1181 1182 Limit cases to types which actually appear in addresses. */ 1183 1184 fmt = GET_RTX_FORMAT (code); 1185 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1186 { 1187 switch (fmt[i]) 1188 { 1189 case 'i': 1190 if (XINT (x, i) != XINT (y, i)) 1191 return 0; 1192 break; 1193 1194 case 'E': 1195 /* Two vectors must have the same length. */ 1196 if (XVECLEN (x, i) != XVECLEN (y, i)) 1197 return 0; 1198 1199 /* And the corresponding elements must match. */ 1200 for (j = 0; j < XVECLEN (x, i); j++) 1201 if (rtx_equal_for_memref_p (XVECEXP (x, i, j), 1202 XVECEXP (y, i, j)) == 0) 1203 return 0; 1204 break; 1205 1206 case 'e': 1207 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0) 1208 return 0; 1209 break; 1210 1211 /* This can happen for asm operands. */ 1212 case 's': 1213 if (strcmp (XSTR (x, i), XSTR (y, i))) 1214 return 0; 1215 break; 1216 1217 /* This can happen for an asm which clobbers memory. */ 1218 case '0': 1219 break; 1220 1221 /* It is believed that rtx's at this level will never 1222 contain anything but integers and other rtx's, 1223 except for within LABEL_REFs and SYMBOL_REFs. */ 1224 default: 1225 abort (); 1226 } 1227 } 1228 return 1; 1229} 1230 1231/* Given an rtx X, find a SYMBOL_REF or LABEL_REF within 1232 X and return it, or return 0 if none found. */ 1233 1234static rtx 1235find_symbolic_term (x) 1236 rtx x; 1237{ 1238 int i; 1239 enum rtx_code code; 1240 const char *fmt; 1241 1242 code = GET_CODE (x); 1243 if (code == SYMBOL_REF || code == LABEL_REF) 1244 return x; 1245 if (GET_RTX_CLASS (code) == 'o') 1246 return 0; 1247 1248 fmt = GET_RTX_FORMAT (code); 1249 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1250 { 1251 rtx t; 1252 1253 if (fmt[i] == 'e') 1254 { 1255 t = find_symbolic_term (XEXP (x, i)); 1256 if (t != 0) 1257 return t; 1258 } 1259 else if (fmt[i] == 'E') 1260 break; 1261 } 1262 return 0; 1263} 1264 1265static rtx 1266find_base_term (x) 1267 rtx x; 1268{ 1269 cselib_val *val; 1270 struct elt_loc_list *l; 1271 1272#if defined (FIND_BASE_TERM) 1273 /* Try machine-dependent ways to find the base term. */ 1274 x = FIND_BASE_TERM (x); 1275#endif 1276 1277 switch (GET_CODE (x)) 1278 { 1279 case REG: 1280 return REG_BASE_VALUE (x); 1281 1282 case TRUNCATE: 1283 if (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (Pmode)) 1284 return 0; 1285 /* Fall through. */ 1286 case HIGH: 1287 case PRE_INC: 1288 case PRE_DEC: 1289 case POST_INC: 1290 case POST_DEC: 1291 case PRE_MODIFY: 1292 case POST_MODIFY: 1293 return find_base_term (XEXP (x, 0)); 1294 1295 case ZERO_EXTEND: 1296 case SIGN_EXTEND: /* Used for Alpha/NT pointers */ 1297 { 1298 rtx temp = find_base_term (XEXP (x, 0)); 1299 1300#ifdef POINTERS_EXTEND_UNSIGNED 1301 if (temp != 0 && CONSTANT_P (temp) && GET_MODE (temp) != Pmode) 1302 temp = convert_memory_address (Pmode, temp); 1303#endif 1304 1305 return temp; 1306 } 1307 1308 case VALUE: 1309 val = CSELIB_VAL_PTR (x); 1310 for (l = val->locs; l; l = l->next) 1311 if ((x = find_base_term (l->loc)) != 0) 1312 return x; 1313 return 0; 1314 1315 case CONST: 1316 x = XEXP (x, 0); 1317 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS) 1318 return 0; 1319 /* fall through */ 1320 case LO_SUM: 1321 case PLUS: 1322 case MINUS: 1323 { 1324 rtx tmp1 = XEXP (x, 0); 1325 rtx tmp2 = XEXP (x, 1); 1326 1327 /* This is a little bit tricky since we have to determine which of 1328 the two operands represents the real base address. Otherwise this 1329 routine may return the index register instead of the base register. 1330 1331 That may cause us to believe no aliasing was possible, when in 1332 fact aliasing is possible. 1333 1334 We use a few simple tests to guess the base register. Additional 1335 tests can certainly be added. For example, if one of the operands 1336 is a shift or multiply, then it must be the index register and the 1337 other operand is the base register. */ 1338 1339 if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2)) 1340 return find_base_term (tmp2); 1341 1342 /* If either operand is known to be a pointer, then use it 1343 to determine the base term. */ 1344 if (REG_P (tmp1) && REG_POINTER (tmp1)) 1345 return find_base_term (tmp1); 1346 1347 if (REG_P (tmp2) && REG_POINTER (tmp2)) 1348 return find_base_term (tmp2); 1349 1350 /* Neither operand was known to be a pointer. Go ahead and find the 1351 base term for both operands. */ 1352 tmp1 = find_base_term (tmp1); 1353 tmp2 = find_base_term (tmp2); 1354 1355 /* If either base term is named object or a special address 1356 (like an argument or stack reference), then use it for the 1357 base term. */ 1358 if (tmp1 != 0 1359 && (GET_CODE (tmp1) == SYMBOL_REF 1360 || GET_CODE (tmp1) == LABEL_REF 1361 || (GET_CODE (tmp1) == ADDRESS 1362 && GET_MODE (tmp1) != VOIDmode))) 1363 return tmp1; 1364 1365 if (tmp2 != 0 1366 && (GET_CODE (tmp2) == SYMBOL_REF 1367 || GET_CODE (tmp2) == LABEL_REF 1368 || (GET_CODE (tmp2) == ADDRESS 1369 && GET_MODE (tmp2) != VOIDmode))) 1370 return tmp2; 1371 1372 /* We could not determine which of the two operands was the 1373 base register and which was the index. So we can determine 1374 nothing from the base alias check. */ 1375 return 0; 1376 } 1377 1378 case AND: 1379 if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) != 0) 1380 return find_base_term (XEXP (x, 0)); 1381 return 0; 1382 1383 case SYMBOL_REF: 1384 case LABEL_REF: 1385 return x; 1386 1387 case ADDRESSOF: 1388 return REG_BASE_VALUE (frame_pointer_rtx); 1389 1390 default: 1391 return 0; 1392 } 1393} 1394 1395/* Return 0 if the addresses X and Y are known to point to different 1396 objects, 1 if they might be pointers to the same object. */ 1397 1398static int 1399base_alias_check (x, y, x_mode, y_mode) 1400 rtx x, y; 1401 enum machine_mode x_mode, y_mode; 1402{ 1403 rtx x_base = find_base_term (x); 1404 rtx y_base = find_base_term (y); 1405 1406 /* If the address itself has no known base see if a known equivalent 1407 value has one. If either address still has no known base, nothing 1408 is known about aliasing. */ 1409 if (x_base == 0) 1410 { 1411 rtx x_c; 1412 1413 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x) 1414 return 1; 1415 1416 x_base = find_base_term (x_c); 1417 if (x_base == 0) 1418 return 1; 1419 } 1420 1421 if (y_base == 0) 1422 { 1423 rtx y_c; 1424 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y) 1425 return 1; 1426 1427 y_base = find_base_term (y_c); 1428 if (y_base == 0) 1429 return 1; 1430 } 1431 1432 /* If the base addresses are equal nothing is known about aliasing. */ 1433 if (rtx_equal_p (x_base, y_base)) 1434 return 1; 1435 1436 /* The base addresses of the read and write are different expressions. 1437 If they are both symbols and they are not accessed via AND, there is 1438 no conflict. We can bring knowledge of object alignment into play 1439 here. For example, on alpha, "char a, b;" can alias one another, 1440 though "char a; long b;" cannot. */ 1441 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS) 1442 { 1443 if (GET_CODE (x) == AND && GET_CODE (y) == AND) 1444 return 1; 1445 if (GET_CODE (x) == AND 1446 && (GET_CODE (XEXP (x, 1)) != CONST_INT 1447 || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1)))) 1448 return 1; 1449 if (GET_CODE (y) == AND 1450 && (GET_CODE (XEXP (y, 1)) != CONST_INT 1451 || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1)))) 1452 return 1; 1453 /* Differing symbols never alias. */ 1454 return 0; 1455 } 1456 1457 /* If one address is a stack reference there can be no alias: 1458 stack references using different base registers do not alias, 1459 a stack reference can not alias a parameter, and a stack reference 1460 can not alias a global. */ 1461 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode) 1462 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode)) 1463 return 0; 1464 1465 if (! flag_argument_noalias) 1466 return 1; 1467 1468 if (flag_argument_noalias > 1) 1469 return 0; 1470 1471 /* Weak noalias assertion (arguments are distinct, but may match globals). */ 1472 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode); 1473} 1474 1475/* Convert the address X into something we can use. This is done by returning 1476 it unchanged unless it is a value; in the latter case we call cselib to get 1477 a more useful rtx. */ 1478 1479rtx 1480get_addr (x) 1481 rtx x; 1482{ 1483 cselib_val *v; 1484 struct elt_loc_list *l; 1485 1486 if (GET_CODE (x) != VALUE) 1487 return x; 1488 v = CSELIB_VAL_PTR (x); 1489 for (l = v->locs; l; l = l->next) 1490 if (CONSTANT_P (l->loc)) 1491 return l->loc; 1492 for (l = v->locs; l; l = l->next) 1493 if (GET_CODE (l->loc) != REG && GET_CODE (l->loc) != MEM) 1494 return l->loc; 1495 if (v->locs) 1496 return v->locs->loc; 1497 return x; 1498} 1499 1500/* Return the address of the (N_REFS + 1)th memory reference to ADDR 1501 where SIZE is the size in bytes of the memory reference. If ADDR 1502 is not modified by the memory reference then ADDR is returned. */ 1503 1504rtx 1505addr_side_effect_eval (addr, size, n_refs) 1506 rtx addr; 1507 int size; 1508 int n_refs; 1509{ 1510 int offset = 0; 1511 1512 switch (GET_CODE (addr)) 1513 { 1514 case PRE_INC: 1515 offset = (n_refs + 1) * size; 1516 break; 1517 case PRE_DEC: 1518 offset = -(n_refs + 1) * size; 1519 break; 1520 case POST_INC: 1521 offset = n_refs * size; 1522 break; 1523 case POST_DEC: 1524 offset = -n_refs * size; 1525 break; 1526 1527 default: 1528 return addr; 1529 } 1530 1531 if (offset) 1532 addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0), GEN_INT (offset)); 1533 else 1534 addr = XEXP (addr, 0); 1535 1536 return addr; 1537} 1538 1539/* Return nonzero if X and Y (memory addresses) could reference the 1540 same location in memory. C is an offset accumulator. When 1541 C is nonzero, we are testing aliases between X and Y + C. 1542 XSIZE is the size in bytes of the X reference, 1543 similarly YSIZE is the size in bytes for Y. 1544 1545 If XSIZE or YSIZE is zero, we do not know the amount of memory being 1546 referenced (the reference was BLKmode), so make the most pessimistic 1547 assumptions. 1548 1549 If XSIZE or YSIZE is negative, we may access memory outside the object 1550 being referenced as a side effect. This can happen when using AND to 1551 align memory references, as is done on the Alpha. 1552 1553 Nice to notice that varying addresses cannot conflict with fp if no 1554 local variables had their addresses taken, but that's too hard now. */ 1555 1556static int 1557memrefs_conflict_p (xsize, x, ysize, y, c) 1558 rtx x, y; 1559 int xsize, ysize; 1560 HOST_WIDE_INT c; 1561{ 1562 if (GET_CODE (x) == VALUE) 1563 x = get_addr (x); 1564 if (GET_CODE (y) == VALUE) 1565 y = get_addr (y); 1566 if (GET_CODE (x) == HIGH) 1567 x = XEXP (x, 0); 1568 else if (GET_CODE (x) == LO_SUM) 1569 x = XEXP (x, 1); 1570 else 1571 x = canon_rtx (addr_side_effect_eval (x, xsize, 0)); 1572 if (GET_CODE (y) == HIGH) 1573 y = XEXP (y, 0); 1574 else if (GET_CODE (y) == LO_SUM) 1575 y = XEXP (y, 1); 1576 else 1577 y = canon_rtx (addr_side_effect_eval (y, ysize, 0)); 1578 1579 if (rtx_equal_for_memref_p (x, y)) 1580 { 1581 if (xsize <= 0 || ysize <= 0) 1582 return 1; 1583 if (c >= 0 && xsize > c) 1584 return 1; 1585 if (c < 0 && ysize+c > 0) 1586 return 1; 1587 return 0; 1588 } 1589 1590 /* This code used to check for conflicts involving stack references and 1591 globals but the base address alias code now handles these cases. */ 1592 1593 if (GET_CODE (x) == PLUS) 1594 { 1595 /* The fact that X is canonicalized means that this 1596 PLUS rtx is canonicalized. */ 1597 rtx x0 = XEXP (x, 0); 1598 rtx x1 = XEXP (x, 1); 1599 1600 if (GET_CODE (y) == PLUS) 1601 { 1602 /* The fact that Y is canonicalized means that this 1603 PLUS rtx is canonicalized. */ 1604 rtx y0 = XEXP (y, 0); 1605 rtx y1 = XEXP (y, 1); 1606 1607 if (rtx_equal_for_memref_p (x1, y1)) 1608 return memrefs_conflict_p (xsize, x0, ysize, y0, c); 1609 if (rtx_equal_for_memref_p (x0, y0)) 1610 return memrefs_conflict_p (xsize, x1, ysize, y1, c); 1611 if (GET_CODE (x1) == CONST_INT) 1612 { 1613 if (GET_CODE (y1) == CONST_INT) 1614 return memrefs_conflict_p (xsize, x0, ysize, y0, 1615 c - INTVAL (x1) + INTVAL (y1)); 1616 else 1617 return memrefs_conflict_p (xsize, x0, ysize, y, 1618 c - INTVAL (x1)); 1619 } 1620 else if (GET_CODE (y1) == CONST_INT) 1621 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1)); 1622 1623 return 1; 1624 } 1625 else if (GET_CODE (x1) == CONST_INT) 1626 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1)); 1627 } 1628 else if (GET_CODE (y) == PLUS) 1629 { 1630 /* The fact that Y is canonicalized means that this 1631 PLUS rtx is canonicalized. */ 1632 rtx y0 = XEXP (y, 0); 1633 rtx y1 = XEXP (y, 1); 1634 1635 if (GET_CODE (y1) == CONST_INT) 1636 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1)); 1637 else 1638 return 1; 1639 } 1640 1641 if (GET_CODE (x) == GET_CODE (y)) 1642 switch (GET_CODE (x)) 1643 { 1644 case MULT: 1645 { 1646 /* Handle cases where we expect the second operands to be the 1647 same, and check only whether the first operand would conflict 1648 or not. */ 1649 rtx x0, y0; 1650 rtx x1 = canon_rtx (XEXP (x, 1)); 1651 rtx y1 = canon_rtx (XEXP (y, 1)); 1652 if (! rtx_equal_for_memref_p (x1, y1)) 1653 return 1; 1654 x0 = canon_rtx (XEXP (x, 0)); 1655 y0 = canon_rtx (XEXP (y, 0)); 1656 if (rtx_equal_for_memref_p (x0, y0)) 1657 return (xsize == 0 || ysize == 0 1658 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); 1659 1660 /* Can't properly adjust our sizes. */ 1661 if (GET_CODE (x1) != CONST_INT) 1662 return 1; 1663 xsize /= INTVAL (x1); 1664 ysize /= INTVAL (x1); 1665 c /= INTVAL (x1); 1666 return memrefs_conflict_p (xsize, x0, ysize, y0, c); 1667 } 1668 1669 case REG: 1670 /* Are these registers known not to be equal? */ 1671 if (alias_invariant) 1672 { 1673 unsigned int r_x = REGNO (x), r_y = REGNO (y); 1674 rtx i_x, i_y; /* invariant relationships of X and Y */ 1675 1676 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x]; 1677 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y]; 1678 1679 if (i_x == 0 && i_y == 0) 1680 break; 1681 1682 if (! memrefs_conflict_p (xsize, i_x ? i_x : x, 1683 ysize, i_y ? i_y : y, c)) 1684 return 0; 1685 } 1686 break; 1687 1688 default: 1689 break; 1690 } 1691 1692 /* Treat an access through an AND (e.g. a subword access on an Alpha) 1693 as an access with indeterminate size. Assume that references 1694 besides AND are aligned, so if the size of the other reference is 1695 at least as large as the alignment, assume no other overlap. */ 1696 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT) 1697 { 1698 if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1))) 1699 xsize = -1; 1700 return memrefs_conflict_p (xsize, XEXP (x, 0), ysize, y, c); 1701 } 1702 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT) 1703 { 1704 /* ??? If we are indexing far enough into the array/structure, we 1705 may yet be able to determine that we can not overlap. But we 1706 also need to that we are far enough from the end not to overlap 1707 a following reference, so we do nothing with that for now. */ 1708 if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1))) 1709 ysize = -1; 1710 return memrefs_conflict_p (xsize, x, ysize, XEXP (y, 0), c); 1711 } 1712 1713 if (GET_CODE (x) == ADDRESSOF) 1714 { 1715 if (y == frame_pointer_rtx 1716 || GET_CODE (y) == ADDRESSOF) 1717 return xsize <= 0 || ysize <= 0; 1718 } 1719 if (GET_CODE (y) == ADDRESSOF) 1720 { 1721 if (x == frame_pointer_rtx) 1722 return xsize <= 0 || ysize <= 0; 1723 } 1724 1725 if (CONSTANT_P (x)) 1726 { 1727 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT) 1728 { 1729 c += (INTVAL (y) - INTVAL (x)); 1730 return (xsize <= 0 || ysize <= 0 1731 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); 1732 } 1733 1734 if (GET_CODE (x) == CONST) 1735 { 1736 if (GET_CODE (y) == CONST) 1737 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 1738 ysize, canon_rtx (XEXP (y, 0)), c); 1739 else 1740 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 1741 ysize, y, c); 1742 } 1743 if (GET_CODE (y) == CONST) 1744 return memrefs_conflict_p (xsize, x, ysize, 1745 canon_rtx (XEXP (y, 0)), c); 1746 1747 if (CONSTANT_P (y)) 1748 return (xsize <= 0 || ysize <= 0 1749 || (rtx_equal_for_memref_p (x, y) 1750 && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)))); 1751 1752 return 1; 1753 } 1754 return 1; 1755} 1756 1757/* Functions to compute memory dependencies. 1758 1759 Since we process the insns in execution order, we can build tables 1760 to keep track of what registers are fixed (and not aliased), what registers 1761 are varying in known ways, and what registers are varying in unknown 1762 ways. 1763 1764 If both memory references are volatile, then there must always be a 1765 dependence between the two references, since their order can not be 1766 changed. A volatile and non-volatile reference can be interchanged 1767 though. 1768 1769 A MEM_IN_STRUCT reference at a non-AND varying address can never 1770 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We 1771 also must allow AND addresses, because they may generate accesses 1772 outside the object being referenced. This is used to generate 1773 aligned addresses from unaligned addresses, for instance, the alpha 1774 storeqi_unaligned pattern. */ 1775 1776/* Read dependence: X is read after read in MEM takes place. There can 1777 only be a dependence here if both reads are volatile. */ 1778 1779int 1780read_dependence (mem, x) 1781 rtx mem; 1782 rtx x; 1783{ 1784 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem); 1785} 1786 1787/* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and 1788 MEM2 is a reference to a structure at a varying address, or returns 1789 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL 1790 value is returned MEM1 and MEM2 can never alias. VARIES_P is used 1791 to decide whether or not an address may vary; it should return 1792 nonzero whenever variation is possible. 1793 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */ 1794 1795static rtx 1796fixed_scalar_and_varying_struct_p (mem1, mem2, mem1_addr, mem2_addr, varies_p) 1797 rtx mem1, mem2; 1798 rtx mem1_addr, mem2_addr; 1799 int (*varies_p) PARAMS ((rtx, int)); 1800{ 1801 if (! flag_strict_aliasing) 1802 return NULL_RTX; 1803 1804 if (MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2) 1805 && !varies_p (mem1_addr, 1) && varies_p (mem2_addr, 1)) 1806 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a 1807 varying address. */ 1808 return mem1; 1809 1810 if (MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2) 1811 && varies_p (mem1_addr, 1) && !varies_p (mem2_addr, 1)) 1812 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a 1813 varying address. */ 1814 return mem2; 1815 1816 return NULL_RTX; 1817} 1818 1819/* Returns nonzero if something about the mode or address format MEM1 1820 indicates that it might well alias *anything*. */ 1821 1822static int 1823aliases_everything_p (mem) 1824 rtx mem; 1825{ 1826 if (GET_CODE (XEXP (mem, 0)) == AND) 1827 /* If the address is an AND, its very hard to know at what it is 1828 actually pointing. */ 1829 return 1; 1830 1831 return 0; 1832} 1833 1834/* Return true if we can determine that the fields referenced cannot 1835 overlap for any pair of objects. */ 1836 1837static bool 1838nonoverlapping_component_refs_p (x, y) 1839 tree x, y; 1840{ 1841 tree fieldx, fieldy, typex, typey, orig_y; 1842 1843 do 1844 { 1845 /* The comparison has to be done at a common type, since we don't 1846 know how the inheritance hierarchy works. */ 1847 orig_y = y; 1848 do 1849 { 1850 fieldx = TREE_OPERAND (x, 1); 1851 typex = DECL_FIELD_CONTEXT (fieldx); 1852 1853 y = orig_y; 1854 do 1855 { 1856 fieldy = TREE_OPERAND (y, 1); 1857 typey = DECL_FIELD_CONTEXT (fieldy); 1858 1859 if (typex == typey) 1860 goto found; 1861 1862 y = TREE_OPERAND (y, 0); 1863 } 1864 while (y && TREE_CODE (y) == COMPONENT_REF); 1865 1866 x = TREE_OPERAND (x, 0); 1867 } 1868 while (x && TREE_CODE (x) == COMPONENT_REF); 1869 1870 /* Never found a common type. */ 1871 return false; 1872 1873 found: 1874 /* If we're left with accessing different fields of a structure, 1875 then no overlap. */ 1876 if (TREE_CODE (typex) == RECORD_TYPE 1877 && fieldx != fieldy) 1878 return true; 1879 1880 /* The comparison on the current field failed. If we're accessing 1881 a very nested structure, look at the next outer level. */ 1882 x = TREE_OPERAND (x, 0); 1883 y = TREE_OPERAND (y, 0); 1884 } 1885 while (x && y 1886 && TREE_CODE (x) == COMPONENT_REF 1887 && TREE_CODE (y) == COMPONENT_REF); 1888 1889 return false; 1890} 1891 1892/* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */ 1893 1894static tree 1895decl_for_component_ref (x) 1896 tree x; 1897{ 1898 do 1899 { 1900 x = TREE_OPERAND (x, 0); 1901 } 1902 while (x && TREE_CODE (x) == COMPONENT_REF); 1903 1904 return x && DECL_P (x) ? x : NULL_TREE; 1905} 1906 1907/* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the 1908 offset of the field reference. */ 1909 1910static rtx 1911adjust_offset_for_component_ref (x, offset) 1912 tree x; 1913 rtx offset; 1914{ 1915 HOST_WIDE_INT ioffset; 1916 1917 if (! offset) 1918 return NULL_RTX; 1919 1920 ioffset = INTVAL (offset); 1921 do 1922 { 1923 tree field = TREE_OPERAND (x, 1); 1924 1925 if (! host_integerp (DECL_FIELD_OFFSET (field), 1)) 1926 return NULL_RTX; 1927 ioffset += (tree_low_cst (DECL_FIELD_OFFSET (field), 1) 1928 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1) 1929 / BITS_PER_UNIT)); 1930 1931 x = TREE_OPERAND (x, 0); 1932 } 1933 while (x && TREE_CODE (x) == COMPONENT_REF); 1934 1935 return GEN_INT (ioffset); 1936} 1937 1938/* Return nonzero if we can deterimine the exprs corresponding to memrefs 1939 X and Y and they do not overlap. */ 1940 1941static int 1942nonoverlapping_memrefs_p (x, y) 1943 rtx x, y; 1944{ 1945 tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y); 1946 rtx rtlx, rtly; 1947 rtx basex, basey; 1948 rtx moffsetx, moffsety; 1949 HOST_WIDE_INT offsetx = 0, offsety = 0, sizex, sizey, tem; 1950 1951 /* Unless both have exprs, we can't tell anything. */ 1952 if (exprx == 0 || expry == 0) 1953 return 0; 1954 1955 /* If both are field references, we may be able to determine something. */ 1956 if (TREE_CODE (exprx) == COMPONENT_REF 1957 && TREE_CODE (expry) == COMPONENT_REF 1958 && nonoverlapping_component_refs_p (exprx, expry)) 1959 return 1; 1960 1961 /* If the field reference test failed, look at the DECLs involved. */ 1962 moffsetx = MEM_OFFSET (x); 1963 if (TREE_CODE (exprx) == COMPONENT_REF) 1964 { 1965 tree t = decl_for_component_ref (exprx); 1966 if (! t) 1967 return 0; 1968 moffsetx = adjust_offset_for_component_ref (exprx, moffsetx); 1969 exprx = t; 1970 } 1971 else if (TREE_CODE (exprx) == INDIRECT_REF) 1972 { 1973 exprx = TREE_OPERAND (exprx, 0); 1974 if (flag_argument_noalias < 2 1975 || TREE_CODE (exprx) != PARM_DECL) 1976 return 0; 1977 } 1978 1979 moffsety = MEM_OFFSET (y); 1980 if (TREE_CODE (expry) == COMPONENT_REF) 1981 { 1982 tree t = decl_for_component_ref (expry); 1983 if (! t) 1984 return 0; 1985 moffsety = adjust_offset_for_component_ref (expry, moffsety); 1986 expry = t; 1987 } 1988 else if (TREE_CODE (expry) == INDIRECT_REF) 1989 { 1990 expry = TREE_OPERAND (expry, 0); 1991 if (flag_argument_noalias < 2 1992 || TREE_CODE (expry) != PARM_DECL) 1993 return 0; 1994 } 1995 1996 if (! DECL_P (exprx) || ! DECL_P (expry)) 1997 return 0; 1998 1999 rtlx = DECL_RTL (exprx); 2000 rtly = DECL_RTL (expry); 2001 2002 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they 2003 can't overlap unless they are the same because we never reuse that part 2004 of the stack frame used for locals for spilled pseudos. */ 2005 if ((GET_CODE (rtlx) != MEM || GET_CODE (rtly) != MEM) 2006 && ! rtx_equal_p (rtlx, rtly)) 2007 return 1; 2008 2009 /* Get the base and offsets of both decls. If either is a register, we 2010 know both are and are the same, so use that as the base. The only 2011 we can avoid overlap is if we can deduce that they are nonoverlapping 2012 pieces of that decl, which is very rare. */ 2013 basex = GET_CODE (rtlx) == MEM ? XEXP (rtlx, 0) : rtlx; 2014 if (GET_CODE (basex) == PLUS && GET_CODE (XEXP (basex, 1)) == CONST_INT) 2015 offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0); 2016 2017 basey = GET_CODE (rtly) == MEM ? XEXP (rtly, 0) : rtly; 2018 if (GET_CODE (basey) == PLUS && GET_CODE (XEXP (basey, 1)) == CONST_INT) 2019 offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0); 2020 2021 /* If the bases are different, we know they do not overlap if both 2022 are constants or if one is a constant and the other a pointer into the 2023 stack frame. Otherwise a different base means we can't tell if they 2024 overlap or not. */ 2025 if (! rtx_equal_p (basex, basey)) 2026 return ((CONSTANT_P (basex) && CONSTANT_P (basey)) 2027 || (CONSTANT_P (basex) && REG_P (basey) 2028 && REGNO_PTR_FRAME_P (REGNO (basey))) 2029 || (CONSTANT_P (basey) && REG_P (basex) 2030 && REGNO_PTR_FRAME_P (REGNO (basex)))); 2031 2032 sizex = (GET_CODE (rtlx) != MEM ? (int) GET_MODE_SIZE (GET_MODE (rtlx)) 2033 : MEM_SIZE (rtlx) ? INTVAL (MEM_SIZE (rtlx)) 2034 : -1); 2035 sizey = (GET_CODE (rtly) != MEM ? (int) GET_MODE_SIZE (GET_MODE (rtly)) 2036 : MEM_SIZE (rtly) ? INTVAL (MEM_SIZE (rtly)) : 2037 -1); 2038 2039 /* If we have an offset for either memref, it can update the values computed 2040 above. */ 2041 if (moffsetx) 2042 offsetx += INTVAL (moffsetx), sizex -= INTVAL (moffsetx); 2043 if (moffsety) 2044 offsety += INTVAL (moffsety), sizey -= INTVAL (moffsety); 2045 2046 /* If a memref has both a size and an offset, we can use the smaller size. 2047 We can't do this if the offset isn't known because we must view this 2048 memref as being anywhere inside the DECL's MEM. */ 2049 if (MEM_SIZE (x) && moffsetx) 2050 sizex = INTVAL (MEM_SIZE (x)); 2051 if (MEM_SIZE (y) && moffsety) 2052 sizey = INTVAL (MEM_SIZE (y)); 2053 2054 /* Put the values of the memref with the lower offset in X's values. */ 2055 if (offsetx > offsety) 2056 { 2057 tem = offsetx, offsetx = offsety, offsety = tem; 2058 tem = sizex, sizex = sizey, sizey = tem; 2059 } 2060 2061 /* If we don't know the size of the lower-offset value, we can't tell 2062 if they conflict. Otherwise, we do the test. */ 2063 return sizex >= 0 && offsety >= offsetx + sizex; 2064} 2065 2066/* True dependence: X is read after store in MEM takes place. */ 2067 2068int 2069true_dependence (mem, mem_mode, x, varies) 2070 rtx mem; 2071 enum machine_mode mem_mode; 2072 rtx x; 2073 int (*varies) PARAMS ((rtx, int)); 2074{ 2075 rtx x_addr, mem_addr; 2076 rtx base; 2077 2078 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 2079 return 1; 2080 2081 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 2082 This is used in epilogue deallocation functions. */ 2083 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 2084 return 1; 2085 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 2086 return 1; 2087 2088 if (DIFFERENT_ALIAS_SETS_P (x, mem)) 2089 return 0; 2090 2091 /* Unchanging memory can't conflict with non-unchanging memory. 2092 A non-unchanging read can conflict with a non-unchanging write. 2093 An unchanging read can conflict with an unchanging write since 2094 there may be a single store to this address to initialize it. 2095 Note that an unchanging store can conflict with a non-unchanging read 2096 since we have to make conservative assumptions when we have a 2097 record with readonly fields and we are copying the whole thing. 2098 Just fall through to the code below to resolve potential conflicts. 2099 This won't handle all cases optimally, but the possible performance 2100 loss should be negligible. */ 2101 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem)) 2102 return 0; 2103 2104 if (nonoverlapping_memrefs_p (mem, x)) 2105 return 0; 2106 2107 if (mem_mode == VOIDmode) 2108 mem_mode = GET_MODE (mem); 2109 2110 x_addr = get_addr (XEXP (x, 0)); 2111 mem_addr = get_addr (XEXP (mem, 0)); 2112 2113 base = find_base_term (x_addr); 2114 if (base && (GET_CODE (base) == LABEL_REF 2115 || (GET_CODE (base) == SYMBOL_REF 2116 && CONSTANT_POOL_ADDRESS_P (base)))) 2117 return 0; 2118 2119 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode)) 2120 return 0; 2121 2122 x_addr = canon_rtx (x_addr); 2123 mem_addr = canon_rtx (mem_addr); 2124 2125 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr, 2126 SIZE_FOR_MODE (x), x_addr, 0)) 2127 return 0; 2128 2129 if (aliases_everything_p (x)) 2130 return 1; 2131 2132 /* We cannot use aliases_everything_p to test MEM, since we must look 2133 at MEM_MODE, rather than GET_MODE (MEM). */ 2134 if (mem_mode == QImode || GET_CODE (mem_addr) == AND) 2135 return 1; 2136 2137 /* In true_dependence we also allow BLKmode to alias anything. Why 2138 don't we do this in anti_dependence and output_dependence? */ 2139 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode) 2140 return 1; 2141 2142 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, 2143 varies); 2144} 2145 2146/* Canonical true dependence: X is read after store in MEM takes place. 2147 Variant of true_dependence which assumes MEM has already been 2148 canonicalized (hence we no longer do that here). 2149 The mem_addr argument has been added, since true_dependence computed 2150 this value prior to canonicalizing. */ 2151 2152int 2153canon_true_dependence (mem, mem_mode, mem_addr, x, varies) 2154 rtx mem, mem_addr, x; 2155 enum machine_mode mem_mode; 2156 int (*varies) PARAMS ((rtx, int)); 2157{ 2158 rtx x_addr; 2159 2160 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 2161 return 1; 2162 2163 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 2164 This is used in epilogue deallocation functions. */ 2165 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 2166 return 1; 2167 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 2168 return 1; 2169 2170 if (DIFFERENT_ALIAS_SETS_P (x, mem)) 2171 return 0; 2172 2173 /* If X is an unchanging read, then it can't possibly conflict with any 2174 non-unchanging store. It may conflict with an unchanging write though, 2175 because there may be a single store to this address to initialize it. 2176 Just fall through to the code below to resolve the case where we have 2177 both an unchanging read and an unchanging write. This won't handle all 2178 cases optimally, but the possible performance loss should be 2179 negligible. */ 2180 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem)) 2181 return 0; 2182 2183 if (nonoverlapping_memrefs_p (x, mem)) 2184 return 0; 2185 2186 x_addr = get_addr (XEXP (x, 0)); 2187 2188 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode)) 2189 return 0; 2190 2191 x_addr = canon_rtx (x_addr); 2192 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr, 2193 SIZE_FOR_MODE (x), x_addr, 0)) 2194 return 0; 2195 2196 if (aliases_everything_p (x)) 2197 return 1; 2198 2199 /* We cannot use aliases_everything_p to test MEM, since we must look 2200 at MEM_MODE, rather than GET_MODE (MEM). */ 2201 if (mem_mode == QImode || GET_CODE (mem_addr) == AND) 2202 return 1; 2203 2204 /* In true_dependence we also allow BLKmode to alias anything. Why 2205 don't we do this in anti_dependence and output_dependence? */ 2206 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode) 2207 return 1; 2208 2209 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, 2210 varies); 2211} 2212 2213/* Returns nonzero if a write to X might alias a previous read from 2214 (or, if WRITEP is nonzero, a write to) MEM. */ 2215 2216static int 2217write_dependence_p (mem, x, writep) 2218 rtx mem; 2219 rtx x; 2220 int writep; 2221{ 2222 rtx x_addr, mem_addr; 2223 rtx fixed_scalar; 2224 rtx base; 2225 2226 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 2227 return 1; 2228 2229 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 2230 This is used in epilogue deallocation functions. */ 2231 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 2232 return 1; 2233 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 2234 return 1; 2235 2236 if (DIFFERENT_ALIAS_SETS_P (x, mem)) 2237 return 0; 2238 2239 /* Unchanging memory can't conflict with non-unchanging memory. */ 2240 if (RTX_UNCHANGING_P (x) != RTX_UNCHANGING_P (mem)) 2241 return 0; 2242 2243 /* If MEM is an unchanging read, then it can't possibly conflict with 2244 the store to X, because there is at most one store to MEM, and it must 2245 have occurred somewhere before MEM. */ 2246 if (! writep && RTX_UNCHANGING_P (mem)) 2247 return 0; 2248 2249 if (nonoverlapping_memrefs_p (x, mem)) 2250 return 0; 2251 2252 x_addr = get_addr (XEXP (x, 0)); 2253 mem_addr = get_addr (XEXP (mem, 0)); 2254 2255 if (! writep) 2256 { 2257 base = find_base_term (mem_addr); 2258 if (base && (GET_CODE (base) == LABEL_REF 2259 || (GET_CODE (base) == SYMBOL_REF 2260 && CONSTANT_POOL_ADDRESS_P (base)))) 2261 return 0; 2262 } 2263 2264 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), 2265 GET_MODE (mem))) 2266 return 0; 2267 2268 x_addr = canon_rtx (x_addr); 2269 mem_addr = canon_rtx (mem_addr); 2270 2271 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr, 2272 SIZE_FOR_MODE (x), x_addr, 0)) 2273 return 0; 2274 2275 fixed_scalar 2276 = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, 2277 rtx_addr_varies_p); 2278 2279 return (!(fixed_scalar == mem && !aliases_everything_p (x)) 2280 && !(fixed_scalar == x && !aliases_everything_p (mem))); 2281} 2282 2283/* Anti dependence: X is written after read in MEM takes place. */ 2284 2285int 2286anti_dependence (mem, x) 2287 rtx mem; 2288 rtx x; 2289{ 2290 return write_dependence_p (mem, x, /*writep=*/0); 2291} 2292 2293/* Output dependence: X is written after store in MEM takes place. */ 2294 2295int 2296output_dependence (mem, x) 2297 rtx mem; 2298 rtx x; 2299{ 2300 return write_dependence_p (mem, x, /*writep=*/1); 2301} 2302 2303/* A subroutine of nonlocal_mentioned_p, returns 1 if *LOC mentions 2304 something which is not local to the function and is not constant. */ 2305 2306static int 2307nonlocal_mentioned_p_1 (loc, data) 2308 rtx *loc; 2309 void *data ATTRIBUTE_UNUSED; 2310{ 2311 rtx x = *loc; 2312 rtx base; 2313 int regno; 2314 2315 if (! x) 2316 return 0; 2317 2318 switch (GET_CODE (x)) 2319 { 2320 case SUBREG: 2321 if (GET_CODE (SUBREG_REG (x)) == REG) 2322 { 2323 /* Global registers are not local. */ 2324 if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER 2325 && global_regs[subreg_regno (x)]) 2326 return 1; 2327 return 0; 2328 } 2329 break; 2330 2331 case REG: 2332 regno = REGNO (x); 2333 /* Global registers are not local. */ 2334 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]) 2335 return 1; 2336 return 0; 2337 2338 case SCRATCH: 2339 case PC: 2340 case CC0: 2341 case CONST_INT: 2342 case CONST_DOUBLE: 2343 case CONST_VECTOR: 2344 case CONST: 2345 case LABEL_REF: 2346 return 0; 2347 2348 case SYMBOL_REF: 2349 /* Constants in the function's constants pool are constant. */ 2350 if (CONSTANT_POOL_ADDRESS_P (x)) 2351 return 0; 2352 return 1; 2353 2354 case CALL: 2355 /* Non-constant calls and recursion are not local. */ 2356 return 1; 2357 2358 case MEM: 2359 /* Be overly conservative and consider any volatile memory 2360 reference as not local. */ 2361 if (MEM_VOLATILE_P (x)) 2362 return 1; 2363 base = find_base_term (XEXP (x, 0)); 2364 if (base) 2365 { 2366 /* A Pmode ADDRESS could be a reference via the structure value 2367 address or static chain. Such memory references are nonlocal. 2368 2369 Thus, we have to examine the contents of the ADDRESS to find 2370 out if this is a local reference or not. */ 2371 if (GET_CODE (base) == ADDRESS 2372 && GET_MODE (base) == Pmode 2373 && (XEXP (base, 0) == stack_pointer_rtx 2374 || XEXP (base, 0) == arg_pointer_rtx 2375#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 2376 || XEXP (base, 0) == hard_frame_pointer_rtx 2377#endif 2378 || XEXP (base, 0) == frame_pointer_rtx)) 2379 return 0; 2380 /* Constants in the function's constant pool are constant. */ 2381 if (GET_CODE (base) == SYMBOL_REF && CONSTANT_POOL_ADDRESS_P (base)) 2382 return 0; 2383 } 2384 return 1; 2385 2386 case UNSPEC_VOLATILE: 2387 case ASM_INPUT: 2388 return 1; 2389 2390 case ASM_OPERANDS: 2391 if (MEM_VOLATILE_P (x)) 2392 return 1; 2393 2394 /* FALLTHROUGH */ 2395 2396 default: 2397 break; 2398 } 2399 2400 return 0; 2401} 2402 2403/* Returns nonzero if X might mention something which is not 2404 local to the function and is not constant. */ 2405 2406static int 2407nonlocal_mentioned_p (x) 2408 rtx x; 2409{ 2410 2411 if (INSN_P (x)) 2412 { 2413 if (GET_CODE (x) == CALL_INSN) 2414 { 2415 if (! CONST_OR_PURE_CALL_P (x)) 2416 return 1; 2417 x = CALL_INSN_FUNCTION_USAGE (x); 2418 if (x == 0) 2419 return 0; 2420 } 2421 else 2422 x = PATTERN (x); 2423 } 2424 2425 return for_each_rtx (&x, nonlocal_mentioned_p_1, NULL); 2426} 2427 2428/* A subroutine of nonlocal_referenced_p, returns 1 if *LOC references 2429 something which is not local to the function and is not constant. */ 2430 2431static int 2432nonlocal_referenced_p_1 (loc, data) 2433 rtx *loc; 2434 void *data ATTRIBUTE_UNUSED; 2435{ 2436 rtx x = *loc; 2437 2438 if (! x) 2439 return 0; 2440 2441 switch (GET_CODE (x)) 2442 { 2443 case MEM: 2444 case REG: 2445 case SYMBOL_REF: 2446 case SUBREG: 2447 return nonlocal_mentioned_p (x); 2448 2449 case CALL: 2450 /* Non-constant calls and recursion are not local. */ 2451 return 1; 2452 2453 case SET: 2454 if (nonlocal_mentioned_p (SET_SRC (x))) 2455 return 1; 2456 2457 if (GET_CODE (SET_DEST (x)) == MEM) 2458 return nonlocal_mentioned_p (XEXP (SET_DEST (x), 0)); 2459 2460 /* If the destination is anything other than a CC0, PC, 2461 MEM, REG, or a SUBREG of a REG that occupies all of 2462 the REG, then X references nonlocal memory if it is 2463 mentioned in the destination. */ 2464 if (GET_CODE (SET_DEST (x)) != CC0 2465 && GET_CODE (SET_DEST (x)) != PC 2466 && GET_CODE (SET_DEST (x)) != REG 2467 && ! (GET_CODE (SET_DEST (x)) == SUBREG 2468 && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG 2469 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (x)))) 2470 + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD) 2471 == ((GET_MODE_SIZE (GET_MODE (SET_DEST (x))) 2472 + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)))) 2473 return nonlocal_mentioned_p (SET_DEST (x)); 2474 return 0; 2475 2476 case CLOBBER: 2477 if (GET_CODE (XEXP (x, 0)) == MEM) 2478 return nonlocal_mentioned_p (XEXP (XEXP (x, 0), 0)); 2479 return 0; 2480 2481 case USE: 2482 return nonlocal_mentioned_p (XEXP (x, 0)); 2483 2484 case ASM_INPUT: 2485 case UNSPEC_VOLATILE: 2486 return 1; 2487 2488 case ASM_OPERANDS: 2489 if (MEM_VOLATILE_P (x)) 2490 return 1; 2491 2492 /* FALLTHROUGH */ 2493 2494 default: 2495 break; 2496 } 2497 2498 return 0; 2499} 2500 2501/* Returns nonzero if X might reference something which is not 2502 local to the function and is not constant. */ 2503 2504static int 2505nonlocal_referenced_p (x) 2506 rtx x; 2507{ 2508 2509 if (INSN_P (x)) 2510 { 2511 if (GET_CODE (x) == CALL_INSN) 2512 { 2513 if (! CONST_OR_PURE_CALL_P (x)) 2514 return 1; 2515 x = CALL_INSN_FUNCTION_USAGE (x); 2516 if (x == 0) 2517 return 0; 2518 } 2519 else 2520 x = PATTERN (x); 2521 } 2522 2523 return for_each_rtx (&x, nonlocal_referenced_p_1, NULL); 2524} 2525 2526/* A subroutine of nonlocal_set_p, returns 1 if *LOC sets 2527 something which is not local to the function and is not constant. */ 2528 2529static int 2530nonlocal_set_p_1 (loc, data) 2531 rtx *loc; 2532 void *data ATTRIBUTE_UNUSED; 2533{ 2534 rtx x = *loc; 2535 2536 if (! x) 2537 return 0; 2538 2539 switch (GET_CODE (x)) 2540 { 2541 case CALL: 2542 /* Non-constant calls and recursion are not local. */ 2543 return 1; 2544 2545 case PRE_INC: 2546 case PRE_DEC: 2547 case POST_INC: 2548 case POST_DEC: 2549 case PRE_MODIFY: 2550 case POST_MODIFY: 2551 return nonlocal_mentioned_p (XEXP (x, 0)); 2552 2553 case SET: 2554 if (nonlocal_mentioned_p (SET_DEST (x))) 2555 return 1; 2556 return nonlocal_set_p (SET_SRC (x)); 2557 2558 case CLOBBER: 2559 return nonlocal_mentioned_p (XEXP (x, 0)); 2560 2561 case USE: 2562 return 0; 2563 2564 case ASM_INPUT: 2565 case UNSPEC_VOLATILE: 2566 return 1; 2567 2568 case ASM_OPERANDS: 2569 if (MEM_VOLATILE_P (x)) 2570 return 1; 2571 2572 /* FALLTHROUGH */ 2573 2574 default: 2575 break; 2576 } 2577 2578 return 0; 2579} 2580 2581/* Returns nonzero if X might set something which is not 2582 local to the function and is not constant. */ 2583 2584static int 2585nonlocal_set_p (x) 2586 rtx x; 2587{ 2588 2589 if (INSN_P (x)) 2590 { 2591 if (GET_CODE (x) == CALL_INSN) 2592 { 2593 if (! CONST_OR_PURE_CALL_P (x)) 2594 return 1; 2595 x = CALL_INSN_FUNCTION_USAGE (x); 2596 if (x == 0) 2597 return 0; 2598 } 2599 else 2600 x = PATTERN (x); 2601 } 2602 2603 return for_each_rtx (&x, nonlocal_set_p_1, NULL); 2604} 2605 2606/* Mark the function if it is constant. */ 2607 2608void 2609mark_constant_function () 2610{ 2611 rtx insn; 2612 int nonlocal_memory_referenced; 2613 2614 if (TREE_READONLY (current_function_decl) 2615 || DECL_IS_PURE (current_function_decl) 2616 || TREE_THIS_VOLATILE (current_function_decl) 2617 || TYPE_MODE (TREE_TYPE (current_function_decl)) == VOIDmode 2618 || current_function_has_nonlocal_goto 2619 || !(*targetm.binds_local_p) (current_function_decl)) 2620 return; 2621 2622 /* A loop might not return which counts as a side effect. */ 2623 if (mark_dfs_back_edges ()) 2624 return; 2625 2626 nonlocal_memory_referenced = 0; 2627 2628 init_alias_analysis (); 2629 2630 /* Determine if this is a constant or pure function. */ 2631 2632 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 2633 { 2634 if (! INSN_P (insn)) 2635 continue; 2636 2637 if (nonlocal_set_p (insn) || global_reg_mentioned_p (insn) 2638 || volatile_refs_p (PATTERN (insn))) 2639 break; 2640 2641 if (! nonlocal_memory_referenced) 2642 nonlocal_memory_referenced = nonlocal_referenced_p (insn); 2643 } 2644 2645 end_alias_analysis (); 2646 2647 /* Mark the function. */ 2648 2649 if (insn) 2650 ; 2651 else if (nonlocal_memory_referenced) 2652 DECL_IS_PURE (current_function_decl) = 1; 2653 else 2654 TREE_READONLY (current_function_decl) = 1; 2655} 2656 2657 2658void 2659init_alias_once () 2660{ 2661 int i; 2662 2663#ifndef OUTGOING_REGNO 2664#define OUTGOING_REGNO(N) N 2665#endif 2666 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 2667 /* Check whether this register can hold an incoming pointer 2668 argument. FUNCTION_ARG_REGNO_P tests outgoing register 2669 numbers, so translate if necessary due to register windows. */ 2670 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i)) 2671 && HARD_REGNO_MODE_OK (i, Pmode)) 2672 static_reg_base_value[i] 2673 = gen_rtx_ADDRESS (VOIDmode, gen_rtx_REG (Pmode, i)); 2674 2675 static_reg_base_value[STACK_POINTER_REGNUM] 2676 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx); 2677 static_reg_base_value[ARG_POINTER_REGNUM] 2678 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx); 2679 static_reg_base_value[FRAME_POINTER_REGNUM] 2680 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx); 2681#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 2682 static_reg_base_value[HARD_FRAME_POINTER_REGNUM] 2683 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx); 2684#endif 2685 2686 alias_sets = splay_tree_new (splay_tree_compare_ints, 0, 0); 2687} 2688 2689/* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE 2690 array. */ 2691 2692void 2693init_alias_analysis () 2694{ 2695 int maxreg = max_reg_num (); 2696 int changed, pass; 2697 int i; 2698 unsigned int ui; 2699 rtx insn; 2700 2701 reg_known_value_size = maxreg; 2702 2703 reg_known_value 2704 = (rtx *) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (rtx)) 2705 - FIRST_PSEUDO_REGISTER; 2706 reg_known_equiv_p 2707 = (char*) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (char)) 2708 - FIRST_PSEUDO_REGISTER; 2709 2710 /* Overallocate reg_base_value to allow some growth during loop 2711 optimization. Loop unrolling can create a large number of 2712 registers. */ 2713 reg_base_value_size = maxreg * 2; 2714 reg_base_value = (rtx *) ggc_alloc_cleared (reg_base_value_size 2715 * sizeof (rtx)); 2716 2717 new_reg_base_value = (rtx *) xmalloc (reg_base_value_size * sizeof (rtx)); 2718 reg_seen = (char *) xmalloc (reg_base_value_size); 2719 if (! reload_completed && flag_unroll_loops) 2720 { 2721 /* ??? Why are we realloc'ing if we're just going to zero it? */ 2722 alias_invariant = (rtx *)xrealloc (alias_invariant, 2723 reg_base_value_size * sizeof (rtx)); 2724 memset ((char *)alias_invariant, 0, reg_base_value_size * sizeof (rtx)); 2725 } 2726 2727 /* The basic idea is that each pass through this loop will use the 2728 "constant" information from the previous pass to propagate alias 2729 information through another level of assignments. 2730 2731 This could get expensive if the assignment chains are long. Maybe 2732 we should throttle the number of iterations, possibly based on 2733 the optimization level or flag_expensive_optimizations. 2734 2735 We could propagate more information in the first pass by making use 2736 of REG_N_SETS to determine immediately that the alias information 2737 for a pseudo is "constant". 2738 2739 A program with an uninitialized variable can cause an infinite loop 2740 here. Instead of doing a full dataflow analysis to detect such problems 2741 we just cap the number of iterations for the loop. 2742 2743 The state of the arrays for the set chain in question does not matter 2744 since the program has undefined behavior. */ 2745 2746 pass = 0; 2747 do 2748 { 2749 /* Assume nothing will change this iteration of the loop. */ 2750 changed = 0; 2751 2752 /* We want to assign the same IDs each iteration of this loop, so 2753 start counting from zero each iteration of the loop. */ 2754 unique_id = 0; 2755 2756 /* We're at the start of the function each iteration through the 2757 loop, so we're copying arguments. */ 2758 copying_arguments = true; 2759 2760 /* Wipe the potential alias information clean for this pass. */ 2761 memset ((char *) new_reg_base_value, 0, reg_base_value_size * sizeof (rtx)); 2762 2763 /* Wipe the reg_seen array clean. */ 2764 memset ((char *) reg_seen, 0, reg_base_value_size); 2765 2766 /* Mark all hard registers which may contain an address. 2767 The stack, frame and argument pointers may contain an address. 2768 An argument register which can hold a Pmode value may contain 2769 an address even if it is not in BASE_REGS. 2770 2771 The address expression is VOIDmode for an argument and 2772 Pmode for other registers. */ 2773 2774 memcpy (new_reg_base_value, static_reg_base_value, 2775 FIRST_PSEUDO_REGISTER * sizeof (rtx)); 2776 2777 /* Walk the insns adding values to the new_reg_base_value array. */ 2778 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 2779 { 2780 if (INSN_P (insn)) 2781 { 2782 rtx note, set; 2783 2784#if defined (HAVE_prologue) || defined (HAVE_epilogue) 2785 /* The prologue/epilogue insns are not threaded onto the 2786 insn chain until after reload has completed. Thus, 2787 there is no sense wasting time checking if INSN is in 2788 the prologue/epilogue until after reload has completed. */ 2789 if (reload_completed 2790 && prologue_epilogue_contains (insn)) 2791 continue; 2792#endif 2793 2794 /* If this insn has a noalias note, process it, Otherwise, 2795 scan for sets. A simple set will have no side effects 2796 which could change the base value of any other register. */ 2797 2798 if (GET_CODE (PATTERN (insn)) == SET 2799 && REG_NOTES (insn) != 0 2800 && find_reg_note (insn, REG_NOALIAS, NULL_RTX)) 2801 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL); 2802 else 2803 note_stores (PATTERN (insn), record_set, NULL); 2804 2805 set = single_set (insn); 2806 2807 if (set != 0 2808 && GET_CODE (SET_DEST (set)) == REG 2809 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER) 2810 { 2811 unsigned int regno = REGNO (SET_DEST (set)); 2812 rtx src = SET_SRC (set); 2813 2814 if (REG_NOTES (insn) != 0 2815 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0 2816 && REG_N_SETS (regno) == 1) 2817 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0) 2818 && GET_CODE (XEXP (note, 0)) != EXPR_LIST 2819 && ! rtx_varies_p (XEXP (note, 0), 1) 2820 && ! reg_overlap_mentioned_p (SET_DEST (set), XEXP (note, 0))) 2821 { 2822 reg_known_value[regno] = XEXP (note, 0); 2823 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV; 2824 } 2825 else if (REG_N_SETS (regno) == 1 2826 && GET_CODE (src) == PLUS 2827 && GET_CODE (XEXP (src, 0)) == REG 2828 && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER 2829 && (reg_known_value[REGNO (XEXP (src, 0))]) 2830 && GET_CODE (XEXP (src, 1)) == CONST_INT) 2831 { 2832 rtx op0 = XEXP (src, 0); 2833 op0 = reg_known_value[REGNO (op0)]; 2834 reg_known_value[regno] 2835 = plus_constant (op0, INTVAL (XEXP (src, 1))); 2836 reg_known_equiv_p[regno] = 0; 2837 } 2838 else if (REG_N_SETS (regno) == 1 2839 && ! rtx_varies_p (src, 1)) 2840 { 2841 reg_known_value[regno] = src; 2842 reg_known_equiv_p[regno] = 0; 2843 } 2844 } 2845 } 2846 else if (GET_CODE (insn) == NOTE 2847 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG) 2848 copying_arguments = false; 2849 } 2850 2851 /* Now propagate values from new_reg_base_value to reg_base_value. */ 2852 for (ui = 0; ui < reg_base_value_size; ui++) 2853 { 2854 if (new_reg_base_value[ui] 2855 && new_reg_base_value[ui] != reg_base_value[ui] 2856 && ! rtx_equal_p (new_reg_base_value[ui], reg_base_value[ui])) 2857 { 2858 reg_base_value[ui] = new_reg_base_value[ui]; 2859 changed = 1; 2860 } 2861 } 2862 } 2863 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES); 2864 2865 /* Fill in the remaining entries. */ 2866 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++) 2867 if (reg_known_value[i] == 0) 2868 reg_known_value[i] = regno_reg_rtx[i]; 2869 2870 /* Simplify the reg_base_value array so that no register refers to 2871 another register, except to special registers indirectly through 2872 ADDRESS expressions. 2873 2874 In theory this loop can take as long as O(registers^2), but unless 2875 there are very long dependency chains it will run in close to linear 2876 time. 2877 2878 This loop may not be needed any longer now that the main loop does 2879 a better job at propagating alias information. */ 2880 pass = 0; 2881 do 2882 { 2883 changed = 0; 2884 pass++; 2885 for (ui = 0; ui < reg_base_value_size; ui++) 2886 { 2887 rtx base = reg_base_value[ui]; 2888 if (base && GET_CODE (base) == REG) 2889 { 2890 unsigned int base_regno = REGNO (base); 2891 if (base_regno == ui) /* register set from itself */ 2892 reg_base_value[ui] = 0; 2893 else 2894 reg_base_value[ui] = reg_base_value[base_regno]; 2895 changed = 1; 2896 } 2897 } 2898 } 2899 while (changed && pass < MAX_ALIAS_LOOP_PASSES); 2900 2901 /* Clean up. */ 2902 free (new_reg_base_value); 2903 new_reg_base_value = 0; 2904 free (reg_seen); 2905 reg_seen = 0; 2906} 2907 2908void 2909end_alias_analysis () 2910{ 2911 free (reg_known_value + FIRST_PSEUDO_REGISTER); 2912 reg_known_value = 0; 2913 reg_known_value_size = 0; 2914 free (reg_known_equiv_p + FIRST_PSEUDO_REGISTER); 2915 reg_known_equiv_p = 0; 2916 reg_base_value = 0; 2917 reg_base_value_size = 0; 2918 if (alias_invariant) 2919 { 2920 free (alias_invariant); 2921 alias_invariant = 0; 2922 } 2923} 2924 2925#include "gt-alias.h" 2926