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