alias.c revision 50397
150397Sobrien/* Alias analysis for GNU C 250397Sobrien Copyright (C) 1997, 1998 Free Software Foundation, Inc. 350397Sobrien Contributed by John Carr (jfc@mit.edu). 450397Sobrien 550397SobrienThis file is part of GNU CC. 650397Sobrien 750397SobrienGNU CC is free software; you can redistribute it and/or modify 850397Sobrienit under the terms of the GNU General Public License as published by 950397Sobrienthe Free Software Foundation; either version 2, or (at your option) 1050397Sobrienany later version. 1150397Sobrien 1250397SobrienGNU CC is distributed in the hope that it will be useful, 1350397Sobrienbut WITHOUT ANY WARRANTY; without even the implied warranty of 1450397SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1550397SobrienGNU General Public License for more details. 1650397Sobrien 1750397SobrienYou should have received a copy of the GNU General Public License 1850397Sobrienalong with GNU CC; see the file COPYING. If not, write to 1950397Sobrienthe Free Software Foundation, 59 Temple Place - Suite 330, 2050397SobrienBoston, MA 02111-1307, USA. */ 2150397Sobrien 2250397Sobrien#include "config.h" 2350397Sobrien#include "system.h" 2450397Sobrien#include "rtl.h" 2550397Sobrien#include "expr.h" 2650397Sobrien#include "regs.h" 2750397Sobrien#include "hard-reg-set.h" 2850397Sobrien#include "flags.h" 2950397Sobrien#include "toplev.h" 3050397Sobrien 3150397Sobrienstatic rtx canon_rtx PROTO((rtx)); 3250397Sobrienstatic int rtx_equal_for_memref_p PROTO((rtx, rtx)); 3350397Sobrienstatic rtx find_symbolic_term PROTO((rtx)); 3450397Sobrienstatic int memrefs_conflict_p PROTO((int, rtx, int, rtx, 3550397Sobrien HOST_WIDE_INT)); 3650397Sobrienstatic void record_set PROTO((rtx, rtx)); 3750397Sobrienstatic rtx find_base_term PROTO((rtx)); 3850397Sobrienstatic int base_alias_check PROTO((rtx, rtx)); 3950397Sobrienstatic rtx find_base_value PROTO((rtx)); 4050397Sobrien 4150397Sobrien/* Set up all info needed to perform alias analysis on memory references. */ 4250397Sobrien 4350397Sobrien#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X))) 4450397Sobrien 4550397Sobrien/* Perform a basic sanity check. Namely, that there are 4650397Sobrien no alias sets if we're not doing strict aliasing. This helps 4750397Sobrien to catch bugs whereby someone uses PUT_CODE, but doesn't clear 4850397Sobrien MEM_ALIAS_SET, or where a MEM is allocated in some way other 4950397Sobrien than by the use of gen_rtx_MEM, and the MEM_ALIAS_SET is not 5050397Sobrien cleared. */ 5150397Sobrien#ifdef ENABLE_CHECKING 5250397Sobrien#define CHECK_ALIAS_SETS_FOR_CONSISTENCY(MEM1, MEM2) \ 5350397Sobrien (!flag_strict_aliasing \ 5450397Sobrien && (MEM_ALIAS_SET (MEM1) || MEM_ALIAS_SET (MEM2)) \ 5550397Sobrien ? (abort (), 0) : 0) 5650397Sobrien#else 5750397Sobrien#define CHECK_ALIAS_SETS_FOR_CONSISTENCY(MEM1, MEM2) ((void)0) 5850397Sobrien#endif 5950397Sobrien 6050397Sobrien/* Returns nonzero if MEM1 and MEM2 do not alias because they are in 6150397Sobrien different alias sets. */ 6250397Sobrien#define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \ 6350397Sobrien (CHECK_ALIAS_SETS_FOR_CONSISTENCY(MEM1, MEM2), \ 6450397Sobrien MEM_ALIAS_SET (MEM1) && MEM_ALIAS_SET (MEM2) \ 6550397Sobrien && MEM_ALIAS_SET (MEM1) != MEM_ALIAS_SET (MEM2)) 6650397Sobrien 6750397Sobrien/* Cap the number of passes we make over the insns propagating alias 6850397Sobrien information through set chains. 6950397Sobrien 7050397Sobrien 10 is a completely arbitrary choice. */ 7150397Sobrien#define MAX_ALIAS_LOOP_PASSES 10 7250397Sobrien 7350397Sobrien/* reg_base_value[N] gives an address to which register N is related. 7450397Sobrien If all sets after the first add or subtract to the current value 7550397Sobrien or otherwise modify it so it does not point to a different top level 7650397Sobrien object, reg_base_value[N] is equal to the address part of the source 7750397Sobrien of the first set. 7850397Sobrien 7950397Sobrien A base address can be an ADDRESS, SYMBOL_REF, or LABEL_REF. ADDRESS 8050397Sobrien expressions represent certain special values: function arguments and 8150397Sobrien the stack, frame, and argument pointers. The contents of an address 8250397Sobrien expression are not used (but they are descriptive for debugging); 8350397Sobrien only the address and mode matter. Pointer equality, not rtx_equal_p, 8450397Sobrien determines whether two ADDRESS expressions refer to the same base 8550397Sobrien address. The mode determines whether it is a function argument or 8650397Sobrien other special value. */ 8750397Sobrien 8850397Sobrienrtx *reg_base_value; 8950397Sobrienrtx *new_reg_base_value; 9050397Sobrienunsigned int reg_base_value_size; /* size of reg_base_value array */ 9150397Sobrien#define REG_BASE_VALUE(X) \ 9250397Sobrien (REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0) 9350397Sobrien 9450397Sobrien/* Vector of known invariant relationships between registers. Set in 9550397Sobrien loop unrolling. Indexed by register number, if nonzero the value 9650397Sobrien is an expression describing this register in terms of another. 9750397Sobrien 9850397Sobrien The length of this array is REG_BASE_VALUE_SIZE. 9950397Sobrien 10050397Sobrien Because this array contains only pseudo registers it has no effect 10150397Sobrien after reload. */ 10250397Sobrienstatic rtx *alias_invariant; 10350397Sobrien 10450397Sobrien/* Vector indexed by N giving the initial (unchanging) value known 10550397Sobrien for pseudo-register N. */ 10650397Sobrienrtx *reg_known_value; 10750397Sobrien 10850397Sobrien/* Indicates number of valid entries in reg_known_value. */ 10950397Sobrienstatic int reg_known_value_size; 11050397Sobrien 11150397Sobrien/* Vector recording for each reg_known_value whether it is due to a 11250397Sobrien REG_EQUIV note. Future passes (viz., reload) may replace the 11350397Sobrien pseudo with the equivalent expression and so we account for the 11450397Sobrien dependences that would be introduced if that happens. */ 11550397Sobrien/* ??? This is a problem only on the Convex. The REG_EQUIV notes created in 11650397Sobrien assign_parms mention the arg pointer, and there are explicit insns in the 11750397Sobrien RTL that modify the arg pointer. Thus we must ensure that such insns don't 11850397Sobrien get scheduled across each other because that would invalidate the REG_EQUIV 11950397Sobrien notes. One could argue that the REG_EQUIV notes are wrong, but solving 12050397Sobrien the problem in the scheduler will likely give better code, so we do it 12150397Sobrien here. */ 12250397Sobrienchar *reg_known_equiv_p; 12350397Sobrien 12450397Sobrien/* True when scanning insns from the start of the rtl to the 12550397Sobrien NOTE_INSN_FUNCTION_BEG note. */ 12650397Sobrien 12750397Sobrienstatic int copying_arguments; 12850397Sobrien 12950397Sobrien/* Inside SRC, the source of a SET, find a base address. */ 13050397Sobrien 13150397Sobrienstatic rtx 13250397Sobrienfind_base_value (src) 13350397Sobrien register rtx src; 13450397Sobrien{ 13550397Sobrien switch (GET_CODE (src)) 13650397Sobrien { 13750397Sobrien case SYMBOL_REF: 13850397Sobrien case LABEL_REF: 13950397Sobrien return src; 14050397Sobrien 14150397Sobrien case REG: 14250397Sobrien /* At the start of a function argument registers have known base 14350397Sobrien values which may be lost later. Returning an ADDRESS 14450397Sobrien expression here allows optimization based on argument values 14550397Sobrien even when the argument registers are used for other purposes. */ 14650397Sobrien if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments) 14750397Sobrien return new_reg_base_value[REGNO (src)]; 14850397Sobrien 14950397Sobrien /* If a pseudo has a known base value, return it. Do not do this 15050397Sobrien for hard regs since it can result in a circular dependency 15150397Sobrien chain for registers which have values at function entry. 15250397Sobrien 15350397Sobrien The test above is not sufficient because the scheduler may move 15450397Sobrien a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */ 15550397Sobrien if (REGNO (src) >= FIRST_PSEUDO_REGISTER 15650397Sobrien && REGNO (src) < reg_base_value_size 15750397Sobrien && reg_base_value[REGNO (src)]) 15850397Sobrien return reg_base_value[REGNO (src)]; 15950397Sobrien 16050397Sobrien return src; 16150397Sobrien 16250397Sobrien case MEM: 16350397Sobrien /* Check for an argument passed in memory. Only record in the 16450397Sobrien copying-arguments block; it is too hard to track changes 16550397Sobrien otherwise. */ 16650397Sobrien if (copying_arguments 16750397Sobrien && (XEXP (src, 0) == arg_pointer_rtx 16850397Sobrien || (GET_CODE (XEXP (src, 0)) == PLUS 16950397Sobrien && XEXP (XEXP (src, 0), 0) == arg_pointer_rtx))) 17050397Sobrien return gen_rtx_ADDRESS (VOIDmode, src); 17150397Sobrien return 0; 17250397Sobrien 17350397Sobrien case CONST: 17450397Sobrien src = XEXP (src, 0); 17550397Sobrien if (GET_CODE (src) != PLUS && GET_CODE (src) != MINUS) 17650397Sobrien break; 17750397Sobrien /* fall through */ 17850397Sobrien 17950397Sobrien case PLUS: 18050397Sobrien case MINUS: 18150397Sobrien { 18250397Sobrien rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1); 18350397Sobrien 18450397Sobrien /* If either operand is a REG, then see if we already have 18550397Sobrien a known value for it. */ 18650397Sobrien if (GET_CODE (src_0) == REG) 18750397Sobrien { 18850397Sobrien temp = find_base_value (src_0); 18950397Sobrien if (temp) 19050397Sobrien src_0 = temp; 19150397Sobrien } 19250397Sobrien 19350397Sobrien if (GET_CODE (src_1) == REG) 19450397Sobrien { 19550397Sobrien temp = find_base_value (src_1); 19650397Sobrien if (temp) 19750397Sobrien src_1 = temp; 19850397Sobrien } 19950397Sobrien 20050397Sobrien /* Guess which operand is the base address. 20150397Sobrien 20250397Sobrien If either operand is a symbol, then it is the base. If 20350397Sobrien either operand is a CONST_INT, then the other is the base. */ 20450397Sobrien 20550397Sobrien if (GET_CODE (src_1) == CONST_INT 20650397Sobrien || GET_CODE (src_0) == SYMBOL_REF 20750397Sobrien || GET_CODE (src_0) == LABEL_REF 20850397Sobrien || GET_CODE (src_0) == CONST) 20950397Sobrien return find_base_value (src_0); 21050397Sobrien 21150397Sobrien if (GET_CODE (src_0) == CONST_INT 21250397Sobrien || GET_CODE (src_1) == SYMBOL_REF 21350397Sobrien || GET_CODE (src_1) == LABEL_REF 21450397Sobrien || GET_CODE (src_1) == CONST) 21550397Sobrien return find_base_value (src_1); 21650397Sobrien 21750397Sobrien /* This might not be necessary anymore. 21850397Sobrien 21950397Sobrien If either operand is a REG that is a known pointer, then it 22050397Sobrien is the base. */ 22150397Sobrien if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0))) 22250397Sobrien return find_base_value (src_0); 22350397Sobrien 22450397Sobrien if (GET_CODE (src_1) == REG && REGNO_POINTER_FLAG (REGNO (src_1))) 22550397Sobrien return find_base_value (src_1); 22650397Sobrien 22750397Sobrien return 0; 22850397Sobrien } 22950397Sobrien 23050397Sobrien case LO_SUM: 23150397Sobrien /* The standard form is (lo_sum reg sym) so look only at the 23250397Sobrien second operand. */ 23350397Sobrien return find_base_value (XEXP (src, 1)); 23450397Sobrien 23550397Sobrien case AND: 23650397Sobrien /* If the second operand is constant set the base 23750397Sobrien address to the first operand. */ 23850397Sobrien if (GET_CODE (XEXP (src, 1)) == CONST_INT && INTVAL (XEXP (src, 1)) != 0) 23950397Sobrien return find_base_value (XEXP (src, 0)); 24050397Sobrien return 0; 24150397Sobrien 24250397Sobrien case ZERO_EXTEND: 24350397Sobrien case SIGN_EXTEND: /* used for NT/Alpha pointers */ 24450397Sobrien case HIGH: 24550397Sobrien return find_base_value (XEXP (src, 0)); 24650397Sobrien 24750397Sobrien default: 24850397Sobrien break; 24950397Sobrien } 25050397Sobrien 25150397Sobrien return 0; 25250397Sobrien} 25350397Sobrien 25450397Sobrien/* Called from init_alias_analysis indirectly through note_stores. */ 25550397Sobrien 25650397Sobrien/* while scanning insns to find base values, reg_seen[N] is nonzero if 25750397Sobrien register N has been set in this function. */ 25850397Sobrienstatic char *reg_seen; 25950397Sobrien 26050397Sobrien/* Addresses which are known not to alias anything else are identified 26150397Sobrien by a unique integer. */ 26250397Sobrienstatic int unique_id; 26350397Sobrien 26450397Sobrienstatic void 26550397Sobrienrecord_set (dest, set) 26650397Sobrien rtx dest, set; 26750397Sobrien{ 26850397Sobrien register int regno; 26950397Sobrien rtx src; 27050397Sobrien 27150397Sobrien if (GET_CODE (dest) != REG) 27250397Sobrien return; 27350397Sobrien 27450397Sobrien regno = REGNO (dest); 27550397Sobrien 27650397Sobrien if (set) 27750397Sobrien { 27850397Sobrien /* A CLOBBER wipes out any old value but does not prevent a previously 27950397Sobrien unset register from acquiring a base address (i.e. reg_seen is not 28050397Sobrien set). */ 28150397Sobrien if (GET_CODE (set) == CLOBBER) 28250397Sobrien { 28350397Sobrien new_reg_base_value[regno] = 0; 28450397Sobrien return; 28550397Sobrien } 28650397Sobrien src = SET_SRC (set); 28750397Sobrien } 28850397Sobrien else 28950397Sobrien { 29050397Sobrien if (reg_seen[regno]) 29150397Sobrien { 29250397Sobrien new_reg_base_value[regno] = 0; 29350397Sobrien return; 29450397Sobrien } 29550397Sobrien reg_seen[regno] = 1; 29650397Sobrien new_reg_base_value[regno] = gen_rtx_ADDRESS (Pmode, 29750397Sobrien GEN_INT (unique_id++)); 29850397Sobrien return; 29950397Sobrien } 30050397Sobrien 30150397Sobrien /* This is not the first set. If the new value is not related to the 30250397Sobrien old value, forget the base value. Note that the following code is 30350397Sobrien not detected: 30450397Sobrien extern int x, y; int *p = &x; p += (&y-&x); 30550397Sobrien ANSI C does not allow computing the difference of addresses 30650397Sobrien of distinct top level objects. */ 30750397Sobrien if (new_reg_base_value[regno]) 30850397Sobrien switch (GET_CODE (src)) 30950397Sobrien { 31050397Sobrien case LO_SUM: 31150397Sobrien case PLUS: 31250397Sobrien case MINUS: 31350397Sobrien if (XEXP (src, 0) != dest && XEXP (src, 1) != dest) 31450397Sobrien new_reg_base_value[regno] = 0; 31550397Sobrien break; 31650397Sobrien case AND: 31750397Sobrien if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT) 31850397Sobrien new_reg_base_value[regno] = 0; 31950397Sobrien break; 32050397Sobrien default: 32150397Sobrien new_reg_base_value[regno] = 0; 32250397Sobrien break; 32350397Sobrien } 32450397Sobrien /* If this is the first set of a register, record the value. */ 32550397Sobrien else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno]) 32650397Sobrien && ! reg_seen[regno] && new_reg_base_value[regno] == 0) 32750397Sobrien new_reg_base_value[regno] = find_base_value (src); 32850397Sobrien 32950397Sobrien reg_seen[regno] = 1; 33050397Sobrien} 33150397Sobrien 33250397Sobrien/* Called from loop optimization when a new pseudo-register is created. */ 33350397Sobrienvoid 33450397Sobrienrecord_base_value (regno, val, invariant) 33550397Sobrien int regno; 33650397Sobrien rtx val; 33750397Sobrien int invariant; 33850397Sobrien{ 33950397Sobrien if (regno >= reg_base_value_size) 34050397Sobrien return; 34150397Sobrien 34250397Sobrien /* If INVARIANT is true then this value also describes an invariant 34350397Sobrien relationship which can be used to deduce that two registers with 34450397Sobrien unknown values are different. */ 34550397Sobrien if (invariant && alias_invariant) 34650397Sobrien alias_invariant[regno] = val; 34750397Sobrien 34850397Sobrien if (GET_CODE (val) == REG) 34950397Sobrien { 35050397Sobrien if (REGNO (val) < reg_base_value_size) 35150397Sobrien { 35250397Sobrien reg_base_value[regno] = reg_base_value[REGNO (val)]; 35350397Sobrien } 35450397Sobrien return; 35550397Sobrien } 35650397Sobrien reg_base_value[regno] = find_base_value (val); 35750397Sobrien} 35850397Sobrien 35950397Sobrienstatic rtx 36050397Sobriencanon_rtx (x) 36150397Sobrien rtx x; 36250397Sobrien{ 36350397Sobrien /* Recursively look for equivalences. */ 36450397Sobrien if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER 36550397Sobrien && REGNO (x) < reg_known_value_size) 36650397Sobrien return reg_known_value[REGNO (x)] == x 36750397Sobrien ? x : canon_rtx (reg_known_value[REGNO (x)]); 36850397Sobrien else if (GET_CODE (x) == PLUS) 36950397Sobrien { 37050397Sobrien rtx x0 = canon_rtx (XEXP (x, 0)); 37150397Sobrien rtx x1 = canon_rtx (XEXP (x, 1)); 37250397Sobrien 37350397Sobrien if (x0 != XEXP (x, 0) || x1 != XEXP (x, 1)) 37450397Sobrien { 37550397Sobrien /* We can tolerate LO_SUMs being offset here; these 37650397Sobrien rtl are used for nothing other than comparisons. */ 37750397Sobrien if (GET_CODE (x0) == CONST_INT) 37850397Sobrien return plus_constant_for_output (x1, INTVAL (x0)); 37950397Sobrien else if (GET_CODE (x1) == CONST_INT) 38050397Sobrien return plus_constant_for_output (x0, INTVAL (x1)); 38150397Sobrien return gen_rtx_PLUS (GET_MODE (x), x0, x1); 38250397Sobrien } 38350397Sobrien } 38450397Sobrien /* This gives us much better alias analysis when called from 38550397Sobrien the loop optimizer. Note we want to leave the original 38650397Sobrien MEM alone, but need to return the canonicalized MEM with 38750397Sobrien all the flags with their original values. */ 38850397Sobrien else if (GET_CODE (x) == MEM) 38950397Sobrien { 39050397Sobrien rtx addr = canon_rtx (XEXP (x, 0)); 39150397Sobrien if (addr != XEXP (x, 0)) 39250397Sobrien { 39350397Sobrien rtx new = gen_rtx_MEM (GET_MODE (x), addr); 39450397Sobrien MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x); 39550397Sobrien RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x); 39650397Sobrien MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x); 39750397Sobrien MEM_ALIAS_SET (new) = MEM_ALIAS_SET (x); 39850397Sobrien x = new; 39950397Sobrien } 40050397Sobrien } 40150397Sobrien return x; 40250397Sobrien} 40350397Sobrien 40450397Sobrien/* Return 1 if X and Y are identical-looking rtx's. 40550397Sobrien 40650397Sobrien We use the data in reg_known_value above to see if two registers with 40750397Sobrien different numbers are, in fact, equivalent. */ 40850397Sobrien 40950397Sobrienstatic int 41050397Sobrienrtx_equal_for_memref_p (x, y) 41150397Sobrien rtx x, y; 41250397Sobrien{ 41350397Sobrien register int i; 41450397Sobrien register int j; 41550397Sobrien register enum rtx_code code; 41650397Sobrien register char *fmt; 41750397Sobrien 41850397Sobrien if (x == 0 && y == 0) 41950397Sobrien return 1; 42050397Sobrien if (x == 0 || y == 0) 42150397Sobrien return 0; 42250397Sobrien x = canon_rtx (x); 42350397Sobrien y = canon_rtx (y); 42450397Sobrien 42550397Sobrien if (x == y) 42650397Sobrien return 1; 42750397Sobrien 42850397Sobrien code = GET_CODE (x); 42950397Sobrien /* Rtx's of different codes cannot be equal. */ 43050397Sobrien if (code != GET_CODE (y)) 43150397Sobrien return 0; 43250397Sobrien 43350397Sobrien /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. 43450397Sobrien (REG:SI x) and (REG:HI x) are NOT equivalent. */ 43550397Sobrien 43650397Sobrien if (GET_MODE (x) != GET_MODE (y)) 43750397Sobrien return 0; 43850397Sobrien 43950397Sobrien /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */ 44050397Sobrien 44150397Sobrien if (code == REG) 44250397Sobrien return REGNO (x) == REGNO (y); 44350397Sobrien if (code == LABEL_REF) 44450397Sobrien return XEXP (x, 0) == XEXP (y, 0); 44550397Sobrien if (code == SYMBOL_REF) 44650397Sobrien return XSTR (x, 0) == XSTR (y, 0); 44750397Sobrien if (code == CONST_INT) 44850397Sobrien return INTVAL (x) == INTVAL (y); 44950397Sobrien if (code == ADDRESSOF) 45050397Sobrien return REGNO (XEXP (x, 0)) == REGNO (XEXP (y, 0)) && XINT (x, 1) == XINT (y, 1); 45150397Sobrien 45250397Sobrien /* For commutative operations, the RTX match if the operand match in any 45350397Sobrien order. Also handle the simple binary and unary cases without a loop. */ 45450397Sobrien if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c') 45550397Sobrien return ((rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)) 45650397Sobrien && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1))) 45750397Sobrien || (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 1)) 45850397Sobrien && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 0)))); 45950397Sobrien else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2') 46050397Sobrien return (rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)) 46150397Sobrien && rtx_equal_for_memref_p (XEXP (x, 1), XEXP (y, 1))); 46250397Sobrien else if (GET_RTX_CLASS (code) == '1') 46350397Sobrien return rtx_equal_for_memref_p (XEXP (x, 0), XEXP (y, 0)); 46450397Sobrien 46550397Sobrien /* Compare the elements. If any pair of corresponding elements 46650397Sobrien fail to match, return 0 for the whole things. 46750397Sobrien 46850397Sobrien Limit cases to types which actually appear in addresses. */ 46950397Sobrien 47050397Sobrien fmt = GET_RTX_FORMAT (code); 47150397Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 47250397Sobrien { 47350397Sobrien switch (fmt[i]) 47450397Sobrien { 47550397Sobrien case 'i': 47650397Sobrien if (XINT (x, i) != XINT (y, i)) 47750397Sobrien return 0; 47850397Sobrien break; 47950397Sobrien 48050397Sobrien case 'E': 48150397Sobrien /* Two vectors must have the same length. */ 48250397Sobrien if (XVECLEN (x, i) != XVECLEN (y, i)) 48350397Sobrien return 0; 48450397Sobrien 48550397Sobrien /* And the corresponding elements must match. */ 48650397Sobrien for (j = 0; j < XVECLEN (x, i); j++) 48750397Sobrien if (rtx_equal_for_memref_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0) 48850397Sobrien return 0; 48950397Sobrien break; 49050397Sobrien 49150397Sobrien case 'e': 49250397Sobrien if (rtx_equal_for_memref_p (XEXP (x, i), XEXP (y, i)) == 0) 49350397Sobrien return 0; 49450397Sobrien break; 49550397Sobrien 49650397Sobrien /* This can happen for an asm which clobbers memory. */ 49750397Sobrien case '0': 49850397Sobrien break; 49950397Sobrien 50050397Sobrien /* It is believed that rtx's at this level will never 50150397Sobrien contain anything but integers and other rtx's, 50250397Sobrien except for within LABEL_REFs and SYMBOL_REFs. */ 50350397Sobrien default: 50450397Sobrien abort (); 50550397Sobrien } 50650397Sobrien } 50750397Sobrien return 1; 50850397Sobrien} 50950397Sobrien 51050397Sobrien/* Given an rtx X, find a SYMBOL_REF or LABEL_REF within 51150397Sobrien X and return it, or return 0 if none found. */ 51250397Sobrien 51350397Sobrienstatic rtx 51450397Sobrienfind_symbolic_term (x) 51550397Sobrien rtx x; 51650397Sobrien{ 51750397Sobrien register int i; 51850397Sobrien register enum rtx_code code; 51950397Sobrien register char *fmt; 52050397Sobrien 52150397Sobrien code = GET_CODE (x); 52250397Sobrien if (code == SYMBOL_REF || code == LABEL_REF) 52350397Sobrien return x; 52450397Sobrien if (GET_RTX_CLASS (code) == 'o') 52550397Sobrien return 0; 52650397Sobrien 52750397Sobrien fmt = GET_RTX_FORMAT (code); 52850397Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 52950397Sobrien { 53050397Sobrien rtx t; 53150397Sobrien 53250397Sobrien if (fmt[i] == 'e') 53350397Sobrien { 53450397Sobrien t = find_symbolic_term (XEXP (x, i)); 53550397Sobrien if (t != 0) 53650397Sobrien return t; 53750397Sobrien } 53850397Sobrien else if (fmt[i] == 'E') 53950397Sobrien break; 54050397Sobrien } 54150397Sobrien return 0; 54250397Sobrien} 54350397Sobrien 54450397Sobrienstatic rtx 54550397Sobrienfind_base_term (x) 54650397Sobrien register rtx x; 54750397Sobrien{ 54850397Sobrien switch (GET_CODE (x)) 54950397Sobrien { 55050397Sobrien case REG: 55150397Sobrien return REG_BASE_VALUE (x); 55250397Sobrien 55350397Sobrien case ZERO_EXTEND: 55450397Sobrien case SIGN_EXTEND: /* Used for Alpha/NT pointers */ 55550397Sobrien case HIGH: 55650397Sobrien case PRE_INC: 55750397Sobrien case PRE_DEC: 55850397Sobrien case POST_INC: 55950397Sobrien case POST_DEC: 56050397Sobrien return find_base_term (XEXP (x, 0)); 56150397Sobrien 56250397Sobrien case CONST: 56350397Sobrien x = XEXP (x, 0); 56450397Sobrien if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS) 56550397Sobrien return 0; 56650397Sobrien /* fall through */ 56750397Sobrien case LO_SUM: 56850397Sobrien case PLUS: 56950397Sobrien case MINUS: 57050397Sobrien { 57150397Sobrien rtx tmp = find_base_term (XEXP (x, 0)); 57250397Sobrien if (tmp) 57350397Sobrien return tmp; 57450397Sobrien return find_base_term (XEXP (x, 1)); 57550397Sobrien } 57650397Sobrien 57750397Sobrien case AND: 57850397Sobrien if (GET_CODE (XEXP (x, 0)) == REG && GET_CODE (XEXP (x, 1)) == CONST_INT) 57950397Sobrien return REG_BASE_VALUE (XEXP (x, 0)); 58050397Sobrien return 0; 58150397Sobrien 58250397Sobrien case SYMBOL_REF: 58350397Sobrien case LABEL_REF: 58450397Sobrien return x; 58550397Sobrien 58650397Sobrien default: 58750397Sobrien return 0; 58850397Sobrien } 58950397Sobrien} 59050397Sobrien 59150397Sobrien/* Return 0 if the addresses X and Y are known to point to different 59250397Sobrien objects, 1 if they might be pointers to the same object. */ 59350397Sobrien 59450397Sobrienstatic int 59550397Sobrienbase_alias_check (x, y) 59650397Sobrien rtx x, y; 59750397Sobrien{ 59850397Sobrien rtx x_base = find_base_term (x); 59950397Sobrien rtx y_base = find_base_term (y); 60050397Sobrien 60150397Sobrien /* If the address itself has no known base see if a known equivalent 60250397Sobrien value has one. If either address still has no known base, nothing 60350397Sobrien is known about aliasing. */ 60450397Sobrien if (x_base == 0) 60550397Sobrien { 60650397Sobrien rtx x_c; 60750397Sobrien if (! flag_expensive_optimizations || (x_c = canon_rtx (x)) == x) 60850397Sobrien return 1; 60950397Sobrien x_base = find_base_term (x_c); 61050397Sobrien if (x_base == 0) 61150397Sobrien return 1; 61250397Sobrien } 61350397Sobrien 61450397Sobrien if (y_base == 0) 61550397Sobrien { 61650397Sobrien rtx y_c; 61750397Sobrien if (! flag_expensive_optimizations || (y_c = canon_rtx (y)) == y) 61850397Sobrien return 1; 61950397Sobrien y_base = find_base_term (y_c); 62050397Sobrien if (y_base == 0) 62150397Sobrien return 1; 62250397Sobrien } 62350397Sobrien 62450397Sobrien /* If the base addresses are equal nothing is known about aliasing. */ 62550397Sobrien if (rtx_equal_p (x_base, y_base)) 62650397Sobrien return 1; 62750397Sobrien 62850397Sobrien /* The base addresses of the read and write are different 62950397Sobrien expressions. If they are both symbols and they are not accessed 63050397Sobrien via AND, there is no conflict. */ 63150397Sobrien /* XXX: We can bring knowledge of object alignment and offset into 63250397Sobrien play here. For example, on alpha, "char a, b;" can alias one 63350397Sobrien another, though "char a; long b;" cannot. Similarly, offsets 63450397Sobrien into strutures may be brought into play. Given "char a, b[40];", 63550397Sobrien a and b[1] may overlap, but a and b[20] do not. */ 63650397Sobrien if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS) 63750397Sobrien { 63850397Sobrien return GET_CODE (x) == AND || GET_CODE (y) == AND; 63950397Sobrien } 64050397Sobrien 64150397Sobrien /* If one address is a stack reference there can be no alias: 64250397Sobrien stack references using different base registers do not alias, 64350397Sobrien a stack reference can not alias a parameter, and a stack reference 64450397Sobrien can not alias a global. */ 64550397Sobrien if ((GET_CODE (x_base) == ADDRESS && GET_MODE (x_base) == Pmode) 64650397Sobrien || (GET_CODE (y_base) == ADDRESS && GET_MODE (y_base) == Pmode)) 64750397Sobrien return 0; 64850397Sobrien 64950397Sobrien if (! flag_argument_noalias) 65050397Sobrien return 1; 65150397Sobrien 65250397Sobrien if (flag_argument_noalias > 1) 65350397Sobrien return 0; 65450397Sobrien 65550397Sobrien /* Weak noalias assertion (arguments are distinct, but may match globals). */ 65650397Sobrien return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode); 65750397Sobrien} 65850397Sobrien 65950397Sobrien/* Return nonzero if X and Y (memory addresses) could reference the 66050397Sobrien same location in memory. C is an offset accumulator. When 66150397Sobrien C is nonzero, we are testing aliases between X and Y + C. 66250397Sobrien XSIZE is the size in bytes of the X reference, 66350397Sobrien similarly YSIZE is the size in bytes for Y. 66450397Sobrien 66550397Sobrien If XSIZE or YSIZE is zero, we do not know the amount of memory being 66650397Sobrien referenced (the reference was BLKmode), so make the most pessimistic 66750397Sobrien assumptions. 66850397Sobrien 66950397Sobrien If XSIZE or YSIZE is negative, we may access memory outside the object 67050397Sobrien being referenced as a side effect. This can happen when using AND to 67150397Sobrien align memory references, as is done on the Alpha. 67250397Sobrien 67350397Sobrien Nice to notice that varying addresses cannot conflict with fp if no 67450397Sobrien local variables had their addresses taken, but that's too hard now. */ 67550397Sobrien 67650397Sobrien 67750397Sobrienstatic int 67850397Sobrienmemrefs_conflict_p (xsize, x, ysize, y, c) 67950397Sobrien register rtx x, y; 68050397Sobrien int xsize, ysize; 68150397Sobrien HOST_WIDE_INT c; 68250397Sobrien{ 68350397Sobrien if (GET_CODE (x) == HIGH) 68450397Sobrien x = XEXP (x, 0); 68550397Sobrien else if (GET_CODE (x) == LO_SUM) 68650397Sobrien x = XEXP (x, 1); 68750397Sobrien else 68850397Sobrien x = canon_rtx (x); 68950397Sobrien if (GET_CODE (y) == HIGH) 69050397Sobrien y = XEXP (y, 0); 69150397Sobrien else if (GET_CODE (y) == LO_SUM) 69250397Sobrien y = XEXP (y, 1); 69350397Sobrien else 69450397Sobrien y = canon_rtx (y); 69550397Sobrien 69650397Sobrien if (rtx_equal_for_memref_p (x, y)) 69750397Sobrien { 69850397Sobrien if (xsize <= 0 || ysize <= 0) 69950397Sobrien return 1; 70050397Sobrien if (c >= 0 && xsize > c) 70150397Sobrien return 1; 70250397Sobrien if (c < 0 && ysize+c > 0) 70350397Sobrien return 1; 70450397Sobrien return 0; 70550397Sobrien } 70650397Sobrien 70750397Sobrien /* This code used to check for conflicts involving stack references and 70850397Sobrien globals but the base address alias code now handles these cases. */ 70950397Sobrien 71050397Sobrien if (GET_CODE (x) == PLUS) 71150397Sobrien { 71250397Sobrien /* The fact that X is canonicalized means that this 71350397Sobrien PLUS rtx is canonicalized. */ 71450397Sobrien rtx x0 = XEXP (x, 0); 71550397Sobrien rtx x1 = XEXP (x, 1); 71650397Sobrien 71750397Sobrien if (GET_CODE (y) == PLUS) 71850397Sobrien { 71950397Sobrien /* The fact that Y is canonicalized means that this 72050397Sobrien PLUS rtx is canonicalized. */ 72150397Sobrien rtx y0 = XEXP (y, 0); 72250397Sobrien rtx y1 = XEXP (y, 1); 72350397Sobrien 72450397Sobrien if (rtx_equal_for_memref_p (x1, y1)) 72550397Sobrien return memrefs_conflict_p (xsize, x0, ysize, y0, c); 72650397Sobrien if (rtx_equal_for_memref_p (x0, y0)) 72750397Sobrien return memrefs_conflict_p (xsize, x1, ysize, y1, c); 72850397Sobrien if (GET_CODE (x1) == CONST_INT) 72950397Sobrien if (GET_CODE (y1) == CONST_INT) 73050397Sobrien return memrefs_conflict_p (xsize, x0, ysize, y0, 73150397Sobrien c - INTVAL (x1) + INTVAL (y1)); 73250397Sobrien else 73350397Sobrien return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1)); 73450397Sobrien else if (GET_CODE (y1) == CONST_INT) 73550397Sobrien return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1)); 73650397Sobrien 73750397Sobrien return 1; 73850397Sobrien } 73950397Sobrien else if (GET_CODE (x1) == CONST_INT) 74050397Sobrien return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1)); 74150397Sobrien } 74250397Sobrien else if (GET_CODE (y) == PLUS) 74350397Sobrien { 74450397Sobrien /* The fact that Y is canonicalized means that this 74550397Sobrien PLUS rtx is canonicalized. */ 74650397Sobrien rtx y0 = XEXP (y, 0); 74750397Sobrien rtx y1 = XEXP (y, 1); 74850397Sobrien 74950397Sobrien if (GET_CODE (y1) == CONST_INT) 75050397Sobrien return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1)); 75150397Sobrien else 75250397Sobrien return 1; 75350397Sobrien } 75450397Sobrien 75550397Sobrien if (GET_CODE (x) == GET_CODE (y)) 75650397Sobrien switch (GET_CODE (x)) 75750397Sobrien { 75850397Sobrien case MULT: 75950397Sobrien { 76050397Sobrien /* Handle cases where we expect the second operands to be the 76150397Sobrien same, and check only whether the first operand would conflict 76250397Sobrien or not. */ 76350397Sobrien rtx x0, y0; 76450397Sobrien rtx x1 = canon_rtx (XEXP (x, 1)); 76550397Sobrien rtx y1 = canon_rtx (XEXP (y, 1)); 76650397Sobrien if (! rtx_equal_for_memref_p (x1, y1)) 76750397Sobrien return 1; 76850397Sobrien x0 = canon_rtx (XEXP (x, 0)); 76950397Sobrien y0 = canon_rtx (XEXP (y, 0)); 77050397Sobrien if (rtx_equal_for_memref_p (x0, y0)) 77150397Sobrien return (xsize == 0 || ysize == 0 77250397Sobrien || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); 77350397Sobrien 77450397Sobrien /* Can't properly adjust our sizes. */ 77550397Sobrien if (GET_CODE (x1) != CONST_INT) 77650397Sobrien return 1; 77750397Sobrien xsize /= INTVAL (x1); 77850397Sobrien ysize /= INTVAL (x1); 77950397Sobrien c /= INTVAL (x1); 78050397Sobrien return memrefs_conflict_p (xsize, x0, ysize, y0, c); 78150397Sobrien } 78250397Sobrien 78350397Sobrien case REG: 78450397Sobrien /* Are these registers known not to be equal? */ 78550397Sobrien if (alias_invariant) 78650397Sobrien { 78750397Sobrien int r_x = REGNO (x), r_y = REGNO (y); 78850397Sobrien rtx i_x, i_y; /* invariant relationships of X and Y */ 78950397Sobrien 79050397Sobrien i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x]; 79150397Sobrien i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y]; 79250397Sobrien 79350397Sobrien if (i_x == 0 && i_y == 0) 79450397Sobrien break; 79550397Sobrien 79650397Sobrien if (! memrefs_conflict_p (xsize, i_x ? i_x : x, 79750397Sobrien ysize, i_y ? i_y : y, c)) 79850397Sobrien return 0; 79950397Sobrien } 80050397Sobrien break; 80150397Sobrien 80250397Sobrien default: 80350397Sobrien break; 80450397Sobrien } 80550397Sobrien 80650397Sobrien /* Treat an access through an AND (e.g. a subword access on an Alpha) 80750397Sobrien as an access with indeterminate size. 80850397Sobrien ??? Could instead convert an n byte reference at (and x y) to an 80950397Sobrien n-y byte reference at (plus x y). */ 81050397Sobrien if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT) 81150397Sobrien return memrefs_conflict_p (-1, XEXP (x, 0), ysize, y, c); 81250397Sobrien if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT) 81350397Sobrien { 81450397Sobrien /* XXX: If we are indexing far enough into the array/structure, we 81550397Sobrien may yet be able to determine that we can not overlap. But we 81650397Sobrien also need to that we are far enough from the end not to overlap 81750397Sobrien a following reference, so we do nothing for now. */ 81850397Sobrien return memrefs_conflict_p (xsize, x, -1, XEXP (y, 0), c); 81950397Sobrien } 82050397Sobrien 82150397Sobrien if (CONSTANT_P (x)) 82250397Sobrien { 82350397Sobrien if (GET_CODE (x) == CONST_INT && GET_CODE (y) == CONST_INT) 82450397Sobrien { 82550397Sobrien c += (INTVAL (y) - INTVAL (x)); 82650397Sobrien return (xsize <= 0 || ysize <= 0 82750397Sobrien || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)); 82850397Sobrien } 82950397Sobrien 83050397Sobrien if (GET_CODE (x) == CONST) 83150397Sobrien { 83250397Sobrien if (GET_CODE (y) == CONST) 83350397Sobrien return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 83450397Sobrien ysize, canon_rtx (XEXP (y, 0)), c); 83550397Sobrien else 83650397Sobrien return memrefs_conflict_p (xsize, canon_rtx (XEXP (x, 0)), 83750397Sobrien ysize, y, c); 83850397Sobrien } 83950397Sobrien if (GET_CODE (y) == CONST) 84050397Sobrien return memrefs_conflict_p (xsize, x, ysize, 84150397Sobrien canon_rtx (XEXP (y, 0)), c); 84250397Sobrien 84350397Sobrien if (CONSTANT_P (y)) 84450397Sobrien return (xsize < 0 || ysize < 0 84550397Sobrien || (rtx_equal_for_memref_p (x, y) 84650397Sobrien && (xsize == 0 || ysize == 0 84750397Sobrien || (c >= 0 && xsize > c) || (c < 0 && ysize+c > 0)))); 84850397Sobrien 84950397Sobrien return 1; 85050397Sobrien } 85150397Sobrien return 1; 85250397Sobrien} 85350397Sobrien 85450397Sobrien/* Functions to compute memory dependencies. 85550397Sobrien 85650397Sobrien Since we process the insns in execution order, we can build tables 85750397Sobrien to keep track of what registers are fixed (and not aliased), what registers 85850397Sobrien are varying in known ways, and what registers are varying in unknown 85950397Sobrien ways. 86050397Sobrien 86150397Sobrien If both memory references are volatile, then there must always be a 86250397Sobrien dependence between the two references, since their order can not be 86350397Sobrien changed. A volatile and non-volatile reference can be interchanged 86450397Sobrien though. 86550397Sobrien 86650397Sobrien A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never 86750397Sobrien conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must 86850397Sobrien allow QImode aliasing because the ANSI C standard allows character 86950397Sobrien pointers to alias anything. We are assuming that characters are 87050397Sobrien always QImode here. We also must allow AND addresses, because they may 87150397Sobrien generate accesses outside the object being referenced. This is used to 87250397Sobrien generate aligned addresses from unaligned addresses, for instance, the 87350397Sobrien alpha storeqi_unaligned pattern. */ 87450397Sobrien 87550397Sobrien/* Read dependence: X is read after read in MEM takes place. There can 87650397Sobrien only be a dependence here if both reads are volatile. */ 87750397Sobrien 87850397Sobrienint 87950397Sobrienread_dependence (mem, x) 88050397Sobrien rtx mem; 88150397Sobrien rtx x; 88250397Sobrien{ 88350397Sobrien return MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem); 88450397Sobrien} 88550397Sobrien 88650397Sobrien/* True dependence: X is read after store in MEM takes place. */ 88750397Sobrien 88850397Sobrienint 88950397Sobrientrue_dependence (mem, mem_mode, x, varies) 89050397Sobrien rtx mem; 89150397Sobrien enum machine_mode mem_mode; 89250397Sobrien rtx x; 89350397Sobrien int (*varies) PROTO((rtx)); 89450397Sobrien{ 89550397Sobrien register rtx x_addr, mem_addr; 89650397Sobrien 89750397Sobrien if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 89850397Sobrien return 1; 89950397Sobrien 90050397Sobrien if (DIFFERENT_ALIAS_SETS_P (x, mem)) 90150397Sobrien return 0; 90250397Sobrien 90350397Sobrien /* If X is an unchanging read, then it can't possibly conflict with any 90450397Sobrien non-unchanging store. It may conflict with an unchanging write though, 90550397Sobrien because there may be a single store to this address to initialize it. 90650397Sobrien Just fall through to the code below to resolve the case where we have 90750397Sobrien both an unchanging read and an unchanging write. This won't handle all 90850397Sobrien cases optimally, but the possible performance loss should be 90950397Sobrien negligible. */ 91050397Sobrien if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem)) 91150397Sobrien return 0; 91250397Sobrien 91350397Sobrien if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0))) 91450397Sobrien return 0; 91550397Sobrien 91650397Sobrien x_addr = canon_rtx (XEXP (x, 0)); 91750397Sobrien mem_addr = canon_rtx (XEXP (mem, 0)); 91850397Sobrien 91950397Sobrien if (mem_mode == VOIDmode) 92050397Sobrien mem_mode = GET_MODE (mem); 92150397Sobrien 92250397Sobrien if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr, 92350397Sobrien SIZE_FOR_MODE (x), x_addr, 0)) 92450397Sobrien return 0; 92550397Sobrien 92650397Sobrien /* If both references are struct references, or both are not, nothing 92750397Sobrien is known about aliasing. 92850397Sobrien 92950397Sobrien If either reference is QImode or BLKmode, ANSI C permits aliasing. 93050397Sobrien 93150397Sobrien If both addresses are constant, or both are not, nothing is known 93250397Sobrien about aliasing. */ 93350397Sobrien if (MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (mem) 93450397Sobrien || mem_mode == QImode || mem_mode == BLKmode 93550397Sobrien || GET_MODE (x) == QImode || GET_MODE (x) == BLKmode 93650397Sobrien || GET_CODE (x_addr) == AND || GET_CODE (mem_addr) == AND 93750397Sobrien || varies (x_addr) == varies (mem_addr)) 93850397Sobrien return 1; 93950397Sobrien 94050397Sobrien /* One memory reference is to a constant address, one is not. 94150397Sobrien One is to a structure, the other is not. 94250397Sobrien 94350397Sobrien If either memory reference is a variable structure the other is a 94450397Sobrien fixed scalar and there is no aliasing. */ 94550397Sobrien 94650397Sobrien /* Disabled by default for egcs 1.1.x as alias analysis isn't good 94750397Sobrien enough yet to discover all cases where this doesn't apply. */ 94850397Sobrien if (flag_structure_noalias) 94950397Sobrien { 95050397Sobrien if ((MEM_IN_STRUCT_P (mem) && varies (mem_addr)) 95150397Sobrien || (MEM_IN_STRUCT_P (x) && varies (x_addr))) 95250397Sobrien return 0; 95350397Sobrien } 95450397Sobrien 95550397Sobrien return 1; 95650397Sobrien} 95750397Sobrien 95850397Sobrien/* Anti dependence: X is written after read in MEM takes place. */ 95950397Sobrien 96050397Sobrienint 96150397Sobrienanti_dependence (mem, x) 96250397Sobrien rtx mem; 96350397Sobrien rtx x; 96450397Sobrien{ 96550397Sobrien rtx x_addr, mem_addr; 96650397Sobrien 96750397Sobrien if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 96850397Sobrien return 1; 96950397Sobrien 97050397Sobrien /* If MEM is an unchanging read, then it can't possibly conflict with 97150397Sobrien the store to X, because there is at most one store to MEM, and it must 97250397Sobrien have occurred somewhere before MEM. */ 97350397Sobrien if (RTX_UNCHANGING_P (mem)) 97450397Sobrien return 0; 97550397Sobrien 97650397Sobrien if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0))) 97750397Sobrien return 0; 97850397Sobrien 97950397Sobrien x = canon_rtx (x); 98050397Sobrien mem = canon_rtx (mem); 98150397Sobrien 98250397Sobrien if (DIFFERENT_ALIAS_SETS_P (x, mem)) 98350397Sobrien return 0; 98450397Sobrien 98550397Sobrien x_addr = XEXP (x, 0); 98650397Sobrien mem_addr = XEXP (mem, 0); 98750397Sobrien 98850397Sobrien return (memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr, 98950397Sobrien SIZE_FOR_MODE (x), x_addr, 0) 99050397Sobrien && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem) 99150397Sobrien && GET_MODE (mem) != QImode 99250397Sobrien && GET_CODE (mem_addr) != AND 99350397Sobrien && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x)) 99450397Sobrien && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x) 99550397Sobrien && GET_MODE (x) != QImode 99650397Sobrien && GET_CODE (x_addr) != AND 99750397Sobrien && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))); 99850397Sobrien} 99950397Sobrien 100050397Sobrien/* Output dependence: X is written after store in MEM takes place. */ 100150397Sobrien 100250397Sobrienint 100350397Sobrienoutput_dependence (mem, x) 100450397Sobrien register rtx mem; 100550397Sobrien register rtx x; 100650397Sobrien{ 100750397Sobrien if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem)) 100850397Sobrien return 1; 100950397Sobrien 101050397Sobrien if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0))) 101150397Sobrien return 0; 101250397Sobrien 101350397Sobrien x = canon_rtx (x); 101450397Sobrien mem = canon_rtx (mem); 101550397Sobrien 101650397Sobrien if (DIFFERENT_ALIAS_SETS_P (x, mem)) 101750397Sobrien return 0; 101850397Sobrien 101950397Sobrien return (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0), 102050397Sobrien SIZE_FOR_MODE (x), XEXP (x, 0), 0) 102150397Sobrien && ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem) 102250397Sobrien && GET_MODE (mem) != QImode 102350397Sobrien && GET_CODE (XEXP (mem, 0)) != AND 102450397Sobrien && ! MEM_IN_STRUCT_P (x) && ! rtx_addr_varies_p (x)) 102550397Sobrien && ! (MEM_IN_STRUCT_P (x) && rtx_addr_varies_p (x) 102650397Sobrien && GET_MODE (x) != QImode 102750397Sobrien && GET_CODE (XEXP (x, 0)) != AND 102850397Sobrien && ! MEM_IN_STRUCT_P (mem) && ! rtx_addr_varies_p (mem))); 102950397Sobrien} 103050397Sobrien 103150397Sobrien 103250397Sobrienstatic HARD_REG_SET argument_registers; 103350397Sobrien 103450397Sobrienvoid 103550397Sobrieninit_alias_once () 103650397Sobrien{ 103750397Sobrien register int i; 103850397Sobrien 103950397Sobrien#ifndef OUTGOING_REGNO 104050397Sobrien#define OUTGOING_REGNO(N) N 104150397Sobrien#endif 104250397Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 104350397Sobrien /* Check whether this register can hold an incoming pointer 104450397Sobrien argument. FUNCTION_ARG_REGNO_P tests outgoing register 104550397Sobrien numbers, so translate if necessary due to register windows. */ 104650397Sobrien if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i)) 104750397Sobrien && HARD_REGNO_MODE_OK (i, Pmode)) 104850397Sobrien SET_HARD_REG_BIT (argument_registers, i); 104950397Sobrien} 105050397Sobrien 105150397Sobrienvoid 105250397Sobrieninit_alias_analysis () 105350397Sobrien{ 105450397Sobrien int maxreg = max_reg_num (); 105550397Sobrien int changed, pass; 105650397Sobrien register int i; 105750397Sobrien register rtx insn; 105850397Sobrien 105950397Sobrien reg_known_value_size = maxreg; 106050397Sobrien 106150397Sobrien reg_known_value 106250397Sobrien = (rtx *) oballoc ((maxreg - FIRST_PSEUDO_REGISTER) * sizeof (rtx)) 106350397Sobrien - FIRST_PSEUDO_REGISTER; 106450397Sobrien reg_known_equiv_p = 106550397Sobrien oballoc (maxreg - FIRST_PSEUDO_REGISTER) - FIRST_PSEUDO_REGISTER; 106650397Sobrien bzero ((char *) (reg_known_value + FIRST_PSEUDO_REGISTER), 106750397Sobrien (maxreg-FIRST_PSEUDO_REGISTER) * sizeof (rtx)); 106850397Sobrien bzero (reg_known_equiv_p + FIRST_PSEUDO_REGISTER, 106950397Sobrien (maxreg - FIRST_PSEUDO_REGISTER) * sizeof (char)); 107050397Sobrien 107150397Sobrien /* Overallocate reg_base_value to allow some growth during loop 107250397Sobrien optimization. Loop unrolling can create a large number of 107350397Sobrien registers. */ 107450397Sobrien reg_base_value_size = maxreg * 2; 107550397Sobrien reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx)); 107650397Sobrien new_reg_base_value = (rtx *)alloca (reg_base_value_size * sizeof (rtx)); 107750397Sobrien reg_seen = (char *)alloca (reg_base_value_size); 107850397Sobrien bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx)); 107950397Sobrien if (! reload_completed && flag_unroll_loops) 108050397Sobrien { 108150397Sobrien alias_invariant = (rtx *)xrealloc (alias_invariant, 108250397Sobrien reg_base_value_size * sizeof (rtx)); 108350397Sobrien bzero ((char *)alias_invariant, reg_base_value_size * sizeof (rtx)); 108450397Sobrien } 108550397Sobrien 108650397Sobrien 108750397Sobrien /* The basic idea is that each pass through this loop will use the 108850397Sobrien "constant" information from the previous pass to propagate alias 108950397Sobrien information through another level of assignments. 109050397Sobrien 109150397Sobrien This could get expensive if the assignment chains are long. Maybe 109250397Sobrien we should throttle the number of iterations, possibly based on 109350397Sobrien the optimization level or flag_expensive_optimizations. 109450397Sobrien 109550397Sobrien We could propagate more information in the first pass by making use 109650397Sobrien of REG_N_SETS to determine immediately that the alias information 109750397Sobrien for a pseudo is "constant". 109850397Sobrien 109950397Sobrien A program with an uninitialized variable can cause an infinite loop 110050397Sobrien here. Instead of doing a full dataflow analysis to detect such problems 110150397Sobrien we just cap the number of iterations for the loop. 110250397Sobrien 110350397Sobrien The state of the arrays for the set chain in question does not matter 110450397Sobrien since the program has undefined behavior. */ 110550397Sobrien 110650397Sobrien pass = 0; 110750397Sobrien do 110850397Sobrien { 110950397Sobrien /* Assume nothing will change this iteration of the loop. */ 111050397Sobrien changed = 0; 111150397Sobrien 111250397Sobrien /* We want to assign the same IDs each iteration of this loop, so 111350397Sobrien start counting from zero each iteration of the loop. */ 111450397Sobrien unique_id = 0; 111550397Sobrien 111650397Sobrien /* We're at the start of the funtion each iteration through the 111750397Sobrien loop, so we're copying arguments. */ 111850397Sobrien copying_arguments = 1; 111950397Sobrien 112050397Sobrien /* Wipe the potential alias information clean for this pass. */ 112150397Sobrien bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx)); 112250397Sobrien 112350397Sobrien /* Wipe the reg_seen array clean. */ 112450397Sobrien bzero ((char *) reg_seen, reg_base_value_size); 112550397Sobrien 112650397Sobrien /* Mark all hard registers which may contain an address. 112750397Sobrien The stack, frame and argument pointers may contain an address. 112850397Sobrien An argument register which can hold a Pmode value may contain 112950397Sobrien an address even if it is not in BASE_REGS. 113050397Sobrien 113150397Sobrien The address expression is VOIDmode for an argument and 113250397Sobrien Pmode for other registers. */ 113350397Sobrien 113450397Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 113550397Sobrien if (TEST_HARD_REG_BIT (argument_registers, i)) 113650397Sobrien new_reg_base_value[i] = gen_rtx_ADDRESS (VOIDmode, 113750397Sobrien gen_rtx_REG (Pmode, i)); 113850397Sobrien 113950397Sobrien new_reg_base_value[STACK_POINTER_REGNUM] 114050397Sobrien = gen_rtx_ADDRESS (Pmode, stack_pointer_rtx); 114150397Sobrien new_reg_base_value[ARG_POINTER_REGNUM] 114250397Sobrien = gen_rtx_ADDRESS (Pmode, arg_pointer_rtx); 114350397Sobrien new_reg_base_value[FRAME_POINTER_REGNUM] 114450397Sobrien = gen_rtx_ADDRESS (Pmode, frame_pointer_rtx); 114550397Sobrien#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM 114650397Sobrien new_reg_base_value[HARD_FRAME_POINTER_REGNUM] 114750397Sobrien = gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx); 114850397Sobrien#endif 114950397Sobrien if (struct_value_incoming_rtx 115050397Sobrien && GET_CODE (struct_value_incoming_rtx) == REG) 115150397Sobrien new_reg_base_value[REGNO (struct_value_incoming_rtx)] 115250397Sobrien = gen_rtx_ADDRESS (Pmode, struct_value_incoming_rtx); 115350397Sobrien 115450397Sobrien if (static_chain_rtx 115550397Sobrien && GET_CODE (static_chain_rtx) == REG) 115650397Sobrien new_reg_base_value[REGNO (static_chain_rtx)] 115750397Sobrien = gen_rtx_ADDRESS (Pmode, static_chain_rtx); 115850397Sobrien 115950397Sobrien /* Walk the insns adding values to the new_reg_base_value array. */ 116050397Sobrien for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 116150397Sobrien { 116250397Sobrien if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') 116350397Sobrien { 116450397Sobrien rtx note, set; 116550397Sobrien /* If this insn has a noalias note, process it, Otherwise, 116650397Sobrien scan for sets. A simple set will have no side effects 116750397Sobrien which could change the base value of any other register. */ 116850397Sobrien 116950397Sobrien if (GET_CODE (PATTERN (insn)) == SET 117050397Sobrien && (find_reg_note (insn, REG_NOALIAS, NULL_RTX))) 117150397Sobrien record_set (SET_DEST (PATTERN (insn)), NULL_RTX); 117250397Sobrien else 117350397Sobrien note_stores (PATTERN (insn), record_set); 117450397Sobrien 117550397Sobrien set = single_set (insn); 117650397Sobrien 117750397Sobrien if (set != 0 117850397Sobrien && GET_CODE (SET_DEST (set)) == REG 117950397Sobrien && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER 118050397Sobrien && (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0 118150397Sobrien && REG_N_SETS (REGNO (SET_DEST (set))) == 1) 118250397Sobrien || (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0) 118350397Sobrien && GET_CODE (XEXP (note, 0)) != EXPR_LIST 118450397Sobrien && ! reg_overlap_mentioned_p (SET_DEST (set), XEXP (note, 0))) 118550397Sobrien { 118650397Sobrien int regno = REGNO (SET_DEST (set)); 118750397Sobrien reg_known_value[regno] = XEXP (note, 0); 118850397Sobrien reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV; 118950397Sobrien } 119050397Sobrien } 119150397Sobrien else if (GET_CODE (insn) == NOTE 119250397Sobrien && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG) 119350397Sobrien copying_arguments = 0; 119450397Sobrien } 119550397Sobrien 119650397Sobrien /* Now propagate values from new_reg_base_value to reg_base_value. */ 119750397Sobrien for (i = 0; i < reg_base_value_size; i++) 119850397Sobrien { 119950397Sobrien if (new_reg_base_value[i] 120050397Sobrien && new_reg_base_value[i] != reg_base_value[i] 120150397Sobrien && ! rtx_equal_p (new_reg_base_value[i], reg_base_value[i])) 120250397Sobrien { 120350397Sobrien reg_base_value[i] = new_reg_base_value[i]; 120450397Sobrien changed = 1; 120550397Sobrien } 120650397Sobrien } 120750397Sobrien } 120850397Sobrien while (changed && ++pass < MAX_ALIAS_LOOP_PASSES); 120950397Sobrien 121050397Sobrien /* Fill in the remaining entries. */ 121150397Sobrien for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++) 121250397Sobrien if (reg_known_value[i] == 0) 121350397Sobrien reg_known_value[i] = regno_reg_rtx[i]; 121450397Sobrien 121550397Sobrien /* Simplify the reg_base_value array so that no register refers to 121650397Sobrien another register, except to special registers indirectly through 121750397Sobrien ADDRESS expressions. 121850397Sobrien 121950397Sobrien In theory this loop can take as long as O(registers^2), but unless 122050397Sobrien there are very long dependency chains it will run in close to linear 122150397Sobrien time. 122250397Sobrien 122350397Sobrien This loop may not be needed any longer now that the main loop does 122450397Sobrien a better job at propagating alias information. */ 122550397Sobrien pass = 0; 122650397Sobrien do 122750397Sobrien { 122850397Sobrien changed = 0; 122950397Sobrien pass++; 123050397Sobrien for (i = 0; i < reg_base_value_size; i++) 123150397Sobrien { 123250397Sobrien rtx base = reg_base_value[i]; 123350397Sobrien if (base && GET_CODE (base) == REG) 123450397Sobrien { 123550397Sobrien int base_regno = REGNO (base); 123650397Sobrien if (base_regno == i) /* register set from itself */ 123750397Sobrien reg_base_value[i] = 0; 123850397Sobrien else 123950397Sobrien reg_base_value[i] = reg_base_value[base_regno]; 124050397Sobrien changed = 1; 124150397Sobrien } 124250397Sobrien } 124350397Sobrien } 124450397Sobrien while (changed && pass < MAX_ALIAS_LOOP_PASSES); 124550397Sobrien 124650397Sobrien new_reg_base_value = 0; 124750397Sobrien reg_seen = 0; 124850397Sobrien} 124950397Sobrien 125050397Sobrienvoid 125150397Sobrienend_alias_analysis () 125250397Sobrien{ 125350397Sobrien reg_known_value = 0; 125450397Sobrien reg_base_value = 0; 125550397Sobrien reg_base_value_size = 0; 125650397Sobrien if (alias_invariant) 125750397Sobrien { 125850397Sobrien free ((char *)alias_invariant); 125950397Sobrien alias_invariant = 0; 126050397Sobrien } 126150397Sobrien} 1262