1 /* Generic partial redundancy elimination with lazy code motion
3 Copyright (C) 1998 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
22 /* These routines are meant to be used by various optimization
23 passes which can be modeled as lazy code motion problems.
24 Including, but not limited to:
26 * Traditional partial redundancy elimination.
28 * Placement of caller/caller register save/restores.
34 * Conversion of flat register files to a stacked register
37 * Dead load/store elimination.
39 These routines accept as input:
41 * Basic block information (number of blocks, lists of
42 predecessors and successors). Note the granularity
43 does not need to be basic block, they could be statements
46 * Bitmaps of local properties (computed, transparent and
47 anticipatable expressions).
49 The output of these routines is bitmap of redundant computations
50 and a bitmap of optimal placement points. */
58 #include "hard-reg-set.h"
61 #include "insn-config.h"
63 #include "basic-block.h"
65 static void compute_antinout
PROTO ((int, int_list_ptr
*, sbitmap
*,
66 sbitmap
*, sbitmap
*, sbitmap
*));
67 static void compute_earlyinout
PROTO ((int, int, int_list_ptr
*, sbitmap
*,
68 sbitmap
*, sbitmap
*, sbitmap
*));
69 static void compute_delayinout
PROTO ((int, int, int_list_ptr
*, sbitmap
*,
71 sbitmap
*, sbitmap
*));
72 static void compute_latein
PROTO ((int, int, int_list_ptr
*, sbitmap
*,
73 sbitmap
*, sbitmap
*));
74 static void compute_isoinout
PROTO ((int, int_list_ptr
*, sbitmap
*,
75 sbitmap
*, sbitmap
*, sbitmap
*));
76 static void compute_optimal
PROTO ((int, sbitmap
*,
77 sbitmap
*, sbitmap
*));
78 static void compute_redundant
PROTO ((int, int, sbitmap
*,
79 sbitmap
*, sbitmap
*, sbitmap
*));
81 /* Similarly, but for the reversed flowgraph. */
82 static void compute_avinout
PROTO ((int, int_list_ptr
*, sbitmap
*,
83 sbitmap
*, sbitmap
*, sbitmap
*));
84 static void compute_fartherinout
PROTO ((int, int, int_list_ptr
*,
86 sbitmap
*, sbitmap
*));
87 static void compute_earlierinout
PROTO ((int, int, int_list_ptr
*, sbitmap
*,
89 sbitmap
*, sbitmap
*));
90 static void compute_firstout
PROTO ((int, int, int_list_ptr
*, sbitmap
*,
91 sbitmap
*, sbitmap
*));
92 static void compute_rev_isoinout
PROTO ((int, int_list_ptr
*, sbitmap
*,
93 sbitmap
*, sbitmap
*, sbitmap
*));
95 /* Given local properties TRANSP, ANTLOC, return the redundant and optimal
96 computation points for expressions.
98 To reduce overall memory consumption, we allocate memory immediately
99 before its needed and deallocate it as soon as possible. */
101 pre_lcm (n_blocks
, n_exprs
, s_preds
, s_succs
, transp
,
102 antloc
, redundant
, optimal
)
105 int_list_ptr
*s_preds
;
106 int_list_ptr
*s_succs
;
112 sbitmap
*antin
, *antout
, *earlyin
, *earlyout
, *delayin
, *delayout
;
113 sbitmap
*latein
, *isoin
, *isoout
;
115 /* Compute global anticipatability. ANTOUT is not needed except to
116 compute ANTIN, so free its memory as soon as we return from
118 antin
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
119 antout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
120 compute_antinout (n_blocks
, s_succs
, antloc
,
121 transp
, antin
, antout
);
125 /* Compute earliestness. EARLYOUT is not needed except to compute
126 EARLYIN, so free its memory as soon as we return from
127 compute_earlyinout. */
128 earlyin
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
129 earlyout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
130 compute_earlyinout (n_blocks
, n_exprs
, s_preds
, transp
, antin
,
135 /* Compute delayedness. DELAYOUT is not needed except to compute
136 DELAYIN, so free its memory as soon as we return from
137 compute_delayinout. We also no longer need ANTIN and EARLYIN. */
138 delayin
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
139 delayout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
140 compute_delayinout (n_blocks
, n_exprs
, s_preds
, antloc
,
141 antin
, earlyin
, delayin
, delayout
);
149 /* Compute latestness. We no longer need DELAYIN after we compute
151 latein
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
152 compute_latein (n_blocks
, n_exprs
, s_succs
, antloc
, delayin
, latein
);
156 /* Compute isolatedness. ISOIN is not needed except to compute
157 ISOOUT, so free its memory as soon as we return from
159 isoin
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
160 isoout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
161 compute_isoinout (n_blocks
, s_succs
, antloc
, latein
, isoin
, isoout
);
165 /* Now compute optimal placement points and the redundant expressions. */
166 compute_optimal (n_blocks
, latein
, isoout
, optimal
);
167 compute_redundant (n_blocks
, n_exprs
, antloc
, latein
, isoout
, redundant
);
174 /* Given local properties TRANSP, AVLOC, return the redundant and optimal
175 computation points for expressions on the reverse flowgraph.
177 To reduce overall memory consumption, we allocate memory immediately
178 before its needed and deallocate it as soon as possible. */
181 pre_rev_lcm (n_blocks
, n_exprs
, s_preds
, s_succs
, transp
,
182 avloc
, redundant
, optimal
)
185 int_list_ptr
*s_preds
;
186 int_list_ptr
*s_succs
;
192 sbitmap
*avin
, *avout
, *fartherin
, *fartherout
, *earlierin
, *earlierout
;
193 sbitmap
*firstout
, *rev_isoin
, *rev_isoout
;
195 /* Compute global availability. AVIN is not needed except to
196 compute AVOUT, so free its memory as soon as we return from
198 avin
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
199 avout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
200 compute_avinout (n_blocks
, s_preds
, avloc
, transp
, avin
, avout
);
204 /* Compute fartherness. FARTHERIN is not needed except to compute
205 FARTHEROUT, so free its memory as soon as we return from
206 compute_earlyinout. */
207 fartherin
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
208 fartherout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
209 compute_fartherinout (n_blocks
, n_exprs
, s_succs
, transp
,
210 avout
, fartherin
, fartherout
);
214 /* Compute earlierness. EARLIERIN is not needed except to compute
215 EARLIEROUT, so free its memory as soon as we return from
216 compute_delayinout. We also no longer need AVOUT and FARTHEROUT. */
217 earlierin
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
218 earlierout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
219 compute_earlierinout (n_blocks
, n_exprs
, s_succs
, avloc
,
220 avout
, fartherout
, earlierin
, earlierout
);
228 /* Compute firstness. We no longer need EARLIEROUT after we compute
230 firstout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
231 compute_firstout (n_blocks
, n_exprs
, s_preds
, avloc
, earlierout
, firstout
);
235 /* Compute rev_isolatedness. ISOIN is not needed except to compute
236 ISOOUT, so free its memory as soon as we return from
238 rev_isoin
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
239 rev_isoout
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
240 compute_rev_isoinout (n_blocks
, s_preds
, avloc
, firstout
,
241 rev_isoin
, rev_isoout
);
245 /* Now compute optimal placement points and the redundant expressions. */
246 compute_optimal (n_blocks
, firstout
, rev_isoin
, optimal
);
247 compute_redundant (n_blocks
, n_exprs
, avloc
, firstout
, rev_isoin
, redundant
);
254 /* Compute expression anticipatability at entrance and exit of each block. */
257 compute_antinout (n_blocks
, s_succs
, antloc
, transp
, antin
, antout
)
259 int_list_ptr
*s_succs
;
265 int bb
, changed
, passes
;
266 sbitmap old_changed
, new_changed
;
268 sbitmap_zero (antout
[n_blocks
- 1]);
269 sbitmap_vector_ones (antin
, n_blocks
);
271 old_changed
= sbitmap_alloc (n_blocks
);
272 new_changed
= sbitmap_alloc (n_blocks
);
273 sbitmap_ones (old_changed
);
280 sbitmap_zero (new_changed
);
281 /* We scan the blocks in the reverse order to speed up
283 for (bb
= n_blocks
- 1; bb
>= 0; bb
--)
287 /* If none of the successors of this block have changed,
288 then this block is not going to change. */
289 for (ps
= s_succs
[bb
] ; ps
; ps
= ps
->next
)
291 if (INT_LIST_VAL (ps
) == EXIT_BLOCK
292 || INT_LIST_VAL (ps
) == ENTRY_BLOCK
)
295 if (TEST_BIT (old_changed
, INT_LIST_VAL (ps
))
296 || TEST_BIT (new_changed
, INT_LIST_VAL (ps
)))
303 if (bb
!= n_blocks
- 1)
304 sbitmap_intersect_of_successors (antout
[bb
], antin
,
306 if (sbitmap_a_or_b_and_c (antin
[bb
], antloc
[bb
],
307 transp
[bb
], antout
[bb
]))
310 SET_BIT (new_changed
, bb
);
313 sbitmap_copy (old_changed
, new_changed
);
320 /* Compute expression earliestness at entrance and exit of each block.
322 From Advanced Compiler Design and Implementation pp411.
324 An expression is earliest at the entrance to basic block BB if no
325 block from entry to block BB both evaluates the expression and
326 produces the same value as evaluating it at the entry to block BB
327 does. Similarly for earlistness at basic block BB exit. */
330 compute_earlyinout (n_blocks
, n_exprs
, s_preds
, transp
, antin
,
334 int_list_ptr
*s_preds
;
340 int bb
, changed
, passes
;
342 sbitmap old_changed
, new_changed
;
344 temp_bitmap
= sbitmap_alloc (n_exprs
);
346 sbitmap_vector_zero (earlyout
, n_blocks
);
347 sbitmap_ones (earlyin
[0]);
349 old_changed
= sbitmap_alloc (n_blocks
);
350 new_changed
= sbitmap_alloc (n_blocks
);
351 sbitmap_ones (old_changed
);
358 sbitmap_zero (new_changed
);
359 for (bb
= 0; bb
< n_blocks
; bb
++)
363 /* If none of the predecessors of this block have changed,
364 then this block is not going to change. */
365 for (ps
= s_preds
[bb
] ; ps
; ps
= ps
->next
)
367 if (INT_LIST_VAL (ps
) == EXIT_BLOCK
368 || INT_LIST_VAL (ps
) == ENTRY_BLOCK
)
371 if (TEST_BIT (old_changed
, INT_LIST_VAL (ps
))
372 || TEST_BIT (new_changed
, INT_LIST_VAL (ps
)))
380 sbitmap_union_of_predecessors (earlyin
[bb
], earlyout
,
382 sbitmap_not (temp_bitmap
, transp
[bb
]);
383 if (sbitmap_union_of_diff (earlyout
[bb
], temp_bitmap
,
384 earlyin
[bb
], antin
[bb
]))
387 SET_BIT (new_changed
, bb
);
390 sbitmap_copy (old_changed
, new_changed
);
398 /* Compute expression delayedness at entrance and exit of each block.
400 From Advanced Compiler Design and Implementation pp411.
402 An expression is delayed at the entrance to BB if it is anticipatable
403 and earliest at that point and if all subsequent computations of
404 the expression are in block BB. */
407 compute_delayinout (n_blocks
, n_exprs
, s_preds
, antloc
,
408 antin
, earlyin
, delayin
, delayout
)
411 int_list_ptr
*s_preds
;
418 int bb
, changed
, passes
;
419 sbitmap
*anti_and_early
;
422 temp_bitmap
= sbitmap_alloc (n_exprs
);
424 /* This is constant throughout the flow equations below, so compute
425 it once to save time. */
426 anti_and_early
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
427 for (bb
= 0; bb
< n_blocks
; bb
++)
428 sbitmap_a_and_b (anti_and_early
[bb
], antin
[bb
], earlyin
[bb
]);
430 sbitmap_vector_zero (delayout
, n_blocks
);
431 sbitmap_copy (delayin
[0], anti_and_early
[0]);
438 for (bb
= 0; bb
< n_blocks
; bb
++)
442 sbitmap_intersect_of_predecessors (temp_bitmap
, delayout
,
444 changed
|= sbitmap_a_or_b (delayin
[bb
],
448 sbitmap_not (temp_bitmap
, antloc
[bb
]);
449 changed
|= sbitmap_a_and_b (delayout
[bb
],
456 /* We're done with this, so go ahead and free it's memory now instead
457 of waiting until the end of pre. */
458 free (anti_and_early
);
462 /* Compute latestness.
464 From Advanced Compiler Design and Implementation pp412.
466 An expression is latest at the entrance to block BB if that is an optimal
467 point for computing the expression and if on every path from block BB's
468 entrance to the exit block, any optimal computation point for the
469 expression occurs after one of the points at which the expression was
470 computed in the original flowgraph. */
473 compute_latein (n_blocks
, n_exprs
, s_succs
, antloc
, delayin
, latein
)
476 int_list_ptr
*s_succs
;
484 temp_bitmap
= sbitmap_alloc (n_exprs
);
486 for (bb
= 0; bb
< n_blocks
; bb
++)
488 /* The last block is succeeded only by the exit block; therefore,
489 temp_bitmap will not be set by the following call! */
490 if (bb
== n_blocks
- 1)
492 sbitmap_intersect_of_successors (temp_bitmap
, delayin
,
494 sbitmap_not (temp_bitmap
, temp_bitmap
);
497 sbitmap_ones (temp_bitmap
);
498 sbitmap_a_and_b_or_c (latein
[bb
], delayin
[bb
],
499 antloc
[bb
], temp_bitmap
);
506 From Advanced Compiler Design and Implementation pp413.
508 A computationally optimal placement for the evaluation of an expression
509 is defined to be isolated if and only if on every path from a successor
510 of the block in which it is computed to the exit block, every original
511 computation of the expression is preceded by the optimal placement point. */
514 compute_isoinout (n_blocks
, s_succs
, antloc
, latein
, isoin
, isoout
)
516 int_list_ptr
*s_succs
;
522 int bb
, changed
, passes
;
524 sbitmap_vector_zero (isoin
, n_blocks
);
525 sbitmap_zero (isoout
[n_blocks
- 1]);
532 for (bb
= n_blocks
- 1; bb
>= 0; bb
--)
534 if (bb
!= n_blocks
- 1)
535 sbitmap_intersect_of_successors (isoout
[bb
], isoin
,
537 changed
|= sbitmap_union_of_diff (isoin
[bb
], latein
[bb
],
538 isoout
[bb
], antloc
[bb
]);
544 /* Compute the set of expressions which have optimal computational points
545 in each basic block. This is the set of expressions that are latest, but
546 that are not isolated in the block. */
549 compute_optimal (n_blocks
, latein
, isoout
, optimal
)
557 for (bb
= 0; bb
< n_blocks
; bb
++)
558 sbitmap_difference (optimal
[bb
], latein
[bb
], isoout
[bb
]);
561 /* Compute the set of expressions that are redundant in a block. They are
562 the expressions that are used in the block and that are neither isolated
566 compute_redundant (n_blocks
, n_exprs
, antloc
, latein
, isoout
, redundant
)
577 temp_bitmap
= sbitmap_alloc (n_exprs
);
579 for (bb
= 0; bb
< n_blocks
; bb
++)
581 sbitmap_a_or_b (temp_bitmap
, latein
[bb
], isoout
[bb
]);
582 sbitmap_difference (redundant
[bb
], antloc
[bb
], temp_bitmap
);
587 /* Compute expression availability at entrance and exit of each block. */
590 compute_avinout (n_blocks
, s_preds
, avloc
, transp
, avin
, avout
)
592 int_list_ptr
*s_preds
;
598 int bb
, changed
, passes
;
600 sbitmap_zero (avin
[0]);
601 sbitmap_vector_ones (avout
, n_blocks
);
608 for (bb
= 0; bb
< n_blocks
; bb
++)
611 sbitmap_intersect_of_predecessors (avin
[bb
], avout
,
613 changed
|= sbitmap_a_or_b_and_c (avout
[bb
], avloc
[bb
],
614 transp
[bb
], avin
[bb
]);
620 /* Compute expression latestness.
622 This is effectively the same as earliestness computed on the reverse
626 compute_fartherinout (n_blocks
, n_exprs
, s_succs
,
627 transp
, avout
, fartherin
, fartherout
)
630 int_list_ptr
*s_succs
;
636 int bb
, changed
, passes
;
639 temp_bitmap
= sbitmap_alloc (n_exprs
);
641 sbitmap_vector_zero (fartherin
, n_blocks
);
642 sbitmap_ones (fartherout
[n_blocks
- 1]);
649 for (bb
= n_blocks
- 1; bb
>= 0; bb
--)
651 if (bb
!= n_blocks
- 1)
652 sbitmap_union_of_successors (fartherout
[bb
], fartherin
,
654 sbitmap_not (temp_bitmap
, transp
[bb
]);
655 changed
|= sbitmap_union_of_diff (fartherin
[bb
], temp_bitmap
,
656 fartherout
[bb
], avout
[bb
]);
664 /* Compute expression earlierness at entrance and exit of each block.
666 This is effectively the same as delayedness computed on the reverse
670 compute_earlierinout (n_blocks
, n_exprs
, s_succs
, avloc
,
671 avout
, fartherout
, earlierin
, earlierout
)
674 int_list_ptr
*s_succs
;
681 int bb
, changed
, passes
;
682 sbitmap
*av_and_farther
;
685 temp_bitmap
= sbitmap_alloc (n_exprs
);
687 /* This is constant throughout the flow equations below, so compute
688 it once to save time. */
689 av_and_farther
= sbitmap_vector_alloc (n_blocks
, n_exprs
);
690 for (bb
= 0; bb
< n_blocks
; bb
++)
691 sbitmap_a_and_b (av_and_farther
[bb
], avout
[bb
], fartherout
[bb
]);
693 sbitmap_vector_zero (earlierin
, n_blocks
);
694 sbitmap_copy (earlierout
[n_blocks
- 1], av_and_farther
[n_blocks
- 1]);
701 for (bb
= n_blocks
- 1; bb
>= 0; bb
--)
703 if (bb
!= n_blocks
- 1)
705 sbitmap_intersect_of_successors (temp_bitmap
, earlierin
,
707 changed
|= sbitmap_a_or_b (earlierout
[bb
],
711 sbitmap_not (temp_bitmap
, avloc
[bb
]);
712 changed
|= sbitmap_a_and_b (earlierin
[bb
],
719 /* We're done with this, so go ahead and free it's memory now instead
720 of waiting until the end of pre. */
721 free (av_and_farther
);
725 /* Compute firstness.
727 This is effectively the same as latestness computed on the reverse
731 compute_firstout (n_blocks
, n_exprs
, s_preds
, avloc
, earlierout
, firstout
)
734 int_list_ptr
*s_preds
;
742 temp_bitmap
= sbitmap_alloc (n_exprs
);
744 for (bb
= 0; bb
< n_blocks
; bb
++)
746 /* The first block is preceded only by the entry block; therefore,
747 temp_bitmap will not be set by the following call! */
750 sbitmap_intersect_of_predecessors (temp_bitmap
, earlierout
,
752 sbitmap_not (temp_bitmap
, temp_bitmap
);
756 sbitmap_ones (temp_bitmap
);
758 sbitmap_a_and_b_or_c (firstout
[bb
], earlierout
[bb
],
759 avloc
[bb
], temp_bitmap
);
764 /* Compute reverse isolated.
766 This is effectively the same as isolatedness computed on the reverse
770 compute_rev_isoinout (n_blocks
, s_preds
, avloc
, firstout
,
771 rev_isoin
, rev_isoout
)
773 int_list_ptr
*s_preds
;
779 int bb
, changed
, passes
;
781 sbitmap_vector_zero (rev_isoout
, n_blocks
);
782 sbitmap_zero (rev_isoin
[0]);
789 for (bb
= 0; bb
< n_blocks
; bb
++)
792 sbitmap_intersect_of_predecessors (rev_isoin
[bb
], rev_isoout
,
794 changed
|= sbitmap_union_of_diff (rev_isoout
[bb
], firstout
[bb
],
795 rev_isoin
[bb
], avloc
[bb
]);