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