1/* Store motion via Lazy Code Motion on the reverse CFG. 2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 3 2006, 2007, 2008, 2009, 2010 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 3, 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 COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "toplev.h" 26 27#include "rtl.h" 28#include "tree.h" 29#include "tm_p.h" 30#include "regs.h" 31#include "hard-reg-set.h" 32#include "flags.h" 33#include "real.h" 34#include "insn-config.h" 35#include "recog.h" 36#include "basic-block.h" 37#include "output.h" 38#include "function.h" 39#include "expr.h" 40#include "except.h" 41#include "ggc.h" 42#include "intl.h" 43#include "timevar.h" 44#include "tree-pass.h" 45#include "hashtab.h" 46#include "df.h" 47#include "dbgcnt.h" 48 49/* This pass implements downward store motion. 50 As of May 1, 2009, the pass is not enabled by default on any target, 51 but bootstrap completes on ia64 and x86_64 with the pass enabled. */ 52 53/* TODO: 54 - remove_reachable_equiv_notes is an incomprehensible pile of goo and 55 a compile time hog that needs a rewrite (maybe cache st_exprs to 56 invalidate REG_EQUAL/REG_EQUIV notes for?). 57 - pattern_regs in st_expr should be a regset (on its own obstack). 58 - antic_stores and avail_stores should be VECs instead of lists. 59 - store_motion_mems should be a VEC instead of a list. 60 - there should be an alloc pool for struct st_expr objects. 61 - investigate whether it is helpful to make the address of an st_expr 62 a cselib VALUE. 63 - when GIMPLE alias information is exported, the effectiveness of this 64 pass should be re-evaluated. 65*/ 66 67/* This is a list of store expressions (MEMs). The structure is used 68 as an expression table to track stores which look interesting, and 69 might be moveable towards the exit block. */ 70 71struct st_expr 72{ 73 /* Pattern of this mem. */ 74 rtx pattern; 75 /* List of registers mentioned by the mem. */ 76 rtx pattern_regs; 77 /* INSN list of stores that are locally anticipatable. */ 78 rtx antic_stores; 79 /* INSN list of stores that are locally available. */ 80 rtx avail_stores; 81 /* Next in the list. */ 82 struct st_expr * next; 83 /* Store ID in the dataflow bitmaps. */ 84 int index; 85 /* Hash value for the hash table. */ 86 unsigned int hash_index; 87 /* Register holding the stored expression when a store is moved. 88 This field is also used as a cache in find_moveable_store, see 89 LAST_AVAIL_CHECK_FAILURE below. */ 90 rtx reaching_reg; 91}; 92 93/* Head of the list of load/store memory refs. */ 94static struct st_expr * store_motion_mems = NULL; 95 96/* Hashtable for the load/store memory refs. */ 97static htab_t store_motion_mems_table = NULL; 98 99/* These bitmaps will hold the local dataflow properties per basic block. */ 100static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp; 101 102/* Nonzero for expressions which should be inserted on a specific edge. */ 103static sbitmap *st_insert_map; 104 105/* Nonzero for expressions which should be deleted in a specific block. */ 106static sbitmap *st_delete_map; 107 108/* Global holding the number of store expressions we are dealing with. */ 109static int num_stores; 110 111/* Contains the edge_list returned by pre_edge_lcm. */ 112static struct edge_list *edge_list; 113 114static hashval_t 115pre_st_expr_hash (const void *p) 116{ 117 int do_not_record_p = 0; 118 const struct st_expr *const x = (const struct st_expr *) p; 119 return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false); 120} 121 122static int 123pre_st_expr_eq (const void *p1, const void *p2) 124{ 125 const struct st_expr *const ptr1 = (const struct st_expr *) p1, 126 *const ptr2 = (const struct st_expr *) p2; 127 return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true); 128} 129 130/* This will search the st_expr list for a matching expression. If it 131 doesn't find one, we create one and initialize it. */ 132 133static struct st_expr * 134st_expr_entry (rtx x) 135{ 136 int do_not_record_p = 0; 137 struct st_expr * ptr; 138 unsigned int hash; 139 void **slot; 140 struct st_expr e; 141 142 hash = hash_rtx (x, GET_MODE (x), &do_not_record_p, 143 NULL, /*have_reg_qty=*/false); 144 145 e.pattern = x; 146 slot = htab_find_slot_with_hash (store_motion_mems_table, &e, hash, INSERT); 147 if (*slot) 148 return (struct st_expr *)*slot; 149 150 ptr = XNEW (struct st_expr); 151 152 ptr->next = store_motion_mems; 153 ptr->pattern = x; 154 ptr->pattern_regs = NULL_RTX; 155 ptr->antic_stores = NULL_RTX; 156 ptr->avail_stores = NULL_RTX; 157 ptr->reaching_reg = NULL_RTX; 158 ptr->index = 0; 159 ptr->hash_index = hash; 160 store_motion_mems = ptr; 161 *slot = ptr; 162 163 return ptr; 164} 165 166/* Free up an individual st_expr entry. */ 167 168static void 169free_st_expr_entry (struct st_expr * ptr) 170{ 171 free_INSN_LIST_list (& ptr->antic_stores); 172 free_INSN_LIST_list (& ptr->avail_stores); 173 174 free (ptr); 175} 176 177/* Free up all memory associated with the st_expr list. */ 178 179static void 180free_store_motion_mems (void) 181{ 182 if (store_motion_mems_table) 183 htab_delete (store_motion_mems_table); 184 store_motion_mems_table = NULL; 185 186 while (store_motion_mems) 187 { 188 struct st_expr * tmp = store_motion_mems; 189 store_motion_mems = store_motion_mems->next; 190 free_st_expr_entry (tmp); 191 } 192 store_motion_mems = NULL; 193} 194 195/* Assign each element of the list of mems a monotonically increasing value. */ 196 197static int 198enumerate_store_motion_mems (void) 199{ 200 struct st_expr * ptr; 201 int n = 0; 202 203 for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next) 204 ptr->index = n++; 205 206 return n; 207} 208 209/* Return first item in the list. */ 210 211static inline struct st_expr * 212first_st_expr (void) 213{ 214 return store_motion_mems; 215} 216 217/* Return the next item in the list after the specified one. */ 218 219static inline struct st_expr * 220next_st_expr (struct st_expr * ptr) 221{ 222 return ptr->next; 223} 224 225/* Dump debugging info about the store_motion_mems list. */ 226 227static void 228print_store_motion_mems (FILE * file) 229{ 230 struct st_expr * ptr; 231 232 fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n"); 233 234 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr)) 235 { 236 fprintf (file, " Pattern (%3d): ", ptr->index); 237 238 print_rtl (file, ptr->pattern); 239 240 fprintf (file, "\n ANTIC stores : "); 241 242 if (ptr->antic_stores) 243 print_rtl (file, ptr->antic_stores); 244 else 245 fprintf (file, "(nil)"); 246 247 fprintf (file, "\n AVAIL stores : "); 248 249 if (ptr->avail_stores) 250 print_rtl (file, ptr->avail_stores); 251 else 252 fprintf (file, "(nil)"); 253 254 fprintf (file, "\n\n"); 255 } 256 257 fprintf (file, "\n"); 258} 259 260/* Return zero if some of the registers in list X are killed 261 due to set of registers in bitmap REGS_SET. */ 262 263static bool 264store_ops_ok (const_rtx x, int *regs_set) 265{ 266 const_rtx reg; 267 268 for (; x; x = XEXP (x, 1)) 269 { 270 reg = XEXP (x, 0); 271 if (regs_set[REGNO(reg)]) 272 return false; 273 } 274 275 return true; 276} 277 278/* Helper for extract_mentioned_regs. */ 279 280static int 281extract_mentioned_regs_1 (rtx *loc, void *data) 282{ 283 rtx *mentioned_regs_p = (rtx *) data; 284 285 if (REG_P (*loc)) 286 *mentioned_regs_p = alloc_EXPR_LIST (0, *loc, *mentioned_regs_p); 287 288 return 0; 289} 290 291/* Returns a list of registers mentioned in X. 292 FIXME: A regset would be prettier and less expensive. */ 293 294static rtx 295extract_mentioned_regs (rtx x) 296{ 297 rtx mentioned_regs = NULL; 298 for_each_rtx (&x, extract_mentioned_regs_1, &mentioned_regs); 299 return mentioned_regs; 300} 301 302/* Check to see if the load X is aliased with STORE_PATTERN. 303 AFTER is true if we are checking the case when STORE_PATTERN occurs 304 after the X. */ 305 306static bool 307load_kills_store (const_rtx x, const_rtx store_pattern, int after) 308{ 309 if (after) 310 return anti_dependence (x, store_pattern); 311 else 312 return true_dependence (store_pattern, GET_MODE (store_pattern), x, 313 rtx_addr_varies_p); 314} 315 316/* Go through the entire rtx X, looking for any loads which might alias 317 STORE_PATTERN. Return true if found. 318 AFTER is true if we are checking the case when STORE_PATTERN occurs 319 after the insn X. */ 320 321static bool 322find_loads (const_rtx x, const_rtx store_pattern, int after) 323{ 324 const char * fmt; 325 int i, j; 326 int ret = false; 327 328 if (!x) 329 return false; 330 331 if (GET_CODE (x) == SET) 332 x = SET_SRC (x); 333 334 if (MEM_P (x)) 335 { 336 if (load_kills_store (x, store_pattern, after)) 337 return true; 338 } 339 340 /* Recursively process the insn. */ 341 fmt = GET_RTX_FORMAT (GET_CODE (x)); 342 343 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--) 344 { 345 if (fmt[i] == 'e') 346 ret |= find_loads (XEXP (x, i), store_pattern, after); 347 else if (fmt[i] == 'E') 348 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 349 ret |= find_loads (XVECEXP (x, i, j), store_pattern, after); 350 } 351 return ret; 352} 353 354/* Go through pattern PAT looking for any loads which might kill the 355 store in X. Return true if found. 356 AFTER is true if we are checking the case when loads kill X occurs 357 after the insn for PAT. */ 358 359static inline bool 360store_killed_in_pat (const_rtx x, const_rtx pat, int after) 361{ 362 if (GET_CODE (pat) == SET) 363 { 364 rtx dest = SET_DEST (pat); 365 366 if (GET_CODE (dest) == ZERO_EXTRACT) 367 dest = XEXP (dest, 0); 368 369 /* Check for memory stores to aliased objects. */ 370 if (MEM_P (dest) 371 && !exp_equiv_p (dest, x, 0, true)) 372 { 373 if (after) 374 { 375 if (output_dependence (dest, x)) 376 return true; 377 } 378 else 379 { 380 if (output_dependence (x, dest)) 381 return true; 382 } 383 } 384 } 385 386 if (find_loads (pat, x, after)) 387 return true; 388 389 return false; 390} 391 392/* Check if INSN kills the store pattern X (is aliased with it). 393 AFTER is true if we are checking the case when store X occurs 394 after the insn. Return true if it does. */ 395 396static bool 397store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after) 398{ 399 const_rtx reg, base, note, pat; 400 401 if (! NONDEBUG_INSN_P (insn)) 402 return false; 403 404 if (CALL_P (insn)) 405 { 406 /* A normal or pure call might read from pattern, 407 but a const call will not. */ 408 if (!RTL_CONST_CALL_P (insn)) 409 return true; 410 411 /* But even a const call reads its parameters. Check whether the 412 base of some of registers used in mem is stack pointer. */ 413 for (reg = x_regs; reg; reg = XEXP (reg, 1)) 414 { 415 base = find_base_term (XEXP (reg, 0)); 416 if (!base 417 || (GET_CODE (base) == ADDRESS 418 && GET_MODE (base) == Pmode 419 && XEXP (base, 0) == stack_pointer_rtx)) 420 return true; 421 } 422 423 return false; 424 } 425 426 pat = PATTERN (insn); 427 if (GET_CODE (pat) == SET) 428 { 429 if (store_killed_in_pat (x, pat, after)) 430 return true; 431 } 432 else if (GET_CODE (pat) == PARALLEL) 433 { 434 int i; 435 436 for (i = 0; i < XVECLEN (pat, 0); i++) 437 if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after)) 438 return true; 439 } 440 else if (find_loads (PATTERN (insn), x, after)) 441 return true; 442 443 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory 444 location aliased with X, then this insn kills X. */ 445 note = find_reg_equal_equiv_note (insn); 446 if (! note) 447 return false; 448 note = XEXP (note, 0); 449 450 /* However, if the note represents a must alias rather than a may 451 alias relationship, then it does not kill X. */ 452 if (exp_equiv_p (note, x, 0, true)) 453 return false; 454 455 /* See if there are any aliased loads in the note. */ 456 return find_loads (note, x, after); 457} 458 459/* Returns true if the expression X is loaded or clobbered on or after INSN 460 within basic block BB. REGS_SET_AFTER is bitmap of registers set in 461 or after the insn. X_REGS is list of registers mentioned in X. If the store 462 is killed, return the last insn in that it occurs in FAIL_INSN. */ 463 464static bool 465store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb, 466 int *regs_set_after, rtx *fail_insn) 467{ 468 rtx last = BB_END (bb), act; 469 470 if (!store_ops_ok (x_regs, regs_set_after)) 471 { 472 /* We do not know where it will happen. */ 473 if (fail_insn) 474 *fail_insn = NULL_RTX; 475 return true; 476 } 477 478 /* Scan from the end, so that fail_insn is determined correctly. */ 479 for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act)) 480 if (store_killed_in_insn (x, x_regs, act, false)) 481 { 482 if (fail_insn) 483 *fail_insn = act; 484 return true; 485 } 486 487 return false; 488} 489 490/* Returns true if the expression X is loaded or clobbered on or before INSN 491 within basic block BB. X_REGS is list of registers mentioned in X. 492 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */ 493static bool 494store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb, 495 int *regs_set_before) 496{ 497 rtx first = BB_HEAD (bb); 498 499 if (!store_ops_ok (x_regs, regs_set_before)) 500 return true; 501 502 for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn)) 503 if (store_killed_in_insn (x, x_regs, insn, true)) 504 return true; 505 506 return false; 507} 508 509/* The last insn in the basic block that compute_store_table is processing, 510 where store_killed_after is true for X. 511 Since we go through the basic block from BB_END to BB_HEAD, this is 512 also the available store at the end of the basic block. Therefore 513 this is in effect a cache, to avoid calling store_killed_after for 514 equivalent aliasing store expressions. 515 This value is only meaningful during the computation of the store 516 table. We hi-jack the REACHING_REG field of struct st_expr to save 517 a bit of memory. */ 518#define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg) 519 520/* Determine whether INSN is MEM store pattern that we will consider moving. 521 REGS_SET_BEFORE is bitmap of registers set before (and including) the 522 current insn, REGS_SET_AFTER is bitmap of registers set after (and 523 including) the insn in this basic block. We must be passing through BB from 524 head to end, as we are using this fact to speed things up. 525 526 The results are stored this way: 527 528 -- the first anticipatable expression is added into ANTIC_STORES 529 -- if the processed expression is not anticipatable, NULL_RTX is added 530 there instead, so that we can use it as indicator that no further 531 expression of this type may be anticipatable 532 -- if the expression is available, it is added as head of AVAIL_STORES; 533 consequently, all of them but this head are dead and may be deleted. 534 -- if the expression is not available, the insn due to that it fails to be 535 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE). 536 537 The things are complicated a bit by fact that there already may be stores 538 to the same MEM from other blocks; also caller must take care of the 539 necessary cleanup of the temporary markers after end of the basic block. 540 */ 541 542static void 543find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after) 544{ 545 struct st_expr * ptr; 546 rtx dest, set, tmp; 547 int check_anticipatable, check_available; 548 basic_block bb = BLOCK_FOR_INSN (insn); 549 550 set = single_set (insn); 551 if (!set) 552 return; 553 554 dest = SET_DEST (set); 555 556 if (! MEM_P (dest) || MEM_VOLATILE_P (dest) 557 || GET_MODE (dest) == BLKmode) 558 return; 559 560 if (side_effects_p (dest)) 561 return; 562 563 /* If we are handling exceptions, we must be careful with memory references 564 that may trap. If we are not, the behavior is undefined, so we may just 565 continue. */ 566 if (flag_non_call_exceptions && may_trap_p (dest)) 567 return; 568 569 /* Even if the destination cannot trap, the source may. In this case we'd 570 need to handle updating the REG_EH_REGION note. */ 571 if (find_reg_note (insn, REG_EH_REGION, NULL_RTX)) 572 return; 573 574 /* Make sure that the SET_SRC of this store insns can be assigned to 575 a register, or we will fail later on in replace_store_insn, which 576 assumes that we can do this. But sometimes the target machine has 577 oddities like MEM read-modify-write instruction. See for example 578 PR24257. */ 579 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set))) 580 return; 581 582 ptr = st_expr_entry (dest); 583 if (!ptr->pattern_regs) 584 ptr->pattern_regs = extract_mentioned_regs (dest); 585 586 /* Do not check for anticipatability if we either found one anticipatable 587 store already, or tested for one and found out that it was killed. */ 588 check_anticipatable = 0; 589 if (!ptr->antic_stores) 590 check_anticipatable = 1; 591 else 592 { 593 tmp = XEXP (ptr->antic_stores, 0); 594 if (tmp != NULL_RTX 595 && BLOCK_FOR_INSN (tmp) != bb) 596 check_anticipatable = 1; 597 } 598 if (check_anticipatable) 599 { 600 if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before)) 601 tmp = NULL_RTX; 602 else 603 tmp = insn; 604 ptr->antic_stores = alloc_INSN_LIST (tmp, ptr->antic_stores); 605 } 606 607 /* It is not necessary to check whether store is available if we did 608 it successfully before; if we failed before, do not bother to check 609 until we reach the insn that caused us to fail. */ 610 check_available = 0; 611 if (!ptr->avail_stores) 612 check_available = 1; 613 else 614 { 615 tmp = XEXP (ptr->avail_stores, 0); 616 if (BLOCK_FOR_INSN (tmp) != bb) 617 check_available = 1; 618 } 619 if (check_available) 620 { 621 /* Check that we have already reached the insn at that the check 622 failed last time. */ 623 if (LAST_AVAIL_CHECK_FAILURE (ptr)) 624 { 625 for (tmp = BB_END (bb); 626 tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr); 627 tmp = PREV_INSN (tmp)) 628 continue; 629 if (tmp == insn) 630 check_available = 0; 631 } 632 else 633 check_available = store_killed_after (dest, ptr->pattern_regs, insn, 634 bb, regs_set_after, 635 &LAST_AVAIL_CHECK_FAILURE (ptr)); 636 } 637 if (!check_available) 638 ptr->avail_stores = alloc_INSN_LIST (insn, ptr->avail_stores); 639} 640 641/* Find available and anticipatable stores. */ 642 643static int 644compute_store_table (void) 645{ 646 int ret; 647 basic_block bb; 648#ifdef ENABLE_CHECKING 649 unsigned regno; 650#endif 651 rtx insn, tmp; 652 df_ref *def_rec; 653 int *last_set_in, *already_set; 654 struct st_expr * ptr, **prev_next_ptr_ptr; 655 unsigned int max_gcse_regno = max_reg_num (); 656 657 store_motion_mems = NULL; 658 store_motion_mems_table = htab_create (13, pre_st_expr_hash, 659 pre_st_expr_eq, NULL); 660 last_set_in = XCNEWVEC (int, max_gcse_regno); 661 already_set = XNEWVEC (int, max_gcse_regno); 662 663 /* Find all the stores we care about. */ 664 FOR_EACH_BB (bb) 665 { 666 /* First compute the registers set in this block. */ 667 FOR_BB_INSNS (bb, insn) 668 { 669 670 if (! NONDEBUG_INSN_P (insn)) 671 continue; 672 673 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) 674 last_set_in[DF_REF_REGNO (*def_rec)] = INSN_UID (insn); 675 } 676 677 /* Now find the stores. */ 678 memset (already_set, 0, sizeof (int) * max_gcse_regno); 679 FOR_BB_INSNS (bb, insn) 680 { 681 if (! NONDEBUG_INSN_P (insn)) 682 continue; 683 684 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) 685 already_set[DF_REF_REGNO (*def_rec)] = INSN_UID (insn); 686 687 /* Now that we've marked regs, look for stores. */ 688 find_moveable_store (insn, already_set, last_set_in); 689 690 /* Unmark regs that are no longer set. */ 691 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) 692 if (last_set_in[DF_REF_REGNO (*def_rec)] == INSN_UID (insn)) 693 last_set_in[DF_REF_REGNO (*def_rec)] = 0; 694 } 695 696#ifdef ENABLE_CHECKING 697 /* last_set_in should now be all-zero. */ 698 for (regno = 0; regno < max_gcse_regno; regno++) 699 gcc_assert (!last_set_in[regno]); 700#endif 701 702 /* Clear temporary marks. */ 703 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr)) 704 { 705 LAST_AVAIL_CHECK_FAILURE (ptr) = NULL_RTX; 706 if (ptr->antic_stores 707 && (tmp = XEXP (ptr->antic_stores, 0)) == NULL_RTX) 708 ptr->antic_stores = XEXP (ptr->antic_stores, 1); 709 } 710 } 711 712 /* Remove the stores that are not available anywhere, as there will 713 be no opportunity to optimize them. */ 714 for (ptr = store_motion_mems, prev_next_ptr_ptr = &store_motion_mems; 715 ptr != NULL; 716 ptr = *prev_next_ptr_ptr) 717 { 718 if (! ptr->avail_stores) 719 { 720 *prev_next_ptr_ptr = ptr->next; 721 htab_remove_elt_with_hash (store_motion_mems_table, 722 ptr, ptr->hash_index); 723 free_st_expr_entry (ptr); 724 } 725 else 726 prev_next_ptr_ptr = &ptr->next; 727 } 728 729 ret = enumerate_store_motion_mems (); 730 731 if (dump_file) 732 print_store_motion_mems (dump_file); 733 734 free (last_set_in); 735 free (already_set); 736 return ret; 737} 738 739/* In all code following after this, REACHING_REG has its original 740 meaning again. Avoid confusion, and undef the accessor macro for 741 the temporary marks usage in compute_store_table. */ 742#undef LAST_AVAIL_CHECK_FAILURE 743 744/* Insert an instruction at the beginning of a basic block, and update 745 the BB_HEAD if needed. */ 746 747static void 748insert_insn_start_basic_block (rtx insn, basic_block bb) 749{ 750 /* Insert at start of successor block. */ 751 rtx prev = PREV_INSN (BB_HEAD (bb)); 752 rtx before = BB_HEAD (bb); 753 while (before != 0) 754 { 755 if (! LABEL_P (before) 756 && !NOTE_INSN_BASIC_BLOCK_P (before)) 757 break; 758 prev = before; 759 if (prev == BB_END (bb)) 760 break; 761 before = NEXT_INSN (before); 762 } 763 764 insn = emit_insn_after_noloc (insn, prev, bb); 765 766 if (dump_file) 767 { 768 fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n", 769 bb->index); 770 print_inline_rtx (dump_file, insn, 6); 771 fprintf (dump_file, "\n"); 772 } 773} 774 775/* This routine will insert a store on an edge. EXPR is the st_expr entry for 776 the memory reference, and E is the edge to insert it on. Returns nonzero 777 if an edge insertion was performed. */ 778 779static int 780insert_store (struct st_expr * expr, edge e) 781{ 782 rtx reg, insn; 783 basic_block bb; 784 edge tmp; 785 edge_iterator ei; 786 787 /* We did all the deleted before this insert, so if we didn't delete a 788 store, then we haven't set the reaching reg yet either. */ 789 if (expr->reaching_reg == NULL_RTX) 790 return 0; 791 792 if (e->flags & EDGE_FAKE) 793 return 0; 794 795 reg = expr->reaching_reg; 796 insn = gen_move_insn (copy_rtx (expr->pattern), reg); 797 798 /* If we are inserting this expression on ALL predecessor edges of a BB, 799 insert it at the start of the BB, and reset the insert bits on the other 800 edges so we don't try to insert it on the other edges. */ 801 bb = e->dest; 802 FOR_EACH_EDGE (tmp, ei, e->dest->preds) 803 if (!(tmp->flags & EDGE_FAKE)) 804 { 805 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest); 806 807 gcc_assert (index != EDGE_INDEX_NO_EDGE); 808 if (! TEST_BIT (st_insert_map[index], expr->index)) 809 break; 810 } 811 812 /* If tmp is NULL, we found an insertion on every edge, blank the 813 insertion vector for these edges, and insert at the start of the BB. */ 814 if (!tmp && bb != EXIT_BLOCK_PTR) 815 { 816 FOR_EACH_EDGE (tmp, ei, e->dest->preds) 817 { 818 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest); 819 RESET_BIT (st_insert_map[index], expr->index); 820 } 821 insert_insn_start_basic_block (insn, bb); 822 return 0; 823 } 824 825 /* We can't put stores in the front of blocks pointed to by abnormal 826 edges since that may put a store where one didn't used to be. */ 827 gcc_assert (!(e->flags & EDGE_ABNORMAL)); 828 829 insert_insn_on_edge (insn, e); 830 831 if (dump_file) 832 { 833 fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n", 834 e->src->index, e->dest->index); 835 print_inline_rtx (dump_file, insn, 6); 836 fprintf (dump_file, "\n"); 837 } 838 839 return 1; 840} 841 842/* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the 843 memory location in SMEXPR set in basic block BB. 844 845 This could be rather expensive. */ 846 847static void 848remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr) 849{ 850 edge_iterator *stack, ei; 851 int sp; 852 edge act; 853 sbitmap visited = sbitmap_alloc (last_basic_block); 854 rtx last, insn, note; 855 rtx mem = smexpr->pattern; 856 857 stack = XNEWVEC (edge_iterator, n_basic_blocks); 858 sp = 0; 859 ei = ei_start (bb->succs); 860 861 sbitmap_zero (visited); 862 863 act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL); 864 while (1) 865 { 866 if (!act) 867 { 868 if (!sp) 869 { 870 free (stack); 871 sbitmap_free (visited); 872 return; 873 } 874 act = ei_edge (stack[--sp]); 875 } 876 bb = act->dest; 877 878 if (bb == EXIT_BLOCK_PTR 879 || TEST_BIT (visited, bb->index)) 880 { 881 if (!ei_end_p (ei)) 882 ei_next (&ei); 883 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL; 884 continue; 885 } 886 SET_BIT (visited, bb->index); 887 888 if (TEST_BIT (st_antloc[bb->index], smexpr->index)) 889 { 890 for (last = smexpr->antic_stores; 891 BLOCK_FOR_INSN (XEXP (last, 0)) != bb; 892 last = XEXP (last, 1)) 893 continue; 894 last = XEXP (last, 0); 895 } 896 else 897 last = NEXT_INSN (BB_END (bb)); 898 899 for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn)) 900 if (NONDEBUG_INSN_P (insn)) 901 { 902 note = find_reg_equal_equiv_note (insn); 903 if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true)) 904 continue; 905 906 if (dump_file) 907 fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n", 908 INSN_UID (insn)); 909 remove_note (insn, note); 910 } 911 912 if (!ei_end_p (ei)) 913 ei_next (&ei); 914 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL; 915 916 if (EDGE_COUNT (bb->succs) > 0) 917 { 918 if (act) 919 stack[sp++] = ei; 920 ei = ei_start (bb->succs); 921 act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL); 922 } 923 } 924} 925 926/* This routine will replace a store with a SET to a specified register. */ 927 928static void 929replace_store_insn (rtx reg, rtx del, basic_block bb, struct st_expr *smexpr) 930{ 931 rtx insn, mem, note, set, ptr; 932 933 mem = smexpr->pattern; 934 insn = gen_move_insn (reg, SET_SRC (single_set (del))); 935 936 for (ptr = smexpr->antic_stores; ptr; ptr = XEXP (ptr, 1)) 937 if (XEXP (ptr, 0) == del) 938 { 939 XEXP (ptr, 0) = insn; 940 break; 941 } 942 943 /* Move the notes from the deleted insn to its replacement. */ 944 REG_NOTES (insn) = REG_NOTES (del); 945 946 /* Emit the insn AFTER all the notes are transferred. 947 This is cheaper since we avoid df rescanning for the note change. */ 948 insn = emit_insn_after (insn, del); 949 950 if (dump_file) 951 { 952 fprintf (dump_file, 953 "STORE_MOTION delete insn in BB %d:\n ", bb->index); 954 print_inline_rtx (dump_file, del, 6); 955 fprintf (dump_file, "\nSTORE_MOTION replaced with insn:\n "); 956 print_inline_rtx (dump_file, insn, 6); 957 fprintf (dump_file, "\n"); 958 } 959 960 delete_insn (del); 961 962 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem; 963 they are no longer accurate provided that they are reached by this 964 definition, so drop them. */ 965 for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn)) 966 if (NONDEBUG_INSN_P (insn)) 967 { 968 set = single_set (insn); 969 if (!set) 970 continue; 971 if (exp_equiv_p (SET_DEST (set), mem, 0, true)) 972 return; 973 note = find_reg_equal_equiv_note (insn); 974 if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true)) 975 continue; 976 977 if (dump_file) 978 fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n", 979 INSN_UID (insn)); 980 remove_note (insn, note); 981 } 982 remove_reachable_equiv_notes (bb, smexpr); 983} 984 985 986/* Delete a store, but copy the value that would have been stored into 987 the reaching_reg for later storing. */ 988 989static void 990delete_store (struct st_expr * expr, basic_block bb) 991{ 992 rtx reg, i, del; 993 994 if (expr->reaching_reg == NULL_RTX) 995 expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern); 996 997 reg = expr->reaching_reg; 998 999 for (i = expr->avail_stores; i; i = XEXP (i, 1)) 1000 { 1001 del = XEXP (i, 0); 1002 if (BLOCK_FOR_INSN (del) == bb) 1003 { 1004 /* We know there is only one since we deleted redundant 1005 ones during the available computation. */ 1006 replace_store_insn (reg, del, bb, expr); 1007 break; 1008 } 1009 } 1010} 1011 1012/* Fill in available, anticipatable, transparent and kill vectors in 1013 STORE_DATA, based on lists of available and anticipatable stores. */ 1014static void 1015build_store_vectors (void) 1016{ 1017 basic_block bb; 1018 int *regs_set_in_block; 1019 rtx insn, st; 1020 struct st_expr * ptr; 1021 unsigned int max_gcse_regno = max_reg_num (); 1022 1023 /* Build the gen_vector. This is any store in the table which is not killed 1024 by aliasing later in its block. */ 1025 st_avloc = sbitmap_vector_alloc (last_basic_block, num_stores); 1026 sbitmap_vector_zero (st_avloc, last_basic_block); 1027 1028 st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores); 1029 sbitmap_vector_zero (st_antloc, last_basic_block); 1030 1031 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr)) 1032 { 1033 for (st = ptr->avail_stores; st != NULL; st = XEXP (st, 1)) 1034 { 1035 insn = XEXP (st, 0); 1036 bb = BLOCK_FOR_INSN (insn); 1037 1038 /* If we've already seen an available expression in this block, 1039 we can delete this one (It occurs earlier in the block). We'll 1040 copy the SRC expression to an unused register in case there 1041 are any side effects. */ 1042 if (TEST_BIT (st_avloc[bb->index], ptr->index)) 1043 { 1044 rtx r = gen_reg_rtx_and_attrs (ptr->pattern); 1045 if (dump_file) 1046 fprintf (dump_file, "Removing redundant store:\n"); 1047 replace_store_insn (r, XEXP (st, 0), bb, ptr); 1048 continue; 1049 } 1050 SET_BIT (st_avloc[bb->index], ptr->index); 1051 } 1052 1053 for (st = ptr->antic_stores; st != NULL; st = XEXP (st, 1)) 1054 { 1055 insn = XEXP (st, 0); 1056 bb = BLOCK_FOR_INSN (insn); 1057 SET_BIT (st_antloc[bb->index], ptr->index); 1058 } 1059 } 1060 1061 st_kill = sbitmap_vector_alloc (last_basic_block, num_stores); 1062 sbitmap_vector_zero (st_kill, last_basic_block); 1063 1064 st_transp = sbitmap_vector_alloc (last_basic_block, num_stores); 1065 sbitmap_vector_zero (st_transp, last_basic_block); 1066 regs_set_in_block = XNEWVEC (int, max_gcse_regno); 1067 1068 FOR_EACH_BB (bb) 1069 { 1070 memset (regs_set_in_block, 0, sizeof (int) * max_gcse_regno); 1071 1072 FOR_BB_INSNS (bb, insn) 1073 if (NONDEBUG_INSN_P (insn)) 1074 { 1075 df_ref *def_rec; 1076 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) 1077 { 1078 unsigned int ref_regno = DF_REF_REGNO (*def_rec); 1079 if (ref_regno < max_gcse_regno) 1080 regs_set_in_block[DF_REF_REGNO (*def_rec)] = 1; 1081 } 1082 } 1083 1084 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr)) 1085 { 1086 if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb), 1087 bb, regs_set_in_block, NULL)) 1088 { 1089 /* It should not be necessary to consider the expression 1090 killed if it is both anticipatable and available. */ 1091 if (!TEST_BIT (st_antloc[bb->index], ptr->index) 1092 || !TEST_BIT (st_avloc[bb->index], ptr->index)) 1093 SET_BIT (st_kill[bb->index], ptr->index); 1094 } 1095 else 1096 SET_BIT (st_transp[bb->index], ptr->index); 1097 } 1098 } 1099 1100 free (regs_set_in_block); 1101 1102 if (dump_file) 1103 { 1104 dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block); 1105 dump_sbitmap_vector (dump_file, "st_kill", "", st_kill, last_basic_block); 1106 dump_sbitmap_vector (dump_file, "st_transp", "", st_transp, last_basic_block); 1107 dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block); 1108 } 1109} 1110 1111/* Free memory used by store motion. */ 1112 1113static void 1114free_store_memory (void) 1115{ 1116 free_store_motion_mems (); 1117 1118 if (st_avloc) 1119 sbitmap_vector_free (st_avloc); 1120 if (st_kill) 1121 sbitmap_vector_free (st_kill); 1122 if (st_transp) 1123 sbitmap_vector_free (st_transp); 1124 if (st_antloc) 1125 sbitmap_vector_free (st_antloc); 1126 if (st_insert_map) 1127 sbitmap_vector_free (st_insert_map); 1128 if (st_delete_map) 1129 sbitmap_vector_free (st_delete_map); 1130 1131 st_avloc = st_kill = st_transp = st_antloc = NULL; 1132 st_insert_map = st_delete_map = NULL; 1133} 1134 1135/* Perform store motion. Much like gcse, except we move expressions the 1136 other way by looking at the flowgraph in reverse. 1137 Return non-zero if transformations are performed by the pass. */ 1138 1139static int 1140one_store_motion_pass (void) 1141{ 1142 basic_block bb; 1143 int x; 1144 struct st_expr * ptr; 1145 int did_edge_inserts = 0; 1146 int n_stores_deleted = 0; 1147 int n_stores_created = 0; 1148 1149 init_alias_analysis (); 1150 1151 /* Find all the available and anticipatable stores. */ 1152 num_stores = compute_store_table (); 1153 if (num_stores == 0) 1154 { 1155 htab_delete (store_motion_mems_table); 1156 store_motion_mems_table = NULL; 1157 end_alias_analysis (); 1158 return 0; 1159 } 1160 1161 /* Now compute kill & transp vectors. */ 1162 build_store_vectors (); 1163 add_noreturn_fake_exit_edges (); 1164 connect_infinite_loops_to_exit (); 1165 1166 edge_list = pre_edge_rev_lcm (num_stores, st_transp, st_avloc, 1167 st_antloc, st_kill, &st_insert_map, 1168 &st_delete_map); 1169 1170 /* Now we want to insert the new stores which are going to be needed. */ 1171 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr)) 1172 { 1173 /* If any of the edges we have above are abnormal, we can't move this 1174 store. */ 1175 for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--) 1176 if (TEST_BIT (st_insert_map[x], ptr->index) 1177 && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL)) 1178 break; 1179 1180 if (x >= 0) 1181 { 1182 if (dump_file != NULL) 1183 fprintf (dump_file, 1184 "Can't replace store %d: abnormal edge from %d to %d\n", 1185 ptr->index, INDEX_EDGE (edge_list, x)->src->index, 1186 INDEX_EDGE (edge_list, x)->dest->index); 1187 continue; 1188 } 1189 1190 /* Now we want to insert the new stores which are going to be needed. */ 1191 1192 FOR_EACH_BB (bb) 1193 if (TEST_BIT (st_delete_map[bb->index], ptr->index)) 1194 { 1195 delete_store (ptr, bb); 1196 n_stores_deleted++; 1197 } 1198 1199 for (x = 0; x < NUM_EDGES (edge_list); x++) 1200 if (TEST_BIT (st_insert_map[x], ptr->index)) 1201 { 1202 did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x)); 1203 n_stores_created++; 1204 } 1205 } 1206 1207 if (did_edge_inserts) 1208 commit_edge_insertions (); 1209 1210 free_store_memory (); 1211 free_edge_list (edge_list); 1212 remove_fake_exit_edges (); 1213 end_alias_analysis (); 1214 1215 if (dump_file) 1216 { 1217 fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ", 1218 current_function_name (), n_basic_blocks); 1219 fprintf (dump_file, "%d insns deleted, %d insns created\n", 1220 n_stores_deleted, n_stores_created); 1221 } 1222 1223 return (n_stores_deleted > 0 || n_stores_created > 0); 1224} 1225 1226 1227static bool 1228gate_rtl_store_motion (void) 1229{ 1230 return optimize > 0 && flag_gcse_sm 1231 && !cfun->calls_setjmp 1232 && optimize_function_for_speed_p (cfun) 1233 && dbg_cnt (store_motion); 1234} 1235 1236static unsigned int 1237execute_rtl_store_motion (void) 1238{ 1239 delete_unreachable_blocks (); 1240 df_analyze (); 1241 flag_rerun_cse_after_global_opts |= one_store_motion_pass (); 1242 return 0; 1243} 1244 1245struct rtl_opt_pass pass_rtl_store_motion = 1246{ 1247 { 1248 RTL_PASS, 1249 "store_motion", /* name */ 1250 gate_rtl_store_motion, /* gate */ 1251 execute_rtl_store_motion, /* execute */ 1252 NULL, /* sub */ 1253 NULL, /* next */ 1254 0, /* static_pass_number */ 1255 TV_LSM, /* tv_id */ 1256 PROP_cfglayout, /* properties_required */ 1257 0, /* properties_provided */ 1258 0, /* properties_destroyed */ 1259 0, /* todo_flags_start */ 1260 TODO_df_finish | TODO_verify_rtl_sharing | 1261 TODO_dump_func | 1262 TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */ 1263 } 1264}; 1265 1266