gcc/dce.c

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