OSDN Git Service

91cc9aa5c281516313091197de9eb2a38635c6be
[pf3gnuchains/gcc-fork.git] / gcc / dce.c
1 /* RTL dead code elimination.
2    Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3.  If not see
18 <http://www.gnu.org/licenses/>.  */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "hashtab.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "tree.h"
27 #include "regs.h"
28 #include "hard-reg-set.h"
29 #include "flags.h"
30 #include "df.h"
31 #include "cselib.h"
32 #include "dce.h"
33 #include "timevar.h"
34 #include "tree-pass.h"
35 #include "dbgcnt.h"
36
37 DEF_VEC_I(int);
38 DEF_VEC_ALLOC_I(int,heap);
39
40
41 /* -------------------------------------------------------------------------
42    Core mark/delete routines
43    ------------------------------------------------------------------------- */
44
45 /* True if we are invoked while the df engine is running; in this case,
46    we don't want to reenter it.  */
47 static bool df_in_progress = false;
48
49 /* Instructions that have been marked but whose dependencies have not
50    yet been processed.  */
51 static VEC(rtx,heap) *worklist;
52
53 /* Bitmap of instructions marked as needed indexed by INSN_UID.  */
54 static sbitmap marked;
55
56 /* Bitmap obstacks used for block processing by the fast algorithm.  */
57 static bitmap_obstack dce_blocks_bitmap_obstack;
58 static bitmap_obstack dce_tmp_bitmap_obstack;
59
60
61 /* A subroutine for which BODY is part of the instruction being tested;
62    either the top-level pattern, or an element of a PARALLEL.  The
63    instruction is known not to be a bare USE or CLOBBER.  */
64
65 static bool
66 deletable_insn_p_1 (rtx body)
67 {
68   switch (GET_CODE (body))
69     {
70     case PREFETCH:
71     case TRAP_IF:
72       /* The UNSPEC case was added here because the ia-64 claims that
73          USEs do not work after reload and generates UNSPECS rather
74          than USEs.  Since dce is run after reload we need to avoid
75          deleting these even if they are dead.  If it turns out that
76          USEs really do work after reload, the ia-64 should be
77          changed, and the UNSPEC case can be removed.  */
78     case UNSPEC:
79       return false;
80
81     default:
82       if (volatile_refs_p (body))
83         return false;
84
85       if (flag_non_call_exceptions && may_trap_p (body))
86         return false;
87
88       return true;
89     }
90 }
91
92
93 /* Return true if INSN is a normal instruction that can be deleted by
94    the DCE pass.  */
95
96 static bool
97 deletable_insn_p (rtx insn, bool fast)
98 {
99   rtx body, x;
100   int i;
101
102   if (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 true;
115
116   if (!NONJUMP_INSN_P (insn))
117     return false;
118
119   body = PATTERN (insn);
120   switch (GET_CODE (body))
121     {
122     case USE:
123       return false;
124
125     case CLOBBER:
126       if (fast)
127         {
128           /* A CLOBBER of a dead pseudo register serves no purpose.
129              That is not necessarily true for hard registers until
130              after reload.  */
131           x = XEXP (body, 0);
132           return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);
133         }
134       else
135         /* Because of the way that use-def chains are built, it is not
136            possible to tell if the clobber is dead because it can
137            never be the target of a use-def chain.  */
138         return false;
139
140     case PARALLEL:
141       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
142         if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))
143           return false;
144       return true;
145
146     default:
147       return deletable_insn_p_1 (body);
148     }
149 }
150
151
152 /* Return true if INSN has been marked as needed.  */
153
154 static inline int
155 marked_insn_p (rtx insn)
156 {
157   if (insn)
158     return TEST_BIT (marked, INSN_UID (insn));
159   else 
160     /* Artificial defs are always needed and they do not have an
161        insn.  */
162     return true;
163 }
164
165
166 /* If INSN has not yet been marked as needed, mark it now, and add it to
167    the worklist.  */
168
169 static void
170 mark_insn (rtx insn, bool fast)
171 {
172   if (!marked_insn_p (insn))
173     {
174       if (!fast)
175         VEC_safe_push (rtx, heap, worklist, insn);
176       SET_BIT (marked, INSN_UID (insn));
177       if (dump_file)
178         fprintf (dump_file, "  Adding insn %d to worklist\n", INSN_UID (insn));
179     }
180 }
181
182
183 /* A note_stores callback used by mark_nonreg_stores.  DATA is the
184    instruction containing DEST.  */
185
186 static void
187 mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data)
188 {
189   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
190     mark_insn ((rtx) data, true);
191 }
192
193
194 /* A note_stores callback used by mark_nonreg_stores.  DATA is the
195    instruction containing DEST.  */
196
197 static void
198 mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)
199 {
200   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
201     mark_insn ((rtx) data, false);
202 }
203
204
205 /* Mark INSN if BODY stores to a non-register destination.  */
206
207 static void
208 mark_nonreg_stores (rtx body, rtx insn, bool fast)
209 {
210   if (fast)
211     note_stores (body, mark_nonreg_stores_1, insn);
212   else
213     note_stores (body, mark_nonreg_stores_2, insn);
214 }
215
216
217 /* Return true if the entire libcall sequence starting at INSN is dead.
218    NOTE is the REG_LIBCALL note attached to INSN.
219
220    A libcall sequence is a block of insns with no side-effects, i.e.
221    that is only used for its return value.  The terminology derives
222    from that of a call, but a libcall sequence need not contain one.
223    It is only defined by a pair of REG_LIBCALL/REG_RETVAL notes.
224
225    From a dataflow viewpoint, a libcall sequence has the property that
226    no UD chain can enter it from the outside.  As a consequence, if a
227    libcall sequence has a dead return value, it is effectively dead.
228    This is both enforced by CSE (cse_extended_basic_block) and relied
229    upon by delete_trivially_dead_insns.
230
231    However, in practice, the return value business is a tricky one and
232    only checking the liveness of the last insn is not sufficient to
233    decide whether the whole sequence is dead (e.g. PR middle-end/19551)
234    so we check the liveness of every insn starting from the call.  */
235
236 static bool
237 libcall_dead_p (rtx insn, rtx note)
238 {
239   rtx last = XEXP (note, 0);
240
241   /* Find the call insn.  */
242   while (insn != last && !CALL_P (insn))
243     insn = NEXT_INSN (insn);
244
245   /* If there is none, do nothing special, since ordinary death handling
246      can understand these insns.  */
247   if (!CALL_P (insn))
248     return false;
249
250   /* If this is a call that returns a value via an invisible pointer, the
251      dataflow engine cannot see it so it has been marked unconditionally.
252      Skip it unless it has been made the last insn in the libcall, for
253      example by the combiner, in which case we're left with no easy way
254      of asserting its liveness.  */
255   if (!single_set (insn))
256     {
257       if (insn == last)
258         return false;
259       insn = NEXT_INSN (insn);
260     }
261
262   while (insn != NEXT_INSN (last))
263     {
264       if (INSN_P (insn) && marked_insn_p (insn))
265         return false;
266       insn = NEXT_INSN (insn);
267     }
268
269   return true;
270 }
271
272
273 /* Delete all REG_EQUAL notes of the registers INSN writes, to prevent
274    bad dangling REG_EQUAL notes. */
275
276 static void
277 delete_corresponding_reg_eq_notes (rtx insn)
278 {
279   struct df_ref **def_rec;
280   for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
281     {
282       struct df_ref *def = *def_rec;
283       unsigned int regno = DF_REF_REGNO (def);
284       /* This loop is a little tricky.  We cannot just go down the
285          chain because it is being modified by the actions in the
286          loop.  So we just get the head.  We plan to drain the list
287          anyway.  */
288       while (DF_REG_EQ_USE_CHAIN (regno))
289         {
290           struct df_ref *eq_use = DF_REG_EQ_USE_CHAIN (regno);
291           rtx noted_insn = DF_REF_INSN (eq_use);
292           rtx note = find_reg_note (noted_insn, REG_EQUAL, NULL_RTX);
293           if (!note)
294             note = find_reg_note (noted_insn, REG_EQUIV, NULL_RTX);
295
296           /* This assert is generally triggered when someone deletes a
297              REG_EQUAL or REG_EQUIV note by hacking the list manually
298              rather than calling remove_note.  */
299           gcc_assert (note);
300           remove_note (noted_insn, note);
301         }
302     }
303 }
304
305
306 /* Delete every instruction that hasn't been marked.  */
307
308 static void
309 delete_unmarked_insns (void)
310 {
311   basic_block bb;
312   rtx insn, next;
313   bool must_clean = false;
314
315   FOR_EACH_BB (bb)
316     FOR_BB_INSNS_SAFE (bb, insn, next)
317       if (INSN_P (insn))
318         {
319           rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
320
321           /* Always delete no-op moves.  */
322           if (noop_move_p (insn))
323             ;
324
325           /* Try to delete libcall sequences as a whole.  */
326           else if (note && libcall_dead_p (insn, note))
327             {
328               rtx last = XEXP (note, 0);
329
330               if (!dbg_cnt (dce))
331                 continue;
332
333               if (dump_file)
334                 fprintf (dump_file, "DCE: Deleting libcall %d-%d\n",
335                          INSN_UID (insn), INSN_UID (last));
336
337               next = NEXT_INSN (last);
338               delete_insn_chain_and_edges (insn, last);
339               continue;
340             }
341
342           /* Otherwise rely only on the DCE algorithm.  */
343           else if (marked_insn_p (insn))
344             continue;
345
346           if (!dbg_cnt (dce))
347             continue;
348
349           if (dump_file)
350             fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
351
352           /* Before we delete the insn we have to delete REG_EQUAL notes
353              for the destination regs in order to avoid dangling notes.  */
354           delete_corresponding_reg_eq_notes (insn);
355
356           /* If we're about to delete the first insn of a libcall, then
357              move the REG_LIBCALL note to the next real insn and update
358              the REG_RETVAL note.  */
359           if (note && (XEXP (note, 0) != insn))
360             {
361               rtx new_libcall_insn = next_real_insn (insn);
362               rtx retval_note = find_reg_note (XEXP (note, 0),
363                                                REG_RETVAL, NULL_RTX);
364               /* If the RETVAL and LIBCALL notes would land on the same
365                  insn just remove them.  */
366               if (XEXP (note, 0) == new_libcall_insn)
367                 remove_note (new_libcall_insn, retval_note);
368               else
369                 {
370                   REG_NOTES (new_libcall_insn)
371                     = gen_rtx_INSN_LIST (REG_LIBCALL, XEXP (note, 0),
372                                          REG_NOTES (new_libcall_insn));
373                   XEXP (retval_note, 0) = new_libcall_insn;
374                 }
375             }
376
377           /* If the insn contains a REG_RETVAL note and is dead, but the
378              libcall as a whole is not dead, then we want to remove the
379              insn, but not the whole libcall sequence.  However, we also
380              need to remove the dangling REG_LIBCALL note in order to
381              avoid mismatched notes.  We could find a new location for
382              the REG_RETVAL note, but it hardly seems worth the effort.  */
383           note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
384           if (note && (XEXP (note, 0) != insn))
385             {
386               rtx libcall_note
387                 = find_reg_note (XEXP (note, 0), REG_LIBCALL, NULL_RTX);
388               remove_note (XEXP (note, 0), libcall_note);
389             }
390
391           /* If a pure or const call is deleted, this may make the cfg
392              have unreachable blocks.  We rememeber this and call
393              delete_unreachable_blocks at the end.  */
394           if (CALL_P (insn))
395             must_clean = true;
396
397           /* Now delete the insn.  */
398           delete_insn_and_edges (insn);
399         }
400
401   /* Deleted a pure or const call.  */
402   if (must_clean)
403     delete_unreachable_blocks ();
404 }
405
406
407 /* Helper function for prescan_insns_for_dce: prescan the entire libcall
408    sequence starting at INSN and return the insn following the libcall.
409    NOTE is the REG_LIBCALL note attached to INSN.  */
410
411 static rtx
412 prescan_libcall_for_dce (rtx insn, rtx note, bool fast)
413 {
414   rtx last = XEXP (note, 0);
415
416   /* A libcall is never necessary on its own but we need to mark the stores
417      to a non-register destination.  */
418   while (insn != last && !CALL_P (insn))
419     {
420       if (INSN_P (insn))
421         mark_nonreg_stores (PATTERN (insn), insn, fast);
422       insn = NEXT_INSN (insn);
423     }
424
425   /* If this is a call that returns a value via an invisible pointer, the
426      dataflow engine cannot see it so it has to be marked unconditionally.  */
427   if (CALL_P (insn) && !single_set (insn))
428     {
429       mark_insn (insn, fast);
430       insn = NEXT_INSN (insn);
431     }
432
433   while (insn != NEXT_INSN (last))
434     {
435       if (INSN_P (insn))
436         mark_nonreg_stores (PATTERN (insn), insn, fast);
437       insn = NEXT_INSN (insn);
438     }
439
440   return insn;
441 }
442
443
444 /* Go through the instructions and mark those whose necessity is not
445    dependent on inter-instruction information.  Make sure all other
446    instructions are not marked.  */
447
448 static void
449 prescan_insns_for_dce (bool fast)
450 {
451   basic_block bb;
452   rtx insn, next;
453   
454   if (dump_file)
455     fprintf (dump_file, "Finding needed instructions:\n");
456   
457   FOR_EACH_BB (bb)
458     FOR_BB_INSNS_SAFE (bb, insn, next)
459       if (INSN_P (insn))
460         {
461           rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
462           if (note)
463             next = prescan_libcall_for_dce (insn, note, fast);
464           else if (deletable_insn_p (insn, fast))
465             mark_nonreg_stores (PATTERN (insn), insn, fast);
466           else
467             mark_insn (insn, fast);
468         }
469
470   if (dump_file)
471     fprintf (dump_file, "Finished finding needed instructions:\n");
472 }
473
474
475 /* UD-based DSE routines. */
476
477 /* Mark instructions that define artificially-used registers, such as
478    the frame pointer and the stack pointer.  */
479
480 static void
481 mark_artificial_uses (void)
482 {
483   basic_block bb;
484   struct df_link *defs;
485   struct df_ref **use_rec;
486
487   FOR_ALL_BB (bb)
488     {
489       for (use_rec = df_get_artificial_uses (bb->index); 
490            *use_rec; use_rec++)
491         for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
492           mark_insn (DF_REF_INSN (defs->ref), false);
493     }
494 }
495
496
497 /* Mark every instruction that defines a register value that INSN uses.  */
498
499 static void
500 mark_reg_dependencies (rtx insn)
501 {
502   struct df_link *defs;
503   struct df_ref **use_rec;
504
505   for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
506     {
507       struct df_ref *use = *use_rec;
508       if (dump_file)
509         {
510           fprintf (dump_file, "Processing use of ");
511           print_simple_rtl (dump_file, DF_REF_REG (use));
512           fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
513         }
514       for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
515         mark_insn (DF_REF_INSN (defs->ref), false);
516     }
517 }
518
519
520 /* Initialize global variables for a new DCE pass.  */
521
522 static void
523 init_dce (bool fast)
524 {
525   if (!df_in_progress)
526     {
527       if (!fast)
528         df_chain_add_problem (DF_UD_CHAIN);
529       df_analyze ();
530     }
531
532   if (dump_file)
533     df_dump (dump_file);
534
535   if (fast)
536     {
537       bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
538       bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
539     }
540
541   marked = sbitmap_alloc (get_max_uid () + 1);
542   sbitmap_zero (marked);
543 }
544
545
546 /* Free the data allocated by init_dce.  */
547
548 static void
549 fini_dce (bool fast)
550 {
551   sbitmap_free (marked);
552
553   if (fast)
554     {
555       bitmap_obstack_release (&dce_blocks_bitmap_obstack);
556       bitmap_obstack_release (&dce_tmp_bitmap_obstack);
557     }
558 }
559
560
561 /* UD-chain based DCE.  */
562
563 static unsigned int
564 rest_of_handle_ud_dce (void)
565 {
566   rtx insn;
567
568   init_dce (false);
569
570   prescan_insns_for_dce (false);
571   mark_artificial_uses ();
572   while (VEC_length (rtx, worklist) > 0)
573     {
574       insn = VEC_pop (rtx, worklist);
575       mark_reg_dependencies (insn);
576     }
577
578   /* Before any insns are deleted, we must remove the chains since
579      they are not bidirectional.  */
580   df_remove_problem (df_chain);
581   delete_unmarked_insns ();
582
583   fini_dce (false);
584   return 0;
585 }
586
587
588 static bool
589 gate_ud_dce (void)
590 {
591   return optimize > 1 && flag_dce
592     && dbg_cnt (dce_ud);
593 }
594
595 struct rtl_opt_pass pass_ud_rtl_dce =
596 {
597  {
598   RTL_PASS,
599   "dce",                                /* name */
600   gate_ud_dce,                        /* gate */
601   rest_of_handle_ud_dce,              /* execute */
602   NULL,                                 /* sub */
603   NULL,                                 /* next */
604   0,                                    /* static_pass_number */
605   TV_DCE,                               /* tv_id */
606   0,                                    /* properties_required */
607   0,                                    /* properties_provided */
608   0,                                    /* properties_destroyed */
609   0,                                    /* todo_flags_start */
610   TODO_dump_func |
611   TODO_df_finish | TODO_verify_rtl_sharing |
612   TODO_ggc_collect                     /* todo_flags_finish */
613  }
614 };
615
616
617 /* -------------------------------------------------------------------------
618    Fast DCE functions
619    ------------------------------------------------------------------------- */
620
621 /* Process basic block BB.  Return true if the live_in set has
622    changed. REDO_OUT is true if the info at the bottom of the block
623    needs to be recalculated before starting.  AU is the proper set of
624    artificial uses. */
625
626 static bool
627 byte_dce_process_block (basic_block bb, bool redo_out, bitmap au)
628 {
629   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
630   rtx insn;
631   bool block_changed;
632   struct df_ref **def_rec;
633
634   if (redo_out)
635     {
636       /* Need to redo the live_out set of this block if when one of
637          the succs of this block has had a change in it live in
638          set.  */
639       edge e;
640       edge_iterator ei;
641       df_confluence_function_n con_fun_n = df_byte_lr->problem->con_fun_n;
642       bitmap_clear (DF_BYTE_LR_OUT (bb));
643       FOR_EACH_EDGE (e, ei, bb->succs)
644         (*con_fun_n) (e);
645     }
646
647   if (dump_file)
648     {
649       fprintf (dump_file, "processing block %d live out = ", bb->index);
650       df_print_byte_regset (dump_file, DF_BYTE_LR_OUT (bb));
651     }
652
653   bitmap_copy (local_live, DF_BYTE_LR_OUT (bb));
654
655   df_byte_lr_simulate_artificial_refs_at_end (bb, local_live);
656
657   FOR_BB_INSNS_REVERSE (bb, insn)
658     if (INSN_P (insn))
659       {
660         /* The insn is needed if there is someone who uses the output.  */
661         for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
662           {
663             struct df_ref *def = *def_rec;
664             unsigned int last;
665             unsigned int dregno = DF_REF_REGNO (def);
666             unsigned int start = df_byte_lr_get_regno_start (dregno);
667             unsigned int len = df_byte_lr_get_regno_len (dregno);
668
669             unsigned int sb;
670             unsigned int lb;
671             /* This is one of the only places where DF_MM_MAY should
672                be used for defs.  Need to make sure that we are
673                checking for all of the bits that may be used.  */
674
675             if (!df_compute_accessed_bytes (def, DF_MM_MAY, &sb, &lb))
676               {
677                 start += sb;
678                 len = lb - sb;
679               }
680
681             if (bitmap_bit_p (au, dregno))
682               {
683                 mark_insn (insn, true);
684                 goto quickexit;
685               }
686             
687             last = start + len;
688             while (start < last)
689               if (bitmap_bit_p (local_live, start++))
690                 {
691                   mark_insn (insn, true);
692                   goto quickexit;
693                 }
694           }
695         
696       quickexit: 
697         
698         /* No matter if the instruction is needed or not, we remove
699            any regno in the defs from the live set.  */
700         df_byte_lr_simulate_defs (insn, local_live);
701
702         /* On the other hand, we do not allow the dead uses to set
703            anything in local_live.  */
704         if (marked_insn_p (insn))
705           df_byte_lr_simulate_uses (insn, local_live);
706
707         if (dump_file)
708           {
709             fprintf (dump_file, "finished processing insn %d live out = ", 
710                      INSN_UID (insn));
711             df_print_byte_regset (dump_file, local_live);
712           }
713       }
714   
715   df_byte_lr_simulate_artificial_refs_at_top (bb, local_live);
716
717   block_changed = !bitmap_equal_p (local_live, DF_BYTE_LR_IN (bb));
718   if (block_changed)
719     bitmap_copy (DF_BYTE_LR_IN (bb), local_live);
720   BITMAP_FREE (local_live);
721   return block_changed;
722 }
723
724
725 /* Process basic block BB.  Return true if the live_in set has
726    changed. REDO_OUT is true if the info at the bottom of the block
727    needs to be recalculated before starting.  AU is the proper set of
728    artificial uses. */
729
730 static bool
731 dce_process_block (basic_block bb, bool redo_out, bitmap au)
732 {
733   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
734   rtx insn;
735   bool block_changed;
736   struct df_ref **def_rec;
737
738   if (redo_out)
739     {
740       /* Need to redo the live_out set of this block if when one of
741          the succs of this block has had a change in it live in
742          set.  */
743       edge e;
744       edge_iterator ei;
745       df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
746       bitmap_clear (DF_LR_OUT (bb));
747       FOR_EACH_EDGE (e, ei, bb->succs)
748         (*con_fun_n) (e);
749     }
750
751   if (dump_file)
752     {
753       fprintf (dump_file, "processing block %d live out = ", bb->index);
754       df_print_regset (dump_file, DF_LR_OUT (bb));
755     }
756
757   bitmap_copy (local_live, DF_LR_OUT (bb));
758
759   df_simulate_artificial_refs_at_end (bb, local_live);
760
761   FOR_BB_INSNS_REVERSE (bb, insn)
762     if (INSN_P (insn))
763       {
764         bool needed = false;
765
766         /* The insn is needed if there is someone who uses the output.  */
767         for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
768           if (bitmap_bit_p (local_live, DF_REF_REGNO (*def_rec))
769               || bitmap_bit_p (au, DF_REF_REGNO (*def_rec)))
770             {
771               needed = true;
772               break;
773             }
774             
775         if (needed)
776           mark_insn (insn, true);
777         
778         /* No matter if the instruction is needed or not, we remove
779            any regno in the defs from the live set.  */
780         df_simulate_defs (insn, local_live);
781
782         /* On the other hand, we do not allow the dead uses to set
783            anything in local_live.  */
784         if (marked_insn_p (insn))
785           df_simulate_uses (insn, local_live);
786       }
787   
788   df_simulate_artificial_refs_at_top (bb, local_live);
789
790   block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
791   if (block_changed)
792     bitmap_copy (DF_LR_IN (bb), local_live);
793
794   BITMAP_FREE (local_live);
795   return block_changed;
796 }
797
798
799 /* Perform fast DCE once initialization is done.  If BYTE_LEVEL is
800    true, use the byte level dce, otherwise do it at the pseudo
801    level.  */
802
803 static void
804 fast_dce (bool byte_level)
805 {
806   int *postorder = df_get_postorder (DF_BACKWARD);
807   int n_blocks = df_get_n_blocks (DF_BACKWARD);
808   /* The set of blocks that have been seen on this iteration.  */
809   bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
810   /* The set of blocks that need to have the out vectors reset because
811      the in of one of their successors has changed.  */
812   bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
813   bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
814   bool global_changed = true;
815
816   /* These regs are considered always live so if they end up dying
817      because of some def, we need to bring the back again.  Calling
818      df_simulate_fixup_sets has the disadvantage of calling
819      bb_has_eh_pred once per insn, so we cache the information
820      here.  */
821   bitmap au = df->regular_block_artificial_uses;
822   bitmap au_eh = df->eh_block_artificial_uses;
823   int i;
824
825   prescan_insns_for_dce (true);
826
827   for (i = 0; i < n_blocks; i++)
828     bitmap_set_bit (all_blocks, postorder[i]);
829
830   while (global_changed)
831     {
832       global_changed = false;
833
834       for (i = 0; i < n_blocks; i++)
835         {
836           int index = postorder[i];
837           basic_block bb = BASIC_BLOCK (index);
838           bool local_changed;
839
840           if (index < NUM_FIXED_BLOCKS)
841             {
842               bitmap_set_bit (processed, index);
843               continue;
844             }
845
846           if (byte_level)
847             local_changed 
848               = byte_dce_process_block (bb, bitmap_bit_p (redo_out, index),
849                                           bb_has_eh_pred (bb) ? au_eh : au);
850           else
851             local_changed 
852               = dce_process_block (bb, bitmap_bit_p (redo_out, index),
853                                    bb_has_eh_pred (bb) ? au_eh : au);
854           bitmap_set_bit (processed, index);
855           
856           if (local_changed)
857             {
858               edge e;
859               edge_iterator ei;
860               FOR_EACH_EDGE (e, ei, bb->preds)
861                 if (bitmap_bit_p (processed, e->src->index))
862                   /* Be tricky about when we need to iterate the
863                      analysis.  We only have redo the analysis if the
864                      bitmaps change at the top of a block that is the
865                      entry to a loop.  */
866                   global_changed = true;
867                 else
868                   bitmap_set_bit (redo_out, e->src->index);
869             }
870         }
871       
872       if (global_changed)
873         {
874           /* Turn off the RUN_DCE flag to prevent recursive calls to
875              dce.  */
876           int old_flag = df_clear_flags (DF_LR_RUN_DCE);
877
878           /* So something was deleted that requires a redo.  Do it on
879              the cheap.  */
880           delete_unmarked_insns ();
881           sbitmap_zero (marked);
882           bitmap_clear (processed);
883           bitmap_clear (redo_out);
884           
885           /* We do not need to rescan any instructions.  We only need
886              to redo the dataflow equations for the blocks that had a
887              change at the top of the block.  Then we need to redo the
888              iteration.  */ 
889           if (byte_level)
890             df_analyze_problem (df_byte_lr, all_blocks, postorder, n_blocks);
891           else
892             df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
893
894           if (old_flag & DF_LR_RUN_DCE)
895             df_set_flags (DF_LR_RUN_DCE);
896
897           prescan_insns_for_dce (true);
898         }
899     }
900
901   delete_unmarked_insns ();
902
903   BITMAP_FREE (processed);
904   BITMAP_FREE (redo_out);
905   BITMAP_FREE (all_blocks);
906 }
907
908
909 /* Fast register level DCE.  */
910
911 static unsigned int
912 rest_of_handle_fast_dce (void)
913 {
914   init_dce (true);
915   fast_dce (false);
916   fini_dce (true);
917   return 0;
918 }
919
920
921 /* Fast byte level DCE.  */
922
923 static unsigned int
924 rest_of_handle_fast_byte_dce (void)
925 {
926   df_byte_lr_add_problem ();
927   init_dce (true);
928   fast_dce (true);
929   fini_dce (true);
930   return 0;
931 }
932
933
934 /* This is an internal call that is used by the df live register
935    problem to run fast dce as a side effect of creating the live
936    information.  The stack is organized so that the lr problem is run,
937    this pass is run, which updates the live info and the df scanning
938    info, and then returns to allow the rest of the problems to be run.
939
940    This can be called by elsewhere but it will not update the bit
941    vectors for any other problems than LR.  */
942
943 void
944 run_fast_df_dce (void)
945 {
946   if (flag_dce)
947     {
948       /* If dce is able to delete something, it has to happen
949          immediately.  Otherwise there will be problems handling the
950          eq_notes.  */
951       enum df_changeable_flags old_flags 
952         = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
953       
954       df_in_progress = true;
955       rest_of_handle_fast_dce ();
956       df_in_progress = false;
957
958       df_set_flags (old_flags);
959     }
960 }
961
962
963 /* Run a fast DCE pass.  */
964
965 void
966 run_fast_dce (void)
967 {
968   if (flag_dce)
969     rest_of_handle_fast_dce ();
970 }
971
972
973 static bool
974 gate_fast_dce (void)
975 {
976   return optimize > 0 && flag_dce
977     && dbg_cnt (dce_fast);
978 }
979
980 struct rtl_opt_pass pass_fast_rtl_dce =
981 {
982  {
983   RTL_PASS,
984   "dce",                                /* name */
985   gate_fast_dce,                        /* gate */
986   rest_of_handle_fast_dce,              /* execute */
987   NULL,                                 /* sub */
988   NULL,                                 /* next */
989   0,                                    /* static_pass_number */
990   TV_DCE,                               /* tv_id */
991   0,                                    /* properties_required */
992   0,                                    /* properties_provided */
993   0,                                    /* properties_destroyed */
994   0,                                    /* todo_flags_start */
995   TODO_dump_func |
996   TODO_df_finish | TODO_verify_rtl_sharing |
997   TODO_ggc_collect                      /* todo_flags_finish */
998  }
999 };
1000
1001 struct rtl_opt_pass pass_fast_rtl_byte_dce =
1002 {
1003  {
1004   RTL_PASS,
1005   "byte-dce",                           /* name */
1006   gate_fast_dce,                        /* gate */
1007   rest_of_handle_fast_byte_dce,         /* execute */
1008   NULL,                                 /* sub */
1009   NULL,                                 /* next */
1010   0,                                    /* static_pass_number */
1011   TV_DCE,                               /* tv_id */
1012   0,                                    /* properties_required */
1013   0,                                    /* properties_provided */
1014   0,                                    /* properties_destroyed */
1015   0,                                    /* todo_flags_start */
1016   TODO_dump_func |
1017   TODO_df_finish | TODO_verify_rtl_sharing |
1018   TODO_ggc_collect                      /* todo_flags_finish */
1019  }
1020 };