1 /* Common subexpression elimination library for GNU compiler. 2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 2, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING. If not, write to the Free 19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA 20 02111-1307, USA. */ 21 22 #include "config.h" 23 #include "system.h" 24 25 #include "rtl.h" 26 #include "tm_p.h" 27 #include "regs.h" 28 #include "hard-reg-set.h" 29 #include "flags.h" 30 #include "real.h" 31 #include "insn-config.h" 32 #include "recog.h" 33 #include "function.h" 34 #include "expr.h" 35 #include "toplev.h" 36 #include "output.h" 37 #include "ggc.h" 38 #include "hashtab.h" 39 #include "cselib.h" 40 41 static int entry_and_rtx_equal_p PARAMS ((const void *, const void *)); 42 static hashval_t get_value_hash PARAMS ((const void *)); 43 static struct elt_list *new_elt_list PARAMS ((struct elt_list *, 44 cselib_val *)); 45 static struct elt_loc_list *new_elt_loc_list PARAMS ((struct elt_loc_list *, 46 rtx)); 47 static void unchain_one_value PARAMS ((cselib_val *)); 48 static void unchain_one_elt_list PARAMS ((struct elt_list **)); 49 static void unchain_one_elt_loc_list PARAMS ((struct elt_loc_list **)); 50 static void clear_table PARAMS ((int)); 51 static int discard_useless_locs PARAMS ((void **, void *)); 52 static int discard_useless_values PARAMS ((void **, void *)); 53 static void remove_useless_values PARAMS ((void)); 54 static rtx wrap_constant PARAMS ((enum machine_mode, rtx)); 55 static unsigned int hash_rtx PARAMS ((rtx, enum machine_mode, int)); 56 static cselib_val *new_cselib_val PARAMS ((unsigned int, 57 enum machine_mode)); 58 static void add_mem_for_addr PARAMS ((cselib_val *, cselib_val *, 59 rtx)); 60 static cselib_val *cselib_lookup_mem PARAMS ((rtx, int)); 61 static void cselib_invalidate_regno PARAMS ((unsigned int, 62 enum machine_mode)); 63 static int cselib_mem_conflict_p PARAMS ((rtx, rtx)); 64 static int cselib_invalidate_mem_1 PARAMS ((void **, void *)); 65 static void cselib_invalidate_mem PARAMS ((rtx)); 66 static void cselib_invalidate_rtx PARAMS ((rtx, rtx, void *)); 67 static void cselib_record_set PARAMS ((rtx, cselib_val *, 68 cselib_val *)); 69 static void cselib_record_sets PARAMS ((rtx)); 70 71 /* There are three ways in which cselib can look up an rtx: 72 - for a REG, the reg_values table (which is indexed by regno) is used 73 - for a MEM, we recursively look up its address and then follow the 74 addr_list of that value 75 - for everything else, we compute a hash value and go through the hash 76 table. Since different rtx's can still have the same hash value, 77 this involves walking the table entries for a given value and comparing 78 the locations of the entries with the rtx we are looking up. */ 79 80 /* A table that enables us to look up elts by their value. */ 81 static GTY((param_is (cselib_val))) htab_t hash_table; 82 83 /* This is a global so we don't have to pass this through every function. 84 It is used in new_elt_loc_list to set SETTING_INSN. */ 85 static rtx cselib_current_insn; 86 static bool cselib_current_insn_in_libcall; 87 88 /* Every new unknown value gets a unique number. */ 89 static unsigned int next_unknown_value; 90 91 /* The number of registers we had when the varrays were last resized. */ 92 static unsigned int cselib_nregs; 93 94 /* Count values without known locations. Whenever this grows too big, we 95 remove these useless values from the table. */ 96 static int n_useless_values; 97 98 /* Number of useless values before we remove them from the hash table. */ 99 #define MAX_USELESS_VALUES 32 100 101 /* This table maps from register number to values. It does not contain 102 pointers to cselib_val structures, but rather elt_lists. The purpose is 103 to be able to refer to the same register in different modes. */ 104 static GTY(()) varray_type reg_values; 105 static GTY((deletable (""))) varray_type reg_values_old; 106 #define REG_VALUES(I) VARRAY_ELT_LIST (reg_values, (I)) 107 108 /* The largest number of hard regs used by any entry added to the 109 REG_VALUES table. Cleared on each clear_table() invocation. */ 110 static unsigned int max_value_regs; 111 112 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used 113 in clear_table() for fast emptying. */ 114 static GTY(()) varray_type used_regs; 115 static GTY((deletable (""))) varray_type used_regs_old; 116 117 /* We pass this to cselib_invalidate_mem to invalidate all of 118 memory for a non-const call instruction. */ 119 static GTY(()) rtx callmem; 120 121 /* Caches for unused structures. */ 122 static GTY((deletable (""))) cselib_val *empty_vals; 123 static GTY((deletable (""))) struct elt_list *empty_elt_lists; 124 static GTY((deletable (""))) struct elt_loc_list *empty_elt_loc_lists; 125 126 /* Set by discard_useless_locs if it deleted the last location of any 127 value. */ 128 static int values_became_useless; 129 130 131 /* Allocate a struct elt_list and fill in its two elements with the 132 arguments. */ 133 134 static struct elt_list * 135 new_elt_list (next, elt) 136 struct elt_list *next; 137 cselib_val *elt; 138 { 139 struct elt_list *el = empty_elt_lists; 140 141 if (el) 142 empty_elt_lists = el->next; 143 else 144 el = (struct elt_list *) ggc_alloc (sizeof (struct elt_list)); 145 el->next = next; 146 el->elt = elt; 147 return el; 148 } 149 150 /* Allocate a struct elt_loc_list and fill in its two elements with the 151 arguments. */ 152 153 static struct elt_loc_list * 154 new_elt_loc_list (next, loc) 155 struct elt_loc_list *next; 156 rtx loc; 157 { 158 struct elt_loc_list *el = empty_elt_loc_lists; 159 160 if (el) 161 empty_elt_loc_lists = el->next; 162 else 163 el = (struct elt_loc_list *) ggc_alloc (sizeof (struct elt_loc_list)); 164 el->next = next; 165 el->loc = loc; 166 el->setting_insn = cselib_current_insn; 167 el->in_libcall = cselib_current_insn_in_libcall; 168 return el; 169 } 170 171 /* The elt_list at *PL is no longer needed. Unchain it and free its 172 storage. */ 173 174 static void 175 unchain_one_elt_list (pl) 176 struct elt_list **pl; 177 { 178 struct elt_list *l = *pl; 179 180 *pl = l->next; 181 l->next = empty_elt_lists; 182 empty_elt_lists = l; 183 } 184 185 /* Likewise for elt_loc_lists. */ 186 187 static void 188 unchain_one_elt_loc_list (pl) 189 struct elt_loc_list **pl; 190 { 191 struct elt_loc_list *l = *pl; 192 193 *pl = l->next; 194 l->next = empty_elt_loc_lists; 195 empty_elt_loc_lists = l; 196 } 197 198 /* Likewise for cselib_vals. This also frees the addr_list associated with 199 V. */ 200 201 static void 202 unchain_one_value (v) 203 cselib_val *v; 204 { 205 while (v->addr_list) 206 unchain_one_elt_list (&v->addr_list); 207 208 v->u.next_free = empty_vals; 209 empty_vals = v; 210 } 211 212 /* Remove all entries from the hash table. Also used during 213 initialization. If CLEAR_ALL isn't set, then only clear the entries 214 which are known to have been used. */ 215 216 static void 217 clear_table (clear_all) 218 int clear_all; 219 { 220 unsigned int i; 221 222 if (clear_all) 223 for (i = 0; i < cselib_nregs; i++) 224 REG_VALUES (i) = 0; 225 else 226 for (i = 0; i < VARRAY_ACTIVE_SIZE (used_regs); i++) 227 REG_VALUES (VARRAY_UINT (used_regs, i)) = 0; 228 229 max_value_regs = 0; 230 231 VARRAY_POP_ALL (used_regs); 232 233 htab_empty (hash_table); 234 235 n_useless_values = 0; 236 237 next_unknown_value = 0; 238 } 239 240 /* The equality test for our hash table. The first argument ENTRY is a table 241 element (i.e. a cselib_val), while the second arg X is an rtx. We know 242 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a 243 CONST of an appropriate mode. */ 244 245 static int 246 entry_and_rtx_equal_p (entry, x_arg) 247 const void *entry, *x_arg; 248 { 249 struct elt_loc_list *l; 250 const cselib_val *v = (const cselib_val *) entry; 251 rtx x = (rtx) x_arg; 252 enum machine_mode mode = GET_MODE (x); 253 254 if (GET_CODE (x) == CONST_INT 255 || (mode == VOIDmode && GET_CODE (x) == CONST_DOUBLE)) 256 abort (); 257 if (mode != GET_MODE (v->u.val_rtx)) 258 return 0; 259 260 /* Unwrap X if necessary. */ 261 if (GET_CODE (x) == CONST 262 && (GET_CODE (XEXP (x, 0)) == CONST_INT 263 || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE)) 264 x = XEXP (x, 0); 265 266 /* We don't guarantee that distinct rtx's have different hash values, 267 so we need to do a comparison. */ 268 for (l = v->locs; l; l = l->next) 269 if (rtx_equal_for_cselib_p (l->loc, x)) 270 return 1; 271 272 return 0; 273 } 274 275 /* The hash function for our hash table. The value is always computed with 276 hash_rtx when adding an element; this function just extracts the hash 277 value from a cselib_val structure. */ 278 279 static hashval_t 280 get_value_hash (entry) 281 const void *entry; 282 { 283 const cselib_val *v = (const cselib_val *) entry; 284 return v->value; 285 } 286 287 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we 288 only return true for values which point to a cselib_val whose value 289 element has been set to zero, which implies the cselib_val will be 290 removed. */ 291 292 int 293 references_value_p (x, only_useless) 294 rtx x; 295 int only_useless; 296 { 297 enum rtx_code code = GET_CODE (x); 298 const char *fmt = GET_RTX_FORMAT (code); 299 int i, j; 300 301 if (GET_CODE (x) == VALUE 302 && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0)) 303 return 1; 304 305 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 306 { 307 if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless)) 308 return 1; 309 else if (fmt[i] == 'E') 310 for (j = 0; j < XVECLEN (x, i); j++) 311 if (references_value_p (XVECEXP (x, i, j), only_useless)) 312 return 1; 313 } 314 315 return 0; 316 } 317 318 /* For all locations found in X, delete locations that reference useless 319 values (i.e. values without any location). Called through 320 htab_traverse. */ 321 322 static int 323 discard_useless_locs (x, info) 324 void **x; 325 void *info ATTRIBUTE_UNUSED; 326 { 327 cselib_val *v = (cselib_val *)*x; 328 struct elt_loc_list **p = &v->locs; 329 int had_locs = v->locs != 0; 330 331 while (*p) 332 { 333 if (references_value_p ((*p)->loc, 1)) 334 unchain_one_elt_loc_list (p); 335 else 336 p = &(*p)->next; 337 } 338 339 if (had_locs && v->locs == 0) 340 { 341 n_useless_values++; 342 values_became_useless = 1; 343 } 344 return 1; 345 } 346 347 /* If X is a value with no locations, remove it from the hashtable. */ 348 349 static int 350 discard_useless_values (x, info) 351 void **x; 352 void *info ATTRIBUTE_UNUSED; 353 { 354 cselib_val *v = (cselib_val *)*x; 355 356 if (v->locs == 0) 357 { 358 htab_clear_slot (hash_table, x); 359 unchain_one_value (v); 360 n_useless_values--; 361 } 362 363 return 1; 364 } 365 366 /* Clean out useless values (i.e. those which no longer have locations 367 associated with them) from the hash table. */ 368 369 static void 370 remove_useless_values () 371 { 372 /* First pass: eliminate locations that reference the value. That in 373 turn can make more values useless. */ 374 do 375 { 376 values_became_useless = 0; 377 htab_traverse (hash_table, discard_useless_locs, 0); 378 } 379 while (values_became_useless); 380 381 /* Second pass: actually remove the values. */ 382 htab_traverse (hash_table, discard_useless_values, 0); 383 384 if (n_useless_values != 0) 385 abort (); 386 } 387 388 /* Return nonzero if we can prove that X and Y contain the same value, taking 389 our gathered information into account. */ 390 391 int 392 rtx_equal_for_cselib_p (x, y) 393 rtx x, y; 394 { 395 enum rtx_code code; 396 const char *fmt; 397 int i; 398 399 if (GET_CODE (x) == REG || GET_CODE (x) == MEM) 400 { 401 cselib_val *e = cselib_lookup (x, GET_MODE (x), 0); 402 403 if (e) 404 x = e->u.val_rtx; 405 } 406 407 if (GET_CODE (y) == REG || GET_CODE (y) == MEM) 408 { 409 cselib_val *e = cselib_lookup (y, GET_MODE (y), 0); 410 411 if (e) 412 y = e->u.val_rtx; 413 } 414 415 if (x == y) 416 return 1; 417 418 if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE) 419 return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y); 420 421 if (GET_CODE (x) == VALUE) 422 { 423 cselib_val *e = CSELIB_VAL_PTR (x); 424 struct elt_loc_list *l; 425 426 for (l = e->locs; l; l = l->next) 427 { 428 rtx t = l->loc; 429 430 /* Avoid infinite recursion. */ 431 if (GET_CODE (t) == REG || GET_CODE (t) == MEM) 432 continue; 433 else if (rtx_equal_for_cselib_p (t, y)) 434 return 1; 435 } 436 437 return 0; 438 } 439 440 if (GET_CODE (y) == VALUE) 441 { 442 cselib_val *e = CSELIB_VAL_PTR (y); 443 struct elt_loc_list *l; 444 445 for (l = e->locs; l; l = l->next) 446 { 447 rtx t = l->loc; 448 449 if (GET_CODE (t) == REG || GET_CODE (t) == MEM) 450 continue; 451 else if (rtx_equal_for_cselib_p (x, t)) 452 return 1; 453 } 454 455 return 0; 456 } 457 458 if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y)) 459 return 0; 460 461 /* This won't be handled correctly by the code below. */ 462 if (GET_CODE (x) == LABEL_REF) 463 return XEXP (x, 0) == XEXP (y, 0); 464 465 code = GET_CODE (x); 466 fmt = GET_RTX_FORMAT (code); 467 468 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 469 { 470 int j; 471 472 switch (fmt[i]) 473 { 474 case 'w': 475 if (XWINT (x, i) != XWINT (y, i)) 476 return 0; 477 break; 478 479 case 'n': 480 case 'i': 481 if (XINT (x, i) != XINT (y, i)) 482 return 0; 483 break; 484 485 case 'V': 486 case 'E': 487 /* Two vectors must have the same length. */ 488 if (XVECLEN (x, i) != XVECLEN (y, i)) 489 return 0; 490 491 /* And the corresponding elements must match. */ 492 for (j = 0; j < XVECLEN (x, i); j++) 493 if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j), 494 XVECEXP (y, i, j))) 495 return 0; 496 break; 497 498 case 'e': 499 if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i))) 500 return 0; 501 break; 502 503 case 'S': 504 case 's': 505 if (strcmp (XSTR (x, i), XSTR (y, i))) 506 return 0; 507 break; 508 509 case 'u': 510 /* These are just backpointers, so they don't matter. */ 511 break; 512 513 case '0': 514 case 't': 515 break; 516 517 /* It is believed that rtx's at this level will never 518 contain anything but integers and other rtx's, 519 except for within LABEL_REFs and SYMBOL_REFs. */ 520 default: 521 abort (); 522 } 523 } 524 return 1; 525 } 526 527 /* We need to pass down the mode of constants through the hash table 528 functions. For that purpose, wrap them in a CONST of the appropriate 529 mode. */ 530 static rtx 531 wrap_constant (mode, x) 532 enum machine_mode mode; 533 rtx x; 534 { 535 if (GET_CODE (x) != CONST_INT 536 && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode)) 537 return x; 538 if (mode == VOIDmode) 539 abort (); 540 return gen_rtx_CONST (mode, x); 541 } 542 543 /* Hash an rtx. Return 0 if we couldn't hash the rtx. 544 For registers and memory locations, we look up their cselib_val structure 545 and return its VALUE element. 546 Possible reasons for return 0 are: the object is volatile, or we couldn't 547 find a register or memory location in the table and CREATE is zero. If 548 CREATE is nonzero, table elts are created for regs and mem. 549 MODE is used in hashing for CONST_INTs only; 550 otherwise the mode of X is used. */ 551 552 static unsigned int 553 hash_rtx (x, mode, create) 554 rtx x; 555 enum machine_mode mode; 556 int create; 557 { 558 cselib_val *e; 559 int i, j; 560 enum rtx_code code; 561 const char *fmt; 562 unsigned int hash = 0; 563 564 code = GET_CODE (x); 565 hash += (unsigned) code + (unsigned) GET_MODE (x); 566 567 switch (code) 568 { 569 case MEM: 570 case REG: 571 e = cselib_lookup (x, GET_MODE (x), create); 572 if (! e) 573 return 0; 574 575 return e->value; 576 577 case CONST_INT: 578 hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + INTVAL (x); 579 return hash ? hash : (unsigned int) CONST_INT; 580 581 case CONST_DOUBLE: 582 /* This is like the general case, except that it only counts 583 the integers representing the constant. */ 584 hash += (unsigned) code + (unsigned) GET_MODE (x); 585 if (GET_MODE (x) != VOIDmode) 586 hash += real_hash (CONST_DOUBLE_REAL_VALUE (x)); 587 else 588 hash += ((unsigned) CONST_DOUBLE_LOW (x) 589 + (unsigned) CONST_DOUBLE_HIGH (x)); 590 return hash ? hash : (unsigned int) CONST_DOUBLE; 591 592 case CONST_VECTOR: 593 { 594 int units; 595 rtx elt; 596 597 units = CONST_VECTOR_NUNITS (x); 598 599 for (i = 0; i < units; ++i) 600 { 601 elt = CONST_VECTOR_ELT (x, i); 602 hash += hash_rtx (elt, GET_MODE (elt), 0); 603 } 604 605 return hash; 606 } 607 608 /* Assume there is only one rtx object for any given label. */ 609 case LABEL_REF: 610 hash 611 += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0); 612 return hash ? hash : (unsigned int) LABEL_REF; 613 614 case SYMBOL_REF: 615 hash 616 += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0); 617 return hash ? hash : (unsigned int) SYMBOL_REF; 618 619 case PRE_DEC: 620 case PRE_INC: 621 case POST_DEC: 622 case POST_INC: 623 case POST_MODIFY: 624 case PRE_MODIFY: 625 case PC: 626 case CC0: 627 case CALL: 628 case UNSPEC_VOLATILE: 629 return 0; 630 631 case ASM_OPERANDS: 632 if (MEM_VOLATILE_P (x)) 633 return 0; 634 635 break; 636 637 default: 638 break; 639 } 640 641 i = GET_RTX_LENGTH (code) - 1; 642 fmt = GET_RTX_FORMAT (code); 643 for (; i >= 0; i--) 644 { 645 if (fmt[i] == 'e') 646 { 647 rtx tem = XEXP (x, i); 648 unsigned int tem_hash = hash_rtx (tem, 0, create); 649 650 if (tem_hash == 0) 651 return 0; 652 653 hash += tem_hash; 654 } 655 else if (fmt[i] == 'E') 656 for (j = 0; j < XVECLEN (x, i); j++) 657 { 658 unsigned int tem_hash = hash_rtx (XVECEXP (x, i, j), 0, create); 659 660 if (tem_hash == 0) 661 return 0; 662 663 hash += tem_hash; 664 } 665 else if (fmt[i] == 's') 666 { 667 const unsigned char *p = (const unsigned char *) XSTR (x, i); 668 669 if (p) 670 while (*p) 671 hash += *p++; 672 } 673 else if (fmt[i] == 'i') 674 hash += XINT (x, i); 675 else if (fmt[i] == '0' || fmt[i] == 't') 676 /* unused */; 677 else 678 abort (); 679 } 680 681 return hash ? hash : 1 + (unsigned int) GET_CODE (x); 682 } 683 684 /* Create a new value structure for VALUE and initialize it. The mode of the 685 value is MODE. */ 686 687 static cselib_val * 688 new_cselib_val (value, mode) 689 unsigned int value; 690 enum machine_mode mode; 691 { 692 cselib_val *e = empty_vals; 693 694 if (e) 695 empty_vals = e->u.next_free; 696 else 697 e = (cselib_val *) ggc_alloc (sizeof (cselib_val)); 698 699 if (value == 0) 700 abort (); 701 702 e->value = value; 703 e->u.val_rtx = gen_rtx_VALUE (mode); 704 CSELIB_VAL_PTR (e->u.val_rtx) = e; 705 e->addr_list = 0; 706 e->locs = 0; 707 return e; 708 } 709 710 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that 711 contains the data at this address. X is a MEM that represents the 712 value. Update the two value structures to represent this situation. */ 713 714 static void 715 add_mem_for_addr (addr_elt, mem_elt, x) 716 cselib_val *addr_elt, *mem_elt; 717 rtx x; 718 { 719 struct elt_loc_list *l; 720 721 /* Avoid duplicates. */ 722 for (l = mem_elt->locs; l; l = l->next) 723 if (GET_CODE (l->loc) == MEM 724 && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt) 725 return; 726 727 addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt); 728 mem_elt->locs 729 = new_elt_loc_list (mem_elt->locs, 730 replace_equiv_address_nv (x, addr_elt->u.val_rtx)); 731 } 732 733 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx. 734 If CREATE, make a new one if we haven't seen it before. */ 735 736 static cselib_val * 737 cselib_lookup_mem (x, create) 738 rtx x; 739 int create; 740 { 741 enum machine_mode mode = GET_MODE (x); 742 void **slot; 743 cselib_val *addr; 744 cselib_val *mem_elt; 745 struct elt_list *l; 746 747 if (MEM_VOLATILE_P (x) || mode == BLKmode 748 || (FLOAT_MODE_P (mode) && flag_float_store)) 749 return 0; 750 751 /* Look up the value for the address. */ 752 addr = cselib_lookup (XEXP (x, 0), mode, create); 753 if (! addr) 754 return 0; 755 756 /* Find a value that describes a value of our mode at that address. */ 757 for (l = addr->addr_list; l; l = l->next) 758 if (GET_MODE (l->elt->u.val_rtx) == mode) 759 return l->elt; 760 761 if (! create) 762 return 0; 763 764 mem_elt = new_cselib_val (++next_unknown_value, mode); 765 add_mem_for_addr (addr, mem_elt, x); 766 slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x), 767 mem_elt->value, INSERT); 768 *slot = mem_elt; 769 return mem_elt; 770 } 771 772 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions 773 with VALUE expressions. This way, it becomes independent of changes 774 to registers and memory. 775 X isn't actually modified; if modifications are needed, new rtl is 776 allocated. However, the return value can share rtl with X. */ 777 778 rtx 779 cselib_subst_to_values (x) 780 rtx x; 781 { 782 enum rtx_code code = GET_CODE (x); 783 const char *fmt = GET_RTX_FORMAT (code); 784 cselib_val *e; 785 struct elt_list *l; 786 rtx copy = x; 787 int i; 788 789 switch (code) 790 { 791 case REG: 792 for (l = REG_VALUES (REGNO (x)); l; l = l->next) 793 if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x)) 794 return l->elt->u.val_rtx; 795 796 abort (); 797 798 case MEM: 799 e = cselib_lookup_mem (x, 0); 800 if (! e) 801 { 802 /* This happens for autoincrements. Assign a value that doesn't 803 match any other. */ 804 e = new_cselib_val (++next_unknown_value, GET_MODE (x)); 805 } 806 return e->u.val_rtx; 807 808 case CONST_DOUBLE: 809 case CONST_VECTOR: 810 case CONST_INT: 811 return x; 812 813 case POST_INC: 814 case PRE_INC: 815 case POST_DEC: 816 case PRE_DEC: 817 case POST_MODIFY: 818 case PRE_MODIFY: 819 e = new_cselib_val (++next_unknown_value, GET_MODE (x)); 820 return e->u.val_rtx; 821 822 default: 823 break; 824 } 825 826 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 827 { 828 if (fmt[i] == 'e') 829 { 830 rtx t = cselib_subst_to_values (XEXP (x, i)); 831 832 if (t != XEXP (x, i) && x == copy) 833 copy = shallow_copy_rtx (x); 834 835 XEXP (copy, i) = t; 836 } 837 else if (fmt[i] == 'E') 838 { 839 int j, k; 840 841 for (j = 0; j < XVECLEN (x, i); j++) 842 { 843 rtx t = cselib_subst_to_values (XVECEXP (x, i, j)); 844 845 if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i)) 846 { 847 if (x == copy) 848 copy = shallow_copy_rtx (x); 849 850 XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i)); 851 for (k = 0; k < j; k++) 852 XVECEXP (copy, i, k) = XVECEXP (x, i, k); 853 } 854 855 XVECEXP (copy, i, j) = t; 856 } 857 } 858 } 859 860 return copy; 861 } 862 863 /* Look up the rtl expression X in our tables and return the value it has. 864 If CREATE is zero, we return NULL if we don't know the value. Otherwise, 865 we create a new one if possible, using mode MODE if X doesn't have a mode 866 (i.e. because it's a constant). */ 867 868 cselib_val * 869 cselib_lookup (x, mode, create) 870 rtx x; 871 enum machine_mode mode; 872 int create; 873 { 874 void **slot; 875 cselib_val *e; 876 unsigned int hashval; 877 878 if (GET_MODE (x) != VOIDmode) 879 mode = GET_MODE (x); 880 881 if (GET_CODE (x) == VALUE) 882 return CSELIB_VAL_PTR (x); 883 884 if (GET_CODE (x) == REG) 885 { 886 struct elt_list *l; 887 unsigned int i = REGNO (x); 888 889 for (l = REG_VALUES (i); l; l = l->next) 890 if (mode == GET_MODE (l->elt->u.val_rtx)) 891 return l->elt; 892 893 if (! create) 894 return 0; 895 896 if (i < FIRST_PSEUDO_REGISTER) 897 { 898 unsigned int n = HARD_REGNO_NREGS (i, mode); 899 900 if (n > max_value_regs) 901 max_value_regs = n; 902 } 903 904 e = new_cselib_val (++next_unknown_value, GET_MODE (x)); 905 e->locs = new_elt_loc_list (e->locs, x); 906 if (REG_VALUES (i) == 0) 907 VARRAY_PUSH_UINT (used_regs, i); 908 REG_VALUES (i) = new_elt_list (REG_VALUES (i), e); 909 slot = htab_find_slot_with_hash (hash_table, x, e->value, INSERT); 910 *slot = e; 911 return e; 912 } 913 914 if (GET_CODE (x) == MEM) 915 return cselib_lookup_mem (x, create); 916 917 hashval = hash_rtx (x, mode, create); 918 /* Can't even create if hashing is not possible. */ 919 if (! hashval) 920 return 0; 921 922 slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x), 923 hashval, create ? INSERT : NO_INSERT); 924 if (slot == 0) 925 return 0; 926 927 e = (cselib_val *) *slot; 928 if (e) 929 return e; 930 931 e = new_cselib_val (hashval, mode); 932 933 /* We have to fill the slot before calling cselib_subst_to_values: 934 the hash table is inconsistent until we do so, and 935 cselib_subst_to_values will need to do lookups. */ 936 *slot = (void *) e; 937 e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x)); 938 return e; 939 } 940 941 /* Invalidate any entries in reg_values that overlap REGNO. This is called 942 if REGNO is changing. MODE is the mode of the assignment to REGNO, which 943 is used to determine how many hard registers are being changed. If MODE 944 is VOIDmode, then only REGNO is being changed; this is used when 945 invalidating call clobbered registers across a call. */ 946 947 static void 948 cselib_invalidate_regno (regno, mode) 949 unsigned int regno; 950 enum machine_mode mode; 951 { 952 unsigned int endregno; 953 unsigned int i; 954 955 /* If we see pseudos after reload, something is _wrong_. */ 956 if (reload_completed && regno >= FIRST_PSEUDO_REGISTER 957 && reg_renumber[regno] >= 0) 958 abort (); 959 960 /* Determine the range of registers that must be invalidated. For 961 pseudos, only REGNO is affected. For hard regs, we must take MODE 962 into account, and we must also invalidate lower register numbers 963 if they contain values that overlap REGNO. */ 964 if (regno < FIRST_PSEUDO_REGISTER) 965 { 966 if (mode == VOIDmode) 967 abort (); 968 969 if (regno < max_value_regs) 970 i = 0; 971 else 972 i = regno - max_value_regs; 973 974 endregno = regno + HARD_REGNO_NREGS (regno, mode); 975 } 976 else 977 { 978 i = regno; 979 endregno = regno + 1; 980 } 981 982 for (; i < endregno; i++) 983 { 984 struct elt_list **l = ®_VALUES (i); 985 986 /* Go through all known values for this reg; if it overlaps the range 987 we're invalidating, remove the value. */ 988 while (*l) 989 { 990 cselib_val *v = (*l)->elt; 991 struct elt_loc_list **p; 992 unsigned int this_last = i; 993 994 if (i < FIRST_PSEUDO_REGISTER) 995 this_last += HARD_REGNO_NREGS (i, GET_MODE (v->u.val_rtx)) - 1; 996 997 if (this_last < regno) 998 { 999 l = &(*l)->next; 1000 continue; 1001 } 1002 1003 /* We have an overlap. */ 1004 unchain_one_elt_list (l); 1005 1006 /* Now, we clear the mapping from value to reg. It must exist, so 1007 this code will crash intentionally if it doesn't. */ 1008 for (p = &v->locs; ; p = &(*p)->next) 1009 { 1010 rtx x = (*p)->loc; 1011 1012 if (GET_CODE (x) == REG && REGNO (x) == i) 1013 { 1014 unchain_one_elt_loc_list (p); 1015 break; 1016 } 1017 } 1018 if (v->locs == 0) 1019 n_useless_values++; 1020 } 1021 } 1022 } 1023 1024 /* The memory at address MEM_BASE is being changed. 1025 Return whether this change will invalidate VAL. */ 1026 1027 static int 1028 cselib_mem_conflict_p (mem_base, val) 1029 rtx mem_base; 1030 rtx val; 1031 { 1032 enum rtx_code code; 1033 const char *fmt; 1034 int i, j; 1035 1036 code = GET_CODE (val); 1037 switch (code) 1038 { 1039 /* Get rid of a few simple cases quickly. */ 1040 case REG: 1041 case PC: 1042 case CC0: 1043 case SCRATCH: 1044 case CONST: 1045 case CONST_INT: 1046 case CONST_DOUBLE: 1047 case CONST_VECTOR: 1048 case SYMBOL_REF: 1049 case LABEL_REF: 1050 return 0; 1051 1052 case MEM: 1053 if (GET_MODE (mem_base) == BLKmode 1054 || GET_MODE (val) == BLKmode 1055 || anti_dependence (val, mem_base)) 1056 return 1; 1057 1058 /* The address may contain nested MEMs. */ 1059 break; 1060 1061 default: 1062 break; 1063 } 1064 1065 fmt = GET_RTX_FORMAT (code); 1066 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1067 { 1068 if (fmt[i] == 'e') 1069 { 1070 if (cselib_mem_conflict_p (mem_base, XEXP (val, i))) 1071 return 1; 1072 } 1073 else if (fmt[i] == 'E') 1074 for (j = 0; j < XVECLEN (val, i); j++) 1075 if (cselib_mem_conflict_p (mem_base, XVECEXP (val, i, j))) 1076 return 1; 1077 } 1078 1079 return 0; 1080 } 1081 1082 /* For the value found in SLOT, walk its locations to determine if any overlap 1083 INFO (which is a MEM rtx). */ 1084 1085 static int 1086 cselib_invalidate_mem_1 (slot, info) 1087 void **slot; 1088 void *info; 1089 { 1090 cselib_val *v = (cselib_val *) *slot; 1091 rtx mem_rtx = (rtx) info; 1092 struct elt_loc_list **p = &v->locs; 1093 int had_locs = v->locs != 0; 1094 1095 while (*p) 1096 { 1097 rtx x = (*p)->loc; 1098 cselib_val *addr; 1099 struct elt_list **mem_chain; 1100 1101 /* MEMs may occur in locations only at the top level; below 1102 that every MEM or REG is substituted by its VALUE. */ 1103 if (GET_CODE (x) != MEM 1104 || ! cselib_mem_conflict_p (mem_rtx, x)) 1105 { 1106 p = &(*p)->next; 1107 continue; 1108 } 1109 1110 /* This one overlaps. */ 1111 /* We must have a mapping from this MEM's address to the 1112 value (E). Remove that, too. */ 1113 addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0); 1114 mem_chain = &addr->addr_list; 1115 for (;;) 1116 { 1117 if ((*mem_chain)->elt == v) 1118 { 1119 unchain_one_elt_list (mem_chain); 1120 break; 1121 } 1122 1123 mem_chain = &(*mem_chain)->next; 1124 } 1125 1126 unchain_one_elt_loc_list (p); 1127 } 1128 1129 if (had_locs && v->locs == 0) 1130 n_useless_values++; 1131 1132 return 1; 1133 } 1134 1135 /* Invalidate any locations in the table which are changed because of a 1136 store to MEM_RTX. If this is called because of a non-const call 1137 instruction, MEM_RTX is (mem:BLK const0_rtx). */ 1138 1139 static void 1140 cselib_invalidate_mem (mem_rtx) 1141 rtx mem_rtx; 1142 { 1143 htab_traverse (hash_table, cselib_invalidate_mem_1, mem_rtx); 1144 } 1145 1146 /* Invalidate DEST, which is being assigned to or clobbered. The second and 1147 the third parameter exist so that this function can be passed to 1148 note_stores; they are ignored. */ 1149 1150 static void 1151 cselib_invalidate_rtx (dest, ignore, data) 1152 rtx dest; 1153 rtx ignore ATTRIBUTE_UNUSED; 1154 void *data ATTRIBUTE_UNUSED; 1155 { 1156 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SIGN_EXTRACT 1157 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG) 1158 dest = XEXP (dest, 0); 1159 1160 if (GET_CODE (dest) == REG) 1161 cselib_invalidate_regno (REGNO (dest), GET_MODE (dest)); 1162 else if (GET_CODE (dest) == MEM) 1163 cselib_invalidate_mem (dest); 1164 1165 /* Some machines don't define AUTO_INC_DEC, but they still use push 1166 instructions. We need to catch that case here in order to 1167 invalidate the stack pointer correctly. Note that invalidating 1168 the stack pointer is different from invalidating DEST. */ 1169 if (push_operand (dest, GET_MODE (dest))) 1170 cselib_invalidate_rtx (stack_pointer_rtx, NULL_RTX, NULL); 1171 } 1172 1173 /* Record the result of a SET instruction. DEST is being set; the source 1174 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT 1175 describes its address. */ 1176 1177 static void 1178 cselib_record_set (dest, src_elt, dest_addr_elt) 1179 rtx dest; 1180 cselib_val *src_elt, *dest_addr_elt; 1181 { 1182 int dreg = GET_CODE (dest) == REG ? (int) REGNO (dest) : -1; 1183 1184 if (src_elt == 0 || side_effects_p (dest)) 1185 return; 1186 1187 if (dreg >= 0) 1188 { 1189 if (REG_VALUES (dreg) == 0) 1190 VARRAY_PUSH_UINT (used_regs, dreg); 1191 1192 if (dreg < FIRST_PSEUDO_REGISTER) 1193 { 1194 unsigned int n = HARD_REGNO_NREGS (dreg, GET_MODE (dest)); 1195 1196 if (n > max_value_regs) 1197 max_value_regs = n; 1198 } 1199 1200 REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt); 1201 if (src_elt->locs == 0) 1202 n_useless_values--; 1203 src_elt->locs = new_elt_loc_list (src_elt->locs, dest); 1204 } 1205 else if (GET_CODE (dest) == MEM && dest_addr_elt != 0) 1206 { 1207 if (src_elt->locs == 0) 1208 n_useless_values--; 1209 add_mem_for_addr (dest_addr_elt, src_elt, dest); 1210 } 1211 } 1212 1213 /* Describe a single set that is part of an insn. */ 1214 struct set 1215 { 1216 rtx src; 1217 rtx dest; 1218 cselib_val *src_elt; 1219 cselib_val *dest_addr_elt; 1220 }; 1221 1222 /* There is no good way to determine how many elements there can be 1223 in a PARALLEL. Since it's fairly cheap, use a really large number. */ 1224 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2) 1225 1226 /* Record the effects of any sets in INSN. */ 1227 static void 1228 cselib_record_sets (insn) 1229 rtx insn; 1230 { 1231 int n_sets = 0; 1232 int i; 1233 struct set sets[MAX_SETS]; 1234 rtx body = PATTERN (insn); 1235 rtx cond = 0; 1236 1237 body = PATTERN (insn); 1238 if (GET_CODE (body) == COND_EXEC) 1239 { 1240 cond = COND_EXEC_TEST (body); 1241 body = COND_EXEC_CODE (body); 1242 } 1243 1244 /* Find all sets. */ 1245 if (GET_CODE (body) == SET) 1246 { 1247 sets[0].src = SET_SRC (body); 1248 sets[0].dest = SET_DEST (body); 1249 n_sets = 1; 1250 } 1251 else if (GET_CODE (body) == PARALLEL) 1252 { 1253 /* Look through the PARALLEL and record the values being 1254 set, if possible. Also handle any CLOBBERs. */ 1255 for (i = XVECLEN (body, 0) - 1; i >= 0; --i) 1256 { 1257 rtx x = XVECEXP (body, 0, i); 1258 1259 if (GET_CODE (x) == SET) 1260 { 1261 sets[n_sets].src = SET_SRC (x); 1262 sets[n_sets].dest = SET_DEST (x); 1263 n_sets++; 1264 } 1265 } 1266 } 1267 1268 /* Look up the values that are read. Do this before invalidating the 1269 locations that are written. */ 1270 for (i = 0; i < n_sets; i++) 1271 { 1272 rtx dest = sets[i].dest; 1273 1274 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for 1275 the low part after invalidating any knowledge about larger modes. */ 1276 if (GET_CODE (sets[i].dest) == STRICT_LOW_PART) 1277 sets[i].dest = dest = XEXP (dest, 0); 1278 1279 /* We don't know how to record anything but REG or MEM. */ 1280 if (GET_CODE (dest) == REG || GET_CODE (dest) == MEM) 1281 { 1282 rtx src = sets[i].src; 1283 if (cond) 1284 src = gen_rtx_IF_THEN_ELSE (GET_MODE (src), cond, src, dest); 1285 sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1); 1286 if (GET_CODE (dest) == MEM) 1287 sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1); 1288 else 1289 sets[i].dest_addr_elt = 0; 1290 } 1291 } 1292 1293 /* Invalidate all locations written by this insn. Note that the elts we 1294 looked up in the previous loop aren't affected, just some of their 1295 locations may go away. */ 1296 note_stores (body, cselib_invalidate_rtx, NULL); 1297 1298 /* Now enter the equivalences in our tables. */ 1299 for (i = 0; i < n_sets; i++) 1300 { 1301 rtx dest = sets[i].dest; 1302 if (GET_CODE (dest) == REG || GET_CODE (dest) == MEM) 1303 cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt); 1304 } 1305 } 1306 1307 /* Record the effects of INSN. */ 1308 1309 void 1310 cselib_process_insn (insn) 1311 rtx insn; 1312 { 1313 int i; 1314 rtx x; 1315 1316 if (find_reg_note (insn, REG_LIBCALL, NULL)) 1317 cselib_current_insn_in_libcall = true; 1318 if (find_reg_note (insn, REG_RETVAL, NULL)) 1319 cselib_current_insn_in_libcall = false; 1320 cselib_current_insn = insn; 1321 1322 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */ 1323 if (GET_CODE (insn) == CODE_LABEL 1324 || (GET_CODE (insn) == CALL_INSN 1325 && find_reg_note (insn, REG_SETJMP, NULL)) 1326 || (GET_CODE (insn) == INSN 1327 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS 1328 && MEM_VOLATILE_P (PATTERN (insn)))) 1329 { 1330 clear_table (0); 1331 return; 1332 } 1333 1334 if (! INSN_P (insn)) 1335 { 1336 cselib_current_insn = 0; 1337 return; 1338 } 1339 1340 /* If this is a call instruction, forget anything stored in a 1341 call clobbered register, or, if this is not a const call, in 1342 memory. */ 1343 if (GET_CODE (insn) == CALL_INSN) 1344 { 1345 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1346 if (call_used_regs[i]) 1347 cselib_invalidate_regno (i, reg_raw_mode[i]); 1348 1349 if (! CONST_OR_PURE_CALL_P (insn)) 1350 cselib_invalidate_mem (callmem); 1351 } 1352 1353 cselib_record_sets (insn); 1354 1355 #ifdef AUTO_INC_DEC 1356 /* Clobber any registers which appear in REG_INC notes. We 1357 could keep track of the changes to their values, but it is 1358 unlikely to help. */ 1359 for (x = REG_NOTES (insn); x; x = XEXP (x, 1)) 1360 if (REG_NOTE_KIND (x) == REG_INC) 1361 cselib_invalidate_rtx (XEXP (x, 0), NULL_RTX, NULL); 1362 #endif 1363 1364 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only 1365 after we have processed the insn. */ 1366 if (GET_CODE (insn) == CALL_INSN) 1367 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1)) 1368 if (GET_CODE (XEXP (x, 0)) == CLOBBER) 1369 cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0), NULL_RTX, NULL); 1370 1371 cselib_current_insn = 0; 1372 1373 if (n_useless_values > MAX_USELESS_VALUES) 1374 remove_useless_values (); 1375 } 1376 1377 /* Make sure our varrays are big enough. Not called from any cselib routines; 1378 it must be called by the user if it allocated new registers. */ 1379 1380 void 1381 cselib_update_varray_sizes () 1382 { 1383 unsigned int nregs = max_reg_num (); 1384 1385 if (nregs == cselib_nregs) 1386 return; 1387 1388 cselib_nregs = nregs; 1389 VARRAY_GROW (reg_values, nregs); 1390 VARRAY_GROW (used_regs, nregs); 1391 } 1392 1393 /* Initialize cselib for one pass. The caller must also call 1394 init_alias_analysis. */ 1395 1396 void 1397 cselib_init () 1398 { 1399 /* This is only created once. */ 1400 if (! callmem) 1401 callmem = gen_rtx_MEM (BLKmode, const0_rtx); 1402 1403 cselib_nregs = max_reg_num (); 1404 if (reg_values_old != NULL && VARRAY_SIZE (reg_values_old) >= cselib_nregs) 1405 { 1406 reg_values = reg_values_old; 1407 used_regs = used_regs_old; 1408 VARRAY_CLEAR (reg_values); 1409 VARRAY_CLEAR (used_regs); 1410 } 1411 else 1412 { 1413 VARRAY_ELT_LIST_INIT (reg_values, cselib_nregs, "reg_values"); 1414 VARRAY_UINT_INIT (used_regs, cselib_nregs, "used_regs"); 1415 } 1416 hash_table = htab_create_ggc (31, get_value_hash, entry_and_rtx_equal_p, 1417 NULL); 1418 clear_table (1); 1419 cselib_current_insn_in_libcall = false; 1420 } 1421 1422 /* Called when the current user is done with cselib. */ 1423 1424 void 1425 cselib_finish () 1426 { 1427 reg_values_old = reg_values; 1428 reg_values = 0; 1429 used_regs_old = used_regs; 1430 used_regs = 0; 1431 hash_table = 0; 1432 n_useless_values = 0; 1433 next_unknown_value = 0; 1434 } 1435 1436 #include "gt-cselib.h" 1437