gcc/dce.c

   1 /* RTL dead code elimination.
   2    Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "hashtab.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "tree.h"
  27 #include "regs.h"
  28 #include "hard-reg-set.h"
  29 #include "flags.h"
  30 #include "except.h"
  31 #include "df.h"
  32 #include "cselib.h"
  33 #include "dce.h"
  34 #include "timevar.h"
  35 #include "tree-pass.h"
  36 #include "dbgcnt.h"
  37 #include "tm_p.h"
  38
  39
  40 /* -------------------------------------------------------------------------
  41    Core mark/delete routines
  42    ------------------------------------------------------------------------- */
  43
  44 /* True if we are invoked while the df engine is running; in this case,
  45    we don't want to reenter it.  */
  46 static bool df_in_progress = false;
  47
  48 /* Instructions that have been marked but whose dependencies have not
  49    yet been processed.  */
  50 static VEC(rtx,heap) *worklist;
  51
  52 /* Bitmap of instructions marked as needed indexed by INSN_UID.  */
  53 static sbitmap marked;
  54
  55 /* Bitmap obstacks used for block processing by the fast algorithm.  */
  56 static bitmap_obstack dce_blocks_bitmap_obstack;
  57 static bitmap_obstack dce_tmp_bitmap_obstack;
  58
  59 static bool find_call_stack_args (rtx, bool, bool, bitmap);
  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, bitmap arg_stores)
  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 find_call_stack_args (insn, false, fast, arg_stores);
 115
 116   if (!NONJUMP_INSN_P (insn))
 117     return false;
 118
 119   /* Similarly, we cannot delete other insns that can throw either.  */
 120   if (df_in_progress && flag_non_call_exceptions && can_throw_internal (insn))
 121     return false;
 122
 123   body = PATTERN (insn);
 124   switch (GET_CODE (body))
 125     {
 126     case USE:
 127       return false;
 128
 129     case CLOBBER:
 130       if (fast)
 131         {
 132           /* A CLOBBER of a dead pseudo register serves no purpose.
 133              That is not necessarily true for hard registers until
 134              after reload.  */
 135           x = XEXP (body, 0);
 136           return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);
 137         }
 138       else
 139         /* Because of the way that use-def chains are built, it is not
 140            possible to tell if the clobber is dead because it can
 141            never be the target of a use-def chain.  */
 142         return false;
 143
 144     case PARALLEL:
 145       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 146         if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))
 147           return false;
 148       return true;
 149
 150     default:
 151       return deletable_insn_p_1 (body);
 152     }
 153 }
 154
 155
 156 /* Return true if INSN has been marked as needed.  */
 157
 158 static inline int
 159 marked_insn_p (rtx insn)
 160 {
 161   /* Artificial defs are always needed and they do not have an insn.
 162      We should never see them here.  */
 163   gcc_assert (insn);
 164   return TEST_BIT (marked, INSN_UID (insn));
 165 }
 166
 167
 168 /* If INSN has not yet been marked as needed, mark it now, and add it to
 169    the worklist.  */
 170
 171 static void
 172 mark_insn (rtx insn, bool fast)
 173 {
 174   if (!marked_insn_p (insn))
 175     {
 176       if (!fast)
 177         VEC_safe_push (rtx, heap, worklist, insn);
 178       SET_BIT (marked, INSN_UID (insn));
 179       if (dump_file)
 180         fprintf (dump_file, "  Adding insn %d to worklist\n", INSN_UID (insn));
 181       if (CALL_P (insn)
 182           && !df_in_progress
 183           && !SIBLING_CALL_P (insn)
 184           && (RTL_CONST_OR_PURE_CALL_P (insn)
 185               && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))
 186         find_call_stack_args (insn, true, fast, NULL);
 187     }
 188 }
 189
 190
 191 /* A note_stores callback used by mark_nonreg_stores.  DATA is the
 192    instruction containing DEST.  */
 193
 194 static void
 195 mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data)
 196 {
 197   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
 198     mark_insn ((rtx) data, true);
 199 }
 200
 201
 202 /* A note_stores callback used by mark_nonreg_stores.  DATA is the
 203    instruction containing DEST.  */
 204
 205 static void
 206 mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)
 207 {
 208   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
 209     mark_insn ((rtx) data, false);
 210 }
 211
 212
 213 /* Mark INSN if BODY stores to a non-register destination.  */
 214
 215 static void
 216 mark_nonreg_stores (rtx body, rtx insn, bool fast)
 217 {
 218   if (fast)
 219     note_stores (body, mark_nonreg_stores_1, insn);
 220   else
 221     note_stores (body, mark_nonreg_stores_2, insn);
 222 }
 223
 224
 225 /* Try to find all stack stores of CALL_INSN arguments if
 226    ACCUMULATE_OUTGOING_ARGS.  If all stack stores have been found
 227    and it is therefore safe to eliminate the call, return true,
 228    otherwise return false.  This function should be first called
 229    with DO_MARK false, and only when the CALL_INSN is actually
 230    going to be marked called again with DO_MARK true.  */
 231
 232 static bool
 233 find_call_stack_args (rtx call_insn, bool do_mark, bool fast,
 234                       bitmap arg_stores)
 235 {
 236   rtx p, insn, prev_insn;
 237   bool ret;
 238   HOST_WIDE_INT min_sp_off, max_sp_off;
 239   bitmap sp_bytes;
 240
 241   gcc_assert (CALL_P (call_insn));
 242   if (!ACCUMULATE_OUTGOING_ARGS)
 243     return true;
 244
 245   if (!do_mark)
 246     {
 247       gcc_assert (arg_stores);
 248       bitmap_clear (arg_stores);
 249     }
 250
 251   min_sp_off = INTTYPE_MAXIMUM (HOST_WIDE_INT);
 252   max_sp_off = 0;
 253
 254   /* First determine the minimum and maximum offset from sp for
 255      stored arguments.  */
 256   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
 257     if (GET_CODE (XEXP (p, 0)) == USE
 258         && MEM_P (XEXP (XEXP (p, 0), 0)))
 259       {
 260         rtx mem = XEXP (XEXP (p, 0), 0), addr, size;
 261         HOST_WIDE_INT off = 0;
 262         size = MEM_SIZE (mem);
 263         if (size == NULL_RTX)
 264           return false;
 265         addr = XEXP (mem, 0);
 266         if (GET_CODE (addr) == PLUS
 267             && REG_P (XEXP (addr, 0))
 268             && CONST_INT_P (XEXP (addr, 1)))
 269           {
 270             off = INTVAL (XEXP (addr, 1));
 271             addr = XEXP (addr, 0);
 272           }
 273         if (addr != stack_pointer_rtx)
 274           {
 275             if (!REG_P (addr))
 276               return false;
 277             /* If not fast, use chains to see if addr wasn't set to
 278                sp + offset.  */
 279             if (!fast)
 280               {
 281                 df_ref *use_rec;
 282                 struct df_link *defs;
 283                 rtx set;
 284
 285                 for (use_rec = DF_INSN_USES (call_insn); *use_rec; use_rec++)
 286                   if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))
 287                     break;
 288
 289                 if (*use_rec == NULL)
 290                   return false;
 291
 292                 for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 293                   if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 294                     break;
 295
 296                 if (defs == NULL)
 297                   return false;
 298
 299                 set = single_set (DF_REF_INSN (defs->ref));
 300                 if (!set)
 301                   return false;
 302
 303                 if (GET_CODE (SET_SRC (set)) != PLUS
 304                     || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
 305                     || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
 306                   return false;
 307
 308                 off += INTVAL (XEXP (SET_SRC (set), 1));
 309               }
 310             else
 311               return false;
 312           }
 313         min_sp_off = MIN (min_sp_off, off);
 314         max_sp_off = MAX (max_sp_off, off + INTVAL (size));
 315       }
 316
 317   if (min_sp_off >= max_sp_off)
 318     return true;
 319   sp_bytes = BITMAP_ALLOC (NULL);
 320
 321   /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
 322      which contain arguments.  Checking has been done in the previous
 323      loop.  */
 324   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
 325     if (GET_CODE (XEXP (p, 0)) == USE
 326         && MEM_P (XEXP (XEXP (p, 0), 0)))
 327       {
 328         rtx mem = XEXP (XEXP (p, 0), 0), addr;
 329         HOST_WIDE_INT off = 0, byte;
 330         addr = XEXP (mem, 0);
 331         if (GET_CODE (addr) == PLUS
 332             && REG_P (XEXP (addr, 0))
 333             && CONST_INT_P (XEXP (addr, 1)))
 334           {
 335             off = INTVAL (XEXP (addr, 1));
 336             addr = XEXP (addr, 0);
 337           }
 338         if (addr != stack_pointer_rtx)
 339           {
 340             df_ref *use_rec;
 341             struct df_link *defs;
 342             rtx set;
 343
 344             for (use_rec = DF_INSN_USES (call_insn); *use_rec; use_rec++)
 345               if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))
 346                 break;
 347
 348             for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 349               if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 350                 break;
 351
 352             set = single_set (DF_REF_INSN (defs->ref));
 353             off += INTVAL (XEXP (SET_SRC (set), 1));
 354           }
 355         for (byte = off; byte < off + INTVAL (MEM_SIZE (mem)); byte++)
 356           {
 357             if (!bitmap_set_bit (sp_bytes, byte - min_sp_off))
 358               gcc_unreachable ();
 359           }
 360       }
 361
 362   /* Walk backwards, looking for argument stores.  The search stops
 363      when seeing another call, sp adjustment or memory store other than
 364      argument store.  */
 365   ret = false;
 366   for (insn = PREV_INSN (call_insn); insn; insn = prev_insn)
 367     {
 368       rtx set, mem, addr;
 369       HOST_WIDE_INT off, byte;
 370
 371       if (insn == BB_HEAD (BLOCK_FOR_INSN (call_insn)))
 372         prev_insn = NULL_RTX;
 373       else
 374         prev_insn = PREV_INSN (insn);
 375
 376       if (CALL_P (insn))
 377         break;
 378
 379       if (!INSN_P (insn))
 380         continue;
 381
 382       set = single_set (insn);
 383       if (!set || SET_DEST (set) == stack_pointer_rtx)
 384         break;
 385
 386       if (!MEM_P (SET_DEST (set)))
 387         continue;
 388
 389       mem = SET_DEST (set);
 390       addr = XEXP (mem, 0);
 391       off = 0;
 392       if (GET_CODE (addr) == PLUS
 393           && REG_P (XEXP (addr, 0))
 394           && CONST_INT_P (XEXP (addr, 1)))
 395         {
 396           off = INTVAL (XEXP (addr, 1));
 397           addr = XEXP (addr, 0);
 398         }
 399       if (addr != stack_pointer_rtx)
 400         {
 401           if (!REG_P (addr))
 402             break;
 403           if (!fast)
 404             {
 405               df_ref *use_rec;
 406               struct df_link *defs;
 407               rtx set;
 408
 409               for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
 410                 if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))
 411                   break;
 412
 413               if (*use_rec == NULL)
 414                 break;
 415
 416               for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 417                 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 418                   break;
 419
 420               if (defs == NULL)
 421                 break;
 422
 423               set = single_set (DF_REF_INSN (defs->ref));
 424               if (!set)
 425                 break;
 426
 427               if (GET_CODE (SET_SRC (set)) != PLUS
 428                   || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
 429                   || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
 430                 break;
 431
 432               off += INTVAL (XEXP (SET_SRC (set), 1));
 433             }
 434           else
 435             break;
 436         }
 437
 438       if (GET_MODE_SIZE (GET_MODE (mem)) == 0)
 439         break;
 440
 441       for (byte = off; byte < off + GET_MODE_SIZE (GET_MODE (mem)); byte++)
 442         {
 443           if (byte < min_sp_off
 444               || byte >= max_sp_off
 445               || !bitmap_clear_bit (sp_bytes, byte - min_sp_off))
 446             break;
 447         }
 448
 449       if (!deletable_insn_p (insn, fast, NULL))
 450         break;
 451
 452       if (do_mark)
 453         mark_insn (insn, fast);
 454       else
 455         bitmap_set_bit (arg_stores, INSN_UID (insn));
 456
 457       if (bitmap_empty_p (sp_bytes))
 458         {
 459           ret = true;
 460           break;
 461         }
 462     }
 463
 464   BITMAP_FREE (sp_bytes);
 465   if (!ret && arg_stores)
 466     bitmap_clear (arg_stores);
 467
 468   return ret;
 469 }
 470
 471
 472 /* Delete all REG_EQUAL notes of the registers INSN writes, to prevent
 473    bad dangling REG_EQUAL notes. */
 474
 475 static void
 476 delete_corresponding_reg_eq_notes (rtx insn)
 477 {
 478   df_ref *def_rec;
 479   for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 480     {
 481       df_ref def = *def_rec;
 482       unsigned int regno = DF_REF_REGNO (def);
 483       /* This loop is a little tricky.  We cannot just go down the
 484          chain because it is being modified by the actions in the
 485          loop.  So we just get the head.  We plan to drain the list
 486          anyway.  */
 487       while (DF_REG_EQ_USE_CHAIN (regno))
 488         {
 489           df_ref eq_use = DF_REG_EQ_USE_CHAIN (regno);
 490           rtx noted_insn = DF_REF_INSN (eq_use);
 491           rtx note = find_reg_note (noted_insn, REG_EQUAL, NULL_RTX);
 492           if (!note)
 493             note = find_reg_note (noted_insn, REG_EQUIV, NULL_RTX);
 494
 495           /* This assert is generally triggered when someone deletes a
 496              REG_EQUAL or REG_EQUIV note by hacking the list manually
 497              rather than calling remove_note.  */
 498           gcc_assert (note);
 499           remove_note (noted_insn, note);
 500         }
 501     }
 502 }
 503
 504
 505 /* Delete every instruction that hasn't been marked.  */
 506
 507 static void
 508 delete_unmarked_insns (void)
 509 {
 510   basic_block bb;
 511   rtx insn, next;
 512   bool must_clean = false;
 513
 514   FOR_EACH_BB_REVERSE (bb)
 515     FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
 516       if (INSN_P (insn))
 517         {
 518           /* Always delete no-op moves.  */
 519           if (noop_move_p (insn))
 520             ;
 521
 522           /* Otherwise rely only on the DCE algorithm.  */
 523           else if (marked_insn_p (insn))
 524             continue;
 525
 526           /* Beware that reaching a dbg counter limit here can result
 527              in miscompiled file.  This occurs when a group of insns
 528              must be deleted together, typically because the kept insn
 529              depends on the output from the deleted insn.  Deleting
 530              this insns in reverse order (both at the bb level and
 531              when looking at the blocks) minimizes this, but does not
 532              eliminate it, since it is possible for the using insn to
 533              be top of a block and the producer to be at the bottom of
 534              the block.  However, in most cases this will only result
 535              in an uninitialized use of an insn that is dead anyway.
 536
 537              However, there is one rare case that will cause a
 538              miscompile: deletion of non-looping pure and constant
 539              calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
 540              In this case it is possible to remove the call, but leave
 541              the argument pushes to the stack.  Because of the changes
 542              to the stack pointer, this will almost always lead to a
 543              miscompile.  */
 544           if (!dbg_cnt (dce))
 545             continue;
 546
 547           if (dump_file)
 548             fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
 549
 550           /* Before we delete the insn we have to delete REG_EQUAL notes
 551              for the destination regs in order to avoid dangling notes.  */
 552           delete_corresponding_reg_eq_notes (insn);
 553
 554           /* If a pure or const call is deleted, this may make the cfg
 555              have unreachable blocks.  We rememeber this and call
 556              delete_unreachable_blocks at the end.  */
 557           if (CALL_P (insn))
 558             must_clean = true;
 559
 560           /* Now delete the insn.  */
 561           delete_insn_and_edges (insn);
 562         }
 563
 564   /* Deleted a pure or const call.  */
 565   if (must_clean)
 566     delete_unreachable_blocks ();
 567 }
 568
 569
 570 /* Go through the instructions and mark those whose necessity is not
 571    dependent on inter-instruction information.  Make sure all other
 572    instructions are not marked.  */
 573
 574 static void
 575 prescan_insns_for_dce (bool fast)
 576 {
 577   basic_block bb;
 578   rtx insn, prev;
 579   bitmap arg_stores = NULL;
 580
 581   if (dump_file)
 582     fprintf (dump_file, "Finding needed instructions:\n");
 583
 584   if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS)
 585     arg_stores = BITMAP_ALLOC (NULL);
 586
 587   FOR_EACH_BB (bb)
 588     {
 589       FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)
 590         if (INSN_P (insn))
 591           {
 592             /* Don't mark argument stores now.  They will be marked
 593                if needed when the associated CALL is marked.  */
 594             if (arg_stores && bitmap_bit_p (arg_stores, INSN_UID (insn)))
 595               continue;
 596             if (deletable_insn_p (insn, fast, arg_stores))
 597               mark_nonreg_stores (PATTERN (insn), insn, fast);
 598             else
 599               mark_insn (insn, fast);
 600           }
 601       /* find_call_stack_args only looks at argument stores in the
 602          same bb.  */
 603       if (arg_stores)
 604         bitmap_clear (arg_stores);
 605     }
 606
 607   if (arg_stores)
 608     BITMAP_FREE (arg_stores);
 609
 610   if (dump_file)
 611     fprintf (dump_file, "Finished finding needed instructions:\n");
 612 }
 613
 614
 615 /* UD-based DSE routines. */
 616
 617 /* Mark instructions that define artificially-used registers, such as
 618    the frame pointer and the stack pointer.  */
 619
 620 static void
 621 mark_artificial_uses (void)
 622 {
 623   basic_block bb;
 624   struct df_link *defs;
 625   df_ref *use_rec;
 626
 627   FOR_ALL_BB (bb)
 628     {
 629       for (use_rec = df_get_artificial_uses (bb->index);
 630            *use_rec; use_rec++)
 631         for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 632           if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 633             mark_insn (DF_REF_INSN (defs->ref), false);
 634     }
 635 }
 636
 637
 638 /* Mark every instruction that defines a register value that INSN uses.  */
 639
 640 static void
 641 mark_reg_dependencies (rtx insn)
 642 {
 643   struct df_link *defs;
 644   df_ref *use_rec;
 645
 646   for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
 647     {
 648       df_ref use = *use_rec;
 649       if (dump_file)
 650         {
 651           fprintf (dump_file, "Processing use of ");
 652           print_simple_rtl (dump_file, DF_REF_REG (use));
 653           fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
 654         }
 655       for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
 656         if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 657           mark_insn (DF_REF_INSN (defs->ref), false);
 658     }
 659 }
 660
 661
 662 /* Initialize global variables for a new DCE pass.  */
 663
 664 static void
 665 init_dce (bool fast)
 666 {
 667   if (!df_in_progress)
 668     {
 669       if (!fast)
 670         df_chain_add_problem (DF_UD_CHAIN);
 671       df_analyze ();
 672     }
 673
 674   if (dump_file)
 675     df_dump (dump_file);
 676
 677   if (fast)
 678     {
 679       bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
 680       bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
 681     }
 682
 683   marked = sbitmap_alloc (get_max_uid () + 1);
 684   sbitmap_zero (marked);
 685 }
 686
 687
 688 /* Free the data allocated by init_dce.  */
 689
 690 static void
 691 fini_dce (bool fast)
 692 {
 693   sbitmap_free (marked);
 694
 695   if (fast)
 696     {
 697       bitmap_obstack_release (&dce_blocks_bitmap_obstack);
 698       bitmap_obstack_release (&dce_tmp_bitmap_obstack);
 699     }
 700 }
 701
 702
 703 /* UD-chain based DCE.  */
 704
 705 static unsigned int
 706 rest_of_handle_ud_dce (void)
 707 {
 708   rtx insn;
 709
 710   init_dce (false);
 711
 712   prescan_insns_for_dce (false);
 713   mark_artificial_uses ();
 714   while (VEC_length (rtx, worklist) > 0)
 715     {
 716       insn = VEC_pop (rtx, worklist);
 717       mark_reg_dependencies (insn);
 718     }
 719   VEC_free (rtx, heap, worklist);
 720
 721   /* Before any insns are deleted, we must remove the chains since
 722      they are not bidirectional.  */
 723   df_remove_problem (df_chain);
 724   delete_unmarked_insns ();
 725
 726   fini_dce (false);
 727   return 0;
 728 }
 729
 730
 731 static bool
 732 gate_ud_dce (void)
 733 {
 734   return optimize > 1 && flag_dce
 735     && dbg_cnt (dce_ud);
 736 }
 737
 738 struct rtl_opt_pass pass_ud_rtl_dce =
 739 {
 740  {
 741   RTL_PASS,
 742   "dce",                                /* name */
 743   gate_ud_dce,                        /* gate */
 744   rest_of_handle_ud_dce,              /* execute */
 745   NULL,                                 /* sub */
 746   NULL,                                 /* next */
 747   0,                                    /* static_pass_number */
 748   TV_DCE,                               /* tv_id */
 749   0,                                    /* properties_required */
 750   0,                                    /* properties_provided */
 751   0,                                    /* properties_destroyed */
 752   0,                                    /* todo_flags_start */
 753   TODO_dump_func |
 754   TODO_df_finish | TODO_verify_rtl_sharing |
 755   TODO_ggc_collect                     /* todo_flags_finish */
 756  }
 757 };
 758
 759
 760 /* -------------------------------------------------------------------------
 761    Fast DCE functions
 762    ------------------------------------------------------------------------- */
 763
 764 /* Process basic block BB.  Return true if the live_in set has
 765    changed. REDO_OUT is true if the info at the bottom of the block
 766    needs to be recalculated before starting.  AU is the proper set of
 767    artificial uses. */
 768
 769 static bool
 770 byte_dce_process_block (basic_block bb, bool redo_out, bitmap au)
 771 {
 772   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
 773   rtx insn;
 774   bool block_changed;
 775   df_ref *def_rec;
 776
 777   if (redo_out)
 778     {
 779       /* Need to redo the live_out set of this block if when one of
 780          the succs of this block has had a change in it live in
 781          set.  */
 782       edge e;
 783       edge_iterator ei;
 784       df_confluence_function_n con_fun_n = df_byte_lr->problem->con_fun_n;
 785       bitmap_clear (DF_BYTE_LR_OUT (bb));
 786       FOR_EACH_EDGE (e, ei, bb->succs)
 787         (*con_fun_n) (e);
 788     }
 789
 790   if (dump_file)
 791     {
 792       fprintf (dump_file, "processing block %d live out = ", bb->index);
 793       df_print_byte_regset (dump_file, DF_BYTE_LR_OUT (bb));
 794     }
 795
 796   bitmap_copy (local_live, DF_BYTE_LR_OUT (bb));
 797
 798   df_byte_lr_simulate_artificial_refs_at_end (bb, local_live);
 799
 800   FOR_BB_INSNS_REVERSE (bb, insn)
 801     if (INSN_P (insn))
 802       {
 803         /* The insn is needed if there is someone who uses the output.  */
 804         for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 805           {
 806             df_ref def = *def_rec;
 807             unsigned int last;
 808             unsigned int dregno = DF_REF_REGNO (def);
 809             unsigned int start = df_byte_lr_get_regno_start (dregno);
 810             unsigned int len = df_byte_lr_get_regno_len (dregno);
 811
 812             unsigned int sb;
 813             unsigned int lb;
 814             /* This is one of the only places where DF_MM_MAY should
 815                be used for defs.  Need to make sure that we are
 816                checking for all of the bits that may be used.  */
 817
 818             if (!df_compute_accessed_bytes (def, DF_MM_MAY, &sb, &lb))
 819               {
 820                 start += sb;
 821                 len = lb - sb;
 822               }
 823
 824             if (bitmap_bit_p (au, dregno))
 825               {
 826                 mark_insn (insn, true);
 827                 goto quickexit;
 828               }
 829
 830             last = start + len;
 831             while (start < last)
 832               if (bitmap_bit_p (local_live, start++))
 833                 {
 834                   mark_insn (insn, true);
 835                   goto quickexit;
 836                 }
 837           }
 838
 839       quickexit:
 840
 841         /* No matter if the instruction is needed or not, we remove
 842            any regno in the defs from the live set.  */
 843         df_byte_lr_simulate_defs (insn, local_live);
 844
 845         /* On the other hand, we do not allow the dead uses to set
 846            anything in local_live.  */
 847         if (marked_insn_p (insn))
 848           df_byte_lr_simulate_uses (insn, local_live);
 849
 850         if (dump_file)
 851           {
 852             fprintf (dump_file, "finished processing insn %d live out = ",
 853                      INSN_UID (insn));
 854             df_print_byte_regset (dump_file, local_live);
 855           }
 856       }
 857
 858   df_byte_lr_simulate_artificial_refs_at_top (bb, local_live);
 859
 860   block_changed = !bitmap_equal_p (local_live, DF_BYTE_LR_IN (bb));
 861   if (block_changed)
 862     bitmap_copy (DF_BYTE_LR_IN (bb), local_live);
 863   BITMAP_FREE (local_live);
 864   return block_changed;
 865 }
 866
 867
 868 /* Process basic block BB.  Return true if the live_in set has
 869    changed. REDO_OUT is true if the info at the bottom of the block
 870    needs to be recalculated before starting.  AU is the proper set of
 871    artificial uses. */
 872
 873 static bool
 874 dce_process_block (basic_block bb, bool redo_out, bitmap au)
 875 {
 876   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
 877   rtx insn;
 878   bool block_changed;
 879   df_ref *def_rec;
 880
 881   if (redo_out)
 882     {
 883       /* Need to redo the live_out set of this block if when one of
 884          the succs of this block has had a change in it live in
 885          set.  */
 886       edge e;
 887       edge_iterator ei;
 888       df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
 889       bitmap_clear (DF_LR_OUT (bb));
 890       FOR_EACH_EDGE (e, ei, bb->succs)
 891         (*con_fun_n) (e);
 892     }
 893
 894   if (dump_file)
 895     {
 896       fprintf (dump_file, "processing block %d lr out = ", bb->index);
 897       df_print_regset (dump_file, DF_LR_OUT (bb));
 898     }
 899
 900   bitmap_copy (local_live, DF_LR_OUT (bb));
 901
 902   df_simulate_initialize_backwards (bb, local_live);
 903
 904   FOR_BB_INSNS_REVERSE (bb, insn)
 905     if (INSN_P (insn))
 906       {
 907         bool needed = false;
 908
 909         /* The insn is needed if there is someone who uses the output.  */
 910         for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 911           if (bitmap_bit_p (local_live, DF_REF_REGNO (*def_rec))
 912               || bitmap_bit_p (au, DF_REF_REGNO (*def_rec)))
 913             {
 914               needed = true;
 915               break;
 916             }
 917
 918         if (needed)
 919           mark_insn (insn, true);
 920
 921         /* No matter if the instruction is needed or not, we remove
 922            any regno in the defs from the live set.  */
 923         df_simulate_defs (insn, local_live);
 924
 925         /* On the other hand, we do not allow the dead uses to set
 926            anything in local_live.  */
 927         if (marked_insn_p (insn))
 928           df_simulate_uses (insn, local_live);
 929       }
 930
 931   df_simulate_finalize_backwards (bb, local_live);
 932
 933   block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
 934   if (block_changed)
 935     bitmap_copy (DF_LR_IN (bb), local_live);
 936
 937   BITMAP_FREE (local_live);
 938   return block_changed;
 939 }
 940
 941
 942 /* Perform fast DCE once initialization is done.  If BYTE_LEVEL is
 943    true, use the byte level dce, otherwise do it at the pseudo
 944    level.  */
 945
 946 static void
 947 fast_dce (bool byte_level)
 948 {
 949   int *postorder = df_get_postorder (DF_BACKWARD);
 950   int n_blocks = df_get_n_blocks (DF_BACKWARD);
 951   /* The set of blocks that have been seen on this iteration.  */
 952   bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 953   /* The set of blocks that need to have the out vectors reset because
 954      the in of one of their successors has changed.  */
 955   bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 956   bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 957   bool global_changed = true;
 958
 959   /* These regs are considered always live so if they end up dying
 960      because of some def, we need to bring the back again.  Calling
 961      df_simulate_fixup_sets has the disadvantage of calling
 962      bb_has_eh_pred once per insn, so we cache the information
 963      here.  */
 964   bitmap au = df->regular_block_artificial_uses;
 965   bitmap au_eh = df->eh_block_artificial_uses;
 966   int i;
 967
 968   prescan_insns_for_dce (true);
 969
 970   for (i = 0; i < n_blocks; i++)
 971     bitmap_set_bit (all_blocks, postorder[i]);
 972
 973   while (global_changed)
 974     {
 975       global_changed = false;
 976
 977       for (i = 0; i < n_blocks; i++)
 978         {
 979           int index = postorder[i];
 980           basic_block bb = BASIC_BLOCK (index);
 981           bool local_changed;
 982
 983           if (index < NUM_FIXED_BLOCKS)
 984             {
 985               bitmap_set_bit (processed, index);
 986               continue;
 987             }
 988
 989           if (byte_level)
 990             local_changed
 991               = byte_dce_process_block (bb, bitmap_bit_p (redo_out, index),
 992                                           bb_has_eh_pred (bb) ? au_eh : au);
 993           else
 994             local_changed
 995               = dce_process_block (bb, bitmap_bit_p (redo_out, index),
 996                                    bb_has_eh_pred (bb) ? au_eh : au);
 997           bitmap_set_bit (processed, index);
 998
 999           if (local_changed)
1000             {
1001               edge e;
1002               edge_iterator ei;
1003               FOR_EACH_EDGE (e, ei, bb->preds)
1004                 if (bitmap_bit_p (processed, e->src->index))
1005                   /* Be tricky about when we need to iterate the
1006                      analysis.  We only have redo the analysis if the
1007                      bitmaps change at the top of a block that is the
1008                      entry to a loop.  */
1009                   global_changed = true;
1010                 else
1011                   bitmap_set_bit (redo_out, e->src->index);
1012             }
1013         }
1014
1015       if (global_changed)
1016         {
1017           /* Turn off the RUN_DCE flag to prevent recursive calls to
1018              dce.  */
1019           int old_flag = df_clear_flags (DF_LR_RUN_DCE);
1020
1021           /* So something was deleted that requires a redo.  Do it on
1022              the cheap.  */
1023           delete_unmarked_insns ();
1024           sbitmap_zero (marked);
1025           bitmap_clear (processed);
1026           bitmap_clear (redo_out);
1027
1028           /* We do not need to rescan any instructions.  We only need
1029              to redo the dataflow equations for the blocks that had a
1030              change at the top of the block.  Then we need to redo the
1031              iteration.  */
1032           if (byte_level)
1033             df_analyze_problem (df_byte_lr, all_blocks, postorder, n_blocks);
1034           else
1035             df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
1036
1037           if (old_flag & DF_LR_RUN_DCE)
1038             df_set_flags (DF_LR_RUN_DCE);
1039
1040           prescan_insns_for_dce (true);
1041         }
1042     }
1043
1044   delete_unmarked_insns ();
1045
1046   BITMAP_FREE (processed);
1047   BITMAP_FREE (redo_out);
1048   BITMAP_FREE (all_blocks);
1049 }
1050
1051
1052 /* Fast register level DCE.  */
1053
1054 static unsigned int
1055 rest_of_handle_fast_dce (void)
1056 {
1057   init_dce (true);
1058   fast_dce (false);
1059   fini_dce (true);
1060   return 0;
1061 }
1062
1063
1064 /* Fast byte level DCE.  */
1065
1066 static unsigned int
1067 rest_of_handle_fast_byte_dce (void)
1068 {
1069   df_byte_lr_add_problem ();
1070   init_dce (true);
1071   fast_dce (true);
1072   fini_dce (true);
1073   return 0;
1074 }
1075
1076
1077 /* This is an internal call that is used by the df live register
1078    problem to run fast dce as a side effect of creating the live
1079    information.  The stack is organized so that the lr problem is run,
1080    this pass is run, which updates the live info and the df scanning
1081    info, and then returns to allow the rest of the problems to be run.
1082
1083    This can be called by elsewhere but it will not update the bit
1084    vectors for any other problems than LR.  */
1085
1086 void
1087 run_fast_df_dce (void)
1088 {
1089   if (flag_dce)
1090     {
1091       /* If dce is able to delete something, it has to happen
1092          immediately.  Otherwise there will be problems handling the
1093          eq_notes.  */
1094       int old_flags =
1095         df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
1096
1097       df_in_progress = true;
1098       rest_of_handle_fast_dce ();
1099       df_in_progress = false;
1100
1101       df_set_flags (old_flags);
1102     }
1103 }
1104
1105
1106 /* Run a fast DCE pass.  */
1107
1108 void
1109 run_fast_dce (void)
1110 {
1111   if (flag_dce)
1112     rest_of_handle_fast_dce ();
1113 }
1114
1115
1116 static bool
1117 gate_fast_dce (void)
1118 {
1119   return optimize > 0 && flag_dce
1120     && dbg_cnt (dce_fast);
1121 }
1122
1123 struct rtl_opt_pass pass_fast_rtl_dce =
1124 {
1125  {
1126   RTL_PASS,
1127   "dce",                                /* name */
1128   gate_fast_dce,                        /* gate */
1129   rest_of_handle_fast_dce,              /* execute */
1130   NULL,                                 /* sub */
1131   NULL,                                 /* next */
1132   0,                                    /* static_pass_number */
1133   TV_DCE,                               /* tv_id */
1134   0,                                    /* properties_required */
1135   0,                                    /* properties_provided */
1136   0,                                    /* properties_destroyed */
1137   0,                                    /* todo_flags_start */
1138   TODO_dump_func |
1139   TODO_df_finish | TODO_verify_rtl_sharing |
1140   TODO_ggc_collect                      /* todo_flags_finish */
1141  }
1142 };
1143
1144 struct rtl_opt_pass pass_fast_rtl_byte_dce =
1145 {
1146  {
1147   RTL_PASS,
1148   "byte-dce",                           /* name */
1149   gate_fast_dce,                        /* gate */
1150   rest_of_handle_fast_byte_dce,         /* execute */
1151   NULL,                                 /* sub */
1152   NULL,                                 /* next */
1153   0,                                    /* static_pass_number */
1154   TV_DCE,                               /* tv_id */
1155   0,                                    /* properties_required */
1156   0,                                    /* properties_provided */
1157   0,                                    /* properties_destroyed */
1158   0,                                    /* todo_flags_start */
1159   TODO_dump_func |
1160   TODO_df_finish | TODO_verify_rtl_sharing |
1161   TODO_ggc_collect                      /* todo_flags_finish */
1162  }
1163 };