]>
Commit | Line | Data |
---|---|---|
44cec300 | 1 | /* Conditional constant propagation pass for the GNU compiler. |
cf403648 | 2 | Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc. |
44cec300 JL |
3 | Original framework by Daniel Berlin <dan@cgsoftware.com> |
4 | Fleshed out and major cleanups by Jeff Law <law@redhat.com> | |
786de7eb | 5 | |
1322177d | 6 | This file is part of GCC. |
786de7eb | 7 | |
1322177d LB |
8 | GCC is free software; you can redistribute it and/or modify it under |
9 | the terms of the GNU General Public License as published by the Free | |
10 | Software Foundation; either version 2, or (at your option) any later | |
11 | version. | |
786de7eb | 12 | |
1322177d LB |
13 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
14 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
44cec300 JL |
15 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
16 | for more details. | |
786de7eb | 17 | |
44cec300 | 18 | You should have received a copy of the GNU General Public License |
1322177d | 19 | along with GCC; see the file COPYING. If not, write to the Free |
44cec300 JL |
20 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA |
21 | 02111-1307, USA. */ | |
22 | ||
23 | /* Conditional constant propagation. | |
24 | ||
25 | References: | |
26 | ||
27 | Constant propagation with conditional branches, | |
28 | Wegman and Zadeck, ACM TOPLAS 13(2):181-210. | |
29 | ||
30 | Building an Optimizing Compiler, | |
31 | Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. | |
32 | ||
33 | Advanced Compiler Design and Implementation, | |
34 | Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 | |
35 | ||
36 | The overall structure is as follows: | |
37 | ||
38 | 1. Run a simple SSA based DCE pass to remove any dead code. | |
39 | 2. Run CCP to compute what registers are known constants | |
40 | and what edges are not executable. Remove unexecutable | |
41 | edges from the CFG and simplify PHI nodes. | |
42 | 3. Replace registers with constants where possible. | |
43 | 4. Remove unreachable blocks computed in step #2. | |
44 | 5. Another simple SSA DCE pass to remove dead code exposed | |
45 | by CCP. | |
46 | ||
786de7eb | 47 | When we exit, we are still in SSA form. |
44cec300 JL |
48 | |
49 | ||
50 | Potential further enhancements: | |
51 | ||
52 | 1. Handle SUBREGs, STRICT_LOW_PART, etc in destinations more | |
53 | gracefully. | |
54 | ||
55 | 2. Handle insns with multiple outputs more gracefully. | |
56 | ||
57 | 3. Handle CONST_DOUBLE and symbolic constants. | |
58 | ||
59 | 4. Fold expressions after performing constant substitutions. */ | |
60 | ||
61 | ||
62 | #include "config.h" | |
63 | #include "system.h" | |
4977bab6 ZW |
64 | #include "coretypes.h" |
65 | #include "tm.h" | |
44cec300 JL |
66 | |
67 | #include "rtl.h" | |
68 | #include "hard-reg-set.h" | |
69 | #include "basic-block.h" | |
70 | #include "ssa.h" | |
71 | #include "insn-config.h" | |
72 | #include "recog.h" | |
73 | #include "output.h" | |
74 | #include "errors.h" | |
75 | #include "ggc.h" | |
76 | #include "df.h" | |
77 | #include "function.h" | |
78 | \f | |
79 | /* Possible lattice values. */ | |
80 | ||
81 | typedef enum | |
82 | { | |
83 | UNDEFINED, | |
84 | CONSTANT, | |
85 | VARYING | |
86 | } latticevalue; | |
87 | ||
786de7eb | 88 | /* Main structure for CCP. |
44cec300 JL |
89 | |
90 | Contains the lattice value and, if it's a constant, the constant | |
91 | value. */ | |
92 | typedef struct | |
93 | { | |
94 | latticevalue lattice_val; | |
95 | rtx const_value; | |
96 | } value; | |
97 | ||
98 | /* Array of values indexed by register number. */ | |
99 | static value *values; | |
100 | ||
101 | /* A bitmap to keep track of executable blocks in the CFG. */ | |
102 | static sbitmap executable_blocks; | |
103 | ||
104 | /* A bitmap for all executable edges in the CFG. */ | |
105 | static sbitmap executable_edges; | |
106 | ||
107 | /* Array of edges on the work list. */ | |
108 | static edge *edge_info; | |
109 | ||
110 | /* We need an edge list to be able to get indexes easily. */ | |
111 | static struct edge_list *edges; | |
112 | ||
113 | /* For building/following use-def and def-use chains. */ | |
114 | static struct df *df_analyzer; | |
115 | ||
116 | /* Current edge we are operating on, from the worklist */ | |
117 | static edge flow_edges; | |
118 | ||
119 | /* Bitmap of SSA edges which will need reexamination as their definition | |
120 | has changed. */ | |
121 | static sbitmap ssa_edges; | |
122 | ||
123 | /* Simple macros to simplify code */ | |
124 | #define SSA_NAME(x) REGNO (SET_DEST (x)) | |
44cec300 JL |
125 | #define EIE(x,y) EDGE_INDEX (edges, x, y) |
126 | ||
44cec300 JL |
127 | static void visit_phi_node PARAMS ((rtx, basic_block)); |
128 | static void visit_expression PARAMS ((rtx, basic_block)); | |
129 | static void defs_to_undefined PARAMS ((rtx)); | |
130 | static void defs_to_varying PARAMS ((rtx)); | |
131 | static void examine_flow_edges PARAMS ((void)); | |
af5c573a | 132 | static int mark_references PARAMS ((rtx *, void *)); |
44cec300 JL |
133 | static void follow_def_use_chains PARAMS ((void)); |
134 | static void optimize_unexecutable_edges PARAMS ((struct edge_list *, sbitmap)); | |
135 | static void ssa_ccp_substitute_constants PARAMS ((void)); | |
136 | static void ssa_ccp_df_delete_unreachable_insns PARAMS ((void)); | |
af5c573a | 137 | static void ssa_fast_dce PARAMS ((struct df *)); |
44cec300 JL |
138 | |
139 | /* Loop through the PHI_NODE's parameters for BLOCK and compare their | |
140 | lattice values to determine PHI_NODE's lattice value. */ | |
141 | static void | |
142 | visit_phi_node (phi_node, block) | |
143 | rtx phi_node; | |
144 | basic_block block; | |
145 | { | |
146 | unsigned int i; | |
147 | rtx phi_node_expr = NULL; | |
148 | unsigned int phi_node_name = SSA_NAME (PATTERN (phi_node)); | |
149 | latticevalue phi_node_lattice_val = UNDEFINED; | |
150 | rtx pat = PATTERN (phi_node); | |
151 | rtvec phi_vec = XVEC (SET_SRC (pat), 0); | |
152 | unsigned int num_elem = GET_NUM_ELEM (phi_vec); | |
153 | ||
154 | for (i = 0; i < num_elem; i += 2) | |
155 | { | |
156 | if (TEST_BIT (executable_edges, | |
157 | EIE (BASIC_BLOCK (INTVAL (RTVEC_ELT (phi_vec, i + 1))), | |
158 | block))) | |
159 | { | |
160 | unsigned int current_parm | |
161 | = REGNO (RTVEC_ELT (phi_vec, i)); | |
162 | ||
163 | latticevalue current_parm_lattice_val | |
164 | = values[current_parm].lattice_val; | |
165 | ||
166 | /* If any node is VARYING, then new value of PHI_NODE | |
167 | is VARYING. */ | |
168 | if (current_parm_lattice_val == VARYING) | |
169 | { | |
170 | phi_node_lattice_val = VARYING; | |
171 | phi_node_expr = NULL; | |
172 | break; | |
173 | } | |
174 | ||
175 | /* If we have more than one distinct constant, then the new | |
176 | value of PHI_NODE is VARYING. */ | |
177 | if (current_parm_lattice_val == CONSTANT | |
178 | && phi_node_lattice_val == CONSTANT | |
179 | && values[current_parm].const_value != phi_node_expr) | |
180 | { | |
181 | phi_node_lattice_val = VARYING; | |
182 | phi_node_expr = NULL; | |
183 | break; | |
184 | } | |
185 | ||
186 | /* If the current value of PHI_NODE is UNDEFINED and one | |
187 | node in PHI_NODE is CONSTANT, then the new value of the | |
188 | PHI is that CONSTANT. Note this can turn into VARYING | |
786de7eb | 189 | if we find another distinct constant later. */ |
44cec300 JL |
190 | if (phi_node_lattice_val == UNDEFINED |
191 | && phi_node_expr == NULL | |
192 | && current_parm_lattice_val == CONSTANT) | |
193 | { | |
194 | phi_node_expr = values[current_parm].const_value; | |
195 | phi_node_lattice_val = CONSTANT; | |
196 | continue; | |
197 | } | |
198 | } | |
199 | } | |
200 | ||
201 | /* If the value of PHI_NODE changed, then we will need to | |
202 | re-execute uses of the output of PHI_NODE. */ | |
203 | if (phi_node_lattice_val != values[phi_node_name].lattice_val) | |
204 | { | |
205 | values[phi_node_name].lattice_val = phi_node_lattice_val; | |
206 | values[phi_node_name].const_value = phi_node_expr; | |
207 | SET_BIT (ssa_edges, phi_node_name); | |
208 | } | |
209 | } | |
210 | ||
211 | /* Sets all defs in an insn to UNDEFINED. */ | |
212 | static void | |
213 | defs_to_undefined (insn) | |
214 | rtx insn; | |
215 | { | |
216 | struct df_link *currdef; | |
217 | for (currdef = DF_INSN_DEFS (df_analyzer, insn); currdef; | |
218 | currdef = currdef->next) | |
219 | { | |
220 | if (values[DF_REF_REGNO (currdef->ref)].lattice_val != UNDEFINED) | |
221 | SET_BIT (ssa_edges, DF_REF_REGNO (currdef->ref)); | |
222 | values[DF_REF_REGNO (currdef->ref)].lattice_val = UNDEFINED; | |
223 | } | |
224 | } | |
225 | ||
226 | /* Sets all defs in an insn to VARYING. */ | |
227 | static void | |
228 | defs_to_varying (insn) | |
229 | rtx insn; | |
230 | { | |
231 | struct df_link *currdef; | |
232 | for (currdef = DF_INSN_DEFS (df_analyzer, insn); currdef; | |
233 | currdef = currdef->next) | |
234 | { | |
235 | if (values[DF_REF_REGNO (currdef->ref)].lattice_val != VARYING) | |
236 | SET_BIT (ssa_edges, DF_REF_REGNO (currdef->ref)); | |
237 | values[DF_REF_REGNO (currdef->ref)].lattice_val = VARYING; | |
238 | } | |
239 | } | |
240 | ||
a1f300c0 | 241 | /* Go through the expression, call the appropriate evaluation routines |
44cec300 JL |
242 | to attempt cprop */ |
243 | static void | |
244 | visit_expression (insn, block) | |
245 | rtx insn; | |
246 | basic_block block; | |
247 | { | |
248 | rtx src, dest, set; | |
249 | ||
42f28de9 JL |
250 | |
251 | /* Ugh. CALL_INSNs may end a basic block and have multiple edges | |
252 | leading out from them. | |
253 | ||
254 | Mark all the outgoing edges as executable, then fall into the | |
255 | normal processing below. */ | |
256 | if (GET_CODE (insn) == CALL_INSN && block->end == insn) | |
257 | { | |
258 | edge curredge; | |
259 | ||
260 | for (curredge = block->succ; curredge; | |
261 | curredge = curredge->succ_next) | |
262 | { | |
263 | int index = EIE (curredge->src, curredge->dest); | |
264 | ||
265 | if (TEST_BIT (executable_edges, index)) | |
266 | continue; | |
267 | ||
268 | SET_BIT (executable_edges, index); | |
269 | edge_info[index] = flow_edges; | |
270 | flow_edges = curredge; | |
271 | } | |
272 | } | |
273 | ||
44cec300 JL |
274 | set = single_set (insn); |
275 | if (! set) | |
276 | { | |
277 | defs_to_varying (insn); | |
278 | return; | |
279 | } | |
280 | ||
281 | src = SET_SRC (set); | |
282 | dest = SET_DEST (set); | |
283 | ||
284 | /* We may want to refine this some day. */ | |
285 | if (GET_CODE (dest) != REG && dest != pc_rtx) | |
286 | { | |
287 | defs_to_varying (insn); | |
288 | return; | |
289 | } | |
290 | ||
291 | /* Hard registers are not put in SSA form and thus we must consider | |
786de7eb | 292 | them varying. All the more reason to avoid hard registers in |
44cec300 JL |
293 | RTL until as late as possible in the compilation. */ |
294 | if (GET_CODE (dest) == REG && REGNO (dest) < FIRST_PSEUDO_REGISTER) | |
295 | { | |
296 | defs_to_varying (insn); | |
297 | return; | |
298 | } | |
299 | ||
300 | /* If this is assigning DEST to a constant, record that fact. */ | |
301 | if (GET_CODE (src) == CONST_INT && GET_CODE (insn) == INSN) | |
302 | { | |
303 | unsigned int resultreg = REGNO (dest); | |
304 | ||
305 | values[resultreg].lattice_val = CONSTANT; | |
306 | values[resultreg].const_value = SET_SRC (PATTERN (insn)); | |
307 | SET_BIT (ssa_edges, resultreg); | |
308 | } | |
309 | ||
310 | /* If this is a copy operation, then we can copy the lattice values. */ | |
311 | else if (GET_CODE (src) == REG && GET_CODE (dest) == REG) | |
312 | { | |
313 | unsigned int old_value = REGNO (src); | |
314 | latticevalue old_lattice_value = values[old_value].lattice_val; | |
315 | unsigned int new_value = REGNO (dest); | |
316 | ||
317 | /* Unless the lattice value is going to change, don't bother | |
318 | adding the "new value" into the worklist. */ | |
319 | if (values[new_value].lattice_val != old_lattice_value | |
320 | || values[new_value].const_value != values[old_value].const_value) | |
321 | SET_BIT (ssa_edges, new_value); | |
322 | ||
323 | /* Copy the old lattice node info into the new value lattice node. */ | |
324 | values[new_value].lattice_val = old_lattice_value; | |
325 | values[new_value].const_value = values[old_value].const_value; | |
326 | } | |
327 | ||
328 | /* Handle jumps. */ | |
329 | else if (GET_CODE (insn) == JUMP_INSN) | |
330 | { | |
331 | rtx x = pc_set (insn); | |
332 | if (GET_CODE (src) != IF_THEN_ELSE) | |
333 | { | |
334 | edge curredge; | |
335 | ||
336 | /* This is a computed jump, table jump, or an unconditional | |
337 | jump. For all these cases we want to mark all successor | |
338 | blocks as executable if they have not already been | |
339 | marked. | |
340 | ||
341 | One day we may try do better with swtich tables and | |
342 | other computed jumps. */ | |
343 | for (curredge = block->succ; curredge; | |
344 | curredge = curredge->succ_next) | |
345 | { | |
346 | int index = EIE (curredge->src, curredge->dest); | |
347 | ||
348 | if (TEST_BIT (executable_edges, index)) | |
349 | continue; | |
350 | ||
351 | SET_BIT (executable_edges, index); | |
352 | edge_info[index] = flow_edges; | |
353 | flow_edges = curredge; | |
354 | } | |
355 | } | |
356 | else | |
357 | { | |
358 | edge curredge; | |
359 | enum rtx_code comparison_code; | |
360 | rtx comparison_src0; | |
361 | rtx comparison_src1; | |
362 | ||
363 | comparison_code = GET_CODE (XEXP (src, 0)); | |
364 | comparison_src0 = XEXP (XEXP (src, 0), 0); | |
365 | comparison_src1 = XEXP (XEXP (src, 0), 1); | |
366 | ||
367 | /* If either operand is undefined, then there is nothing to | |
368 | do right now. If/when operands are later defined we will | |
369 | revaluate the condition and take the appropriate action. */ | |
370 | if ((GET_CODE (comparison_src0) == REG | |
371 | && values[REGNO (comparison_src0)].lattice_val == UNDEFINED) | |
372 | || (GET_CODE (comparison_src1) == REG | |
373 | && values[REGNO (comparison_src1)].lattice_val == UNDEFINED)) | |
374 | return; | |
375 | ||
376 | /* If either operand is varying, then we must consider all | |
377 | paths as executable. */ | |
378 | if ((GET_CODE (comparison_src0) == REG | |
379 | && values[REGNO (comparison_src0)].lattice_val == VARYING) | |
380 | || (GET_CODE (comparison_src1) == REG | |
381 | && values[REGNO (comparison_src1)].lattice_val == VARYING)) | |
382 | { | |
383 | for (curredge = block->succ; curredge; | |
384 | curredge = curredge->succ_next) | |
385 | { | |
386 | int index = EIE (curredge->src, curredge->dest); | |
387 | ||
388 | if (TEST_BIT (executable_edges, index)) | |
389 | continue; | |
390 | ||
391 | SET_BIT (executable_edges, index); | |
392 | edge_info[index] = flow_edges; | |
393 | flow_edges = curredge; | |
394 | } | |
395 | return; | |
396 | } | |
397 | ||
398 | /* Try to simplify the comparison. */ | |
399 | if (GET_CODE (comparison_src0) == REG | |
400 | && values[REGNO (comparison_src0)].lattice_val == CONSTANT) | |
401 | comparison_src0 = values[REGNO (comparison_src0)].const_value; | |
402 | ||
403 | if (GET_CODE (comparison_src1) == REG | |
404 | && values[REGNO (comparison_src1)].lattice_val == CONSTANT) | |
405 | comparison_src1 = values[REGNO (comparison_src1)].const_value; | |
406 | ||
407 | x = simplify_ternary_operation (IF_THEN_ELSE, | |
408 | VOIDmode, | |
409 | GET_MODE (XEXP (src, 0)), | |
410 | gen_rtx (comparison_code, | |
411 | GET_MODE (XEXP (src, 0)), | |
412 | comparison_src0, | |
413 | comparison_src1), | |
414 | XEXP (src, 1), | |
415 | XEXP (src, 2)); | |
416 | ||
417 | /* Walk through all the outgoing edges from this block and see | |
418 | which (if any) we should mark as executable. */ | |
419 | for (curredge = block->succ; curredge; | |
420 | curredge = curredge->succ_next) | |
421 | { | |
422 | int index = EIE (curredge->src, curredge->dest); | |
423 | ||
424 | if (TEST_BIT (executable_edges, index)) | |
425 | continue; | |
426 | ||
427 | /* If we were unable to simplify the expression at this | |
428 | point, it's highly unlikely we'll be able to simplify | |
429 | it later. So consider all edges as executable if the | |
430 | expression did not simplify. | |
431 | ||
432 | If the expression simplified to (pc), then we know we | |
433 | will take the fall-thru edge, so mark it. Similarly, | |
434 | if the expression simplified to (label_ref ...), then | |
435 | we know the branch will be taken and we mark that | |
436 | edge as taken. */ | |
437 | if (!x | |
438 | || (x == pc_rtx | |
439 | && (curredge->flags & EDGE_FALLTHRU)) | |
440 | || (GET_CODE (x) == LABEL_REF | |
441 | && ! (curredge->flags & EDGE_FALLTHRU))) | |
442 | { | |
443 | SET_BIT (executable_edges, index); | |
444 | edge_info[index] = flow_edges; | |
445 | flow_edges = curredge; | |
446 | } | |
447 | } | |
448 | } | |
449 | } | |
450 | else if (!PHI_NODE_P (insn)) | |
451 | { | |
452 | rtx simplified = NULL; | |
453 | ||
454 | /* We've got some kind of INSN. If it's simple, try to evaluate | |
786de7eb | 455 | it and record the results. |
44cec300 JL |
456 | |
457 | We already know this insn is a single_set and that it sets | |
458 | a pseudo register. So we just need to extract the source | |
459 | arguments, simplify them to constants if possible, then | |
460 | simplify the expression as a whole if possible. */ | |
461 | switch (GET_RTX_CLASS (GET_CODE (src))) | |
462 | { | |
463 | case '<': | |
464 | { | |
465 | rtx src0 = XEXP (src, 0); | |
466 | rtx src1 = XEXP (src, 1); | |
467 | enum machine_mode mode; | |
468 | ||
469 | /* If either is undefined, then the result is undefined. */ | |
470 | if ((GET_CODE (src0) == REG | |
471 | && values[REGNO (src0)].lattice_val == UNDEFINED) | |
472 | || (GET_CODE (src1) == REG | |
473 | && values[REGNO (src1)].lattice_val == UNDEFINED)) | |
474 | { | |
475 | defs_to_undefined (insn); | |
476 | break; | |
477 | } | |
42f28de9 JL |
478 | |
479 | /* Determine the mode for the operation before we simplify | |
480 | our arguments to constants. */ | |
481 | mode = GET_MODE (src0); | |
482 | if (mode == VOIDmode) | |
483 | mode = GET_MODE (src1); | |
484 | ||
44cec300 JL |
485 | /* Simplify source operands to whatever known values they |
486 | may have. */ | |
487 | if (GET_CODE (src0) == REG | |
488 | && values[REGNO (src0)].lattice_val == CONSTANT) | |
489 | src0 = values[REGNO (src0)].const_value; | |
490 | ||
491 | if (GET_CODE (src1) == REG | |
492 | && values[REGNO (src1)].lattice_val == CONSTANT) | |
493 | src1 = values[REGNO (src1)].const_value; | |
494 | ||
495 | /* See if the simplifier can determine if this operation | |
496 | computes a constant value. */ | |
44cec300 JL |
497 | simplified = simplify_relational_operation (GET_CODE (src), |
498 | mode, src0, src1); | |
499 | break; | |
500 | ||
501 | } | |
502 | ||
503 | case '1': | |
504 | { | |
505 | rtx src0 = XEXP (src, 0); | |
42f28de9 | 506 | enum machine_mode mode0 = GET_MODE (src0); |
44cec300 JL |
507 | |
508 | /* If the operand is undefined, then the result is undefined. */ | |
509 | if (GET_CODE (src0) == REG | |
510 | && values[REGNO (src0)].lattice_val == UNDEFINED) | |
511 | { | |
512 | defs_to_undefined (insn); | |
513 | break; | |
514 | } | |
786de7eb | 515 | |
44cec300 JL |
516 | /* Simplify source operands to whatever known values they |
517 | may have. */ | |
518 | if (GET_CODE (src0) == REG | |
519 | && values[REGNO (src0)].lattice_val == CONSTANT) | |
520 | src0 = values[REGNO (src0)].const_value; | |
521 | ||
522 | /* See if the simplifier can determine if this operation | |
523 | computes a constant value. */ | |
524 | simplified = simplify_unary_operation (GET_CODE (src), | |
525 | GET_MODE (src), | |
526 | src0, | |
42f28de9 | 527 | mode0); |
44cec300 JL |
528 | break; |
529 | } | |
530 | ||
531 | case '2': | |
532 | case 'c': | |
533 | { | |
534 | rtx src0 = XEXP (src, 0); | |
535 | rtx src1 = XEXP (src, 1); | |
536 | ||
537 | /* If either is undefined, then the result is undefined. */ | |
538 | if ((GET_CODE (src0) == REG | |
539 | && values[REGNO (src0)].lattice_val == UNDEFINED) | |
540 | || (GET_CODE (src1) == REG | |
541 | && values[REGNO (src1)].lattice_val == UNDEFINED)) | |
542 | { | |
543 | defs_to_undefined (insn); | |
544 | break; | |
545 | } | |
786de7eb | 546 | |
44cec300 JL |
547 | /* Simplify source operands to whatever known values they |
548 | may have. */ | |
549 | if (GET_CODE (src0) == REG | |
550 | && values[REGNO (src0)].lattice_val == CONSTANT) | |
551 | src0 = values[REGNO (src0)].const_value; | |
552 | ||
553 | if (GET_CODE (src1) == REG | |
554 | && values[REGNO (src1)].lattice_val == CONSTANT) | |
555 | src1 = values[REGNO (src1)].const_value; | |
556 | ||
557 | /* See if the simplifier can determine if this operation | |
558 | computes a constant value. */ | |
559 | simplified = simplify_binary_operation (GET_CODE (src), | |
560 | GET_MODE (src), | |
561 | src0, src1); | |
562 | break; | |
563 | } | |
564 | ||
565 | case '3': | |
566 | case 'b': | |
567 | { | |
568 | rtx src0 = XEXP (src, 0); | |
569 | rtx src1 = XEXP (src, 1); | |
570 | rtx src2 = XEXP (src, 2); | |
571 | ||
572 | /* If either is undefined, then the result is undefined. */ | |
573 | if ((GET_CODE (src0) == REG | |
574 | && values[REGNO (src0)].lattice_val == UNDEFINED) | |
575 | || (GET_CODE (src1) == REG | |
576 | && values[REGNO (src1)].lattice_val == UNDEFINED) | |
577 | || (GET_CODE (src2) == REG | |
578 | && values[REGNO (src2)].lattice_val == UNDEFINED)) | |
579 | { | |
580 | defs_to_undefined (insn); | |
581 | break; | |
582 | } | |
786de7eb | 583 | |
44cec300 JL |
584 | /* Simplify source operands to whatever known values they |
585 | may have. */ | |
586 | if (GET_CODE (src0) == REG | |
587 | && values[REGNO (src0)].lattice_val == CONSTANT) | |
588 | src0 = values[REGNO (src0)].const_value; | |
589 | ||
590 | if (GET_CODE (src1) == REG | |
591 | && values[REGNO (src1)].lattice_val == CONSTANT) | |
592 | src1 = values[REGNO (src1)].const_value; | |
593 | ||
594 | if (GET_CODE (src2) == REG | |
595 | && values[REGNO (src2)].lattice_val == CONSTANT) | |
596 | src2 = values[REGNO (src2)].const_value; | |
597 | ||
598 | /* See if the simplifier can determine if this operation | |
599 | computes a constant value. */ | |
600 | simplified = simplify_ternary_operation (GET_CODE (src), | |
601 | GET_MODE (src), | |
602 | GET_MODE (src), | |
603 | src0, src1, src2); | |
604 | break; | |
605 | } | |
786de7eb | 606 | |
44cec300 JL |
607 | default: |
608 | defs_to_varying (insn); | |
609 | } | |
610 | ||
611 | if (simplified && GET_CODE (simplified) == CONST_INT) | |
612 | { | |
613 | if (values[REGNO (dest)].lattice_val != CONSTANT | |
614 | || values[REGNO (dest)].const_value != simplified) | |
615 | SET_BIT (ssa_edges, REGNO (dest)); | |
616 | ||
617 | values[REGNO (dest)].lattice_val = CONSTANT; | |
618 | values[REGNO (dest)].const_value = simplified; | |
619 | } | |
620 | else | |
786de7eb | 621 | defs_to_varying (insn); |
44cec300 JL |
622 | } |
623 | } | |
624 | ||
625 | /* Iterate over the FLOW_EDGES work list. Simulate the target block | |
626 | for each edge. */ | |
627 | static void | |
2c1ed626 | 628 | examine_flow_edges () |
44cec300 JL |
629 | { |
630 | while (flow_edges != NULL) | |
631 | { | |
632 | basic_block succ_block; | |
633 | rtx curr_phi_node; | |
634 | ||
635 | /* Pull the next block to simulate off the worklist. */ | |
636 | succ_block = flow_edges->dest; | |
637 | flow_edges = edge_info[EIE (flow_edges->src, flow_edges->dest)]; | |
638 | ||
639 | /* There is nothing to do for the exit block. */ | |
640 | if (succ_block == EXIT_BLOCK_PTR) | |
641 | continue; | |
642 | ||
643 | /* Always simulate PHI nodes, even if we have simulated this block | |
644 | before. Note that all PHI nodes are consecutive within a block. */ | |
af5c573a | 645 | for (curr_phi_node = first_insn_after_basic_block_note (succ_block); |
44cec300 JL |
646 | PHI_NODE_P (curr_phi_node); |
647 | curr_phi_node = NEXT_INSN (curr_phi_node)) | |
648 | visit_phi_node (curr_phi_node, succ_block); | |
649 | ||
650 | /* If this is the first time we've simulated this block, then we | |
651 | must simulate each of its insns. */ | |
0b17ab2f | 652 | if (!TEST_BIT (executable_blocks, succ_block->index)) |
44cec300 JL |
653 | { |
654 | rtx currinsn; | |
655 | edge succ_edge = succ_block->succ; | |
656 | ||
657 | /* Note that we have simulated this block. */ | |
0b17ab2f | 658 | SET_BIT (executable_blocks, succ_block->index); |
44cec300 JL |
659 | |
660 | /* Simulate each insn within the block. */ | |
661 | currinsn = succ_block->head; | |
662 | while (currinsn != succ_block->end) | |
663 | { | |
664 | if (INSN_P (currinsn)) | |
665 | visit_expression (currinsn, succ_block); | |
666 | ||
667 | currinsn = NEXT_INSN (currinsn); | |
668 | } | |
786de7eb | 669 | |
44cec300 JL |
670 | /* Don't forget the last insn in the block. */ |
671 | if (INSN_P (currinsn)) | |
672 | visit_expression (currinsn, succ_block); | |
786de7eb | 673 | |
44cec300 JL |
674 | /* If we haven't looked at the next block, and it has a |
675 | single successor, add it onto the worklist. This is because | |
676 | if we only have one successor, we know it gets executed, | |
2d76cb1a | 677 | so we don't have to wait for cprop to tell us. */ |
44cec300 JL |
678 | if (succ_edge != NULL |
679 | && succ_edge->succ_next == NULL | |
680 | && !TEST_BIT (executable_edges, | |
681 | EIE (succ_edge->src, succ_edge->dest))) | |
682 | { | |
683 | SET_BIT (executable_edges, | |
684 | EIE (succ_edge->src, succ_edge->dest)); | |
685 | edge_info[EIE (succ_edge->src, succ_edge->dest)] = flow_edges; | |
686 | flow_edges = succ_edge; | |
687 | } | |
688 | } | |
689 | } | |
690 | } | |
691 | ||
692 | /* Follow the def-use chains for each definition on the worklist and | |
693 | simulate the uses of the definition. */ | |
694 | ||
695 | static void | |
696 | follow_def_use_chains () | |
697 | { | |
698 | /* Iterate over all the entries on the SSA_EDGES worklist. */ | |
699 | while (sbitmap_first_set_bit (ssa_edges) >= 0) | |
700 | { | |
701 | int member; | |
702 | struct df_link *curruse; | |
703 | ||
704 | /* Pick an entry off the worklist (it does not matter which | |
705 | entry we pick). */ | |
786de7eb | 706 | member = sbitmap_first_set_bit (ssa_edges); |
44cec300 JL |
707 | RESET_BIT (ssa_edges, member); |
708 | ||
709 | /* Iterate through all the uses of this entry. */ | |
710 | for (curruse = df_analyzer->regs[member].uses; curruse; | |
711 | curruse = curruse->next) | |
712 | { | |
713 | rtx useinsn; | |
714 | ||
715 | useinsn = DF_REF_INSN (curruse->ref); | |
716 | if (PHI_NODE_P (useinsn)) | |
717 | { | |
718 | if (TEST_BIT (executable_blocks, BLOCK_NUM (useinsn))) | |
719 | visit_phi_node (useinsn, BLOCK_FOR_INSN (useinsn)); | |
786de7eb | 720 | } |
44cec300 JL |
721 | else |
722 | { | |
723 | if (TEST_BIT (executable_blocks, BLOCK_NUM (useinsn))) | |
724 | visit_expression (useinsn, BLOCK_FOR_INSN (useinsn)); | |
725 | } | |
726 | } | |
727 | } | |
728 | } | |
729 | ||
730 | /* Examine each edge to see if we were able to prove any were | |
786de7eb | 731 | not executable. |
44cec300 JL |
732 | |
733 | If an edge is not executable, then we can remove its alternative | |
734 | in PHI nodes as the destination of the edge, we can simplify the | |
735 | conditional branch at the source of the edge, and we can remove | |
736 | the edge from the CFG. Note we do not delete unreachable blocks | |
737 | yet as the DF analyzer can not deal with that yet. */ | |
738 | static void | |
739 | optimize_unexecutable_edges (edges, executable_edges) | |
740 | struct edge_list *edges; | |
741 | sbitmap executable_edges; | |
742 | { | |
743 | int i; | |
e0082a72 | 744 | basic_block bb; |
44cec300 JL |
745 | |
746 | for (i = 0; i < NUM_EDGES (edges); i++) | |
747 | { | |
748 | if (!TEST_BIT (executable_edges, i)) | |
749 | { | |
750 | edge edge = INDEX_EDGE (edges, i); | |
751 | ||
752 | if (edge->flags & EDGE_ABNORMAL) | |
753 | continue; | |
754 | ||
755 | /* We found an edge that is not executable. First simplify | |
756 | the PHI nodes in the target block. */ | |
757 | if (edge->dest != EXIT_BLOCK_PTR) | |
758 | { | |
af5c573a | 759 | rtx insn = first_insn_after_basic_block_note (edge->dest); |
44cec300 JL |
760 | |
761 | while (PHI_NODE_P (insn)) | |
762 | { | |
763 | remove_phi_alternative (PATTERN (insn), edge->src); | |
978cf2fc DB |
764 | if (rtl_dump_file) |
765 | fprintf (rtl_dump_file, | |
0b17ab2f RH |
766 | "Removing alternative for bb %d of phi %d\n", |
767 | edge->src->index, SSA_NAME (PATTERN (insn))); | |
44cec300 JL |
768 | insn = NEXT_INSN (insn); |
769 | } | |
770 | } | |
978cf2fc DB |
771 | if (rtl_dump_file) |
772 | fprintf (rtl_dump_file, | |
773 | "Removing unexecutable edge from %d to %d\n", | |
0b17ab2f | 774 | edge->src->index, edge->dest->index); |
44cec300 JL |
775 | /* Since the edge was not executable, remove it from the CFG. */ |
776 | remove_edge (edge); | |
777 | } | |
778 | } | |
779 | ||
780 | /* We have removed all the unexecutable edges from the CFG. Fix up | |
781 | the conditional jumps at the end of any affected block. | |
782 | ||
783 | We have three cases to deal with: | |
784 | ||
785 | a. Both outgoing edges are not executable. This happens if the | |
786 | source block is not reachable. We will deal with this by | |
787 | deleting all the insns in the block later. | |
788 | ||
789 | b. The fall-thru edge is not executable. In this case we | |
790 | change the conditional jump into an unconditional jump and | |
791 | add a BARRIER after the unconditional jump. Note that since | |
792 | we are working on generic RTL we can change the jump in-place | |
793 | instead of dealing with the headache of reemitting the jump. | |
794 | ||
795 | c. The branch taken edge is not executable. In this case | |
796 | we turn the jump into (set (pc) (pc)) which is a nop-jump | |
797 | and we will remove the unrecognizable insn later. | |
798 | ||
799 | In cases B & C we are removing uses of registers, so make sure | |
800 | to note those changes for the DF analyzer. */ | |
801 | ||
e0082a72 | 802 | FOR_EACH_BB (bb) |
44cec300 | 803 | { |
44cec300 JL |
804 | rtx insn = bb->end; |
805 | edge edge = bb->succ; | |
806 | ||
807 | /* If we have no predecessors, then this block is unreachable and | |
808 | will be cleaned up when we remove unreachable blocks. */ | |
809 | if (bb->pred == NULL || GET_CODE (insn) != JUMP_INSN) | |
810 | continue; | |
811 | ||
812 | /* If this block ends in a conditional jump, but only has one | |
813 | successor, then the jump needs adjustment. */ | |
814 | if (condjump_p (insn) && ! simplejump_p (insn) | |
815 | && bb->succ && bb->succ->succ_next == NULL) | |
816 | { | |
817 | /* If the fallthru edge is the executable edge, then turn | |
818 | this jump into a nop jump, otherwise make it an unconditinoal | |
819 | jump to its target. */ | |
820 | if (edge->flags & EDGE_FALLTHRU) | |
821 | { | |
822 | PUT_CODE (insn, NOTE); | |
823 | NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; | |
824 | } | |
825 | else | |
826 | { | |
827 | SET_SRC (PATTERN (insn)) = gen_rtx_LABEL_REF (Pmode, | |
828 | JUMP_LABEL (insn)); | |
829 | emit_barrier_after (insn); | |
830 | INSN_CODE (insn) = -1; | |
831 | } | |
832 | ||
833 | /* Inform the DF analyzer that this insn changed. */ | |
834 | df_insn_modify (df_analyzer, BLOCK_FOR_INSN (insn), insn); | |
835 | } | |
836 | } | |
837 | } | |
786de7eb | 838 | |
44cec300 JL |
839 | /* Perform substitution of known values for pseudo registers. |
840 | ||
841 | ??? Note we do not do simplifications or constant folding here, it | |
842 | is unlikely that any significant simplifications can be done here | |
843 | anyway. Consider that if the simplification would result in an | |
844 | expression that produces a constant value that the value would | |
845 | have been discovered and recorded already. | |
786de7eb | 846 | |
44cec300 JL |
847 | We perform two transformations. First, we initialize pseudos to their |
848 | known constant values at their definition point. Second, we try to | |
849 | replace uses with the known constant value. */ | |
850 | ||
851 | static void | |
852 | ssa_ccp_substitute_constants () | |
853 | { | |
af5c573a | 854 | unsigned int i; |
44cec300 JL |
855 | |
856 | for (i = FIRST_PSEUDO_REGISTER; i < VARRAY_SIZE (ssa_definition); i++) | |
857 | { | |
858 | if (values[i].lattice_val == CONSTANT) | |
859 | { | |
2041cde4 JJ |
860 | rtx def = VARRAY_RTX (ssa_definition, i); |
861 | rtx set = single_set (def); | |
44cec300 JL |
862 | struct df_link *curruse; |
863 | ||
864 | if (! set) | |
865 | continue; | |
866 | ||
867 | /* Do not try to simplify PHI nodes down to a constant load. | |
868 | That will be done later as we translate out of SSA. Also, | |
869 | doing that here could violate the rule that all PHI nodes | |
83c66c1e DN |
870 | are consecutive at the start of the basic block. |
871 | ||
872 | Don't do anything to nodes that were already sets to | |
873 | constants. */ | |
874 | if (! PHI_NODE_P (def) | |
875 | && ! ((GET_CODE (def) == INSN | |
876 | && GET_CODE (SET_SRC (set)) == CONST_INT))) | |
44cec300 | 877 | { |
978cf2fc DB |
878 | if (rtl_dump_file) |
879 | fprintf (rtl_dump_file, | |
880 | "Register %d is now set to a constant\n", | |
881 | SSA_NAME (PATTERN (def))); | |
44cec300 JL |
882 | SET_SRC (set) = values[i].const_value; |
883 | INSN_CODE (def) = -1; | |
884 | df_insn_modify (df_analyzer, BLOCK_FOR_INSN (def), def); | |
885 | } | |
886 | ||
887 | /* Iterate through all the uses of this entry and try replacements | |
888 | there too. Note it is not particularly profitable to try | |
889 | and fold/simplify expressions here as most of the common | |
890 | cases were handled above. */ | |
891 | for (curruse = df_analyzer->regs[i].uses; | |
892 | curruse; | |
893 | curruse = curruse->next) | |
894 | { | |
895 | rtx useinsn; | |
896 | ||
897 | useinsn = DF_REF_INSN (curruse->ref); | |
898 | ||
899 | if (!INSN_DELETED_P (useinsn) | |
900 | && ! (GET_CODE (useinsn) == NOTE | |
901 | && NOTE_LINE_NUMBER (useinsn) == NOTE_INSN_DELETED) | |
902 | && (GET_CODE (useinsn) == INSN | |
903 | || GET_CODE (useinsn) == JUMP_INSN)) | |
904 | { | |
786de7eb | 905 | |
978cf2fc | 906 | if (validate_replace_src (regno_reg_rtx [i], |
44cec300 | 907 | values[i].const_value, |
978cf2fc DB |
908 | useinsn)) |
909 | { | |
910 | if (rtl_dump_file) | |
786de7eb | 911 | fprintf (rtl_dump_file, |
978cf2fc DB |
912 | "Register %d in insn %d replaced with constant\n", |
913 | i, INSN_UID (useinsn)); | |
914 | INSN_CODE (useinsn) = -1; | |
915 | df_insn_modify (df_analyzer, | |
916 | BLOCK_FOR_INSN (useinsn), | |
917 | useinsn); | |
918 | } | |
786de7eb | 919 | |
44cec300 | 920 | } |
44cec300 JL |
921 | } |
922 | } | |
923 | } | |
924 | } | |
925 | ||
926 | /* Now find all unreachable basic blocks. All the insns in those | |
927 | blocks are unreachable, so delete them and mark any necessary | |
928 | updates for the DF analyzer. */ | |
929 | ||
930 | static void | |
931 | ssa_ccp_df_delete_unreachable_insns () | |
932 | { | |
e0082a72 | 933 | basic_block b; |
44cec300 JL |
934 | |
935 | /* Use the CFG to find all the reachable blocks. */ | |
936 | find_unreachable_blocks (); | |
937 | ||
938 | /* Now we know what blocks are not reachable. Mark all the insns | |
939 | in those blocks as deleted for the DF analyzer. We'll let the | |
940 | normal flow code actually remove the unreachable blocks. */ | |
e0082a72 | 941 | FOR_EACH_BB_REVERSE (b) |
44cec300 | 942 | { |
e0c39f1b | 943 | if (!(b->flags & BB_REACHABLE)) |
44cec300 JL |
944 | { |
945 | rtx start = b->head; | |
946 | rtx end = b->end; | |
947 | rtx tmp; | |
948 | ||
949 | /* Include any jump table following the basic block. */ | |
950 | end = b->end; | |
951 | if (GET_CODE (end) == JUMP_INSN | |
952 | && (tmp = JUMP_LABEL (end)) != NULL_RTX | |
953 | && (tmp = NEXT_INSN (tmp)) != NULL_RTX | |
954 | && GET_CODE (tmp) == JUMP_INSN | |
955 | && (GET_CODE (PATTERN (tmp)) == ADDR_VEC | |
956 | || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC)) | |
957 | end = tmp; | |
958 | ||
959 | while (1) | |
960 | { | |
961 | rtx next = NEXT_INSN (start); | |
962 | ||
963 | if (GET_CODE (start) == INSN | |
964 | || GET_CODE (start) == CALL_INSN | |
965 | || GET_CODE (start) == JUMP_INSN) | |
966 | df_insn_delete (df_analyzer, BLOCK_FOR_INSN (start), start); | |
967 | ||
968 | if (start == end) | |
969 | break; | |
970 | start = next; | |
971 | } | |
972 | } | |
973 | } | |
974 | } | |
975 | ||
976 | ||
977 | /* Main entry point for SSA Conditional Constant Propagation. | |
978 | ||
979 | Long term it should accept as input the specific flow graph to | |
980 | operate on so that it can be called for sub-graphs. */ | |
981 | ||
982 | void | |
2c1ed626 | 983 | ssa_const_prop () |
44cec300 JL |
984 | { |
985 | unsigned int i; | |
986 | edge curredge; | |
987 | ||
988 | /* We need alias analysis (for what?) */ | |
989 | init_alias_analysis (); | |
990 | ||
991 | df_analyzer = df_init (); | |
992 | df_analyse (df_analyzer, 0, | |
993 | DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS); | |
994 | ||
44cec300 JL |
995 | /* Perform a quick and dirty dead code elimination pass. This is not |
996 | as aggressive as it could be, but it's good enough to clean up a | |
997 | lot of unwanted junk and it is fast. */ | |
998 | ssa_fast_dce (df_analyzer); | |
999 | ||
1000 | /* Build an edge list from the CFG. */ | |
1001 | edges = create_edge_list (); | |
1002 | ||
1003 | /* Initialize the values array with everything as undefined. */ | |
1004 | values = (value *) xmalloc (VARRAY_SIZE (ssa_definition) * sizeof (value)); | |
1005 | for (i = 0; i < VARRAY_SIZE (ssa_definition); i++) | |
1006 | { | |
1007 | if (i < FIRST_PSEUDO_REGISTER) | |
786de7eb | 1008 | values[i].lattice_val = VARYING; |
44cec300 JL |
1009 | else |
1010 | values[i].lattice_val = UNDEFINED; | |
1011 | values[i].const_value = NULL; | |
1012 | } | |
1013 | ||
1014 | ssa_edges = sbitmap_alloc (VARRAY_SIZE (ssa_definition)); | |
1015 | sbitmap_zero (ssa_edges); | |
1016 | ||
d55bc081 | 1017 | executable_blocks = sbitmap_alloc (last_basic_block); |
44cec300 JL |
1018 | sbitmap_zero (executable_blocks); |
1019 | ||
1020 | executable_edges = sbitmap_alloc (NUM_EDGES (edges)); | |
1021 | sbitmap_zero (executable_edges); | |
1022 | ||
1023 | edge_info = (edge *) xmalloc (NUM_EDGES (edges) * sizeof (edge)); | |
1024 | flow_edges = ENTRY_BLOCK_PTR->succ; | |
1025 | ||
1026 | /* Add the successors of the entry block to the edge worklist. That | |
1027 | is enough of a seed to get SSA-CCP started. */ | |
1028 | for (curredge = ENTRY_BLOCK_PTR->succ; curredge; | |
1029 | curredge = curredge->succ_next) | |
1030 | { | |
1031 | int index = EIE (curredge->src, curredge->dest); | |
1032 | SET_BIT (executable_edges, index); | |
1033 | edge_info[index] = curredge->succ_next; | |
1034 | } | |
1035 | ||
1036 | /* Iterate until until the worklists are empty. */ | |
1037 | do | |
1038 | { | |
1039 | examine_flow_edges (); | |
1040 | follow_def_use_chains (); | |
1041 | } | |
1042 | while (flow_edges != NULL); | |
1043 | ||
1044 | /* Now perform substitutions based on the known constant values. */ | |
1045 | ssa_ccp_substitute_constants (); | |
1046 | ||
1047 | /* Remove unexecutable edges from the CFG and make appropriate | |
1048 | adjustments to PHI nodes. */ | |
1049 | optimize_unexecutable_edges (edges, executable_edges); | |
1050 | ||
1051 | /* Now remove all unreachable insns and update the DF information. | |
1052 | as appropriate. */ | |
1053 | ssa_ccp_df_delete_unreachable_insns (); | |
1054 | ||
1055 | #if 0 | |
1056 | /* The DF analyzer expects the number of blocks to remain constant, | |
1057 | so we can't remove unreachable blocks. | |
1058 | ||
1059 | Code the DF analyzer calls expects there to be no unreachable | |
1060 | blocks in the CFG. So we can't leave unreachable blocks in the | |
1061 | CFG. | |
1062 | ||
1063 | So, there is no way to do an incremental update of the DF data | |
1064 | at this point. */ | |
1065 | df_analyse (df_analyzer, 0, | |
1066 | DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS); | |
1067 | #endif | |
1068 | ||
1069 | /* Clean up any dead code exposed by SSA-CCP, do this after updating | |
1070 | the dataflow information! */ | |
1071 | ssa_fast_dce (df_analyzer); | |
1072 | ||
1073 | free (values); | |
1074 | values = NULL; | |
1075 | ||
1076 | free (edge_info); | |
1077 | edge_info = NULL; | |
1078 | ||
1079 | sbitmap_free (executable_blocks); | |
1080 | executable_blocks = NULL; | |
1081 | ||
c96bd05e DN |
1082 | sbitmap_free (ssa_edges); |
1083 | ssa_edges = NULL; | |
786de7eb | 1084 | |
44cec300 JL |
1085 | free_edge_list (edges); |
1086 | edges = NULL; | |
1087 | ||
1088 | sbitmap_free (executable_edges); | |
1089 | executable_edges = NULL; | |
1090 | ||
1091 | df_finish (df_analyzer); | |
1092 | end_alias_analysis (); | |
1093 | } | |
1094 | ||
1095 | static int | |
1096 | mark_references (current_rtx, data) | |
1097 | rtx *current_rtx; | |
1098 | void *data; | |
1099 | { | |
1100 | rtx x = *current_rtx; | |
cf403648 | 1101 | sbitmap worklist = (sbitmap) data; |
44cec300 JL |
1102 | |
1103 | if (x == NULL_RTX) | |
1104 | return 0; | |
1105 | ||
1106 | if (GET_CODE (x) == SET) | |
1107 | { | |
1108 | rtx dest = SET_DEST (x); | |
1109 | ||
1110 | if (GET_CODE (dest) == STRICT_LOW_PART | |
1111 | || GET_CODE (dest) == SUBREG | |
1112 | || GET_CODE (dest) == SIGN_EXTRACT | |
1113 | || GET_CODE (dest) == ZERO_EXTRACT) | |
1114 | { | |
1115 | rtx reg; | |
1116 | ||
1117 | reg = dest; | |
1118 | ||
1119 | while (GET_CODE (reg) == STRICT_LOW_PART | |
1120 | || GET_CODE (reg) == SUBREG | |
1121 | || GET_CODE (reg) == SIGN_EXTRACT | |
1122 | || GET_CODE (reg) == ZERO_EXTRACT) | |
1123 | reg = XEXP (reg, 0); | |
1124 | ||
1125 | if (GET_CODE (reg) == REG) | |
1126 | SET_BIT (worklist, REGNO (reg)); | |
1127 | } | |
1128 | ||
1129 | if (GET_CODE (dest) == REG) | |
1130 | { | |
1131 | for_each_rtx (&SET_SRC (x), mark_references, data); | |
1132 | return -1; | |
1133 | } | |
1134 | ||
1135 | return 0; | |
1136 | } | |
1137 | else if (GET_CODE (x) == REG) | |
1138 | { | |
1139 | SET_BIT (worklist, REGNO (x)); | |
1140 | return -1; | |
1141 | } | |
1142 | else if (GET_CODE (x) == CLOBBER) | |
1143 | return -1; | |
1144 | else | |
1145 | return 0; | |
1146 | } | |
1147 | ||
1148 | static void | |
1149 | ssa_fast_dce (df) | |
1150 | struct df *df; | |
1151 | { | |
1152 | sbitmap worklist = sbitmap_alloc (VARRAY_SIZE (ssa_definition)); | |
1153 | sbitmap_ones (worklist); | |
1154 | ||
1155 | /* Iterate on the worklist until there's no definitions left to | |
1156 | examine. */ | |
1157 | while (sbitmap_first_set_bit (worklist) >= 0) | |
1158 | { | |
1159 | struct df_link *curruse; | |
1160 | int reg, found_use; | |
1161 | ||
1162 | /* Remove an item from the worklist. */ | |
1163 | reg = sbitmap_first_set_bit (worklist); | |
1164 | RESET_BIT (worklist, reg); | |
1165 | ||
1166 | /* We never consider deleting assignments to hard regs or things | |
1167 | which do not have SSA definitions, or things we have already | |
1168 | deleted, or things with unusual side effects. */ | |
1169 | if (reg < FIRST_PSEUDO_REGISTER | |
1170 | || ! VARRAY_RTX (ssa_definition, reg) | |
1171 | || INSN_DELETED_P (VARRAY_RTX (ssa_definition, reg)) | |
1172 | || (GET_CODE (VARRAY_RTX (ssa_definition, reg)) == NOTE | |
1173 | && (NOTE_LINE_NUMBER (VARRAY_RTX (ssa_definition, reg)) | |
1174 | == NOTE_INSN_DELETED)) | |
1175 | || side_effects_p (PATTERN (VARRAY_RTX (ssa_definition, reg)))) | |
1176 | continue; | |
786de7eb | 1177 | |
44cec300 JL |
1178 | /* Iterate over the uses of this register. If we can not find |
1179 | any uses that have not been deleted, then the definition of | |
1180 | this register is dead. */ | |
1181 | found_use = 0; | |
1182 | for (curruse = df->regs[reg].uses; curruse; curruse = curruse->next) | |
1183 | { | |
44cec300 JL |
1184 | if (curruse->ref |
1185 | && DF_REF_INSN (curruse->ref) | |
1186 | && ! INSN_DELETED_P (DF_REF_INSN (curruse->ref)) | |
1187 | && ! (GET_CODE (DF_REF_INSN (curruse->ref)) == NOTE | |
1188 | && (NOTE_LINE_NUMBER (DF_REF_INSN (curruse->ref)) | |
1189 | == NOTE_INSN_DELETED)) | |
1190 | && DF_REF_INSN (curruse->ref) != VARRAY_RTX (ssa_definition, reg)) | |
1191 | { | |
1192 | found_use = 1; | |
1193 | break; | |
1194 | } | |
1195 | } | |
1196 | ||
1197 | /* If we did not find a use of this register, then the definition | |
1198 | of this register is dead. */ | |
786de7eb | 1199 | |
44cec300 JL |
1200 | if (! found_use) |
1201 | { | |
1202 | rtx def = VARRAY_RTX (ssa_definition, reg); | |
1203 | ||
1204 | /* Add all registers referenced by INSN to the work | |
1205 | list. */ | |
1206 | for_each_rtx (&PATTERN (def), mark_references, worklist); | |
1207 | ||
1208 | /* Inform the analyzer that this insn is going to be | |
1209 | deleted. */ | |
1210 | df_insn_delete (df, BLOCK_FOR_INSN (def), def); | |
1211 | ||
44cec300 JL |
1212 | VARRAY_RTX (ssa_definition, reg) = NULL; |
1213 | } | |
1214 | } | |
1a9485cf JL |
1215 | |
1216 | sbitmap_free (worklist); | |
d094b0b3 JL |
1217 | |
1218 | /* Update the use-def chains in the df_analyzer as needed. */ | |
1219 | df_analyse (df_analyzer, 0, | |
786de7eb | 1220 | DF_RD_CHAIN | DF_RU_CHAIN | DF_REG_INFO | DF_HARD_REGS); |
44cec300 | 1221 | } |