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             gcc_assert (!bitmap_bit_p (sp_bytes, byte - min_sp_off));
 358             bitmap_set_bit (sp_bytes, byte - min_sp_off);
 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_bit_p (sp_bytes, byte - min_sp_off))
 446             break;
 447           bitmap_clear_bit (sp_bytes, byte - min_sp_off);
 448         }
 449
 450       if (!deletable_insn_p (insn, fast, NULL))
 451         break;
 452
 453       if (do_mark)
 454         mark_insn (insn, fast);
 455       else
 456         bitmap_set_bit (arg_stores, INSN_UID (insn));
 457
 458       if (bitmap_empty_p (sp_bytes))
 459         {
 460           ret = true;
 461           break;
 462         }
 463     }
 464
 465   BITMAP_FREE (sp_bytes);
 466   if (!ret && arg_stores)
 467     bitmap_clear (arg_stores);
 468
 469   return ret;
 470 }
 471
 472
 473 /* Delete all REG_EQUAL notes of the registers INSN writes, to prevent
 474    bad dangling REG_EQUAL notes. */
 475
 476 static void
 477 delete_corresponding_reg_eq_notes (rtx insn)
 478 {
 479   df_ref *def_rec;
 480   for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 481     {
 482       df_ref def = *def_rec;
 483       unsigned int regno = DF_REF_REGNO (def);
 484       /* This loop is a little tricky.  We cannot just go down the
 485          chain because it is being modified by the actions in the
 486          loop.  So we just get the head.  We plan to drain the list
 487          anyway.  */
 488       while (DF_REG_EQ_USE_CHAIN (regno))
 489         {
 490           df_ref eq_use = DF_REG_EQ_USE_CHAIN (regno);
 491           rtx noted_insn = DF_REF_INSN (eq_use);
 492           rtx note = find_reg_note (noted_insn, REG_EQUAL, NULL_RTX);
 493           if (!note)
 494             note = find_reg_note (noted_insn, REG_EQUIV, NULL_RTX);
 495
 496           /* This assert is generally triggered when someone deletes a
 497              REG_EQUAL or REG_EQUIV note by hacking the list manually
 498              rather than calling remove_note.  */
 499           gcc_assert (note);
 500           remove_note (noted_insn, note);
 501         }
 502     }
 503 }
 504
 505
 506 /* Delete every instruction that hasn't been marked.  */
 507
 508 static void
 509 delete_unmarked_insns (void)
 510 {
 511   basic_block bb;
 512   rtx insn, next;
 513   bool must_clean = false;
 514
 515   FOR_EACH_BB_REVERSE (bb)
 516     FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
 517       if (INSN_P (insn))
 518         {
 519           /* Always delete no-op moves.  */
 520           if (noop_move_p (insn))
 521             ;
 522
 523           /* Otherwise rely only on the DCE algorithm.  */
 524           else if (marked_insn_p (insn))
 525             continue;
 526
 527           /* Beware that reaching a dbg counter limit here can result
 528              in miscompiled file.  This occurs when a group of insns
 529              must be deleted together, typically because the kept insn
 530              depends on the output from the deleted insn.  Deleting
 531              this insns in reverse order (both at the bb level and
 532              when looking at the blocks) minimizes this, but does not
 533              eliminate it, since it is possible for the using insn to
 534              be top of a block and the producer to be at the bottom of
 535              the block.  However, in most cases this will only result
 536              in an uninitialized use of an insn that is dead anyway.
 537
 538              However, there is one rare case that will cause a
 539              miscompile: deletion of non-looping pure and constant
 540              calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
 541              In this case it is possible to remove the call, but leave
 542              the argument pushes to the stack.  Because of the changes
 543              to the stack pointer, this will almost always lead to a
 544              miscompile.  */
 545           if (!dbg_cnt (dce))
 546             continue;
 547
 548           if (dump_file)
 549             fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
 550
 551           /* Before we delete the insn we have to delete REG_EQUAL notes
 552              for the destination regs in order to avoid dangling notes.  */
 553           delete_corresponding_reg_eq_notes (insn);
 554
 555           /* If a pure or const call is deleted, this may make the cfg
 556              have unreachable blocks.  We rememeber this and call
 557              delete_unreachable_blocks at the end.  */
 558           if (CALL_P (insn))
 559             must_clean = true;
 560
 561           /* Now delete the insn.  */
 562           delete_insn_and_edges (insn);
 563         }
 564
 565   /* Deleted a pure or const call.  */
 566   if (must_clean)
 567     delete_unreachable_blocks ();
 568 }
 569
 570
 571 /* Go through the instructions and mark those whose necessity is not
 572    dependent on inter-instruction information.  Make sure all other
 573    instructions are not marked.  */
 574
 575 static void
 576 prescan_insns_for_dce (bool fast)
 577 {
 578   basic_block bb;
 579   rtx insn, prev;
 580   bitmap arg_stores = NULL;
 581
 582   if (dump_file)
 583     fprintf (dump_file, "Finding needed instructions:\n");
 584
 585   if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS)
 586     arg_stores = BITMAP_ALLOC (NULL);
 587
 588   FOR_EACH_BB (bb)
 589     {
 590       FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)
 591         if (INSN_P (insn))
 592           {
 593             /* Don't mark argument stores now.  They will be marked
 594                if needed when the associated CALL is marked.  */
 595             if (arg_stores && bitmap_bit_p (arg_stores, INSN_UID (insn)))
 596               continue;
 597             if (deletable_insn_p (insn, fast, arg_stores))
 598               mark_nonreg_stores (PATTERN (insn), insn, fast);
 599             else
 600               mark_insn (insn, fast);
 601           }
 602       /* find_call_stack_args only looks at argument stores in the
 603          same bb.  */
 604       if (arg_stores)
 605         bitmap_clear (arg_stores);
 606     }
 607
 608   if (arg_stores)
 609     BITMAP_FREE (arg_stores);
 610
 611   if (dump_file)
 612     fprintf (dump_file, "Finished finding needed instructions:\n");
 613 }
 614
 615
 616 /* UD-based DSE routines. */
 617
 618 /* Mark instructions that define artificially-used registers, such as
 619    the frame pointer and the stack pointer.  */
 620
 621 static void
 622 mark_artificial_uses (void)
 623 {
 624   basic_block bb;
 625   struct df_link *defs;
 626   df_ref *use_rec;
 627
 628   FOR_ALL_BB (bb)
 629     {
 630       for (use_rec = df_get_artificial_uses (bb->index);
 631            *use_rec; use_rec++)
 632         for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
 633           if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 634             mark_insn (DF_REF_INSN (defs->ref), false);
 635     }
 636 }
 637
 638
 639 /* Mark every instruction that defines a register value that INSN uses.  */
 640
 641 static void
 642 mark_reg_dependencies (rtx insn)
 643 {
 644   struct df_link *defs;
 645   df_ref *use_rec;
 646
 647   for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
 648     {
 649       df_ref use = *use_rec;
 650       if (dump_file)
 651         {
 652           fprintf (dump_file, "Processing use of ");
 653           print_simple_rtl (dump_file, DF_REF_REG (use));
 654           fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
 655         }
 656       for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
 657         if (! DF_REF_IS_ARTIFICIAL (defs->ref))
 658           mark_insn (DF_REF_INSN (defs->ref), false);
 659     }
 660 }
 661
 662
 663 /* Initialize global variables for a new DCE pass.  */
 664
 665 static void
 666 init_dce (bool fast)
 667 {
 668   if (!df_in_progress)
 669     {
 670       if (!fast)
 671         df_chain_add_problem (DF_UD_CHAIN);
 672       df_analyze ();
 673     }
 674
 675   if (dump_file)
 676     df_dump (dump_file);
 677
 678   if (fast)
 679     {
 680       bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
 681       bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
 682     }
 683
 684   marked = sbitmap_alloc (get_max_uid () + 1);
 685   sbitmap_zero (marked);
 686 }
 687
 688
 689 /* Free the data allocated by init_dce.  */
 690
 691 static void
 692 fini_dce (bool fast)
 693 {
 694   sbitmap_free (marked);
 695
 696   if (fast)
 697     {
 698       bitmap_obstack_release (&dce_blocks_bitmap_obstack);
 699       bitmap_obstack_release (&dce_tmp_bitmap_obstack);
 700     }
 701 }
 702
 703
 704 /* UD-chain based DCE.  */
 705
 706 static unsigned int
 707 rest_of_handle_ud_dce (void)
 708 {
 709   rtx insn;
 710
 711   init_dce (false);
 712
 713   prescan_insns_for_dce (false);
 714   mark_artificial_uses ();
 715   while (VEC_length (rtx, worklist) > 0)
 716     {
 717       insn = VEC_pop (rtx, worklist);
 718       mark_reg_dependencies (insn);
 719     }
 720   VEC_free (rtx, heap, worklist);
 721
 722   /* Before any insns are deleted, we must remove the chains since
 723      they are not bidirectional.  */
 724   df_remove_problem (df_chain);
 725   delete_unmarked_insns ();
 726
 727   fini_dce (false);
 728   return 0;
 729 }
 730
 731
 732 static bool
 733 gate_ud_dce (void)
 734 {
 735   return optimize > 1 && flag_dce
 736     && dbg_cnt (dce_ud);
 737 }
 738
 739 struct rtl_opt_pass pass_ud_rtl_dce =
 740 {
 741  {
 742   RTL_PASS,
 743   "dce",                                /* name */
 744   gate_ud_dce,                        /* gate */
 745   rest_of_handle_ud_dce,              /* execute */
 746   NULL,                                 /* sub */
 747   NULL,                                 /* next */
 748   0,                                    /* static_pass_number */
 749   TV_DCE,                               /* tv_id */
 750   0,                                    /* properties_required */
 751   0,                                    /* properties_provided */
 752   0,                                    /* properties_destroyed */
 753   0,                                    /* todo_flags_start */
 754   TODO_dump_func |
 755   TODO_df_finish | TODO_verify_rtl_sharing |
 756   TODO_ggc_collect                     /* todo_flags_finish */
 757  }
 758 };
 759
 760
 761 /* -------------------------------------------------------------------------
 762    Fast DCE functions
 763    ------------------------------------------------------------------------- */
 764
 765 /* Process basic block BB.  Return true if the live_in set has
 766    changed. REDO_OUT is true if the info at the bottom of the block
 767    needs to be recalculated before starting.  AU is the proper set of
 768    artificial uses. */
 769
 770 static bool
 771 byte_dce_process_block (basic_block bb, bool redo_out, bitmap au)
 772 {
 773   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
 774   rtx insn;
 775   bool block_changed;
 776   df_ref *def_rec;
 777
 778   if (redo_out)
 779     {
 780       /* Need to redo the live_out set of this block if when one of
 781          the succs of this block has had a change in it live in
 782          set.  */
 783       edge e;
 784       edge_iterator ei;
 785       df_confluence_function_n con_fun_n = df_byte_lr->problem->con_fun_n;
 786       bitmap_clear (DF_BYTE_LR_OUT (bb));
 787       FOR_EACH_EDGE (e, ei, bb->succs)
 788         (*con_fun_n) (e);
 789     }
 790
 791   if (dump_file)
 792     {
 793       fprintf (dump_file, "processing block %d live out = ", bb->index);
 794       df_print_byte_regset (dump_file, DF_BYTE_LR_OUT (bb));
 795     }
 796
 797   bitmap_copy (local_live, DF_BYTE_LR_OUT (bb));
 798
 799   df_byte_lr_simulate_artificial_refs_at_end (bb, local_live);
 800
 801   FOR_BB_INSNS_REVERSE (bb, insn)
 802     if (INSN_P (insn))
 803       {
 804         /* The insn is needed if there is someone who uses the output.  */
 805         for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
 806           {
 807             df_ref def = *def_rec;
 808             unsigned int last;
 809             unsigned int dregno = DF_REF_REGNO (def);
 810             unsigned int start = df_byte_lr_get_regno_start (dregno);
 811             unsigned int len = df_byte_lr_get_regno_len (dregno);
 812
 813             unsigned int sb;
 814             unsigned int lb;
 815             /* This is one of the only places where DF_MM_MAY should
 816                be used for defs.  Need to make sure that we are
 817                checking for all of the bits that may be used.  */
 818
 819             if (!df_compute_accessed_bytes (def, DF_MM_MAY, &sb, &lb))
 820               {
 821                 start += sb;
 822                 len = lb - sb;
 823               }
 824
 825             if (bitmap_bit_p (au, dregno))
 826               {
 827                 mark_insn (insn, true);
 828                 goto quickexit;
 829               }
 830
 831             last = start + len;
 832             while (start < last)
 833               if (bitmap_bit_p (local_live, start++))
 834                 {
 835                   mark_insn (insn, true);
 836                   goto quickexit;
 837                 }
 838           }
 839
 840       quickexit:
 841
 842         /* No matter if the instruction is needed or not, we remove
 843            any regno in the defs from the live set.  */
 844         df_byte_lr_simulate_defs (insn, local_live);
 845
 846         /* On the other hand, we do not allow the dead uses to set
 847            anything in local_live.  */
 848         if (marked_insn_p (insn))
 849           df_byte_lr_simulate_uses (insn, local_live);
 850
 851         if (dump_file)
 852           {
 853             fprintf (dump_file, "finished processing insn %d live out = ",
 854                      INSN_UID (insn));
 855             df_print_byte_regset (dump_file, local_live);
 856           }
 857       }
 858
 859   df_byte_lr_simulate_artificial_refs_at_top (bb, local_live);
 860
 861   block_changed = !bitmap_equal_p (local_live, DF_BYTE_LR_IN (bb));
 862   if (block_changed)
 863     bitmap_copy (DF_BYTE_LR_IN (bb), local_live);
 864   BITMAP_FREE (local_live);
 865   return block_changed;
 866 }
 867
 868
 869 /* Process basic block BB.  Return true if the live_in set has
 870    changed. REDO_OUT is true if the info at the bottom of the block
 871    needs to be recalculated before starting.  AU is the proper set of
 872    artificial uses. */
 873
 874 static bool
 875 dce_process_block (basic_block bb, bool redo_out, bitmap au)
 876 {
 877   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
 878   rtx insn;
 879   bool block_changed;
 880   df_ref *def_rec;
 881
 882   if (redo_out)
 883     {
 884       /* Need to redo the live_out set of this block if when one of
 885          the succs of this block has had a change in it live in
 886          set.  */
 887       edge e;
 888       edge_iterator ei;
 889       df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
 890       bitmap_clear (DF_LR_OUT (bb));
 891       FOR_EACH_EDGE (e, ei, bb->succs)
 892         (*con_fun_n) (e);
 893     }
 894
 895   if (dump_file)
 896     {
 897       fprintf (dump_file, "processing block %d lr out = ", bb->index);
 898       df_print_regset (dump_file, DF_LR_OUT (bb));
 899     }
 900
 901   bitmap_copy (local_live, DF_LR_OUT (bb));
 902
 903   df_simulate_initialize_backwards (bb, local_live);
 904
 905   FOR_BB_INSNS_REVERSE (bb, insn)
 906     if (INSN_P (insn))
 907       {
 908         bool needed = false;
 909
 910         /* The insn is needed if there is someone who uses the output.  */
 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               break;
 917             }
 918
 919         if (needed)
 920           mark_insn (insn, true);
 921
 922         /* No matter if the instruction is needed or not, we remove
 923            any regno in the defs from the live set.  */
 924         df_simulate_defs (insn, local_live);
 925
 926         /* On the other hand, we do not allow the dead uses to set
 927            anything in local_live.  */
 928         if (marked_insn_p (insn))
 929           df_simulate_uses (insn, local_live);
 930       }
 931
 932   df_simulate_finalize_backwards (bb, local_live);
 933
 934   block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
 935   if (block_changed)
 936     bitmap_copy (DF_LR_IN (bb), local_live);
 937
 938   BITMAP_FREE (local_live);
 939   return block_changed;
 940 }
 941
 942
 943 /* Perform fast DCE once initialization is done.  If BYTE_LEVEL is
 944    true, use the byte level dce, otherwise do it at the pseudo
 945    level.  */
 946
 947 static void
 948 fast_dce (bool byte_level)
 949 {
 950   int *postorder = df_get_postorder (DF_BACKWARD);
 951   int n_blocks = df_get_n_blocks (DF_BACKWARD);
 952   /* The set of blocks that have been seen on this iteration.  */
 953   bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 954   /* The set of blocks that need to have the out vectors reset because
 955      the in of one of their successors has changed.  */
 956   bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 957   bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
 958   bool global_changed = true;
 959
 960   /* These regs are considered always live so if they end up dying
 961      because of some def, we need to bring the back again.  Calling
 962      df_simulate_fixup_sets has the disadvantage of calling
 963      bb_has_eh_pred once per insn, so we cache the information
 964      here.  */
 965   bitmap au = df->regular_block_artificial_uses;
 966   bitmap au_eh = df->eh_block_artificial_uses;
 967   int i;
 968
 969   prescan_insns_for_dce (true);
 970
 971   for (i = 0; i < n_blocks; i++)
 972     bitmap_set_bit (all_blocks, postorder[i]);
 973
 974   while (global_changed)
 975     {
 976       global_changed = false;
 977
 978       for (i = 0; i < n_blocks; i++)
 979         {
 980           int index = postorder[i];
 981           basic_block bb = BASIC_BLOCK (index);
 982           bool local_changed;
 983
 984           if (index < NUM_FIXED_BLOCKS)
 985             {
 986               bitmap_set_bit (processed, index);
 987               continue;
 988             }
 989
 990           if (byte_level)
 991             local_changed
 992               = byte_dce_process_block (bb, bitmap_bit_p (redo_out, index),
 993                                           bb_has_eh_pred (bb) ? au_eh : au);
 994           else
 995             local_changed
 996               = dce_process_block (bb, bitmap_bit_p (redo_out, index),
 997                                    bb_has_eh_pred (bb) ? au_eh : au);
 998           bitmap_set_bit (processed, index);
 999
1000           if (local_changed)
1001             {
1002               edge e;
1003               edge_iterator ei;
1004               FOR_EACH_EDGE (e, ei, bb->preds)
1005                 if (bitmap_bit_p (processed, e->src->index))
1006                   /* Be tricky about when we need to iterate the
1007                      analysis.  We only have redo the analysis if the
1008                      bitmaps change at the top of a block that is the
1009                      entry to a loop.  */
1010                   global_changed = true;
1011                 else
1012                   bitmap_set_bit (redo_out, e->src->index);
1013             }
1014         }
1015
1016       if (global_changed)
1017         {
1018           /* Turn off the RUN_DCE flag to prevent recursive calls to
1019              dce.  */
1020           int old_flag = df_clear_flags (DF_LR_RUN_DCE);
1021
1022           /* So something was deleted that requires a redo.  Do it on
1023              the cheap.  */
1024           delete_unmarked_insns ();
1025           sbitmap_zero (marked);
1026           bitmap_clear (processed);
1027           bitmap_clear (redo_out);
1028
1029           /* We do not need to rescan any instructions.  We only need
1030              to redo the dataflow equations for the blocks that had a
1031              change at the top of the block.  Then we need to redo the
1032              iteration.  */
1033           if (byte_level)
1034             df_analyze_problem (df_byte_lr, all_blocks, postorder, n_blocks);
1035           else
1036             df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
1037
1038           if (old_flag & DF_LR_RUN_DCE)
1039             df_set_flags (DF_LR_RUN_DCE);
1040
1041           prescan_insns_for_dce (true);
1042         }
1043     }
1044
1045   delete_unmarked_insns ();
1046
1047   BITMAP_FREE (processed);
1048   BITMAP_FREE (redo_out);
1049   BITMAP_FREE (all_blocks);
1050 }
1051
1052
1053 /* Fast register level DCE.  */
1054
1055 static unsigned int
1056 rest_of_handle_fast_dce (void)
1057 {
1058   init_dce (true);
1059   fast_dce (false);
1060   fini_dce (true);
1061   return 0;
1062 }
1063
1064
1065 /* Fast byte level DCE.  */
1066
1067 static unsigned int
1068 rest_of_handle_fast_byte_dce (void)
1069 {
1070   df_byte_lr_add_problem ();
1071   init_dce (true);
1072   fast_dce (true);
1073   fini_dce (true);
1074   return 0;
1075 }
1076
1077
1078 /* This is an internal call that is used by the df live register
1079    problem to run fast dce as a side effect of creating the live
1080    information.  The stack is organized so that the lr problem is run,
1081    this pass is run, which updates the live info and the df scanning
1082    info, and then returns to allow the rest of the problems to be run.
1083
1084    This can be called by elsewhere but it will not update the bit
1085    vectors for any other problems than LR.  */
1086
1087 void
1088 run_fast_df_dce (void)
1089 {
1090   if (flag_dce)
1091     {
1092       /* If dce is able to delete something, it has to happen
1093          immediately.  Otherwise there will be problems handling the
1094          eq_notes.  */
1095       int old_flags =
1096         df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
1097
1098       df_in_progress = true;
1099       rest_of_handle_fast_dce ();
1100       df_in_progress = false;
1101
1102       df_set_flags (old_flags);
1103     }
1104 }
1105
1106
1107 /* Run a fast DCE pass.  */
1108
1109 void
1110 run_fast_dce (void)
1111 {
1112   if (flag_dce)
1113     rest_of_handle_fast_dce ();
1114 }
1115
1116
1117 static bool
1118 gate_fast_dce (void)
1119 {
1120   return optimize > 0 && flag_dce
1121     && dbg_cnt (dce_fast);
1122 }
1123
1124 struct rtl_opt_pass pass_fast_rtl_dce =
1125 {
1126  {
1127   RTL_PASS,
1128   "dce",                                /* name */
1129   gate_fast_dce,                        /* gate */
1130   rest_of_handle_fast_dce,              /* execute */
1131   NULL,                                 /* sub */
1132   NULL,                                 /* next */
1133   0,                                    /* static_pass_number */
1134   TV_DCE,                               /* tv_id */
1135   0,                                    /* properties_required */
1136   0,                                    /* properties_provided */
1137   0,                                    /* properties_destroyed */
1138   0,                                    /* todo_flags_start */
1139   TODO_dump_func |
1140   TODO_df_finish | TODO_verify_rtl_sharing |
1141   TODO_ggc_collect                      /* todo_flags_finish */
1142  }
1143 };
1144
1145 struct rtl_opt_pass pass_fast_rtl_byte_dce =
1146 {
1147  {
1148   RTL_PASS,
1149   "byte-dce",                           /* name */
1150   gate_fast_dce,                        /* gate */
1151   rest_of_handle_fast_byte_dce,         /* execute */
1152   NULL,                                 /* sub */
1153   NULL,                                 /* next */
1154   0,                                    /* static_pass_number */
1155   TV_DCE,                               /* tv_id */
1156   0,                                    /* properties_required */
1157   0,                                    /* properties_provided */
1158   0,                                    /* properties_destroyed */
1159   0,                                    /* todo_flags_start */
1160   TODO_dump_func |
1161   TODO_df_finish | TODO_verify_rtl_sharing |
1162   TODO_ggc_collect                      /* todo_flags_finish */
1163  }
1164 };