1/* Common subexpression elimination library for GNU compiler. 2 Copyright (C) 1987-2020 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING3. If not see 18<http://www.gnu.org/licenses/>. */ 19 20#include "config.h" 21#include "system.h" 22#include "coretypes.h" 23#include "backend.h" 24#include "target.h" 25#include "rtl.h" 26#include "tree.h" 27#include "df.h" 28#include "memmodel.h" 29#include "tm_p.h" 30#include "regs.h" 31#include "emit-rtl.h" 32#include "dumpfile.h" 33#include "cselib.h" 34#include "function-abi.h" 35 36/* A list of cselib_val structures. */ 37struct elt_list 38{ 39 struct elt_list *next; 40 cselib_val *elt; 41}; 42 43static bool cselib_record_memory; 44static bool cselib_preserve_constants; 45static bool cselib_any_perm_equivs; 46static inline void promote_debug_loc (struct elt_loc_list *l); 47static struct elt_list *new_elt_list (struct elt_list *, cselib_val *); 48static void new_elt_loc_list (cselib_val *, rtx); 49static void unchain_one_value (cselib_val *); 50static void unchain_one_elt_list (struct elt_list **); 51static void unchain_one_elt_loc_list (struct elt_loc_list **); 52static void remove_useless_values (void); 53static unsigned int cselib_hash_rtx (rtx, int, machine_mode); 54static cselib_val *new_cselib_val (unsigned int, machine_mode, rtx); 55static void add_mem_for_addr (cselib_val *, cselib_val *, rtx); 56static cselib_val *cselib_lookup_mem (rtx, int); 57static void cselib_invalidate_regno (unsigned int, machine_mode); 58static void cselib_invalidate_mem (rtx); 59static void cselib_record_set (rtx, cselib_val *, cselib_val *); 60static void cselib_record_sets (rtx_insn *); 61static rtx autoinc_split (rtx, rtx *, machine_mode); 62 63#define PRESERVED_VALUE_P(RTX) \ 64 (RTL_FLAG_CHECK1 ("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging) 65 66#define SP_BASED_VALUE_P(RTX) \ 67 (RTL_FLAG_CHECK1 ("SP_BASED_VALUE_P", (RTX), VALUE)->jump) 68 69#define SP_DERIVED_VALUE_P(RTX) \ 70 (RTL_FLAG_CHECK1 ("SP_DERIVED_VALUE_P", (RTX), VALUE)->call) 71 72struct expand_value_data 73{ 74 bitmap regs_active; 75 cselib_expand_callback callback; 76 void *callback_arg; 77 bool dummy; 78}; 79 80static rtx cselib_expand_value_rtx_1 (rtx, struct expand_value_data *, int); 81 82/* There are three ways in which cselib can look up an rtx: 83 - for a REG, the reg_values table (which is indexed by regno) is used 84 - for a MEM, we recursively look up its address and then follow the 85 addr_list of that value 86 - for everything else, we compute a hash value and go through the hash 87 table. Since different rtx's can still have the same hash value, 88 this involves walking the table entries for a given value and comparing 89 the locations of the entries with the rtx we are looking up. */ 90 91struct cselib_hasher : nofree_ptr_hash <cselib_val> 92{ 93 struct key { 94 /* The rtx value and its mode (needed separately for constant 95 integers). */ 96 machine_mode mode; 97 rtx x; 98 /* The mode of the contaning MEM, if any, otherwise VOIDmode. */ 99 machine_mode memmode; 100 }; 101 typedef key *compare_type; 102 static inline hashval_t hash (const cselib_val *); 103 static inline bool equal (const cselib_val *, const key *); 104}; 105 106/* The hash function for our hash table. The value is always computed with 107 cselib_hash_rtx when adding an element; this function just extracts the 108 hash value from a cselib_val structure. */ 109 110inline hashval_t 111cselib_hasher::hash (const cselib_val *v) 112{ 113 return v->hash; 114} 115 116/* The equality test for our hash table. The first argument V is a table 117 element (i.e. a cselib_val), while the second arg X is an rtx. We know 118 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a 119 CONST of an appropriate mode. */ 120 121inline bool 122cselib_hasher::equal (const cselib_val *v, const key *x_arg) 123{ 124 struct elt_loc_list *l; 125 rtx x = x_arg->x; 126 machine_mode mode = x_arg->mode; 127 machine_mode memmode = x_arg->memmode; 128 129 if (mode != GET_MODE (v->val_rtx)) 130 return false; 131 132 if (GET_CODE (x) == VALUE) 133 return x == v->val_rtx; 134 135 if (SP_DERIVED_VALUE_P (v->val_rtx) && GET_MODE (x) == Pmode) 136 { 137 rtx xoff = NULL; 138 if (autoinc_split (x, &xoff, memmode) == v->val_rtx && xoff == NULL_RTX) 139 return true; 140 } 141 142 /* We don't guarantee that distinct rtx's have different hash values, 143 so we need to do a comparison. */ 144 for (l = v->locs; l; l = l->next) 145 if (rtx_equal_for_cselib_1 (l->loc, x, memmode, 0)) 146 { 147 promote_debug_loc (l); 148 return true; 149 } 150 151 return false; 152} 153 154/* A table that enables us to look up elts by their value. */ 155static hash_table<cselib_hasher> *cselib_hash_table; 156 157/* A table to hold preserved values. */ 158static hash_table<cselib_hasher> *cselib_preserved_hash_table; 159 160/* This is a global so we don't have to pass this through every function. 161 It is used in new_elt_loc_list to set SETTING_INSN. */ 162static rtx_insn *cselib_current_insn; 163 164/* The unique id that the next create value will take. */ 165static unsigned int next_uid; 166 167/* The number of registers we had when the varrays were last resized. */ 168static unsigned int cselib_nregs; 169 170/* Count values without known locations, or with only locations that 171 wouldn't have been known except for debug insns. Whenever this 172 grows too big, we remove these useless values from the table. 173 174 Counting values with only debug values is a bit tricky. We don't 175 want to increment n_useless_values when we create a value for a 176 debug insn, for this would get n_useless_values out of sync, but we 177 want increment it if all locs in the list that were ever referenced 178 in nondebug insns are removed from the list. 179 180 In the general case, once we do that, we'd have to stop accepting 181 nondebug expressions in the loc list, to avoid having two values 182 equivalent that, without debug insns, would have been made into 183 separate values. However, because debug insns never introduce 184 equivalences themselves (no assignments), the only means for 185 growing loc lists is through nondebug assignments. If the locs 186 also happen to be referenced in debug insns, it will work just fine. 187 188 A consequence of this is that there's at most one debug-only loc in 189 each loc list. If we keep it in the first entry, testing whether 190 we have a debug-only loc list takes O(1). 191 192 Furthermore, since any additional entry in a loc list containing a 193 debug loc would have to come from an assignment (nondebug) that 194 references both the initial debug loc and the newly-equivalent loc, 195 the initial debug loc would be promoted to a nondebug loc, and the 196 loc list would not contain debug locs any more. 197 198 So the only case we have to be careful with in order to keep 199 n_useless_values in sync between debug and nondebug compilations is 200 to avoid incrementing n_useless_values when removing the single loc 201 from a value that turns out to not appear outside debug values. We 202 increment n_useless_debug_values instead, and leave such values 203 alone until, for other reasons, we garbage-collect useless 204 values. */ 205static int n_useless_values; 206static int n_useless_debug_values; 207 208/* Count values whose locs have been taken exclusively from debug 209 insns for the entire life of the value. */ 210static int n_debug_values; 211 212/* Number of useless values before we remove them from the hash table. */ 213#define MAX_USELESS_VALUES 32 214 215/* This table maps from register number to values. It does not 216 contain pointers to cselib_val structures, but rather elt_lists. 217 The purpose is to be able to refer to the same register in 218 different modes. The first element of the list defines the mode in 219 which the register was set; if the mode is unknown or the value is 220 no longer valid in that mode, ELT will be NULL for the first 221 element. */ 222static struct elt_list **reg_values; 223static unsigned int reg_values_size; 224#define REG_VALUES(i) reg_values[i] 225 226/* The largest number of hard regs used by any entry added to the 227 REG_VALUES table. Cleared on each cselib_clear_table() invocation. */ 228static unsigned int max_value_regs; 229 230/* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used 231 in cselib_clear_table() for fast emptying. */ 232static unsigned int *used_regs; 233static unsigned int n_used_regs; 234 235/* We pass this to cselib_invalidate_mem to invalidate all of 236 memory for a non-const call instruction. */ 237static GTY(()) rtx callmem; 238 239/* Set by discard_useless_locs if it deleted the last location of any 240 value. */ 241static int values_became_useless; 242 243/* Used as stop element of the containing_mem list so we can check 244 presence in the list by checking the next pointer. */ 245static cselib_val dummy_val; 246 247/* If non-NULL, value of the eliminated arg_pointer_rtx or frame_pointer_rtx 248 that is constant through the whole function and should never be 249 eliminated. */ 250static cselib_val *cfa_base_preserved_val; 251static unsigned int cfa_base_preserved_regno = INVALID_REGNUM; 252 253/* Used to list all values that contain memory reference. 254 May or may not contain the useless values - the list is compacted 255 each time memory is invalidated. */ 256static cselib_val *first_containing_mem = &dummy_val; 257 258static object_allocator<elt_list> elt_list_pool ("elt_list"); 259static object_allocator<elt_loc_list> elt_loc_list_pool ("elt_loc_list"); 260static object_allocator<cselib_val> cselib_val_pool ("cselib_val_list"); 261 262static pool_allocator value_pool ("value", RTX_CODE_SIZE (VALUE)); 263 264/* If nonnull, cselib will call this function before freeing useless 265 VALUEs. A VALUE is deemed useless if its "locs" field is null. */ 266void (*cselib_discard_hook) (cselib_val *); 267 268/* If nonnull, cselib will call this function before recording sets or 269 even clobbering outputs of INSN. All the recorded sets will be 270 represented in the array sets[n_sets]. new_val_min can be used to 271 tell whether values present in sets are introduced by this 272 instruction. */ 273void (*cselib_record_sets_hook) (rtx_insn *insn, struct cselib_set *sets, 274 int n_sets); 275 276 277 278/* Allocate a struct elt_list and fill in its two elements with the 279 arguments. */ 280 281static inline struct elt_list * 282new_elt_list (struct elt_list *next, cselib_val *elt) 283{ 284 elt_list *el = elt_list_pool.allocate (); 285 el->next = next; 286 el->elt = elt; 287 return el; 288} 289 290/* Allocate a struct elt_loc_list with LOC and prepend it to VAL's loc 291 list. */ 292 293static inline void 294new_elt_loc_list (cselib_val *val, rtx loc) 295{ 296 struct elt_loc_list *el, *next = val->locs; 297 298 gcc_checking_assert (!next || !next->setting_insn 299 || !DEBUG_INSN_P (next->setting_insn) 300 || cselib_current_insn == next->setting_insn); 301 302 /* If we're creating the first loc in a debug insn context, we've 303 just created a debug value. Count it. */ 304 if (!next && cselib_current_insn && DEBUG_INSN_P (cselib_current_insn)) 305 n_debug_values++; 306 307 val = canonical_cselib_val (val); 308 next = val->locs; 309 310 if (GET_CODE (loc) == VALUE) 311 { 312 loc = canonical_cselib_val (CSELIB_VAL_PTR (loc))->val_rtx; 313 314 gcc_checking_assert (PRESERVED_VALUE_P (loc) 315 == PRESERVED_VALUE_P (val->val_rtx)); 316 317 if (val->val_rtx == loc) 318 return; 319 else if (val->uid > CSELIB_VAL_PTR (loc)->uid) 320 { 321 /* Reverse the insertion. */ 322 new_elt_loc_list (CSELIB_VAL_PTR (loc), val->val_rtx); 323 return; 324 } 325 326 gcc_checking_assert (val->uid < CSELIB_VAL_PTR (loc)->uid); 327 328 if (CSELIB_VAL_PTR (loc)->locs) 329 { 330 /* Bring all locs from LOC to VAL. */ 331 for (el = CSELIB_VAL_PTR (loc)->locs; el->next; el = el->next) 332 { 333 /* Adjust values that have LOC as canonical so that VAL 334 becomes their canonical. */ 335 if (el->loc && GET_CODE (el->loc) == VALUE) 336 { 337 gcc_checking_assert (CSELIB_VAL_PTR (el->loc)->locs->loc 338 == loc); 339 CSELIB_VAL_PTR (el->loc)->locs->loc = val->val_rtx; 340 } 341 } 342 el->next = val->locs; 343 next = val->locs = CSELIB_VAL_PTR (loc)->locs; 344 } 345 346 if (CSELIB_VAL_PTR (loc)->addr_list) 347 { 348 /* Bring in addr_list into canonical node. */ 349 struct elt_list *last = CSELIB_VAL_PTR (loc)->addr_list; 350 while (last->next) 351 last = last->next; 352 last->next = val->addr_list; 353 val->addr_list = CSELIB_VAL_PTR (loc)->addr_list; 354 CSELIB_VAL_PTR (loc)->addr_list = NULL; 355 } 356 357 if (CSELIB_VAL_PTR (loc)->next_containing_mem != NULL 358 && val->next_containing_mem == NULL) 359 { 360 /* Add VAL to the containing_mem list after LOC. LOC will 361 be removed when we notice it doesn't contain any 362 MEMs. */ 363 val->next_containing_mem = CSELIB_VAL_PTR (loc)->next_containing_mem; 364 CSELIB_VAL_PTR (loc)->next_containing_mem = val; 365 } 366 367 /* Chain LOC back to VAL. */ 368 el = elt_loc_list_pool.allocate (); 369 el->loc = val->val_rtx; 370 el->setting_insn = cselib_current_insn; 371 el->next = NULL; 372 CSELIB_VAL_PTR (loc)->locs = el; 373 } 374 375 el = elt_loc_list_pool.allocate (); 376 el->loc = loc; 377 el->setting_insn = cselib_current_insn; 378 el->next = next; 379 val->locs = el; 380} 381 382/* Promote loc L to a nondebug cselib_current_insn if L is marked as 383 originating from a debug insn, maintaining the debug values 384 count. */ 385 386static inline void 387promote_debug_loc (struct elt_loc_list *l) 388{ 389 if (l && l->setting_insn && DEBUG_INSN_P (l->setting_insn) 390 && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn))) 391 { 392 n_debug_values--; 393 l->setting_insn = cselib_current_insn; 394 if (cselib_preserve_constants && l->next) 395 { 396 gcc_assert (l->next->setting_insn 397 && DEBUG_INSN_P (l->next->setting_insn) 398 && !l->next->next); 399 l->next->setting_insn = cselib_current_insn; 400 } 401 else 402 gcc_assert (!l->next); 403 } 404} 405 406/* The elt_list at *PL is no longer needed. Unchain it and free its 407 storage. */ 408 409static inline void 410unchain_one_elt_list (struct elt_list **pl) 411{ 412 struct elt_list *l = *pl; 413 414 *pl = l->next; 415 elt_list_pool.remove (l); 416} 417 418/* Likewise for elt_loc_lists. */ 419 420static void 421unchain_one_elt_loc_list (struct elt_loc_list **pl) 422{ 423 struct elt_loc_list *l = *pl; 424 425 *pl = l->next; 426 elt_loc_list_pool.remove (l); 427} 428 429/* Likewise for cselib_vals. This also frees the addr_list associated with 430 V. */ 431 432static void 433unchain_one_value (cselib_val *v) 434{ 435 while (v->addr_list) 436 unchain_one_elt_list (&v->addr_list); 437 438 cselib_val_pool.remove (v); 439} 440 441/* Remove all entries from the hash table. Also used during 442 initialization. */ 443 444void 445cselib_clear_table (void) 446{ 447 cselib_reset_table (1); 448} 449 450/* Return TRUE if V is a constant, a function invariant or a VALUE 451 equivalence; FALSE otherwise. */ 452 453static bool 454invariant_or_equiv_p (cselib_val *v) 455{ 456 struct elt_loc_list *l; 457 458 if (v == cfa_base_preserved_val) 459 return true; 460 461 /* Keep VALUE equivalences around. */ 462 for (l = v->locs; l; l = l->next) 463 if (GET_CODE (l->loc) == VALUE) 464 return true; 465 466 if (v->locs != NULL 467 && v->locs->next == NULL) 468 { 469 if (CONSTANT_P (v->locs->loc) 470 && (GET_CODE (v->locs->loc) != CONST 471 || !references_value_p (v->locs->loc, 0))) 472 return true; 473 /* Although a debug expr may be bound to different expressions, 474 we can preserve it as if it was constant, to get unification 475 and proper merging within var-tracking. */ 476 if (GET_CODE (v->locs->loc) == DEBUG_EXPR 477 || GET_CODE (v->locs->loc) == DEBUG_IMPLICIT_PTR 478 || GET_CODE (v->locs->loc) == ENTRY_VALUE 479 || GET_CODE (v->locs->loc) == DEBUG_PARAMETER_REF) 480 return true; 481 482 /* (plus (value V) (const_int C)) is invariant iff V is invariant. */ 483 if (GET_CODE (v->locs->loc) == PLUS 484 && CONST_INT_P (XEXP (v->locs->loc, 1)) 485 && GET_CODE (XEXP (v->locs->loc, 0)) == VALUE 486 && invariant_or_equiv_p (CSELIB_VAL_PTR (XEXP (v->locs->loc, 0)))) 487 return true; 488 } 489 490 return false; 491} 492 493/* Remove from hash table all VALUEs except constants, function 494 invariants and VALUE equivalences. */ 495 496int 497preserve_constants_and_equivs (cselib_val **x, void *info ATTRIBUTE_UNUSED) 498{ 499 cselib_val *v = *x; 500 501 if (invariant_or_equiv_p (v)) 502 { 503 cselib_hasher::key lookup = { 504 GET_MODE (v->val_rtx), v->val_rtx, VOIDmode 505 }; 506 cselib_val **slot 507 = cselib_preserved_hash_table->find_slot_with_hash (&lookup, 508 v->hash, INSERT); 509 gcc_assert (!*slot); 510 *slot = v; 511 } 512 513 cselib_hash_table->clear_slot (x); 514 515 return 1; 516} 517 518/* Remove all entries from the hash table, arranging for the next 519 value to be numbered NUM. */ 520 521void 522cselib_reset_table (unsigned int num) 523{ 524 unsigned int i; 525 526 max_value_regs = 0; 527 528 if (cfa_base_preserved_val) 529 { 530 unsigned int regno = cfa_base_preserved_regno; 531 unsigned int new_used_regs = 0; 532 for (i = 0; i < n_used_regs; i++) 533 if (used_regs[i] == regno) 534 { 535 new_used_regs = 1; 536 continue; 537 } 538 else 539 REG_VALUES (used_regs[i]) = 0; 540 gcc_assert (new_used_regs == 1); 541 n_used_regs = new_used_regs; 542 used_regs[0] = regno; 543 max_value_regs 544 = hard_regno_nregs (regno, 545 GET_MODE (cfa_base_preserved_val->locs->loc)); 546 547 /* If cfa_base is sp + const_int, need to preserve also the 548 SP_DERIVED_VALUE_P value. */ 549 for (struct elt_loc_list *l = cfa_base_preserved_val->locs; 550 l; l = l->next) 551 if (GET_CODE (l->loc) == PLUS 552 && GET_CODE (XEXP (l->loc, 0)) == VALUE 553 && SP_DERIVED_VALUE_P (XEXP (l->loc, 0)) 554 && CONST_INT_P (XEXP (l->loc, 1))) 555 { 556 if (! invariant_or_equiv_p (CSELIB_VAL_PTR (XEXP (l->loc, 0)))) 557 { 558 rtx val = cfa_base_preserved_val->val_rtx; 559 rtx_insn *save_cselib_current_insn = cselib_current_insn; 560 cselib_current_insn = l->setting_insn; 561 new_elt_loc_list (CSELIB_VAL_PTR (XEXP (l->loc, 0)), 562 plus_constant (Pmode, val, 563 -UINTVAL (XEXP (l->loc, 1)))); 564 cselib_current_insn = save_cselib_current_insn; 565 } 566 break; 567 } 568 } 569 else 570 { 571 for (i = 0; i < n_used_regs; i++) 572 REG_VALUES (used_regs[i]) = 0; 573 n_used_regs = 0; 574 } 575 576 if (cselib_preserve_constants) 577 cselib_hash_table->traverse <void *, preserve_constants_and_equivs> (NULL); 578 else 579 { 580 cselib_hash_table->empty (); 581 gcc_checking_assert (!cselib_any_perm_equivs); 582 } 583 584 n_useless_values = 0; 585 n_useless_debug_values = 0; 586 n_debug_values = 0; 587 588 next_uid = num; 589 590 first_containing_mem = &dummy_val; 591} 592 593/* Return the number of the next value that will be generated. */ 594 595unsigned int 596cselib_get_next_uid (void) 597{ 598 return next_uid; 599} 600 601/* Search for X, whose hashcode is HASH, in CSELIB_HASH_TABLE, 602 INSERTing if requested. When X is part of the address of a MEM, 603 MEMMODE should specify the mode of the MEM. */ 604 605static cselib_val ** 606cselib_find_slot (machine_mode mode, rtx x, hashval_t hash, 607 enum insert_option insert, machine_mode memmode) 608{ 609 cselib_val **slot = NULL; 610 cselib_hasher::key lookup = { mode, x, memmode }; 611 if (cselib_preserve_constants) 612 slot = cselib_preserved_hash_table->find_slot_with_hash (&lookup, hash, 613 NO_INSERT); 614 if (!slot) 615 slot = cselib_hash_table->find_slot_with_hash (&lookup, hash, insert); 616 return slot; 617} 618 619/* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we 620 only return true for values which point to a cselib_val whose value 621 element has been set to zero, which implies the cselib_val will be 622 removed. */ 623 624int 625references_value_p (const_rtx x, int only_useless) 626{ 627 const enum rtx_code code = GET_CODE (x); 628 const char *fmt = GET_RTX_FORMAT (code); 629 int i, j; 630 631 if (GET_CODE (x) == VALUE 632 && (! only_useless 633 || (CSELIB_VAL_PTR (x)->locs == 0 && !PRESERVED_VALUE_P (x)))) 634 return 1; 635 636 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 637 { 638 if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless)) 639 return 1; 640 else if (fmt[i] == 'E') 641 for (j = 0; j < XVECLEN (x, i); j++) 642 if (references_value_p (XVECEXP (x, i, j), only_useless)) 643 return 1; 644 } 645 646 return 0; 647} 648 649/* Return true if V is a useless VALUE and can be discarded as such. */ 650 651static bool 652cselib_useless_value_p (cselib_val *v) 653{ 654 return (v->locs == 0 655 && !PRESERVED_VALUE_P (v->val_rtx) 656 && !SP_DERIVED_VALUE_P (v->val_rtx)); 657} 658 659/* For all locations found in X, delete locations that reference useless 660 values (i.e. values without any location). Called through 661 htab_traverse. */ 662 663int 664discard_useless_locs (cselib_val **x, void *info ATTRIBUTE_UNUSED) 665{ 666 cselib_val *v = *x; 667 struct elt_loc_list **p = &v->locs; 668 bool had_locs = v->locs != NULL; 669 rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL; 670 671 while (*p) 672 { 673 if (references_value_p ((*p)->loc, 1)) 674 unchain_one_elt_loc_list (p); 675 else 676 p = &(*p)->next; 677 } 678 679 if (had_locs && cselib_useless_value_p (v)) 680 { 681 if (setting_insn && DEBUG_INSN_P (setting_insn)) 682 n_useless_debug_values++; 683 else 684 n_useless_values++; 685 values_became_useless = 1; 686 } 687 return 1; 688} 689 690/* If X is a value with no locations, remove it from the hashtable. */ 691 692int 693discard_useless_values (cselib_val **x, void *info ATTRIBUTE_UNUSED) 694{ 695 cselib_val *v = *x; 696 697 if (v->locs == 0 && cselib_useless_value_p (v)) 698 { 699 if (cselib_discard_hook) 700 cselib_discard_hook (v); 701 702 CSELIB_VAL_PTR (v->val_rtx) = NULL; 703 cselib_hash_table->clear_slot (x); 704 unchain_one_value (v); 705 n_useless_values--; 706 } 707 708 return 1; 709} 710 711/* Clean out useless values (i.e. those which no longer have locations 712 associated with them) from the hash table. */ 713 714static void 715remove_useless_values (void) 716{ 717 cselib_val **p, *v; 718 719 /* First pass: eliminate locations that reference the value. That in 720 turn can make more values useless. */ 721 do 722 { 723 values_became_useless = 0; 724 cselib_hash_table->traverse <void *, discard_useless_locs> (NULL); 725 } 726 while (values_became_useless); 727 728 /* Second pass: actually remove the values. */ 729 730 p = &first_containing_mem; 731 for (v = *p; v != &dummy_val; v = v->next_containing_mem) 732 if (v->locs && v == canonical_cselib_val (v)) 733 { 734 *p = v; 735 p = &(*p)->next_containing_mem; 736 } 737 *p = &dummy_val; 738 739 n_useless_values += n_useless_debug_values; 740 n_debug_values -= n_useless_debug_values; 741 n_useless_debug_values = 0; 742 743 cselib_hash_table->traverse <void *, discard_useless_values> (NULL); 744 745 gcc_assert (!n_useless_values); 746} 747 748/* Arrange for a value to not be removed from the hash table even if 749 it becomes useless. */ 750 751void 752cselib_preserve_value (cselib_val *v) 753{ 754 PRESERVED_VALUE_P (v->val_rtx) = 1; 755} 756 757/* Test whether a value is preserved. */ 758 759bool 760cselib_preserved_value_p (cselib_val *v) 761{ 762 return PRESERVED_VALUE_P (v->val_rtx); 763} 764 765/* Arrange for a REG value to be assumed constant through the whole function, 766 never invalidated and preserved across cselib_reset_table calls. */ 767 768void 769cselib_preserve_cfa_base_value (cselib_val *v, unsigned int regno) 770{ 771 if (cselib_preserve_constants 772 && v->locs 773 && REG_P (v->locs->loc)) 774 { 775 cfa_base_preserved_val = v; 776 cfa_base_preserved_regno = regno; 777 } 778} 779 780/* Clean all non-constant expressions in the hash table, but retain 781 their values. */ 782 783void 784cselib_preserve_only_values (void) 785{ 786 int i; 787 788 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 789 cselib_invalidate_regno (i, reg_raw_mode[i]); 790 791 cselib_invalidate_mem (callmem); 792 793 remove_useless_values (); 794 795 gcc_assert (first_containing_mem == &dummy_val); 796} 797 798/* Arrange for a value to be marked as based on stack pointer 799 for find_base_term purposes. */ 800 801void 802cselib_set_value_sp_based (cselib_val *v) 803{ 804 SP_BASED_VALUE_P (v->val_rtx) = 1; 805} 806 807/* Test whether a value is based on stack pointer for 808 find_base_term purposes. */ 809 810bool 811cselib_sp_based_value_p (cselib_val *v) 812{ 813 return SP_BASED_VALUE_P (v->val_rtx); 814} 815 816/* Return the mode in which a register was last set. If X is not a 817 register, return its mode. If the mode in which the register was 818 set is not known, or the value was already clobbered, return 819 VOIDmode. */ 820 821machine_mode 822cselib_reg_set_mode (const_rtx x) 823{ 824 if (!REG_P (x)) 825 return GET_MODE (x); 826 827 if (REG_VALUES (REGNO (x)) == NULL 828 || REG_VALUES (REGNO (x))->elt == NULL) 829 return VOIDmode; 830 831 return GET_MODE (REG_VALUES (REGNO (x))->elt->val_rtx); 832} 833 834/* If x is a PLUS or an autoinc operation, expand the operation, 835 storing the offset, if any, in *OFF. */ 836 837static rtx 838autoinc_split (rtx x, rtx *off, machine_mode memmode) 839{ 840 switch (GET_CODE (x)) 841 { 842 case PLUS: 843 *off = XEXP (x, 1); 844 x = XEXP (x, 0); 845 break; 846 847 case PRE_DEC: 848 if (memmode == VOIDmode) 849 return x; 850 851 *off = gen_int_mode (-GET_MODE_SIZE (memmode), GET_MODE (x)); 852 x = XEXP (x, 0); 853 break; 854 855 case PRE_INC: 856 if (memmode == VOIDmode) 857 return x; 858 859 *off = gen_int_mode (GET_MODE_SIZE (memmode), GET_MODE (x)); 860 x = XEXP (x, 0); 861 break; 862 863 case PRE_MODIFY: 864 x = XEXP (x, 1); 865 break; 866 867 case POST_DEC: 868 case POST_INC: 869 case POST_MODIFY: 870 x = XEXP (x, 0); 871 break; 872 873 default: 874 break; 875 } 876 877 if (GET_MODE (x) == Pmode 878 && (REG_P (x) || MEM_P (x) || GET_CODE (x) == VALUE) 879 && (*off == NULL_RTX || CONST_INT_P (*off))) 880 { 881 cselib_val *e; 882 if (GET_CODE (x) == VALUE) 883 e = CSELIB_VAL_PTR (x); 884 else 885 e = cselib_lookup (x, GET_MODE (x), 0, memmode); 886 if (e) 887 { 888 if (SP_DERIVED_VALUE_P (e->val_rtx) 889 && (*off == NULL_RTX || *off == const0_rtx)) 890 { 891 *off = NULL_RTX; 892 return e->val_rtx; 893 } 894 for (struct elt_loc_list *l = e->locs; l; l = l->next) 895 if (GET_CODE (l->loc) == PLUS 896 && GET_CODE (XEXP (l->loc, 0)) == VALUE 897 && SP_DERIVED_VALUE_P (XEXP (l->loc, 0)) 898 && CONST_INT_P (XEXP (l->loc, 1))) 899 { 900 if (*off == NULL_RTX) 901 *off = XEXP (l->loc, 1); 902 else 903 *off = plus_constant (Pmode, *off, 904 INTVAL (XEXP (l->loc, 1))); 905 if (*off == const0_rtx) 906 *off = NULL_RTX; 907 return XEXP (l->loc, 0); 908 } 909 } 910 } 911 return x; 912} 913 914/* Return nonzero if we can prove that X and Y contain the same value, 915 taking our gathered information into account. MEMMODE holds the 916 mode of the enclosing MEM, if any, as required to deal with autoinc 917 addressing modes. If X and Y are not (known to be) part of 918 addresses, MEMMODE should be VOIDmode. */ 919 920int 921rtx_equal_for_cselib_1 (rtx x, rtx y, machine_mode memmode, int depth) 922{ 923 enum rtx_code code; 924 const char *fmt; 925 int i; 926 927 if (REG_P (x) || MEM_P (x)) 928 { 929 cselib_val *e = cselib_lookup (x, GET_MODE (x), 0, memmode); 930 931 if (e) 932 x = e->val_rtx; 933 } 934 935 if (REG_P (y) || MEM_P (y)) 936 { 937 cselib_val *e = cselib_lookup (y, GET_MODE (y), 0, memmode); 938 939 if (e) 940 y = e->val_rtx; 941 } 942 943 if (x == y) 944 return 1; 945 946 if (GET_CODE (x) == VALUE) 947 { 948 cselib_val *e = canonical_cselib_val (CSELIB_VAL_PTR (x)); 949 struct elt_loc_list *l; 950 951 if (GET_CODE (y) == VALUE) 952 return e == canonical_cselib_val (CSELIB_VAL_PTR (y)); 953 954 if ((SP_DERIVED_VALUE_P (x) 955 || SP_DERIVED_VALUE_P (e->val_rtx)) 956 && GET_MODE (y) == Pmode) 957 { 958 rtx yoff = NULL; 959 rtx yr = autoinc_split (y, &yoff, memmode); 960 if ((yr == x || yr == e->val_rtx) && yoff == NULL_RTX) 961 return 1; 962 } 963 964 if (depth == 128) 965 return 0; 966 967 for (l = e->locs; l; l = l->next) 968 { 969 rtx t = l->loc; 970 971 /* Avoid infinite recursion. We know we have the canonical 972 value, so we can just skip any values in the equivalence 973 list. */ 974 if (REG_P (t) || MEM_P (t) || GET_CODE (t) == VALUE) 975 continue; 976 else if (rtx_equal_for_cselib_1 (t, y, memmode, depth + 1)) 977 return 1; 978 } 979 980 return 0; 981 } 982 else if (GET_CODE (y) == VALUE) 983 { 984 cselib_val *e = canonical_cselib_val (CSELIB_VAL_PTR (y)); 985 struct elt_loc_list *l; 986 987 if ((SP_DERIVED_VALUE_P (y) 988 || SP_DERIVED_VALUE_P (e->val_rtx)) 989 && GET_MODE (x) == Pmode) 990 { 991 rtx xoff = NULL; 992 rtx xr = autoinc_split (x, &xoff, memmode); 993 if ((xr == y || xr == e->val_rtx) && xoff == NULL_RTX) 994 return 1; 995 } 996 997 if (depth == 128) 998 return 0; 999 1000 for (l = e->locs; l; l = l->next) 1001 { 1002 rtx t = l->loc; 1003 1004 if (REG_P (t) || MEM_P (t) || GET_CODE (t) == VALUE) 1005 continue; 1006 else if (rtx_equal_for_cselib_1 (x, t, memmode, depth + 1)) 1007 return 1; 1008 } 1009 1010 return 0; 1011 } 1012 1013 if (GET_MODE (x) != GET_MODE (y)) 1014 return 0; 1015 1016 if (GET_CODE (x) != GET_CODE (y) 1017 || (GET_CODE (x) == PLUS 1018 && GET_MODE (x) == Pmode 1019 && CONST_INT_P (XEXP (x, 1)) 1020 && CONST_INT_P (XEXP (y, 1)))) 1021 { 1022 rtx xorig = x, yorig = y; 1023 rtx xoff = NULL, yoff = NULL; 1024 1025 x = autoinc_split (x, &xoff, memmode); 1026 y = autoinc_split (y, &yoff, memmode); 1027 1028 /* Don't recurse if nothing changed. */ 1029 if (x != xorig || y != yorig) 1030 { 1031 if (!xoff != !yoff) 1032 return 0; 1033 1034 if (xoff && !rtx_equal_for_cselib_1 (xoff, yoff, memmode, depth)) 1035 return 0; 1036 1037 return rtx_equal_for_cselib_1 (x, y, memmode, depth); 1038 } 1039 1040 if (GET_CODE (xorig) != GET_CODE (yorig)) 1041 return 0; 1042 } 1043 1044 /* These won't be handled correctly by the code below. */ 1045 switch (GET_CODE (x)) 1046 { 1047 CASE_CONST_UNIQUE: 1048 case DEBUG_EXPR: 1049 return 0; 1050 1051 case CONST_VECTOR: 1052 if (!same_vector_encodings_p (x, y)) 1053 return false; 1054 break; 1055 1056 case DEBUG_IMPLICIT_PTR: 1057 return DEBUG_IMPLICIT_PTR_DECL (x) 1058 == DEBUG_IMPLICIT_PTR_DECL (y); 1059 1060 case DEBUG_PARAMETER_REF: 1061 return DEBUG_PARAMETER_REF_DECL (x) 1062 == DEBUG_PARAMETER_REF_DECL (y); 1063 1064 case ENTRY_VALUE: 1065 /* ENTRY_VALUEs are function invariant, it is thus undesirable to 1066 use rtx_equal_for_cselib_1 to compare the operands. */ 1067 return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y)); 1068 1069 case LABEL_REF: 1070 return label_ref_label (x) == label_ref_label (y); 1071 1072 case REG: 1073 return REGNO (x) == REGNO (y); 1074 1075 case MEM: 1076 /* We have to compare any autoinc operations in the addresses 1077 using this MEM's mode. */ 1078 return rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 0), GET_MODE (x), 1079 depth); 1080 1081 default: 1082 break; 1083 } 1084 1085 code = GET_CODE (x); 1086 fmt = GET_RTX_FORMAT (code); 1087 1088 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1089 { 1090 int j; 1091 1092 switch (fmt[i]) 1093 { 1094 case 'w': 1095 if (XWINT (x, i) != XWINT (y, i)) 1096 return 0; 1097 break; 1098 1099 case 'n': 1100 case 'i': 1101 if (XINT (x, i) != XINT (y, i)) 1102 return 0; 1103 break; 1104 1105 case 'p': 1106 if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y))) 1107 return 0; 1108 break; 1109 1110 case 'V': 1111 case 'E': 1112 /* Two vectors must have the same length. */ 1113 if (XVECLEN (x, i) != XVECLEN (y, i)) 1114 return 0; 1115 1116 /* And the corresponding elements must match. */ 1117 for (j = 0; j < XVECLEN (x, i); j++) 1118 if (! rtx_equal_for_cselib_1 (XVECEXP (x, i, j), 1119 XVECEXP (y, i, j), memmode, depth)) 1120 return 0; 1121 break; 1122 1123 case 'e': 1124 if (i == 1 1125 && targetm.commutative_p (x, UNKNOWN) 1126 && rtx_equal_for_cselib_1 (XEXP (x, 1), XEXP (y, 0), memmode, 1127 depth) 1128 && rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 1), memmode, 1129 depth)) 1130 return 1; 1131 if (! rtx_equal_for_cselib_1 (XEXP (x, i), XEXP (y, i), memmode, 1132 depth)) 1133 return 0; 1134 break; 1135 1136 case 'S': 1137 case 's': 1138 if (strcmp (XSTR (x, i), XSTR (y, i))) 1139 return 0; 1140 break; 1141 1142 case 'u': 1143 /* These are just backpointers, so they don't matter. */ 1144 break; 1145 1146 case '0': 1147 case 't': 1148 break; 1149 1150 /* It is believed that rtx's at this level will never 1151 contain anything but integers and other rtx's, 1152 except for within LABEL_REFs and SYMBOL_REFs. */ 1153 default: 1154 gcc_unreachable (); 1155 } 1156 } 1157 return 1; 1158} 1159 1160/* Helper function for cselib_hash_rtx. Arguments like for cselib_hash_rtx, 1161 except that it hashes (plus:P x c). */ 1162 1163static unsigned int 1164cselib_hash_plus_const_int (rtx x, HOST_WIDE_INT c, int create, 1165 machine_mode memmode) 1166{ 1167 cselib_val *e = cselib_lookup (x, GET_MODE (x), create, memmode); 1168 if (! e) 1169 return 0; 1170 1171 if (! SP_DERIVED_VALUE_P (e->val_rtx)) 1172 for (struct elt_loc_list *l = e->locs; l; l = l->next) 1173 if (GET_CODE (l->loc) == PLUS 1174 && GET_CODE (XEXP (l->loc, 0)) == VALUE 1175 && SP_DERIVED_VALUE_P (XEXP (l->loc, 0)) 1176 && CONST_INT_P (XEXP (l->loc, 1))) 1177 { 1178 e = CSELIB_VAL_PTR (XEXP (l->loc, 0)); 1179 c = trunc_int_for_mode (c + UINTVAL (XEXP (l->loc, 1)), Pmode); 1180 break; 1181 } 1182 if (c == 0) 1183 return e->hash; 1184 1185 unsigned hash = (unsigned) PLUS + (unsigned) GET_MODE (x); 1186 hash += e->hash; 1187 unsigned int tem_hash = (unsigned) CONST_INT + (unsigned) VOIDmode; 1188 tem_hash += ((unsigned) CONST_INT << 7) + (unsigned HOST_WIDE_INT) c; 1189 if (tem_hash == 0) 1190 tem_hash = (unsigned int) CONST_INT; 1191 hash += tem_hash; 1192 return hash ? hash : 1 + (unsigned int) PLUS; 1193} 1194 1195/* Hash an rtx. Return 0 if we couldn't hash the rtx. 1196 For registers and memory locations, we look up their cselib_val structure 1197 and return its VALUE element. 1198 Possible reasons for return 0 are: the object is volatile, or we couldn't 1199 find a register or memory location in the table and CREATE is zero. If 1200 CREATE is nonzero, table elts are created for regs and mem. 1201 N.B. this hash function returns the same hash value for RTXes that 1202 differ only in the order of operands, thus it is suitable for comparisons 1203 that take commutativity into account. 1204 If we wanted to also support associative rules, we'd have to use a different 1205 strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) . 1206 MEMMODE indicates the mode of an enclosing MEM, and it's only 1207 used to compute autoinc values. 1208 We used to have a MODE argument for hashing for CONST_INTs, but that 1209 didn't make sense, since it caused spurious hash differences between 1210 (set (reg:SI 1) (const_int)) 1211 (plus:SI (reg:SI 2) (reg:SI 1)) 1212 and 1213 (plus:SI (reg:SI 2) (const_int)) 1214 If the mode is important in any context, it must be checked specifically 1215 in a comparison anyway, since relying on hash differences is unsafe. */ 1216 1217static unsigned int 1218cselib_hash_rtx (rtx x, int create, machine_mode memmode) 1219{ 1220 cselib_val *e; 1221 poly_int64 offset; 1222 int i, j; 1223 enum rtx_code code; 1224 const char *fmt; 1225 unsigned int hash = 0; 1226 1227 code = GET_CODE (x); 1228 hash += (unsigned) code + (unsigned) GET_MODE (x); 1229 1230 switch (code) 1231 { 1232 case VALUE: 1233 e = CSELIB_VAL_PTR (x); 1234 return e->hash; 1235 1236 case MEM: 1237 case REG: 1238 e = cselib_lookup (x, GET_MODE (x), create, memmode); 1239 if (! e) 1240 return 0; 1241 1242 return e->hash; 1243 1244 case DEBUG_EXPR: 1245 hash += ((unsigned) DEBUG_EXPR << 7) 1246 + DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x)); 1247 return hash ? hash : (unsigned int) DEBUG_EXPR; 1248 1249 case DEBUG_IMPLICIT_PTR: 1250 hash += ((unsigned) DEBUG_IMPLICIT_PTR << 7) 1251 + DECL_UID (DEBUG_IMPLICIT_PTR_DECL (x)); 1252 return hash ? hash : (unsigned int) DEBUG_IMPLICIT_PTR; 1253 1254 case DEBUG_PARAMETER_REF: 1255 hash += ((unsigned) DEBUG_PARAMETER_REF << 7) 1256 + DECL_UID (DEBUG_PARAMETER_REF_DECL (x)); 1257 return hash ? hash : (unsigned int) DEBUG_PARAMETER_REF; 1258 1259 case ENTRY_VALUE: 1260 /* ENTRY_VALUEs are function invariant, thus try to avoid 1261 recursing on argument if ENTRY_VALUE is one of the 1262 forms emitted by expand_debug_expr, otherwise 1263 ENTRY_VALUE hash would depend on the current value 1264 in some register or memory. */ 1265 if (REG_P (ENTRY_VALUE_EXP (x))) 1266 hash += (unsigned int) REG 1267 + (unsigned int) GET_MODE (ENTRY_VALUE_EXP (x)) 1268 + (unsigned int) REGNO (ENTRY_VALUE_EXP (x)); 1269 else if (MEM_P (ENTRY_VALUE_EXP (x)) 1270 && REG_P (XEXP (ENTRY_VALUE_EXP (x), 0))) 1271 hash += (unsigned int) MEM 1272 + (unsigned int) GET_MODE (XEXP (ENTRY_VALUE_EXP (x), 0)) 1273 + (unsigned int) REGNO (XEXP (ENTRY_VALUE_EXP (x), 0)); 1274 else 1275 hash += cselib_hash_rtx (ENTRY_VALUE_EXP (x), create, memmode); 1276 return hash ? hash : (unsigned int) ENTRY_VALUE; 1277 1278 case CONST_INT: 1279 hash += ((unsigned) CONST_INT << 7) + UINTVAL (x); 1280 return hash ? hash : (unsigned int) CONST_INT; 1281 1282 case CONST_WIDE_INT: 1283 for (i = 0; i < CONST_WIDE_INT_NUNITS (x); i++) 1284 hash += CONST_WIDE_INT_ELT (x, i); 1285 return hash; 1286 1287 case CONST_POLY_INT: 1288 { 1289 inchash::hash h; 1290 h.add_int (hash); 1291 for (unsigned int i = 0; i < NUM_POLY_INT_COEFFS; ++i) 1292 h.add_wide_int (CONST_POLY_INT_COEFFS (x)[i]); 1293 return h.end (); 1294 } 1295 1296 case CONST_DOUBLE: 1297 /* This is like the general case, except that it only counts 1298 the integers representing the constant. */ 1299 hash += (unsigned) code + (unsigned) GET_MODE (x); 1300 if (TARGET_SUPPORTS_WIDE_INT == 0 && GET_MODE (x) == VOIDmode) 1301 hash += ((unsigned) CONST_DOUBLE_LOW (x) 1302 + (unsigned) CONST_DOUBLE_HIGH (x)); 1303 else 1304 hash += real_hash (CONST_DOUBLE_REAL_VALUE (x)); 1305 return hash ? hash : (unsigned int) CONST_DOUBLE; 1306 1307 case CONST_FIXED: 1308 hash += (unsigned int) code + (unsigned int) GET_MODE (x); 1309 hash += fixed_hash (CONST_FIXED_VALUE (x)); 1310 return hash ? hash : (unsigned int) CONST_FIXED; 1311 1312 case CONST_VECTOR: 1313 { 1314 int units; 1315 rtx elt; 1316 1317 units = const_vector_encoded_nelts (x); 1318 1319 for (i = 0; i < units; ++i) 1320 { 1321 elt = CONST_VECTOR_ENCODED_ELT (x, i); 1322 hash += cselib_hash_rtx (elt, 0, memmode); 1323 } 1324 1325 return hash; 1326 } 1327 1328 /* Assume there is only one rtx object for any given label. */ 1329 case LABEL_REF: 1330 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap 1331 differences and differences between each stage's debugging dumps. */ 1332 hash += (((unsigned int) LABEL_REF << 7) 1333 + CODE_LABEL_NUMBER (label_ref_label (x))); 1334 return hash ? hash : (unsigned int) LABEL_REF; 1335 1336 case SYMBOL_REF: 1337 { 1338 /* Don't hash on the symbol's address to avoid bootstrap differences. 1339 Different hash values may cause expressions to be recorded in 1340 different orders and thus different registers to be used in the 1341 final assembler. This also avoids differences in the dump files 1342 between various stages. */ 1343 unsigned int h = 0; 1344 const unsigned char *p = (const unsigned char *) XSTR (x, 0); 1345 1346 while (*p) 1347 h += (h << 7) + *p++; /* ??? revisit */ 1348 1349 hash += ((unsigned int) SYMBOL_REF << 7) + h; 1350 return hash ? hash : (unsigned int) SYMBOL_REF; 1351 } 1352 1353 case PRE_DEC: 1354 case PRE_INC: 1355 /* We can't compute these without knowing the MEM mode. */ 1356 gcc_assert (memmode != VOIDmode); 1357 offset = GET_MODE_SIZE (memmode); 1358 if (code == PRE_DEC) 1359 offset = -offset; 1360 /* Adjust the hash so that (mem:MEMMODE (pre_* (reg))) hashes 1361 like (mem:MEMMODE (plus (reg) (const_int I))). */ 1362 if (GET_MODE (x) == Pmode 1363 && (REG_P (XEXP (x, 0)) 1364 || MEM_P (XEXP (x, 0)) 1365 || GET_CODE (XEXP (x, 0)) == VALUE)) 1366 { 1367 HOST_WIDE_INT c; 1368 if (offset.is_constant (&c)) 1369 return cselib_hash_plus_const_int (XEXP (x, 0), 1370 trunc_int_for_mode (c, Pmode), 1371 create, memmode); 1372 } 1373 hash = ((unsigned) PLUS + (unsigned) GET_MODE (x) 1374 + cselib_hash_rtx (XEXP (x, 0), create, memmode) 1375 + cselib_hash_rtx (gen_int_mode (offset, GET_MODE (x)), 1376 create, memmode)); 1377 return hash ? hash : 1 + (unsigned) PLUS; 1378 1379 case PRE_MODIFY: 1380 gcc_assert (memmode != VOIDmode); 1381 return cselib_hash_rtx (XEXP (x, 1), create, memmode); 1382 1383 case POST_DEC: 1384 case POST_INC: 1385 case POST_MODIFY: 1386 gcc_assert (memmode != VOIDmode); 1387 return cselib_hash_rtx (XEXP (x, 0), create, memmode); 1388 1389 case PC: 1390 case CC0: 1391 case CALL: 1392 case UNSPEC_VOLATILE: 1393 return 0; 1394 1395 case ASM_OPERANDS: 1396 if (MEM_VOLATILE_P (x)) 1397 return 0; 1398 1399 break; 1400 1401 case PLUS: 1402 if (GET_MODE (x) == Pmode 1403 && (REG_P (XEXP (x, 0)) 1404 || MEM_P (XEXP (x, 0)) 1405 || GET_CODE (XEXP (x, 0)) == VALUE) 1406 && CONST_INT_P (XEXP (x, 1))) 1407 return cselib_hash_plus_const_int (XEXP (x, 0), INTVAL (XEXP (x, 1)), 1408 create, memmode); 1409 break; 1410 1411 default: 1412 break; 1413 } 1414 1415 i = GET_RTX_LENGTH (code) - 1; 1416 fmt = GET_RTX_FORMAT (code); 1417 for (; i >= 0; i--) 1418 { 1419 switch (fmt[i]) 1420 { 1421 case 'e': 1422 { 1423 rtx tem = XEXP (x, i); 1424 unsigned int tem_hash = cselib_hash_rtx (tem, create, memmode); 1425 1426 if (tem_hash == 0) 1427 return 0; 1428 1429 hash += tem_hash; 1430 } 1431 break; 1432 case 'E': 1433 for (j = 0; j < XVECLEN (x, i); j++) 1434 { 1435 unsigned int tem_hash 1436 = cselib_hash_rtx (XVECEXP (x, i, j), create, memmode); 1437 1438 if (tem_hash == 0) 1439 return 0; 1440 1441 hash += tem_hash; 1442 } 1443 break; 1444 1445 case 's': 1446 { 1447 const unsigned char *p = (const unsigned char *) XSTR (x, i); 1448 1449 if (p) 1450 while (*p) 1451 hash += *p++; 1452 break; 1453 } 1454 1455 case 'i': 1456 hash += XINT (x, i); 1457 break; 1458 1459 case 'p': 1460 hash += constant_lower_bound (SUBREG_BYTE (x)); 1461 break; 1462 1463 case '0': 1464 case 't': 1465 /* unused */ 1466 break; 1467 1468 default: 1469 gcc_unreachable (); 1470 } 1471 } 1472 1473 return hash ? hash : 1 + (unsigned int) GET_CODE (x); 1474} 1475 1476/* Create a new value structure for VALUE and initialize it. The mode of the 1477 value is MODE. */ 1478 1479static inline cselib_val * 1480new_cselib_val (unsigned int hash, machine_mode mode, rtx x) 1481{ 1482 cselib_val *e = cselib_val_pool.allocate (); 1483 1484 gcc_assert (hash); 1485 gcc_assert (next_uid); 1486 1487 e->hash = hash; 1488 e->uid = next_uid++; 1489 /* We use an alloc pool to allocate this RTL construct because it 1490 accounts for about 8% of the overall memory usage. We know 1491 precisely when we can have VALUE RTXen (when cselib is active) 1492 so we don't need to put them in garbage collected memory. 1493 ??? Why should a VALUE be an RTX in the first place? */ 1494 e->val_rtx = (rtx_def*) value_pool.allocate (); 1495 memset (e->val_rtx, 0, RTX_HDR_SIZE); 1496 PUT_CODE (e->val_rtx, VALUE); 1497 PUT_MODE (e->val_rtx, mode); 1498 CSELIB_VAL_PTR (e->val_rtx) = e; 1499 e->addr_list = 0; 1500 e->locs = 0; 1501 e->next_containing_mem = 0; 1502 1503 if (dump_file && (dump_flags & TDF_CSELIB)) 1504 { 1505 fprintf (dump_file, "cselib value %u:%u ", e->uid, hash); 1506 if (flag_dump_noaddr || flag_dump_unnumbered) 1507 fputs ("# ", dump_file); 1508 else 1509 fprintf (dump_file, "%p ", (void*)e); 1510 print_rtl_single (dump_file, x); 1511 fputc ('\n', dump_file); 1512 } 1513 1514 return e; 1515} 1516 1517/* ADDR_ELT is a value that is used as address. MEM_ELT is the value that 1518 contains the data at this address. X is a MEM that represents the 1519 value. Update the two value structures to represent this situation. */ 1520 1521static void 1522add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x) 1523{ 1524 addr_elt = canonical_cselib_val (addr_elt); 1525 mem_elt = canonical_cselib_val (mem_elt); 1526 1527 /* Avoid duplicates. */ 1528 addr_space_t as = MEM_ADDR_SPACE (x); 1529 for (elt_loc_list *l = mem_elt->locs; l; l = l->next) 1530 if (MEM_P (l->loc) 1531 && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt 1532 && MEM_ADDR_SPACE (l->loc) == as) 1533 { 1534 promote_debug_loc (l); 1535 return; 1536 } 1537 1538 addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt); 1539 new_elt_loc_list (mem_elt, 1540 replace_equiv_address_nv (x, addr_elt->val_rtx)); 1541 if (mem_elt->next_containing_mem == NULL) 1542 { 1543 mem_elt->next_containing_mem = first_containing_mem; 1544 first_containing_mem = mem_elt; 1545 } 1546} 1547 1548/* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx. 1549 If CREATE, make a new one if we haven't seen it before. */ 1550 1551static cselib_val * 1552cselib_lookup_mem (rtx x, int create) 1553{ 1554 machine_mode mode = GET_MODE (x); 1555 machine_mode addr_mode; 1556 cselib_val **slot; 1557 cselib_val *addr; 1558 cselib_val *mem_elt; 1559 1560 if (MEM_VOLATILE_P (x) || mode == BLKmode 1561 || !cselib_record_memory 1562 || (FLOAT_MODE_P (mode) && flag_float_store)) 1563 return 0; 1564 1565 addr_mode = GET_MODE (XEXP (x, 0)); 1566 if (addr_mode == VOIDmode) 1567 addr_mode = Pmode; 1568 1569 /* Look up the value for the address. */ 1570 addr = cselib_lookup (XEXP (x, 0), addr_mode, create, mode); 1571 if (! addr) 1572 return 0; 1573 addr = canonical_cselib_val (addr); 1574 1575 /* Find a value that describes a value of our mode at that address. */ 1576 addr_space_t as = MEM_ADDR_SPACE (x); 1577 for (elt_list *l = addr->addr_list; l; l = l->next) 1578 if (GET_MODE (l->elt->val_rtx) == mode) 1579 { 1580 for (elt_loc_list *l2 = l->elt->locs; l2; l2 = l2->next) 1581 if (MEM_P (l2->loc) && MEM_ADDR_SPACE (l2->loc) == as) 1582 { 1583 promote_debug_loc (l->elt->locs); 1584 return l->elt; 1585 } 1586 } 1587 1588 if (! create) 1589 return 0; 1590 1591 mem_elt = new_cselib_val (next_uid, mode, x); 1592 add_mem_for_addr (addr, mem_elt, x); 1593 slot = cselib_find_slot (mode, x, mem_elt->hash, INSERT, VOIDmode); 1594 *slot = mem_elt; 1595 return mem_elt; 1596} 1597 1598/* Search through the possible substitutions in P. We prefer a non reg 1599 substitution because this allows us to expand the tree further. If 1600 we find, just a reg, take the lowest regno. There may be several 1601 non-reg results, we just take the first one because they will all 1602 expand to the same place. */ 1603 1604static rtx 1605expand_loc (struct elt_loc_list *p, struct expand_value_data *evd, 1606 int max_depth) 1607{ 1608 rtx reg_result = NULL; 1609 unsigned int regno = UINT_MAX; 1610 struct elt_loc_list *p_in = p; 1611 1612 for (; p; p = p->next) 1613 { 1614 /* Return these right away to avoid returning stack pointer based 1615 expressions for frame pointer and vice versa, which is something 1616 that would confuse DSE. See the comment in cselib_expand_value_rtx_1 1617 for more details. */ 1618 if (REG_P (p->loc) 1619 && (REGNO (p->loc) == STACK_POINTER_REGNUM 1620 || REGNO (p->loc) == FRAME_POINTER_REGNUM 1621 || REGNO (p->loc) == HARD_FRAME_POINTER_REGNUM 1622 || REGNO (p->loc) == cfa_base_preserved_regno)) 1623 return p->loc; 1624 /* Avoid infinite recursion trying to expand a reg into a 1625 the same reg. */ 1626 if ((REG_P (p->loc)) 1627 && (REGNO (p->loc) < regno) 1628 && !bitmap_bit_p (evd->regs_active, REGNO (p->loc))) 1629 { 1630 reg_result = p->loc; 1631 regno = REGNO (p->loc); 1632 } 1633 /* Avoid infinite recursion and do not try to expand the 1634 value. */ 1635 else if (GET_CODE (p->loc) == VALUE 1636 && CSELIB_VAL_PTR (p->loc)->locs == p_in) 1637 continue; 1638 else if (!REG_P (p->loc)) 1639 { 1640 rtx result, note; 1641 if (dump_file && (dump_flags & TDF_CSELIB)) 1642 { 1643 print_inline_rtx (dump_file, p->loc, 0); 1644 fprintf (dump_file, "\n"); 1645 } 1646 if (GET_CODE (p->loc) == LO_SUM 1647 && GET_CODE (XEXP (p->loc, 1)) == SYMBOL_REF 1648 && p->setting_insn 1649 && (note = find_reg_note (p->setting_insn, REG_EQUAL, NULL_RTX)) 1650 && XEXP (note, 0) == XEXP (p->loc, 1)) 1651 return XEXP (p->loc, 1); 1652 result = cselib_expand_value_rtx_1 (p->loc, evd, max_depth - 1); 1653 if (result) 1654 return result; 1655 } 1656 1657 } 1658 1659 if (regno != UINT_MAX) 1660 { 1661 rtx result; 1662 if (dump_file && (dump_flags & TDF_CSELIB)) 1663 fprintf (dump_file, "r%d\n", regno); 1664 1665 result = cselib_expand_value_rtx_1 (reg_result, evd, max_depth - 1); 1666 if (result) 1667 return result; 1668 } 1669 1670 if (dump_file && (dump_flags & TDF_CSELIB)) 1671 { 1672 if (reg_result) 1673 { 1674 print_inline_rtx (dump_file, reg_result, 0); 1675 fprintf (dump_file, "\n"); 1676 } 1677 else 1678 fprintf (dump_file, "NULL\n"); 1679 } 1680 return reg_result; 1681} 1682 1683 1684/* Forward substitute and expand an expression out to its roots. 1685 This is the opposite of common subexpression. Because local value 1686 numbering is such a weak optimization, the expanded expression is 1687 pretty much unique (not from a pointer equals point of view but 1688 from a tree shape point of view. 1689 1690 This function returns NULL if the expansion fails. The expansion 1691 will fail if there is no value number for one of the operands or if 1692 one of the operands has been overwritten between the current insn 1693 and the beginning of the basic block. For instance x has no 1694 expansion in: 1695 1696 r1 <- r1 + 3 1697 x <- r1 + 8 1698 1699 REGS_ACTIVE is a scratch bitmap that should be clear when passing in. 1700 It is clear on return. */ 1701 1702rtx 1703cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth) 1704{ 1705 struct expand_value_data evd; 1706 1707 evd.regs_active = regs_active; 1708 evd.callback = NULL; 1709 evd.callback_arg = NULL; 1710 evd.dummy = false; 1711 1712 return cselib_expand_value_rtx_1 (orig, &evd, max_depth); 1713} 1714 1715/* Same as cselib_expand_value_rtx, but using a callback to try to 1716 resolve some expressions. The CB function should return ORIG if it 1717 can't or does not want to deal with a certain RTX. Any other 1718 return value, including NULL, will be used as the expansion for 1719 VALUE, without any further changes. */ 1720 1721rtx 1722cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth, 1723 cselib_expand_callback cb, void *data) 1724{ 1725 struct expand_value_data evd; 1726 1727 evd.regs_active = regs_active; 1728 evd.callback = cb; 1729 evd.callback_arg = data; 1730 evd.dummy = false; 1731 1732 return cselib_expand_value_rtx_1 (orig, &evd, max_depth); 1733} 1734 1735/* Similar to cselib_expand_value_rtx_cb, but no rtxs are actually copied 1736 or simplified. Useful to find out whether cselib_expand_value_rtx_cb 1737 would return NULL or non-NULL, without allocating new rtx. */ 1738 1739bool 1740cselib_dummy_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth, 1741 cselib_expand_callback cb, void *data) 1742{ 1743 struct expand_value_data evd; 1744 1745 evd.regs_active = regs_active; 1746 evd.callback = cb; 1747 evd.callback_arg = data; 1748 evd.dummy = true; 1749 1750 return cselib_expand_value_rtx_1 (orig, &evd, max_depth) != NULL; 1751} 1752 1753/* Internal implementation of cselib_expand_value_rtx and 1754 cselib_expand_value_rtx_cb. */ 1755 1756static rtx 1757cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd, 1758 int max_depth) 1759{ 1760 rtx copy, scopy; 1761 int i, j; 1762 RTX_CODE code; 1763 const char *format_ptr; 1764 machine_mode mode; 1765 1766 code = GET_CODE (orig); 1767 1768 /* For the context of dse, if we end up expand into a huge tree, we 1769 will not have a useful address, so we might as well just give up 1770 quickly. */ 1771 if (max_depth <= 0) 1772 return NULL; 1773 1774 switch (code) 1775 { 1776 case REG: 1777 { 1778 struct elt_list *l = REG_VALUES (REGNO (orig)); 1779 1780 if (l && l->elt == NULL) 1781 l = l->next; 1782 for (; l; l = l->next) 1783 if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig)) 1784 { 1785 rtx result; 1786 unsigned regno = REGNO (orig); 1787 1788 /* The only thing that we are not willing to do (this 1789 is requirement of dse and if others potential uses 1790 need this function we should add a parm to control 1791 it) is that we will not substitute the 1792 STACK_POINTER_REGNUM, FRAME_POINTER or the 1793 HARD_FRAME_POINTER. 1794 1795 These expansions confuses the code that notices that 1796 stores into the frame go dead at the end of the 1797 function and that the frame is not effected by calls 1798 to subroutines. If you allow the 1799 STACK_POINTER_REGNUM substitution, then dse will 1800 think that parameter pushing also goes dead which is 1801 wrong. If you allow the FRAME_POINTER or the 1802 HARD_FRAME_POINTER then you lose the opportunity to 1803 make the frame assumptions. */ 1804 if (regno == STACK_POINTER_REGNUM 1805 || regno == FRAME_POINTER_REGNUM 1806 || regno == HARD_FRAME_POINTER_REGNUM 1807 || regno == cfa_base_preserved_regno) 1808 return orig; 1809 1810 bitmap_set_bit (evd->regs_active, regno); 1811 1812 if (dump_file && (dump_flags & TDF_CSELIB)) 1813 fprintf (dump_file, "expanding: r%d into: ", regno); 1814 1815 result = expand_loc (l->elt->locs, evd, max_depth); 1816 bitmap_clear_bit (evd->regs_active, regno); 1817 1818 if (result) 1819 return result; 1820 else 1821 return orig; 1822 } 1823 return orig; 1824 } 1825 1826 CASE_CONST_ANY: 1827 case SYMBOL_REF: 1828 case CODE_LABEL: 1829 case PC: 1830 case CC0: 1831 case SCRATCH: 1832 /* SCRATCH must be shared because they represent distinct values. */ 1833 return orig; 1834 case CLOBBER: 1835 if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0)))) 1836 return orig; 1837 break; 1838 1839 case CONST: 1840 if (shared_const_p (orig)) 1841 return orig; 1842 break; 1843 1844 case SUBREG: 1845 { 1846 rtx subreg; 1847 1848 if (evd->callback) 1849 { 1850 subreg = evd->callback (orig, evd->regs_active, max_depth, 1851 evd->callback_arg); 1852 if (subreg != orig) 1853 return subreg; 1854 } 1855 1856 subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd, 1857 max_depth - 1); 1858 if (!subreg) 1859 return NULL; 1860 scopy = simplify_gen_subreg (GET_MODE (orig), subreg, 1861 GET_MODE (SUBREG_REG (orig)), 1862 SUBREG_BYTE (orig)); 1863 if (scopy == NULL 1864 || (GET_CODE (scopy) == SUBREG 1865 && !REG_P (SUBREG_REG (scopy)) 1866 && !MEM_P (SUBREG_REG (scopy)))) 1867 return NULL; 1868 1869 return scopy; 1870 } 1871 1872 case VALUE: 1873 { 1874 rtx result; 1875 1876 if (dump_file && (dump_flags & TDF_CSELIB)) 1877 { 1878 fputs ("\nexpanding ", dump_file); 1879 print_rtl_single (dump_file, orig); 1880 fputs (" into...", dump_file); 1881 } 1882 1883 if (evd->callback) 1884 { 1885 result = evd->callback (orig, evd->regs_active, max_depth, 1886 evd->callback_arg); 1887 1888 if (result != orig) 1889 return result; 1890 } 1891 1892 result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth); 1893 return result; 1894 } 1895 1896 case DEBUG_EXPR: 1897 if (evd->callback) 1898 return evd->callback (orig, evd->regs_active, max_depth, 1899 evd->callback_arg); 1900 return orig; 1901 1902 default: 1903 break; 1904 } 1905 1906 /* Copy the various flags, fields, and other information. We assume 1907 that all fields need copying, and then clear the fields that should 1908 not be copied. That is the sensible default behavior, and forces 1909 us to explicitly document why we are *not* copying a flag. */ 1910 if (evd->dummy) 1911 copy = NULL; 1912 else 1913 copy = shallow_copy_rtx (orig); 1914 1915 format_ptr = GET_RTX_FORMAT (code); 1916 1917 for (i = 0; i < GET_RTX_LENGTH (code); i++) 1918 switch (*format_ptr++) 1919 { 1920 case 'e': 1921 if (XEXP (orig, i) != NULL) 1922 { 1923 rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd, 1924 max_depth - 1); 1925 if (!result) 1926 return NULL; 1927 if (copy) 1928 XEXP (copy, i) = result; 1929 } 1930 break; 1931 1932 case 'E': 1933 case 'V': 1934 if (XVEC (orig, i) != NULL) 1935 { 1936 if (copy) 1937 XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i)); 1938 for (j = 0; j < XVECLEN (orig, i); j++) 1939 { 1940 rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j), 1941 evd, max_depth - 1); 1942 if (!result) 1943 return NULL; 1944 if (copy) 1945 XVECEXP (copy, i, j) = result; 1946 } 1947 } 1948 break; 1949 1950 case 't': 1951 case 'w': 1952 case 'i': 1953 case 's': 1954 case 'S': 1955 case 'T': 1956 case 'u': 1957 case 'B': 1958 case '0': 1959 /* These are left unchanged. */ 1960 break; 1961 1962 default: 1963 gcc_unreachable (); 1964 } 1965 1966 if (evd->dummy) 1967 return orig; 1968 1969 mode = GET_MODE (copy); 1970 /* If an operand has been simplified into CONST_INT, which doesn't 1971 have a mode and the mode isn't derivable from whole rtx's mode, 1972 try simplify_*_operation first with mode from original's operand 1973 and as a fallback wrap CONST_INT into gen_rtx_CONST. */ 1974 scopy = copy; 1975 switch (GET_RTX_CLASS (code)) 1976 { 1977 case RTX_UNARY: 1978 if (CONST_INT_P (XEXP (copy, 0)) 1979 && GET_MODE (XEXP (orig, 0)) != VOIDmode) 1980 { 1981 scopy = simplify_unary_operation (code, mode, XEXP (copy, 0), 1982 GET_MODE (XEXP (orig, 0))); 1983 if (scopy) 1984 return scopy; 1985 } 1986 break; 1987 case RTX_COMM_ARITH: 1988 case RTX_BIN_ARITH: 1989 /* These expressions can derive operand modes from the whole rtx's mode. */ 1990 break; 1991 case RTX_TERNARY: 1992 case RTX_BITFIELD_OPS: 1993 if (CONST_INT_P (XEXP (copy, 0)) 1994 && GET_MODE (XEXP (orig, 0)) != VOIDmode) 1995 { 1996 scopy = simplify_ternary_operation (code, mode, 1997 GET_MODE (XEXP (orig, 0)), 1998 XEXP (copy, 0), XEXP (copy, 1), 1999 XEXP (copy, 2)); 2000 if (scopy) 2001 return scopy; 2002 } 2003 break; 2004 case RTX_COMPARE: 2005 case RTX_COMM_COMPARE: 2006 if (CONST_INT_P (XEXP (copy, 0)) 2007 && GET_MODE (XEXP (copy, 1)) == VOIDmode 2008 && (GET_MODE (XEXP (orig, 0)) != VOIDmode 2009 || GET_MODE (XEXP (orig, 1)) != VOIDmode)) 2010 { 2011 scopy = simplify_relational_operation (code, mode, 2012 (GET_MODE (XEXP (orig, 0)) 2013 != VOIDmode) 2014 ? GET_MODE (XEXP (orig, 0)) 2015 : GET_MODE (XEXP (orig, 1)), 2016 XEXP (copy, 0), 2017 XEXP (copy, 1)); 2018 if (scopy) 2019 return scopy; 2020 } 2021 break; 2022 default: 2023 break; 2024 } 2025 scopy = simplify_rtx (copy); 2026 if (scopy) 2027 return scopy; 2028 return copy; 2029} 2030 2031/* Walk rtx X and replace all occurrences of REG and MEM subexpressions 2032 with VALUE expressions. This way, it becomes independent of changes 2033 to registers and memory. 2034 X isn't actually modified; if modifications are needed, new rtl is 2035 allocated. However, the return value can share rtl with X. 2036 If X is within a MEM, MEMMODE must be the mode of the MEM. */ 2037 2038rtx 2039cselib_subst_to_values (rtx x, machine_mode memmode) 2040{ 2041 enum rtx_code code = GET_CODE (x); 2042 const char *fmt = GET_RTX_FORMAT (code); 2043 cselib_val *e; 2044 struct elt_list *l; 2045 rtx copy = x; 2046 int i; 2047 poly_int64 offset; 2048 2049 switch (code) 2050 { 2051 case REG: 2052 l = REG_VALUES (REGNO (x)); 2053 if (l && l->elt == NULL) 2054 l = l->next; 2055 for (; l; l = l->next) 2056 if (GET_MODE (l->elt->val_rtx) == GET_MODE (x)) 2057 return l->elt->val_rtx; 2058 2059 gcc_unreachable (); 2060 2061 case MEM: 2062 e = cselib_lookup_mem (x, 0); 2063 /* This used to happen for autoincrements, but we deal with them 2064 properly now. Remove the if stmt for the next release. */ 2065 if (! e) 2066 { 2067 /* Assign a value that doesn't match any other. */ 2068 e = new_cselib_val (next_uid, GET_MODE (x), x); 2069 } 2070 return e->val_rtx; 2071 2072 case ENTRY_VALUE: 2073 e = cselib_lookup (x, GET_MODE (x), 0, memmode); 2074 if (! e) 2075 break; 2076 return e->val_rtx; 2077 2078 CASE_CONST_ANY: 2079 return x; 2080 2081 case PRE_DEC: 2082 case PRE_INC: 2083 gcc_assert (memmode != VOIDmode); 2084 offset = GET_MODE_SIZE (memmode); 2085 if (code == PRE_DEC) 2086 offset = -offset; 2087 return cselib_subst_to_values (plus_constant (GET_MODE (x), 2088 XEXP (x, 0), offset), 2089 memmode); 2090 2091 case PRE_MODIFY: 2092 gcc_assert (memmode != VOIDmode); 2093 return cselib_subst_to_values (XEXP (x, 1), memmode); 2094 2095 case POST_DEC: 2096 case POST_INC: 2097 case POST_MODIFY: 2098 gcc_assert (memmode != VOIDmode); 2099 return cselib_subst_to_values (XEXP (x, 0), memmode); 2100 2101 case PLUS: 2102 if (GET_MODE (x) == Pmode && CONST_INT_P (XEXP (x, 1))) 2103 { 2104 rtx t = cselib_subst_to_values (XEXP (x, 0), memmode); 2105 if (GET_CODE (t) == VALUE) 2106 { 2107 if (SP_DERIVED_VALUE_P (t) && XEXP (x, 1) == const0_rtx) 2108 return t; 2109 for (struct elt_loc_list *l = CSELIB_VAL_PTR (t)->locs; 2110 l; l = l->next) 2111 if (GET_CODE (l->loc) == PLUS 2112 && GET_CODE (XEXP (l->loc, 0)) == VALUE 2113 && SP_DERIVED_VALUE_P (XEXP (l->loc, 0)) 2114 && CONST_INT_P (XEXP (l->loc, 1))) 2115 return plus_constant (Pmode, l->loc, INTVAL (XEXP (x, 1))); 2116 } 2117 if (t != XEXP (x, 0)) 2118 { 2119 copy = shallow_copy_rtx (x); 2120 XEXP (copy, 0) = t; 2121 } 2122 return copy; 2123 } 2124 2125 default: 2126 break; 2127 } 2128 2129 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2130 { 2131 if (fmt[i] == 'e') 2132 { 2133 rtx t = cselib_subst_to_values (XEXP (x, i), memmode); 2134 2135 if (t != XEXP (x, i)) 2136 { 2137 if (x == copy) 2138 copy = shallow_copy_rtx (x); 2139 XEXP (copy, i) = t; 2140 } 2141 } 2142 else if (fmt[i] == 'E') 2143 { 2144 int j; 2145 2146 for (j = 0; j < XVECLEN (x, i); j++) 2147 { 2148 rtx t = cselib_subst_to_values (XVECEXP (x, i, j), memmode); 2149 2150 if (t != XVECEXP (x, i, j)) 2151 { 2152 if (XVEC (x, i) == XVEC (copy, i)) 2153 { 2154 if (x == copy) 2155 copy = shallow_copy_rtx (x); 2156 XVEC (copy, i) = shallow_copy_rtvec (XVEC (x, i)); 2157 } 2158 XVECEXP (copy, i, j) = t; 2159 } 2160 } 2161 } 2162 } 2163 2164 return copy; 2165} 2166 2167/* Wrapper for cselib_subst_to_values, that indicates X is in INSN. */ 2168 2169rtx 2170cselib_subst_to_values_from_insn (rtx x, machine_mode memmode, rtx_insn *insn) 2171{ 2172 rtx ret; 2173 gcc_assert (!cselib_current_insn); 2174 cselib_current_insn = insn; 2175 ret = cselib_subst_to_values (x, memmode); 2176 cselib_current_insn = NULL; 2177 return ret; 2178} 2179 2180/* Look up the rtl expression X in our tables and return the value it 2181 has. If CREATE is zero, we return NULL if we don't know the value. 2182 Otherwise, we create a new one if possible, using mode MODE if X 2183 doesn't have a mode (i.e. because it's a constant). When X is part 2184 of an address, MEMMODE should be the mode of the enclosing MEM if 2185 we're tracking autoinc expressions. */ 2186 2187static cselib_val * 2188cselib_lookup_1 (rtx x, machine_mode mode, 2189 int create, machine_mode memmode) 2190{ 2191 cselib_val **slot; 2192 cselib_val *e; 2193 unsigned int hashval; 2194 2195 if (GET_MODE (x) != VOIDmode) 2196 mode = GET_MODE (x); 2197 2198 if (GET_CODE (x) == VALUE) 2199 return CSELIB_VAL_PTR (x); 2200 2201 if (REG_P (x)) 2202 { 2203 struct elt_list *l; 2204 unsigned int i = REGNO (x); 2205 2206 l = REG_VALUES (i); 2207 if (l && l->elt == NULL) 2208 l = l->next; 2209 for (; l; l = l->next) 2210 if (mode == GET_MODE (l->elt->val_rtx)) 2211 { 2212 promote_debug_loc (l->elt->locs); 2213 return l->elt; 2214 } 2215 2216 if (! create) 2217 return 0; 2218 2219 if (i < FIRST_PSEUDO_REGISTER) 2220 { 2221 unsigned int n = hard_regno_nregs (i, mode); 2222 2223 if (n > max_value_regs) 2224 max_value_regs = n; 2225 } 2226 2227 e = new_cselib_val (next_uid, GET_MODE (x), x); 2228 if (GET_MODE (x) == Pmode && x == stack_pointer_rtx) 2229 SP_DERIVED_VALUE_P (e->val_rtx) = 1; 2230 new_elt_loc_list (e, x); 2231 2232 scalar_int_mode int_mode; 2233 if (REG_VALUES (i) == 0) 2234 { 2235 /* Maintain the invariant that the first entry of 2236 REG_VALUES, if present, must be the value used to set the 2237 register, or NULL. */ 2238 used_regs[n_used_regs++] = i; 2239 REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL); 2240 } 2241 else if (cselib_preserve_constants 2242 && is_int_mode (mode, &int_mode)) 2243 { 2244 /* During var-tracking, try harder to find equivalences 2245 for SUBREGs. If a setter sets say a DImode register 2246 and user uses that register only in SImode, add a lowpart 2247 subreg location. */ 2248 struct elt_list *lwider = NULL; 2249 scalar_int_mode lmode; 2250 l = REG_VALUES (i); 2251 if (l && l->elt == NULL) 2252 l = l->next; 2253 for (; l; l = l->next) 2254 if (is_int_mode (GET_MODE (l->elt->val_rtx), &lmode) 2255 && GET_MODE_SIZE (lmode) > GET_MODE_SIZE (int_mode) 2256 && (lwider == NULL 2257 || partial_subreg_p (lmode, 2258 GET_MODE (lwider->elt->val_rtx)))) 2259 { 2260 struct elt_loc_list *el; 2261 if (i < FIRST_PSEUDO_REGISTER 2262 && hard_regno_nregs (i, lmode) != 1) 2263 continue; 2264 for (el = l->elt->locs; el; el = el->next) 2265 if (!REG_P (el->loc)) 2266 break; 2267 if (el) 2268 lwider = l; 2269 } 2270 if (lwider) 2271 { 2272 rtx sub = lowpart_subreg (int_mode, lwider->elt->val_rtx, 2273 GET_MODE (lwider->elt->val_rtx)); 2274 if (sub) 2275 new_elt_loc_list (e, sub); 2276 } 2277 } 2278 REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e); 2279 slot = cselib_find_slot (mode, x, e->hash, INSERT, memmode); 2280 *slot = e; 2281 return e; 2282 } 2283 2284 if (MEM_P (x)) 2285 return cselib_lookup_mem (x, create); 2286 2287 hashval = cselib_hash_rtx (x, create, memmode); 2288 /* Can't even create if hashing is not possible. */ 2289 if (! hashval) 2290 return 0; 2291 2292 slot = cselib_find_slot (mode, x, hashval, 2293 create ? INSERT : NO_INSERT, memmode); 2294 if (slot == 0) 2295 return 0; 2296 2297 e = (cselib_val *) *slot; 2298 if (e) 2299 return e; 2300 2301 e = new_cselib_val (hashval, mode, x); 2302 2303 /* We have to fill the slot before calling cselib_subst_to_values: 2304 the hash table is inconsistent until we do so, and 2305 cselib_subst_to_values will need to do lookups. */ 2306 *slot = e; 2307 rtx v = cselib_subst_to_values (x, memmode); 2308 2309 /* If cselib_preserve_constants, we might get a SP_DERIVED_VALUE_P 2310 VALUE that isn't in the hash tables anymore. */ 2311 if (GET_CODE (v) == VALUE && SP_DERIVED_VALUE_P (v) && PRESERVED_VALUE_P (v)) 2312 PRESERVED_VALUE_P (e->val_rtx) = 1; 2313 2314 new_elt_loc_list (e, v); 2315 return e; 2316} 2317 2318/* Wrapper for cselib_lookup, that indicates X is in INSN. */ 2319 2320cselib_val * 2321cselib_lookup_from_insn (rtx x, machine_mode mode, 2322 int create, machine_mode memmode, rtx_insn *insn) 2323{ 2324 cselib_val *ret; 2325 2326 gcc_assert (!cselib_current_insn); 2327 cselib_current_insn = insn; 2328 2329 ret = cselib_lookup (x, mode, create, memmode); 2330 2331 cselib_current_insn = NULL; 2332 2333 return ret; 2334} 2335 2336/* Wrapper for cselib_lookup_1, that logs the lookup result and 2337 maintains invariants related with debug insns. */ 2338 2339cselib_val * 2340cselib_lookup (rtx x, machine_mode mode, 2341 int create, machine_mode memmode) 2342{ 2343 cselib_val *ret = cselib_lookup_1 (x, mode, create, memmode); 2344 2345 /* ??? Should we return NULL if we're not to create an entry, the 2346 found loc is a debug loc and cselib_current_insn is not DEBUG? 2347 If so, we should also avoid converting val to non-DEBUG; probably 2348 easiest setting cselib_current_insn to NULL before the call 2349 above. */ 2350 2351 if (dump_file && (dump_flags & TDF_CSELIB)) 2352 { 2353 fputs ("cselib lookup ", dump_file); 2354 print_inline_rtx (dump_file, x, 2); 2355 fprintf (dump_file, " => %u:%u\n", 2356 ret ? ret->uid : 0, 2357 ret ? ret->hash : 0); 2358 } 2359 2360 return ret; 2361} 2362 2363/* Invalidate the value at *L, which is part of REG_VALUES (REGNO). */ 2364 2365static void 2366cselib_invalidate_regno_val (unsigned int regno, struct elt_list **l) 2367{ 2368 cselib_val *v = (*l)->elt; 2369 if (*l == REG_VALUES (regno)) 2370 { 2371 /* Maintain the invariant that the first entry of 2372 REG_VALUES, if present, must be the value used to set 2373 the register, or NULL. This is also nice because 2374 then we won't push the same regno onto user_regs 2375 multiple times. */ 2376 (*l)->elt = NULL; 2377 l = &(*l)->next; 2378 } 2379 else 2380 unchain_one_elt_list (l); 2381 2382 v = canonical_cselib_val (v); 2383 2384 bool had_locs = v->locs != NULL; 2385 rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL; 2386 2387 /* Now, we clear the mapping from value to reg. It must exist, so 2388 this code will crash intentionally if it doesn't. */ 2389 for (elt_loc_list **p = &v->locs; ; p = &(*p)->next) 2390 { 2391 rtx x = (*p)->loc; 2392 2393 if (REG_P (x) && REGNO (x) == regno) 2394 { 2395 unchain_one_elt_loc_list (p); 2396 break; 2397 } 2398 } 2399 2400 if (had_locs && cselib_useless_value_p (v)) 2401 { 2402 if (setting_insn && DEBUG_INSN_P (setting_insn)) 2403 n_useless_debug_values++; 2404 else 2405 n_useless_values++; 2406 } 2407} 2408 2409/* Invalidate any entries in reg_values that overlap REGNO. This is called 2410 if REGNO is changing. MODE is the mode of the assignment to REGNO, which 2411 is used to determine how many hard registers are being changed. If MODE 2412 is VOIDmode, then only REGNO is being changed; this is used when 2413 invalidating call clobbered registers across a call. */ 2414 2415static void 2416cselib_invalidate_regno (unsigned int regno, machine_mode mode) 2417{ 2418 unsigned int endregno; 2419 unsigned int i; 2420 2421 /* If we see pseudos after reload, something is _wrong_. */ 2422 gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER 2423 || reg_renumber[regno] < 0); 2424 2425 /* Determine the range of registers that must be invalidated. For 2426 pseudos, only REGNO is affected. For hard regs, we must take MODE 2427 into account, and we must also invalidate lower register numbers 2428 if they contain values that overlap REGNO. */ 2429 if (regno < FIRST_PSEUDO_REGISTER) 2430 { 2431 gcc_assert (mode != VOIDmode); 2432 2433 if (regno < max_value_regs) 2434 i = 0; 2435 else 2436 i = regno - max_value_regs; 2437 2438 endregno = end_hard_regno (mode, regno); 2439 } 2440 else 2441 { 2442 i = regno; 2443 endregno = regno + 1; 2444 } 2445 2446 for (; i < endregno; i++) 2447 { 2448 struct elt_list **l = ®_VALUES (i); 2449 2450 /* Go through all known values for this reg; if it overlaps the range 2451 we're invalidating, remove the value. */ 2452 while (*l) 2453 { 2454 cselib_val *v = (*l)->elt; 2455 unsigned int this_last = i; 2456 2457 if (i < FIRST_PSEUDO_REGISTER && v != NULL) 2458 this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1; 2459 2460 if (this_last < regno || v == NULL 2461 || (v == cfa_base_preserved_val 2462 && i == cfa_base_preserved_regno)) 2463 { 2464 l = &(*l)->next; 2465 continue; 2466 } 2467 2468 /* We have an overlap. */ 2469 cselib_invalidate_regno_val (i, l); 2470 } 2471 } 2472} 2473 2474/* Invalidate any locations in the table which are changed because of a 2475 store to MEM_RTX. If this is called because of a non-const call 2476 instruction, MEM_RTX is (mem:BLK const0_rtx). */ 2477 2478static void 2479cselib_invalidate_mem (rtx mem_rtx) 2480{ 2481 cselib_val **vp, *v, *next; 2482 int num_mems = 0; 2483 rtx mem_addr; 2484 2485 mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0))); 2486 mem_rtx = canon_rtx (mem_rtx); 2487 2488 vp = &first_containing_mem; 2489 for (v = *vp; v != &dummy_val; v = next) 2490 { 2491 bool has_mem = false; 2492 struct elt_loc_list **p = &v->locs; 2493 bool had_locs = v->locs != NULL; 2494 rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL; 2495 2496 while (*p) 2497 { 2498 rtx x = (*p)->loc; 2499 cselib_val *addr; 2500 struct elt_list **mem_chain; 2501 2502 /* MEMs may occur in locations only at the top level; below 2503 that every MEM or REG is substituted by its VALUE. */ 2504 if (!MEM_P (x)) 2505 { 2506 p = &(*p)->next; 2507 continue; 2508 } 2509 if (num_mems < param_max_cselib_memory_locations 2510 && ! canon_anti_dependence (x, false, mem_rtx, 2511 GET_MODE (mem_rtx), mem_addr)) 2512 { 2513 has_mem = true; 2514 num_mems++; 2515 p = &(*p)->next; 2516 continue; 2517 } 2518 2519 /* This one overlaps. */ 2520 /* We must have a mapping from this MEM's address to the 2521 value (E). Remove that, too. */ 2522 addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0, GET_MODE (x)); 2523 addr = canonical_cselib_val (addr); 2524 gcc_checking_assert (v == canonical_cselib_val (v)); 2525 mem_chain = &addr->addr_list; 2526 for (;;) 2527 { 2528 cselib_val *canon = canonical_cselib_val ((*mem_chain)->elt); 2529 2530 if (canon == v) 2531 { 2532 unchain_one_elt_list (mem_chain); 2533 break; 2534 } 2535 2536 /* Record canonicalized elt. */ 2537 (*mem_chain)->elt = canon; 2538 2539 mem_chain = &(*mem_chain)->next; 2540 } 2541 2542 unchain_one_elt_loc_list (p); 2543 } 2544 2545 if (had_locs && cselib_useless_value_p (v)) 2546 { 2547 if (setting_insn && DEBUG_INSN_P (setting_insn)) 2548 n_useless_debug_values++; 2549 else 2550 n_useless_values++; 2551 } 2552 2553 next = v->next_containing_mem; 2554 if (has_mem) 2555 { 2556 *vp = v; 2557 vp = &(*vp)->next_containing_mem; 2558 } 2559 else 2560 v->next_containing_mem = NULL; 2561 } 2562 *vp = &dummy_val; 2563} 2564 2565/* Invalidate DEST. */ 2566 2567void 2568cselib_invalidate_rtx (rtx dest) 2569{ 2570 while (GET_CODE (dest) == SUBREG 2571 || GET_CODE (dest) == ZERO_EXTRACT 2572 || GET_CODE (dest) == STRICT_LOW_PART) 2573 dest = XEXP (dest, 0); 2574 2575 if (REG_P (dest)) 2576 cselib_invalidate_regno (REGNO (dest), GET_MODE (dest)); 2577 else if (MEM_P (dest)) 2578 cselib_invalidate_mem (dest); 2579} 2580 2581/* A wrapper for cselib_invalidate_rtx to be called via note_stores. */ 2582 2583static void 2584cselib_invalidate_rtx_note_stores (rtx dest, const_rtx, 2585 void *data ATTRIBUTE_UNUSED) 2586{ 2587 cselib_invalidate_rtx (dest); 2588} 2589 2590/* Record the result of a SET instruction. DEST is being set; the source 2591 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT 2592 describes its address. */ 2593 2594static void 2595cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt) 2596{ 2597 if (src_elt == 0 || side_effects_p (dest)) 2598 return; 2599 2600 if (REG_P (dest)) 2601 { 2602 unsigned int dreg = REGNO (dest); 2603 if (dreg < FIRST_PSEUDO_REGISTER) 2604 { 2605 unsigned int n = REG_NREGS (dest); 2606 2607 if (n > max_value_regs) 2608 max_value_regs = n; 2609 } 2610 2611 if (REG_VALUES (dreg) == 0) 2612 { 2613 used_regs[n_used_regs++] = dreg; 2614 REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt); 2615 } 2616 else 2617 { 2618 /* The register should have been invalidated. */ 2619 gcc_assert (REG_VALUES (dreg)->elt == 0); 2620 REG_VALUES (dreg)->elt = src_elt; 2621 } 2622 2623 if (cselib_useless_value_p (src_elt)) 2624 n_useless_values--; 2625 new_elt_loc_list (src_elt, dest); 2626 } 2627 else if (MEM_P (dest) && dest_addr_elt != 0 2628 && cselib_record_memory) 2629 { 2630 if (cselib_useless_value_p (src_elt)) 2631 n_useless_values--; 2632 add_mem_for_addr (dest_addr_elt, src_elt, dest); 2633 } 2634} 2635 2636/* Make ELT and X's VALUE equivalent to each other at INSN. */ 2637 2638void 2639cselib_add_permanent_equiv (cselib_val *elt, rtx x, rtx_insn *insn) 2640{ 2641 cselib_val *nelt; 2642 rtx_insn *save_cselib_current_insn = cselib_current_insn; 2643 2644 gcc_checking_assert (elt); 2645 gcc_checking_assert (PRESERVED_VALUE_P (elt->val_rtx)); 2646 gcc_checking_assert (!side_effects_p (x)); 2647 2648 cselib_current_insn = insn; 2649 2650 nelt = cselib_lookup (x, GET_MODE (elt->val_rtx), 1, VOIDmode); 2651 2652 if (nelt != elt) 2653 { 2654 cselib_any_perm_equivs = true; 2655 2656 if (!PRESERVED_VALUE_P (nelt->val_rtx)) 2657 cselib_preserve_value (nelt); 2658 2659 new_elt_loc_list (nelt, elt->val_rtx); 2660 } 2661 2662 cselib_current_insn = save_cselib_current_insn; 2663} 2664 2665/* Return TRUE if any permanent equivalences have been recorded since 2666 the table was last initialized. */ 2667bool 2668cselib_have_permanent_equivalences (void) 2669{ 2670 return cselib_any_perm_equivs; 2671} 2672 2673/* Record stack_pointer_rtx to be equal to 2674 (plus:P cfa_base_preserved_val offset). Used by var-tracking 2675 at the start of basic blocks for !frame_pointer_needed functions. */ 2676 2677void 2678cselib_record_sp_cfa_base_equiv (HOST_WIDE_INT offset, rtx_insn *insn) 2679{ 2680 rtx sp_derived_value = NULL_RTX; 2681 for (struct elt_loc_list *l = cfa_base_preserved_val->locs; l; l = l->next) 2682 if (GET_CODE (l->loc) == VALUE 2683 && SP_DERIVED_VALUE_P (l->loc)) 2684 { 2685 sp_derived_value = l->loc; 2686 break; 2687 } 2688 else if (GET_CODE (l->loc) == PLUS 2689 && GET_CODE (XEXP (l->loc, 0)) == VALUE 2690 && SP_DERIVED_VALUE_P (XEXP (l->loc, 0)) 2691 && CONST_INT_P (XEXP (l->loc, 1))) 2692 { 2693 sp_derived_value = XEXP (l->loc, 0); 2694 offset = offset + UINTVAL (XEXP (l->loc, 1)); 2695 break; 2696 } 2697 if (sp_derived_value == NULL_RTX) 2698 return; 2699 cselib_val *val 2700 = cselib_lookup_from_insn (plus_constant (Pmode, sp_derived_value, offset), 2701 Pmode, 1, VOIDmode, insn); 2702 if (val != NULL) 2703 { 2704 PRESERVED_VALUE_P (val->val_rtx) = 1; 2705 cselib_record_set (stack_pointer_rtx, val, NULL); 2706 } 2707} 2708 2709/* Return true if V is SP_DERIVED_VALUE_P (or SP_DERIVED_VALUE_P + CONST_INT) 2710 that can be expressed using cfa_base_preserved_val + CONST_INT. */ 2711 2712bool 2713cselib_sp_derived_value_p (cselib_val *v) 2714{ 2715 if (!SP_DERIVED_VALUE_P (v->val_rtx)) 2716 for (struct elt_loc_list *l = v->locs; l; l = l->next) 2717 if (GET_CODE (l->loc) == PLUS 2718 && GET_CODE (XEXP (l->loc, 0)) == VALUE 2719 && SP_DERIVED_VALUE_P (XEXP (l->loc, 0)) 2720 && CONST_INT_P (XEXP (l->loc, 1))) 2721 v = CSELIB_VAL_PTR (XEXP (l->loc, 0)); 2722 if (!SP_DERIVED_VALUE_P (v->val_rtx)) 2723 return false; 2724 for (struct elt_loc_list *l = v->locs; l; l = l->next) 2725 if (l->loc == cfa_base_preserved_val->val_rtx) 2726 return true; 2727 else if (GET_CODE (l->loc) == PLUS 2728 && XEXP (l->loc, 0) == cfa_base_preserved_val->val_rtx 2729 && CONST_INT_P (XEXP (l->loc, 1))) 2730 return true; 2731 return false; 2732} 2733 2734/* There is no good way to determine how many elements there can be 2735 in a PARALLEL. Since it's fairly cheap, use a really large number. */ 2736#define MAX_SETS (FIRST_PSEUDO_REGISTER * 2) 2737 2738struct cselib_record_autoinc_data 2739{ 2740 struct cselib_set *sets; 2741 int n_sets; 2742}; 2743 2744/* Callback for for_each_inc_dec. Records in ARG the SETs implied by 2745 autoinc RTXs: SRC plus SRCOFF if non-NULL is stored in DEST. */ 2746 2747static int 2748cselib_record_autoinc_cb (rtx mem ATTRIBUTE_UNUSED, rtx op ATTRIBUTE_UNUSED, 2749 rtx dest, rtx src, rtx srcoff, void *arg) 2750{ 2751 struct cselib_record_autoinc_data *data; 2752 data = (struct cselib_record_autoinc_data *)arg; 2753 2754 data->sets[data->n_sets].dest = dest; 2755 2756 if (srcoff) 2757 data->sets[data->n_sets].src = gen_rtx_PLUS (GET_MODE (src), src, srcoff); 2758 else 2759 data->sets[data->n_sets].src = src; 2760 2761 data->n_sets++; 2762 2763 return 0; 2764} 2765 2766/* Record the effects of any sets and autoincs in INSN. */ 2767static void 2768cselib_record_sets (rtx_insn *insn) 2769{ 2770 int n_sets = 0; 2771 int i; 2772 struct cselib_set sets[MAX_SETS]; 2773 rtx cond = 0; 2774 int n_sets_before_autoinc; 2775 int n_strict_low_parts = 0; 2776 struct cselib_record_autoinc_data data; 2777 2778 rtx body = PATTERN (insn); 2779 if (GET_CODE (body) == COND_EXEC) 2780 { 2781 cond = COND_EXEC_TEST (body); 2782 body = COND_EXEC_CODE (body); 2783 } 2784 2785 /* Find all sets. */ 2786 if (GET_CODE (body) == SET) 2787 { 2788 sets[0].src = SET_SRC (body); 2789 sets[0].dest = SET_DEST (body); 2790 n_sets = 1; 2791 } 2792 else if (GET_CODE (body) == PARALLEL) 2793 { 2794 /* Look through the PARALLEL and record the values being 2795 set, if possible. Also handle any CLOBBERs. */ 2796 for (i = XVECLEN (body, 0) - 1; i >= 0; --i) 2797 { 2798 rtx x = XVECEXP (body, 0, i); 2799 2800 if (GET_CODE (x) == SET) 2801 { 2802 sets[n_sets].src = SET_SRC (x); 2803 sets[n_sets].dest = SET_DEST (x); 2804 n_sets++; 2805 } 2806 } 2807 } 2808 2809 if (n_sets == 1 2810 && MEM_P (sets[0].src) 2811 && !cselib_record_memory 2812 && MEM_READONLY_P (sets[0].src)) 2813 { 2814 rtx note = find_reg_equal_equiv_note (insn); 2815 2816 if (note && CONSTANT_P (XEXP (note, 0))) 2817 sets[0].src = XEXP (note, 0); 2818 } 2819 2820 data.sets = sets; 2821 data.n_sets = n_sets_before_autoinc = n_sets; 2822 for_each_inc_dec (PATTERN (insn), cselib_record_autoinc_cb, &data); 2823 n_sets = data.n_sets; 2824 2825 /* Look up the values that are read. Do this before invalidating the 2826 locations that are written. */ 2827 for (i = 0; i < n_sets; i++) 2828 { 2829 rtx dest = sets[i].dest; 2830 rtx orig = dest; 2831 2832 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for 2833 the low part after invalidating any knowledge about larger modes. */ 2834 if (GET_CODE (sets[i].dest) == STRICT_LOW_PART) 2835 sets[i].dest = dest = XEXP (dest, 0); 2836 2837 /* We don't know how to record anything but REG or MEM. */ 2838 if (REG_P (dest) 2839 || (MEM_P (dest) && cselib_record_memory)) 2840 { 2841 rtx src = sets[i].src; 2842 if (cond) 2843 src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest); 2844 sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1, VOIDmode); 2845 if (MEM_P (dest)) 2846 { 2847 machine_mode address_mode = get_address_mode (dest); 2848 2849 sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), 2850 address_mode, 1, 2851 GET_MODE (dest)); 2852 } 2853 else 2854 sets[i].dest_addr_elt = 0; 2855 } 2856 2857 /* Improve handling of STRICT_LOW_PART if the current value is known 2858 to be const0_rtx, then the low bits will be set to dest and higher 2859 bits will remain zero. Used in code like: 2860 2861 {di:SI=0;clobber flags:CC;} 2862 flags:CCNO=cmp(bx:SI,0) 2863 strict_low_part(di:QI)=flags:CCNO<=0 2864 2865 where we can note both that di:QI=flags:CCNO<=0 and 2866 also that because di:SI is known to be 0 and strict_low_part(di:QI) 2867 preserves the upper bits that di:SI=zero_extend(flags:CCNO<=0). */ 2868 scalar_int_mode mode; 2869 if (dest != orig 2870 && cselib_record_sets_hook 2871 && REG_P (dest) 2872 && HARD_REGISTER_P (dest) 2873 && sets[i].src_elt 2874 && is_a <scalar_int_mode> (GET_MODE (dest), &mode) 2875 && n_sets + n_strict_low_parts < MAX_SETS) 2876 { 2877 opt_scalar_int_mode wider_mode_iter; 2878 FOR_EACH_WIDER_MODE (wider_mode_iter, mode) 2879 { 2880 scalar_int_mode wider_mode = wider_mode_iter.require (); 2881 if (GET_MODE_PRECISION (wider_mode) > BITS_PER_WORD) 2882 break; 2883 2884 rtx reg = gen_lowpart (wider_mode, dest); 2885 if (!REG_P (reg)) 2886 break; 2887 2888 cselib_val *v = cselib_lookup (reg, wider_mode, 0, VOIDmode); 2889 if (!v) 2890 continue; 2891 2892 struct elt_loc_list *l; 2893 for (l = v->locs; l; l = l->next) 2894 if (l->loc == const0_rtx) 2895 break; 2896 2897 if (!l) 2898 continue; 2899 2900 sets[n_sets + n_strict_low_parts].dest = reg; 2901 sets[n_sets + n_strict_low_parts].src = dest; 2902 sets[n_sets + n_strict_low_parts++].src_elt = sets[i].src_elt; 2903 break; 2904 } 2905 } 2906 } 2907 2908 if (cselib_record_sets_hook) 2909 cselib_record_sets_hook (insn, sets, n_sets); 2910 2911 /* Invalidate all locations written by this insn. Note that the elts we 2912 looked up in the previous loop aren't affected, just some of their 2913 locations may go away. */ 2914 note_pattern_stores (body, cselib_invalidate_rtx_note_stores, NULL); 2915 2916 for (i = n_sets_before_autoinc; i < n_sets; i++) 2917 cselib_invalidate_rtx (sets[i].dest); 2918 2919 /* If this is an asm, look for duplicate sets. This can happen when the 2920 user uses the same value as an output multiple times. This is valid 2921 if the outputs are not actually used thereafter. Treat this case as 2922 if the value isn't actually set. We do this by smashing the destination 2923 to pc_rtx, so that we won't record the value later. */ 2924 if (n_sets >= 2 && asm_noperands (body) >= 0) 2925 { 2926 for (i = 0; i < n_sets; i++) 2927 { 2928 rtx dest = sets[i].dest; 2929 if (REG_P (dest) || MEM_P (dest)) 2930 { 2931 int j; 2932 for (j = i + 1; j < n_sets; j++) 2933 if (rtx_equal_p (dest, sets[j].dest)) 2934 { 2935 sets[i].dest = pc_rtx; 2936 sets[j].dest = pc_rtx; 2937 } 2938 } 2939 } 2940 } 2941 2942 /* Now enter the equivalences in our tables. */ 2943 for (i = 0; i < n_sets; i++) 2944 { 2945 rtx dest = sets[i].dest; 2946 if (REG_P (dest) 2947 || (MEM_P (dest) && cselib_record_memory)) 2948 cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt); 2949 } 2950 2951 /* And deal with STRICT_LOW_PART. */ 2952 for (i = 0; i < n_strict_low_parts; i++) 2953 { 2954 if (! PRESERVED_VALUE_P (sets[n_sets + i].src_elt->val_rtx)) 2955 continue; 2956 machine_mode dest_mode = GET_MODE (sets[n_sets + i].dest); 2957 cselib_val *v 2958 = cselib_lookup (sets[n_sets + i].dest, dest_mode, 1, VOIDmode); 2959 cselib_preserve_value (v); 2960 rtx r = gen_rtx_ZERO_EXTEND (dest_mode, 2961 sets[n_sets + i].src_elt->val_rtx); 2962 cselib_add_permanent_equiv (v, r, insn); 2963 } 2964} 2965 2966/* Return true if INSN in the prologue initializes hard_frame_pointer_rtx. */ 2967 2968bool 2969fp_setter_insn (rtx_insn *insn) 2970{ 2971 rtx expr, pat = NULL_RTX; 2972 2973 if (!RTX_FRAME_RELATED_P (insn)) 2974 return false; 2975 2976 expr = find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX); 2977 if (expr) 2978 pat = XEXP (expr, 0); 2979 if (!modified_in_p (hard_frame_pointer_rtx, pat ? pat : insn)) 2980 return false; 2981 2982 /* Don't return true for frame pointer restores in the epilogue. */ 2983 if (find_reg_note (insn, REG_CFA_RESTORE, hard_frame_pointer_rtx)) 2984 return false; 2985 return true; 2986} 2987 2988/* V is one of the values in REG_VALUES (REGNO). Return true if it 2989 would be invalidated by CALLEE_ABI. */ 2990 2991static bool 2992cselib_invalidated_by_call_p (const function_abi &callee_abi, 2993 unsigned int regno, cselib_val *v) 2994{ 2995 machine_mode mode = GET_MODE (v->val_rtx); 2996 if (mode == VOIDmode) 2997 { 2998 v = REG_VALUES (regno)->elt; 2999 if (!v) 3000 /* If we don't know what the mode of the constant value is, and we 3001 don't know what mode the register was set in, conservatively 3002 assume that the register is clobbered. The value's going to be 3003 essentially useless in this case anyway. */ 3004 return true; 3005 mode = GET_MODE (v->val_rtx); 3006 } 3007 return callee_abi.clobbers_reg_p (mode, regno); 3008} 3009 3010/* Record the effects of INSN. */ 3011 3012void 3013cselib_process_insn (rtx_insn *insn) 3014{ 3015 int i; 3016 rtx x; 3017 3018 cselib_current_insn = insn; 3019 3020 /* Forget everything at a CODE_LABEL or a setjmp. */ 3021 if ((LABEL_P (insn) 3022 || (CALL_P (insn) 3023 && find_reg_note (insn, REG_SETJMP, NULL))) 3024 && !cselib_preserve_constants) 3025 { 3026 cselib_reset_table (next_uid); 3027 cselib_current_insn = NULL; 3028 return; 3029 } 3030 3031 if (! INSN_P (insn)) 3032 { 3033 cselib_current_insn = NULL; 3034 return; 3035 } 3036 3037 /* If this is a call instruction, forget anything stored in a 3038 call clobbered register, or, if this is not a const call, in 3039 memory. */ 3040 if (CALL_P (insn)) 3041 { 3042 function_abi callee_abi = insn_callee_abi (insn); 3043 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3044 { 3045 elt_list **l = ®_VALUES (i); 3046 while (*l) 3047 { 3048 cselib_val *v = (*l)->elt; 3049 if (v && cselib_invalidated_by_call_p (callee_abi, i, v)) 3050 cselib_invalidate_regno_val (i, l); 3051 else 3052 l = &(*l)->next; 3053 } 3054 } 3055 3056 /* Since it is not clear how cselib is going to be used, be 3057 conservative here and treat looping pure or const functions 3058 as if they were regular functions. */ 3059 if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn) 3060 || !(RTL_CONST_OR_PURE_CALL_P (insn))) 3061 cselib_invalidate_mem (callmem); 3062 else 3063 /* For const/pure calls, invalidate any argument slots because 3064 they are owned by the callee. */ 3065 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1)) 3066 if (GET_CODE (XEXP (x, 0)) == USE 3067 && MEM_P (XEXP (XEXP (x, 0), 0))) 3068 cselib_invalidate_mem (XEXP (XEXP (x, 0), 0)); 3069 } 3070 3071 cselib_record_sets (insn); 3072 3073 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only 3074 after we have processed the insn. */ 3075 if (CALL_P (insn)) 3076 { 3077 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1)) 3078 if (GET_CODE (XEXP (x, 0)) == CLOBBER) 3079 cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0)); 3080 3081 /* Flush everything on setjmp. */ 3082 if (cselib_preserve_constants 3083 && find_reg_note (insn, REG_SETJMP, NULL)) 3084 { 3085 cselib_preserve_only_values (); 3086 cselib_reset_table (next_uid); 3087 } 3088 } 3089 3090 /* On setter of the hard frame pointer if frame_pointer_needed, 3091 invalidate stack_pointer_rtx, so that sp and {,h}fp based 3092 VALUEs are distinct. */ 3093 if (reload_completed 3094 && frame_pointer_needed 3095 && fp_setter_insn (insn)) 3096 cselib_invalidate_rtx (stack_pointer_rtx); 3097 3098 cselib_current_insn = NULL; 3099 3100 if (n_useless_values > MAX_USELESS_VALUES 3101 /* remove_useless_values is linear in the hash table size. Avoid 3102 quadratic behavior for very large hashtables with very few 3103 useless elements. */ 3104 && ((unsigned int)n_useless_values 3105 > (cselib_hash_table->elements () - n_debug_values) / 4)) 3106 remove_useless_values (); 3107} 3108 3109/* Initialize cselib for one pass. The caller must also call 3110 init_alias_analysis. */ 3111 3112void 3113cselib_init (int record_what) 3114{ 3115 cselib_record_memory = record_what & CSELIB_RECORD_MEMORY; 3116 cselib_preserve_constants = record_what & CSELIB_PRESERVE_CONSTANTS; 3117 cselib_any_perm_equivs = false; 3118 3119 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything, 3120 see canon_true_dependence. This is only created once. */ 3121 if (! callmem) 3122 callmem = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (VOIDmode)); 3123 3124 cselib_nregs = max_reg_num (); 3125 3126 /* We preserve reg_values to allow expensive clearing of the whole thing. 3127 Reallocate it however if it happens to be too large. */ 3128 if (!reg_values || reg_values_size < cselib_nregs 3129 || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4)) 3130 { 3131 free (reg_values); 3132 /* Some space for newly emit instructions so we don't end up 3133 reallocating in between passes. */ 3134 reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16; 3135 reg_values = XCNEWVEC (struct elt_list *, reg_values_size); 3136 } 3137 used_regs = XNEWVEC (unsigned int, cselib_nregs); 3138 n_used_regs = 0; 3139 /* FIXME: enable sanitization (PR87845) */ 3140 cselib_hash_table 3141 = new hash_table<cselib_hasher> (31, /* ggc */ false, 3142 /* sanitize_eq_and_hash */ false); 3143 if (cselib_preserve_constants) 3144 cselib_preserved_hash_table 3145 = new hash_table<cselib_hasher> (31, /* ggc */ false, 3146 /* sanitize_eq_and_hash */ false); 3147 next_uid = 1; 3148} 3149 3150/* Called when the current user is done with cselib. */ 3151 3152void 3153cselib_finish (void) 3154{ 3155 bool preserved = cselib_preserve_constants; 3156 cselib_discard_hook = NULL; 3157 cselib_preserve_constants = false; 3158 cselib_any_perm_equivs = false; 3159 cfa_base_preserved_val = NULL; 3160 cfa_base_preserved_regno = INVALID_REGNUM; 3161 elt_list_pool.release (); 3162 elt_loc_list_pool.release (); 3163 cselib_val_pool.release (); 3164 value_pool.release (); 3165 cselib_clear_table (); 3166 delete cselib_hash_table; 3167 cselib_hash_table = NULL; 3168 if (preserved) 3169 delete cselib_preserved_hash_table; 3170 cselib_preserved_hash_table = NULL; 3171 free (used_regs); 3172 used_regs = 0; 3173 n_useless_values = 0; 3174 n_useless_debug_values = 0; 3175 n_debug_values = 0; 3176 next_uid = 0; 3177} 3178 3179/* Dump the cselib_val *X to FILE *OUT. */ 3180 3181int 3182dump_cselib_val (cselib_val **x, FILE *out) 3183{ 3184 cselib_val *v = *x; 3185 bool need_lf = true; 3186 3187 print_inline_rtx (out, v->val_rtx, 0); 3188 3189 if (v->locs) 3190 { 3191 struct elt_loc_list *l = v->locs; 3192 if (need_lf) 3193 { 3194 fputc ('\n', out); 3195 need_lf = false; 3196 } 3197 fputs (" locs:", out); 3198 do 3199 { 3200 if (l->setting_insn) 3201 fprintf (out, "\n from insn %i ", 3202 INSN_UID (l->setting_insn)); 3203 else 3204 fprintf (out, "\n "); 3205 print_inline_rtx (out, l->loc, 4); 3206 } 3207 while ((l = l->next)); 3208 fputc ('\n', out); 3209 } 3210 else 3211 { 3212 fputs (" no locs", out); 3213 need_lf = true; 3214 } 3215 3216 if (v->addr_list) 3217 { 3218 struct elt_list *e = v->addr_list; 3219 if (need_lf) 3220 { 3221 fputc ('\n', out); 3222 need_lf = false; 3223 } 3224 fputs (" addr list:", out); 3225 do 3226 { 3227 fputs ("\n ", out); 3228 print_inline_rtx (out, e->elt->val_rtx, 2); 3229 } 3230 while ((e = e->next)); 3231 fputc ('\n', out); 3232 } 3233 else 3234 { 3235 fputs (" no addrs", out); 3236 need_lf = true; 3237 } 3238 3239 if (v->next_containing_mem == &dummy_val) 3240 fputs (" last mem\n", out); 3241 else if (v->next_containing_mem) 3242 { 3243 fputs (" next mem ", out); 3244 print_inline_rtx (out, v->next_containing_mem->val_rtx, 2); 3245 fputc ('\n', out); 3246 } 3247 else if (need_lf) 3248 fputc ('\n', out); 3249 3250 return 1; 3251} 3252 3253/* Dump to OUT everything in the CSELIB table. */ 3254 3255void 3256dump_cselib_table (FILE *out) 3257{ 3258 fprintf (out, "cselib hash table:\n"); 3259 cselib_hash_table->traverse <FILE *, dump_cselib_val> (out); 3260 fprintf (out, "cselib preserved hash table:\n"); 3261 cselib_preserved_hash_table->traverse <FILE *, dump_cselib_val> (out); 3262 if (first_containing_mem != &dummy_val) 3263 { 3264 fputs ("first mem ", out); 3265 print_inline_rtx (out, first_containing_mem->val_rtx, 2); 3266 fputc ('\n', out); 3267 } 3268 fprintf (out, "next uid %i\n", next_uid); 3269} 3270 3271#include "gt-cselib.h" 3272