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