gcc/dce.c

   1 /* RTL dead code elimination.
   2    Copyright (C) 2005, 2006, 2007 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
  37 DEF_VEC_I(int);
  38 DEF_VEC_ALLOC_I(int,heap);
  39
  40
  41 /* -------------------------------------------------------------------------
  42    Core mark/delete routines
  43    ------------------------------------------------------------------------- */
  44
  45 /* The data-flow information needed by this pass.  */
  46 static bool df_in_progress = false;
  47
  48 /* True if we deleted at least one instruction.  */
  49 static bool something_changed;
  50
  51 /* Instructions that have been marked but whose dependencies have not
  52    yet been processed.  */
  53 static VEC(rtx,heap) *worklist;
  54
  55 static bitmap_obstack dce_blocks_bitmap_obstack;
  56 static bitmap_obstack dce_tmp_bitmap_obstack;
  57
  58 static sbitmap marked = NULL;
  59
  60 /* A subroutine for which BODY is part of the instruction being tested;
  61    either the top-level pattern, or an element of a PARALLEL.  The
  62    instruction is known not to be a bare USE or CLOBBER.  */
  63
  64 static bool
  65 deletable_insn_p_1 (rtx body)
  66 {
  67   switch (GET_CODE (body))
  68     {
  69     case PREFETCH:
  70     case TRAP_IF:
  71       /* The UNSPEC case was added here because the ia-64 claims that
  72          USEs do not work after reload and generates UNSPECS rather
  73          than USEs.  Since dce is run after reload we need to avoid
  74          deleting these even if they are dead.  If it turns out that
  75          USEs really do work after reload, the ia-64 should be
  76          changed, and the UNSPEC case can be removed.  */
  77     case UNSPEC:
  78       return false;
  79
  80     default:
  81       if (volatile_insn_p (body))
  82         return false;
  83
  84       if (flag_non_call_exceptions && may_trap_p (body))
  85         return false;
  86
  87       return true;
  88     }
  89 }
  90
  91 /* Return true if INSN is a normal instruction that can be deleted by
  92    the DCE pass.  */
  93
  94 static bool
  95 deletable_insn_p (rtx insn, bool fast)
  96 {
  97   rtx body, x;
  98   int i;
  99
 100   if (!NONJUMP_INSN_P (insn))
 101     return false;
 102
 103   body = PATTERN (insn);
 104   switch (GET_CODE (body))
 105     {
 106     case USE:
 107       return false;
 108
 109     case CLOBBER:
 110       if (fast)
 111         {
 112           /* A CLOBBER of a dead pseudo register serves no purpose.
 113              That is not necessarily true for hard registers until
 114              after reload.  */
 115           x = XEXP (body, 0);
 116           return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);
 117         }
 118       else
 119         /* Because of the way that use-def chains are built, it is not
 120            possible to tell if the clobber is dead because it can
 121            never be the target of a use-def chain.  */
 122         return false;
 123
 124     case PARALLEL:
 125       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 126         if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))
 127           return false;
 128       return true;
 129
 130     default:
 131       return deletable_insn_p_1 (body);
 132     }
 133 }
 134
 135
 136 /* Return true if INSN has not been marked as needed.  */
 137
 138 static inline int
 139 marked_insn_p (rtx insn)
 140 {
 141   if (insn)
 142     return TEST_BIT (marked, INSN_UID (insn));
 143   else
 144     /* Artificial defs are always needed and they do not have an
 145        insn.  */
 146     return true;
 147 }
 148
 149
 150 /* If INSN has not yet been marked as needed, mark it now, and add it to
 151    the worklist.  */
 152
 153 static void
 154 mark_insn (rtx insn, bool fast)
 155 {
 156   if (!marked_insn_p (insn))
 157     {
 158       if (!fast)
 159         VEC_safe_push (rtx, heap, worklist, insn);
 160       SET_BIT (marked, INSN_UID (insn));
 161       if (dump_file)
 162         fprintf (dump_file, "  Adding insn %d to worklist\n", INSN_UID (insn));
 163     }
 164 }
 165
 166
 167 /* A note_stores callback used by mark_nonreg_stores.  DATA is the
 168    instruction containing DEST.  */
 169
 170 static void
 171 mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data)
 172 {
 173   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
 174     mark_insn ((rtx) data, true);
 175 }
 176
 177
 178 /* A note_stores callback used by mark_nonreg_stores.  DATA is the
 179    instruction containing DEST.  */
 180
 181 static void
 182 mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)
 183 {
 184   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
 185     mark_insn ((rtx) data, false);
 186 }
 187
 188
 189 /* Mark INSN if BODY stores to a non-register destination.  */
 190
 191 static void
 192 mark_nonreg_stores (rtx body, rtx insn, bool fast)
 193 {
 194   if (fast)
 195     note_stores (body, mark_nonreg_stores_1, insn);
 196   else
 197     note_stores (body, mark_nonreg_stores_2, insn);
 198 }
 199
 200
 201 /* Initialize global variables for a new DCE pass.  */
 202
 203 static void
 204 init_dce (bool fast)
 205 {
 206   if (!df_in_progress)
 207     {
 208       if (!fast)
 209         df_chain_add_problem (DF_UD_CHAIN);
 210       df_analyze ();
 211     }
 212
 213   if (dump_file)
 214     df_dump (dump_file);
 215
 216   bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
 217   bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
 218   marked = sbitmap_alloc (get_max_uid () + 1);
 219   sbitmap_zero (marked);
 220 }
 221
 222
 223 /* Delete all REG_EQUAL notes of the registers INSN writes, to prevent
 224    bad dangling REG_EQUAL notes. */
 225
 226 static void
 227 delete_corresponding_reg_eq_notes (rtx insn)
 228 {
 229   struct df_ref **def_rec;
 230   for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 231     {
 232       struct df_ref *def = *def_rec;
 233       unsigned int regno = DF_REF_REGNO (def);
 234       /* This loop is a little tricky.  We cannot just go down the
 235          chain because it is being modified by the actions in the
 236          loop.  So we just get the head.  We plan to drain the list
 237          anyway.  */
 238       while (DF_REG_EQ_USE_CHAIN (regno))
 239         {
 240           struct df_ref *eq_use = DF_REG_EQ_USE_CHAIN (regno);
 241           rtx noted_insn = DF_REF_INSN (eq_use);
 242           rtx note = find_reg_note (noted_insn, REG_EQUAL, NULL_RTX);
 243           if (!note)
 244             note = find_reg_note (noted_insn, REG_EQUIV, NULL_RTX);
 245
 246           /* This assert is generally triggered when someone deletes a
 247              REG_EQUAL or REG_EQUIV note by hacking the list manually
 248              rather than calling remove_note.  */
 249           gcc_assert (note);
 250           remove_note (noted_insn, note);
 251         }
 252     }
 253 }
 254
 255
 256 /* Delete every instruction that hasn't been marked.  Clear the insn
 257    from DCE_DF if DF_DELETE is true.  */
 258
 259 static void
 260 delete_unmarked_insns (void)
 261 {
 262   basic_block bb;
 263   rtx insn, next;
 264
 265   something_changed = false;
 266   FOR_EACH_BB (bb)
 267     FOR_BB_INSNS_SAFE (bb, insn, next)
 268       if (INSN_P (insn))
 269         {
 270           if (noop_move_p (insn))
 271             {
 272               /* Note that this code does not handle the case where
 273                  the last insn of libcall is deleted.  As it turns out
 274                  this case is excluded in the call to noop_move_p.  */
 275               rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
 276               if (note && (XEXP (note, 0) != insn))
 277                 {
 278                   rtx new_libcall_insn = next_real_insn (insn);
 279                   rtx retval_note = find_reg_note (XEXP (note, 0),
 280                                                    REG_RETVAL, NULL_RTX);
 281                   REG_NOTES (new_libcall_insn)
 282                     = gen_rtx_INSN_LIST (REG_LIBCALL, XEXP (note, 0),
 283                                          REG_NOTES (new_libcall_insn));
 284                   XEXP (retval_note, 0) = new_libcall_insn;
 285                 }
 286             }
 287           else if (marked_insn_p (insn))
 288             continue;
 289
 290           /* WARNING, this debugging can itself cause problems if the
 291              edge of the counter causes part of a libcall to be
 292              deleted but not all of it.  */
 293           if (!dbg_cnt (dce))
 294             continue;
 295
 296           if (dump_file)
 297             fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
 298
 299           /* Before we delete the insn, we have to delete
 300              REG_EQUAL of the destination regs of the deleted insn
 301              to prevent dangling REG_EQUAL. */
 302           delete_corresponding_reg_eq_notes (insn);
 303
 304           delete_insn_and_edges (insn);
 305           something_changed = true;
 306         }
 307 }
 308
 309
 310 /* Mark all insns using DELETE_PARM in the libcall that contains
 311    START_INSN.  */
 312 static void
 313 mark_libcall (rtx start_insn, bool delete_parm)
 314 {
 315   rtx note = find_reg_note (start_insn, REG_LIBCALL_ID, NULL_RTX);
 316   int id = INTVAL (XEXP (note, 0));
 317   rtx insn;
 318
 319   mark_insn (start_insn, delete_parm);
 320   insn = NEXT_INSN (start_insn);
 321
 322   /* There are tales, long ago and far away, of the mystical nested
 323      libcall.  No one alive has actually seen one, but other parts of
 324      the compiler support them so we will here.  */
 325   for (insn = NEXT_INSN (start_insn); insn; insn = NEXT_INSN (insn))
 326     {
 327       if (INSN_P (insn))
 328         {
 329           /* Stay in the loop as long as we are in any libcall.  */
 330           if ((note = find_reg_note (insn, REG_LIBCALL_ID, NULL_RTX)))
 331             {
 332               if (id == INTVAL (XEXP (note, 0)))
 333                 {
 334                   mark_insn (insn, delete_parm);
 335                   if (dump_file)
 336                     fprintf (dump_file, "matching forward libcall %d[%d]\n",
 337                              INSN_UID (insn), id);
 338                 }
 339             }
 340           else
 341             break;
 342         }
 343     }
 344
 345   for (insn = PREV_INSN (start_insn); insn; insn = PREV_INSN (insn))
 346     {
 347       if (INSN_P (insn))
 348         {
 349           /* Stay in the loop as long as we are in any libcall.  */
 350           if ((note = find_reg_note (insn, REG_LIBCALL_ID, NULL_RTX)))
 351             {
 352               if (id == INTVAL (XEXP (note, 0)))
 353                 {
 354                   mark_insn (insn, delete_parm);
 355                   if (dump_file)
 356                     fprintf (dump_file, "matching backward libcall %d[%d]\n",
 357                              INSN_UID (insn), id);
 358                 }
 359             }
 360           else
 361             break;
 362         }
 363     }
 364 }
 365
 366
 367 /* Go through the instructions and mark those whose necessity is not
 368    dependent on inter-instruction information.  Make sure all other
 369    instructions are not marked.  */
 370
 371 static void
 372 prescan_insns_for_dce (bool fast)
 373 {
 374   basic_block bb;
 375   rtx insn;
 376
 377   if (dump_file)
 378     fprintf (dump_file, "Finding needed instructions:\n");
 379
 380   FOR_EACH_BB (bb)
 381     FOR_BB_INSNS (bb, insn)
 382     if (INSN_P (insn))
 383       {
 384         rtx note = find_reg_note (insn, REG_LIBCALL_ID, NULL_RTX);
 385         if (note)
 386           mark_libcall (insn, fast);
 387         else if (deletable_insn_p (insn, fast))
 388           mark_nonreg_stores (PATTERN (insn), insn, fast);
 389         else
 390           mark_insn (insn, fast);
 391       }
 392
 393   if (dump_file)
 394     fprintf (dump_file, "Finished finding needed instructions:\n");
 395 }
 396
 397
 398 /* UD-based DSE routines. */
 399
 400 /* Mark instructions that define artificially-used registers, such as
 401    the frame pointer and the stack pointer.  */
 402
 403 static void
 404 mark_artificial_uses (void)
 405 {
 406   basic_block bb;
 407   struct df_link *defs;
 408   struct df_ref **use_rec;
 409
 410   FOR_ALL_BB (bb)
 411     {
 412       for (use_rec = df_get_artificial_uses (bb->index);
 413            *use_rec; use_rec++)
 414         for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 415           mark_insn (DF_REF_INSN (defs->ref), false);
 416     }
 417 }
 418
 419 /* Mark every instruction that defines a register value that INSN uses.  */
 420
 421 static void
 422 mark_reg_dependencies (rtx insn)
 423 {
 424   struct df_link *defs;
 425   struct df_ref **use_rec;
 426
 427   /* If this is part of a libcall, mark the entire libcall.  */
 428   if (find_reg_note (insn, REG_LIBCALL_ID, NULL_RTX))
 429     mark_libcall (insn, false);
 430
 431   for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
 432     {
 433       struct df_ref *use = *use_rec;
 434       if (dump_file)
 435         {
 436           fprintf (dump_file, "Processing use of ");
 437           print_simple_rtl (dump_file, DF_REF_REG (use));
 438           fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
 439         }
 440       for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
 441         mark_insn (DF_REF_INSN (defs->ref), false);
 442     }
 443 }
 444
 445
 446 static void
 447 end_ud_dce (void)
 448 {
 449   sbitmap_free (marked);
 450   gcc_assert (VEC_empty (rtx, worklist));
 451 }
 452
 453
 454 /* UD-chain based DCE.  */
 455
 456 static unsigned int
 457 rest_of_handle_ud_dce (void)
 458 {
 459   rtx insn;
 460
 461   df_in_progress = false;
 462   init_dce (false);
 463
 464   prescan_insns_for_dce (false);
 465   mark_artificial_uses ();
 466   while (VEC_length (rtx, worklist) > 0)
 467     {
 468       insn = VEC_pop (rtx, worklist);
 469       mark_reg_dependencies (insn);
 470     }
 471   /* Before any insns are deleted, we must remove the chains since
 472      they are not bidirectional.  */
 473   df_remove_problem (df_chain);
 474   delete_unmarked_insns ();
 475
 476   end_ud_dce ();
 477   return 0;
 478 }
 479
 480
 481 static bool
 482 gate_ud_dce (void)
 483 {
 484   return optimize > 1 && flag_dce;
 485 }
 486
 487 struct tree_opt_pass pass_ud_rtl_dce =
 488 {
 489   "dce",                                /* name */
 490   gate_ud_dce,                        /* gate */
 491   rest_of_handle_ud_dce,              /* execute */
 492   NULL,                                 /* sub */
 493   NULL,                                 /* next */
 494   0,                                    /* static_pass_number */
 495   TV_DCE,                               /* tv_id */
 496   0,                                    /* properties_required */
 497   0,                                    /* properties_provided */
 498   0,                                    /* properties_destroyed */
 499   0,                                    /* todo_flags_start */
 500   TODO_dump_func |
 501   TODO_df_finish | TODO_verify_rtl_sharing |
 502   TODO_ggc_collect,                     /* todo_flags_finish */
 503   'w'                                   /* letter */
 504 };
 505
 506 /* -------------------------------------------------------------------------
 507    Fast DCE functions
 508    ------------------------------------------------------------------------- */
 509
 510
 511 /* Free the data allocated by init_dce.  */
 512
 513 static void
 514 fini_dce (void)
 515 {
 516   sbitmap_free (marked);
 517   bitmap_obstack_release (&dce_blocks_bitmap_obstack);
 518   bitmap_obstack_release (&dce_tmp_bitmap_obstack);
 519   df_in_progress = false;
 520 }
 521
 522
 523 /* Process basic block BB.  Return true if the live_in set has
 524    changed.  */
 525
 526 static bool
 527 dce_process_block (basic_block bb, bool redo_out)
 528 {
 529   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
 530   bitmap au;
 531   rtx insn;
 532   bool block_changed;
 533   struct df_ref **def_rec, **use_rec;
 534   unsigned int bb_index = bb->index;
 535
 536   if (redo_out)
 537     {
 538       /* Need to redo the live_out set of this block if when one of
 539          the succs of this block has had a change in it live in
 540          set.  */
 541       edge e;
 542       edge_iterator ei;
 543       df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
 544       bitmap_clear (DF_LR_OUT (bb));
 545       FOR_EACH_EDGE (e, ei, bb->succs)
 546         (*con_fun_n) (e);
 547     }
 548
 549   if (dump_file)
 550     {
 551       fprintf (dump_file, "processing block %d live out = ", bb->index);
 552       df_print_regset (dump_file, DF_LR_OUT (bb));
 553     }
 554
 555   bitmap_copy (local_live, DF_LR_OUT (bb));
 556
 557   /* Process the artificial defs and uses at the bottom of the block.  */
 558   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 559     {
 560       struct df_ref *def = *def_rec;
 561       if (((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 562           && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
 563         bitmap_clear_bit (local_live, DF_REF_REGNO (def));
 564     }
 565
 566   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 567     {
 568       struct df_ref *use = *use_rec;
 569       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 570         bitmap_set_bit (local_live, DF_REF_REGNO (use));
 571     }
 572
 573   /* These regs are considered always live so if they end up dying
 574      because of some def, we need to bring the back again.
 575      Calling df_simulate_fixup_sets has the disadvantage of calling
 576      df_has_eh_preds once per insn, so we cache the information here.  */
 577   if (df_has_eh_preds (bb))
 578     au = df->eh_block_artificial_uses;
 579   else
 580     au = df->regular_block_artificial_uses;
 581
 582   FOR_BB_INSNS_REVERSE (bb, insn)
 583     if (INSN_P (insn))
 584       {
 585         /* If this is a recursive call, the libcall will have already
 586            been marked.  */
 587         if (!marked_insn_p (insn))
 588           {
 589             bool needed = false;
 590
 591             /* The insn is needed if there is someone who uses the output.  */
 592             for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 593               if (bitmap_bit_p (local_live, DF_REF_REGNO (*def_rec))
 594                   || bitmap_bit_p (au, DF_REF_REGNO (*def_rec)))
 595                 {
 596                   needed = true;
 597                   break;
 598                 }
 599
 600             if (needed)
 601               {
 602                 rtx note = find_reg_note (insn, REG_LIBCALL_ID, NULL_RTX);
 603
 604                 /* If we need to mark an insn in the middle of a
 605                    libcall, we need to back up to mark the entire
 606                    libcall.  Given that libcalls are rare, rescanning
 607                    the block should be a reasonable solution to trying
 608                    to figure out how to back up.  */
 609                 if (note)
 610                   {
 611                     if (dump_file)
 612                       fprintf (dump_file, "needed libcall %d\n", INSN_UID (insn));
 613                     mark_libcall (insn, true);
 614                     BITMAP_FREE (local_live);
 615                     return dce_process_block (bb, false);
 616                   }
 617                 else
 618                   mark_insn (insn, true);
 619               }
 620           }
 621
 622         /* No matter if the instruction is needed or not, we remove
 623            any regno in the defs from the live set.  */
 624         df_simulate_defs (insn, local_live);
 625
 626         /* On the other hand, we do not allow the dead uses to set
 627            anything in local_live.  */
 628         if (marked_insn_p (insn))
 629           df_simulate_uses (insn, local_live);
 630       }
 631
 632   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 633     {
 634       struct df_ref *def = *def_rec;
 635       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP)
 636           && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
 637         bitmap_clear_bit (local_live, DF_REF_REGNO (def));
 638     }
 639 #ifdef EH_USES
 640   /* Process the uses that are live into an exception handler.  */
 641   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 642     {
 643       /* Add use to set of uses in this BB.  */
 644       struct df_ref *use = *use_rec;
 645       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
 646         bitmap_set_bit (local_live, DF_REF_REGNO (use));
 647     }
 648 #endif
 649
 650   block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
 651   if (block_changed)
 652     bitmap_copy (DF_LR_IN (bb), local_live);
 653
 654   BITMAP_FREE (local_live);
 655   return block_changed;
 656 }
 657
 658 static void
 659 fast_dce (void)
 660 {
 661   int *postorder = df_get_postorder (DF_BACKWARD);
 662   int n_blocks = df_get_n_blocks (DF_BACKWARD);
 663   int i;
 664   /* The set of blocks that have been seen on this iteration.  */
 665   bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 666   /* The set of blocks that need to have the out vectors reset because
 667      the in of one of their successors has changed.  */
 668   bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 669   bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 670   bool global_changed = true;
 671
 672   int loop_count = 0;
 673
 674   prescan_insns_for_dce (true);
 675
 676   for (i = 0; i < n_blocks; i++)
 677     bitmap_set_bit (all_blocks, postorder[i]);
 678
 679   while (global_changed)
 680     {
 681       global_changed = false;
 682       for (i = 0; i < n_blocks; i++)
 683         {
 684           int index = postorder[i];
 685           basic_block bb = BASIC_BLOCK (index);
 686           bool local_changed;
 687
 688           if (index < NUM_FIXED_BLOCKS)
 689             {
 690               bitmap_set_bit (processed, index);
 691               continue;
 692             }
 693
 694           local_changed
 695             = dce_process_block (bb, bitmap_bit_p (redo_out, index));
 696           bitmap_set_bit (processed, index);
 697
 698           if (local_changed)
 699             {
 700               edge e;
 701               edge_iterator ei;
 702               FOR_EACH_EDGE (e, ei, bb->preds)
 703                 if (bitmap_bit_p (processed, e->src->index))
 704                   /* Be tricky about when we need to iterate the
 705                      analysis.  We only have redo the analysis if the
 706                      bitmaps change at the top of a block that is the
 707                      entry to a loop.  */
 708                   global_changed = true;
 709                 else
 710                   bitmap_set_bit (redo_out, e->src->index);
 711             }
 712         }
 713
 714       if (global_changed)
 715         {
 716           /* Turn off the RUN_DCE flag to prevent recursive calls to
 717              dce.  */
 718           int old_flag = df_clear_flags (DF_LR_RUN_DCE);
 719
 720           /* So something was deleted that requires a redo.  Do it on
 721              the cheap.  */
 722           delete_unmarked_insns ();
 723           sbitmap_zero (marked);
 724           bitmap_clear (processed);
 725           bitmap_clear (redo_out);
 726
 727           /* We do not need to rescan any instructions.  We only need
 728              to redo the dataflow equations for the blocks that had a
 729              change at the top of the block.  Then we need to redo the
 730              iteration.  */
 731           df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
 732
 733           if (old_flag & DF_LR_RUN_DCE)
 734             df_set_flags (DF_LR_RUN_DCE);
 735           prescan_insns_for_dce (true);
 736         }
 737       loop_count++;
 738     }
 739
 740   delete_unmarked_insns ();
 741
 742   BITMAP_FREE (processed);
 743   BITMAP_FREE (redo_out);
 744   BITMAP_FREE (all_blocks);
 745 }
 746
 747
 748 /* Callback for running pass_rtl_dce.  */
 749
 750 static unsigned int
 751 rest_of_handle_fast_dce (void)
 752 {
 753   init_dce (true);
 754   fast_dce ();
 755   fini_dce ();
 756   df_in_progress = false;
 757   return 0;
 758 }
 759
 760
 761 /* This is an internal call that is used by the df live register
 762    problem to run fast dce as a side effect of creating the live
 763    information.  The stack is organized so that the lr problem is run,
 764    this pass is run, which updates the live info and the df scanning
 765    info, and then returns to allow the rest of the problems to be run.
 766
 767    This can be called by elsewhere but it will not update the bit
 768    vectors for any other problems than LR.
 769 */
 770
 771 void
 772 run_fast_df_dce (void)
 773 {
 774   if (flag_dce)
 775     {
 776       /* If dce is able to delete something, it has to happen
 777          immediately.  Otherwise there will be problems handling the
 778          eq_notes.  */
 779       enum df_changeable_flags old_flags
 780         = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
 781
 782       df_in_progress = true;
 783       rest_of_handle_fast_dce ();
 784       df_set_flags (old_flags);
 785     }
 786 }
 787
 788 static bool
 789 gate_fast_dce (void)
 790 {
 791   return optimize > 0 && flag_dce;
 792 }
 793
 794
 795 /* Run a fast DCE pass and return true if any instructions were
 796    deleted.  */
 797
 798 bool
 799 run_fast_dce (void)
 800 {
 801   return gate_fast_dce () && (rest_of_handle_fast_dce (), something_changed);
 802 }
 803
 804
 805 struct tree_opt_pass pass_fast_rtl_dce =
 806 {
 807   "dce",                                /* name */
 808   gate_fast_dce,                        /* gate */
 809   rest_of_handle_fast_dce,              /* execute */
 810   NULL,                                 /* sub */
 811   NULL,                                 /* next */
 812   0,                                    /* static_pass_number */
 813   TV_DCE,                               /* tv_id */
 814   0,                                    /* properties_required */
 815   0,                                    /* properties_provided */
 816   0,                                    /* properties_destroyed */
 817   0,                                    /* todo_flags_start */
 818   TODO_dump_func |
 819   TODO_df_finish | TODO_verify_rtl_sharing |
 820   TODO_ggc_collect,                     /* todo_flags_finish */
 821   'w'                                   /* letter */
 822 };
 823