1 /* Alias analysis for GNU C 2 Copyright (C) 1997-2022 Free Software Foundation, Inc. 3 Contributed by John Carr (jfc (at) mit.edu). 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "backend.h" 25 #include "target.h" 26 #include "rtl.h" 27 #include "tree.h" 28 #include "gimple.h" 29 #include "df.h" 30 #include "memmodel.h" 31 #include "tm_p.h" 32 #include "gimple-ssa.h" 33 #include "emit-rtl.h" 34 #include "alias.h" 35 #include "fold-const.h" 36 #include "varasm.h" 37 #include "cselib.h" 38 #include "langhooks.h" 39 #include "cfganal.h" 40 #include "rtl-iter.h" 41 #include "cgraph.h" 42 #include "ipa-utils.h" 43 44 /* The aliasing API provided here solves related but different problems: 45 46 Say there exists (in c) 47 48 struct X { 49 struct Y y1; 50 struct Z z2; 51 } x1, *px1, *px2; 52 53 struct Y y2, *py; 54 struct Z z2, *pz; 55 56 57 py = &x1.y1; 58 px2 = &x1; 59 60 Consider the four questions: 61 62 Can a store to x1 interfere with px2->y1? 63 Can a store to x1 interfere with px2->z2? 64 Can a store to x1 change the value pointed to by with py? 65 Can a store to x1 change the value pointed to by with pz? 66 67 The answer to these questions can be yes, yes, yes, and maybe. 68 69 The first two questions can be answered with a simple examination 70 of the type system. If structure X contains a field of type Y then 71 a store through a pointer to an X can overwrite any field that is 72 contained (recursively) in an X (unless we know that px1 != px2). 73 74 The last two questions can be solved in the same way as the first 75 two questions but this is too conservative. The observation is 76 that in some cases we can know which (if any) fields are addressed 77 and if those addresses are used in bad ways. This analysis may be 78 language specific. In C, arbitrary operations may be applied to 79 pointers. However, there is some indication that this may be too 80 conservative for some C++ types. 81 82 The pass ipa-type-escape does this analysis for the types whose 83 instances do not escape across the compilation boundary. 84 85 Historically in GCC, these two problems were combined and a single 86 data structure that was used to represent the solution to these 87 problems. We now have two similar but different data structures, 88 The data structure to solve the last two questions is similar to 89 the first, but does not contain the fields whose address are never 90 taken. For types that do escape the compilation unit, the data 91 structures will have identical information. 92 */ 93 94 /* The alias sets assigned to MEMs assist the back-end in determining 95 which MEMs can alias which other MEMs. In general, two MEMs in 96 different alias sets cannot alias each other, with one important 97 exception. Consider something like: 98 99 struct S { int i; double d; }; 100 101 a store to an `S' can alias something of either type `int' or type 102 `double'. (However, a store to an `int' cannot alias a `double' 103 and vice versa.) We indicate this via a tree structure that looks 104 like: 105 struct S 106 / \ 107 / \ 108 |/_ _\| 109 int double 110 111 (The arrows are directed and point downwards.) 112 In this situation we say the alias set for `struct S' is the 113 `superset' and that those for `int' and `double' are `subsets'. 114 115 To see whether two alias sets can point to the same memory, we must 116 see if either alias set is a subset of the other. We need not trace 117 past immediate descendants, however, since we propagate all 118 grandchildren up one level. 119 120 Alias set zero is implicitly a superset of all other alias sets. 121 However, this is no actual entry for alias set zero. It is an 122 error to attempt to explicitly construct a subset of zero. */ 123 124 struct alias_set_hash : int_hash <int, INT_MIN, INT_MIN + 1> {}; 125 126 struct GTY(()) alias_set_entry { 127 /* The alias set number, as stored in MEM_ALIAS_SET. */ 128 alias_set_type alias_set; 129 130 /* Nonzero if would have a child of zero: this effectively makes this 131 alias set the same as alias set zero. */ 132 bool has_zero_child; 133 /* Nonzero if alias set corresponds to pointer type itself (i.e. not to 134 aggregate contaiing pointer. 135 This is used for a special case where we need an universal pointer type 136 compatible with all other pointer types. */ 137 bool is_pointer; 138 /* Nonzero if is_pointer or if one of childs have has_pointer set. */ 139 bool has_pointer; 140 141 /* The children of the alias set. These are not just the immediate 142 children, but, in fact, all descendants. So, if we have: 143 144 struct T { struct S s; float f; } 145 146 continuing our example above, the children here will be all of 147 `int', `double', `float', and `struct S'. */ 148 hash_map<alias_set_hash, int> *children; 149 }; 150 151 static int rtx_equal_for_memref_p (const_rtx, const_rtx); 152 static void record_set (rtx, const_rtx, void *); 153 static int base_alias_check (rtx, rtx, rtx, rtx, machine_mode, 154 machine_mode); 155 static rtx find_base_value (rtx); 156 static int mems_in_disjoint_alias_sets_p (const_rtx, const_rtx); 157 static alias_set_entry *get_alias_set_entry (alias_set_type); 158 static tree decl_for_component_ref (tree); 159 static int write_dependence_p (const_rtx, 160 const_rtx, machine_mode, rtx, 161 bool, bool, bool); 162 static int compare_base_symbol_refs (const_rtx, const_rtx, 163 HOST_WIDE_INT * = NULL); 164 165 static void memory_modified_1 (rtx, const_rtx, void *); 166 167 /* Query statistics for the different low-level disambiguators. 168 A high-level query may trigger multiple of them. */ 169 170 static struct { 171 unsigned long long num_alias_zero; 172 unsigned long long num_same_alias_set; 173 unsigned long long num_same_objects; 174 unsigned long long num_volatile; 175 unsigned long long num_dag; 176 unsigned long long num_universal; 177 unsigned long long num_disambiguated; 178 } alias_stats; 179 180 181 /* Set up all info needed to perform alias analysis on memory references. */ 182 183 /* Returns the size in bytes of the mode of X. */ 184 #define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X))) 185 186 /* Cap the number of passes we make over the insns propagating alias 187 information through set chains. 188 ??? 10 is a completely arbitrary choice. This should be based on the 189 maximum loop depth in the CFG, but we do not have this information 190 available (even if current_loops _is_ available). */ 191 #define MAX_ALIAS_LOOP_PASSES 10 192 193 /* reg_base_value[N] gives an address to which register N is related. 194 If all sets after the first add or subtract to the current value 195 or otherwise modify it so it does not point to a different top level 196 object, reg_base_value[N] is equal to the address part of the source 197 of the first set. 198 199 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS 200 expressions represent three types of base: 201 202 1. incoming arguments. There is just one ADDRESS to represent all 203 arguments, since we do not know at this level whether accesses 204 based on different arguments can alias. The ADDRESS has id 0. 205 206 2. stack_pointer_rtx, frame_pointer_rtx, hard_frame_pointer_rtx 207 (if distinct from frame_pointer_rtx) and arg_pointer_rtx. 208 Each of these rtxes has a separate ADDRESS associated with it, 209 each with a negative id. 210 211 GCC is (and is required to be) precise in which register it 212 chooses to access a particular region of stack. We can therefore 213 assume that accesses based on one of these rtxes do not alias 214 accesses based on another of these rtxes. 215 216 3. bases that are derived from malloc()ed memory (REG_NOALIAS). 217 Each such piece of memory has a separate ADDRESS associated 218 with it, each with an id greater than 0. 219 220 Accesses based on one ADDRESS do not alias accesses based on other 221 ADDRESSes. Accesses based on ADDRESSes in groups (2) and (3) do not 222 alias globals either; the ADDRESSes have Pmode to indicate this. 223 The ADDRESS in group (1) _may_ alias globals; it has VOIDmode to 224 indicate this. */ 225 226 static GTY(()) vec<rtx, va_gc> *reg_base_value; 227 static rtx *new_reg_base_value; 228 229 /* The single VOIDmode ADDRESS that represents all argument bases. 230 It has id 0. */ 231 static GTY(()) rtx arg_base_value; 232 233 /* Used to allocate unique ids to each REG_NOALIAS ADDRESS. */ 234 static int unique_id; 235 236 /* We preserve the copy of old array around to avoid amount of garbage 237 produced. About 8% of garbage produced were attributed to this 238 array. */ 239 static GTY((deletable)) vec<rtx, va_gc> *old_reg_base_value; 240 241 /* Values of XINT (address, 0) of Pmode ADDRESS rtxes for special 242 registers. */ 243 #define UNIQUE_BASE_VALUE_SP -1 244 #define UNIQUE_BASE_VALUE_ARGP -2 245 #define UNIQUE_BASE_VALUE_FP -3 246 #define UNIQUE_BASE_VALUE_HFP -4 247 248 #define static_reg_base_value \ 249 (this_target_rtl->x_static_reg_base_value) 250 251 #define REG_BASE_VALUE(X) \ 252 (REGNO (X) < vec_safe_length (reg_base_value) \ 253 ? (*reg_base_value)[REGNO (X)] : 0) 254 255 /* Vector indexed by N giving the initial (unchanging) value known for 256 pseudo-register N. This vector is initialized in init_alias_analysis, 257 and does not change until end_alias_analysis is called. */ 258 static GTY(()) vec<rtx, va_gc> *reg_known_value; 259 260 /* Vector recording for each reg_known_value whether it is due to a 261 REG_EQUIV note. Future passes (viz., reload) may replace the 262 pseudo with the equivalent expression and so we account for the 263 dependences that would be introduced if that happens. 264 265 The REG_EQUIV notes created in assign_parms may mention the arg 266 pointer, and there are explicit insns in the RTL that modify the 267 arg pointer. Thus we must ensure that such insns don't get 268 scheduled across each other because that would invalidate the 269 REG_EQUIV notes. One could argue that the REG_EQUIV notes are 270 wrong, but solving the problem in the scheduler will likely give 271 better code, so we do it here. */ 272 static sbitmap reg_known_equiv_p; 273 274 /* True when scanning insns from the start of the rtl to the 275 NOTE_INSN_FUNCTION_BEG note. */ 276 static bool copying_arguments; 277 278 279 /* The splay-tree used to store the various alias set entries. */ 280 static GTY (()) vec<alias_set_entry *, va_gc> *alias_sets; 281 282 /* Build a decomposed reference object for querying the alias-oracle 284 from the MEM rtx and store it in *REF. 285 Returns false if MEM is not suitable for the alias-oracle. */ 286 287 static bool 288 ao_ref_from_mem (ao_ref *ref, const_rtx mem) 289 { 290 tree expr = MEM_EXPR (mem); 291 tree base; 292 293 if (!expr) 294 return false; 295 296 ao_ref_init (ref, expr); 297 298 /* Get the base of the reference and see if we have to reject or 299 adjust it. */ 300 base = ao_ref_base (ref); 301 if (base == NULL_TREE) 302 return false; 303 304 /* The tree oracle doesn't like bases that are neither decls 305 nor indirect references of SSA names. */ 306 if (!(DECL_P (base) 307 || (TREE_CODE (base) == MEM_REF 308 && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) 309 || (TREE_CODE (base) == TARGET_MEM_REF 310 && TREE_CODE (TMR_BASE (base)) == SSA_NAME))) 311 return false; 312 313 ref->ref_alias_set = MEM_ALIAS_SET (mem); 314 315 /* If MEM_OFFSET or MEM_SIZE are unknown what we got from MEM_EXPR 316 is conservative, so trust it. */ 317 if (!MEM_OFFSET_KNOWN_P (mem) 318 || !MEM_SIZE_KNOWN_P (mem)) 319 return true; 320 321 /* If MEM_OFFSET/MEM_SIZE get us outside of ref->offset/ref->max_size 322 drop ref->ref. */ 323 if (maybe_lt (MEM_OFFSET (mem), 0) 324 || (ref->max_size_known_p () 325 && maybe_gt ((MEM_OFFSET (mem) + MEM_SIZE (mem)) * BITS_PER_UNIT, 326 ref->max_size))) 327 ref->ref = NULL_TREE; 328 329 /* Refine size and offset we got from analyzing MEM_EXPR by using 330 MEM_SIZE and MEM_OFFSET. */ 331 332 ref->offset += MEM_OFFSET (mem) * BITS_PER_UNIT; 333 ref->size = MEM_SIZE (mem) * BITS_PER_UNIT; 334 335 /* The MEM may extend into adjacent fields, so adjust max_size if 336 necessary. */ 337 if (ref->max_size_known_p ()) 338 ref->max_size = upper_bound (ref->max_size, ref->size); 339 340 /* If MEM_OFFSET and MEM_SIZE might get us outside of the base object of 341 the MEM_EXPR punt. This happens for STRICT_ALIGNMENT targets a lot. */ 342 if (MEM_EXPR (mem) != get_spill_slot_decl (false) 343 && (maybe_lt (ref->offset, 0) 344 || (DECL_P (ref->base) 345 && (DECL_SIZE (ref->base) == NULL_TREE 346 || !poly_int_tree_p (DECL_SIZE (ref->base)) 347 || maybe_lt (wi::to_poly_offset (DECL_SIZE (ref->base)), 348 ref->offset + ref->size))))) 349 return false; 350 351 return true; 352 } 353 354 /* Query the alias-oracle on whether the two memory rtx X and MEM may 355 alias. If TBAA_P is set also apply TBAA. Returns true if the 356 two rtxen may alias, false otherwise. */ 357 358 static bool 359 rtx_refs_may_alias_p (const_rtx x, const_rtx mem, bool tbaa_p) 360 { 361 ao_ref ref1, ref2; 362 363 if (!ao_ref_from_mem (&ref1, x) 364 || !ao_ref_from_mem (&ref2, mem)) 365 return true; 366 367 return refs_may_alias_p_1 (&ref1, &ref2, 368 tbaa_p 369 && MEM_ALIAS_SET (x) != 0 370 && MEM_ALIAS_SET (mem) != 0); 371 } 372 373 /* Return true if the ref EARLIER behaves the same as LATER with respect 374 to TBAA for every memory reference that might follow LATER. */ 375 376 bool 377 refs_same_for_tbaa_p (tree earlier, tree later) 378 { 379 ao_ref earlier_ref, later_ref; 380 ao_ref_init (&earlier_ref, earlier); 381 ao_ref_init (&later_ref, later); 382 alias_set_type earlier_set = ao_ref_alias_set (&earlier_ref); 383 alias_set_type later_set = ao_ref_alias_set (&later_ref); 384 if (!(earlier_set == later_set 385 || alias_set_subset_of (later_set, earlier_set))) 386 return false; 387 alias_set_type later_base_set = ao_ref_base_alias_set (&later_ref); 388 alias_set_type earlier_base_set = ao_ref_base_alias_set (&earlier_ref); 389 return (earlier_base_set == later_base_set 390 || alias_set_subset_of (later_base_set, earlier_base_set)); 391 } 392 393 /* Similar to refs_same_for_tbaa_p() but for use on MEM rtxs. */ 394 bool 395 mems_same_for_tbaa_p (rtx earlier, rtx later) 396 { 397 gcc_assert (MEM_P (earlier)); 398 gcc_assert (MEM_P (later)); 399 400 return ((MEM_ALIAS_SET (earlier) == MEM_ALIAS_SET (later) 401 || alias_set_subset_of (MEM_ALIAS_SET (later), 402 MEM_ALIAS_SET (earlier))) 403 && (!MEM_EXPR (earlier) 404 || refs_same_for_tbaa_p (MEM_EXPR (earlier), MEM_EXPR (later)))); 405 } 406 407 /* Returns a pointer to the alias set entry for ALIAS_SET, if there is 408 such an entry, or NULL otherwise. */ 409 410 static inline alias_set_entry * 411 get_alias_set_entry (alias_set_type alias_set) 412 { 413 return (*alias_sets)[alias_set]; 414 } 415 416 /* Returns nonzero if the alias sets for MEM1 and MEM2 are such that 417 the two MEMs cannot alias each other. */ 418 419 static inline int 420 mems_in_disjoint_alias_sets_p (const_rtx mem1, const_rtx mem2) 421 { 422 return (flag_strict_aliasing 423 && ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), 424 MEM_ALIAS_SET (mem2))); 425 } 426 427 /* Return true if the first alias set is a subset of the second. */ 428 429 bool 430 alias_set_subset_of (alias_set_type set1, alias_set_type set2) 431 { 432 alias_set_entry *ase2; 433 434 /* Disable TBAA oracle with !flag_strict_aliasing. */ 435 if (!flag_strict_aliasing) 436 return true; 437 438 /* Everything is a subset of the "aliases everything" set. */ 439 if (set2 == 0) 440 return true; 441 442 /* Check if set1 is a subset of set2. */ 443 ase2 = get_alias_set_entry (set2); 444 if (ase2 != 0 445 && (ase2->has_zero_child 446 || (ase2->children && ase2->children->get (set1)))) 447 return true; 448 449 /* As a special case we consider alias set of "void *" to be both subset 450 and superset of every alias set of a pointer. This extra symmetry does 451 not matter for alias_sets_conflict_p but it makes aliasing_component_refs_p 452 to return true on the following testcase: 453 454 void *ptr; 455 char **ptr2=(char **)&ptr; 456 *ptr2 = ... 457 458 Additionally if a set contains universal pointer, we consider every pointer 459 to be a subset of it, but we do not represent this explicitely - doing so 460 would require us to update transitive closure each time we introduce new 461 pointer type. This makes aliasing_component_refs_p to return true 462 on the following testcase: 463 464 struct a {void *ptr;} 465 char **ptr = (char **)&a.ptr; 466 ptr = ... 467 468 This makes void * truly universal pointer type. See pointer handling in 469 get_alias_set for more details. */ 470 if (ase2 && ase2->has_pointer) 471 { 472 alias_set_entry *ase1 = get_alias_set_entry (set1); 473 474 if (ase1 && ase1->is_pointer) 475 { 476 alias_set_type voidptr_set = TYPE_ALIAS_SET (ptr_type_node); 477 /* If one is ptr_type_node and other is pointer, then we consider 478 them subset of each other. */ 479 if (set1 == voidptr_set || set2 == voidptr_set) 480 return true; 481 /* If SET2 contains universal pointer's alias set, then we consdier 482 every (non-universal) pointer. */ 483 if (ase2->children && set1 != voidptr_set 484 && ase2->children->get (voidptr_set)) 485 return true; 486 } 487 } 488 return false; 489 } 490 491 /* Return 1 if the two specified alias sets may conflict. */ 492 493 int 494 alias_sets_conflict_p (alias_set_type set1, alias_set_type set2) 495 { 496 alias_set_entry *ase1; 497 alias_set_entry *ase2; 498 499 /* The easy case. */ 500 if (alias_sets_must_conflict_p (set1, set2)) 501 return 1; 502 503 /* See if the first alias set is a subset of the second. */ 504 ase1 = get_alias_set_entry (set1); 505 if (ase1 != 0 506 && ase1->children && ase1->children->get (set2)) 507 { 508 ++alias_stats.num_dag; 509 return 1; 510 } 511 512 /* Now do the same, but with the alias sets reversed. */ 513 ase2 = get_alias_set_entry (set2); 514 if (ase2 != 0 515 && ase2->children && ase2->children->get (set1)) 516 { 517 ++alias_stats.num_dag; 518 return 1; 519 } 520 521 /* We want void * to be compatible with any other pointer without 522 really dropping it to alias set 0. Doing so would make it 523 compatible with all non-pointer types too. 524 525 This is not strictly necessary by the C/C++ language 526 standards, but avoids common type punning mistakes. In 527 addition to that, we need the existence of such universal 528 pointer to implement Fortran's C_PTR type (which is defined as 529 type compatible with all C pointers). */ 530 if (ase1 && ase2 && ase1->has_pointer && ase2->has_pointer) 531 { 532 alias_set_type voidptr_set = TYPE_ALIAS_SET (ptr_type_node); 533 534 /* If one of the sets corresponds to universal pointer, 535 we consider it to conflict with anything that is 536 or contains pointer. */ 537 if (set1 == voidptr_set || set2 == voidptr_set) 538 { 539 ++alias_stats.num_universal; 540 return true; 541 } 542 /* If one of sets is (non-universal) pointer and the other 543 contains universal pointer, we also get conflict. */ 544 if (ase1->is_pointer && set2 != voidptr_set 545 && ase2->children && ase2->children->get (voidptr_set)) 546 { 547 ++alias_stats.num_universal; 548 return true; 549 } 550 if (ase2->is_pointer && set1 != voidptr_set 551 && ase1->children && ase1->children->get (voidptr_set)) 552 { 553 ++alias_stats.num_universal; 554 return true; 555 } 556 } 557 558 ++alias_stats.num_disambiguated; 559 560 /* The two alias sets are distinct and neither one is the 561 child of the other. Therefore, they cannot conflict. */ 562 return 0; 563 } 564 565 /* Return 1 if the two specified alias sets will always conflict. */ 566 567 int 568 alias_sets_must_conflict_p (alias_set_type set1, alias_set_type set2) 569 { 570 /* Disable TBAA oracle with !flag_strict_aliasing. */ 571 if (!flag_strict_aliasing) 572 return 1; 573 if (set1 == 0 || set2 == 0) 574 { 575 ++alias_stats.num_alias_zero; 576 return 1; 577 } 578 if (set1 == set2) 579 { 580 ++alias_stats.num_same_alias_set; 581 return 1; 582 } 583 584 return 0; 585 } 586 587 /* Return 1 if any MEM object of type T1 will always conflict (using the 588 dependency routines in this file) with any MEM object of type T2. 589 This is used when allocating temporary storage. If T1 and/or T2 are 590 NULL_TREE, it means we know nothing about the storage. */ 591 592 int 593 objects_must_conflict_p (tree t1, tree t2) 594 { 595 alias_set_type set1, set2; 596 597 /* If neither has a type specified, we don't know if they'll conflict 598 because we may be using them to store objects of various types, for 599 example the argument and local variables areas of inlined functions. */ 600 if (t1 == 0 && t2 == 0) 601 return 0; 602 603 /* If they are the same type, they must conflict. */ 604 if (t1 == t2) 605 { 606 ++alias_stats.num_same_objects; 607 return 1; 608 } 609 /* Likewise if both are volatile. */ 610 if (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2)) 611 { 612 ++alias_stats.num_volatile; 613 return 1; 614 } 615 616 set1 = t1 ? get_alias_set (t1) : 0; 617 set2 = t2 ? get_alias_set (t2) : 0; 618 619 /* We can't use alias_sets_conflict_p because we must make sure 620 that every subtype of t1 will conflict with every subtype of 621 t2 for which a pair of subobjects of these respective subtypes 622 overlaps on the stack. */ 623 return alias_sets_must_conflict_p (set1, set2); 624 } 625 626 /* Return true if T is an end of the access path which can be used 628 by type based alias oracle. */ 629 630 bool 631 ends_tbaa_access_path_p (const_tree t) 632 { 633 switch (TREE_CODE (t)) 634 { 635 case COMPONENT_REF: 636 if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1))) 637 return true; 638 /* Permit type-punning when accessing a union, provided the access 639 is directly through the union. For example, this code does not 640 permit taking the address of a union member and then storing 641 through it. Even the type-punning allowed here is a GCC 642 extension, albeit a common and useful one; the C standard says 643 that such accesses have implementation-defined behavior. */ 644 else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0))) == UNION_TYPE) 645 return true; 646 break; 647 648 case ARRAY_REF: 649 case ARRAY_RANGE_REF: 650 if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0)))) 651 return true; 652 break; 653 654 case REALPART_EXPR: 655 case IMAGPART_EXPR: 656 break; 657 658 case BIT_FIELD_REF: 659 case VIEW_CONVERT_EXPR: 660 /* Bitfields and casts are never addressable. */ 661 return true; 662 break; 663 664 default: 665 gcc_unreachable (); 666 } 667 return false; 668 } 669 670 /* Return the outermost parent of component present in the chain of 671 component references handled by get_inner_reference in T with the 672 following property: 673 - the component is non-addressable 674 or NULL_TREE if no such parent exists. In the former cases, the alias 675 set of this parent is the alias set that must be used for T itself. */ 676 677 tree 678 component_uses_parent_alias_set_from (const_tree t) 679 { 680 const_tree found = NULL_TREE; 681 682 while (handled_component_p (t)) 683 { 684 if (ends_tbaa_access_path_p (t)) 685 found = t; 686 687 t = TREE_OPERAND (t, 0); 688 } 689 690 if (found) 691 return TREE_OPERAND (found, 0); 692 693 return NULL_TREE; 694 } 695 696 697 /* Return whether the pointer-type T effective for aliasing may 698 access everything and thus the reference has to be assigned 699 alias-set zero. */ 700 701 static bool 702 ref_all_alias_ptr_type_p (const_tree t) 703 { 704 return (TREE_CODE (TREE_TYPE (t)) == VOID_TYPE 705 || TYPE_REF_CAN_ALIAS_ALL (t)); 706 } 707 708 /* Return the alias set for the memory pointed to by T, which may be 709 either a type or an expression. Return -1 if there is nothing 710 special about dereferencing T. */ 711 712 static alias_set_type 713 get_deref_alias_set_1 (tree t) 714 { 715 /* All we care about is the type. */ 716 if (! TYPE_P (t)) 717 t = TREE_TYPE (t); 718 719 /* If we have an INDIRECT_REF via a void pointer, we don't 720 know anything about what that might alias. Likewise if the 721 pointer is marked that way. */ 722 if (ref_all_alias_ptr_type_p (t)) 723 return 0; 724 725 return -1; 726 } 727 728 /* Return the alias set for the memory pointed to by T, which may be 729 either a type or an expression. */ 730 731 alias_set_type 732 get_deref_alias_set (tree t) 733 { 734 /* If we're not doing any alias analysis, just assume everything 735 aliases everything else. */ 736 if (!flag_strict_aliasing) 737 return 0; 738 739 alias_set_type set = get_deref_alias_set_1 (t); 740 741 /* Fall back to the alias-set of the pointed-to type. */ 742 if (set == -1) 743 { 744 if (! TYPE_P (t)) 745 t = TREE_TYPE (t); 746 set = get_alias_set (TREE_TYPE (t)); 747 } 748 749 return set; 750 } 751 752 /* Return the pointer-type relevant for TBAA purposes from the 753 memory reference tree *T or NULL_TREE in which case *T is 754 adjusted to point to the outermost component reference that 755 can be used for assigning an alias set. */ 756 757 tree 758 reference_alias_ptr_type_1 (tree *t) 759 { 760 tree inner; 761 762 /* Get the base object of the reference. */ 763 inner = *t; 764 while (handled_component_p (inner)) 765 { 766 /* If there is a VIEW_CONVERT_EXPR in the chain we cannot use 767 the type of any component references that wrap it to 768 determine the alias-set. */ 769 if (TREE_CODE (inner) == VIEW_CONVERT_EXPR) 770 *t = TREE_OPERAND (inner, 0); 771 inner = TREE_OPERAND (inner, 0); 772 } 773 774 /* Handle pointer dereferences here, they can override the 775 alias-set. */ 776 if (INDIRECT_REF_P (inner) 777 && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 0)))) 778 return TREE_TYPE (TREE_OPERAND (inner, 0)); 779 else if (TREE_CODE (inner) == TARGET_MEM_REF) 780 return TREE_TYPE (TMR_OFFSET (inner)); 781 else if (TREE_CODE (inner) == MEM_REF 782 && ref_all_alias_ptr_type_p (TREE_TYPE (TREE_OPERAND (inner, 1)))) 783 return TREE_TYPE (TREE_OPERAND (inner, 1)); 784 785 /* If the innermost reference is a MEM_REF that has a 786 conversion embedded treat it like a VIEW_CONVERT_EXPR above, 787 using the memory access type for determining the alias-set. */ 788 if (TREE_CODE (inner) == MEM_REF 789 && (TYPE_MAIN_VARIANT (TREE_TYPE (inner)) 790 != TYPE_MAIN_VARIANT 791 (TREE_TYPE (TREE_TYPE (TREE_OPERAND (inner, 1)))))) 792 return TREE_TYPE (TREE_OPERAND (inner, 1)); 793 794 /* Otherwise, pick up the outermost object that we could have 795 a pointer to. */ 796 tree tem = component_uses_parent_alias_set_from (*t); 797 if (tem) 798 *t = tem; 799 800 return NULL_TREE; 801 } 802 803 /* Return the pointer-type relevant for TBAA purposes from the 804 gimple memory reference tree T. This is the type to be used for 805 the offset operand of MEM_REF or TARGET_MEM_REF replacements of T 806 and guarantees that get_alias_set will return the same alias 807 set for T and the replacement. */ 808 809 tree 810 reference_alias_ptr_type (tree t) 811 { 812 /* If the frontend assigns this alias-set zero, preserve that. */ 813 if (lang_hooks.get_alias_set (t) == 0) 814 return ptr_type_node; 815 816 tree ptype = reference_alias_ptr_type_1 (&t); 817 /* If there is a given pointer type for aliasing purposes, return it. */ 818 if (ptype != NULL_TREE) 819 return ptype; 820 821 /* Otherwise build one from the outermost component reference we 822 may use. */ 823 if (TREE_CODE (t) == MEM_REF 824 || TREE_CODE (t) == TARGET_MEM_REF) 825 return TREE_TYPE (TREE_OPERAND (t, 1)); 826 else 827 return build_pointer_type (TYPE_MAIN_VARIANT (TREE_TYPE (t))); 828 } 829 830 /* Return whether the pointer-types T1 and T2 used to determine 831 two alias sets of two references will yield the same answer 832 from get_deref_alias_set. */ 833 834 bool 835 alias_ptr_types_compatible_p (tree t1, tree t2) 836 { 837 if (TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2)) 838 return true; 839 840 if (ref_all_alias_ptr_type_p (t1) 841 || ref_all_alias_ptr_type_p (t2)) 842 return false; 843 844 /* This function originally abstracts from simply comparing 845 get_deref_alias_set so that we are sure this still computes 846 the same result after LTO type merging is applied. 847 When in LTO type merging is done we can actually do this compare. 848 */ 849 if (in_lto_p) 850 return get_deref_alias_set (t1) == get_deref_alias_set (t2); 851 else 852 return (TYPE_MAIN_VARIANT (TREE_TYPE (t1)) 853 == TYPE_MAIN_VARIANT (TREE_TYPE (t2))); 854 } 855 856 /* Create emptry alias set entry. */ 857 858 alias_set_entry * 859 init_alias_set_entry (alias_set_type set) 860 { 861 alias_set_entry *ase = ggc_alloc<alias_set_entry> (); 862 ase->alias_set = set; 863 ase->children = NULL; 864 ase->has_zero_child = false; 865 ase->is_pointer = false; 866 ase->has_pointer = false; 867 gcc_checking_assert (!get_alias_set_entry (set)); 868 (*alias_sets)[set] = ase; 869 return ase; 870 } 871 872 /* Return the alias set for T, which may be either a type or an 873 expression. Call language-specific routine for help, if needed. */ 874 875 alias_set_type 876 get_alias_set (tree t) 877 { 878 alias_set_type set; 879 880 /* We cannot give up with -fno-strict-aliasing because we need to build 881 proper type representations for possible functions which are built with 882 -fstrict-aliasing. */ 883 884 /* return 0 if this or its type is an error. */ 885 if (t == error_mark_node 886 || (! TYPE_P (t) 887 && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node))) 888 return 0; 889 890 /* We can be passed either an expression or a type. This and the 891 language-specific routine may make mutually-recursive calls to each other 892 to figure out what to do. At each juncture, we see if this is a tree 893 that the language may need to handle specially. First handle things that 894 aren't types. */ 895 if (! TYPE_P (t)) 896 { 897 /* Give the language a chance to do something with this tree 898 before we look at it. */ 899 STRIP_NOPS (t); 900 set = lang_hooks.get_alias_set (t); 901 if (set != -1) 902 return set; 903 904 /* Get the alias pointer-type to use or the outermost object 905 that we could have a pointer to. */ 906 tree ptype = reference_alias_ptr_type_1 (&t); 907 if (ptype != NULL) 908 return get_deref_alias_set (ptype); 909 910 /* If we've already determined the alias set for a decl, just return 911 it. This is necessary for C++ anonymous unions, whose component 912 variables don't look like union members (boo!). */ 913 if (VAR_P (t) 914 && DECL_RTL_SET_P (t) && MEM_P (DECL_RTL (t))) 915 return MEM_ALIAS_SET (DECL_RTL (t)); 916 917 /* Now all we care about is the type. */ 918 t = TREE_TYPE (t); 919 } 920 921 /* Variant qualifiers don't affect the alias set, so get the main 922 variant. */ 923 t = TYPE_MAIN_VARIANT (t); 924 925 if (AGGREGATE_TYPE_P (t) 926 && TYPE_TYPELESS_STORAGE (t)) 927 return 0; 928 929 /* Always use the canonical type as well. If this is a type that 930 requires structural comparisons to identify compatible types 931 use alias set zero. */ 932 if (TYPE_STRUCTURAL_EQUALITY_P (t)) 933 { 934 /* Allow the language to specify another alias set for this 935 type. */ 936 set = lang_hooks.get_alias_set (t); 937 if (set != -1) 938 return set; 939 /* Handle structure type equality for pointer types, arrays and vectors. 940 This is easy to do, because the code below ignores canonical types on 941 these anyway. This is important for LTO, where TYPE_CANONICAL for 942 pointers cannot be meaningfully computed by the frontend. */ 943 if (canonical_type_used_p (t)) 944 { 945 /* In LTO we set canonical types for all types where it makes 946 sense to do so. Double check we did not miss some type. */ 947 gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t)); 948 return 0; 949 } 950 } 951 else 952 { 953 t = TYPE_CANONICAL (t); 954 gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t)); 955 } 956 957 /* If this is a type with a known alias set, return it. */ 958 gcc_checking_assert (t == TYPE_MAIN_VARIANT (t)); 959 if (TYPE_ALIAS_SET_KNOWN_P (t)) 960 return TYPE_ALIAS_SET (t); 961 962 /* We don't want to set TYPE_ALIAS_SET for incomplete types. */ 963 if (!COMPLETE_TYPE_P (t)) 964 { 965 /* For arrays with unknown size the conservative answer is the 966 alias set of the element type. */ 967 if (TREE_CODE (t) == ARRAY_TYPE) 968 return get_alias_set (TREE_TYPE (t)); 969 970 /* But return zero as a conservative answer for incomplete types. */ 971 return 0; 972 } 973 974 /* See if the language has special handling for this type. */ 975 set = lang_hooks.get_alias_set (t); 976 if (set != -1) 977 return set; 978 979 /* There are no objects of FUNCTION_TYPE, so there's no point in 980 using up an alias set for them. (There are, of course, pointers 981 and references to functions, but that's different.) */ 982 else if (TREE_CODE (t) == FUNCTION_TYPE || TREE_CODE (t) == METHOD_TYPE) 983 set = 0; 984 985 /* Unless the language specifies otherwise, let vector types alias 986 their components. This avoids some nasty type punning issues in 987 normal usage. And indeed lets vectors be treated more like an 988 array slice. */ 989 else if (TREE_CODE (t) == VECTOR_TYPE) 990 set = get_alias_set (TREE_TYPE (t)); 991 992 /* Unless the language specifies otherwise, treat array types the 993 same as their components. This avoids the asymmetry we get 994 through recording the components. Consider accessing a 995 character(kind=1) through a reference to a character(kind=1)[1:1]. 996 Or consider if we want to assign integer(kind=4)[0:D.1387] and 997 integer(kind=4)[4] the same alias set or not. 998 Just be pragmatic here and make sure the array and its element 999 type get the same alias set assigned. */ 1000 else if (TREE_CODE (t) == ARRAY_TYPE 1001 && (!TYPE_NONALIASED_COMPONENT (t) 1002 || TYPE_STRUCTURAL_EQUALITY_P (t))) 1003 set = get_alias_set (TREE_TYPE (t)); 1004 1005 /* From the former common C and C++ langhook implementation: 1006 1007 Unfortunately, there is no canonical form of a pointer type. 1008 In particular, if we have `typedef int I', then `int *', and 1009 `I *' are different types. So, we have to pick a canonical 1010 representative. We do this below. 1011 1012 Technically, this approach is actually more conservative that 1013 it needs to be. In particular, `const int *' and `int *' 1014 should be in different alias sets, according to the C and C++ 1015 standard, since their types are not the same, and so, 1016 technically, an `int **' and `const int **' cannot point at 1017 the same thing. 1018 1019 But, the standard is wrong. In particular, this code is 1020 legal C++: 1021 1022 int *ip; 1023 int **ipp = &ip; 1024 const int* const* cipp = ipp; 1025 And, it doesn't make sense for that to be legal unless you 1026 can dereference IPP and CIPP. So, we ignore cv-qualifiers on 1027 the pointed-to types. This issue has been reported to the 1028 C++ committee. 1029 1030 For this reason go to canonical type of the unqalified pointer type. 1031 Until GCC 6 this code set all pointers sets to have alias set of 1032 ptr_type_node but that is a bad idea, because it prevents disabiguations 1033 in between pointers. For Firefox this accounts about 20% of all 1034 disambiguations in the program. */ 1035 else if (POINTER_TYPE_P (t) && t != ptr_type_node) 1036 { 1037 tree p; 1038 auto_vec <bool, 8> reference; 1039 1040 /* Unnest all pointers and references. 1041 We also want to make pointer to array/vector equivalent to pointer to 1042 its element (see the reasoning above). Skip all those types, too. */ 1043 for (p = t; POINTER_TYPE_P (p) 1044 || (TREE_CODE (p) == ARRAY_TYPE 1045 && (!TYPE_NONALIASED_COMPONENT (p) 1046 || !COMPLETE_TYPE_P (p) 1047 || TYPE_STRUCTURAL_EQUALITY_P (p))) 1048 || TREE_CODE (p) == VECTOR_TYPE; 1049 p = TREE_TYPE (p)) 1050 { 1051 /* Ada supports recursive pointers. Instead of doing recursion 1052 check, just give up once the preallocated space of 8 elements 1053 is up. In this case just punt to void * alias set. */ 1054 if (reference.length () == 8) 1055 { 1056 p = ptr_type_node; 1057 break; 1058 } 1059 if (TREE_CODE (p) == REFERENCE_TYPE) 1060 /* In LTO we want languages that use references to be compatible 1061 with languages that use pointers. */ 1062 reference.safe_push (true && !in_lto_p); 1063 if (TREE_CODE (p) == POINTER_TYPE) 1064 reference.safe_push (false); 1065 } 1066 p = TYPE_MAIN_VARIANT (p); 1067 1068 /* In LTO for C++ programs we can turn incomplete types to complete 1069 using ODR name lookup. */ 1070 if (in_lto_p && TYPE_STRUCTURAL_EQUALITY_P (p) && odr_type_p (p)) 1071 { 1072 p = prevailing_odr_type (p); 1073 gcc_checking_assert (TYPE_MAIN_VARIANT (p) == p); 1074 } 1075 1076 /* Make void * compatible with char * and also void **. 1077 Programs are commonly violating TBAA by this. 1078 1079 We also make void * to conflict with every pointer 1080 (see record_component_aliases) and thus it is safe it to use it for 1081 pointers to types with TYPE_STRUCTURAL_EQUALITY_P. */ 1082 if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p)) 1083 set = get_alias_set (ptr_type_node); 1084 else 1085 { 1086 /* Rebuild pointer type starting from canonical types using 1087 unqualified pointers and references only. This way all such 1088 pointers will have the same alias set and will conflict with 1089 each other. 1090 1091 Most of time we already have pointers or references of a given type. 1092 If not we build new one just to be sure that if someone later 1093 (probably only middle-end can, as we should assign all alias 1094 classes only after finishing translation unit) builds the pointer 1095 type, the canonical type will match. */ 1096 p = TYPE_CANONICAL (p); 1097 while (!reference.is_empty ()) 1098 { 1099 if (reference.pop ()) 1100 p = build_reference_type (p); 1101 else 1102 p = build_pointer_type (p); 1103 gcc_checking_assert (p == TYPE_MAIN_VARIANT (p)); 1104 /* build_pointer_type should always return the canonical type. 1105 For LTO TYPE_CANOINCAL may be NULL, because we do not compute 1106 them. Be sure that frontends do not glob canonical types of 1107 pointers in unexpected way and that p == TYPE_CANONICAL (p) 1108 in all other cases. */ 1109 gcc_checking_assert (!TYPE_CANONICAL (p) 1110 || p == TYPE_CANONICAL (p)); 1111 } 1112 1113 /* Assign the alias set to both p and t. 1114 We cannot call get_alias_set (p) here as that would trigger 1115 infinite recursion when p == t. In other cases it would just 1116 trigger unnecesary legwork of rebuilding the pointer again. */ 1117 gcc_checking_assert (p == TYPE_MAIN_VARIANT (p)); 1118 if (TYPE_ALIAS_SET_KNOWN_P (p)) 1119 set = TYPE_ALIAS_SET (p); 1120 else 1121 { 1122 set = new_alias_set (); 1123 TYPE_ALIAS_SET (p) = set; 1124 } 1125 } 1126 } 1127 /* Alias set of ptr_type_node is special and serve as universal pointer which 1128 is TBAA compatible with every other pointer type. Be sure we have the 1129 alias set built even for LTO which otherwise keeps all TYPE_CANONICAL 1130 of pointer types NULL. */ 1131 else if (t == ptr_type_node) 1132 set = new_alias_set (); 1133 1134 /* Otherwise make a new alias set for this type. */ 1135 else 1136 { 1137 /* Each canonical type gets its own alias set, so canonical types 1138 shouldn't form a tree. It doesn't really matter for types 1139 we handle specially above, so only check it where it possibly 1140 would result in a bogus alias set. */ 1141 gcc_checking_assert (TYPE_CANONICAL (t) == t); 1142 1143 set = new_alias_set (); 1144 } 1145 1146 TYPE_ALIAS_SET (t) = set; 1147 1148 /* If this is an aggregate type or a complex type, we must record any 1149 component aliasing information. */ 1150 if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE) 1151 record_component_aliases (t); 1152 1153 /* We treat pointer types specially in alias_set_subset_of. */ 1154 if (POINTER_TYPE_P (t) && set) 1155 { 1156 alias_set_entry *ase = get_alias_set_entry (set); 1157 if (!ase) 1158 ase = init_alias_set_entry (set); 1159 ase->is_pointer = true; 1160 ase->has_pointer = true; 1161 } 1162 1163 return set; 1164 } 1165 1166 /* Return a brand-new alias set. */ 1167 1168 alias_set_type 1169 new_alias_set (void) 1170 { 1171 if (alias_sets == 0) 1172 vec_safe_push (alias_sets, (alias_set_entry *) NULL); 1173 vec_safe_push (alias_sets, (alias_set_entry *) NULL); 1174 return alias_sets->length () - 1; 1175 } 1176 1177 /* Indicate that things in SUBSET can alias things in SUPERSET, but that 1178 not everything that aliases SUPERSET also aliases SUBSET. For example, 1179 in C, a store to an `int' can alias a load of a structure containing an 1180 `int', and vice versa. But it can't alias a load of a 'double' member 1181 of the same structure. Here, the structure would be the SUPERSET and 1182 `int' the SUBSET. This relationship is also described in the comment at 1183 the beginning of this file. 1184 1185 This function should be called only once per SUPERSET/SUBSET pair. 1186 1187 It is illegal for SUPERSET to be zero; everything is implicitly a 1188 subset of alias set zero. */ 1189 1190 void 1191 record_alias_subset (alias_set_type superset, alias_set_type subset) 1192 { 1193 alias_set_entry *superset_entry; 1194 alias_set_entry *subset_entry; 1195 1196 /* It is possible in complex type situations for both sets to be the same, 1197 in which case we can ignore this operation. */ 1198 if (superset == subset) 1199 return; 1200 1201 gcc_assert (superset); 1202 1203 superset_entry = get_alias_set_entry (superset); 1204 if (superset_entry == 0) 1205 { 1206 /* Create an entry for the SUPERSET, so that we have a place to 1207 attach the SUBSET. */ 1208 superset_entry = init_alias_set_entry (superset); 1209 } 1210 1211 if (subset == 0) 1212 superset_entry->has_zero_child = 1; 1213 else 1214 { 1215 if (!superset_entry->children) 1216 superset_entry->children 1217 = hash_map<alias_set_hash, int>::create_ggc (64); 1218 1219 /* Enter the SUBSET itself as a child of the SUPERSET. If it was 1220 already there we're done. */ 1221 if (superset_entry->children->put (subset, 0)) 1222 return; 1223 1224 subset_entry = get_alias_set_entry (subset); 1225 /* If there is an entry for the subset, enter all of its children 1226 (if they are not already present) as children of the SUPERSET. */ 1227 if (subset_entry) 1228 { 1229 if (subset_entry->has_zero_child) 1230 superset_entry->has_zero_child = true; 1231 if (subset_entry->has_pointer) 1232 superset_entry->has_pointer = true; 1233 1234 if (subset_entry->children) 1235 { 1236 hash_map<alias_set_hash, int>::iterator iter 1237 = subset_entry->children->begin (); 1238 for (; iter != subset_entry->children->end (); ++iter) 1239 superset_entry->children->put ((*iter).first, (*iter).second); 1240 } 1241 } 1242 } 1243 } 1244 1245 /* Record that component types of TYPE, if any, are part of SUPERSET for 1246 aliasing purposes. For record types, we only record component types 1247 for fields that are not marked non-addressable. For array types, we 1248 only record the component type if it is not marked non-aliased. */ 1249 1250 void 1251 record_component_aliases (tree type, alias_set_type superset) 1252 { 1253 tree field; 1254 1255 if (superset == 0) 1256 return; 1257 1258 switch (TREE_CODE (type)) 1259 { 1260 case RECORD_TYPE: 1261 case UNION_TYPE: 1262 case QUAL_UNION_TYPE: 1263 { 1264 /* LTO non-ODR type merging does not make any difference between 1265 component pointer types. We may have 1266 1267 struct foo {int *a;}; 1268 1269 as TYPE_CANONICAL of 1270 1271 struct bar {float *a;}; 1272 1273 Because accesses to int * and float * do not alias, we would get 1274 false negative when accessing the same memory location by 1275 float ** and bar *. We thus record the canonical type as: 1276 1277 struct {void *a;}; 1278 1279 void * is special cased and works as a universal pointer type. 1280 Accesses to it conflicts with accesses to any other pointer 1281 type. */ 1282 bool void_pointers = in_lto_p 1283 && (!odr_type_p (type) 1284 || !odr_based_tbaa_p (type)); 1285 for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field)) 1286 if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field)) 1287 { 1288 tree t = TREE_TYPE (field); 1289 if (void_pointers) 1290 { 1291 /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their 1292 element type and that type has to be normalized to void *, 1293 too, in the case it is a pointer. */ 1294 while (!canonical_type_used_p (t) && !POINTER_TYPE_P (t)) 1295 { 1296 gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t)); 1297 t = TREE_TYPE (t); 1298 } 1299 if (POINTER_TYPE_P (t)) 1300 t = ptr_type_node; 1301 else if (flag_checking) 1302 gcc_checking_assert (get_alias_set (t) 1303 == get_alias_set (TREE_TYPE (field))); 1304 } 1305 1306 alias_set_type set = get_alias_set (t); 1307 record_alias_subset (superset, set); 1308 /* If the field has alias-set zero make sure to still record 1309 any componets of it. This makes sure that for 1310 struct A { 1311 struct B { 1312 int i; 1313 char c[4]; 1314 } b; 1315 }; 1316 in C++ even though 'B' has alias-set zero because 1317 TYPE_TYPELESS_STORAGE is set, 'A' has the alias-set of 1318 'int' as subset. */ 1319 if (set == 0) 1320 record_component_aliases (t, superset); 1321 } 1322 } 1323 break; 1324 1325 case COMPLEX_TYPE: 1326 record_alias_subset (superset, get_alias_set (TREE_TYPE (type))); 1327 break; 1328 1329 /* VECTOR_TYPE and ARRAY_TYPE share the alias set with their 1330 element type. */ 1331 1332 default: 1333 break; 1334 } 1335 } 1336 1337 /* Record that component types of TYPE, if any, are part of that type for 1338 aliasing purposes. For record types, we only record component types 1339 for fields that are not marked non-addressable. For array types, we 1340 only record the component type if it is not marked non-aliased. */ 1341 1342 void 1343 record_component_aliases (tree type) 1344 { 1345 alias_set_type superset = get_alias_set (type); 1346 record_component_aliases (type, superset); 1347 } 1348 1349 1350 /* Allocate an alias set for use in storing and reading from the varargs 1351 spill area. */ 1352 1353 static GTY(()) alias_set_type varargs_set = -1; 1354 1355 alias_set_type 1356 get_varargs_alias_set (void) 1357 { 1358 #if 1 1359 /* We now lower VA_ARG_EXPR, and there's currently no way to attach the 1360 varargs alias set to an INDIRECT_REF (FIXME!), so we can't 1361 consistently use the varargs alias set for loads from the varargs 1362 area. So don't use it anywhere. */ 1363 return 0; 1364 #else 1365 if (varargs_set == -1) 1366 varargs_set = new_alias_set (); 1367 1368 return varargs_set; 1369 #endif 1370 } 1371 1372 /* Likewise, but used for the fixed portions of the frame, e.g., register 1373 save areas. */ 1374 1375 static GTY(()) alias_set_type frame_set = -1; 1376 1377 alias_set_type 1378 get_frame_alias_set (void) 1379 { 1380 if (frame_set == -1) 1381 frame_set = new_alias_set (); 1382 1383 return frame_set; 1384 } 1385 1386 /* Create a new, unique base with id ID. */ 1387 1388 static rtx 1389 unique_base_value (HOST_WIDE_INT id) 1390 { 1391 return gen_rtx_ADDRESS (Pmode, id); 1392 } 1393 1394 /* Return true if accesses based on any other base value cannot alias 1395 those based on X. */ 1396 1397 static bool 1398 unique_base_value_p (rtx x) 1399 { 1400 return GET_CODE (x) == ADDRESS && GET_MODE (x) == Pmode; 1401 } 1402 1403 /* Return true if X is known to be a base value. */ 1404 1405 static bool 1406 known_base_value_p (rtx x) 1407 { 1408 switch (GET_CODE (x)) 1409 { 1410 case LABEL_REF: 1411 case SYMBOL_REF: 1412 return true; 1413 1414 case ADDRESS: 1415 /* Arguments may or may not be bases; we don't know for sure. */ 1416 return GET_MODE (x) != VOIDmode; 1417 1418 default: 1419 return false; 1420 } 1421 } 1422 1423 /* Inside SRC, the source of a SET, find a base address. */ 1424 1425 static rtx 1426 find_base_value (rtx src) 1427 { 1428 unsigned int regno; 1429 scalar_int_mode int_mode; 1430 1431 #if defined (FIND_BASE_TERM) 1432 /* Try machine-dependent ways to find the base term. */ 1433 src = FIND_BASE_TERM (src); 1434 #endif 1435 1436 switch (GET_CODE (src)) 1437 { 1438 case SYMBOL_REF: 1439 case LABEL_REF: 1440 return src; 1441 1442 case REG: 1443 regno = REGNO (src); 1444 /* At the start of a function, argument registers have known base 1445 values which may be lost later. Returning an ADDRESS 1446 expression here allows optimization based on argument values 1447 even when the argument registers are used for other purposes. */ 1448 if (regno < FIRST_PSEUDO_REGISTER && copying_arguments) 1449 return new_reg_base_value[regno]; 1450 1451 /* If a pseudo has a known base value, return it. Do not do this 1452 for non-fixed hard regs since it can result in a circular 1453 dependency chain for registers which have values at function entry. 1454 1455 The test above is not sufficient because the scheduler may move 1456 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */ 1457 if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno]) 1458 && regno < vec_safe_length (reg_base_value)) 1459 { 1460 /* If we're inside init_alias_analysis, use new_reg_base_value 1461 to reduce the number of relaxation iterations. */ 1462 if (new_reg_base_value && new_reg_base_value[regno] 1463 && DF_REG_DEF_COUNT (regno) == 1) 1464 return new_reg_base_value[regno]; 1465 1466 if ((*reg_base_value)[regno]) 1467 return (*reg_base_value)[regno]; 1468 } 1469 1470 return 0; 1471 1472 case MEM: 1473 /* Check for an argument passed in memory. Only record in the 1474 copying-arguments block; it is too hard to track changes 1475 otherwise. */ 1476 if (copying_arguments 1477 && (XEXP (src, 0) == arg_pointer_rtx 1478 || (GET_CODE (XEXP (src, 0)) == PLUS 1479 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx))) 1480 return arg_base_value; 1481 return 0; 1482 1483 case CONST: 1484 src = XEXP (src, 0); 1485 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS) 1486 break; 1487 1488 /* fall through */ 1489 1490 case PLUS: 1491 case MINUS: 1492 { 1493 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1); 1494 1495 /* If either operand is a REG that is a known pointer, then it 1496 is the base. */ 1497 if (REG_P (src_0) && REG_POINTER (src_0)) 1498 return find_base_value (src_0); 1499 if (REG_P (src_1) && REG_POINTER (src_1)) 1500 return find_base_value (src_1); 1501 1502 /* If either operand is a REG, then see if we already have 1503 a known value for it. */ 1504 if (REG_P (src_0)) 1505 { 1506 temp = find_base_value (src_0); 1507 if (temp != 0) 1508 src_0 = temp; 1509 } 1510 1511 if (REG_P (src_1)) 1512 { 1513 temp = find_base_value (src_1); 1514 if (temp!= 0) 1515 src_1 = temp; 1516 } 1517 1518 /* If either base is named object or a special address 1519 (like an argument or stack reference), then use it for the 1520 base term. */ 1521 if (src_0 != 0 && known_base_value_p (src_0)) 1522 return src_0; 1523 1524 if (src_1 != 0 && known_base_value_p (src_1)) 1525 return src_1; 1526 1527 /* Guess which operand is the base address: 1528 If either operand is a symbol, then it is the base. If 1529 either operand is a CONST_INT, then the other is the base. */ 1530 if (CONST_INT_P (src_1) || CONSTANT_P (src_0)) 1531 return find_base_value (src_0); 1532 else if (CONST_INT_P (src_0) || CONSTANT_P (src_1)) 1533 return find_base_value (src_1); 1534 1535 return 0; 1536 } 1537 1538 case LO_SUM: 1539 /* The standard form is (lo_sum reg sym) so look only at the 1540 second operand. */ 1541 return find_base_value (XEXP (src, 1)); 1542 1543 case AND: 1544 /* Look through aligning ANDs. And AND with zero or one with 1545 the LSB set isn't one (see for example PR92462). */ 1546 if (CONST_INT_P (XEXP (src, 1)) 1547 && INTVAL (XEXP (src, 1)) != 0 1548 && (INTVAL (XEXP (src, 1)) & 1) == 0) 1549 return find_base_value (XEXP (src, 0)); 1550 return 0; 1551 1552 case TRUNCATE: 1553 /* As we do not know which address space the pointer is referring to, we can 1554 handle this only if the target does not support different pointer or 1555 address modes depending on the address space. */ 1556 if (!target_default_pointer_address_modes_p ()) 1557 break; 1558 if (!is_a <scalar_int_mode> (GET_MODE (src), &int_mode) 1559 || GET_MODE_PRECISION (int_mode) < GET_MODE_PRECISION (Pmode)) 1560 break; 1561 /* Fall through. */ 1562 case HIGH: 1563 case PRE_INC: 1564 case PRE_DEC: 1565 case POST_INC: 1566 case POST_DEC: 1567 case PRE_MODIFY: 1568 case POST_MODIFY: 1569 return find_base_value (XEXP (src, 0)); 1570 1571 case ZERO_EXTEND: 1572 case SIGN_EXTEND: /* used for NT/Alpha pointers */ 1573 /* As we do not know which address space the pointer is referring to, we can 1574 handle this only if the target does not support different pointer or 1575 address modes depending on the address space. */ 1576 if (!target_default_pointer_address_modes_p ()) 1577 break; 1578 1579 { 1580 rtx temp = find_base_value (XEXP (src, 0)); 1581 1582 if (temp != 0 && CONSTANT_P (temp)) 1583 temp = convert_memory_address (Pmode, temp); 1584 1585 return temp; 1586 } 1587 1588 default: 1589 break; 1590 } 1591 1592 return 0; 1593 } 1594 1595 /* Called from init_alias_analysis indirectly through note_stores, 1596 or directly if DEST is a register with a REG_NOALIAS note attached. 1597 SET is null in the latter case. */ 1598 1599 /* While scanning insns to find base values, reg_seen[N] is nonzero if 1600 register N has been set in this function. */ 1601 static sbitmap reg_seen; 1602 1603 static void 1604 record_set (rtx dest, const_rtx set, void *data ATTRIBUTE_UNUSED) 1605 { 1606 unsigned regno; 1607 rtx src; 1608 int n; 1609 1610 if (!REG_P (dest)) 1611 return; 1612 1613 regno = REGNO (dest); 1614 1615 gcc_checking_assert (regno < reg_base_value->length ()); 1616 1617 n = REG_NREGS (dest); 1618 if (n != 1) 1619 { 1620 while (--n >= 0) 1621 { 1622 bitmap_set_bit (reg_seen, regno + n); 1623 new_reg_base_value[regno + n] = 0; 1624 } 1625 return; 1626 } 1627 1628 if (set) 1629 { 1630 /* A CLOBBER wipes out any old value but does not prevent a previously 1631 unset register from acquiring a base address (i.e. reg_seen is not 1632 set). */ 1633 if (GET_CODE (set) == CLOBBER) 1634 { 1635 new_reg_base_value[regno] = 0; 1636 return; 1637 } 1638 1639 src = SET_SRC (set); 1640 } 1641 else 1642 { 1643 /* There's a REG_NOALIAS note against DEST. */ 1644 if (bitmap_bit_p (reg_seen, regno)) 1645 { 1646 new_reg_base_value[regno] = 0; 1647 return; 1648 } 1649 bitmap_set_bit (reg_seen, regno); 1650 new_reg_base_value[regno] = unique_base_value (unique_id++); 1651 return; 1652 } 1653 1654 /* If this is not the first set of REGNO, see whether the new value 1655 is related to the old one. There are two cases of interest: 1656 1657 (1) The register might be assigned an entirely new value 1658 that has the same base term as the original set. 1659 1660 (2) The set might be a simple self-modification that 1661 cannot change REGNO's base value. 1662 1663 If neither case holds, reject the original base value as invalid. 1664 Note that the following situation is not detected: 1665 1666 extern int x, y; int *p = &x; p += (&y-&x); 1667 1668 ANSI C does not allow computing the difference of addresses 1669 of distinct top level objects. */ 1670 if (new_reg_base_value[regno] != 0 1671 && find_base_value (src) != new_reg_base_value[regno]) 1672 switch (GET_CODE (src)) 1673 { 1674 case LO_SUM: 1675 case MINUS: 1676 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest) 1677 new_reg_base_value[regno] = 0; 1678 break; 1679 case PLUS: 1680 /* If the value we add in the PLUS is also a valid base value, 1681 this might be the actual base value, and the original value 1682 an index. */ 1683 { 1684 rtx other = NULL_RTX; 1685 1686 if (XEXP (src, 0) == dest) 1687 other = XEXP (src, 1); 1688 else if (XEXP (src, 1) == dest) 1689 other = XEXP (src, 0); 1690 1691 if (! other || find_base_value (other)) 1692 new_reg_base_value[regno] = 0; 1693 break; 1694 } 1695 case AND: 1696 if (XEXP (src, 0) != dest || !CONST_INT_P (XEXP (src, 1))) 1697 new_reg_base_value[regno] = 0; 1698 break; 1699 default: 1700 new_reg_base_value[regno] = 0; 1701 break; 1702 } 1703 /* If this is the first set of a register, record the value. */ 1704 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno]) 1705 && ! bitmap_bit_p (reg_seen, regno) && new_reg_base_value[regno] == 0) 1706 new_reg_base_value[regno] = find_base_value (src); 1707 1708 bitmap_set_bit (reg_seen, regno); 1709 } 1710 1711 /* Return REG_BASE_VALUE for REGNO. Selective scheduler uses this to avoid 1712 using hard registers with non-null REG_BASE_VALUE for renaming. */ 1713 rtx 1714 get_reg_base_value (unsigned int regno) 1715 { 1716 return (*reg_base_value)[regno]; 1717 } 1718 1719 /* If a value is known for REGNO, return it. */ 1720 1721 rtx 1722 get_reg_known_value (unsigned int regno) 1723 { 1724 if (regno >= FIRST_PSEUDO_REGISTER) 1725 { 1726 regno -= FIRST_PSEUDO_REGISTER; 1727 if (regno < vec_safe_length (reg_known_value)) 1728 return (*reg_known_value)[regno]; 1729 } 1730 return NULL; 1731 } 1732 1733 /* Set it. */ 1734 1735 static void 1736 set_reg_known_value (unsigned int regno, rtx val) 1737 { 1738 if (regno >= FIRST_PSEUDO_REGISTER) 1739 { 1740 regno -= FIRST_PSEUDO_REGISTER; 1741 if (regno < vec_safe_length (reg_known_value)) 1742 (*reg_known_value)[regno] = val; 1743 } 1744 } 1745 1746 /* Similarly for reg_known_equiv_p. */ 1747 1748 bool 1749 get_reg_known_equiv_p (unsigned int regno) 1750 { 1751 if (regno >= FIRST_PSEUDO_REGISTER) 1752 { 1753 regno -= FIRST_PSEUDO_REGISTER; 1754 if (regno < vec_safe_length (reg_known_value)) 1755 return bitmap_bit_p (reg_known_equiv_p, regno); 1756 } 1757 return false; 1758 } 1759 1760 static void 1761 set_reg_known_equiv_p (unsigned int regno, bool val) 1762 { 1763 if (regno >= FIRST_PSEUDO_REGISTER) 1764 { 1765 regno -= FIRST_PSEUDO_REGISTER; 1766 if (regno < vec_safe_length (reg_known_value)) 1767 { 1768 if (val) 1769 bitmap_set_bit (reg_known_equiv_p, regno); 1770 else 1771 bitmap_clear_bit (reg_known_equiv_p, regno); 1772 } 1773 } 1774 } 1775 1776 1777 /* Returns a canonical version of X, from the point of view alias 1778 analysis. (For example, if X is a MEM whose address is a register, 1779 and the register has a known value (say a SYMBOL_REF), then a MEM 1780 whose address is the SYMBOL_REF is returned.) */ 1781 1782 rtx 1783 canon_rtx (rtx x) 1784 { 1785 /* Recursively look for equivalences. */ 1786 if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER) 1787 { 1788 rtx t = get_reg_known_value (REGNO (x)); 1789 if (t == x) 1790 return x; 1791 if (t) 1792 return canon_rtx (t); 1793 } 1794 1795 if (GET_CODE (x) == PLUS) 1796 { 1797 rtx x0 = canon_rtx (XEXP (x, 0)); 1798 rtx x1 = canon_rtx (XEXP (x, 1)); 1799 1800 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1)) 1801 return simplify_gen_binary (PLUS, GET_MODE (x), x0, x1); 1802 } 1803 1804 /* This gives us much better alias analysis when called from 1805 the loop optimizer. Note we want to leave the original 1806 MEM alone, but need to return the canonicalized MEM with 1807 all the flags with their original values. */ 1808 else if (MEM_P (x)) 1809 x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0))); 1810 1811 return x; 1812 } 1813 1814 /* Return 1 if X and Y are identical-looking rtx's. 1815 Expect that X and Y has been already canonicalized. 1816 1817 We use the data in reg_known_value above to see if two registers with 1818 different numbers are, in fact, equivalent. */ 1819 1820 static int 1821 rtx_equal_for_memref_p (const_rtx x, const_rtx y) 1822 { 1823 int i; 1824 int j; 1825 enum rtx_code code; 1826 const char *fmt; 1827 1828 if (x == 0 && y == 0) 1829 return 1; 1830 if (x == 0 || y == 0) 1831 return 0; 1832 1833 if (x == y) 1834 return 1; 1835 1836 code = GET_CODE (x); 1837 /* Rtx's of different codes cannot be equal. */ 1838 if (code != GET_CODE (y)) 1839 return 0; 1840 1841 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. 1842 (REG:SI x) and (REG:HI x) are NOT equivalent. */ 1843 1844 if (GET_MODE (x) != GET_MODE (y)) 1845 return 0; 1846 1847 /* Some RTL can be compared without a recursive examination. */ 1848 switch (code) 1849 { 1850 case REG: 1851 return REGNO (x) == REGNO (y); 1852 1853 case LABEL_REF: 1854 return label_ref_label (x) == label_ref_label (y); 1855 1856 case SYMBOL_REF: 1857 { 1858 HOST_WIDE_INT distance = 0; 1859 return (compare_base_symbol_refs (x, y, &distance) == 1 1860 && distance == 0); 1861 } 1862 1863 case ENTRY_VALUE: 1864 /* This is magic, don't go through canonicalization et al. */ 1865 return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y)); 1866 1867 case VALUE: 1868 CASE_CONST_UNIQUE: 1869 /* Pointer equality guarantees equality for these nodes. */ 1870 return 0; 1871 1872 default: 1873 break; 1874 } 1875 1876 /* canon_rtx knows how to handle plus. No need to canonicalize. */ 1877 if (code == PLUS) 1878 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)) 1879 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1))) 1880 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1)) 1881 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0)))); 1882 /* For commutative operations, the RTX match if the operand match in any 1883 order. Also handle the simple binary and unary cases without a loop. */ 1884 if (COMMUTATIVE_P (x)) 1885 { 1886 rtx xop0 = canon_rtx (XEXP (x, 0)); 1887 rtx yop0 = canon_rtx (XEXP (y, 0)); 1888 rtx yop1 = canon_rtx (XEXP (y, 1)); 1889 1890 return ((rtx_equal_for_memref_p (xop0, yop0) 1891 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop1)) 1892 || (rtx_equal_for_memref_p (xop0, yop1) 1893 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), yop0))); 1894 } 1895 else if (NON_COMMUTATIVE_P (x)) 1896 { 1897 return (rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)), 1898 canon_rtx (XEXP (y, 0))) 1899 && rtx_equal_for_memref_p (canon_rtx (XEXP (x, 1)), 1900 canon_rtx (XEXP (y, 1)))); 1901 } 1902 else if (UNARY_P (x)) 1903 return rtx_equal_for_memref_p (canon_rtx (XEXP (x, 0)), 1904 canon_rtx (XEXP (y, 0))); 1905 1906 /* Compare the elements. If any pair of corresponding elements 1907 fail to match, return 0 for the whole things. 1908 1909 Limit cases to types which actually appear in addresses. */ 1910 1911 fmt = GET_RTX_FORMAT (code); 1912 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1913 { 1914 switch (fmt[i]) 1915 { 1916 case 'i': 1917 if (XINT (x, i) != XINT (y, i)) 1918 return 0; 1919 break; 1920 1921 case 'p': 1922 if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y))) 1923 return 0; 1924 break; 1925 1926 case 'E': 1927 /* Two vectors must have the same length. */ 1928 if (XVECLEN (x, i) != XVECLEN (y, i)) 1929 return 0; 1930 1931 /* And the corresponding elements must match. */ 1932 for (j = 0; j < XVECLEN (x, i); j++) 1933 if (rtx_equal_for_memref_p (canon_rtx (XVECEXP (x, i, j)), 1934 canon_rtx (XVECEXP (y, i, j))) == 0) 1935 return 0; 1936 break; 1937 1938 case 'e': 1939 if (rtx_equal_for_memref_p (canon_rtx (XEXP (x, i)), 1940 canon_rtx (XEXP (y, i))) == 0) 1941 return 0; 1942 break; 1943 1944 /* This can happen for asm operands. */ 1945 case 's': 1946 if (strcmp (XSTR (x, i), XSTR (y, i))) 1947 return 0; 1948 break; 1949 1950 /* This can happen for an asm which clobbers memory. */ 1951 case '0': 1952 break; 1953 1954 /* It is believed that rtx's at this level will never 1955 contain anything but integers and other rtx's, 1956 except for within LABEL_REFs and SYMBOL_REFs. */ 1957 default: 1958 gcc_unreachable (); 1959 } 1960 } 1961 return 1; 1962 } 1963 1964 static rtx 1965 find_base_term (rtx x, vec<std::pair<cselib_val *, 1966 struct elt_loc_list *> > &visited_vals) 1967 { 1968 cselib_val *val; 1969 struct elt_loc_list *l, *f; 1970 rtx ret; 1971 scalar_int_mode int_mode; 1972 1973 #if defined (FIND_BASE_TERM) 1974 /* Try machine-dependent ways to find the base term. */ 1975 x = FIND_BASE_TERM (x); 1976 #endif 1977 1978 switch (GET_CODE (x)) 1979 { 1980 case REG: 1981 return REG_BASE_VALUE (x); 1982 1983 case TRUNCATE: 1984 /* As we do not know which address space the pointer is referring to, we can 1985 handle this only if the target does not support different pointer or 1986 address modes depending on the address space. */ 1987 if (!target_default_pointer_address_modes_p ()) 1988 return 0; 1989 if (!is_a <scalar_int_mode> (GET_MODE (x), &int_mode) 1990 || GET_MODE_PRECISION (int_mode) < GET_MODE_PRECISION (Pmode)) 1991 return 0; 1992 /* Fall through. */ 1993 case HIGH: 1994 case PRE_INC: 1995 case PRE_DEC: 1996 case POST_INC: 1997 case POST_DEC: 1998 case PRE_MODIFY: 1999 case POST_MODIFY: 2000 return find_base_term (XEXP (x, 0), visited_vals); 2001 2002 case ZERO_EXTEND: 2003 case SIGN_EXTEND: /* Used for Alpha/NT pointers */ 2004 /* As we do not know which address space the pointer is referring to, we can 2005 handle this only if the target does not support different pointer or 2006 address modes depending on the address space. */ 2007 if (!target_default_pointer_address_modes_p ()) 2008 return 0; 2009 2010 { 2011 rtx temp = find_base_term (XEXP (x, 0), visited_vals); 2012 2013 if (temp != 0 && CONSTANT_P (temp)) 2014 temp = convert_memory_address (Pmode, temp); 2015 2016 return temp; 2017 } 2018 2019 case VALUE: 2020 val = CSELIB_VAL_PTR (x); 2021 ret = NULL_RTX; 2022 2023 if (!val) 2024 return ret; 2025 2026 if (cselib_sp_based_value_p (val)) 2027 return static_reg_base_value[STACK_POINTER_REGNUM]; 2028 2029 if (visited_vals.length () > (unsigned) param_max_find_base_term_values) 2030 return ret; 2031 2032 f = val->locs; 2033 /* Reset val->locs to avoid infinite recursion. */ 2034 if (f) 2035 visited_vals.safe_push (std::make_pair (val, f)); 2036 val->locs = NULL; 2037 2038 for (l = f; l; l = l->next) 2039 if (GET_CODE (l->loc) == VALUE 2040 && CSELIB_VAL_PTR (l->loc)->locs 2041 && !CSELIB_VAL_PTR (l->loc)->locs->next 2042 && CSELIB_VAL_PTR (l->loc)->locs->loc == x) 2043 continue; 2044 else if ((ret = find_base_term (l->loc, visited_vals)) != 0) 2045 break; 2046 2047 return ret; 2048 2049 case LO_SUM: 2050 /* The standard form is (lo_sum reg sym) so look only at the 2051 second operand. */ 2052 return find_base_term (XEXP (x, 1), visited_vals); 2053 2054 case CONST: 2055 x = XEXP (x, 0); 2056 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS) 2057 return 0; 2058 /* Fall through. */ 2059 case PLUS: 2060 case MINUS: 2061 { 2062 rtx tmp1 = XEXP (x, 0); 2063 rtx tmp2 = XEXP (x, 1); 2064 2065 /* This is a little bit tricky since we have to determine which of 2066 the two operands represents the real base address. Otherwise this 2067 routine may return the index register instead of the base register. 2068 2069 That may cause us to believe no aliasing was possible, when in 2070 fact aliasing is possible. 2071 2072 We use a few simple tests to guess the base register. Additional 2073 tests can certainly be added. For example, if one of the operands 2074 is a shift or multiply, then it must be the index register and the 2075 other operand is the base register. */ 2076 2077 if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2)) 2078 return find_base_term (tmp2, visited_vals); 2079 2080 /* If either operand is known to be a pointer, then prefer it 2081 to determine the base term. */ 2082 if (REG_P (tmp1) && REG_POINTER (tmp1)) 2083 ; 2084 else if (REG_P (tmp2) && REG_POINTER (tmp2)) 2085 std::swap (tmp1, tmp2); 2086 /* If second argument is constant which has base term, prefer it 2087 over variable tmp1. See PR64025. */ 2088 else if (CONSTANT_P (tmp2) && !CONST_INT_P (tmp2)) 2089 std::swap (tmp1, tmp2); 2090 2091 /* Go ahead and find the base term for both operands. If either base 2092 term is from a pointer or is a named object or a special address 2093 (like an argument or stack reference), then use it for the 2094 base term. */ 2095 rtx base = find_base_term (tmp1, visited_vals); 2096 if (base != NULL_RTX 2097 && ((REG_P (tmp1) && REG_POINTER (tmp1)) 2098 || known_base_value_p (base))) 2099 return base; 2100 base = find_base_term (tmp2, visited_vals); 2101 if (base != NULL_RTX 2102 && ((REG_P (tmp2) && REG_POINTER (tmp2)) 2103 || known_base_value_p (base))) 2104 return base; 2105 2106 /* We could not determine which of the two operands was the 2107 base register and which was the index. So we can determine 2108 nothing from the base alias check. */ 2109 return 0; 2110 } 2111 2112 case AND: 2113 /* Look through aligning ANDs. And AND with zero or one with 2114 the LSB set isn't one (see for example PR92462). */ 2115 if (CONST_INT_P (XEXP (x, 1)) 2116 && INTVAL (XEXP (x, 1)) != 0 2117 && (INTVAL (XEXP (x, 1)) & 1) == 0) 2118 return find_base_term (XEXP (x, 0), visited_vals); 2119 return 0; 2120 2121 case SYMBOL_REF: 2122 case LABEL_REF: 2123 return x; 2124 2125 default: 2126 return 0; 2127 } 2128 } 2129 2130 /* Wrapper around the worker above which removes locs from visited VALUEs 2131 to avoid visiting them multiple times. We unwind that changes here. */ 2132 2133 static rtx 2134 find_base_term (rtx x) 2135 { 2136 auto_vec<std::pair<cselib_val *, struct elt_loc_list *>, 32> visited_vals; 2137 rtx res = find_base_term (x, visited_vals); 2138 for (unsigned i = 0; i < visited_vals.length (); ++i) 2139 visited_vals[i].first->locs = visited_vals[i].second; 2140 return res; 2141 } 2142 2143 /* Return true if accesses to address X may alias accesses based 2144 on the stack pointer. */ 2145 2146 bool 2147 may_be_sp_based_p (rtx x) 2148 { 2149 rtx base = find_base_term (x); 2150 return !base || base == static_reg_base_value[STACK_POINTER_REGNUM]; 2151 } 2152 2153 /* BASE1 and BASE2 are decls. Return 1 if they refer to same object, 0 2154 if they refer to different objects and -1 if we cannot decide. */ 2155 2156 int 2157 compare_base_decls (tree base1, tree base2) 2158 { 2159 int ret; 2160 gcc_checking_assert (DECL_P (base1) && DECL_P (base2)); 2161 if (base1 == base2) 2162 return 1; 2163 2164 /* If we have two register decls with register specification we 2165 cannot decide unless their assembler names are the same. */ 2166 if (VAR_P (base1) 2167 && VAR_P (base2) 2168 && DECL_HARD_REGISTER (base1) 2169 && DECL_HARD_REGISTER (base2) 2170 && DECL_ASSEMBLER_NAME_SET_P (base1) 2171 && DECL_ASSEMBLER_NAME_SET_P (base2)) 2172 { 2173 if (DECL_ASSEMBLER_NAME_RAW (base1) == DECL_ASSEMBLER_NAME_RAW (base2)) 2174 return 1; 2175 return -1; 2176 } 2177 2178 /* Declarations of non-automatic variables may have aliases. All other 2179 decls are unique. */ 2180 if (!decl_in_symtab_p (base1) 2181 || !decl_in_symtab_p (base2)) 2182 return 0; 2183 2184 /* Don't cause symbols to be inserted by the act of checking. */ 2185 symtab_node *node1 = symtab_node::get (base1); 2186 if (!node1) 2187 return 0; 2188 symtab_node *node2 = symtab_node::get (base2); 2189 if (!node2) 2190 return 0; 2191 2192 ret = node1->equal_address_to (node2, true); 2193 return ret; 2194 } 2195 2196 /* Compare SYMBOL_REFs X_BASE and Y_BASE. 2197 2198 - Return 1 if Y_BASE - X_BASE is constant, adding that constant 2199 to *DISTANCE if DISTANCE is nonnull. 2200 2201 - Return 0 if no accesses based on X_BASE can alias Y_BASE. 2202 2203 - Return -1 if one of the two results applies, but we can't tell 2204 which at compile time. Update DISTANCE in the same way as 2205 for a return value of 1, for the case in which that holds. */ 2206 2207 static int 2208 compare_base_symbol_refs (const_rtx x_base, const_rtx y_base, 2209 HOST_WIDE_INT *distance) 2210 { 2211 tree x_decl = SYMBOL_REF_DECL (x_base); 2212 tree y_decl = SYMBOL_REF_DECL (y_base); 2213 bool binds_def = true; 2214 bool swap = false; 2215 2216 if (XSTR (x_base, 0) == XSTR (y_base, 0)) 2217 return 1; 2218 if (x_decl && y_decl) 2219 return compare_base_decls (x_decl, y_decl); 2220 if (x_decl || y_decl) 2221 { 2222 if (!x_decl) 2223 { 2224 swap = true; 2225 std::swap (x_decl, y_decl); 2226 std::swap (x_base, y_base); 2227 } 2228 /* We handle specially only section anchors. Other symbols are 2229 either equal (via aliasing) or refer to different objects. */ 2230 if (!SYMBOL_REF_HAS_BLOCK_INFO_P (y_base)) 2231 return -1; 2232 /* Anchors contains static VAR_DECLs and CONST_DECLs. We are safe 2233 to ignore CONST_DECLs because they are readonly. */ 2234 if (!VAR_P (x_decl) 2235 || (!TREE_STATIC (x_decl) && !TREE_PUBLIC (x_decl))) 2236 return 0; 2237 2238 symtab_node *x_node = symtab_node::get_create (x_decl) 2239 ->ultimate_alias_target (); 2240 /* External variable cannot be in section anchor. */ 2241 if (!x_node->definition) 2242 return 0; 2243 x_base = XEXP (DECL_RTL (x_node->decl), 0); 2244 /* If not in anchor, we can disambiguate. */ 2245 if (!SYMBOL_REF_HAS_BLOCK_INFO_P (x_base)) 2246 return 0; 2247 2248 /* We have an alias of anchored variable. If it can be interposed; 2249 we must assume it may or may not alias its anchor. */ 2250 binds_def = decl_binds_to_current_def_p (x_decl); 2251 } 2252 /* If we have variable in section anchor, we can compare by offset. */ 2253 if (SYMBOL_REF_HAS_BLOCK_INFO_P (x_base) 2254 && SYMBOL_REF_HAS_BLOCK_INFO_P (y_base)) 2255 { 2256 if (SYMBOL_REF_BLOCK (x_base) != SYMBOL_REF_BLOCK (y_base)) 2257 return 0; 2258 if (distance) 2259 *distance += (swap ? -1 : 1) * (SYMBOL_REF_BLOCK_OFFSET (y_base) 2260 - SYMBOL_REF_BLOCK_OFFSET (x_base)); 2261 return binds_def ? 1 : -1; 2262 } 2263 /* Either the symbols are equal (via aliasing) or they refer to 2264 different objects. */ 2265 return -1; 2266 } 2267 2268 /* Return 0 if the addresses X and Y are known to point to different 2269 objects, 1 if they might be pointers to the same object. */ 2270 2271 static int 2272 base_alias_check (rtx x, rtx x_base, rtx y, rtx y_base, 2273 machine_mode x_mode, machine_mode y_mode) 2274 { 2275 /* If the address itself has no known base see if a known equivalent 2276 value has one. If either address still has no known base, nothing 2277 is known about aliasing. */ 2278 if (x_base == 0) 2279 { 2280 rtx x_c; 2281 2282 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x) 2283 return 1; 2284 2285 x_base = find_base_term (x_c); 2286 if (x_base == 0) 2287 return 1; 2288 } 2289 2290 if (y_base == 0) 2291 { 2292 rtx y_c; 2293 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y) 2294 return 1; 2295 2296 y_base = find_base_term (y_c); 2297 if (y_base == 0) 2298 return 1; 2299 } 2300 2301 /* If the base addresses are equal nothing is known about aliasing. */ 2302 if (rtx_equal_p (x_base, y_base)) 2303 return 1; 2304 2305 /* The base addresses are different expressions. If they are not accessed 2306 via AND, there is no conflict. We can bring knowledge of object 2307 alignment into play here. For example, on alpha, "char a, b;" can 2308 alias one another, though "char a; long b;" cannot. AND addresses may 2309 implicitly alias surrounding objects; i.e. unaligned access in DImode 2310 via AND address can alias all surrounding object types except those 2311 with aligment 8 or higher. */ 2312 if (GET_CODE (x) == AND && GET_CODE (y) == AND) 2313 return 1; 2314 if (GET_CODE (x) == AND 2315 && (!CONST_INT_P (XEXP (x, 1)) 2316 || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1)))) 2317 return 1; 2318 if (GET_CODE (y) == AND 2319 && (!CONST_INT_P (XEXP (y, 1)) 2320 || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1)))) 2321 return 1; 2322 2323 /* Differing symbols not accessed via AND never alias. */ 2324 if (GET_CODE (x_base) == SYMBOL_REF && GET_CODE (y_base) == SYMBOL_REF) 2325 return compare_base_symbol_refs (x_base, y_base) != 0; 2326 2327 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS) 2328 return 0; 2329 2330 if (unique_base_value_p (x_base) || unique_base_value_p (y_base)) 2331 return 0; 2332 2333 return 1; 2334 } 2335 2336 /* Return TRUE if EXPR refers to a VALUE whose uid is greater than 2337 (or equal to) that of V. */ 2338 2339 static bool 2340 refs_newer_value_p (const_rtx expr, rtx v) 2341 { 2342 int minuid = CSELIB_VAL_PTR (v)->uid; 2343 subrtx_iterator::array_type array; 2344 FOR_EACH_SUBRTX (iter, array, expr, NONCONST) 2345 if (GET_CODE (*iter) == VALUE && CSELIB_VAL_PTR (*iter)->uid >= minuid) 2346 return true; 2347 return false; 2348 } 2349 2350 /* Convert the address X into something we can use. This is done by returning 2351 it unchanged unless it is a VALUE or VALUE +/- constant; for VALUE 2352 we call cselib to get a more useful rtx. */ 2353 2354 rtx 2355 get_addr (rtx x) 2356 { 2357 cselib_val *v; 2358 struct elt_loc_list *l; 2359 2360 if (GET_CODE (x) != VALUE) 2361 { 2362 if ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS) 2363 && GET_CODE (XEXP (x, 0)) == VALUE 2364 && CONST_SCALAR_INT_P (XEXP (x, 1))) 2365 { 2366 rtx op0 = get_addr (XEXP (x, 0)); 2367 if (op0 != XEXP (x, 0)) 2368 { 2369 poly_int64 c; 2370 if (GET_CODE (x) == PLUS 2371 && poly_int_rtx_p (XEXP (x, 1), &c)) 2372 return plus_constant (GET_MODE (x), op0, c); 2373 return simplify_gen_binary (GET_CODE (x), GET_MODE (x), 2374 op0, XEXP (x, 1)); 2375 } 2376 } 2377 return x; 2378 } 2379 v = CSELIB_VAL_PTR (x); 2380 if (v) 2381 { 2382 bool have_equivs = cselib_have_permanent_equivalences (); 2383 if (have_equivs) 2384 v = canonical_cselib_val (v); 2385 for (l = v->locs; l; l = l->next) 2386 if (CONSTANT_P (l->loc)) 2387 return l->loc; 2388 for (l = v->locs; l; l = l->next) 2389 if (!REG_P (l->loc) && !MEM_P (l->loc) 2390 /* Avoid infinite recursion when potentially dealing with 2391 var-tracking artificial equivalences, by skipping the 2392 equivalences themselves, and not choosing expressions 2393 that refer to newer VALUEs. */ 2394 && (!have_equivs 2395 || (GET_CODE (l->loc) != VALUE 2396 && !refs_newer_value_p (l->loc, x)))) 2397 return l->loc; 2398 if (have_equivs) 2399 { 2400 for (l = v->locs; l; l = l->next) 2401 if (REG_P (l->loc) 2402 || (GET_CODE (l->loc) != VALUE 2403 && !refs_newer_value_p (l->loc, x))) 2404 return l->loc; 2405 /* Return the canonical value. */ 2406 return v->val_rtx; 2407 } 2408 if (v->locs) 2409 return v->locs->loc; 2410 } 2411 return x; 2412 } 2413 2414 /* Return the address of the (N_REFS + 1)th memory reference to ADDR 2415 where SIZE is the size in bytes of the memory reference. If ADDR 2416 is not modified by the memory reference then ADDR is returned. */ 2417 2418 static rtx 2419 addr_side_effect_eval (rtx addr, poly_int64 size, int n_refs) 2420 { 2421 poly_int64 offset = 0; 2422 2423 switch (GET_CODE (addr)) 2424 { 2425 case PRE_INC: 2426 offset = (n_refs + 1) * size; 2427 break; 2428 case PRE_DEC: 2429 offset = -(n_refs + 1) * size; 2430 break; 2431 case POST_INC: 2432 offset = n_refs * size; 2433 break; 2434 case POST_DEC: 2435 offset = -n_refs * size; 2436 break; 2437 2438 default: 2439 return addr; 2440 } 2441 2442 addr = plus_constant (GET_MODE (addr), XEXP (addr, 0), offset); 2443 addr = canon_rtx (addr); 2444 2445 return addr; 2446 } 2447 2448 /* Return TRUE if an object X sized at XSIZE bytes and another object 2449 Y sized at YSIZE bytes, starting C bytes after X, may overlap. If 2450 any of the sizes is zero, assume an overlap, otherwise use the 2451 absolute value of the sizes as the actual sizes. */ 2452 2453 static inline bool 2454 offset_overlap_p (poly_int64 c, poly_int64 xsize, poly_int64 ysize) 2455 { 2456 if (known_eq (xsize, 0) || known_eq (ysize, 0)) 2457 return true; 2458 2459 if (maybe_ge (c, 0)) 2460 return maybe_gt (maybe_lt (xsize, 0) ? -xsize : xsize, c); 2461 else 2462 return maybe_gt (maybe_lt (ysize, 0) ? -ysize : ysize, -c); 2463 } 2464 2465 /* Return one if X and Y (memory addresses) reference the 2466 same location in memory or if the references overlap. 2467 Return zero if they do not overlap, else return 2468 minus one in which case they still might reference the same location. 2469 2470 C is an offset accumulator. When 2471 C is nonzero, we are testing aliases between X and Y + C. 2472 XSIZE is the size in bytes of the X reference, 2473 similarly YSIZE is the size in bytes for Y. 2474 Expect that canon_rtx has been already called for X and Y. 2475 2476 If XSIZE or YSIZE is zero, we do not know the amount of memory being 2477 referenced (the reference was BLKmode), so make the most pessimistic 2478 assumptions. 2479 2480 If XSIZE or YSIZE is negative, we may access memory outside the object 2481 being referenced as a side effect. This can happen when using AND to 2482 align memory references, as is done on the Alpha. 2483 2484 Nice to notice that varying addresses cannot conflict with fp if no 2485 local variables had their addresses taken, but that's too hard now. 2486 2487 ??? Contrary to the tree alias oracle this does not return 2488 one for X + non-constant and Y + non-constant when X and Y are equal. 2489 If that is fixed the TBAA hack for union type-punning can be removed. */ 2490 2491 static int 2492 memrefs_conflict_p (poly_int64 xsize, rtx x, poly_int64 ysize, rtx y, 2493 poly_int64 c) 2494 { 2495 if (GET_CODE (x) == VALUE) 2496 { 2497 if (REG_P (y)) 2498 { 2499 struct elt_loc_list *l = NULL; 2500 if (CSELIB_VAL_PTR (x)) 2501 for (l = canonical_cselib_val (CSELIB_VAL_PTR (x))->locs; 2502 l; l = l->next) 2503 if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, y)) 2504 break; 2505 if (l) 2506 x = y; 2507 else 2508 x = get_addr (x); 2509 } 2510 /* Don't call get_addr if y is the same VALUE. */ 2511 else if (x != y) 2512 x = get_addr (x); 2513 } 2514 if (GET_CODE (y) == VALUE) 2515 { 2516 if (REG_P (x)) 2517 { 2518 struct elt_loc_list *l = NULL; 2519 if (CSELIB_VAL_PTR (y)) 2520 for (l = canonical_cselib_val (CSELIB_VAL_PTR (y))->locs; 2521 l; l = l->next) 2522 if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, x)) 2523 break; 2524 if (l) 2525 y = x; 2526 else 2527 y = get_addr (y); 2528 } 2529 /* Don't call get_addr if x is the same VALUE. */ 2530 else if (y != x) 2531 y = get_addr (y); 2532 } 2533 if (GET_CODE (x) == HIGH) 2534 x = XEXP (x, 0); 2535 else if (GET_CODE (x) == LO_SUM) 2536 x = XEXP (x, 1); 2537 else 2538 x = addr_side_effect_eval (x, maybe_lt (xsize, 0) ? -xsize : xsize, 0); 2539 if (GET_CODE (y) == HIGH) 2540 y = XEXP (y, 0); 2541 else if (GET_CODE (y) == LO_SUM) 2542 y = XEXP (y, 1); 2543 else 2544 y = addr_side_effect_eval (y, maybe_lt (ysize, 0) ? -ysize : ysize, 0); 2545 2546 if (GET_CODE (x) == SYMBOL_REF && GET_CODE (y) == SYMBOL_REF) 2547 { 2548 HOST_WIDE_INT distance = 0; 2549 int cmp = compare_base_symbol_refs (x, y, &distance); 2550 2551 /* If both decls are the same, decide by offsets. */ 2552 if (cmp == 1) 2553 return offset_overlap_p (c + distance, xsize, ysize); 2554 /* Assume a potential overlap for symbolic addresses that went 2555 through alignment adjustments (i.e., that have negative 2556 sizes), because we can't know how far they are from each 2557 other. */ 2558 if (maybe_lt (xsize, 0) || maybe_lt (ysize, 0)) 2559 return -1; 2560 /* If decls are different or we know by offsets that there is no overlap, 2561 we win. */ 2562 if (!cmp || !offset_overlap_p (c + distance, xsize, ysize)) 2563 return 0; 2564 /* Decls may or may not be different and offsets overlap....*/ 2565 return -1; 2566 } 2567 else if (rtx_equal_for_memref_p (x, y)) 2568 { 2569 return offset_overlap_p (c, xsize, ysize); 2570 } 2571 2572 /* This code used to check for conflicts involving stack references and 2573 globals but the base address alias code now handles these cases. */ 2574 2575 if (GET_CODE (x) == PLUS) 2576 { 2577 /* The fact that X is canonicalized means that this 2578 PLUS rtx is canonicalized. */ 2579 rtx x0 = XEXP (x, 0); 2580 rtx x1 = XEXP (x, 1); 2581 2582 /* However, VALUEs might end up in different positions even in 2583 canonical PLUSes. Comparing their addresses is enough. */ 2584 if (x0 == y) 2585 return memrefs_conflict_p (xsize, x1, ysize, const0_rtx, c); 2586 else if (x1 == y) 2587 return memrefs_conflict_p (xsize, x0, ysize, const0_rtx, c); 2588 2589 poly_int64 cx1, cy1; 2590 if (GET_CODE (y) == PLUS) 2591 { 2592 /* The fact that Y is canonicalized means that this 2593 PLUS rtx is canonicalized. */ 2594 rtx y0 = XEXP (y, 0); 2595 rtx y1 = XEXP (y, 1); 2596 2597 if (x0 == y1) 2598 return memrefs_conflict_p (xsize, x1, ysize, y0, c); 2599 if (x1 == y0) 2600 return memrefs_conflict_p (xsize, x0, ysize, y1, c); 2601 2602 if (rtx_equal_for_memref_p (x1, y1)) 2603 return memrefs_conflict_p (xsize, x0, ysize, y0, c); 2604 if (rtx_equal_for_memref_p (x0, y0)) 2605 return memrefs_conflict_p (xsize, x1, ysize, y1, c); 2606 if (poly_int_rtx_p (x1, &cx1)) 2607 { 2608 if (poly_int_rtx_p (y1, &cy1)) 2609 return memrefs_conflict_p (xsize, x0, ysize, y0, 2610 c - cx1 + cy1); 2611 else 2612 return memrefs_conflict_p (xsize, x0, ysize, y, c - cx1); 2613 } 2614 else if (poly_int_rtx_p (y1, &cy1)) 2615 return memrefs_conflict_p (xsize, x, ysize, y0, c + cy1); 2616 2617 return -1; 2618 } 2619 else if (poly_int_rtx_p (x1, &cx1)) 2620 return memrefs_conflict_p (xsize, x0, ysize, y, c - cx1); 2621 } 2622 else if (GET_CODE (y) == PLUS) 2623 { 2624 /* The fact that Y is canonicalized means that this 2625 PLUS rtx is canonicalized. */ 2626 rtx y0 = XEXP (y, 0); 2627 rtx y1 = XEXP (y, 1); 2628 2629 if (x == y0) 2630 return memrefs_conflict_p (xsize, const0_rtx, ysize, y1, c); 2631 if (x == y1) 2632 return memrefs_conflict_p (xsize, const0_rtx, ysize, y0, c); 2633 2634 poly_int64 cy1; 2635 if (poly_int_rtx_p (y1, &cy1)) 2636 return memrefs_conflict_p (xsize, x, ysize, y0, c + cy1); 2637 else 2638 return -1; 2639 } 2640 2641 if (GET_CODE (x) == GET_CODE (y)) 2642 switch (GET_CODE (x)) 2643 { 2644 case MULT: 2645 { 2646 /* Handle cases where we expect the second operands to be the 2647 same, and check only whether the first operand would conflict 2648 or not. */ 2649 rtx x0, y0; 2650 rtx x1 = canon_rtx (XEXP (x, 1)); 2651 rtx y1 = canon_rtx (XEXP (y, 1)); 2652 if (! rtx_equal_for_memref_p (x1, y1)) 2653 return -1; 2654 x0 = canon_rtx (XEXP (x, 0)); 2655 y0 = canon_rtx (XEXP (y, 0)); 2656 if (rtx_equal_for_memref_p (x0, y0)) 2657 return offset_overlap_p (c, xsize, ysize); 2658 2659 /* Can't properly adjust our sizes. */ 2660 poly_int64 c1; 2661 if (!poly_int_rtx_p (x1, &c1) 2662 || !can_div_trunc_p (xsize, c1, &xsize) 2663 || !can_div_trunc_p (ysize, c1, &ysize) 2664 || !can_div_trunc_p (c, c1, &c)) 2665 return -1; 2666 return memrefs_conflict_p (xsize, x0, ysize, y0, c); 2667 } 2668 2669 default: 2670 break; 2671 } 2672 2673 /* Deal with alignment ANDs by adjusting offset and size so as to 2674 cover the maximum range, without taking any previously known 2675 alignment into account. Make a size negative after such an 2676 adjustments, so that, if we end up with e.g. two SYMBOL_REFs, we 2677 assume a potential overlap, because they may end up in contiguous 2678 memory locations and the stricter-alignment access may span over 2679 part of both. */ 2680 if (GET_CODE (x) == AND && CONST_INT_P (XEXP (x, 1))) 2681 { 2682 HOST_WIDE_INT sc = INTVAL (XEXP (x, 1)); 2683 unsigned HOST_WIDE_INT uc = sc; 2684 if (sc < 0 && pow2_or_zerop (-uc)) 2685 { 2686 if (maybe_gt (xsize, 0)) 2687 xsize = -xsize; 2688 if (maybe_ne (xsize, 0)) 2689 xsize += sc + 1; 2690 c -= sc + 1; 2691 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 2692 ysize, y, c); 2693 } 2694 } 2695 if (GET_CODE (y) == AND && CONST_INT_P (XEXP (y, 1))) 2696 { 2697 HOST_WIDE_INT sc = INTVAL (XEXP (y, 1)); 2698 unsigned HOST_WIDE_INT uc = sc; 2699 if (sc < 0 && pow2_or_zerop (-uc)) 2700 { 2701 if (maybe_gt (ysize, 0)) 2702 ysize = -ysize; 2703 if (maybe_ne (ysize, 0)) 2704 ysize += sc + 1; 2705 c += sc + 1; 2706 return memrefs_conflict_p (xsize, x, 2707 ysize, canon_rtx (XEXP (y, 0)), c); 2708 } 2709 } 2710 2711 if (CONSTANT_P (x)) 2712 { 2713 poly_int64 cx, cy; 2714 if (poly_int_rtx_p (x, &cx) && poly_int_rtx_p (y, &cy)) 2715 { 2716 c += cy - cx; 2717 return offset_overlap_p (c, xsize, ysize); 2718 } 2719 2720 if (GET_CODE (x) == CONST) 2721 { 2722 if (GET_CODE (y) == CONST) 2723 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 2724 ysize, canon_rtx (XEXP (y, 0)), c); 2725 else 2726 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 2727 ysize, y, c); 2728 } 2729 if (GET_CODE (y) == CONST) 2730 return memrefs_conflict_p (xsize, x, ysize, 2731 canon_rtx (XEXP (y, 0)), c); 2732 2733 /* Assume a potential overlap for symbolic addresses that went 2734 through alignment adjustments (i.e., that have negative 2735 sizes), because we can't know how far they are from each 2736 other. */ 2737 if (CONSTANT_P (y)) 2738 return (maybe_lt (xsize, 0) 2739 || maybe_lt (ysize, 0) 2740 || offset_overlap_p (c, xsize, ysize)); 2741 2742 return -1; 2743 } 2744 2745 return -1; 2746 } 2747 2748 /* Functions to compute memory dependencies. 2749 2750 Since we process the insns in execution order, we can build tables 2751 to keep track of what registers are fixed (and not aliased), what registers 2752 are varying in known ways, and what registers are varying in unknown 2753 ways. 2754 2755 If both memory references are volatile, then there must always be a 2756 dependence between the two references, since their order cannot be 2757 changed. A volatile and non-volatile reference can be interchanged 2758 though. 2759 2760 We also must allow AND addresses, because they may generate accesses 2761 outside the object being referenced. This is used to generate aligned 2762 addresses from unaligned addresses, for instance, the alpha 2763 storeqi_unaligned pattern. */ 2764 2765 /* Read dependence: X is read after read in MEM takes place. There can 2766 only be a dependence here if both reads are volatile, or if either is 2767 an explicit barrier. */ 2768 2769 int 2770 read_dependence (const_rtx mem, const_rtx x) 2771 { 2772 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 2773 return true; 2774 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER 2775 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER) 2776 return true; 2777 return false; 2778 } 2779 2780 /* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */ 2781 2782 static tree 2783 decl_for_component_ref (tree x) 2784 { 2785 do 2786 { 2787 x = TREE_OPERAND (x, 0); 2788 } 2789 while (x && TREE_CODE (x) == COMPONENT_REF); 2790 2791 return x && DECL_P (x) ? x : NULL_TREE; 2792 } 2793 2794 /* Walk up the COMPONENT_REF list in X and adjust *OFFSET to compensate 2795 for the offset of the field reference. *KNOWN_P says whether the 2796 offset is known. */ 2797 2798 static void 2799 adjust_offset_for_component_ref (tree x, bool *known_p, 2800 poly_int64 *offset) 2801 { 2802 if (!*known_p) 2803 return; 2804 do 2805 { 2806 tree xoffset = component_ref_field_offset (x); 2807 tree field = TREE_OPERAND (x, 1); 2808 if (!poly_int_tree_p (xoffset)) 2809 { 2810 *known_p = false; 2811 return; 2812 } 2813 2814 poly_offset_int woffset 2815 = (wi::to_poly_offset (xoffset) 2816 + (wi::to_offset (DECL_FIELD_BIT_OFFSET (field)) 2817 >> LOG2_BITS_PER_UNIT) 2818 + *offset); 2819 if (!woffset.to_shwi (offset)) 2820 { 2821 *known_p = false; 2822 return; 2823 } 2824 2825 x = TREE_OPERAND (x, 0); 2826 } 2827 while (x && TREE_CODE (x) == COMPONENT_REF); 2828 } 2829 2830 /* Return nonzero if we can determine the exprs corresponding to memrefs 2831 X and Y and they do not overlap. 2832 If LOOP_VARIANT is set, skip offset-based disambiguation */ 2833 2834 int 2835 nonoverlapping_memrefs_p (const_rtx x, const_rtx y, bool loop_invariant) 2836 { 2837 tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y); 2838 rtx rtlx, rtly; 2839 rtx basex, basey; 2840 bool moffsetx_known_p, moffsety_known_p; 2841 poly_int64 moffsetx = 0, moffsety = 0; 2842 poly_int64 offsetx = 0, offsety = 0, sizex, sizey; 2843 2844 /* Unless both have exprs, we can't tell anything. */ 2845 if (exprx == 0 || expry == 0) 2846 return 0; 2847 2848 /* For spill-slot accesses make sure we have valid offsets. */ 2849 if ((exprx == get_spill_slot_decl (false) 2850 && ! MEM_OFFSET_KNOWN_P (x)) 2851 || (expry == get_spill_slot_decl (false) 2852 && ! MEM_OFFSET_KNOWN_P (y))) 2853 return 0; 2854 2855 /* If the field reference test failed, look at the DECLs involved. */ 2856 moffsetx_known_p = MEM_OFFSET_KNOWN_P (x); 2857 if (moffsetx_known_p) 2858 moffsetx = MEM_OFFSET (x); 2859 if (TREE_CODE (exprx) == COMPONENT_REF) 2860 { 2861 tree t = decl_for_component_ref (exprx); 2862 if (! t) 2863 return 0; 2864 adjust_offset_for_component_ref (exprx, &moffsetx_known_p, &moffsetx); 2865 exprx = t; 2866 } 2867 2868 moffsety_known_p = MEM_OFFSET_KNOWN_P (y); 2869 if (moffsety_known_p) 2870 moffsety = MEM_OFFSET (y); 2871 if (TREE_CODE (expry) == COMPONENT_REF) 2872 { 2873 tree t = decl_for_component_ref (expry); 2874 if (! t) 2875 return 0; 2876 adjust_offset_for_component_ref (expry, &moffsety_known_p, &moffsety); 2877 expry = t; 2878 } 2879 2880 if (! DECL_P (exprx) || ! DECL_P (expry)) 2881 return 0; 2882 2883 /* If we refer to different gimple registers, or one gimple register 2884 and one non-gimple-register, we know they can't overlap. First, 2885 gimple registers don't have their addresses taken. Now, there 2886 could be more than one stack slot for (different versions of) the 2887 same gimple register, but we can presumably tell they don't 2888 overlap based on offsets from stack base addresses elsewhere. 2889 It's important that we don't proceed to DECL_RTL, because gimple 2890 registers may not pass DECL_RTL_SET_P, and make_decl_rtl won't be 2891 able to do anything about them since no SSA information will have 2892 remained to guide it. */ 2893 if (is_gimple_reg (exprx) || is_gimple_reg (expry)) 2894 return exprx != expry 2895 || (moffsetx_known_p && moffsety_known_p 2896 && MEM_SIZE_KNOWN_P (x) && MEM_SIZE_KNOWN_P (y) 2897 && !offset_overlap_p (moffsety - moffsetx, 2898 MEM_SIZE (x), MEM_SIZE (y))); 2899 2900 /* With invalid code we can end up storing into the constant pool. 2901 Bail out to avoid ICEing when creating RTL for this. 2902 See gfortran.dg/lto/20091028-2_0.f90. */ 2903 if (TREE_CODE (exprx) == CONST_DECL 2904 || TREE_CODE (expry) == CONST_DECL) 2905 return 1; 2906 2907 /* If one decl is known to be a function or label in a function and 2908 the other is some kind of data, they can't overlap. */ 2909 if ((TREE_CODE (exprx) == FUNCTION_DECL 2910 || TREE_CODE (exprx) == LABEL_DECL) 2911 != (TREE_CODE (expry) == FUNCTION_DECL 2912 || TREE_CODE (expry) == LABEL_DECL)) 2913 return 1; 2914 2915 /* If either of the decls doesn't have DECL_RTL set (e.g. marked as 2916 living in multiple places), we can't tell anything. Exception 2917 are FUNCTION_DECLs for which we can create DECL_RTL on demand. */ 2918 if ((!DECL_RTL_SET_P (exprx) && TREE_CODE (exprx) != FUNCTION_DECL) 2919 || (!DECL_RTL_SET_P (expry) && TREE_CODE (expry) != FUNCTION_DECL)) 2920 return 0; 2921 2922 rtlx = DECL_RTL (exprx); 2923 rtly = DECL_RTL (expry); 2924 2925 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they 2926 can't overlap unless they are the same because we never reuse that part 2927 of the stack frame used for locals for spilled pseudos. */ 2928 if ((!MEM_P (rtlx) || !MEM_P (rtly)) 2929 && ! rtx_equal_p (rtlx, rtly)) 2930 return 1; 2931 2932 /* If we have MEMs referring to different address spaces (which can 2933 potentially overlap), we cannot easily tell from the addresses 2934 whether the references overlap. */ 2935 if (MEM_P (rtlx) && MEM_P (rtly) 2936 && MEM_ADDR_SPACE (rtlx) != MEM_ADDR_SPACE (rtly)) 2937 return 0; 2938 2939 /* Get the base and offsets of both decls. If either is a register, we 2940 know both are and are the same, so use that as the base. The only 2941 we can avoid overlap is if we can deduce that they are nonoverlapping 2942 pieces of that decl, which is very rare. */ 2943 basex = MEM_P (rtlx) ? XEXP (rtlx, 0) : rtlx; 2944 basex = strip_offset_and_add (basex, &offsetx); 2945 2946 basey = MEM_P (rtly) ? XEXP (rtly, 0) : rtly; 2947 basey = strip_offset_and_add (basey, &offsety); 2948 2949 /* If the bases are different, we know they do not overlap if both 2950 are constants or if one is a constant and the other a pointer into the 2951 stack frame. Otherwise a different base means we can't tell if they 2952 overlap or not. */ 2953 if (compare_base_decls (exprx, expry) == 0) 2954 return ((CONSTANT_P (basex) && CONSTANT_P (basey)) 2955 || (CONSTANT_P (basex) && REG_P (basey) 2956 && REGNO_PTR_FRAME_P (REGNO (basey))) 2957 || (CONSTANT_P (basey) && REG_P (basex) 2958 && REGNO_PTR_FRAME_P (REGNO (basex)))); 2959 2960 /* Offset based disambiguation not appropriate for loop invariant */ 2961 if (loop_invariant) 2962 return 0; 2963 2964 /* Offset based disambiguation is OK even if we do not know that the 2965 declarations are necessarily different 2966 (i.e. compare_base_decls (exprx, expry) == -1) */ 2967 2968 sizex = (!MEM_P (rtlx) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtlx))) 2969 : MEM_SIZE_KNOWN_P (rtlx) ? MEM_SIZE (rtlx) 2970 : -1); 2971 sizey = (!MEM_P (rtly) ? poly_int64 (GET_MODE_SIZE (GET_MODE (rtly))) 2972 : MEM_SIZE_KNOWN_P (rtly) ? MEM_SIZE (rtly) 2973 : -1); 2974 2975 /* If we have an offset for either memref, it can update the values computed 2976 above. */ 2977 if (moffsetx_known_p) 2978 offsetx += moffsetx, sizex -= moffsetx; 2979 if (moffsety_known_p) 2980 offsety += moffsety, sizey -= moffsety; 2981 2982 /* If a memref has both a size and an offset, we can use the smaller size. 2983 We can't do this if the offset isn't known because we must view this 2984 memref as being anywhere inside the DECL's MEM. */ 2985 if (MEM_SIZE_KNOWN_P (x) && moffsetx_known_p) 2986 sizex = MEM_SIZE (x); 2987 if (MEM_SIZE_KNOWN_P (y) && moffsety_known_p) 2988 sizey = MEM_SIZE (y); 2989 2990 return !ranges_maybe_overlap_p (offsetx, sizex, offsety, sizey); 2991 } 2992 2993 /* Helper for true_dependence and canon_true_dependence. 2994 Checks for true dependence: X is read after store in MEM takes place. 2995 2996 If MEM_CANONICALIZED is FALSE, then X_ADDR and MEM_ADDR should be 2997 NULL_RTX, and the canonical addresses of MEM and X are both computed 2998 here. If MEM_CANONICALIZED, then MEM must be already canonicalized. 2999 3000 If X_ADDR is non-NULL, it is used in preference of XEXP (x, 0). 3001 3002 Returns 1 if there is a true dependence, 0 otherwise. */ 3003 3004 static int 3005 true_dependence_1 (const_rtx mem, machine_mode mem_mode, rtx mem_addr, 3006 const_rtx x, rtx x_addr, bool mem_canonicalized) 3007 { 3008 rtx true_mem_addr; 3009 rtx base; 3010 int ret; 3011 3012 gcc_checking_assert (mem_canonicalized ? (mem_addr != NULL_RTX) 3013 : (mem_addr == NULL_RTX && x_addr == NULL_RTX)); 3014 3015 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 3016 return 1; 3017 3018 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 3019 This is used in epilogue deallocation functions, and in cselib. */ 3020 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 3021 return 1; 3022 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 3023 return 1; 3024 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER 3025 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER) 3026 return 1; 3027 3028 if (! x_addr) 3029 x_addr = XEXP (x, 0); 3030 x_addr = get_addr (x_addr); 3031 3032 if (! mem_addr) 3033 { 3034 mem_addr = XEXP (mem, 0); 3035 if (mem_mode == VOIDmode) 3036 mem_mode = GET_MODE (mem); 3037 } 3038 true_mem_addr = get_addr (mem_addr); 3039 3040 /* Read-only memory is by definition never modified, and therefore can't 3041 conflict with anything. However, don't assume anything when AND 3042 addresses are involved and leave to the code below to determine 3043 dependence. We don't expect to find read-only set on MEM, but 3044 stupid user tricks can produce them, so don't die. */ 3045 if (MEM_READONLY_P (x) 3046 && GET_CODE (x_addr) != AND 3047 && GET_CODE (true_mem_addr) != AND) 3048 return 0; 3049 3050 /* If we have MEMs referring to different address spaces (which can 3051 potentially overlap), we cannot easily tell from the addresses 3052 whether the references overlap. */ 3053 if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x)) 3054 return 1; 3055 3056 base = find_base_term (x_addr); 3057 if (base && (GET_CODE (base) == LABEL_REF 3058 || (GET_CODE (base) == SYMBOL_REF 3059 && CONSTANT_POOL_ADDRESS_P (base)))) 3060 return 0; 3061 3062 rtx mem_base = find_base_term (true_mem_addr); 3063 if (! base_alias_check (x_addr, base, true_mem_addr, mem_base, 3064 GET_MODE (x), mem_mode)) 3065 return 0; 3066 3067 x_addr = canon_rtx (x_addr); 3068 if (!mem_canonicalized) 3069 mem_addr = canon_rtx (true_mem_addr); 3070 3071 if ((ret = memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr, 3072 SIZE_FOR_MODE (x), x_addr, 0)) != -1) 3073 return ret; 3074 3075 if (mems_in_disjoint_alias_sets_p (x, mem)) 3076 return 0; 3077 3078 if (nonoverlapping_memrefs_p (mem, x, false)) 3079 return 0; 3080 3081 return rtx_refs_may_alias_p (x, mem, true); 3082 } 3083 3084 /* True dependence: X is read after store in MEM takes place. */ 3085 3086 int 3087 true_dependence (const_rtx mem, machine_mode mem_mode, const_rtx x) 3088 { 3089 return true_dependence_1 (mem, mem_mode, NULL_RTX, 3090 x, NULL_RTX, /*mem_canonicalized=*/false); 3091 } 3092 3093 /* Canonical true dependence: X is read after store in MEM takes place. 3094 Variant of true_dependence which assumes MEM has already been 3095 canonicalized (hence we no longer do that here). 3096 The mem_addr argument has been added, since true_dependence_1 computed 3097 this value prior to canonicalizing. */ 3098 3099 int 3100 canon_true_dependence (const_rtx mem, machine_mode mem_mode, rtx mem_addr, 3101 const_rtx x, rtx x_addr) 3102 { 3103 return true_dependence_1 (mem, mem_mode, mem_addr, 3104 x, x_addr, /*mem_canonicalized=*/true); 3105 } 3106 3107 /* Returns nonzero if a write to X might alias a previous read from 3108 (or, if WRITEP is true, a write to) MEM. 3109 If X_CANONCALIZED is true, then X_ADDR is the canonicalized address of X, 3110 and X_MODE the mode for that access. 3111 If MEM_CANONICALIZED is true, MEM is canonicalized. */ 3112 3113 static int 3114 write_dependence_p (const_rtx mem, 3115 const_rtx x, machine_mode x_mode, rtx x_addr, 3116 bool mem_canonicalized, bool x_canonicalized, bool writep) 3117 { 3118 rtx mem_addr; 3119 rtx true_mem_addr, true_x_addr; 3120 rtx base; 3121 int ret; 3122 3123 gcc_checking_assert (x_canonicalized 3124 ? (x_addr != NULL_RTX 3125 && (x_mode != VOIDmode || GET_MODE (x) == VOIDmode)) 3126 : (x_addr == NULL_RTX && x_mode == VOIDmode)); 3127 3128 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 3129 return 1; 3130 3131 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 3132 This is used in epilogue deallocation functions. */ 3133 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 3134 return 1; 3135 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 3136 return 1; 3137 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER 3138 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER) 3139 return 1; 3140 3141 if (!x_addr) 3142 x_addr = XEXP (x, 0); 3143 true_x_addr = get_addr (x_addr); 3144 3145 mem_addr = XEXP (mem, 0); 3146 true_mem_addr = get_addr (mem_addr); 3147 3148 /* A read from read-only memory can't conflict with read-write memory. 3149 Don't assume anything when AND addresses are involved and leave to 3150 the code below to determine dependence. */ 3151 if (!writep 3152 && MEM_READONLY_P (mem) 3153 && GET_CODE (true_x_addr) != AND 3154 && GET_CODE (true_mem_addr) != AND) 3155 return 0; 3156 3157 /* If we have MEMs referring to different address spaces (which can 3158 potentially overlap), we cannot easily tell from the addresses 3159 whether the references overlap. */ 3160 if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x)) 3161 return 1; 3162 3163 base = find_base_term (true_mem_addr); 3164 if (! writep 3165 && base 3166 && (GET_CODE (base) == LABEL_REF 3167 || (GET_CODE (base) == SYMBOL_REF 3168 && CONSTANT_POOL_ADDRESS_P (base)))) 3169 return 0; 3170 3171 rtx x_base = find_base_term (true_x_addr); 3172 if (! base_alias_check (true_x_addr, x_base, true_mem_addr, base, 3173 GET_MODE (x), GET_MODE (mem))) 3174 return 0; 3175 3176 if (!x_canonicalized) 3177 { 3178 x_addr = canon_rtx (true_x_addr); 3179 x_mode = GET_MODE (x); 3180 } 3181 if (!mem_canonicalized) 3182 mem_addr = canon_rtx (true_mem_addr); 3183 3184 if ((ret = memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr, 3185 GET_MODE_SIZE (x_mode), x_addr, 0)) != -1) 3186 return ret; 3187 3188 if (nonoverlapping_memrefs_p (x, mem, false)) 3189 return 0; 3190 3191 return rtx_refs_may_alias_p (x, mem, false); 3192 } 3193 3194 /* Anti dependence: X is written after read in MEM takes place. */ 3195 3196 int 3197 anti_dependence (const_rtx mem, const_rtx x) 3198 { 3199 return write_dependence_p (mem, x, VOIDmode, NULL_RTX, 3200 /*mem_canonicalized=*/false, 3201 /*x_canonicalized*/false, /*writep=*/false); 3202 } 3203 3204 /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X. 3205 Also, consider X in X_MODE (which might be from an enclosing 3206 STRICT_LOW_PART / ZERO_EXTRACT). 3207 If MEM_CANONICALIZED is true, MEM is canonicalized. */ 3208 3209 int 3210 canon_anti_dependence (const_rtx mem, bool mem_canonicalized, 3211 const_rtx x, machine_mode x_mode, rtx x_addr) 3212 { 3213 return write_dependence_p (mem, x, x_mode, x_addr, 3214 mem_canonicalized, /*x_canonicalized=*/true, 3215 /*writep=*/false); 3216 } 3217 3218 /* Output dependence: X is written after store in MEM takes place. */ 3219 3220 int 3221 output_dependence (const_rtx mem, const_rtx x) 3222 { 3223 return write_dependence_p (mem, x, VOIDmode, NULL_RTX, 3224 /*mem_canonicalized=*/false, 3225 /*x_canonicalized*/false, /*writep=*/true); 3226 } 3227 3228 /* Likewise, but we already have a canonicalized MEM, and X_ADDR for X. 3229 Also, consider X in X_MODE (which might be from an enclosing 3230 STRICT_LOW_PART / ZERO_EXTRACT). 3231 If MEM_CANONICALIZED is true, MEM is canonicalized. */ 3232 3233 int 3234 canon_output_dependence (const_rtx mem, bool mem_canonicalized, 3235 const_rtx x, machine_mode x_mode, rtx x_addr) 3236 { 3237 return write_dependence_p (mem, x, x_mode, x_addr, 3238 mem_canonicalized, /*x_canonicalized=*/true, 3239 /*writep=*/true); 3240 } 3241 3242 3244 3245 /* Check whether X may be aliased with MEM. Don't do offset-based 3246 memory disambiguation & TBAA. */ 3247 int 3248 may_alias_p (const_rtx mem, const_rtx x) 3249 { 3250 rtx x_addr, mem_addr; 3251 3252 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 3253 return 1; 3254 3255 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 3256 This is used in epilogue deallocation functions. */ 3257 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 3258 return 1; 3259 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 3260 return 1; 3261 if (MEM_ALIAS_SET (x) == ALIAS_SET_MEMORY_BARRIER 3262 || MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER) 3263 return 1; 3264 3265 x_addr = XEXP (x, 0); 3266 x_addr = get_addr (x_addr); 3267 3268 mem_addr = XEXP (mem, 0); 3269 mem_addr = get_addr (mem_addr); 3270 3271 /* Read-only memory is by definition never modified, and therefore can't 3272 conflict with anything. However, don't assume anything when AND 3273 addresses are involved and leave to the code below to determine 3274 dependence. We don't expect to find read-only set on MEM, but 3275 stupid user tricks can produce them, so don't die. */ 3276 if (MEM_READONLY_P (x) 3277 && GET_CODE (x_addr) != AND 3278 && GET_CODE (mem_addr) != AND) 3279 return 0; 3280 3281 /* If we have MEMs referring to different address spaces (which can 3282 potentially overlap), we cannot easily tell from the addresses 3283 whether the references overlap. */ 3284 if (MEM_ADDR_SPACE (mem) != MEM_ADDR_SPACE (x)) 3285 return 1; 3286 3287 rtx x_base = find_base_term (x_addr); 3288 rtx mem_base = find_base_term (mem_addr); 3289 if (! base_alias_check (x_addr, x_base, mem_addr, mem_base, 3290 GET_MODE (x), GET_MODE (mem_addr))) 3291 return 0; 3292 3293 if (nonoverlapping_memrefs_p (mem, x, true)) 3294 return 0; 3295 3296 /* TBAA not valid for loop_invarint */ 3297 return rtx_refs_may_alias_p (x, mem, false); 3298 } 3299 3300 void 3301 init_alias_target (void) 3302 { 3303 int i; 3304 3305 if (!arg_base_value) 3306 arg_base_value = gen_rtx_ADDRESS (VOIDmode, 0); 3307 3308 memset (static_reg_base_value, 0, sizeof static_reg_base_value); 3309 3310 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3311 /* Check whether this register can hold an incoming pointer 3312 argument. FUNCTION_ARG_REGNO_P tests outgoing register 3313 numbers, so translate if necessary due to register windows. */ 3314 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i)) 3315 && targetm.hard_regno_mode_ok (i, Pmode)) 3316 static_reg_base_value[i] = arg_base_value; 3317 3318 /* RTL code is required to be consistent about whether it uses the 3319 stack pointer, the frame pointer or the argument pointer to 3320 access a given area of the frame. We can therefore use the 3321 base address to distinguish between the different areas. */ 3322 static_reg_base_value[STACK_POINTER_REGNUM] 3323 = unique_base_value (UNIQUE_BASE_VALUE_SP); 3324 static_reg_base_value[ARG_POINTER_REGNUM] 3325 = unique_base_value (UNIQUE_BASE_VALUE_ARGP); 3326 static_reg_base_value[FRAME_POINTER_REGNUM] 3327 = unique_base_value (UNIQUE_BASE_VALUE_FP); 3328 3329 /* The above rules extend post-reload, with eliminations applying 3330 consistently to each of the three pointers. Cope with cases in 3331 which the frame pointer is eliminated to the hard frame pointer 3332 rather than the stack pointer. */ 3333 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER) 3334 static_reg_base_value[HARD_FRAME_POINTER_REGNUM] 3335 = unique_base_value (UNIQUE_BASE_VALUE_HFP); 3336 } 3337 3338 /* Set MEMORY_MODIFIED when X modifies DATA (that is assumed 3339 to be memory reference. */ 3340 static bool memory_modified; 3341 static void 3342 memory_modified_1 (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data) 3343 { 3344 if (MEM_P (x)) 3345 { 3346 if (anti_dependence (x, (const_rtx)data) || output_dependence (x, (const_rtx)data)) 3347 memory_modified = true; 3348 } 3349 } 3350 3351 3352 /* Return true when INSN possibly modify memory contents of MEM 3353 (i.e. address can be modified). */ 3354 bool 3355 memory_modified_in_insn_p (const_rtx mem, const_rtx insn) 3356 { 3357 if (!INSN_P (insn)) 3358 return false; 3359 /* Conservatively assume all non-readonly MEMs might be modified in 3360 calls. */ 3361 if (CALL_P (insn)) 3362 return true; 3363 memory_modified = false; 3364 note_stores (as_a<const rtx_insn *> (insn), memory_modified_1, 3365 CONST_CAST_RTX(mem)); 3366 return memory_modified; 3367 } 3368 3369 /* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE 3370 array. */ 3371 3372 void 3373 init_alias_analysis (void) 3374 { 3375 const bool frame_pointer_eliminated 3376 = reload_completed 3377 && !frame_pointer_needed 3378 && targetm.can_eliminate (FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM); 3379 unsigned int maxreg = max_reg_num (); 3380 int changed, pass; 3381 int i; 3382 unsigned int ui; 3383 rtx_insn *insn; 3384 rtx val; 3385 int rpo_cnt; 3386 int *rpo; 3387 3388 timevar_push (TV_ALIAS_ANALYSIS); 3389 3390 vec_safe_grow_cleared (reg_known_value, maxreg - FIRST_PSEUDO_REGISTER, 3391 true); 3392 reg_known_equiv_p = sbitmap_alloc (maxreg - FIRST_PSEUDO_REGISTER); 3393 bitmap_clear (reg_known_equiv_p); 3394 3395 /* If we have memory allocated from the previous run, use it. */ 3396 if (old_reg_base_value) 3397 reg_base_value = old_reg_base_value; 3398 3399 if (reg_base_value) 3400 reg_base_value->truncate (0); 3401 3402 vec_safe_grow_cleared (reg_base_value, maxreg, true); 3403 3404 new_reg_base_value = XNEWVEC (rtx, maxreg); 3405 reg_seen = sbitmap_alloc (maxreg); 3406 3407 /* The basic idea is that each pass through this loop will use the 3408 "constant" information from the previous pass to propagate alias 3409 information through another level of assignments. 3410 3411 The propagation is done on the CFG in reverse post-order, to propagate 3412 things forward as far as possible in each iteration. 3413 3414 This could get expensive if the assignment chains are long. Maybe 3415 we should throttle the number of iterations, possibly based on 3416 the optimization level or flag_expensive_optimizations. 3417 3418 We could propagate more information in the first pass by making use 3419 of DF_REG_DEF_COUNT to determine immediately that the alias information 3420 for a pseudo is "constant". 3421 3422 A program with an uninitialized variable can cause an infinite loop 3423 here. Instead of doing a full dataflow analysis to detect such problems 3424 we just cap the number of iterations for the loop. 3425 3426 The state of the arrays for the set chain in question does not matter 3427 since the program has undefined behavior. */ 3428 3429 rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); 3430 rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false); 3431 3432 pass = 0; 3433 do 3434 { 3435 /* Assume nothing will change this iteration of the loop. */ 3436 changed = 0; 3437 3438 /* We want to assign the same IDs each iteration of this loop, so 3439 start counting from one each iteration of the loop. */ 3440 unique_id = 1; 3441 3442 /* We're at the start of the function each iteration through the 3443 loop, so we're copying arguments. */ 3444 copying_arguments = true; 3445 3446 /* Wipe the potential alias information clean for this pass. */ 3447 memset (new_reg_base_value, 0, maxreg * sizeof (rtx)); 3448 3449 /* Wipe the reg_seen array clean. */ 3450 bitmap_clear (reg_seen); 3451 3452 /* Initialize the alias information for this pass. */ 3453 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3454 if (static_reg_base_value[i] 3455 /* Don't treat the hard frame pointer as special if we 3456 eliminated the frame pointer to the stack pointer. */ 3457 && !(i == HARD_FRAME_POINTER_REGNUM && frame_pointer_eliminated)) 3458 { 3459 new_reg_base_value[i] = static_reg_base_value[i]; 3460 bitmap_set_bit (reg_seen, i); 3461 } 3462 3463 /* Walk the insns adding values to the new_reg_base_value array. */ 3464 for (i = 0; i < rpo_cnt; i++) 3465 { 3466 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]); 3467 FOR_BB_INSNS (bb, insn) 3468 { 3469 if (NONDEBUG_INSN_P (insn)) 3470 { 3471 rtx note, set; 3472 3473 /* Treat the hard frame pointer as special unless we 3474 eliminated the frame pointer to the stack pointer. */ 3475 if (!frame_pointer_eliminated 3476 && modified_in_p (hard_frame_pointer_rtx, insn)) 3477 continue; 3478 3479 /* If this insn has a noalias note, process it, Otherwise, 3480 scan for sets. A simple set will have no side effects 3481 which could change the base value of any other register. */ 3482 if (GET_CODE (PATTERN (insn)) == SET 3483 && REG_NOTES (insn) != 0 3484 && find_reg_note (insn, REG_NOALIAS, NULL_RTX)) 3485 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL); 3486 else 3487 note_stores (insn, record_set, NULL); 3488 3489 set = single_set (insn); 3490 3491 if (set != 0 3492 && REG_P (SET_DEST (set)) 3493 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER) 3494 { 3495 unsigned int regno = REGNO (SET_DEST (set)); 3496 rtx src = SET_SRC (set); 3497 rtx t; 3498 3499 note = find_reg_equal_equiv_note (insn); 3500 if (note && REG_NOTE_KIND (note) == REG_EQUAL 3501 && DF_REG_DEF_COUNT (regno) != 1) 3502 note = NULL_RTX; 3503 3504 poly_int64 offset; 3505 if (note != NULL_RTX 3506 && GET_CODE (XEXP (note, 0)) != EXPR_LIST 3507 && ! rtx_varies_p (XEXP (note, 0), 1) 3508 && ! reg_overlap_mentioned_p (SET_DEST (set), 3509 XEXP (note, 0))) 3510 { 3511 set_reg_known_value (regno, XEXP (note, 0)); 3512 set_reg_known_equiv_p (regno, 3513 REG_NOTE_KIND (note) == REG_EQUIV); 3514 } 3515 else if (DF_REG_DEF_COUNT (regno) == 1 3516 && GET_CODE (src) == PLUS 3517 && REG_P (XEXP (src, 0)) 3518 && (t = get_reg_known_value (REGNO (XEXP (src, 0)))) 3519 && poly_int_rtx_p (XEXP (src, 1), &offset)) 3520 { 3521 t = plus_constant (GET_MODE (src), t, offset); 3522 set_reg_known_value (regno, t); 3523 set_reg_known_equiv_p (regno, false); 3524 } 3525 else if (DF_REG_DEF_COUNT (regno) == 1 3526 && ! rtx_varies_p (src, 1)) 3527 { 3528 set_reg_known_value (regno, src); 3529 set_reg_known_equiv_p (regno, false); 3530 } 3531 } 3532 } 3533 else if (NOTE_P (insn) 3534 && NOTE_KIND (insn) == NOTE_INSN_FUNCTION_BEG) 3535 copying_arguments = false; 3536 } 3537 } 3538 3539 /* Now propagate values from new_reg_base_value to reg_base_value. */ 3540 gcc_assert (maxreg == (unsigned int) max_reg_num ()); 3541 3542 for (ui = 0; ui < maxreg; ui++) 3543 { 3544 if (new_reg_base_value[ui] 3545 && new_reg_base_value[ui] != (*reg_base_value)[ui] 3546 && ! rtx_equal_p (new_reg_base_value[ui], (*reg_base_value)[ui])) 3547 { 3548 (*reg_base_value)[ui] = new_reg_base_value[ui]; 3549 changed = 1; 3550 } 3551 } 3552 } 3553 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES); 3554 XDELETEVEC (rpo); 3555 3556 /* Fill in the remaining entries. */ 3557 FOR_EACH_VEC_ELT (*reg_known_value, i, val) 3558 { 3559 int regno = i + FIRST_PSEUDO_REGISTER; 3560 if (! val) 3561 set_reg_known_value (regno, regno_reg_rtx[regno]); 3562 } 3563 3564 /* Clean up. */ 3565 free (new_reg_base_value); 3566 new_reg_base_value = 0; 3567 sbitmap_free (reg_seen); 3568 reg_seen = 0; 3569 timevar_pop (TV_ALIAS_ANALYSIS); 3570 } 3571 3572 /* Equate REG_BASE_VALUE (reg1) to REG_BASE_VALUE (reg2). 3573 Special API for var-tracking pass purposes. */ 3574 3575 void 3576 vt_equate_reg_base_value (const_rtx reg1, const_rtx reg2) 3577 { 3578 (*reg_base_value)[REGNO (reg1)] = REG_BASE_VALUE (reg2); 3579 } 3580 3581 void 3582 end_alias_analysis (void) 3583 { 3584 old_reg_base_value = reg_base_value; 3585 vec_free (reg_known_value); 3586 sbitmap_free (reg_known_equiv_p); 3587 } 3588 3589 void 3590 dump_alias_stats_in_alias_c (FILE *s) 3591 { 3592 fprintf (s, " TBAA oracle: %llu disambiguations %llu queries\n" 3593 " %llu are in alias set 0\n" 3594 " %llu queries asked about the same object\n" 3595 " %llu queries asked about the same alias set\n" 3596 " %llu access volatile\n" 3597 " %llu are dependent in the DAG\n" 3598 " %llu are aritificially in conflict with void *\n", 3599 alias_stats.num_disambiguated, 3600 alias_stats.num_alias_zero + alias_stats.num_same_alias_set 3601 + alias_stats.num_same_objects + alias_stats.num_volatile 3602 + alias_stats.num_dag + alias_stats.num_disambiguated 3603 + alias_stats.num_universal, 3604 alias_stats.num_alias_zero, alias_stats.num_same_alias_set, 3605 alias_stats.num_same_objects, alias_stats.num_volatile, 3606 alias_stats.num_dag, alias_stats.num_universal); 3607 } 3608 #include "gt-alias.h" 3609
Indexes created Tue Feb 24 01:34:59 UTC 2026