gcc/dce.c

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