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