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