1/* Post reload partially redundant load elimination 2 Copyright (C) 2004, 2005 3 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "toplev.h" 27 28#include "rtl.h" 29#include "tree.h" 30#include "tm_p.h" 31#include "regs.h" 32#include "hard-reg-set.h" 33#include "flags.h" 34#include "real.h" 35#include "insn-config.h" 36#include "recog.h" 37#include "basic-block.h" 38#include "output.h" 39#include "function.h" 40#include "expr.h" 41#include "except.h" 42#include "intl.h" 43#include "obstack.h" 44#include "hashtab.h" 45#include "params.h" 46#include "target.h" 47#include "timevar.h" 48#include "tree-pass.h" 49 50/* The following code implements gcse after reload, the purpose of this 51 pass is to cleanup redundant loads generated by reload and other 52 optimizations that come after gcse. It searches for simple inter-block 53 redundancies and tries to eliminate them by adding moves and loads 54 in cold places. 55 56 Perform partially redundant load elimination, try to eliminate redundant 57 loads created by the reload pass. We try to look for full or partial 58 redundant loads fed by one or more loads/stores in predecessor BBs, 59 and try adding loads to make them fully redundant. We also check if 60 it's worth adding loads to be able to delete the redundant load. 61 62 Algorithm: 63 1. Build available expressions hash table: 64 For each load/store instruction, if the loaded/stored memory didn't 65 change until the end of the basic block add this memory expression to 66 the hash table. 67 2. Perform Redundancy elimination: 68 For each load instruction do the following: 69 perform partial redundancy elimination, check if it's worth adding 70 loads to make the load fully redundant. If so add loads and 71 register copies and delete the load. 72 3. Delete instructions made redundant in step 2. 73 74 Future enhancement: 75 If the loaded register is used/defined between load and some store, 76 look for some other free register between load and all its stores, 77 and replace the load with a copy from this register to the loaded 78 register. 79*/ 80 81 82/* Keep statistics of this pass. */ 83static struct 84{ 85 int moves_inserted; 86 int copies_inserted; 87 int insns_deleted; 88} stats; 89 90/* We need to keep a hash table of expressions. The table entries are of 91 type 'struct expr', and for each expression there is a single linked 92 list of occurrences. */ 93 94/* The table itself. */ 95static htab_t expr_table; 96 97/* Expression elements in the hash table. */ 98struct expr 99{ 100 /* The expression (SET_SRC for expressions, PATTERN for assignments). */ 101 rtx expr; 102 103 /* The same hash for this entry. */ 104 hashval_t hash; 105 106 /* List of available occurrence in basic blocks in the function. */ 107 struct occr *avail_occr; 108}; 109 110static struct obstack expr_obstack; 111 112/* Occurrence of an expression. 113 There is at most one occurrence per basic block. If a pattern appears 114 more than once, the last appearance is used. */ 115 116struct occr 117{ 118 /* Next occurrence of this expression. */ 119 struct occr *next; 120 /* The insn that computes the expression. */ 121 rtx insn; 122 /* Nonzero if this [anticipatable] occurrence has been deleted. */ 123 char deleted_p; 124}; 125 126static struct obstack occr_obstack; 127 128/* The following structure holds the information about the occurrences of 129 the redundant instructions. */ 130struct unoccr 131{ 132 struct unoccr *next; 133 edge pred; 134 rtx insn; 135}; 136 137static struct obstack unoccr_obstack; 138 139/* Array where each element is the CUID if the insn that last set the hard 140 register with the number of the element, since the start of the current 141 basic block. 142 143 This array is used during the building of the hash table (step 1) to 144 determine if a reg is killed before the end of a basic block. 145 146 It is also used when eliminating partial redundancies (step 2) to see 147 if a reg was modified since the start of a basic block. */ 148static int *reg_avail_info; 149 150/* A list of insns that may modify memory within the current basic block. */ 151struct modifies_mem 152{ 153 rtx insn; 154 struct modifies_mem *next; 155}; 156static struct modifies_mem *modifies_mem_list; 157 158/* The modifies_mem structs also go on an obstack, only this obstack is 159 freed each time after completing the analysis or transformations on 160 a basic block. So we allocate a dummy modifies_mem_obstack_bottom 161 object on the obstack to keep track of the bottom of the obstack. */ 162static struct obstack modifies_mem_obstack; 163static struct modifies_mem *modifies_mem_obstack_bottom; 164 165/* Mapping of insn UIDs to CUIDs. 166 CUIDs are like UIDs except they increase monotonically in each basic 167 block, have no gaps, and only apply to real insns. */ 168static int *uid_cuid; 169#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)]) 170 171 172/* Helpers for memory allocation/freeing. */ 173static void alloc_mem (void); 174static void free_mem (void); 175 176/* Support for hash table construction and transformations. */ 177static bool oprs_unchanged_p (rtx, rtx, bool); 178static void record_last_reg_set_info (rtx, int); 179static void record_last_mem_set_info (rtx); 180static void record_last_set_info (rtx, rtx, void *); 181static void record_opr_changes (rtx); 182 183static void find_mem_conflicts (rtx, rtx, void *); 184static int load_killed_in_block_p (int, rtx, bool); 185static void reset_opr_set_tables (void); 186 187/* Hash table support. */ 188static hashval_t hash_expr (rtx, int *); 189static hashval_t hash_expr_for_htab (const void *); 190static int expr_equiv_p (const void *, const void *); 191static void insert_expr_in_table (rtx, rtx); 192static struct expr *lookup_expr_in_table (rtx); 193static int dump_hash_table_entry (void **, void *); 194static void dump_hash_table (FILE *); 195 196/* Helpers for eliminate_partially_redundant_load. */ 197static bool reg_killed_on_edge (rtx, edge); 198static bool reg_used_on_edge (rtx, edge); 199 200static rtx get_avail_load_store_reg (rtx); 201 202static bool bb_has_well_behaved_predecessors (basic_block); 203static struct occr* get_bb_avail_insn (basic_block, struct occr *); 204static void hash_scan_set (rtx); 205static void compute_hash_table (void); 206 207/* The work horses of this pass. */ 208static void eliminate_partially_redundant_load (basic_block, 209 rtx, 210 struct expr *); 211static void eliminate_partially_redundant_loads (void); 212 213 214/* Allocate memory for the CUID mapping array and register/memory 215 tracking tables. */ 216 217static void 218alloc_mem (void) 219{ 220 int i; 221 basic_block bb; 222 rtx insn; 223 224 /* Find the largest UID and create a mapping from UIDs to CUIDs. */ 225 uid_cuid = XCNEWVEC (int, get_max_uid () + 1); 226 i = 1; 227 FOR_EACH_BB (bb) 228 FOR_BB_INSNS (bb, insn) 229 { 230 if (INSN_P (insn)) 231 uid_cuid[INSN_UID (insn)] = i++; 232 else 233 uid_cuid[INSN_UID (insn)] = i; 234 } 235 236 /* Allocate the available expressions hash table. We don't want to 237 make the hash table too small, but unnecessarily making it too large 238 also doesn't help. The i/4 is a gcse.c relic, and seems like a 239 reasonable choice. */ 240 expr_table = htab_create (MAX (i / 4, 13), 241 hash_expr_for_htab, expr_equiv_p, NULL); 242 243 /* We allocate everything on obstacks because we often can roll back 244 the whole obstack to some point. Freeing obstacks is very fast. */ 245 gcc_obstack_init (&expr_obstack); 246 gcc_obstack_init (&occr_obstack); 247 gcc_obstack_init (&unoccr_obstack); 248 gcc_obstack_init (&modifies_mem_obstack); 249 250 /* Working array used to track the last set for each register 251 in the current block. */ 252 reg_avail_info = (int *) xmalloc (FIRST_PSEUDO_REGISTER * sizeof (int)); 253 254 /* Put a dummy modifies_mem object on the modifies_mem_obstack, so we 255 can roll it back in reset_opr_set_tables. */ 256 modifies_mem_obstack_bottom = 257 (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack, 258 sizeof (struct modifies_mem)); 259} 260 261/* Free memory allocated by alloc_mem. */ 262 263static void 264free_mem (void) 265{ 266 free (uid_cuid); 267 268 htab_delete (expr_table); 269 270 obstack_free (&expr_obstack, NULL); 271 obstack_free (&occr_obstack, NULL); 272 obstack_free (&unoccr_obstack, NULL); 273 obstack_free (&modifies_mem_obstack, NULL); 274 275 free (reg_avail_info); 276} 277 278 279/* Hash expression X. 280 DO_NOT_RECORD_P is a boolean indicating if a volatile operand is found 281 or if the expression contains something we don't want to insert in the 282 table. */ 283 284static hashval_t 285hash_expr (rtx x, int *do_not_record_p) 286{ 287 *do_not_record_p = 0; 288 return hash_rtx (x, GET_MODE (x), do_not_record_p, 289 NULL, /*have_reg_qty=*/false); 290} 291 292/* Callback for hashtab. 293 Return the hash value for expression EXP. We don't actually hash 294 here, we just return the cached hash value. */ 295 296static hashval_t 297hash_expr_for_htab (const void *expp) 298{ 299 struct expr *exp = (struct expr *) expp; 300 return exp->hash; 301} 302 303/* Callback for hashtab. 304 Return nonzero if exp1 is equivalent to exp2. */ 305 306static int 307expr_equiv_p (const void *exp1p, const void *exp2p) 308{ 309 struct expr *exp1 = (struct expr *) exp1p; 310 struct expr *exp2 = (struct expr *) exp2p; 311 int equiv_p = exp_equiv_p (exp1->expr, exp2->expr, 0, true); 312 313 gcc_assert (!equiv_p || exp1->hash == exp2->hash); 314 return equiv_p; 315} 316 317 318/* Insert expression X in INSN in the hash TABLE. 319 If it is already present, record it as the last occurrence in INSN's 320 basic block. */ 321 322static void 323insert_expr_in_table (rtx x, rtx insn) 324{ 325 int do_not_record_p; 326 hashval_t hash; 327 struct expr *cur_expr, **slot; 328 struct occr *avail_occr, *last_occr = NULL; 329 330 hash = hash_expr (x, &do_not_record_p); 331 332 /* Do not insert expression in the table if it contains volatile operands, 333 or if hash_expr determines the expression is something we don't want 334 to or can't handle. */ 335 if (do_not_record_p) 336 return; 337 338 /* We anticipate that redundant expressions are rare, so for convenience 339 allocate a new hash table element here already and set its fields. 340 If we don't do this, we need a hack with a static struct expr. Anyway, 341 obstack_free is really fast and one more obstack_alloc doesn't hurt if 342 we're going to see more expressions later on. */ 343 cur_expr = (struct expr *) obstack_alloc (&expr_obstack, 344 sizeof (struct expr)); 345 cur_expr->expr = x; 346 cur_expr->hash = hash; 347 cur_expr->avail_occr = NULL; 348 349 slot = (struct expr **) htab_find_slot_with_hash (expr_table, cur_expr, 350 hash, INSERT); 351 352 if (! (*slot)) 353 /* The expression isn't found, so insert it. */ 354 *slot = cur_expr; 355 else 356 { 357 /* The expression is already in the table, so roll back the 358 obstack and use the existing table entry. */ 359 obstack_free (&expr_obstack, cur_expr); 360 cur_expr = *slot; 361 } 362 363 /* Search for another occurrence in the same basic block. */ 364 avail_occr = cur_expr->avail_occr; 365 while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn)) 366 { 367 /* If an occurrence isn't found, save a pointer to the end of 368 the list. */ 369 last_occr = avail_occr; 370 avail_occr = avail_occr->next; 371 } 372 373 if (avail_occr) 374 /* Found another instance of the expression in the same basic block. 375 Prefer this occurrence to the currently recorded one. We want 376 the last one in the block and the block is scanned from start 377 to end. */ 378 avail_occr->insn = insn; 379 else 380 { 381 /* First occurrence of this expression in this basic block. */ 382 avail_occr = (struct occr *) obstack_alloc (&occr_obstack, 383 sizeof (struct occr)); 384 385 /* First occurrence of this expression in any block? */ 386 if (cur_expr->avail_occr == NULL) 387 cur_expr->avail_occr = avail_occr; 388 else 389 last_occr->next = avail_occr; 390 391 avail_occr->insn = insn; 392 avail_occr->next = NULL; 393 avail_occr->deleted_p = 0; 394 } 395} 396 397 398/* Lookup pattern PAT in the expression hash table. 399 The result is a pointer to the table entry, or NULL if not found. */ 400 401static struct expr * 402lookup_expr_in_table (rtx pat) 403{ 404 int do_not_record_p; 405 struct expr **slot, *tmp_expr; 406 hashval_t hash = hash_expr (pat, &do_not_record_p); 407 408 if (do_not_record_p) 409 return NULL; 410 411 tmp_expr = (struct expr *) obstack_alloc (&expr_obstack, 412 sizeof (struct expr)); 413 tmp_expr->expr = pat; 414 tmp_expr->hash = hash; 415 tmp_expr->avail_occr = NULL; 416 417 slot = (struct expr **) htab_find_slot_with_hash (expr_table, tmp_expr, 418 hash, INSERT); 419 obstack_free (&expr_obstack, tmp_expr); 420 421 if (!slot) 422 return NULL; 423 else 424 return (*slot); 425} 426 427 428/* Dump all expressions and occurrences that are currently in the 429 expression hash table to FILE. */ 430 431/* This helper is called via htab_traverse. */ 432static int 433dump_hash_table_entry (void **slot, void *filep) 434{ 435 struct expr *expr = (struct expr *) *slot; 436 FILE *file = (FILE *) filep; 437 struct occr *occr; 438 439 fprintf (file, "expr: "); 440 print_rtl (file, expr->expr); 441 fprintf (file,"\nhashcode: %u\n", expr->hash); 442 fprintf (file,"list of occurrences:\n"); 443 occr = expr->avail_occr; 444 while (occr) 445 { 446 rtx insn = occr->insn; 447 print_rtl_single (file, insn); 448 fprintf (file, "\n"); 449 occr = occr->next; 450 } 451 fprintf (file, "\n"); 452 return 1; 453} 454 455static void 456dump_hash_table (FILE *file) 457{ 458 fprintf (file, "\n\nexpression hash table\n"); 459 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", 460 (long) htab_size (expr_table), 461 (long) htab_elements (expr_table), 462 htab_collisions (expr_table)); 463 if (htab_elements (expr_table) > 0) 464 { 465 fprintf (file, "\n\ntable entries:\n"); 466 htab_traverse (expr_table, dump_hash_table_entry, file); 467 } 468 fprintf (file, "\n"); 469} 470 471/* Return true if register X is recorded as being set by an instruction 472 whose CUID is greater than the one given. */ 473 474static bool 475reg_changed_after_insn_p (rtx x, int cuid) 476{ 477 unsigned int regno, end_regno; 478 479 regno = REGNO (x); 480 end_regno = END_HARD_REGNO (x); 481 do 482 if (reg_avail_info[regno] > cuid) 483 return true; 484 while (++regno < end_regno); 485 return false; 486} 487 488/* Return nonzero if the operands of expression X are unchanged 489 1) from the start of INSN's basic block up to but not including INSN 490 if AFTER_INSN is false, or 491 2) from INSN to the end of INSN's basic block if AFTER_INSN is true. */ 492 493static bool 494oprs_unchanged_p (rtx x, rtx insn, bool after_insn) 495{ 496 int i, j; 497 enum rtx_code code; 498 const char *fmt; 499 500 if (x == 0) 501 return 1; 502 503 code = GET_CODE (x); 504 switch (code) 505 { 506 case REG: 507 /* We are called after register allocation. */ 508 gcc_assert (REGNO (x) < FIRST_PSEUDO_REGISTER); 509 if (after_insn) 510 return !reg_changed_after_insn_p (x, INSN_CUID (insn) - 1); 511 else 512 return !reg_changed_after_insn_p (x, 0); 513 514 case MEM: 515 if (load_killed_in_block_p (INSN_CUID (insn), x, after_insn)) 516 return 0; 517 else 518 return oprs_unchanged_p (XEXP (x, 0), insn, after_insn); 519 520 case PC: 521 case CC0: /*FIXME*/ 522 case CONST: 523 case CONST_INT: 524 case CONST_DOUBLE: 525 case CONST_VECTOR: 526 case SYMBOL_REF: 527 case LABEL_REF: 528 case ADDR_VEC: 529 case ADDR_DIFF_VEC: 530 return 1; 531 532 case PRE_DEC: 533 case PRE_INC: 534 case POST_DEC: 535 case POST_INC: 536 case PRE_MODIFY: 537 case POST_MODIFY: 538 if (after_insn) 539 return 0; 540 break; 541 542 default: 543 break; 544 } 545 546 for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--) 547 { 548 if (fmt[i] == 'e') 549 { 550 if (! oprs_unchanged_p (XEXP (x, i), insn, after_insn)) 551 return 0; 552 } 553 else if (fmt[i] == 'E') 554 for (j = 0; j < XVECLEN (x, i); j++) 555 if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, after_insn)) 556 return 0; 557 } 558 559 return 1; 560} 561 562 563/* Used for communication between find_mem_conflicts and 564 load_killed_in_block_p. Nonzero if find_mem_conflicts finds a 565 conflict between two memory references. 566 This is a bit of a hack to work around the limitations of note_stores. */ 567static int mems_conflict_p; 568 569/* DEST is the output of an instruction. If it is a memory reference, and 570 possibly conflicts with the load found in DATA, then set mems_conflict_p 571 to a nonzero value. */ 572 573static void 574find_mem_conflicts (rtx dest, rtx setter ATTRIBUTE_UNUSED, 575 void *data) 576{ 577 rtx mem_op = (rtx) data; 578 579 while (GET_CODE (dest) == SUBREG 580 || GET_CODE (dest) == ZERO_EXTRACT 581 || GET_CODE (dest) == STRICT_LOW_PART) 582 dest = XEXP (dest, 0); 583 584 /* If DEST is not a MEM, then it will not conflict with the load. Note 585 that function calls are assumed to clobber memory, but are handled 586 elsewhere. */ 587 if (! MEM_P (dest)) 588 return; 589 590 if (true_dependence (dest, GET_MODE (dest), mem_op, 591 rtx_addr_varies_p)) 592 mems_conflict_p = 1; 593} 594 595 596/* Return nonzero if the expression in X (a memory reference) is killed 597 in the current basic block before (if AFTER_INSN is false) or after 598 (if AFTER_INSN is true) the insn with the CUID in UID_LIMIT. 599 600 This function assumes that the modifies_mem table is flushed when 601 the hash table construction or redundancy elimination phases start 602 processing a new basic block. */ 603 604static int 605load_killed_in_block_p (int uid_limit, rtx x, bool after_insn) 606{ 607 struct modifies_mem *list_entry = modifies_mem_list; 608 609 while (list_entry) 610 { 611 rtx setter = list_entry->insn; 612 613 /* Ignore entries in the list that do not apply. */ 614 if ((after_insn 615 && INSN_CUID (setter) < uid_limit) 616 || (! after_insn 617 && INSN_CUID (setter) > uid_limit)) 618 { 619 list_entry = list_entry->next; 620 continue; 621 } 622 623 /* If SETTER is a call everything is clobbered. Note that calls 624 to pure functions are never put on the list, so we need not 625 worry about them. */ 626 if (CALL_P (setter)) 627 return 1; 628 629 /* SETTER must be an insn of some kind that sets memory. Call 630 note_stores to examine each hunk of memory that is modified. 631 It will set mems_conflict_p to nonzero if there may be a 632 conflict between X and SETTER. */ 633 mems_conflict_p = 0; 634 note_stores (PATTERN (setter), find_mem_conflicts, x); 635 if (mems_conflict_p) 636 return 1; 637 638 list_entry = list_entry->next; 639 } 640 return 0; 641} 642 643 644/* Record register first/last/block set information for REGNO in INSN. */ 645 646static inline void 647record_last_reg_set_info (rtx insn, int regno) 648{ 649 reg_avail_info[regno] = INSN_CUID (insn); 650} 651 652 653/* Record memory modification information for INSN. We do not actually care 654 about the memory location(s) that are set, or even how they are set (consider 655 a CALL_INSN). We merely need to record which insns modify memory. */ 656 657static void 658record_last_mem_set_info (rtx insn) 659{ 660 struct modifies_mem *list_entry; 661 662 list_entry = (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack, 663 sizeof (struct modifies_mem)); 664 list_entry->insn = insn; 665 list_entry->next = modifies_mem_list; 666 modifies_mem_list = list_entry; 667} 668 669/* Called from compute_hash_table via note_stores to handle one 670 SET or CLOBBER in an insn. DATA is really the instruction in which 671 the SET is taking place. */ 672 673static void 674record_last_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data) 675{ 676 rtx last_set_insn = (rtx) data; 677 678 if (GET_CODE (dest) == SUBREG) 679 dest = SUBREG_REG (dest); 680 681 if (REG_P (dest)) 682 record_last_reg_set_info (last_set_insn, REGNO (dest)); 683 else if (MEM_P (dest)) 684 { 685 /* Ignore pushes, they don't clobber memory. They may still 686 clobber the stack pointer though. Some targets do argument 687 pushes without adding REG_INC notes. See e.g. PR25196, 688 where a pushsi2 on i386 doesn't have REG_INC notes. Note 689 such changes here too. */ 690 if (! push_operand (dest, GET_MODE (dest))) 691 record_last_mem_set_info (last_set_insn); 692 else 693 record_last_reg_set_info (last_set_insn, STACK_POINTER_REGNUM); 694 } 695} 696 697 698/* Reset tables used to keep track of what's still available since the 699 start of the block. */ 700 701static void 702reset_opr_set_tables (void) 703{ 704 memset (reg_avail_info, 0, FIRST_PSEUDO_REGISTER * sizeof (int)); 705 obstack_free (&modifies_mem_obstack, modifies_mem_obstack_bottom); 706 modifies_mem_list = NULL; 707} 708 709 710/* Record things set by INSN. 711 This data is used by oprs_unchanged_p. */ 712 713static void 714record_opr_changes (rtx insn) 715{ 716 rtx note; 717 718 /* Find all stores and record them. */ 719 note_stores (PATTERN (insn), record_last_set_info, insn); 720 721 /* Also record autoincremented REGs for this insn as changed. */ 722 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 723 if (REG_NOTE_KIND (note) == REG_INC) 724 record_last_reg_set_info (insn, REGNO (XEXP (note, 0))); 725 726 /* Finally, if this is a call, record all call clobbers. */ 727 if (CALL_P (insn)) 728 { 729 unsigned int regno, end_regno; 730 rtx link, x; 731 732 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) 733 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)) 734 record_last_reg_set_info (insn, regno); 735 736 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1)) 737 if (GET_CODE (XEXP (link, 0)) == CLOBBER) 738 { 739 x = XEXP (XEXP (link, 0), 0); 740 if (REG_P (x)) 741 { 742 gcc_assert (HARD_REGISTER_P (x)); 743 regno = REGNO (x); 744 end_regno = END_HARD_REGNO (x); 745 do 746 record_last_reg_set_info (insn, regno); 747 while (++regno < end_regno); 748 } 749 } 750 751 if (! CONST_OR_PURE_CALL_P (insn)) 752 record_last_mem_set_info (insn); 753 } 754} 755 756 757/* Scan the pattern of INSN and add an entry to the hash TABLE. 758 After reload we are interested in loads/stores only. */ 759 760static void 761hash_scan_set (rtx insn) 762{ 763 rtx pat = PATTERN (insn); 764 rtx src = SET_SRC (pat); 765 rtx dest = SET_DEST (pat); 766 767 /* We are only interested in loads and stores. */ 768 if (! MEM_P (src) && ! MEM_P (dest)) 769 return; 770 771 /* Don't mess with jumps and nops. */ 772 if (JUMP_P (insn) || set_noop_p (pat)) 773 return; 774 775 if (REG_P (dest)) 776 { 777 if (/* Don't CSE something if we can't do a reg/reg copy. */ 778 can_copy_p (GET_MODE (dest)) 779 /* Is SET_SRC something we want to gcse? */ 780 && general_operand (src, GET_MODE (src)) 781#ifdef STACK_REGS 782 /* Never consider insns touching the register stack. It may 783 create situations that reg-stack cannot handle (e.g. a stack 784 register live across an abnormal edge). */ 785 && (REGNO (dest) < FIRST_STACK_REG || REGNO (dest) > LAST_STACK_REG) 786#endif 787 /* An expression is not available if its operands are 788 subsequently modified, including this insn. */ 789 && oprs_unchanged_p (src, insn, true)) 790 { 791 insert_expr_in_table (src, insn); 792 } 793 } 794 else if (REG_P (src)) 795 { 796 /* Only record sets of pseudo-regs in the hash table. */ 797 if (/* Don't CSE something if we can't do a reg/reg copy. */ 798 can_copy_p (GET_MODE (src)) 799 /* Is SET_DEST something we want to gcse? */ 800 && general_operand (dest, GET_MODE (dest)) 801#ifdef STACK_REGS 802 /* As above for STACK_REGS. */ 803 && (REGNO (src) < FIRST_STACK_REG || REGNO (src) > LAST_STACK_REG) 804#endif 805 && ! (flag_float_store && FLOAT_MODE_P (GET_MODE (dest))) 806 /* Check if the memory expression is killed after insn. */ 807 && ! load_killed_in_block_p (INSN_CUID (insn) + 1, dest, true) 808 && oprs_unchanged_p (XEXP (dest, 0), insn, true)) 809 { 810 insert_expr_in_table (dest, insn); 811 } 812 } 813} 814 815 816/* Create hash table of memory expressions available at end of basic 817 blocks. Basically you should think of this hash table as the 818 representation of AVAIL_OUT. This is the set of expressions that 819 is generated in a basic block and not killed before the end of the 820 same basic block. Notice that this is really a local computation. */ 821 822static void 823compute_hash_table (void) 824{ 825 basic_block bb; 826 827 FOR_EACH_BB (bb) 828 { 829 rtx insn; 830 831 /* First pass over the instructions records information used to 832 determine when registers and memory are last set. 833 Since we compute a "local" AVAIL_OUT, reset the tables that 834 help us keep track of what has been modified since the start 835 of the block. */ 836 reset_opr_set_tables (); 837 FOR_BB_INSNS (bb, insn) 838 { 839 if (INSN_P (insn)) 840 record_opr_changes (insn); 841 } 842 843 /* The next pass actually builds the hash table. */ 844 FOR_BB_INSNS (bb, insn) 845 if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == SET) 846 hash_scan_set (insn); 847 } 848} 849 850 851/* Check if register REG is killed in any insn waiting to be inserted on 852 edge E. This function is required to check that our data flow analysis 853 is still valid prior to commit_edge_insertions. */ 854 855static bool 856reg_killed_on_edge (rtx reg, edge e) 857{ 858 rtx insn; 859 860 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn)) 861 if (INSN_P (insn) && reg_set_p (reg, insn)) 862 return true; 863 864 return false; 865} 866 867/* Similar to above - check if register REG is used in any insn waiting 868 to be inserted on edge E. 869 Assumes no such insn can be a CALL_INSN; if so call reg_used_between_p 870 with PREV(insn),NEXT(insn) instead of calling reg_overlap_mentioned_p. */ 871 872static bool 873reg_used_on_edge (rtx reg, edge e) 874{ 875 rtx insn; 876 877 for (insn = e->insns.r; insn; insn = NEXT_INSN (insn)) 878 if (INSN_P (insn) && reg_overlap_mentioned_p (reg, PATTERN (insn))) 879 return true; 880 881 return false; 882} 883 884/* Return the loaded/stored register of a load/store instruction. */ 885 886static rtx 887get_avail_load_store_reg (rtx insn) 888{ 889 if (REG_P (SET_DEST (PATTERN (insn)))) 890 /* A load. */ 891 return SET_DEST(PATTERN(insn)); 892 else 893 { 894 /* A store. */ 895 gcc_assert (REG_P (SET_SRC (PATTERN (insn)))); 896 return SET_SRC (PATTERN (insn)); 897 } 898} 899 900/* Return nonzero if the predecessors of BB are "well behaved". */ 901 902static bool 903bb_has_well_behaved_predecessors (basic_block bb) 904{ 905 edge pred; 906 edge_iterator ei; 907 908 if (EDGE_COUNT (bb->preds) == 0) 909 return false; 910 911 FOR_EACH_EDGE (pred, ei, bb->preds) 912 { 913 if ((pred->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (pred)) 914 return false; 915 916 if (JUMP_TABLE_DATA_P (BB_END (pred->src))) 917 return false; 918 } 919 return true; 920} 921 922 923/* Search for the occurrences of expression in BB. */ 924 925static struct occr* 926get_bb_avail_insn (basic_block bb, struct occr *occr) 927{ 928 for (; occr != NULL; occr = occr->next) 929 if (BLOCK_FOR_INSN (occr->insn) == bb) 930 return occr; 931 return NULL; 932} 933 934 935/* This handles the case where several stores feed a partially redundant 936 load. It checks if the redundancy elimination is possible and if it's 937 worth it. 938 939 Redundancy elimination is possible if, 940 1) None of the operands of an insn have been modified since the start 941 of the current basic block. 942 2) In any predecessor of the current basic block, the same expression 943 is generated. 944 945 See the function body for the heuristics that determine if eliminating 946 a redundancy is also worth doing, assuming it is possible. */ 947 948static void 949eliminate_partially_redundant_load (basic_block bb, rtx insn, 950 struct expr *expr) 951{ 952 edge pred; 953 rtx avail_insn = NULL_RTX; 954 rtx avail_reg; 955 rtx dest, pat; 956 struct occr *a_occr; 957 struct unoccr *occr, *avail_occrs = NULL; 958 struct unoccr *unoccr, *unavail_occrs = NULL, *rollback_unoccr = NULL; 959 int npred_ok = 0; 960 gcov_type ok_count = 0; /* Redundant load execution count. */ 961 gcov_type critical_count = 0; /* Execution count of critical edges. */ 962 edge_iterator ei; 963 bool critical_edge_split = false; 964 965 /* The execution count of the loads to be added to make the 966 load fully redundant. */ 967 gcov_type not_ok_count = 0; 968 basic_block pred_bb; 969 970 pat = PATTERN (insn); 971 dest = SET_DEST (pat); 972 973 /* Check that the loaded register is not used, set, or killed from the 974 beginning of the block. */ 975 if (reg_changed_after_insn_p (dest, 0) 976 || reg_used_between_p (dest, PREV_INSN (BB_HEAD (bb)), insn)) 977 return; 978 979 /* Check potential for replacing load with copy for predecessors. */ 980 FOR_EACH_EDGE (pred, ei, bb->preds) 981 { 982 rtx next_pred_bb_end; 983 984 avail_insn = NULL_RTX; 985 avail_reg = NULL_RTX; 986 pred_bb = pred->src; 987 next_pred_bb_end = NEXT_INSN (BB_END (pred_bb)); 988 for (a_occr = get_bb_avail_insn (pred_bb, expr->avail_occr); a_occr; 989 a_occr = get_bb_avail_insn (pred_bb, a_occr->next)) 990 { 991 /* Check if the loaded register is not used. */ 992 avail_insn = a_occr->insn; 993 avail_reg = get_avail_load_store_reg (avail_insn); 994 gcc_assert (avail_reg); 995 996 /* Make sure we can generate a move from register avail_reg to 997 dest. */ 998 extract_insn (gen_move_insn (copy_rtx (dest), 999 copy_rtx (avail_reg))); 1000 if (! constrain_operands (1) 1001 || reg_killed_on_edge (avail_reg, pred) 1002 || reg_used_on_edge (dest, pred)) 1003 { 1004 avail_insn = NULL; 1005 continue; 1006 } 1007 if (!reg_set_between_p (avail_reg, avail_insn, next_pred_bb_end)) 1008 /* AVAIL_INSN remains non-null. */ 1009 break; 1010 else 1011 avail_insn = NULL; 1012 } 1013 1014 if (EDGE_CRITICAL_P (pred)) 1015 critical_count += pred->count; 1016 1017 if (avail_insn != NULL_RTX) 1018 { 1019 npred_ok++; 1020 ok_count += pred->count; 1021 if (! set_noop_p (PATTERN (gen_move_insn (copy_rtx (dest), 1022 copy_rtx (avail_reg))))) 1023 { 1024 /* Check if there is going to be a split. */ 1025 if (EDGE_CRITICAL_P (pred)) 1026 critical_edge_split = true; 1027 } 1028 else /* Its a dead move no need to generate. */ 1029 continue; 1030 occr = (struct unoccr *) obstack_alloc (&unoccr_obstack, 1031 sizeof (struct unoccr)); 1032 occr->insn = avail_insn; 1033 occr->pred = pred; 1034 occr->next = avail_occrs; 1035 avail_occrs = occr; 1036 if (! rollback_unoccr) 1037 rollback_unoccr = occr; 1038 } 1039 else 1040 { 1041 /* Adding a load on a critical edge will cause a split. */ 1042 if (EDGE_CRITICAL_P (pred)) 1043 critical_edge_split = true; 1044 not_ok_count += pred->count; 1045 unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack, 1046 sizeof (struct unoccr)); 1047 unoccr->insn = NULL_RTX; 1048 unoccr->pred = pred; 1049 unoccr->next = unavail_occrs; 1050 unavail_occrs = unoccr; 1051 if (! rollback_unoccr) 1052 rollback_unoccr = unoccr; 1053 } 1054 } 1055 1056 if (/* No load can be replaced by copy. */ 1057 npred_ok == 0 1058 /* Prevent exploding the code. */ 1059 || (optimize_size && npred_ok > 1) 1060 /* If we don't have profile information we cannot tell if splitting 1061 a critical edge is profitable or not so don't do it. */ 1062 || ((! profile_info || ! flag_branch_probabilities 1063 || targetm.cannot_modify_jumps_p ()) 1064 && critical_edge_split)) 1065 goto cleanup; 1066 1067 /* Check if it's worth applying the partial redundancy elimination. */ 1068 if (ok_count < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count) 1069 goto cleanup; 1070 if (ok_count < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count) 1071 goto cleanup; 1072 1073 /* Generate moves to the loaded register from where 1074 the memory is available. */ 1075 for (occr = avail_occrs; occr; occr = occr->next) 1076 { 1077 avail_insn = occr->insn; 1078 pred = occr->pred; 1079 /* Set avail_reg to be the register having the value of the 1080 memory. */ 1081 avail_reg = get_avail_load_store_reg (avail_insn); 1082 gcc_assert (avail_reg); 1083 1084 insert_insn_on_edge (gen_move_insn (copy_rtx (dest), 1085 copy_rtx (avail_reg)), 1086 pred); 1087 stats.moves_inserted++; 1088 1089 if (dump_file) 1090 fprintf (dump_file, 1091 "generating move from %d to %d on edge from %d to %d\n", 1092 REGNO (avail_reg), 1093 REGNO (dest), 1094 pred->src->index, 1095 pred->dest->index); 1096 } 1097 1098 /* Regenerate loads where the memory is unavailable. */ 1099 for (unoccr = unavail_occrs; unoccr; unoccr = unoccr->next) 1100 { 1101 pred = unoccr->pred; 1102 insert_insn_on_edge (copy_insn (PATTERN (insn)), pred); 1103 stats.copies_inserted++; 1104 1105 if (dump_file) 1106 { 1107 fprintf (dump_file, 1108 "generating on edge from %d to %d a copy of load: ", 1109 pred->src->index, 1110 pred->dest->index); 1111 print_rtl (dump_file, PATTERN (insn)); 1112 fprintf (dump_file, "\n"); 1113 } 1114 } 1115 1116 /* Delete the insn if it is not available in this block and mark it 1117 for deletion if it is available. If insn is available it may help 1118 discover additional redundancies, so mark it for later deletion. */ 1119 for (a_occr = get_bb_avail_insn (bb, expr->avail_occr); 1120 a_occr && (a_occr->insn != insn); 1121 a_occr = get_bb_avail_insn (bb, a_occr->next)); 1122 1123 if (!a_occr) 1124 { 1125 stats.insns_deleted++; 1126 1127 if (dump_file) 1128 { 1129 fprintf (dump_file, "deleting insn:\n"); 1130 print_rtl_single (dump_file, insn); 1131 fprintf (dump_file, "\n"); 1132 } 1133 delete_insn (insn); 1134 } 1135 else 1136 a_occr->deleted_p = 1; 1137 1138cleanup: 1139 if (rollback_unoccr) 1140 obstack_free (&unoccr_obstack, rollback_unoccr); 1141} 1142 1143/* Performing the redundancy elimination as described before. */ 1144 1145static void 1146eliminate_partially_redundant_loads (void) 1147{ 1148 rtx insn; 1149 basic_block bb; 1150 1151 /* Note we start at block 1. */ 1152 1153 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) 1154 return; 1155 1156 FOR_BB_BETWEEN (bb, 1157 ENTRY_BLOCK_PTR->next_bb->next_bb, 1158 EXIT_BLOCK_PTR, 1159 next_bb) 1160 { 1161 /* Don't try anything on basic blocks with strange predecessors. */ 1162 if (! bb_has_well_behaved_predecessors (bb)) 1163 continue; 1164 1165 /* Do not try anything on cold basic blocks. */ 1166 if (probably_cold_bb_p (bb)) 1167 continue; 1168 1169 /* Reset the table of things changed since the start of the current 1170 basic block. */ 1171 reset_opr_set_tables (); 1172 1173 /* Look at all insns in the current basic block and see if there are 1174 any loads in it that we can record. */ 1175 FOR_BB_INSNS (bb, insn) 1176 { 1177 /* Is it a load - of the form (set (reg) (mem))? */ 1178 if (NONJUMP_INSN_P (insn) 1179 && GET_CODE (PATTERN (insn)) == SET 1180 && REG_P (SET_DEST (PATTERN (insn))) 1181 && MEM_P (SET_SRC (PATTERN (insn)))) 1182 { 1183 rtx pat = PATTERN (insn); 1184 rtx src = SET_SRC (pat); 1185 struct expr *expr; 1186 1187 if (!MEM_VOLATILE_P (src) 1188 && GET_MODE (src) != BLKmode 1189 && general_operand (src, GET_MODE (src)) 1190 /* Are the operands unchanged since the start of the 1191 block? */ 1192 && oprs_unchanged_p (src, insn, false) 1193 && !(flag_non_call_exceptions && may_trap_p (src)) 1194 && !side_effects_p (src) 1195 /* Is the expression recorded? */ 1196 && (expr = lookup_expr_in_table (src)) != NULL) 1197 { 1198 /* We now have a load (insn) and an available memory at 1199 its BB start (expr). Try to remove the loads if it is 1200 redundant. */ 1201 eliminate_partially_redundant_load (bb, insn, expr); 1202 } 1203 } 1204 1205 /* Keep track of everything modified by this insn, so that we 1206 know what has been modified since the start of the current 1207 basic block. */ 1208 if (INSN_P (insn)) 1209 record_opr_changes (insn); 1210 } 1211 } 1212 1213 commit_edge_insertions (); 1214} 1215 1216/* Go over the expression hash table and delete insns that were 1217 marked for later deletion. */ 1218 1219/* This helper is called via htab_traverse. */ 1220static int 1221delete_redundant_insns_1 (void **slot, void *data ATTRIBUTE_UNUSED) 1222{ 1223 struct expr *expr = (struct expr *) *slot; 1224 struct occr *occr; 1225 1226 for (occr = expr->avail_occr; occr != NULL; occr = occr->next) 1227 { 1228 if (occr->deleted_p) 1229 { 1230 delete_insn (occr->insn); 1231 stats.insns_deleted++; 1232 1233 if (dump_file) 1234 { 1235 fprintf (dump_file, "deleting insn:\n"); 1236 print_rtl_single (dump_file, occr->insn); 1237 fprintf (dump_file, "\n"); 1238 } 1239 } 1240 } 1241 1242 return 1; 1243} 1244 1245static void 1246delete_redundant_insns (void) 1247{ 1248 htab_traverse (expr_table, delete_redundant_insns_1, NULL); 1249 if (dump_file) 1250 fprintf (dump_file, "\n"); 1251} 1252 1253/* Main entry point of the GCSE after reload - clean some redundant loads 1254 due to spilling. */ 1255 1256static void 1257gcse_after_reload_main (rtx f ATTRIBUTE_UNUSED) 1258{ 1259 1260 memset (&stats, 0, sizeof (stats)); 1261 1262 /* Allocate ememory for this pass. 1263 Also computes and initializes the insns' CUIDs. */ 1264 alloc_mem (); 1265 1266 /* We need alias analysis. */ 1267 init_alias_analysis (); 1268 1269 compute_hash_table (); 1270 1271 if (dump_file) 1272 dump_hash_table (dump_file); 1273 1274 if (htab_elements (expr_table) > 0) 1275 { 1276 eliminate_partially_redundant_loads (); 1277 delete_redundant_insns (); 1278 1279 if (dump_file) 1280 { 1281 fprintf (dump_file, "GCSE AFTER RELOAD stats:\n"); 1282 fprintf (dump_file, "copies inserted: %d\n", stats.copies_inserted); 1283 fprintf (dump_file, "moves inserted: %d\n", stats.moves_inserted); 1284 fprintf (dump_file, "insns deleted: %d\n", stats.insns_deleted); 1285 fprintf (dump_file, "\n\n"); 1286 } 1287 } 1288 1289 /* We are finished with alias. */ 1290 end_alias_analysis (); 1291 1292 free_mem (); 1293} 1294 1295 1296static bool 1297gate_handle_gcse2 (void) 1298{ 1299 return (optimize > 0 && flag_gcse_after_reload); 1300} 1301 1302 1303static unsigned int 1304rest_of_handle_gcse2 (void) 1305{ 1306 gcse_after_reload_main (get_insns ()); 1307 rebuild_jump_labels (get_insns ()); 1308 delete_trivially_dead_insns (get_insns (), max_reg_num ()); 1309 return 0; 1310} 1311 1312struct tree_opt_pass pass_gcse2 = 1313{ 1314 "gcse2", /* name */ 1315 gate_handle_gcse2, /* gate */ 1316 rest_of_handle_gcse2, /* execute */ 1317 NULL, /* sub */ 1318 NULL, /* next */ 1319 0, /* static_pass_number */ 1320 TV_GCSE_AFTER_RELOAD, /* tv_id */ 1321 0, /* properties_required */ 1322 0, /* properties_provided */ 1323 0, /* properties_destroyed */ 1324 0, /* todo_flags_start */ 1325 TODO_dump_func | 1326 TODO_verify_flow | TODO_ggc_collect, /* todo_flags_finish */ 1327 'J' /* letter */ 1328}; 1329 1330