PR middle-end/86864
[official-gcc.git] / gcc / dce.c
blob7fc3fd209b5adaf9c1b3b6051d82d6834bb16488
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
9 version.
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
14 for more details.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "rtl.h"
25 #include "tree.h"
26 #include "predict.h"
27 #include "df.h"
28 #include "memmodel.h"
29 #include "tm_p.h"
30 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
31 #include "cfgrtl.h"
32 #include "cfgbuild.h"
33 #include "cfgcleanup.h"
34 #include "dce.h"
35 #include "valtrack.h"
36 #include "tree-pass.h"
37 #include "dbgcnt.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. */
68 static bool
69 deletable_insn_p_1 (rtx body)
71 switch (GET_CODE (body))
73 case PREFETCH:
74 case TRAP_IF:
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. */
81 case UNSPEC:
82 return false;
84 default:
85 return !volatile_refs_p (body);
90 /* Return true if INSN is a normal instruction that can be deleted by
91 the DCE pass. */
93 static bool
94 deletable_insn_p (rtx_insn *insn, bool fast, bitmap arg_stores)
96 rtx body, x;
97 int i;
98 df_ref def;
100 if (CALL_P (insn)
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. */
104 && (!df_in_progress)
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
109 infinite loop. */
110 && (RTL_CONST_OR_PURE_CALL_P (insn)
111 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))
112 return find_call_stack_args (as_a <rtx_call_insn *> (insn), false,
113 fast, arg_stores);
115 /* Don't delete jumps, notes and the like. */
116 if (!NONJUMP_INSN_P (insn))
117 return false;
119 /* Don't delete insns that may throw if we cannot do so. */
120 if (!(cfun->can_delete_dead_exceptions && can_alter_cfg)
121 && !insn_nothrow_p (insn))
122 return false;
124 /* If INSN sets a global_reg, leave it untouched. */
125 FOR_EACH_INSN_DEF (def, insn)
126 if (HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
127 && global_regs[DF_REF_REGNO (def)])
128 return false;
129 /* Initialization of pseudo PIC register should never be removed. */
130 else if (DF_REF_REG (def) == pic_offset_table_rtx
131 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
132 return false;
134 /* Callee-save restores are needed. */
135 if (RTX_FRAME_RELATED_P (insn)
136 && crtl->shrink_wrapped_separate
137 && find_reg_note (insn, REG_CFA_RESTORE, NULL))
138 return false;
140 body = PATTERN (insn);
141 switch (GET_CODE (body))
143 case USE:
144 case VAR_LOCATION:
145 return false;
147 case CLOBBER:
148 case CLOBBER_HIGH:
149 if (fast)
151 /* A CLOBBER of a dead pseudo register serves no purpose.
152 That is not necessarily true for hard registers until
153 after reload. */
154 x = XEXP (body, 0);
155 return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);
157 else
158 /* Because of the way that use-def chains are built, it is not
159 possible to tell if the clobber is dead because it can
160 never be the target of a use-def chain. */
161 return false;
163 case PARALLEL:
164 for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
165 if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))
166 return false;
167 return true;
169 default:
170 return deletable_insn_p_1 (body);
175 /* Return true if INSN has been marked as needed. */
177 static inline int
178 marked_insn_p (rtx_insn *insn)
180 /* Artificial defs are always needed and they do not have an insn.
181 We should never see them here. */
182 gcc_assert (insn);
183 return bitmap_bit_p (marked, INSN_UID (insn));
187 /* If INSN has not yet been marked as needed, mark it now, and add it to
188 the worklist. */
190 static void
191 mark_insn (rtx_insn *insn, bool fast)
193 if (!marked_insn_p (insn))
195 if (!fast)
196 worklist.safe_push (insn);
197 bitmap_set_bit (marked, INSN_UID (insn));
198 if (dump_file)
199 fprintf (dump_file, " Adding insn %d to worklist\n", INSN_UID (insn));
200 if (CALL_P (insn)
201 && !df_in_progress
202 && !SIBLING_CALL_P (insn)
203 && (RTL_CONST_OR_PURE_CALL_P (insn)
204 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))
205 find_call_stack_args (as_a <rtx_call_insn *> (insn), true, fast, NULL);
210 /* A note_stores callback used by mark_nonreg_stores. DATA is the
211 instruction containing DEST. */
213 static void
214 mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data)
216 if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
218 gcc_checking_assert (GET_CODE (pattern) != CLOBBER_HIGH);
219 mark_insn ((rtx_insn *) data, true);
224 /* A note_stores callback used by mark_nonreg_stores. DATA is the
225 instruction containing DEST. */
227 static void
228 mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)
230 if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
232 gcc_checking_assert (GET_CODE (pattern) != CLOBBER_HIGH);
233 mark_insn ((rtx_insn *) data, false);
238 /* Mark INSN if BODY stores to a non-register destination. */
240 static void
241 mark_nonreg_stores (rtx body, rtx_insn *insn, bool fast)
243 if (fast)
244 note_stores (body, mark_nonreg_stores_1, insn);
245 else
246 note_stores (body, mark_nonreg_stores_2, insn);
250 /* Return true if a store to SIZE bytes, starting OFF bytes from stack pointer,
251 is a call argument store, and clear corresponding bits from SP_BYTES
252 bitmap if it is. */
254 static bool
255 check_argument_store (HOST_WIDE_INT size, HOST_WIDE_INT off,
256 HOST_WIDE_INT min_sp_off, HOST_WIDE_INT max_sp_off,
257 bitmap sp_bytes)
259 HOST_WIDE_INT byte;
260 for (byte = off; byte < off + size; byte++)
262 if (byte < min_sp_off
263 || byte >= max_sp_off
264 || !bitmap_clear_bit (sp_bytes, byte - min_sp_off))
265 return false;
267 return true;
271 /* Try to find all stack stores of CALL_INSN arguments if
272 ACCUMULATE_OUTGOING_ARGS. If all stack stores have been found
273 and it is therefore safe to eliminate the call, return true,
274 otherwise return false. This function should be first called
275 with DO_MARK false, and only when the CALL_INSN is actually
276 going to be marked called again with DO_MARK true. */
278 static bool
279 find_call_stack_args (rtx_call_insn *call_insn, bool do_mark, bool fast,
280 bitmap arg_stores)
282 rtx p;
283 rtx_insn *insn, *prev_insn;
284 bool ret;
285 HOST_WIDE_INT min_sp_off, max_sp_off;
286 bitmap sp_bytes;
288 gcc_assert (CALL_P (call_insn));
289 if (!ACCUMULATE_OUTGOING_ARGS)
290 return true;
292 if (!do_mark)
294 gcc_assert (arg_stores);
295 bitmap_clear (arg_stores);
298 min_sp_off = INTTYPE_MAXIMUM (HOST_WIDE_INT);
299 max_sp_off = 0;
301 /* First determine the minimum and maximum offset from sp for
302 stored arguments. */
303 for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
304 if (GET_CODE (XEXP (p, 0)) == USE
305 && MEM_P (XEXP (XEXP (p, 0), 0)))
307 rtx mem = XEXP (XEXP (p, 0), 0), addr;
308 HOST_WIDE_INT off = 0, size;
309 if (!MEM_SIZE_KNOWN_P (mem) || !MEM_SIZE (mem).is_constant (&size))
310 return false;
311 addr = XEXP (mem, 0);
312 if (GET_CODE (addr) == PLUS
313 && REG_P (XEXP (addr, 0))
314 && CONST_INT_P (XEXP (addr, 1)))
316 off = INTVAL (XEXP (addr, 1));
317 addr = XEXP (addr, 0);
319 if (addr != stack_pointer_rtx)
321 if (!REG_P (addr))
322 return false;
323 /* If not fast, use chains to see if addr wasn't set to
324 sp + offset. */
325 if (!fast)
327 df_ref use;
328 struct df_link *defs;
329 rtx set;
331 FOR_EACH_INSN_USE (use, call_insn)
332 if (rtx_equal_p (addr, DF_REF_REG (use)))
333 break;
335 if (use == NULL)
336 return false;
338 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
339 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
340 break;
342 if (defs == NULL)
343 return false;
345 set = single_set (DF_REF_INSN (defs->ref));
346 if (!set)
347 return false;
349 if (GET_CODE (SET_SRC (set)) != PLUS
350 || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
351 || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
352 return false;
354 off += INTVAL (XEXP (SET_SRC (set), 1));
356 else
357 return false;
359 min_sp_off = MIN (min_sp_off, off);
360 max_sp_off = MAX (max_sp_off, off + size);
363 if (min_sp_off >= max_sp_off)
364 return true;
365 sp_bytes = BITMAP_ALLOC (NULL);
367 /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
368 which contain arguments. Checking has been done in the previous
369 loop. */
370 for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
371 if (GET_CODE (XEXP (p, 0)) == USE
372 && MEM_P (XEXP (XEXP (p, 0), 0)))
374 rtx mem = XEXP (XEXP (p, 0), 0), addr;
375 HOST_WIDE_INT off = 0, byte, size;
376 /* Checked in the previous iteration. */
377 size = MEM_SIZE (mem).to_constant ();
378 addr = XEXP (mem, 0);
379 if (GET_CODE (addr) == PLUS
380 && REG_P (XEXP (addr, 0))
381 && CONST_INT_P (XEXP (addr, 1)))
383 off = INTVAL (XEXP (addr, 1));
384 addr = XEXP (addr, 0);
386 if (addr != stack_pointer_rtx)
388 df_ref use;
389 struct df_link *defs;
390 rtx set;
392 FOR_EACH_INSN_USE (use, call_insn)
393 if (rtx_equal_p (addr, DF_REF_REG (use)))
394 break;
396 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
397 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
398 break;
400 set = single_set (DF_REF_INSN (defs->ref));
401 off += INTVAL (XEXP (SET_SRC (set), 1));
403 for (byte = off; byte < off + size; byte++)
405 if (!bitmap_set_bit (sp_bytes, byte - min_sp_off))
406 gcc_unreachable ();
410 /* Walk backwards, looking for argument stores. The search stops
411 when seeing another call, sp adjustment or memory store other than
412 argument store. */
413 ret = false;
414 for (insn = PREV_INSN (call_insn); insn; insn = prev_insn)
416 rtx set, mem, addr;
417 HOST_WIDE_INT off;
419 if (insn == BB_HEAD (BLOCK_FOR_INSN (call_insn)))
420 prev_insn = NULL;
421 else
422 prev_insn = PREV_INSN (insn);
424 if (CALL_P (insn))
425 break;
427 if (!NONDEBUG_INSN_P (insn))
428 continue;
430 set = single_set (insn);
431 if (!set || SET_DEST (set) == stack_pointer_rtx)
432 break;
434 if (!MEM_P (SET_DEST (set)))
435 continue;
437 mem = SET_DEST (set);
438 addr = XEXP (mem, 0);
439 off = 0;
440 if (GET_CODE (addr) == PLUS
441 && REG_P (XEXP (addr, 0))
442 && CONST_INT_P (XEXP (addr, 1)))
444 off = INTVAL (XEXP (addr, 1));
445 addr = XEXP (addr, 0);
447 if (addr != stack_pointer_rtx)
449 if (!REG_P (addr))
450 break;
451 if (!fast)
453 df_ref use;
454 struct df_link *defs;
455 rtx set;
457 FOR_EACH_INSN_USE (use, insn)
458 if (rtx_equal_p (addr, DF_REF_REG (use)))
459 break;
461 if (use == NULL)
462 break;
464 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
465 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
466 break;
468 if (defs == NULL)
469 break;
471 set = single_set (DF_REF_INSN (defs->ref));
472 if (!set)
473 break;
475 if (GET_CODE (SET_SRC (set)) != PLUS
476 || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
477 || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
478 break;
480 off += INTVAL (XEXP (SET_SRC (set), 1));
482 else
483 break;
486 HOST_WIDE_INT size;
487 if (!MEM_SIZE_KNOWN_P (mem)
488 || !MEM_SIZE (mem).is_constant (&size)
489 || !check_argument_store (size, off, min_sp_off,
490 max_sp_off, sp_bytes))
491 break;
493 if (!deletable_insn_p (insn, fast, NULL))
494 break;
496 if (do_mark)
497 mark_insn (insn, fast);
498 else
499 bitmap_set_bit (arg_stores, INSN_UID (insn));
501 if (bitmap_empty_p (sp_bytes))
503 ret = true;
504 break;
508 BITMAP_FREE (sp_bytes);
509 if (!ret && arg_stores)
510 bitmap_clear (arg_stores);
512 return ret;
516 /* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN
517 writes to. */
519 static void
520 remove_reg_equal_equiv_notes_for_defs (rtx_insn *insn)
522 df_ref def;
524 FOR_EACH_INSN_DEF (def, insn)
525 remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (def));
528 /* Scan all BBs for debug insns and reset those that reference values
529 defined in unmarked insns. */
531 static void
532 reset_unmarked_insns_debug_uses (void)
534 basic_block bb;
535 rtx_insn *insn, *next;
537 FOR_EACH_BB_REVERSE_FN (bb, cfun)
538 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
539 if (DEBUG_INSN_P (insn))
541 df_ref use;
543 FOR_EACH_INSN_USE (use, insn)
545 struct df_link *defs;
546 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
548 rtx_insn *ref_insn;
549 if (DF_REF_IS_ARTIFICIAL (defs->ref))
550 continue;
551 ref_insn = DF_REF_INSN (defs->ref);
552 if (!marked_insn_p (ref_insn))
553 break;
555 if (!defs)
556 continue;
557 /* ??? FIXME could we propagate the values assigned to
558 each of the DEFs? */
559 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
560 df_insn_rescan_debug_internal (insn);
561 break;
566 /* Delete every instruction that hasn't been marked. */
568 static void
569 delete_unmarked_insns (void)
571 basic_block bb;
572 rtx_insn *insn, *next;
573 bool must_clean = false;
575 FOR_EACH_BB_REVERSE_FN (bb, cfun)
576 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
577 if (NONDEBUG_INSN_P (insn))
579 rtx turn_into_use = NULL_RTX;
581 /* Always delete no-op moves. */
582 if (noop_move_p (insn))
584 if (RTX_FRAME_RELATED_P (insn))
585 turn_into_use
586 = find_reg_note (insn, REG_CFA_RESTORE, NULL);
587 if (turn_into_use && REG_P (XEXP (turn_into_use, 0)))
588 turn_into_use = XEXP (turn_into_use, 0);
589 else
590 turn_into_use = NULL_RTX;
593 /* Otherwise rely only on the DCE algorithm. */
594 else if (marked_insn_p (insn))
595 continue;
597 /* Beware that reaching a dbg counter limit here can result
598 in miscompiled file. This occurs when a group of insns
599 must be deleted together, typically because the kept insn
600 depends on the output from the deleted insn. Deleting
601 this insns in reverse order (both at the bb level and
602 when looking at the blocks) minimizes this, but does not
603 eliminate it, since it is possible for the using insn to
604 be top of a block and the producer to be at the bottom of
605 the block. However, in most cases this will only result
606 in an uninitialized use of an insn that is dead anyway.
608 However, there is one rare case that will cause a
609 miscompile: deletion of non-looping pure and constant
610 calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
611 In this case it is possible to remove the call, but leave
612 the argument pushes to the stack. Because of the changes
613 to the stack pointer, this will almost always lead to a
614 miscompile. */
615 if (!dbg_cnt (dce))
616 continue;
618 if (dump_file)
619 fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
621 /* Before we delete the insn we have to remove the REG_EQUAL notes
622 for the destination regs in order to avoid dangling notes. */
623 remove_reg_equal_equiv_notes_for_defs (insn);
625 /* If a pure or const call is deleted, this may make the cfg
626 have unreachable blocks. We rememeber this and call
627 delete_unreachable_blocks at the end. */
628 if (CALL_P (insn))
629 must_clean = true;
631 if (turn_into_use)
633 /* Don't remove frame related noop moves if they cary
634 REG_CFA_RESTORE note, while we don't need to emit any code,
635 we need it to emit the CFI restore note. */
636 PATTERN (insn)
637 = gen_rtx_USE (GET_MODE (turn_into_use), turn_into_use);
638 INSN_CODE (insn) = -1;
639 df_insn_rescan (insn);
641 else
642 /* Now delete the insn. */
643 delete_insn_and_edges (insn);
646 /* Deleted a pure or const call. */
647 if (must_clean)
648 delete_unreachable_blocks ();
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. */
656 static void
657 prescan_insns_for_dce (bool fast)
659 basic_block bb;
660 rtx_insn *insn, *prev;
661 bitmap arg_stores = NULL;
663 if (dump_file)
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)))
677 continue;
678 if (deletable_insn_p (insn, fast, arg_stores))
679 mark_nonreg_stores (PATTERN (insn), insn, fast);
680 else
681 mark_insn (insn, fast);
683 /* find_call_stack_args only looks at argument stores in the
684 same bb. */
685 if (arg_stores)
686 bitmap_clear (arg_stores);
689 if (arg_stores)
690 BITMAP_FREE (arg_stores);
692 if (dump_file)
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. */
702 static void
703 mark_artificial_uses (void)
705 basic_block bb;
706 struct df_link *defs;
707 df_ref use;
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. */
719 static void
720 mark_reg_dependencies (rtx_insn *insn)
722 struct df_link *defs;
723 df_ref use;
725 if (DEBUG_INSN_P (insn))
726 return;
728 FOR_EACH_INSN_USE (use, insn)
730 if (dump_file)
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. */
745 static void
746 init_dce (bool fast)
748 if (!df_in_progress)
750 if (!fast)
752 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
753 df_chain_add_problem (DF_UD_CHAIN);
755 df_analyze ();
758 if (dump_file)
759 df_dump (dump_file);
761 if (fast)
763 bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
764 bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
765 can_alter_cfg = false;
767 else
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. */
777 static void
778 fini_dce (bool fast)
780 sbitmap_free (marked);
782 if (fast)
784 bitmap_obstack_release (&dce_blocks_bitmap_obstack);
785 bitmap_obstack_release (&dce_tmp_bitmap_obstack);
790 /* UD-chain based DCE. */
792 static unsigned int
793 rest_of_handle_ud_dce (void)
795 rtx_insn *insn;
797 init_dce (false);
799 prescan_insns_for_dce (false);
800 mark_artificial_uses ();
801 while (worklist.length () > 0)
803 insn = worklist.pop ();
804 mark_reg_dependencies (insn);
806 worklist.release ();
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 ();
816 fini_dce (false);
817 return 0;
821 namespace {
823 const pass_data pass_data_ud_rtl_dce =
825 RTL_PASS, /* type */
826 "ud_dce", /* name */
827 OPTGROUP_NONE, /* optinfo_flags */
828 TV_DCE, /* tv_id */
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
838 public:
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
856 } // anon namespace
858 rtl_opt_pass *
859 make_pass_ud_rtl_dce (gcc::context *ctxt)
861 return new pass_ud_rtl_dce (ctxt);
865 /* -------------------------------------------------------------------------
866 Fast DCE functions
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. */
875 static bool
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);
880 rtx_insn *insn;
881 bool block_changed;
882 struct dead_debug_local debug;
884 if (redo_out)
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
888 set. */
889 edge e;
890 edge_iterator ei;
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)
894 (*con_fun_n) (e);
897 if (dump_file)
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))
909 df_ref use;
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))),
913 2 * UNITS_PER_WORD)
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))
920 bool any_changed;
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);
925 if (any_changed)
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
936 death. */
937 if (debug.used && !bitmap_empty_p (debug.used))
939 df_ref def;
941 FOR_EACH_INSN_DEF (def, insn)
942 dead_debug_insert_temp (&debug, DF_REF_REGNO (def), insn,
943 marked_insn_p (insn)
944 && !control_flow_insn_p (insn)
945 ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
946 : DEBUG_TEMP_BEFORE_WITH_VALUE);
949 if (dump_file)
951 fprintf (dump_file, "finished processing insn %d live out = ",
952 INSN_UID (insn));
953 df_print_word_regset (dump_file, local_live);
957 block_changed = !bitmap_equal_p (local_live, DF_WORD_LR_IN (bb));
958 if (block_changed)
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. */
973 static bool
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);
978 rtx_insn *insn;
979 bool block_changed;
980 df_ref def;
981 struct dead_debug_local debug;
983 if (redo_out)
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
987 set. */
988 edge e;
989 edge_iterator ei;
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)
993 (*con_fun_n) (e);
996 if (dump_file)
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))
1010 df_ref use;
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. */
1021 if (!needed)
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)))
1026 needed = true;
1027 mark_insn (insn, true);
1028 break;
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. */
1037 if (needed)
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
1043 death. */
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));
1056 if (block_changed)
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
1066 level. */
1068 static void
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
1085 here. */
1086 bitmap au = &df->regular_block_artificial_uses;
1087 bitmap au_eh = &df->eh_block_artificial_uses;
1088 int i;
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);
1106 bool local_changed;
1108 if (index < NUM_FIXED_BLOCKS)
1110 bitmap_set_bit (processed, index);
1111 continue;
1114 if (word_level)
1115 local_changed
1116 = word_dce_process_block (bb, bitmap_bit_p (redo_out, index),
1117 &global_debug);
1118 else
1119 local_changed
1120 = dce_process_block (bb, bitmap_bit_p (redo_out, index),
1121 bb_has_eh_pred (bb) ? au_eh : au,
1122 &global_debug);
1123 bitmap_set_bit (processed, index);
1125 if (local_changed)
1127 edge e;
1128 edge_iterator ei;
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
1134 entry to a loop. */
1135 global_changed = true;
1136 else
1137 bitmap_set_bit (redo_out, e->src->index);
1141 if (global_changed)
1143 /* Turn off the RUN_DCE flag to prevent recursive calls to
1144 dce. */
1145 int old_flag = df_clear_flags (DF_LR_RUN_DCE);
1147 /* So something was deleted that requires a redo. Do it on
1148 the cheap. */
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
1157 iteration. */
1158 if (word_level)
1159 df_analyze_problem (df_word_lr, all_blocks, postorder, n_blocks);
1160 else
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. */
1182 static unsigned int
1183 rest_of_handle_fast_dce (void)
1185 init_dce (true);
1186 fast_dce (false);
1187 fini_dce (true);
1188 return 0;
1192 /* Fast byte level DCE. */
1194 void
1195 run_word_dce (void)
1197 int old_flags;
1199 if (!flag_dce)
1200 return;
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 ();
1205 init_dce (true);
1206 fast_dce (true);
1207 fini_dce (true);
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. */
1222 void
1223 run_fast_df_dce (void)
1225 if (flag_dce)
1227 /* If dce is able to delete something, it has to happen
1228 immediately. Otherwise there will be problems handling the
1229 eq_notes. */
1230 int old_flags =
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. */
1244 void
1245 run_fast_dce (void)
1247 if (flag_dce)
1248 rest_of_handle_fast_dce ();
1252 namespace {
1254 const pass_data pass_data_fast_rtl_dce =
1256 RTL_PASS, /* type */
1257 "rtl_dce", /* name */
1258 OPTGROUP_NONE, /* optinfo_flags */
1259 TV_DCE, /* tv_id */
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
1269 public:
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
1287 } // anon namespace
1289 rtl_opt_pass *
1290 make_pass_fast_rtl_dce (gcc::context *ctxt)
1292 return new pass_fast_rtl_dce (ctxt);