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