1*c87b03e5Sespie /* Dead-code elimination pass for the GNU compiler.
2*c87b03e5Sespie Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc.
3*c87b03e5Sespie Written by Jeffrey D. Oldham <oldham@codesourcery.com>.
4*c87b03e5Sespie
5*c87b03e5Sespie This file is part of GCC.
6*c87b03e5Sespie
7*c87b03e5Sespie GCC is free software; you can redistribute it and/or modify it under
8*c87b03e5Sespie the terms of the GNU General Public License as published by the Free
9*c87b03e5Sespie Software Foundation; either version 2, or (at your option) any later
10*c87b03e5Sespie version.
11*c87b03e5Sespie
12*c87b03e5Sespie GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13*c87b03e5Sespie WARRANTY; without even the implied warranty of MERCHANTABILITY or
14*c87b03e5Sespie FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15*c87b03e5Sespie for more details.
16*c87b03e5Sespie
17*c87b03e5Sespie You should have received a copy of the GNU General Public License
18*c87b03e5Sespie along with GCC; see the file COPYING. If not, write to the Free
19*c87b03e5Sespie Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20*c87b03e5Sespie 02111-1307, USA. */
21*c87b03e5Sespie
22*c87b03e5Sespie /* Dead-code elimination is the removal of instructions which have no
23*c87b03e5Sespie impact on the program's output. "Dead instructions" have no impact
24*c87b03e5Sespie on the program's output, while "necessary instructions" may have
25*c87b03e5Sespie impact on the output.
26*c87b03e5Sespie
27*c87b03e5Sespie The algorithm consists of three phases:
28*c87b03e5Sespie 1) marking as necessary all instructions known to be necessary,
29*c87b03e5Sespie e.g., writing a value to memory,
30*c87b03e5Sespie 2) propagating necessary instructions, e.g., the instructions
31*c87b03e5Sespie giving values to operands in necessary instructions, and
32*c87b03e5Sespie 3) removing dead instructions (except replacing dead conditionals
33*c87b03e5Sespie with unconditional jumps).
34*c87b03e5Sespie
35*c87b03e5Sespie Side Effects:
36*c87b03e5Sespie The last step can require adding labels, deleting insns, and
37*c87b03e5Sespie modifying basic block structures. Some conditional jumps may be
38*c87b03e5Sespie converted to unconditional jumps so the control-flow graph may be
39*c87b03e5Sespie out-of-date.
40*c87b03e5Sespie
41*c87b03e5Sespie Edges from some infinite loops to the exit block can be added to
42*c87b03e5Sespie the control-flow graph, but will be removed after this pass is
43*c87b03e5Sespie complete.
44*c87b03e5Sespie
45*c87b03e5Sespie It Does Not Perform:
46*c87b03e5Sespie We decided to not simultaneously perform jump optimization and dead
47*c87b03e5Sespie loop removal during dead-code elimination. Thus, all jump
48*c87b03e5Sespie instructions originally present remain after dead-code elimination
49*c87b03e5Sespie but 1) unnecessary conditional jump instructions are changed to
50*c87b03e5Sespie unconditional jump instructions and 2) all unconditional jump
51*c87b03e5Sespie instructions remain.
52*c87b03e5Sespie
53*c87b03e5Sespie Assumptions:
54*c87b03e5Sespie 1) SSA has been performed.
55*c87b03e5Sespie 2) The basic block and control-flow graph structures are accurate.
56*c87b03e5Sespie 3) The flow graph permits constructing an edge_list.
57*c87b03e5Sespie 4) note rtxes should be saved.
58*c87b03e5Sespie
59*c87b03e5Sespie Unfinished:
60*c87b03e5Sespie When replacing unnecessary conditional jumps with unconditional
61*c87b03e5Sespie jumps, the control-flow graph is not updated. It should be.
62*c87b03e5Sespie
63*c87b03e5Sespie References:
64*c87b03e5Sespie Building an Optimizing Compiler
65*c87b03e5Sespie Robert Morgan
66*c87b03e5Sespie Butterworth-Heinemann, 1998
67*c87b03e5Sespie Section 8.9
68*c87b03e5Sespie */
69*c87b03e5Sespie
70*c87b03e5Sespie #include "config.h"
71*c87b03e5Sespie #include "system.h"
72*c87b03e5Sespie
73*c87b03e5Sespie #include "rtl.h"
74*c87b03e5Sespie #include "hard-reg-set.h"
75*c87b03e5Sespie #include "basic-block.h"
76*c87b03e5Sespie #include "ssa.h"
77*c87b03e5Sespie #include "insn-config.h"
78*c87b03e5Sespie #include "recog.h"
79*c87b03e5Sespie #include "output.h"
80*c87b03e5Sespie
81*c87b03e5Sespie
82*c87b03e5Sespie /* A map from blocks to the edges on which they are control dependent. */
83*c87b03e5Sespie typedef struct {
84*c87b03e5Sespie /* An dynamically allocated array. The Nth element corresponds to
85*c87b03e5Sespie the block with index N + 2. The Ith bit in the bitmap is set if
86*c87b03e5Sespie that block is dependent on the Ith edge. */
87*c87b03e5Sespie bitmap *data;
88*c87b03e5Sespie /* The number of elements in the array. */
89*c87b03e5Sespie int length;
90*c87b03e5Sespie } control_dependent_block_to_edge_map_s, *control_dependent_block_to_edge_map;
91*c87b03e5Sespie
92*c87b03e5Sespie /* Local function prototypes. */
93*c87b03e5Sespie static control_dependent_block_to_edge_map control_dependent_block_to_edge_map_create
94*c87b03e5Sespie PARAMS((size_t num_basic_blocks));
95*c87b03e5Sespie static void set_control_dependent_block_to_edge_map_bit
96*c87b03e5Sespie PARAMS ((control_dependent_block_to_edge_map c, basic_block bb,
97*c87b03e5Sespie int edge_index));
98*c87b03e5Sespie static void control_dependent_block_to_edge_map_free
99*c87b03e5Sespie PARAMS ((control_dependent_block_to_edge_map c));
100*c87b03e5Sespie static void find_all_control_dependences
101*c87b03e5Sespie PARAMS ((struct edge_list *el, dominance_info pdom,
102*c87b03e5Sespie control_dependent_block_to_edge_map cdbte));
103*c87b03e5Sespie static void find_control_dependence
104*c87b03e5Sespie PARAMS ((struct edge_list *el, int edge_index, dominance_info pdom,
105*c87b03e5Sespie control_dependent_block_to_edge_map cdbte));
106*c87b03e5Sespie static basic_block find_pdom
107*c87b03e5Sespie PARAMS ((dominance_info pdom, basic_block block));
108*c87b03e5Sespie static int inherently_necessary_register_1
109*c87b03e5Sespie PARAMS ((rtx *current_rtx, void *data));
110*c87b03e5Sespie static int inherently_necessary_register
111*c87b03e5Sespie PARAMS ((rtx current_rtx));
112*c87b03e5Sespie static int find_inherently_necessary
113*c87b03e5Sespie PARAMS ((rtx current_rtx));
114*c87b03e5Sespie static int propagate_necessity_through_operand
115*c87b03e5Sespie PARAMS ((rtx *current_rtx, void *data));
116*c87b03e5Sespie static void note_inherently_necessary_set
117*c87b03e5Sespie PARAMS ((rtx, rtx, void *));
118*c87b03e5Sespie
119*c87b03e5Sespie /* Unnecessary insns are indicated using insns' in_struct bit. */
120*c87b03e5Sespie
121*c87b03e5Sespie /* Indicate INSN is dead-code; returns nothing. */
122*c87b03e5Sespie #define KILL_INSN(INSN) INSN_DEAD_CODE_P(INSN) = 1
123*c87b03e5Sespie /* Indicate INSN is necessary, i.e., not dead-code; returns nothing. */
124*c87b03e5Sespie #define RESURRECT_INSN(INSN) INSN_DEAD_CODE_P(INSN) = 0
125*c87b03e5Sespie /* Return nonzero if INSN is unnecessary. */
126*c87b03e5Sespie #define UNNECESSARY_P(INSN) INSN_DEAD_CODE_P(INSN)
127*c87b03e5Sespie static void mark_all_insn_unnecessary
128*c87b03e5Sespie PARAMS ((void));
129*c87b03e5Sespie /* Execute CODE with free variable INSN for all unnecessary insns in
130*c87b03e5Sespie an unspecified order, producing no output. */
131*c87b03e5Sespie #define EXECUTE_IF_UNNECESSARY(INSN, CODE) \
132*c87b03e5Sespie { \
133*c87b03e5Sespie rtx INSN; \
134*c87b03e5Sespie \
135*c87b03e5Sespie for (INSN = get_insns (); INSN != NULL_RTX; INSN = NEXT_INSN (INSN)) \
136*c87b03e5Sespie if (INSN_DEAD_CODE_P (INSN)) { \
137*c87b03e5Sespie CODE; \
138*c87b03e5Sespie } \
139*c87b03e5Sespie }
140*c87b03e5Sespie /* Find the label beginning block BB. */
141*c87b03e5Sespie static rtx find_block_label
142*c87b03e5Sespie PARAMS ((basic_block bb));
143*c87b03e5Sespie /* Remove INSN, updating its basic block structure. */
144*c87b03e5Sespie static void delete_insn_bb
145*c87b03e5Sespie PARAMS ((rtx insn));
146*c87b03e5Sespie
147*c87b03e5Sespie /* Recording which blocks are control dependent on which edges. We
148*c87b03e5Sespie expect each block to be control dependent on very few edges so we
149*c87b03e5Sespie use a bitmap for each block recording its edges. An array holds
150*c87b03e5Sespie the bitmap. Its position 0 entry holds the bitmap for block
151*c87b03e5Sespie INVALID_BLOCK+1 so that all blocks, including the entry and exit
152*c87b03e5Sespie blocks can participate in the data structure. */
153*c87b03e5Sespie
154*c87b03e5Sespie /* Create a control_dependent_block_to_edge_map, given the number
155*c87b03e5Sespie NUM_BASIC_BLOCKS of non-entry, non-exit basic blocks, e.g.,
156*c87b03e5Sespie n_basic_blocks. This memory must be released using
157*c87b03e5Sespie control_dependent_block_to_edge_map_free (). */
158*c87b03e5Sespie
159*c87b03e5Sespie static control_dependent_block_to_edge_map
control_dependent_block_to_edge_map_create(num_basic_blocks)160*c87b03e5Sespie control_dependent_block_to_edge_map_create (num_basic_blocks)
161*c87b03e5Sespie size_t num_basic_blocks;
162*c87b03e5Sespie {
163*c87b03e5Sespie int i;
164*c87b03e5Sespie control_dependent_block_to_edge_map c
165*c87b03e5Sespie = xmalloc (sizeof (control_dependent_block_to_edge_map_s));
166*c87b03e5Sespie c->length = num_basic_blocks - (INVALID_BLOCK+1);
167*c87b03e5Sespie c->data = xmalloc ((size_t) c->length*sizeof (bitmap));
168*c87b03e5Sespie for (i = 0; i < c->length; ++i)
169*c87b03e5Sespie c->data[i] = BITMAP_XMALLOC ();
170*c87b03e5Sespie
171*c87b03e5Sespie return c;
172*c87b03e5Sespie }
173*c87b03e5Sespie
174*c87b03e5Sespie /* Indicate block BB is control dependent on an edge with index
175*c87b03e5Sespie EDGE_INDEX in the mapping C of blocks to edges on which they are
176*c87b03e5Sespie control-dependent. */
177*c87b03e5Sespie
178*c87b03e5Sespie static void
set_control_dependent_block_to_edge_map_bit(c,bb,edge_index)179*c87b03e5Sespie set_control_dependent_block_to_edge_map_bit (c, bb, edge_index)
180*c87b03e5Sespie control_dependent_block_to_edge_map c;
181*c87b03e5Sespie basic_block bb;
182*c87b03e5Sespie int edge_index;
183*c87b03e5Sespie {
184*c87b03e5Sespie if (bb->index - (INVALID_BLOCK+1) >= c->length)
185*c87b03e5Sespie abort ();
186*c87b03e5Sespie
187*c87b03e5Sespie bitmap_set_bit (c->data[bb->index - (INVALID_BLOCK+1)],
188*c87b03e5Sespie edge_index);
189*c87b03e5Sespie }
190*c87b03e5Sespie
191*c87b03e5Sespie /* Execute CODE for each edge (given number EDGE_NUMBER within the
192*c87b03e5Sespie CODE) for which the block containing INSN is control dependent,
193*c87b03e5Sespie returning no output. CDBTE is the mapping of blocks to edges on
194*c87b03e5Sespie which they are control-dependent. */
195*c87b03e5Sespie
196*c87b03e5Sespie #define EXECUTE_IF_CONTROL_DEPENDENT(CDBTE, INSN, EDGE_NUMBER, CODE) \
197*c87b03e5Sespie EXECUTE_IF_SET_IN_BITMAP \
198*c87b03e5Sespie (CDBTE->data[BLOCK_NUM (INSN) - (INVALID_BLOCK+1)], 0, \
199*c87b03e5Sespie EDGE_NUMBER, CODE)
200*c87b03e5Sespie
201*c87b03e5Sespie /* Destroy a control_dependent_block_to_edge_map C. */
202*c87b03e5Sespie
203*c87b03e5Sespie static void
control_dependent_block_to_edge_map_free(c)204*c87b03e5Sespie control_dependent_block_to_edge_map_free (c)
205*c87b03e5Sespie control_dependent_block_to_edge_map c;
206*c87b03e5Sespie {
207*c87b03e5Sespie int i;
208*c87b03e5Sespie for (i = 0; i < c->length; ++i)
209*c87b03e5Sespie BITMAP_XFREE (c->data[i]);
210*c87b03e5Sespie free ((PTR) c);
211*c87b03e5Sespie }
212*c87b03e5Sespie
213*c87b03e5Sespie /* Record all blocks' control dependences on all edges in the edge
214*c87b03e5Sespie list EL, ala Morgan, Section 3.6. The mapping PDOM of blocks to
215*c87b03e5Sespie their postdominators are used, and results are stored in CDBTE,
216*c87b03e5Sespie which should be empty. */
217*c87b03e5Sespie
218*c87b03e5Sespie static void
find_all_control_dependences(el,pdom,cdbte)219*c87b03e5Sespie find_all_control_dependences (el, pdom, cdbte)
220*c87b03e5Sespie struct edge_list *el;
221*c87b03e5Sespie dominance_info pdom;
222*c87b03e5Sespie control_dependent_block_to_edge_map cdbte;
223*c87b03e5Sespie {
224*c87b03e5Sespie int i;
225*c87b03e5Sespie
226*c87b03e5Sespie for (i = 0; i < NUM_EDGES (el); ++i)
227*c87b03e5Sespie find_control_dependence (el, i, pdom, cdbte);
228*c87b03e5Sespie }
229*c87b03e5Sespie
230*c87b03e5Sespie /* Determine all blocks' control dependences on the given edge with
231*c87b03e5Sespie edge_list EL index EDGE_INDEX, ala Morgan, Section 3.6. The
232*c87b03e5Sespie mapping PDOM of blocks to their postdominators are used, and
233*c87b03e5Sespie results are stored in CDBTE, which is assumed to be initialized
234*c87b03e5Sespie with zeros in each (block b', edge) position. */
235*c87b03e5Sespie
236*c87b03e5Sespie static void
find_control_dependence(el,edge_index,pdom,cdbte)237*c87b03e5Sespie find_control_dependence (el, edge_index, pdom, cdbte)
238*c87b03e5Sespie struct edge_list *el;
239*c87b03e5Sespie int edge_index;
240*c87b03e5Sespie dominance_info pdom;
241*c87b03e5Sespie control_dependent_block_to_edge_map cdbte;
242*c87b03e5Sespie {
243*c87b03e5Sespie basic_block current_block;
244*c87b03e5Sespie basic_block ending_block;
245*c87b03e5Sespie
246*c87b03e5Sespie if (INDEX_EDGE_PRED_BB (el, edge_index) == EXIT_BLOCK_PTR)
247*c87b03e5Sespie abort ();
248*c87b03e5Sespie ending_block =
249*c87b03e5Sespie (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
250*c87b03e5Sespie ? ENTRY_BLOCK_PTR->next_bb
251*c87b03e5Sespie : find_pdom (pdom, INDEX_EDGE_PRED_BB (el, edge_index));
252*c87b03e5Sespie
253*c87b03e5Sespie for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
254*c87b03e5Sespie current_block != ending_block && current_block != EXIT_BLOCK_PTR;
255*c87b03e5Sespie current_block = find_pdom (pdom, current_block))
256*c87b03e5Sespie {
257*c87b03e5Sespie set_control_dependent_block_to_edge_map_bit (cdbte,
258*c87b03e5Sespie current_block,
259*c87b03e5Sespie edge_index);
260*c87b03e5Sespie }
261*c87b03e5Sespie }
262*c87b03e5Sespie
263*c87b03e5Sespie /* Find the immediate postdominator PDOM of the specified basic block
264*c87b03e5Sespie BLOCK. This function is necessary because some blocks have
265*c87b03e5Sespie negative numbers. */
266*c87b03e5Sespie
267*c87b03e5Sespie static basic_block
find_pdom(pdom,block)268*c87b03e5Sespie find_pdom (pdom, block)
269*c87b03e5Sespie dominance_info pdom;
270*c87b03e5Sespie basic_block block;
271*c87b03e5Sespie {
272*c87b03e5Sespie if (!block)
273*c87b03e5Sespie abort ();
274*c87b03e5Sespie if (block->index == INVALID_BLOCK)
275*c87b03e5Sespie abort ();
276*c87b03e5Sespie
277*c87b03e5Sespie if (block == ENTRY_BLOCK_PTR)
278*c87b03e5Sespie return ENTRY_BLOCK_PTR->next_bb;
279*c87b03e5Sespie else if (block == EXIT_BLOCK_PTR)
280*c87b03e5Sespie return EXIT_BLOCK_PTR;
281*c87b03e5Sespie else
282*c87b03e5Sespie {
283*c87b03e5Sespie basic_block bb = get_immediate_dominator (pdom, block);
284*c87b03e5Sespie if (!bb)
285*c87b03e5Sespie return EXIT_BLOCK_PTR;
286*c87b03e5Sespie return bb;
287*c87b03e5Sespie }
288*c87b03e5Sespie }
289*c87b03e5Sespie
290*c87b03e5Sespie /* Determine if the given CURRENT_RTX uses a hard register not
291*c87b03e5Sespie converted to SSA. Returns nonzero only if it uses such a hard
292*c87b03e5Sespie register. DATA is not used.
293*c87b03e5Sespie
294*c87b03e5Sespie The program counter (PC) is not considered inherently necessary
295*c87b03e5Sespie since code should be position-independent and thus not depend on
296*c87b03e5Sespie particular PC values. */
297*c87b03e5Sespie
298*c87b03e5Sespie static int
inherently_necessary_register_1(current_rtx,data)299*c87b03e5Sespie inherently_necessary_register_1 (current_rtx, data)
300*c87b03e5Sespie rtx *current_rtx;
301*c87b03e5Sespie void *data ATTRIBUTE_UNUSED;
302*c87b03e5Sespie {
303*c87b03e5Sespie rtx x = *current_rtx;
304*c87b03e5Sespie
305*c87b03e5Sespie if (x == NULL_RTX)
306*c87b03e5Sespie return 0;
307*c87b03e5Sespie switch (GET_CODE (x))
308*c87b03e5Sespie {
309*c87b03e5Sespie case CLOBBER:
310*c87b03e5Sespie /* Do not traverse the rest of the clobber. */
311*c87b03e5Sespie return -1;
312*c87b03e5Sespie break;
313*c87b03e5Sespie case PC:
314*c87b03e5Sespie return 0;
315*c87b03e5Sespie break;
316*c87b03e5Sespie case REG:
317*c87b03e5Sespie if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)) || x == pc_rtx)
318*c87b03e5Sespie return 0;
319*c87b03e5Sespie else
320*c87b03e5Sespie return !0;
321*c87b03e5Sespie break;
322*c87b03e5Sespie default:
323*c87b03e5Sespie return 0;
324*c87b03e5Sespie break;
325*c87b03e5Sespie }
326*c87b03e5Sespie }
327*c87b03e5Sespie
328*c87b03e5Sespie /* Return nonzero if the insn CURRENT_RTX is inherently necessary. */
329*c87b03e5Sespie
330*c87b03e5Sespie static int
inherently_necessary_register(current_rtx)331*c87b03e5Sespie inherently_necessary_register (current_rtx)
332*c87b03e5Sespie rtx current_rtx;
333*c87b03e5Sespie {
334*c87b03e5Sespie return for_each_rtx (¤t_rtx,
335*c87b03e5Sespie &inherently_necessary_register_1, NULL);
336*c87b03e5Sespie }
337*c87b03e5Sespie
338*c87b03e5Sespie
339*c87b03e5Sespie /* Called via note_stores for each store in an insn. Note whether
340*c87b03e5Sespie or not a particular store is inherently necessary. Store a
341*c87b03e5Sespie nonzero value in inherently_necessary_p if such a store is found. */
342*c87b03e5Sespie
343*c87b03e5Sespie static void
note_inherently_necessary_set(dest,set,data)344*c87b03e5Sespie note_inherently_necessary_set (dest, set, data)
345*c87b03e5Sespie rtx set ATTRIBUTE_UNUSED;
346*c87b03e5Sespie rtx dest;
347*c87b03e5Sespie void *data;
348*c87b03e5Sespie {
349*c87b03e5Sespie int *inherently_necessary_set_p = (int *) data;
350*c87b03e5Sespie
351*c87b03e5Sespie while (GET_CODE (dest) == SUBREG
352*c87b03e5Sespie || GET_CODE (dest) == STRICT_LOW_PART
353*c87b03e5Sespie || GET_CODE (dest) == ZERO_EXTRACT
354*c87b03e5Sespie || GET_CODE (dest) == SIGN_EXTRACT)
355*c87b03e5Sespie dest = XEXP (dest, 0);
356*c87b03e5Sespie
357*c87b03e5Sespie if (GET_CODE (dest) == MEM
358*c87b03e5Sespie || GET_CODE (dest) == UNSPEC
359*c87b03e5Sespie || GET_CODE (dest) == UNSPEC_VOLATILE)
360*c87b03e5Sespie *inherently_necessary_set_p = 1;
361*c87b03e5Sespie }
362*c87b03e5Sespie
363*c87b03e5Sespie /* Mark X as inherently necessary if appropriate. For example,
364*c87b03e5Sespie function calls and storing values into memory are inherently
365*c87b03e5Sespie necessary. This function is to be used with for_each_rtx ().
366*c87b03e5Sespie Return nonzero iff inherently necessary. */
367*c87b03e5Sespie
368*c87b03e5Sespie static int
find_inherently_necessary(x)369*c87b03e5Sespie find_inherently_necessary (x)
370*c87b03e5Sespie rtx x;
371*c87b03e5Sespie {
372*c87b03e5Sespie if (x == NULL_RTX)
373*c87b03e5Sespie return 0;
374*c87b03e5Sespie else if (inherently_necessary_register (x))
375*c87b03e5Sespie return !0;
376*c87b03e5Sespie else
377*c87b03e5Sespie switch (GET_CODE (x))
378*c87b03e5Sespie {
379*c87b03e5Sespie case CALL_INSN:
380*c87b03e5Sespie case BARRIER:
381*c87b03e5Sespie case PREFETCH:
382*c87b03e5Sespie return !0;
383*c87b03e5Sespie case CODE_LABEL:
384*c87b03e5Sespie case NOTE:
385*c87b03e5Sespie return 0;
386*c87b03e5Sespie case JUMP_INSN:
387*c87b03e5Sespie return JUMP_TABLE_DATA_P (x) || computed_jump_p (x) != 0;
388*c87b03e5Sespie case INSN:
389*c87b03e5Sespie {
390*c87b03e5Sespie int inherently_necessary_set = 0;
391*c87b03e5Sespie note_stores (PATTERN (x),
392*c87b03e5Sespie note_inherently_necessary_set,
393*c87b03e5Sespie &inherently_necessary_set);
394*c87b03e5Sespie
395*c87b03e5Sespie /* If we found an inherently necessary set or an asm
396*c87b03e5Sespie instruction, then we consider this insn inherently
397*c87b03e5Sespie necessary. */
398*c87b03e5Sespie return (inherently_necessary_set
399*c87b03e5Sespie || GET_CODE (PATTERN (x)) == ASM_INPUT
400*c87b03e5Sespie || asm_noperands (PATTERN (x)) >= 0);
401*c87b03e5Sespie }
402*c87b03e5Sespie default:
403*c87b03e5Sespie /* Found an impossible insn type. */
404*c87b03e5Sespie abort ();
405*c87b03e5Sespie break;
406*c87b03e5Sespie }
407*c87b03e5Sespie }
408*c87b03e5Sespie
409*c87b03e5Sespie /* Propagate necessity through REG and SUBREG operands of CURRENT_RTX.
410*c87b03e5Sespie This function is called with for_each_rtx () on necessary
411*c87b03e5Sespie instructions. The DATA must be a varray of unprocessed
412*c87b03e5Sespie instructions. */
413*c87b03e5Sespie
414*c87b03e5Sespie static int
propagate_necessity_through_operand(current_rtx,data)415*c87b03e5Sespie propagate_necessity_through_operand (current_rtx, data)
416*c87b03e5Sespie rtx *current_rtx;
417*c87b03e5Sespie void *data;
418*c87b03e5Sespie {
419*c87b03e5Sespie rtx x = *current_rtx;
420*c87b03e5Sespie varray_type *unprocessed_instructions = (varray_type *) data;
421*c87b03e5Sespie
422*c87b03e5Sespie if (x == NULL_RTX)
423*c87b03e5Sespie return 0;
424*c87b03e5Sespie switch ( GET_CODE (x))
425*c87b03e5Sespie {
426*c87b03e5Sespie case REG:
427*c87b03e5Sespie if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
428*c87b03e5Sespie {
429*c87b03e5Sespie rtx insn = VARRAY_RTX (ssa_definition, REGNO (x));
430*c87b03e5Sespie if (insn != NULL_RTX && UNNECESSARY_P (insn))
431*c87b03e5Sespie {
432*c87b03e5Sespie RESURRECT_INSN (insn);
433*c87b03e5Sespie VARRAY_PUSH_RTX (*unprocessed_instructions, insn);
434*c87b03e5Sespie }
435*c87b03e5Sespie }
436*c87b03e5Sespie return 0;
437*c87b03e5Sespie
438*c87b03e5Sespie default:
439*c87b03e5Sespie return 0;
440*c87b03e5Sespie }
441*c87b03e5Sespie }
442*c87b03e5Sespie
443*c87b03e5Sespie /* Indicate all insns initially assumed to be unnecessary. */
444*c87b03e5Sespie
445*c87b03e5Sespie static void
mark_all_insn_unnecessary()446*c87b03e5Sespie mark_all_insn_unnecessary ()
447*c87b03e5Sespie {
448*c87b03e5Sespie rtx insn;
449*c87b03e5Sespie for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
450*c87b03e5Sespie KILL_INSN (insn);
451*c87b03e5Sespie }
452*c87b03e5Sespie
453*c87b03e5Sespie /* Find the label beginning block BB, adding one if necessary. */
454*c87b03e5Sespie
455*c87b03e5Sespie static rtx
find_block_label(bb)456*c87b03e5Sespie find_block_label (bb)
457*c87b03e5Sespie basic_block bb;
458*c87b03e5Sespie {
459*c87b03e5Sespie rtx insn = bb->head;
460*c87b03e5Sespie if (LABEL_P (insn))
461*c87b03e5Sespie return insn;
462*c87b03e5Sespie else
463*c87b03e5Sespie {
464*c87b03e5Sespie rtx new_label = emit_label_before (gen_label_rtx (), insn);
465*c87b03e5Sespie if (insn == bb->head)
466*c87b03e5Sespie bb->head = new_label;
467*c87b03e5Sespie return new_label;
468*c87b03e5Sespie }
469*c87b03e5Sespie }
470*c87b03e5Sespie
471*c87b03e5Sespie /* Remove INSN, updating its basic block structure. */
472*c87b03e5Sespie
473*c87b03e5Sespie static void
delete_insn_bb(insn)474*c87b03e5Sespie delete_insn_bb (insn)
475*c87b03e5Sespie rtx insn;
476*c87b03e5Sespie {
477*c87b03e5Sespie if (!insn)
478*c87b03e5Sespie abort ();
479*c87b03e5Sespie
480*c87b03e5Sespie /* Do not actually delete anything that is not an INSN.
481*c87b03e5Sespie
482*c87b03e5Sespie We can get here because we only consider INSNs as
483*c87b03e5Sespie potentially necessary. We leave it to later passes
484*c87b03e5Sespie to remove unnecessary notes, unused labels, etc. */
485*c87b03e5Sespie if (! INSN_P (insn))
486*c87b03e5Sespie return;
487*c87b03e5Sespie
488*c87b03e5Sespie delete_insn (insn);
489*c87b03e5Sespie }
490*c87b03e5Sespie
491*c87b03e5Sespie /* Perform the dead-code elimination. */
492*c87b03e5Sespie
493*c87b03e5Sespie void
ssa_eliminate_dead_code()494*c87b03e5Sespie ssa_eliminate_dead_code ()
495*c87b03e5Sespie {
496*c87b03e5Sespie rtx insn;
497*c87b03e5Sespie basic_block bb;
498*c87b03e5Sespie /* Necessary instructions with operands to explore. */
499*c87b03e5Sespie varray_type unprocessed_instructions;
500*c87b03e5Sespie /* Map element (b,e) is nonzero if the block is control dependent on
501*c87b03e5Sespie edge. "cdbte" abbreviates control dependent block to edge. */
502*c87b03e5Sespie control_dependent_block_to_edge_map cdbte;
503*c87b03e5Sespie /* Element I is the immediate postdominator of block I. */
504*c87b03e5Sespie dominance_info pdom;
505*c87b03e5Sespie struct edge_list *el;
506*c87b03e5Sespie
507*c87b03e5Sespie /* Initialize the data structures. */
508*c87b03e5Sespie mark_all_insn_unnecessary ();
509*c87b03e5Sespie VARRAY_RTX_INIT (unprocessed_instructions, 64,
510*c87b03e5Sespie "unprocessed instructions");
511*c87b03e5Sespie cdbte = control_dependent_block_to_edge_map_create (last_basic_block);
512*c87b03e5Sespie
513*c87b03e5Sespie /* Prepare for use of BLOCK_NUM (). */
514*c87b03e5Sespie connect_infinite_loops_to_exit ();
515*c87b03e5Sespie
516*c87b03e5Sespie /* Compute control dependence. */
517*c87b03e5Sespie pdom = calculate_dominance_info (CDI_POST_DOMINATORS);
518*c87b03e5Sespie el = create_edge_list ();
519*c87b03e5Sespie find_all_control_dependences (el, pdom, cdbte);
520*c87b03e5Sespie
521*c87b03e5Sespie /* Find inherently necessary instructions. */
522*c87b03e5Sespie for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
523*c87b03e5Sespie if (find_inherently_necessary (insn))
524*c87b03e5Sespie {
525*c87b03e5Sespie RESURRECT_INSN (insn);
526*c87b03e5Sespie VARRAY_PUSH_RTX (unprocessed_instructions, insn);
527*c87b03e5Sespie }
528*c87b03e5Sespie
529*c87b03e5Sespie /* Propagate necessity using the operands of necessary instructions. */
530*c87b03e5Sespie while (VARRAY_ACTIVE_SIZE (unprocessed_instructions) > 0)
531*c87b03e5Sespie {
532*c87b03e5Sespie rtx current_instruction;
533*c87b03e5Sespie int edge_number;
534*c87b03e5Sespie
535*c87b03e5Sespie current_instruction = VARRAY_TOP_RTX (unprocessed_instructions);
536*c87b03e5Sespie VARRAY_POP (unprocessed_instructions);
537*c87b03e5Sespie
538*c87b03e5Sespie /* Make corresponding control dependent edges necessary. */
539*c87b03e5Sespie /* Assume the only JUMP_INSN is the block's last insn. It appears
540*c87b03e5Sespie that the last instruction of the program need not be a
541*c87b03e5Sespie JUMP_INSN. */
542*c87b03e5Sespie
543*c87b03e5Sespie if (INSN_P (current_instruction)
544*c87b03e5Sespie && !JUMP_TABLE_DATA_P (current_instruction))
545*c87b03e5Sespie {
546*c87b03e5Sespie /* Notes and labels contain no interesting operands. */
547*c87b03e5Sespie EXECUTE_IF_CONTROL_DEPENDENT
548*c87b03e5Sespie (cdbte, current_instruction, edge_number,
549*c87b03e5Sespie {
550*c87b03e5Sespie rtx jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
551*c87b03e5Sespie if (GET_CODE (jump_insn) == JUMP_INSN
552*c87b03e5Sespie && UNNECESSARY_P (jump_insn))
553*c87b03e5Sespie {
554*c87b03e5Sespie RESURRECT_INSN (jump_insn);
555*c87b03e5Sespie VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
556*c87b03e5Sespie }
557*c87b03e5Sespie });
558*c87b03e5Sespie
559*c87b03e5Sespie /* Propagate through the operands. */
560*c87b03e5Sespie for_each_rtx (¤t_instruction,
561*c87b03e5Sespie &propagate_necessity_through_operand,
562*c87b03e5Sespie (PTR) &unprocessed_instructions);
563*c87b03e5Sespie
564*c87b03e5Sespie /* PHI nodes are somewhat special in that each PHI alternative
565*c87b03e5Sespie has data and control dependencies. The data dependencies
566*c87b03e5Sespie are handled via propagate_necessity_through_operand. We
567*c87b03e5Sespie handle the control dependency here.
568*c87b03e5Sespie
569*c87b03e5Sespie We consider the control dependent edges leading to the
570*c87b03e5Sespie predecessor block associated with each PHI alternative
571*c87b03e5Sespie as necessary. */
572*c87b03e5Sespie if (PHI_NODE_P (current_instruction))
573*c87b03e5Sespie {
574*c87b03e5Sespie rtvec phi_vec = XVEC (SET_SRC (PATTERN (current_instruction)), 0);
575*c87b03e5Sespie int num_elem = GET_NUM_ELEM (phi_vec);
576*c87b03e5Sespie int v;
577*c87b03e5Sespie
578*c87b03e5Sespie for (v = num_elem - 2; v >= 0; v -= 2)
579*c87b03e5Sespie {
580*c87b03e5Sespie basic_block bb;
581*c87b03e5Sespie
582*c87b03e5Sespie bb = BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, v + 1)));
583*c87b03e5Sespie EXECUTE_IF_CONTROL_DEPENDENT
584*c87b03e5Sespie (cdbte, bb->end, edge_number,
585*c87b03e5Sespie {
586*c87b03e5Sespie rtx jump_insn;
587*c87b03e5Sespie
588*c87b03e5Sespie jump_insn = (INDEX_EDGE_PRED_BB (el, edge_number))->end;
589*c87b03e5Sespie if (((GET_CODE (jump_insn) == JUMP_INSN))
590*c87b03e5Sespie && UNNECESSARY_P (jump_insn))
591*c87b03e5Sespie {
592*c87b03e5Sespie RESURRECT_INSN (jump_insn);
593*c87b03e5Sespie VARRAY_PUSH_RTX (unprocessed_instructions, jump_insn);
594*c87b03e5Sespie }
595*c87b03e5Sespie });
596*c87b03e5Sespie
597*c87b03e5Sespie }
598*c87b03e5Sespie }
599*c87b03e5Sespie }
600*c87b03e5Sespie }
601*c87b03e5Sespie
602*c87b03e5Sespie /* Remove the unnecessary instructions. */
603*c87b03e5Sespie EXECUTE_IF_UNNECESSARY (insn,
604*c87b03e5Sespie {
605*c87b03e5Sespie if (any_condjump_p (insn))
606*c87b03e5Sespie {
607*c87b03e5Sespie basic_block bb = BLOCK_FOR_INSN (insn);
608*c87b03e5Sespie basic_block pdom_bb = find_pdom (pdom, bb);
609*c87b03e5Sespie rtx lbl;
610*c87b03e5Sespie edge e;
611*c87b03e5Sespie
612*c87b03e5Sespie /* Egad. The immediate post dominator is the exit block. We
613*c87b03e5Sespie would like to optimize this conditional jump to jump directly
614*c87b03e5Sespie to the exit block. That can be difficult as we may not have
615*c87b03e5Sespie a suitable CODE_LABEL that allows us to fall unmolested into
616*c87b03e5Sespie the exit block.
617*c87b03e5Sespie
618*c87b03e5Sespie So, we just delete the conditional branch by turning it into
619*c87b03e5Sespie a deleted note. That is safe, but just not as optimal as
620*c87b03e5Sespie it could be. */
621*c87b03e5Sespie if (pdom_bb == EXIT_BLOCK_PTR)
622*c87b03e5Sespie {
623*c87b03e5Sespie /* Since we're going to just delete the branch, we need
624*c87b03e5Sespie look at all the edges and remove all those which are not
625*c87b03e5Sespie a fallthru edge. */
626*c87b03e5Sespie e = bb->succ;
627*c87b03e5Sespie while (e)
628*c87b03e5Sespie {
629*c87b03e5Sespie edge temp = e;
630*c87b03e5Sespie
631*c87b03e5Sespie e = e->succ_next;
632*c87b03e5Sespie if ((temp->flags & EDGE_FALLTHRU) == 0)
633*c87b03e5Sespie {
634*c87b03e5Sespie /* We've found a non-fallthru edge, find any PHI nodes
635*c87b03e5Sespie at the target and clean them up. */
636*c87b03e5Sespie if (temp->dest != EXIT_BLOCK_PTR)
637*c87b03e5Sespie {
638*c87b03e5Sespie rtx insn
639*c87b03e5Sespie = first_insn_after_basic_block_note (temp->dest);
640*c87b03e5Sespie
641*c87b03e5Sespie while (PHI_NODE_P (insn))
642*c87b03e5Sespie {
643*c87b03e5Sespie remove_phi_alternative (PATTERN (insn), temp->src);
644*c87b03e5Sespie insn = NEXT_INSN (insn);
645*c87b03e5Sespie }
646*c87b03e5Sespie }
647*c87b03e5Sespie
648*c87b03e5Sespie remove_edge (temp);
649*c87b03e5Sespie }
650*c87b03e5Sespie }
651*c87b03e5Sespie
652*c87b03e5Sespie /* Now "delete" the conditional jump. */
653*c87b03e5Sespie PUT_CODE (insn, NOTE);
654*c87b03e5Sespie NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
655*c87b03e5Sespie continue;
656*c87b03e5Sespie }
657*c87b03e5Sespie
658*c87b03e5Sespie /* We've found a conditional branch that is unnecessary.
659*c87b03e5Sespie
660*c87b03e5Sespie First, remove all outgoing edges from this block, updating
661*c87b03e5Sespie PHI nodes as appropriate. */
662*c87b03e5Sespie e = bb->succ;
663*c87b03e5Sespie while (e)
664*c87b03e5Sespie {
665*c87b03e5Sespie edge temp = e;
666*c87b03e5Sespie
667*c87b03e5Sespie e = e->succ_next;
668*c87b03e5Sespie
669*c87b03e5Sespie if (temp->flags & EDGE_ABNORMAL)
670*c87b03e5Sespie continue;
671*c87b03e5Sespie
672*c87b03e5Sespie /* We found an edge that is not executable. First simplify
673*c87b03e5Sespie the PHI nodes in the target block. */
674*c87b03e5Sespie if (temp->dest != EXIT_BLOCK_PTR)
675*c87b03e5Sespie {
676*c87b03e5Sespie rtx insn = first_insn_after_basic_block_note (temp->dest);
677*c87b03e5Sespie
678*c87b03e5Sespie while (PHI_NODE_P (insn))
679*c87b03e5Sespie {
680*c87b03e5Sespie remove_phi_alternative (PATTERN (insn), temp->src);
681*c87b03e5Sespie insn = NEXT_INSN (insn);
682*c87b03e5Sespie }
683*c87b03e5Sespie }
684*c87b03e5Sespie
685*c87b03e5Sespie remove_edge (temp);
686*c87b03e5Sespie }
687*c87b03e5Sespie
688*c87b03e5Sespie /* Create an edge from this block to the post dominator.
689*c87b03e5Sespie What about the PHI nodes at the target? */
690*c87b03e5Sespie make_edge (bb, pdom_bb, 0);
691*c87b03e5Sespie
692*c87b03e5Sespie /* Third, transform this insn into an unconditional
693*c87b03e5Sespie jump to the label for the immediate postdominator. */
694*c87b03e5Sespie lbl = find_block_label (pdom_bb);
695*c87b03e5Sespie SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (VOIDmode, lbl);
696*c87b03e5Sespie INSN_CODE (insn) = -1;
697*c87b03e5Sespie JUMP_LABEL (insn) = lbl;
698*c87b03e5Sespie LABEL_NUSES (lbl)++;
699*c87b03e5Sespie
700*c87b03e5Sespie /* A barrier must follow any unconditional jump. Barriers
701*c87b03e5Sespie are not in basic blocks so this must occur after
702*c87b03e5Sespie deleting the conditional jump. */
703*c87b03e5Sespie emit_barrier_after (insn);
704*c87b03e5Sespie }
705*c87b03e5Sespie else if (!JUMP_P (insn))
706*c87b03e5Sespie delete_insn_bb (insn);
707*c87b03e5Sespie });
708*c87b03e5Sespie
709*c87b03e5Sespie /* Remove fake edges from the CFG. */
710*c87b03e5Sespie remove_fake_edges ();
711*c87b03e5Sespie
712*c87b03e5Sespie /* Find any blocks with no successors and ensure they are followed
713*c87b03e5Sespie by a BARRIER. delete_insn has the nasty habit of deleting barriers
714*c87b03e5Sespie when deleting insns. */
715*c87b03e5Sespie FOR_EACH_BB (bb)
716*c87b03e5Sespie {
717*c87b03e5Sespie if (bb->succ == NULL)
718*c87b03e5Sespie {
719*c87b03e5Sespie rtx next = NEXT_INSN (bb->end);
720*c87b03e5Sespie
721*c87b03e5Sespie if (!next || GET_CODE (next) != BARRIER)
722*c87b03e5Sespie emit_barrier_after (bb->end);
723*c87b03e5Sespie }
724*c87b03e5Sespie }
725*c87b03e5Sespie /* Release allocated memory. */
726*c87b03e5Sespie for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
727*c87b03e5Sespie RESURRECT_INSN (insn);
728*c87b03e5Sespie if (VARRAY_ACTIVE_SIZE (unprocessed_instructions) != 0)
729*c87b03e5Sespie abort ();
730*c87b03e5Sespie control_dependent_block_to_edge_map_free (cdbte);
731*c87b03e5Sespie free ((PTR) pdom);
732*c87b03e5Sespie free_edge_list (el);
733*c87b03e5Sespie }
734