1 /* RTL dead code elimination.
2 Copyright (C) 2005, 2006, 2007, 2008 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"
28 #include "hard-reg-set.h"
34 #include "tree-pass.h"
38 DEF_VEC_ALLOC_I(int,heap
);
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 /* Instructions that have been marked but whose dependencies have not
50 yet been processed. */
51 static VEC(rtx
,heap
) *worklist
;
53 /* Bitmap of instructions marked as needed indexed by INSN_UID. */
54 static sbitmap marked
;
56 /* Bitmap obstacks used for block processing by the fast algorithm. */
57 static bitmap_obstack dce_blocks_bitmap_obstack
;
58 static bitmap_obstack dce_tmp_bitmap_obstack
;
61 /* A subroutine for which BODY is part of the instruction being tested;
62 either the top-level pattern, or an element of a PARALLEL. The
63 instruction is known not to be a bare USE or CLOBBER. */
66 deletable_insn_p_1 (rtx body
)
68 switch (GET_CODE (body
))
72 /* The UNSPEC case was added here because the ia-64 claims that
73 USEs do not work after reload and generates UNSPECS rather
74 than USEs. Since dce is run after reload we need to avoid
75 deleting these even if they are dead. If it turns out that
76 USEs really do work after reload, the ia-64 should be
77 changed, and the UNSPEC case can be removed. */
82 if (volatile_refs_p (body
))
85 if (flag_non_call_exceptions
&& may_trap_p (body
))
93 /* Return true if INSN is a normal instruction that can be deleted by
97 deletable_insn_p (rtx insn
, bool fast
)
103 /* We cannot delete calls inside of the recursive dce because
104 this may cause basic blocks to be deleted and this messes up
105 the rest of the stack of optimization passes. */
107 /* We cannot delete pure or const sibling calls because it is
108 hard to see the result. */
109 && (!SIBLING_CALL_P (insn
))
110 /* We can delete dead const or pure calls as long as they do not
112 && (RTL_CONST_OR_PURE_CALL_P (insn
)
113 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)))
116 if (!NONJUMP_INSN_P (insn
))
119 body
= PATTERN (insn
);
120 switch (GET_CODE (body
))
128 /* A CLOBBER of a dead pseudo register serves no purpose.
129 That is not necessarily true for hard registers until
132 return REG_P (x
) && (!HARD_REGISTER_P (x
) || reload_completed
);
135 /* Because of the way that use-def chains are built, it is not
136 possible to tell if the clobber is dead because it can
137 never be the target of a use-def chain. */
141 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; i
--)
142 if (!deletable_insn_p_1 (XVECEXP (body
, 0, i
)))
147 return deletable_insn_p_1 (body
);
152 /* Return true if INSN has been marked as needed. */
155 marked_insn_p (rtx insn
)
157 /* Artificial defs are always needed and they do not have an insn.
158 We should never see them here. */
160 return TEST_BIT (marked
, INSN_UID (insn
));
164 /* If INSN has not yet been marked as needed, mark it now, and add it to
168 mark_insn (rtx insn
, bool fast
)
170 if (!marked_insn_p (insn
))
173 VEC_safe_push (rtx
, heap
, worklist
, insn
);
174 SET_BIT (marked
, INSN_UID (insn
));
176 fprintf (dump_file
, " Adding insn %d to worklist\n", INSN_UID (insn
));
181 /* A note_stores callback used by mark_nonreg_stores. DATA is the
182 instruction containing DEST. */
185 mark_nonreg_stores_1 (rtx dest
, const_rtx pattern
, void *data
)
187 if (GET_CODE (pattern
) != CLOBBER
&& !REG_P (dest
))
188 mark_insn ((rtx
) data
, true);
192 /* A note_stores callback used by mark_nonreg_stores. DATA is the
193 instruction containing DEST. */
196 mark_nonreg_stores_2 (rtx dest
, const_rtx pattern
, void *data
)
198 if (GET_CODE (pattern
) != CLOBBER
&& !REG_P (dest
))
199 mark_insn ((rtx
) data
, false);
203 /* Mark INSN if BODY stores to a non-register destination. */
206 mark_nonreg_stores (rtx body
, rtx insn
, bool fast
)
209 note_stores (body
, mark_nonreg_stores_1
, insn
);
211 note_stores (body
, mark_nonreg_stores_2
, insn
);
215 /* Delete all REG_EQUAL notes of the registers INSN writes, to prevent
216 bad dangling REG_EQUAL notes. */
219 delete_corresponding_reg_eq_notes (rtx insn
)
222 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
224 df_ref def
= *def_rec
;
225 unsigned int regno
= DF_REF_REGNO (def
);
226 /* This loop is a little tricky. We cannot just go down the
227 chain because it is being modified by the actions in the
228 loop. So we just get the head. We plan to drain the list
230 while (DF_REG_EQ_USE_CHAIN (regno
))
232 df_ref eq_use
= DF_REG_EQ_USE_CHAIN (regno
);
233 rtx noted_insn
= DF_REF_INSN (eq_use
);
234 rtx note
= find_reg_note (noted_insn
, REG_EQUAL
, NULL_RTX
);
236 note
= find_reg_note (noted_insn
, REG_EQUIV
, NULL_RTX
);
238 /* This assert is generally triggered when someone deletes a
239 REG_EQUAL or REG_EQUIV note by hacking the list manually
240 rather than calling remove_note. */
242 remove_note (noted_insn
, note
);
248 /* Delete every instruction that hasn't been marked. */
251 delete_unmarked_insns (void)
255 bool must_clean
= false;
258 FOR_BB_INSNS_SAFE (bb
, insn
, next
)
261 /* Always delete no-op moves. */
262 if (noop_move_p (insn
))
265 /* Otherwise rely only on the DCE algorithm. */
266 else if (marked_insn_p (insn
))
273 fprintf (dump_file
, "DCE: Deleting insn %d\n", INSN_UID (insn
));
275 /* Before we delete the insn we have to delete REG_EQUAL notes
276 for the destination regs in order to avoid dangling notes. */
277 delete_corresponding_reg_eq_notes (insn
);
279 /* If a pure or const call is deleted, this may make the cfg
280 have unreachable blocks. We rememeber this and call
281 delete_unreachable_blocks at the end. */
285 /* Now delete the insn. */
286 delete_insn_and_edges (insn
);
289 /* Deleted a pure or const call. */
291 delete_unreachable_blocks ();
295 /* Go through the instructions and mark those whose necessity is not
296 dependent on inter-instruction information. Make sure all other
297 instructions are not marked. */
300 prescan_insns_for_dce (bool fast
)
306 fprintf (dump_file
, "Finding needed instructions:\n");
309 FOR_BB_INSNS_SAFE (bb
, insn
, next
)
312 if (deletable_insn_p (insn
, fast
))
313 mark_nonreg_stores (PATTERN (insn
), insn
, fast
);
315 mark_insn (insn
, fast
);
319 fprintf (dump_file
, "Finished finding needed instructions:\n");
323 /* UD-based DSE routines. */
325 /* Mark instructions that define artificially-used registers, such as
326 the frame pointer and the stack pointer. */
329 mark_artificial_uses (void)
332 struct df_link
*defs
;
337 for (use_rec
= df_get_artificial_uses (bb
->index
);
339 for (defs
= DF_REF_CHAIN (*use_rec
); defs
; defs
= defs
->next
)
340 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
341 mark_insn (DF_REF_INSN (defs
->ref
), false);
346 /* Mark every instruction that defines a register value that INSN uses. */
349 mark_reg_dependencies (rtx insn
)
351 struct df_link
*defs
;
354 for (use_rec
= DF_INSN_USES (insn
); *use_rec
; use_rec
++)
356 df_ref use
= *use_rec
;
359 fprintf (dump_file
, "Processing use of ");
360 print_simple_rtl (dump_file
, DF_REF_REG (use
));
361 fprintf (dump_file
, " in insn %d:\n", INSN_UID (insn
));
363 for (defs
= DF_REF_CHAIN (use
); defs
; defs
= defs
->next
)
364 if (! DF_REF_IS_ARTIFICIAL (defs
->ref
))
365 mark_insn (DF_REF_INSN (defs
->ref
), false);
370 /* Initialize global variables for a new DCE pass. */
378 df_chain_add_problem (DF_UD_CHAIN
);
387 bitmap_obstack_initialize (&dce_blocks_bitmap_obstack
);
388 bitmap_obstack_initialize (&dce_tmp_bitmap_obstack
);
391 marked
= sbitmap_alloc (get_max_uid () + 1);
392 sbitmap_zero (marked
);
396 /* Free the data allocated by init_dce. */
401 sbitmap_free (marked
);
405 bitmap_obstack_release (&dce_blocks_bitmap_obstack
);
406 bitmap_obstack_release (&dce_tmp_bitmap_obstack
);
411 /* UD-chain based DCE. */
414 rest_of_handle_ud_dce (void)
420 prescan_insns_for_dce (false);
421 mark_artificial_uses ();
422 while (VEC_length (rtx
, worklist
) > 0)
424 insn
= VEC_pop (rtx
, worklist
);
425 mark_reg_dependencies (insn
);
427 VEC_free (rtx
, heap
, worklist
);
429 /* Before any insns are deleted, we must remove the chains since
430 they are not bidirectional. */
431 df_remove_problem (df_chain
);
432 delete_unmarked_insns ();
442 return optimize
> 1 && flag_dce
446 struct rtl_opt_pass pass_ud_rtl_dce
=
451 gate_ud_dce
, /* gate */
452 rest_of_handle_ud_dce
, /* execute */
455 0, /* static_pass_number */
457 0, /* properties_required */
458 0, /* properties_provided */
459 0, /* properties_destroyed */
460 0, /* todo_flags_start */
462 TODO_df_finish
| TODO_verify_rtl_sharing
|
463 TODO_ggc_collect
/* todo_flags_finish */
468 /* -------------------------------------------------------------------------
470 ------------------------------------------------------------------------- */
472 /* Process basic block BB. Return true if the live_in set has
473 changed. REDO_OUT is true if the info at the bottom of the block
474 needs to be recalculated before starting. AU is the proper set of
478 byte_dce_process_block (basic_block bb
, bool redo_out
, bitmap au
)
480 bitmap local_live
= BITMAP_ALLOC (&dce_tmp_bitmap_obstack
);
487 /* Need to redo the live_out set of this block if when one of
488 the succs of this block has had a change in it live in
492 df_confluence_function_n con_fun_n
= df_byte_lr
->problem
->con_fun_n
;
493 bitmap_clear (DF_BYTE_LR_OUT (bb
));
494 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
500 fprintf (dump_file
, "processing block %d live out = ", bb
->index
);
501 df_print_byte_regset (dump_file
, DF_BYTE_LR_OUT (bb
));
504 bitmap_copy (local_live
, DF_BYTE_LR_OUT (bb
));
506 df_byte_lr_simulate_artificial_refs_at_end (bb
, local_live
);
508 FOR_BB_INSNS_REVERSE (bb
, insn
)
511 /* The insn is needed if there is someone who uses the output. */
512 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
514 df_ref def
= *def_rec
;
516 unsigned int dregno
= DF_REF_REGNO (def
);
517 unsigned int start
= df_byte_lr_get_regno_start (dregno
);
518 unsigned int len
= df_byte_lr_get_regno_len (dregno
);
522 /* This is one of the only places where DF_MM_MAY should
523 be used for defs. Need to make sure that we are
524 checking for all of the bits that may be used. */
526 if (!df_compute_accessed_bytes (def
, DF_MM_MAY
, &sb
, &lb
))
532 if (bitmap_bit_p (au
, dregno
))
534 mark_insn (insn
, true);
540 if (bitmap_bit_p (local_live
, start
++))
542 mark_insn (insn
, true);
549 /* No matter if the instruction is needed or not, we remove
550 any regno in the defs from the live set. */
551 df_byte_lr_simulate_defs (insn
, local_live
);
553 /* On the other hand, we do not allow the dead uses to set
554 anything in local_live. */
555 if (marked_insn_p (insn
))
556 df_byte_lr_simulate_uses (insn
, local_live
);
560 fprintf (dump_file
, "finished processing insn %d live out = ",
562 df_print_byte_regset (dump_file
, local_live
);
566 df_byte_lr_simulate_artificial_refs_at_top (bb
, local_live
);
568 block_changed
= !bitmap_equal_p (local_live
, DF_BYTE_LR_IN (bb
));
570 bitmap_copy (DF_BYTE_LR_IN (bb
), local_live
);
571 BITMAP_FREE (local_live
);
572 return block_changed
;
576 /* Process basic block BB. Return true if the live_in set has
577 changed. REDO_OUT is true if the info at the bottom of the block
578 needs to be recalculated before starting. AU is the proper set of
582 dce_process_block (basic_block bb
, bool redo_out
, bitmap au
)
584 bitmap local_live
= BITMAP_ALLOC (&dce_tmp_bitmap_obstack
);
591 /* Need to redo the live_out set of this block if when one of
592 the succs of this block has had a change in it live in
596 df_confluence_function_n con_fun_n
= df_lr
->problem
->con_fun_n
;
597 bitmap_clear (DF_LR_OUT (bb
));
598 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
604 fprintf (dump_file
, "processing block %d live out = ", bb
->index
);
605 df_print_regset (dump_file
, DF_LR_OUT (bb
));
608 bitmap_copy (local_live
, DF_LR_OUT (bb
));
610 df_simulate_initialize_backwards (bb
, local_live
);
612 FOR_BB_INSNS_REVERSE (bb
, insn
)
617 /* The insn is needed if there is someone who uses the output. */
618 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
619 if (bitmap_bit_p (local_live
, DF_REF_REGNO (*def_rec
))
620 || bitmap_bit_p (au
, DF_REF_REGNO (*def_rec
)))
627 mark_insn (insn
, true);
629 /* No matter if the instruction is needed or not, we remove
630 any regno in the defs from the live set. */
631 df_simulate_defs (insn
, local_live
);
633 /* On the other hand, we do not allow the dead uses to set
634 anything in local_live. */
635 if (marked_insn_p (insn
))
636 df_simulate_uses (insn
, local_live
);
639 df_simulate_finalize_backwards (bb
, local_live
);
641 block_changed
= !bitmap_equal_p (local_live
, DF_LR_IN (bb
));
643 bitmap_copy (DF_LR_IN (bb
), local_live
);
645 BITMAP_FREE (local_live
);
646 return block_changed
;
650 /* Perform fast DCE once initialization is done. If BYTE_LEVEL is
651 true, use the byte level dce, otherwise do it at the pseudo
655 fast_dce (bool byte_level
)
657 int *postorder
= df_get_postorder (DF_BACKWARD
);
658 int n_blocks
= df_get_n_blocks (DF_BACKWARD
);
659 /* The set of blocks that have been seen on this iteration. */
660 bitmap processed
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
661 /* The set of blocks that need to have the out vectors reset because
662 the in of one of their successors has changed. */
663 bitmap redo_out
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
664 bitmap all_blocks
= BITMAP_ALLOC (&dce_blocks_bitmap_obstack
);
665 bool global_changed
= true;
667 /* These regs are considered always live so if they end up dying
668 because of some def, we need to bring the back again. Calling
669 df_simulate_fixup_sets has the disadvantage of calling
670 bb_has_eh_pred once per insn, so we cache the information
672 bitmap au
= df
->regular_block_artificial_uses
;
673 bitmap au_eh
= df
->eh_block_artificial_uses
;
676 prescan_insns_for_dce (true);
678 for (i
= 0; i
< n_blocks
; i
++)
679 bitmap_set_bit (all_blocks
, postorder
[i
]);
681 while (global_changed
)
683 global_changed
= false;
685 for (i
= 0; i
< n_blocks
; i
++)
687 int index
= postorder
[i
];
688 basic_block bb
= BASIC_BLOCK (index
);
691 if (index
< NUM_FIXED_BLOCKS
)
693 bitmap_set_bit (processed
, index
);
699 = byte_dce_process_block (bb
, bitmap_bit_p (redo_out
, index
),
700 bb_has_eh_pred (bb
) ? au_eh
: au
);
703 = dce_process_block (bb
, bitmap_bit_p (redo_out
, index
),
704 bb_has_eh_pred (bb
) ? au_eh
: au
);
705 bitmap_set_bit (processed
, index
);
711 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
712 if (bitmap_bit_p (processed
, e
->src
->index
))
713 /* Be tricky about when we need to iterate the
714 analysis. We only have redo the analysis if the
715 bitmaps change at the top of a block that is the
717 global_changed
= true;
719 bitmap_set_bit (redo_out
, e
->src
->index
);
725 /* Turn off the RUN_DCE flag to prevent recursive calls to
727 int old_flag
= df_clear_flags (DF_LR_RUN_DCE
);
729 /* So something was deleted that requires a redo. Do it on
731 delete_unmarked_insns ();
732 sbitmap_zero (marked
);
733 bitmap_clear (processed
);
734 bitmap_clear (redo_out
);
736 /* We do not need to rescan any instructions. We only need
737 to redo the dataflow equations for the blocks that had a
738 change at the top of the block. Then we need to redo the
741 df_analyze_problem (df_byte_lr
, all_blocks
, postorder
, n_blocks
);
743 df_analyze_problem (df_lr
, all_blocks
, postorder
, n_blocks
);
745 if (old_flag
& DF_LR_RUN_DCE
)
746 df_set_flags (DF_LR_RUN_DCE
);
748 prescan_insns_for_dce (true);
752 delete_unmarked_insns ();
754 BITMAP_FREE (processed
);
755 BITMAP_FREE (redo_out
);
756 BITMAP_FREE (all_blocks
);
760 /* Fast register level DCE. */
763 rest_of_handle_fast_dce (void)
772 /* Fast byte level DCE. */
775 rest_of_handle_fast_byte_dce (void)
777 df_byte_lr_add_problem ();
785 /* This is an internal call that is used by the df live register
786 problem to run fast dce as a side effect of creating the live
787 information. The stack is organized so that the lr problem is run,
788 this pass is run, which updates the live info and the df scanning
789 info, and then returns to allow the rest of the problems to be run.
791 This can be called by elsewhere but it will not update the bit
792 vectors for any other problems than LR. */
795 run_fast_df_dce (void)
799 /* If dce is able to delete something, it has to happen
800 immediately. Otherwise there will be problems handling the
802 enum df_changeable_flags old_flags
803 = df_clear_flags (DF_DEFER_INSN_RESCAN
+ DF_NO_INSN_RESCAN
);
805 df_in_progress
= true;
806 rest_of_handle_fast_dce ();
807 df_in_progress
= false;
809 df_set_flags (old_flags
);
814 /* Run a fast DCE pass. */
820 rest_of_handle_fast_dce ();
827 return optimize
> 0 && flag_dce
828 && dbg_cnt (dce_fast
);
831 struct rtl_opt_pass pass_fast_rtl_dce
=
836 gate_fast_dce
, /* gate */
837 rest_of_handle_fast_dce
, /* execute */
840 0, /* static_pass_number */
842 0, /* properties_required */
843 0, /* properties_provided */
844 0, /* properties_destroyed */
845 0, /* todo_flags_start */
847 TODO_df_finish
| TODO_verify_rtl_sharing
|
848 TODO_ggc_collect
/* todo_flags_finish */
852 struct rtl_opt_pass pass_fast_rtl_byte_dce
=
856 "byte-dce", /* name */
857 gate_fast_dce
, /* gate */
858 rest_of_handle_fast_byte_dce
, /* execute */
861 0, /* static_pass_number */
863 0, /* properties_required */
864 0, /* properties_provided */
865 0, /* properties_destroyed */
866 0, /* todo_flags_start */
868 TODO_df_finish
| TODO_verify_rtl_sharing
|
869 TODO_ggc_collect
/* todo_flags_finish */