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