1 /* RTL dead code elimination.
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
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"
35 #include "tree-pass.h"
38 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
41 /* -------------------------------------------------------------------------
42 Core mark/delete routines
43 ------------------------------------------------------------------------- */
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;
49 /* True if we are allowed to alter the CFG in this pass. */
50 static bool can_alter_cfg
= false;
52 /* Instructions that have been marked but whose dependencies have not
53 yet been processed. */
54 static VEC(rtx
,heap
) *worklist
;
56 /* Bitmap of instructions marked as needed indexed by INSN_UID. */
57 static sbitmap marked
;
59 /* Bitmap obstacks used for block processing by the fast algorithm. */
60 static bitmap_obstack dce_blocks_bitmap_obstack
;
61 static bitmap_obstack dce_tmp_bitmap_obstack
;
63 static bool find_call_stack_args (rtx
, bool, bool, bitmap
);
65 /* A subroutine for which BODY is part of the instruction being tested;
66 either the top-level pattern, or an element of a PARALLEL. The
67 instruction is known not to be a bare USE or CLOBBER. */
70 deletable_insn_p_1 (rtx body
)
72 switch (GET_CODE (body
))
76 /* The UNSPEC case was added here because the ia-64 claims that
77 USEs do not work after reload and generates UNSPECS rather
78 than USEs. Since dce is run after reload we need to avoid
79 deleting these even if they are dead. If it turns out that
80 USEs really do work after reload, the ia-64 should be
81 changed, and the UNSPEC case can be removed. */
86 return !volatile_refs_p (body
);
91 /* Return true if INSN is a normal instruction that can be deleted by
95 deletable_insn_p (rtx 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 return find_call_stack_args (insn
, false, fast
, arg_stores
);
114 /* Don't delete jumps, notes and the like. */
115 if (!NONJUMP_INSN_P (insn
))
118 /* Don't delete insns that may throw if we cannot do so. */
119 if (!(cfun
->can_delete_dead_exceptions
&& can_alter_cfg
)
120 && !insn_nothrow_p (insn
))
123 body
= PATTERN (insn
);
124 switch (GET_CODE (body
))
133 /* A CLOBBER of a dead pseudo register serves no purpose.
134 That is not necessarily true for hard registers until
137 return REG_P (x
) && (!HARD_REGISTER_P (x
) || reload_completed
);
140 /* Because of the way that use-def chains are built, it is not
141 possible to tell if the clobber is dead because it can
142 never be the target of a use-def chain. */
146 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; i
--)
147 if (!deletable_insn_p_1 (XVECEXP (body
, 0, i
)))
152 return deletable_insn_p_1 (body
);
157 /* Return true if INSN has been marked as needed. */
160 marked_insn_p (rtx insn
)
162 /* Artificial defs are always needed and they do not have an insn.
163 We should never see them here. */
165 return TEST_BIT (marked
, INSN_UID (insn
));
169 /* If INSN has not yet been marked as needed, mark it now, and add it to
173 mark_insn (rtx insn
, bool fast
)
175 if (!marked_insn_p (insn
))
178 VEC_safe_push (rtx
, heap
, worklist
, insn
);
179 SET_BIT (marked
, INSN_UID (insn
));
181 fprintf (dump_file
, " Adding insn %d to worklist\n", INSN_UID (insn
));
184 && !SIBLING_CALL_P (insn
)
185 && (RTL_CONST_OR_PURE_CALL_P (insn
)
186 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)))
187 find_call_stack_args (insn
, true, fast
, NULL
);
192 /* A note_stores callback used by mark_nonreg_stores. DATA is the
193 instruction containing DEST. */
196 mark_nonreg_stores_1 (rtx dest
, const_rtx pattern
, void *data
)
198 if (GET_CODE (pattern
) != CLOBBER
&& !REG_P (dest
))
199 mark_insn ((rtx
) data
, true);
203 /* A note_stores callback used by mark_nonreg_stores. DATA is the
204 instruction containing DEST. */
207 mark_nonreg_stores_2 (rtx dest
, const_rtx pattern
, void *data
)
209 if (GET_CODE (pattern
) != CLOBBER
&& !REG_P (dest
))
210 mark_insn ((rtx
) data
, false);
214 /* Mark INSN if BODY stores to a non-register destination. */
217 mark_nonreg_stores (rtx body
, rtx insn
, bool fast
)
220 note_stores (body
, mark_nonreg_stores_1
, insn
);
222 note_stores (body
, mark_nonreg_stores_2
, insn
);
226 /* Return true if store to MEM, starting OFF bytes from stack pointer,
227 is a call argument store, and clear corresponding bits from SP_BYTES
231 check_argument_store (rtx mem
, HOST_WIDE_INT off
, HOST_WIDE_INT min_sp_off
,
232 HOST_WIDE_INT max_sp_off
, bitmap sp_bytes
)
235 for (byte
= off
; byte
< off
+ GET_MODE_SIZE (GET_MODE (mem
)); byte
++)
237 if (byte
< min_sp_off
238 || byte
>= max_sp_off
239 || !bitmap_clear_bit (sp_bytes
, byte
- min_sp_off
))
246 /* Try to find all stack stores of CALL_INSN arguments if
247 ACCUMULATE_OUTGOING_ARGS. If all stack stores have been found
248 and it is therefore safe to eliminate the call, return true,
249 otherwise return false. This function should be first called
250 with DO_MARK false, and only when the CALL_INSN is actually
251 going to be marked called again with DO_MARK true. */
254 find_call_stack_args (rtx call_insn
, bool do_mark
, bool fast
,
257 rtx p
, insn
, prev_insn
;
259 HOST_WIDE_INT min_sp_off
, max_sp_off
;
262 gcc_assert (CALL_P (call_insn
));
263 if (!ACCUMULATE_OUTGOING_ARGS
)
268 gcc_assert (arg_stores
);
269 bitmap_clear (arg_stores
);
272 min_sp_off
= INTTYPE_MAXIMUM (HOST_WIDE_INT
);
275 /* First determine the minimum and maximum offset from sp for
277 for (p
= CALL_INSN_FUNCTION_USAGE (call_insn
); p
; p
= XEXP (p
, 1))
278 if (GET_CODE (XEXP (p
, 0)) == USE
279 && MEM_P (XEXP (XEXP (p
, 0), 0)))
281 rtx mem
= XEXP (XEXP (p
, 0), 0), addr
;
282 HOST_WIDE_INT off
= 0, size
;
283 if (!MEM_SIZE_KNOWN_P (mem
))
285 size
= MEM_SIZE (mem
);
286 addr
= XEXP (mem
, 0);
287 if (GET_CODE (addr
) == PLUS
288 && REG_P (XEXP (addr
, 0))
289 && CONST_INT_P (XEXP (addr
, 1)))
291 off
= INTVAL (XEXP (addr
, 1));
292 addr
= XEXP (addr
, 0);
294 if (addr
!= stack_pointer_rtx
)
298 /* If not fast, use chains to see if addr wasn't set to
303 struct df_link
*defs
;
306 for (use_rec
= DF_INSN_USES (call_insn
); *use_rec
; use_rec
++)
307 if (rtx_equal_p (addr
, DF_REF_REG (*use_rec
)))
310 if (*use_rec
== NULL
)
313 for (defs
= DF_REF_CHAIN (*use_rec
); defs
; defs
= defs
->next
)
314 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
320 set
= single_set (DF_REF_INSN (defs
->ref
));
324 if (GET_CODE (SET_SRC (set
)) != PLUS
325 || XEXP (SET_SRC (set
), 0) != stack_pointer_rtx
326 || !CONST_INT_P (XEXP (SET_SRC (set
), 1)))
329 off
+= INTVAL (XEXP (SET_SRC (set
), 1));
334 min_sp_off
= MIN (min_sp_off
, off
);
335 max_sp_off
= MAX (max_sp_off
, off
+ size
);
338 if (min_sp_off
>= max_sp_off
)
340 sp_bytes
= BITMAP_ALLOC (NULL
);
342 /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
343 which contain arguments. Checking has been done in the previous
345 for (p
= CALL_INSN_FUNCTION_USAGE (call_insn
); p
; p
= XEXP (p
, 1))
346 if (GET_CODE (XEXP (p
, 0)) == USE
347 && MEM_P (XEXP (XEXP (p
, 0), 0)))
349 rtx mem
= XEXP (XEXP (p
, 0), 0), addr
;
350 HOST_WIDE_INT off
= 0, byte
;
351 addr
= XEXP (mem
, 0);
352 if (GET_CODE (addr
) == PLUS
353 && REG_P (XEXP (addr
, 0))
354 && CONST_INT_P (XEXP (addr
, 1)))
356 off
= INTVAL (XEXP (addr
, 1));
357 addr
= XEXP (addr
, 0);
359 if (addr
!= stack_pointer_rtx
)
362 struct df_link
*defs
;
365 for (use_rec
= DF_INSN_USES (call_insn
); *use_rec
; use_rec
++)
366 if (rtx_equal_p (addr
, DF_REF_REG (*use_rec
)))
369 for (defs
= DF_REF_CHAIN (*use_rec
); defs
; defs
= defs
->next
)
370 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
373 set
= single_set (DF_REF_INSN (defs
->ref
));
374 off
+= INTVAL (XEXP (SET_SRC (set
), 1));
376 for (byte
= off
; byte
< off
+ MEM_SIZE (mem
); byte
++)
378 if (!bitmap_set_bit (sp_bytes
, byte
- min_sp_off
))
383 /* Walk backwards, looking for argument stores. The search stops
384 when seeing another call, sp adjustment or memory store other than
387 for (insn
= PREV_INSN (call_insn
); insn
; insn
= prev_insn
)
392 if (insn
== BB_HEAD (BLOCK_FOR_INSN (call_insn
)))
393 prev_insn
= NULL_RTX
;
395 prev_insn
= PREV_INSN (insn
);
400 if (!NONDEBUG_INSN_P (insn
))
403 set
= single_set (insn
);
404 if (!set
|| SET_DEST (set
) == stack_pointer_rtx
)
407 if (!MEM_P (SET_DEST (set
)))
410 mem
= SET_DEST (set
);
411 addr
= XEXP (mem
, 0);
413 if (GET_CODE (addr
) == PLUS
414 && REG_P (XEXP (addr
, 0))
415 && CONST_INT_P (XEXP (addr
, 1)))
417 off
= INTVAL (XEXP (addr
, 1));
418 addr
= XEXP (addr
, 0);
420 if (addr
!= stack_pointer_rtx
)
427 struct df_link
*defs
;
430 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
431 if (rtx_equal_p (addr
, DF_REF_REG (*use_rec
)))
434 if (*use_rec
== NULL
)
437 for (defs
= DF_REF_CHAIN (*use_rec
); defs
; defs
= defs
->next
)
438 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
444 set
= single_set (DF_REF_INSN (defs
->ref
));
448 if (GET_CODE (SET_SRC (set
)) != PLUS
449 || XEXP (SET_SRC (set
), 0) != stack_pointer_rtx
450 || !CONST_INT_P (XEXP (SET_SRC (set
), 1)))
453 off
+= INTVAL (XEXP (SET_SRC (set
), 1));
459 if (GET_MODE_SIZE (GET_MODE (mem
)) == 0
460 || !check_argument_store (mem
, off
, min_sp_off
,
461 max_sp_off
, sp_bytes
))
464 if (!deletable_insn_p (insn
, fast
, NULL
))
468 mark_insn (insn
, fast
);
470 bitmap_set_bit (arg_stores
, INSN_UID (insn
));
472 if (bitmap_empty_p (sp_bytes
))
479 BITMAP_FREE (sp_bytes
);
480 if (!ret
&& arg_stores
)
481 bitmap_clear (arg_stores
);
487 /* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN
491 remove_reg_equal_equiv_notes_for_defs (rtx insn
)
495 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
496 remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (*def_rec
));
499 /* Scan all BBs for debug insns and reset those that reference values
500 defined in unmarked insns. */
503 reset_unmarked_insns_debug_uses (void)
508 FOR_EACH_BB_REVERSE (bb
)
509 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, next
)
510 if (DEBUG_INSN_P (insn
))
514 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
516 df_ref use
= *use_rec
;
517 struct df_link
*defs
;
518 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
521 if (DF_REF_IS_ARTIFICIAL (defs
->ref
))
523 ref_insn
= DF_REF_INSN (defs
->ref
);
524 if (!marked_insn_p (ref_insn
))
529 /* ??? FIXME could we propagate the values assigned to
531 INSN_VAR_LOCATION_LOC (insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
532 df_insn_rescan_debug_internal (insn
);
538 /* Delete every instruction that hasn't been marked. */
541 delete_unmarked_insns (void)
545 bool must_clean
= false;
547 FOR_EACH_BB_REVERSE (bb
)
548 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, next
)
549 if (NONDEBUG_INSN_P (insn
))
551 /* Always delete no-op moves. */
552 if (noop_move_p (insn
))
555 /* Otherwise rely only on the DCE algorithm. */
556 else if (marked_insn_p (insn
))
559 /* Beware that reaching a dbg counter limit here can result
560 in miscompiled file. This occurs when a group of insns
561 must be deleted together, typically because the kept insn
562 depends on the output from the deleted insn. Deleting
563 this insns in reverse order (both at the bb level and
564 when looking at the blocks) minimizes this, but does not
565 eliminate it, since it is possible for the using insn to
566 be top of a block and the producer to be at the bottom of
567 the block. However, in most cases this will only result
568 in an uninitialized use of an insn that is dead anyway.
570 However, there is one rare case that will cause a
571 miscompile: deletion of non-looping pure and constant
572 calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
573 In this case it is possible to remove the call, but leave
574 the argument pushes to the stack. Because of the changes
575 to the stack pointer, this will almost always lead to a
581 fprintf (dump_file
, "DCE: Deleting insn %d\n", INSN_UID (insn
));
583 /* Before we delete the insn we have to remove the REG_EQUAL notes
584 for the destination regs in order to avoid dangling notes. */
585 remove_reg_equal_equiv_notes_for_defs (insn
);
587 /* If a pure or const call is deleted, this may make the cfg
588 have unreachable blocks. We rememeber this and call
589 delete_unreachable_blocks at the end. */
593 /* Now delete the insn. */
594 delete_insn_and_edges (insn
);
597 /* Deleted a pure or const call. */
599 delete_unreachable_blocks ();
603 /* Go through the instructions and mark those whose necessity is not
604 dependent on inter-instruction information. Make sure all other
605 instructions are not marked. */
608 prescan_insns_for_dce (bool fast
)
612 bitmap arg_stores
= NULL
;
615 fprintf (dump_file
, "Finding needed instructions:\n");
617 if (!df_in_progress
&& ACCUMULATE_OUTGOING_ARGS
)
618 arg_stores
= BITMAP_ALLOC (NULL
);
622 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, prev
)
623 if (NONDEBUG_INSN_P (insn
))
625 /* Don't mark argument stores now. They will be marked
626 if needed when the associated CALL is marked. */
627 if (arg_stores
&& bitmap_bit_p (arg_stores
, INSN_UID (insn
)))
629 if (deletable_insn_p (insn
, fast
, arg_stores
))
630 mark_nonreg_stores (PATTERN (insn
), insn
, fast
);
632 mark_insn (insn
, fast
);
634 /* find_call_stack_args only looks at argument stores in the
637 bitmap_clear (arg_stores
);
641 BITMAP_FREE (arg_stores
);
644 fprintf (dump_file
, "Finished finding needed instructions:\n");
648 /* UD-based DSE routines. */
650 /* Mark instructions that define artificially-used registers, such as
651 the frame pointer and the stack pointer. */
654 mark_artificial_uses (void)
657 struct df_link
*defs
;
662 for (use_rec
= df_get_artificial_uses (bb
->index
);
664 for (defs
= DF_REF_CHAIN (*use_rec
); defs
; defs
= defs
->next
)
665 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
666 mark_insn (DF_REF_INSN (defs
->ref
), false);
671 /* Mark every instruction that defines a register value that INSN uses. */
674 mark_reg_dependencies (rtx insn
)
676 struct df_link
*defs
;
679 if (DEBUG_INSN_P (insn
))
682 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
684 df_ref use
= *use_rec
;
687 fprintf (dump_file
, "Processing use of ");
688 print_simple_rtl (dump_file
, DF_REF_REG (use
));
689 fprintf (dump_file
, " in insn %d:\n", INSN_UID (insn
));
691 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
692 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
693 mark_insn (DF_REF_INSN (defs
->ref
), false);
698 /* Initialize global variables for a new DCE pass. */
706 df_chain_add_problem (DF_UD_CHAIN
);
715 bitmap_obstack_initialize (&dce_blocks_bitmap_obstack
);
716 bitmap_obstack_initialize (&dce_tmp_bitmap_obstack
);
717 can_alter_cfg
= false;
720 can_alter_cfg
= true;
722 marked
= sbitmap_alloc (get_max_uid () + 1);
723 sbitmap_zero (marked
);
727 /* Free the data allocated by init_dce. */
732 sbitmap_free (marked
);
736 bitmap_obstack_release (&dce_blocks_bitmap_obstack
);
737 bitmap_obstack_release (&dce_tmp_bitmap_obstack
);
742 /* UD-chain based DCE. */
745 rest_of_handle_ud_dce (void)
751 prescan_insns_for_dce (false);
752 mark_artificial_uses ();
753 while (VEC_length (rtx
, worklist
) > 0)
755 insn
= VEC_pop (rtx
, worklist
);
756 mark_reg_dependencies (insn
);
758 VEC_free (rtx
, heap
, worklist
);
760 if (MAY_HAVE_DEBUG_INSNS
)
761 reset_unmarked_insns_debug_uses ();
763 /* Before any insns are deleted, we must remove the chains since
764 they are not bidirectional. */
765 df_remove_problem (df_chain
);
766 delete_unmarked_insns ();
776 return optimize
> 1 && flag_dce
780 struct rtl_opt_pass pass_ud_rtl_dce
=
785 gate_ud_dce
, /* gate */
786 rest_of_handle_ud_dce
, /* execute */
789 0, /* static_pass_number */
791 0, /* properties_required */
792 0, /* properties_provided */
793 0, /* properties_destroyed */
794 0, /* todo_flags_start */
795 TODO_df_finish
| TODO_verify_rtl_sharing
|
796 TODO_ggc_collect
/* todo_flags_finish */
801 /* -------------------------------------------------------------------------
803 ------------------------------------------------------------------------- */
805 /* Process basic block BB. Return true if the live_in set has
806 changed. REDO_OUT is true if the info at the bottom of the block
807 needs to be recalculated before starting. AU is the proper set of
811 word_dce_process_block (basic_block bb
, bool redo_out
)
813 bitmap local_live
= BITMAP_ALLOC (&dce_tmp_bitmap_obstack
);
816 struct dead_debug debug
;
820 /* Need to redo the live_out set of this block if when one of
821 the succs of this block has had a change in it live in
825 df_confluence_function_n con_fun_n
= df_word_lr
->problem
->con_fun_n
;
826 bitmap_clear (DF_WORD_LR_OUT (bb
));
827 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
833 fprintf (dump_file
, "processing block %d live out = ", bb
->index
);
834 df_print_word_regset (dump_file
, DF_WORD_LR_OUT (bb
));
837 bitmap_copy (local_live
, DF_WORD_LR_OUT (bb
));
838 dead_debug_init (&debug
, NULL
);
840 FOR_BB_INSNS_REVERSE (bb
, insn
)
841 if (DEBUG_INSN_P (insn
))
844 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
845 if (DF_REF_REGNO (*use_rec
) >= FIRST_PSEUDO_REGISTER
846 && (GET_MODE_SIZE (GET_MODE (DF_REF_REAL_REG (*use_rec
)))
847 == 2 * UNITS_PER_WORD
)
848 && !bitmap_bit_p (local_live
, 2 * DF_REF_REGNO (*use_rec
))
849 && !bitmap_bit_p (local_live
, 2 * DF_REF_REGNO (*use_rec
) + 1))
850 dead_debug_add (&debug
, *use_rec
, DF_REF_REGNO (*use_rec
));
852 else if (INSN_P (insn
))
856 /* No matter if the instruction is needed or not, we remove
857 any regno in the defs from the live set. */
858 any_changed
= df_word_lr_simulate_defs (insn
, local_live
);
860 mark_insn (insn
, true);
862 /* On the other hand, we do not allow the dead uses to set
863 anything in local_live. */
864 if (marked_insn_p (insn
))
865 df_word_lr_simulate_uses (insn
, local_live
);
867 /* Insert debug temps for dead REGs used in subsequent debug
868 insns. We may have to emit a debug temp even if the insn
869 was marked, in case the debug use was after the point of
871 if (debug
.used
&& !bitmap_empty_p (debug
.used
))
875 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
876 dead_debug_insert_temp (&debug
, DF_REF_REGNO (*def_rec
), insn
,
877 DEBUG_TEMP_BEFORE_WITH_VALUE
);
882 fprintf (dump_file
, "finished processing insn %d live out = ",
884 df_print_word_regset (dump_file
, local_live
);
888 block_changed
= !bitmap_equal_p (local_live
, DF_WORD_LR_IN (bb
));
890 bitmap_copy (DF_WORD_LR_IN (bb
), local_live
);
892 dead_debug_finish (&debug
, NULL
);
893 BITMAP_FREE (local_live
);
894 return block_changed
;
898 /* Process basic block BB. Return true if the live_in set has
899 changed. REDO_OUT is true if the info at the bottom of the block
900 needs to be recalculated before starting. AU is the proper set of
904 dce_process_block (basic_block bb
, bool redo_out
, bitmap au
)
906 bitmap local_live
= BITMAP_ALLOC (&dce_tmp_bitmap_obstack
);
910 struct dead_debug debug
;
914 /* Need to redo the live_out set of this block if when one of
915 the succs of this block has had a change in it live in
919 df_confluence_function_n con_fun_n
= df_lr
->problem
->con_fun_n
;
920 bitmap_clear (DF_LR_OUT (bb
));
921 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
927 fprintf (dump_file
, "processing block %d lr out = ", bb
->index
);
928 df_print_regset (dump_file
, DF_LR_OUT (bb
));
931 bitmap_copy (local_live
, DF_LR_OUT (bb
));
933 df_simulate_initialize_backwards (bb
, local_live
);
934 dead_debug_init (&debug
, NULL
);
936 FOR_BB_INSNS_REVERSE (bb
, insn
)
937 if (DEBUG_INSN_P (insn
))
940 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
941 if (!bitmap_bit_p (local_live
, DF_REF_REGNO (*use_rec
))
942 && !bitmap_bit_p (au
, DF_REF_REGNO (*use_rec
)))
943 dead_debug_add (&debug
, *use_rec
, DF_REF_REGNO (*use_rec
));
945 else if (INSN_P (insn
))
947 bool needed
= marked_insn_p (insn
);
949 /* The insn is needed if there is someone who uses the output. */
951 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
952 if (bitmap_bit_p (local_live
, DF_REF_REGNO (*def_rec
))
953 || bitmap_bit_p (au
, DF_REF_REGNO (*def_rec
)))
956 mark_insn (insn
, true);
960 /* No matter if the instruction is needed or not, we remove
961 any regno in the defs from the live set. */
962 df_simulate_defs (insn
, local_live
);
964 /* On the other hand, we do not allow the dead uses to set
965 anything in local_live. */
967 df_simulate_uses (insn
, local_live
);
969 /* Insert debug temps for dead REGs used in subsequent debug
970 insns. We may have to emit a debug temp even if the insn
971 was marked, in case the debug use was after the point of
973 if (debug
.used
&& !bitmap_empty_p (debug
.used
))
974 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
975 dead_debug_insert_temp (&debug
, DF_REF_REGNO (*def_rec
), insn
,
976 DEBUG_TEMP_BEFORE_WITH_VALUE
);
979 dead_debug_finish (&debug
, NULL
);
980 df_simulate_finalize_backwards (bb
, local_live
);
982 block_changed
= !bitmap_equal_p (local_live
, DF_LR_IN (bb
));
984 bitmap_copy (DF_LR_IN (bb
), local_live
);
986 BITMAP_FREE (local_live
);
987 return block_changed
;
991 /* Perform fast DCE once initialization is done. If WORD_LEVEL is
992 true, use the word level dce, otherwise do it at the pseudo
996 fast_dce (bool word_level
)
998 int *postorder
= df_get_postorder (DF_BACKWARD
);
999 int n_blocks
= df_get_n_blocks (DF_BACKWARD
);
1000 /* The set of blocks that have been seen on this iteration. */
1001 bitmap processed
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
1002 /* The set of blocks that need to have the out vectors reset because
1003 the in of one of their successors has changed. */
1004 bitmap redo_out
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
1005 bitmap all_blocks
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
1006 bool global_changed
= true;
1008 /* These regs are considered always live so if they end up dying
1009 because of some def, we need to bring the back again. Calling
1010 df_simulate_fixup_sets has the disadvantage of calling
1011 bb_has_eh_pred once per insn, so we cache the information
1013 bitmap au
= &df
->regular_block_artificial_uses
;
1014 bitmap au_eh
= &df
->eh_block_artificial_uses
;
1017 prescan_insns_for_dce (true);
1019 for (i
= 0; i
< n_blocks
; i
++)
1020 bitmap_set_bit (all_blocks
, postorder
[i
]);
1022 while (global_changed
)
1024 global_changed
= false;
1026 for (i
= 0; i
< n_blocks
; i
++)
1028 int index
= postorder
[i
];
1029 basic_block bb
= BASIC_BLOCK (index
);
1032 if (index
< NUM_FIXED_BLOCKS
)
1034 bitmap_set_bit (processed
, index
);
1040 = word_dce_process_block (bb
, bitmap_bit_p (redo_out
, index
));
1043 = dce_process_block (bb
, bitmap_bit_p (redo_out
, index
),
1044 bb_has_eh_pred (bb
) ? au_eh
: au
);
1045 bitmap_set_bit (processed
, index
);
1051 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1052 if (bitmap_bit_p (processed
, e
->src
->index
))
1053 /* Be tricky about when we need to iterate the
1054 analysis. We only have redo the analysis if the
1055 bitmaps change at the top of a block that is the
1057 global_changed
= true;
1059 bitmap_set_bit (redo_out
, e
->src
->index
);
1065 /* Turn off the RUN_DCE flag to prevent recursive calls to
1067 int old_flag
= df_clear_flags (DF_LR_RUN_DCE
);
1069 /* So something was deleted that requires a redo. Do it on
1071 delete_unmarked_insns ();
1072 sbitmap_zero (marked
);
1073 bitmap_clear (processed
);
1074 bitmap_clear (redo_out
);
1076 /* We do not need to rescan any instructions. We only need
1077 to redo the dataflow equations for the blocks that had a
1078 change at the top of the block. Then we need to redo the
1081 df_analyze_problem (df_word_lr
, all_blocks
, postorder
, n_blocks
);
1083 df_analyze_problem (df_lr
, all_blocks
, postorder
, n_blocks
);
1085 if (old_flag
& DF_LR_RUN_DCE
)
1086 df_set_flags (DF_LR_RUN_DCE
);
1088 prescan_insns_for_dce (true);
1092 delete_unmarked_insns ();
1094 BITMAP_FREE (processed
);
1095 BITMAP_FREE (redo_out
);
1096 BITMAP_FREE (all_blocks
);
1100 /* Fast register level DCE. */
1103 rest_of_handle_fast_dce (void)
1112 /* Fast byte level DCE. */
1122 timevar_push (TV_DCE
);
1123 old_flags
= df_clear_flags (DF_DEFER_INSN_RESCAN
+ DF_NO_INSN_RESCAN
);
1124 df_word_lr_add_problem ();
1128 df_set_flags (old_flags
);
1129 timevar_pop (TV_DCE
);
1133 /* This is an internal call that is used by the df live register
1134 problem to run fast dce as a side effect of creating the live
1135 information. The stack is organized so that the lr problem is run,
1136 this pass is run, which updates the live info and the df scanning
1137 info, and then returns to allow the rest of the problems to be run.
1139 This can be called by elsewhere but it will not update the bit
1140 vectors for any other problems than LR. */
1143 run_fast_df_dce (void)
1147 /* If dce is able to delete something, it has to happen
1148 immediately. Otherwise there will be problems handling the
1151 df_clear_flags (DF_DEFER_INSN_RESCAN
+ DF_NO_INSN_RESCAN
);
1153 df_in_progress
= true;
1154 rest_of_handle_fast_dce ();
1155 df_in_progress
= false;
1157 df_set_flags (old_flags
);
1162 /* Run a fast DCE pass. */
1168 rest_of_handle_fast_dce ();
1173 gate_fast_dce (void)
1175 return optimize
> 0 && flag_dce
1176 && dbg_cnt (dce_fast
);
1179 struct rtl_opt_pass pass_fast_rtl_dce
=
1183 "rtl_dce", /* name */
1184 gate_fast_dce
, /* gate */
1185 rest_of_handle_fast_dce
, /* execute */
1188 0, /* static_pass_number */
1190 0, /* properties_required */
1191 0, /* properties_provided */
1192 0, /* properties_destroyed */
1193 0, /* todo_flags_start */
1194 TODO_df_finish
| TODO_verify_rtl_sharing
|
1195 TODO_ggc_collect
/* todo_flags_finish */