1 /* RTL dead code elimination.
2 Copyright (C) 2005-2019 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
))
154 /* A CLOBBER of a dead pseudo register serves no purpose.
155 That is not necessarily true for hard registers until
158 return REG_P (x
) && (!HARD_REGISTER_P (x
) || reload_completed
);
161 /* Because of the way that use-def chains are built, it is not
162 possible to tell if the clobber is dead because it can
163 never be the target of a use-def chain. */
167 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; i
--)
168 if (!deletable_insn_p_1 (XVECEXP (body
, 0, i
)))
173 return deletable_insn_p_1 (body
);
178 /* Return true if INSN has been marked as needed. */
181 marked_insn_p (rtx_insn
*insn
)
183 /* Artificial defs are always needed and they do not have an insn.
184 We should never see them here. */
186 return bitmap_bit_p (marked
, INSN_UID (insn
));
190 /* If INSN has not yet been marked as needed, mark it now, and add it to
194 mark_insn (rtx_insn
*insn
, bool fast
)
196 if (!marked_insn_p (insn
))
199 worklist
.safe_push (insn
);
200 bitmap_set_bit (marked
, INSN_UID (insn
));
202 fprintf (dump_file
, " Adding insn %d to worklist\n", INSN_UID (insn
));
205 && !SIBLING_CALL_P (insn
)
206 && (RTL_CONST_OR_PURE_CALL_P (insn
)
207 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
))
208 && ((cfun
->can_delete_dead_exceptions
&& can_alter_cfg
)
209 || insn_nothrow_p (insn
)))
210 find_call_stack_args (as_a
<rtx_call_insn
*> (insn
), true, fast
, NULL
);
215 /* A note_stores callback used by mark_nonreg_stores. DATA is the
216 instruction containing DEST. */
219 mark_nonreg_stores_1 (rtx dest
, const_rtx pattern
, void *data
)
221 if (GET_CODE (pattern
) != CLOBBER
&& !REG_P (dest
))
223 gcc_checking_assert (GET_CODE (pattern
) != CLOBBER_HIGH
);
224 mark_insn ((rtx_insn
*) data
, true);
229 /* A note_stores callback used by mark_nonreg_stores. DATA is the
230 instruction containing DEST. */
233 mark_nonreg_stores_2 (rtx dest
, const_rtx pattern
, void *data
)
235 if (GET_CODE (pattern
) != CLOBBER
&& !REG_P (dest
))
237 gcc_checking_assert (GET_CODE (pattern
) != CLOBBER_HIGH
);
238 mark_insn ((rtx_insn
*) data
, false);
243 /* Mark INSN if BODY stores to a non-register destination. */
246 mark_nonreg_stores (rtx body
, rtx_insn
*insn
, bool fast
)
249 note_stores (body
, mark_nonreg_stores_1
, insn
);
251 note_stores (body
, mark_nonreg_stores_2
, insn
);
255 /* Return true if a store to SIZE bytes, starting OFF bytes from stack pointer,
256 is a call argument store, and clear corresponding bits from SP_BYTES
260 check_argument_store (HOST_WIDE_INT size
, HOST_WIDE_INT off
,
261 HOST_WIDE_INT min_sp_off
, HOST_WIDE_INT max_sp_off
,
265 for (byte
= off
; byte
< off
+ size
; byte
++)
267 if (byte
< min_sp_off
268 || byte
>= max_sp_off
269 || !bitmap_clear_bit (sp_bytes
, byte
- min_sp_off
))
275 /* If MEM has sp address, return 0, if it has sp + const address,
276 return that const, if it has reg address where reg is set to sp + const
277 and FAST is false, return const, otherwise return
278 INTTYPE_MINUMUM (HOST_WIDE_INT). */
281 sp_based_mem_offset (rtx_call_insn
*call_insn
, const_rtx mem
, bool fast
)
283 HOST_WIDE_INT off
= 0;
284 rtx addr
= XEXP (mem
, 0);
285 if (GET_CODE (addr
) == PLUS
286 && REG_P (XEXP (addr
, 0))
287 && CONST_INT_P (XEXP (addr
, 1)))
289 off
= INTVAL (XEXP (addr
, 1));
290 addr
= XEXP (addr
, 0);
292 if (addr
== stack_pointer_rtx
)
295 if (!REG_P (addr
) || fast
)
296 return INTTYPE_MINIMUM (HOST_WIDE_INT
);
298 /* If not fast, use chains to see if addr wasn't set to sp + offset. */
300 FOR_EACH_INSN_USE (use
, call_insn
)
301 if (rtx_equal_p (addr
, DF_REF_REG (use
)))
305 return INTTYPE_MINIMUM (HOST_WIDE_INT
);
307 struct df_link
*defs
;
308 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
309 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
313 return INTTYPE_MINIMUM (HOST_WIDE_INT
);
315 rtx set
= single_set (DF_REF_INSN (defs
->ref
));
317 return INTTYPE_MINIMUM (HOST_WIDE_INT
);
319 if (GET_CODE (SET_SRC (set
)) != PLUS
320 || XEXP (SET_SRC (set
), 0) != stack_pointer_rtx
321 || !CONST_INT_P (XEXP (SET_SRC (set
), 1)))
322 return INTTYPE_MINIMUM (HOST_WIDE_INT
);
324 off
+= INTVAL (XEXP (SET_SRC (set
), 1));
328 /* Try to find all stack stores of CALL_INSN arguments if
329 ACCUMULATE_OUTGOING_ARGS. If all stack stores have been found
330 and it is therefore safe to eliminate the call, return true,
331 otherwise return false. This function should be first called
332 with DO_MARK false, and only when the CALL_INSN is actually
333 going to be marked called again with DO_MARK true. */
336 find_call_stack_args (rtx_call_insn
*call_insn
, bool do_mark
, bool fast
,
340 rtx_insn
*insn
, *prev_insn
;
342 HOST_WIDE_INT min_sp_off
, max_sp_off
;
345 gcc_assert (CALL_P (call_insn
));
346 if (!ACCUMULATE_OUTGOING_ARGS
)
351 gcc_assert (arg_stores
);
352 bitmap_clear (arg_stores
);
355 min_sp_off
= INTTYPE_MAXIMUM (HOST_WIDE_INT
);
358 /* First determine the minimum and maximum offset from sp for
360 for (p
= CALL_INSN_FUNCTION_USAGE (call_insn
); p
; p
= XEXP (p
, 1))
361 if (GET_CODE (XEXP (p
, 0)) == USE
362 && MEM_P (XEXP (XEXP (p
, 0), 0)))
364 rtx mem
= XEXP (XEXP (p
, 0), 0);
366 if (!MEM_SIZE_KNOWN_P (mem
) || !MEM_SIZE (mem
).is_constant (&size
))
368 HOST_WIDE_INT off
= sp_based_mem_offset (call_insn
, mem
, fast
);
369 if (off
== INTTYPE_MINIMUM (HOST_WIDE_INT
))
371 min_sp_off
= MIN (min_sp_off
, off
);
372 max_sp_off
= MAX (max_sp_off
, off
+ size
);
375 if (min_sp_off
>= max_sp_off
)
377 sp_bytes
= BITMAP_ALLOC (NULL
);
379 /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
380 which contain arguments. Checking has been done in the previous
382 for (p
= CALL_INSN_FUNCTION_USAGE (call_insn
); p
; p
= XEXP (p
, 1))
383 if (GET_CODE (XEXP (p
, 0)) == USE
384 && MEM_P (XEXP (XEXP (p
, 0), 0)))
386 rtx mem
= XEXP (XEXP (p
, 0), 0);
387 /* Checked in the previous iteration. */
388 HOST_WIDE_INT size
= MEM_SIZE (mem
).to_constant ();
389 HOST_WIDE_INT off
= sp_based_mem_offset (call_insn
, mem
, fast
);
390 gcc_checking_assert (off
!= INTTYPE_MINIMUM (HOST_WIDE_INT
));
391 for (HOST_WIDE_INT byte
= off
; byte
< off
+ size
; byte
++)
392 if (!bitmap_set_bit (sp_bytes
, byte
- min_sp_off
))
396 /* Walk backwards, looking for argument stores. The search stops
397 when seeing another call, sp adjustment or memory store other than
400 for (insn
= PREV_INSN (call_insn
); insn
; insn
= prev_insn
)
402 if (insn
== BB_HEAD (BLOCK_FOR_INSN (call_insn
)))
405 prev_insn
= PREV_INSN (insn
);
410 if (!NONDEBUG_INSN_P (insn
))
413 rtx set
= single_set (insn
);
414 if (!set
|| SET_DEST (set
) == stack_pointer_rtx
)
417 if (!MEM_P (SET_DEST (set
)))
420 rtx mem
= SET_DEST (set
);
421 HOST_WIDE_INT off
= sp_based_mem_offset (call_insn
, mem
, fast
);
422 if (off
== INTTYPE_MINIMUM (HOST_WIDE_INT
))
426 if (!MEM_SIZE_KNOWN_P (mem
)
427 || !MEM_SIZE (mem
).is_constant (&size
)
428 || !check_argument_store (size
, off
, min_sp_off
,
429 max_sp_off
, sp_bytes
))
432 if (!deletable_insn_p (insn
, fast
, NULL
))
436 mark_insn (insn
, fast
);
438 bitmap_set_bit (arg_stores
, INSN_UID (insn
));
440 if (bitmap_empty_p (sp_bytes
))
447 BITMAP_FREE (sp_bytes
);
448 if (!ret
&& arg_stores
)
449 bitmap_clear (arg_stores
);
455 /* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN
459 remove_reg_equal_equiv_notes_for_defs (rtx_insn
*insn
)
463 FOR_EACH_INSN_DEF (def
, insn
)
464 remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (def
));
467 /* Scan all BBs for debug insns and reset those that reference values
468 defined in unmarked insns. */
471 reset_unmarked_insns_debug_uses (void)
474 rtx_insn
*insn
, *next
;
476 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
477 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, next
)
478 if (DEBUG_INSN_P (insn
))
482 FOR_EACH_INSN_USE (use
, insn
)
484 struct df_link
*defs
;
485 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
488 if (DF_REF_IS_ARTIFICIAL (defs
->ref
))
490 ref_insn
= DF_REF_INSN (defs
->ref
);
491 if (!marked_insn_p (ref_insn
))
496 /* ??? FIXME could we propagate the values assigned to
498 INSN_VAR_LOCATION_LOC (insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
499 df_insn_rescan_debug_internal (insn
);
505 /* Delete every instruction that hasn't been marked. */
508 delete_unmarked_insns (void)
511 rtx_insn
*insn
, *next
;
512 bool must_clean
= false;
514 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
515 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, next
)
516 if (NONDEBUG_INSN_P (insn
))
518 rtx turn_into_use
= NULL_RTX
;
520 /* Always delete no-op moves. */
521 if (noop_move_p (insn
)
522 /* Unless the no-op move can throw and we are not allowed
524 && (!cfun
->can_throw_non_call_exceptions
525 || (cfun
->can_delete_dead_exceptions
&& can_alter_cfg
)
526 || insn_nothrow_p (insn
)))
528 if (RTX_FRAME_RELATED_P (insn
))
530 = find_reg_note (insn
, REG_CFA_RESTORE
, NULL
);
531 if (turn_into_use
&& REG_P (XEXP (turn_into_use
, 0)))
532 turn_into_use
= XEXP (turn_into_use
, 0);
534 turn_into_use
= NULL_RTX
;
537 /* Otherwise rely only on the DCE algorithm. */
538 else if (marked_insn_p (insn
))
541 /* Beware that reaching a dbg counter limit here can result
542 in miscompiled file. This occurs when a group of insns
543 must be deleted together, typically because the kept insn
544 depends on the output from the deleted insn. Deleting
545 this insns in reverse order (both at the bb level and
546 when looking at the blocks) minimizes this, but does not
547 eliminate it, since it is possible for the using insn to
548 be top of a block and the producer to be at the bottom of
549 the block. However, in most cases this will only result
550 in an uninitialized use of an insn that is dead anyway.
552 However, there is one rare case that will cause a
553 miscompile: deletion of non-looping pure and constant
554 calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
555 In this case it is possible to remove the call, but leave
556 the argument pushes to the stack. Because of the changes
557 to the stack pointer, this will almost always lead to a
563 fprintf (dump_file
, "DCE: Deleting insn %d\n", INSN_UID (insn
));
565 /* Before we delete the insn we have to remove the REG_EQUAL notes
566 for the destination regs in order to avoid dangling notes. */
567 remove_reg_equal_equiv_notes_for_defs (insn
);
571 /* Don't remove frame related noop moves if they cary
572 REG_CFA_RESTORE note, while we don't need to emit any code,
573 we need it to emit the CFI restore note. */
575 = gen_rtx_USE (GET_MODE (turn_into_use
), turn_into_use
);
576 INSN_CODE (insn
) = -1;
577 df_insn_rescan (insn
);
580 /* Now delete the insn. */
581 must_clean
|= delete_insn_and_edges (insn
);
584 /* Deleted a pure or const call. */
587 gcc_assert (can_alter_cfg
);
588 delete_unreachable_blocks ();
589 free_dominance_info (CDI_DOMINATORS
);
594 /* Go through the instructions and mark those whose necessity is not
595 dependent on inter-instruction information. Make sure all other
596 instructions are not marked. */
599 prescan_insns_for_dce (bool fast
)
602 rtx_insn
*insn
, *prev
;
603 bitmap arg_stores
= NULL
;
606 fprintf (dump_file
, "Finding needed instructions:\n");
608 if (!df_in_progress
&& ACCUMULATE_OUTGOING_ARGS
)
609 arg_stores
= BITMAP_ALLOC (NULL
);
611 FOR_EACH_BB_FN (bb
, cfun
)
613 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, prev
)
614 if (NONDEBUG_INSN_P (insn
))
616 /* Don't mark argument stores now. They will be marked
617 if needed when the associated CALL is marked. */
618 if (arg_stores
&& bitmap_bit_p (arg_stores
, INSN_UID (insn
)))
620 if (deletable_insn_p (insn
, fast
, arg_stores
))
621 mark_nonreg_stores (PATTERN (insn
), insn
, fast
);
623 mark_insn (insn
, fast
);
625 /* find_call_stack_args only looks at argument stores in the
628 bitmap_clear (arg_stores
);
632 BITMAP_FREE (arg_stores
);
635 fprintf (dump_file
, "Finished finding needed instructions:\n");
639 /* UD-based DSE routines. */
641 /* Mark instructions that define artificially-used registers, such as
642 the frame pointer and the stack pointer. */
645 mark_artificial_uses (void)
648 struct df_link
*defs
;
651 FOR_ALL_BB_FN (bb
, cfun
)
652 FOR_EACH_ARTIFICIAL_USE (use
, bb
->index
)
653 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
654 if (!DF_REF_IS_ARTIFICIAL (defs
->ref
))
655 mark_insn (DF_REF_INSN (defs
->ref
), false);
659 /* Mark every instruction that defines a register value that INSN uses. */
662 mark_reg_dependencies (rtx_insn
*insn
)
664 struct df_link
*defs
;
667 if (DEBUG_INSN_P (insn
))
670 FOR_EACH_INSN_USE (use
, insn
)
674 fprintf (dump_file
, "Processing use of ");
675 print_simple_rtl (dump_file
, DF_REF_REG (use
));
676 fprintf (dump_file
, " in insn %d:\n", INSN_UID (insn
));
678 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
679 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
680 mark_insn (DF_REF_INSN (defs
->ref
), false);
685 /* Initialize global variables for a new DCE pass. */
694 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
695 df_chain_add_problem (DF_UD_CHAIN
);
705 bitmap_obstack_initialize (&dce_blocks_bitmap_obstack
);
706 bitmap_obstack_initialize (&dce_tmp_bitmap_obstack
);
707 can_alter_cfg
= false;
710 can_alter_cfg
= true;
712 marked
= sbitmap_alloc (get_max_uid () + 1);
713 bitmap_clear (marked
);
717 /* Free the data allocated by init_dce. */
722 sbitmap_free (marked
);
726 bitmap_obstack_release (&dce_blocks_bitmap_obstack
);
727 bitmap_obstack_release (&dce_tmp_bitmap_obstack
);
732 /* UD-chain based DCE. */
735 rest_of_handle_ud_dce (void)
741 prescan_insns_for_dce (false);
742 mark_artificial_uses ();
743 while (worklist
.length () > 0)
745 insn
= worklist
.pop ();
746 mark_reg_dependencies (insn
);
750 if (MAY_HAVE_DEBUG_BIND_INSNS
)
751 reset_unmarked_insns_debug_uses ();
753 /* Before any insns are deleted, we must remove the chains since
754 they are not bidirectional. */
755 df_remove_problem (df_chain
);
756 delete_unmarked_insns ();
765 const pass_data pass_data_ud_rtl_dce
=
769 OPTGROUP_NONE
, /* optinfo_flags */
771 0, /* properties_required */
772 0, /* properties_provided */
773 0, /* properties_destroyed */
774 0, /* todo_flags_start */
775 TODO_df_finish
, /* todo_flags_finish */
778 class pass_ud_rtl_dce
: public rtl_opt_pass
781 pass_ud_rtl_dce (gcc::context
*ctxt
)
782 : rtl_opt_pass (pass_data_ud_rtl_dce
, ctxt
)
785 /* opt_pass methods: */
786 virtual bool gate (function
*)
788 return optimize
> 1 && flag_dce
&& dbg_cnt (dce_ud
);
791 virtual unsigned int execute (function
*)
793 return rest_of_handle_ud_dce ();
796 }; // class pass_ud_rtl_dce
801 make_pass_ud_rtl_dce (gcc::context
*ctxt
)
803 return new pass_ud_rtl_dce (ctxt
);
807 /* -------------------------------------------------------------------------
809 ------------------------------------------------------------------------- */
811 /* Process basic block BB. Return true if the live_in set has
812 changed. REDO_OUT is true if the info at the bottom of the block
813 needs to be recalculated before starting. AU is the proper set of
814 artificial uses. Track global substitution of uses of dead pseudos
815 in debug insns using GLOBAL_DEBUG. */
818 word_dce_process_block (basic_block bb
, bool redo_out
,
819 struct dead_debug_global
*global_debug
)
821 bitmap local_live
= BITMAP_ALLOC (&dce_tmp_bitmap_obstack
);
824 struct dead_debug_local debug
;
828 /* Need to redo the live_out set of this block if when one of
829 the succs of this block has had a change in it live in
833 df_confluence_function_n con_fun_n
= df_word_lr
->problem
->con_fun_n
;
834 bitmap_clear (DF_WORD_LR_OUT (bb
));
835 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
841 fprintf (dump_file
, "processing block %d live out = ", bb
->index
);
842 df_print_word_regset (dump_file
, DF_WORD_LR_OUT (bb
));
845 bitmap_copy (local_live
, DF_WORD_LR_OUT (bb
));
846 dead_debug_local_init (&debug
, NULL
, global_debug
);
848 FOR_BB_INSNS_REVERSE (bb
, insn
)
849 if (DEBUG_INSN_P (insn
))
852 FOR_EACH_INSN_USE (use
, insn
)
853 if (DF_REF_REGNO (use
) >= FIRST_PSEUDO_REGISTER
854 && known_eq (GET_MODE_SIZE (GET_MODE (DF_REF_REAL_REG (use
))),
856 && !bitmap_bit_p (local_live
, 2 * DF_REF_REGNO (use
))
857 && !bitmap_bit_p (local_live
, 2 * DF_REF_REGNO (use
) + 1))
858 dead_debug_add (&debug
, use
, DF_REF_REGNO (use
));
860 else if (INSN_P (insn
))
864 /* No matter if the instruction is needed or not, we remove
865 any regno in the defs from the live set. */
866 any_changed
= df_word_lr_simulate_defs (insn
, local_live
);
868 mark_insn (insn
, true);
870 /* On the other hand, we do not allow the dead uses to set
871 anything in local_live. */
872 if (marked_insn_p (insn
))
873 df_word_lr_simulate_uses (insn
, local_live
);
875 /* Insert debug temps for dead REGs used in subsequent debug
876 insns. We may have to emit a debug temp even if the insn
877 was marked, in case the debug use was after the point of
879 if (debug
.used
&& !bitmap_empty_p (debug
.used
))
883 FOR_EACH_INSN_DEF (def
, insn
)
884 dead_debug_insert_temp (&debug
, DF_REF_REGNO (def
), insn
,
886 && !control_flow_insn_p (insn
)
887 ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
888 : DEBUG_TEMP_BEFORE_WITH_VALUE
);
893 fprintf (dump_file
, "finished processing insn %d live out = ",
895 df_print_word_regset (dump_file
, local_live
);
899 block_changed
= !bitmap_equal_p (local_live
, DF_WORD_LR_IN (bb
));
901 bitmap_copy (DF_WORD_LR_IN (bb
), local_live
);
903 dead_debug_local_finish (&debug
, NULL
);
904 BITMAP_FREE (local_live
);
905 return block_changed
;
909 /* Process basic block BB. Return true if the live_in set has
910 changed. REDO_OUT is true if the info at the bottom of the block
911 needs to be recalculated before starting. AU is the proper set of
912 artificial uses. Track global substitution of uses of dead pseudos
913 in debug insns using GLOBAL_DEBUG. */
916 dce_process_block (basic_block bb
, bool redo_out
, bitmap au
,
917 struct dead_debug_global
*global_debug
)
919 bitmap local_live
= BITMAP_ALLOC (&dce_tmp_bitmap_obstack
);
923 struct dead_debug_local debug
;
927 /* Need to redo the live_out set of this block if when one of
928 the succs of this block has had a change in it live in
932 df_confluence_function_n con_fun_n
= df_lr
->problem
->con_fun_n
;
933 bitmap_clear (DF_LR_OUT (bb
));
934 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
940 fprintf (dump_file
, "processing block %d lr out = ", bb
->index
);
941 df_print_regset (dump_file
, DF_LR_OUT (bb
));
944 bitmap_copy (local_live
, DF_LR_OUT (bb
));
946 df_simulate_initialize_backwards (bb
, local_live
);
947 dead_debug_local_init (&debug
, NULL
, global_debug
);
949 FOR_BB_INSNS_REVERSE (bb
, insn
)
950 if (DEBUG_INSN_P (insn
))
953 FOR_EACH_INSN_USE (use
, insn
)
954 if (!bitmap_bit_p (local_live
, DF_REF_REGNO (use
))
955 && !bitmap_bit_p (au
, DF_REF_REGNO (use
)))
956 dead_debug_add (&debug
, use
, DF_REF_REGNO (use
));
958 else if (INSN_P (insn
))
960 bool needed
= marked_insn_p (insn
);
962 /* The insn is needed if there is someone who uses the output. */
964 FOR_EACH_INSN_DEF (def
, insn
)
965 if (bitmap_bit_p (local_live
, DF_REF_REGNO (def
))
966 || bitmap_bit_p (au
, DF_REF_REGNO (def
)))
969 mark_insn (insn
, true);
973 /* No matter if the instruction is needed or not, we remove
974 any regno in the defs from the live set. */
975 df_simulate_defs (insn
, local_live
);
977 /* On the other hand, we do not allow the dead uses to set
978 anything in local_live. */
980 df_simulate_uses (insn
, local_live
);
982 /* Insert debug temps for dead REGs used in subsequent debug
983 insns. We may have to emit a debug temp even if the insn
984 was marked, in case the debug use was after the point of
986 if (debug
.used
&& !bitmap_empty_p (debug
.used
))
987 FOR_EACH_INSN_DEF (def
, insn
)
988 dead_debug_insert_temp (&debug
, DF_REF_REGNO (def
), insn
,
989 needed
&& !control_flow_insn_p (insn
)
990 ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
991 : DEBUG_TEMP_BEFORE_WITH_VALUE
);
994 dead_debug_local_finish (&debug
, NULL
);
995 df_simulate_finalize_backwards (bb
, local_live
);
997 block_changed
= !bitmap_equal_p (local_live
, DF_LR_IN (bb
));
999 bitmap_copy (DF_LR_IN (bb
), local_live
);
1001 BITMAP_FREE (local_live
);
1002 return block_changed
;
1006 /* Perform fast DCE once initialization is done. If WORD_LEVEL is
1007 true, use the word level dce, otherwise do it at the pseudo
1011 fast_dce (bool word_level
)
1013 int *postorder
= df_get_postorder (DF_BACKWARD
);
1014 int n_blocks
= df_get_n_blocks (DF_BACKWARD
);
1015 /* The set of blocks that have been seen on this iteration. */
1016 bitmap processed
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
1017 /* The set of blocks that need to have the out vectors reset because
1018 the in of one of their successors has changed. */
1019 bitmap redo_out
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
1020 bitmap all_blocks
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
1021 bool global_changed
= true;
1023 /* These regs are considered always live so if they end up dying
1024 because of some def, we need to bring the back again. Calling
1025 df_simulate_fixup_sets has the disadvantage of calling
1026 bb_has_eh_pred once per insn, so we cache the information
1028 bitmap au
= &df
->regular_block_artificial_uses
;
1029 bitmap au_eh
= &df
->eh_block_artificial_uses
;
1031 struct dead_debug_global global_debug
;
1033 prescan_insns_for_dce (true);
1035 for (i
= 0; i
< n_blocks
; i
++)
1036 bitmap_set_bit (all_blocks
, postorder
[i
]);
1038 dead_debug_global_init (&global_debug
, NULL
);
1040 while (global_changed
)
1042 global_changed
= false;
1044 for (i
= 0; i
< n_blocks
; i
++)
1046 int index
= postorder
[i
];
1047 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, index
);
1050 if (index
< NUM_FIXED_BLOCKS
)
1052 bitmap_set_bit (processed
, index
);
1058 = word_dce_process_block (bb
, bitmap_bit_p (redo_out
, index
),
1062 = dce_process_block (bb
, bitmap_bit_p (redo_out
, index
),
1063 bb_has_eh_pred (bb
) ? au_eh
: au
,
1065 bitmap_set_bit (processed
, index
);
1071 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1072 if (bitmap_bit_p (processed
, e
->src
->index
))
1073 /* Be tricky about when we need to iterate the
1074 analysis. We only have redo the analysis if the
1075 bitmaps change at the top of a block that is the
1077 global_changed
= true;
1079 bitmap_set_bit (redo_out
, e
->src
->index
);
1085 /* Turn off the RUN_DCE flag to prevent recursive calls to
1087 int old_flag
= df_clear_flags (DF_LR_RUN_DCE
);
1089 /* So something was deleted that requires a redo. Do it on
1091 delete_unmarked_insns ();
1092 bitmap_clear (marked
);
1093 bitmap_clear (processed
);
1094 bitmap_clear (redo_out
);
1096 /* We do not need to rescan any instructions. We only need
1097 to redo the dataflow equations for the blocks that had a
1098 change at the top of the block. Then we need to redo the
1101 df_analyze_problem (df_word_lr
, all_blocks
, postorder
, n_blocks
);
1103 df_analyze_problem (df_lr
, all_blocks
, postorder
, n_blocks
);
1105 if (old_flag
& DF_LR_RUN_DCE
)
1106 df_set_flags (DF_LR_RUN_DCE
);
1108 prescan_insns_for_dce (true);
1112 dead_debug_global_finish (&global_debug
, NULL
);
1114 delete_unmarked_insns ();
1116 BITMAP_FREE (processed
);
1117 BITMAP_FREE (redo_out
);
1118 BITMAP_FREE (all_blocks
);
1122 /* Fast register level DCE. */
1125 rest_of_handle_fast_dce (void)
1134 /* Fast byte level DCE. */
1144 timevar_push (TV_DCE
);
1145 old_flags
= df_clear_flags (DF_DEFER_INSN_RESCAN
+ DF_NO_INSN_RESCAN
);
1146 df_word_lr_add_problem ();
1150 df_set_flags (old_flags
);
1151 timevar_pop (TV_DCE
);
1155 /* This is an internal call that is used by the df live register
1156 problem to run fast dce as a side effect of creating the live
1157 information. The stack is organized so that the lr problem is run,
1158 this pass is run, which updates the live info and the df scanning
1159 info, and then returns to allow the rest of the problems to be run.
1161 This can be called by elsewhere but it will not update the bit
1162 vectors for any other problems than LR. */
1165 run_fast_df_dce (void)
1169 /* If dce is able to delete something, it has to happen
1170 immediately. Otherwise there will be problems handling the
1173 df_clear_flags (DF_DEFER_INSN_RESCAN
+ DF_NO_INSN_RESCAN
);
1175 df_in_progress
= true;
1176 rest_of_handle_fast_dce ();
1177 df_in_progress
= false;
1179 df_set_flags (old_flags
);
1184 /* Run a fast DCE pass. */
1190 rest_of_handle_fast_dce ();
1196 const pass_data pass_data_fast_rtl_dce
=
1198 RTL_PASS
, /* type */
1199 "rtl_dce", /* name */
1200 OPTGROUP_NONE
, /* optinfo_flags */
1202 0, /* properties_required */
1203 0, /* properties_provided */
1204 0, /* properties_destroyed */
1205 0, /* todo_flags_start */
1206 TODO_df_finish
, /* todo_flags_finish */
1209 class pass_fast_rtl_dce
: public rtl_opt_pass
1212 pass_fast_rtl_dce (gcc::context
*ctxt
)
1213 : rtl_opt_pass (pass_data_fast_rtl_dce
, ctxt
)
1216 /* opt_pass methods: */
1217 virtual bool gate (function
*)
1219 return optimize
> 0 && flag_dce
&& dbg_cnt (dce_fast
);
1222 virtual unsigned int execute (function
*)
1224 return rest_of_handle_fast_dce ();
1227 }; // class pass_fast_rtl_dce
1232 make_pass_fast_rtl_dce (gcc::context
*ctxt
)
1234 return new pass_fast_rtl_dce (ctxt
);