gcc/dce.c

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