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