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