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