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