gcc/dce.c

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