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 /* 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               REG_NOTES (new_libcall_insn)
 350                 = gen_rtx_INSN_LIST (REG_LIBCALL, XEXP (note, 0),
 351                                      REG_NOTES (new_libcall_insn));
 352               XEXP (retval_note, 0) = new_libcall_insn;
 353             }
 354
 355           /* If the insn contains a REG_RETVAL note and is dead, but the
 356              libcall as a whole is not dead, then we want to remove the
 357              insn, but not the whole libcall sequence.  However, we also
 358              need to remove the dangling REG_LIBCALL note in order to
 359              avoid mismatched notes.  We could find a new location for
 360              the REG_RETVAL note, but it hardly seems worth the effort.  */
 361           note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
 362           if (note && (XEXP (note, 0) != insn))
 363             {
 364               rtx libcall_note
 365                 = find_reg_note (XEXP (note, 0), REG_LIBCALL, NULL_RTX);
 366               remove_note (XEXP (note, 0), libcall_note);
 367             }
 368
 369           /* Now delete the insn.  */
 370           delete_insn_and_edges (insn);
 371         }
 372 }
 373
 374
 375 /* Helper function for prescan_insns_for_dce: prescan the entire libcall
 376    sequence starting at INSN and return the insn following the libcall.
 377    NOTE is the REG_LIBCALL note attached to INSN.  */
 378
 379 static rtx
 380 prescan_libcall_for_dce (rtx insn, rtx note, bool fast)
 381 {
 382   rtx last = XEXP (note, 0);
 383
 384   /* A libcall is never necessary on its own but we need to mark the stores
 385      to a non-register destination.  */
 386   while (insn != last && !CALL_P (insn))
 387     {
 388       if (INSN_P (insn))
 389         mark_nonreg_stores (PATTERN (insn), insn, fast);
 390       insn = NEXT_INSN (insn);
 391     }
 392
 393   /* If this is a call that returns a value via an invisible pointer, the
 394      dataflow engine cannot see it so it has to be marked unconditionally.  */
 395   if (CALL_P (insn) && !single_set (insn))
 396     {
 397       mark_insn (insn, fast);
 398       insn = NEXT_INSN (insn);
 399     }
 400
 401   while (insn != NEXT_INSN (last))
 402     {
 403       if (INSN_P (insn))
 404         mark_nonreg_stores (PATTERN (insn), insn, fast);
 405       insn = NEXT_INSN (insn);
 406     }
 407
 408   return insn;
 409 }
 410
 411
 412 /* Go through the instructions and mark those whose necessity is not
 413    dependent on inter-instruction information.  Make sure all other
 414    instructions are not marked.  */
 415
 416 static void
 417 prescan_insns_for_dce (bool fast)
 418 {
 419   basic_block bb;
 420   rtx insn, next;
 421
 422   if (dump_file)
 423     fprintf (dump_file, "Finding needed instructions:\n");
 424
 425   FOR_EACH_BB (bb)
 426     FOR_BB_INSNS_SAFE (bb, insn, next)
 427       if (INSN_P (insn))
 428         {
 429           rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
 430           if (note)
 431             next = prescan_libcall_for_dce (insn, note, fast);
 432           else if (deletable_insn_p (insn, fast))
 433             mark_nonreg_stores (PATTERN (insn), insn, fast);
 434           else
 435             mark_insn (insn, fast);
 436         }
 437
 438   if (dump_file)
 439     fprintf (dump_file, "Finished finding needed instructions:\n");
 440 }
 441
 442
 443 /* UD-based DSE routines. */
 444
 445 /* Mark instructions that define artificially-used registers, such as
 446    the frame pointer and the stack pointer.  */
 447
 448 static void
 449 mark_artificial_uses (void)
 450 {
 451   basic_block bb;
 452   struct df_link *defs;
 453   struct df_ref **use_rec;
 454
 455   FOR_ALL_BB (bb)
 456     {
 457       for (use_rec = df_get_artificial_uses (bb->index);
 458            *use_rec; use_rec++)
 459         for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 460           mark_insn (DF_REF_INSN (defs->ref), false);
 461     }
 462 }
 463
 464
 465 /* Mark every instruction that defines a register value that INSN uses.  */
 466
 467 static void
 468 mark_reg_dependencies (rtx insn)
 469 {
 470   struct df_link *defs;
 471   struct df_ref **use_rec;
 472
 473   for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
 474     {
 475       struct df_ref *use = *use_rec;
 476       if (dump_file)
 477         {
 478           fprintf (dump_file, "Processing use of ");
 479           print_simple_rtl (dump_file, DF_REF_REG (use));
 480           fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
 481         }
 482       for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
 483         mark_insn (DF_REF_INSN (defs->ref), false);
 484     }
 485 }
 486
 487
 488 /* Initialize global variables for a new DCE pass.  */
 489
 490 static void
 491 init_dce (bool fast)
 492 {
 493   if (!df_in_progress)
 494     {
 495       if (!fast)
 496         df_chain_add_problem (DF_UD_CHAIN);
 497       df_analyze ();
 498     }
 499
 500   if (dump_file)
 501     df_dump (dump_file);
 502
 503   if (fast)
 504     {
 505       bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
 506       bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
 507     }
 508
 509   marked = sbitmap_alloc (get_max_uid () + 1);
 510   sbitmap_zero (marked);
 511 }
 512
 513
 514 /* Free the data allocated by init_dce.  */
 515
 516 static void
 517 fini_dce (bool fast)
 518 {
 519   sbitmap_free (marked);
 520
 521   if (fast)
 522     {
 523       bitmap_obstack_release (&dce_blocks_bitmap_obstack);
 524       bitmap_obstack_release (&dce_tmp_bitmap_obstack);
 525     }
 526 }
 527
 528
 529 /* UD-chain based DCE.  */
 530
 531 static unsigned int
 532 rest_of_handle_ud_dce (void)
 533 {
 534   rtx insn;
 535
 536   init_dce (false);
 537
 538   prescan_insns_for_dce (false);
 539   mark_artificial_uses ();
 540   while (VEC_length (rtx, worklist) > 0)
 541     {
 542       insn = VEC_pop (rtx, worklist);
 543       mark_reg_dependencies (insn);
 544     }
 545
 546   /* Before any insns are deleted, we must remove the chains since
 547      they are not bidirectional.  */
 548   df_remove_problem (df_chain);
 549   delete_unmarked_insns ();
 550
 551   fini_dce (false);
 552   return 0;
 553 }
 554
 555
 556 static bool
 557 gate_ud_dce (void)
 558 {
 559   return optimize > 1 && flag_dce;
 560 }
 561
 562 struct tree_opt_pass pass_ud_rtl_dce =
 563 {
 564   "dce",                                /* name */
 565   gate_ud_dce,                        /* gate */
 566   rest_of_handle_ud_dce,              /* execute */
 567   NULL,                                 /* sub */
 568   NULL,                                 /* next */
 569   0,                                    /* static_pass_number */
 570   TV_DCE,                               /* tv_id */
 571   0,                                    /* properties_required */
 572   0,                                    /* properties_provided */
 573   0,                                    /* properties_destroyed */
 574   0,                                    /* todo_flags_start */
 575   TODO_dump_func |
 576   TODO_df_finish | TODO_verify_rtl_sharing |
 577   TODO_ggc_collect,                     /* todo_flags_finish */
 578   'w'                                   /* letter */
 579 };
 580
 581
 582 /* -------------------------------------------------------------------------
 583    Fast DCE functions
 584    ------------------------------------------------------------------------- */
 585
 586 /* Process basic block BB.  Return true if the live_in set has changed.  */
 587
 588 static bool
 589 dce_process_block (basic_block bb, bool redo_out)
 590 {
 591   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
 592   bitmap au;
 593   rtx insn;
 594   bool block_changed;
 595   struct df_ref **def_rec, **use_rec;
 596   unsigned int bb_index = bb->index;
 597
 598   if (redo_out)
 599     {
 600       /* Need to redo the live_out set of this block if when one of
 601          the succs of this block has had a change in it live in
 602          set.  */
 603       edge e;
 604       edge_iterator ei;
 605       df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
 606       bitmap_clear (DF_LR_OUT (bb));
 607       FOR_EACH_EDGE (e, ei, bb->succs)
 608         (*con_fun_n) (e);
 609     }
 610
 611   if (dump_file)
 612     {
 613       fprintf (dump_file, "processing block %d live out = ", bb->index);
 614       df_print_regset (dump_file, DF_LR_OUT (bb));
 615     }
 616
 617   bitmap_copy (local_live, DF_LR_OUT (bb));
 618
 619   /* Process the artificial defs and uses at the bottom of the block.  */
 620   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 621     {
 622       struct df_ref *def = *def_rec;
 623       if (((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 624           && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
 625         bitmap_clear_bit (local_live, DF_REF_REGNO (def));
 626     }
 627
 628   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 629     {
 630       struct df_ref *use = *use_rec;
 631       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 632         bitmap_set_bit (local_live, DF_REF_REGNO (use));
 633     }
 634
 635   /* These regs are considered always live so if they end up dying
 636      because of some def, we need to bring the back again.
 637      Calling df_simulate_fixup_sets has the disadvantage of calling
 638      bb_has_eh_pred once per insn, so we cache the information here.  */
 639   if (bb_has_eh_pred (bb))
 640     au = df->eh_block_artificial_uses;
 641   else
 642     au = df->regular_block_artificial_uses;
 643
 644   FOR_BB_INSNS_REVERSE (bb, insn)
 645     if (INSN_P (insn))
 646       {
 647         bool needed = false;
 648
 649         /* The insn is needed if there is someone who uses the output.  */
 650         for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 651           if (bitmap_bit_p (local_live, DF_REF_REGNO (*def_rec))
 652               || bitmap_bit_p (au, DF_REF_REGNO (*def_rec)))
 653             {
 654               needed = true;
 655               break;
 656             }
 657
 658         if (needed)
 659           mark_insn (insn, true);
 660
 661         /* No matter if the instruction is needed or not, we remove
 662            any regno in the defs from the live set.  */
 663         df_simulate_defs (insn, local_live);
 664
 665         /* On the other hand, we do not allow the dead uses to set
 666            anything in local_live.  */
 667         if (marked_insn_p (insn))
 668           df_simulate_uses (insn, local_live);
 669       }
 670
 671   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 672     {
 673       struct df_ref *def = *def_rec;
 674       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP)
 675           && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
 676         bitmap_clear_bit (local_live, DF_REF_REGNO (def));
 677     }
 678
 679 #ifdef EH_USES
 680   /* Process the uses that are live into an exception handler.  */
 681   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 682     {
 683       /* Add use to set of uses in this BB.  */
 684       struct df_ref *use = *use_rec;
 685       if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
 686         bitmap_set_bit (local_live, DF_REF_REGNO (use));
 687     }
 688 #endif
 689
 690   block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
 691   if (block_changed)
 692     bitmap_copy (DF_LR_IN (bb), local_live);
 693
 694   BITMAP_FREE (local_live);
 695   return block_changed;
 696 }
 697
 698
 699 /* Perform fast DCE once initialization is done.  */
 700
 701 static void
 702 fast_dce (void)
 703 {
 704   int *postorder = df_get_postorder (DF_BACKWARD);
 705   int n_blocks = df_get_n_blocks (DF_BACKWARD);
 706   /* The set of blocks that have been seen on this iteration.  */
 707   bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 708   /* The set of blocks that need to have the out vectors reset because
 709      the in of one of their successors has changed.  */
 710   bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 711   bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 712   bool global_changed = true;
 713   int i;
 714
 715   prescan_insns_for_dce (true);
 716
 717   for (i = 0; i < n_blocks; i++)
 718     bitmap_set_bit (all_blocks, postorder[i]);
 719
 720   while (global_changed)
 721     {
 722       global_changed = false;
 723
 724       for (i = 0; i < n_blocks; i++)
 725         {
 726           int index = postorder[i];
 727           basic_block bb = BASIC_BLOCK (index);
 728           bool local_changed;
 729
 730           if (index < NUM_FIXED_BLOCKS)
 731             {
 732               bitmap_set_bit (processed, index);
 733               continue;
 734             }
 735
 736           local_changed
 737             = dce_process_block (bb, bitmap_bit_p (redo_out, index));
 738           bitmap_set_bit (processed, index);
 739
 740           if (local_changed)
 741             {
 742               edge e;
 743               edge_iterator ei;
 744               FOR_EACH_EDGE (e, ei, bb->preds)
 745                 if (bitmap_bit_p (processed, e->src->index))
 746                   /* Be tricky about when we need to iterate the
 747                      analysis.  We only have redo the analysis if the
 748                      bitmaps change at the top of a block that is the
 749                      entry to a loop.  */
 750                   global_changed = true;
 751                 else
 752                   bitmap_set_bit (redo_out, e->src->index);
 753             }
 754         }
 755
 756       if (global_changed)
 757         {
 758           /* Turn off the RUN_DCE flag to prevent recursive calls to
 759              dce.  */
 760           int old_flag = df_clear_flags (DF_LR_RUN_DCE);
 761
 762           /* So something was deleted that requires a redo.  Do it on
 763              the cheap.  */
 764           delete_unmarked_insns ();
 765           sbitmap_zero (marked);
 766           bitmap_clear (processed);
 767           bitmap_clear (redo_out);
 768
 769           /* We do not need to rescan any instructions.  We only need
 770              to redo the dataflow equations for the blocks that had a
 771              change at the top of the block.  Then we need to redo the
 772              iteration.  */
 773           df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
 774
 775           if (old_flag & DF_LR_RUN_DCE)
 776             df_set_flags (DF_LR_RUN_DCE);
 777
 778           prescan_insns_for_dce (true);
 779         }
 780     }
 781
 782   delete_unmarked_insns ();
 783
 784   BITMAP_FREE (processed);
 785   BITMAP_FREE (redo_out);
 786   BITMAP_FREE (all_blocks);
 787 }
 788
 789
 790 /* Fast DCE.  */
 791
 792 static unsigned int
 793 rest_of_handle_fast_dce (void)
 794 {
 795   init_dce (true);
 796   fast_dce ();
 797   fini_dce (true);
 798   return 0;
 799 }
 800
 801
 802 /* This is an internal call that is used by the df live register
 803    problem to run fast dce as a side effect of creating the live
 804    information.  The stack is organized so that the lr problem is run,
 805    this pass is run, which updates the live info and the df scanning
 806    info, and then returns to allow the rest of the problems to be run.
 807
 808    This can be called by elsewhere but it will not update the bit
 809    vectors for any other problems than LR.  */
 810
 811 void
 812 run_fast_df_dce (void)
 813 {
 814   if (flag_dce)
 815     {
 816       /* If dce is able to delete something, it has to happen
 817          immediately.  Otherwise there will be problems handling the
 818          eq_notes.  */
 819       enum df_changeable_flags old_flags
 820         = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
 821
 822       df_in_progress = true;
 823       rest_of_handle_fast_dce ();
 824       df_in_progress = false;
 825
 826       df_set_flags (old_flags);
 827     }
 828 }
 829
 830
 831 /* Run a fast DCE pass.  */
 832
 833 void
 834 run_fast_dce (void)
 835 {
 836   if (flag_dce)
 837     rest_of_handle_fast_dce ();
 838 }
 839
 840
 841 static bool
 842 gate_fast_dce (void)
 843 {
 844   return optimize > 0 && flag_dce;
 845 }
 846
 847 struct tree_opt_pass pass_fast_rtl_dce =
 848 {
 849   "dce",                                /* name */
 850   gate_fast_dce,                        /* gate */
 851   rest_of_handle_fast_dce,              /* execute */
 852   NULL,                                 /* sub */
 853   NULL,                                 /* next */
 854   0,                                    /* static_pass_number */
 855   TV_DCE,                               /* tv_id */
 856   0,                                    /* properties_required */
 857   0,                                    /* properties_provided */
 858   0,                                    /* properties_destroyed */
 859   0,                                    /* todo_flags_start */
 860   TODO_dump_func |
 861   TODO_df_finish | TODO_verify_rtl_sharing |
 862   TODO_ggc_collect,                     /* todo_flags_finish */
 863   'w'                                   /* letter */
 864 };