Mercurial > hg > CbC > CbC_gcc

comparison gcc/dce.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* RTL dead code elimination.
2 Copyright (C) 2005, 2006, 2007, 2008, 2009 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 "hashtab.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "tree.h"
27 #include "regs.h"
28 #include "hard-reg-set.h"
29 #include "flags.h"
30 #include "df.h"
31 #include "cselib.h"
32 #include "dce.h"
33 #include "timevar.h"
34 #include "tree-pass.h"
35 #include "dbgcnt.h"
36 #include "tm_p.h"
37
38 DEF_VEC_I(int);
39 DEF_VEC_ALLOC_I(int,heap);
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 if (volatile_refs_p (body))
85 return false;
86
87 if (flag_non_call_exceptions && may_trap_p (body))
88 return false;
89
90 return true;
91 }
92 }
93
94
95 /* Return true if INSN is a normal instruction that can be deleted by
96 the DCE pass. */
97
98 static bool
99 deletable_insn_p (rtx insn, bool fast, bitmap arg_stores)
100 {
101 rtx body, x;
102 int i;
103
104 if (CALL_P (insn)
105 /* We cannot delete calls inside of the recursive dce because
106 this may cause basic blocks to be deleted and this messes up
107 the rest of the stack of optimization passes. */
108 && (!df_in_progress)
109 /* We cannot delete pure or const sibling calls because it is
110 hard to see the result. */
111 && (!SIBLING_CALL_P (insn))
112 /* We can delete dead const or pure calls as long as they do not
113 infinite loop. */
114 && (RTL_CONST_OR_PURE_CALL_P (insn)
115 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))
116 return find_call_stack_args (insn, false, fast, arg_stores);
117
118 if (!NONJUMP_INSN_P (insn))
119 return false;
120
121 body = PATTERN (insn);
122 switch (GET_CODE (body))
123 {
124 case USE:
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 /* Try to find all stack stores of CALL_INSN arguments if
224 ACCUMULATE_OUTGOING_ARGS. If all stack stores have been found
225 and it is therefore safe to eliminate the call, return true,
226 otherwise return false. This function should be first called
227 with DO_MARK false, and only when the CALL_INSN is actually
228 going to be marked called again with DO_MARK true. */
229
230 static bool
231 find_call_stack_args (rtx call_insn, bool do_mark, bool fast,
232 bitmap arg_stores)
233 {
234 rtx p, insn, prev_insn;
235 bool ret;
236 HOST_WIDE_INT min_sp_off, max_sp_off;
237 bitmap sp_bytes;
238
239 gcc_assert (CALL_P (call_insn));
240 if (!ACCUMULATE_OUTGOING_ARGS)
241 return true;
242
243 if (!do_mark)
244 {
245 gcc_assert (arg_stores);
246 bitmap_clear (arg_stores);
247 }
248
249 min_sp_off = INTTYPE_MAXIMUM (HOST_WIDE_INT);
250 max_sp_off = 0;
251
252 /* First determine the minimum and maximum offset from sp for
253 stored arguments. */
254 for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
255 if (GET_CODE (XEXP (p, 0)) == USE
256 && MEM_P (XEXP (XEXP (p, 0), 0)))
257 {
258 rtx mem = XEXP (XEXP (p, 0), 0), addr, size;
259 HOST_WIDE_INT off = 0;
260 size = MEM_SIZE (mem);
261 if (size == NULL_RTX)
262 return false;
263 addr = XEXP (mem, 0);
264 if (GET_CODE (addr) == PLUS
265 && REG_P (XEXP (addr, 0))
266 && CONST_INT_P (XEXP (addr, 1)))
267 {
268 off = INTVAL (XEXP (addr, 1));
269 addr = XEXP (addr, 0);
270 }
271 if (addr != stack_pointer_rtx)
272 {
273 if (!REG_P (addr))
274 return false;
275 /* If not fast, use chains to see if addr wasn't set to
276 sp + offset. */
277 if (!fast)
278 {
279 df_ref *use_rec;
280 struct df_link *defs;
281 rtx set;
282
283 for (use_rec = DF_INSN_USES (call_insn); *use_rec; use_rec++)
284 if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))
285 break;
286
287 if (*use_rec == NULL)
288 return false;
289
290 for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
291 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
292 break;
293
294 if (defs == NULL)
295 return false;
296
297 set = single_set (DF_REF_INSN (defs->ref));
298 if (!set)
299 return false;
300
301 if (GET_CODE (SET_SRC (set)) != PLUS
302 || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
303 || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
304 return false;
305
306 off += INTVAL (XEXP (SET_SRC (set), 1));
307 }
308 else
309 return false;
310 }
311 min_sp_off = MIN (min_sp_off, off);
312 max_sp_off = MAX (max_sp_off, off + INTVAL (size));
313 }
314
315 if (min_sp_off >= max_sp_off)
316 return true;
317 sp_bytes = BITMAP_ALLOC (NULL);
318
319 /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
320 which contain arguments. Checking has been done in the previous
321 loop. */
322 for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
323 if (GET_CODE (XEXP (p, 0)) == USE
324 && MEM_P (XEXP (XEXP (p, 0), 0)))
325 {
326 rtx mem = XEXP (XEXP (p, 0), 0), addr;
327 HOST_WIDE_INT off = 0, byte;
328 addr = XEXP (mem, 0);
329 if (GET_CODE (addr) == PLUS
330 && REG_P (XEXP (addr, 0))
331 && CONST_INT_P (XEXP (addr, 1)))
332 {
333 off = INTVAL (XEXP (addr, 1));
334 addr = XEXP (addr, 0);
335 }
336 if (addr != stack_pointer_rtx)
337 {
338 df_ref *use_rec;
339 struct df_link *defs;
340 rtx set;
341
342 for (use_rec = DF_INSN_USES (call_insn); *use_rec; use_rec++)
343 if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))
344 break;
345
346 for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
347 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
348 break;
349
350 set = single_set (DF_REF_INSN (defs->ref));
351 off += INTVAL (XEXP (SET_SRC (set), 1));
352 }
353 for (byte = off; byte < off + INTVAL (MEM_SIZE (mem)); byte++)
354 {
355 gcc_assert (!bitmap_bit_p (sp_bytes, byte - min_sp_off));
356 bitmap_set_bit (sp_bytes, byte - min_sp_off);
357 }
358 }
359
360 /* Walk backwards, looking for argument stores. The search stops
361 when seeing another call, sp adjustment or memory store other than
362 argument store. */
363 ret = false;
364 for (insn = PREV_INSN (call_insn); insn; insn = prev_insn)
365 {
366 rtx set, mem, addr;
367 HOST_WIDE_INT off, byte;
368
369 if (insn == BB_HEAD (BLOCK_FOR_INSN (call_insn)))
370 prev_insn = NULL_RTX;
371 else
372 prev_insn = PREV_INSN (insn);
373
374 if (CALL_P (insn))
375 break;
376
377 if (!INSN_P (insn))
378 continue;
379
380 set = single_set (insn);
381 if (!set || SET_DEST (set) == stack_pointer_rtx)
382 break;
383
384 if (!MEM_P (SET_DEST (set)))
385 continue;
386
387 mem = SET_DEST (set);
388 addr = XEXP (mem, 0);
389 off = 0;
390 if (GET_CODE (addr) == PLUS
391 && REG_P (XEXP (addr, 0))
392 && CONST_INT_P (XEXP (addr, 1)))
393 {
394 off = INTVAL (XEXP (addr, 1));
395 addr = XEXP (addr, 0);
396 }
397 if (addr != stack_pointer_rtx)
398 {
399 if (!REG_P (addr))
400 break;
401 if (!fast)
402 {
403 df_ref *use_rec;
404 struct df_link *defs;
405 rtx set;
406
407 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
408 if (rtx_equal_p (addr, DF_REF_REG (*use_rec)))
409 break;
410
411 if (*use_rec == NULL)
412 break;
413
414 for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
415 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
416 break;
417
418 if (defs == NULL)
419 break;
420
421 set = single_set (DF_REF_INSN (defs->ref));
422 if (!set)
423 break;
424
425 if (GET_CODE (SET_SRC (set)) != PLUS
426 || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
427 || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
428 break;
429
430 off += INTVAL (XEXP (SET_SRC (set), 1));
431 }
432 else
433 break;
434 }
435
436 if (GET_MODE_SIZE (GET_MODE (mem)) == 0)
437 break;
438
439 for (byte = off; byte < off + GET_MODE_SIZE (GET_MODE (mem)); byte++)
440 {
441 if (byte < min_sp_off
442 || byte >= max_sp_off
443 || !bitmap_bit_p (sp_bytes, byte - min_sp_off))
444 break;
445 bitmap_clear_bit (sp_bytes, byte - min_sp_off);
446 }
447
448 if (!deletable_insn_p (insn, fast, NULL))
449 break;
450
451 if (do_mark)
452 mark_insn (insn, fast);
453 else
454 bitmap_set_bit (arg_stores, INSN_UID (insn));
455
456 if (bitmap_empty_p (sp_bytes))
457 {
458 ret = true;
459 break;
460 }
461 }
462
463 BITMAP_FREE (sp_bytes);
464 if (!ret && arg_stores)
465 bitmap_clear (arg_stores);
466
467 return ret;
468 }
469
470
471 /* Delete all REG_EQUAL notes of the registers INSN writes, to prevent
472 bad dangling REG_EQUAL notes. */
473
474 static void
475 delete_corresponding_reg_eq_notes (rtx insn)
476 {
477 df_ref *def_rec;
478 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
479 {
480 df_ref def = *def_rec;
481 unsigned int regno = DF_REF_REGNO (def);
482 /* This loop is a little tricky. We cannot just go down the
483 chain because it is being modified by the actions in the
484 loop. So we just get the head. We plan to drain the list
485 anyway. */
486 while (DF_REG_EQ_USE_CHAIN (regno))
487 {
488 df_ref eq_use = DF_REG_EQ_USE_CHAIN (regno);
489 rtx noted_insn = DF_REF_INSN (eq_use);
490 rtx note = find_reg_note (noted_insn, REG_EQUAL, NULL_RTX);
491 if (!note)
492 note = find_reg_note (noted_insn, REG_EQUIV, NULL_RTX);
493
494 /* This assert is generally triggered when someone deletes a
495 REG_EQUAL or REG_EQUIV note by hacking the list manually
496 rather than calling remove_note. */
497 gcc_assert (note);
498 remove_note (noted_insn, note);
499 }
500 }
501 }
502
503
504 /* Delete every instruction that hasn't been marked. */
505
506 static void
507 delete_unmarked_insns (void)
508 {
509 basic_block bb;
510 rtx insn, next;
511 bool must_clean = false;
512
513 FOR_EACH_BB_REVERSE (bb)
514 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
515 if (INSN_P (insn))
516 {
517 /* Always delete no-op moves. */
518 if (noop_move_p (insn))
519 ;
520
521 /* Otherwise rely only on the DCE algorithm. */
522 else if (marked_insn_p (insn))
523 continue;
524
525 /* Beware that reaching a dbg counter limit here can result
526 in miscompiled file. This occurs when a group of insns
527 must be deleted together, typically because the kept insn
528 depends on the output from the deleted insn. Deleting
529 this insns in reverse order (both at the bb level and
530 when looking at the blocks) minimizes this, but does not
531 eliminate it, since it is possible for the using insn to
532 be top of a block and the producer to be at the bottom of
533 the block. However, in most cases this will only result
534 in an uninitialized use of an insn that is dead anyway.
535
536 However, there is one rare case that will cause a
537 miscompile: deletion of non-looping pure and constant
538 calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
539 In this case it is possible to remove the call, but leave
540 the argument pushes to the stack. Because of the changes
541 to the stack pointer, this will almost always lead to a
542 miscompile. */
543 if (!dbg_cnt (dce))
544 continue;
545
546 if (dump_file)
547 fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
548
549 /* Before we delete the insn we have to delete REG_EQUAL notes
550 for the destination regs in order to avoid dangling notes. */
551 delete_corresponding_reg_eq_notes (insn);
552
553 /* If a pure or const call is deleted, this may make the cfg
554 have unreachable blocks. We rememeber this and call
555 delete_unreachable_blocks at the end. */
556 if (CALL_P (insn))
557 must_clean = true;
558
559 /* Now delete the insn. */
560 delete_insn_and_edges (insn);
561 }
562
563 /* Deleted a pure or const call. */
564 if (must_clean)
565 delete_unreachable_blocks ();
566 }
567
568
569 /* Go through the instructions and mark those whose necessity is not
570 dependent on inter-instruction information. Make sure all other
571 instructions are not marked. */
572
573 static void
574 prescan_insns_for_dce (bool fast)
575 {
576 basic_block bb;
577 rtx insn, prev;
578 bitmap arg_stores = NULL;
579
580 if (dump_file)
581 fprintf (dump_file, "Finding needed instructions:\n");
582
583 if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS)
584 arg_stores = BITMAP_ALLOC (NULL);
585
586 FOR_EACH_BB (bb)
587 {
588 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)
589 if (INSN_P (insn))
590 {
591 /* Don't mark argument stores now. They will be marked
592 if needed when the associated CALL is marked. */
593 if (arg_stores && bitmap_bit_p (arg_stores, INSN_UID (insn)))
594 continue;
595 if (deletable_insn_p (insn, fast, arg_stores))
596 mark_nonreg_stores (PATTERN (insn), insn, fast);
597 else
598 mark_insn (insn, fast);
599 }
600 /* find_call_stack_args only looks at argument stores in the
601 same bb. */
602 if (arg_stores)
603 bitmap_clear (arg_stores);
604 }
605
606 if (arg_stores)
607 BITMAP_FREE (arg_stores);
608
609 if (dump_file)
610 fprintf (dump_file, "Finished finding needed instructions:\n");
611 }
612
613
614 /* UD-based DSE routines. */
615
616 /* Mark instructions that define artificially-used registers, such as
617 the frame pointer and the stack pointer. */
618
619 static void
620 mark_artificial_uses (void)
621 {
622 basic_block bb;
623 struct df_link *defs;
624 df_ref *use_rec;
625
626 FOR_ALL_BB (bb)
627 {
628 for (use_rec = df_get_artificial_uses (bb->index);
629 *use_rec; use_rec++)
630 for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
631 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
632 mark_insn (DF_REF_INSN (defs->ref), false);
633 }
634 }
635
636
637 /* Mark every instruction that defines a register value that INSN uses. */
638
639 static void
640 mark_reg_dependencies (rtx insn)
641 {
642 struct df_link *defs;
643 df_ref *use_rec;
644
645 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
646 {
647 df_ref use = *use_rec;
648 if (dump_file)
649 {
650 fprintf (dump_file, "Processing use of ");
651 print_simple_rtl (dump_file, DF_REF_REG (use));
652 fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
653 }
654 for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
655 if (! DF_REF_IS_ARTIFICIAL (defs->ref))
656 mark_insn (DF_REF_INSN (defs->ref), false);
657 }
658 }
659
660
661 /* Initialize global variables for a new DCE pass. */
662
663 static void
664 init_dce (bool fast)
665 {
666 if (!df_in_progress)
667 {
668 if (!fast)
669 df_chain_add_problem (DF_UD_CHAIN);
670 df_analyze ();
671 }
672
673 if (dump_file)
674 df_dump (dump_file);
675
676 if (fast)
677 {
678 bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
679 bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
680 }
681
682 marked = sbitmap_alloc (get_max_uid () + 1);
683 sbitmap_zero (marked);
684 }
685
686
687 /* Free the data allocated by init_dce. */
688
689 static void
690 fini_dce (bool fast)
691 {
692 sbitmap_free (marked);
693
694 if (fast)
695 {
696 bitmap_obstack_release (&dce_blocks_bitmap_obstack);
697 bitmap_obstack_release (&dce_tmp_bitmap_obstack);
698 }
699 }
700
701
702 /* UD-chain based DCE. */
703
704 static unsigned int
705 rest_of_handle_ud_dce (void)
706 {
707 rtx insn;
708
709 init_dce (false);
710
711 prescan_insns_for_dce (false);
712 mark_artificial_uses ();
713 while (VEC_length (rtx, worklist) > 0)
714 {
715 insn = VEC_pop (rtx, worklist);
716 mark_reg_dependencies (insn);
717 }
718 VEC_free (rtx, heap, worklist);
719
720 /* Before any insns are deleted, we must remove the chains since
721 they are not bidirectional. */
722 df_remove_problem (df_chain);
723 delete_unmarked_insns ();
724
725 fini_dce (false);
726 return 0;
727 }
728
729
730 static bool
731 gate_ud_dce (void)
732 {
733 return optimize > 1 && flag_dce
734 && dbg_cnt (dce_ud);
735 }
736
737 struct rtl_opt_pass pass_ud_rtl_dce =
738 {
739 {
740 RTL_PASS,
741 "dce", /* name */
742 gate_ud_dce, /* gate */
743 rest_of_handle_ud_dce, /* execute */
744 NULL, /* sub */
745 NULL, /* next */
746 0, /* static_pass_number */
747 TV_DCE, /* tv_id */
748 0, /* properties_required */
749 0, /* properties_provided */
750 0, /* properties_destroyed */
751 0, /* todo_flags_start */
752 TODO_dump_func |
753 TODO_df_finish | TODO_verify_rtl_sharing |
754 TODO_ggc_collect /* todo_flags_finish */
755 }
756 };
757
758
759 /* -------------------------------------------------------------------------
760 Fast DCE functions
761 ------------------------------------------------------------------------- */
762
763 /* Process basic block BB. Return true if the live_in set has
764 changed. REDO_OUT is true if the info at the bottom of the block
765 needs to be recalculated before starting. AU is the proper set of
766 artificial uses. */
767
768 static bool
769 byte_dce_process_block (basic_block bb, bool redo_out, bitmap au)
770 {
771 bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
772 rtx insn;
773 bool block_changed;
774 df_ref *def_rec;
775
776 if (redo_out)
777 {
778 /* Need to redo the live_out set of this block if when one of
779 the succs of this block has had a change in it live in
780 set. */
781 edge e;
782 edge_iterator ei;
783 df_confluence_function_n con_fun_n = df_byte_lr->problem->con_fun_n;
784 bitmap_clear (DF_BYTE_LR_OUT (bb));
785 FOR_EACH_EDGE (e, ei, bb->succs)
786 (*con_fun_n) (e);
787 }
788
789 if (dump_file)
790 {
791 fprintf (dump_file, "processing block %d live out = ", bb->index);
792 df_print_byte_regset (dump_file, DF_BYTE_LR_OUT (bb));
793 }
794
795 bitmap_copy (local_live, DF_BYTE_LR_OUT (bb));
796
797 df_byte_lr_simulate_artificial_refs_at_end (bb, local_live);
798
799 FOR_BB_INSNS_REVERSE (bb, insn)
800 if (INSN_P (insn))
801 {
802 /* The insn is needed if there is someone who uses the output. */
803 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
804 {
805 df_ref def = *def_rec;
806 unsigned int last;
807 unsigned int dregno = DF_REF_REGNO (def);
808 unsigned int start = df_byte_lr_get_regno_start (dregno);
809 unsigned int len = df_byte_lr_get_regno_len (dregno);
810
811 unsigned int sb;
812 unsigned int lb;
813 /* This is one of the only places where DF_MM_MAY should
814 be used for defs. Need to make sure that we are
815 checking for all of the bits that may be used. */
816
817 if (!df_compute_accessed_bytes (def, DF_MM_MAY, &sb, &lb))
818 {
819 start += sb;
820 len = lb - sb;
821 }
822
823 if (bitmap_bit_p (au, dregno))
824 {
825 mark_insn (insn, true);
826 goto quickexit;
827 }
828
829 last = start + len;
830 while (start < last)
831 if (bitmap_bit_p (local_live, start++))
832 {
833 mark_insn (insn, true);
834 goto quickexit;
835 }
836 }
837
838 quickexit:
839
840 /* No matter if the instruction is needed or not, we remove
841 any regno in the defs from the live set. */
842 df_byte_lr_simulate_defs (insn, local_live);
843
844 /* On the other hand, we do not allow the dead uses to set
845 anything in local_live. */
846 if (marked_insn_p (insn))
847 df_byte_lr_simulate_uses (insn, local_live);
848
849 if (dump_file)
850 {
851 fprintf (dump_file, "finished processing insn %d live out = ",
852 INSN_UID (insn));
853 df_print_byte_regset (dump_file, local_live);
854 }
855 }
856
857 df_byte_lr_simulate_artificial_refs_at_top (bb, local_live);
858
859 block_changed = !bitmap_equal_p (local_live, DF_BYTE_LR_IN (bb));
860 if (block_changed)
861 bitmap_copy (DF_BYTE_LR_IN (bb), local_live);
862 BITMAP_FREE (local_live);
863 return block_changed;
864 }
865
866
867 /* Process basic block BB. Return true if the live_in set has
868 changed. REDO_OUT is true if the info at the bottom of the block
869 needs to be recalculated before starting. AU is the proper set of
870 artificial uses. */
871
872 static bool
873 dce_process_block (basic_block bb, bool redo_out, bitmap au)
874 {
875 bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
876 rtx insn;
877 bool block_changed;
878 df_ref *def_rec;
879
880 if (redo_out)
881 {
882 /* Need to redo the live_out set of this block if when one of
883 the succs of this block has had a change in it live in
884 set. */
885 edge e;
886 edge_iterator ei;
887 df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
888 bitmap_clear (DF_LR_OUT (bb));
889 FOR_EACH_EDGE (e, ei, bb->succs)
890 (*con_fun_n) (e);
891 }
892
893 if (dump_file)
894 {
895 fprintf (dump_file, "processing block %d lr out = ", bb->index);
896 df_print_regset (dump_file, DF_LR_OUT (bb));
897 }
898
899 bitmap_copy (local_live, DF_LR_OUT (bb));
900
901 df_simulate_initialize_backwards (bb, local_live);
902
903 FOR_BB_INSNS_REVERSE (bb, insn)
904 if (INSN_P (insn))
905 {
906 bool needed = false;
907
908 /* The insn is needed if there is someone who uses the output. */
909 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
910 if (bitmap_bit_p (local_live, DF_REF_REGNO (*def_rec))
911 || bitmap_bit_p (au, DF_REF_REGNO (*def_rec)))
912 {
913 needed = true;
914 break;
915 }
916
917 if (needed)
918 mark_insn (insn, true);
919
920 /* No matter if the instruction is needed or not, we remove
921 any regno in the defs from the live set. */
922 df_simulate_defs (insn, local_live);
923
924 /* On the other hand, we do not allow the dead uses to set
925 anything in local_live. */
926 if (marked_insn_p (insn))
927 df_simulate_uses (insn, local_live);
928 }
929
930 df_simulate_finalize_backwards (bb, local_live);
931
932 block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
933 if (block_changed)
934 bitmap_copy (DF_LR_IN (bb), local_live);
935
936 BITMAP_FREE (local_live);
937 return block_changed;
938 }
939
940
941 /* Perform fast DCE once initialization is done. If BYTE_LEVEL is
942 true, use the byte level dce, otherwise do it at the pseudo
943 level. */
944
945 static void
946 fast_dce (bool byte_level)
947 {
948 int *postorder = df_get_postorder (DF_BACKWARD);
949 int n_blocks = df_get_n_blocks (DF_BACKWARD);
950 /* The set of blocks that have been seen on this iteration. */
951 bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
952 /* The set of blocks that need to have the out vectors reset because
953 the in of one of their successors has changed. */
954 bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
955 bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
956 bool global_changed = true;
957
958 /* These regs are considered always live so if they end up dying
959 because of some def, we need to bring the back again. Calling
960 df_simulate_fixup_sets has the disadvantage of calling
961 bb_has_eh_pred once per insn, so we cache the information
962 here. */
963 bitmap au = df->regular_block_artificial_uses;
964 bitmap au_eh = df->eh_block_artificial_uses;
965 int i;
966
967 prescan_insns_for_dce (true);
968
969 for (i = 0; i < n_blocks; i++)
970 bitmap_set_bit (all_blocks, postorder[i]);
971
972 while (global_changed)
973 {
974 global_changed = false;
975
976 for (i = 0; i < n_blocks; i++)
977 {
978 int index = postorder[i];
979 basic_block bb = BASIC_BLOCK (index);
980 bool local_changed;
981
982 if (index < NUM_FIXED_BLOCKS)
983 {
984 bitmap_set_bit (processed, index);
985 continue;
986 }
987
988 if (byte_level)
989 local_changed
990 = byte_dce_process_block (bb, bitmap_bit_p (redo_out, index),
991 bb_has_eh_pred (bb) ? au_eh : au);
992 else
993 local_changed
994 = dce_process_block (bb, bitmap_bit_p (redo_out, index),
995 bb_has_eh_pred (bb) ? au_eh : au);
996 bitmap_set_bit (processed, index);
997
998 if (local_changed)
999 {
1000 edge e;
1001 edge_iterator ei;
1002 FOR_EACH_EDGE (e, ei, bb->preds)
1003 if (bitmap_bit_p (processed, e->src->index))
1004 /* Be tricky about when we need to iterate the
1005 analysis. We only have redo the analysis if the
1006 bitmaps change at the top of a block that is the
1007 entry to a loop. */
1008 global_changed = true;
1009 else
1010 bitmap_set_bit (redo_out, e->src->index);
1011 }
1012 }
1013
1014 if (global_changed)
1015 {
1016 /* Turn off the RUN_DCE flag to prevent recursive calls to
1017 dce. */
1018 int old_flag = df_clear_flags (DF_LR_RUN_DCE);
1019
1020 /* So something was deleted that requires a redo. Do it on
1021 the cheap. */
1022 delete_unmarked_insns ();
1023 sbitmap_zero (marked);
1024 bitmap_clear (processed);
1025 bitmap_clear (redo_out);
1026
1027 /* We do not need to rescan any instructions. We only need
1028 to redo the dataflow equations for the blocks that had a
1029 change at the top of the block. Then we need to redo the
1030 iteration. */
1031 if (byte_level)
1032 df_analyze_problem (df_byte_lr, all_blocks, postorder, n_blocks);
1033 else
1034 df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
1035
1036 if (old_flag & DF_LR_RUN_DCE)
1037 df_set_flags (DF_LR_RUN_DCE);
1038
1039 prescan_insns_for_dce (true);
1040 }
1041 }
1042
1043 delete_unmarked_insns ();
1044
1045 BITMAP_FREE (processed);
1046 BITMAP_FREE (redo_out);
1047 BITMAP_FREE (all_blocks);
1048 }
1049
1050
1051 /* Fast register level DCE. */
1052
1053 static unsigned int
1054 rest_of_handle_fast_dce (void)
1055 {
1056 init_dce (true);
1057 fast_dce (false);
1058 fini_dce (true);
1059 return 0;
1060 }
1061
1062
1063 /* Fast byte level DCE. */
1064
1065 static unsigned int
1066 rest_of_handle_fast_byte_dce (void)
1067 {
1068 df_byte_lr_add_problem ();
1069 init_dce (true);
1070 fast_dce (true);
1071 fini_dce (true);
1072 return 0;
1073 }
1074
1075
1076 /* This is an internal call that is used by the df live register
1077 problem to run fast dce as a side effect of creating the live
1078 information. The stack is organized so that the lr problem is run,
1079 this pass is run, which updates the live info and the df scanning
1080 info, and then returns to allow the rest of the problems to be run.
1081
1082 This can be called by elsewhere but it will not update the bit
1083 vectors for any other problems than LR. */
1084
1085 void
1086 run_fast_df_dce (void)
1087 {
1088 if (flag_dce)
1089 {
1090 /* If dce is able to delete something, it has to happen
1091 immediately. Otherwise there will be problems handling the
1092 eq_notes. */
1093 enum df_changeable_flags old_flags
1094 = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
1095
1096 df_in_progress = true;
1097 rest_of_handle_fast_dce ();
1098 df_in_progress = false;
1099
1100 df_set_flags (old_flags);
1101 }
1102 }
1103
1104
1105 /* Run a fast DCE pass. */
1106
1107 void
1108 run_fast_dce (void)
1109 {
1110 if (flag_dce)
1111 rest_of_handle_fast_dce ();
1112 }
1113
1114
1115 static bool
1116 gate_fast_dce (void)
1117 {
1118 return optimize > 0 && flag_dce
1119 && dbg_cnt (dce_fast);
1120 }
1121
1122 struct rtl_opt_pass pass_fast_rtl_dce =
1123 {
1124 {
1125 RTL_PASS,
1126 "dce", /* name */
1127 gate_fast_dce, /* gate */
1128 rest_of_handle_fast_dce, /* execute */
1129 NULL, /* sub */
1130 NULL, /* next */
1131 0, /* static_pass_number */
1132 TV_DCE, /* tv_id */
1133 0, /* properties_required */
1134 0, /* properties_provided */
1135 0, /* properties_destroyed */
1136 0, /* todo_flags_start */
1137 TODO_dump_func |
1138 TODO_df_finish | TODO_verify_rtl_sharing |
1139 TODO_ggc_collect /* todo_flags_finish */
1140 }
1141 };
1142
1143 struct rtl_opt_pass pass_fast_rtl_byte_dce =
1144 {
1145 {
1146 RTL_PASS,
1147 "byte-dce", /* name */
1148 gate_fast_dce, /* gate */
1149 rest_of_handle_fast_byte_dce, /* execute */
1150 NULL, /* sub */
1151 NULL, /* next */
1152 0, /* static_pass_number */
1153 TV_DCE, /* tv_id */
1154 0, /* properties_required */
1155 0, /* properties_provided */
1156 0, /* properties_destroyed */
1157 0, /* todo_flags_start */
1158 TODO_dump_func |
1159 TODO_df_finish | TODO_verify_rtl_sharing |
1160 TODO_ggc_collect /* todo_flags_finish */
1161 }
1162 };