1 /* Dead-code elimination pass for the GNU compiler.
2 Copyright (C) 2000, 2001 Free Software Foundation, Inc.
3 Written by Jeffrey D. Oldham <oldham@codesourcery.com>.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 2, or (at your option) any
12 GNU CC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* Dead-code elimination is the removal of instructions which have no
23 impact on the program's output. "Dead instructions" have no impact
24 on the program's output, while "necessary instructions" may have
27 The algorithm consists of three phases:
28 1) marking as necessary all instructions known to be necessary,
29 e.g., writing a value to memory,
30 2) propagating necessary instructions, e.g., the instructions
31 giving values to operands in necessary instructions, and
32 3) removing dead instructions (except replacing dead conditionals
33 with unconditional jumps).
36 The last step can require adding labels, deleting insns, and
37 modifying basic block structures. Some conditional jumps may be
38 converted to unconditional jumps so the control-flow graph may be
41 Edges from some infinite loops to the exit block can be added to
42 the control-flow graph, but will be removed after this pass is
46 We decided to not simultaneously perform jump optimization and dead
47 loop removal during dead-code elimination. Thus, all jump
48 instructions originally present remain after dead-code elimination
49 but 1) unnecessary conditional jump instructions are changed to
50 unconditional jump instructions and 2) all unconditional jump
54 1) SSA has been performed.
55 2) The basic block and control-flow graph structures are accurate.
56 3) The flow graph permits constructing an edge_list.
57 4) note rtxes should be saved.
60 When replacing unnecessary conditional jumps with unconditional
61 jumps, the control-flow graph is not updated. It should be.
64 Building an Optimizing Compiler
66 Butterworth-Heinemann, 1998
74 #include "hard-reg-set.h"
75 #include "basic-block.h"
77 #include "insn-config.h"
82 /* A map from blocks to the edges on which they are control dependent. */
84 /* An dynamically allocated array. The Nth element corresponds to
85 the block with index N + 2. The Ith bit in the bitmap is set if
86 that block is dependent on the Ith edge. */
88 /* The number of elements in the array. */
90 } control_dependent_block_to_edge_map_s
, *control_dependent_block_to_edge_map
;
92 /* Local function prototypes. */
93 static control_dependent_block_to_edge_map control_dependent_block_to_edge_map_create
94 PARAMS((size_t num_basic_blocks
));
95 static void set_control_dependent_block_to_edge_map_bit
96 PARAMS ((control_dependent_block_to_edge_map c
, basic_block bb
,
98 static void control_dependent_block_to_edge_map_free
99 PARAMS ((control_dependent_block_to_edge_map c
));
100 static void find_all_control_dependences
101 PARAMS ((struct edge_list
*el
, int *pdom
,
102 control_dependent_block_to_edge_map cdbte
));
103 static void find_control_dependence
104 PARAMS ((struct edge_list
*el
, int edge_index
, int *pdom
,
105 control_dependent_block_to_edge_map cdbte
));
106 static basic_block find_pdom
107 PARAMS ((int *pdom
, basic_block block
));
108 static int inherently_necessary_register_1
109 PARAMS ((rtx
*current_rtx
, void *data
));
110 static int inherently_necessary_register
111 PARAMS ((rtx current_rtx
));
112 static int find_inherently_necessary
113 PARAMS ((rtx current_rtx
));
114 static int propagate_necessity_through_operand
115 PARAMS ((rtx
*current_rtx
, void *data
));
116 static void note_inherently_necessary_set
117 PARAMS ((rtx
, rtx
, void *));
119 /* Unnecessary insns are indicated using insns' in_struct bit. */
121 /* Indicate INSN is dead-code; returns nothing. */
122 #define KILL_INSN(INSN) INSN_DEAD_CODE_P(INSN) = 1
123 /* Indicate INSN is necessary, i.e., not dead-code; returns nothing. */
124 #define RESURRECT_INSN(INSN) INSN_DEAD_CODE_P(INSN) = 0
125 /* Return nonzero if INSN is unnecessary. */
126 #define UNNECESSARY_P(INSN) INSN_DEAD_CODE_P(INSN)
127 static void mark_all_insn_unnecessary
129 /* Execute CODE with free variable INSN for all unnecessary insns in
130 an unspecified order, producing no output. */
131 #define EXECUTE_IF_UNNECESSARY(INSN, CODE) \
135 for (INSN = get_insns (); INSN != NULL_RTX; INSN = NEXT_INSN (INSN)) \
136 if (INSN_DEAD_CODE_P (INSN)) { \
140 /* Find the label beginning block BB. */
141 static rtx find_block_label
142 PARAMS ((basic_block bb
));
143 /* Remove INSN, updating its basic block structure. */
144 static void delete_insn_bb
147 /* Recording which blocks are control dependent on which edges. We
148 expect each block to be control dependent on very few edges so we
149 use a bitmap for each block recording its edges. An array holds
150 the bitmap. Its position 0 entry holds the bitmap for block
151 INVALID_BLOCK+1 so that all blocks, including the entry and exit
152 blocks can participate in the data structure. */
154 /* Create a control_dependent_block_to_edge_map, given the number
155 NUM_BASIC_BLOCKS of non-entry, non-exit basic blocks, e.g.,
156 n_basic_blocks. This memory must be released using
157 control_dependent_block_to_edge_map_free (). */
159 static control_dependent_block_to_edge_map
160 control_dependent_block_to_edge_map_create (num_basic_blocks
)
161 size_t num_basic_blocks
;
164 control_dependent_block_to_edge_map c
165 = xmalloc (sizeof (control_dependent_block_to_edge_map_s
));
166 c
->length
= num_basic_blocks
- (INVALID_BLOCK
+1);
167 c
->data
= xmalloc ((size_t) c
->length
*sizeof (bitmap
));
168 for (i
= 0; i
< c
->length
; ++i
)
169 c
->data
[i
] = BITMAP_XMALLOC ();
174 /* Indicate block BB is control dependent on an edge with index
175 EDGE_INDEX in the mapping C of blocks to edges on which they are
176 control-dependent. */
179 set_control_dependent_block_to_edge_map_bit (c
, bb
, edge_index
)
180 control_dependent_block_to_edge_map c
;
184 if (bb
->index
- (INVALID_BLOCK
+1) >= c
->length
)
187 bitmap_set_bit (c
->data
[bb
->index
- (INVALID_BLOCK
+1)],
191 /* Execute CODE for each edge (given number EDGE_NUMBER within the
192 CODE) for which the block containing INSN is control dependent,
193 returning no output. CDBTE is the mapping of blocks to edges on
194 which they are control-dependent. */
196 #define EXECUTE_IF_CONTROL_DEPENDENT(CDBTE, INSN, EDGE_NUMBER, CODE) \
197 EXECUTE_IF_SET_IN_BITMAP \
198 (CDBTE->data[BLOCK_NUM (INSN) - (INVALID_BLOCK+1)], 0, \
201 /* Destroy a control_dependent_block_to_edge_map C. */
204 control_dependent_block_to_edge_map_free (c
)
205 control_dependent_block_to_edge_map c
;
208 for (i
= 0; i
< c
->length
; ++i
)
209 BITMAP_XFREE (c
->data
[i
]);
213 /* Record all blocks' control dependences on all edges in the edge
214 list EL, ala Morgan, Section 3.6. The mapping PDOM of blocks to
215 their postdominators are used, and results are stored in CDBTE,
216 which should be empty. */
219 find_all_control_dependences (el
, pdom
, cdbte
)
220 struct edge_list
*el
;
222 control_dependent_block_to_edge_map cdbte
;
226 for (i
= 0; i
< NUM_EDGES (el
); ++i
)
227 find_control_dependence (el
, i
, pdom
, cdbte
);
230 /* Determine all blocks' control dependences on the given edge with
231 edge_list EL index EDGE_INDEX, ala Morgan, Section 3.6. The
232 mapping PDOM of blocks to their postdominators are used, and
233 results are stored in CDBTE, which is assumed to be initialized
234 with zeros in each (block b', edge) position. */
237 find_control_dependence (el
, edge_index
, pdom
, cdbte
)
238 struct edge_list
*el
;
241 control_dependent_block_to_edge_map cdbte
;
243 basic_block current_block
;
244 basic_block ending_block
;
246 if (INDEX_EDGE_PRED_BB (el
, edge_index
) == EXIT_BLOCK_PTR
)
249 (INDEX_EDGE_PRED_BB (el
, edge_index
) == ENTRY_BLOCK_PTR
)
251 : find_pdom (pdom
, INDEX_EDGE_PRED_BB (el
, edge_index
));
253 for (current_block
= INDEX_EDGE_SUCC_BB (el
, edge_index
);
254 current_block
!= ending_block
&& current_block
!= EXIT_BLOCK_PTR
;
255 current_block
= find_pdom (pdom
, current_block
))
257 set_control_dependent_block_to_edge_map_bit (cdbte
,
263 /* Find the immediate postdominator PDOM of the specified basic block
264 BLOCK. This function is necessary because some blocks have
268 find_pdom (pdom
, block
)
274 if (block
->index
== INVALID_BLOCK
)
277 if (block
== ENTRY_BLOCK_PTR
)
278 return BASIC_BLOCK (0);
279 else if (block
== EXIT_BLOCK_PTR
|| pdom
[block
->index
] == EXIT_BLOCK
)
280 return EXIT_BLOCK_PTR
;
282 return BASIC_BLOCK (pdom
[block
->index
]);
285 /* Determine if the given CURRENT_RTX uses a hard register not
286 converted to SSA. Returns nonzero only if it uses such a hard
287 register. DATA is not used.
289 The program counter (PC) is not considered inherently necessary
290 since code should be position-independent and thus not depend on
291 particular PC values. */
294 inherently_necessary_register_1 (current_rtx
, data
)
296 void *data ATTRIBUTE_UNUSED
;
298 rtx x
= *current_rtx
;
302 switch (GET_CODE (x
))
305 /* Do not traverse the rest of the clobber. */
312 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x
)) || x
== pc_rtx
)
323 /* Return nonzero if the insn CURRENT_RTX is inherently necessary. */
326 inherently_necessary_register (current_rtx
)
329 return for_each_rtx (¤t_rtx
,
330 &inherently_necessary_register_1
, NULL
);
334 /* Called via note_stores for each store in an insn. Note whether
335 or not a particular store is inherently necessary. Store a
336 nonzero value in inherently_necessary_p if such a store is found. */
339 note_inherently_necessary_set (dest
, set
, data
)
340 rtx set ATTRIBUTE_UNUSED
;
344 int *inherently_necessary_set_p
= (int *)data
;
346 while (GET_CODE (dest
) == SUBREG
347 || GET_CODE (dest
) == STRICT_LOW_PART
348 || GET_CODE (dest
) == ZERO_EXTRACT
349 || GET_CODE (dest
) == SIGN_EXTRACT
)
350 dest
= XEXP (dest
, 0);
352 if (GET_CODE (dest
) == MEM
353 || GET_CODE (dest
) == UNSPEC
354 || GET_CODE (dest
) == UNSPEC_VOLATILE
)
355 *inherently_necessary_set_p
= 1;
358 /* Mark X as inherently necessary if appropriate. For example,
359 function calls and storing values into memory are inherently
360 necessary. This function is to be used with for_each_rtx ().
361 Return nonzero iff inherently necessary. */
364 find_inherently_necessary (x
)
369 else if (inherently_necessary_register (x
))
372 switch (GET_CODE (x
))
381 return JUMP_TABLE_DATA_P (x
) || computed_jump_p (x
) != 0;
384 int inherently_necessary_set
= 0;
385 note_stores (PATTERN (x
),
386 note_inherently_necessary_set
,
387 &inherently_necessary_set
);
389 /* If we found an inherently necessary set or an asm
390 instruction, then we consider this insn inherently
392 return (inherently_necessary_set
393 || GET_CODE (PATTERN (x
)) == ASM_INPUT
394 || asm_noperands (PATTERN (x
)) >= 0);
397 /* Found an impossible insn type. */
403 /* Propagate necessity through REG and SUBREG operands of CURRENT_RTX.
404 This function is called with for_each_rtx () on necessary
405 instructions. The DATA must be a varray of unprocessed
409 propagate_necessity_through_operand (current_rtx
, data
)
413 rtx x
= *current_rtx
;
414 varray_type
*unprocessed_instructions
= (varray_type
*) data
;
418 switch ( GET_CODE (x
))
421 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x
)))
423 rtx insn
= VARRAY_RTX (ssa_definition
, REGNO (x
));
424 if (insn
!= NULL_RTX
&& UNNECESSARY_P (insn
))
426 RESURRECT_INSN (insn
);
427 VARRAY_PUSH_RTX (*unprocessed_instructions
, insn
);
437 /* Indicate all insns initially assumed to be unnecessary. */
440 mark_all_insn_unnecessary ()
443 for (insn
= get_insns (); insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
447 /* Find the label beginning block BB, adding one if necessary. */
450 find_block_label (bb
)
458 rtx new_label
= emit_label_before (gen_label_rtx (), insn
);
459 if (insn
== bb
->head
)
460 bb
->head
= new_label
;
465 /* Remove INSN, updating its basic block structure. */
468 delete_insn_bb (insn
)
475 /* Do not actually delete anything that is not an INSN.
477 We can get here because we only consider INSNs as
478 potentially necessary. We leave it to later passes
479 to remove unnecessary notes, unused labels, etc. */
483 bb
= BLOCK_FOR_INSN (insn
);
486 if (bb
->head
== bb
->end
)
488 /* Delete the insn by converting it to a note. */
489 PUT_CODE (insn
, NOTE
);
490 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
493 else if (insn
== bb
->head
)
494 bb
->head
= NEXT_INSN (insn
);
495 else if (insn
== bb
->end
)
496 bb
->end
= PREV_INSN (insn
);
500 /* Perform the dead-code elimination. */
503 ssa_eliminate_dead_code ()
507 /* Necessary instructions with operands to explore. */
508 varray_type unprocessed_instructions
;
509 /* Map element (b,e) is nonzero if the block is control dependent on
510 edge. "cdbte" abbreviates control dependent block to edge. */
511 control_dependent_block_to_edge_map cdbte
;
512 /* Element I is the immediate postdominator of block I. */
514 struct edge_list
*el
;
516 int max_insn_uid
= get_max_uid ();
518 /* Initialize the data structures. */
519 mark_all_insn_unnecessary ();
520 VARRAY_RTX_INIT (unprocessed_instructions
, 64,
521 "unprocessed instructions");
522 cdbte
= control_dependent_block_to_edge_map_create (n_basic_blocks
);
524 /* Prepare for use of BLOCK_NUM (). */
525 connect_infinite_loops_to_exit ();
526 /* Be careful not to clear the added edges. */
527 compute_bb_for_insn (max_insn_uid
);
529 /* Compute control dependence. */
530 pdom
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
531 for (i
= 0; i
< n_basic_blocks
; ++i
)
532 pdom
[i
] = INVALID_BLOCK
;
533 calculate_dominance_info (pdom
, NULL
, CDI_POST_DOMINATORS
);
534 /* Assume there is a path from each node to the exit block. */
535 for (i
= 0; i
< n_basic_blocks
; ++i
)
536 if (pdom
[i
] == INVALID_BLOCK
)
537 pdom
[i
] = EXIT_BLOCK
;
538 el
= create_edge_list();
539 find_all_control_dependences (el
, pdom
, cdbte
);
541 /* Find inherently necessary instructions. */
542 for (insn
= get_insns (); insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
543 if (find_inherently_necessary (insn
))
545 RESURRECT_INSN (insn
);
546 VARRAY_PUSH_RTX (unprocessed_instructions
, insn
);
549 /* Propagate necessity using the operands of necessary instructions. */
550 while (VARRAY_ACTIVE_SIZE (unprocessed_instructions
) > 0)
552 rtx current_instruction
;
555 current_instruction
= VARRAY_TOP_RTX (unprocessed_instructions
);
556 VARRAY_POP (unprocessed_instructions
);
558 /* Make corresponding control dependent edges necessary. */
559 /* Assume the only JUMP_INSN is the block's last insn. It appears
560 that the last instruction of the program need not be a
563 if (INSN_P (current_instruction
)
564 && !JUMP_TABLE_DATA_P (current_instruction
))
566 /* Notes and labels contain no interesting operands. */
567 EXECUTE_IF_CONTROL_DEPENDENT
568 (cdbte
, current_instruction
, edge_number
,
570 rtx jump_insn
= (INDEX_EDGE_PRED_BB (el
, edge_number
))->end
;
571 if (GET_CODE (jump_insn
) == JUMP_INSN
572 && UNNECESSARY_P (jump_insn
))
574 RESURRECT_INSN (jump_insn
);
575 VARRAY_PUSH_RTX (unprocessed_instructions
, jump_insn
);
579 /* Propagate through the operands. */
580 for_each_rtx (¤t_instruction
,
581 &propagate_necessity_through_operand
,
582 (PTR
) &unprocessed_instructions
);
584 /* PHI nodes are somewhat special in that each PHI alternative
585 has data and control dependencies. The data dependencies
586 are handled via propagate_necessity_through_operand. We
587 handle the control dependency here.
589 We consider the control dependent edges leading to the
590 predecessor block associated with each PHI alternative
592 if (PHI_NODE_P (current_instruction
))
594 rtvec phi_vec
= XVEC (SET_SRC (PATTERN (current_instruction
)), 0);
595 int num_elem
= GET_NUM_ELEM (phi_vec
);
598 for (v
= num_elem
- 2; v
>= 0; v
-= 2)
602 bb
= BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)));
603 EXECUTE_IF_CONTROL_DEPENDENT
604 (cdbte
, bb
->end
, edge_number
,
608 jump_insn
= (INDEX_EDGE_PRED_BB (el
, edge_number
))->end
;
609 if (((GET_CODE (jump_insn
) == JUMP_INSN
))
610 && UNNECESSARY_P (jump_insn
))
612 RESURRECT_INSN (jump_insn
);
613 VARRAY_PUSH_RTX (unprocessed_instructions
, jump_insn
);
622 /* Remove the unnecessary instructions. */
623 EXECUTE_IF_UNNECESSARY (insn
,
625 if (any_condjump_p (insn
))
627 basic_block bb
= BLOCK_FOR_INSN (insn
);
628 basic_block pdom_bb
= find_pdom (pdom
, bb
);
632 /* Egad. The immediate post dominator is the exit block. We
633 would like to optimize this conditional jump to jump directly
634 to the exit block. That can be difficult as we may not have
635 a suitable CODE_LABEL that allows us to fall unmolested into
638 So, we just delete the conditional branch by turning it into
639 a deleted note. That is safe, but just not as optimal as
641 if (pdom_bb
== EXIT_BLOCK_PTR
)
643 /* Since we're going to just delete the branch, we need
644 look at all the edges and remove all those which are not
652 if ((temp
->flags
& EDGE_FALLTHRU
) == 0)
654 /* We've found a non-fallthru edge, find any PHI nodes
655 at the target and clean them up. */
656 if (temp
->dest
!= EXIT_BLOCK_PTR
)
659 = first_insn_after_basic_block_note (temp
->dest
);
661 while (PHI_NODE_P (insn
))
663 remove_phi_alternative (PATTERN (insn
), temp
->src
);
664 insn
= NEXT_INSN (insn
);
672 /* Now "delete" the conditional jump. */
673 PUT_CODE (insn
, NOTE
);
674 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
678 /* We've found a conditional branch that is unnecessary.
680 First, remove all outgoing edges from this block, updating
681 PHI nodes as appropriate. */
689 if (temp
->flags
& EDGE_ABNORMAL
)
692 /* We found an edge that is not executable. First simplify
693 the PHI nodes in the target block. */
694 if (temp
->dest
!= EXIT_BLOCK_PTR
)
696 rtx insn
= first_insn_after_basic_block_note (temp
->dest
);
698 while (PHI_NODE_P (insn
))
700 remove_phi_alternative (PATTERN (insn
), temp
->src
);
701 insn
= NEXT_INSN (insn
);
708 /* Create an edge from this block to the post dominator.
709 What about the PHI nodes at the target? */
710 make_edge (NULL
, bb
, pdom_bb
, 0);
712 /* Third, transform this insn into an unconditional
713 jump to the label for the immediate postdominator. */
714 lbl
= find_block_label (pdom_bb
);
715 SET_SRC (PATTERN (insn
)) = gen_rtx_LABEL_REF (VOIDmode
, lbl
);
716 INSN_CODE (insn
) = -1;
717 JUMP_LABEL (insn
) = lbl
;
720 /* A barrier must follow any unconditional jump. Barriers
721 are not in basic blocks so this must occur after
722 deleting the conditional jump. */
723 emit_barrier_after (insn
);
725 else if (!JUMP_P (insn
))
726 delete_insn_bb (insn
);
729 /* Remove fake edges from the CFG. */
730 remove_fake_edges ();
732 /* Find any blocks with no successors and ensure they are followed
733 by a BARRIER. delete_insn has the nasty habit of deleting barriers
734 when deleting insns. */
735 for (i
= 0; i
< n_basic_blocks
; i
++)
737 basic_block bb
= BASIC_BLOCK (i
);
739 if (bb
->succ
== NULL
)
741 rtx next
= NEXT_INSN (bb
->end
);
743 if (!next
|| GET_CODE (next
) != BARRIER
)
744 emit_barrier_after (bb
->end
);
747 /* Release allocated memory. */
748 for (insn
= get_insns (); insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
749 RESURRECT_INSN (insn
);
750 if (VARRAY_ACTIVE_SIZE (unprocessed_instructions
) != 0)
752 VARRAY_FREE (unprocessed_instructions
);
753 control_dependent_block_to_edge_map_free (cdbte
);