gcc/dce.c

   1 /* RTL dead code elimination.
   2    Copyright (C) 2005, 2006, 2007, 2008 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 /* True if we are invoked while the df engine is running; in this case,
  46    we don't want to reenter it.  */
  47 static bool df_in_progress = false;
  48
  49 /* Instructions that have been marked but whose dependencies have not
  50    yet been processed.  */
  51 static VEC(rtx,heap) *worklist;
  52
  53 /* Bitmap of instructions marked as needed indexed by INSN_UID.  */
  54 static sbitmap marked;
  55
  56 /* Bitmap obstacks used for block processing by the fast algorithm.  */
  57 static bitmap_obstack dce_blocks_bitmap_obstack;
  58 static bitmap_obstack dce_tmp_bitmap_obstack;
  59
  60
  61 /* A subroutine for which BODY is part of the instruction being tested;
  62    either the top-level pattern, or an element of a PARALLEL.  The
  63    instruction is known not to be a bare USE or CLOBBER.  */
  64
  65 static bool
  66 deletable_insn_p_1 (rtx body)
  67 {
  68   switch (GET_CODE (body))
  69     {
  70     case PREFETCH:
  71     case TRAP_IF:
  72       /* The UNSPEC case was added here because the ia-64 claims that
  73          USEs do not work after reload and generates UNSPECS rather
  74          than USEs.  Since dce is run after reload we need to avoid
  75          deleting these even if they are dead.  If it turns out that
  76          USEs really do work after reload, the ia-64 should be
  77          changed, and the UNSPEC case can be removed.  */
  78     case UNSPEC:
  79       return false;
  80
  81     default:
  82       if (volatile_refs_p (body))
  83         return false;
  84
  85       if (flag_non_call_exceptions && may_trap_p (body))
  86         return false;
  87
  88       return true;
  89     }
  90 }
  91
  92
  93 /* Return true if INSN is a normal instruction that can be deleted by
  94    the DCE pass.  */
  95
  96 static bool
  97 deletable_insn_p (rtx insn, bool fast)
  98 {
  99   rtx body, x;
 100   int i;
 101
 102   if (!NONJUMP_INSN_P (insn))
 103     return false;
 104
 105   body = PATTERN (insn);
 106   switch (GET_CODE (body))
 107     {
 108     case USE:
 109       return false;
 110
 111     case CLOBBER:
 112       if (fast)
 113         {
 114           /* A CLOBBER of a dead pseudo register serves no purpose.
 115              That is not necessarily true for hard registers until
 116              after reload.  */
 117           x = XEXP (body, 0);
 118           return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);
 119         }
 120       else
 121         /* Because of the way that use-def chains are built, it is not
 122            possible to tell if the clobber is dead because it can
 123            never be the target of a use-def chain.  */
 124         return false;
 125
 126     case PARALLEL:
 127       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 128         if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))
 129           return false;
 130       return true;
 131
 132     default:
 133       return deletable_insn_p_1 (body);
 134     }
 135 }
 136
 137
 138 /* Return true if INSN has been marked as needed.  */
 139
 140 static inline int
 141 marked_insn_p (rtx insn)
 142 {
 143   if (insn)
 144     return TEST_BIT (marked, INSN_UID (insn));
 145   else
 146     /* Artificial defs are always needed and they do not have an
 147        insn.  */
 148     return true;
 149 }
 150
 151
 152 /* If INSN has not yet been marked as needed, mark it now, and add it to
 153    the worklist.  */
 154
 155 static void
 156 mark_insn (rtx insn, bool fast)
 157 {
 158   if (!marked_insn_p (insn))
 159     {
 160       if (!fast)
 161         VEC_safe_push (rtx, heap, worklist, insn);
 162       SET_BIT (marked, INSN_UID (insn));
 163       if (dump_file)
 164         fprintf (dump_file, "  Adding insn %d to worklist\n", INSN_UID (insn));
 165     }
 166 }
 167
 168
 169 /* A note_stores callback used by mark_nonreg_stores.  DATA is the
 170    instruction containing DEST.  */
 171
 172 static void
 173 mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data)
 174 {
 175   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
 176     mark_insn ((rtx) data, true);
 177 }
 178
 179
 180 /* A note_stores callback used by mark_nonreg_stores.  DATA is the
 181    instruction containing DEST.  */
 182
 183 static void
 184 mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)
 185 {
 186   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
 187     mark_insn ((rtx) data, false);
 188 }
 189
 190
 191 /* Mark INSN if BODY stores to a non-register destination.  */
 192
 193 static void
 194 mark_nonreg_stores (rtx body, rtx insn, bool fast)
 195 {
 196   if (fast)
 197     note_stores (body, mark_nonreg_stores_1, insn);
 198   else
 199     note_stores (body, mark_nonreg_stores_2, insn);
 200 }
 201
 202
 203 /* Return true if the entire libcall sequence starting at INSN is dead.
 204    NOTE is the REG_LIBCALL note attached to INSN.
 205
 206    A libcall sequence is a block of insns with no side-effects, i.e.
 207    that is only used for its return value.  The terminology derives
 208    from that of a call, but a libcall sequence need not contain one.
 209    It is only defined by a pair of REG_LIBCALL/REG_RETVAL notes.
 210
 211    From a dataflow viewpoint, a libcall sequence has the property that
 212    no UD chain can enter it from the outside.  As a consequence, if a
 213    libcall sequence has a dead return value, it is effectively dead.
 214    This is both enforced by CSE (cse_extended_basic_block) and relied
 215    upon by delete_trivially_dead_insns.
 216
 217    However, in practice, the return value business is a tricky one and
 218    only checking the liveness of the last insn is not sufficient to
 219    decide whether the whole sequence is dead (e.g. PR middle-end/19551)
 220    so we check the liveness of every insn starting from the call.  */
 221
 222 static bool
 223 libcall_dead_p (rtx insn, rtx note)
 224 {
 225   rtx last = XEXP (note, 0);
 226
 227   /* Find the call insn.  */
 228   while (insn != last && !CALL_P (insn))
 229     insn = NEXT_INSN (insn);
 230
 231   /* If there is none, do nothing special, since ordinary death handling
 232      can understand these insns.  */
 233   if (!CALL_P (insn))
 234     return false;
 235
 236   /* If this is a call that returns a value via an invisible pointer, the
 237      dataflow engine cannot see it so it has been marked unconditionally.
 238      Skip it unless it has been made the last insn in the libcall, for
 239      example by the combiner, in which case we're left with no easy way
 240      of asserting its liveness.  */
 241   if (!single_set (insn))
 242     {
 243       if (insn == last)
 244         return false;
 245       insn = NEXT_INSN (insn);
 246     }
 247
 248   while (insn != NEXT_INSN (last))
 249     {
 250       if (INSN_P (insn) && marked_insn_p (insn))
 251         return false;
 252       insn = NEXT_INSN (insn);
 253     }
 254
 255   return true;
 256 }
 257
 258
 259 /* Delete all REG_EQUAL notes of the registers INSN writes, to prevent
 260    bad dangling REG_EQUAL notes. */
 261
 262 static void
 263 delete_corresponding_reg_eq_notes (rtx insn)
 264 {
 265   struct df_ref **def_rec;
 266   for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 267     {
 268       struct df_ref *def = *def_rec;
 269       unsigned int regno = DF_REF_REGNO (def);
 270       /* This loop is a little tricky.  We cannot just go down the
 271          chain because it is being modified by the actions in the
 272          loop.  So we just get the head.  We plan to drain the list
 273          anyway.  */
 274       while (DF_REG_EQ_USE_CHAIN (regno))
 275         {
 276           struct df_ref *eq_use = DF_REG_EQ_USE_CHAIN (regno);
 277           rtx noted_insn = DF_REF_INSN (eq_use);
 278           rtx note = find_reg_note (noted_insn, REG_EQUAL, NULL_RTX);
 279           if (!note)
 280             note = find_reg_note (noted_insn, REG_EQUIV, NULL_RTX);
 281
 282           /* This assert is generally triggered when someone deletes a
 283              REG_EQUAL or REG_EQUIV note by hacking the list manually
 284              rather than calling remove_note.  */
 285           gcc_assert (note);
 286           remove_note (noted_insn, note);
 287         }
 288     }
 289 }
 290
 291
 292 /* Delete every instruction that hasn't been marked.  */
 293
 294 static void
 295 delete_unmarked_insns (void)
 296 {
 297   basic_block bb;
 298   rtx insn, next;
 299
 300   FOR_EACH_BB (bb)
 301     FOR_BB_INSNS_SAFE (bb, insn, next)
 302       if (INSN_P (insn))
 303         {
 304           rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
 305
 306           /* Always delete no-op moves.  */
 307           if (noop_move_p (insn))
 308             ;
 309
 310           /* Try to delete libcall sequences as a whole.  */
 311           else if (note && libcall_dead_p (insn, note))
 312             {
 313               rtx last = XEXP (note, 0);
 314
 315               if (!dbg_cnt (dce))
 316                 continue;
 317
 318               if (dump_file)
 319                 fprintf (dump_file, "DCE: Deleting libcall %d-%d\n",
 320                          INSN_UID (insn), INSN_UID (last));
 321
 322               next = NEXT_INSN (last);
 323               delete_insn_chain_and_edges (insn, last);
 324               continue;
 325             }
 326
 327           /* Otherwise rely only on the DCE algorithm.  */
 328           else if (marked_insn_p (insn))
 329             continue;
 330
 331           if (!dbg_cnt (dce))
 332             continue;
 333
 334           if (dump_file)
 335             fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
 336
 337           /* Before we delete the insn we have to delete REG_EQUAL notes
 338              for the destination regs in order to avoid dangling notes.  */
 339           delete_corresponding_reg_eq_notes (insn);
 340
 341           /* If we're about to delete the first insn of a libcall, then
 342              move the REG_LIBCALL note to the next real insn and update
 343              the REG_RETVAL note.  */
 344           if (note && (XEXP (note, 0) != insn))
 345             {
 346               rtx new_libcall_insn = next_real_insn (insn);
 347               rtx retval_note = find_reg_note (XEXP (note, 0),
 348                                                REG_RETVAL, NULL_RTX);
 349               /* If the RETVAL and LIBCALL notes would land on the same
 350                  insn just remove them.  */
 351               if (XEXP (note, 0) == new_libcall_insn)
 352                 remove_note (new_libcall_insn, retval_note);
 353               else
 354                 {
 355                   REG_NOTES (new_libcall_insn)
 356                     = gen_rtx_INSN_LIST (REG_LIBCALL, XEXP (note, 0),
 357                                          REG_NOTES (new_libcall_insn));
 358                   XEXP (retval_note, 0) = new_libcall_insn;
 359                 }
 360             }
 361
 362           /* If the insn contains a REG_RETVAL note and is dead, but the
 363              libcall as a whole is not dead, then we want to remove the
 364              insn, but not the whole libcall sequence.  However, we also
 365              need to remove the dangling REG_LIBCALL note in order to
 366              avoid mismatched notes.  We could find a new location for
 367              the REG_RETVAL note, but it hardly seems worth the effort.  */
 368           note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
 369           if (note && (XEXP (note, 0) != insn))
 370             {
 371               rtx libcall_note
 372                 = find_reg_note (XEXP (note, 0), REG_LIBCALL, NULL_RTX);
 373               remove_note (XEXP (note, 0), libcall_note);
 374             }
 375
 376           /* Now delete the insn.  */
 377           delete_insn_and_edges (insn);
 378         }
 379 }
 380
 381
 382 /* Helper function for prescan_insns_for_dce: prescan the entire libcall
 383    sequence starting at INSN and return the insn following the libcall.
 384    NOTE is the REG_LIBCALL note attached to INSN.  */
 385
 386 static rtx
 387 prescan_libcall_for_dce (rtx insn, rtx note, bool fast)
 388 {
 389   rtx last = XEXP (note, 0);
 390
 391   /* A libcall is never necessary on its own but we need to mark the stores
 392      to a non-register destination.  */
 393   while (insn != last && !CALL_P (insn))
 394     {
 395       if (INSN_P (insn))
 396         mark_nonreg_stores (PATTERN (insn), insn, fast);
 397       insn = NEXT_INSN (insn);
 398     }
 399
 400   /* If this is a call that returns a value via an invisible pointer, the
 401      dataflow engine cannot see it so it has to be marked unconditionally.  */
 402   if (CALL_P (insn) && !single_set (insn))
 403     {
 404       mark_insn (insn, fast);
 405       insn = NEXT_INSN (insn);
 406     }
 407
 408   while (insn != NEXT_INSN (last))
 409     {
 410       if (INSN_P (insn))
 411         mark_nonreg_stores (PATTERN (insn), insn, fast);
 412       insn = NEXT_INSN (insn);
 413     }
 414
 415   return insn;
 416 }
 417
 418
 419 /* Go through the instructions and mark those whose necessity is not
 420    dependent on inter-instruction information.  Make sure all other
 421    instructions are not marked.  */
 422
 423 static void
 424 prescan_insns_for_dce (bool fast)
 425 {
 426   basic_block bb;
 427   rtx insn, next;
 428
 429   if (dump_file)
 430     fprintf (dump_file, "Finding needed instructions:\n");
 431
 432   FOR_EACH_BB (bb)
 433     FOR_BB_INSNS_SAFE (bb, insn, next)
 434       if (INSN_P (insn))
 435         {
 436           rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
 437           if (note)
 438             next = prescan_libcall_for_dce (insn, note, fast);
 439           else if (deletable_insn_p (insn, fast))
 440             mark_nonreg_stores (PATTERN (insn), insn, fast);
 441           else
 442             mark_insn (insn, fast);
 443         }
 444
 445   if (dump_file)
 446     fprintf (dump_file, "Finished finding needed instructions:\n");
 447 }
 448
 449
 450 /* UD-based DSE routines. */
 451
 452 /* Mark instructions that define artificially-used registers, such as
 453    the frame pointer and the stack pointer.  */
 454
 455 static void
 456 mark_artificial_uses (void)
 457 {
 458   basic_block bb;
 459   struct df_link *defs;
 460   struct df_ref **use_rec;
 461
 462   FOR_ALL_BB (bb)
 463     {
 464       for (use_rec = df_get_artificial_uses (bb->index);
 465            *use_rec; use_rec++)
 466         for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 467           mark_insn (DF_REF_INSN (defs->ref), false);
 468     }
 469 }
 470
 471
 472 /* Mark every instruction that defines a register value that INSN uses.  */
 473
 474 static void
 475 mark_reg_dependencies (rtx insn)
 476 {
 477   struct df_link *defs;
 478   struct df_ref **use_rec;
 479
 480   for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
 481     {
 482       struct df_ref *use = *use_rec;
 483       if (dump_file)
 484         {
 485           fprintf (dump_file, "Processing use of ");
 486           print_simple_rtl (dump_file, DF_REF_REG (use));
 487           fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
 488         }
 489       for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
 490         mark_insn (DF_REF_INSN (defs->ref), false);
 491     }
 492 }
 493
 494
 495 /* Initialize global variables for a new DCE pass.  */
 496
 497 static void
 498 init_dce (bool fast)
 499 {
 500   if (!df_in_progress)
 501     {
 502       if (!fast)
 503         df_chain_add_problem (DF_UD_CHAIN);
 504       df_analyze ();
 505     }
 506
 507   if (dump_file)
 508     df_dump (dump_file);
 509
 510   if (fast)
 511     {
 512       bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
 513       bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
 514     }
 515
 516   marked = sbitmap_alloc (get_max_uid () + 1);
 517   sbitmap_zero (marked);
 518 }
 519
 520
 521 /* Free the data allocated by init_dce.  */
 522
 523 static void
 524 fini_dce (bool fast)
 525 {
 526   sbitmap_free (marked);
 527
 528   if (fast)
 529     {
 530       bitmap_obstack_release (&dce_blocks_bitmap_obstack);
 531       bitmap_obstack_release (&dce_tmp_bitmap_obstack);
 532     }
 533 }
 534
 535
 536 /* UD-chain based DCE.  */
 537
 538 static unsigned int
 539 rest_of_handle_ud_dce (void)
 540 {
 541   rtx insn;
 542
 543   init_dce (false);
 544
 545   prescan_insns_for_dce (false);
 546   mark_artificial_uses ();
 547   while (VEC_length (rtx, worklist) > 0)
 548     {
 549       insn = VEC_pop (rtx, worklist);
 550       mark_reg_dependencies (insn);
 551     }
 552
 553   /* Before any insns are deleted, we must remove the chains since
 554      they are not bidirectional.  */
 555   df_remove_problem (df_chain);
 556   delete_unmarked_insns ();
 557
 558   fini_dce (false);
 559   return 0;
 560 }
 561
 562
 563 static bool
 564 gate_ud_dce (void)
 565 {
 566   return optimize > 1 && flag_dce
 567     && dbg_cnt (dce_ud);
 568 }
 569
 570 struct rtl_opt_pass pass_ud_rtl_dce =
 571 {
 572  {
 573   RTL_PASS,
 574   "dce",                                /* name */
 575   gate_ud_dce,                        /* gate */
 576   rest_of_handle_ud_dce,              /* execute */
 577   NULL,                                 /* sub */
 578   NULL,                                 /* next */
 579   0,                                    /* static_pass_number */
 580   TV_DCE,                               /* tv_id */
 581   0,                                    /* properties_required */
 582   0,                                    /* properties_provided */
 583   0,                                    /* properties_destroyed */
 584   0,                                    /* todo_flags_start */
 585   TODO_dump_func |
 586   TODO_df_finish | TODO_verify_rtl_sharing |
 587   TODO_ggc_collect                     /* todo_flags_finish */
 588  }
 589 };
 590
 591
 592 /* -------------------------------------------------------------------------
 593    Fast DCE functions
 594    ------------------------------------------------------------------------- */
 595
 596 /* Process basic block BB.  Return true if the live_in set has
 597    changed. REDO_OUT is true if the info at the bottom of the block
 598    needs to be recalculated before starting.  AU is the proper set of
 599    artificial uses. */
 600
 601 static bool
 602 byte_dce_process_block (basic_block bb, bool redo_out, bitmap au)
 603 {
 604   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
 605   rtx insn;
 606   bool block_changed;
 607   struct df_ref **def_rec;
 608
 609   if (redo_out)
 610     {
 611       /* Need to redo the live_out set of this block if when one of
 612          the succs of this block has had a change in it live in
 613          set.  */
 614       edge e;
 615       edge_iterator ei;
 616       df_confluence_function_n con_fun_n = df_byte_lr->problem->con_fun_n;
 617       bitmap_clear (DF_BYTE_LR_OUT (bb));
 618       FOR_EACH_EDGE (e, ei, bb->succs)
 619         (*con_fun_n) (e);
 620     }
 621
 622   if (dump_file)
 623     {
 624       fprintf (dump_file, "processing block %d live out = ", bb->index);
 625       df_print_byte_regset (dump_file, DF_BYTE_LR_OUT (bb));
 626     }
 627
 628   bitmap_copy (local_live, DF_BYTE_LR_OUT (bb));
 629
 630   df_byte_lr_simulate_artificial_refs_at_end (bb, local_live);
 631
 632   FOR_BB_INSNS_REVERSE (bb, insn)
 633     if (INSN_P (insn))
 634       {
 635         /* The insn is needed if there is someone who uses the output.  */
 636         for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 637           {
 638             struct df_ref *def = *def_rec;
 639             unsigned int last;
 640             unsigned int dregno = DF_REF_REGNO (def);
 641             unsigned int start = df_byte_lr_get_regno_start (dregno);
 642             unsigned int len = df_byte_lr_get_regno_len (dregno);
 643
 644             unsigned int sb;
 645             unsigned int lb;
 646             /* This is one of the only places where DF_MM_MAY should
 647                be used for defs.  Need to make sure that we are
 648                checking for all of the bits that may be used.  */
 649
 650             if (!df_compute_accessed_bytes (def, DF_MM_MAY, &sb, &lb))
 651               {
 652                 start += sb;
 653                 len = lb - sb;
 654               }
 655
 656             if (bitmap_bit_p (au, dregno))
 657               {
 658                 mark_insn (insn, true);
 659                 goto quickexit;
 660               }
 661
 662             last = start + len;
 663             while (start < last)
 664               if (bitmap_bit_p (local_live, start++))
 665                 {
 666                   mark_insn (insn, true);
 667                   goto quickexit;
 668                 }
 669           }
 670
 671       quickexit:
 672
 673         /* No matter if the instruction is needed or not, we remove
 674            any regno in the defs from the live set.  */
 675         df_byte_lr_simulate_defs (insn, local_live);
 676
 677         /* On the other hand, we do not allow the dead uses to set
 678            anything in local_live.  */
 679         if (marked_insn_p (insn))
 680           df_byte_lr_simulate_uses (insn, local_live);
 681
 682         if (dump_file)
 683           {
 684             fprintf (dump_file, "finished processing insn %d live out = ",
 685                      INSN_UID (insn));
 686             df_print_byte_regset (dump_file, local_live);
 687           }
 688       }
 689
 690   df_byte_lr_simulate_artificial_refs_at_top (bb, local_live);
 691
 692   block_changed = !bitmap_equal_p (local_live, DF_BYTE_LR_IN (bb));
 693   if (block_changed)
 694     bitmap_copy (DF_BYTE_LR_IN (bb), local_live);
 695   BITMAP_FREE (local_live);
 696   return block_changed;
 697 }
 698
 699
 700 /* Process basic block BB.  Return true if the live_in set has
 701    changed. REDO_OUT is true if the info at the bottom of the block
 702    needs to be recalculated before starting.  AU is the proper set of
 703    artificial uses. */
 704
 705 static bool
 706 dce_process_block (basic_block bb, bool redo_out, bitmap au)
 707 {
 708   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
 709   rtx insn;
 710   bool block_changed;
 711   struct df_ref **def_rec;
 712
 713   if (redo_out)
 714     {
 715       /* Need to redo the live_out set of this block if when one of
 716          the succs of this block has had a change in it live in
 717          set.  */
 718       edge e;
 719       edge_iterator ei;
 720       df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
 721       bitmap_clear (DF_LR_OUT (bb));
 722       FOR_EACH_EDGE (e, ei, bb->succs)
 723         (*con_fun_n) (e);
 724     }
 725
 726   if (dump_file)
 727     {
 728       fprintf (dump_file, "processing block %d live out = ", bb->index);
 729       df_print_regset (dump_file, DF_LR_OUT (bb));
 730     }
 731
 732   bitmap_copy (local_live, DF_LR_OUT (bb));
 733
 734   df_simulate_artificial_refs_at_end (bb, local_live);
 735
 736   FOR_BB_INSNS_REVERSE (bb, insn)
 737     if (INSN_P (insn))
 738       {
 739         bool needed = false;
 740
 741         /* The insn is needed if there is someone who uses the output.  */
 742         for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 743           if (bitmap_bit_p (local_live, DF_REF_REGNO (*def_rec))
 744               || bitmap_bit_p (au, DF_REF_REGNO (*def_rec)))
 745             {
 746               needed = true;
 747               break;
 748             }
 749
 750         if (needed)
 751           mark_insn (insn, true);
 752
 753         /* No matter if the instruction is needed or not, we remove
 754            any regno in the defs from the live set.  */
 755         df_simulate_defs (insn, local_live);
 756
 757         /* On the other hand, we do not allow the dead uses to set
 758            anything in local_live.  */
 759         if (marked_insn_p (insn))
 760           df_simulate_uses (insn, local_live);
 761       }
 762
 763   df_simulate_artificial_refs_at_top (bb, local_live);
 764
 765   block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
 766   if (block_changed)
 767     bitmap_copy (DF_LR_IN (bb), local_live);
 768
 769   BITMAP_FREE (local_live);
 770   return block_changed;
 771 }
 772
 773
 774 /* Perform fast DCE once initialization is done.  If BYTE_LEVEL is
 775    true, use the byte level dce, otherwise do it at the pseudo
 776    level.  */
 777
 778 static void
 779 fast_dce (bool byte_level)
 780 {
 781   int *postorder = df_get_postorder (DF_BACKWARD);
 782   int n_blocks = df_get_n_blocks (DF_BACKWARD);
 783   /* The set of blocks that have been seen on this iteration.  */
 784   bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 785   /* The set of blocks that need to have the out vectors reset because
 786      the in of one of their successors has changed.  */
 787   bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 788   bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 789   bool global_changed = true;
 790
 791   /* These regs are considered always live so if they end up dying
 792      because of some def, we need to bring the back again.  Calling
 793      df_simulate_fixup_sets has the disadvantage of calling
 794      bb_has_eh_pred once per insn, so we cache the information
 795      here.  */
 796   bitmap au = df->regular_block_artificial_uses;
 797   bitmap au_eh = df->eh_block_artificial_uses;
 798   int i;
 799
 800   prescan_insns_for_dce (true);
 801
 802   for (i = 0; i < n_blocks; i++)
 803     bitmap_set_bit (all_blocks, postorder[i]);
 804
 805   while (global_changed)
 806     {
 807       global_changed = false;
 808
 809       for (i = 0; i < n_blocks; i++)
 810         {
 811           int index = postorder[i];
 812           basic_block bb = BASIC_BLOCK (index);
 813           bool local_changed;
 814
 815           if (index < NUM_FIXED_BLOCKS)
 816             {
 817               bitmap_set_bit (processed, index);
 818               continue;
 819             }
 820
 821           if (byte_level)
 822             local_changed
 823               = byte_dce_process_block (bb, bitmap_bit_p (redo_out, index),
 824                                           bb_has_eh_pred (bb) ? au_eh : au);
 825           else
 826             local_changed
 827               = dce_process_block (bb, bitmap_bit_p (redo_out, index),
 828                                    bb_has_eh_pred (bb) ? au_eh : au);
 829           bitmap_set_bit (processed, index);
 830
 831           if (local_changed)
 832             {
 833               edge e;
 834               edge_iterator ei;
 835               FOR_EACH_EDGE (e, ei, bb->preds)
 836                 if (bitmap_bit_p (processed, e->src->index))
 837                   /* Be tricky about when we need to iterate the
 838                      analysis.  We only have redo the analysis if the
 839                      bitmaps change at the top of a block that is the
 840                      entry to a loop.  */
 841                   global_changed = true;
 842                 else
 843                   bitmap_set_bit (redo_out, e->src->index);
 844             }
 845         }
 846
 847       if (global_changed)
 848         {
 849           /* Turn off the RUN_DCE flag to prevent recursive calls to
 850              dce.  */
 851           int old_flag = df_clear_flags (DF_LR_RUN_DCE);
 852
 853           /* So something was deleted that requires a redo.  Do it on
 854              the cheap.  */
 855           delete_unmarked_insns ();
 856           sbitmap_zero (marked);
 857           bitmap_clear (processed);
 858           bitmap_clear (redo_out);
 859
 860           /* We do not need to rescan any instructions.  We only need
 861              to redo the dataflow equations for the blocks that had a
 862              change at the top of the block.  Then we need to redo the
 863              iteration.  */
 864           if (byte_level)
 865             df_analyze_problem (df_byte_lr, all_blocks, postorder, n_blocks);
 866           else
 867             df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
 868
 869           if (old_flag & DF_LR_RUN_DCE)
 870             df_set_flags (DF_LR_RUN_DCE);
 871
 872           prescan_insns_for_dce (true);
 873         }
 874     }
 875
 876   delete_unmarked_insns ();
 877
 878   BITMAP_FREE (processed);
 879   BITMAP_FREE (redo_out);
 880   BITMAP_FREE (all_blocks);
 881 }
 882
 883
 884 /* Fast register level DCE.  */
 885
 886 static unsigned int
 887 rest_of_handle_fast_dce (void)
 888 {
 889   init_dce (true);
 890   fast_dce (false);
 891   fini_dce (true);
 892   return 0;
 893 }
 894
 895
 896 /* Fast byte level DCE.  */
 897
 898 static unsigned int
 899 rest_of_handle_fast_byte_dce (void)
 900 {
 901   df_byte_lr_add_problem ();
 902   init_dce (true);
 903   fast_dce (true);
 904   fini_dce (true);
 905   return 0;
 906 }
 907
 908
 909 /* This is an internal call that is used by the df live register
 910    problem to run fast dce as a side effect of creating the live
 911    information.  The stack is organized so that the lr problem is run,
 912    this pass is run, which updates the live info and the df scanning
 913    info, and then returns to allow the rest of the problems to be run.
 914
 915    This can be called by elsewhere but it will not update the bit
 916    vectors for any other problems than LR.  */
 917
 918 void
 919 run_fast_df_dce (void)
 920 {
 921   if (flag_dce)
 922     {
 923       /* If dce is able to delete something, it has to happen
 924          immediately.  Otherwise there will be problems handling the
 925          eq_notes.  */
 926       enum df_changeable_flags old_flags
 927         = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
 928
 929       df_in_progress = true;
 930       rest_of_handle_fast_dce ();
 931       df_in_progress = false;
 932
 933       df_set_flags (old_flags);
 934     }
 935 }
 936
 937
 938 /* Run a fast DCE pass.  */
 939
 940 void
 941 run_fast_dce (void)
 942 {
 943   if (flag_dce)
 944     rest_of_handle_fast_dce ();
 945 }
 946
 947
 948 static bool
 949 gate_fast_dce (void)
 950 {
 951   return optimize > 0 && flag_dce
 952     && dbg_cnt (dce_fast);
 953 }
 954
 955 struct rtl_opt_pass pass_fast_rtl_dce =
 956 {
 957  {
 958   RTL_PASS,
 959   "dce",                                /* name */
 960   gate_fast_dce,                        /* gate */
 961   rest_of_handle_fast_dce,              /* execute */
 962   NULL,                                 /* sub */
 963   NULL,                                 /* next */
 964   0,                                    /* static_pass_number */
 965   TV_DCE,                               /* tv_id */
 966   0,                                    /* properties_required */
 967   0,                                    /* properties_provided */
 968   0,                                    /* properties_destroyed */
 969   0,                                    /* todo_flags_start */
 970   TODO_dump_func |
 971   TODO_df_finish | TODO_verify_rtl_sharing |
 972   TODO_ggc_collect                      /* todo_flags_finish */
 973  }
 974 };
 975
 976 struct rtl_opt_pass pass_fast_rtl_byte_dce =
 977 {
 978  {
 979   RTL_PASS,
 980   "byte-dce",                           /* name */
 981   gate_fast_dce,                        /* gate */
 982   rest_of_handle_fast_byte_dce,         /* execute */
 983   NULL,                                 /* sub */
 984   NULL,                                 /* next */
 985   0,                                    /* static_pass_number */
 986   TV_DCE,                               /* tv_id */
 987   0,                                    /* properties_required */
 988   0,                                    /* properties_provided */
 989   0,                                    /* properties_destroyed */
 990   0,                                    /* todo_flags_start */
 991   TODO_dump_func |
 992   TODO_df_finish | TODO_verify_rtl_sharing |
 993   TODO_ggc_collect                      /* todo_flags_finish */
 994  }
 995 };