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 #include "emit-rtl.h"  /* FIXME: Can go away once crtl is moved to rtl.h.  */
  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 static bool find_call_stack_args (rtx, bool, bool, bitmap);
  61
  62 /* A subroutine for which BODY is part of the instruction being tested;
  63    either the top-level pattern, or an element of a PARALLEL.  The
  64    instruction is known not to be a bare USE or CLOBBER.  */
  65
  66 static bool
  67 deletable_insn_p_1 (rtx body)
  68 {
  69   switch (GET_CODE (body))
  70     {
  71     case PREFETCH:
  72     case TRAP_IF:
  73       /* The UNSPEC case was added here because the ia-64 claims that
  74          USEs do not work after reload and generates UNSPECS rather
  75          than USEs.  Since dce is run after reload we need to avoid
  76          deleting these even if they are dead.  If it turns out that
  77          USEs really do work after reload, the ia-64 should be
  78          changed, and the UNSPEC case can be removed.  */
  79     case UNSPEC:
  80       return false;
  81
  82     default:
  83       return !volatile_refs_p (body);
  84     }
  85 }
  86
  87
  88 /* Return true if INSN is a normal instruction that can be deleted by
  89    the DCE pass.  */
  90
  91 static bool
  92 deletable_insn_p (rtx insn, bool fast, bitmap arg_stores)
  93 {
  94   rtx body, x;
  95   int i;
  96
  97   if (CALL_P (insn)
  98       /* We cannot delete calls inside of the recursive dce because
  99          this may cause basic blocks to be deleted and this messes up
 100          the rest of the stack of optimization passes.  */
 101       && (!df_in_progress)
 102       /* We cannot delete pure or const sibling calls because it is
 103          hard to see the result.  */
 104       && (!SIBLING_CALL_P (insn))
 105       /* We can delete dead const or pure calls as long as they do not
 106          infinite loop.  */
 107       && (RTL_CONST_OR_PURE_CALL_P (insn)
 108           && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))
 109     return find_call_stack_args (insn, false, fast, arg_stores);
 110
 111   /* Don't delete jumps, notes and the like.  */
 112   if (!NONJUMP_INSN_P (insn))
 113     return false;
 114
 115   /* Don't delete insns that can throw.  */
 116   if (!insn_nothrow_p (insn))
 117     return false;
 118
 119   body = PATTERN (insn);
 120   switch (GET_CODE (body))
 121     {
 122     case USE:
 123     case VAR_LOCATION:
 124       return false;
 125
 126     case CLOBBER:
 127       if (fast)
 128         {
 129           /* A CLOBBER of a dead pseudo register serves no purpose.
 130              That is not necessarily true for hard registers until
 131              after reload.  */
 132           x = XEXP (body, 0);
 133           return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);
 134         }
 135       else
 136         /* Because of the way that use-def chains are built, it is not
 137            possible to tell if the clobber is dead because it can
 138            never be the target of a use-def chain.  */
 139         return false;
 140
 141     case PARALLEL:
 142       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 143         if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))
 144           return false;
 145       return true;
 146
 147     default:
 148       return deletable_insn_p_1 (body);
 149     }
 150 }
 151
 152
 153 /* Return true if INSN has been marked as needed.  */
 154
 155 static inline int
 156 marked_insn_p (rtx insn)
 157 {
 158   /* Artificial defs are always needed and they do not have an insn.
 159      We should never see them here.  */
 160   gcc_assert (insn);
 161   return TEST_BIT (marked, INSN_UID (insn));
 162 }
 163
 164
 165 /* If INSN has not yet been marked as needed, mark it now, and add it to
 166    the worklist.  */
 167
 168 static void
 169 mark_insn (rtx insn, bool fast)
 170 {
 171   if (!marked_insn_p (insn))
 172     {
 173       if (!fast)
 174         VEC_safe_push (rtx, heap, worklist, insn);
 175       SET_BIT (marked, INSN_UID (insn));
 176       if (dump_file)
 177         fprintf (dump_file, "  Adding insn %d to worklist\n", INSN_UID (insn));
 178       if (CALL_P (insn)
 179           && !df_in_progress
 180           && !SIBLING_CALL_P (insn)
 181           && (RTL_CONST_OR_PURE_CALL_P (insn)
 182               && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))
 183         find_call_stack_args (insn, true, fast, NULL);
 184     }
 185 }
 186
 187
 188 /* A note_stores callback used by mark_nonreg_stores.  DATA is the
 189    instruction containing DEST.  */
 190
 191 static void
 192 mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data)
 193 {
 194   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
 195     mark_insn ((rtx) data, true);
 196 }
 197
 198
 199 /* A note_stores callback used by mark_nonreg_stores.  DATA is the
 200    instruction containing DEST.  */
 201
 202 static void
 203 mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)
 204 {
 205   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
 206     mark_insn ((rtx) data, false);
 207 }
 208
 209
 210 /* Mark INSN if BODY stores to a non-register destination.  */
 211
 212 static void
 213 mark_nonreg_stores (rtx body, rtx insn, bool fast)
 214 {
 215   if (fast)
 216     note_stores (body, mark_nonreg_stores_1, insn);
 217   else
 218     note_stores (body, mark_nonreg_stores_2, insn);
 219 }
 220
 221
 222 /* Try to find all stack stores of CALL_INSN arguments if
 223    ACCUMULATE_OUTGOING_ARGS.  If all stack stores have been found
 224    and it is therefore safe to eliminate the call, return true,
 225    otherwise return false.  This function should be first called
 226    with DO_MARK false, and only when the CALL_INSN is actually
 227    going to be marked called again with DO_MARK true.  */
 228
 229 static bool
 230 find_call_stack_args (rtx call_insn, bool do_mark, bool fast,
 231                       bitmap arg_stores)
 232 {
 233   rtx p, insn, prev_insn;
 234   bool ret;
 235   HOST_WIDE_INT min_sp_off, max_sp_off;
 236   bitmap sp_bytes;
 237
 238   gcc_assert (CALL_P (call_insn));
 239   if (!ACCUMULATE_OUTGOING_ARGS)
 240     return true;
 241
 242   if (!do_mark)
 243     {
 244       gcc_assert (arg_stores);
 245       bitmap_clear (arg_stores);
 246     }
 247
 248   min_sp_off = INTTYPE_MAXIMUM (HOST_WIDE_INT);
 249   max_sp_off = 0;
 250
 251   /* First determine the minimum and maximum offset from sp for
 252      stored arguments.  */
 253   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
 254     if (GET_CODE (XEXP (p, 0)) == USE
 255         && MEM_P (XEXP (XEXP (p, 0), 0)))
 256       {
 257         rtx mem = XEXP (XEXP (p, 0), 0), addr, size;
 258         HOST_WIDE_INT off = 0;
 259         size = MEM_SIZE (mem);
 260         if (size == NULL_RTX)
 261           return false;
 262         addr = XEXP (mem, 0);
 263         if (GET_CODE (addr) == PLUS
 264             && REG_P (XEXP (addr, 0))
 265             && CONST_INT_P (XEXP (addr, 1)))
 266           {
 267             off = INTVAL (XEXP (addr, 1));
 268             addr = XEXP (addr, 0);
 269           }
 270         if (addr != stack_pointer_rtx)
 271           {
 272             if (!REG_P (addr))
 273               return false;
 274             /* If not fast, use chains to see if addr wasn't set to
 275                sp + offset.  */
 276             if (!fast)
 277               {
 278                 df_ref *use_rec;
 279                 struct df_link *defs;
 280                 rtx set;
 281
 282                 for (use_rec = DF_INSN_USES (call_insn); *use_rec; use_rec++)
 283                   if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))
 284                     break;
 285
 286                 if (*use_rec == NULL)
 287                   return false;
 288
 289                 for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 290                   if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 291                     break;
 292
 293                 if (defs == NULL)
 294                   return false;
 295
 296                 set = single_set (DF_REF_INSN (defs->ref));
 297                 if (!set)
 298                   return false;
 299
 300                 if (GET_CODE (SET_SRC (set)) != PLUS
 301                     || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
 302                     || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
 303                   return false;
 304
 305                 off += INTVAL (XEXP (SET_SRC (set), 1));
 306               }
 307             else
 308               return false;
 309           }
 310         min_sp_off = MIN (min_sp_off, off);
 311         max_sp_off = MAX (max_sp_off, off + INTVAL (size));
 312       }
 313
 314   if (min_sp_off >= max_sp_off)
 315     return true;
 316   sp_bytes = BITMAP_ALLOC (NULL);
 317
 318   /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
 319      which contain arguments.  Checking has been done in the previous
 320      loop.  */
 321   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
 322     if (GET_CODE (XEXP (p, 0)) == USE
 323         && MEM_P (XEXP (XEXP (p, 0), 0)))
 324       {
 325         rtx mem = XEXP (XEXP (p, 0), 0), addr;
 326         HOST_WIDE_INT off = 0, byte;
 327         addr = XEXP (mem, 0);
 328         if (GET_CODE (addr) == PLUS
 329             && REG_P (XEXP (addr, 0))
 330             && CONST_INT_P (XEXP (addr, 1)))
 331           {
 332             off = INTVAL (XEXP (addr, 1));
 333             addr = XEXP (addr, 0);
 334           }
 335         if (addr != stack_pointer_rtx)
 336           {
 337             df_ref *use_rec;
 338             struct df_link *defs;
 339             rtx set;
 340
 341             for (use_rec = DF_INSN_USES (call_insn); *use_rec; use_rec++)
 342               if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))
 343                 break;
 344
 345             for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 346               if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 347                 break;
 348
 349             set = single_set (DF_REF_INSN (defs->ref));
 350             off += INTVAL (XEXP (SET_SRC (set), 1));
 351           }
 352         for (byte = off; byte < off + INTVAL (MEM_SIZE (mem)); byte++)
 353           {
 354             if (!bitmap_set_bit (sp_bytes, byte - min_sp_off))
 355               gcc_unreachable ();
 356           }
 357       }
 358
 359   /* Walk backwards, looking for argument stores.  The search stops
 360      when seeing another call, sp adjustment or memory store other than
 361      argument store.  */
 362   ret = false;
 363   for (insn = PREV_INSN (call_insn); insn; insn = prev_insn)
 364     {
 365       rtx set, mem, addr;
 366       HOST_WIDE_INT off, byte;
 367
 368       if (insn == BB_HEAD (BLOCK_FOR_INSN (call_insn)))
 369         prev_insn = NULL_RTX;
 370       else
 371         prev_insn = PREV_INSN (insn);
 372
 373       if (CALL_P (insn))
 374         break;
 375
 376       if (!INSN_P (insn))
 377         continue;
 378
 379       set = single_set (insn);
 380       if (!set || SET_DEST (set) == stack_pointer_rtx)
 381         break;
 382
 383       if (!MEM_P (SET_DEST (set)))
 384         continue;
 385
 386       mem = SET_DEST (set);
 387       addr = XEXP (mem, 0);
 388       off = 0;
 389       if (GET_CODE (addr) == PLUS
 390           && REG_P (XEXP (addr, 0))
 391           && CONST_INT_P (XEXP (addr, 1)))
 392         {
 393           off = INTVAL (XEXP (addr, 1));
 394           addr = XEXP (addr, 0);
 395         }
 396       if (addr != stack_pointer_rtx)
 397         {
 398           if (!REG_P (addr))
 399             break;
 400           if (!fast)
 401             {
 402               df_ref *use_rec;
 403               struct df_link *defs;
 404               rtx set;
 405
 406               for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
 407                 if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))
 408                   break;
 409
 410               if (*use_rec == NULL)
 411                 break;
 412
 413               for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 414                 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 415                   break;
 416
 417               if (defs == NULL)
 418                 break;
 419
 420               set = single_set (DF_REF_INSN (defs->ref));
 421               if (!set)
 422                 break;
 423
 424               if (GET_CODE (SET_SRC (set)) != PLUS
 425                   || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
 426                   || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
 427                 break;
 428
 429               off += INTVAL (XEXP (SET_SRC (set), 1));
 430             }
 431           else
 432             break;
 433         }
 434
 435       if (GET_MODE_SIZE (GET_MODE (mem)) == 0)
 436         break;
 437
 438       for (byte = off; byte < off + GET_MODE_SIZE (GET_MODE (mem)); byte++)
 439         {
 440           if (byte < min_sp_off
 441               || byte >= max_sp_off
 442               || !bitmap_clear_bit (sp_bytes, byte - min_sp_off))
 443             break;
 444         }
 445
 446       if (!deletable_insn_p (insn, fast, NULL))
 447         break;
 448
 449       if (do_mark)
 450         mark_insn (insn, fast);
 451       else
 452         bitmap_set_bit (arg_stores, INSN_UID (insn));
 453
 454       if (bitmap_empty_p (sp_bytes))
 455         {
 456           ret = true;
 457           break;
 458         }
 459     }
 460
 461   BITMAP_FREE (sp_bytes);
 462   if (!ret && arg_stores)
 463     bitmap_clear (arg_stores);
 464
 465   return ret;
 466 }
 467
 468
 469 /* Delete all REG_EQUAL notes of the registers INSN writes, to prevent
 470    bad dangling REG_EQUAL notes. */
 471
 472 static void
 473 delete_corresponding_reg_eq_notes (rtx insn)
 474 {
 475   df_ref *def_rec;
 476   for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 477     {
 478       df_ref def = *def_rec;
 479       unsigned int regno = DF_REF_REGNO (def);
 480       /* This loop is a little tricky.  We cannot just go down the
 481          chain because it is being modified by the actions in the
 482          loop.  So we just get the head.  We plan to drain the list
 483          anyway.  */
 484       while (DF_REG_EQ_USE_CHAIN (regno))
 485         {
 486           df_ref eq_use = DF_REG_EQ_USE_CHAIN (regno);
 487           rtx noted_insn = DF_REF_INSN (eq_use);
 488           rtx note = find_reg_note (noted_insn, REG_EQUAL, NULL_RTX);
 489           if (!note)
 490             note = find_reg_note (noted_insn, REG_EQUIV, NULL_RTX);
 491
 492           /* This assert is generally triggered when someone deletes a
 493              REG_EQUAL or REG_EQUIV note by hacking the list manually
 494              rather than calling remove_note.  */
 495           gcc_assert (note);
 496           remove_note (noted_insn, note);
 497         }
 498     }
 499 }
 500
 501
 502 /* Delete every instruction that hasn't been marked.  */
 503
 504 static void
 505 delete_unmarked_insns (void)
 506 {
 507   basic_block bb;
 508   rtx insn, next;
 509   bool must_clean = false;
 510
 511   FOR_EACH_BB_REVERSE (bb)
 512     FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
 513       if (INSN_P (insn))
 514         {
 515           /* Always delete no-op moves.  */
 516           if (noop_move_p (insn))
 517             ;
 518
 519           /* Otherwise rely only on the DCE algorithm.  */
 520           else if (marked_insn_p (insn))
 521             continue;
 522
 523           /* Beware that reaching a dbg counter limit here can result
 524              in miscompiled file.  This occurs when a group of insns
 525              must be deleted together, typically because the kept insn
 526              depends on the output from the deleted insn.  Deleting
 527              this insns in reverse order (both at the bb level and
 528              when looking at the blocks) minimizes this, but does not
 529              eliminate it, since it is possible for the using insn to
 530              be top of a block and the producer to be at the bottom of
 531              the block.  However, in most cases this will only result
 532              in an uninitialized use of an insn that is dead anyway.
 533
 534              However, there is one rare case that will cause a
 535              miscompile: deletion of non-looping pure and constant
 536              calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
 537              In this case it is possible to remove the call, but leave
 538              the argument pushes to the stack.  Because of the changes
 539              to the stack pointer, this will almost always lead to a
 540              miscompile.  */
 541           if (!dbg_cnt (dce))
 542             continue;
 543
 544           if (dump_file)
 545             fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
 546
 547           /* Before we delete the insn we have to delete REG_EQUAL notes
 548              for the destination regs in order to avoid dangling notes.  */
 549           delete_corresponding_reg_eq_notes (insn);
 550
 551           /* If a pure or const call is deleted, this may make the cfg
 552              have unreachable blocks.  We rememeber this and call
 553              delete_unreachable_blocks at the end.  */
 554           if (CALL_P (insn))
 555             must_clean = true;
 556
 557           /* Now delete the insn.  */
 558           delete_insn_and_edges (insn);
 559         }
 560
 561   /* Deleted a pure or const call.  */
 562   if (must_clean)
 563     delete_unreachable_blocks ();
 564 }
 565
 566
 567 /* Go through the instructions and mark those whose necessity is not
 568    dependent on inter-instruction information.  Make sure all other
 569    instructions are not marked.  */
 570
 571 static void
 572 prescan_insns_for_dce (bool fast)
 573 {
 574   basic_block bb;
 575   rtx insn, prev;
 576   bitmap arg_stores = NULL;
 577
 578   if (dump_file)
 579     fprintf (dump_file, "Finding needed instructions:\n");
 580
 581   if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS)
 582     arg_stores = BITMAP_ALLOC (NULL);
 583
 584   FOR_EACH_BB (bb)
 585     {
 586       FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)
 587         if (INSN_P (insn))
 588           {
 589             /* Don't mark argument stores now.  They will be marked
 590                if needed when the associated CALL is marked.  */
 591             if (arg_stores && bitmap_bit_p (arg_stores, INSN_UID (insn)))
 592               continue;
 593             if (deletable_insn_p (insn, fast, arg_stores))
 594               mark_nonreg_stores (PATTERN (insn), insn, fast);
 595             else
 596               mark_insn (insn, fast);
 597           }
 598       /* find_call_stack_args only looks at argument stores in the
 599          same bb.  */
 600       if (arg_stores)
 601         bitmap_clear (arg_stores);
 602     }
 603
 604   if (arg_stores)
 605     BITMAP_FREE (arg_stores);
 606
 607   if (dump_file)
 608     fprintf (dump_file, "Finished finding needed instructions:\n");
 609 }
 610
 611
 612 /* UD-based DSE routines. */
 613
 614 /* Mark instructions that define artificially-used registers, such as
 615    the frame pointer and the stack pointer.  */
 616
 617 static void
 618 mark_artificial_uses (void)
 619 {
 620   basic_block bb;
 621   struct df_link *defs;
 622   df_ref *use_rec;
 623
 624   FOR_ALL_BB (bb)
 625     {
 626       for (use_rec = df_get_artificial_uses (bb->index);
 627            *use_rec; use_rec++)
 628         for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 629           if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 630             mark_insn (DF_REF_INSN (defs->ref), false);
 631     }
 632 }
 633
 634
 635 /* Mark every instruction that defines a register value that INSN uses.  */
 636
 637 static void
 638 mark_reg_dependencies (rtx insn)
 639 {
 640   struct df_link *defs;
 641   df_ref *use_rec;
 642
 643   if (DEBUG_INSN_P (insn))
 644     return;
 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   "ud 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 = marked_insn_p (insn);
 908
 909         /* The insn is needed if there is someone who uses the output.  */
 910         if (!needed)
 911           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 912             if (bitmap_bit_p (local_live, DF_REF_REGNO (*def_rec))
 913                 || bitmap_bit_p (au, DF_REF_REGNO (*def_rec)))
 914               {
 915                 needed = true;
 916                 mark_insn (insn, true);
 917                 break;
 918               }
 919
 920         /* No matter if the instruction is needed or not, we remove
 921            any regno in the defs from the live set.  */
 922         df_simulate_defs (insn, local_live);
 923
 924         /* On the other hand, we do not allow the dead uses to set
 925            anything in local_live.  */
 926         if (needed)
 927           df_simulate_uses (insn, local_live);
 928       }
 929
 930   df_simulate_finalize_backwards (bb, local_live);
 931
 932   block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
 933   if (block_changed)
 934     bitmap_copy (DF_LR_IN (bb), local_live);
 935
 936   BITMAP_FREE (local_live);
 937   return block_changed;
 938 }
 939
 940
 941 /* Perform fast DCE once initialization is done.  If BYTE_LEVEL is
 942    true, use the byte level dce, otherwise do it at the pseudo
 943    level.  */
 944
 945 static void
 946 fast_dce (bool byte_level)
 947 {
 948   int *postorder = df_get_postorder (DF_BACKWARD);
 949   int n_blocks = df_get_n_blocks (DF_BACKWARD);
 950   /* The set of blocks that have been seen on this iteration.  */
 951   bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 952   /* The set of blocks that need to have the out vectors reset because
 953      the in of one of their successors has changed.  */
 954   bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 955   bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 956   bool global_changed = true;
 957
 958   /* These regs are considered always live so if they end up dying
 959      because of some def, we need to bring the back again.  Calling
 960      df_simulate_fixup_sets has the disadvantage of calling
 961      bb_has_eh_pred once per insn, so we cache the information
 962      here.  */
 963   bitmap au = &df->regular_block_artificial_uses;
 964   bitmap au_eh = &df->eh_block_artificial_uses;
 965   int i;
 966
 967   prescan_insns_for_dce (true);
 968
 969   for (i = 0; i < n_blocks; i++)
 970     bitmap_set_bit (all_blocks, postorder[i]);
 971
 972   while (global_changed)
 973     {
 974       global_changed = false;
 975
 976       for (i = 0; i < n_blocks; i++)
 977         {
 978           int index = postorder[i];
 979           basic_block bb = BASIC_BLOCK (index);
 980           bool local_changed;
 981
 982           if (index < NUM_FIXED_BLOCKS)
 983             {
 984               bitmap_set_bit (processed, index);
 985               continue;
 986             }
 987
 988           if (byte_level)
 989             local_changed
 990               = byte_dce_process_block (bb, bitmap_bit_p (redo_out, index),
 991                                           bb_has_eh_pred (bb) ? au_eh : au);
 992           else
 993             local_changed
 994               = dce_process_block (bb, bitmap_bit_p (redo_out, index),
 995                                    bb_has_eh_pred (bb) ? au_eh : au);
 996           bitmap_set_bit (processed, index);
 997
 998           if (local_changed)
 999             {
1000               edge e;
1001               edge_iterator ei;
1002               FOR_EACH_EDGE (e, ei, bb->preds)
1003                 if (bitmap_bit_p (processed, e->src->index))
1004                   /* Be tricky about when we need to iterate the
1005                      analysis.  We only have redo the analysis if the
1006                      bitmaps change at the top of a block that is the
1007                      entry to a loop.  */
1008                   global_changed = true;
1009                 else
1010                   bitmap_set_bit (redo_out, e->src->index);
1011             }
1012         }
1013
1014       if (global_changed)
1015         {
1016           /* Turn off the RUN_DCE flag to prevent recursive calls to
1017              dce.  */
1018           int old_flag = df_clear_flags (DF_LR_RUN_DCE);
1019
1020           /* So something was deleted that requires a redo.  Do it on
1021              the cheap.  */
1022           delete_unmarked_insns ();
1023           sbitmap_zero (marked);
1024           bitmap_clear (processed);
1025           bitmap_clear (redo_out);
1026
1027           /* We do not need to rescan any instructions.  We only need
1028              to redo the dataflow equations for the blocks that had a
1029              change at the top of the block.  Then we need to redo the
1030              iteration.  */
1031           if (byte_level)
1032             df_analyze_problem (df_byte_lr, all_blocks, postorder, n_blocks);
1033           else
1034             df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
1035
1036           if (old_flag & DF_LR_RUN_DCE)
1037             df_set_flags (DF_LR_RUN_DCE);
1038
1039           prescan_insns_for_dce (true);
1040         }
1041     }
1042
1043   delete_unmarked_insns ();
1044
1045   BITMAP_FREE (processed);
1046   BITMAP_FREE (redo_out);
1047   BITMAP_FREE (all_blocks);
1048 }
1049
1050
1051 /* Fast register level DCE.  */
1052
1053 static unsigned int
1054 rest_of_handle_fast_dce (void)
1055 {
1056   init_dce (true);
1057   fast_dce (false);
1058   fini_dce (true);
1059   return 0;
1060 }
1061
1062
1063 /* Fast byte level DCE.  */
1064
1065 static unsigned int
1066 rest_of_handle_fast_byte_dce (void)
1067 {
1068   df_byte_lr_add_problem ();
1069   init_dce (true);
1070   fast_dce (true);
1071   fini_dce (true);
1072   return 0;
1073 }
1074
1075
1076 /* This is an internal call that is used by the df live register
1077    problem to run fast dce as a side effect of creating the live
1078    information.  The stack is organized so that the lr problem is run,
1079    this pass is run, which updates the live info and the df scanning
1080    info, and then returns to allow the rest of the problems to be run.
1081
1082    This can be called by elsewhere but it will not update the bit
1083    vectors for any other problems than LR.  */
1084
1085 void
1086 run_fast_df_dce (void)
1087 {
1088   if (flag_dce)
1089     {
1090       /* If dce is able to delete something, it has to happen
1091          immediately.  Otherwise there will be problems handling the
1092          eq_notes.  */
1093       int old_flags =
1094         df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
1095
1096       df_in_progress = true;
1097       rest_of_handle_fast_dce ();
1098       df_in_progress = false;
1099
1100       df_set_flags (old_flags);
1101     }
1102 }
1103
1104
1105 /* Run a fast DCE pass.  */
1106
1107 void
1108 run_fast_dce (void)
1109 {
1110   if (flag_dce)
1111     rest_of_handle_fast_dce ();
1112 }
1113
1114
1115 static bool
1116 gate_fast_dce (void)
1117 {
1118   return optimize > 0 && flag_dce
1119     && dbg_cnt (dce_fast);
1120 }
1121
1122 struct rtl_opt_pass pass_fast_rtl_dce =
1123 {
1124  {
1125   RTL_PASS,
1126   "rtl dce",                            /* name */
1127   gate_fast_dce,                        /* gate */
1128   rest_of_handle_fast_dce,              /* execute */
1129   NULL,                                 /* sub */
1130   NULL,                                 /* next */
1131   0,                                    /* static_pass_number */
1132   TV_DCE,                               /* tv_id */
1133   0,                                    /* properties_required */
1134   0,                                    /* properties_provided */
1135   0,                                    /* properties_destroyed */
1136   0,                                    /* todo_flags_start */
1137   TODO_dump_func |
1138   TODO_df_finish | TODO_verify_rtl_sharing |
1139   TODO_ggc_collect                      /* todo_flags_finish */
1140  }
1141 };
1142
1143 struct rtl_opt_pass pass_fast_rtl_byte_dce =
1144 {
1145  {
1146   RTL_PASS,
1147   "byte-dce",                           /* name */
1148   gate_fast_dce,                        /* gate */
1149   rest_of_handle_fast_byte_dce,         /* execute */
1150   NULL,                                 /* sub */
1151   NULL,                                 /* next */
1152   0,                                    /* static_pass_number */
1153   TV_DCE,                               /* tv_id */
1154   0,                                    /* properties_required */
1155   0,                                    /* properties_provided */
1156   0,                                    /* properties_destroyed */
1157   0,                                    /* todo_flags_start */
1158   TODO_dump_func |
1159   TODO_df_finish | TODO_verify_rtl_sharing |
1160   TODO_ggc_collect                      /* todo_flags_finish */
1161  }
1162 };