190075Sobrien/* Common subexpression elimination library for GNU compiler. 290075Sobrien Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3169689Skan 1999, 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc. 490075Sobrien 590075SobrienThis file is part of GCC. 690075Sobrien 790075SobrienGCC is free software; you can redistribute it and/or modify it under 890075Sobrienthe terms of the GNU General Public License as published by the Free 990075SobrienSoftware Foundation; either version 2, or (at your option) any later 1090075Sobrienversion. 1190075Sobrien 1290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1590075Sobrienfor more details. 1690075Sobrien 1790075SobrienYou should have received a copy of the GNU General Public License 1890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 2190075Sobrien 2290075Sobrien#include "config.h" 2390075Sobrien#include "system.h" 24132718Skan#include "coretypes.h" 25132718Skan#include "tm.h" 2690075Sobrien 2790075Sobrien#include "rtl.h" 2890075Sobrien#include "tm_p.h" 2990075Sobrien#include "regs.h" 3090075Sobrien#include "hard-reg-set.h" 3190075Sobrien#include "flags.h" 3290075Sobrien#include "real.h" 3390075Sobrien#include "insn-config.h" 3490075Sobrien#include "recog.h" 3590075Sobrien#include "function.h" 36169689Skan#include "emit-rtl.h" 3790075Sobrien#include "toplev.h" 3890075Sobrien#include "output.h" 3990075Sobrien#include "ggc.h" 4090075Sobrien#include "hashtab.h" 4190075Sobrien#include "cselib.h" 42132718Skan#include "params.h" 43132718Skan#include "alloc-pool.h" 44169689Skan#include "target.h" 4590075Sobrien 46169689Skanstatic bool cselib_record_memory; 47132718Skanstatic int entry_and_rtx_equal_p (const void *, const void *); 48132718Skanstatic hashval_t get_value_hash (const void *); 49132718Skanstatic struct elt_list *new_elt_list (struct elt_list *, cselib_val *); 50132718Skanstatic struct elt_loc_list *new_elt_loc_list (struct elt_loc_list *, rtx); 51132718Skanstatic void unchain_one_value (cselib_val *); 52132718Skanstatic void unchain_one_elt_list (struct elt_list **); 53132718Skanstatic void unchain_one_elt_loc_list (struct elt_loc_list **); 54132718Skanstatic int discard_useless_locs (void **, void *); 55132718Skanstatic int discard_useless_values (void **, void *); 56132718Skanstatic void remove_useless_values (void); 57132718Skanstatic rtx wrap_constant (enum machine_mode, rtx); 58169689Skanstatic unsigned int cselib_hash_rtx (rtx, int); 59132718Skanstatic cselib_val *new_cselib_val (unsigned int, enum machine_mode); 60132718Skanstatic void add_mem_for_addr (cselib_val *, cselib_val *, rtx); 61132718Skanstatic cselib_val *cselib_lookup_mem (rtx, int); 62132718Skanstatic void cselib_invalidate_regno (unsigned int, enum machine_mode); 63132718Skanstatic void cselib_invalidate_mem (rtx); 64132718Skanstatic void cselib_record_set (rtx, cselib_val *, cselib_val *); 65132718Skanstatic void cselib_record_sets (rtx); 6690075Sobrien 6790075Sobrien/* There are three ways in which cselib can look up an rtx: 6890075Sobrien - for a REG, the reg_values table (which is indexed by regno) is used 6990075Sobrien - for a MEM, we recursively look up its address and then follow the 7090075Sobrien addr_list of that value 7190075Sobrien - for everything else, we compute a hash value and go through the hash 7290075Sobrien table. Since different rtx's can still have the same hash value, 7390075Sobrien this involves walking the table entries for a given value and comparing 7490075Sobrien the locations of the entries with the rtx we are looking up. */ 7590075Sobrien 7690075Sobrien/* A table that enables us to look up elts by their value. */ 77169689Skanstatic htab_t cselib_hash_table; 7890075Sobrien 7990075Sobrien/* This is a global so we don't have to pass this through every function. 8090075Sobrien It is used in new_elt_loc_list to set SETTING_INSN. */ 8190075Sobrienstatic rtx cselib_current_insn; 82117395Skanstatic bool cselib_current_insn_in_libcall; 8390075Sobrien 8490075Sobrien/* Every new unknown value gets a unique number. */ 8590075Sobrienstatic unsigned int next_unknown_value; 8690075Sobrien 8790075Sobrien/* The number of registers we had when the varrays were last resized. */ 8890075Sobrienstatic unsigned int cselib_nregs; 8990075Sobrien 9090075Sobrien/* Count values without known locations. Whenever this grows too big, we 9190075Sobrien remove these useless values from the table. */ 9290075Sobrienstatic int n_useless_values; 9390075Sobrien 9490075Sobrien/* Number of useless values before we remove them from the hash table. */ 9590075Sobrien#define MAX_USELESS_VALUES 32 9690075Sobrien 97132718Skan/* This table maps from register number to values. It does not 98132718Skan contain pointers to cselib_val structures, but rather elt_lists. 99132718Skan The purpose is to be able to refer to the same register in 100132718Skan different modes. The first element of the list defines the mode in 101132718Skan which the register was set; if the mode is unknown or the value is 102132718Skan no longer valid in that mode, ELT will be NULL for the first 103132718Skan element. */ 104169689Skanstatic struct elt_list **reg_values; 105169689Skanstatic unsigned int reg_values_size; 106169689Skan#define REG_VALUES(i) reg_values[i] 10790075Sobrien 108102780Skan/* The largest number of hard regs used by any entry added to the 109169689Skan REG_VALUES table. Cleared on each cselib_clear_table() invocation. */ 110102780Skanstatic unsigned int max_value_regs; 111102780Skan 11290075Sobrien/* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used 113169689Skan in cselib_clear_table() for fast emptying. */ 114169689Skanstatic unsigned int *used_regs; 115169689Skanstatic unsigned int n_used_regs; 11690075Sobrien 11790075Sobrien/* We pass this to cselib_invalidate_mem to invalidate all of 11890075Sobrien memory for a non-const call instruction. */ 119117395Skanstatic GTY(()) rtx callmem; 12090075Sobrien 12190075Sobrien/* Set by discard_useless_locs if it deleted the last location of any 12290075Sobrien value. */ 12390075Sobrienstatic int values_became_useless; 124132718Skan 125132718Skan/* Used as stop element of the containing_mem list so we can check 126132718Skan presence in the list by checking the next pointer. */ 127132718Skanstatic cselib_val dummy_val; 128132718Skan 129132718Skan/* Used to list all values that contain memory reference. 130132718Skan May or may not contain the useless values - the list is compacted 131132718Skan each time memory is invalidated. */ 132132718Skanstatic cselib_val *first_containing_mem = &dummy_val; 133132718Skanstatic alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool, value_pool; 13490075Sobrien 13590075Sobrien 13690075Sobrien/* Allocate a struct elt_list and fill in its two elements with the 13790075Sobrien arguments. */ 13890075Sobrien 139132718Skanstatic inline struct elt_list * 140132718Skannew_elt_list (struct elt_list *next, cselib_val *elt) 14190075Sobrien{ 142132718Skan struct elt_list *el; 143132718Skan el = pool_alloc (elt_list_pool); 14490075Sobrien el->next = next; 14590075Sobrien el->elt = elt; 14690075Sobrien return el; 14790075Sobrien} 14890075Sobrien 14990075Sobrien/* Allocate a struct elt_loc_list and fill in its two elements with the 15090075Sobrien arguments. */ 15190075Sobrien 152132718Skanstatic inline struct elt_loc_list * 153132718Skannew_elt_loc_list (struct elt_loc_list *next, rtx loc) 15490075Sobrien{ 155132718Skan struct elt_loc_list *el; 156132718Skan el = pool_alloc (elt_loc_list_pool); 15790075Sobrien el->next = next; 15890075Sobrien el->loc = loc; 15990075Sobrien el->setting_insn = cselib_current_insn; 160117395Skan el->in_libcall = cselib_current_insn_in_libcall; 16190075Sobrien return el; 16290075Sobrien} 16390075Sobrien 16490075Sobrien/* The elt_list at *PL is no longer needed. Unchain it and free its 16590075Sobrien storage. */ 16690075Sobrien 167132718Skanstatic inline void 168132718Skanunchain_one_elt_list (struct elt_list **pl) 16990075Sobrien{ 17090075Sobrien struct elt_list *l = *pl; 17190075Sobrien 17290075Sobrien *pl = l->next; 173132718Skan pool_free (elt_list_pool, l); 17490075Sobrien} 17590075Sobrien 17690075Sobrien/* Likewise for elt_loc_lists. */ 17790075Sobrien 17890075Sobrienstatic void 179132718Skanunchain_one_elt_loc_list (struct elt_loc_list **pl) 18090075Sobrien{ 18190075Sobrien struct elt_loc_list *l = *pl; 18290075Sobrien 18390075Sobrien *pl = l->next; 184132718Skan pool_free (elt_loc_list_pool, l); 18590075Sobrien} 18690075Sobrien 18790075Sobrien/* Likewise for cselib_vals. This also frees the addr_list associated with 18890075Sobrien V. */ 18990075Sobrien 19090075Sobrienstatic void 191132718Skanunchain_one_value (cselib_val *v) 19290075Sobrien{ 19390075Sobrien while (v->addr_list) 19490075Sobrien unchain_one_elt_list (&v->addr_list); 19590075Sobrien 196132718Skan pool_free (cselib_val_pool, v); 19790075Sobrien} 19890075Sobrien 19990075Sobrien/* Remove all entries from the hash table. Also used during 20090075Sobrien initialization. If CLEAR_ALL isn't set, then only clear the entries 20190075Sobrien which are known to have been used. */ 20290075Sobrien 203169689Skanvoid 204169689Skancselib_clear_table (void) 20590075Sobrien{ 20690075Sobrien unsigned int i; 20790075Sobrien 208169689Skan for (i = 0; i < n_used_regs; i++) 209169689Skan REG_VALUES (used_regs[i]) = 0; 21090075Sobrien 211102780Skan max_value_regs = 0; 212102780Skan 213169689Skan n_used_regs = 0; 21490075Sobrien 215169689Skan htab_empty (cselib_hash_table); 21690075Sobrien 21790075Sobrien n_useless_values = 0; 21890075Sobrien 21990075Sobrien next_unknown_value = 0; 220132718Skan 221132718Skan first_containing_mem = &dummy_val; 22290075Sobrien} 22390075Sobrien 22490075Sobrien/* The equality test for our hash table. The first argument ENTRY is a table 22590075Sobrien element (i.e. a cselib_val), while the second arg X is an rtx. We know 22690075Sobrien that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a 22790075Sobrien CONST of an appropriate mode. */ 22890075Sobrien 22990075Sobrienstatic int 230132718Skanentry_and_rtx_equal_p (const void *entry, const void *x_arg) 23190075Sobrien{ 23290075Sobrien struct elt_loc_list *l; 23390075Sobrien const cselib_val *v = (const cselib_val *) entry; 23490075Sobrien rtx x = (rtx) x_arg; 23590075Sobrien enum machine_mode mode = GET_MODE (x); 23690075Sobrien 237169689Skan gcc_assert (GET_CODE (x) != CONST_INT 238169689Skan && (mode != VOIDmode || GET_CODE (x) != CONST_DOUBLE)); 239169689Skan 24090075Sobrien if (mode != GET_MODE (v->u.val_rtx)) 24190075Sobrien return 0; 24290075Sobrien 24390075Sobrien /* Unwrap X if necessary. */ 24490075Sobrien if (GET_CODE (x) == CONST 24590075Sobrien && (GET_CODE (XEXP (x, 0)) == CONST_INT 24690075Sobrien || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE)) 24790075Sobrien x = XEXP (x, 0); 248132718Skan 24990075Sobrien /* We don't guarantee that distinct rtx's have different hash values, 25090075Sobrien so we need to do a comparison. */ 25190075Sobrien for (l = v->locs; l; l = l->next) 25290075Sobrien if (rtx_equal_for_cselib_p (l->loc, x)) 25390075Sobrien return 1; 25490075Sobrien 25590075Sobrien return 0; 25690075Sobrien} 25790075Sobrien 25890075Sobrien/* The hash function for our hash table. The value is always computed with 259169689Skan cselib_hash_rtx when adding an element; this function just extracts the 260169689Skan hash value from a cselib_val structure. */ 26190075Sobrien 262117395Skanstatic hashval_t 263132718Skanget_value_hash (const void *entry) 26490075Sobrien{ 26590075Sobrien const cselib_val *v = (const cselib_val *) entry; 26690075Sobrien return v->value; 26790075Sobrien} 26890075Sobrien 26990075Sobrien/* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we 27090075Sobrien only return true for values which point to a cselib_val whose value 27190075Sobrien element has been set to zero, which implies the cselib_val will be 27290075Sobrien removed. */ 27390075Sobrien 27490075Sobrienint 275132718Skanreferences_value_p (rtx x, int only_useless) 27690075Sobrien{ 27790075Sobrien enum rtx_code code = GET_CODE (x); 27890075Sobrien const char *fmt = GET_RTX_FORMAT (code); 27990075Sobrien int i, j; 28090075Sobrien 28190075Sobrien if (GET_CODE (x) == VALUE 28290075Sobrien && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0)) 28390075Sobrien return 1; 28490075Sobrien 28590075Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 28690075Sobrien { 28790075Sobrien if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless)) 28890075Sobrien return 1; 28990075Sobrien else if (fmt[i] == 'E') 29090075Sobrien for (j = 0; j < XVECLEN (x, i); j++) 29190075Sobrien if (references_value_p (XVECEXP (x, i, j), only_useless)) 29290075Sobrien return 1; 29390075Sobrien } 29490075Sobrien 29590075Sobrien return 0; 29690075Sobrien} 29790075Sobrien 29890075Sobrien/* For all locations found in X, delete locations that reference useless 29990075Sobrien values (i.e. values without any location). Called through 30090075Sobrien htab_traverse. */ 30190075Sobrien 30290075Sobrienstatic int 303132718Skandiscard_useless_locs (void **x, void *info ATTRIBUTE_UNUSED) 30490075Sobrien{ 30590075Sobrien cselib_val *v = (cselib_val *)*x; 30690075Sobrien struct elt_loc_list **p = &v->locs; 30790075Sobrien int had_locs = v->locs != 0; 30890075Sobrien 30990075Sobrien while (*p) 31090075Sobrien { 31190075Sobrien if (references_value_p ((*p)->loc, 1)) 31290075Sobrien unchain_one_elt_loc_list (p); 31390075Sobrien else 31490075Sobrien p = &(*p)->next; 31590075Sobrien } 31690075Sobrien 31790075Sobrien if (had_locs && v->locs == 0) 31890075Sobrien { 31990075Sobrien n_useless_values++; 32090075Sobrien values_became_useless = 1; 32190075Sobrien } 32290075Sobrien return 1; 32390075Sobrien} 32490075Sobrien 32590075Sobrien/* If X is a value with no locations, remove it from the hashtable. */ 32690075Sobrien 32790075Sobrienstatic int 328132718Skandiscard_useless_values (void **x, void *info ATTRIBUTE_UNUSED) 32990075Sobrien{ 33090075Sobrien cselib_val *v = (cselib_val *)*x; 33190075Sobrien 33290075Sobrien if (v->locs == 0) 33390075Sobrien { 334132718Skan CSELIB_VAL_PTR (v->u.val_rtx) = NULL; 335169689Skan htab_clear_slot (cselib_hash_table, x); 33690075Sobrien unchain_one_value (v); 33790075Sobrien n_useless_values--; 33890075Sobrien } 33990075Sobrien 34090075Sobrien return 1; 34190075Sobrien} 34290075Sobrien 34390075Sobrien/* Clean out useless values (i.e. those which no longer have locations 34490075Sobrien associated with them) from the hash table. */ 34590075Sobrien 34690075Sobrienstatic void 347132718Skanremove_useless_values (void) 34890075Sobrien{ 349132718Skan cselib_val **p, *v; 35090075Sobrien /* First pass: eliminate locations that reference the value. That in 35190075Sobrien turn can make more values useless. */ 35290075Sobrien do 35390075Sobrien { 35490075Sobrien values_became_useless = 0; 355169689Skan htab_traverse (cselib_hash_table, discard_useless_locs, 0); 35690075Sobrien } 35790075Sobrien while (values_became_useless); 35890075Sobrien 35990075Sobrien /* Second pass: actually remove the values. */ 360169689Skan 361132718Skan p = &first_containing_mem; 362132718Skan for (v = *p; v != &dummy_val; v = v->next_containing_mem) 363132718Skan if (v->locs) 364132718Skan { 365132718Skan *p = v; 366132718Skan p = &(*p)->next_containing_mem; 367132718Skan } 368132718Skan *p = &dummy_val; 369132718Skan 370169689Skan htab_traverse (cselib_hash_table, discard_useless_values, 0); 37190075Sobrien 372169689Skan gcc_assert (!n_useless_values); 37390075Sobrien} 37490075Sobrien 375132718Skan/* Return the mode in which a register was last set. If X is not a 376132718Skan register, return its mode. If the mode in which the register was 377132718Skan set is not known, or the value was already clobbered, return 378132718Skan VOIDmode. */ 379132718Skan 380132718Skanenum machine_mode 381132718Skancselib_reg_set_mode (rtx x) 382132718Skan{ 383169689Skan if (!REG_P (x)) 384132718Skan return GET_MODE (x); 385132718Skan 386132718Skan if (REG_VALUES (REGNO (x)) == NULL 387132718Skan || REG_VALUES (REGNO (x))->elt == NULL) 388132718Skan return VOIDmode; 389132718Skan 390132718Skan return GET_MODE (REG_VALUES (REGNO (x))->elt->u.val_rtx); 391132718Skan} 392132718Skan 39390075Sobrien/* Return nonzero if we can prove that X and Y contain the same value, taking 39490075Sobrien our gathered information into account. */ 39590075Sobrien 39690075Sobrienint 397132718Skanrtx_equal_for_cselib_p (rtx x, rtx y) 39890075Sobrien{ 39990075Sobrien enum rtx_code code; 40090075Sobrien const char *fmt; 40190075Sobrien int i; 402132718Skan 403169689Skan if (REG_P (x) || MEM_P (x)) 40490075Sobrien { 40590075Sobrien cselib_val *e = cselib_lookup (x, GET_MODE (x), 0); 40690075Sobrien 40790075Sobrien if (e) 40890075Sobrien x = e->u.val_rtx; 40990075Sobrien } 41090075Sobrien 411169689Skan if (REG_P (y) || MEM_P (y)) 41290075Sobrien { 41390075Sobrien cselib_val *e = cselib_lookup (y, GET_MODE (y), 0); 41490075Sobrien 41590075Sobrien if (e) 41690075Sobrien y = e->u.val_rtx; 41790075Sobrien } 41890075Sobrien 41990075Sobrien if (x == y) 42090075Sobrien return 1; 42190075Sobrien 42290075Sobrien if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE) 42390075Sobrien return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y); 42490075Sobrien 42590075Sobrien if (GET_CODE (x) == VALUE) 42690075Sobrien { 42790075Sobrien cselib_val *e = CSELIB_VAL_PTR (x); 42890075Sobrien struct elt_loc_list *l; 42990075Sobrien 43090075Sobrien for (l = e->locs; l; l = l->next) 43190075Sobrien { 43290075Sobrien rtx t = l->loc; 43390075Sobrien 43490075Sobrien /* Avoid infinite recursion. */ 435169689Skan if (REG_P (t) || MEM_P (t)) 43690075Sobrien continue; 43790075Sobrien else if (rtx_equal_for_cselib_p (t, y)) 43890075Sobrien return 1; 43990075Sobrien } 440132718Skan 44190075Sobrien return 0; 44290075Sobrien } 44390075Sobrien 44490075Sobrien if (GET_CODE (y) == VALUE) 44590075Sobrien { 44690075Sobrien cselib_val *e = CSELIB_VAL_PTR (y); 44790075Sobrien struct elt_loc_list *l; 44890075Sobrien 44990075Sobrien for (l = e->locs; l; l = l->next) 45090075Sobrien { 45190075Sobrien rtx t = l->loc; 45290075Sobrien 453169689Skan if (REG_P (t) || MEM_P (t)) 45490075Sobrien continue; 45590075Sobrien else if (rtx_equal_for_cselib_p (x, t)) 45690075Sobrien return 1; 45790075Sobrien } 458132718Skan 45990075Sobrien return 0; 46090075Sobrien } 46190075Sobrien 46290075Sobrien if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y)) 46390075Sobrien return 0; 46490075Sobrien 465169689Skan /* These won't be handled correctly by the code below. */ 466169689Skan switch (GET_CODE (x)) 467169689Skan { 468169689Skan case CONST_DOUBLE: 469169689Skan return 0; 470132718Skan 471169689Skan case LABEL_REF: 472169689Skan return XEXP (x, 0) == XEXP (y, 0); 473169689Skan 474169689Skan default: 475169689Skan break; 476169689Skan } 477169689Skan 47890075Sobrien code = GET_CODE (x); 47990075Sobrien fmt = GET_RTX_FORMAT (code); 48090075Sobrien 48190075Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 48290075Sobrien { 48390075Sobrien int j; 48490075Sobrien 48590075Sobrien switch (fmt[i]) 48690075Sobrien { 48790075Sobrien case 'w': 48890075Sobrien if (XWINT (x, i) != XWINT (y, i)) 48990075Sobrien return 0; 49090075Sobrien break; 49190075Sobrien 49290075Sobrien case 'n': 49390075Sobrien case 'i': 49490075Sobrien if (XINT (x, i) != XINT (y, i)) 49590075Sobrien return 0; 49690075Sobrien break; 49790075Sobrien 49890075Sobrien case 'V': 49990075Sobrien case 'E': 50090075Sobrien /* Two vectors must have the same length. */ 50190075Sobrien if (XVECLEN (x, i) != XVECLEN (y, i)) 50290075Sobrien return 0; 50390075Sobrien 50490075Sobrien /* And the corresponding elements must match. */ 50590075Sobrien for (j = 0; j < XVECLEN (x, i); j++) 50690075Sobrien if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j), 50790075Sobrien XVECEXP (y, i, j))) 50890075Sobrien return 0; 50990075Sobrien break; 51090075Sobrien 51190075Sobrien case 'e': 512169689Skan if (i == 1 513169689Skan && targetm.commutative_p (x, UNKNOWN) 514169689Skan && rtx_equal_for_cselib_p (XEXP (x, 1), XEXP (y, 0)) 515169689Skan && rtx_equal_for_cselib_p (XEXP (x, 0), XEXP (y, 1))) 516169689Skan return 1; 51790075Sobrien if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i))) 51890075Sobrien return 0; 51990075Sobrien break; 52090075Sobrien 52190075Sobrien case 'S': 52290075Sobrien case 's': 52390075Sobrien if (strcmp (XSTR (x, i), XSTR (y, i))) 52490075Sobrien return 0; 52590075Sobrien break; 52690075Sobrien 52790075Sobrien case 'u': 52890075Sobrien /* These are just backpointers, so they don't matter. */ 52990075Sobrien break; 53090075Sobrien 53190075Sobrien case '0': 53290075Sobrien case 't': 53390075Sobrien break; 53490075Sobrien 53590075Sobrien /* It is believed that rtx's at this level will never 53690075Sobrien contain anything but integers and other rtx's, 53790075Sobrien except for within LABEL_REFs and SYMBOL_REFs. */ 53890075Sobrien default: 539169689Skan gcc_unreachable (); 54090075Sobrien } 54190075Sobrien } 54290075Sobrien return 1; 54390075Sobrien} 54490075Sobrien 54590075Sobrien/* We need to pass down the mode of constants through the hash table 54690075Sobrien functions. For that purpose, wrap them in a CONST of the appropriate 54790075Sobrien mode. */ 54890075Sobrienstatic rtx 549132718Skanwrap_constant (enum machine_mode mode, rtx x) 55090075Sobrien{ 55190075Sobrien if (GET_CODE (x) != CONST_INT 55290075Sobrien && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode)) 55390075Sobrien return x; 554169689Skan gcc_assert (mode != VOIDmode); 55590075Sobrien return gen_rtx_CONST (mode, x); 55690075Sobrien} 55790075Sobrien 55890075Sobrien/* Hash an rtx. Return 0 if we couldn't hash the rtx. 55990075Sobrien For registers and memory locations, we look up their cselib_val structure 56090075Sobrien and return its VALUE element. 56190075Sobrien Possible reasons for return 0 are: the object is volatile, or we couldn't 56290075Sobrien find a register or memory location in the table and CREATE is zero. If 56390075Sobrien CREATE is nonzero, table elts are created for regs and mem. 564169689Skan N.B. this hash function returns the same hash value for RTXes that 565169689Skan differ only in the order of operands, thus it is suitable for comparisons 566169689Skan that take commutativity into account. 567169689Skan If we wanted to also support associative rules, we'd have to use a different 568169689Skan strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) . 569169689Skan We used to have a MODE argument for hashing for CONST_INTs, but that 570169689Skan didn't make sense, since it caused spurious hash differences between 571169689Skan (set (reg:SI 1) (const_int)) 572169689Skan (plus:SI (reg:SI 2) (reg:SI 1)) 573169689Skan and 574169689Skan (plus:SI (reg:SI 2) (const_int)) 575169689Skan If the mode is important in any context, it must be checked specifically 576169689Skan in a comparison anyway, since relying on hash differences is unsafe. */ 57790075Sobrien 57890075Sobrienstatic unsigned int 579169689Skancselib_hash_rtx (rtx x, int create) 58090075Sobrien{ 58190075Sobrien cselib_val *e; 58290075Sobrien int i, j; 58390075Sobrien enum rtx_code code; 58490075Sobrien const char *fmt; 58590075Sobrien unsigned int hash = 0; 58690075Sobrien 58790075Sobrien code = GET_CODE (x); 58890075Sobrien hash += (unsigned) code + (unsigned) GET_MODE (x); 58990075Sobrien 59090075Sobrien switch (code) 59190075Sobrien { 59290075Sobrien case MEM: 59390075Sobrien case REG: 59490075Sobrien e = cselib_lookup (x, GET_MODE (x), create); 59590075Sobrien if (! e) 59690075Sobrien return 0; 59790075Sobrien 59890075Sobrien return e->value; 59990075Sobrien 60090075Sobrien case CONST_INT: 601169689Skan hash += ((unsigned) CONST_INT << 7) + INTVAL (x); 60290075Sobrien return hash ? hash : (unsigned int) CONST_INT; 60390075Sobrien 60490075Sobrien case CONST_DOUBLE: 60590075Sobrien /* This is like the general case, except that it only counts 60690075Sobrien the integers representing the constant. */ 60790075Sobrien hash += (unsigned) code + (unsigned) GET_MODE (x); 60890075Sobrien if (GET_MODE (x) != VOIDmode) 609117395Skan hash += real_hash (CONST_DOUBLE_REAL_VALUE (x)); 61090075Sobrien else 61190075Sobrien hash += ((unsigned) CONST_DOUBLE_LOW (x) 61290075Sobrien + (unsigned) CONST_DOUBLE_HIGH (x)); 61390075Sobrien return hash ? hash : (unsigned int) CONST_DOUBLE; 61490075Sobrien 61596263Sobrien case CONST_VECTOR: 61696263Sobrien { 61796263Sobrien int units; 61896263Sobrien rtx elt; 61996263Sobrien 62096263Sobrien units = CONST_VECTOR_NUNITS (x); 62196263Sobrien 62296263Sobrien for (i = 0; i < units; ++i) 62396263Sobrien { 62496263Sobrien elt = CONST_VECTOR_ELT (x, i); 625169689Skan hash += cselib_hash_rtx (elt, 0); 62696263Sobrien } 62796263Sobrien 62896263Sobrien return hash; 62996263Sobrien } 63096263Sobrien 63190075Sobrien /* Assume there is only one rtx object for any given label. */ 63290075Sobrien case LABEL_REF: 633169689Skan /* We don't hash on the address of the CODE_LABEL to avoid bootstrap 634169689Skan differences and differences between each stage's debugging dumps. */ 635169689Skan hash += (((unsigned int) LABEL_REF << 7) 636169689Skan + CODE_LABEL_NUMBER (XEXP (x, 0))); 63790075Sobrien return hash ? hash : (unsigned int) LABEL_REF; 63890075Sobrien 63990075Sobrien case SYMBOL_REF: 640169689Skan { 641169689Skan /* Don't hash on the symbol's address to avoid bootstrap differences. 642169689Skan Different hash values may cause expressions to be recorded in 643169689Skan different orders and thus different registers to be used in the 644169689Skan final assembler. This also avoids differences in the dump files 645169689Skan between various stages. */ 646169689Skan unsigned int h = 0; 647169689Skan const unsigned char *p = (const unsigned char *) XSTR (x, 0); 64890075Sobrien 649169689Skan while (*p) 650169689Skan h += (h << 7) + *p++; /* ??? revisit */ 651169689Skan 652169689Skan hash += ((unsigned int) SYMBOL_REF << 7) + h; 653169689Skan return hash ? hash : (unsigned int) SYMBOL_REF; 654169689Skan } 655169689Skan 65690075Sobrien case PRE_DEC: 65790075Sobrien case PRE_INC: 65890075Sobrien case POST_DEC: 65990075Sobrien case POST_INC: 66090075Sobrien case POST_MODIFY: 66190075Sobrien case PRE_MODIFY: 66290075Sobrien case PC: 66390075Sobrien case CC0: 66490075Sobrien case CALL: 66590075Sobrien case UNSPEC_VOLATILE: 66690075Sobrien return 0; 66790075Sobrien 66890075Sobrien case ASM_OPERANDS: 66990075Sobrien if (MEM_VOLATILE_P (x)) 67090075Sobrien return 0; 67190075Sobrien 67290075Sobrien break; 673132718Skan 67490075Sobrien default: 67590075Sobrien break; 67690075Sobrien } 67790075Sobrien 67890075Sobrien i = GET_RTX_LENGTH (code) - 1; 67990075Sobrien fmt = GET_RTX_FORMAT (code); 68090075Sobrien for (; i >= 0; i--) 68190075Sobrien { 682169689Skan switch (fmt[i]) 68390075Sobrien { 684169689Skan case 'e': 68590075Sobrien { 686169689Skan rtx tem = XEXP (x, i); 687169689Skan unsigned int tem_hash = cselib_hash_rtx (tem, create); 688169689Skan 68990075Sobrien if (tem_hash == 0) 69090075Sobrien return 0; 691169689Skan 69290075Sobrien hash += tem_hash; 69390075Sobrien } 694169689Skan break; 695169689Skan case 'E': 696169689Skan for (j = 0; j < XVECLEN (x, i); j++) 697169689Skan { 698169689Skan unsigned int tem_hash 699169689Skan = cselib_hash_rtx (XVECEXP (x, i, j), create); 700169689Skan 701169689Skan if (tem_hash == 0) 702169689Skan return 0; 703169689Skan 704169689Skan hash += tem_hash; 705169689Skan } 706169689Skan break; 70790075Sobrien 708169689Skan case 's': 709169689Skan { 710169689Skan const unsigned char *p = (const unsigned char *) XSTR (x, i); 711169689Skan 712169689Skan if (p) 713169689Skan while (*p) 714169689Skan hash += *p++; 715169689Skan break; 716169689Skan } 717169689Skan 718169689Skan case 'i': 719169689Skan hash += XINT (x, i); 720169689Skan break; 721169689Skan 722169689Skan case '0': 723169689Skan case 't': 724169689Skan /* unused */ 725169689Skan break; 726169689Skan 727169689Skan default: 728169689Skan gcc_unreachable (); 72990075Sobrien } 73090075Sobrien } 73190075Sobrien 73290075Sobrien return hash ? hash : 1 + (unsigned int) GET_CODE (x); 73390075Sobrien} 73490075Sobrien 73590075Sobrien/* Create a new value structure for VALUE and initialize it. The mode of the 73690075Sobrien value is MODE. */ 73790075Sobrien 738132718Skanstatic inline cselib_val * 739132718Skannew_cselib_val (unsigned int value, enum machine_mode mode) 74090075Sobrien{ 741132718Skan cselib_val *e = pool_alloc (cselib_val_pool); 74290075Sobrien 743169689Skan gcc_assert (value); 74490075Sobrien 74590075Sobrien e->value = value; 746169689Skan /* We use an alloc pool to allocate this RTL construct because it 747169689Skan accounts for about 8% of the overall memory usage. We know 748169689Skan precisely when we can have VALUE RTXen (when cselib is active) 749169689Skan so we don't need to put them in garbage collected memory. 750169689Skan ??? Why should a VALUE be an RTX in the first place? */ 751132718Skan e->u.val_rtx = pool_alloc (value_pool); 752132718Skan memset (e->u.val_rtx, 0, RTX_HDR_SIZE); 753132718Skan PUT_CODE (e->u.val_rtx, VALUE); 754132718Skan PUT_MODE (e->u.val_rtx, mode); 75590075Sobrien CSELIB_VAL_PTR (e->u.val_rtx) = e; 75690075Sobrien e->addr_list = 0; 75790075Sobrien e->locs = 0; 758132718Skan e->next_containing_mem = 0; 75990075Sobrien return e; 76090075Sobrien} 76190075Sobrien 76290075Sobrien/* ADDR_ELT is a value that is used as address. MEM_ELT is the value that 76390075Sobrien contains the data at this address. X is a MEM that represents the 76490075Sobrien value. Update the two value structures to represent this situation. */ 76590075Sobrien 76690075Sobrienstatic void 767132718Skanadd_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x) 76890075Sobrien{ 76990075Sobrien struct elt_loc_list *l; 77090075Sobrien 77190075Sobrien /* Avoid duplicates. */ 77290075Sobrien for (l = mem_elt->locs; l; l = l->next) 773169689Skan if (MEM_P (l->loc) 77490075Sobrien && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt) 77590075Sobrien return; 77690075Sobrien 77790075Sobrien addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt); 77890075Sobrien mem_elt->locs 77990075Sobrien = new_elt_loc_list (mem_elt->locs, 78090075Sobrien replace_equiv_address_nv (x, addr_elt->u.val_rtx)); 781132718Skan if (mem_elt->next_containing_mem == NULL) 782132718Skan { 783132718Skan mem_elt->next_containing_mem = first_containing_mem; 784132718Skan first_containing_mem = mem_elt; 785132718Skan } 78690075Sobrien} 78790075Sobrien 78890075Sobrien/* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx. 78990075Sobrien If CREATE, make a new one if we haven't seen it before. */ 79090075Sobrien 79190075Sobrienstatic cselib_val * 792132718Skancselib_lookup_mem (rtx x, int create) 79390075Sobrien{ 79490075Sobrien enum machine_mode mode = GET_MODE (x); 79590075Sobrien void **slot; 79690075Sobrien cselib_val *addr; 79790075Sobrien cselib_val *mem_elt; 79890075Sobrien struct elt_list *l; 79990075Sobrien 80090075Sobrien if (MEM_VOLATILE_P (x) || mode == BLKmode 801169689Skan || !cselib_record_memory 80290075Sobrien || (FLOAT_MODE_P (mode) && flag_float_store)) 80390075Sobrien return 0; 80490075Sobrien 80590075Sobrien /* Look up the value for the address. */ 80690075Sobrien addr = cselib_lookup (XEXP (x, 0), mode, create); 80790075Sobrien if (! addr) 80890075Sobrien return 0; 80990075Sobrien 81090075Sobrien /* Find a value that describes a value of our mode at that address. */ 81190075Sobrien for (l = addr->addr_list; l; l = l->next) 81290075Sobrien if (GET_MODE (l->elt->u.val_rtx) == mode) 81390075Sobrien return l->elt; 81490075Sobrien 81590075Sobrien if (! create) 81690075Sobrien return 0; 81790075Sobrien 81890075Sobrien mem_elt = new_cselib_val (++next_unknown_value, mode); 81990075Sobrien add_mem_for_addr (addr, mem_elt, x); 820169689Skan slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x), 82190075Sobrien mem_elt->value, INSERT); 82290075Sobrien *slot = mem_elt; 82390075Sobrien return mem_elt; 82490075Sobrien} 82590075Sobrien 82690075Sobrien/* Walk rtx X and replace all occurrences of REG and MEM subexpressions 82790075Sobrien with VALUE expressions. This way, it becomes independent of changes 82890075Sobrien to registers and memory. 82990075Sobrien X isn't actually modified; if modifications are needed, new rtl is 83090075Sobrien allocated. However, the return value can share rtl with X. */ 83190075Sobrien 83290075Sobrienrtx 833132718Skancselib_subst_to_values (rtx x) 83490075Sobrien{ 83590075Sobrien enum rtx_code code = GET_CODE (x); 83690075Sobrien const char *fmt = GET_RTX_FORMAT (code); 83790075Sobrien cselib_val *e; 83890075Sobrien struct elt_list *l; 83990075Sobrien rtx copy = x; 84090075Sobrien int i; 84190075Sobrien 84290075Sobrien switch (code) 84390075Sobrien { 84490075Sobrien case REG: 845132718Skan l = REG_VALUES (REGNO (x)); 846132718Skan if (l && l->elt == NULL) 847132718Skan l = l->next; 848132718Skan for (; l; l = l->next) 84990075Sobrien if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x)) 85090075Sobrien return l->elt->u.val_rtx; 85190075Sobrien 852169689Skan gcc_unreachable (); 85390075Sobrien 85490075Sobrien case MEM: 85590075Sobrien e = cselib_lookup_mem (x, 0); 85690075Sobrien if (! e) 85790075Sobrien { 85890075Sobrien /* This happens for autoincrements. Assign a value that doesn't 85990075Sobrien match any other. */ 86090075Sobrien e = new_cselib_val (++next_unknown_value, GET_MODE (x)); 86190075Sobrien } 86290075Sobrien return e->u.val_rtx; 86390075Sobrien 86490075Sobrien case CONST_DOUBLE: 86596263Sobrien case CONST_VECTOR: 86690075Sobrien case CONST_INT: 86790075Sobrien return x; 86890075Sobrien 86990075Sobrien case POST_INC: 87090075Sobrien case PRE_INC: 87190075Sobrien case POST_DEC: 87290075Sobrien case PRE_DEC: 87390075Sobrien case POST_MODIFY: 87490075Sobrien case PRE_MODIFY: 87590075Sobrien e = new_cselib_val (++next_unknown_value, GET_MODE (x)); 87690075Sobrien return e->u.val_rtx; 877132718Skan 87890075Sobrien default: 87990075Sobrien break; 88090075Sobrien } 88190075Sobrien 88290075Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 88390075Sobrien { 88490075Sobrien if (fmt[i] == 'e') 88590075Sobrien { 88690075Sobrien rtx t = cselib_subst_to_values (XEXP (x, i)); 88790075Sobrien 88890075Sobrien if (t != XEXP (x, i) && x == copy) 88990075Sobrien copy = shallow_copy_rtx (x); 89090075Sobrien 89190075Sobrien XEXP (copy, i) = t; 89290075Sobrien } 89390075Sobrien else if (fmt[i] == 'E') 89490075Sobrien { 89590075Sobrien int j, k; 89690075Sobrien 89790075Sobrien for (j = 0; j < XVECLEN (x, i); j++) 89890075Sobrien { 89990075Sobrien rtx t = cselib_subst_to_values (XVECEXP (x, i, j)); 90090075Sobrien 90190075Sobrien if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i)) 90290075Sobrien { 90390075Sobrien if (x == copy) 90490075Sobrien copy = shallow_copy_rtx (x); 90590075Sobrien 90690075Sobrien XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i)); 90790075Sobrien for (k = 0; k < j; k++) 90890075Sobrien XVECEXP (copy, i, k) = XVECEXP (x, i, k); 90990075Sobrien } 91090075Sobrien 91190075Sobrien XVECEXP (copy, i, j) = t; 91290075Sobrien } 91390075Sobrien } 91490075Sobrien } 91590075Sobrien 91690075Sobrien return copy; 91790075Sobrien} 91890075Sobrien 91990075Sobrien/* Look up the rtl expression X in our tables and return the value it has. 92090075Sobrien If CREATE is zero, we return NULL if we don't know the value. Otherwise, 92190075Sobrien we create a new one if possible, using mode MODE if X doesn't have a mode 92290075Sobrien (i.e. because it's a constant). */ 92390075Sobrien 92490075Sobriencselib_val * 925132718Skancselib_lookup (rtx x, enum machine_mode mode, int create) 92690075Sobrien{ 92790075Sobrien void **slot; 92890075Sobrien cselib_val *e; 92990075Sobrien unsigned int hashval; 93090075Sobrien 93190075Sobrien if (GET_MODE (x) != VOIDmode) 93290075Sobrien mode = GET_MODE (x); 93390075Sobrien 93490075Sobrien if (GET_CODE (x) == VALUE) 93590075Sobrien return CSELIB_VAL_PTR (x); 93690075Sobrien 937169689Skan if (REG_P (x)) 93890075Sobrien { 93990075Sobrien struct elt_list *l; 94090075Sobrien unsigned int i = REGNO (x); 94190075Sobrien 942132718Skan l = REG_VALUES (i); 943132718Skan if (l && l->elt == NULL) 944132718Skan l = l->next; 945132718Skan for (; l; l = l->next) 94690075Sobrien if (mode == GET_MODE (l->elt->u.val_rtx)) 94790075Sobrien return l->elt; 94890075Sobrien 94990075Sobrien if (! create) 95090075Sobrien return 0; 95190075Sobrien 952102780Skan if (i < FIRST_PSEUDO_REGISTER) 953102780Skan { 954169689Skan unsigned int n = hard_regno_nregs[i][mode]; 955102780Skan 956102780Skan if (n > max_value_regs) 957102780Skan max_value_regs = n; 958102780Skan } 959102780Skan 96090075Sobrien e = new_cselib_val (++next_unknown_value, GET_MODE (x)); 96190075Sobrien e->locs = new_elt_loc_list (e->locs, x); 96290075Sobrien if (REG_VALUES (i) == 0) 963132718Skan { 964132718Skan /* Maintain the invariant that the first entry of 965132718Skan REG_VALUES, if present, must be the value used to set the 966132718Skan register, or NULL. */ 967169689Skan used_regs[n_used_regs++] = i; 968132718Skan REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL); 969132718Skan } 970132718Skan REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e); 971169689Skan slot = htab_find_slot_with_hash (cselib_hash_table, x, e->value, INSERT); 97290075Sobrien *slot = e; 97390075Sobrien return e; 97490075Sobrien } 97590075Sobrien 976169689Skan if (MEM_P (x)) 97790075Sobrien return cselib_lookup_mem (x, create); 97890075Sobrien 979169689Skan hashval = cselib_hash_rtx (x, create); 98090075Sobrien /* Can't even create if hashing is not possible. */ 98190075Sobrien if (! hashval) 98290075Sobrien return 0; 98390075Sobrien 984169689Skan slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x), 98590075Sobrien hashval, create ? INSERT : NO_INSERT); 98690075Sobrien if (slot == 0) 98790075Sobrien return 0; 98890075Sobrien 98990075Sobrien e = (cselib_val *) *slot; 99090075Sobrien if (e) 99190075Sobrien return e; 99290075Sobrien 99390075Sobrien e = new_cselib_val (hashval, mode); 99490075Sobrien 99590075Sobrien /* We have to fill the slot before calling cselib_subst_to_values: 99690075Sobrien the hash table is inconsistent until we do so, and 99790075Sobrien cselib_subst_to_values will need to do lookups. */ 99890075Sobrien *slot = (void *) e; 99990075Sobrien e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x)); 100090075Sobrien return e; 100190075Sobrien} 100290075Sobrien 100390075Sobrien/* Invalidate any entries in reg_values that overlap REGNO. This is called 100490075Sobrien if REGNO is changing. MODE is the mode of the assignment to REGNO, which 100590075Sobrien is used to determine how many hard registers are being changed. If MODE 100690075Sobrien is VOIDmode, then only REGNO is being changed; this is used when 100790075Sobrien invalidating call clobbered registers across a call. */ 100890075Sobrien 100990075Sobrienstatic void 1010132718Skancselib_invalidate_regno (unsigned int regno, enum machine_mode mode) 101190075Sobrien{ 101290075Sobrien unsigned int endregno; 101390075Sobrien unsigned int i; 101490075Sobrien 101590075Sobrien /* If we see pseudos after reload, something is _wrong_. */ 1016169689Skan gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER 1017169689Skan || reg_renumber[regno] < 0); 101890075Sobrien 101990075Sobrien /* Determine the range of registers that must be invalidated. For 102090075Sobrien pseudos, only REGNO is affected. For hard regs, we must take MODE 102190075Sobrien into account, and we must also invalidate lower register numbers 102290075Sobrien if they contain values that overlap REGNO. */ 1023117395Skan if (regno < FIRST_PSEUDO_REGISTER) 1024102780Skan { 1025169689Skan gcc_assert (mode != VOIDmode); 1026132718Skan 1027102780Skan if (regno < max_value_regs) 1028102780Skan i = 0; 1029102780Skan else 1030102780Skan i = regno - max_value_regs; 103190075Sobrien 1032169689Skan endregno = regno + hard_regno_nregs[regno][mode]; 1033102780Skan } 1034102780Skan else 103590075Sobrien { 1036102780Skan i = regno; 1037102780Skan endregno = regno + 1; 1038102780Skan } 1039102780Skan 1040102780Skan for (; i < endregno; i++) 1041102780Skan { 104290075Sobrien struct elt_list **l = ®_VALUES (i); 104390075Sobrien 104490075Sobrien /* Go through all known values for this reg; if it overlaps the range 104590075Sobrien we're invalidating, remove the value. */ 104690075Sobrien while (*l) 104790075Sobrien { 104890075Sobrien cselib_val *v = (*l)->elt; 104990075Sobrien struct elt_loc_list **p; 105090075Sobrien unsigned int this_last = i; 105190075Sobrien 1052132718Skan if (i < FIRST_PSEUDO_REGISTER && v != NULL) 1053169689Skan this_last += hard_regno_nregs[i][GET_MODE (v->u.val_rtx)] - 1; 105490075Sobrien 1055132718Skan if (this_last < regno || v == NULL) 105690075Sobrien { 105790075Sobrien l = &(*l)->next; 105890075Sobrien continue; 105990075Sobrien } 106090075Sobrien 106190075Sobrien /* We have an overlap. */ 1062132718Skan if (*l == REG_VALUES (i)) 1063132718Skan { 1064132718Skan /* Maintain the invariant that the first entry of 1065132718Skan REG_VALUES, if present, must be the value used to set 1066132718Skan the register, or NULL. This is also nice because 1067132718Skan then we won't push the same regno onto user_regs 1068132718Skan multiple times. */ 1069132718Skan (*l)->elt = NULL; 1070132718Skan l = &(*l)->next; 1071132718Skan } 1072132718Skan else 1073132718Skan unchain_one_elt_list (l); 107490075Sobrien 107590075Sobrien /* Now, we clear the mapping from value to reg. It must exist, so 107690075Sobrien this code will crash intentionally if it doesn't. */ 107790075Sobrien for (p = &v->locs; ; p = &(*p)->next) 107890075Sobrien { 107990075Sobrien rtx x = (*p)->loc; 108090075Sobrien 1081169689Skan if (REG_P (x) && REGNO (x) == i) 108290075Sobrien { 108390075Sobrien unchain_one_elt_loc_list (p); 108490075Sobrien break; 108590075Sobrien } 108690075Sobrien } 108790075Sobrien if (v->locs == 0) 108890075Sobrien n_useless_values++; 108990075Sobrien } 109090075Sobrien } 109190075Sobrien} 1092132718Skan 1093132718Skan/* Return 1 if X has a value that can vary even between two 1094132718Skan executions of the program. 0 means X can be compared reliably 1095132718Skan against certain constants or near-constants. */ 109690075Sobrien 109790075Sobrienstatic int 1098132718Skancselib_rtx_varies_p (rtx x ATTRIBUTE_UNUSED, int from_alias ATTRIBUTE_UNUSED) 109990075Sobrien{ 1100132718Skan /* We actually don't need to verify very hard. This is because 1101132718Skan if X has actually changed, we invalidate the memory anyway, 1102132718Skan so assume that all common memory addresses are 1103132718Skan invariant. */ 110490075Sobrien return 0; 110590075Sobrien} 110690075Sobrien 1107132718Skan/* Invalidate any locations in the table which are changed because of a 1108132718Skan store to MEM_RTX. If this is called because of a non-const call 1109132718Skan instruction, MEM_RTX is (mem:BLK const0_rtx). */ 111090075Sobrien 1111132718Skanstatic void 1112132718Skancselib_invalidate_mem (rtx mem_rtx) 111390075Sobrien{ 1114132718Skan cselib_val **vp, *v, *next; 1115132718Skan int num_mems = 0; 1116132718Skan rtx mem_addr; 111790075Sobrien 1118132718Skan mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0))); 1119132718Skan mem_rtx = canon_rtx (mem_rtx); 1120132718Skan 1121132718Skan vp = &first_containing_mem; 1122132718Skan for (v = *vp; v != &dummy_val; v = next) 112390075Sobrien { 1124132718Skan bool has_mem = false; 1125132718Skan struct elt_loc_list **p = &v->locs; 1126132718Skan int had_locs = v->locs != 0; 112790075Sobrien 1128132718Skan while (*p) 112990075Sobrien { 1130132718Skan rtx x = (*p)->loc; 1131132718Skan cselib_val *addr; 1132132718Skan struct elt_list **mem_chain; 113390075Sobrien 1134132718Skan /* MEMs may occur in locations only at the top level; below 1135132718Skan that every MEM or REG is substituted by its VALUE. */ 1136169689Skan if (!MEM_P (x)) 113790075Sobrien { 1138132718Skan p = &(*p)->next; 1139132718Skan continue; 114090075Sobrien } 1141132718Skan if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS) 1142132718Skan && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr, 1143132718Skan x, cselib_rtx_varies_p)) 1144132718Skan { 1145132718Skan has_mem = true; 1146132718Skan num_mems++; 1147132718Skan p = &(*p)->next; 1148132718Skan continue; 1149132718Skan } 115090075Sobrien 1151132718Skan /* This one overlaps. */ 1152132718Skan /* We must have a mapping from this MEM's address to the 1153132718Skan value (E). Remove that, too. */ 1154132718Skan addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0); 1155132718Skan mem_chain = &addr->addr_list; 1156132718Skan for (;;) 1157132718Skan { 1158132718Skan if ((*mem_chain)->elt == v) 1159132718Skan { 1160132718Skan unchain_one_elt_list (mem_chain); 1161132718Skan break; 1162132718Skan } 116390075Sobrien 1164132718Skan mem_chain = &(*mem_chain)->next; 1165132718Skan } 116690075Sobrien 1167132718Skan unchain_one_elt_loc_list (p); 1168132718Skan } 116990075Sobrien 1170132718Skan if (had_locs && v->locs == 0) 1171132718Skan n_useless_values++; 117290075Sobrien 1173132718Skan next = v->next_containing_mem; 1174132718Skan if (has_mem) 1175132718Skan { 1176132718Skan *vp = v; 1177132718Skan vp = &(*vp)->next_containing_mem; 1178132718Skan } 1179132718Skan else 1180132718Skan v->next_containing_mem = NULL; 1181132718Skan } 1182132718Skan *vp = &dummy_val; 118390075Sobrien} 118490075Sobrien 1185146895Skan/* Invalidate DEST, which is being assigned to or clobbered. */ 118690075Sobrien 1187146895Skanvoid 1188146895Skancselib_invalidate_rtx (rtx dest) 118990075Sobrien{ 1190169689Skan while (GET_CODE (dest) == SUBREG 1191169689Skan || GET_CODE (dest) == ZERO_EXTRACT 1192169689Skan || GET_CODE (dest) == STRICT_LOW_PART) 119390075Sobrien dest = XEXP (dest, 0); 119490075Sobrien 1195169689Skan if (REG_P (dest)) 119690075Sobrien cselib_invalidate_regno (REGNO (dest), GET_MODE (dest)); 1197169689Skan else if (MEM_P (dest)) 119890075Sobrien cselib_invalidate_mem (dest); 119990075Sobrien 120090075Sobrien /* Some machines don't define AUTO_INC_DEC, but they still use push 120190075Sobrien instructions. We need to catch that case here in order to 120290075Sobrien invalidate the stack pointer correctly. Note that invalidating 120390075Sobrien the stack pointer is different from invalidating DEST. */ 120490075Sobrien if (push_operand (dest, GET_MODE (dest))) 1205146895Skan cselib_invalidate_rtx (stack_pointer_rtx); 120690075Sobrien} 120790075Sobrien 1208146895Skan/* A wrapper for cselib_invalidate_rtx to be called via note_stores. */ 1209146895Skan 1210146895Skanstatic void 1211146895Skancselib_invalidate_rtx_note_stores (rtx dest, rtx ignore ATTRIBUTE_UNUSED, 1212146895Skan void *data ATTRIBUTE_UNUSED) 1213146895Skan{ 1214146895Skan cselib_invalidate_rtx (dest); 1215146895Skan} 1216146895Skan 121790075Sobrien/* Record the result of a SET instruction. DEST is being set; the source 121890075Sobrien contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT 121990075Sobrien describes its address. */ 122090075Sobrien 122190075Sobrienstatic void 1222132718Skancselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt) 122390075Sobrien{ 1224169689Skan int dreg = REG_P (dest) ? (int) REGNO (dest) : -1; 122590075Sobrien 122690075Sobrien if (src_elt == 0 || side_effects_p (dest)) 122790075Sobrien return; 122890075Sobrien 122990075Sobrien if (dreg >= 0) 123090075Sobrien { 1231102780Skan if (dreg < FIRST_PSEUDO_REGISTER) 1232102780Skan { 1233169689Skan unsigned int n = hard_regno_nregs[dreg][GET_MODE (dest)]; 1234102780Skan 1235102780Skan if (n > max_value_regs) 1236102780Skan max_value_regs = n; 1237102780Skan } 1238102780Skan 1239132718Skan if (REG_VALUES (dreg) == 0) 1240132718Skan { 1241169689Skan used_regs[n_used_regs++] = dreg; 1242132718Skan REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt); 1243132718Skan } 1244132718Skan else 1245132718Skan { 1246169689Skan /* The register should have been invalidated. */ 1247169689Skan gcc_assert (REG_VALUES (dreg)->elt == 0); 1248169689Skan REG_VALUES (dreg)->elt = src_elt; 1249132718Skan } 1250132718Skan 125190075Sobrien if (src_elt->locs == 0) 125290075Sobrien n_useless_values--; 125390075Sobrien src_elt->locs = new_elt_loc_list (src_elt->locs, dest); 125490075Sobrien } 1255169689Skan else if (MEM_P (dest) && dest_addr_elt != 0 1256169689Skan && cselib_record_memory) 125790075Sobrien { 125890075Sobrien if (src_elt->locs == 0) 125990075Sobrien n_useless_values--; 126090075Sobrien add_mem_for_addr (dest_addr_elt, src_elt, dest); 126190075Sobrien } 126290075Sobrien} 126390075Sobrien 126490075Sobrien/* Describe a single set that is part of an insn. */ 126590075Sobrienstruct set 126690075Sobrien{ 126790075Sobrien rtx src; 126890075Sobrien rtx dest; 126990075Sobrien cselib_val *src_elt; 127090075Sobrien cselib_val *dest_addr_elt; 127190075Sobrien}; 127290075Sobrien 127390075Sobrien/* There is no good way to determine how many elements there can be 127490075Sobrien in a PARALLEL. Since it's fairly cheap, use a really large number. */ 127590075Sobrien#define MAX_SETS (FIRST_PSEUDO_REGISTER * 2) 127690075Sobrien 127790075Sobrien/* Record the effects of any sets in INSN. */ 127890075Sobrienstatic void 1279132718Skancselib_record_sets (rtx insn) 128090075Sobrien{ 128190075Sobrien int n_sets = 0; 128290075Sobrien int i; 128390075Sobrien struct set sets[MAX_SETS]; 128490075Sobrien rtx body = PATTERN (insn); 128590075Sobrien rtx cond = 0; 128690075Sobrien 128790075Sobrien body = PATTERN (insn); 128890075Sobrien if (GET_CODE (body) == COND_EXEC) 128990075Sobrien { 129090075Sobrien cond = COND_EXEC_TEST (body); 129190075Sobrien body = COND_EXEC_CODE (body); 129290075Sobrien } 129390075Sobrien 129490075Sobrien /* Find all sets. */ 129590075Sobrien if (GET_CODE (body) == SET) 129690075Sobrien { 129790075Sobrien sets[0].src = SET_SRC (body); 129890075Sobrien sets[0].dest = SET_DEST (body); 129990075Sobrien n_sets = 1; 130090075Sobrien } 130190075Sobrien else if (GET_CODE (body) == PARALLEL) 130290075Sobrien { 130390075Sobrien /* Look through the PARALLEL and record the values being 130490075Sobrien set, if possible. Also handle any CLOBBERs. */ 130590075Sobrien for (i = XVECLEN (body, 0) - 1; i >= 0; --i) 130690075Sobrien { 130790075Sobrien rtx x = XVECEXP (body, 0, i); 130890075Sobrien 130990075Sobrien if (GET_CODE (x) == SET) 131090075Sobrien { 131190075Sobrien sets[n_sets].src = SET_SRC (x); 131290075Sobrien sets[n_sets].dest = SET_DEST (x); 131390075Sobrien n_sets++; 131490075Sobrien } 131590075Sobrien } 131690075Sobrien } 131790075Sobrien 131890075Sobrien /* Look up the values that are read. Do this before invalidating the 131990075Sobrien locations that are written. */ 132090075Sobrien for (i = 0; i < n_sets; i++) 132190075Sobrien { 132290075Sobrien rtx dest = sets[i].dest; 132390075Sobrien 132490075Sobrien /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for 132590075Sobrien the low part after invalidating any knowledge about larger modes. */ 132690075Sobrien if (GET_CODE (sets[i].dest) == STRICT_LOW_PART) 132790075Sobrien sets[i].dest = dest = XEXP (dest, 0); 132890075Sobrien 132990075Sobrien /* We don't know how to record anything but REG or MEM. */ 1330169689Skan if (REG_P (dest) 1331169689Skan || (MEM_P (dest) && cselib_record_memory)) 133290075Sobrien { 133390075Sobrien rtx src = sets[i].src; 133490075Sobrien if (cond) 133590075Sobrien src = gen_rtx_IF_THEN_ELSE (GET_MODE (src), cond, src, dest); 133690075Sobrien sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1); 1337169689Skan if (MEM_P (dest)) 133890075Sobrien sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1); 133990075Sobrien else 134090075Sobrien sets[i].dest_addr_elt = 0; 134190075Sobrien } 134290075Sobrien } 134390075Sobrien 134490075Sobrien /* Invalidate all locations written by this insn. Note that the elts we 134590075Sobrien looked up in the previous loop aren't affected, just some of their 134690075Sobrien locations may go away. */ 1347146895Skan note_stores (body, cselib_invalidate_rtx_note_stores, NULL); 134890075Sobrien 1349132718Skan /* If this is an asm, look for duplicate sets. This can happen when the 1350132718Skan user uses the same value as an output multiple times. This is valid 1351132718Skan if the outputs are not actually used thereafter. Treat this case as 1352132718Skan if the value isn't actually set. We do this by smashing the destination 1353132718Skan to pc_rtx, so that we won't record the value later. */ 1354132718Skan if (n_sets >= 2 && asm_noperands (body) >= 0) 1355132718Skan { 1356132718Skan for (i = 0; i < n_sets; i++) 1357132718Skan { 1358132718Skan rtx dest = sets[i].dest; 1359169689Skan if (REG_P (dest) || MEM_P (dest)) 1360132718Skan { 1361132718Skan int j; 1362132718Skan for (j = i + 1; j < n_sets; j++) 1363132718Skan if (rtx_equal_p (dest, sets[j].dest)) 1364132718Skan { 1365132718Skan sets[i].dest = pc_rtx; 1366132718Skan sets[j].dest = pc_rtx; 1367132718Skan } 1368132718Skan } 1369132718Skan } 1370132718Skan } 1371132718Skan 137290075Sobrien /* Now enter the equivalences in our tables. */ 137390075Sobrien for (i = 0; i < n_sets; i++) 137490075Sobrien { 137590075Sobrien rtx dest = sets[i].dest; 1376169689Skan if (REG_P (dest) 1377169689Skan || (MEM_P (dest) && cselib_record_memory)) 137890075Sobrien cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt); 137990075Sobrien } 138090075Sobrien} 138190075Sobrien 138290075Sobrien/* Record the effects of INSN. */ 138390075Sobrien 138490075Sobrienvoid 1385132718Skancselib_process_insn (rtx insn) 138690075Sobrien{ 138790075Sobrien int i; 138890075Sobrien rtx x; 138990075Sobrien 1390117395Skan if (find_reg_note (insn, REG_LIBCALL, NULL)) 1391117395Skan cselib_current_insn_in_libcall = true; 139290075Sobrien cselib_current_insn = insn; 139390075Sobrien 139490075Sobrien /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */ 1395169689Skan if (LABEL_P (insn) 1396169689Skan || (CALL_P (insn) 139790075Sobrien && find_reg_note (insn, REG_SETJMP, NULL)) 1398169689Skan || (NONJUMP_INSN_P (insn) 139990075Sobrien && GET_CODE (PATTERN (insn)) == ASM_OPERANDS 140090075Sobrien && MEM_VOLATILE_P (PATTERN (insn)))) 140190075Sobrien { 1402146895Skan if (find_reg_note (insn, REG_RETVAL, NULL)) 1403146895Skan cselib_current_insn_in_libcall = false; 1404169689Skan cselib_clear_table (); 140590075Sobrien return; 140690075Sobrien } 140790075Sobrien 140890075Sobrien if (! INSN_P (insn)) 140990075Sobrien { 1410146895Skan if (find_reg_note (insn, REG_RETVAL, NULL)) 1411146895Skan cselib_current_insn_in_libcall = false; 141290075Sobrien cselib_current_insn = 0; 141390075Sobrien return; 141490075Sobrien } 141590075Sobrien 141690075Sobrien /* If this is a call instruction, forget anything stored in a 141790075Sobrien call clobbered register, or, if this is not a const call, in 141890075Sobrien memory. */ 1419169689Skan if (CALL_P (insn)) 142090075Sobrien { 142190075Sobrien for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1422169689Skan if (call_used_regs[i] 1423169689Skan || (REG_VALUES (i) && REG_VALUES (i)->elt 1424169689Skan && HARD_REGNO_CALL_PART_CLOBBERED (i, 1425169689Skan GET_MODE (REG_VALUES (i)->elt->u.val_rtx)))) 1426117395Skan cselib_invalidate_regno (i, reg_raw_mode[i]); 142790075Sobrien 142890075Sobrien if (! CONST_OR_PURE_CALL_P (insn)) 142990075Sobrien cselib_invalidate_mem (callmem); 143090075Sobrien } 143190075Sobrien 143290075Sobrien cselib_record_sets (insn); 143390075Sobrien 143490075Sobrien#ifdef AUTO_INC_DEC 143590075Sobrien /* Clobber any registers which appear in REG_INC notes. We 143690075Sobrien could keep track of the changes to their values, but it is 143790075Sobrien unlikely to help. */ 143890075Sobrien for (x = REG_NOTES (insn); x; x = XEXP (x, 1)) 143990075Sobrien if (REG_NOTE_KIND (x) == REG_INC) 1440146895Skan cselib_invalidate_rtx (XEXP (x, 0)); 144190075Sobrien#endif 144290075Sobrien 144390075Sobrien /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only 144490075Sobrien after we have processed the insn. */ 1445169689Skan if (CALL_P (insn)) 144690075Sobrien for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1)) 144790075Sobrien if (GET_CODE (XEXP (x, 0)) == CLOBBER) 1448146895Skan cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0)); 144990075Sobrien 1450146895Skan if (find_reg_note (insn, REG_RETVAL, NULL)) 1451146895Skan cselib_current_insn_in_libcall = false; 145290075Sobrien cselib_current_insn = 0; 145390075Sobrien 1454169689Skan if (n_useless_values > MAX_USELESS_VALUES 1455169689Skan /* remove_useless_values is linear in the hash table size. Avoid 1456169689Skan quadratic behaviour for very large hashtables with very few 1457169689Skan useless elements. */ 1458169689Skan && (unsigned int)n_useless_values > cselib_hash_table->n_elements / 4) 145990075Sobrien remove_useless_values (); 146090075Sobrien} 146190075Sobrien 146290075Sobrien/* Initialize cselib for one pass. The caller must also call 146390075Sobrien init_alias_analysis. */ 146490075Sobrien 146590075Sobrienvoid 1466169689Skancselib_init (bool record_memory) 146790075Sobrien{ 1468132718Skan elt_list_pool = create_alloc_pool ("elt_list", 1469132718Skan sizeof (struct elt_list), 10); 1470132718Skan elt_loc_list_pool = create_alloc_pool ("elt_loc_list", 1471132718Skan sizeof (struct elt_loc_list), 10); 1472132718Skan cselib_val_pool = create_alloc_pool ("cselib_val_list", 1473132718Skan sizeof (cselib_val), 10); 1474169689Skan value_pool = create_alloc_pool ("value", RTX_CODE_SIZE (VALUE), 100); 1475169689Skan cselib_record_memory = record_memory; 1476117395Skan /* This is only created once. */ 147790075Sobrien if (! callmem) 1478117395Skan callmem = gen_rtx_MEM (BLKmode, const0_rtx); 1479117395Skan 1480117395Skan cselib_nregs = max_reg_num (); 1481169689Skan 1482169689Skan /* We preserve reg_values to allow expensive clearing of the whole thing. 1483169689Skan Reallocate it however if it happens to be too large. */ 1484169689Skan if (!reg_values || reg_values_size < cselib_nregs 1485169689Skan || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4)) 148690075Sobrien { 1487169689Skan if (reg_values) 1488169689Skan free (reg_values); 1489169689Skan /* Some space for newly emit instructions so we don't end up 1490169689Skan reallocating in between passes. */ 1491169689Skan reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16; 1492169689Skan reg_values = XCNEWVEC (struct elt_list *, reg_values_size); 149390075Sobrien } 1494169689Skan used_regs = XNEWVEC (unsigned int, cselib_nregs); 1495169689Skan n_used_regs = 0; 1496169689Skan cselib_hash_table = htab_create (31, get_value_hash, 1497169689Skan entry_and_rtx_equal_p, NULL); 1498117395Skan cselib_current_insn_in_libcall = false; 149990075Sobrien} 150090075Sobrien 150190075Sobrien/* Called when the current user is done with cselib. */ 150290075Sobrien 150390075Sobrienvoid 1504132718Skancselib_finish (void) 150590075Sobrien{ 1506132718Skan free_alloc_pool (elt_list_pool); 1507132718Skan free_alloc_pool (elt_loc_list_pool); 1508132718Skan free_alloc_pool (cselib_val_pool); 1509132718Skan free_alloc_pool (value_pool); 1510169689Skan cselib_clear_table (); 1511169689Skan htab_delete (cselib_hash_table); 1512169689Skan free (used_regs); 1513117395Skan used_regs = 0; 1514169689Skan cselib_hash_table = 0; 1515117395Skan n_useless_values = 0; 1516117395Skan next_unknown_value = 0; 151790075Sobrien} 1518117395Skan 1519117395Skan#include "gt-cselib.h" 1520