1 /* RTL dead code elimination. 2 Copyright (C) 2005-2019 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 "memmodel.h" 29 #include "tm_p.h" 30 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */ 31 #include "cfgrtl.h" 32 #include "cfgbuild.h" 33 #include "cfgcleanup.h" 34 #include "dce.h" 35 #include "valtrack.h" 36 #include "tree-pass.h" 37 #include "dbgcnt.h" 38 #include "rtl-iter.h" 39 40 41 /* ------------------------------------------------------------------------- 42 Core mark/delete routines 43 ------------------------------------------------------------------------- */ 44 45 /* True if we are invoked while the df engine is running; in this case, 46 we don't want to reenter it. */ 47 static bool df_in_progress = false; 48 49 /* True if we are allowed to alter the CFG in this pass. */ 50 static bool can_alter_cfg = false; 51 52 /* Instructions that have been marked but whose dependencies have not 53 yet been processed. */ 54 static vec<rtx_insn *> worklist; 55 56 /* Bitmap of instructions marked as needed indexed by INSN_UID. */ 57 static sbitmap marked; 58 59 /* Bitmap obstacks used for block processing by the fast algorithm. */ 60 static bitmap_obstack dce_blocks_bitmap_obstack; 61 static bitmap_obstack dce_tmp_bitmap_obstack; 62 63 static bool find_call_stack_args (rtx_call_insn *, bool, bool, bitmap); 64 65 /* A subroutine for which BODY is part of the instruction being tested; 66 either the top-level pattern, or an element of a PARALLEL. The 67 instruction is known not to be a bare USE or CLOBBER. */ 68 69 static bool 70 deletable_insn_p_1 (rtx body) 71 { 72 switch (GET_CODE (body)) 73 { 74 case PREFETCH: 75 case TRAP_IF: 76 /* The UNSPEC case was added here because the ia-64 claims that 77 USEs do not work after reload and generates UNSPECS rather 78 than USEs. Since dce is run after reload we need to avoid 79 deleting these even if they are dead. If it turns out that 80 USEs really do work after reload, the ia-64 should be 81 changed, and the UNSPEC case can be removed. */ 82 case UNSPEC: 83 return false; 84 85 default: 86 return !volatile_refs_p (body); 87 } 88 } 89 90 /* Don't delete calls that may throw if we cannot do so. */ 91 92 static bool 93 can_delete_call (rtx_insn *insn) 94 { 95 if (cfun->can_delete_dead_exceptions && can_alter_cfg) 96 return true; 97 if (!insn_nothrow_p (insn)) 98 return false; 99 if (can_alter_cfg) 100 return true; 101 /* If we can't alter cfg, even when the call can't throw exceptions, it 102 might have EDGE_ABNORMAL_CALL edges and so we shouldn't delete such 103 calls. */ 104 gcc_assert (CALL_P (insn)); 105 if (BLOCK_FOR_INSN (insn) && BB_END (BLOCK_FOR_INSN (insn)) == insn) 106 { 107 edge e; 108 edge_iterator ei; 109 110 FOR_EACH_EDGE (e, ei, BLOCK_FOR_INSN (insn)->succs) 111 if ((e->flags & EDGE_ABNORMAL_CALL) != 0) 112 return false; 113 } 114 return true; 115 } 116 117 /* Return true if INSN is a normal instruction that can be deleted by 118 the DCE pass. */ 119 120 static bool 121 deletable_insn_p (rtx_insn *insn, bool fast, bitmap arg_stores) 122 { 123 rtx body, x; 124 int i; 125 df_ref def; 126 127 if (CALL_P (insn) 128 /* We cannot delete calls inside of the recursive dce because 129 this may cause basic blocks to be deleted and this messes up 130 the rest of the stack of optimization passes. */ 131 && (!df_in_progress) 132 /* We cannot delete pure or const sibling calls because it is 133 hard to see the result. */ 134 && (!SIBLING_CALL_P (insn)) 135 /* We can delete dead const or pure calls as long as they do not 136 infinite loop. */ 137 && (RTL_CONST_OR_PURE_CALL_P (insn) 138 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)) 139 /* Don't delete calls that may throw if we cannot do so. */ 140 && can_delete_call (insn)) 141 return find_call_stack_args (as_a <rtx_call_insn *> (insn), false, 142 fast, arg_stores); 143 144 /* Don't delete jumps, notes and the like. */ 145 if (!NONJUMP_INSN_P (insn)) 146 return false; 147 148 /* Don't delete insns that may throw if we cannot do so. */ 149 if (!(cfun->can_delete_dead_exceptions && can_alter_cfg) 150 && !insn_nothrow_p (insn)) 151 return false; 152 153 /* If INSN sets a global_reg, leave it untouched. */ 154 FOR_EACH_INSN_DEF (def, insn) 155 if (HARD_REGISTER_NUM_P (DF_REF_REGNO (def)) 156 && global_regs[DF_REF_REGNO (def)]) 157 return false; 158 /* Initialization of pseudo PIC register should never be removed. */ 159 else if (DF_REF_REG (def) == pic_offset_table_rtx 160 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER) 161 return false; 162 163 /* Callee-save restores are needed. */ 164 if (RTX_FRAME_RELATED_P (insn) 165 && crtl->shrink_wrapped_separate 166 && find_reg_note (insn, REG_CFA_RESTORE, NULL)) 167 return false; 168 169 body = PATTERN (insn); 170 switch (GET_CODE (body)) 171 { 172 case USE: 173 case VAR_LOCATION: 174 return false; 175 176 case CLOBBER: 177 case CLOBBER_HIGH: 178 if (fast) 179 { 180 /* A CLOBBER of a dead pseudo register serves no purpose. 181 That is not necessarily true for hard registers until 182 after reload. */ 183 x = XEXP (body, 0); 184 return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed); 185 } 186 else 187 /* Because of the way that use-def chains are built, it is not 188 possible to tell if the clobber is dead because it can 189 never be the target of a use-def chain. */ 190 return false; 191 192 case PARALLEL: 193 for (i = XVECLEN (body, 0) - 1; i >= 0; i--) 194 if (!deletable_insn_p_1 (XVECEXP (body, 0, i))) 195 return false; 196 return true; 197 198 default: 199 return deletable_insn_p_1 (body); 200 } 201 } 202 203 204 /* Return true if INSN has been marked as needed. */ 205 206 static inline int 207 marked_insn_p (rtx_insn *insn) 208 { 209 /* Artificial defs are always needed and they do not have an insn. 210 We should never see them here. */ 211 gcc_assert (insn); 212 return bitmap_bit_p (marked, INSN_UID (insn)); 213 } 214 215 216 /* If INSN has not yet been marked as needed, mark it now, and add it to 217 the worklist. */ 218 219 static void 220 mark_insn (rtx_insn *insn, bool fast) 221 { 222 if (!marked_insn_p (insn)) 223 { 224 if (!fast) 225 worklist.safe_push (insn); 226 bitmap_set_bit (marked, INSN_UID (insn)); 227 if (dump_file) 228 fprintf (dump_file, " Adding insn %d to worklist\n", INSN_UID (insn)); 229 if (CALL_P (insn) 230 && !df_in_progress 231 && !SIBLING_CALL_P (insn) 232 && (RTL_CONST_OR_PURE_CALL_P (insn) 233 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)) 234 && can_delete_call (insn)) 235 find_call_stack_args (as_a <rtx_call_insn *> (insn), true, fast, NULL); 236 } 237 } 238 239 240 /* A note_stores callback used by mark_nonreg_stores. DATA is the 241 instruction containing DEST. */ 242 243 static void 244 mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data) 245 { 246 if (GET_CODE (pattern) != CLOBBER && !REG_P (dest)) 247 { 248 gcc_checking_assert (GET_CODE (pattern) != CLOBBER_HIGH); 249 mark_insn ((rtx_insn *) data, true); 250 } 251 } 252 253 254 /* A note_stores callback used by mark_nonreg_stores. DATA is the 255 instruction containing DEST. */ 256 257 static void 258 mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data) 259 { 260 if (GET_CODE (pattern) != CLOBBER && !REG_P (dest)) 261 { 262 gcc_checking_assert (GET_CODE (pattern) != CLOBBER_HIGH); 263 mark_insn ((rtx_insn *) data, false); 264 } 265 } 266 267 268 /* Mark INSN if BODY stores to a non-register destination. */ 269 270 static void 271 mark_nonreg_stores (rtx body, rtx_insn *insn, bool fast) 272 { 273 if (fast) 274 note_stores (body, mark_nonreg_stores_1, insn); 275 else 276 note_stores (body, mark_nonreg_stores_2, insn); 277 } 278 279 280 /* Return true if a store to SIZE bytes, starting OFF bytes from stack pointer, 281 is a call argument store, and clear corresponding bits from SP_BYTES 282 bitmap if it is. */ 283 284 static bool 285 check_argument_store (HOST_WIDE_INT size, HOST_WIDE_INT off, 286 HOST_WIDE_INT min_sp_off, HOST_WIDE_INT max_sp_off, 287 bitmap sp_bytes) 288 { 289 HOST_WIDE_INT byte; 290 for (byte = off; byte < off + size; byte++) 291 { 292 if (byte < min_sp_off 293 || byte >= max_sp_off 294 || !bitmap_clear_bit (sp_bytes, byte - min_sp_off)) 295 return false; 296 } 297 return true; 298 } 299 300 /* If MEM has sp address, return 0, if it has sp + const address, 301 return that const, if it has reg address where reg is set to sp + const 302 and FAST is false, return const, otherwise return 303 INTTYPE_MINUMUM (HOST_WIDE_INT). */ 304 305 static HOST_WIDE_INT 306 sp_based_mem_offset (rtx_call_insn *call_insn, const_rtx mem, bool fast) 307 { 308 HOST_WIDE_INT off = 0; 309 rtx addr = XEXP (mem, 0); 310 if (GET_CODE (addr) == PLUS 311 && REG_P (XEXP (addr, 0)) 312 && CONST_INT_P (XEXP (addr, 1))) 313 { 314 off = INTVAL (XEXP (addr, 1)); 315 addr = XEXP (addr, 0); 316 } 317 if (addr == stack_pointer_rtx) 318 return off; 319 320 if (!REG_P (addr) || fast) 321 return INTTYPE_MINIMUM (HOST_WIDE_INT); 322 323 /* If not fast, use chains to see if addr wasn't set to sp + offset. */ 324 df_ref use; 325 FOR_EACH_INSN_USE (use, call_insn) 326 if (rtx_equal_p (addr, DF_REF_REG (use))) 327 break; 328 329 if (use == NULL) 330 return INTTYPE_MINIMUM (HOST_WIDE_INT); 331 332 struct df_link *defs; 333 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next) 334 if (! DF_REF_IS_ARTIFICIAL (defs->ref)) 335 break; 336 337 if (defs == NULL) 338 return INTTYPE_MINIMUM (HOST_WIDE_INT); 339 340 rtx set = single_set (DF_REF_INSN (defs->ref)); 341 if (!set) 342 return INTTYPE_MINIMUM (HOST_WIDE_INT); 343 344 if (GET_CODE (SET_SRC (set)) != PLUS 345 || XEXP (SET_SRC (set), 0) != stack_pointer_rtx 346 || !CONST_INT_P (XEXP (SET_SRC (set), 1))) 347 return INTTYPE_MINIMUM (HOST_WIDE_INT); 348 349 off += INTVAL (XEXP (SET_SRC (set), 1)); 350 return off; 351 } 352 353 /* Data for check_argument_load called via note_uses. */ 354 struct check_argument_load_data { 355 bitmap sp_bytes; 356 HOST_WIDE_INT min_sp_off, max_sp_off; 357 rtx_call_insn *call_insn; 358 bool fast; 359 bool load_found; 360 }; 361 362 /* Helper function for find_call_stack_args. Check if there are 363 any loads from the argument slots in between the const/pure call 364 and store to the argument slot, set LOAD_FOUND if any is found. */ 365 366 static void 367 check_argument_load (rtx *loc, void *data) 368 { 369 struct check_argument_load_data *d 370 = (struct check_argument_load_data *) data; 371 subrtx_iterator::array_type array; 372 FOR_EACH_SUBRTX (iter, array, *loc, NONCONST) 373 { 374 const_rtx mem = *iter; 375 HOST_WIDE_INT size; 376 if (MEM_P (mem) 377 && MEM_SIZE_KNOWN_P (mem) 378 && MEM_SIZE (mem).is_constant (&size)) 379 { 380 HOST_WIDE_INT off = sp_based_mem_offset (d->call_insn, mem, d->fast); 381 if (off != INTTYPE_MINIMUM (HOST_WIDE_INT) 382 && off < d->max_sp_off 383 && off + size > d->min_sp_off) 384 for (HOST_WIDE_INT byte = MAX (off, d->min_sp_off); 385 byte < MIN (off + size, d->max_sp_off); byte++) 386 if (bitmap_bit_p (d->sp_bytes, byte - d->min_sp_off)) 387 { 388 d->load_found = true; 389 return; 390 } 391 } 392 } 393 } 394 395 /* Try to find all stack stores of CALL_INSN arguments if 396 ACCUMULATE_OUTGOING_ARGS. If all stack stores have been found 397 and it is therefore safe to eliminate the call, return true, 398 otherwise return false. This function should be first called 399 with DO_MARK false, and only when the CALL_INSN is actually 400 going to be marked called again with DO_MARK true. */ 401 402 static bool 403 find_call_stack_args (rtx_call_insn *call_insn, bool do_mark, bool fast, 404 bitmap arg_stores) 405 { 406 rtx p; 407 rtx_insn *insn, *prev_insn; 408 bool ret; 409 HOST_WIDE_INT min_sp_off, max_sp_off; 410 bitmap sp_bytes; 411 412 gcc_assert (CALL_P (call_insn)); 413 if (!ACCUMULATE_OUTGOING_ARGS) 414 return true; 415 416 if (!do_mark) 417 { 418 gcc_assert (arg_stores); 419 bitmap_clear (arg_stores); 420 } 421 422 min_sp_off = INTTYPE_MAXIMUM (HOST_WIDE_INT); 423 max_sp_off = 0; 424 425 /* First determine the minimum and maximum offset from sp for 426 stored arguments. */ 427 for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1)) 428 if (GET_CODE (XEXP (p, 0)) == USE 429 && MEM_P (XEXP (XEXP (p, 0), 0))) 430 { 431 rtx mem = XEXP (XEXP (p, 0), 0); 432 HOST_WIDE_INT size; 433 if (!MEM_SIZE_KNOWN_P (mem) || !MEM_SIZE (mem).is_constant (&size)) 434 return false; 435 HOST_WIDE_INT off = sp_based_mem_offset (call_insn, mem, fast); 436 if (off == INTTYPE_MINIMUM (HOST_WIDE_INT)) 437 return false; 438 min_sp_off = MIN (min_sp_off, off); 439 max_sp_off = MAX (max_sp_off, off + size); 440 } 441 442 if (min_sp_off >= max_sp_off) 443 return true; 444 sp_bytes = BITMAP_ALLOC (NULL); 445 446 /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off 447 which contain arguments. Checking has been done in the previous 448 loop. */ 449 for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1)) 450 if (GET_CODE (XEXP (p, 0)) == USE 451 && MEM_P (XEXP (XEXP (p, 0), 0))) 452 { 453 rtx mem = XEXP (XEXP (p, 0), 0); 454 /* Checked in the previous iteration. */ 455 HOST_WIDE_INT size = MEM_SIZE (mem).to_constant (); 456 HOST_WIDE_INT off = sp_based_mem_offset (call_insn, mem, fast); 457 gcc_checking_assert (off != INTTYPE_MINIMUM (HOST_WIDE_INT)); 458 for (HOST_WIDE_INT byte = off; byte < off + size; byte++) 459 if (!bitmap_set_bit (sp_bytes, byte - min_sp_off)) 460 gcc_unreachable (); 461 } 462 463 /* Walk backwards, looking for argument stores. The search stops 464 when seeing another call, sp adjustment, memory store other than 465 argument store or a read from an argument stack slot. */ 466 struct check_argument_load_data data 467 = { sp_bytes, min_sp_off, max_sp_off, call_insn, fast, false }; 468 ret = false; 469 for (insn = PREV_INSN (call_insn); insn; insn = prev_insn) 470 { 471 if (insn == BB_HEAD (BLOCK_FOR_INSN (call_insn))) 472 prev_insn = NULL; 473 else 474 prev_insn = PREV_INSN (insn); 475 476 if (CALL_P (insn)) 477 break; 478 479 if (!NONDEBUG_INSN_P (insn)) 480 continue; 481 482 rtx set = single_set (insn); 483 if (!set || SET_DEST (set) == stack_pointer_rtx) 484 break; 485 486 note_uses (&PATTERN (insn), check_argument_load, &data); 487 if (data.load_found) 488 break; 489 490 if (!MEM_P (SET_DEST (set))) 491 continue; 492 493 rtx mem = SET_DEST (set); 494 HOST_WIDE_INT off = sp_based_mem_offset (call_insn, mem, fast); 495 if (off == INTTYPE_MINIMUM (HOST_WIDE_INT)) 496 break; 497 498 HOST_WIDE_INT size; 499 if (!MEM_SIZE_KNOWN_P (mem) 500 || !MEM_SIZE (mem).is_constant (&size) 501 || !check_argument_store (size, off, min_sp_off, 502 max_sp_off, sp_bytes)) 503 break; 504 505 if (!deletable_insn_p (insn, fast, NULL)) 506 break; 507 508 if (do_mark) 509 mark_insn (insn, fast); 510 else 511 bitmap_set_bit (arg_stores, INSN_UID (insn)); 512 513 if (bitmap_empty_p (sp_bytes)) 514 { 515 ret = true; 516 break; 517 } 518 } 519 520 BITMAP_FREE (sp_bytes); 521 if (!ret && arg_stores) 522 bitmap_clear (arg_stores); 523 524 return ret; 525 } 526 527 528 /* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN 529 writes to. */ 530 531 static void 532 remove_reg_equal_equiv_notes_for_defs (rtx_insn *insn) 533 { 534 df_ref def; 535 536 FOR_EACH_INSN_DEF (def, insn) 537 remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (def)); 538 } 539 540 /* Scan all BBs for debug insns and reset those that reference values 541 defined in unmarked insns. */ 542 543 static void 544 reset_unmarked_insns_debug_uses (void) 545 { 546 basic_block bb; 547 rtx_insn *insn, *next; 548 549 FOR_EACH_BB_REVERSE_FN (bb, cfun) 550 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next) 551 if (DEBUG_INSN_P (insn)) 552 { 553 df_ref use; 554 555 FOR_EACH_INSN_USE (use, insn) 556 { 557 struct df_link *defs; 558 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next) 559 { 560 rtx_insn *ref_insn; 561 if (DF_REF_IS_ARTIFICIAL (defs->ref)) 562 continue; 563 ref_insn = DF_REF_INSN (defs->ref); 564 if (!marked_insn_p (ref_insn)) 565 break; 566 } 567 if (!defs) 568 continue; 569 /* ??? FIXME could we propagate the values assigned to 570 each of the DEFs? */ 571 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC (); 572 df_insn_rescan_debug_internal (insn); 573 break; 574 } 575 } 576 } 577 578 /* Delete every instruction that hasn't been marked. */ 579 580 static void 581 delete_unmarked_insns (void) 582 { 583 basic_block bb; 584 rtx_insn *insn, *next; 585 bool must_clean = false; 586 587 FOR_EACH_BB_REVERSE_FN (bb, cfun) 588 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next) 589 if (NONDEBUG_INSN_P (insn)) 590 { 591 rtx turn_into_use = NULL_RTX; 592 593 /* Always delete no-op moves. */ 594 if (noop_move_p (insn) 595 /* Unless the no-op move can throw and we are not allowed 596 to alter cfg. */ 597 && (!cfun->can_throw_non_call_exceptions 598 || (cfun->can_delete_dead_exceptions && can_alter_cfg) 599 || insn_nothrow_p (insn))) 600 { 601 if (RTX_FRAME_RELATED_P (insn)) 602 turn_into_use 603 = find_reg_note (insn, REG_CFA_RESTORE, NULL); 604 if (turn_into_use && REG_P (XEXP (turn_into_use, 0))) 605 turn_into_use = XEXP (turn_into_use, 0); 606 else 607 turn_into_use = NULL_RTX; 608 } 609 610 /* Otherwise rely only on the DCE algorithm. */ 611 else if (marked_insn_p (insn)) 612 continue; 613 614 /* Beware that reaching a dbg counter limit here can result 615 in miscompiled file. This occurs when a group of insns 616 must be deleted together, typically because the kept insn 617 depends on the output from the deleted insn. Deleting 618 this insns in reverse order (both at the bb level and 619 when looking at the blocks) minimizes this, but does not 620 eliminate it, since it is possible for the using insn to 621 be top of a block and the producer to be at the bottom of 622 the block. However, in most cases this will only result 623 in an uninitialized use of an insn that is dead anyway. 624 625 However, there is one rare case that will cause a 626 miscompile: deletion of non-looping pure and constant 627 calls on a machine where ACCUMULATE_OUTGOING_ARGS is true. 628 In this case it is possible to remove the call, but leave 629 the argument pushes to the stack. Because of the changes 630 to the stack pointer, this will almost always lead to a 631 miscompile. */ 632 if (!dbg_cnt (dce)) 633 continue; 634 635 if (dump_file) 636 fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn)); 637 638 /* Before we delete the insn we have to remove the REG_EQUAL notes 639 for the destination regs in order to avoid dangling notes. */ 640 remove_reg_equal_equiv_notes_for_defs (insn); 641 642 if (turn_into_use) 643 { 644 /* Don't remove frame related noop moves if they cary 645 REG_CFA_RESTORE note, while we don't need to emit any code, 646 we need it to emit the CFI restore note. */ 647 PATTERN (insn) 648 = gen_rtx_USE (GET_MODE (turn_into_use), turn_into_use); 649 INSN_CODE (insn) = -1; 650 df_insn_rescan (insn); 651 } 652 else 653 /* Now delete the insn. */ 654 must_clean |= delete_insn_and_edges (insn); 655 } 656 657 /* Deleted a pure or const call. */ 658 if (must_clean) 659 { 660 gcc_assert (can_alter_cfg); 661 delete_unreachable_blocks (); 662 free_dominance_info (CDI_DOMINATORS); 663 } 664 } 665 666 667 /* Go through the instructions and mark those whose necessity is not 668 dependent on inter-instruction information. Make sure all other 669 instructions are not marked. */ 670 671 static void 672 prescan_insns_for_dce (bool fast) 673 { 674 basic_block bb; 675 rtx_insn *insn, *prev; 676 bitmap arg_stores = NULL; 677 678 if (dump_file) 679 fprintf (dump_file, "Finding needed instructions:\n"); 680 681 if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS) 682 arg_stores = BITMAP_ALLOC (NULL); 683 684 FOR_EACH_BB_FN (bb, cfun) 685 { 686 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev) 687 if (NONDEBUG_INSN_P (insn)) 688 { 689 /* Don't mark argument stores now. They will be marked 690 if needed when the associated CALL is marked. */ 691 if (arg_stores && bitmap_bit_p (arg_stores, INSN_UID (insn))) 692 continue; 693 if (deletable_insn_p (insn, fast, arg_stores)) 694 mark_nonreg_stores (PATTERN (insn), insn, fast); 695 else 696 mark_insn (insn, fast); 697 } 698 /* find_call_stack_args only looks at argument stores in the 699 same bb. */ 700 if (arg_stores) 701 bitmap_clear (arg_stores); 702 } 703 704 if (arg_stores) 705 BITMAP_FREE (arg_stores); 706 707 if (dump_file) 708 fprintf (dump_file, "Finished finding needed instructions:\n"); 709 } 710 711 712 /* UD-based DSE routines. */ 713 714 /* Mark instructions that define artificially-used registers, such as 715 the frame pointer and the stack pointer. */ 716 717 static void 718 mark_artificial_uses (void) 719 { 720 basic_block bb; 721 struct df_link *defs; 722 df_ref use; 723 724 FOR_ALL_BB_FN (bb, cfun) 725 FOR_EACH_ARTIFICIAL_USE (use, bb->index) 726 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next) 727 if (!DF_REF_IS_ARTIFICIAL (defs->ref)) 728 mark_insn (DF_REF_INSN (defs->ref), false); 729 } 730 731 732 /* Mark every instruction that defines a register value that INSN uses. */ 733 734 static void 735 mark_reg_dependencies (rtx_insn *insn) 736 { 737 struct df_link *defs; 738 df_ref use; 739 740 if (DEBUG_INSN_P (insn)) 741 return; 742 743 FOR_EACH_INSN_USE (use, insn) 744 { 745 if (dump_file) 746 { 747 fprintf (dump_file, "Processing use of "); 748 print_simple_rtl (dump_file, DF_REF_REG (use)); 749 fprintf (dump_file, " in insn %d:\n", INSN_UID (insn)); 750 } 751 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next) 752 if (! DF_REF_IS_ARTIFICIAL (defs->ref)) 753 mark_insn (DF_REF_INSN (defs->ref), false); 754 } 755 } 756 757 758 /* Initialize global variables for a new DCE pass. */ 759 760 static void 761 init_dce (bool fast) 762 { 763 if (!df_in_progress) 764 { 765 if (!fast) 766 { 767 df_set_flags (DF_RD_PRUNE_DEAD_DEFS); 768 df_chain_add_problem (DF_UD_CHAIN); 769 } 770 df_analyze (); 771 } 772 773 if (dump_file) 774 df_dump (dump_file); 775 776 if (fast) 777 { 778 bitmap_obstack_initialize (&dce_blocks_bitmap_obstack); 779 bitmap_obstack_initialize (&dce_tmp_bitmap_obstack); 780 can_alter_cfg = false; 781 } 782 else 783 can_alter_cfg = true; 784 785 marked = sbitmap_alloc (get_max_uid () + 1); 786 bitmap_clear (marked); 787 } 788 789 790 /* Free the data allocated by init_dce. */ 791 792 static void 793 fini_dce (bool fast) 794 { 795 sbitmap_free (marked); 796 797 if (fast) 798 { 799 bitmap_obstack_release (&dce_blocks_bitmap_obstack); 800 bitmap_obstack_release (&dce_tmp_bitmap_obstack); 801 } 802 } 803 804 805 /* UD-chain based DCE. */ 806 807 static unsigned int 808 rest_of_handle_ud_dce (void) 809 { 810 rtx_insn *insn; 811 812 init_dce (false); 813 814 prescan_insns_for_dce (false); 815 mark_artificial_uses (); 816 while (worklist.length () > 0) 817 { 818 insn = worklist.pop (); 819 mark_reg_dependencies (insn); 820 } 821 worklist.release (); 822 823 if (MAY_HAVE_DEBUG_BIND_INSNS) 824 reset_unmarked_insns_debug_uses (); 825 826 /* Before any insns are deleted, we must remove the chains since 827 they are not bidirectional. */ 828 df_remove_problem (df_chain); 829 delete_unmarked_insns (); 830 831 fini_dce (false); 832 return 0; 833 } 834 835 836 namespace { 837 838 const pass_data pass_data_ud_rtl_dce = 839 { 840 RTL_PASS, /* type */ 841 "ud_dce", /* name */ 842 OPTGROUP_NONE, /* optinfo_flags */ 843 TV_DCE, /* tv_id */ 844 0, /* properties_required */ 845 0, /* properties_provided */ 846 0, /* properties_destroyed */ 847 0, /* todo_flags_start */ 848 TODO_df_finish, /* todo_flags_finish */ 849 }; 850 851 class pass_ud_rtl_dce : public rtl_opt_pass 852 { 853 public: 854 pass_ud_rtl_dce (gcc::context *ctxt) 855 : rtl_opt_pass (pass_data_ud_rtl_dce, ctxt) 856 {} 857 858 /* opt_pass methods: */ 859 virtual bool gate (function *) 860 { 861 return optimize > 1 && flag_dce && dbg_cnt (dce_ud); 862 } 863 864 virtual unsigned int execute (function *) 865 { 866 return rest_of_handle_ud_dce (); 867 } 868 869 }; // class pass_ud_rtl_dce 870 871 } // anon namespace 872 873 rtl_opt_pass * 874 make_pass_ud_rtl_dce (gcc::context *ctxt) 875 { 876 return new pass_ud_rtl_dce (ctxt); 877 } 878 879 880 /* ------------------------------------------------------------------------- 881 Fast DCE functions 882 ------------------------------------------------------------------------- */ 883 884 /* Process basic block BB. Return true if the live_in set has 885 changed. REDO_OUT is true if the info at the bottom of the block 886 needs to be recalculated before starting. AU is the proper set of 887 artificial uses. Track global substitution of uses of dead pseudos 888 in debug insns using GLOBAL_DEBUG. */ 889 890 static bool 891 word_dce_process_block (basic_block bb, bool redo_out, 892 struct dead_debug_global *global_debug) 893 { 894 bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack); 895 rtx_insn *insn; 896 bool block_changed; 897 struct dead_debug_local debug; 898 899 if (redo_out) 900 { 901 /* Need to redo the live_out set of this block if when one of 902 the succs of this block has had a change in it live in 903 set. */ 904 edge e; 905 edge_iterator ei; 906 df_confluence_function_n con_fun_n = df_word_lr->problem->con_fun_n; 907 bitmap_clear (DF_WORD_LR_OUT (bb)); 908 FOR_EACH_EDGE (e, ei, bb->succs) 909 (*con_fun_n) (e); 910 } 911 912 if (dump_file) 913 { 914 fprintf (dump_file, "processing block %d live out = ", bb->index); 915 df_print_word_regset (dump_file, DF_WORD_LR_OUT (bb)); 916 } 917 918 bitmap_copy (local_live, DF_WORD_LR_OUT (bb)); 919 dead_debug_local_init (&debug, NULL, global_debug); 920 921 FOR_BB_INSNS_REVERSE (bb, insn) 922 if (DEBUG_INSN_P (insn)) 923 { 924 df_ref use; 925 FOR_EACH_INSN_USE (use, insn) 926 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER 927 && known_eq (GET_MODE_SIZE (GET_MODE (DF_REF_REAL_REG (use))), 928 2 * UNITS_PER_WORD) 929 && !bitmap_bit_p (local_live, 2 * DF_REF_REGNO (use)) 930 && !bitmap_bit_p (local_live, 2 * DF_REF_REGNO (use) + 1)) 931 dead_debug_add (&debug, use, DF_REF_REGNO (use)); 932 } 933 else if (INSN_P (insn)) 934 { 935 bool any_changed; 936 937 /* No matter if the instruction is needed or not, we remove 938 any regno in the defs from the live set. */ 939 any_changed = df_word_lr_simulate_defs (insn, local_live); 940 if (any_changed) 941 mark_insn (insn, true); 942 943 /* On the other hand, we do not allow the dead uses to set 944 anything in local_live. */ 945 if (marked_insn_p (insn)) 946 df_word_lr_simulate_uses (insn, local_live); 947 948 /* Insert debug temps for dead REGs used in subsequent debug 949 insns. We may have to emit a debug temp even if the insn 950 was marked, in case the debug use was after the point of 951 death. */ 952 if (debug.used && !bitmap_empty_p (debug.used)) 953 { 954 df_ref def; 955 956 FOR_EACH_INSN_DEF (def, insn) 957 dead_debug_insert_temp (&debug, DF_REF_REGNO (def), insn, 958 marked_insn_p (insn) 959 && !control_flow_insn_p (insn) 960 ? DEBUG_TEMP_AFTER_WITH_REG_FORCE 961 : DEBUG_TEMP_BEFORE_WITH_VALUE); 962 } 963 964 if (dump_file) 965 { 966 fprintf (dump_file, "finished processing insn %d live out = ", 967 INSN_UID (insn)); 968 df_print_word_regset (dump_file, local_live); 969 } 970 } 971 972 block_changed = !bitmap_equal_p (local_live, DF_WORD_LR_IN (bb)); 973 if (block_changed) 974 bitmap_copy (DF_WORD_LR_IN (bb), local_live); 975 976 dead_debug_local_finish (&debug, NULL); 977 BITMAP_FREE (local_live); 978 return block_changed; 979 } 980 981 982 /* Process basic block BB. Return true if the live_in set has 983 changed. REDO_OUT is true if the info at the bottom of the block 984 needs to be recalculated before starting. AU is the proper set of 985 artificial uses. Track global substitution of uses of dead pseudos 986 in debug insns using GLOBAL_DEBUG. */ 987 988 static bool 989 dce_process_block (basic_block bb, bool redo_out, bitmap au, 990 struct dead_debug_global *global_debug) 991 { 992 bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack); 993 rtx_insn *insn; 994 bool block_changed; 995 df_ref def; 996 struct dead_debug_local debug; 997 998 if (redo_out) 999 { 1000 /* Need to redo the live_out set of this block if when one of 1001 the succs of this block has had a change in it live in 1002 set. */ 1003 edge e; 1004 edge_iterator ei; 1005 df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n; 1006 bitmap_clear (DF_LR_OUT (bb)); 1007 FOR_EACH_EDGE (e, ei, bb->succs) 1008 (*con_fun_n) (e); 1009 } 1010 1011 if (dump_file) 1012 { 1013 fprintf (dump_file, "processing block %d lr out = ", bb->index); 1014 df_print_regset (dump_file, DF_LR_OUT (bb)); 1015 } 1016 1017 bitmap_copy (local_live, DF_LR_OUT (bb)); 1018 1019 df_simulate_initialize_backwards (bb, local_live); 1020 dead_debug_local_init (&debug, NULL, global_debug); 1021 1022 FOR_BB_INSNS_REVERSE (bb, insn) 1023 if (DEBUG_INSN_P (insn)) 1024 { 1025 df_ref use; 1026 FOR_EACH_INSN_USE (use, insn) 1027 if (!bitmap_bit_p (local_live, DF_REF_REGNO (use)) 1028 && !bitmap_bit_p (au, DF_REF_REGNO (use))) 1029 dead_debug_add (&debug, use, DF_REF_REGNO (use)); 1030 } 1031 else if (INSN_P (insn)) 1032 { 1033 bool needed = marked_insn_p (insn); 1034 1035 /* The insn is needed if there is someone who uses the output. */ 1036 if (!needed) 1037 FOR_EACH_INSN_DEF (def, insn) 1038 if (bitmap_bit_p (local_live, DF_REF_REGNO (def)) 1039 || bitmap_bit_p (au, DF_REF_REGNO (def))) 1040 { 1041 needed = true; 1042 mark_insn (insn, true); 1043 break; 1044 } 1045 1046 /* No matter if the instruction is needed or not, we remove 1047 any regno in the defs from the live set. */ 1048 df_simulate_defs (insn, local_live); 1049 1050 /* On the other hand, we do not allow the dead uses to set 1051 anything in local_live. */ 1052 if (needed) 1053 df_simulate_uses (insn, local_live); 1054 1055 /* Insert debug temps for dead REGs used in subsequent debug 1056 insns. We may have to emit a debug temp even if the insn 1057 was marked, in case the debug use was after the point of 1058 death. */ 1059 if (debug.used && !bitmap_empty_p (debug.used)) 1060 FOR_EACH_INSN_DEF (def, insn) 1061 dead_debug_insert_temp (&debug, DF_REF_REGNO (def), insn, 1062 needed && !control_flow_insn_p (insn) 1063 ? DEBUG_TEMP_AFTER_WITH_REG_FORCE 1064 : DEBUG_TEMP_BEFORE_WITH_VALUE); 1065 } 1066 1067 dead_debug_local_finish (&debug, NULL); 1068 df_simulate_finalize_backwards (bb, local_live); 1069 1070 block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb)); 1071 if (block_changed) 1072 bitmap_copy (DF_LR_IN (bb), local_live); 1073 1074 BITMAP_FREE (local_live); 1075 return block_changed; 1076 } 1077 1078 1079 /* Perform fast DCE once initialization is done. If WORD_LEVEL is 1080 true, use the word level dce, otherwise do it at the pseudo 1081 level. */ 1082 1083 static void 1084 fast_dce (bool word_level) 1085 { 1086 int *postorder = df_get_postorder (DF_BACKWARD); 1087 int n_blocks = df_get_n_blocks (DF_BACKWARD); 1088 /* The set of blocks that have been seen on this iteration. */ 1089 bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack); 1090 /* The set of blocks that need to have the out vectors reset because 1091 the in of one of their successors has changed. */ 1092 bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack); 1093 bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack); 1094 bool global_changed = true; 1095 1096 /* These regs are considered always live so if they end up dying 1097 because of some def, we need to bring the back again. Calling 1098 df_simulate_fixup_sets has the disadvantage of calling 1099 bb_has_eh_pred once per insn, so we cache the information 1100 here. */ 1101 bitmap au = &df->regular_block_artificial_uses; 1102 bitmap au_eh = &df->eh_block_artificial_uses; 1103 int i; 1104 struct dead_debug_global global_debug; 1105 1106 prescan_insns_for_dce (true); 1107 1108 for (i = 0; i < n_blocks; i++) 1109 bitmap_set_bit (all_blocks, postorder[i]); 1110 1111 dead_debug_global_init (&global_debug, NULL); 1112 1113 while (global_changed) 1114 { 1115 global_changed = false; 1116 1117 for (i = 0; i < n_blocks; i++) 1118 { 1119 int index = postorder[i]; 1120 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index); 1121 bool local_changed; 1122 1123 if (index < NUM_FIXED_BLOCKS) 1124 { 1125 bitmap_set_bit (processed, index); 1126 continue; 1127 } 1128 1129 if (word_level) 1130 local_changed 1131 = word_dce_process_block (bb, bitmap_bit_p (redo_out, index), 1132 &global_debug); 1133 else 1134 local_changed 1135 = dce_process_block (bb, bitmap_bit_p (redo_out, index), 1136 bb_has_eh_pred (bb) ? au_eh : au, 1137 &global_debug); 1138 bitmap_set_bit (processed, index); 1139 1140 if (local_changed) 1141 { 1142 edge e; 1143 edge_iterator ei; 1144 FOR_EACH_EDGE (e, ei, bb->preds) 1145 if (bitmap_bit_p (processed, e->src->index)) 1146 /* Be tricky about when we need to iterate the 1147 analysis. We only have redo the analysis if the 1148 bitmaps change at the top of a block that is the 1149 entry to a loop. */ 1150 global_changed = true; 1151 else 1152 bitmap_set_bit (redo_out, e->src->index); 1153 } 1154 } 1155 1156 if (global_changed) 1157 { 1158 /* Turn off the RUN_DCE flag to prevent recursive calls to 1159 dce. */ 1160 int old_flag = df_clear_flags (DF_LR_RUN_DCE); 1161 1162 /* So something was deleted that requires a redo. Do it on 1163 the cheap. */ 1164 delete_unmarked_insns (); 1165 bitmap_clear (marked); 1166 bitmap_clear (processed); 1167 bitmap_clear (redo_out); 1168 1169 /* We do not need to rescan any instructions. We only need 1170 to redo the dataflow equations for the blocks that had a 1171 change at the top of the block. Then we need to redo the 1172 iteration. */ 1173 if (word_level) 1174 df_analyze_problem (df_word_lr, all_blocks, postorder, n_blocks); 1175 else 1176 df_analyze_problem (df_lr, all_blocks, postorder, n_blocks); 1177 1178 if (old_flag & DF_LR_RUN_DCE) 1179 df_set_flags (DF_LR_RUN_DCE); 1180 1181 prescan_insns_for_dce (true); 1182 } 1183 } 1184 1185 dead_debug_global_finish (&global_debug, NULL); 1186 1187 delete_unmarked_insns (); 1188 1189 BITMAP_FREE (processed); 1190 BITMAP_FREE (redo_out); 1191 BITMAP_FREE (all_blocks); 1192 } 1193 1194 1195 /* Fast register level DCE. */ 1196 1197 static unsigned int 1198 rest_of_handle_fast_dce (void) 1199 { 1200 init_dce (true); 1201 fast_dce (false); 1202 fini_dce (true); 1203 return 0; 1204 } 1205 1206 1207 /* Fast byte level DCE. */ 1208 1209 void 1210 run_word_dce (void) 1211 { 1212 int old_flags; 1213 1214 if (!flag_dce) 1215 return; 1216 1217 timevar_push (TV_DCE); 1218 old_flags = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN); 1219 df_word_lr_add_problem (); 1220 init_dce (true); 1221 fast_dce (true); 1222 fini_dce (true); 1223 df_set_flags (old_flags); 1224 timevar_pop (TV_DCE); 1225 } 1226 1227 1228 /* This is an internal call that is used by the df live register 1229 problem to run fast dce as a side effect of creating the live 1230 information. The stack is organized so that the lr problem is run, 1231 this pass is run, which updates the live info and the df scanning 1232 info, and then returns to allow the rest of the problems to be run. 1233 1234 This can be called by elsewhere but it will not update the bit 1235 vectors for any other problems than LR. */ 1236 1237 void 1238 run_fast_df_dce (void) 1239 { 1240 if (flag_dce) 1241 { 1242 /* If dce is able to delete something, it has to happen 1243 immediately. Otherwise there will be problems handling the 1244 eq_notes. */ 1245 int old_flags = 1246 df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN); 1247 1248 df_in_progress = true; 1249 rest_of_handle_fast_dce (); 1250 df_in_progress = false; 1251 1252 df_set_flags (old_flags); 1253 } 1254 } 1255 1256 1257 /* Run a fast DCE pass. */ 1258 1259 void 1260 run_fast_dce (void) 1261 { 1262 if (flag_dce) 1263 rest_of_handle_fast_dce (); 1264 } 1265 1266 1267 namespace { 1268 1269 const pass_data pass_data_fast_rtl_dce = 1270 { 1271 RTL_PASS, /* type */ 1272 "rtl_dce", /* name */ 1273 OPTGROUP_NONE, /* optinfo_flags */ 1274 TV_DCE, /* tv_id */ 1275 0, /* properties_required */ 1276 0, /* properties_provided */ 1277 0, /* properties_destroyed */ 1278 0, /* todo_flags_start */ 1279 TODO_df_finish, /* todo_flags_finish */ 1280 }; 1281 1282 class pass_fast_rtl_dce : public rtl_opt_pass 1283 { 1284 public: 1285 pass_fast_rtl_dce (gcc::context *ctxt) 1286 : rtl_opt_pass (pass_data_fast_rtl_dce, ctxt) 1287 {} 1288 1289 /* opt_pass methods: */ 1290 virtual bool gate (function *) 1291 { 1292 return optimize > 0 && flag_dce && dbg_cnt (dce_fast); 1293 } 1294 1295 virtual unsigned int execute (function *) 1296 { 1297 return rest_of_handle_fast_dce (); 1298 } 1299 1300 }; // class pass_fast_rtl_dce 1301 1302 } // anon namespace 1303 1304 rtl_opt_pass * 1305 make_pass_fast_rtl_dce (gcc::context *ctxt) 1306 { 1307 return new pass_fast_rtl_dce (ctxt); 1308 } 1309