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