1 /* RTL dead code elimination.
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
29 #include "hard-reg-set.h"
36 #include "tree-pass.h"
39 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
42 /* -------------------------------------------------------------------------
43 Core mark/delete routines
44 ------------------------------------------------------------------------- */
46 /* True if we are invoked while the df engine is running; in this case,
47 we don't want to reenter it. */
48 static bool df_in_progress
= false;
50 /* True if we are allowed to alter the CFG in this pass. */
51 static bool can_alter_cfg
= false;
53 /* Instructions that have been marked but whose dependencies have not
54 yet been processed. */
55 static VEC(rtx
,heap
) *worklist
;
57 /* Bitmap of instructions marked as needed indexed by INSN_UID. */
58 static sbitmap marked
;
60 /* Bitmap obstacks used for block processing by the fast algorithm. */
61 static bitmap_obstack dce_blocks_bitmap_obstack
;
62 static bitmap_obstack dce_tmp_bitmap_obstack
;
64 static bool find_call_stack_args (rtx
, bool, bool, bitmap
);
66 /* A subroutine for which BODY is part of the instruction being tested;
67 either the top-level pattern, or an element of a PARALLEL. The
68 instruction is known not to be a bare USE or CLOBBER. */
71 deletable_insn_p_1 (rtx body
)
73 switch (GET_CODE (body
))
77 /* The UNSPEC case was added here because the ia-64 claims that
78 USEs do not work after reload and generates UNSPECS rather
79 than USEs. Since dce is run after reload we need to avoid
80 deleting these even if they are dead. If it turns out that
81 USEs really do work after reload, the ia-64 should be
82 changed, and the UNSPEC case can be removed. */
87 return !volatile_refs_p (body
);
92 /* Return true if INSN is a normal instruction that can be deleted by
96 deletable_insn_p (rtx insn
, bool fast
, bitmap arg_stores
)
102 /* We cannot delete calls inside of the recursive dce because
103 this may cause basic blocks to be deleted and this messes up
104 the rest of the stack of optimization passes. */
106 /* We cannot delete pure or const sibling calls because it is
107 hard to see the result. */
108 && (!SIBLING_CALL_P (insn
))
109 /* We can delete dead const or pure calls as long as they do not
111 && (RTL_CONST_OR_PURE_CALL_P (insn
)
112 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)))
113 return find_call_stack_args (insn
, false, fast
, arg_stores
);
115 /* Don't delete jumps, notes and the like. */
116 if (!NONJUMP_INSN_P (insn
))
119 /* Don't delete insns that may throw if we cannot do so. */
120 if (!(cfun
->can_delete_dead_exceptions
&& can_alter_cfg
)
121 && !insn_nothrow_p (insn
))
124 body
= PATTERN (insn
);
125 switch (GET_CODE (body
))
134 /* A CLOBBER of a dead pseudo register serves no purpose.
135 That is not necessarily true for hard registers until
138 return REG_P (x
) && (!HARD_REGISTER_P (x
) || reload_completed
);
141 /* Because of the way that use-def chains are built, it is not
142 possible to tell if the clobber is dead because it can
143 never be the target of a use-def chain. */
147 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; i
--)
148 if (!deletable_insn_p_1 (XVECEXP (body
, 0, i
)))
153 return deletable_insn_p_1 (body
);
158 /* Return true if INSN has been marked as needed. */
161 marked_insn_p (rtx insn
)
163 /* Artificial defs are always needed and they do not have an insn.
164 We should never see them here. */
166 return TEST_BIT (marked
, INSN_UID (insn
));
170 /* If INSN has not yet been marked as needed, mark it now, and add it to
174 mark_insn (rtx insn
, bool fast
)
176 if (!marked_insn_p (insn
))
179 VEC_safe_push (rtx
, heap
, worklist
, insn
);
180 SET_BIT (marked
, INSN_UID (insn
));
182 fprintf (dump_file
, " Adding insn %d to worklist\n", INSN_UID (insn
));
185 && !SIBLING_CALL_P (insn
)
186 && (RTL_CONST_OR_PURE_CALL_P (insn
)
187 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)))
188 find_call_stack_args (insn
, true, fast
, NULL
);
193 /* A note_stores callback used by mark_nonreg_stores. DATA is the
194 instruction containing DEST. */
197 mark_nonreg_stores_1 (rtx dest
, const_rtx pattern
, void *data
)
199 if (GET_CODE (pattern
) != CLOBBER
&& !REG_P (dest
))
200 mark_insn ((rtx
) data
, true);
204 /* A note_stores callback used by mark_nonreg_stores. DATA is the
205 instruction containing DEST. */
208 mark_nonreg_stores_2 (rtx dest
, const_rtx pattern
, void *data
)
210 if (GET_CODE (pattern
) != CLOBBER
&& !REG_P (dest
))
211 mark_insn ((rtx
) data
, false);
215 /* Mark INSN if BODY stores to a non-register destination. */
218 mark_nonreg_stores (rtx body
, rtx insn
, bool fast
)
221 note_stores (body
, mark_nonreg_stores_1
, insn
);
223 note_stores (body
, mark_nonreg_stores_2
, insn
);
227 /* Return true if store to MEM, starting OFF bytes from stack pointer,
228 is a call argument store, and clear corresponding bits from SP_BYTES
232 check_argument_store (rtx mem
, HOST_WIDE_INT off
, HOST_WIDE_INT min_sp_off
,
233 HOST_WIDE_INT max_sp_off
, bitmap sp_bytes
)
236 for (byte
= off
; byte
< off
+ GET_MODE_SIZE (GET_MODE (mem
)); byte
++)
238 if (byte
< min_sp_off
239 || byte
>= max_sp_off
240 || !bitmap_clear_bit (sp_bytes
, byte
- min_sp_off
))
247 /* Try to find all stack stores of CALL_INSN arguments if
248 ACCUMULATE_OUTGOING_ARGS. If all stack stores have been found
249 and it is therefore safe to eliminate the call, return true,
250 otherwise return false. This function should be first called
251 with DO_MARK false, and only when the CALL_INSN is actually
252 going to be marked called again with DO_MARK true. */
255 find_call_stack_args (rtx call_insn
, bool do_mark
, bool fast
,
258 rtx p
, insn
, prev_insn
;
260 HOST_WIDE_INT min_sp_off
, max_sp_off
;
263 gcc_assert (CALL_P (call_insn
));
264 if (!ACCUMULATE_OUTGOING_ARGS
)
269 gcc_assert (arg_stores
);
270 bitmap_clear (arg_stores
);
273 min_sp_off
= INTTYPE_MAXIMUM (HOST_WIDE_INT
);
276 /* First determine the minimum and maximum offset from sp for
278 for (p
= CALL_INSN_FUNCTION_USAGE (call_insn
); p
; p
= XEXP (p
, 1))
279 if (GET_CODE (XEXP (p
, 0)) == USE
280 && MEM_P (XEXP (XEXP (p
, 0), 0)))
282 rtx mem
= XEXP (XEXP (p
, 0), 0), addr
;
283 HOST_WIDE_INT off
= 0, size
;
284 if (!MEM_SIZE_KNOWN_P (mem
))
286 size
= MEM_SIZE (mem
);
287 addr
= XEXP (mem
, 0);
288 if (GET_CODE (addr
) == PLUS
289 && REG_P (XEXP (addr
, 0))
290 && CONST_INT_P (XEXP (addr
, 1)))
292 off
= INTVAL (XEXP (addr
, 1));
293 addr
= XEXP (addr
, 0);
295 if (addr
!= stack_pointer_rtx
)
299 /* If not fast, use chains to see if addr wasn't set to
304 struct df_link
*defs
;
307 for (use_rec
= DF_INSN_USES (call_insn
); *use_rec
; use_rec
++)
308 if (rtx_equal_p (addr
, DF_REF_REG (*use_rec
)))
311 if (*use_rec
== NULL
)
314 for (defs
= DF_REF_CHAIN (*use_rec
); defs
; defs
= defs
->next
)
315 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
321 set
= single_set (DF_REF_INSN (defs
->ref
));
325 if (GET_CODE (SET_SRC (set
)) != PLUS
326 || XEXP (SET_SRC (set
), 0) != stack_pointer_rtx
327 || !CONST_INT_P (XEXP (SET_SRC (set
), 1)))
330 off
+= INTVAL (XEXP (SET_SRC (set
), 1));
335 min_sp_off
= MIN (min_sp_off
, off
);
336 max_sp_off
= MAX (max_sp_off
, off
+ size
);
339 if (min_sp_off
>= max_sp_off
)
341 sp_bytes
= BITMAP_ALLOC (NULL
);
343 /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
344 which contain arguments. Checking has been done in the previous
346 for (p
= CALL_INSN_FUNCTION_USAGE (call_insn
); p
; p
= XEXP (p
, 1))
347 if (GET_CODE (XEXP (p
, 0)) == USE
348 && MEM_P (XEXP (XEXP (p
, 0), 0)))
350 rtx mem
= XEXP (XEXP (p
, 0), 0), addr
;
351 HOST_WIDE_INT off
= 0, byte
;
352 addr
= XEXP (mem
, 0);
353 if (GET_CODE (addr
) == PLUS
354 && REG_P (XEXP (addr
, 0))
355 && CONST_INT_P (XEXP (addr
, 1)))
357 off
= INTVAL (XEXP (addr
, 1));
358 addr
= XEXP (addr
, 0);
360 if (addr
!= stack_pointer_rtx
)
363 struct df_link
*defs
;
366 for (use_rec
= DF_INSN_USES (call_insn
); *use_rec
; use_rec
++)
367 if (rtx_equal_p (addr
, DF_REF_REG (*use_rec
)))
370 for (defs
= DF_REF_CHAIN (*use_rec
); defs
; defs
= defs
->next
)
371 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
374 set
= single_set (DF_REF_INSN (defs
->ref
));
375 off
+= INTVAL (XEXP (SET_SRC (set
), 1));
377 for (byte
= off
; byte
< off
+ MEM_SIZE (mem
); byte
++)
379 if (!bitmap_set_bit (sp_bytes
, byte
- min_sp_off
))
384 /* Walk backwards, looking for argument stores. The search stops
385 when seeing another call, sp adjustment or memory store other than
388 for (insn
= PREV_INSN (call_insn
); insn
; insn
= prev_insn
)
393 if (insn
== BB_HEAD (BLOCK_FOR_INSN (call_insn
)))
394 prev_insn
= NULL_RTX
;
396 prev_insn
= PREV_INSN (insn
);
401 if (!NONDEBUG_INSN_P (insn
))
404 set
= single_set (insn
);
405 if (!set
|| SET_DEST (set
) == stack_pointer_rtx
)
408 if (!MEM_P (SET_DEST (set
)))
411 mem
= SET_DEST (set
);
412 addr
= XEXP (mem
, 0);
414 if (GET_CODE (addr
) == PLUS
415 && REG_P (XEXP (addr
, 0))
416 && CONST_INT_P (XEXP (addr
, 1)))
418 off
= INTVAL (XEXP (addr
, 1));
419 addr
= XEXP (addr
, 0);
421 if (addr
!= stack_pointer_rtx
)
428 struct df_link
*defs
;
431 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
432 if (rtx_equal_p (addr
, DF_REF_REG (*use_rec
)))
435 if (*use_rec
== NULL
)
438 for (defs
= DF_REF_CHAIN (*use_rec
); defs
; defs
= defs
->next
)
439 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
445 set
= single_set (DF_REF_INSN (defs
->ref
));
449 if (GET_CODE (SET_SRC (set
)) != PLUS
450 || XEXP (SET_SRC (set
), 0) != stack_pointer_rtx
451 || !CONST_INT_P (XEXP (SET_SRC (set
), 1)))
454 off
+= INTVAL (XEXP (SET_SRC (set
), 1));
460 if (GET_MODE_SIZE (GET_MODE (mem
)) == 0
461 || !check_argument_store (mem
, off
, min_sp_off
,
462 max_sp_off
, sp_bytes
))
465 if (!deletable_insn_p (insn
, fast
, NULL
))
469 mark_insn (insn
, fast
);
471 bitmap_set_bit (arg_stores
, INSN_UID (insn
));
473 if (bitmap_empty_p (sp_bytes
))
480 BITMAP_FREE (sp_bytes
);
481 if (!ret
&& arg_stores
)
482 bitmap_clear (arg_stores
);
488 /* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN
492 remove_reg_equal_equiv_notes_for_defs (rtx insn
)
496 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
497 remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (*def_rec
));
500 /* Scan all BBs for debug insns and reset those that reference values
501 defined in unmarked insns. */
504 reset_unmarked_insns_debug_uses (void)
509 FOR_EACH_BB_REVERSE (bb
)
510 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, next
)
511 if (DEBUG_INSN_P (insn
))
515 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
517 df_ref use
= *use_rec
;
518 struct df_link
*defs
;
519 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
522 if (DF_REF_IS_ARTIFICIAL (defs
->ref
))
524 ref_insn
= DF_REF_INSN (defs
->ref
);
525 if (!marked_insn_p (ref_insn
))
530 /* ??? FIXME could we propagate the values assigned to
532 INSN_VAR_LOCATION_LOC (insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
533 df_insn_rescan_debug_internal (insn
);
539 /* Delete every instruction that hasn't been marked. */
542 delete_unmarked_insns (void)
546 bool must_clean
= false;
548 FOR_EACH_BB_REVERSE (bb
)
549 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, next
)
550 if (NONDEBUG_INSN_P (insn
))
552 /* Always delete no-op moves. */
553 if (noop_move_p (insn
))
556 /* Otherwise rely only on the DCE algorithm. */
557 else if (marked_insn_p (insn
))
560 /* Beware that reaching a dbg counter limit here can result
561 in miscompiled file. This occurs when a group of insns
562 must be deleted together, typically because the kept insn
563 depends on the output from the deleted insn. Deleting
564 this insns in reverse order (both at the bb level and
565 when looking at the blocks) minimizes this, but does not
566 eliminate it, since it is possible for the using insn to
567 be top of a block and the producer to be at the bottom of
568 the block. However, in most cases this will only result
569 in an uninitialized use of an insn that is dead anyway.
571 However, there is one rare case that will cause a
572 miscompile: deletion of non-looping pure and constant
573 calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
574 In this case it is possible to remove the call, but leave
575 the argument pushes to the stack. Because of the changes
576 to the stack pointer, this will almost always lead to a
582 fprintf (dump_file
, "DCE: Deleting insn %d\n", INSN_UID (insn
));
584 /* Before we delete the insn we have to remove the REG_EQUAL notes
585 for the destination regs in order to avoid dangling notes. */
586 remove_reg_equal_equiv_notes_for_defs (insn
);
588 /* If a pure or const call is deleted, this may make the cfg
589 have unreachable blocks. We rememeber this and call
590 delete_unreachable_blocks at the end. */
594 /* Now delete the insn. */
595 delete_insn_and_edges (insn
);
598 /* Deleted a pure or const call. */
600 delete_unreachable_blocks ();
604 /* Go through the instructions and mark those whose necessity is not
605 dependent on inter-instruction information. Make sure all other
606 instructions are not marked. */
609 prescan_insns_for_dce (bool fast
)
613 bitmap arg_stores
= NULL
;
616 fprintf (dump_file
, "Finding needed instructions:\n");
618 if (!df_in_progress
&& ACCUMULATE_OUTGOING_ARGS
)
619 arg_stores
= BITMAP_ALLOC (NULL
);
623 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, prev
)
624 if (NONDEBUG_INSN_P (insn
))
626 /* Don't mark argument stores now. They will be marked
627 if needed when the associated CALL is marked. */
628 if (arg_stores
&& bitmap_bit_p (arg_stores
, INSN_UID (insn
)))
630 if (deletable_insn_p (insn
, fast
, arg_stores
))
631 mark_nonreg_stores (PATTERN (insn
), insn
, fast
);
633 mark_insn (insn
, fast
);
635 /* find_call_stack_args only looks at argument stores in the
638 bitmap_clear (arg_stores
);
642 BITMAP_FREE (arg_stores
);
645 fprintf (dump_file
, "Finished finding needed instructions:\n");
649 /* UD-based DSE routines. */
651 /* Mark instructions that define artificially-used registers, such as
652 the frame pointer and the stack pointer. */
655 mark_artificial_uses (void)
658 struct df_link
*defs
;
663 for (use_rec
= df_get_artificial_uses (bb
->index
);
665 for (defs
= DF_REF_CHAIN (*use_rec
); defs
; defs
= defs
->next
)
666 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
667 mark_insn (DF_REF_INSN (defs
->ref
), false);
672 /* Mark every instruction that defines a register value that INSN uses. */
675 mark_reg_dependencies (rtx insn
)
677 struct df_link
*defs
;
680 if (DEBUG_INSN_P (insn
))
683 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
685 df_ref use
= *use_rec
;
688 fprintf (dump_file
, "Processing use of ");
689 print_simple_rtl (dump_file
, DF_REF_REG (use
));
690 fprintf (dump_file
, " in insn %d:\n", INSN_UID (insn
));
692 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
693 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
694 mark_insn (DF_REF_INSN (defs
->ref
), false);
699 /* Initialize global variables for a new DCE pass. */
708 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
709 df_chain_add_problem (DF_UD_CHAIN
);
719 bitmap_obstack_initialize (&dce_blocks_bitmap_obstack
);
720 bitmap_obstack_initialize (&dce_tmp_bitmap_obstack
);
721 can_alter_cfg
= false;
724 can_alter_cfg
= true;
726 marked
= sbitmap_alloc (get_max_uid () + 1);
727 bitmap_clear (marked
);
731 /* Free the data allocated by init_dce. */
736 sbitmap_free (marked
);
740 bitmap_obstack_release (&dce_blocks_bitmap_obstack
);
741 bitmap_obstack_release (&dce_tmp_bitmap_obstack
);
746 /* UD-chain based DCE. */
749 rest_of_handle_ud_dce (void)
755 prescan_insns_for_dce (false);
756 mark_artificial_uses ();
757 while (VEC_length (rtx
, worklist
) > 0)
759 insn
= VEC_pop (rtx
, worklist
);
760 mark_reg_dependencies (insn
);
762 VEC_free (rtx
, heap
, worklist
);
764 if (MAY_HAVE_DEBUG_INSNS
)
765 reset_unmarked_insns_debug_uses ();
767 /* Before any insns are deleted, we must remove the chains since
768 they are not bidirectional. */
769 df_remove_problem (df_chain
);
770 delete_unmarked_insns ();
780 return optimize
> 1 && flag_dce
784 struct rtl_opt_pass pass_ud_rtl_dce
=
789 gate_ud_dce
, /* gate */
790 rest_of_handle_ud_dce
, /* execute */
793 0, /* static_pass_number */
795 0, /* properties_required */
796 0, /* properties_provided */
797 0, /* properties_destroyed */
798 0, /* todo_flags_start */
799 TODO_df_finish
| TODO_verify_rtl_sharing
|
800 TODO_ggc_collect
/* todo_flags_finish */
805 /* -------------------------------------------------------------------------
807 ------------------------------------------------------------------------- */
809 /* Process basic block BB. Return true if the live_in set has
810 changed. REDO_OUT is true if the info at the bottom of the block
811 needs to be recalculated before starting. AU is the proper set of
812 artificial uses. Track global substitution of uses of dead pseudos
813 in debug insns using GLOBAL_DEBUG. */
816 word_dce_process_block (basic_block bb
, bool redo_out
,
817 struct dead_debug_global
*global_debug
)
819 bitmap local_live
= BITMAP_ALLOC (&dce_tmp_bitmap_obstack
);
822 struct dead_debug_local debug
;
826 /* Need to redo the live_out set of this block if when one of
827 the succs of this block has had a change in it live in
831 df_confluence_function_n con_fun_n
= df_word_lr
->problem
->con_fun_n
;
832 bitmap_clear (DF_WORD_LR_OUT (bb
));
833 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
839 fprintf (dump_file
, "processing block %d live out = ", bb
->index
);
840 df_print_word_regset (dump_file
, DF_WORD_LR_OUT (bb
));
843 bitmap_copy (local_live
, DF_WORD_LR_OUT (bb
));
844 dead_debug_local_init (&debug
, NULL
, global_debug
);
846 FOR_BB_INSNS_REVERSE (bb
, insn
)
847 if (DEBUG_INSN_P (insn
))
850 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
851 if (DF_REF_REGNO (*use_rec
) >= FIRST_PSEUDO_REGISTER
852 && (GET_MODE_SIZE (GET_MODE (DF_REF_REAL_REG (*use_rec
)))
853 == 2 * UNITS_PER_WORD
)
854 && !bitmap_bit_p (local_live
, 2 * DF_REF_REGNO (*use_rec
))
855 && !bitmap_bit_p (local_live
, 2 * DF_REF_REGNO (*use_rec
) + 1))
856 dead_debug_add (&debug
, *use_rec
, DF_REF_REGNO (*use_rec
));
858 else if (INSN_P (insn
))
862 /* No matter if the instruction is needed or not, we remove
863 any regno in the defs from the live set. */
864 any_changed
= df_word_lr_simulate_defs (insn
, local_live
);
866 mark_insn (insn
, true);
868 /* On the other hand, we do not allow the dead uses to set
869 anything in local_live. */
870 if (marked_insn_p (insn
))
871 df_word_lr_simulate_uses (insn
, local_live
);
873 /* Insert debug temps for dead REGs used in subsequent debug
874 insns. We may have to emit a debug temp even if the insn
875 was marked, in case the debug use was after the point of
877 if (debug
.used
&& !bitmap_empty_p (debug
.used
))
881 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
882 dead_debug_insert_temp (&debug
, DF_REF_REGNO (*def_rec
), insn
,
884 && !control_flow_insn_p (insn
)
885 ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
886 : DEBUG_TEMP_BEFORE_WITH_VALUE
);
891 fprintf (dump_file
, "finished processing insn %d live out = ",
893 df_print_word_regset (dump_file
, local_live
);
897 block_changed
= !bitmap_equal_p (local_live
, DF_WORD_LR_IN (bb
));
899 bitmap_copy (DF_WORD_LR_IN (bb
), local_live
);
901 dead_debug_local_finish (&debug
, NULL
);
902 BITMAP_FREE (local_live
);
903 return block_changed
;
907 /* Process basic block BB. Return true if the live_in set has
908 changed. REDO_OUT is true if the info at the bottom of the block
909 needs to be recalculated before starting. AU is the proper set of
910 artificial uses. Track global substitution of uses of dead pseudos
911 in debug insns using GLOBAL_DEBUG. */
914 dce_process_block (basic_block bb
, bool redo_out
, bitmap au
,
915 struct dead_debug_global
*global_debug
)
917 bitmap local_live
= BITMAP_ALLOC (&dce_tmp_bitmap_obstack
);
921 struct dead_debug_local debug
;
925 /* Need to redo the live_out set of this block if when one of
926 the succs of this block has had a change in it live in
930 df_confluence_function_n con_fun_n
= df_lr
->problem
->con_fun_n
;
931 bitmap_clear (DF_LR_OUT (bb
));
932 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
938 fprintf (dump_file
, "processing block %d lr out = ", bb
->index
);
939 df_print_regset (dump_file
, DF_LR_OUT (bb
));
942 bitmap_copy (local_live
, DF_LR_OUT (bb
));
944 df_simulate_initialize_backwards (bb
, local_live
);
945 dead_debug_local_init (&debug
, NULL
, global_debug
);
947 FOR_BB_INSNS_REVERSE (bb
, insn
)
948 if (DEBUG_INSN_P (insn
))
951 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
952 if (!bitmap_bit_p (local_live
, DF_REF_REGNO (*use_rec
))
953 && !bitmap_bit_p (au
, DF_REF_REGNO (*use_rec
)))
954 dead_debug_add (&debug
, *use_rec
, DF_REF_REGNO (*use_rec
));
956 else if (INSN_P (insn
))
958 bool needed
= marked_insn_p (insn
);
960 /* The insn is needed if there is someone who uses the output. */
962 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
963 if (bitmap_bit_p (local_live
, DF_REF_REGNO (*def_rec
))
964 || bitmap_bit_p (au
, DF_REF_REGNO (*def_rec
)))
967 mark_insn (insn
, true);
971 /* No matter if the instruction is needed or not, we remove
972 any regno in the defs from the live set. */
973 df_simulate_defs (insn
, local_live
);
975 /* On the other hand, we do not allow the dead uses to set
976 anything in local_live. */
978 df_simulate_uses (insn
, local_live
);
980 /* Insert debug temps for dead REGs used in subsequent debug
981 insns. We may have to emit a debug temp even if the insn
982 was marked, in case the debug use was after the point of
984 if (debug
.used
&& !bitmap_empty_p (debug
.used
))
985 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
986 dead_debug_insert_temp (&debug
, DF_REF_REGNO (*def_rec
), insn
,
987 needed
&& !control_flow_insn_p (insn
)
988 ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
989 : DEBUG_TEMP_BEFORE_WITH_VALUE
);
992 dead_debug_local_finish (&debug
, NULL
);
993 df_simulate_finalize_backwards (bb
, local_live
);
995 block_changed
= !bitmap_equal_p (local_live
, DF_LR_IN (bb
));
997 bitmap_copy (DF_LR_IN (bb
), local_live
);
999 BITMAP_FREE (local_live
);
1000 return block_changed
;
1004 /* Perform fast DCE once initialization is done. If WORD_LEVEL is
1005 true, use the word level dce, otherwise do it at the pseudo
1009 fast_dce (bool word_level
)
1011 int *postorder
= df_get_postorder (DF_BACKWARD
);
1012 int n_blocks
= df_get_n_blocks (DF_BACKWARD
);
1013 /* The set of blocks that have been seen on this iteration. */
1014 bitmap processed
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
1015 /* The set of blocks that need to have the out vectors reset because
1016 the in of one of their successors has changed. */
1017 bitmap redo_out
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
1018 bitmap all_blocks
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
1019 bool global_changed
= true;
1021 /* These regs are considered always live so if they end up dying
1022 because of some def, we need to bring the back again. Calling
1023 df_simulate_fixup_sets has the disadvantage of calling
1024 bb_has_eh_pred once per insn, so we cache the information
1026 bitmap au
= &df
->regular_block_artificial_uses
;
1027 bitmap au_eh
= &df
->eh_block_artificial_uses
;
1029 struct dead_debug_global global_debug
;
1031 prescan_insns_for_dce (true);
1033 for (i
= 0; i
< n_blocks
; i
++)
1034 bitmap_set_bit (all_blocks
, postorder
[i
]);
1036 dead_debug_global_init (&global_debug
, NULL
);
1038 while (global_changed
)
1040 global_changed
= false;
1042 for (i
= 0; i
< n_blocks
; i
++)
1044 int index
= postorder
[i
];
1045 basic_block bb
= BASIC_BLOCK (index
);
1048 if (index
< NUM_FIXED_BLOCKS
)
1050 bitmap_set_bit (processed
, index
);
1056 = word_dce_process_block (bb
, bitmap_bit_p (redo_out
, index
),
1060 = dce_process_block (bb
, bitmap_bit_p (redo_out
, index
),
1061 bb_has_eh_pred (bb
) ? au_eh
: au
,
1063 bitmap_set_bit (processed
, index
);
1069 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1070 if (bitmap_bit_p (processed
, e
->src
->index
))
1071 /* Be tricky about when we need to iterate the
1072 analysis. We only have redo the analysis if the
1073 bitmaps change at the top of a block that is the
1075 global_changed
= true;
1077 bitmap_set_bit (redo_out
, e
->src
->index
);
1083 /* Turn off the RUN_DCE flag to prevent recursive calls to
1085 int old_flag
= df_clear_flags (DF_LR_RUN_DCE
);
1087 /* So something was deleted that requires a redo. Do it on
1089 delete_unmarked_insns ();
1090 bitmap_clear (marked
);
1091 bitmap_clear (processed
);
1092 bitmap_clear (redo_out
);
1094 /* We do not need to rescan any instructions. We only need
1095 to redo the dataflow equations for the blocks that had a
1096 change at the top of the block. Then we need to redo the
1099 df_analyze_problem (df_word_lr
, all_blocks
, postorder
, n_blocks
);
1101 df_analyze_problem (df_lr
, all_blocks
, postorder
, n_blocks
);
1103 if (old_flag
& DF_LR_RUN_DCE
)
1104 df_set_flags (DF_LR_RUN_DCE
);
1106 prescan_insns_for_dce (true);
1110 dead_debug_global_finish (&global_debug
, NULL
);
1112 delete_unmarked_insns ();
1114 BITMAP_FREE (processed
);
1115 BITMAP_FREE (redo_out
);
1116 BITMAP_FREE (all_blocks
);
1120 /* Fast register level DCE. */
1123 rest_of_handle_fast_dce (void)
1132 /* Fast byte level DCE. */
1142 timevar_push (TV_DCE
);
1143 old_flags
= df_clear_flags (DF_DEFER_INSN_RESCAN
+ DF_NO_INSN_RESCAN
);
1144 df_word_lr_add_problem ();
1148 df_set_flags (old_flags
);
1149 timevar_pop (TV_DCE
);
1153 /* This is an internal call that is used by the df live register
1154 problem to run fast dce as a side effect of creating the live
1155 information. The stack is organized so that the lr problem is run,
1156 this pass is run, which updates the live info and the df scanning
1157 info, and then returns to allow the rest of the problems to be run.
1159 This can be called by elsewhere but it will not update the bit
1160 vectors for any other problems than LR. */
1163 run_fast_df_dce (void)
1167 /* If dce is able to delete something, it has to happen
1168 immediately. Otherwise there will be problems handling the
1171 df_clear_flags (DF_DEFER_INSN_RESCAN
+ DF_NO_INSN_RESCAN
);
1173 df_in_progress
= true;
1174 rest_of_handle_fast_dce ();
1175 df_in_progress
= false;
1177 df_set_flags (old_flags
);
1182 /* Run a fast DCE pass. */
1188 rest_of_handle_fast_dce ();
1193 gate_fast_dce (void)
1195 return optimize
> 0 && flag_dce
1196 && dbg_cnt (dce_fast
);
1199 struct rtl_opt_pass pass_fast_rtl_dce
=
1203 "rtl_dce", /* name */
1204 gate_fast_dce
, /* gate */
1205 rest_of_handle_fast_dce
, /* execute */
1208 0, /* static_pass_number */
1210 0, /* properties_required */
1211 0, /* properties_provided */
1212 0, /* properties_destroyed */
1213 0, /* todo_flags_start */
1214 TODO_df_finish
| TODO_verify_rtl_sharing
|
1215 TODO_ggc_collect
/* todo_flags_finish */