1/* Alias analysis for GNU C 2 Copyright (C) 1997, 1998, 1999, 2000 Free Software Foundation, Inc. 3 Contributed by John Carr (jfc@mit.edu). 4 5This file is part of GNU CC. 6 7GNU CC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GNU CC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GNU CC; see the file COPYING. If not, write to 19the Free Software Foundation, 59 Temple Place - Suite 330, 20Boston, MA 02111-1307, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "rtl.h" 25#include "expr.h" 26#include "regs.h" 27#include "hard-reg-set.h" 28#include "flags.h" 29#include "output.h" 30#include "toplev.h" 31#include "splay-tree.h" 32 33/* The alias sets assigned to MEMs assist the back-end in determining 34 which MEMs can alias which other MEMs. In general, two MEMs in 35 different alias sets to not alias each other. There is one 36 exception, however. Consider something like: 37 38 struct S {int i; double d; }; 39 40 a store to an `S' can alias something of either type `int' or type 41 `double'. (However, a store to an `int' cannot alias a `double' 42 and vice versa.) We indicate this via a tree structure that looks 43 like: 44 struct S 45 / \ 46 / \ 47 |/_ _\| 48 int double 49 50 (The arrows are directed and point downwards.) If, when comparing 51 two alias sets, we can hold one set fixed, and trace the other set 52 downwards, and at some point find the first set, the two MEMs can 53 alias one another. In this situation we say the alias set for 54 `struct S' is the `superset' and that those for `int' and `double' 55 are `subsets'. 56 57 Alias set zero is implicitly a superset of all other alias sets. 58 However, this is no actual entry for alias set zero. It is an 59 error to attempt to explicitly construct a subset of zero. */ 60 61typedef struct alias_set_entry { 62 /* The alias set number, as stored in MEM_ALIAS_SET. */ 63 int alias_set; 64 65 /* The children of the alias set. These are not just the immediate 66 children, but, in fact, all children. So, if we have: 67 68 struct T { struct S s; float f; } 69 70 continuing our example above, the children here will be all of 71 `int', `double', `float', and `struct S'. */ 72 splay_tree children; 73}* alias_set_entry; 74 75static rtx canon_rtx PROTO((rtx)); 76static int rtx_equal_for_memref_p PROTO((rtx, rtx)); 77static rtx find_symbolic_term PROTO((rtx)); 78static int memrefs_conflict_p PROTO((int, rtx, int, rtx, 79 HOST_WIDE_INT)); 80static void record_set PROTO((rtx, rtx)); 81static rtx find_base_term PROTO((rtx)); 82static int base_alias_check PROTO((rtx, rtx, enum machine_mode, 83 enum machine_mode)); 84static rtx find_base_value PROTO((rtx)); 85static int mems_in_disjoint_alias_sets_p PROTO((rtx, rtx)); 86static int insert_subset_children PROTO((splay_tree_node, 87 void*)); 88static alias_set_entry get_alias_set_entry PROTO((int)); 89static rtx fixed_scalar_and_varying_struct_p PROTO((rtx, rtx, int (*)(rtx))); 90static int aliases_everything_p PROTO((rtx)); 91static int write_dependence_p PROTO((rtx, rtx, int)); 92 93/* Set up all info needed to perform alias analysis on memory references. */ 94 95#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X))) 96 97/* Returns nonzero if MEM1 and MEM2 do not alias because they are in 98 different alias sets. We ignore alias sets in functions making use 99 of variable arguments because the va_arg macros on some systems are 100 not legal ANSI C. */ 101#define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \ 102 mems_in_disjoint_alias_sets_p (MEM1, MEM2) 103 104/* Cap the number of passes we make over the insns propagating alias 105 information through set chains. 106 107 10 is a completely arbitrary choice. */ 108#define MAX_ALIAS_LOOP_PASSES 10 109 110/* reg_base_value[N] gives an address to which register N is related. 111 If all sets after the first add or subtract to the current value 112 or otherwise modify it so it does not point to a different top level 113 object, reg_base_value[N] is equal to the address part of the source 114 of the first set. 115 116 A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS 117 expressions represent certain special values: function arguments and 118 the stack, frame, and argument pointers. The contents of an address 119 expression are not used (but they are descriptive for debugging); 120 only the address and mode matter. Pointer equality, not rtx_equal_p, 121 determines whether two ADDRESS expressions refer to the same base 122 address. The mode determines whether it is a function argument or 123 other special value. */ 124 125rtx *reg_base_value; 126rtx *new_reg_base_value; 127unsigned int reg_base_value_size; /* size of reg_base_value array */ 128#define REG_BASE_VALUE(X) \ 129 ((unsigned) REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0) 130 131/* Vector of known invariant relationships between registers. Set in 132 loop unrolling. Indexed by register number, if nonzero the value 133 is an expression describing this register in terms of another. 134 135 The length of this array is REG_BASE_VALUE_SIZE. 136 137 Because this array contains only pseudo registers it has no effect 138 after reload. */ 139static rtx *alias_invariant; 140 141/* Vector indexed by N giving the initial (unchanging) value known 142 for pseudo-register N. */ 143rtx *reg_known_value; 144 145/* Indicates number of valid entries in reg_known_value. */ 146static int reg_known_value_size; 147 148/* Vector recording for each reg_known_value whether it is due to a 149 REG_EQUIV note. Future passes (viz., reload) may replace the 150 pseudo with the equivalent expression and so we account for the 151 dependences that would be introduced if that happens. */ 152/* ??? This is a problem only on the Convex. The REG_EQUIV notes created in 153 assign_parms mention the arg pointer, and there are explicit insns in the 154 RTL that modify the arg pointer. Thus we must ensure that such insns don't 155 get scheduled across each other because that would invalidate the REG_EQUIV 156 notes. One could argue that the REG_EQUIV notes are wrong, but solving 157 the problem in the scheduler will likely give better code, so we do it 158 here. */ 159char *reg_known_equiv_p; 160 161/* True when scanning insns from the start of the rtl to the 162 NOTE_INSN_FUNCTION_BEG note. */ 163 164static int copying_arguments; 165 166/* The splay-tree used to store the various alias set entries. */ 167 168static splay_tree alias_sets; 169 170/* Returns a pointer to the alias set entry for ALIAS_SET, if there is 171 such an entry, or NULL otherwise. */ 172 173static alias_set_entry 174get_alias_set_entry (alias_set) 175 int alias_set; 176{ 177 splay_tree_node sn = 178 splay_tree_lookup (alias_sets, (splay_tree_key) alias_set); 179 180 return sn ? ((alias_set_entry) sn->value) : ((alias_set_entry) 0); 181} 182 183/* Returns nonzero value if the alias sets for MEM1 and MEM2 are such 184 that the two MEMs cannot alias each other. */ 185 186static int 187mems_in_disjoint_alias_sets_p (mem1, mem2) 188 rtx mem1; 189 rtx mem2; 190{ 191 alias_set_entry ase; 192 193#ifdef ENABLE_CHECKING 194/* Perform a basic sanity check. Namely, that there are no alias sets 195 if we're not using strict aliasing. This helps to catch bugs 196 whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or 197 where a MEM is allocated in some way other than by the use of 198 gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to 199 use alias sets to indicate that spilled registers cannot alias each 200 other, we might need to remove this check. */ 201 if (!flag_strict_aliasing && 202 (MEM_ALIAS_SET (mem1) || MEM_ALIAS_SET (mem2))) 203 abort (); 204#endif 205 206 /* The code used in varargs macros are often not conforming ANSI C, 207 which can trick the compiler into making incorrect aliasing 208 assumptions in these functions. So, we don't use alias sets in 209 such a function. FIXME: This should be moved into the front-end; 210 it is a language-dependent notion, and there's no reason not to 211 still use these checks to handle globals. */ 212 if (current_function_stdarg || current_function_varargs) 213 return 0; 214 215 if (!MEM_ALIAS_SET (mem1) || !MEM_ALIAS_SET (mem2)) 216 /* We have no alias set information for one of the MEMs, so we 217 have to assume it can alias anything. */ 218 return 0; 219 220 if (MEM_ALIAS_SET (mem1) == MEM_ALIAS_SET (mem2)) 221 /* The two alias sets are the same, so they may alias. */ 222 return 0; 223 224 /* Iterate through each of the children of the first alias set, 225 comparing it with the second alias set. */ 226 ase = get_alias_set_entry (MEM_ALIAS_SET (mem1)); 227 if (ase && splay_tree_lookup (ase->children, 228 (splay_tree_key) MEM_ALIAS_SET (mem2))) 229 return 0; 230 231 /* Now do the same, but with the alias sets reversed. */ 232 ase = get_alias_set_entry (MEM_ALIAS_SET (mem2)); 233 if (ase && splay_tree_lookup (ase->children, 234 (splay_tree_key) MEM_ALIAS_SET (mem1))) 235 return 0; 236 237 /* The two MEMs are in distinct alias sets, and neither one is the 238 child of the other. Therefore, they cannot alias. */ 239 return 1; 240} 241 242/* Insert the NODE into the splay tree given by DATA. Used by 243 record_alias_subset via splay_tree_foreach. */ 244 245static int 246insert_subset_children (node, data) 247 splay_tree_node node; 248 void *data; 249{ 250 splay_tree_insert ((splay_tree) data, 251 node->key, 252 node->value); 253 254 return 0; 255} 256 257/* Indicate that things in SUBSET can alias things in SUPERSET, but 258 not vice versa. For example, in C, a store to an `int' can alias a 259 structure containing an `int', but not vice versa. Here, the 260 structure would be the SUPERSET and `int' the SUBSET. This 261 function should be called only once per SUPERSET/SUBSET pair. At 262 present any given alias set may only be a subset of one superset. 263 264 It is illegal for SUPERSET to be zero; everything is implicitly a 265 subset of alias set zero. */ 266 267void 268record_alias_subset (superset, subset) 269 int superset; 270 int subset; 271{ 272 alias_set_entry superset_entry; 273 alias_set_entry subset_entry; 274 275 if (superset == 0) 276 abort (); 277 278 superset_entry = get_alias_set_entry (superset); 279 if (!superset_entry) 280 { 281 /* Create an entry for the SUPERSET, so that we have a place to 282 attach the SUBSET. */ 283 superset_entry = 284 (alias_set_entry) xmalloc (sizeof (struct alias_set_entry)); 285 superset_entry->alias_set = superset; 286 superset_entry->children 287 = splay_tree_new (splay_tree_compare_ints, 0, 0); 288 splay_tree_insert (alias_sets, 289 (splay_tree_key) superset, 290 (splay_tree_value) superset_entry); 291 292 } 293 294 subset_entry = get_alias_set_entry (subset); 295 if (subset_entry) 296 /* There is an entry for the subset. Enter all of its children 297 (if they are not already present) as children of the SUPERSET. */ 298 splay_tree_foreach (subset_entry->children, 299 insert_subset_children, 300 superset_entry->children); 301 302 /* Enter the SUBSET itself as a child of the SUPERSET. */ 303 splay_tree_insert (superset_entry->children, 304 (splay_tree_key) subset, 305 /*value=*/0); 306} 307 308/* Inside SRC, the source of a SET, find a base address. */ 309 310static rtx 311find_base_value (src) 312 register rtx src; 313{ 314 switch (GET_CODE (src)) 315 { 316 case SYMBOL_REF: 317 case LABEL_REF: 318 return src; 319 320 case REG: 321 /* At the start of a function argument registers have known base 322 values which may be lost later. Returning an ADDRESS 323 expression here allows optimization based on argument values 324 even when the argument registers are used for other purposes. */ 325 if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments) 326 return new_reg_base_value[REGNO (src)]; 327 328 /* If a pseudo has a known base value, return it. Do not do this 329 for hard regs since it can result in a circular dependency 330 chain for registers which have values at function entry. 331 332 The test above is not sufficient because the scheduler may move 333 a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */ 334 if (REGNO (src) >= FIRST_PSEUDO_REGISTER 335 && (unsigned) REGNO (src) < reg_base_value_size 336 && reg_base_value[REGNO (src)]) 337 return reg_base_value[REGNO (src)]; 338 339 return src; 340 341 case MEM: 342 /* Check for an argument passed in memory. Only record in the 343 copying-arguments block; it is too hard to track changes 344 otherwise. */ 345 if (copying_arguments 346 && (XEXP (src, 0) == arg_pointer_rtx 347 || (GET_CODE (XEXP (src, 0)) == PLUS 348 && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx))) 349 return gen_rtx_ADDRESS (VOIDmode, src); 350 return 0; 351 352 case CONST: 353 src = XEXP (src, 0); 354 if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS) 355 break; 356 /* fall through */ 357 358 case PLUS: 359 case MINUS: 360 { 361 rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1); 362 363 /* If either operand is a REG, then see if we already have 364 a known value for it. */ 365 if (GET_CODE (src_0) == REG) 366 { 367 temp = find_base_value (src_0); 368 if (temp) 369 src_0 = temp; 370 } 371 372 if (GET_CODE (src_1) == REG) 373 { 374 temp = find_base_value (src_1); 375 if (temp) 376 src_1 = temp; 377 } 378 379 /* Guess which operand is the base address. 380 381 If either operand is a symbol, then it is the base. If 382 either operand is a CONST_INT, then the other is the base. */ 383 384 if (GET_CODE (src_1) == CONST_INT 385 || GET_CODE (src_0) == SYMBOL_REF 386 || GET_CODE (src_0) == LABEL_REF 387 || GET_CODE (src_0) == CONST) 388 return find_base_value (src_0); 389 390 if (GET_CODE (src_0) == CONST_INT 391 || GET_CODE (src_1) == SYMBOL_REF 392 || GET_CODE (src_1) == LABEL_REF 393 || GET_CODE (src_1) == CONST) 394 return find_base_value (src_1); 395 396 /* This might not be necessary anymore. 397 398 If either operand is a REG that is a known pointer, then it 399 is the base. */ 400 if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0))) 401 return find_base_value (src_0); 402 403 if (GET_CODE (src_1) == REG && REGNO_POINTER_FLAG (REGNO (src_1))) 404 return find_base_value (src_1); 405 406 return 0; 407 } 408 409 case LO_SUM: 410 /* The standard form is (lo_sum reg sym) so look only at the 411 second operand. */ 412 return find_base_value (XEXP (src, 1)); 413 414 case AND: 415 /* If the second operand is constant set the base 416 address to the first operand. */ 417 if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0) 418 return find_base_value (XEXP (src, 0)); 419 return 0; 420 421 case ZERO_EXTEND: 422 case SIGN_EXTEND: /* used for NT/Alpha pointers */ 423 case HIGH: 424 return find_base_value (XEXP (src, 0)); 425 426 default: 427 break; 428 } 429 430 return 0; 431} 432 433/* Called from init_alias_analysis indirectly through note_stores. */ 434 435/* while scanning insns to find base values, reg_seen[N] is nonzero if 436 register N has been set in this function. */ 437static char *reg_seen; 438 439/* Addresses which are known not to alias anything else are identified 440 by a unique integer. */ 441static int unique_id; 442 443static void 444record_set (dest, set) 445 rtx dest, set; 446{ 447 register int regno; 448 rtx src; 449 450 if (GET_CODE (dest) != REG) 451 return; 452 453 regno = REGNO (dest); 454 455 if (set) 456 { 457 /* A CLOBBER wipes out any old value but does not prevent a previously 458 unset register from acquiring a base address (i.e. reg_seen is not 459 set). */ 460 if (GET_CODE (set) == CLOBBER) 461 { 462 new_reg_base_value[regno] = 0; 463 return; 464 } 465 src = SET_SRC (set); 466 } 467 else 468 { 469 if (reg_seen[regno]) 470 { 471 new_reg_base_value[regno] = 0; 472 return; 473 } 474 reg_seen[regno] = 1; 475 new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode, 476 GEN_INT (unique_id++)); 477 return; 478 } 479 480 /* This is not the first set. If the new value is not related to the 481 old value, forget the base value. Note that the following code is 482 not detected: 483 extern int x, y; int *p = &x; p += (&y-&x); 484 ANSI C does not allow computing the difference of addresses 485 of distinct top level objects. */ 486 if (new_reg_base_value[regno]) 487 switch (GET_CODE (src)) 488 { 489 case LO_SUM: 490 case PLUS: 491 case MINUS: 492 if (XEXP (src, 0) != dest && XEXP (src, 1) != dest) 493 new_reg_base_value[regno] = 0; 494 break; 495 case AND: 496 if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT) 497 new_reg_base_value[regno] = 0; 498 break; 499 default: 500 new_reg_base_value[regno] = 0; 501 break; 502 } 503 /* If this is the first set of a register, record the value. */ 504 else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno]) 505 && ! reg_seen[regno] && new_reg_base_value[regno] == 0) 506 new_reg_base_value[regno] = find_base_value (src); 507 508 reg_seen[regno] = 1; 509} 510 511/* Called from loop optimization when a new pseudo-register is created. */ 512void 513record_base_value (regno, val, invariant) 514 int regno; 515 rtx val; 516 int invariant; 517{ 518 if ((unsigned) regno >= reg_base_value_size) 519 return; 520 521 /* If INVARIANT is true then this value also describes an invariant 522 relationship which can be used to deduce that two registers with 523 unknown values are different. */ 524 if (invariant && alias_invariant) 525 alias_invariant[regno] = val; 526 527 if (GET_CODE (val) == REG) 528 { 529 if ((unsigned) REGNO (val) < reg_base_value_size) 530 { 531 reg_base_value[regno] = reg_base_value[REGNO (val)]; 532 } 533 return; 534 } 535 reg_base_value[regno] = find_base_value (val); 536} 537 538static rtx 539canon_rtx (x) 540 rtx x; 541{ 542 /* Recursively look for equivalences. */ 543 if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER 544 && REGNO (x) < reg_known_value_size) 545 return reg_known_value[REGNO (x)] == x 546 ? x : canon_rtx (reg_known_value[REGNO (x)]); 547 else if (GET_CODE (x) == PLUS) 548 { 549 rtx x0 = canon_rtx (XEXP (x, 0)); 550 rtx x1 = canon_rtx (XEXP (x, 1)); 551 552 if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1)) 553 { 554 /* We can tolerate LO_SUMs being offset here; these 555 rtl are used for nothing other than comparisons. */ 556 if (GET_CODE (x0) == CONST_INT) 557 return plus_constant_for_output (x1, INTVAL (x0)); 558 else if (GET_CODE (x1) == CONST_INT) 559 return plus_constant_for_output (x0, INTVAL (x1)); 560 return gen_rtx_PLUS (GET_MODE (x), x0, x1); 561 } 562 } 563 /* This gives us much better alias analysis when called from 564 the loop optimizer. Note we want to leave the original 565 MEM alone, but need to return the canonicalized MEM with 566 all the flags with their original values. */ 567 else if (GET_CODE (x) == MEM) 568 { 569 rtx addr = canon_rtx (XEXP (x, 0)); 570 if (addr != XEXP (x, 0)) 571 { 572 rtx new = gen_rtx_MEM (GET_MODE (x), addr); 573 RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x); 574 MEM_COPY_ATTRIBUTES (new, x); 575 MEM_ALIAS_SET (new) = MEM_ALIAS_SET (x); 576 x = new; 577 } 578 } 579 return x; 580} 581 582/* Return 1 if X and Y are identical-looking rtx's. 583 584 We use the data in reg_known_value above to see if two registers with 585 different numbers are, in fact, equivalent. */ 586 587static int 588rtx_equal_for_memref_p (x, y) 589 rtx x, y; 590{ 591 register int i; 592 register int j; 593 register enum rtx_code code; 594 register char *fmt; 595 596 if (x == 0 && y == 0) 597 return 1; 598 if (x == 0 || y == 0) 599 return 0; 600 x = canon_rtx (x); 601 y = canon_rtx (y); 602 603 if (x == y) 604 return 1; 605 606 code = GET_CODE (x); 607 /* Rtx's of different codes cannot be equal. */ 608 if (code != GET_CODE (y)) 609 return 0; 610 611 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. 612 (REG:SI x) and (REG:HI x) are NOT equivalent. */ 613 614 if (GET_MODE (x) != GET_MODE (y)) 615 return 0; 616 617 /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */ 618 619 if (code == REG) 620 return REGNO (x) == REGNO (y); 621 if (code == LABEL_REF) 622 return XEXP (x, 0) == XEXP (y, 0); 623 if (code == SYMBOL_REF) 624 return XSTR (x, 0) == XSTR (y, 0); 625 if (code == CONST_INT) 626 return INTVAL (x) == INTVAL (y); 627 if (code == ADDRESSOF) 628 return REGNO (XEXP (x, 0)) == REGNO (XEXP (y, 0)) && XINT (x, 1) == XINT (y, 1); 629 630 /* For commutative operations, the RTX match if the operand match in any 631 order. Also handle the simple binary and unary cases without a loop. */ 632 if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c') 633 return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)) 634 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1))) 635 || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1)) 636 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0)))); 637 else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2') 638 return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)) 639 && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1))); 640 else if (GET_RTX_CLASS (code) == '1') 641 return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)); 642 643 /* Compare the elements. If any pair of corresponding elements 644 fail to match, return 0 for the whole things. 645 646 Limit cases to types which actually appear in addresses. */ 647 648 fmt = GET_RTX_FORMAT (code); 649 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 650 { 651 switch (fmt[i]) 652 { 653 case 'i': 654 if (XINT (x, i) != XINT (y, i)) 655 return 0; 656 break; 657 658 case 'E': 659 /* Two vectors must have the same length. */ 660 if (XVECLEN (x, i) != XVECLEN (y, i)) 661 return 0; 662 663 /* And the corresponding elements must match. */ 664 for (j = 0; j < XVECLEN (x, i); j++) 665 if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0) 666 return 0; 667 break; 668 669 case 'e': 670 if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0) 671 return 0; 672 break; 673 674 /* This can happen for an asm which clobbers memory. */ 675 case '0': 676 break; 677 678 /* It is believed that rtx's at this level will never 679 contain anything but integers and other rtx's, 680 except for within LABEL_REFs and SYMBOL_REFs. */ 681 default: 682 abort (); 683 } 684 } 685 return 1; 686} 687 688/* Given an rtx X, find a SYMBOL_REF or LABEL_REF within 689 X and return it, or return 0 if none found. */ 690 691static rtx 692find_symbolic_term (x) 693 rtx x; 694{ 695 register int i; 696 register enum rtx_code code; 697 register char *fmt; 698 699 code = GET_CODE (x); 700 if (code == SYMBOL_REF || code == LABEL_REF) 701 return x; 702 if (GET_RTX_CLASS (code) == 'o') 703 return 0; 704 705 fmt = GET_RTX_FORMAT (code); 706 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 707 { 708 rtx t; 709 710 if (fmt[i] == 'e') 711 { 712 t = find_symbolic_term (XEXP (x, i)); 713 if (t != 0) 714 return t; 715 } 716 else if (fmt[i] == 'E') 717 break; 718 } 719 return 0; 720} 721 722static rtx 723find_base_term (x) 724 register rtx x; 725{ 726 switch (GET_CODE (x)) 727 { 728 case REG: 729 return REG_BASE_VALUE (x); 730 731 case ZERO_EXTEND: 732 case SIGN_EXTEND: /* Used for Alpha/NT pointers */ 733 case HIGH: 734 case PRE_INC: 735 case PRE_DEC: 736 case POST_INC: 737 case POST_DEC: 738 return find_base_term (XEXP (x, 0)); 739 740 case CONST: 741 x = XEXP (x, 0); 742 if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS) 743 return 0; 744 /* fall through */ 745 case LO_SUM: 746 case PLUS: 747 case MINUS: 748 { 749 rtx tmp1 = XEXP (x, 0); 750 rtx tmp2 = XEXP (x, 1); 751 752 /* This is a litle bit tricky since we have to determine which of 753 the two operands represents the real base address. Otherwise this 754 routine may return the index register instead of the base register. 755 756 That may cause us to believe no aliasing was possible, when in 757 fact aliasing is possible. 758 759 We use a few simple tests to guess the base register. Additional 760 tests can certainly be added. For example, if one of the operands 761 is a shift or multiply, then it must be the index register and the 762 other operand is the base register. */ 763 764 /* If either operand is known to be a pointer, then use it 765 to determine the base term. */ 766 if (REG_P (tmp1) && REGNO_POINTER_FLAG (REGNO (tmp1))) 767 return find_base_term (tmp1); 768 769 if (REG_P (tmp2) && REGNO_POINTER_FLAG (REGNO (tmp2))) 770 return find_base_term (tmp2); 771 772 /* Neither operand was known to be a pointer. Go ahead and find the 773 base term for both operands. */ 774 tmp1 = find_base_term (tmp1); 775 tmp2 = find_base_term (tmp2); 776 777 /* If either base term is named object or a special address 778 (like an argument or stack reference), then use it for the 779 base term. */ 780 if (tmp1 781 && (GET_CODE (tmp1) == SYMBOL_REF 782 || GET_CODE (tmp1) == LABEL_REF 783 || (GET_CODE (tmp1) == ADDRESS 784 && GET_MODE (tmp1) != VOIDmode))) 785 return tmp1; 786 787 if (tmp2 788 && (GET_CODE (tmp2) == SYMBOL_REF 789 || GET_CODE (tmp2) == LABEL_REF 790 || (GET_CODE (tmp2) == ADDRESS 791 && GET_MODE (tmp2) != VOIDmode))) 792 return tmp2; 793 794 /* We could not determine which of the two operands was the 795 base register and which was the index. So we can determine 796 nothing from the base alias check. */ 797 return 0; 798 } 799 800 case AND: 801 if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT) 802 return REG_BASE_VALUE (XEXP (x, 0)); 803 return 0; 804 805 case SYMBOL_REF: 806 case LABEL_REF: 807 return x; 808 809 default: 810 return 0; 811 } 812} 813 814/* Return 0 if the addresses X and Y are known to point to different 815 objects, 1 if they might be pointers to the same object. */ 816 817static int 818base_alias_check (x, y, x_mode, y_mode) 819 rtx x, y; 820 enum machine_mode x_mode, y_mode; 821{ 822 rtx x_base = find_base_term (x); 823 rtx y_base = find_base_term (y); 824 825 /* If the address itself has no known base see if a known equivalent 826 value has one. If either address still has no known base, nothing 827 is known about aliasing. */ 828 if (x_base == 0) 829 { 830 rtx x_c; 831 if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x) 832 return 1; 833 x_base = find_base_term (x_c); 834 if (x_base == 0) 835 return 1; 836 } 837 838 if (y_base == 0) 839 { 840 rtx y_c; 841 if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y) 842 return 1; 843 y_base = find_base_term (y_c); 844 if (y_base == 0) 845 return 1; 846 } 847 848 /* If the base addresses are equal nothing is known about aliasing. */ 849 if (rtx_equal_p (x_base, y_base)) 850 return 1; 851 852 /* The base addresses of the read and write are different expressions. 853 If they are both symbols and they are not accessed via AND, there is 854 no conflict. We can bring knowledge of object alignment into play 855 here. For example, on alpha, "char a, b;" can alias one another, 856 though "char a; long b;" cannot. */ 857 if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS) 858 { 859 if (GET_CODE (x) == AND && GET_CODE (y) == AND) 860 return 1; 861 if (GET_CODE (x) == AND 862 && (GET_CODE (XEXP (x, 1)) != CONST_INT 863 || GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1)))) 864 return 1; 865 if (GET_CODE (y) == AND 866 && (GET_CODE (XEXP (y, 1)) != CONST_INT 867 || GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1)))) 868 return 1; 869 /* Differing symbols never alias. */ 870 return 0; 871 } 872 873 /* If one address is a stack reference there can be no alias: 874 stack references using different base registers do not alias, 875 a stack reference can not alias a parameter, and a stack reference 876 can not alias a global. */ 877 if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode) 878 || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode)) 879 return 0; 880 881 if (! flag_argument_noalias) 882 return 1; 883 884 if (flag_argument_noalias > 1) 885 return 0; 886 887 /* Weak noalias assertion (arguments are distinct, but may match globals). */ 888 return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode); 889} 890 891/* Return the address of the (N_REFS + 1)th memory reference to ADDR 892 where SIZE is the size in bytes of the memory reference. If ADDR 893 is not modified by the memory reference then ADDR is returned. */ 894 895rtx 896addr_side_effect_eval (addr, size, n_refs) 897 rtx addr; 898 int size; 899 int n_refs; 900{ 901 int offset = 0; 902 903 switch (GET_CODE (addr)) 904 { 905 case PRE_INC: 906 offset = (n_refs + 1) * size; 907 break; 908 case PRE_DEC: 909 offset = -(n_refs + 1) * size; 910 break; 911 case POST_INC: 912 offset = n_refs * size; 913 break; 914 case POST_DEC: 915 offset = -n_refs * size; 916 break; 917 918 default: 919 return addr; 920 } 921 922 if (offset) 923 addr = gen_rtx_PLUS (GET_MODE (addr), XEXP (addr, 0), GEN_INT (offset)); 924 else 925 addr = XEXP (addr, 0); 926 927 return addr; 928} 929 930/* Return nonzero if X and Y (memory addresses) could reference the 931 same location in memory. C is an offset accumulator. When 932 C is nonzero, we are testing aliases between X and Y + C. 933 XSIZE is the size in bytes of the X reference, 934 similarly YSIZE is the size in bytes for Y. 935 936 If XSIZE or YSIZE is zero, we do not know the amount of memory being 937 referenced (the reference was BLKmode), so make the most pessimistic 938 assumptions. 939 940 If XSIZE or YSIZE is negative, we may access memory outside the object 941 being referenced as a side effect. This can happen when using AND to 942 align memory references, as is done on the Alpha. 943 944 Nice to notice that varying addresses cannot conflict with fp if no 945 local variables had their addresses taken, but that's too hard now. */ 946 947 948static int 949memrefs_conflict_p (xsize, x, ysize, y, c) 950 register rtx x, y; 951 int xsize, ysize; 952 HOST_WIDE_INT c; 953{ 954 if (GET_CODE (x) == HIGH) 955 x = XEXP (x, 0); 956 else if (GET_CODE (x) == LO_SUM) 957 x = XEXP (x, 1); 958 else 959 x = canon_rtx (addr_side_effect_eval (x, xsize, 0)); 960 if (GET_CODE (y) == HIGH) 961 y = XEXP (y, 0); 962 else if (GET_CODE (y) == LO_SUM) 963 y = XEXP (y, 1); 964 else 965 y = canon_rtx (addr_side_effect_eval (y, ysize, 0)); 966 967 if (rtx_equal_for_memref_p (x, y)) 968 { 969 if (xsize <= 0 || ysize <= 0) 970 return 1; 971 if (c >= 0 && xsize > c) 972 return 1; 973 if (c < 0 && ysize+c > 0) 974 return 1; 975 return 0; 976 } 977 978 /* This code used to check for conflicts involving stack references and 979 globals but the base address alias code now handles these cases. */ 980 981 if (GET_CODE (x) == PLUS) 982 { 983 /* The fact that X is canonicalized means that this 984 PLUS rtx is canonicalized. */ 985 rtx x0 = XEXP (x, 0); 986 rtx x1 = XEXP (x, 1); 987 988 if (GET_CODE (y) == PLUS) 989 { 990 /* The fact that Y is canonicalized means that this 991 PLUS rtx is canonicalized. */ 992 rtx y0 = XEXP (y, 0); 993 rtx y1 = XEXP (y, 1); 994 995 if (rtx_equal_for_memref_p (x1, y1)) 996 return memrefs_conflict_p (xsize, x0, ysize, y0, c); 997 if (rtx_equal_for_memref_p (x0, y0)) 998 return memrefs_conflict_p (xsize, x1, ysize, y1, c); 999 if (GET_CODE (x1) == CONST_INT) 1000 { 1001 if (GET_CODE (y1) == CONST_INT) 1002 return memrefs_conflict_p (xsize, x0, ysize, y0, 1003 c - INTVAL (x1) + INTVAL (y1)); 1004 else 1005 return memrefs_conflict_p (xsize, x0, ysize, y, 1006 c - INTVAL (x1)); 1007 } 1008 else if (GET_CODE (y1) == CONST_INT) 1009 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1)); 1010 1011 return 1; 1012 } 1013 else if (GET_CODE (x1) == CONST_INT) 1014 return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1)); 1015 } 1016 else if (GET_CODE (y) == PLUS) 1017 { 1018 /* The fact that Y is canonicalized means that this 1019 PLUS rtx is canonicalized. */ 1020 rtx y0 = XEXP (y, 0); 1021 rtx y1 = XEXP (y, 1); 1022 1023 if (GET_CODE (y1) == CONST_INT) 1024 return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1)); 1025 else 1026 return 1; 1027 } 1028 1029 if (GET_CODE (x) == GET_CODE (y)) 1030 switch (GET_CODE (x)) 1031 { 1032 case MULT: 1033 { 1034 /* Handle cases where we expect the second operands to be the 1035 same, and check only whether the first operand would conflict 1036 or not. */ 1037 rtx x0, y0; 1038 rtx x1 = canon_rtx (XEXP (x, 1)); 1039 rtx y1 = canon_rtx (XEXP (y, 1)); 1040 if (! rtx_equal_for_memref_p (x1, y1)) 1041 return 1; 1042 x0 = canon_rtx (XEXP (x, 0)); 1043 y0 = canon_rtx (XEXP (y, 0)); 1044 if (rtx_equal_for_memref_p (x0, y0)) 1045 return (xsize == 0 || ysize == 0 1046 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); 1047 1048 /* Can't properly adjust our sizes. */ 1049 if (GET_CODE (x1) != CONST_INT) 1050 return 1; 1051 xsize /= INTVAL (x1); 1052 ysize /= INTVAL (x1); 1053 c /= INTVAL (x1); 1054 return memrefs_conflict_p (xsize, x0, ysize, y0, c); 1055 } 1056 1057 case REG: 1058 /* Are these registers known not to be equal? */ 1059 if (alias_invariant) 1060 { 1061 unsigned int r_x = REGNO (x), r_y = REGNO (y); 1062 rtx i_x, i_y; /* invariant relationships of X and Y */ 1063 1064 i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x]; 1065 i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y]; 1066 1067 if (i_x == 0 && i_y == 0) 1068 break; 1069 1070 if (! memrefs_conflict_p (xsize, i_x ? i_x : x, 1071 ysize, i_y ? i_y : y, c)) 1072 return 0; 1073 } 1074 break; 1075 1076 default: 1077 break; 1078 } 1079 1080 /* Treat an access through an AND (e.g. a subword access on an Alpha) 1081 as an access with indeterminate size. Assume that references 1082 besides AND are aligned, so if the size of the other reference is 1083 at least as large as the alignment, assume no other overlap. */ 1084 if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT) 1085 { 1086 if (GET_CODE (y) == AND || ysize < -INTVAL (XEXP (x, 1))) 1087 xsize = -1; 1088 return memrefs_conflict_p (xsize, XEXP (x, 0), ysize, y, c); 1089 } 1090 if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT) 1091 { 1092 /* ??? If we are indexing far enough into the array/structure, we 1093 may yet be able to determine that we can not overlap. But we 1094 also need to that we are far enough from the end not to overlap 1095 a following reference, so we do nothing with that for now. */ 1096 if (GET_CODE (x) == AND || xsize < -INTVAL (XEXP (y, 1))) 1097 ysize = -1; 1098 return memrefs_conflict_p (xsize, x, ysize, XEXP (y, 0), c); 1099 } 1100 1101 if (CONSTANT_P (x)) 1102 { 1103 if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT) 1104 { 1105 c += (INTVAL (y) - INTVAL (x)); 1106 return (xsize <= 0 || ysize <= 0 1107 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); 1108 } 1109 1110 if (GET_CODE (x) == CONST) 1111 { 1112 if (GET_CODE (y) == CONST) 1113 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 1114 ysize, canon_rtx (XEXP (y, 0)), c); 1115 else 1116 return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 1117 ysize, y, c); 1118 } 1119 if (GET_CODE (y) == CONST) 1120 return memrefs_conflict_p (xsize, x, ysize, 1121 canon_rtx (XEXP (y, 0)), c); 1122 1123 if (CONSTANT_P (y)) 1124 return (xsize < 0 || ysize < 0 1125 || (rtx_equal_for_memref_p (x, y) 1126 && (xsize == 0 || ysize == 0 1127 || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)))); 1128 1129 return 1; 1130 } 1131 return 1; 1132} 1133 1134/* Functions to compute memory dependencies. 1135 1136 Since we process the insns in execution order, we can build tables 1137 to keep track of what registers are fixed (and not aliased), what registers 1138 are varying in known ways, and what registers are varying in unknown 1139 ways. 1140 1141 If both memory references are volatile, then there must always be a 1142 dependence between the two references, since their order can not be 1143 changed. A volatile and non-volatile reference can be interchanged 1144 though. 1145 1146 A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never 1147 conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must 1148 allow QImode aliasing because the ANSI C standard allows character 1149 pointers to alias anything. We are assuming that characters are 1150 always QImode here. We also must allow AND addresses, because they may 1151 generate accesses outside the object being referenced. This is used to 1152 generate aligned addresses from unaligned addresses, for instance, the 1153 alpha storeqi_unaligned pattern. */ 1154 1155/* Read dependence: X is read after read in MEM takes place. There can 1156 only be a dependence here if both reads are volatile. */ 1157 1158int 1159read_dependence (mem, x) 1160 rtx mem; 1161 rtx x; 1162{ 1163 return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem); 1164} 1165 1166/* Returns MEM1 if and only if MEM1 is a scalar at a fixed address and 1167 MEM2 is a reference to a structure at a varying address, or returns 1168 MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL 1169 value is returned MEM1 and MEM2 can never alias. VARIES_P is used 1170 to decide whether or not an address may vary; it should return 1171 nozero whenever variation is possible. */ 1172 1173static rtx 1174fixed_scalar_and_varying_struct_p (mem1, mem2, varies_p) 1175 rtx mem1; 1176 rtx mem2; 1177 int (*varies_p) PROTO((rtx)); 1178{ 1179 rtx mem1_addr = XEXP (mem1, 0); 1180 rtx mem2_addr = XEXP (mem2, 0); 1181 1182 if (MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2) 1183 && !varies_p (mem1_addr) && varies_p (mem2_addr)) 1184 /* MEM1 is a scalar at a fixed address; MEM2 is a struct at a 1185 varying address. */ 1186 return mem1; 1187 1188 if (MEM_IN_STRUCT_P (mem1) && MEM_SCALAR_P (mem2) 1189 && varies_p (mem1_addr) && !varies_p (mem2_addr)) 1190 /* MEM2 is a scalar at a fixed address; MEM1 is a struct at a 1191 varying address. */ 1192 return mem2; 1193 1194 return NULL_RTX; 1195} 1196 1197/* Returns nonzero if something about the mode or address format MEM1 1198 indicates that it might well alias *anything*. */ 1199 1200static int 1201aliases_everything_p (mem) 1202 rtx mem; 1203{ 1204 if (GET_MODE (mem) == QImode) 1205 /* ANSI C says that a `char*' can point to anything. */ 1206 return 1; 1207 1208 if (GET_CODE (XEXP (mem, 0)) == AND) 1209 /* If the address is an AND, its very hard to know at what it is 1210 actually pointing. */ 1211 return 1; 1212 1213 return 0; 1214} 1215 1216/* True dependence: X is read after store in MEM takes place. */ 1217 1218int 1219true_dependence (mem, mem_mode, x, varies) 1220 rtx mem; 1221 enum machine_mode mem_mode; 1222 rtx x; 1223 int (*varies) PROTO((rtx)); 1224{ 1225 register rtx x_addr, mem_addr; 1226 1227 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 1228 return 1; 1229 1230 if (DIFFERENT_ALIAS_SETS_P (x, mem)) 1231 return 0; 1232 1233 /* If X is an unchanging read, then it can't possibly conflict with any 1234 non-unchanging store. It may conflict with an unchanging write though, 1235 because there may be a single store to this address to initialize it. 1236 Just fall through to the code below to resolve the case where we have 1237 both an unchanging read and an unchanging write. This won't handle all 1238 cases optimally, but the possible performance loss should be 1239 negligible. */ 1240 if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem)) 1241 return 0; 1242 1243 if (mem_mode == VOIDmode) 1244 mem_mode = GET_MODE (mem); 1245 1246 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0), GET_MODE (x), mem_mode)) 1247 return 0; 1248 1249 x_addr = canon_rtx (XEXP (x, 0)); 1250 mem_addr = canon_rtx (XEXP (mem, 0)); 1251 1252 if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr, 1253 SIZE_FOR_MODE (x), x_addr, 0)) 1254 return 0; 1255 1256 if (aliases_everything_p (x)) 1257 return 1; 1258 1259 /* We cannot use aliases_everyting_p to test MEM, since we must look 1260 at MEM_MODE, rather than GET_MODE (MEM). */ 1261 if (mem_mode == QImode || GET_CODE (mem_addr) == AND) 1262 return 1; 1263 1264 /* In true_dependence we also allow BLKmode to alias anything. Why 1265 don't we do this in anti_dependence and output_dependence? */ 1266 if (mem_mode == BLKmode || GET_MODE (x) == BLKmode) 1267 return 1; 1268 1269 return !fixed_scalar_and_varying_struct_p (mem, x, varies); 1270} 1271 1272/* Returns non-zero if a write to X might alias a previous read from 1273 (or, if WRITEP is non-zero, a write to) MEM. */ 1274 1275static int 1276write_dependence_p (mem, x, writep) 1277 rtx mem; 1278 rtx x; 1279 int writep; 1280{ 1281 rtx x_addr, mem_addr; 1282 rtx fixed_scalar; 1283 1284 if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 1285 return 1; 1286 1287 /* If MEM is an unchanging read, then it can't possibly conflict with 1288 the store to X, because there is at most one store to MEM, and it must 1289 have occurred somewhere before MEM. */ 1290 if (!writep && RTX_UNCHANGING_P (mem)) 1291 return 0; 1292 1293 if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0), GET_MODE (x), 1294 GET_MODE (mem))) 1295 return 0; 1296 1297 x = canon_rtx (x); 1298 mem = canon_rtx (mem); 1299 1300 if (DIFFERENT_ALIAS_SETS_P (x, mem)) 1301 return 0; 1302 1303 x_addr = XEXP (x, 0); 1304 mem_addr = XEXP (mem, 0); 1305 1306 if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr, 1307 SIZE_FOR_MODE (x), x_addr, 0)) 1308 return 0; 1309 1310 fixed_scalar 1311 = fixed_scalar_and_varying_struct_p (mem, x, rtx_addr_varies_p); 1312 1313 return (!(fixed_scalar == mem && !aliases_everything_p (x)) 1314 && !(fixed_scalar == x && !aliases_everything_p (mem))); 1315} 1316 1317/* Anti dependence: X is written after read in MEM takes place. */ 1318 1319int 1320anti_dependence (mem, x) 1321 rtx mem; 1322 rtx x; 1323{ 1324 return write_dependence_p (mem, x, /*writep=*/0); 1325} 1326 1327/* Output dependence: X is written after store in MEM takes place. */ 1328 1329int 1330output_dependence (mem, x) 1331 register rtx mem; 1332 register rtx x; 1333{ 1334 return write_dependence_p (mem, x, /*writep=*/1); 1335} 1336 1337 1338static HARD_REG_SET argument_registers; 1339 1340void 1341init_alias_once () 1342{ 1343 register int i; 1344 1345#ifndef OUTGOING_REGNO 1346#define OUTGOING_REGNO(N) N 1347#endif 1348 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1349 /* Check whether this register can hold an incoming pointer 1350 argument. FUNCTION_ARG_REGNO_P tests outgoing register 1351 numbers, so translate if necessary due to register windows. */ 1352 if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i)) 1353 && HARD_REGNO_MODE_OK (i, Pmode)) 1354 SET_HARD_REG_BIT (argument_registers, i); 1355 1356 alias_sets = splay_tree_new (splay_tree_compare_ints, 0, 0); 1357} 1358 1359void 1360init_alias_analysis () 1361{ 1362 int maxreg = max_reg_num (); 1363 int changed, pass; 1364 register int i; 1365 register unsigned int ui; 1366 register rtx insn; 1367 1368 reg_known_value_size = maxreg; 1369 1370 reg_known_value 1371 = (rtx *) oballoc ((maxreg - FIRST_PSEUDO_REGISTER) * sizeof (rtx)) 1372 - FIRST_PSEUDO_REGISTER; 1373 reg_known_equiv_p = 1374 oballoc (maxreg - FIRST_PSEUDO_REGISTER) - FIRST_PSEUDO_REGISTER; 1375 bzero ((char *) (reg_known_value + FIRST_PSEUDO_REGISTER), 1376 (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx)); 1377 bzero (reg_known_equiv_p + FIRST_PSEUDO_REGISTER, 1378 (maxreg - FIRST_PSEUDO_REGISTER) * sizeof (char)); 1379 1380 /* Overallocate reg_base_value to allow some growth during loop 1381 optimization. Loop unrolling can create a large number of 1382 registers. */ 1383 reg_base_value_size = maxreg * 2; 1384 reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx)); 1385 new_reg_base_value = (rtx *)alloca (reg_base_value_size * sizeof (rtx)); 1386 reg_seen = (char *)alloca (reg_base_value_size); 1387 bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx)); 1388 if (! reload_completed && flag_unroll_loops) 1389 { 1390 alias_invariant = (rtx *)xrealloc (alias_invariant, 1391 reg_base_value_size * sizeof (rtx)); 1392 bzero ((char *)alias_invariant, reg_base_value_size * sizeof (rtx)); 1393 } 1394 1395 1396 /* The basic idea is that each pass through this loop will use the 1397 "constant" information from the previous pass to propagate alias 1398 information through another level of assignments. 1399 1400 This could get expensive if the assignment chains are long. Maybe 1401 we should throttle the number of iterations, possibly based on 1402 the optimization level or flag_expensive_optimizations. 1403 1404 We could propagate more information in the first pass by making use 1405 of REG_N_SETS to determine immediately that the alias information 1406 for a pseudo is "constant". 1407 1408 A program with an uninitialized variable can cause an infinite loop 1409 here. Instead of doing a full dataflow analysis to detect such problems 1410 we just cap the number of iterations for the loop. 1411 1412 The state of the arrays for the set chain in question does not matter 1413 since the program has undefined behavior. */ 1414 1415 pass = 0; 1416 do 1417 { 1418 /* Assume nothing will change this iteration of the loop. */ 1419 changed = 0; 1420 1421 /* We want to assign the same IDs each iteration of this loop, so 1422 start counting from zero each iteration of the loop. */ 1423 unique_id = 0; 1424 1425 /* We're at the start of the funtion each iteration through the 1426 loop, so we're copying arguments. */ 1427 copying_arguments = 1; 1428 1429 /* Wipe the potential alias information clean for this pass. */ 1430 bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx)); 1431 1432 /* Wipe the reg_seen array clean. */ 1433 bzero ((char *) reg_seen, reg_base_value_size); 1434 1435 /* Mark all hard registers which may contain an address. 1436 The stack, frame and argument pointers may contain an address. 1437 An argument register which can hold a Pmode value may contain 1438 an address even if it is not in BASE_REGS. 1439 1440 The address expression is VOIDmode for an argument and 1441 Pmode for other registers. */ 1442 1443 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1444 if (TEST_HARD_REG_BIT (argument_registers, i)) 1445 new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode, 1446 gen_rtx_REG (Pmode, i)); 1447 1448 new_reg_base_value[STACK_POINTER_REGNUM] 1449 = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx); 1450 new_reg_base_value[ARG_POINTER_REGNUM] 1451 = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx); 1452 new_reg_base_value[FRAME_POINTER_REGNUM] 1453 = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx); 1454#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 1455 new_reg_base_value[HARD_FRAME_POINTER_REGNUM] 1456 = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx); 1457#endif 1458 1459 /* Walk the insns adding values to the new_reg_base_value array. */ 1460 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 1461 { 1462 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') 1463 { 1464 rtx note, set; 1465 /* If this insn has a noalias note, process it, Otherwise, 1466 scan for sets. A simple set will have no side effects 1467 which could change the base value of any other register. */ 1468 1469 if (GET_CODE (PATTERN (insn)) == SET 1470 && (find_reg_note (insn, REG_NOALIAS, NULL_RTX))) 1471 record_set (SET_DEST (PATTERN (insn)), NULL_RTX); 1472 else 1473 note_stores (PATTERN (insn), record_set); 1474 1475 set = single_set (insn); 1476 1477 if (set != 0 1478 && GET_CODE (SET_DEST (set)) == REG 1479 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER 1480 && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0 1481 && REG_N_SETS (REGNO (SET_DEST (set))) == 1) 1482 || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0) 1483 && GET_CODE (XEXP (note, 0)) != EXPR_LIST 1484 && ! reg_overlap_mentioned_p (SET_DEST (set), XEXP (note, 0))) 1485 { 1486 int regno = REGNO (SET_DEST (set)); 1487 reg_known_value[regno] = XEXP (note, 0); 1488 reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV; 1489 } 1490 } 1491 else if (GET_CODE (insn) == NOTE 1492 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG) 1493 copying_arguments = 0; 1494 } 1495 1496 /* Now propagate values from new_reg_base_value to reg_base_value. */ 1497 for (ui = 0; ui < reg_base_value_size; ui++) 1498 { 1499 if (new_reg_base_value[ui] 1500 && new_reg_base_value[ui] != reg_base_value[ui] 1501 && ! rtx_equal_p (new_reg_base_value[ui], reg_base_value[ui])) 1502 { 1503 reg_base_value[ui] = new_reg_base_value[ui]; 1504 changed = 1; 1505 } 1506 } 1507 } 1508 while (changed && ++pass < MAX_ALIAS_LOOP_PASSES); 1509 1510 /* Fill in the remaining entries. */ 1511 for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++) 1512 if (reg_known_value[i] == 0) 1513 reg_known_value[i] = regno_reg_rtx[i]; 1514 1515 /* Simplify the reg_base_value array so that no register refers to 1516 another register, except to special registers indirectly through 1517 ADDRESS expressions. 1518 1519 In theory this loop can take as long as O(registers^2), but unless 1520 there are very long dependency chains it will run in close to linear 1521 time. 1522 1523 This loop may not be needed any longer now that the main loop does 1524 a better job at propagating alias information. */ 1525 pass = 0; 1526 do 1527 { 1528 changed = 0; 1529 pass++; 1530 for (ui = 0; ui < reg_base_value_size; ui++) 1531 { 1532 rtx base = reg_base_value[ui]; 1533 if (base && GET_CODE (base) == REG) 1534 { 1535 unsigned int base_regno = REGNO (base); 1536 if (base_regno == ui) /* register set from itself */ 1537 reg_base_value[ui] = 0; 1538 else 1539 reg_base_value[ui] = reg_base_value[base_regno]; 1540 changed = 1; 1541 } 1542 } 1543 } 1544 while (changed && pass < MAX_ALIAS_LOOP_PASSES); 1545 1546 new_reg_base_value = 0; 1547 reg_seen = 0; 1548} 1549 1550void 1551end_alias_analysis () 1552{ 1553 reg_known_value = 0; 1554 reg_base_value = 0; 1555 reg_base_value_size = 0; 1556 if (alias_invariant) 1557 { 1558 free ((char *)alias_invariant); 1559 alias_invariant = 0; 1560 } 1561} 1562