contrib/gcc-4.4/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 "df.h"
  31 #include "cselib.h"
  32 #include "dce.h"
  33 #include "timevar.h"
  34 #include "tree-pass.h"
  35 #include "dbgcnt.h"
  36 #include "tm_p.h"
  37
  38 DEF_VEC_I(int);
  39 DEF_VEC_ALLOC_I(int,heap);
  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       if (volatile_refs_p (body))
  85         return false;
  86
  87       if (flag_non_call_exceptions && may_trap_p (body))
  88         return false;
  89
  90       return true;
  91     }
  92 }
  93
  94
  95 /* Return true if INSN is a normal instruction that can be deleted by
  96    the DCE pass.  */
  97
  98 static bool
  99 deletable_insn_p (rtx insn, bool fast, bitmap arg_stores)
 100 {
 101   rtx body, x;
 102   int i;
 103
 104   if (CALL_P (insn)
 105       /* We cannot delete calls inside of the recursive dce because
 106          this may cause basic blocks to be deleted and this messes up
 107          the rest of the stack of optimization passes.  */
 108       && (!df_in_progress)
 109       /* We cannot delete pure or const sibling calls because it is
 110          hard to see the result.  */
 111       && (!SIBLING_CALL_P (insn))
 112       /* We can delete dead const or pure calls as long as they do not
 113          infinite loop.  */
 114       && (RTL_CONST_OR_PURE_CALL_P (insn)
 115           && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))
 116     return find_call_stack_args (insn, false, fast, arg_stores);
 117
 118   if (!NONJUMP_INSN_P (insn))
 119     return false;
 120
 121   body = PATTERN (insn);
 122   switch (GET_CODE (body))
 123     {
 124     case USE:
 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             gcc_assert (!bitmap_bit_p (sp_bytes, byte - min_sp_off));
 356             bitmap_set_bit (sp_bytes, byte - min_sp_off);
 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_bit_p (sp_bytes, byte - min_sp_off))
 444             break;
 445           bitmap_clear_bit (sp_bytes, byte - min_sp_off);
 446         }
 447
 448       if (!deletable_insn_p (insn, fast, NULL))
 449         break;
 450
 451       if (do_mark)
 452         mark_insn (insn, fast);
 453       else
 454         bitmap_set_bit (arg_stores, INSN_UID (insn));
 455
 456       if (bitmap_empty_p (sp_bytes))
 457         {
 458           ret = true;
 459           break;
 460         }
 461     }
 462
 463   BITMAP_FREE (sp_bytes);
 464   if (!ret && arg_stores)
 465     bitmap_clear (arg_stores);
 466
 467   return ret;
 468 }
 469
 470
 471 /* Delete all REG_EQUAL notes of the registers INSN writes, to prevent
 472    bad dangling REG_EQUAL notes. */
 473
 474 static void
 475 delete_corresponding_reg_eq_notes (rtx insn)
 476 {
 477   df_ref *def_rec;
 478   for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 479     {
 480       df_ref def = *def_rec;
 481       unsigned int regno = DF_REF_REGNO (def);
 482       /* This loop is a little tricky.  We cannot just go down the
 483          chain because it is being modified by the actions in the
 484          loop.  So we just get the head.  We plan to drain the list
 485          anyway.  */
 486       while (DF_REG_EQ_USE_CHAIN (regno))
 487         {
 488           df_ref eq_use = DF_REG_EQ_USE_CHAIN (regno);
 489           rtx noted_insn = DF_REF_INSN (eq_use);
 490           rtx note = find_reg_note (noted_insn, REG_EQUAL, NULL_RTX);
 491           if (!note)
 492             note = find_reg_note (noted_insn, REG_EQUIV, NULL_RTX);
 493
 494           /* This assert is generally triggered when someone deletes a
 495              REG_EQUAL or REG_EQUIV note by hacking the list manually
 496              rather than calling remove_note.  */
 497           gcc_assert (note);
 498           remove_note (noted_insn, note);
 499         }
 500     }
 501 }
 502
 503
 504 /* Delete every instruction that hasn't been marked.  */
 505
 506 static void
 507 delete_unmarked_insns (void)
 508 {
 509   basic_block bb;
 510   rtx insn, next;
 511   bool must_clean = false;
 512
 513   FOR_EACH_BB_REVERSE (bb)
 514     FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
 515       if (INSN_P (insn))
 516         {
 517           /* Always delete no-op moves.  */
 518           if (noop_move_p (insn))
 519             ;
 520
 521           /* Otherwise rely only on the DCE algorithm.  */
 522           else if (marked_insn_p (insn))
 523             continue;
 524
 525           /* Beware that reaching a dbg counter limit here can result
 526              in miscompiled file.  This occurs when a group of insns
 527              must be deleted together, typically because the kept insn
 528              depends on the output from the deleted insn.  Deleting
 529              this insns in reverse order (both at the bb level and
 530              when looking at the blocks) minimizes this, but does not
 531              eliminate it, since it is possible for the using insn to
 532              be top of a block and the producer to be at the bottom of
 533              the block.  However, in most cases this will only result
 534              in an uninitialized use of an insn that is dead anyway.
 535
 536              However, there is one rare case that will cause a
 537              miscompile: deletion of non-looping pure and constant
 538              calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
 539              In this case it is possible to remove the call, but leave
 540              the argument pushes to the stack.  Because of the changes
 541              to the stack pointer, this will almost always lead to a
 542              miscompile.  */
 543           if (!dbg_cnt (dce))
 544             continue;
 545
 546           if (dump_file)
 547             fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
 548
 549           /* Before we delete the insn we have to delete REG_EQUAL notes
 550              for the destination regs in order to avoid dangling notes.  */
 551           delete_corresponding_reg_eq_notes (insn);
 552
 553           /* If a pure or const call is deleted, this may make the cfg
 554              have unreachable blocks.  We rememeber this and call
 555              delete_unreachable_blocks at the end.  */
 556           if (CALL_P (insn))
 557             must_clean = true;
 558
 559           /* Now delete the insn.  */
 560           delete_insn_and_edges (insn);
 561         }
 562
 563   /* Deleted a pure or const call.  */
 564   if (must_clean)
 565     delete_unreachable_blocks ();
 566 }
 567
 568
 569 /* Go through the instructions and mark those whose necessity is not
 570    dependent on inter-instruction information.  Make sure all other
 571    instructions are not marked.  */
 572
 573 static void
 574 prescan_insns_for_dce (bool fast)
 575 {
 576   basic_block bb;
 577   rtx insn, prev;
 578   bitmap arg_stores = NULL;
 579
 580   if (dump_file)
 581     fprintf (dump_file, "Finding needed instructions:\n");
 582
 583   if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS)
 584     arg_stores = BITMAP_ALLOC (NULL);
 585
 586   FOR_EACH_BB (bb)
 587     {
 588       FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)
 589         if (INSN_P (insn))
 590           {
 591             /* Don't mark argument stores now.  They will be marked
 592                if needed when the associated CALL is marked.  */
 593             if (arg_stores && bitmap_bit_p (arg_stores, INSN_UID (insn)))
 594               continue;
 595             if (deletable_insn_p (insn, fast, arg_stores))
 596               mark_nonreg_stores (PATTERN (insn), insn, fast);
 597             else
 598               mark_insn (insn, fast);
 599           }
 600       /* find_call_stack_args only looks at argument stores in the
 601          same bb.  */
 602       if (arg_stores)
 603         bitmap_clear (arg_stores);
 604     }
 605
 606   if (arg_stores)
 607     BITMAP_FREE (arg_stores);
 608
 609   if (dump_file)
 610     fprintf (dump_file, "Finished finding needed instructions:\n");
 611 }
 612
 613
 614 /* UD-based DSE routines. */
 615
 616 /* Mark instructions that define artificially-used registers, such as
 617    the frame pointer and the stack pointer.  */
 618
 619 static void
 620 mark_artificial_uses (void)
 621 {
 622   basic_block bb;
 623   struct df_link *defs;
 624   df_ref *use_rec;
 625
 626   FOR_ALL_BB (bb)
 627     {
 628       for (use_rec = df_get_artificial_uses (bb->index);
 629            *use_rec; use_rec++)
 630         for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 631           if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 632             mark_insn (DF_REF_INSN (defs->ref), false);
 633     }
 634 }
 635
 636
 637 /* Mark every instruction that defines a register value that INSN uses.  */
 638
 639 static void
 640 mark_reg_dependencies (rtx insn)
 641 {
 642   struct df_link *defs;
 643   df_ref *use_rec;
 644
 645   for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
 646     {
 647       df_ref use = *use_rec;
 648       if (dump_file)
 649         {
 650           fprintf (dump_file, "Processing use of ");
 651           print_simple_rtl (dump_file, DF_REF_REG (use));
 652           fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
 653         }
 654       for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
 655         if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 656           mark_insn (DF_REF_INSN (defs->ref), false);
 657     }
 658 }
 659
 660
 661 /* Initialize global variables for a new DCE pass.  */
 662
 663 static void
 664 init_dce (bool fast)
 665 {
 666   if (!df_in_progress)
 667     {
 668       if (!fast)
 669         df_chain_add_problem (DF_UD_CHAIN);
 670       df_analyze ();
 671     }
 672
 673   if (dump_file)
 674     df_dump (dump_file);
 675
 676   if (fast)
 677     {
 678       bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
 679       bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
 680     }
 681
 682   marked = sbitmap_alloc (get_max_uid () + 1);
 683   sbitmap_zero (marked);
 684 }
 685
 686
 687 /* Free the data allocated by init_dce.  */
 688
 689 static void
 690 fini_dce (bool fast)
 691 {
 692   sbitmap_free (marked);
 693
 694   if (fast)
 695     {
 696       bitmap_obstack_release (&dce_blocks_bitmap_obstack);
 697       bitmap_obstack_release (&dce_tmp_bitmap_obstack);
 698     }
 699 }
 700
 701
 702 /* UD-chain based DCE.  */
 703
 704 static unsigned int
 705 rest_of_handle_ud_dce (void)
 706 {
 707   rtx insn;
 708
 709   init_dce (false);
 710
 711   prescan_insns_for_dce (false);
 712   mark_artificial_uses ();
 713   while (VEC_length (rtx, worklist) > 0)
 714     {
 715       insn = VEC_pop (rtx, worklist);
 716       mark_reg_dependencies (insn);
 717     }
 718   VEC_free (rtx, heap, worklist);
 719
 720   /* Before any insns are deleted, we must remove the chains since
 721      they are not bidirectional.  */
 722   df_remove_problem (df_chain);
 723   delete_unmarked_insns ();
 724
 725   fini_dce (false);
 726   return 0;
 727 }
 728
 729
 730 static bool
 731 gate_ud_dce (void)
 732 {
 733   return optimize > 1 && flag_dce
 734     && dbg_cnt (dce_ud);
 735 }
 736
 737 struct rtl_opt_pass pass_ud_rtl_dce =
 738 {
 739  {
 740   RTL_PASS,
 741   "dce",                                /* name */
 742   gate_ud_dce,                        /* gate */
 743   rest_of_handle_ud_dce,              /* execute */
 744   NULL,                                 /* sub */
 745   NULL,                                 /* next */
 746   0,                                    /* static_pass_number */
 747   TV_DCE,                               /* tv_id */
 748   0,                                    /* properties_required */
 749   0,                                    /* properties_provided */
 750   0,                                    /* properties_destroyed */
 751   0,                                    /* todo_flags_start */
 752   TODO_dump_func |
 753   TODO_df_finish | TODO_verify_rtl_sharing |
 754   TODO_ggc_collect                     /* todo_flags_finish */
 755  }
 756 };
 757
 758
 759 /* -------------------------------------------------------------------------
 760    Fast DCE functions
 761    ------------------------------------------------------------------------- */
 762
 763 /* Process basic block BB.  Return true if the live_in set has
 764    changed. REDO_OUT is true if the info at the bottom of the block
 765    needs to be recalculated before starting.  AU is the proper set of
 766    artificial uses. */
 767
 768 static bool
 769 byte_dce_process_block (basic_block bb, bool redo_out, bitmap au)
 770 {
 771   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
 772   rtx insn;
 773   bool block_changed;
 774   df_ref *def_rec;
 775
 776   if (redo_out)
 777     {
 778       /* Need to redo the live_out set of this block if when one of
 779          the succs of this block has had a change in it live in
 780          set.  */
 781       edge e;
 782       edge_iterator ei;
 783       df_confluence_function_n con_fun_n = df_byte_lr->problem->con_fun_n;
 784       bitmap_clear (DF_BYTE_LR_OUT (bb));
 785       FOR_EACH_EDGE (e, ei, bb->succs)
 786         (*con_fun_n) (e);
 787     }
 788
 789   if (dump_file)
 790     {
 791       fprintf (dump_file, "processing block %d live out = ", bb->index);
 792       df_print_byte_regset (dump_file, DF_BYTE_LR_OUT (bb));
 793     }
 794
 795   bitmap_copy (local_live, DF_BYTE_LR_OUT (bb));
 796
 797   df_byte_lr_simulate_artificial_refs_at_end (bb, local_live);
 798
 799   FOR_BB_INSNS_REVERSE (bb, insn)
 800     if (INSN_P (insn))
 801       {
 802         /* The insn is needed if there is someone who uses the output.  */
 803         for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 804           {
 805             df_ref def = *def_rec;
 806             unsigned int last;
 807             unsigned int dregno = DF_REF_REGNO (def);
 808             unsigned int start = df_byte_lr_get_regno_start (dregno);
 809             unsigned int len = df_byte_lr_get_regno_len (dregno);
 810
 811             unsigned int sb;
 812             unsigned int lb;
 813             /* This is one of the only places where DF_MM_MAY should
 814                be used for defs.  Need to make sure that we are
 815                checking for all of the bits that may be used.  */
 816
 817             if (!df_compute_accessed_bytes (def, DF_MM_MAY, &sb, &lb))
 818               {
 819                 start += sb;
 820                 len = lb - sb;
 821               }
 822
 823             if (bitmap_bit_p (au, dregno))
 824               {
 825                 mark_insn (insn, true);
 826                 goto quickexit;
 827               }
 828
 829             last = start + len;
 830             while (start < last)
 831               if (bitmap_bit_p (local_live, start++))
 832                 {
 833                   mark_insn (insn, true);
 834                   goto quickexit;
 835                 }
 836           }
 837
 838       quickexit:
 839
 840         /* No matter if the instruction is needed or not, we remove
 841            any regno in the defs from the live set.  */
 842         df_byte_lr_simulate_defs (insn, local_live);
 843
 844         /* On the other hand, we do not allow the dead uses to set
 845            anything in local_live.  */
 846         if (marked_insn_p (insn))
 847           df_byte_lr_simulate_uses (insn, local_live);
 848
 849         if (dump_file)
 850           {
 851             fprintf (dump_file, "finished processing insn %d live out = ",
 852                      INSN_UID (insn));
 853             df_print_byte_regset (dump_file, local_live);
 854           }
 855       }
 856
 857   df_byte_lr_simulate_artificial_refs_at_top (bb, local_live);
 858
 859   block_changed = !bitmap_equal_p (local_live, DF_BYTE_LR_IN (bb));
 860   if (block_changed)
 861     bitmap_copy (DF_BYTE_LR_IN (bb), local_live);
 862   BITMAP_FREE (local_live);
 863   return block_changed;
 864 }
 865
 866
 867 /* Process basic block BB.  Return true if the live_in set has
 868    changed. REDO_OUT is true if the info at the bottom of the block
 869    needs to be recalculated before starting.  AU is the proper set of
 870    artificial uses. */
 871
 872 static bool
 873 dce_process_block (basic_block bb, bool redo_out, bitmap au)
 874 {
 875   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
 876   rtx insn;
 877   bool block_changed;
 878   df_ref *def_rec;
 879
 880   if (redo_out)
 881     {
 882       /* Need to redo the live_out set of this block if when one of
 883          the succs of this block has had a change in it live in
 884          set.  */
 885       edge e;
 886       edge_iterator ei;
 887       df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
 888       bitmap_clear (DF_LR_OUT (bb));
 889       FOR_EACH_EDGE (e, ei, bb->succs)
 890         (*con_fun_n) (e);
 891     }
 892
 893   if (dump_file)
 894     {
 895       fprintf (dump_file, "processing block %d lr out = ", bb->index);
 896       df_print_regset (dump_file, DF_LR_OUT (bb));
 897     }
 898
 899   bitmap_copy (local_live, DF_LR_OUT (bb));
 900
 901   df_simulate_initialize_backwards (bb, local_live);
 902
 903   FOR_BB_INSNS_REVERSE (bb, insn)
 904     if (INSN_P (insn))
 905       {
 906         bool needed = false;
 907
 908         /* The insn is needed if there is someone who uses the output.  */
 909         for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 910           if (bitmap_bit_p (local_live, DF_REF_REGNO (*def_rec))
 911               || bitmap_bit_p (au, DF_REF_REGNO (*def_rec)))
 912             {
 913               needed = true;
 914               break;
 915             }
 916
 917         if (needed)
 918           mark_insn (insn, true);
 919
 920         /* No matter if the instruction is needed or not, we remove
 921            any regno in the defs from the live set.  */
 922         df_simulate_defs (insn, local_live);
 923
 924         /* On the other hand, we do not allow the dead uses to set
 925            anything in local_live.  */
 926         if (marked_insn_p (insn))
 927           df_simulate_uses (insn, local_live);
 928       }
 929
 930   df_simulate_finalize_backwards (bb, local_live);
 931
 932   block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
 933   if (block_changed)
 934     bitmap_copy (DF_LR_IN (bb), local_live);
 935
 936   BITMAP_FREE (local_live);
 937   return block_changed;
 938 }
 939
 940
 941 /* Perform fast DCE once initialization is done.  If BYTE_LEVEL is
 942    true, use the byte level dce, otherwise do it at the pseudo
 943    level.  */
 944
 945 static void
 946 fast_dce (bool byte_level)
 947 {
 948   int *postorder = df_get_postorder (DF_BACKWARD);
 949   int n_blocks = df_get_n_blocks (DF_BACKWARD);
 950   /* The set of blocks that have been seen on this iteration.  */
 951   bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 952   /* The set of blocks that need to have the out vectors reset because
 953      the in of one of their successors has changed.  */
 954   bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 955   bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 956   bool global_changed = true;
 957
 958   /* These regs are considered always live so if they end up dying
 959      because of some def, we need to bring the back again.  Calling
 960      df_simulate_fixup_sets has the disadvantage of calling
 961      bb_has_eh_pred once per insn, so we cache the information
 962      here.  */
 963   bitmap au = df->regular_block_artificial_uses;
 964   bitmap au_eh = df->eh_block_artificial_uses;
 965   int i;
 966
 967   prescan_insns_for_dce (true);
 968
 969   for (i = 0; i < n_blocks; i++)
 970     bitmap_set_bit (all_blocks, postorder[i]);
 971
 972   while (global_changed)
 973     {
 974       global_changed = false;
 975
 976       for (i = 0; i < n_blocks; i++)
 977         {
 978           int index = postorder[i];
 979           basic_block bb = BASIC_BLOCK (index);
 980           bool local_changed;
 981
 982           if (index < NUM_FIXED_BLOCKS)
 983             {
 984               bitmap_set_bit (processed, index);
 985               continue;
 986             }
 987
 988           if (byte_level)
 989             local_changed
 990               = byte_dce_process_block (bb, bitmap_bit_p (redo_out, index),
 991                                           bb_has_eh_pred (bb) ? au_eh : au);
 992           else
 993             local_changed
 994               = dce_process_block (bb, bitmap_bit_p (redo_out, index),
 995                                    bb_has_eh_pred (bb) ? au_eh : au);
 996           bitmap_set_bit (processed, index);
 997
 998           if (local_changed)
 999             {
1000               edge e;
1001               edge_iterator ei;
1002               FOR_EACH_EDGE (e, ei, bb->preds)
1003                 if (bitmap_bit_p (processed, e->src->index))
1004                   /* Be tricky about when we need to iterate the
1005                      analysis.  We only have redo the analysis if the
1006                      bitmaps change at the top of a block that is the
1007                      entry to a loop.  */
1008                   global_changed = true;
1009                 else
1010                   bitmap_set_bit (redo_out, e->src->index);
1011             }
1012         }
1013
1014       if (global_changed)
1015         {
1016           /* Turn off the RUN_DCE flag to prevent recursive calls to
1017              dce.  */
1018           int old_flag = df_clear_flags (DF_LR_RUN_DCE);
1019
1020           /* So something was deleted that requires a redo.  Do it on
1021              the cheap.  */
1022           delete_unmarked_insns ();
1023           sbitmap_zero (marked);
1024           bitmap_clear (processed);
1025           bitmap_clear (redo_out);
1026
1027           /* We do not need to rescan any instructions.  We only need
1028              to redo the dataflow equations for the blocks that had a
1029              change at the top of the block.  Then we need to redo the
1030              iteration.  */
1031           if (byte_level)
1032             df_analyze_problem (df_byte_lr, all_blocks, postorder, n_blocks);
1033           else
1034             df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
1035
1036           if (old_flag & DF_LR_RUN_DCE)
1037             df_set_flags (DF_LR_RUN_DCE);
1038
1039           prescan_insns_for_dce (true);
1040         }
1041     }
1042
1043   delete_unmarked_insns ();
1044
1045   BITMAP_FREE (processed);
1046   BITMAP_FREE (redo_out);
1047   BITMAP_FREE (all_blocks);
1048 }
1049
1050
1051 /* Fast register level DCE.  */
1052
1053 static unsigned int
1054 rest_of_handle_fast_dce (void)
1055 {
1056   init_dce (true);
1057   fast_dce (false);
1058   fini_dce (true);
1059   return 0;
1060 }
1061
1062
1063 /* Fast byte level DCE.  */
1064
1065 static unsigned int
1066 rest_of_handle_fast_byte_dce (void)
1067 {
1068   df_byte_lr_add_problem ();
1069   init_dce (true);
1070   fast_dce (true);
1071   fini_dce (true);
1072   return 0;
1073 }
1074
1075
1076 /* This is an internal call that is used by the df live register
1077    problem to run fast dce as a side effect of creating the live
1078    information.  The stack is organized so that the lr problem is run,
1079    this pass is run, which updates the live info and the df scanning
1080    info, and then returns to allow the rest of the problems to be run.
1081
1082    This can be called by elsewhere but it will not update the bit
1083    vectors for any other problems than LR.  */
1084
1085 void
1086 run_fast_df_dce (void)
1087 {
1088   if (flag_dce)
1089     {
1090       /* If dce is able to delete something, it has to happen
1091          immediately.  Otherwise there will be problems handling the
1092          eq_notes.  */
1093       enum df_changeable_flags old_flags
1094         = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
1095
1096       df_in_progress = true;
1097       rest_of_handle_fast_dce ();
1098       df_in_progress = false;
1099
1100       df_set_flags (old_flags);
1101     }
1102 }
1103
1104
1105 /* Run a fast DCE pass.  */
1106
1107 void
1108 run_fast_dce (void)
1109 {
1110   if (flag_dce)
1111     rest_of_handle_fast_dce ();
1112 }
1113
1114
1115 static bool
1116 gate_fast_dce (void)
1117 {
1118   return optimize > 0 && flag_dce
1119     && dbg_cnt (dce_fast);
1120 }
1121
1122 struct rtl_opt_pass pass_fast_rtl_dce =
1123 {
1124  {
1125   RTL_PASS,
1126   "dce",                                /* name */
1127   gate_fast_dce,                        /* gate */
1128   rest_of_handle_fast_dce,              /* execute */
1129   NULL,                                 /* sub */
1130   NULL,                                 /* next */
1131   0,                                    /* static_pass_number */
1132   TV_DCE,                               /* tv_id */
1133   0,                                    /* properties_required */
1134   0,                                    /* properties_provided */
1135   0,                                    /* properties_destroyed */
1136   0,                                    /* todo_flags_start */
1137   TODO_dump_func |
1138   TODO_df_finish | TODO_verify_rtl_sharing |
1139   TODO_ggc_collect                      /* todo_flags_finish */
1140  }
1141 };
1142
1143 struct rtl_opt_pass pass_fast_rtl_byte_dce =
1144 {
1145  {
1146   RTL_PASS,
1147   "byte-dce",                           /* name */
1148   gate_fast_dce,                        /* gate */
1149   rest_of_handle_fast_byte_dce,         /* execute */
1150   NULL,                                 /* sub */
1151   NULL,                                 /* next */
1152   0,                                    /* static_pass_number */
1153   TV_DCE,                               /* tv_id */
1154   0,                                    /* properties_required */
1155   0,                                    /* properties_provided */
1156   0,                                    /* properties_destroyed */
1157   0,                                    /* todo_flags_start */
1158   TODO_dump_func |
1159   TODO_df_finish | TODO_verify_rtl_sharing |
1160   TODO_ggc_collect                      /* todo_flags_finish */
1161  }
1162 };