alias.c revision 110611
1/* Alias analysis for GNU C 2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 3 Contributed by John Carr (jfc@mit.edu). 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 59 Temple Place - Suite 330, Boston, MA 2002111-1307, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "rtl.h" 25#include "tree.h" 26#include "tm_p.h" 27#include "function.h" 28#include "expr.h" 29#include "regs.h" 30#include "hard-reg-set.h" 31#include "basic-block.h" 32#include "flags.h" 33#include "output.h" 34#include "toplev.h" 35#include "cselib.h" 36#include "splay-tree.h" 37#include "ggc.h" 38#include "langhooks.h" 39 40/* The alias sets assigned to MEMs assist the back-end in determining 41 which MEMs can alias which other MEMs. In general, two MEMs in 42 different alias sets cannot alias each other, with one important 43 exception. Consider something like: 44 45 struct S {int i; double d; }; 46 47 a store to an `S' can alias something of either type `int' or type 48 `double'. (However, a store to an `int' cannot alias a `double' 49 and vice versa.) We indicate this via a tree structure that looks 50 like: 51 struct S 52 / \ 53 / \ 54 |/_ _\| 55 int double 56 57 (The arrows are directed and point downwards.) 58 In this situation we say the alias set for `struct S' is the 59 `superset' and that those for `int' and `double' are `subsets'. 60 61 To see whether two alias sets can point to the same memory, we must 62 see if either alias set is a subset of the other. We need not trace 63 past immediate descendents, however, since we propagate all 64 grandchildren up one level. 65 66 Alias set zero is implicitly a superset of all other alias sets. 67 However, this is no actual entry for alias set zero. It is an 68 error to attempt to explicitly construct a subset of zero. */ 69 70typedef struct alias_set_entry 71{ 72 /* The alias set number, as stored in MEM_ALIAS_SET. */ 73 HOST_WIDE_INT alias_set; 74 75 /* The children of the alias set. These are not just the immediate 76 children, but, in fact, all descendents. So, if we have: 77 78 struct T { struct S s; float f; } 79 80 continuing our example above, the children here will be all of 81 `int', `double', `float', and `struct S'. */ 82 splay_tree children; 83 84 /* Nonzero if would have a child of zero: this effectively makes this 85 alias set the same as alias set zero. */ 86 int has_zero_child; 87} *alias_set_entry; 88 89static int rtx_equal_for_memref_p PARAMS ((rtx, rtx)); 90static rtx find_symbolic_term PARAMS ((rtx)); 91rtx get_addr PARAMS ((rtx)); 92static int memrefs_conflict_p PARAMS ((int, rtx, int, rtx, 93 HOST_WIDE_INT)); 94static void record_set PARAMS ((rtx, rtx, void *)); 95static rtx find_base_term PARAMS ((rtx)); 96static int base_alias_check PARAMS ((rtx, rtx, enum machine_mode, 97 enum machine_mode)); 98static rtx find_base_value PARAMS ((rtx)); 99static int mems_in_disjoint_alias_sets_p PARAMS ((rtx, rtx)); 100static int insert_subset_children PARAMS ((splay_tree_node, void*)); 101static tree find_base_decl PARAMS ((tree)); 102static alias_set_entry get_alias_set_entry PARAMS ((HOST_WIDE_INT)); 103static rtx fixed_scalar_and_varying_struct_p PARAMS ((rtx, rtx, rtx, rtx, 104 int (*) (rtx, int))); 105static int aliases_everything_p PARAMS ((rtx)); 106static bool nonoverlapping_component_refs_p PARAMS ((tree, tree)); 107static tree decl_for_component_ref PARAMS ((tree)); 108static rtx adjust_offset_for_component_ref PARAMS ((tree, rtx)); 109static int nonoverlapping_memrefs_p PARAMS ((rtx, rtx)); 110static int write_dependence_p PARAMS ((rtx, rtx, int)); 111static int nonlocal_mentioned_p PARAMS ((rtx)); 112 113/* Set up all info needed to perform alias analysis on memory references. */ 114 115/* Returns the size in bytes of the mode of X. */ 116#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X))) 117 118/* Returns nonzero if MEM1 and MEM2 do not alias because they are in 119 different alias sets. We ignore alias sets in functions making use 120 of variable arguments because the va_arg macros on some systems are 121 not legal ANSI C. */ 122#define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \ 123 mems_in_disjoint_alias_sets_p (MEM1, MEM2) 124 125/* Cap the number of passes we make over the insns propagating alias 126 information through set chains. 10 is a completely arbitrary choice. */ 127#define MAX_ALIAS_LOOP_PASSES 10 128 129/* reg_base_value[N] gives an address to which register N is related. 130 If all sets after the first add or subtract to the current value 131 or otherwise modify it so it does not point to a different top level 132 object, reg_base_value[N] is equal to the address part of the source 133 of the first set. 134 135 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS 136 expressions represent certain special values: function arguments and 137 the stack, frame, and argument pointers. 138 139 The contents of an ADDRESS is not normally used, the mode of the 140 ADDRESS determines whether the ADDRESS is a function argument or some 141 other special value. Pointer equality, not rtx_equal_p, determines whether 142 two ADDRESS expressions refer to the same base address. 143 144 The only use of the contents of an ADDRESS is for determining if the 145 current function performs nonlocal memory memory references for the 146 purposes of marking the function as a constant function. */ 147 148static rtx *reg_base_value; 149static rtx *new_reg_base_value; 150static unsigned int reg_base_value_size; /* size of reg_base_value array */ 151 152#define REG_BASE_VALUE(X) \ 153 (REGNO (X) < reg_base_value_size \ 154 ? reg_base_value[REGNO (X)] : 0) 155 156/* Vector of known invariant relationships between registers. Set in 157 loop unrolling. Indexed by register number, if nonzero the value 158 is an expression describing this register in terms of another. 159 160 The length of this array is REG_BASE_VALUE_SIZE. 161 162 Because this array contains only pseudo registers it has no effect 163 after reload. */ 164static rtx *alias_invariant; 165 166/* Vector indexed by N giving the initial (unchanging) value known for 167 pseudo-register N. This array is initialized in 168 init_alias_analysis, and does not change until end_alias_analysis 169 is called. */ 170rtx *reg_known_value; 171 172/* Indicates number of valid entries in reg_known_value. */ 173static unsigned int reg_known_value_size; 174 175/* Vector recording for each reg_known_value whether it is due to a 176 REG_EQUIV note. Future passes (viz., reload) may replace the 177 pseudo with the equivalent expression and so we account for the 178 dependences that would be introduced if that happens. 179 180 The REG_EQUIV notes created in assign_parms may mention the arg 181 pointer, and there are explicit insns in the RTL that modify the 182 arg pointer. Thus we must ensure that such insns don't get 183 scheduled across each other because that would invalidate the 184 REG_EQUIV notes. One could argue that the REG_EQUIV notes are 185 wrong, but solving the problem in the scheduler will likely give 186 better code, so we do it here. */ 187char *reg_known_equiv_p; 188 189/* True when scanning insns from the start of the rtl to the 190 NOTE_INSN_FUNCTION_BEG note. */ 191static int copying_arguments; 192 193/* The splay-tree used to store the various alias set entries. */ 194static splay_tree alias_sets; 195 196/* Returns a pointer to the alias set entry for ALIAS_SET, if there is 197 such an entry, or NULL otherwise. */ 198 199static alias_set_entry 200get_alias_set_entry (alias_set) 201 HOST_WIDE_INT alias_set; 202{ 203 splay_tree_node sn 204 = splay_tree_lookup (alias_sets, (splay_tree_key) alias_set); 205 206 return sn != 0 ? ((alias_set_entry) sn->value) : 0; 207} 208 209/* Returns nonzero if the alias sets for MEM1 and MEM2 are such that 210 the two MEMs cannot alias each other. */ 211 212static int 213mems_in_disjoint_alias_sets_p (mem1, mem2) 214 rtx mem1; 215 rtx mem2; 216{ 217#ifdef ENABLE_CHECKING 218/* Perform a basic sanity check. Namely, that there are no alias sets 219 if we're not using strict aliasing. This helps to catch bugs 220 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or 221 where a MEM is allocated in some way other than by the use of 222 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to 223 use alias sets to indicate that spilled registers cannot alias each 224 other, we might need to remove this check. */ 225 if (! flag_strict_aliasing 226 && (MEM_ALIAS_SET (mem1) != 0 || MEM_ALIAS_SET (mem2) != 0)) 227 abort (); 228#endif 229 230 return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), MEM_ALIAS_SET (mem2)); 231} 232 233/* Insert the NODE into the splay tree given by DATA. Used by 234 record_alias_subset via splay_tree_foreach. */ 235 236static int 237insert_subset_children (node, data) 238 splay_tree_node node; 239 void *data; 240{ 241 splay_tree_insert ((splay_tree) data, node->key, node->value); 242 243 return 0; 244} 245 246/* Return 1 if the two specified alias sets may conflict. */ 247 248int 249alias_sets_conflict_p (set1, set2) 250 HOST_WIDE_INT set1, set2; 251{ 252 alias_set_entry ase; 253 254 /* If have no alias set information for one of the operands, we have 255 to assume it can alias anything. */ 256 if (set1 == 0 || set2 == 0 257 /* If the two alias sets are the same, they may alias. */ 258 || set1 == set2) 259 return 1; 260 261 /* See if the first alias set is a subset of the second. */ 262 ase = get_alias_set_entry (set1); 263 if (ase != 0 264 && (ase->has_zero_child 265 || splay_tree_lookup (ase->children, 266 (splay_tree_key) set2))) 267 return 1; 268 269 /* Now do the same, but with the alias sets reversed. */ 270 ase = get_alias_set_entry (set2); 271 if (ase != 0 272 && (ase->has_zero_child 273 || splay_tree_lookup (ase->children, 274 (splay_tree_key) set1))) 275 return 1; 276 277 /* The two alias sets are distinct and neither one is the 278 child of the other. Therefore, they cannot alias. */ 279 return 0; 280} 281 282/* Return 1 if TYPE is a RECORD_TYPE, UNION_TYPE, or QUAL_UNION_TYPE and has 283 has any readonly fields. If any of the fields have types that 284 contain readonly fields, return true as well. */ 285 286int 287readonly_fields_p (type) 288 tree type; 289{ 290 tree field; 291 292 if (TREE_CODE (type) != RECORD_TYPE && TREE_CODE (type) != UNION_TYPE 293 && TREE_CODE (type) != QUAL_UNION_TYPE) 294 return 0; 295 296 for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field)) 297 if (TREE_CODE (field) == FIELD_DECL 298 && (TREE_READONLY (field) 299 || readonly_fields_p (TREE_TYPE (field)))) 300 return 1; 301 302 return 0; 303} 304 305/* Return 1 if any MEM object of type T1 will always conflict (using the 306 dependency routines in this file) with any MEM object of type T2. 307 This is used when allocating temporary storage. If T1 and/or T2 are 308 NULL_TREE, it means we know nothing about the storage. */ 309 310int 311objects_must_conflict_p (t1, t2) 312 tree t1, t2; 313{ 314 /* If neither has a type specified, we don't know if they'll conflict 315 because we may be using them to store objects of various types, for 316 example the argument and local variables areas of inlined functions. */ 317 if (t1 == 0 && t2 == 0) 318 return 0; 319 320 /* If one or the other has readonly fields or is readonly, 321 then they may not conflict. */ 322 if ((t1 != 0 && readonly_fields_p (t1)) 323 || (t2 != 0 && readonly_fields_p (t2)) 324 || (t1 != 0 && lang_hooks.honor_readonly && TYPE_READONLY (t1)) 325 || (t2 != 0 && lang_hooks.honor_readonly && TYPE_READONLY (t2))) 326 return 0; 327 328 /* If they are the same type, they must conflict. */ 329 if (t1 == t2 330 /* Likewise if both are volatile. */ 331 || (t1 != 0 && TYPE_VOLATILE (t1) && t2 != 0 && TYPE_VOLATILE (t2))) 332 return 1; 333 334 /* If one is aggregate and the other is scalar then they may not 335 conflict. */ 336 if ((t1 != 0 && AGGREGATE_TYPE_P (t1)) 337 != (t2 != 0 && AGGREGATE_TYPE_P (t2))) 338 return 0; 339 340 /* Otherwise they conflict only if the alias sets conflict. */ 341 return alias_sets_conflict_p (t1 ? get_alias_set (t1) : 0, 342 t2 ? get_alias_set (t2) : 0); 343} 344 345/* T is an expression with pointer type. Find the DECL on which this 346 expression is based. (For example, in `a[i]' this would be `a'.) 347 If there is no such DECL, or a unique decl cannot be determined, 348 NULL_TREE is returned. */ 349 350static tree 351find_base_decl (t) 352 tree t; 353{ 354 tree d0, d1, d2; 355 356 if (t == 0 || t == error_mark_node || ! POINTER_TYPE_P (TREE_TYPE (t))) 357 return 0; 358 359 /* If this is a declaration, return it. */ 360 if (TREE_CODE_CLASS (TREE_CODE (t)) == 'd') 361 return t; 362 363 /* Handle general expressions. It would be nice to deal with 364 COMPONENT_REFs here. If we could tell that `a' and `b' were the 365 same, then `a->f' and `b->f' are also the same. */ 366 switch (TREE_CODE_CLASS (TREE_CODE (t))) 367 { 368 case '1': 369 return find_base_decl (TREE_OPERAND (t, 0)); 370 371 case '2': 372 /* Return 0 if found in neither or both are the same. */ 373 d0 = find_base_decl (TREE_OPERAND (t, 0)); 374 d1 = find_base_decl (TREE_OPERAND (t, 1)); 375 if (d0 == d1) 376 return d0; 377 else if (d0 == 0) 378 return d1; 379 else if (d1 == 0) 380 return d0; 381 else 382 return 0; 383 384 case '3': 385 d0 = find_base_decl (TREE_OPERAND (t, 0)); 386 d1 = find_base_decl (TREE_OPERAND (t, 1)); 387 d2 = find_base_decl (TREE_OPERAND (t, 2)); 388 389 /* Set any nonzero values from the last, then from the first. */ 390 if (d1 == 0) d1 = d2; 391 if (d0 == 0) d0 = d1; 392 if (d1 == 0) d1 = d0; 393 if (d2 == 0) d2 = d1; 394 395 /* At this point all are nonzero or all are zero. If all three are the 396 same, return it. Otherwise, return zero. */ 397 return (d0 == d1 && d1 == d2) ? d0 : 0; 398 399 default: 400 return 0; 401 } 402} 403 404/* Return 1 if all the nested component references handled by 405 get_inner_reference in T are such that we can address the object in T. */ 406 407int 408can_address_p (t) 409 tree t; 410{ 411 /* If we're at the end, it is vacuously addressable. */ 412 if (! handled_component_p (t)) 413 return 1; 414 415 /* Bitfields are never addressable. */ 416 else if (TREE_CODE (t) == BIT_FIELD_REF) 417 return 0; 418 419 /* Fields are addressable unless they are marked as nonaddressable or 420 the containing type has alias set 0. */ 421 else if (TREE_CODE (t) == COMPONENT_REF 422 && ! DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)) 423 && get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) != 0 424 && can_address_p (TREE_OPERAND (t, 0))) 425 return 1; 426 427 /* Likewise for arrays. */ 428 else if ((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF) 429 && ! TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))) 430 && get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) != 0 431 && can_address_p (TREE_OPERAND (t, 0))) 432 return 1; 433 434 return 0; 435} 436 437/* Return the alias set for T, which may be either a type or an 438 expression. Call language-specific routine for help, if needed. */ 439 440HOST_WIDE_INT 441get_alias_set (t) 442 tree t; 443{ 444 HOST_WIDE_INT set; 445 446 /* If we're not doing any alias analysis, just assume everything 447 aliases everything else. Also return 0 if this or its type is 448 an error. */ 449 if (! flag_strict_aliasing || t == error_mark_node 450 || (! TYPE_P (t) 451 && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node))) 452 return 0; 453 454 /* We can be passed either an expression or a type. This and the 455 language-specific routine may make mutually-recursive calls to each other 456 to figure out what to do. At each juncture, we see if this is a tree 457 that the language may need to handle specially. First handle things that 458 aren't types. */ 459 if (! TYPE_P (t)) 460 { 461 tree inner = t; 462 tree placeholder_ptr = 0; 463 464 /* Remove any nops, then give the language a chance to do 465 something with this tree before we look at it. */ 466 STRIP_NOPS (t); 467 set = (*lang_hooks.get_alias_set) (t); 468 if (set != -1) 469 return set; 470 471 /* First see if the actual object referenced is an INDIRECT_REF from a 472 restrict-qualified pointer or a "void *". Replace 473 PLACEHOLDER_EXPRs. */ 474 while (TREE_CODE (inner) == PLACEHOLDER_EXPR 475 || handled_component_p (inner)) 476 { 477 if (TREE_CODE (inner) == PLACEHOLDER_EXPR) 478 inner = find_placeholder (inner, &placeholder_ptr); 479 else 480 inner = TREE_OPERAND (inner, 0); 481 482 STRIP_NOPS (inner); 483 } 484 485 /* Check for accesses through restrict-qualified pointers. */ 486 if (TREE_CODE (inner) == INDIRECT_REF) 487 { 488 tree decl = find_base_decl (TREE_OPERAND (inner, 0)); 489 490 if (decl && DECL_POINTER_ALIAS_SET_KNOWN_P (decl)) 491 { 492 /* If we haven't computed the actual alias set, do it now. */ 493 if (DECL_POINTER_ALIAS_SET (decl) == -2) 494 { 495 /* No two restricted pointers can point at the same thing. 496 However, a restricted pointer can point at the same thing 497 as an unrestricted pointer, if that unrestricted pointer 498 is based on the restricted pointer. So, we make the 499 alias set for the restricted pointer a subset of the 500 alias set for the type pointed to by the type of the 501 decl. */ 502 HOST_WIDE_INT pointed_to_alias_set 503 = get_alias_set (TREE_TYPE (TREE_TYPE (decl))); 504 505 if (pointed_to_alias_set == 0) 506 /* It's not legal to make a subset of alias set zero. */ 507 ; 508 else 509 { 510 DECL_POINTER_ALIAS_SET (decl) = new_alias_set (); 511 record_alias_subset (pointed_to_alias_set, 512 DECL_POINTER_ALIAS_SET (decl)); 513 } 514 } 515 516 /* We use the alias set indicated in the declaration. */ 517 return DECL_POINTER_ALIAS_SET (decl); 518 } 519 520 /* If we have an INDIRECT_REF via a void pointer, we don't 521 know anything about what that might alias. */ 522 else if (TREE_CODE (TREE_TYPE (inner)) == VOID_TYPE) 523 return 0; 524 } 525 526 /* Otherwise, pick up the outermost object that we could have a pointer 527 to, processing conversion and PLACEHOLDER_EXPR as above. */ 528 placeholder_ptr = 0; 529 while (TREE_CODE (t) == PLACEHOLDER_EXPR 530 || (handled_component_p (t) && ! can_address_p (t))) 531 { 532 if (TREE_CODE (t) == PLACEHOLDER_EXPR) 533 t = find_placeholder (t, &placeholder_ptr); 534 else 535 t = TREE_OPERAND (t, 0); 536 537 STRIP_NOPS (t); 538 } 539 540 /* If we've already determined the alias set for a decl, just return 541 it. This is necessary for C++ anonymous unions, whose component 542 variables don't look like union members (boo!). */ 543 if (TREE_CODE (t) == VAR_DECL 544 && DECL_RTL_SET_P (t) && GET_CODE (DECL_RTL (t)) == MEM) 545 return MEM_ALIAS_SET (DECL_RTL (t)); 546 547 /* Now all we care about is the type. */ 548 t = TREE_TYPE (t); 549 } 550 551 /* Variant qualifiers don't affect the alias set, so get the main 552 variant. If this is a type with a known alias set, return it. */ 553 t = TYPE_MAIN_VARIANT (t); 554 if (TYPE_ALIAS_SET_KNOWN_P (t)) 555 return TYPE_ALIAS_SET (t); 556 557 /* See if the language has special handling for this type. */ 558 set = (*lang_hooks.get_alias_set) (t); 559 if (set != -1) 560 return set; 561 562 /* There are no objects of FUNCTION_TYPE, so there's no point in 563 using up an alias set for them. (There are, of course, pointers 564 and references to functions, but that's different.) */ 565 else if (TREE_CODE (t) == FUNCTION_TYPE) 566 set = 0; 567 568 /* Unless the language specifies otherwise, let vector types alias 569 their components. This avoids some nasty type punning issues in 570 normal usage. And indeed lets vectors be treated more like an 571 array slice. */ 572 else if (TREE_CODE (t) == VECTOR_TYPE) 573 set = get_alias_set (TREE_TYPE (t)); 574 575 else 576 /* Otherwise make a new alias set for this type. */ 577 set = new_alias_set (); 578 579 TYPE_ALIAS_SET (t) = set; 580 581 /* If this is an aggregate type, we must record any component aliasing 582 information. */ 583 if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE) 584 record_component_aliases (t); 585 586 return set; 587} 588 589/* Return a brand-new alias set. */ 590 591HOST_WIDE_INT 592new_alias_set () 593{ 594 static HOST_WIDE_INT last_alias_set; 595 596 if (flag_strict_aliasing) 597 return ++last_alias_set; 598 else 599 return 0; 600} 601 602/* Indicate that things in SUBSET can alias things in SUPERSET, but 603 not vice versa. For example, in C, a store to an `int' can alias a 604 structure containing an `int', but not vice versa. Here, the 605 structure would be the SUPERSET and `int' the SUBSET. This 606 function should be called only once per SUPERSET/SUBSET pair. 607 608 It is illegal for SUPERSET to be zero; everything is implicitly a 609 subset of alias set zero. */ 610 611void 612record_alias_subset (superset, subset) 613 HOST_WIDE_INT superset; 614 HOST_WIDE_INT subset; 615{ 616 alias_set_entry superset_entry; 617 alias_set_entry subset_entry; 618 619 /* It is possible in complex type situations for both sets to be the same, 620 in which case we can ignore this operation. */ 621 if (superset == subset) 622 return; 623 624 if (superset == 0) 625 abort (); 626 627 superset_entry = get_alias_set_entry (superset); 628 if (superset_entry == 0) 629 { 630 /* Create an entry for the SUPERSET, so that we have a place to 631 attach the SUBSET. */ 632 superset_entry 633 = (alias_set_entry) xmalloc (sizeof (struct alias_set_entry)); 634 superset_entry->alias_set = superset; 635 superset_entry->children 636 = splay_tree_new (splay_tree_compare_ints, 0, 0); 637 superset_entry->has_zero_child = 0; 638 splay_tree_insert (alias_sets, (splay_tree_key) superset, 639 (splay_tree_value) superset_entry); 640 } 641 642 if (subset == 0) 643 superset_entry->has_zero_child = 1; 644 else 645 { 646 subset_entry = get_alias_set_entry (subset); 647 /* If there is an entry for the subset, enter all of its children 648 (if they are not already present) as children of the SUPERSET. */ 649 if (subset_entry) 650 { 651 if (subset_entry->has_zero_child) 652 superset_entry->has_zero_child = 1; 653 654 splay_tree_foreach (subset_entry->children, insert_subset_children, 655 superset_entry->children); 656 } 657 658 /* Enter the SUBSET itself as a child of the SUPERSET. */ 659 splay_tree_insert (superset_entry->children, 660 (splay_tree_key) subset, 0); 661 } 662} 663 664/* Record that component types of TYPE, if any, are part of that type for 665 aliasing purposes. For record types, we only record component types 666 for fields that are marked addressable. For array types, we always 667 record the component types, so the front end should not call this 668 function if the individual component aren't addressable. */ 669 670void 671record_component_aliases (type) 672 tree type; 673{ 674 HOST_WIDE_INT superset = get_alias_set (type); 675 tree field; 676 677 if (superset == 0) 678 return; 679 680 switch (TREE_CODE (type)) 681 { 682 case ARRAY_TYPE: 683 if (! TYPE_NONALIASED_COMPONENT (type)) 684 record_alias_subset (superset, get_alias_set (TREE_TYPE (type))); 685 break; 686 687 case RECORD_TYPE: 688 case UNION_TYPE: 689 case QUAL_UNION_TYPE: 690 for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field)) 691 if (TREE_CODE (field) == FIELD_DECL && ! DECL_NONADDRESSABLE_P (field)) 692 record_alias_subset (superset, get_alias_set (TREE_TYPE (field))); 693 break; 694 695 case COMPLEX_TYPE: 696 record_alias_subset (superset, get_alias_set (TREE_TYPE (type))); 697 break; 698 699 default: 700 break; 701 } 702} 703 704/* Allocate an alias set for use in storing and reading from the varargs 705 spill area. */ 706 707HOST_WIDE_INT 708get_varargs_alias_set () 709{ 710 static HOST_WIDE_INT set = -1; 711 712 if (set == -1) 713 set = new_alias_set (); 714 715 return set; 716} 717 718/* Likewise, but used for the fixed portions of the frame, e.g., register 719 save areas. */ 720 721HOST_WIDE_INT 722get_frame_alias_set () 723{ 724 static HOST_WIDE_INT set = -1; 725 726 if (set == -1) 727 set = new_alias_set (); 728 729 return set; 730} 731 732/* Inside SRC, the source of a SET, find a base address. */ 733 734static rtx 735find_base_value (src) 736 rtx src; 737{ 738 unsigned int regno; 739 740 switch (GET_CODE (src)) 741 { 742 case SYMBOL_REF: 743 case LABEL_REF: 744 return src; 745 746 case REG: 747 regno = REGNO (src); 748 /* At the start of a function, argument registers have known base 749 values which may be lost later. Returning an ADDRESS 750 expression here allows optimization based on argument values 751 even when the argument registers are used for other purposes. */ 752 if (regno < FIRST_PSEUDO_REGISTER && copying_arguments) 753 return new_reg_base_value[regno]; 754 755 /* If a pseudo has a known base value, return it. Do not do this 756 for non-fixed hard regs since it can result in a circular 757 dependency chain for registers which have values at function entry. 758 759 The test above is not sufficient because the scheduler may move 760 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */ 761 if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno]) 762 && regno < reg_base_value_size 763 && reg_base_value[regno]) 764 return reg_base_value[regno]; 765 766 return src; 767 768 case MEM: 769 /* Check for an argument passed in memory. Only record in the 770 copying-arguments block; it is too hard to track changes 771 otherwise. */ 772 if (copying_arguments 773 && (XEXP (src, 0) == arg_pointer_rtx 774 || (GET_CODE (XEXP (src, 0)) == PLUS 775 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx))) 776 return gen_rtx_ADDRESS (VOIDmode, src); 777 return 0; 778 779 case CONST: 780 src = XEXP (src, 0); 781 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS) 782 break; 783 784 /* ... fall through ... */ 785 786 case PLUS: 787 case MINUS: 788 { 789 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1); 790 791 /* If either operand is a REG that is a known pointer, then it 792 is the base. */ 793 if (REG_P (src_0) && REG_POINTER (src_0)) 794 return find_base_value (src_0); 795 if (REG_P (src_1) && REG_POINTER (src_1)) 796 return find_base_value (src_1); 797 798 /* If either operand is a REG, then see if we already have 799 a known value for it. */ 800 if (REG_P (src_0)) 801 { 802 temp = find_base_value (src_0); 803 if (temp != 0) 804 src_0 = temp; 805 } 806 807 if (REG_P (src_1)) 808 { 809 temp = find_base_value (src_1); 810 if (temp!= 0) 811 src_1 = temp; 812 } 813 814 /* If either base is named object or a special address 815 (like an argument or stack reference), then use it for the 816 base term. */ 817 if (src_0 != 0 818 && (GET_CODE (src_0) == SYMBOL_REF 819 || GET_CODE (src_0) == LABEL_REF 820 || (GET_CODE (src_0) == ADDRESS 821 && GET_MODE (src_0) != VOIDmode))) 822 return src_0; 823 824 if (src_1 != 0 825 && (GET_CODE (src_1) == SYMBOL_REF 826 || GET_CODE (src_1) == LABEL_REF 827 || (GET_CODE (src_1) == ADDRESS 828 && GET_MODE (src_1) != VOIDmode))) 829 return src_1; 830 831 /* Guess which operand is the base address: 832 If either operand is a symbol, then it is the base. If 833 either operand is a CONST_INT, then the other is the base. */ 834 if (GET_CODE (src_1) == CONST_INT || CONSTANT_P (src_0)) 835 return find_base_value (src_0); 836 else if (GET_CODE (src_0) == CONST_INT || CONSTANT_P (src_1)) 837 return find_base_value (src_1); 838 839 return 0; 840 } 841 842 case LO_SUM: 843 /* The standard form is (lo_sum reg sym) so look only at the 844 second operand. */ 845 return find_base_value (XEXP (src, 1)); 846 847 case AND: 848 /* If the second operand is constant set the base 849 address to the first operand. */ 850 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0) 851 return find_base_value (XEXP (src, 0)); 852 return 0; 853 854 case TRUNCATE: 855 if (GET_MODE_SIZE (GET_MODE (src)) < GET_MODE_SIZE (Pmode)) 856 break; 857 /* Fall through. */ 858 case HIGH: 859 case PRE_INC: 860 case PRE_DEC: 861 case POST_INC: 862 case POST_DEC: 863 case PRE_MODIFY: 864 case POST_MODIFY: 865 return find_base_value (XEXP (src, 0)); 866 867 case ZERO_EXTEND: 868 case SIGN_EXTEND: /* used for NT/Alpha pointers */ 869 { 870 rtx temp = find_base_value (XEXP (src, 0)); 871 872#ifdef POINTERS_EXTEND_UNSIGNED 873 if (temp != 0 && CONSTANT_P (temp) && GET_MODE (temp) != Pmode) 874 temp = convert_memory_address (Pmode, temp); 875#endif 876 877 return temp; 878 } 879 880 default: 881 break; 882 } 883 884 return 0; 885} 886 887/* Called from init_alias_analysis indirectly through note_stores. */ 888 889/* While scanning insns to find base values, reg_seen[N] is nonzero if 890 register N has been set in this function. */ 891static char *reg_seen; 892 893/* Addresses which are known not to alias anything else are identified 894 by a unique integer. */ 895static int unique_id; 896 897static void 898record_set (dest, set, data) 899 rtx dest, set; 900 void *data ATTRIBUTE_UNUSED; 901{ 902 unsigned regno; 903 rtx src; 904 905 if (GET_CODE (dest) != REG) 906 return; 907 908 regno = REGNO (dest); 909 910 if (regno >= reg_base_value_size) 911 abort (); 912 913 if (set) 914 { 915 /* A CLOBBER wipes out any old value but does not prevent a previously 916 unset register from acquiring a base address (i.e. reg_seen is not 917 set). */ 918 if (GET_CODE (set) == CLOBBER) 919 { 920 new_reg_base_value[regno] = 0; 921 return; 922 } 923 src = SET_SRC (set); 924 } 925 else 926 { 927 if (reg_seen[regno]) 928 { 929 new_reg_base_value[regno] = 0; 930 return; 931 } 932 reg_seen[regno] = 1; 933 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode, 934 GEN_INT (unique_id++)); 935 return; 936 } 937 938 /* This is not the first set. If the new value is not related to the 939 old value, forget the base value. Note that the following code is 940 not detected: 941 extern int x, y; int *p = &x; p += (&y-&x); 942 ANSI C does not allow computing the difference of addresses 943 of distinct top level objects. */ 944 if (new_reg_base_value[regno]) 945 switch (GET_CODE (src)) 946 { 947 case LO_SUM: 948 case MINUS: 949 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest) 950 new_reg_base_value[regno] = 0; 951 break; 952 case PLUS: 953 /* If the value we add in the PLUS is also a valid base value, 954 this might be the actual base value, and the original value 955 an index. */ 956 { 957 rtx other = NULL_RTX; 958 959 if (XEXP (src, 0) == dest) 960 other = XEXP (src, 1); 961 else if (XEXP (src, 1) == dest) 962 other = XEXP (src, 0); 963 964 if (! other || find_base_value (other)) 965 new_reg_base_value[regno] = 0; 966 break; 967 } 968 case AND: 969 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT) 970 new_reg_base_value[regno] = 0; 971 break; 972 default: 973 new_reg_base_value[regno] = 0; 974 break; 975 } 976 /* If this is the first set of a register, record the value. */ 977 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno]) 978 && ! reg_seen[regno] && new_reg_base_value[regno] == 0) 979 new_reg_base_value[regno] = find_base_value (src); 980 981 reg_seen[regno] = 1; 982} 983 984/* Called from loop optimization when a new pseudo-register is 985 created. It indicates that REGNO is being set to VAL. f INVARIANT 986 is true then this value also describes an invariant relationship 987 which can be used to deduce that two registers with unknown values 988 are different. */ 989 990void 991record_base_value (regno, val, invariant) 992 unsigned int regno; 993 rtx val; 994 int invariant; 995{ 996 if (regno >= reg_base_value_size) 997 return; 998 999 if (invariant && alias_invariant) 1000 alias_invariant[regno] = val; 1001 1002 if (GET_CODE (val) == REG) 1003 { 1004 if (REGNO (val) < reg_base_value_size) 1005 reg_base_value[regno] = reg_base_value[REGNO (val)]; 1006 1007 return; 1008 } 1009 1010 reg_base_value[regno] = find_base_value (val); 1011} 1012 1013/* Clear alias info for a register. This is used if an RTL transformation 1014 changes the value of a register. This is used in flow by AUTO_INC_DEC 1015 optimizations. We don't need to clear reg_base_value, since flow only 1016 changes the offset. */ 1017 1018void 1019clear_reg_alias_info (reg) 1020 rtx reg; 1021{ 1022 unsigned int regno = REGNO (reg); 1023 1024 if (regno < reg_known_value_size && regno >= FIRST_PSEUDO_REGISTER) 1025 reg_known_value[regno] = reg; 1026} 1027 1028/* Returns a canonical version of X, from the point of view alias 1029 analysis. (For example, if X is a MEM whose address is a register, 1030 and the register has a known value (say a SYMBOL_REF), then a MEM 1031 whose address is the SYMBOL_REF is returned.) */ 1032 1033rtx 1034canon_rtx (x) 1035 rtx x; 1036{ 1037 /* Recursively look for equivalences. */ 1038 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER 1039 && REGNO (x) < reg_known_value_size) 1040 return reg_known_value[REGNO (x)] == x 1041 ? x : canon_rtx (reg_known_value[REGNO (x)]); 1042 else if (GET_CODE (x) == PLUS) 1043 { 1044 rtx x0 = canon_rtx (XEXP (x, 0)); 1045 rtx x1 = canon_rtx (XEXP (x, 1)); 1046 1047 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1)) 1048 { 1049 if (GET_CODE (x0) == CONST_INT) 1050 return plus_constant (x1, INTVAL (x0)); 1051 else if (GET_CODE (x1) == CONST_INT) 1052 return plus_constant (x0, INTVAL (x1)); 1053 return gen_rtx_PLUS (GET_MODE (x), x0, x1); 1054 } 1055 } 1056 1057 /* This gives us much better alias analysis when called from 1058 the loop optimizer. Note we want to leave the original 1059 MEM alone, but need to return the canonicalized MEM with 1060 all the flags with their original values. */ 1061 else if (GET_CODE (x) == MEM) 1062 x = replace_equiv_address_nv (x, canon_rtx (XEXP (x, 0))); 1063 1064 return x; 1065} 1066 1067/* Return 1 if X and Y are identical-looking rtx's. 1068 1069 We use the data in reg_known_value above to see if two registers with 1070 different numbers are, in fact, equivalent. */ 1071 1072static int 1073rtx_equal_for_memref_p (x, y) 1074 rtx x, y; 1075{ 1076 int i; 1077 int j; 1078 enum rtx_code code; 1079 const char *fmt; 1080 1081 if (x == 0 && y == 0) 1082 return 1; 1083 if (x == 0 || y == 0) 1084 return 0; 1085 1086 x = canon_rtx (x); 1087 y = canon_rtx (y); 1088 1089 if (x == y) 1090 return 1; 1091 1092 code = GET_CODE (x); 1093 /* Rtx's of different codes cannot be equal. */ 1094 if (code != GET_CODE (y)) 1095 return 0; 1096 1097 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. 1098 (REG:SI x) and (REG:HI x) are NOT equivalent. */ 1099 1100 if (GET_MODE (x) != GET_MODE (y)) 1101 return 0; 1102 1103 /* Some RTL can be compared without a recursive examination. */ 1104 switch (code) 1105 { 1106 case VALUE: 1107 return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y); 1108 1109 case REG: 1110 return REGNO (x) == REGNO (y); 1111 1112 case LABEL_REF: 1113 return XEXP (x, 0) == XEXP (y, 0); 1114 1115 case SYMBOL_REF: 1116 return XSTR (x, 0) == XSTR (y, 0); 1117 1118 case CONST_INT: 1119 case CONST_DOUBLE: 1120 /* There's no need to compare the contents of CONST_DOUBLEs or 1121 CONST_INTs because pointer equality is a good enough 1122 comparison for these nodes. */ 1123 return 0; 1124 1125 case ADDRESSOF: 1126 return (XINT (x, 1) == XINT (y, 1) 1127 && rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0))); 1128 1129 default: 1130 break; 1131 } 1132 1133 /* For commutative operations, the RTX match if the operand match in any 1134 order. Also handle the simple binary and unary cases without a loop. */ 1135 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c') 1136 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)) 1137 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1))) 1138 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1)) 1139 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0)))); 1140 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2') 1141 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)) 1142 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1))); 1143 else if (GET_RTX_CLASS (code) == '1') 1144 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)); 1145 1146 /* Compare the elements. If any pair of corresponding elements 1147 fail to match, return 0 for the whole things. 1148 1149 Limit cases to types which actually appear in addresses. */ 1150 1151 fmt = GET_RTX_FORMAT (code); 1152 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1153 { 1154 switch (fmt[i]) 1155 { 1156 case 'i': 1157 if (XINT (x, i) != XINT (y, i)) 1158 return 0; 1159 break; 1160 1161 case 'E': 1162 /* Two vectors must have the same length. */ 1163 if (XVECLEN (x, i) != XVECLEN (y, i)) 1164 return 0; 1165 1166 /* And the corresponding elements must match. */ 1167 for (j = 0; j < XVECLEN (x, i); j++) 1168 if (rtx_equal_for_memref_p (XVECEXP (x, i, j), 1169 XVECEXP (y, i, j)) == 0) 1170 return 0; 1171 break; 1172 1173 case 'e': 1174 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0) 1175 return 0; 1176 break; 1177 1178 /* This can happen for asm operands. */ 1179 case 's': 1180 if (strcmp (XSTR (x, i), XSTR (y, i))) 1181 return 0; 1182 break; 1183 1184 /* This can happen for an asm which clobbers memory. */ 1185 case '0': 1186 break; 1187 1188 /* It is believed that rtx's at this level will never 1189 contain anything but integers and other rtx's, 1190 except for within LABEL_REFs and SYMBOL_REFs. */ 1191 default: 1192 abort (); 1193 } 1194 } 1195 return 1; 1196} 1197 1198/* Given an rtx X, find a SYMBOL_REF or LABEL_REF within 1199 X and return it, or return 0 if none found. */ 1200 1201static rtx 1202find_symbolic_term (x) 1203 rtx x; 1204{ 1205 int i; 1206 enum rtx_code code; 1207 const char *fmt; 1208 1209 code = GET_CODE (x); 1210 if (code == SYMBOL_REF || code == LABEL_REF) 1211 return x; 1212 if (GET_RTX_CLASS (code) == 'o') 1213 return 0; 1214 1215 fmt = GET_RTX_FORMAT (code); 1216 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1217 { 1218 rtx t; 1219 1220 if (fmt[i] == 'e') 1221 { 1222 t = find_symbolic_term (XEXP (x, i)); 1223 if (t != 0) 1224 return t; 1225 } 1226 else if (fmt[i] == 'E') 1227 break; 1228 } 1229 return 0; 1230} 1231 1232static rtx 1233find_base_term (x) 1234 rtx x; 1235{ 1236 cselib_val *val; 1237 struct elt_loc_list *l; 1238 1239#if defined (FIND_BASE_TERM) 1240 /* Try machine-dependent ways to find the base term. */ 1241 x = FIND_BASE_TERM (x); 1242#endif 1243 1244 switch (GET_CODE (x)) 1245 { 1246 case REG: 1247 return REG_BASE_VALUE (x); 1248 1249 case TRUNCATE: 1250 if (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (Pmode)) 1251 return 0; 1252 /* Fall through. */ 1253 case HIGH: 1254 case PRE_INC: 1255 case PRE_DEC: 1256 case POST_INC: 1257 case POST_DEC: 1258 case PRE_MODIFY: 1259 case POST_MODIFY: 1260 return find_base_term (XEXP (x, 0)); 1261 1262 case ZERO_EXTEND: 1263 case SIGN_EXTEND: /* Used for Alpha/NT pointers */ 1264 { 1265 rtx temp = find_base_term (XEXP (x, 0)); 1266 1267#ifdef POINTERS_EXTEND_UNSIGNED 1268 if (temp != 0 && CONSTANT_P (temp) && GET_MODE (temp) != Pmode) 1269 temp = convert_memory_address (Pmode, temp); 1270#endif 1271 1272 return temp; 1273 } 1274 1275 case VALUE: 1276 val = CSELIB_VAL_PTR (x); 1277 for (l = val->locs; l; l = l->next) 1278 if ((x = find_base_term (l->loc)) != 0) 1279 return x; 1280 return 0; 1281 1282 case CONST: 1283 x = XEXP (x, 0); 1284 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS) 1285 return 0; 1286 /* fall through */ 1287 case LO_SUM: 1288 case PLUS: 1289 case MINUS: 1290 { 1291 rtx tmp1 = XEXP (x, 0); 1292 rtx tmp2 = XEXP (x, 1); 1293 1294 /* This is a little bit tricky since we have to determine which of 1295 the two operands represents the real base address. Otherwise this 1296 routine may return the index register instead of the base register. 1297 1298 That may cause us to believe no aliasing was possible, when in 1299 fact aliasing is possible. 1300 1301 We use a few simple tests to guess the base register. Additional 1302 tests can certainly be added. For example, if one of the operands 1303 is a shift or multiply, then it must be the index register and the 1304 other operand is the base register. */ 1305 1306 if (tmp1 == pic_offset_table_rtx && CONSTANT_P (tmp2)) 1307 return find_base_term (tmp2); 1308 1309 /* If either operand is known to be a pointer, then use it 1310 to determine the base term. */ 1311 if (REG_P (tmp1) && REG_POINTER (tmp1)) 1312 return find_base_term (tmp1); 1313 1314 if (REG_P (tmp2) && REG_POINTER (tmp2)) 1315 return find_base_term (tmp2); 1316 1317 /* Neither operand was known to be a pointer. Go ahead and find the 1318 base term for both operands. */ 1319 tmp1 = find_base_term (tmp1); 1320 tmp2 = find_base_term (tmp2); 1321 1322 /* If either base term is named object or a special address 1323 (like an argument or stack reference), then use it for the 1324 base term. */ 1325 if (tmp1 != 0 1326 && (GET_CODE (tmp1) == SYMBOL_REF 1327 || GET_CODE (tmp1) == LABEL_REF 1328 || (GET_CODE (tmp1) == ADDRESS 1329 && GET_MODE (tmp1) != VOIDmode))) 1330 return tmp1; 1331 1332 if (tmp2 != 0 1333 && (GET_CODE (tmp2) == SYMBOL_REF 1334 || GET_CODE (tmp2) == LABEL_REF 1335 || (GET_CODE (tmp2) == ADDRESS 1336 && GET_MODE (tmp2) != VOIDmode))) 1337 return tmp2; 1338 1339 /* We could not determine which of the two operands was the 1340 base register and which was the index. So we can determine 1341 nothing from the base alias check. */ 1342 return 0; 1343 } 1344 1345 case AND: 1346 if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) != 0) 1347 return find_base_term (XEXP (x, 0)); 1348 return 0; 1349 1350 case SYMBOL_REF: 1351 case LABEL_REF: 1352 return x; 1353 1354 case ADDRESSOF: 1355 return REG_BASE_VALUE (frame_pointer_rtx); 1356 1357 default: 1358 return 0; 1359 } 1360} 1361 1362/* Return 0 if the addresses X and Y are known to point to different 1363 objects, 1 if they might be pointers to the same object. */ 1364 1365static int 1366base_alias_check (x, y, x_mode, y_mode) 1367 rtx x, y; 1368 enum machine_mode x_mode, y_mode; 1369{ 1370 rtx x_base = find_base_term (x); 1371 rtx y_base = find_base_term (y); 1372 1373 /* If the address itself has no known base see if a known equivalent 1374 value has one. If either address still has no known base, nothing 1375 is known about aliasing. */ 1376 if (x_base == 0) 1377 { 1378 rtx x_c; 1379 1380 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x) 1381 return 1; 1382 1383 x_base = find_base_term (x_c); 1384 if (x_base == 0) 1385 return 1; 1386 } 1387 1388 if (y_base == 0) 1389 { 1390 rtx y_c; 1391 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y) 1392 return 1; 1393 1394 y_base = find_base_term (y_c); 1395 if (y_base == 0) 1396 return 1; 1397 } 1398 1399 /* If the base addresses are equal nothing is known about aliasing. */ 1400 if (rtx_equal_p (x_base, y_base)) 1401 return 1; 1402 1403 /* The base addresses of the read and write are different expressions. 1404 If they are both symbols and they are not accessed via AND, there is 1405 no conflict. We can bring knowledge of object alignment into play 1406 here. For example, on alpha, "char a, b;" can alias one another, 1407 though "char a; long b;" cannot. */ 1408 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS) 1409 { 1410 if (GET_CODE (x) == AND && GET_CODE (y) == AND) 1411 return 1; 1412 if (GET_CODE (x) == AND 1413 && (GET_CODE (XEXP (x, 1)) != CONST_INT 1414 || (int) GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1)))) 1415 return 1; 1416 if (GET_CODE (y) == AND 1417 && (GET_CODE (XEXP (y, 1)) != CONST_INT 1418 || (int) GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1)))) 1419 return 1; 1420 /* Differing symbols never alias. */ 1421 return 0; 1422 } 1423 1424 /* If one address is a stack reference there can be no alias: 1425 stack references using different base registers do not alias, 1426 a stack reference can not alias a parameter, and a stack reference 1427 can not alias a global. */ 1428 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode) 1429 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode)) 1430 return 0; 1431 1432 if (! flag_argument_noalias) 1433 return 1; 1434 1435 if (flag_argument_noalias > 1) 1436 return 0; 1437 1438 /* Weak noalias assertion (arguments are distinct, but may match globals). */ 1439 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode); 1440} 1441 1442/* Convert the address X into something we can use. This is done by returning 1443 it unchanged unless it is a value; in the latter case we call cselib to get 1444 a more useful rtx. */ 1445 1446rtx 1447get_addr (x) 1448 rtx x; 1449{ 1450 cselib_val *v; 1451 struct elt_loc_list *l; 1452 1453 if (GET_CODE (x) != VALUE) 1454 return x; 1455 v = CSELIB_VAL_PTR (x); 1456 for (l = v->locs; l; l = l->next) 1457 if (CONSTANT_P (l->loc)) 1458 return l->loc; 1459 for (l = v->locs; l; l = l->next) 1460 if (GET_CODE (l->loc) != REG && GET_CODE (l->loc) != MEM) 1461 return l->loc; 1462 if (v->locs) 1463 return v->locs->loc; 1464 return x; 1465} 1466 1467/* Return the address of the (N_REFS + 1)th memory reference to ADDR 1468 where SIZE is the size in bytes of the memory reference. If ADDR 1469 is not modified by the memory reference then ADDR is returned. */ 1470 1471rtx 1472addr_side_effect_eval (addr, size, n_refs) 1473 rtx addr; 1474 int size; 1475 int n_refs; 1476{ 1477 int offset = 0; 1478 1479 switch (GET_CODE (addr)) 1480 { 1481 case PRE_INC: 1482 offset = (n_refs + 1) * size; 1483 break; 1484 case PRE_DEC: 1485 offset = -(n_refs + 1) * size; 1486 break; 1487 case POST_INC: 1488 offset = n_refs * size; 1489 break; 1490 case POST_DEC: 1491 offset = -n_refs * size; 1492 break; 1493 1494 default: 1495 return addr; 1496 } 1497 1498 if (offset) 1499 addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0), GEN_INT (offset)); 1500 else 1501 addr = XEXP (addr, 0); 1502 1503 return addr; 1504} 1505 1506/* Return nonzero if X and Y (memory addresses) could reference the 1507 same location in memory. C is an offset accumulator. When 1508 C is nonzero, we are testing aliases between X and Y + C. 1509 XSIZE is the size in bytes of the X reference, 1510 similarly YSIZE is the size in bytes for Y. 1511 1512 If XSIZE or YSIZE is zero, we do not know the amount of memory being 1513 referenced (the reference was BLKmode), so make the most pessimistic 1514 assumptions. 1515 1516 If XSIZE or YSIZE is negative, we may access memory outside the object 1517 being referenced as a side effect. This can happen when using AND to 1518 align memory references, as is done on the Alpha. 1519 1520 Nice to notice that varying addresses cannot conflict with fp if no 1521 local variables had their addresses taken, but that's too hard now. */ 1522 1523static int 1524memrefs_conflict_p (xsize, x, ysize, y, c) 1525 rtx x, y; 1526 int xsize, ysize; 1527 HOST_WIDE_INT c; 1528{ 1529 if (GET_CODE (x) == VALUE) 1530 x = get_addr (x); 1531 if (GET_CODE (y) == VALUE) 1532 y = get_addr (y); 1533 if (GET_CODE (x) == HIGH) 1534 x = XEXP (x, 0); 1535 else if (GET_CODE (x) == LO_SUM) 1536 x = XEXP (x, 1); 1537 else 1538 x = canon_rtx (addr_side_effect_eval (x, xsize, 0)); 1539 if (GET_CODE (y) == HIGH) 1540 y = XEXP (y, 0); 1541 else if (GET_CODE (y) == LO_SUM) 1542 y = XEXP (y, 1); 1543 else 1544 y = canon_rtx (addr_side_effect_eval (y, ysize, 0)); 1545 1546 if (rtx_equal_for_memref_p (x, y)) 1547 { 1548 if (xsize <= 0 || ysize <= 0) 1549 return 1; 1550 if (c >= 0 && xsize > c) 1551 return 1; 1552 if (c < 0 && ysize+c > 0) 1553 return 1; 1554 return 0; 1555 } 1556 1557 /* This code used to check for conflicts involving stack references and 1558 globals but the base address alias code now handles these cases. */ 1559 1560 if (GET_CODE (x) == PLUS) 1561 { 1562 /* The fact that X is canonicalized means that this 1563 PLUS rtx is canonicalized. */ 1564 rtx x0 = XEXP (x, 0); 1565 rtx x1 = XEXP (x, 1); 1566 1567 if (GET_CODE (y) == PLUS) 1568 { 1569 /* The fact that Y is canonicalized means that this 1570 PLUS rtx is canonicalized. */ 1571 rtx y0 = XEXP (y, 0); 1572 rtx y1 = XEXP (y, 1); 1573 1574 if (rtx_equal_for_memref_p (x1, y1)) 1575 return memrefs_conflict_p (xsize, x0, ysize, y0, c); 1576 if (rtx_equal_for_memref_p (x0, y0)) 1577 return memrefs_conflict_p (xsize, x1, ysize, y1, c); 1578 if (GET_CODE (x1) == CONST_INT) 1579 { 1580 if (GET_CODE (y1) == CONST_INT) 1581 return memrefs_conflict_p (xsize, x0, ysize, y0, 1582 c - INTVAL (x1) + INTVAL (y1)); 1583 else 1584 return memrefs_conflict_p (xsize, x0, ysize, y, 1585 c - INTVAL (x1)); 1586 } 1587 else if (GET_CODE (y1) == CONST_INT) 1588 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1)); 1589 1590 return 1; 1591 } 1592 else if (GET_CODE (x1) == CONST_INT) 1593 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1)); 1594 } 1595 else if (GET_CODE (y) == PLUS) 1596 { 1597 /* The fact that Y is canonicalized means that this 1598 PLUS rtx is canonicalized. */ 1599 rtx y0 = XEXP (y, 0); 1600 rtx y1 = XEXP (y, 1); 1601 1602 if (GET_CODE (y1) == CONST_INT) 1603 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1)); 1604 else 1605 return 1; 1606 } 1607 1608 if (GET_CODE (x) == GET_CODE (y)) 1609 switch (GET_CODE (x)) 1610 { 1611 case MULT: 1612 { 1613 /* Handle cases where we expect the second operands to be the 1614 same, and check only whether the first operand would conflict 1615 or not. */ 1616 rtx x0, y0; 1617 rtx x1 = canon_rtx (XEXP (x, 1)); 1618 rtx y1 = canon_rtx (XEXP (y, 1)); 1619 if (! rtx_equal_for_memref_p (x1, y1)) 1620 return 1; 1621 x0 = canon_rtx (XEXP (x, 0)); 1622 y0 = canon_rtx (XEXP (y, 0)); 1623 if (rtx_equal_for_memref_p (x0, y0)) 1624 return (xsize == 0 || ysize == 0 1625 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); 1626 1627 /* Can't properly adjust our sizes. */ 1628 if (GET_CODE (x1) != CONST_INT) 1629 return 1; 1630 xsize /= INTVAL (x1); 1631 ysize /= INTVAL (x1); 1632 c /= INTVAL (x1); 1633 return memrefs_conflict_p (xsize, x0, ysize, y0, c); 1634 } 1635 1636 case REG: 1637 /* Are these registers known not to be equal? */ 1638 if (alias_invariant) 1639 { 1640 unsigned int r_x = REGNO (x), r_y = REGNO (y); 1641 rtx i_x, i_y; /* invariant relationships of X and Y */ 1642 1643 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x]; 1644 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y]; 1645 1646 if (i_x == 0 && i_y == 0) 1647 break; 1648 1649 if (! memrefs_conflict_p (xsize, i_x ? i_x : x, 1650 ysize, i_y ? i_y : y, c)) 1651 return 0; 1652 } 1653 break; 1654 1655 default: 1656 break; 1657 } 1658 1659 /* Treat an access through an AND (e.g. a subword access on an Alpha) 1660 as an access with indeterminate size. Assume that references 1661 besides AND are aligned, so if the size of the other reference is 1662 at least as large as the alignment, assume no other overlap. */ 1663 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT) 1664 { 1665 if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1))) 1666 xsize = -1; 1667 return memrefs_conflict_p (xsize, XEXP (x, 0), ysize, y, c); 1668 } 1669 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT) 1670 { 1671 /* ??? If we are indexing far enough into the array/structure, we 1672 may yet be able to determine that we can not overlap. But we 1673 also need to that we are far enough from the end not to overlap 1674 a following reference, so we do nothing with that for now. */ 1675 if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1))) 1676 ysize = -1; 1677 return memrefs_conflict_p (xsize, x, ysize, XEXP (y, 0), c); 1678 } 1679 1680 if (GET_CODE (x) == ADDRESSOF) 1681 { 1682 if (y == frame_pointer_rtx 1683 || GET_CODE (y) == ADDRESSOF) 1684 return xsize <= 0 || ysize <= 0; 1685 } 1686 if (GET_CODE (y) == ADDRESSOF) 1687 { 1688 if (x == frame_pointer_rtx) 1689 return xsize <= 0 || ysize <= 0; 1690 } 1691 1692 if (CONSTANT_P (x)) 1693 { 1694 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT) 1695 { 1696 c += (INTVAL (y) - INTVAL (x)); 1697 return (xsize <= 0 || ysize <= 0 1698 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); 1699 } 1700 1701 if (GET_CODE (x) == CONST) 1702 { 1703 if (GET_CODE (y) == CONST) 1704 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 1705 ysize, canon_rtx (XEXP (y, 0)), c); 1706 else 1707 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 1708 ysize, y, c); 1709 } 1710 if (GET_CODE (y) == CONST) 1711 return memrefs_conflict_p (xsize, x, ysize, 1712 canon_rtx (XEXP (y, 0)), c); 1713 1714 if (CONSTANT_P (y)) 1715 return (xsize <= 0 || ysize <= 0 1716 || (rtx_equal_for_memref_p (x, y) 1717 && ((c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)))); 1718 1719 return 1; 1720 } 1721 return 1; 1722} 1723 1724/* Functions to compute memory dependencies. 1725 1726 Since we process the insns in execution order, we can build tables 1727 to keep track of what registers are fixed (and not aliased), what registers 1728 are varying in known ways, and what registers are varying in unknown 1729 ways. 1730 1731 If both memory references are volatile, then there must always be a 1732 dependence between the two references, since their order can not be 1733 changed. A volatile and non-volatile reference can be interchanged 1734 though. 1735 1736 A MEM_IN_STRUCT reference at a non-AND varying address can never 1737 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We 1738 also must allow AND addresses, because they may generate accesses 1739 outside the object being referenced. This is used to generate 1740 aligned addresses from unaligned addresses, for instance, the alpha 1741 storeqi_unaligned pattern. */ 1742 1743/* Read dependence: X is read after read in MEM takes place. There can 1744 only be a dependence here if both reads are volatile. */ 1745 1746int 1747read_dependence (mem, x) 1748 rtx mem; 1749 rtx x; 1750{ 1751 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem); 1752} 1753 1754/* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and 1755 MEM2 is a reference to a structure at a varying address, or returns 1756 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL 1757 value is returned MEM1 and MEM2 can never alias. VARIES_P is used 1758 to decide whether or not an address may vary; it should return 1759 nonzero whenever variation is possible. 1760 MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */ 1761 1762static rtx 1763fixed_scalar_and_varying_struct_p (mem1, mem2, mem1_addr, mem2_addr, varies_p) 1764 rtx mem1, mem2; 1765 rtx mem1_addr, mem2_addr; 1766 int (*varies_p) PARAMS ((rtx, int)); 1767{ 1768 if (! flag_strict_aliasing) 1769 return NULL_RTX; 1770 1771 if (MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2) 1772 && !varies_p (mem1_addr, 1) && varies_p (mem2_addr, 1)) 1773 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a 1774 varying address. */ 1775 return mem1; 1776 1777 if (MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2) 1778 && varies_p (mem1_addr, 1) && !varies_p (mem2_addr, 1)) 1779 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a 1780 varying address. */ 1781 return mem2; 1782 1783 return NULL_RTX; 1784} 1785 1786/* Returns nonzero if something about the mode or address format MEM1 1787 indicates that it might well alias *anything*. */ 1788 1789static int 1790aliases_everything_p (mem) 1791 rtx mem; 1792{ 1793 if (GET_CODE (XEXP (mem, 0)) == AND) 1794 /* If the address is an AND, its very hard to know at what it is 1795 actually pointing. */ 1796 return 1; 1797 1798 return 0; 1799} 1800 1801/* Return true if we can determine that the fields referenced cannot 1802 overlap for any pair of objects. */ 1803 1804static bool 1805nonoverlapping_component_refs_p (x, y) 1806 tree x, y; 1807{ 1808 tree fieldx, fieldy, typex, typey, orig_y; 1809 1810 do 1811 { 1812 /* The comparison has to be done at a common type, since we don't 1813 know how the inheritance hierarchy works. */ 1814 orig_y = y; 1815 do 1816 { 1817 fieldx = TREE_OPERAND (x, 1); 1818 typex = DECL_FIELD_CONTEXT (fieldx); 1819 1820 y = orig_y; 1821 do 1822 { 1823 fieldy = TREE_OPERAND (y, 1); 1824 typey = DECL_FIELD_CONTEXT (fieldy); 1825 1826 if (typex == typey) 1827 goto found; 1828 1829 y = TREE_OPERAND (y, 0); 1830 } 1831 while (y && TREE_CODE (y) == COMPONENT_REF); 1832 1833 x = TREE_OPERAND (x, 0); 1834 } 1835 while (x && TREE_CODE (x) == COMPONENT_REF); 1836 1837 /* Never found a common type. */ 1838 return false; 1839 1840 found: 1841 /* If we're left with accessing different fields of a structure, 1842 then no overlap. */ 1843 if (TREE_CODE (typex) == RECORD_TYPE 1844 && fieldx != fieldy) 1845 return true; 1846 1847 /* The comparison on the current field failed. If we're accessing 1848 a very nested structure, look at the next outer level. */ 1849 x = TREE_OPERAND (x, 0); 1850 y = TREE_OPERAND (y, 0); 1851 } 1852 while (x && y 1853 && TREE_CODE (x) == COMPONENT_REF 1854 && TREE_CODE (y) == COMPONENT_REF); 1855 1856 return false; 1857} 1858 1859/* Look at the bottom of the COMPONENT_REF list for a DECL, and return it. */ 1860 1861static tree 1862decl_for_component_ref (x) 1863 tree x; 1864{ 1865 do 1866 { 1867 x = TREE_OPERAND (x, 0); 1868 } 1869 while (x && TREE_CODE (x) == COMPONENT_REF); 1870 1871 return x && DECL_P (x) ? x : NULL_TREE; 1872} 1873 1874/* Walk up the COMPONENT_REF list and adjust OFFSET to compensate for the 1875 offset of the field reference. */ 1876 1877static rtx 1878adjust_offset_for_component_ref (x, offset) 1879 tree x; 1880 rtx offset; 1881{ 1882 HOST_WIDE_INT ioffset; 1883 1884 if (! offset) 1885 return NULL_RTX; 1886 1887 ioffset = INTVAL (offset); 1888 do 1889 { 1890 tree field = TREE_OPERAND (x, 1); 1891 1892 if (! host_integerp (DECL_FIELD_OFFSET (field), 1)) 1893 return NULL_RTX; 1894 ioffset += (tree_low_cst (DECL_FIELD_OFFSET (field), 1) 1895 + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1) 1896 / BITS_PER_UNIT)); 1897 1898 x = TREE_OPERAND (x, 0); 1899 } 1900 while (x && TREE_CODE (x) == COMPONENT_REF); 1901 1902 return GEN_INT (ioffset); 1903} 1904 1905/* Return nonzero if we can deterimine the exprs corresponding to memrefs 1906 X and Y and they do not overlap. */ 1907 1908static int 1909nonoverlapping_memrefs_p (x, y) 1910 rtx x, y; 1911{ 1912 tree exprx = MEM_EXPR (x), expry = MEM_EXPR (y); 1913 rtx rtlx, rtly; 1914 rtx basex, basey; 1915 rtx moffsetx, moffsety; 1916 HOST_WIDE_INT offsetx = 0, offsety = 0, sizex, sizey, tem; 1917 1918 /* Unless both have exprs, we can't tell anything. */ 1919 if (exprx == 0 || expry == 0) 1920 return 0; 1921 1922 /* If both are field references, we may be able to determine something. */ 1923 if (TREE_CODE (exprx) == COMPONENT_REF 1924 && TREE_CODE (expry) == COMPONENT_REF 1925 && nonoverlapping_component_refs_p (exprx, expry)) 1926 return 1; 1927 1928 /* If the field reference test failed, look at the DECLs involved. */ 1929 moffsetx = MEM_OFFSET (x); 1930 if (TREE_CODE (exprx) == COMPONENT_REF) 1931 { 1932 tree t = decl_for_component_ref (exprx); 1933 if (! t) 1934 return 0; 1935 moffsetx = adjust_offset_for_component_ref (exprx, moffsetx); 1936 exprx = t; 1937 } 1938 else if (TREE_CODE (exprx) == INDIRECT_REF) 1939 { 1940 exprx = TREE_OPERAND (exprx, 0); 1941 if (flag_argument_noalias < 2 1942 || TREE_CODE (exprx) != PARM_DECL) 1943 return 0; 1944 } 1945 1946 moffsety = MEM_OFFSET (y); 1947 if (TREE_CODE (expry) == COMPONENT_REF) 1948 { 1949 tree t = decl_for_component_ref (expry); 1950 if (! t) 1951 return 0; 1952 moffsety = adjust_offset_for_component_ref (expry, moffsety); 1953 expry = t; 1954 } 1955 else if (TREE_CODE (expry) == INDIRECT_REF) 1956 { 1957 expry = TREE_OPERAND (expry, 0); 1958 if (flag_argument_noalias < 2 1959 || TREE_CODE (expry) != PARM_DECL) 1960 return 0; 1961 } 1962 1963 if (! DECL_P (exprx) || ! DECL_P (expry)) 1964 return 0; 1965 1966 rtlx = DECL_RTL (exprx); 1967 rtly = DECL_RTL (expry); 1968 1969 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they 1970 can't overlap unless they are the same because we never reuse that part 1971 of the stack frame used for locals for spilled pseudos. */ 1972 if ((GET_CODE (rtlx) != MEM || GET_CODE (rtly) != MEM) 1973 && ! rtx_equal_p (rtlx, rtly)) 1974 return 1; 1975 1976 /* Get the base and offsets of both decls. If either is a register, we 1977 know both are and are the same, so use that as the base. The only 1978 we can avoid overlap is if we can deduce that they are nonoverlapping 1979 pieces of that decl, which is very rare. */ 1980 basex = GET_CODE (rtlx) == MEM ? XEXP (rtlx, 0) : rtlx; 1981 if (GET_CODE (basex) == PLUS && GET_CODE (XEXP (basex, 1)) == CONST_INT) 1982 offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0); 1983 1984 basey = GET_CODE (rtly) == MEM ? XEXP (rtly, 0) : rtly; 1985 if (GET_CODE (basey) == PLUS && GET_CODE (XEXP (basey, 1)) == CONST_INT) 1986 offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0); 1987 1988 /* If the bases are different, we know they do not overlap if both 1989 are constants or if one is a constant and the other a pointer into the 1990 stack frame. Otherwise a different base means we can't tell if they 1991 overlap or not. */ 1992 if (! rtx_equal_p (basex, basey)) 1993 return ((CONSTANT_P (basex) && CONSTANT_P (basey)) 1994 || (CONSTANT_P (basex) && REG_P (basey) 1995 && REGNO_PTR_FRAME_P (REGNO (basey))) 1996 || (CONSTANT_P (basey) && REG_P (basex) 1997 && REGNO_PTR_FRAME_P (REGNO (basex)))); 1998 1999 sizex = (GET_CODE (rtlx) != MEM ? (int) GET_MODE_SIZE (GET_MODE (rtlx)) 2000 : MEM_SIZE (rtlx) ? INTVAL (MEM_SIZE (rtlx)) 2001 : -1); 2002 sizey = (GET_CODE (rtly) != MEM ? (int) GET_MODE_SIZE (GET_MODE (rtly)) 2003 : MEM_SIZE (rtly) ? INTVAL (MEM_SIZE (rtly)) : 2004 -1); 2005 2006 /* If we have an offset for either memref, it can update the values computed 2007 above. */ 2008 if (moffsetx) 2009 offsetx += INTVAL (moffsetx), sizex -= INTVAL (moffsetx); 2010 if (moffsety) 2011 offsety += INTVAL (moffsety), sizey -= INTVAL (moffsety); 2012 2013 /* If a memref has both a size and an offset, we can use the smaller size. 2014 We can't do this if the offset isn't known because we must view this 2015 memref as being anywhere inside the DECL's MEM. */ 2016 if (MEM_SIZE (x) && moffsetx) 2017 sizex = INTVAL (MEM_SIZE (x)); 2018 if (MEM_SIZE (y) && moffsety) 2019 sizey = INTVAL (MEM_SIZE (y)); 2020 2021 /* Put the values of the memref with the lower offset in X's values. */ 2022 if (offsetx > offsety) 2023 { 2024 tem = offsetx, offsetx = offsety, offsety = tem; 2025 tem = sizex, sizex = sizey, sizey = tem; 2026 } 2027 2028 /* If we don't know the size of the lower-offset value, we can't tell 2029 if they conflict. Otherwise, we do the test. */ 2030 return sizex >= 0 && offsety >= offsetx + sizex; 2031} 2032 2033/* True dependence: X is read after store in MEM takes place. */ 2034 2035int 2036true_dependence (mem, mem_mode, x, varies) 2037 rtx mem; 2038 enum machine_mode mem_mode; 2039 rtx x; 2040 int (*varies) PARAMS ((rtx, int)); 2041{ 2042 rtx x_addr, mem_addr; 2043 rtx base; 2044 2045 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 2046 return 1; 2047 2048 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 2049 This is used in epilogue deallocation functions. */ 2050 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 2051 return 1; 2052 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 2053 return 1; 2054 2055 if (DIFFERENT_ALIAS_SETS_P (x, mem)) 2056 return 0; 2057 2058 /* Unchanging memory can't conflict with non-unchanging memory. 2059 A non-unchanging read can conflict with a non-unchanging write. 2060 An unchanging read can conflict with an unchanging write since 2061 there may be a single store to this address to initialize it. 2062 Note that an unchanging store can conflict with a non-unchanging read 2063 since we have to make conservative assumptions when we have a 2064 record with readonly fields and we are copying the whole thing. 2065 Just fall through to the code below to resolve potential conflicts. 2066 This won't handle all cases optimally, but the possible performance 2067 loss should be negligible. */ 2068 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem)) 2069 return 0; 2070 2071 if (nonoverlapping_memrefs_p (mem, x)) 2072 return 0; 2073 2074 if (mem_mode == VOIDmode) 2075 mem_mode = GET_MODE (mem); 2076 2077 x_addr = get_addr (XEXP (x, 0)); 2078 mem_addr = get_addr (XEXP (mem, 0)); 2079 2080 base = find_base_term (x_addr); 2081 if (base && (GET_CODE (base) == LABEL_REF 2082 || (GET_CODE (base) == SYMBOL_REF 2083 && CONSTANT_POOL_ADDRESS_P (base)))) 2084 return 0; 2085 2086 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode)) 2087 return 0; 2088 2089 x_addr = canon_rtx (x_addr); 2090 mem_addr = canon_rtx (mem_addr); 2091 2092 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr, 2093 SIZE_FOR_MODE (x), x_addr, 0)) 2094 return 0; 2095 2096 if (aliases_everything_p (x)) 2097 return 1; 2098 2099 /* We cannot use aliases_everything_p to test MEM, since we must look 2100 at MEM_MODE, rather than GET_MODE (MEM). */ 2101 if (mem_mode == QImode || GET_CODE (mem_addr) == AND) 2102 return 1; 2103 2104 /* In true_dependence we also allow BLKmode to alias anything. Why 2105 don't we do this in anti_dependence and output_dependence? */ 2106 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode) 2107 return 1; 2108 2109 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, 2110 varies); 2111} 2112 2113/* Canonical true dependence: X is read after store in MEM takes place. 2114 Variant of true_dependence which assumes MEM has already been 2115 canonicalized (hence we no longer do that here). 2116 The mem_addr argument has been added, since true_dependence computed 2117 this value prior to canonicalizing. */ 2118 2119int 2120canon_true_dependence (mem, mem_mode, mem_addr, x, varies) 2121 rtx mem, mem_addr, x; 2122 enum machine_mode mem_mode; 2123 int (*varies) PARAMS ((rtx, int)); 2124{ 2125 rtx x_addr; 2126 2127 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 2128 return 1; 2129 2130 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 2131 This is used in epilogue deallocation functions. */ 2132 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 2133 return 1; 2134 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 2135 return 1; 2136 2137 if (DIFFERENT_ALIAS_SETS_P (x, mem)) 2138 return 0; 2139 2140 /* If X is an unchanging read, then it can't possibly conflict with any 2141 non-unchanging store. It may conflict with an unchanging write though, 2142 because there may be a single store to this address to initialize it. 2143 Just fall through to the code below to resolve the case where we have 2144 both an unchanging read and an unchanging write. This won't handle all 2145 cases optimally, but the possible performance loss should be 2146 negligible. */ 2147 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem)) 2148 return 0; 2149 2150 if (nonoverlapping_memrefs_p (x, mem)) 2151 return 0; 2152 2153 x_addr = get_addr (XEXP (x, 0)); 2154 2155 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode)) 2156 return 0; 2157 2158 x_addr = canon_rtx (x_addr); 2159 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr, 2160 SIZE_FOR_MODE (x), x_addr, 0)) 2161 return 0; 2162 2163 if (aliases_everything_p (x)) 2164 return 1; 2165 2166 /* We cannot use aliases_everything_p to test MEM, since we must look 2167 at MEM_MODE, rather than GET_MODE (MEM). */ 2168 if (mem_mode == QImode || GET_CODE (mem_addr) == AND) 2169 return 1; 2170 2171 /* In true_dependence we also allow BLKmode to alias anything. Why 2172 don't we do this in anti_dependence and output_dependence? */ 2173 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode) 2174 return 1; 2175 2176 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, 2177 varies); 2178} 2179 2180/* Returns non-zero if a write to X might alias a previous read from 2181 (or, if WRITEP is non-zero, a write to) MEM. */ 2182 2183static int 2184write_dependence_p (mem, x, writep) 2185 rtx mem; 2186 rtx x; 2187 int writep; 2188{ 2189 rtx x_addr, mem_addr; 2190 rtx fixed_scalar; 2191 rtx base; 2192 2193 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 2194 return 1; 2195 2196 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 2197 This is used in epilogue deallocation functions. */ 2198 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 2199 return 1; 2200 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 2201 return 1; 2202 2203 if (DIFFERENT_ALIAS_SETS_P (x, mem)) 2204 return 0; 2205 2206 /* Unchanging memory can't conflict with non-unchanging memory. */ 2207 if (RTX_UNCHANGING_P (x) != RTX_UNCHANGING_P (mem)) 2208 return 0; 2209 2210 /* If MEM is an unchanging read, then it can't possibly conflict with 2211 the store to X, because there is at most one store to MEM, and it must 2212 have occurred somewhere before MEM. */ 2213 if (! writep && RTX_UNCHANGING_P (mem)) 2214 return 0; 2215 2216 if (nonoverlapping_memrefs_p (x, mem)) 2217 return 0; 2218 2219 x_addr = get_addr (XEXP (x, 0)); 2220 mem_addr = get_addr (XEXP (mem, 0)); 2221 2222 if (! writep) 2223 { 2224 base = find_base_term (mem_addr); 2225 if (base && (GET_CODE (base) == LABEL_REF 2226 || (GET_CODE (base) == SYMBOL_REF 2227 && CONSTANT_POOL_ADDRESS_P (base)))) 2228 return 0; 2229 } 2230 2231 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), 2232 GET_MODE (mem))) 2233 return 0; 2234 2235 x_addr = canon_rtx (x_addr); 2236 mem_addr = canon_rtx (mem_addr); 2237 2238 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr, 2239 SIZE_FOR_MODE (x), x_addr, 0)) 2240 return 0; 2241 2242 fixed_scalar 2243 = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, 2244 rtx_addr_varies_p); 2245 2246 return (!(fixed_scalar == mem && !aliases_everything_p (x)) 2247 && !(fixed_scalar == x && !aliases_everything_p (mem))); 2248} 2249 2250/* Anti dependence: X is written after read in MEM takes place. */ 2251 2252int 2253anti_dependence (mem, x) 2254 rtx mem; 2255 rtx x; 2256{ 2257 return write_dependence_p (mem, x, /*writep=*/0); 2258} 2259 2260/* Output dependence: X is written after store in MEM takes place. */ 2261 2262int 2263output_dependence (mem, x) 2264 rtx mem; 2265 rtx x; 2266{ 2267 return write_dependence_p (mem, x, /*writep=*/1); 2268} 2269 2270/* Returns non-zero if X mentions something which is not 2271 local to the function and is not constant. */ 2272 2273static int 2274nonlocal_mentioned_p (x) 2275 rtx x; 2276{ 2277 rtx base; 2278 RTX_CODE code; 2279 int regno; 2280 2281 code = GET_CODE (x); 2282 2283 if (GET_RTX_CLASS (code) == 'i') 2284 { 2285 /* Constant functions can be constant if they don't use 2286 scratch memory used to mark function w/o side effects. */ 2287 if (code == CALL_INSN && CONST_OR_PURE_CALL_P (x)) 2288 { 2289 x = CALL_INSN_FUNCTION_USAGE (x); 2290 if (x == 0) 2291 return 0; 2292 } 2293 else 2294 x = PATTERN (x); 2295 code = GET_CODE (x); 2296 } 2297 2298 switch (code) 2299 { 2300 case SUBREG: 2301 if (GET_CODE (SUBREG_REG (x)) == REG) 2302 { 2303 /* Global registers are not local. */ 2304 if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER 2305 && global_regs[subreg_regno (x)]) 2306 return 1; 2307 return 0; 2308 } 2309 break; 2310 2311 case REG: 2312 regno = REGNO (x); 2313 /* Global registers are not local. */ 2314 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]) 2315 return 1; 2316 return 0; 2317 2318 case SCRATCH: 2319 case PC: 2320 case CC0: 2321 case CONST_INT: 2322 case CONST_DOUBLE: 2323 case CONST_VECTOR: 2324 case CONST: 2325 case LABEL_REF: 2326 return 0; 2327 2328 case SYMBOL_REF: 2329 /* Constants in the function's constants pool are constant. */ 2330 if (CONSTANT_POOL_ADDRESS_P (x)) 2331 return 0; 2332 return 1; 2333 2334 case CALL: 2335 /* Non-constant calls and recursion are not local. */ 2336 return 1; 2337 2338 case MEM: 2339 /* Be overly conservative and consider any volatile memory 2340 reference as not local. */ 2341 if (MEM_VOLATILE_P (x)) 2342 return 1; 2343 base = find_base_term (XEXP (x, 0)); 2344 if (base) 2345 { 2346 /* A Pmode ADDRESS could be a reference via the structure value 2347 address or static chain. Such memory references are nonlocal. 2348 2349 Thus, we have to examine the contents of the ADDRESS to find 2350 out if this is a local reference or not. */ 2351 if (GET_CODE (base) == ADDRESS 2352 && GET_MODE (base) == Pmode 2353 && (XEXP (base, 0) == stack_pointer_rtx 2354 || XEXP (base, 0) == arg_pointer_rtx 2355#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 2356 || XEXP (base, 0) == hard_frame_pointer_rtx 2357#endif 2358 || XEXP (base, 0) == frame_pointer_rtx)) 2359 return 0; 2360 /* Constants in the function's constant pool are constant. */ 2361 if (GET_CODE (base) == SYMBOL_REF && CONSTANT_POOL_ADDRESS_P (base)) 2362 return 0; 2363 } 2364 return 1; 2365 2366 case UNSPEC_VOLATILE: 2367 case ASM_INPUT: 2368 return 1; 2369 2370 case ASM_OPERANDS: 2371 if (MEM_VOLATILE_P (x)) 2372 return 1; 2373 2374 /* FALLTHROUGH */ 2375 2376 default: 2377 break; 2378 } 2379 2380 /* Recursively scan the operands of this expression. */ 2381 2382 { 2383 const char *fmt = GET_RTX_FORMAT (code); 2384 int i; 2385 2386 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2387 { 2388 if (fmt[i] == 'e' && XEXP (x, i)) 2389 { 2390 if (nonlocal_mentioned_p (XEXP (x, i))) 2391 return 1; 2392 } 2393 else if (fmt[i] == 'E') 2394 { 2395 int j; 2396 for (j = 0; j < XVECLEN (x, i); j++) 2397 if (nonlocal_mentioned_p (XVECEXP (x, i, j))) 2398 return 1; 2399 } 2400 } 2401 } 2402 2403 return 0; 2404} 2405 2406/* Mark the function if it is constant. */ 2407 2408void 2409mark_constant_function () 2410{ 2411 rtx insn; 2412 int nonlocal_mentioned; 2413 2414 if (TREE_PUBLIC (current_function_decl) 2415 || TREE_READONLY (current_function_decl) 2416 || DECL_IS_PURE (current_function_decl) 2417 || TREE_THIS_VOLATILE (current_function_decl) 2418 || TYPE_MODE (TREE_TYPE (current_function_decl)) == VOIDmode) 2419 return; 2420 2421 /* A loop might not return which counts as a side effect. */ 2422 if (mark_dfs_back_edges ()) 2423 return; 2424 2425 nonlocal_mentioned = 0; 2426 2427 init_alias_analysis (); 2428 2429 /* Determine if this is a constant function. */ 2430 2431 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 2432 if (INSN_P (insn) && nonlocal_mentioned_p (insn)) 2433 { 2434 nonlocal_mentioned = 1; 2435 break; 2436 } 2437 2438 end_alias_analysis (); 2439 2440 /* Mark the function. */ 2441 2442 if (! nonlocal_mentioned) 2443 TREE_READONLY (current_function_decl) = 1; 2444} 2445 2446 2447static HARD_REG_SET argument_registers; 2448 2449void 2450init_alias_once () 2451{ 2452 int i; 2453 2454#ifndef OUTGOING_REGNO 2455#define OUTGOING_REGNO(N) N 2456#endif 2457 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 2458 /* Check whether this register can hold an incoming pointer 2459 argument. FUNCTION_ARG_REGNO_P tests outgoing register 2460 numbers, so translate if necessary due to register windows. */ 2461 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i)) 2462 && HARD_REGNO_MODE_OK (i, Pmode)) 2463 SET_HARD_REG_BIT (argument_registers, i); 2464 2465 alias_sets = splay_tree_new (splay_tree_compare_ints, 0, 0); 2466} 2467 2468/* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE 2469 array. */ 2470 2471void 2472init_alias_analysis () 2473{ 2474 int maxreg = max_reg_num (); 2475 int changed, pass; 2476 int i; 2477 unsigned int ui; 2478 rtx insn; 2479 2480 reg_known_value_size = maxreg; 2481 2482 reg_known_value 2483 = (rtx *) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (rtx)) 2484 - FIRST_PSEUDO_REGISTER; 2485 reg_known_equiv_p 2486 = (char*) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (char)) 2487 - FIRST_PSEUDO_REGISTER; 2488 2489 /* Overallocate reg_base_value to allow some growth during loop 2490 optimization. Loop unrolling can create a large number of 2491 registers. */ 2492 reg_base_value_size = maxreg * 2; 2493 reg_base_value = (rtx *) xcalloc (reg_base_value_size, sizeof (rtx)); 2494 ggc_add_rtx_root (reg_base_value, reg_base_value_size); 2495 2496 new_reg_base_value = (rtx *) xmalloc (reg_base_value_size * sizeof (rtx)); 2497 reg_seen = (char *) xmalloc (reg_base_value_size); 2498 if (! reload_completed && flag_unroll_loops) 2499 { 2500 /* ??? Why are we realloc'ing if we're just going to zero it? */ 2501 alias_invariant = (rtx *)xrealloc (alias_invariant, 2502 reg_base_value_size * sizeof (rtx)); 2503 memset ((char *)alias_invariant, 0, reg_base_value_size * sizeof (rtx)); 2504 } 2505 2506 /* The basic idea is that each pass through this loop will use the 2507 "constant" information from the previous pass to propagate alias 2508 information through another level of assignments. 2509 2510 This could get expensive if the assignment chains are long. Maybe 2511 we should throttle the number of iterations, possibly based on 2512 the optimization level or flag_expensive_optimizations. 2513 2514 We could propagate more information in the first pass by making use 2515 of REG_N_SETS to determine immediately that the alias information 2516 for a pseudo is "constant". 2517 2518 A program with an uninitialized variable can cause an infinite loop 2519 here. Instead of doing a full dataflow analysis to detect such problems 2520 we just cap the number of iterations for the loop. 2521 2522 The state of the arrays for the set chain in question does not matter 2523 since the program has undefined behavior. */ 2524 2525 pass = 0; 2526 do 2527 { 2528 /* Assume nothing will change this iteration of the loop. */ 2529 changed = 0; 2530 2531 /* We want to assign the same IDs each iteration of this loop, so 2532 start counting from zero each iteration of the loop. */ 2533 unique_id = 0; 2534 2535 /* We're at the start of the function each iteration through the 2536 loop, so we're copying arguments. */ 2537 copying_arguments = 1; 2538 2539 /* Wipe the potential alias information clean for this pass. */ 2540 memset ((char *) new_reg_base_value, 0, reg_base_value_size * sizeof (rtx)); 2541 2542 /* Wipe the reg_seen array clean. */ 2543 memset ((char *) reg_seen, 0, reg_base_value_size); 2544 2545 /* Mark all hard registers which may contain an address. 2546 The stack, frame and argument pointers may contain an address. 2547 An argument register which can hold a Pmode value may contain 2548 an address even if it is not in BASE_REGS. 2549 2550 The address expression is VOIDmode for an argument and 2551 Pmode for other registers. */ 2552 2553 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 2554 if (TEST_HARD_REG_BIT (argument_registers, i)) 2555 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode, 2556 gen_rtx_REG (Pmode, i)); 2557 2558 new_reg_base_value[STACK_POINTER_REGNUM] 2559 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx); 2560 new_reg_base_value[ARG_POINTER_REGNUM] 2561 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx); 2562 new_reg_base_value[FRAME_POINTER_REGNUM] 2563 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx); 2564#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 2565 new_reg_base_value[HARD_FRAME_POINTER_REGNUM] 2566 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx); 2567#endif 2568 2569 /* Walk the insns adding values to the new_reg_base_value array. */ 2570 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 2571 { 2572 if (INSN_P (insn)) 2573 { 2574 rtx note, set; 2575 2576#if defined (HAVE_prologue) || defined (HAVE_epilogue) 2577 /* The prologue/epilogue insns are not threaded onto the 2578 insn chain until after reload has completed. Thus, 2579 there is no sense wasting time checking if INSN is in 2580 the prologue/epilogue until after reload has completed. */ 2581 if (reload_completed 2582 && prologue_epilogue_contains (insn)) 2583 continue; 2584#endif 2585 2586 /* If this insn has a noalias note, process it, Otherwise, 2587 scan for sets. A simple set will have no side effects 2588 which could change the base value of any other register. */ 2589 2590 if (GET_CODE (PATTERN (insn)) == SET 2591 && REG_NOTES (insn) != 0 2592 && find_reg_note (insn, REG_NOALIAS, NULL_RTX)) 2593 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL); 2594 else 2595 note_stores (PATTERN (insn), record_set, NULL); 2596 2597 set = single_set (insn); 2598 2599 if (set != 0 2600 && GET_CODE (SET_DEST (set)) == REG 2601 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER) 2602 { 2603 unsigned int regno = REGNO (SET_DEST (set)); 2604 rtx src = SET_SRC (set); 2605 2606 if (REG_NOTES (insn) != 0 2607 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0 2608 && REG_N_SETS (regno) == 1) 2609 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0) 2610 && GET_CODE (XEXP (note, 0)) != EXPR_LIST 2611 && ! rtx_varies_p (XEXP (note, 0), 1) 2612 && ! reg_overlap_mentioned_p (SET_DEST (set), XEXP (note, 0))) 2613 { 2614 reg_known_value[regno] = XEXP (note, 0); 2615 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV; 2616 } 2617 else if (REG_N_SETS (regno) == 1 2618 && GET_CODE (src) == PLUS 2619 && GET_CODE (XEXP (src, 0)) == REG 2620 && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER 2621 && (reg_known_value[REGNO (XEXP (src, 0))]) 2622 && GET_CODE (XEXP (src, 1)) == CONST_INT) 2623 { 2624 rtx op0 = XEXP (src, 0); 2625 op0 = reg_known_value[REGNO (op0)]; 2626 reg_known_value[regno] 2627 = plus_constant (op0, INTVAL (XEXP (src, 1))); 2628 reg_known_equiv_p[regno] = 0; 2629 } 2630 else if (REG_N_SETS (regno) == 1 2631 && ! rtx_varies_p (src, 1)) 2632 { 2633 reg_known_value[regno] = src; 2634 reg_known_equiv_p[regno] = 0; 2635 } 2636 } 2637 } 2638 else if (GET_CODE (insn) == NOTE 2639 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG) 2640 copying_arguments = 0; 2641 } 2642 2643 /* Now propagate values from new_reg_base_value to reg_base_value. */ 2644 for (ui = 0; ui < reg_base_value_size; ui++) 2645 { 2646 if (new_reg_base_value[ui] 2647 && new_reg_base_value[ui] != reg_base_value[ui] 2648 && ! rtx_equal_p (new_reg_base_value[ui], reg_base_value[ui])) 2649 { 2650 reg_base_value[ui] = new_reg_base_value[ui]; 2651 changed = 1; 2652 } 2653 } 2654 } 2655 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES); 2656 2657 /* Fill in the remaining entries. */ 2658 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++) 2659 if (reg_known_value[i] == 0) 2660 reg_known_value[i] = regno_reg_rtx[i]; 2661 2662 /* Simplify the reg_base_value array so that no register refers to 2663 another register, except to special registers indirectly through 2664 ADDRESS expressions. 2665 2666 In theory this loop can take as long as O(registers^2), but unless 2667 there are very long dependency chains it will run in close to linear 2668 time. 2669 2670 This loop may not be needed any longer now that the main loop does 2671 a better job at propagating alias information. */ 2672 pass = 0; 2673 do 2674 { 2675 changed = 0; 2676 pass++; 2677 for (ui = 0; ui < reg_base_value_size; ui++) 2678 { 2679 rtx base = reg_base_value[ui]; 2680 if (base && GET_CODE (base) == REG) 2681 { 2682 unsigned int base_regno = REGNO (base); 2683 if (base_regno == ui) /* register set from itself */ 2684 reg_base_value[ui] = 0; 2685 else 2686 reg_base_value[ui] = reg_base_value[base_regno]; 2687 changed = 1; 2688 } 2689 } 2690 } 2691 while (changed && pass < MAX_ALIAS_LOOP_PASSES); 2692 2693 /* Clean up. */ 2694 free (new_reg_base_value); 2695 new_reg_base_value = 0; 2696 free (reg_seen); 2697 reg_seen = 0; 2698} 2699 2700void 2701end_alias_analysis () 2702{ 2703 free (reg_known_value + FIRST_PSEUDO_REGISTER); 2704 reg_known_value = 0; 2705 reg_known_value_size = 0; 2706 free (reg_known_equiv_p + FIRST_PSEUDO_REGISTER); 2707 reg_known_equiv_p = 0; 2708 if (reg_base_value) 2709 { 2710 ggc_del_root (reg_base_value); 2711 free (reg_base_value); 2712 reg_base_value = 0; 2713 } 2714 reg_base_value_size = 0; 2715 if (alias_invariant) 2716 { 2717 free (alias_invariant); 2718 alias_invariant = 0; 2719 } 2720} 2721