1 /* RTL dead code elimination.
2 Copyright (C) 2005-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
22 #include "coretypes.h"
30 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
33 #include "cfgcleanup.h"
36 #include "tree-pass.h"
40 /* -------------------------------------------------------------------------
41 Core mark/delete routines
42 ------------------------------------------------------------------------- */
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;
48 /* True if we are allowed to alter the CFG in this pass. */
49 static bool can_alter_cfg
= false;
51 /* Instructions that have been marked but whose dependencies have not
52 yet been processed. */
53 static vec
<rtx_insn
*> worklist
;
55 /* Bitmap of instructions marked as needed indexed by INSN_UID. */
56 static sbitmap marked
;
58 /* Bitmap obstacks used for block processing by the fast algorithm. */
59 static bitmap_obstack dce_blocks_bitmap_obstack
;
60 static bitmap_obstack dce_tmp_bitmap_obstack
;
62 static bool find_call_stack_args (rtx_call_insn
*, bool, bool, bitmap
);
64 /* A subroutine for which BODY is part of the instruction being tested;
65 either the top-level pattern, or an element of a PARALLEL. The
66 instruction is known not to be a bare USE or CLOBBER. */
69 deletable_insn_p_1 (rtx body
)
71 switch (GET_CODE (body
))
75 /* The UNSPEC case was added here because the ia-64 claims that
76 USEs do not work after reload and generates UNSPECS rather
77 than USEs. Since dce is run after reload we need to avoid
78 deleting these even if they are dead. If it turns out that
79 USEs really do work after reload, the ia-64 should be
80 changed, and the UNSPEC case can be removed. */
85 return !volatile_refs_p (body
);
90 /* Return true if INSN is a normal instruction that can be deleted by
94 deletable_insn_p (rtx_insn
*insn
, bool fast
, bitmap arg_stores
)
101 /* We cannot delete calls inside of the recursive dce because
102 this may cause basic blocks to be deleted and this messes up
103 the rest of the stack of optimization passes. */
105 /* We cannot delete pure or const sibling calls because it is
106 hard to see the result. */
107 && (!SIBLING_CALL_P (insn
))
108 /* We can delete dead const or pure calls as long as they do not
110 && (RTL_CONST_OR_PURE_CALL_P (insn
)
111 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
112 /* Don't delete calls that may throw if we cannot do so. */
113 && ((cfun
->can_delete_dead_exceptions
&& can_alter_cfg
)
114 || insn_nothrow_p (insn
)))
115 return find_call_stack_args (as_a
<rtx_call_insn
*> (insn
), false,
118 /* Don't delete jumps, notes and the like. */
119 if (!NONJUMP_INSN_P (insn
))
122 /* Don't delete insns that may throw if we cannot do so. */
123 if (!(cfun
->can_delete_dead_exceptions
&& can_alter_cfg
)
124 && !insn_nothrow_p (insn
))
127 /* If INSN sets a global_reg, leave it untouched. */
128 FOR_EACH_INSN_DEF (def
, insn
)
129 if (HARD_REGISTER_NUM_P (DF_REF_REGNO (def
))
130 && global_regs
[DF_REF_REGNO (def
)])
132 /* Initialization of pseudo PIC register should never be removed. */
133 else if (DF_REF_REG (def
) == pic_offset_table_rtx
134 && REGNO (pic_offset_table_rtx
) >= FIRST_PSEUDO_REGISTER
)
137 /* Callee-save restores are needed. */
138 if (RTX_FRAME_RELATED_P (insn
)
139 && crtl
->shrink_wrapped_separate
140 && find_reg_note (insn
, REG_CFA_RESTORE
, NULL
))
143 body
= PATTERN (insn
);
144 switch (GET_CODE (body
))
153 /* A CLOBBER of a dead pseudo register serves no purpose.
154 That is not necessarily true for hard registers until
157 return REG_P (x
) && (!HARD_REGISTER_P (x
) || reload_completed
);
160 /* Because of the way that use-def chains are built, it is not
161 possible to tell if the clobber is dead because it can
162 never be the target of a use-def chain. */
166 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; i
--)
167 if (!deletable_insn_p_1 (XVECEXP (body
, 0, i
)))
172 return deletable_insn_p_1 (body
);
177 /* Return true if INSN has been marked as needed. */
180 marked_insn_p (rtx_insn
*insn
)
182 /* Artificial defs are always needed and they do not have an insn.
183 We should never see them here. */
185 return bitmap_bit_p (marked
, INSN_UID (insn
));
189 /* If INSN has not yet been marked as needed, mark it now, and add it to
193 mark_insn (rtx_insn
*insn
, bool fast
)
195 if (!marked_insn_p (insn
))
198 worklist
.safe_push (insn
);
199 bitmap_set_bit (marked
, INSN_UID (insn
));
201 fprintf (dump_file
, " Adding insn %d to worklist\n", INSN_UID (insn
));
204 && !SIBLING_CALL_P (insn
)
205 && (RTL_CONST_OR_PURE_CALL_P (insn
)
206 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
207 && ((cfun
->can_delete_dead_exceptions
&& can_alter_cfg
)
208 || insn_nothrow_p (insn
)))
209 find_call_stack_args (as_a
<rtx_call_insn
*> (insn
), true, fast
, NULL
);
214 /* A note_stores callback used by mark_nonreg_stores. DATA is the
215 instruction containing DEST. */
218 mark_nonreg_stores_1 (rtx dest
, const_rtx pattern
, void *data
)
220 if (GET_CODE (pattern
) != CLOBBER
&& !REG_P (dest
))
221 mark_insn ((rtx_insn
*) data
, true);
225 /* A note_stores callback used by mark_nonreg_stores. DATA is the
226 instruction containing DEST. */
229 mark_nonreg_stores_2 (rtx dest
, const_rtx pattern
, void *data
)
231 if (GET_CODE (pattern
) != CLOBBER
&& !REG_P (dest
))
232 mark_insn ((rtx_insn
*) data
, false);
236 /* Mark INSN if BODY stores to a non-register destination. */
239 mark_nonreg_stores (rtx body
, rtx_insn
*insn
, bool fast
)
242 note_stores (body
, mark_nonreg_stores_1
, insn
);
244 note_stores (body
, mark_nonreg_stores_2
, insn
);
248 /* Return true if a store to SIZE bytes, starting OFF bytes from stack pointer,
249 is a call argument store, and clear corresponding bits from SP_BYTES
253 check_argument_store (HOST_WIDE_INT size
, HOST_WIDE_INT off
,
254 HOST_WIDE_INT min_sp_off
, HOST_WIDE_INT max_sp_off
,
258 for (byte
= off
; byte
< off
+ size
; byte
++)
260 if (byte
< min_sp_off
261 || byte
>= max_sp_off
262 || !bitmap_clear_bit (sp_bytes
, byte
- min_sp_off
))
269 /* Try to find all stack stores of CALL_INSN arguments if
270 ACCUMULATE_OUTGOING_ARGS. If all stack stores have been found
271 and it is therefore safe to eliminate the call, return true,
272 otherwise return false. This function should be first called
273 with DO_MARK false, and only when the CALL_INSN is actually
274 going to be marked called again with DO_MARK true. */
277 find_call_stack_args (rtx_call_insn
*call_insn
, bool do_mark
, bool fast
,
281 rtx_insn
*insn
, *prev_insn
;
283 HOST_WIDE_INT min_sp_off
, max_sp_off
;
286 gcc_assert (CALL_P (call_insn
));
287 if (!ACCUMULATE_OUTGOING_ARGS
)
292 gcc_assert (arg_stores
);
293 bitmap_clear (arg_stores
);
296 min_sp_off
= INTTYPE_MAXIMUM (HOST_WIDE_INT
);
299 /* First determine the minimum and maximum offset from sp for
301 for (p
= CALL_INSN_FUNCTION_USAGE (call_insn
); p
; p
= XEXP (p
, 1))
302 if (GET_CODE (XEXP (p
, 0)) == USE
303 && MEM_P (XEXP (XEXP (p
, 0), 0)))
305 rtx mem
= XEXP (XEXP (p
, 0), 0), addr
;
306 HOST_WIDE_INT off
= 0, size
;
307 if (!MEM_SIZE_KNOWN_P (mem
) || !MEM_SIZE (mem
).is_constant (&size
))
309 addr
= XEXP (mem
, 0);
310 if (GET_CODE (addr
) == PLUS
311 && REG_P (XEXP (addr
, 0))
312 && CONST_INT_P (XEXP (addr
, 1)))
314 off
= INTVAL (XEXP (addr
, 1));
315 addr
= XEXP (addr
, 0);
317 if (addr
!= stack_pointer_rtx
)
321 /* If not fast, use chains to see if addr wasn't set to
326 struct df_link
*defs
;
329 FOR_EACH_INSN_USE (use
, call_insn
)
330 if (rtx_equal_p (addr
, DF_REF_REG (use
)))
336 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
337 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
343 set
= single_set (DF_REF_INSN (defs
->ref
));
347 if (GET_CODE (SET_SRC (set
)) != PLUS
348 || XEXP (SET_SRC (set
), 0) != stack_pointer_rtx
349 || !CONST_INT_P (XEXP (SET_SRC (set
), 1)))
352 off
+= INTVAL (XEXP (SET_SRC (set
), 1));
357 min_sp_off
= MIN (min_sp_off
, off
);
358 max_sp_off
= MAX (max_sp_off
, off
+ size
);
361 if (min_sp_off
>= max_sp_off
)
363 sp_bytes
= BITMAP_ALLOC (NULL
);
365 /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
366 which contain arguments. Checking has been done in the previous
368 for (p
= CALL_INSN_FUNCTION_USAGE (call_insn
); p
; p
= XEXP (p
, 1))
369 if (GET_CODE (XEXP (p
, 0)) == USE
370 && MEM_P (XEXP (XEXP (p
, 0), 0)))
372 rtx mem
= XEXP (XEXP (p
, 0), 0), addr
;
373 HOST_WIDE_INT off
= 0, byte
, size
;
374 /* Checked in the previous iteration. */
375 size
= MEM_SIZE (mem
).to_constant ();
376 addr
= XEXP (mem
, 0);
377 if (GET_CODE (addr
) == PLUS
378 && REG_P (XEXP (addr
, 0))
379 && CONST_INT_P (XEXP (addr
, 1)))
381 off
= INTVAL (XEXP (addr
, 1));
382 addr
= XEXP (addr
, 0);
384 if (addr
!= stack_pointer_rtx
)
387 struct df_link
*defs
;
390 FOR_EACH_INSN_USE (use
, call_insn
)
391 if (rtx_equal_p (addr
, DF_REF_REG (use
)))
394 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
395 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
398 set
= single_set (DF_REF_INSN (defs
->ref
));
399 off
+= INTVAL (XEXP (SET_SRC (set
), 1));
401 for (byte
= off
; byte
< off
+ size
; byte
++)
403 if (!bitmap_set_bit (sp_bytes
, byte
- min_sp_off
))
408 /* Walk backwards, looking for argument stores. The search stops
409 when seeing another call, sp adjustment or memory store other than
412 for (insn
= PREV_INSN (call_insn
); insn
; insn
= prev_insn
)
417 if (insn
== BB_HEAD (BLOCK_FOR_INSN (call_insn
)))
420 prev_insn
= PREV_INSN (insn
);
425 if (!NONDEBUG_INSN_P (insn
))
428 set
= single_set (insn
);
429 if (!set
|| SET_DEST (set
) == stack_pointer_rtx
)
432 if (!MEM_P (SET_DEST (set
)))
435 mem
= SET_DEST (set
);
436 addr
= XEXP (mem
, 0);
438 if (GET_CODE (addr
) == PLUS
439 && REG_P (XEXP (addr
, 0))
440 && CONST_INT_P (XEXP (addr
, 1)))
442 off
= INTVAL (XEXP (addr
, 1));
443 addr
= XEXP (addr
, 0);
445 if (addr
!= stack_pointer_rtx
)
452 struct df_link
*defs
;
455 FOR_EACH_INSN_USE (use
, insn
)
456 if (rtx_equal_p (addr
, DF_REF_REG (use
)))
462 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
463 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
469 set
= single_set (DF_REF_INSN (defs
->ref
));
473 if (GET_CODE (SET_SRC (set
)) != PLUS
474 || XEXP (SET_SRC (set
), 0) != stack_pointer_rtx
475 || !CONST_INT_P (XEXP (SET_SRC (set
), 1)))
478 off
+= INTVAL (XEXP (SET_SRC (set
), 1));
485 if (!MEM_SIZE_KNOWN_P (mem
)
486 || !MEM_SIZE (mem
).is_constant (&size
)
487 || !check_argument_store (size
, off
, min_sp_off
,
488 max_sp_off
, sp_bytes
))
491 if (!deletable_insn_p (insn
, fast
, NULL
))
495 mark_insn (insn
, fast
);
497 bitmap_set_bit (arg_stores
, INSN_UID (insn
));
499 if (bitmap_empty_p (sp_bytes
))
506 BITMAP_FREE (sp_bytes
);
507 if (!ret
&& arg_stores
)
508 bitmap_clear (arg_stores
);
514 /* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN
518 remove_reg_equal_equiv_notes_for_defs (rtx_insn
*insn
)
522 FOR_EACH_INSN_DEF (def
, insn
)
523 remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (def
));
526 /* Scan all BBs for debug insns and reset those that reference values
527 defined in unmarked insns. */
530 reset_unmarked_insns_debug_uses (void)
533 rtx_insn
*insn
, *next
;
535 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
536 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, next
)
537 if (DEBUG_INSN_P (insn
))
541 FOR_EACH_INSN_USE (use
, insn
)
543 struct df_link
*defs
;
544 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
547 if (DF_REF_IS_ARTIFICIAL (defs
->ref
))
549 ref_insn
= DF_REF_INSN (defs
->ref
);
550 if (!marked_insn_p (ref_insn
))
555 /* ??? FIXME could we propagate the values assigned to
557 INSN_VAR_LOCATION_LOC (insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
558 df_insn_rescan_debug_internal (insn
);
564 /* Delete every instruction that hasn't been marked. */
567 delete_unmarked_insns (void)
570 rtx_insn
*insn
, *next
;
571 bool must_clean
= false;
573 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
574 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, next
)
575 if (NONDEBUG_INSN_P (insn
))
577 rtx turn_into_use
= NULL_RTX
;
579 /* Always delete no-op moves. */
580 if (noop_move_p (insn
)
581 /* Unless the no-op move can throw and we are not allowed
583 && (!cfun
->can_throw_non_call_exceptions
584 || (cfun
->can_delete_dead_exceptions
&& can_alter_cfg
)
585 || insn_nothrow_p (insn
)))
587 if (RTX_FRAME_RELATED_P (insn
))
589 = find_reg_note (insn
, REG_CFA_RESTORE
, NULL
);
590 if (turn_into_use
&& REG_P (XEXP (turn_into_use
, 0)))
591 turn_into_use
= XEXP (turn_into_use
, 0);
593 turn_into_use
= NULL_RTX
;
596 /* Otherwise rely only on the DCE algorithm. */
597 else if (marked_insn_p (insn
))
600 /* Beware that reaching a dbg counter limit here can result
601 in miscompiled file. This occurs when a group of insns
602 must be deleted together, typically because the kept insn
603 depends on the output from the deleted insn. Deleting
604 this insns in reverse order (both at the bb level and
605 when looking at the blocks) minimizes this, but does not
606 eliminate it, since it is possible for the using insn to
607 be top of a block and the producer to be at the bottom of
608 the block. However, in most cases this will only result
609 in an uninitialized use of an insn that is dead anyway.
611 However, there is one rare case that will cause a
612 miscompile: deletion of non-looping pure and constant
613 calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
614 In this case it is possible to remove the call, but leave
615 the argument pushes to the stack. Because of the changes
616 to the stack pointer, this will almost always lead to a
622 fprintf (dump_file
, "DCE: Deleting insn %d\n", INSN_UID (insn
));
624 /* Before we delete the insn we have to remove the REG_EQUAL notes
625 for the destination regs in order to avoid dangling notes. */
626 remove_reg_equal_equiv_notes_for_defs (insn
);
630 /* Don't remove frame related noop moves if they cary
631 REG_CFA_RESTORE note, while we don't need to emit any code,
632 we need it to emit the CFI restore note. */
634 = gen_rtx_USE (GET_MODE (turn_into_use
), turn_into_use
);
635 INSN_CODE (insn
) = -1;
636 df_insn_rescan (insn
);
639 /* Now delete the insn. */
640 must_clean
|= delete_insn_and_edges (insn
);
643 /* Deleted a pure or const call. */
646 delete_unreachable_blocks ();
647 free_dominance_info (CDI_DOMINATORS
);
652 /* Go through the instructions and mark those whose necessity is not
653 dependent on inter-instruction information. Make sure all other
654 instructions are not marked. */
657 prescan_insns_for_dce (bool fast
)
660 rtx_insn
*insn
, *prev
;
661 bitmap arg_stores
= NULL
;
664 fprintf (dump_file
, "Finding needed instructions:\n");
666 if (!df_in_progress
&& ACCUMULATE_OUTGOING_ARGS
)
667 arg_stores
= BITMAP_ALLOC (NULL
);
669 FOR_EACH_BB_FN (bb
, cfun
)
671 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, prev
)
672 if (NONDEBUG_INSN_P (insn
))
674 /* Don't mark argument stores now. They will be marked
675 if needed when the associated CALL is marked. */
676 if (arg_stores
&& bitmap_bit_p (arg_stores
, INSN_UID (insn
)))
678 if (deletable_insn_p (insn
, fast
, arg_stores
))
679 mark_nonreg_stores (PATTERN (insn
), insn
, fast
);
681 mark_insn (insn
, fast
);
683 /* find_call_stack_args only looks at argument stores in the
686 bitmap_clear (arg_stores
);
690 BITMAP_FREE (arg_stores
);
693 fprintf (dump_file
, "Finished finding needed instructions:\n");
697 /* UD-based DSE routines. */
699 /* Mark instructions that define artificially-used registers, such as
700 the frame pointer and the stack pointer. */
703 mark_artificial_uses (void)
706 struct df_link
*defs
;
709 FOR_ALL_BB_FN (bb
, cfun
)
710 FOR_EACH_ARTIFICIAL_USE (use
, bb
->index
)
711 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
712 if (!DF_REF_IS_ARTIFICIAL (defs
->ref
))
713 mark_insn (DF_REF_INSN (defs
->ref
), false);
717 /* Mark every instruction that defines a register value that INSN uses. */
720 mark_reg_dependencies (rtx_insn
*insn
)
722 struct df_link
*defs
;
725 if (DEBUG_INSN_P (insn
))
728 FOR_EACH_INSN_USE (use
, insn
)
732 fprintf (dump_file
, "Processing use of ");
733 print_simple_rtl (dump_file
, DF_REF_REG (use
));
734 fprintf (dump_file
, " in insn %d:\n", INSN_UID (insn
));
736 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
737 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
738 mark_insn (DF_REF_INSN (defs
->ref
), false);
743 /* Initialize global variables for a new DCE pass. */
752 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
753 df_chain_add_problem (DF_UD_CHAIN
);
763 bitmap_obstack_initialize (&dce_blocks_bitmap_obstack
);
764 bitmap_obstack_initialize (&dce_tmp_bitmap_obstack
);
765 can_alter_cfg
= false;
768 can_alter_cfg
= true;
770 marked
= sbitmap_alloc (get_max_uid () + 1);
771 bitmap_clear (marked
);
775 /* Free the data allocated by init_dce. */
780 sbitmap_free (marked
);
784 bitmap_obstack_release (&dce_blocks_bitmap_obstack
);
785 bitmap_obstack_release (&dce_tmp_bitmap_obstack
);
790 /* UD-chain based DCE. */
793 rest_of_handle_ud_dce (void)
799 prescan_insns_for_dce (false);
800 mark_artificial_uses ();
801 while (worklist
.length () > 0)
803 insn
= worklist
.pop ();
804 mark_reg_dependencies (insn
);
808 if (MAY_HAVE_DEBUG_BIND_INSNS
)
809 reset_unmarked_insns_debug_uses ();
811 /* Before any insns are deleted, we must remove the chains since
812 they are not bidirectional. */
813 df_remove_problem (df_chain
);
814 delete_unmarked_insns ();
823 const pass_data pass_data_ud_rtl_dce
=
827 OPTGROUP_NONE
, /* optinfo_flags */
829 0, /* properties_required */
830 0, /* properties_provided */
831 0, /* properties_destroyed */
832 0, /* todo_flags_start */
833 TODO_df_finish
, /* todo_flags_finish */
836 class pass_ud_rtl_dce
: public rtl_opt_pass
839 pass_ud_rtl_dce (gcc::context
*ctxt
)
840 : rtl_opt_pass (pass_data_ud_rtl_dce
, ctxt
)
843 /* opt_pass methods: */
844 virtual bool gate (function
*)
846 return optimize
> 1 && flag_dce
&& dbg_cnt (dce_ud
);
849 virtual unsigned int execute (function
*)
851 return rest_of_handle_ud_dce ();
854 }; // class pass_ud_rtl_dce
859 make_pass_ud_rtl_dce (gcc::context
*ctxt
)
861 return new pass_ud_rtl_dce (ctxt
);
865 /* -------------------------------------------------------------------------
867 ------------------------------------------------------------------------- */
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. Track global substitution of uses of dead pseudos
873 in debug insns using GLOBAL_DEBUG. */
876 word_dce_process_block (basic_block bb
, bool redo_out
,
877 struct dead_debug_global
*global_debug
)
879 bitmap local_live
= BITMAP_ALLOC (&dce_tmp_bitmap_obstack
);
882 struct dead_debug_local debug
;
886 /* Need to redo the live_out set of this block if when one of
887 the succs of this block has had a change in it live in
891 df_confluence_function_n con_fun_n
= df_word_lr
->problem
->con_fun_n
;
892 bitmap_clear (DF_WORD_LR_OUT (bb
));
893 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
899 fprintf (dump_file
, "processing block %d live out = ", bb
->index
);
900 df_print_word_regset (dump_file
, DF_WORD_LR_OUT (bb
));
903 bitmap_copy (local_live
, DF_WORD_LR_OUT (bb
));
904 dead_debug_local_init (&debug
, NULL
, global_debug
);
906 FOR_BB_INSNS_REVERSE (bb
, insn
)
907 if (DEBUG_INSN_P (insn
))
910 FOR_EACH_INSN_USE (use
, insn
)
911 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
912 && known_eq (GET_MODE_SIZE (GET_MODE (DF_REF_REAL_REG (use
))),
914 && !bitmap_bit_p (local_live
, 2 * DF_REF_REGNO (use
))
915 && !bitmap_bit_p (local_live
, 2 * DF_REF_REGNO (use
) + 1))
916 dead_debug_add (&debug
, use
, DF_REF_REGNO (use
));
918 else if (INSN_P (insn
))
922 /* No matter if the instruction is needed or not, we remove
923 any regno in the defs from the live set. */
924 any_changed
= df_word_lr_simulate_defs (insn
, local_live
);
926 mark_insn (insn
, true);
928 /* On the other hand, we do not allow the dead uses to set
929 anything in local_live. */
930 if (marked_insn_p (insn
))
931 df_word_lr_simulate_uses (insn
, local_live
);
933 /* Insert debug temps for dead REGs used in subsequent debug
934 insns. We may have to emit a debug temp even if the insn
935 was marked, in case the debug use was after the point of
937 if (debug
.used
&& !bitmap_empty_p (debug
.used
))
941 FOR_EACH_INSN_DEF (def
, insn
)
942 dead_debug_insert_temp (&debug
, DF_REF_REGNO (def
), insn
,
944 && !control_flow_insn_p (insn
)
945 ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
946 : DEBUG_TEMP_BEFORE_WITH_VALUE
);
951 fprintf (dump_file
, "finished processing insn %d live out = ",
953 df_print_word_regset (dump_file
, local_live
);
957 block_changed
= !bitmap_equal_p (local_live
, DF_WORD_LR_IN (bb
));
959 bitmap_copy (DF_WORD_LR_IN (bb
), local_live
);
961 dead_debug_local_finish (&debug
, NULL
);
962 BITMAP_FREE (local_live
);
963 return block_changed
;
967 /* Process basic block BB. Return true if the live_in set has
968 changed. REDO_OUT is true if the info at the bottom of the block
969 needs to be recalculated before starting. AU is the proper set of
970 artificial uses. Track global substitution of uses of dead pseudos
971 in debug insns using GLOBAL_DEBUG. */
974 dce_process_block (basic_block bb
, bool redo_out
, bitmap au
,
975 struct dead_debug_global
*global_debug
)
977 bitmap local_live
= BITMAP_ALLOC (&dce_tmp_bitmap_obstack
);
981 struct dead_debug_local debug
;
985 /* Need to redo the live_out set of this block if when one of
986 the succs of this block has had a change in it live in
990 df_confluence_function_n con_fun_n
= df_lr
->problem
->con_fun_n
;
991 bitmap_clear (DF_LR_OUT (bb
));
992 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
998 fprintf (dump_file
, "processing block %d lr out = ", bb
->index
);
999 df_print_regset (dump_file
, DF_LR_OUT (bb
));
1002 bitmap_copy (local_live
, DF_LR_OUT (bb
));
1004 df_simulate_initialize_backwards (bb
, local_live
);
1005 dead_debug_local_init (&debug
, NULL
, global_debug
);
1007 FOR_BB_INSNS_REVERSE (bb
, insn
)
1008 if (DEBUG_INSN_P (insn
))
1011 FOR_EACH_INSN_USE (use
, insn
)
1012 if (!bitmap_bit_p (local_live
, DF_REF_REGNO (use
))
1013 && !bitmap_bit_p (au
, DF_REF_REGNO (use
)))
1014 dead_debug_add (&debug
, use
, DF_REF_REGNO (use
));
1016 else if (INSN_P (insn
))
1018 bool needed
= marked_insn_p (insn
);
1020 /* The insn is needed if there is someone who uses the output. */
1022 FOR_EACH_INSN_DEF (def
, insn
)
1023 if (bitmap_bit_p (local_live
, DF_REF_REGNO (def
))
1024 || bitmap_bit_p (au
, DF_REF_REGNO (def
)))
1027 mark_insn (insn
, true);
1031 /* No matter if the instruction is needed or not, we remove
1032 any regno in the defs from the live set. */
1033 df_simulate_defs (insn
, local_live
);
1035 /* On the other hand, we do not allow the dead uses to set
1036 anything in local_live. */
1038 df_simulate_uses (insn
, local_live
);
1040 /* Insert debug temps for dead REGs used in subsequent debug
1041 insns. We may have to emit a debug temp even if the insn
1042 was marked, in case the debug use was after the point of
1044 if (debug
.used
&& !bitmap_empty_p (debug
.used
))
1045 FOR_EACH_INSN_DEF (def
, insn
)
1046 dead_debug_insert_temp (&debug
, DF_REF_REGNO (def
), insn
,
1047 needed
&& !control_flow_insn_p (insn
)
1048 ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
1049 : DEBUG_TEMP_BEFORE_WITH_VALUE
);
1052 dead_debug_local_finish (&debug
, NULL
);
1053 df_simulate_finalize_backwards (bb
, local_live
);
1055 block_changed
= !bitmap_equal_p (local_live
, DF_LR_IN (bb
));
1057 bitmap_copy (DF_LR_IN (bb
), local_live
);
1059 BITMAP_FREE (local_live
);
1060 return block_changed
;
1064 /* Perform fast DCE once initialization is done. If WORD_LEVEL is
1065 true, use the word level dce, otherwise do it at the pseudo
1069 fast_dce (bool word_level
)
1071 int *postorder
= df_get_postorder (DF_BACKWARD
);
1072 int n_blocks
= df_get_n_blocks (DF_BACKWARD
);
1073 /* The set of blocks that have been seen on this iteration. */
1074 bitmap processed
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
1075 /* The set of blocks that need to have the out vectors reset because
1076 the in of one of their successors has changed. */
1077 bitmap redo_out
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
1078 bitmap all_blocks
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
1079 bool global_changed
= true;
1081 /* These regs are considered always live so if they end up dying
1082 because of some def, we need to bring the back again. Calling
1083 df_simulate_fixup_sets has the disadvantage of calling
1084 bb_has_eh_pred once per insn, so we cache the information
1086 bitmap au
= &df
->regular_block_artificial_uses
;
1087 bitmap au_eh
= &df
->eh_block_artificial_uses
;
1089 struct dead_debug_global global_debug
;
1091 prescan_insns_for_dce (true);
1093 for (i
= 0; i
< n_blocks
; i
++)
1094 bitmap_set_bit (all_blocks
, postorder
[i
]);
1096 dead_debug_global_init (&global_debug
, NULL
);
1098 while (global_changed
)
1100 global_changed
= false;
1102 for (i
= 0; i
< n_blocks
; i
++)
1104 int index
= postorder
[i
];
1105 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, index
);
1108 if (index
< NUM_FIXED_BLOCKS
)
1110 bitmap_set_bit (processed
, index
);
1116 = word_dce_process_block (bb
, bitmap_bit_p (redo_out
, index
),
1120 = dce_process_block (bb
, bitmap_bit_p (redo_out
, index
),
1121 bb_has_eh_pred (bb
) ? au_eh
: au
,
1123 bitmap_set_bit (processed
, index
);
1129 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1130 if (bitmap_bit_p (processed
, e
->src
->index
))
1131 /* Be tricky about when we need to iterate the
1132 analysis. We only have redo the analysis if the
1133 bitmaps change at the top of a block that is the
1135 global_changed
= true;
1137 bitmap_set_bit (redo_out
, e
->src
->index
);
1143 /* Turn off the RUN_DCE flag to prevent recursive calls to
1145 int old_flag
= df_clear_flags (DF_LR_RUN_DCE
);
1147 /* So something was deleted that requires a redo. Do it on
1149 delete_unmarked_insns ();
1150 bitmap_clear (marked
);
1151 bitmap_clear (processed
);
1152 bitmap_clear (redo_out
);
1154 /* We do not need to rescan any instructions. We only need
1155 to redo the dataflow equations for the blocks that had a
1156 change at the top of the block. Then we need to redo the
1159 df_analyze_problem (df_word_lr
, all_blocks
, postorder
, n_blocks
);
1161 df_analyze_problem (df_lr
, all_blocks
, postorder
, n_blocks
);
1163 if (old_flag
& DF_LR_RUN_DCE
)
1164 df_set_flags (DF_LR_RUN_DCE
);
1166 prescan_insns_for_dce (true);
1170 dead_debug_global_finish (&global_debug
, NULL
);
1172 delete_unmarked_insns ();
1174 BITMAP_FREE (processed
);
1175 BITMAP_FREE (redo_out
);
1176 BITMAP_FREE (all_blocks
);
1180 /* Fast register level DCE. */
1183 rest_of_handle_fast_dce (void)
1192 /* Fast byte level DCE. */
1202 timevar_push (TV_DCE
);
1203 old_flags
= df_clear_flags (DF_DEFER_INSN_RESCAN
+ DF_NO_INSN_RESCAN
);
1204 df_word_lr_add_problem ();
1208 df_set_flags (old_flags
);
1209 timevar_pop (TV_DCE
);
1213 /* This is an internal call that is used by the df live register
1214 problem to run fast dce as a side effect of creating the live
1215 information. The stack is organized so that the lr problem is run,
1216 this pass is run, which updates the live info and the df scanning
1217 info, and then returns to allow the rest of the problems to be run.
1219 This can be called by elsewhere but it will not update the bit
1220 vectors for any other problems than LR. */
1223 run_fast_df_dce (void)
1227 /* If dce is able to delete something, it has to happen
1228 immediately. Otherwise there will be problems handling the
1231 df_clear_flags (DF_DEFER_INSN_RESCAN
+ DF_NO_INSN_RESCAN
);
1233 df_in_progress
= true;
1234 rest_of_handle_fast_dce ();
1235 df_in_progress
= false;
1237 df_set_flags (old_flags
);
1242 /* Run a fast DCE pass. */
1248 rest_of_handle_fast_dce ();
1254 const pass_data pass_data_fast_rtl_dce
=
1256 RTL_PASS
, /* type */
1257 "rtl_dce", /* name */
1258 OPTGROUP_NONE
, /* optinfo_flags */
1260 0, /* properties_required */
1261 0, /* properties_provided */
1262 0, /* properties_destroyed */
1263 0, /* todo_flags_start */
1264 TODO_df_finish
, /* todo_flags_finish */
1267 class pass_fast_rtl_dce
: public rtl_opt_pass
1270 pass_fast_rtl_dce (gcc::context
*ctxt
)
1271 : rtl_opt_pass (pass_data_fast_rtl_dce
, ctxt
)
1274 /* opt_pass methods: */
1275 virtual bool gate (function
*)
1277 return optimize
> 0 && flag_dce
&& dbg_cnt (dce_fast
);
1280 virtual unsigned int execute (function
*)
1282 return rest_of_handle_fast_dce ();
1285 }; // class pass_fast_rtl_dce
1290 make_pass_fast_rtl_dce (gcc::context
*ctxt
)
1292 return new pass_fast_rtl_dce (ctxt
);