gcc/dce.c

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