Branch data Line data Source code
1 : : /* RTL dead code elimination.
2 : : Copyright (C) 2005-2025 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 : : #include "rtl-iter.h"
39 : :
40 : :
41 : : /* -------------------------------------------------------------------------
42 : : Core mark/delete routines
43 : : ------------------------------------------------------------------------- */
44 : :
45 : : /* True if we are invoked while the df engine is running; in this case,
46 : : we don't want to reenter it. */
47 : : static bool df_in_progress = false;
48 : :
49 : : /* True if we are allowed to alter the CFG in this pass. */
50 : : static bool can_alter_cfg = false;
51 : :
52 : : /* Instructions that have been marked but whose dependencies have not
53 : : yet been processed. */
54 : : static vec<rtx_insn *> worklist;
55 : :
56 : : /* Bitmap of instructions marked as needed indexed by INSN_UID. */
57 : : static sbitmap marked;
58 : :
59 : : /* Bitmap obstacks used for block processing by the fast algorithm. */
60 : : static bitmap_obstack dce_blocks_bitmap_obstack;
61 : : static bitmap_obstack dce_tmp_bitmap_obstack;
62 : :
63 : : static bool find_call_stack_args (rtx_call_insn *, bool, bool, bitmap);
64 : :
65 : : /* A subroutine for which BODY is part of the instruction being tested;
66 : : either the top-level pattern, or an element of a PARALLEL. The
67 : : instruction is known not to be a bare USE or CLOBBER. */
68 : :
69 : : static bool
70 : 864874232 : deletable_insn_p_1 (rtx body)
71 : : {
72 : 864874232 : switch (GET_CODE (body))
73 : : {
74 : : case PREFETCH:
75 : : case TRAP_IF:
76 : : /* The UNSPEC case was added here because the ia-64 claims that
77 : : USEs do not work after reload and generates UNSPECS rather
78 : : than USEs. Since dce is run after reload we need to avoid
79 : : deleting these even if they are dead. If it turns out that
80 : : USEs really do work after reload, the ia-64 should be
81 : : changed, and the UNSPEC case can be removed. */
82 : : case UNSPEC:
83 : : return false;
84 : :
85 : 864571010 : default:
86 : 864571010 : return !volatile_refs_p (body);
87 : : }
88 : : }
89 : :
90 : : /* Don't delete calls that may throw if we cannot do so. */
91 : :
92 : : static bool
93 : 2181630 : can_delete_call (rtx_insn *insn)
94 : : {
95 : 2181630 : if (cfun->can_delete_dead_exceptions && can_alter_cfg)
96 : : return true;
97 : 1559657 : if (!insn_nothrow_p (insn))
98 : : return false;
99 : 1551003 : if (can_alter_cfg)
100 : : return true;
101 : : /* If we can't alter cfg, even when the call can't throw exceptions, it
102 : : might have EDGE_ABNORMAL_CALL edges and so we shouldn't delete such
103 : : calls. */
104 : 1456684 : gcc_assert (CALL_P (insn));
105 : 1456684 : if (BLOCK_FOR_INSN (insn) && BB_END (BLOCK_FOR_INSN (insn)) == insn)
106 : : {
107 : 627 : edge e;
108 : 627 : edge_iterator ei;
109 : :
110 : 1008 : FOR_EACH_EDGE (e, ei, BLOCK_FOR_INSN (insn)->succs)
111 : 627 : if ((e->flags & EDGE_ABNORMAL_CALL) != 0)
112 : 246 : return false;
113 : : }
114 : : return true;
115 : : }
116 : :
117 : : /* Return true if INSN is a normal instruction that can be deleted by
118 : : the DCE pass. */
119 : :
120 : : static bool
121 : 925574623 : deletable_insn_p (rtx_insn *insn, bool fast, bitmap arg_stores)
122 : : {
123 : 925574623 : rtx body, x;
124 : 925574623 : int i;
125 : 925574623 : df_ref def;
126 : :
127 : 925574623 : if (CALL_P (insn)
128 : : /* We cannot delete calls inside of the recursive dce because
129 : : this may cause basic blocks to be deleted and this messes up
130 : : the rest of the stack of optimization passes. */
131 : 70293767 : && (!df_in_progress)
132 : : /* We cannot delete pure or const sibling calls because it is
133 : : hard to see the result. */
134 : 13177468 : && (!SIBLING_CALL_P (insn))
135 : : /* We can delete dead const or pure calls as long as they do not
136 : : infinite loop. */
137 : 12911488 : && (RTL_CONST_OR_PURE_CALL_P (insn)
138 : 1184474 : && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
139 : : /* Don't delete calls that may throw if we cannot do so. */
140 : 926667181 : && can_delete_call (insn))
141 : 1088108 : return find_call_stack_args (as_a <rtx_call_insn *> (insn), false,
142 : 1088108 : fast, arg_stores);
143 : :
144 : : /* Don't delete jumps, notes and the like. */
145 : 924486515 : if (!NONJUMP_INSN_P (insn))
146 : : return false;
147 : :
148 : : /* Don't delete insns that may throw if we cannot do so. */
149 : 426913746 : if (!(cfun->can_delete_dead_exceptions && can_alter_cfg)
150 : 1165069014 : && !insn_nothrow_p (insn))
151 : : return false;
152 : :
153 : : /* If INSN sets a global_reg, leave it untouched. */
154 : 1494230868 : FOR_EACH_INSN_DEF (def, insn)
155 : 757379783 : if (HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
156 : 504450748 : && global_regs[DF_REF_REGNO (def)])
157 : : return false;
158 : : /* Initialization of pseudo PIC register should never be removed. */
159 : 757379200 : else if (DF_REF_REG (def) == pic_offset_table_rtx
160 : 757379200 : && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
161 : : return false;
162 : :
163 : : /* Callee-save restores are needed. */
164 : 736851085 : if (RTX_FRAME_RELATED_P (insn)
165 : 11057849 : && crtl->shrink_wrapped_separate
166 : 736851085 : && find_reg_note (insn, REG_CFA_RESTORE, NULL))
167 : : return false;
168 : :
169 : 736851085 : body = PATTERN (insn);
170 : 736851085 : switch (GET_CODE (body))
171 : : {
172 : : case USE:
173 : : case VAR_LOCATION:
174 : : return false;
175 : :
176 : 1014942 : case CLOBBER:
177 : 1014942 : if (fast)
178 : : {
179 : : /* A CLOBBER of a dead pseudo register serves no purpose.
180 : : That is not necessarily true for hard registers until
181 : : after reload. */
182 : 819181 : x = XEXP (body, 0);
183 : 819181 : return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);
184 : : }
185 : : else
186 : : /* Because of the way that use-def chains are built, it is not
187 : : possible to tell if the clobber is dead because it can
188 : : never be the target of a use-def chain. */
189 : : return false;
190 : :
191 : 127500794 : case PARALLEL:
192 : 388282413 : for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
193 : 262616935 : if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))
194 : : return false;
195 : : return true;
196 : :
197 : 602257297 : default:
198 : 602257297 : return deletable_insn_p_1 (body);
199 : : }
200 : : }
201 : :
202 : :
203 : : /* Return true if INSN has been marked as needed. */
204 : :
205 : : static inline int
206 : 2770663334 : marked_insn_p (rtx_insn *insn)
207 : : {
208 : : /* Artificial defs are always needed and they do not have an insn.
209 : : We should never see them here. */
210 : 2770663334 : gcc_assert (insn);
211 : 2770663334 : return bitmap_bit_p (marked, INSN_UID (insn));
212 : : }
213 : :
214 : :
215 : : /* If INSN has not yet been marked as needed, mark it now, and add it to
216 : : the worklist. */
217 : :
218 : : static void
219 : 962312414 : mark_insn (rtx_insn *insn, bool fast)
220 : : {
221 : 962312414 : if (!marked_insn_p (insn))
222 : : {
223 : 922338960 : if (!fast)
224 : 51797607 : worklist.safe_push (insn);
225 : 922338960 : bitmap_set_bit (marked, INSN_UID (insn));
226 : 922338960 : if (dump_file)
227 : 13009 : fprintf (dump_file, " Adding insn %d to worklist\n", INSN_UID (insn));
228 : 922338960 : if (CALL_P (insn)
229 : 70290281 : && !df_in_progress
230 : 13173982 : && !SIBLING_CALL_P (insn)
231 : 12908002 : && (RTL_CONST_OR_PURE_CALL_P (insn)
232 : 1180988 : && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
233 : 923428032 : && can_delete_call (insn))
234 : 1084622 : find_call_stack_args (as_a <rtx_call_insn *> (insn), true, fast, NULL);
235 : : }
236 : 962312414 : }
237 : :
238 : :
239 : : /* A note_stores callback used by mark_nonreg_stores. DATA is the
240 : : instruction containing DEST. */
241 : :
242 : : static void
243 : 801580944 : mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data)
244 : : {
245 : 801580944 : if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
246 : 129640926 : mark_insn ((rtx_insn *) data, true);
247 : 801580944 : }
248 : :
249 : :
250 : : /* A note_stores callback used by mark_nonreg_stores. DATA is the
251 : : instruction containing DEST. */
252 : :
253 : : static void
254 : 48701894 : mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)
255 : : {
256 : 48701894 : if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
257 : 6682246 : mark_insn ((rtx_insn *) data, false);
258 : 48701894 : }
259 : :
260 : :
261 : : /* Mark INSN if it stores to a non-register destination. */
262 : :
263 : : static void
264 : 719853450 : mark_nonreg_stores (rtx_insn *insn, bool fast)
265 : : {
266 : 719853450 : if (fast)
267 : 678822544 : note_stores (insn, mark_nonreg_stores_1, insn);
268 : : else
269 : 41030906 : note_stores (insn, mark_nonreg_stores_2, insn);
270 : 719853450 : }
271 : :
272 : :
273 : : /* Return true if a store to SIZE bytes, starting OFF bytes from stack pointer,
274 : : is a call argument store, and clear corresponding bits from SP_BYTES
275 : : bitmap if it is. */
276 : :
277 : : static bool
278 : 276 : check_argument_store (HOST_WIDE_INT size, HOST_WIDE_INT off,
279 : : HOST_WIDE_INT min_sp_off, HOST_WIDE_INT max_sp_off,
280 : : bitmap sp_bytes)
281 : : {
282 : 276 : HOST_WIDE_INT byte;
283 : 1396 : for (byte = off; byte < off + size; byte++)
284 : : {
285 : 1120 : if (byte < min_sp_off
286 : 1120 : || byte >= max_sp_off
287 : 1120 : || !bitmap_clear_bit (sp_bytes, byte - min_sp_off))
288 : 0 : return false;
289 : : }
290 : : return true;
291 : : }
292 : :
293 : : /* If MEM has sp address, return 0, if it has sp + const address,
294 : : return that const, if it has reg address where reg is set to sp + const
295 : : and FAST is false, return const, otherwise return
296 : : INTTYPE_MINUMUM (HOST_WIDE_INT). */
297 : :
298 : : static HOST_WIDE_INT
299 : 832 : sp_based_mem_offset (rtx_call_insn *call_insn, const_rtx mem, bool fast)
300 : : {
301 : 832 : HOST_WIDE_INT off = 0;
302 : 832 : rtx addr = XEXP (mem, 0);
303 : 832 : if (GET_CODE (addr) == PLUS
304 : 676 : && REG_P (XEXP (addr, 0))
305 : 676 : && CONST_INT_P (XEXP (addr, 1)))
306 : : {
307 : 676 : off = INTVAL (XEXP (addr, 1));
308 : 676 : addr = XEXP (addr, 0);
309 : : }
310 : 832 : if (addr == stack_pointer_rtx)
311 : : return off;
312 : :
313 : 0 : if (!REG_P (addr) || fast)
314 : : return INTTYPE_MINIMUM (HOST_WIDE_INT);
315 : :
316 : : /* If not fast, use chains to see if addr wasn't set to sp + offset. */
317 : 0 : df_ref use;
318 : 0 : FOR_EACH_INSN_USE (use, call_insn)
319 : 0 : if (rtx_equal_p (addr, DF_REF_REG (use)))
320 : : break;
321 : :
322 : 0 : if (use == NULL)
323 : : return INTTYPE_MINIMUM (HOST_WIDE_INT);
324 : :
325 : 0 : struct df_link *defs;
326 : 0 : for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
327 : 0 : if (! DF_REF_IS_ARTIFICIAL (defs->ref))
328 : : break;
329 : :
330 : 0 : if (defs == NULL)
331 : : return INTTYPE_MINIMUM (HOST_WIDE_INT);
332 : :
333 : 0 : rtx set = single_set (DF_REF_INSN (defs->ref));
334 : 0 : if (!set)
335 : : return INTTYPE_MINIMUM (HOST_WIDE_INT);
336 : :
337 : 0 : if (GET_CODE (SET_SRC (set)) != PLUS
338 : 0 : || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
339 : 0 : || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
340 : : return INTTYPE_MINIMUM (HOST_WIDE_INT);
341 : :
342 : 0 : off += INTVAL (XEXP (SET_SRC (set), 1));
343 : 0 : return off;
344 : : }
345 : :
346 : : /* Data for check_argument_load called via note_uses. */
347 : : struct check_argument_load_data {
348 : : bitmap sp_bytes;
349 : : HOST_WIDE_INT min_sp_off, max_sp_off;
350 : : rtx_call_insn *call_insn;
351 : : bool fast;
352 : : bool load_found;
353 : : };
354 : :
355 : : /* Helper function for find_call_stack_args. Check if there are
356 : : any loads from the argument slots in between the const/pure call
357 : : and store to the argument slot, set LOAD_FOUND if any is found. */
358 : :
359 : : static void
360 : 838 : check_argument_load (rtx *loc, void *data)
361 : : {
362 : 838 : struct check_argument_load_data *d
363 : : = (struct check_argument_load_data *) data;
364 : 838 : subrtx_iterator::array_type array;
365 : 2144 : FOR_EACH_SUBRTX (iter, array, *loc, NONCONST)
366 : : {
367 : 1306 : const_rtx mem = *iter;
368 : 1306 : HOST_WIDE_INT size;
369 : 1306 : if (MEM_P (mem)
370 : 4 : && MEM_SIZE_KNOWN_P (mem)
371 : 1310 : && MEM_SIZE (mem).is_constant (&size))
372 : : {
373 : 4 : HOST_WIDE_INT off = sp_based_mem_offset (d->call_insn, mem, d->fast);
374 : 4 : if (off != INTTYPE_MINIMUM (HOST_WIDE_INT)
375 : 4 : && off < d->max_sp_off
376 : 0 : && off + size > d->min_sp_off)
377 : 0 : for (HOST_WIDE_INT byte = MAX (off, d->min_sp_off);
378 : 0 : byte < MIN (off + size, d->max_sp_off); byte++)
379 : 0 : if (bitmap_bit_p (d->sp_bytes, byte - d->min_sp_off))
380 : : {
381 : 0 : d->load_found = true;
382 : 0 : return;
383 : : }
384 : : }
385 : : }
386 : 838 : }
387 : :
388 : : /* Try to find all stack stores of CALL_INSN arguments if
389 : : ACCUMULATE_OUTGOING_ARGS. If all stack stores have been found
390 : : and it is therefore safe to eliminate the call, return true,
391 : : otherwise return false. This function should be first called
392 : : with DO_MARK false, and only when the CALL_INSN is actually
393 : : going to be marked called again with DO_MARK true. */
394 : :
395 : : static bool
396 : 2172730 : find_call_stack_args (rtx_call_insn *call_insn, bool do_mark, bool fast,
397 : : bitmap arg_stores)
398 : : {
399 : 2172730 : rtx p;
400 : 2172730 : rtx_insn *insn, *prev_insn;
401 : 2172730 : bool ret;
402 : 2172730 : HOST_WIDE_INT min_sp_off, max_sp_off;
403 : 2172730 : bitmap sp_bytes;
404 : :
405 : 2172730 : gcc_assert (CALL_P (call_insn));
406 : 2172730 : if (!ACCUMULATE_OUTGOING_ARGS)
407 : 2172150 : return true;
408 : :
409 : 580 : if (!do_mark)
410 : : {
411 : 290 : gcc_assert (arg_stores);
412 : 290 : bitmap_clear (arg_stores);
413 : : }
414 : :
415 : 580 : min_sp_off = INTTYPE_MAXIMUM (HOST_WIDE_INT);
416 : 580 : max_sp_off = 0;
417 : :
418 : : /* First determine the minimum and maximum offset from sp for
419 : : stored arguments. */
420 : 2260 : for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
421 : 1680 : if (GET_CODE (XEXP (p, 0)) == USE
422 : 1404 : && MEM_P (XEXP (XEXP (p, 0), 0)))
423 : : {
424 : 276 : rtx mem = XEXP (XEXP (p, 0), 0);
425 : 276 : HOST_WIDE_INT size;
426 : 276 : if (!MEM_SIZE_KNOWN_P (mem) || !MEM_SIZE (mem).is_constant (&size))
427 : 2172730 : return false;
428 : 276 : HOST_WIDE_INT off = sp_based_mem_offset (call_insn, mem, fast);
429 : 276 : if (off == INTTYPE_MINIMUM (HOST_WIDE_INT))
430 : : return false;
431 : 276 : min_sp_off = MIN (min_sp_off, off);
432 : 276 : max_sp_off = MAX (max_sp_off, off + size);
433 : : }
434 : :
435 : 580 : if (min_sp_off >= max_sp_off)
436 : : return true;
437 : 52 : sp_bytes = BITMAP_ALLOC (NULL);
438 : :
439 : : /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
440 : : which contain arguments. Checking has been done in the previous
441 : : loop. */
442 : 688 : for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
443 : 636 : if (GET_CODE (XEXP (p, 0)) == USE
444 : 588 : && MEM_P (XEXP (XEXP (p, 0), 0)))
445 : : {
446 : 276 : rtx mem = XEXP (XEXP (p, 0), 0);
447 : : /* Checked in the previous iteration. */
448 : 276 : HOST_WIDE_INT size = MEM_SIZE (mem).to_constant ();
449 : 276 : HOST_WIDE_INT off = sp_based_mem_offset (call_insn, mem, fast);
450 : 276 : gcc_checking_assert (off != INTTYPE_MINIMUM (HOST_WIDE_INT));
451 : 1396 : for (HOST_WIDE_INT byte = off; byte < off + size; byte++)
452 : 1120 : if (!bitmap_set_bit (sp_bytes, byte - min_sp_off))
453 : 0 : gcc_unreachable ();
454 : : }
455 : :
456 : : /* Walk backwards, looking for argument stores. The search stops
457 : : when seeing another call, sp adjustment, memory store other than
458 : : argument store or a read from an argument stack slot. */
459 : 52 : struct check_argument_load_data data
460 : 52 : = { sp_bytes, min_sp_off, max_sp_off, call_insn, fast, false };
461 : 52 : ret = false;
462 : 562 : for (insn = PREV_INSN (call_insn); insn; insn = prev_insn)
463 : : {
464 : 562 : if (insn == BB_HEAD (BLOCK_FOR_INSN (call_insn)))
465 : : prev_insn = NULL;
466 : : else
467 : 562 : prev_insn = PREV_INSN (insn);
468 : :
469 : 562 : if (CALL_P (insn))
470 : : break;
471 : :
472 : 562 : if (!NONDEBUG_INSN_P (insn))
473 : 0 : continue;
474 : :
475 : 562 : rtx set = single_set (insn);
476 : 562 : if (!set || SET_DEST (set) == stack_pointer_rtx)
477 : : break;
478 : :
479 : 562 : note_uses (&PATTERN (insn), check_argument_load, &data);
480 : 562 : if (data.load_found)
481 : : break;
482 : :
483 : 562 : if (!MEM_P (SET_DEST (set)))
484 : 286 : continue;
485 : :
486 : 276 : rtx mem = SET_DEST (set);
487 : 276 : HOST_WIDE_INT off = sp_based_mem_offset (call_insn, mem, fast);
488 : 276 : if (off == INTTYPE_MINIMUM (HOST_WIDE_INT))
489 : : break;
490 : :
491 : 276 : HOST_WIDE_INT size;
492 : 276 : if (!MEM_SIZE_KNOWN_P (mem)
493 : 276 : || !MEM_SIZE (mem).is_constant (&size)
494 : 276 : || !check_argument_store (size, off, min_sp_off,
495 : : max_sp_off, sp_bytes))
496 : : break;
497 : :
498 : 276 : if (!deletable_insn_p (insn, fast, NULL))
499 : : break;
500 : :
501 : 276 : if (do_mark)
502 : 138 : mark_insn (insn, fast);
503 : : else
504 : 138 : bitmap_set_bit (arg_stores, INSN_UID (insn));
505 : :
506 : 276 : if (bitmap_empty_p (sp_bytes))
507 : : {
508 : : ret = true;
509 : : break;
510 : : }
511 : : }
512 : :
513 : 52 : BITMAP_FREE (sp_bytes);
514 : 52 : if (!ret && arg_stores)
515 : 0 : bitmap_clear (arg_stores);
516 : :
517 : : return ret;
518 : : }
519 : :
520 : :
521 : : /* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN
522 : : writes to. */
523 : :
524 : : static void
525 : 3245237 : remove_reg_equal_equiv_notes_for_defs (rtx_insn *insn)
526 : : {
527 : 3245237 : df_ref def;
528 : :
529 : 6866010 : FOR_EACH_INSN_DEF (def, insn)
530 : 3620773 : remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (def));
531 : 3245237 : }
532 : :
533 : : /* Scan all BBs for debug insns and reset those that reference values
534 : : defined in unmarked insns. */
535 : :
536 : : static void
537 : 466629 : reset_unmarked_insns_debug_uses (void)
538 : : {
539 : 466629 : basic_block bb;
540 : 466629 : rtx_insn *insn, *next;
541 : :
542 : 6766281 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
543 : 183095016 : FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
544 : 85247856 : if (DEBUG_INSN_P (insn))
545 : : {
546 : 40343702 : df_ref use;
547 : :
548 : 49001735 : FOR_EACH_INSN_USE (use, insn)
549 : : {
550 : 8660474 : struct df_link *defs;
551 : 20422838 : for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
552 : : {
553 : 11764805 : rtx_insn *ref_insn;
554 : 11764805 : if (DF_REF_IS_ARTIFICIAL (defs->ref))
555 : 2740475 : continue;
556 : 9024330 : ref_insn = DF_REF_INSN (defs->ref);
557 : 9024330 : if (!marked_insn_p (ref_insn))
558 : : break;
559 : : }
560 : 8660474 : if (!defs)
561 : 8658033 : continue;
562 : : /* ??? FIXME could we propagate the values assigned to
563 : : each of the DEFs? */
564 : 2441 : INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
565 : 2441 : df_insn_rescan_debug_internal (insn);
566 : 2441 : break;
567 : : }
568 : : }
569 : 466629 : }
570 : :
571 : : /* Delete every instruction that hasn't been marked. */
572 : :
573 : : static void
574 : 10549086 : delete_unmarked_insns (void)
575 : : {
576 : 10549086 : basic_block bb;
577 : 10549086 : rtx_insn *insn, *next;
578 : 10549086 : bool must_clean = false;
579 : :
580 : 181527817 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
581 : 4317967328 : FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
582 : 1988004933 : if (NONDEBUG_INSN_P (insn))
583 : : {
584 : 925574485 : rtx turn_into_use = NULL_RTX;
585 : :
586 : : /* Always delete no-op moves. */
587 : 925574485 : if (noop_move_p (insn)
588 : : /* Unless the no-op move can throw and we are not allowed
589 : : to alter cfg. */
590 : 925574485 : && (!cfun->can_throw_non_call_exceptions
591 : 2990 : || (cfun->can_delete_dead_exceptions && can_alter_cfg)
592 : 2990 : || insn_nothrow_p (insn)))
593 : : {
594 : 9726 : if (RTX_FRAME_RELATED_P (insn))
595 : 0 : turn_into_use
596 : 0 : = find_reg_note (insn, REG_CFA_RESTORE, NULL);
597 : 0 : if (turn_into_use && REG_P (XEXP (turn_into_use, 0)))
598 : 3245237 : turn_into_use = XEXP (turn_into_use, 0);
599 : : else
600 : : turn_into_use = NULL_RTX;
601 : : }
602 : :
603 : : /* Otherwise rely only on the DCE algorithm. */
604 : 925564759 : else if (marked_insn_p (insn))
605 : 922329248 : continue;
606 : :
607 : : /* Beware that reaching a dbg counter limit here can result
608 : : in miscompiled file. This occurs when a group of insns
609 : : must be deleted together, typically because the kept insn
610 : : depends on the output from the deleted insn. Deleting
611 : : this insns in reverse order (both at the bb level and
612 : : when looking at the blocks) minimizes this, but does not
613 : : eliminate it, since it is possible for the using insn to
614 : : be top of a block and the producer to be at the bottom of
615 : : the block. However, in most cases this will only result
616 : : in an uninitialized use of an insn that is dead anyway.
617 : :
618 : : However, there is one rare case that will cause a
619 : : miscompile: deletion of non-looping pure and constant
620 : : calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
621 : : In this case it is possible to remove the call, but leave
622 : : the argument pushes to the stack. Because of the changes
623 : : to the stack pointer, this will almost always lead to a
624 : : miscompile. */
625 : 3245237 : if (!dbg_cnt (dce))
626 : 0 : continue;
627 : :
628 : 3245237 : if (dump_file)
629 : 77 : fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
630 : :
631 : : /* Before we delete the insn we have to remove the REG_EQUAL notes
632 : : for the destination regs in order to avoid dangling notes. */
633 : 3245237 : remove_reg_equal_equiv_notes_for_defs (insn);
634 : :
635 : 3245237 : if (turn_into_use)
636 : : {
637 : : /* Don't remove frame related noop moves if they cary
638 : : REG_CFA_RESTORE note, while we don't need to emit any code,
639 : : we need it to emit the CFI restore note. */
640 : 0 : PATTERN (insn)
641 : 0 : = gen_rtx_USE (GET_MODE (turn_into_use), turn_into_use);
642 : 0 : INSN_CODE (insn) = -1;
643 : 0 : df_insn_rescan (insn);
644 : : }
645 : : else
646 : : /* Now delete the insn. */
647 : 3245237 : must_clean |= delete_insn_and_edges (insn);
648 : : }
649 : :
650 : : /* Deleted a pure or const call. */
651 : 10549086 : if (must_clean)
652 : : {
653 : 4 : gcc_assert (can_alter_cfg);
654 : 4 : delete_unreachable_blocks ();
655 : 4 : free_dominance_info (CDI_DOMINATORS);
656 : : }
657 : 10549086 : }
658 : :
659 : :
660 : : /* Go through the instructions and mark those whose necessity is not
661 : : dependent on inter-instruction information. Make sure all other
662 : : instructions are not marked. */
663 : :
664 : : static void
665 : 10549086 : prescan_insns_for_dce (bool fast)
666 : : {
667 : 10549086 : basic_block bb;
668 : 10549086 : rtx_insn *insn, *prev;
669 : 10549086 : bitmap arg_stores = NULL;
670 : :
671 : 10549086 : if (dump_file)
672 : 370 : fprintf (dump_file, "Finding needed instructions:\n");
673 : :
674 : 10549086 : if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS)
675 : 140417 : arg_stores = BITMAP_ALLOC (NULL);
676 : :
677 : 181527817 : FOR_EACH_BB_FN (bb, cfun)
678 : : {
679 : 4317298184 : FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)
680 : 1987670361 : if (NONDEBUG_INSN_P (insn))
681 : : {
682 : : /* Don't mark argument stores now. They will be marked
683 : : if needed when the associated CALL is marked. */
684 : 925574485 : if (arg_stores && bitmap_bit_p (arg_stores, INSN_UID (insn)))
685 : 138 : continue;
686 : 925574347 : if (deletable_insn_p (insn, fast, arg_stores))
687 : 719853450 : mark_nonreg_stores (insn, fast);
688 : : else
689 : 205720897 : mark_insn (insn, fast);
690 : : }
691 : : /* find_call_stack_args only looks at argument stores in the
692 : : same bb. */
693 : 170978731 : if (arg_stores)
694 : 171125 : bitmap_clear (arg_stores);
695 : : }
696 : :
697 : 10549086 : if (arg_stores)
698 : 140417 : BITMAP_FREE (arg_stores);
699 : :
700 : 10549086 : if (dump_file)
701 : 370 : fprintf (dump_file, "Finished finding needed instructions:\n");
702 : 10549086 : }
703 : :
704 : :
705 : : /* UD-based DSE routines. */
706 : :
707 : : /* Mark instructions that define artificially-used registers, such as
708 : : the frame pointer and the stack pointer. */
709 : :
710 : : static void
711 : 927784 : mark_artificial_uses (void)
712 : : {
713 : 927784 : basic_block bb;
714 : 927784 : struct df_link *defs;
715 : 927784 : df_ref use;
716 : :
717 : 11895488 : FOR_ALL_BB_FN (bb, cfun)
718 : 61732432 : FOR_EACH_ARTIFICIAL_USE (use, bb->index)
719 : 82706096 : for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
720 : 42909072 : if (!DF_REF_IS_ARTIFICIAL (defs->ref))
721 : 5797755 : mark_insn (DF_REF_INSN (defs->ref), false);
722 : 927784 : }
723 : :
724 : :
725 : : /* Mark every instruction that defines a register value that INSN uses. */
726 : :
727 : : static void
728 : 51797607 : mark_reg_dependencies (rtx_insn *insn)
729 : : {
730 : 51797607 : struct df_link *defs;
731 : 51797607 : df_ref use;
732 : :
733 : 51797607 : if (DEBUG_INSN_P (insn))
734 : : return;
735 : :
736 : 117168533 : FOR_EACH_INSN_USE (use, insn)
737 : : {
738 : 65370926 : if (dump_file)
739 : : {
740 : 1238 : fprintf (dump_file, "Processing use of ");
741 : 1238 : print_simple_rtl (dump_file, DF_REF_REG (use));
742 : 1238 : fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
743 : : }
744 : 141334746 : for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
745 : 75963820 : if (! DF_REF_IS_ARTIFICIAL (defs->ref))
746 : 65008115 : mark_insn (DF_REF_INSN (defs->ref), false);
747 : : }
748 : : }
749 : :
750 : :
751 : : /* Initialize global variables for a new DCE pass. */
752 : :
753 : : static void
754 : 10548814 : init_dce (bool fast)
755 : : {
756 : 10548814 : if (!df_in_progress)
757 : : {
758 : 2273017 : if (!fast)
759 : : {
760 : 927784 : df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
761 : 927784 : df_chain_add_problem (DF_UD_CHAIN);
762 : : }
763 : 2273017 : df_analyze ();
764 : : }
765 : :
766 : 10548814 : if (dump_file)
767 : 370 : df_dump (dump_file);
768 : :
769 : 10548814 : if (fast)
770 : : {
771 : 9621030 : bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
772 : 9621030 : bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
773 : 9621030 : can_alter_cfg = false;
774 : : }
775 : : else
776 : 927784 : can_alter_cfg = true;
777 : :
778 : 10548814 : marked = sbitmap_alloc (get_max_uid () + 1);
779 : 10548814 : bitmap_clear (marked);
780 : 10548814 : }
781 : :
782 : :
783 : : /* Free the data allocated by init_dce. */
784 : :
785 : : static void
786 : 10548814 : fini_dce (bool fast)
787 : : {
788 : 10548814 : sbitmap_free (marked);
789 : :
790 : 10548814 : if (fast)
791 : : {
792 : 9621030 : bitmap_obstack_release (&dce_blocks_bitmap_obstack);
793 : 9621030 : bitmap_obstack_release (&dce_tmp_bitmap_obstack);
794 : : }
795 : 10548814 : }
796 : :
797 : :
798 : : /* UD-chain based DCE. */
799 : :
800 : : static unsigned int
801 : 927784 : rest_of_handle_ud_dce (void)
802 : : {
803 : 927784 : rtx_insn *insn;
804 : :
805 : 927784 : init_dce (false);
806 : :
807 : 927784 : prescan_insns_for_dce (false);
808 : 927784 : mark_artificial_uses ();
809 : 53653175 : while (worklist.length () > 0)
810 : : {
811 : 51797607 : insn = worklist.pop ();
812 : 51797607 : mark_reg_dependencies (insn);
813 : : }
814 : 927784 : worklist.release ();
815 : :
816 : 927784 : if (MAY_HAVE_DEBUG_BIND_INSNS)
817 : 466629 : reset_unmarked_insns_debug_uses ();
818 : :
819 : : /* Before any insns are deleted, we must remove the chains since
820 : : they are not bidirectional. */
821 : 927784 : df_remove_problem (df_chain);
822 : 927784 : delete_unmarked_insns ();
823 : :
824 : 927784 : fini_dce (false);
825 : 927784 : return 0;
826 : : }
827 : :
828 : :
829 : : namespace {
830 : :
831 : : const pass_data pass_data_ud_rtl_dce =
832 : : {
833 : : RTL_PASS, /* type */
834 : : "ud_dce", /* name */
835 : : OPTGROUP_NONE, /* optinfo_flags */
836 : : TV_DCE, /* tv_id */
837 : : 0, /* properties_required */
838 : : 0, /* properties_provided */
839 : : 0, /* properties_destroyed */
840 : : 0, /* todo_flags_start */
841 : : TODO_df_finish, /* todo_flags_finish */
842 : : };
843 : :
844 : : class pass_ud_rtl_dce : public rtl_opt_pass
845 : : {
846 : : public:
847 : 280831 : pass_ud_rtl_dce (gcc::context *ctxt)
848 : 561662 : : rtl_opt_pass (pass_data_ud_rtl_dce, ctxt)
849 : : {}
850 : :
851 : : /* opt_pass methods: */
852 : 1427244 : bool gate (function *) final override
853 : : {
854 : 1427244 : return optimize > 1 && flag_dce && dbg_cnt (dce_ud);
855 : : }
856 : :
857 : 927784 : unsigned int execute (function *) final override
858 : : {
859 : 927784 : return rest_of_handle_ud_dce ();
860 : : }
861 : :
862 : : }; // class pass_ud_rtl_dce
863 : :
864 : : } // anon namespace
865 : :
866 : : rtl_opt_pass *
867 : 280831 : make_pass_ud_rtl_dce (gcc::context *ctxt)
868 : : {
869 : 280831 : return new pass_ud_rtl_dce (ctxt);
870 : : }
871 : :
872 : :
873 : : /* -------------------------------------------------------------------------
874 : : Fast DCE functions
875 : : ------------------------------------------------------------------------- */
876 : :
877 : : /* Process basic block BB. Return true if the live_in set has
878 : : changed. REDO_OUT is true if the info at the bottom of the block
879 : : needs to be recalculated before starting. AU is the proper set of
880 : : artificial uses. Track global substitution of uses of dead pseudos
881 : : in debug insns using GLOBAL_DEBUG. */
882 : :
883 : : static bool
884 : 3498153 : word_dce_process_block (basic_block bb, bool redo_out,
885 : : struct dead_debug_global *global_debug)
886 : : {
887 : 3498153 : bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
888 : 3498153 : rtx_insn *insn;
889 : 3498153 : bool block_changed;
890 : 3498153 : struct dead_debug_local debug;
891 : :
892 : 3498153 : if (redo_out)
893 : : {
894 : : /* Need to redo the live_out set of this block if when one of
895 : : the succs of this block has had a change in it live in
896 : : set. */
897 : 6 : edge e;
898 : 6 : edge_iterator ei;
899 : 6 : df_confluence_function_n con_fun_n = df_word_lr->problem->con_fun_n;
900 : 12 : bitmap_clear (DF_WORD_LR_OUT (bb));
901 : 17 : FOR_EACH_EDGE (e, ei, bb->succs)
902 : 11 : (*con_fun_n) (e);
903 : : }
904 : :
905 : 3498153 : if (dump_file)
906 : : {
907 : 0 : fprintf (dump_file, "processing block %d live out = ", bb->index);
908 : 0 : df_print_word_regset (dump_file, DF_WORD_LR_OUT (bb));
909 : : }
910 : :
911 : 6996306 : bitmap_copy (local_live, DF_WORD_LR_OUT (bb));
912 : 3498153 : dead_debug_local_init (&debug, NULL, global_debug);
913 : :
914 : 44305376 : FOR_BB_INSNS_REVERSE (bb, insn)
915 : 40807223 : if (DEBUG_INSN_P (insn))
916 : : {
917 : 13875972 : df_ref use;
918 : 17260324 : FOR_EACH_INSN_USE (use, insn)
919 : 3384352 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER
920 : 5075452 : && known_eq (GET_MODE_SIZE (GET_MODE (DF_REF_REAL_REG (use))),
921 : : 2 * UNITS_PER_WORD)
922 : 158231 : && !bitmap_bit_p (local_live, 2 * DF_REF_REGNO (use))
923 : 3387816 : && !bitmap_bit_p (local_live, 2 * DF_REF_REGNO (use) + 1))
924 : 0 : dead_debug_add (&debug, use, DF_REF_REGNO (use));
925 : : }
926 : 26931251 : else if (INSN_P (insn))
927 : : {
928 : 20378762 : bool any_changed;
929 : :
930 : : /* No matter if the instruction is needed or not, we remove
931 : : any regno in the defs from the live set. */
932 : 20378762 : any_changed = df_word_lr_simulate_defs (insn, local_live);
933 : 20378762 : if (any_changed)
934 : 15262381 : mark_insn (insn, true);
935 : :
936 : : /* On the other hand, we do not allow the dead uses to set
937 : : anything in local_live. */
938 : 20378762 : if (marked_insn_p (insn))
939 : 20369143 : df_word_lr_simulate_uses (insn, local_live);
940 : :
941 : : /* Insert debug temps for dead REGs used in subsequent debug
942 : : insns. We may have to emit a debug temp even if the insn
943 : : was marked, in case the debug use was after the point of
944 : : death. */
945 : 20378762 : if (debug.used && !bitmap_empty_p (debug.used))
946 : : {
947 : 0 : df_ref def;
948 : :
949 : 0 : FOR_EACH_INSN_DEF (def, insn)
950 : 0 : dead_debug_insert_temp (&debug, DF_REF_REGNO (def), insn,
951 : 0 : marked_insn_p (insn)
952 : 0 : && !control_flow_insn_p (insn)
953 : : ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
954 : : : DEBUG_TEMP_BEFORE_WITH_VALUE);
955 : : }
956 : :
957 : 20378762 : if (dump_file)
958 : : {
959 : 0 : fprintf (dump_file, "finished processing insn %d live out = ",
960 : 0 : INSN_UID (insn));
961 : 0 : df_print_word_regset (dump_file, local_live);
962 : : }
963 : : }
964 : :
965 : 6996306 : block_changed = !bitmap_equal_p (local_live, DF_WORD_LR_IN (bb));
966 : 3498153 : if (block_changed)
967 : 10 : bitmap_copy (DF_WORD_LR_IN (bb), local_live);
968 : :
969 : 3498153 : dead_debug_local_finish (&debug, NULL);
970 : 3498153 : BITMAP_FREE (local_live);
971 : 3498153 : return block_changed;
972 : : }
973 : :
974 : :
975 : : /* Process basic block BB. Return true if the live_in set has
976 : : changed. REDO_OUT is true if the info at the bottom of the block
977 : : needs to be recalculated before starting. AU is the proper set of
978 : : artificial uses. Track global substitution of uses of dead pseudos
979 : : in debug insns using GLOBAL_DEBUG. */
980 : :
981 : : static bool
982 : 158368442 : dce_process_block (basic_block bb, bool redo_out, bitmap au,
983 : : struct dead_debug_global *global_debug)
984 : : {
985 : 158368442 : bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
986 : 158368442 : rtx_insn *insn;
987 : 158368442 : bool block_changed;
988 : 158368442 : df_ref def;
989 : 158368442 : struct dead_debug_local debug;
990 : :
991 : 158368442 : if (redo_out)
992 : : {
993 : : /* Need to redo the live_out set of this block if when one of
994 : : the succs of this block has had a change in it live in
995 : : set. */
996 : 80472 : edge e;
997 : 80472 : edge_iterator ei;
998 : 80472 : df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
999 : 160944 : bitmap_clear (DF_LR_OUT (bb));
1000 : 232942 : FOR_EACH_EDGE (e, ei, bb->succs)
1001 : 152470 : (*con_fun_n) (e);
1002 : : }
1003 : :
1004 : 158368442 : if (dump_file)
1005 : : {
1006 : 2747 : fprintf (dump_file, "processing block %d lr out = ", bb->index);
1007 : 5494 : df_print_regset (dump_file, DF_LR_OUT (bb));
1008 : : }
1009 : :
1010 : 316736884 : bitmap_copy (local_live, DF_LR_OUT (bb));
1011 : :
1012 : 158368442 : df_simulate_initialize_backwards (bb, local_live);
1013 : 158368442 : dead_debug_local_init (&debug, NULL, global_debug);
1014 : :
1015 : 1998809299 : FOR_BB_INSNS_REVERSE (bb, insn)
1016 : 1840440857 : if (DEBUG_INSN_P (insn))
1017 : : {
1018 : 700388274 : df_ref use;
1019 : 852647232 : FOR_EACH_INSN_USE (use, insn)
1020 : 152258958 : if (!bitmap_bit_p (local_live, DF_REF_REGNO (use))
1021 : 152258958 : && !bitmap_bit_p (au, DF_REF_REGNO (use)))
1022 : 301570 : dead_debug_add (&debug, use, DF_REF_REGNO (use));
1023 : : }
1024 : 1140052583 : else if (INSN_P (insn))
1025 : : {
1026 : 853383069 : bool needed = marked_insn_p (insn);
1027 : :
1028 : : /* The insn is needed if there is someone who uses the output. */
1029 : 853383069 : if (!needed)
1030 : 663000359 : FOR_EACH_INSN_DEF (def, insn)
1031 : 659789500 : if (bitmap_bit_p (local_live, DF_REF_REGNO (def))
1032 : 659789500 : || bitmap_bit_p (au, DF_REF_REGNO (def)))
1033 : : {
1034 : 534199956 : needed = true;
1035 : 534199956 : mark_insn (insn, true);
1036 : 534199956 : break;
1037 : : }
1038 : :
1039 : : /* No matter if the instruction is needed or not, we remove
1040 : : any regno in the defs from the live set. */
1041 : 853383069 : df_simulate_defs (insn, local_live);
1042 : :
1043 : : /* On the other hand, we do not allow the dead uses to set
1044 : : anything in local_live. */
1045 : 853383069 : if (needed)
1046 : 850172210 : df_simulate_uses (insn, local_live);
1047 : :
1048 : : /* Insert debug temps for dead REGs used in subsequent debug
1049 : : insns. We may have to emit a debug temp even if the insn
1050 : : was marked, in case the debug use was after the point of
1051 : : death. */
1052 : 853383069 : if (debug.used && !bitmap_empty_p (debug.used))
1053 : 95633633 : FOR_EACH_INSN_DEF (def, insn)
1054 : 159805360 : dead_debug_insert_temp (&debug, DF_REF_REGNO (def), insn,
1055 : 79730555 : needed && !control_flow_insn_p (insn)
1056 : : ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
1057 : : : DEBUG_TEMP_BEFORE_WITH_VALUE);
1058 : : }
1059 : :
1060 : 158368442 : dead_debug_local_finish (&debug, NULL);
1061 : 158368442 : df_simulate_finalize_backwards (bb, local_live);
1062 : :
1063 : 316736884 : block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
1064 : 158368442 : if (block_changed)
1065 : 160778 : bitmap_copy (DF_LR_IN (bb), local_live);
1066 : :
1067 : 158368442 : BITMAP_FREE (local_live);
1068 : 158368442 : return block_changed;
1069 : : }
1070 : :
1071 : :
1072 : : /* Perform fast DCE once initialization is done. If WORD_LEVEL is
1073 : : true, use the word level dce, otherwise do it at the pseudo
1074 : : level. */
1075 : :
1076 : : static void
1077 : 9621030 : fast_dce (bool word_level)
1078 : : {
1079 : 9621030 : int *postorder = df_get_postorder (DF_BACKWARD);
1080 : 9621030 : int n_blocks = df_get_n_blocks (DF_BACKWARD);
1081 : : /* The set of blocks that have been seen on this iteration. */
1082 : 9621030 : bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
1083 : : /* The set of blocks that need to have the out vectors reset because
1084 : : the in of one of their successors has changed. */
1085 : 9621030 : bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
1086 : 9621030 : bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
1087 : 9621030 : bool global_changed = true;
1088 : :
1089 : : /* These regs are considered always live so if they end up dying
1090 : : because of some def, we need to bring the back again. Calling
1091 : : df_simulate_fixup_sets has the disadvantage of calling
1092 : : bb_has_eh_pred once per insn, so we cache the information
1093 : : here. */
1094 : 9621030 : bitmap au = &df->regular_block_artificial_uses;
1095 : 9621030 : bitmap au_eh = &df->eh_block_artificial_uses;
1096 : 9621030 : int i;
1097 : 9621030 : struct dead_debug_global global_debug;
1098 : :
1099 : 9621030 : prescan_insns_for_dce (true);
1100 : :
1101 : 200305731 : for (i = 0; i < n_blocks; i++)
1102 : 181063671 : bitmap_set_bit (all_blocks, postorder[i]);
1103 : :
1104 : 9621030 : dead_debug_global_init (&global_debug, NULL);
1105 : :
1106 : 9621030 : while (global_changed)
1107 : : {
1108 : : global_changed = false;
1109 : :
1110 : 190730501 : for (i = 0; i < n_blocks; i++)
1111 : : {
1112 : 181109199 : int index = postorder[i];
1113 : 181109199 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
1114 : 181109199 : bool local_changed;
1115 : :
1116 : 181109199 : if (index < NUM_FIXED_BLOCKS)
1117 : : {
1118 : 19242604 : bitmap_set_bit (processed, index);
1119 : 19242604 : continue;
1120 : : }
1121 : :
1122 : 161866595 : if (word_level)
1123 : 3498153 : local_changed
1124 : 3498153 : = word_dce_process_block (bb, bitmap_bit_p (redo_out, index),
1125 : : &global_debug);
1126 : : else
1127 : 158368442 : local_changed
1128 : 313418152 : = dce_process_block (bb, bitmap_bit_p (redo_out, index),
1129 : 158368442 : bb_has_eh_pred (bb) ? au_eh : au,
1130 : : &global_debug);
1131 : 161866595 : bitmap_set_bit (processed, index);
1132 : :
1133 : 161866595 : if (local_changed)
1134 : : {
1135 : 80394 : edge e;
1136 : 80394 : edge_iterator ei;
1137 : 170997 : FOR_EACH_EDGE (e, ei, bb->preds)
1138 : 90603 : if (bitmap_bit_p (processed, e->src->index))
1139 : : /* Be tricky about when we need to iterate the
1140 : : analysis. We only have redo the analysis if the
1141 : : bitmaps change at the top of a block that is the
1142 : : entry to a loop. */
1143 : : global_changed = true;
1144 : : else
1145 : 90187 : bitmap_set_bit (redo_out, e->src->index);
1146 : : }
1147 : : }
1148 : :
1149 : 9621302 : if (global_changed)
1150 : : {
1151 : : /* Turn off the RUN_DCE flag to prevent recursive calls to
1152 : : dce. */
1153 : 272 : int old_flag = df_clear_flags (DF_LR_RUN_DCE);
1154 : :
1155 : : /* So something was deleted that requires a redo. Do it on
1156 : : the cheap. */
1157 : 272 : delete_unmarked_insns ();
1158 : 272 : bitmap_clear (marked);
1159 : 272 : bitmap_clear (processed);
1160 : 272 : bitmap_clear (redo_out);
1161 : :
1162 : : /* We do not need to rescan any instructions. We only need
1163 : : to redo the dataflow equations for the blocks that had a
1164 : : change at the top of the block. Then we need to redo the
1165 : : iteration. */
1166 : 272 : if (word_level)
1167 : 0 : df_analyze_problem (df_word_lr, all_blocks, postorder, n_blocks);
1168 : : else
1169 : 272 : df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
1170 : :
1171 : 272 : if (old_flag & DF_LR_RUN_DCE)
1172 : 270 : df_set_flags (DF_LR_RUN_DCE);
1173 : :
1174 : 272 : prescan_insns_for_dce (true);
1175 : : }
1176 : : }
1177 : :
1178 : 9621030 : dead_debug_global_finish (&global_debug, NULL);
1179 : :
1180 : 9621030 : delete_unmarked_insns ();
1181 : :
1182 : 9621030 : BITMAP_FREE (processed);
1183 : 9621030 : BITMAP_FREE (redo_out);
1184 : 9621030 : BITMAP_FREE (all_blocks);
1185 : :
1186 : : /* Both forms of DCE should make further DCE unnecessary. */
1187 : 9621030 : df_lr_dce->solutions_dirty = false;
1188 : 9621030 : }
1189 : :
1190 : :
1191 : : /* Fast register level DCE. */
1192 : :
1193 : : static unsigned int
1194 : 9478317 : rest_of_handle_fast_dce (void)
1195 : : {
1196 : 9478317 : init_dce (true);
1197 : 9478317 : fast_dce (false);
1198 : 9478317 : fini_dce (true);
1199 : 9478317 : return 0;
1200 : : }
1201 : :
1202 : :
1203 : : /* Fast byte level DCE. */
1204 : :
1205 : : void
1206 : 142726 : run_word_dce (void)
1207 : : {
1208 : 142726 : int old_flags;
1209 : :
1210 : 142726 : if (!flag_dce)
1211 : : return;
1212 : :
1213 : 142713 : timevar_push (TV_DCE);
1214 : 142713 : old_flags = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
1215 : 142713 : df_word_lr_add_problem ();
1216 : 142713 : init_dce (true);
1217 : 142713 : fast_dce (true);
1218 : 142713 : fini_dce (true);
1219 : 142713 : df_set_flags (old_flags);
1220 : 142713 : timevar_pop (TV_DCE);
1221 : : }
1222 : :
1223 : :
1224 : : /* This is an internal call that is used by the df live register
1225 : : problem to run fast dce as a side effect of creating the live
1226 : : information. The stack is organized so that the lr problem is run,
1227 : : this pass is run, which updates the live info and the df scanning
1228 : : info, and then returns to allow the rest of the problems to be run.
1229 : :
1230 : : This can be called by elsewhere but it will not update the bit
1231 : : vectors for any other problems than LR. */
1232 : :
1233 : : void
1234 : 8277000 : run_fast_df_dce (void)
1235 : : {
1236 : 8277000 : if (flag_dce)
1237 : : {
1238 : : /* If dce is able to delete something, it has to happen
1239 : : immediately. Otherwise there will be problems handling the
1240 : : eq_notes. */
1241 : 8275797 : int old_flags =
1242 : 8275797 : df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
1243 : :
1244 : 8275797 : df_in_progress = true;
1245 : 8275797 : rest_of_handle_fast_dce ();
1246 : 8275797 : df_in_progress = false;
1247 : :
1248 : 8275797 : df_set_flags (old_flags);
1249 : : }
1250 : 8277000 : }
1251 : :
1252 : :
1253 : : /* Run a fast DCE pass. */
1254 : :
1255 : : void
1256 : 199649 : run_fast_dce (void)
1257 : : {
1258 : 199649 : if (flag_dce)
1259 : 199624 : rest_of_handle_fast_dce ();
1260 : 199649 : }
1261 : :
1262 : :
1263 : : namespace {
1264 : :
1265 : : const pass_data pass_data_fast_rtl_dce =
1266 : : {
1267 : : RTL_PASS, /* type */
1268 : : "rtl_dce", /* name */
1269 : : OPTGROUP_NONE, /* optinfo_flags */
1270 : : TV_DCE, /* tv_id */
1271 : : 0, /* properties_required */
1272 : : 0, /* properties_provided */
1273 : : 0, /* properties_destroyed */
1274 : : 0, /* todo_flags_start */
1275 : : TODO_df_finish, /* todo_flags_finish */
1276 : : };
1277 : :
1278 : : class pass_fast_rtl_dce : public rtl_opt_pass
1279 : : {
1280 : : public:
1281 : 280831 : pass_fast_rtl_dce (gcc::context *ctxt)
1282 : 561662 : : rtl_opt_pass (pass_data_fast_rtl_dce, ctxt)
1283 : : {}
1284 : :
1285 : : /* opt_pass methods: */
1286 : 1427244 : bool gate (function *) final override
1287 : : {
1288 : 1427244 : return optimize > 0 && flag_dce && dbg_cnt (dce_fast);
1289 : : }
1290 : :
1291 : 1002896 : unsigned int execute (function *) final override
1292 : : {
1293 : 1002896 : return rest_of_handle_fast_dce ();
1294 : : }
1295 : :
1296 : : }; // class pass_fast_rtl_dce
1297 : :
1298 : : } // anon namespace
1299 : :
1300 : : rtl_opt_pass *
1301 : 280831 : make_pass_fast_rtl_dce (gcc::context *ctxt)
1302 : : {
1303 : 280831 : return new pass_fast_rtl_dce (ctxt);
1304 : : }
|