alias.c revision 107590
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 moffsety = MEM_OFFSET (y); 1939 if (TREE_CODE (expry) == COMPONENT_REF) 1940 { 1941 tree t = decl_for_component_ref (expry); 1942 if (! t) 1943 return 0; 1944 moffsety = adjust_offset_for_component_ref (expry, moffsety); 1945 expry = t; 1946 } 1947 1948 if (! DECL_P (exprx) || ! DECL_P (expry)) 1949 return 0; 1950 1951 rtlx = DECL_RTL (exprx); 1952 rtly = DECL_RTL (expry); 1953 1954 /* If either RTL is not a MEM, it must be a REG or CONCAT, meaning they 1955 can't overlap unless they are the same because we never reuse that part 1956 of the stack frame used for locals for spilled pseudos. */ 1957 if ((GET_CODE (rtlx) != MEM || GET_CODE (rtly) != MEM) 1958 && ! rtx_equal_p (rtlx, rtly)) 1959 return 1; 1960 1961 /* Get the base and offsets of both decls. If either is a register, we 1962 know both are and are the same, so use that as the base. The only 1963 we can avoid overlap is if we can deduce that they are nonoverlapping 1964 pieces of that decl, which is very rare. */ 1965 basex = GET_CODE (rtlx) == MEM ? XEXP (rtlx, 0) : rtlx; 1966 if (GET_CODE (basex) == PLUS && GET_CODE (XEXP (basex, 1)) == CONST_INT) 1967 offsetx = INTVAL (XEXP (basex, 1)), basex = XEXP (basex, 0); 1968 1969 basey = GET_CODE (rtly) == MEM ? XEXP (rtly, 0) : rtly; 1970 if (GET_CODE (basey) == PLUS && GET_CODE (XEXP (basey, 1)) == CONST_INT) 1971 offsety = INTVAL (XEXP (basey, 1)), basey = XEXP (basey, 0); 1972 1973 /* If the bases are different, we know they do not overlap if both 1974 are constants or if one is a constant and the other a pointer into the 1975 stack frame. Otherwise a different base means we can't tell if they 1976 overlap or not. */ 1977 if (! rtx_equal_p (basex, basey)) 1978 return ((CONSTANT_P (basex) && CONSTANT_P (basey)) 1979 || (CONSTANT_P (basex) && REG_P (basey) 1980 && REGNO_PTR_FRAME_P (REGNO (basey))) 1981 || (CONSTANT_P (basey) && REG_P (basex) 1982 && REGNO_PTR_FRAME_P (REGNO (basex)))); 1983 1984 sizex = (GET_CODE (rtlx) != MEM ? (int) GET_MODE_SIZE (GET_MODE (rtlx)) 1985 : MEM_SIZE (rtlx) ? INTVAL (MEM_SIZE (rtlx)) 1986 : -1); 1987 sizey = (GET_CODE (rtly) != MEM ? (int) GET_MODE_SIZE (GET_MODE (rtly)) 1988 : MEM_SIZE (rtly) ? INTVAL (MEM_SIZE (rtly)) : 1989 -1); 1990 1991 /* If we have an offset for either memref, it can update the values computed 1992 above. */ 1993 if (moffsetx) 1994 offsetx += INTVAL (moffsetx), sizex -= INTVAL (moffsetx); 1995 if (moffsety) 1996 offsety += INTVAL (moffsety), sizey -= INTVAL (moffsety); 1997 1998 /* If a memref has both a size and an offset, we can use the smaller size. 1999 We can't do this if the offset isn't known because we must view this 2000 memref as being anywhere inside the DECL's MEM. */ 2001 if (MEM_SIZE (x) && moffsetx) 2002 sizex = INTVAL (MEM_SIZE (x)); 2003 if (MEM_SIZE (y) && moffsety) 2004 sizey = INTVAL (MEM_SIZE (y)); 2005 2006 /* Put the values of the memref with the lower offset in X's values. */ 2007 if (offsetx > offsety) 2008 { 2009 tem = offsetx, offsetx = offsety, offsety = tem; 2010 tem = sizex, sizex = sizey, sizey = tem; 2011 } 2012 2013 /* If we don't know the size of the lower-offset value, we can't tell 2014 if they conflict. Otherwise, we do the test. */ 2015 return sizex >= 0 && offsety > offsetx + sizex; 2016} 2017 2018/* True dependence: X is read after store in MEM takes place. */ 2019 2020int 2021true_dependence (mem, mem_mode, x, varies) 2022 rtx mem; 2023 enum machine_mode mem_mode; 2024 rtx x; 2025 int (*varies) PARAMS ((rtx, int)); 2026{ 2027 rtx x_addr, mem_addr; 2028 rtx base; 2029 2030 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 2031 return 1; 2032 2033 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 2034 This is used in epilogue deallocation functions. */ 2035 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 2036 return 1; 2037 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 2038 return 1; 2039 2040 if (DIFFERENT_ALIAS_SETS_P (x, mem)) 2041 return 0; 2042 2043 /* Unchanging memory can't conflict with non-unchanging memory. 2044 A non-unchanging read can conflict with a non-unchanging write. 2045 An unchanging read can conflict with an unchanging write since 2046 there may be a single store to this address to initialize it. 2047 Note that an unchanging store can conflict with a non-unchanging read 2048 since we have to make conservative assumptions when we have a 2049 record with readonly fields and we are copying the whole thing. 2050 Just fall through to the code below to resolve potential conflicts. 2051 This won't handle all cases optimally, but the possible performance 2052 loss should be negligible. */ 2053 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem)) 2054 return 0; 2055 2056 if (nonoverlapping_memrefs_p (mem, x)) 2057 return 0; 2058 2059 if (mem_mode == VOIDmode) 2060 mem_mode = GET_MODE (mem); 2061 2062 x_addr = get_addr (XEXP (x, 0)); 2063 mem_addr = get_addr (XEXP (mem, 0)); 2064 2065 base = find_base_term (x_addr); 2066 if (base && (GET_CODE (base) == LABEL_REF 2067 || (GET_CODE (base) == SYMBOL_REF 2068 && CONSTANT_POOL_ADDRESS_P (base)))) 2069 return 0; 2070 2071 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode)) 2072 return 0; 2073 2074 x_addr = canon_rtx (x_addr); 2075 mem_addr = canon_rtx (mem_addr); 2076 2077 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr, 2078 SIZE_FOR_MODE (x), x_addr, 0)) 2079 return 0; 2080 2081 if (aliases_everything_p (x)) 2082 return 1; 2083 2084 /* We cannot use aliases_everything_p to test MEM, since we must look 2085 at MEM_MODE, rather than GET_MODE (MEM). */ 2086 if (mem_mode == QImode || GET_CODE (mem_addr) == AND) 2087 return 1; 2088 2089 /* In true_dependence we also allow BLKmode to alias anything. Why 2090 don't we do this in anti_dependence and output_dependence? */ 2091 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode) 2092 return 1; 2093 2094 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, 2095 varies); 2096} 2097 2098/* Canonical true dependence: X is read after store in MEM takes place. 2099 Variant of true_dependence which assumes MEM has already been 2100 canonicalized (hence we no longer do that here). 2101 The mem_addr argument has been added, since true_dependence computed 2102 this value prior to canonicalizing. */ 2103 2104int 2105canon_true_dependence (mem, mem_mode, mem_addr, x, varies) 2106 rtx mem, mem_addr, x; 2107 enum machine_mode mem_mode; 2108 int (*varies) PARAMS ((rtx, int)); 2109{ 2110 rtx x_addr; 2111 2112 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 2113 return 1; 2114 2115 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 2116 This is used in epilogue deallocation functions. */ 2117 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 2118 return 1; 2119 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 2120 return 1; 2121 2122 if (DIFFERENT_ALIAS_SETS_P (x, mem)) 2123 return 0; 2124 2125 /* If X is an unchanging read, then it can't possibly conflict with any 2126 non-unchanging store. It may conflict with an unchanging write though, 2127 because there may be a single store to this address to initialize it. 2128 Just fall through to the code below to resolve the case where we have 2129 both an unchanging read and an unchanging write. This won't handle all 2130 cases optimally, but the possible performance loss should be 2131 negligible. */ 2132 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem)) 2133 return 0; 2134 2135 if (nonoverlapping_memrefs_p (x, mem)) 2136 return 0; 2137 2138 x_addr = get_addr (XEXP (x, 0)); 2139 2140 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode)) 2141 return 0; 2142 2143 x_addr = canon_rtx (x_addr); 2144 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr, 2145 SIZE_FOR_MODE (x), x_addr, 0)) 2146 return 0; 2147 2148 if (aliases_everything_p (x)) 2149 return 1; 2150 2151 /* We cannot use aliases_everything_p to test MEM, since we must look 2152 at MEM_MODE, rather than GET_MODE (MEM). */ 2153 if (mem_mode == QImode || GET_CODE (mem_addr) == AND) 2154 return 1; 2155 2156 /* In true_dependence we also allow BLKmode to alias anything. Why 2157 don't we do this in anti_dependence and output_dependence? */ 2158 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode) 2159 return 1; 2160 2161 return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, 2162 varies); 2163} 2164 2165/* Returns non-zero if a write to X might alias a previous read from 2166 (or, if WRITEP is non-zero, a write to) MEM. */ 2167 2168static int 2169write_dependence_p (mem, x, writep) 2170 rtx mem; 2171 rtx x; 2172 int writep; 2173{ 2174 rtx x_addr, mem_addr; 2175 rtx fixed_scalar; 2176 rtx base; 2177 2178 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 2179 return 1; 2180 2181 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything. 2182 This is used in epilogue deallocation functions. */ 2183 if (GET_MODE (x) == BLKmode && GET_CODE (XEXP (x, 0)) == SCRATCH) 2184 return 1; 2185 if (GET_MODE (mem) == BLKmode && GET_CODE (XEXP (mem, 0)) == SCRATCH) 2186 return 1; 2187 2188 if (DIFFERENT_ALIAS_SETS_P (x, mem)) 2189 return 0; 2190 2191 /* Unchanging memory can't conflict with non-unchanging memory. */ 2192 if (RTX_UNCHANGING_P (x) != RTX_UNCHANGING_P (mem)) 2193 return 0; 2194 2195 /* If MEM is an unchanging read, then it can't possibly conflict with 2196 the store to X, because there is at most one store to MEM, and it must 2197 have occurred somewhere before MEM. */ 2198 if (! writep && RTX_UNCHANGING_P (mem)) 2199 return 0; 2200 2201 if (nonoverlapping_memrefs_p (x, mem)) 2202 return 0; 2203 2204 x_addr = get_addr (XEXP (x, 0)); 2205 mem_addr = get_addr (XEXP (mem, 0)); 2206 2207 if (! writep) 2208 { 2209 base = find_base_term (mem_addr); 2210 if (base && (GET_CODE (base) == LABEL_REF 2211 || (GET_CODE (base) == SYMBOL_REF 2212 && CONSTANT_POOL_ADDRESS_P (base)))) 2213 return 0; 2214 } 2215 2216 if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), 2217 GET_MODE (mem))) 2218 return 0; 2219 2220 x_addr = canon_rtx (x_addr); 2221 mem_addr = canon_rtx (mem_addr); 2222 2223 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr, 2224 SIZE_FOR_MODE (x), x_addr, 0)) 2225 return 0; 2226 2227 fixed_scalar 2228 = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr, 2229 rtx_addr_varies_p); 2230 2231 return (!(fixed_scalar == mem && !aliases_everything_p (x)) 2232 && !(fixed_scalar == x && !aliases_everything_p (mem))); 2233} 2234 2235/* Anti dependence: X is written after read in MEM takes place. */ 2236 2237int 2238anti_dependence (mem, x) 2239 rtx mem; 2240 rtx x; 2241{ 2242 return write_dependence_p (mem, x, /*writep=*/0); 2243} 2244 2245/* Output dependence: X is written after store in MEM takes place. */ 2246 2247int 2248output_dependence (mem, x) 2249 rtx mem; 2250 rtx x; 2251{ 2252 return write_dependence_p (mem, x, /*writep=*/1); 2253} 2254 2255/* Returns non-zero if X mentions something which is not 2256 local to the function and is not constant. */ 2257 2258static int 2259nonlocal_mentioned_p (x) 2260 rtx x; 2261{ 2262 rtx base; 2263 RTX_CODE code; 2264 int regno; 2265 2266 code = GET_CODE (x); 2267 2268 if (GET_RTX_CLASS (code) == 'i') 2269 { 2270 /* Constant functions can be constant if they don't use 2271 scratch memory used to mark function w/o side effects. */ 2272 if (code == CALL_INSN && CONST_OR_PURE_CALL_P (x)) 2273 { 2274 x = CALL_INSN_FUNCTION_USAGE (x); 2275 if (x == 0) 2276 return 0; 2277 } 2278 else 2279 x = PATTERN (x); 2280 code = GET_CODE (x); 2281 } 2282 2283 switch (code) 2284 { 2285 case SUBREG: 2286 if (GET_CODE (SUBREG_REG (x)) == REG) 2287 { 2288 /* Global registers are not local. */ 2289 if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER 2290 && global_regs[subreg_regno (x)]) 2291 return 1; 2292 return 0; 2293 } 2294 break; 2295 2296 case REG: 2297 regno = REGNO (x); 2298 /* Global registers are not local. */ 2299 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]) 2300 return 1; 2301 return 0; 2302 2303 case SCRATCH: 2304 case PC: 2305 case CC0: 2306 case CONST_INT: 2307 case CONST_DOUBLE: 2308 case CONST_VECTOR: 2309 case CONST: 2310 case LABEL_REF: 2311 return 0; 2312 2313 case SYMBOL_REF: 2314 /* Constants in the function's constants pool are constant. */ 2315 if (CONSTANT_POOL_ADDRESS_P (x)) 2316 return 0; 2317 return 1; 2318 2319 case CALL: 2320 /* Non-constant calls and recursion are not local. */ 2321 return 1; 2322 2323 case MEM: 2324 /* Be overly conservative and consider any volatile memory 2325 reference as not local. */ 2326 if (MEM_VOLATILE_P (x)) 2327 return 1; 2328 base = find_base_term (XEXP (x, 0)); 2329 if (base) 2330 { 2331 /* A Pmode ADDRESS could be a reference via the structure value 2332 address or static chain. Such memory references are nonlocal. 2333 2334 Thus, we have to examine the contents of the ADDRESS to find 2335 out if this is a local reference or not. */ 2336 if (GET_CODE (base) == ADDRESS 2337 && GET_MODE (base) == Pmode 2338 && (XEXP (base, 0) == stack_pointer_rtx 2339 || XEXP (base, 0) == arg_pointer_rtx 2340#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 2341 || XEXP (base, 0) == hard_frame_pointer_rtx 2342#endif 2343 || XEXP (base, 0) == frame_pointer_rtx)) 2344 return 0; 2345 /* Constants in the function's constant pool are constant. */ 2346 if (GET_CODE (base) == SYMBOL_REF && CONSTANT_POOL_ADDRESS_P (base)) 2347 return 0; 2348 } 2349 return 1; 2350 2351 case UNSPEC_VOLATILE: 2352 case ASM_INPUT: 2353 return 1; 2354 2355 case ASM_OPERANDS: 2356 if (MEM_VOLATILE_P (x)) 2357 return 1; 2358 2359 /* FALLTHROUGH */ 2360 2361 default: 2362 break; 2363 } 2364 2365 /* Recursively scan the operands of this expression. */ 2366 2367 { 2368 const char *fmt = GET_RTX_FORMAT (code); 2369 int i; 2370 2371 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2372 { 2373 if (fmt[i] == 'e' && XEXP (x, i)) 2374 { 2375 if (nonlocal_mentioned_p (XEXP (x, i))) 2376 return 1; 2377 } 2378 else if (fmt[i] == 'E') 2379 { 2380 int j; 2381 for (j = 0; j < XVECLEN (x, i); j++) 2382 if (nonlocal_mentioned_p (XVECEXP (x, i, j))) 2383 return 1; 2384 } 2385 } 2386 } 2387 2388 return 0; 2389} 2390 2391/* Mark the function if it is constant. */ 2392 2393void 2394mark_constant_function () 2395{ 2396 rtx insn; 2397 int nonlocal_mentioned; 2398 2399 if (TREE_PUBLIC (current_function_decl) 2400 || TREE_READONLY (current_function_decl) 2401 || DECL_IS_PURE (current_function_decl) 2402 || TREE_THIS_VOLATILE (current_function_decl) 2403 || TYPE_MODE (TREE_TYPE (current_function_decl)) == VOIDmode) 2404 return; 2405 2406 /* A loop might not return which counts as a side effect. */ 2407 if (mark_dfs_back_edges ()) 2408 return; 2409 2410 nonlocal_mentioned = 0; 2411 2412 init_alias_analysis (); 2413 2414 /* Determine if this is a constant function. */ 2415 2416 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 2417 if (INSN_P (insn) && nonlocal_mentioned_p (insn)) 2418 { 2419 nonlocal_mentioned = 1; 2420 break; 2421 } 2422 2423 end_alias_analysis (); 2424 2425 /* Mark the function. */ 2426 2427 if (! nonlocal_mentioned) 2428 TREE_READONLY (current_function_decl) = 1; 2429} 2430 2431 2432static HARD_REG_SET argument_registers; 2433 2434void 2435init_alias_once () 2436{ 2437 int i; 2438 2439#ifndef OUTGOING_REGNO 2440#define OUTGOING_REGNO(N) N 2441#endif 2442 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 2443 /* Check whether this register can hold an incoming pointer 2444 argument. FUNCTION_ARG_REGNO_P tests outgoing register 2445 numbers, so translate if necessary due to register windows. */ 2446 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i)) 2447 && HARD_REGNO_MODE_OK (i, Pmode)) 2448 SET_HARD_REG_BIT (argument_registers, i); 2449 2450 alias_sets = splay_tree_new (splay_tree_compare_ints, 0, 0); 2451} 2452 2453/* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE 2454 array. */ 2455 2456void 2457init_alias_analysis () 2458{ 2459 int maxreg = max_reg_num (); 2460 int changed, pass; 2461 int i; 2462 unsigned int ui; 2463 rtx insn; 2464 2465 reg_known_value_size = maxreg; 2466 2467 reg_known_value 2468 = (rtx *) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (rtx)) 2469 - FIRST_PSEUDO_REGISTER; 2470 reg_known_equiv_p 2471 = (char*) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (char)) 2472 - FIRST_PSEUDO_REGISTER; 2473 2474 /* Overallocate reg_base_value to allow some growth during loop 2475 optimization. Loop unrolling can create a large number of 2476 registers. */ 2477 reg_base_value_size = maxreg * 2; 2478 reg_base_value = (rtx *) xcalloc (reg_base_value_size, sizeof (rtx)); 2479 ggc_add_rtx_root (reg_base_value, reg_base_value_size); 2480 2481 new_reg_base_value = (rtx *) xmalloc (reg_base_value_size * sizeof (rtx)); 2482 reg_seen = (char *) xmalloc (reg_base_value_size); 2483 if (! reload_completed && flag_unroll_loops) 2484 { 2485 /* ??? Why are we realloc'ing if we're just going to zero it? */ 2486 alias_invariant = (rtx *)xrealloc (alias_invariant, 2487 reg_base_value_size * sizeof (rtx)); 2488 memset ((char *)alias_invariant, 0, reg_base_value_size * sizeof (rtx)); 2489 } 2490 2491 /* The basic idea is that each pass through this loop will use the 2492 "constant" information from the previous pass to propagate alias 2493 information through another level of assignments. 2494 2495 This could get expensive if the assignment chains are long. Maybe 2496 we should throttle the number of iterations, possibly based on 2497 the optimization level or flag_expensive_optimizations. 2498 2499 We could propagate more information in the first pass by making use 2500 of REG_N_SETS to determine immediately that the alias information 2501 for a pseudo is "constant". 2502 2503 A program with an uninitialized variable can cause an infinite loop 2504 here. Instead of doing a full dataflow analysis to detect such problems 2505 we just cap the number of iterations for the loop. 2506 2507 The state of the arrays for the set chain in question does not matter 2508 since the program has undefined behavior. */ 2509 2510 pass = 0; 2511 do 2512 { 2513 /* Assume nothing will change this iteration of the loop. */ 2514 changed = 0; 2515 2516 /* We want to assign the same IDs each iteration of this loop, so 2517 start counting from zero each iteration of the loop. */ 2518 unique_id = 0; 2519 2520 /* We're at the start of the function each iteration through the 2521 loop, so we're copying arguments. */ 2522 copying_arguments = 1; 2523 2524 /* Wipe the potential alias information clean for this pass. */ 2525 memset ((char *) new_reg_base_value, 0, reg_base_value_size * sizeof (rtx)); 2526 2527 /* Wipe the reg_seen array clean. */ 2528 memset ((char *) reg_seen, 0, reg_base_value_size); 2529 2530 /* Mark all hard registers which may contain an address. 2531 The stack, frame and argument pointers may contain an address. 2532 An argument register which can hold a Pmode value may contain 2533 an address even if it is not in BASE_REGS. 2534 2535 The address expression is VOIDmode for an argument and 2536 Pmode for other registers. */ 2537 2538 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 2539 if (TEST_HARD_REG_BIT (argument_registers, i)) 2540 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode, 2541 gen_rtx_REG (Pmode, i)); 2542 2543 new_reg_base_value[STACK_POINTER_REGNUM] 2544 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx); 2545 new_reg_base_value[ARG_POINTER_REGNUM] 2546 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx); 2547 new_reg_base_value[FRAME_POINTER_REGNUM] 2548 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx); 2549#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 2550 new_reg_base_value[HARD_FRAME_POINTER_REGNUM] 2551 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx); 2552#endif 2553 2554 /* Walk the insns adding values to the new_reg_base_value array. */ 2555 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 2556 { 2557 if (INSN_P (insn)) 2558 { 2559 rtx note, set; 2560 2561#if defined (HAVE_prologue) || defined (HAVE_epilogue) 2562 /* The prologue/epilogue insns are not threaded onto the 2563 insn chain until after reload has completed. Thus, 2564 there is no sense wasting time checking if INSN is in 2565 the prologue/epilogue until after reload has completed. */ 2566 if (reload_completed 2567 && prologue_epilogue_contains (insn)) 2568 continue; 2569#endif 2570 2571 /* If this insn has a noalias note, process it, Otherwise, 2572 scan for sets. A simple set will have no side effects 2573 which could change the base value of any other register. */ 2574 2575 if (GET_CODE (PATTERN (insn)) == SET 2576 && REG_NOTES (insn) != 0 2577 && find_reg_note (insn, REG_NOALIAS, NULL_RTX)) 2578 record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL); 2579 else 2580 note_stores (PATTERN (insn), record_set, NULL); 2581 2582 set = single_set (insn); 2583 2584 if (set != 0 2585 && GET_CODE (SET_DEST (set)) == REG 2586 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER) 2587 { 2588 unsigned int regno = REGNO (SET_DEST (set)); 2589 rtx src = SET_SRC (set); 2590 2591 if (REG_NOTES (insn) != 0 2592 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0 2593 && REG_N_SETS (regno) == 1) 2594 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0) 2595 && GET_CODE (XEXP (note, 0)) != EXPR_LIST 2596 && ! rtx_varies_p (XEXP (note, 0), 1) 2597 && ! reg_overlap_mentioned_p (SET_DEST (set), XEXP (note, 0))) 2598 { 2599 reg_known_value[regno] = XEXP (note, 0); 2600 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV; 2601 } 2602 else if (REG_N_SETS (regno) == 1 2603 && GET_CODE (src) == PLUS 2604 && GET_CODE (XEXP (src, 0)) == REG 2605 && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER 2606 && (reg_known_value[REGNO (XEXP (src, 0))]) 2607 && GET_CODE (XEXP (src, 1)) == CONST_INT) 2608 { 2609 rtx op0 = XEXP (src, 0); 2610 op0 = reg_known_value[REGNO (op0)]; 2611 reg_known_value[regno] 2612 = plus_constant (op0, INTVAL (XEXP (src, 1))); 2613 reg_known_equiv_p[regno] = 0; 2614 } 2615 else if (REG_N_SETS (regno) == 1 2616 && ! rtx_varies_p (src, 1)) 2617 { 2618 reg_known_value[regno] = src; 2619 reg_known_equiv_p[regno] = 0; 2620 } 2621 } 2622 } 2623 else if (GET_CODE (insn) == NOTE 2624 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG) 2625 copying_arguments = 0; 2626 } 2627 2628 /* Now propagate values from new_reg_base_value to reg_base_value. */ 2629 for (ui = 0; ui < reg_base_value_size; ui++) 2630 { 2631 if (new_reg_base_value[ui] 2632 && new_reg_base_value[ui] != reg_base_value[ui] 2633 && ! rtx_equal_p (new_reg_base_value[ui], reg_base_value[ui])) 2634 { 2635 reg_base_value[ui] = new_reg_base_value[ui]; 2636 changed = 1; 2637 } 2638 } 2639 } 2640 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES); 2641 2642 /* Fill in the remaining entries. */ 2643 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++) 2644 if (reg_known_value[i] == 0) 2645 reg_known_value[i] = regno_reg_rtx[i]; 2646 2647 /* Simplify the reg_base_value array so that no register refers to 2648 another register, except to special registers indirectly through 2649 ADDRESS expressions. 2650 2651 In theory this loop can take as long as O(registers^2), but unless 2652 there are very long dependency chains it will run in close to linear 2653 time. 2654 2655 This loop may not be needed any longer now that the main loop does 2656 a better job at propagating alias information. */ 2657 pass = 0; 2658 do 2659 { 2660 changed = 0; 2661 pass++; 2662 for (ui = 0; ui < reg_base_value_size; ui++) 2663 { 2664 rtx base = reg_base_value[ui]; 2665 if (base && GET_CODE (base) == REG) 2666 { 2667 unsigned int base_regno = REGNO (base); 2668 if (base_regno == ui) /* register set from itself */ 2669 reg_base_value[ui] = 0; 2670 else 2671 reg_base_value[ui] = reg_base_value[base_regno]; 2672 changed = 1; 2673 } 2674 } 2675 } 2676 while (changed && pass < MAX_ALIAS_LOOP_PASSES); 2677 2678 /* Clean up. */ 2679 free (new_reg_base_value); 2680 new_reg_base_value = 0; 2681 free (reg_seen); 2682 reg_seen = 0; 2683} 2684 2685void 2686end_alias_analysis () 2687{ 2688 free (reg_known_value + FIRST_PSEUDO_REGISTER); 2689 reg_known_value = 0; 2690 reg_known_value_size = 0; 2691 free (reg_known_equiv_p + FIRST_PSEUDO_REGISTER); 2692 reg_known_equiv_p = 0; 2693 if (reg_base_value) 2694 { 2695 ggc_del_root (reg_base_value); 2696 free (reg_base_value); 2697 reg_base_value = 0; 2698 } 2699 reg_base_value_size = 0; 2700 if (alias_invariant) 2701 { 2702 free (alias_invariant); 2703 alias_invariant = 0; 2704 } 2705} 2706