1 /* RTL dead code elimination.
2 Copyright (C) 2005-2018 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>. */
19
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"
38
39
40 /* -------------------------------------------------------------------------
41 Core mark/delete routines
42 ------------------------------------------------------------------------- */
43
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;
47
48 /* True if we are allowed to alter the CFG in this pass. */
49 static bool can_alter_cfg = false;
50
51 /* Instructions that have been marked but whose dependencies have not
52 yet been processed. */
53 static vec<rtx_insn *> worklist;
54
55 /* Bitmap of instructions marked as needed indexed by INSN_UID. */
56 static sbitmap marked;
57
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;
61
62 static bool find_call_stack_args (rtx_call_insn *, bool, bool, bitmap);
63
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. */
67
68 static bool
deletable_insn_p_1(rtx body)69 deletable_insn_p_1 (rtx body)
70 {
71 switch (GET_CODE (body))
72 {
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;
83
84 default:
85 return !volatile_refs_p (body);
86 }
87 }
88
89
90 /* Return true if INSN is a normal instruction that can be deleted by
91 the DCE pass. */
92
93 static bool
deletable_insn_p(rtx_insn * insn,bool fast,bitmap arg_stores)94 deletable_insn_p (rtx_insn *insn, bool fast, bitmap arg_stores)
95 {
96 rtx body, x;
97 int i;
98 df_ref def;
99
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 /* Don't delete calls that may throw if we cannot do so. */
113 && ((cfun->can_delete_dead_exceptions && can_alter_cfg)
114 || insn_nothrow_p (insn)))
115 return find_call_stack_args (as_a <rtx_call_insn *> (insn), false,
116 fast, arg_stores);
117
118 /* Don't delete jumps, notes and the like. */
119 if (!NONJUMP_INSN_P (insn))
120 return false;
121
122 /* Don't delete insns that may throw if we cannot do so. */
123 if (!(cfun->can_delete_dead_exceptions && can_alter_cfg)
124 && !insn_nothrow_p (insn))
125 return false;
126
127 /* If INSN sets a global_reg, leave it untouched. */
128 FOR_EACH_INSN_DEF (def, insn)
129 if (HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
130 && global_regs[DF_REF_REGNO (def)])
131 return false;
132 /* Initialization of pseudo PIC register should never be removed. */
133 else if (DF_REF_REG (def) == pic_offset_table_rtx
134 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
135 return false;
136
137 /* Callee-save restores are needed. */
138 if (RTX_FRAME_RELATED_P (insn)
139 && crtl->shrink_wrapped_separate
140 && find_reg_note (insn, REG_CFA_RESTORE, NULL))
141 return false;
142
143 body = PATTERN (insn);
144 switch (GET_CODE (body))
145 {
146 case USE:
147 case VAR_LOCATION:
148 return false;
149
150 case CLOBBER:
151 if (fast)
152 {
153 /* A CLOBBER of a dead pseudo register serves no purpose.
154 That is not necessarily true for hard registers until
155 after reload. */
156 x = XEXP (body, 0);
157 return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);
158 }
159 else
160 /* Because of the way that use-def chains are built, it is not
161 possible to tell if the clobber is dead because it can
162 never be the target of a use-def chain. */
163 return false;
164
165 case PARALLEL:
166 for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
167 if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))
168 return false;
169 return true;
170
171 default:
172 return deletable_insn_p_1 (body);
173 }
174 }
175
176
177 /* Return true if INSN has been marked as needed. */
178
179 static inline int
marked_insn_p(rtx_insn * insn)180 marked_insn_p (rtx_insn *insn)
181 {
182 /* Artificial defs are always needed and they do not have an insn.
183 We should never see them here. */
184 gcc_assert (insn);
185 return bitmap_bit_p (marked, INSN_UID (insn));
186 }
187
188
189 /* If INSN has not yet been marked as needed, mark it now, and add it to
190 the worklist. */
191
192 static void
mark_insn(rtx_insn * insn,bool fast)193 mark_insn (rtx_insn *insn, bool fast)
194 {
195 if (!marked_insn_p (insn))
196 {
197 if (!fast)
198 worklist.safe_push (insn);
199 bitmap_set_bit (marked, INSN_UID (insn));
200 if (dump_file)
201 fprintf (dump_file, " Adding insn %d to worklist\n", INSN_UID (insn));
202 if (CALL_P (insn)
203 && !df_in_progress
204 && !SIBLING_CALL_P (insn)
205 && (RTL_CONST_OR_PURE_CALL_P (insn)
206 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
207 && ((cfun->can_delete_dead_exceptions && can_alter_cfg)
208 || insn_nothrow_p (insn)))
209 find_call_stack_args (as_a <rtx_call_insn *> (insn), true, fast, NULL);
210 }
211 }
212
213
214 /* A note_stores callback used by mark_nonreg_stores. DATA is the
215 instruction containing DEST. */
216
217 static void
mark_nonreg_stores_1(rtx dest,const_rtx pattern,void * data)218 mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data)
219 {
220 if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
221 mark_insn ((rtx_insn *) data, true);
222 }
223
224
225 /* A note_stores callback used by mark_nonreg_stores. DATA is the
226 instruction containing DEST. */
227
228 static void
mark_nonreg_stores_2(rtx dest,const_rtx pattern,void * data)229 mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)
230 {
231 if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
232 mark_insn ((rtx_insn *) data, false);
233 }
234
235
236 /* Mark INSN if BODY stores to a non-register destination. */
237
238 static void
mark_nonreg_stores(rtx body,rtx_insn * insn,bool fast)239 mark_nonreg_stores (rtx body, rtx_insn *insn, bool fast)
240 {
241 if (fast)
242 note_stores (body, mark_nonreg_stores_1, insn);
243 else
244 note_stores (body, mark_nonreg_stores_2, insn);
245 }
246
247
248 /* Return true if a store to SIZE bytes, starting OFF bytes from stack pointer,
249 is a call argument store, and clear corresponding bits from SP_BYTES
250 bitmap if it is. */
251
252 static bool
check_argument_store(HOST_WIDE_INT size,HOST_WIDE_INT off,HOST_WIDE_INT min_sp_off,HOST_WIDE_INT max_sp_off,bitmap sp_bytes)253 check_argument_store (HOST_WIDE_INT size, HOST_WIDE_INT off,
254 HOST_WIDE_INT min_sp_off, HOST_WIDE_INT max_sp_off,
255 bitmap sp_bytes)
256 {
257 HOST_WIDE_INT byte;
258 for (byte = off; byte < off + size; byte++)
259 {
260 if (byte < min_sp_off
261 || byte >= max_sp_off
262 || !bitmap_clear_bit (sp_bytes, byte - min_sp_off))
263 return false;
264 }
265 return true;
266 }
267
268
269 /* Try to find all stack stores of CALL_INSN arguments if
270 ACCUMULATE_OUTGOING_ARGS. If all stack stores have been found
271 and it is therefore safe to eliminate the call, return true,
272 otherwise return false. This function should be first called
273 with DO_MARK false, and only when the CALL_INSN is actually
274 going to be marked called again with DO_MARK true. */
275
276 static bool
find_call_stack_args(rtx_call_insn * call_insn,bool do_mark,bool fast,bitmap arg_stores)277 find_call_stack_args (rtx_call_insn *call_insn, bool do_mark, bool fast,
278 bitmap arg_stores)
279 {
280 rtx p;
281 rtx_insn *insn, *prev_insn;
282 bool ret;
283 HOST_WIDE_INT min_sp_off, max_sp_off;
284 bitmap sp_bytes;
285
286 gcc_assert (CALL_P (call_insn));
287 if (!ACCUMULATE_OUTGOING_ARGS)
288 return true;
289
290 if (!do_mark)
291 {
292 gcc_assert (arg_stores);
293 bitmap_clear (arg_stores);
294 }
295
296 min_sp_off = INTTYPE_MAXIMUM (HOST_WIDE_INT);
297 max_sp_off = 0;
298
299 /* First determine the minimum and maximum offset from sp for
300 stored arguments. */
301 for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
302 if (GET_CODE (XEXP (p, 0)) == USE
303 && MEM_P (XEXP (XEXP (p, 0), 0)))
304 {
305 rtx mem = XEXP (XEXP (p, 0), 0), addr;
306 HOST_WIDE_INT off = 0, size;
307 if (!MEM_SIZE_KNOWN_P (mem) || !MEM_SIZE (mem).is_constant (&size))
308 return false;
309 addr = XEXP (mem, 0);
310 if (GET_CODE (addr) == PLUS
311 && REG_P (XEXP (addr, 0))
312 && CONST_INT_P (XEXP (addr, 1)))
313 {
314 off = INTVAL (XEXP (addr, 1));
315 addr = XEXP (addr, 0);
316 }
317 if (addr != stack_pointer_rtx)
318 {
319 if (!REG_P (addr))
320 return false;
321 /* If not fast, use chains to see if addr wasn't set to
322 sp + offset. */
323 if (!fast)
324 {
325 df_ref use;
326 struct df_link *defs;
327 rtx set;
328
329 FOR_EACH_INSN_USE (use, call_insn)
330 if (rtx_equal_p (addr, DF_REF_REG (use)))
331 break;
332
333 if (use == NULL)
334 return false;
335
336 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
337 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
338 break;
339
340 if (defs == NULL)
341 return false;
342
343 set = single_set (DF_REF_INSN (defs->ref));
344 if (!set)
345 return false;
346
347 if (GET_CODE (SET_SRC (set)) != PLUS
348 || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
349 || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
350 return false;
351
352 off += INTVAL (XEXP (SET_SRC (set), 1));
353 }
354 else
355 return false;
356 }
357 min_sp_off = MIN (min_sp_off, off);
358 max_sp_off = MAX (max_sp_off, off + size);
359 }
360
361 if (min_sp_off >= max_sp_off)
362 return true;
363 sp_bytes = BITMAP_ALLOC (NULL);
364
365 /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
366 which contain arguments. Checking has been done in the previous
367 loop. */
368 for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
369 if (GET_CODE (XEXP (p, 0)) == USE
370 && MEM_P (XEXP (XEXP (p, 0), 0)))
371 {
372 rtx mem = XEXP (XEXP (p, 0), 0), addr;
373 HOST_WIDE_INT off = 0, byte, size;
374 /* Checked in the previous iteration. */
375 size = MEM_SIZE (mem).to_constant ();
376 addr = XEXP (mem, 0);
377 if (GET_CODE (addr) == PLUS
378 && REG_P (XEXP (addr, 0))
379 && CONST_INT_P (XEXP (addr, 1)))
380 {
381 off = INTVAL (XEXP (addr, 1));
382 addr = XEXP (addr, 0);
383 }
384 if (addr != stack_pointer_rtx)
385 {
386 df_ref use;
387 struct df_link *defs;
388 rtx set;
389
390 FOR_EACH_INSN_USE (use, call_insn)
391 if (rtx_equal_p (addr, DF_REF_REG (use)))
392 break;
393
394 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
395 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
396 break;
397
398 set = single_set (DF_REF_INSN (defs->ref));
399 off += INTVAL (XEXP (SET_SRC (set), 1));
400 }
401 for (byte = off; byte < off + size; byte++)
402 {
403 if (!bitmap_set_bit (sp_bytes, byte - min_sp_off))
404 gcc_unreachable ();
405 }
406 }
407
408 /* Walk backwards, looking for argument stores. The search stops
409 when seeing another call, sp adjustment or memory store other than
410 argument store. */
411 ret = false;
412 for (insn = PREV_INSN (call_insn); insn; insn = prev_insn)
413 {
414 rtx set, mem, addr;
415 HOST_WIDE_INT off;
416
417 if (insn == BB_HEAD (BLOCK_FOR_INSN (call_insn)))
418 prev_insn = NULL;
419 else
420 prev_insn = PREV_INSN (insn);
421
422 if (CALL_P (insn))
423 break;
424
425 if (!NONDEBUG_INSN_P (insn))
426 continue;
427
428 set = single_set (insn);
429 if (!set || SET_DEST (set) == stack_pointer_rtx)
430 break;
431
432 if (!MEM_P (SET_DEST (set)))
433 continue;
434
435 mem = SET_DEST (set);
436 addr = XEXP (mem, 0);
437 off = 0;
438 if (GET_CODE (addr) == PLUS
439 && REG_P (XEXP (addr, 0))
440 && CONST_INT_P (XEXP (addr, 1)))
441 {
442 off = INTVAL (XEXP (addr, 1));
443 addr = XEXP (addr, 0);
444 }
445 if (addr != stack_pointer_rtx)
446 {
447 if (!REG_P (addr))
448 break;
449 if (!fast)
450 {
451 df_ref use;
452 struct df_link *defs;
453 rtx set;
454
455 FOR_EACH_INSN_USE (use, insn)
456 if (rtx_equal_p (addr, DF_REF_REG (use)))
457 break;
458
459 if (use == NULL)
460 break;
461
462 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
463 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
464 break;
465
466 if (defs == NULL)
467 break;
468
469 set = single_set (DF_REF_INSN (defs->ref));
470 if (!set)
471 break;
472
473 if (GET_CODE (SET_SRC (set)) != PLUS
474 || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
475 || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
476 break;
477
478 off += INTVAL (XEXP (SET_SRC (set), 1));
479 }
480 else
481 break;
482 }
483
484 HOST_WIDE_INT size;
485 if (!MEM_SIZE_KNOWN_P (mem)
486 || !MEM_SIZE (mem).is_constant (&size)
487 || !check_argument_store (size, off, min_sp_off,
488 max_sp_off, sp_bytes))
489 break;
490
491 if (!deletable_insn_p (insn, fast, NULL))
492 break;
493
494 if (do_mark)
495 mark_insn (insn, fast);
496 else
497 bitmap_set_bit (arg_stores, INSN_UID (insn));
498
499 if (bitmap_empty_p (sp_bytes))
500 {
501 ret = true;
502 break;
503 }
504 }
505
506 BITMAP_FREE (sp_bytes);
507 if (!ret && arg_stores)
508 bitmap_clear (arg_stores);
509
510 return ret;
511 }
512
513
514 /* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN
515 writes to. */
516
517 static void
remove_reg_equal_equiv_notes_for_defs(rtx_insn * insn)518 remove_reg_equal_equiv_notes_for_defs (rtx_insn *insn)
519 {
520 df_ref def;
521
522 FOR_EACH_INSN_DEF (def, insn)
523 remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (def));
524 }
525
526 /* Scan all BBs for debug insns and reset those that reference values
527 defined in unmarked insns. */
528
529 static void
reset_unmarked_insns_debug_uses(void)530 reset_unmarked_insns_debug_uses (void)
531 {
532 basic_block bb;
533 rtx_insn *insn, *next;
534
535 FOR_EACH_BB_REVERSE_FN (bb, cfun)
536 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
537 if (DEBUG_INSN_P (insn))
538 {
539 df_ref use;
540
541 FOR_EACH_INSN_USE (use, insn)
542 {
543 struct df_link *defs;
544 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
545 {
546 rtx_insn *ref_insn;
547 if (DF_REF_IS_ARTIFICIAL (defs->ref))
548 continue;
549 ref_insn = DF_REF_INSN (defs->ref);
550 if (!marked_insn_p (ref_insn))
551 break;
552 }
553 if (!defs)
554 continue;
555 /* ??? FIXME could we propagate the values assigned to
556 each of the DEFs? */
557 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
558 df_insn_rescan_debug_internal (insn);
559 break;
560 }
561 }
562 }
563
564 /* Delete every instruction that hasn't been marked. */
565
566 static void
delete_unmarked_insns(void)567 delete_unmarked_insns (void)
568 {
569 basic_block bb;
570 rtx_insn *insn, *next;
571 bool must_clean = false;
572
573 FOR_EACH_BB_REVERSE_FN (bb, cfun)
574 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
575 if (NONDEBUG_INSN_P (insn))
576 {
577 rtx turn_into_use = NULL_RTX;
578
579 /* Always delete no-op moves. */
580 if (noop_move_p (insn)
581 /* Unless the no-op move can throw and we are not allowed
582 to alter cfg. */
583 && (!cfun->can_throw_non_call_exceptions
584 || (cfun->can_delete_dead_exceptions && can_alter_cfg)
585 || insn_nothrow_p (insn)))
586 {
587 if (RTX_FRAME_RELATED_P (insn))
588 turn_into_use
589 = find_reg_note (insn, REG_CFA_RESTORE, NULL);
590 if (turn_into_use && REG_P (XEXP (turn_into_use, 0)))
591 turn_into_use = XEXP (turn_into_use, 0);
592 else
593 turn_into_use = NULL_RTX;
594 }
595
596 /* Otherwise rely only on the DCE algorithm. */
597 else if (marked_insn_p (insn))
598 continue;
599
600 /* Beware that reaching a dbg counter limit here can result
601 in miscompiled file. This occurs when a group of insns
602 must be deleted together, typically because the kept insn
603 depends on the output from the deleted insn. Deleting
604 this insns in reverse order (both at the bb level and
605 when looking at the blocks) minimizes this, but does not
606 eliminate it, since it is possible for the using insn to
607 be top of a block and the producer to be at the bottom of
608 the block. However, in most cases this will only result
609 in an uninitialized use of an insn that is dead anyway.
610
611 However, there is one rare case that will cause a
612 miscompile: deletion of non-looping pure and constant
613 calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
614 In this case it is possible to remove the call, but leave
615 the argument pushes to the stack. Because of the changes
616 to the stack pointer, this will almost always lead to a
617 miscompile. */
618 if (!dbg_cnt (dce))
619 continue;
620
621 if (dump_file)
622 fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
623
624 /* Before we delete the insn we have to remove the REG_EQUAL notes
625 for the destination regs in order to avoid dangling notes. */
626 remove_reg_equal_equiv_notes_for_defs (insn);
627
628 if (turn_into_use)
629 {
630 /* Don't remove frame related noop moves if they cary
631 REG_CFA_RESTORE note, while we don't need to emit any code,
632 we need it to emit the CFI restore note. */
633 PATTERN (insn)
634 = gen_rtx_USE (GET_MODE (turn_into_use), turn_into_use);
635 INSN_CODE (insn) = -1;
636 df_insn_rescan (insn);
637 }
638 else
639 /* Now delete the insn. */
640 must_clean |= delete_insn_and_edges (insn);
641 }
642
643 /* Deleted a pure or const call. */
644 if (must_clean)
645 {
646 delete_unreachable_blocks ();
647 free_dominance_info (CDI_DOMINATORS);
648 }
649 }
650
651
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. */
655
656 static void
prescan_insns_for_dce(bool fast)657 prescan_insns_for_dce (bool fast)
658 {
659 basic_block bb;
660 rtx_insn *insn, *prev;
661 bitmap arg_stores = NULL;
662
663 if (dump_file)
664 fprintf (dump_file, "Finding needed instructions:\n");
665
666 if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS)
667 arg_stores = BITMAP_ALLOC (NULL);
668
669 FOR_EACH_BB_FN (bb, cfun)
670 {
671 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)
672 if (NONDEBUG_INSN_P (insn))
673 {
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);
682 }
683 /* find_call_stack_args only looks at argument stores in the
684 same bb. */
685 if (arg_stores)
686 bitmap_clear (arg_stores);
687 }
688
689 if (arg_stores)
690 BITMAP_FREE (arg_stores);
691
692 if (dump_file)
693 fprintf (dump_file, "Finished finding needed instructions:\n");
694 }
695
696
697 /* UD-based DSE routines. */
698
699 /* Mark instructions that define artificially-used registers, such as
700 the frame pointer and the stack pointer. */
701
702 static void
mark_artificial_uses(void)703 mark_artificial_uses (void)
704 {
705 basic_block bb;
706 struct df_link *defs;
707 df_ref use;
708
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);
714 }
715
716
717 /* Mark every instruction that defines a register value that INSN uses. */
718
719 static void
mark_reg_dependencies(rtx_insn * insn)720 mark_reg_dependencies (rtx_insn *insn)
721 {
722 struct df_link *defs;
723 df_ref use;
724
725 if (DEBUG_INSN_P (insn))
726 return;
727
728 FOR_EACH_INSN_USE (use, insn)
729 {
730 if (dump_file)
731 {
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));
735 }
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);
739 }
740 }
741
742
743 /* Initialize global variables for a new DCE pass. */
744
745 static void
init_dce(bool fast)746 init_dce (bool fast)
747 {
748 if (!df_in_progress)
749 {
750 if (!fast)
751 {
752 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
753 df_chain_add_problem (DF_UD_CHAIN);
754 }
755 df_analyze ();
756 }
757
758 if (dump_file)
759 df_dump (dump_file);
760
761 if (fast)
762 {
763 bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
764 bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
765 can_alter_cfg = false;
766 }
767 else
768 can_alter_cfg = true;
769
770 marked = sbitmap_alloc (get_max_uid () + 1);
771 bitmap_clear (marked);
772 }
773
774
775 /* Free the data allocated by init_dce. */
776
777 static void
fini_dce(bool fast)778 fini_dce (bool fast)
779 {
780 sbitmap_free (marked);
781
782 if (fast)
783 {
784 bitmap_obstack_release (&dce_blocks_bitmap_obstack);
785 bitmap_obstack_release (&dce_tmp_bitmap_obstack);
786 }
787 }
788
789
790 /* UD-chain based DCE. */
791
792 static unsigned int
rest_of_handle_ud_dce(void)793 rest_of_handle_ud_dce (void)
794 {
795 rtx_insn *insn;
796
797 init_dce (false);
798
799 prescan_insns_for_dce (false);
800 mark_artificial_uses ();
801 while (worklist.length () > 0)
802 {
803 insn = worklist.pop ();
804 mark_reg_dependencies (insn);
805 }
806 worklist.release ();
807
808 if (MAY_HAVE_DEBUG_BIND_INSNS)
809 reset_unmarked_insns_debug_uses ();
810
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 ();
815
816 fini_dce (false);
817 return 0;
818 }
819
820
821 namespace {
822
823 const pass_data pass_data_ud_rtl_dce =
824 {
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 */
834 };
835
836 class pass_ud_rtl_dce : public rtl_opt_pass
837 {
838 public:
pass_ud_rtl_dce(gcc::context * ctxt)839 pass_ud_rtl_dce (gcc::context *ctxt)
840 : rtl_opt_pass (pass_data_ud_rtl_dce, ctxt)
841 {}
842
843 /* opt_pass methods: */
gate(function *)844 virtual bool gate (function *)
845 {
846 return optimize > 1 && flag_dce && dbg_cnt (dce_ud);
847 }
848
execute(function *)849 virtual unsigned int execute (function *)
850 {
851 return rest_of_handle_ud_dce ();
852 }
853
854 }; // class pass_ud_rtl_dce
855
856 } // anon namespace
857
858 rtl_opt_pass *
make_pass_ud_rtl_dce(gcc::context * ctxt)859 make_pass_ud_rtl_dce (gcc::context *ctxt)
860 {
861 return new pass_ud_rtl_dce (ctxt);
862 }
863
864
865 /* -------------------------------------------------------------------------
866 Fast DCE functions
867 ------------------------------------------------------------------------- */
868
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. */
874
875 static bool
word_dce_process_block(basic_block bb,bool redo_out,struct dead_debug_global * global_debug)876 word_dce_process_block (basic_block bb, bool redo_out,
877 struct dead_debug_global *global_debug)
878 {
879 bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
880 rtx_insn *insn;
881 bool block_changed;
882 struct dead_debug_local debug;
883
884 if (redo_out)
885 {
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);
895 }
896
897 if (dump_file)
898 {
899 fprintf (dump_file, "processing block %d live out = ", bb->index);
900 df_print_word_regset (dump_file, DF_WORD_LR_OUT (bb));
901 }
902
903 bitmap_copy (local_live, DF_WORD_LR_OUT (bb));
904 dead_debug_local_init (&debug, NULL, global_debug);
905
906 FOR_BB_INSNS_REVERSE (bb, insn)
907 if (DEBUG_INSN_P (insn))
908 {
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));
917 }
918 else if (INSN_P (insn))
919 {
920 bool any_changed;
921
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);
927
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);
932
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))
938 {
939 df_ref def;
940
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);
947 }
948
949 if (dump_file)
950 {
951 fprintf (dump_file, "finished processing insn %d live out = ",
952 INSN_UID (insn));
953 df_print_word_regset (dump_file, local_live);
954 }
955 }
956
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);
960
961 dead_debug_local_finish (&debug, NULL);
962 BITMAP_FREE (local_live);
963 return block_changed;
964 }
965
966
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. */
972
973 static bool
dce_process_block(basic_block bb,bool redo_out,bitmap au,struct dead_debug_global * global_debug)974 dce_process_block (basic_block bb, bool redo_out, bitmap au,
975 struct dead_debug_global *global_debug)
976 {
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;
982
983 if (redo_out)
984 {
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);
994 }
995
996 if (dump_file)
997 {
998 fprintf (dump_file, "processing block %d lr out = ", bb->index);
999 df_print_regset (dump_file, DF_LR_OUT (bb));
1000 }
1001
1002 bitmap_copy (local_live, DF_LR_OUT (bb));
1003
1004 df_simulate_initialize_backwards (bb, local_live);
1005 dead_debug_local_init (&debug, NULL, global_debug);
1006
1007 FOR_BB_INSNS_REVERSE (bb, insn)
1008 if (DEBUG_INSN_P (insn))
1009 {
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));
1015 }
1016 else if (INSN_P (insn))
1017 {
1018 bool needed = marked_insn_p (insn);
1019
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)))
1025 {
1026 needed = true;
1027 mark_insn (insn, true);
1028 break;
1029 }
1030
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);
1034
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);
1039
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);
1050 }
1051
1052 dead_debug_local_finish (&debug, NULL);
1053 df_simulate_finalize_backwards (bb, local_live);
1054
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);
1058
1059 BITMAP_FREE (local_live);
1060 return block_changed;
1061 }
1062
1063
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. */
1067
1068 static void
fast_dce(bool word_level)1069 fast_dce (bool word_level)
1070 {
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;
1080
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;
1090
1091 prescan_insns_for_dce (true);
1092
1093 for (i = 0; i < n_blocks; i++)
1094 bitmap_set_bit (all_blocks, postorder[i]);
1095
1096 dead_debug_global_init (&global_debug, NULL);
1097
1098 while (global_changed)
1099 {
1100 global_changed = false;
1101
1102 for (i = 0; i < n_blocks; i++)
1103 {
1104 int index = postorder[i];
1105 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
1106 bool local_changed;
1107
1108 if (index < NUM_FIXED_BLOCKS)
1109 {
1110 bitmap_set_bit (processed, index);
1111 continue;
1112 }
1113
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);
1124
1125 if (local_changed)
1126 {
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);
1138 }
1139 }
1140
1141 if (global_changed)
1142 {
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);
1146
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);
1153
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);
1162
1163 if (old_flag & DF_LR_RUN_DCE)
1164 df_set_flags (DF_LR_RUN_DCE);
1165
1166 prescan_insns_for_dce (true);
1167 }
1168 }
1169
1170 dead_debug_global_finish (&global_debug, NULL);
1171
1172 delete_unmarked_insns ();
1173
1174 BITMAP_FREE (processed);
1175 BITMAP_FREE (redo_out);
1176 BITMAP_FREE (all_blocks);
1177 }
1178
1179
1180 /* Fast register level DCE. */
1181
1182 static unsigned int
rest_of_handle_fast_dce(void)1183 rest_of_handle_fast_dce (void)
1184 {
1185 init_dce (true);
1186 fast_dce (false);
1187 fini_dce (true);
1188 return 0;
1189 }
1190
1191
1192 /* Fast byte level DCE. */
1193
1194 void
run_word_dce(void)1195 run_word_dce (void)
1196 {
1197 int old_flags;
1198
1199 if (!flag_dce)
1200 return;
1201
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);
1210 }
1211
1212
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.
1218
1219 This can be called by elsewhere but it will not update the bit
1220 vectors for any other problems than LR. */
1221
1222 void
run_fast_df_dce(void)1223 run_fast_df_dce (void)
1224 {
1225 if (flag_dce)
1226 {
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);
1232
1233 df_in_progress = true;
1234 rest_of_handle_fast_dce ();
1235 df_in_progress = false;
1236
1237 df_set_flags (old_flags);
1238 }
1239 }
1240
1241
1242 /* Run a fast DCE pass. */
1243
1244 void
run_fast_dce(void)1245 run_fast_dce (void)
1246 {
1247 if (flag_dce)
1248 rest_of_handle_fast_dce ();
1249 }
1250
1251
1252 namespace {
1253
1254 const pass_data pass_data_fast_rtl_dce =
1255 {
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 */
1265 };
1266
1267 class pass_fast_rtl_dce : public rtl_opt_pass
1268 {
1269 public:
pass_fast_rtl_dce(gcc::context * ctxt)1270 pass_fast_rtl_dce (gcc::context *ctxt)
1271 : rtl_opt_pass (pass_data_fast_rtl_dce, ctxt)
1272 {}
1273
1274 /* opt_pass methods: */
gate(function *)1275 virtual bool gate (function *)
1276 {
1277 return optimize > 0 && flag_dce && dbg_cnt (dce_fast);
1278 }
1279
execute(function *)1280 virtual unsigned int execute (function *)
1281 {
1282 return rest_of_handle_fast_dce ();
1283 }
1284
1285 }; // class pass_fast_rtl_dce
1286
1287 } // anon namespace
1288
1289 rtl_opt_pass *
make_pass_fast_rtl_dce(gcc::context * ctxt)1290 make_pass_fast_rtl_dce (gcc::context *ctxt)
1291 {
1292 return new pass_fast_rtl_dce (ctxt);
1293 }
1294