re PR tree-optimization/47053 (ICE: verify_flow_info failed: BB 2 can not throw but...
[gcc.git] / gcc / dce.c
1 /* RTL dead code elimination.
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
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
10 version.
11
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
15 for more details.
16
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/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "hashtab.h"
25 #include "tm.h"
26 #include "rtl.h"
27 #include "tree.h"
28 #include "regs.h"
29 #include "hard-reg-set.h"
30 #include "flags.h"
31 #include "except.h"
32 #include "df.h"
33 #include "cselib.h"
34 #include "dce.h"
35 #include "timevar.h"
36 #include "tree-pass.h"
37 #include "dbgcnt.h"
38 #include "tm_p.h"
39 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
40
41
42 /* -------------------------------------------------------------------------
43 Core mark/delete routines
44 ------------------------------------------------------------------------- */
45
46 /* True if we are invoked while the df engine is running; in this case,
47 we don't want to reenter it. */
48 static bool df_in_progress = false;
49
50 /* Instructions that have been marked but whose dependencies have not
51 yet been processed. */
52 static VEC(rtx,heap) *worklist;
53
54 /* Bitmap of instructions marked as needed indexed by INSN_UID. */
55 static sbitmap marked;
56
57 /* Bitmap obstacks used for block processing by the fast algorithm. */
58 static bitmap_obstack dce_blocks_bitmap_obstack;
59 static bitmap_obstack dce_tmp_bitmap_obstack;
60
61 static bool find_call_stack_args (rtx, bool, bool, bitmap);
62
63 /* A subroutine for which BODY is part of the instruction being tested;
64 either the top-level pattern, or an element of a PARALLEL. The
65 instruction is known not to be a bare USE or CLOBBER. */
66
67 static bool
68 deletable_insn_p_1 (rtx body)
69 {
70 switch (GET_CODE (body))
71 {
72 case PREFETCH:
73 case TRAP_IF:
74 /* The UNSPEC case was added here because the ia-64 claims that
75 USEs do not work after reload and generates UNSPECS rather
76 than USEs. Since dce is run after reload we need to avoid
77 deleting these even if they are dead. If it turns out that
78 USEs really do work after reload, the ia-64 should be
79 changed, and the UNSPEC case can be removed. */
80 case UNSPEC:
81 return false;
82
83 default:
84 return !volatile_refs_p (body);
85 }
86 }
87
88
89 /* Return true if INSN is a normal instruction that can be deleted by
90 the DCE pass. */
91
92 static bool
93 deletable_insn_p (rtx insn, bool fast, bitmap arg_stores)
94 {
95 rtx body, x;
96 int i;
97
98 if (CALL_P (insn)
99 /* We cannot delete calls inside of the recursive dce because
100 this may cause basic blocks to be deleted and this messes up
101 the rest of the stack of optimization passes. */
102 && (!df_in_progress)
103 /* We cannot delete pure or const sibling calls because it is
104 hard to see the result. */
105 && (!SIBLING_CALL_P (insn))
106 /* We can delete dead const or pure calls as long as they do not
107 infinite loop. */
108 && (RTL_CONST_OR_PURE_CALL_P (insn)
109 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))
110 return find_call_stack_args (insn, false, fast, arg_stores);
111
112 /* Don't delete jumps, notes and the like. */
113 if (!NONJUMP_INSN_P (insn))
114 return false;
115
116 /* Don't delete insns that can throw. */
117 if (!insn_nothrow_p (insn))
118 return false;
119
120 body = PATTERN (insn);
121 switch (GET_CODE (body))
122 {
123 case USE:
124 case VAR_LOCATION:
125 return false;
126
127 case CLOBBER:
128 if (fast)
129 {
130 /* A CLOBBER of a dead pseudo register serves no purpose.
131 That is not necessarily true for hard registers until
132 after reload. */
133 x = XEXP (body, 0);
134 return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);
135 }
136 else
137 /* Because of the way that use-def chains are built, it is not
138 possible to tell if the clobber is dead because it can
139 never be the target of a use-def chain. */
140 return false;
141
142 case PARALLEL:
143 for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
144 if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))
145 return false;
146 return true;
147
148 default:
149 return deletable_insn_p_1 (body);
150 }
151 }
152
153
154 /* Return true if INSN has been marked as needed. */
155
156 static inline int
157 marked_insn_p (rtx insn)
158 {
159 /* Artificial defs are always needed and they do not have an insn.
160 We should never see them here. */
161 gcc_assert (insn);
162 return TEST_BIT (marked, INSN_UID (insn));
163 }
164
165
166 /* If INSN has not yet been marked as needed, mark it now, and add it to
167 the worklist. */
168
169 static void
170 mark_insn (rtx insn, bool fast)
171 {
172 if (!marked_insn_p (insn))
173 {
174 if (!fast)
175 VEC_safe_push (rtx, heap, worklist, insn);
176 SET_BIT (marked, INSN_UID (insn));
177 if (dump_file)
178 fprintf (dump_file, " Adding insn %d to worklist\n", INSN_UID (insn));
179 if (CALL_P (insn)
180 && !df_in_progress
181 && !SIBLING_CALL_P (insn)
182 && (RTL_CONST_OR_PURE_CALL_P (insn)
183 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))
184 find_call_stack_args (insn, true, fast, NULL);
185 }
186 }
187
188
189 /* A note_stores callback used by mark_nonreg_stores. DATA is the
190 instruction containing DEST. */
191
192 static void
193 mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data)
194 {
195 if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
196 mark_insn ((rtx) data, true);
197 }
198
199
200 /* A note_stores callback used by mark_nonreg_stores. DATA is the
201 instruction containing DEST. */
202
203 static void
204 mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)
205 {
206 if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
207 mark_insn ((rtx) data, false);
208 }
209
210
211 /* Mark INSN if BODY stores to a non-register destination. */
212
213 static void
214 mark_nonreg_stores (rtx body, rtx insn, bool fast)
215 {
216 if (fast)
217 note_stores (body, mark_nonreg_stores_1, insn);
218 else
219 note_stores (body, mark_nonreg_stores_2, insn);
220 }
221
222
223 /* Return true if store to MEM, starting OFF bytes from stack pointer,
224 is a call argument store, and clear corresponding bits from SP_BYTES
225 bitmap if it is. */
226
227 static bool
228 check_argument_store (rtx mem, HOST_WIDE_INT off, HOST_WIDE_INT min_sp_off,
229 HOST_WIDE_INT max_sp_off, bitmap sp_bytes)
230 {
231 HOST_WIDE_INT byte;
232 for (byte = off; byte < off + GET_MODE_SIZE (GET_MODE (mem)); byte++)
233 {
234 if (byte < min_sp_off
235 || byte >= max_sp_off
236 || !bitmap_clear_bit (sp_bytes, byte - min_sp_off))
237 return false;
238 }
239 return true;
240 }
241
242
243 /* Try to find all stack stores of CALL_INSN arguments if
244 ACCUMULATE_OUTGOING_ARGS. If all stack stores have been found
245 and it is therefore safe to eliminate the call, return true,
246 otherwise return false. This function should be first called
247 with DO_MARK false, and only when the CALL_INSN is actually
248 going to be marked called again with DO_MARK true. */
249
250 static bool
251 find_call_stack_args (rtx call_insn, bool do_mark, bool fast,
252 bitmap arg_stores)
253 {
254 rtx p, insn, prev_insn;
255 bool ret;
256 HOST_WIDE_INT min_sp_off, max_sp_off;
257 bitmap sp_bytes;
258
259 gcc_assert (CALL_P (call_insn));
260 if (!ACCUMULATE_OUTGOING_ARGS)
261 return true;
262
263 if (!do_mark)
264 {
265 gcc_assert (arg_stores);
266 bitmap_clear (arg_stores);
267 }
268
269 min_sp_off = INTTYPE_MAXIMUM (HOST_WIDE_INT);
270 max_sp_off = 0;
271
272 /* First determine the minimum and maximum offset from sp for
273 stored arguments. */
274 for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
275 if (GET_CODE (XEXP (p, 0)) == USE
276 && MEM_P (XEXP (XEXP (p, 0), 0)))
277 {
278 rtx mem = XEXP (XEXP (p, 0), 0), addr, size;
279 HOST_WIDE_INT off = 0;
280 size = MEM_SIZE (mem);
281 if (size == NULL_RTX)
282 return false;
283 addr = XEXP (mem, 0);
284 if (GET_CODE (addr) == PLUS
285 && REG_P (XEXP (addr, 0))
286 && CONST_INT_P (XEXP (addr, 1)))
287 {
288 off = INTVAL (XEXP (addr, 1));
289 addr = XEXP (addr, 0);
290 }
291 if (addr != stack_pointer_rtx)
292 {
293 if (!REG_P (addr))
294 return false;
295 /* If not fast, use chains to see if addr wasn't set to
296 sp + offset. */
297 if (!fast)
298 {
299 df_ref *use_rec;
300 struct df_link *defs;
301 rtx set;
302
303 for (use_rec = DF_INSN_USES (call_insn); *use_rec; use_rec++)
304 if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))
305 break;
306
307 if (*use_rec == NULL)
308 return false;
309
310 for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
311 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
312 break;
313
314 if (defs == NULL)
315 return false;
316
317 set = single_set (DF_REF_INSN (defs->ref));
318 if (!set)
319 return false;
320
321 if (GET_CODE (SET_SRC (set)) != PLUS
322 || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
323 || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
324 return false;
325
326 off += INTVAL (XEXP (SET_SRC (set), 1));
327 }
328 else
329 return false;
330 }
331 min_sp_off = MIN (min_sp_off, off);
332 max_sp_off = MAX (max_sp_off, off + INTVAL (size));
333 }
334
335 if (min_sp_off >= max_sp_off)
336 return true;
337 sp_bytes = BITMAP_ALLOC (NULL);
338
339 /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
340 which contain arguments. Checking has been done in the previous
341 loop. */
342 for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
343 if (GET_CODE (XEXP (p, 0)) == USE
344 && MEM_P (XEXP (XEXP (p, 0), 0)))
345 {
346 rtx mem = XEXP (XEXP (p, 0), 0), addr;
347 HOST_WIDE_INT off = 0, byte;
348 addr = XEXP (mem, 0);
349 if (GET_CODE (addr) == PLUS
350 && REG_P (XEXP (addr, 0))
351 && CONST_INT_P (XEXP (addr, 1)))
352 {
353 off = INTVAL (XEXP (addr, 1));
354 addr = XEXP (addr, 0);
355 }
356 if (addr != stack_pointer_rtx)
357 {
358 df_ref *use_rec;
359 struct df_link *defs;
360 rtx set;
361
362 for (use_rec = DF_INSN_USES (call_insn); *use_rec; use_rec++)
363 if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))
364 break;
365
366 for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
367 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
368 break;
369
370 set = single_set (DF_REF_INSN (defs->ref));
371 off += INTVAL (XEXP (SET_SRC (set), 1));
372 }
373 for (byte = off; byte < off + INTVAL (MEM_SIZE (mem)); byte++)
374 {
375 if (!bitmap_set_bit (sp_bytes, byte - min_sp_off))
376 gcc_unreachable ();
377 }
378 }
379
380 /* Walk backwards, looking for argument stores. The search stops
381 when seeing another call, sp adjustment or memory store other than
382 argument store. */
383 ret = false;
384 for (insn = PREV_INSN (call_insn); insn; insn = prev_insn)
385 {
386 rtx set, mem, addr;
387 HOST_WIDE_INT off;
388
389 if (insn == BB_HEAD (BLOCK_FOR_INSN (call_insn)))
390 prev_insn = NULL_RTX;
391 else
392 prev_insn = PREV_INSN (insn);
393
394 if (CALL_P (insn))
395 break;
396
397 if (!NONDEBUG_INSN_P (insn))
398 continue;
399
400 set = single_set (insn);
401 if (!set || SET_DEST (set) == stack_pointer_rtx)
402 break;
403
404 if (!MEM_P (SET_DEST (set)))
405 continue;
406
407 mem = SET_DEST (set);
408 addr = XEXP (mem, 0);
409 off = 0;
410 if (GET_CODE (addr) == PLUS
411 && REG_P (XEXP (addr, 0))
412 && CONST_INT_P (XEXP (addr, 1)))
413 {
414 off = INTVAL (XEXP (addr, 1));
415 addr = XEXP (addr, 0);
416 }
417 if (addr != stack_pointer_rtx)
418 {
419 if (!REG_P (addr))
420 break;
421 if (!fast)
422 {
423 df_ref *use_rec;
424 struct df_link *defs;
425 rtx set;
426
427 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
428 if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))
429 break;
430
431 if (*use_rec == NULL)
432 break;
433
434 for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
435 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
436 break;
437
438 if (defs == NULL)
439 break;
440
441 set = single_set (DF_REF_INSN (defs->ref));
442 if (!set)
443 break;
444
445 if (GET_CODE (SET_SRC (set)) != PLUS
446 || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
447 || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
448 break;
449
450 off += INTVAL (XEXP (SET_SRC (set), 1));
451 }
452 else
453 break;
454 }
455
456 if (GET_MODE_SIZE (GET_MODE (mem)) == 0
457 || !check_argument_store (mem, off, min_sp_off,
458 max_sp_off, sp_bytes))
459 break;
460
461 if (!deletable_insn_p (insn, fast, NULL))
462 break;
463
464 if (do_mark)
465 mark_insn (insn, fast);
466 else
467 bitmap_set_bit (arg_stores, INSN_UID (insn));
468
469 if (bitmap_empty_p (sp_bytes))
470 {
471 ret = true;
472 break;
473 }
474 }
475
476 BITMAP_FREE (sp_bytes);
477 if (!ret && arg_stores)
478 bitmap_clear (arg_stores);
479
480 return ret;
481 }
482
483
484 /* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN
485 writes to. */
486
487 static void
488 remove_reg_equal_equiv_notes_for_defs (rtx insn)
489 {
490 df_ref *def_rec;
491
492 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
493 remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (*def_rec));
494 }
495
496
497 /* Delete every instruction that hasn't been marked. */
498
499 static void
500 delete_unmarked_insns (void)
501 {
502 basic_block bb;
503 rtx insn, next;
504 bool must_clean = false;
505
506 FOR_EACH_BB_REVERSE (bb)
507 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
508 if (INSN_P (insn))
509 {
510 /* Always delete no-op moves. */
511 if (noop_move_p (insn))
512 ;
513
514 /* Otherwise rely only on the DCE algorithm. */
515 else if (marked_insn_p (insn))
516 continue;
517
518 /* Beware that reaching a dbg counter limit here can result
519 in miscompiled file. This occurs when a group of insns
520 must be deleted together, typically because the kept insn
521 depends on the output from the deleted insn. Deleting
522 this insns in reverse order (both at the bb level and
523 when looking at the blocks) minimizes this, but does not
524 eliminate it, since it is possible for the using insn to
525 be top of a block and the producer to be at the bottom of
526 the block. However, in most cases this will only result
527 in an uninitialized use of an insn that is dead anyway.
528
529 However, there is one rare case that will cause a
530 miscompile: deletion of non-looping pure and constant
531 calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
532 In this case it is possible to remove the call, but leave
533 the argument pushes to the stack. Because of the changes
534 to the stack pointer, this will almost always lead to a
535 miscompile. */
536 if (!dbg_cnt (dce))
537 continue;
538
539 if (dump_file)
540 fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
541
542 /* Before we delete the insn we have to remove the REG_EQUAL notes
543 for the destination regs in order to avoid dangling notes. */
544 remove_reg_equal_equiv_notes_for_defs (insn);
545
546 /* If a pure or const call is deleted, this may make the cfg
547 have unreachable blocks. We rememeber this and call
548 delete_unreachable_blocks at the end. */
549 if (CALL_P (insn))
550 must_clean = true;
551
552 /* Now delete the insn. */
553 delete_insn_and_edges (insn);
554 }
555
556 /* Deleted a pure or const call. */
557 if (must_clean)
558 delete_unreachable_blocks ();
559 }
560
561
562 /* Go through the instructions and mark those whose necessity is not
563 dependent on inter-instruction information. Make sure all other
564 instructions are not marked. */
565
566 static void
567 prescan_insns_for_dce (bool fast)
568 {
569 basic_block bb;
570 rtx insn, prev;
571 bitmap arg_stores = NULL;
572
573 if (dump_file)
574 fprintf (dump_file, "Finding needed instructions:\n");
575
576 if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS)
577 arg_stores = BITMAP_ALLOC (NULL);
578
579 FOR_EACH_BB (bb)
580 {
581 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)
582 if (INSN_P (insn))
583 {
584 /* Don't mark argument stores now. They will be marked
585 if needed when the associated CALL is marked. */
586 if (arg_stores && bitmap_bit_p (arg_stores, INSN_UID (insn)))
587 continue;
588 if (deletable_insn_p (insn, fast, arg_stores))
589 mark_nonreg_stores (PATTERN (insn), insn, fast);
590 else
591 mark_insn (insn, fast);
592 }
593 /* find_call_stack_args only looks at argument stores in the
594 same bb. */
595 if (arg_stores)
596 bitmap_clear (arg_stores);
597 }
598
599 if (arg_stores)
600 BITMAP_FREE (arg_stores);
601
602 if (dump_file)
603 fprintf (dump_file, "Finished finding needed instructions:\n");
604 }
605
606
607 /* UD-based DSE routines. */
608
609 /* Mark instructions that define artificially-used registers, such as
610 the frame pointer and the stack pointer. */
611
612 static void
613 mark_artificial_uses (void)
614 {
615 basic_block bb;
616 struct df_link *defs;
617 df_ref *use_rec;
618
619 FOR_ALL_BB (bb)
620 {
621 for (use_rec = df_get_artificial_uses (bb->index);
622 *use_rec; use_rec++)
623 for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
624 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
625 mark_insn (DF_REF_INSN (defs->ref), false);
626 }
627 }
628
629
630 /* Mark every instruction that defines a register value that INSN uses. */
631
632 static void
633 mark_reg_dependencies (rtx insn)
634 {
635 struct df_link *defs;
636 df_ref *use_rec;
637
638 if (DEBUG_INSN_P (insn))
639 return;
640
641 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
642 {
643 df_ref use = *use_rec;
644 if (dump_file)
645 {
646 fprintf (dump_file, "Processing use of ");
647 print_simple_rtl (dump_file, DF_REF_REG (use));
648 fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
649 }
650 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
651 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
652 mark_insn (DF_REF_INSN (defs->ref), false);
653 }
654 }
655
656
657 /* Initialize global variables for a new DCE pass. */
658
659 static void
660 init_dce (bool fast)
661 {
662 if (!df_in_progress)
663 {
664 if (!fast)
665 df_chain_add_problem (DF_UD_CHAIN);
666 df_analyze ();
667 }
668
669 if (dump_file)
670 df_dump (dump_file);
671
672 if (fast)
673 {
674 bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
675 bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
676 }
677
678 marked = sbitmap_alloc (get_max_uid () + 1);
679 sbitmap_zero (marked);
680 }
681
682
683 /* Free the data allocated by init_dce. */
684
685 static void
686 fini_dce (bool fast)
687 {
688 sbitmap_free (marked);
689
690 if (fast)
691 {
692 bitmap_obstack_release (&dce_blocks_bitmap_obstack);
693 bitmap_obstack_release (&dce_tmp_bitmap_obstack);
694 }
695 }
696
697
698 /* UD-chain based DCE. */
699
700 static unsigned int
701 rest_of_handle_ud_dce (void)
702 {
703 rtx insn;
704
705 init_dce (false);
706
707 prescan_insns_for_dce (false);
708 mark_artificial_uses ();
709 while (VEC_length (rtx, worklist) > 0)
710 {
711 insn = VEC_pop (rtx, worklist);
712 mark_reg_dependencies (insn);
713 }
714 VEC_free (rtx, heap, worklist);
715
716 /* Before any insns are deleted, we must remove the chains since
717 they are not bidirectional. */
718 df_remove_problem (df_chain);
719 delete_unmarked_insns ();
720
721 fini_dce (false);
722 return 0;
723 }
724
725
726 static bool
727 gate_ud_dce (void)
728 {
729 return optimize > 1 && flag_dce
730 && dbg_cnt (dce_ud);
731 }
732
733 struct rtl_opt_pass pass_ud_rtl_dce =
734 {
735 {
736 RTL_PASS,
737 "ud dce", /* name */
738 gate_ud_dce, /* gate */
739 rest_of_handle_ud_dce, /* execute */
740 NULL, /* sub */
741 NULL, /* next */
742 0, /* static_pass_number */
743 TV_DCE, /* tv_id */
744 0, /* properties_required */
745 0, /* properties_provided */
746 0, /* properties_destroyed */
747 0, /* todo_flags_start */
748 TODO_dump_func |
749 TODO_df_finish | TODO_verify_rtl_sharing |
750 TODO_ggc_collect /* todo_flags_finish */
751 }
752 };
753
754
755 /* -------------------------------------------------------------------------
756 Fast DCE functions
757 ------------------------------------------------------------------------- */
758
759 /* Process basic block BB. Return true if the live_in set has
760 changed. REDO_OUT is true if the info at the bottom of the block
761 needs to be recalculated before starting. AU is the proper set of
762 artificial uses. */
763
764 static bool
765 word_dce_process_block (basic_block bb, bool redo_out)
766 {
767 bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
768 rtx insn;
769 bool block_changed;
770
771 if (redo_out)
772 {
773 /* Need to redo the live_out set of this block if when one of
774 the succs of this block has had a change in it live in
775 set. */
776 edge e;
777 edge_iterator ei;
778 df_confluence_function_n con_fun_n = df_word_lr->problem->con_fun_n;
779 bitmap_clear (DF_WORD_LR_OUT (bb));
780 FOR_EACH_EDGE (e, ei, bb->succs)
781 (*con_fun_n) (e);
782 }
783
784 if (dump_file)
785 {
786 fprintf (dump_file, "processing block %d live out = ", bb->index);
787 df_print_word_regset (dump_file, DF_WORD_LR_OUT (bb));
788 }
789
790 bitmap_copy (local_live, DF_WORD_LR_OUT (bb));
791
792 FOR_BB_INSNS_REVERSE (bb, insn)
793 if (NONDEBUG_INSN_P (insn))
794 {
795 bool any_changed;
796 /* No matter if the instruction is needed or not, we remove
797 any regno in the defs from the live set. */
798 any_changed = df_word_lr_simulate_defs (insn, local_live);
799 if (any_changed)
800 mark_insn (insn, true);
801
802 /* On the other hand, we do not allow the dead uses to set
803 anything in local_live. */
804 if (marked_insn_p (insn))
805 df_word_lr_simulate_uses (insn, local_live);
806
807 if (dump_file)
808 {
809 fprintf (dump_file, "finished processing insn %d live out = ",
810 INSN_UID (insn));
811 df_print_word_regset (dump_file, local_live);
812 }
813 }
814
815 block_changed = !bitmap_equal_p (local_live, DF_WORD_LR_IN (bb));
816 if (block_changed)
817 bitmap_copy (DF_WORD_LR_IN (bb), local_live);
818
819 BITMAP_FREE (local_live);
820 return block_changed;
821 }
822
823
824 /* Process basic block BB. Return true if the live_in set has
825 changed. REDO_OUT is true if the info at the bottom of the block
826 needs to be recalculated before starting. AU is the proper set of
827 artificial uses. */
828
829 static bool
830 dce_process_block (basic_block bb, bool redo_out, bitmap au)
831 {
832 bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
833 rtx insn;
834 bool block_changed;
835 df_ref *def_rec;
836
837 if (redo_out)
838 {
839 /* Need to redo the live_out set of this block if when one of
840 the succs of this block has had a change in it live in
841 set. */
842 edge e;
843 edge_iterator ei;
844 df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
845 bitmap_clear (DF_LR_OUT (bb));
846 FOR_EACH_EDGE (e, ei, bb->succs)
847 (*con_fun_n) (e);
848 }
849
850 if (dump_file)
851 {
852 fprintf (dump_file, "processing block %d lr out = ", bb->index);
853 df_print_regset (dump_file, DF_LR_OUT (bb));
854 }
855
856 bitmap_copy (local_live, DF_LR_OUT (bb));
857
858 df_simulate_initialize_backwards (bb, local_live);
859
860 FOR_BB_INSNS_REVERSE (bb, insn)
861 if (INSN_P (insn))
862 {
863 bool needed = marked_insn_p (insn);
864
865 /* The insn is needed if there is someone who uses the output. */
866 if (!needed)
867 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
868 if (bitmap_bit_p (local_live, DF_REF_REGNO (*def_rec))
869 || bitmap_bit_p (au, DF_REF_REGNO (*def_rec)))
870 {
871 needed = true;
872 mark_insn (insn, true);
873 break;
874 }
875
876 /* No matter if the instruction is needed or not, we remove
877 any regno in the defs from the live set. */
878 df_simulate_defs (insn, local_live);
879
880 /* On the other hand, we do not allow the dead uses to set
881 anything in local_live. */
882 if (needed)
883 df_simulate_uses (insn, local_live);
884 }
885
886 df_simulate_finalize_backwards (bb, local_live);
887
888 block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
889 if (block_changed)
890 bitmap_copy (DF_LR_IN (bb), local_live);
891
892 BITMAP_FREE (local_live);
893 return block_changed;
894 }
895
896
897 /* Perform fast DCE once initialization is done. If WORD_LEVEL is
898 true, use the word level dce, otherwise do it at the pseudo
899 level. */
900
901 static void
902 fast_dce (bool word_level)
903 {
904 int *postorder = df_get_postorder (DF_BACKWARD);
905 int n_blocks = df_get_n_blocks (DF_BACKWARD);
906 /* The set of blocks that have been seen on this iteration. */
907 bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
908 /* The set of blocks that need to have the out vectors reset because
909 the in of one of their successors has changed. */
910 bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
911 bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
912 bool global_changed = true;
913
914 /* These regs are considered always live so if they end up dying
915 because of some def, we need to bring the back again. Calling
916 df_simulate_fixup_sets has the disadvantage of calling
917 bb_has_eh_pred once per insn, so we cache the information
918 here. */
919 bitmap au = &df->regular_block_artificial_uses;
920 bitmap au_eh = &df->eh_block_artificial_uses;
921 int i;
922
923 prescan_insns_for_dce (true);
924
925 for (i = 0; i < n_blocks; i++)
926 bitmap_set_bit (all_blocks, postorder[i]);
927
928 while (global_changed)
929 {
930 global_changed = false;
931
932 for (i = 0; i < n_blocks; i++)
933 {
934 int index = postorder[i];
935 basic_block bb = BASIC_BLOCK (index);
936 bool local_changed;
937
938 if (index < NUM_FIXED_BLOCKS)
939 {
940 bitmap_set_bit (processed, index);
941 continue;
942 }
943
944 if (word_level)
945 local_changed
946 = word_dce_process_block (bb, bitmap_bit_p (redo_out, index));
947 else
948 local_changed
949 = dce_process_block (bb, bitmap_bit_p (redo_out, index),
950 bb_has_eh_pred (bb) ? au_eh : au);
951 bitmap_set_bit (processed, index);
952
953 if (local_changed)
954 {
955 edge e;
956 edge_iterator ei;
957 FOR_EACH_EDGE (e, ei, bb->preds)
958 if (bitmap_bit_p (processed, e->src->index))
959 /* Be tricky about when we need to iterate the
960 analysis. We only have redo the analysis if the
961 bitmaps change at the top of a block that is the
962 entry to a loop. */
963 global_changed = true;
964 else
965 bitmap_set_bit (redo_out, e->src->index);
966 }
967 }
968
969 if (global_changed)
970 {
971 /* Turn off the RUN_DCE flag to prevent recursive calls to
972 dce. */
973 int old_flag = df_clear_flags (DF_LR_RUN_DCE);
974
975 /* So something was deleted that requires a redo. Do it on
976 the cheap. */
977 delete_unmarked_insns ();
978 sbitmap_zero (marked);
979 bitmap_clear (processed);
980 bitmap_clear (redo_out);
981
982 /* We do not need to rescan any instructions. We only need
983 to redo the dataflow equations for the blocks that had a
984 change at the top of the block. Then we need to redo the
985 iteration. */
986 if (word_level)
987 df_analyze_problem (df_word_lr, all_blocks, postorder, n_blocks);
988 else
989 df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
990
991 if (old_flag & DF_LR_RUN_DCE)
992 df_set_flags (DF_LR_RUN_DCE);
993
994 prescan_insns_for_dce (true);
995 }
996 }
997
998 delete_unmarked_insns ();
999
1000 BITMAP_FREE (processed);
1001 BITMAP_FREE (redo_out);
1002 BITMAP_FREE (all_blocks);
1003 }
1004
1005
1006 /* Fast register level DCE. */
1007
1008 static unsigned int
1009 rest_of_handle_fast_dce (void)
1010 {
1011 init_dce (true);
1012 fast_dce (false);
1013 fini_dce (true);
1014 return 0;
1015 }
1016
1017
1018 /* Fast byte level DCE. */
1019
1020 void
1021 run_word_dce (void)
1022 {
1023 int old_flags;
1024
1025 if (!flag_dce)
1026 return;
1027
1028 timevar_push (TV_DCE);
1029 old_flags = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
1030 df_word_lr_add_problem ();
1031 init_dce (true);
1032 fast_dce (true);
1033 fini_dce (true);
1034 df_set_flags (old_flags);
1035 timevar_pop (TV_DCE);
1036 }
1037
1038
1039 /* This is an internal call that is used by the df live register
1040 problem to run fast dce as a side effect of creating the live
1041 information. The stack is organized so that the lr problem is run,
1042 this pass is run, which updates the live info and the df scanning
1043 info, and then returns to allow the rest of the problems to be run.
1044
1045 This can be called by elsewhere but it will not update the bit
1046 vectors for any other problems than LR. */
1047
1048 void
1049 run_fast_df_dce (void)
1050 {
1051 if (flag_dce)
1052 {
1053 /* If dce is able to delete something, it has to happen
1054 immediately. Otherwise there will be problems handling the
1055 eq_notes. */
1056 int old_flags =
1057 df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
1058
1059 df_in_progress = true;
1060 rest_of_handle_fast_dce ();
1061 df_in_progress = false;
1062
1063 df_set_flags (old_flags);
1064 }
1065 }
1066
1067
1068 /* Run a fast DCE pass. */
1069
1070 void
1071 run_fast_dce (void)
1072 {
1073 if (flag_dce)
1074 rest_of_handle_fast_dce ();
1075 }
1076
1077
1078 static bool
1079 gate_fast_dce (void)
1080 {
1081 return optimize > 0 && flag_dce
1082 && dbg_cnt (dce_fast);
1083 }
1084
1085 struct rtl_opt_pass pass_fast_rtl_dce =
1086 {
1087 {
1088 RTL_PASS,
1089 "rtl dce", /* name */
1090 gate_fast_dce, /* gate */
1091 rest_of_handle_fast_dce, /* execute */
1092 NULL, /* sub */
1093 NULL, /* next */
1094 0, /* static_pass_number */
1095 TV_DCE, /* tv_id */
1096 0, /* properties_required */
1097 0, /* properties_provided */
1098 0, /* properties_destroyed */
1099 0, /* todo_flags_start */
1100 TODO_dump_func |
1101 TODO_df_finish | TODO_verify_rtl_sharing |
1102 TODO_ggc_collect /* todo_flags_finish */
1103 }
1104 };