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