gcc/dce.c

   1 /* RTL dead code elimination.
   2    Copyright (C) 2005-2016 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 "backend.h"
  24 #include "rtl.h"
  25 #include "tree.h"
  26 #include "predict.h"
  27 #include "df.h"
  28 #include "tm_p.h"
  29 #include "emit-rtl.h"  /* FIXME: Can go away once crtl is moved to rtl.h.  */
  30 #include "cfgrtl.h"
  31 #include "cfgbuild.h"
  32 #include "cfgcleanup.h"
  33 #include "dce.h"
  34 #include "valtrack.h"
  35 #include "tree-pass.h"
  36 #include "dbgcnt.h"
  37
  38
  39 /* -------------------------------------------------------------------------
  40    Core mark/delete routines
  41    ------------------------------------------------------------------------- */
  42
  43 /* True if we are invoked while the df engine is running; in this case,
  44    we don't want to reenter it.  */
  45 static bool df_in_progress = false;
  46
  47 /* True if we are allowed to alter the CFG in this pass.  */
  48 static bool can_alter_cfg = false;
  49
  50 /* Instructions that have been marked but whose dependencies have not
  51    yet been processed.  */
  52 static vec<rtx_insn *> worklist;
  53
  54 /* Bitmap of instructions marked as needed indexed by INSN_UID.  */
  55 static sbitmap marked;
  56
  57 /* Bitmap obstacks used for block processing by the fast algorithm.  */
  58 static bitmap_obstack dce_blocks_bitmap_obstack;
  59 static bitmap_obstack dce_tmp_bitmap_obstack;
  60
  61 static bool find_call_stack_args (rtx_call_insn *, bool, bool, bitmap);
  62
  63 /* A subroutine for which BODY is part of the instruction being tested;
  64    either the top-level pattern, or an element of a PARALLEL.  The
  65    instruction is known not to be a bare USE or CLOBBER.  */
  66
  67 static bool
  68 deletable_insn_p_1 (rtx body)
  69 {
  70   switch (GET_CODE (body))
  71     {
  72     case PREFETCH:
  73     case TRAP_IF:
  74       /* The UNSPEC case was added here because the ia-64 claims that
  75          USEs do not work after reload and generates UNSPECS rather
  76          than USEs.  Since dce is run after reload we need to avoid
  77          deleting these even if they are dead.  If it turns out that
  78          USEs really do work after reload, the ia-64 should be
  79          changed, and the UNSPEC case can be removed.  */
  80     case UNSPEC:
  81       return false;
  82
  83     default:
  84       return !volatile_refs_p (body);
  85     }
  86 }
  87
  88
  89 /* Return true if INSN is a normal instruction that can be deleted by
  90    the DCE pass.  */
  91
  92 static bool
  93 deletable_insn_p (rtx_insn *insn, bool fast, bitmap arg_stores)
  94 {
  95   rtx body, x;
  96   int i;
  97   df_ref def;
  98
  99   if (CALL_P (insn)
 100       /* We cannot delete calls inside of the recursive dce because
 101          this may cause basic blocks to be deleted and this messes up
 102          the rest of the stack of optimization passes.  */
 103       && (!df_in_progress)
 104       /* We cannot delete pure or const sibling calls because it is
 105          hard to see the result.  */
 106       && (!SIBLING_CALL_P (insn))
 107       /* We can delete dead const or pure calls as long as they do not
 108          infinite loop.  */
 109       && (RTL_CONST_OR_PURE_CALL_P (insn)
 110           && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))
 111     return find_call_stack_args (as_a <rtx_call_insn *> (insn), false,
 112                                  fast, arg_stores);
 113
 114   /* Don't delete jumps, notes and the like.  */
 115   if (!NONJUMP_INSN_P (insn))
 116     return false;
 117
 118   /* Don't delete insns that may throw if we cannot do so.  */
 119   if (!(cfun->can_delete_dead_exceptions && can_alter_cfg)
 120       && !insn_nothrow_p (insn))
 121     return false;
 122
 123   /* If INSN sets a global_reg, leave it untouched.  */
 124   FOR_EACH_INSN_DEF (def, insn)
 125     if (HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
 126         && global_regs[DF_REF_REGNO (def)])
 127       return false;
 128     /* Initialization of pseudo PIC register should never be removed.  */
 129     else if (DF_REF_REG (def) == pic_offset_table_rtx
 130              && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
 131       return false;
 132
 133   body = PATTERN (insn);
 134   switch (GET_CODE (body))
 135     {
 136     case USE:
 137     case VAR_LOCATION:
 138       return false;
 139
 140     case CLOBBER:
 141       if (fast)
 142         {
 143           /* A CLOBBER of a dead pseudo register serves no purpose.
 144              That is not necessarily true for hard registers until
 145              after reload.  */
 146           x = XEXP (body, 0);
 147           return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);
 148         }
 149       else
 150         /* Because of the way that use-def chains are built, it is not
 151            possible to tell if the clobber is dead because it can
 152            never be the target of a use-def chain.  */
 153         return false;
 154
 155     case PARALLEL:
 156       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 157         if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))
 158           return false;
 159       return true;
 160
 161     default:
 162       return deletable_insn_p_1 (body);
 163     }
 164 }
 165
 166
 167 /* Return true if INSN has been marked as needed.  */
 168
 169 static inline int
 170 marked_insn_p (rtx_insn *insn)
 171 {
 172   /* Artificial defs are always needed and they do not have an insn.
 173      We should never see them here.  */
 174   gcc_assert (insn);
 175   return bitmap_bit_p (marked, INSN_UID (insn));
 176 }
 177
 178
 179 /* If INSN has not yet been marked as needed, mark it now, and add it to
 180    the worklist.  */
 181
 182 static void
 183 mark_insn (rtx_insn *insn, bool fast)
 184 {
 185   if (!marked_insn_p (insn))
 186     {
 187       if (!fast)
 188         worklist.safe_push (insn);
 189       bitmap_set_bit (marked, INSN_UID (insn));
 190       if (dump_file)
 191         fprintf (dump_file, "  Adding insn %d to worklist\n", INSN_UID (insn));
 192       if (CALL_P (insn)
 193           && !df_in_progress
 194           && !SIBLING_CALL_P (insn)
 195           && (RTL_CONST_OR_PURE_CALL_P (insn)
 196               && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))
 197         find_call_stack_args (as_a <rtx_call_insn *> (insn), true, fast, NULL);
 198     }
 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_1 (rtx dest, const_rtx pattern, void *data)
 207 {
 208   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
 209     mark_insn ((rtx_insn *) data, true);
 210 }
 211
 212
 213 /* A note_stores callback used by mark_nonreg_stores.  DATA is the
 214    instruction containing DEST.  */
 215
 216 static void
 217 mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)
 218 {
 219   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
 220     mark_insn ((rtx_insn *) data, false);
 221 }
 222
 223
 224 /* Mark INSN if BODY stores to a non-register destination.  */
 225
 226 static void
 227 mark_nonreg_stores (rtx body, rtx_insn *insn, bool fast)
 228 {
 229   if (fast)
 230     note_stores (body, mark_nonreg_stores_1, insn);
 231   else
 232     note_stores (body, mark_nonreg_stores_2, insn);
 233 }
 234
 235
 236 /* Return true if store to MEM, starting OFF bytes from stack pointer,
 237    is a call argument store, and clear corresponding bits from SP_BYTES
 238    bitmap if it is.  */
 239
 240 static bool
 241 check_argument_store (rtx mem, HOST_WIDE_INT off, HOST_WIDE_INT min_sp_off,
 242                       HOST_WIDE_INT max_sp_off, bitmap sp_bytes)
 243 {
 244   HOST_WIDE_INT byte;
 245   for (byte = off; byte < off + GET_MODE_SIZE (GET_MODE (mem)); byte++)
 246     {
 247       if (byte < min_sp_off
 248           || byte >= max_sp_off
 249           || !bitmap_clear_bit (sp_bytes, byte - min_sp_off))
 250         return false;
 251     }
 252   return true;
 253 }
 254
 255
 256 /* Try to find all stack stores of CALL_INSN arguments if
 257    ACCUMULATE_OUTGOING_ARGS.  If all stack stores have been found
 258    and it is therefore safe to eliminate the call, return true,
 259    otherwise return false.  This function should be first called
 260    with DO_MARK false, and only when the CALL_INSN is actually
 261    going to be marked called again with DO_MARK true.  */
 262
 263 static bool
 264 find_call_stack_args (rtx_call_insn *call_insn, bool do_mark, bool fast,
 265                       bitmap arg_stores)
 266 {
 267   rtx p;
 268   rtx_insn *insn, *prev_insn;
 269   bool ret;
 270   HOST_WIDE_INT min_sp_off, max_sp_off;
 271   bitmap sp_bytes;
 272
 273   gcc_assert (CALL_P (call_insn));
 274   if (!ACCUMULATE_OUTGOING_ARGS)
 275     return true;
 276
 277   if (!do_mark)
 278     {
 279       gcc_assert (arg_stores);
 280       bitmap_clear (arg_stores);
 281     }
 282
 283   min_sp_off = INTTYPE_MAXIMUM (HOST_WIDE_INT);
 284   max_sp_off = 0;
 285
 286   /* First determine the minimum and maximum offset from sp for
 287      stored arguments.  */
 288   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
 289     if (GET_CODE (XEXP (p, 0)) == USE
 290         && MEM_P (XEXP (XEXP (p, 0), 0)))
 291       {
 292         rtx mem = XEXP (XEXP (p, 0), 0), addr;
 293         HOST_WIDE_INT off = 0, size;
 294         if (!MEM_SIZE_KNOWN_P (mem))
 295           return false;
 296         size = MEM_SIZE (mem);
 297         addr = XEXP (mem, 0);
 298         if (GET_CODE (addr) == PLUS
 299             && REG_P (XEXP (addr, 0))
 300             && CONST_INT_P (XEXP (addr, 1)))
 301           {
 302             off = INTVAL (XEXP (addr, 1));
 303             addr = XEXP (addr, 0);
 304           }
 305         if (addr != stack_pointer_rtx)
 306           {
 307             if (!REG_P (addr))
 308               return false;
 309             /* If not fast, use chains to see if addr wasn't set to
 310                sp + offset.  */
 311             if (!fast)
 312               {
 313                 df_ref use;
 314                 struct df_link *defs;
 315                 rtx set;
 316
 317                 FOR_EACH_INSN_USE (use, call_insn)
 318                   if (rtx_equal_p (addr, DF_REF_REG (use)))
 319                     break;
 320
 321                 if (use == NULL)
 322                   return false;
 323
 324                 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
 325                   if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 326                     break;
 327
 328                 if (defs == NULL)
 329                   return false;
 330
 331                 set = single_set (DF_REF_INSN (defs->ref));
 332                 if (!set)
 333                   return false;
 334
 335                 if (GET_CODE (SET_SRC (set)) != PLUS
 336                     || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
 337                     || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
 338                   return false;
 339
 340                 off += INTVAL (XEXP (SET_SRC (set), 1));
 341               }
 342             else
 343               return false;
 344           }
 345         min_sp_off = MIN (min_sp_off, off);
 346         max_sp_off = MAX (max_sp_off, off + size);
 347       }
 348
 349   if (min_sp_off >= max_sp_off)
 350     return true;
 351   sp_bytes = BITMAP_ALLOC (NULL);
 352
 353   /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
 354      which contain arguments.  Checking has been done in the previous
 355      loop.  */
 356   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
 357     if (GET_CODE (XEXP (p, 0)) == USE
 358         && MEM_P (XEXP (XEXP (p, 0), 0)))
 359       {
 360         rtx mem = XEXP (XEXP (p, 0), 0), addr;
 361         HOST_WIDE_INT off = 0, byte;
 362         addr = XEXP (mem, 0);
 363         if (GET_CODE (addr) == PLUS
 364             && REG_P (XEXP (addr, 0))
 365             && CONST_INT_P (XEXP (addr, 1)))
 366           {
 367             off = INTVAL (XEXP (addr, 1));
 368             addr = XEXP (addr, 0);
 369           }
 370         if (addr != stack_pointer_rtx)
 371           {
 372             df_ref use;
 373             struct df_link *defs;
 374             rtx set;
 375
 376             FOR_EACH_INSN_USE (use, call_insn)
 377               if (rtx_equal_p (addr, DF_REF_REG (use)))
 378                 break;
 379
 380             for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
 381               if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 382                 break;
 383
 384             set = single_set (DF_REF_INSN (defs->ref));
 385             off += INTVAL (XEXP (SET_SRC (set), 1));
 386           }
 387         for (byte = off; byte < off + MEM_SIZE (mem); byte++)
 388           {
 389             if (!bitmap_set_bit (sp_bytes, byte - min_sp_off))
 390               gcc_unreachable ();
 391           }
 392       }
 393
 394   /* Walk backwards, looking for argument stores.  The search stops
 395      when seeing another call, sp adjustment or memory store other than
 396      argument store.  */
 397   ret = false;
 398   for (insn = PREV_INSN (call_insn); insn; insn = prev_insn)
 399     {
 400       rtx set, mem, addr;
 401       HOST_WIDE_INT off;
 402
 403       if (insn == BB_HEAD (BLOCK_FOR_INSN (call_insn)))
 404         prev_insn = NULL;
 405       else
 406         prev_insn = PREV_INSN (insn);
 407
 408       if (CALL_P (insn))
 409         break;
 410
 411       if (!NONDEBUG_INSN_P (insn))
 412         continue;
 413
 414       set = single_set (insn);
 415       if (!set || SET_DEST (set) == stack_pointer_rtx)
 416         break;
 417
 418       if (!MEM_P (SET_DEST (set)))
 419         continue;
 420
 421       mem = SET_DEST (set);
 422       addr = XEXP (mem, 0);
 423       off = 0;
 424       if (GET_CODE (addr) == PLUS
 425           && REG_P (XEXP (addr, 0))
 426           && CONST_INT_P (XEXP (addr, 1)))
 427         {
 428           off = INTVAL (XEXP (addr, 1));
 429           addr = XEXP (addr, 0);
 430         }
 431       if (addr != stack_pointer_rtx)
 432         {
 433           if (!REG_P (addr))
 434             break;
 435           if (!fast)
 436             {
 437               df_ref use;
 438               struct df_link *defs;
 439               rtx set;
 440
 441               FOR_EACH_INSN_USE (use, insn)
 442                 if (rtx_equal_p (addr, DF_REF_REG (use)))
 443                   break;
 444
 445               if (use == NULL)
 446                 break;
 447
 448               for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
 449                 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 450                   break;
 451
 452               if (defs == NULL)
 453                 break;
 454
 455               set = single_set (DF_REF_INSN (defs->ref));
 456               if (!set)
 457                 break;
 458
 459               if (GET_CODE (SET_SRC (set)) != PLUS
 460                   || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
 461                   || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
 462                 break;
 463
 464               off += INTVAL (XEXP (SET_SRC (set), 1));
 465             }
 466           else
 467             break;
 468         }
 469
 470       if (GET_MODE_SIZE (GET_MODE (mem)) == 0
 471           || !check_argument_store (mem, off, min_sp_off,
 472                                     max_sp_off, sp_bytes))
 473         break;
 474
 475       if (!deletable_insn_p (insn, fast, NULL))
 476         break;
 477
 478       if (do_mark)
 479         mark_insn (insn, fast);
 480       else
 481         bitmap_set_bit (arg_stores, INSN_UID (insn));
 482
 483       if (bitmap_empty_p (sp_bytes))
 484         {
 485           ret = true;
 486           break;
 487         }
 488     }
 489
 490   BITMAP_FREE (sp_bytes);
 491   if (!ret && arg_stores)
 492     bitmap_clear (arg_stores);
 493
 494   return ret;
 495 }
 496
 497
 498 /* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN
 499    writes to.  */
 500
 501 static void
 502 remove_reg_equal_equiv_notes_for_defs (rtx_insn *insn)
 503 {
 504   df_ref def;
 505
 506   FOR_EACH_INSN_DEF (def, insn)
 507     remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (def));
 508 }
 509
 510 /* Scan all BBs for debug insns and reset those that reference values
 511    defined in unmarked insns.  */
 512
 513 static void
 514 reset_unmarked_insns_debug_uses (void)
 515 {
 516   basic_block bb;
 517   rtx_insn *insn, *next;
 518
 519   FOR_EACH_BB_REVERSE_FN (bb, cfun)
 520     FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
 521       if (DEBUG_INSN_P (insn))
 522         {
 523           df_ref use;
 524
 525           FOR_EACH_INSN_USE (use, insn)
 526             {
 527               struct df_link *defs;
 528               for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
 529                 {
 530                   rtx_insn *ref_insn;
 531                   if (DF_REF_IS_ARTIFICIAL (defs->ref))
 532                     continue;
 533                   ref_insn = DF_REF_INSN (defs->ref);
 534                   if (!marked_insn_p (ref_insn))
 535                     break;
 536                 }
 537               if (!defs)
 538                 continue;
 539               /* ??? FIXME could we propagate the values assigned to
 540                  each of the DEFs?  */
 541               INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
 542               df_insn_rescan_debug_internal (insn);
 543               break;
 544             }
 545         }
 546 }
 547
 548 /* Delete every instruction that hasn't been marked.  */
 549
 550 static void
 551 delete_unmarked_insns (void)
 552 {
 553   basic_block bb;
 554   rtx_insn *insn, *next;
 555   bool must_clean = false;
 556
 557   FOR_EACH_BB_REVERSE_FN (bb, cfun)
 558     FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
 559       if (NONDEBUG_INSN_P (insn))
 560         {
 561           /* Always delete no-op moves.  */
 562           if (noop_move_p (insn))
 563             ;
 564
 565           /* Otherwise rely only on the DCE algorithm.  */
 566           else if (marked_insn_p (insn))
 567             continue;
 568
 569           /* Beware that reaching a dbg counter limit here can result
 570              in miscompiled file.  This occurs when a group of insns
 571              must be deleted together, typically because the kept insn
 572              depends on the output from the deleted insn.  Deleting
 573              this insns in reverse order (both at the bb level and
 574              when looking at the blocks) minimizes this, but does not
 575              eliminate it, since it is possible for the using insn to
 576              be top of a block and the producer to be at the bottom of
 577              the block.  However, in most cases this will only result
 578              in an uninitialized use of an insn that is dead anyway.
 579
 580              However, there is one rare case that will cause a
 581              miscompile: deletion of non-looping pure and constant
 582              calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
 583              In this case it is possible to remove the call, but leave
 584              the argument pushes to the stack.  Because of the changes
 585              to the stack pointer, this will almost always lead to a
 586              miscompile.  */
 587           if (!dbg_cnt (dce))
 588             continue;
 589
 590           if (dump_file)
 591             fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
 592
 593           /* Before we delete the insn we have to remove the REG_EQUAL notes
 594              for the destination regs in order to avoid dangling notes.  */
 595           remove_reg_equal_equiv_notes_for_defs (insn);
 596
 597           /* If a pure or const call is deleted, this may make the cfg
 598              have unreachable blocks.  We rememeber this and call
 599              delete_unreachable_blocks at the end.  */
 600           if (CALL_P (insn))
 601             must_clean = true;
 602
 603           /* Now delete the insn.  */
 604           delete_insn_and_edges (insn);
 605         }
 606
 607   /* Deleted a pure or const call.  */
 608   if (must_clean)
 609     delete_unreachable_blocks ();
 610 }
 611
 612
 613 /* Go through the instructions and mark those whose necessity is not
 614    dependent on inter-instruction information.  Make sure all other
 615    instructions are not marked.  */
 616
 617 static void
 618 prescan_insns_for_dce (bool fast)
 619 {
 620   basic_block bb;
 621   rtx_insn *insn, *prev;
 622   bitmap arg_stores = NULL;
 623
 624   if (dump_file)
 625     fprintf (dump_file, "Finding needed instructions:\n");
 626
 627   if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS)
 628     arg_stores = BITMAP_ALLOC (NULL);
 629
 630   FOR_EACH_BB_FN (bb, cfun)
 631     {
 632       FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)
 633         if (NONDEBUG_INSN_P (insn))
 634           {
 635             /* Don't mark argument stores now.  They will be marked
 636                if needed when the associated CALL is marked.  */
 637             if (arg_stores && bitmap_bit_p (arg_stores, INSN_UID (insn)))
 638               continue;
 639             if (deletable_insn_p (insn, fast, arg_stores))
 640               mark_nonreg_stores (PATTERN (insn), insn, fast);
 641             else
 642               mark_insn (insn, fast);
 643           }
 644       /* find_call_stack_args only looks at argument stores in the
 645          same bb.  */
 646       if (arg_stores)
 647         bitmap_clear (arg_stores);
 648     }
 649
 650   if (arg_stores)
 651     BITMAP_FREE (arg_stores);
 652
 653   if (dump_file)
 654     fprintf (dump_file, "Finished finding needed instructions:\n");
 655 }
 656
 657
 658 /* UD-based DSE routines. */
 659
 660 /* Mark instructions that define artificially-used registers, such as
 661    the frame pointer and the stack pointer.  */
 662
 663 static void
 664 mark_artificial_uses (void)
 665 {
 666   basic_block bb;
 667   struct df_link *defs;
 668   df_ref use;
 669
 670   FOR_ALL_BB_FN (bb, cfun)
 671     FOR_EACH_ARTIFICIAL_USE (use, bb->index)
 672       for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
 673         if (!DF_REF_IS_ARTIFICIAL (defs->ref))
 674           mark_insn (DF_REF_INSN (defs->ref), false);
 675 }
 676
 677
 678 /* Mark every instruction that defines a register value that INSN uses.  */
 679
 680 static void
 681 mark_reg_dependencies (rtx_insn *insn)
 682 {
 683   struct df_link *defs;
 684   df_ref use;
 685
 686   if (DEBUG_INSN_P (insn))
 687     return;
 688
 689   FOR_EACH_INSN_USE (use, insn)
 690     {
 691       if (dump_file)
 692         {
 693           fprintf (dump_file, "Processing use of ");
 694           print_simple_rtl (dump_file, DF_REF_REG (use));
 695           fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
 696         }
 697       for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
 698         if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 699           mark_insn (DF_REF_INSN (defs->ref), false);
 700     }
 701 }
 702
 703
 704 /* Initialize global variables for a new DCE pass.  */
 705
 706 static void
 707 init_dce (bool fast)
 708 {
 709   if (!df_in_progress)
 710     {
 711       if (!fast)
 712         {
 713           df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
 714           df_chain_add_problem (DF_UD_CHAIN);
 715         }
 716       df_analyze ();
 717     }
 718
 719   if (dump_file)
 720     df_dump (dump_file);
 721
 722   if (fast)
 723     {
 724       bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
 725       bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
 726       can_alter_cfg = false;
 727     }
 728   else
 729     can_alter_cfg = true;
 730
 731   marked = sbitmap_alloc (get_max_uid () + 1);
 732   bitmap_clear (marked);
 733 }
 734
 735
 736 /* Free the data allocated by init_dce.  */
 737
 738 static void
 739 fini_dce (bool fast)
 740 {
 741   sbitmap_free (marked);
 742
 743   if (fast)
 744     {
 745       bitmap_obstack_release (&dce_blocks_bitmap_obstack);
 746       bitmap_obstack_release (&dce_tmp_bitmap_obstack);
 747     }
 748 }
 749
 750
 751 /* UD-chain based DCE.  */
 752
 753 static unsigned int
 754 rest_of_handle_ud_dce (void)
 755 {
 756   rtx_insn *insn;
 757
 758   init_dce (false);
 759
 760   prescan_insns_for_dce (false);
 761   mark_artificial_uses ();
 762   while (worklist.length () > 0)
 763     {
 764       insn = worklist.pop ();
 765       mark_reg_dependencies (insn);
 766     }
 767   worklist.release ();
 768
 769   if (MAY_HAVE_DEBUG_INSNS)
 770     reset_unmarked_insns_debug_uses ();
 771
 772   /* Before any insns are deleted, we must remove the chains since
 773      they are not bidirectional.  */
 774   df_remove_problem (df_chain);
 775   delete_unmarked_insns ();
 776
 777   fini_dce (false);
 778   return 0;
 779 }
 780
 781
 782 namespace {
 783
 784 const pass_data pass_data_ud_rtl_dce =
 785 {
 786   RTL_PASS, /* type */
 787   "ud_dce", /* name */
 788   OPTGROUP_NONE, /* optinfo_flags */
 789   TV_DCE, /* tv_id */
 790   0, /* properties_required */
 791   0, /* properties_provided */
 792   0, /* properties_destroyed */
 793   0, /* todo_flags_start */
 794   TODO_df_finish, /* todo_flags_finish */
 795 };
 796
 797 class pass_ud_rtl_dce : public rtl_opt_pass
 798 {
 799 public:
 800   pass_ud_rtl_dce (gcc::context *ctxt)
 801     : rtl_opt_pass (pass_data_ud_rtl_dce, ctxt)
 802   {}
 803
 804   /* opt_pass methods: */
 805   virtual bool gate (function *)
 806     {
 807       return optimize > 1 && flag_dce && dbg_cnt (dce_ud);
 808     }
 809
 810   virtual unsigned int execute (function *)
 811     {
 812       return rest_of_handle_ud_dce ();
 813     }
 814
 815 }; // class pass_ud_rtl_dce
 816
 817 } // anon namespace
 818
 819 rtl_opt_pass *
 820 make_pass_ud_rtl_dce (gcc::context *ctxt)
 821 {
 822   return new pass_ud_rtl_dce (ctxt);
 823 }
 824
 825
 826 /* -------------------------------------------------------------------------
 827    Fast DCE functions
 828    ------------------------------------------------------------------------- */
 829
 830 /* Process basic block BB.  Return true if the live_in set has
 831    changed. REDO_OUT is true if the info at the bottom of the block
 832    needs to be recalculated before starting.  AU is the proper set of
 833    artificial uses.  Track global substitution of uses of dead pseudos
 834    in debug insns using GLOBAL_DEBUG.  */
 835
 836 static bool
 837 word_dce_process_block (basic_block bb, bool redo_out,
 838                         struct dead_debug_global *global_debug)
 839 {
 840   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
 841   rtx_insn *insn;
 842   bool block_changed;
 843   struct dead_debug_local debug;
 844
 845   if (redo_out)
 846     {
 847       /* Need to redo the live_out set of this block if when one of
 848          the succs of this block has had a change in it live in
 849          set.  */
 850       edge e;
 851       edge_iterator ei;
 852       df_confluence_function_n con_fun_n = df_word_lr->problem->con_fun_n;
 853       bitmap_clear (DF_WORD_LR_OUT (bb));
 854       FOR_EACH_EDGE (e, ei, bb->succs)
 855         (*con_fun_n) (e);
 856     }
 857
 858   if (dump_file)
 859     {
 860       fprintf (dump_file, "processing block %d live out = ", bb->index);
 861       df_print_word_regset (dump_file, DF_WORD_LR_OUT (bb));
 862     }
 863
 864   bitmap_copy (local_live, DF_WORD_LR_OUT (bb));
 865   dead_debug_local_init (&debug, NULL, global_debug);
 866
 867   FOR_BB_INSNS_REVERSE (bb, insn)
 868     if (DEBUG_INSN_P (insn))
 869       {
 870         df_ref use;
 871         FOR_EACH_INSN_USE (use, insn)
 872           if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER
 873               && (GET_MODE_SIZE (GET_MODE (DF_REF_REAL_REG (use)))
 874                   == 2 * UNITS_PER_WORD)
 875               && !bitmap_bit_p (local_live, 2 * DF_REF_REGNO (use))
 876               && !bitmap_bit_p (local_live, 2 * DF_REF_REGNO (use) + 1))
 877             dead_debug_add (&debug, use, DF_REF_REGNO (use));
 878       }
 879     else if (INSN_P (insn))
 880       {
 881         bool any_changed;
 882
 883         /* No matter if the instruction is needed or not, we remove
 884            any regno in the defs from the live set.  */
 885         any_changed = df_word_lr_simulate_defs (insn, local_live);
 886         if (any_changed)
 887           mark_insn (insn, true);
 888
 889         /* On the other hand, we do not allow the dead uses to set
 890            anything in local_live.  */
 891         if (marked_insn_p (insn))
 892           df_word_lr_simulate_uses (insn, local_live);
 893
 894         /* Insert debug temps for dead REGs used in subsequent debug
 895            insns.  We may have to emit a debug temp even if the insn
 896            was marked, in case the debug use was after the point of
 897            death.  */
 898         if (debug.used && !bitmap_empty_p (debug.used))
 899           {
 900             df_ref def;
 901
 902             FOR_EACH_INSN_DEF (def, insn)
 903               dead_debug_insert_temp (&debug, DF_REF_REGNO (def), insn,
 904                                       marked_insn_p (insn)
 905                                       && !control_flow_insn_p (insn)
 906                                       ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
 907                                       : DEBUG_TEMP_BEFORE_WITH_VALUE);
 908           }
 909
 910         if (dump_file)
 911           {
 912             fprintf (dump_file, "finished processing insn %d live out = ",
 913                      INSN_UID (insn));
 914             df_print_word_regset (dump_file, local_live);
 915           }
 916       }
 917
 918   block_changed = !bitmap_equal_p (local_live, DF_WORD_LR_IN (bb));
 919   if (block_changed)
 920     bitmap_copy (DF_WORD_LR_IN (bb), local_live);
 921
 922   dead_debug_local_finish (&debug, NULL);
 923   BITMAP_FREE (local_live);
 924   return block_changed;
 925 }
 926
 927
 928 /* Process basic block BB.  Return true if the live_in set has
 929    changed. REDO_OUT is true if the info at the bottom of the block
 930    needs to be recalculated before starting.  AU is the proper set of
 931    artificial uses.  Track global substitution of uses of dead pseudos
 932    in debug insns using GLOBAL_DEBUG.  */
 933
 934 static bool
 935 dce_process_block (basic_block bb, bool redo_out, bitmap au,
 936                    struct dead_debug_global *global_debug)
 937 {
 938   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
 939   rtx_insn *insn;
 940   bool block_changed;
 941   df_ref def;
 942   struct dead_debug_local debug;
 943
 944   if (redo_out)
 945     {
 946       /* Need to redo the live_out set of this block if when one of
 947          the succs of this block has had a change in it live in
 948          set.  */
 949       edge e;
 950       edge_iterator ei;
 951       df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
 952       bitmap_clear (DF_LR_OUT (bb));
 953       FOR_EACH_EDGE (e, ei, bb->succs)
 954         (*con_fun_n) (e);
 955     }
 956
 957   if (dump_file)
 958     {
 959       fprintf (dump_file, "processing block %d lr out = ", bb->index);
 960       df_print_regset (dump_file, DF_LR_OUT (bb));
 961     }
 962
 963   bitmap_copy (local_live, DF_LR_OUT (bb));
 964
 965   df_simulate_initialize_backwards (bb, local_live);
 966   dead_debug_local_init (&debug, NULL, global_debug);
 967
 968   FOR_BB_INSNS_REVERSE (bb, insn)
 969     if (DEBUG_INSN_P (insn))
 970       {
 971         df_ref use;
 972         FOR_EACH_INSN_USE (use, insn)
 973           if (!bitmap_bit_p (local_live, DF_REF_REGNO (use))
 974               && !bitmap_bit_p (au, DF_REF_REGNO (use)))
 975             dead_debug_add (&debug, use, DF_REF_REGNO (use));
 976       }
 977     else if (INSN_P (insn))
 978       {
 979         bool needed = marked_insn_p (insn);
 980
 981         /* The insn is needed if there is someone who uses the output.  */
 982         if (!needed)
 983           FOR_EACH_INSN_DEF (def, insn)
 984             if (bitmap_bit_p (local_live, DF_REF_REGNO (def))
 985                 || bitmap_bit_p (au, DF_REF_REGNO (def)))
 986               {
 987                 needed = true;
 988                 mark_insn (insn, true);
 989                 break;
 990               }
 991
 992         /* No matter if the instruction is needed or not, we remove
 993            any regno in the defs from the live set.  */
 994         df_simulate_defs (insn, local_live);
 995
 996         /* On the other hand, we do not allow the dead uses to set
 997            anything in local_live.  */
 998         if (needed)
 999           df_simulate_uses (insn, local_live);
1000
1001         /* Insert debug temps for dead REGs used in subsequent debug
1002            insns.  We may have to emit a debug temp even if the insn
1003            was marked, in case the debug use was after the point of
1004            death.  */
1005         if (debug.used && !bitmap_empty_p (debug.used))
1006           FOR_EACH_INSN_DEF (def, insn)
1007             dead_debug_insert_temp (&debug, DF_REF_REGNO (def), insn,
1008                                     needed && !control_flow_insn_p (insn)
1009                                     ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
1010                                     : DEBUG_TEMP_BEFORE_WITH_VALUE);
1011       }
1012
1013   dead_debug_local_finish (&debug, NULL);
1014   df_simulate_finalize_backwards (bb, local_live);
1015
1016   block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
1017   if (block_changed)
1018     bitmap_copy (DF_LR_IN (bb), local_live);
1019
1020   BITMAP_FREE (local_live);
1021   return block_changed;
1022 }
1023
1024
1025 /* Perform fast DCE once initialization is done.  If WORD_LEVEL is
1026    true, use the word level dce, otherwise do it at the pseudo
1027    level.  */
1028
1029 static void
1030 fast_dce (bool word_level)
1031 {
1032   int *postorder = df_get_postorder (DF_BACKWARD);
1033   int n_blocks = df_get_n_blocks (DF_BACKWARD);
1034   /* The set of blocks that have been seen on this iteration.  */
1035   bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
1036   /* The set of blocks that need to have the out vectors reset because
1037      the in of one of their successors has changed.  */
1038   bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
1039   bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
1040   bool global_changed = true;
1041
1042   /* These regs are considered always live so if they end up dying
1043      because of some def, we need to bring the back again.  Calling
1044      df_simulate_fixup_sets has the disadvantage of calling
1045      bb_has_eh_pred once per insn, so we cache the information
1046      here.  */
1047   bitmap au = &df->regular_block_artificial_uses;
1048   bitmap au_eh = &df->eh_block_artificial_uses;
1049   int i;
1050   struct dead_debug_global global_debug;
1051
1052   prescan_insns_for_dce (true);
1053
1054   for (i = 0; i < n_blocks; i++)
1055     bitmap_set_bit (all_blocks, postorder[i]);
1056
1057   dead_debug_global_init (&global_debug, NULL);
1058
1059   while (global_changed)
1060     {
1061       global_changed = false;
1062
1063       for (i = 0; i < n_blocks; i++)
1064         {
1065           int index = postorder[i];
1066           basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
1067           bool local_changed;
1068
1069           if (index < NUM_FIXED_BLOCKS)
1070             {
1071               bitmap_set_bit (processed, index);
1072               continue;
1073             }
1074
1075           if (word_level)
1076             local_changed
1077               = word_dce_process_block (bb, bitmap_bit_p (redo_out, index),
1078                                         &global_debug);
1079           else
1080             local_changed
1081               = dce_process_block (bb, bitmap_bit_p (redo_out, index),
1082                                    bb_has_eh_pred (bb) ? au_eh : au,
1083                                    &global_debug);
1084           bitmap_set_bit (processed, index);
1085
1086           if (local_changed)
1087             {
1088               edge e;
1089               edge_iterator ei;
1090               FOR_EACH_EDGE (e, ei, bb->preds)
1091                 if (bitmap_bit_p (processed, e->src->index))
1092                   /* Be tricky about when we need to iterate the
1093                      analysis.  We only have redo the analysis if the
1094                      bitmaps change at the top of a block that is the
1095                      entry to a loop.  */
1096                   global_changed = true;
1097                 else
1098                   bitmap_set_bit (redo_out, e->src->index);
1099             }
1100         }
1101
1102       if (global_changed)
1103         {
1104           /* Turn off the RUN_DCE flag to prevent recursive calls to
1105              dce.  */
1106           int old_flag = df_clear_flags (DF_LR_RUN_DCE);
1107
1108           /* So something was deleted that requires a redo.  Do it on
1109              the cheap.  */
1110           delete_unmarked_insns ();
1111           bitmap_clear (marked);
1112           bitmap_clear (processed);
1113           bitmap_clear (redo_out);
1114
1115           /* We do not need to rescan any instructions.  We only need
1116              to redo the dataflow equations for the blocks that had a
1117              change at the top of the block.  Then we need to redo the
1118              iteration.  */
1119           if (word_level)
1120             df_analyze_problem (df_word_lr, all_blocks, postorder, n_blocks);
1121           else
1122             df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
1123
1124           if (old_flag & DF_LR_RUN_DCE)
1125             df_set_flags (DF_LR_RUN_DCE);
1126
1127           prescan_insns_for_dce (true);
1128         }
1129     }
1130
1131   dead_debug_global_finish (&global_debug, NULL);
1132
1133   delete_unmarked_insns ();
1134
1135   BITMAP_FREE (processed);
1136   BITMAP_FREE (redo_out);
1137   BITMAP_FREE (all_blocks);
1138 }
1139
1140
1141 /* Fast register level DCE.  */
1142
1143 static unsigned int
1144 rest_of_handle_fast_dce (void)
1145 {
1146   init_dce (true);
1147   fast_dce (false);
1148   fini_dce (true);
1149   return 0;
1150 }
1151
1152
1153 /* Fast byte level DCE.  */
1154
1155 void
1156 run_word_dce (void)
1157 {
1158   int old_flags;
1159
1160   if (!flag_dce)
1161     return;
1162
1163   timevar_push (TV_DCE);
1164   old_flags = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
1165   df_word_lr_add_problem ();
1166   init_dce (true);
1167   fast_dce (true);
1168   fini_dce (true);
1169   df_set_flags (old_flags);
1170   timevar_pop (TV_DCE);
1171 }
1172
1173
1174 /* This is an internal call that is used by the df live register
1175    problem to run fast dce as a side effect of creating the live
1176    information.  The stack is organized so that the lr problem is run,
1177    this pass is run, which updates the live info and the df scanning
1178    info, and then returns to allow the rest of the problems to be run.
1179
1180    This can be called by elsewhere but it will not update the bit
1181    vectors for any other problems than LR.  */
1182
1183 void
1184 run_fast_df_dce (void)
1185 {
1186   if (flag_dce)
1187     {
1188       /* If dce is able to delete something, it has to happen
1189          immediately.  Otherwise there will be problems handling the
1190          eq_notes.  */
1191       int old_flags =
1192         df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
1193
1194       df_in_progress = true;
1195       rest_of_handle_fast_dce ();
1196       df_in_progress = false;
1197
1198       df_set_flags (old_flags);
1199     }
1200 }
1201
1202
1203 /* Run a fast DCE pass.  */
1204
1205 void
1206 run_fast_dce (void)
1207 {
1208   if (flag_dce)
1209     rest_of_handle_fast_dce ();
1210 }
1211
1212
1213 namespace {
1214
1215 const pass_data pass_data_fast_rtl_dce =
1216 {
1217   RTL_PASS, /* type */
1218   "rtl_dce", /* name */
1219   OPTGROUP_NONE, /* optinfo_flags */
1220   TV_DCE, /* tv_id */
1221   0, /* properties_required */
1222   0, /* properties_provided */
1223   0, /* properties_destroyed */
1224   0, /* todo_flags_start */
1225   TODO_df_finish, /* todo_flags_finish */
1226 };
1227
1228 class pass_fast_rtl_dce : public rtl_opt_pass
1229 {
1230 public:
1231   pass_fast_rtl_dce (gcc::context *ctxt)
1232     : rtl_opt_pass (pass_data_fast_rtl_dce, ctxt)
1233   {}
1234
1235   /* opt_pass methods: */
1236   virtual bool gate (function *)
1237     {
1238       return optimize > 0 && flag_dce && dbg_cnt (dce_fast);
1239     }
1240
1241   virtual unsigned int execute (function *)
1242     {
1243       return rest_of_handle_fast_dce ();
1244     }
1245
1246 }; // class pass_fast_rtl_dce
1247
1248 } // anon namespace
1249
1250 rtl_opt_pass *
1251 make_pass_fast_rtl_dce (gcc::context *ctxt)
1252 {
1253   return new pass_fast_rtl_dce (ctxt);
1254 }