]>
Commit | Line | Data |
---|---|---|
e48ba7af | 1 | /* Generic partial redundancy elimination with lazy code motion |
2 | support. | |
3 | Copyright (C) 1998 Free Software Foundation, Inc. | |
4 | ||
5 | This file is part of GNU CC. | |
6 | ||
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) | |
10 | any later version. | |
11 | ||
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. | |
16 | ||
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. */ | |
21 | ||
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: | |
25 | ||
26 | * Traditional partial redundancy elimination. | |
27 | ||
28 | * Placement of caller/caller register save/restores. | |
29 | ||
30 | * Load/store motion. | |
31 | ||
32 | * Copy motion. | |
33 | ||
34 | * Conversion of flat register files to a stacked register | |
35 | model. | |
36 | ||
37 | * Dead load/store elimination. | |
38 | ||
39 | These routines accept as input: | |
40 | ||
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 | |
44 | or functions. | |
45 | ||
46 | * Bitmaps of local properties (computed, transparent and | |
47 | anticipatable expressions). | |
48 | ||
49 | The output of these routines is bitmap of redundant computations | |
50 | and a bitmap of optimal placement points. */ | |
51 | ||
52 | ||
53 | #include "config.h" | |
54 | #include "system.h" | |
55 | ||
56 | #include "rtl.h" | |
57 | #include "regs.h" | |
58 | #include "hard-reg-set.h" | |
59 | #include "flags.h" | |
60 | #include "real.h" | |
61 | #include "insn-config.h" | |
62 | #include "recog.h" | |
63 | #include "basic-block.h" | |
64 | ||
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 *, | |
70 | sbitmap *, 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 *)); | |
80 | ||
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 *, | |
85 | sbitmap *, sbitmap *, | |
86 | sbitmap *, sbitmap *)); | |
87 | static void compute_earlierinout PROTO ((int, int, int_list_ptr *, sbitmap *, | |
88 | sbitmap *, 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 *)); | |
94 | ||
95 | /* Given local properties TRANSP, ANTLOC, return the redundant and optimal | |
96 | computation points for expressions. | |
97 | ||
98 | To reduce overall memory consumption, we allocate memory immediately | |
99 | before its needed and deallocate it as soon as possible. */ | |
100 | void | |
101 | pre_lcm (n_blocks, n_exprs, s_preds, s_succs, transp, | |
102 | antloc, redundant, optimal) | |
103 | int n_blocks; | |
104 | int n_exprs; | |
105 | int_list_ptr *s_preds; | |
106 | int_list_ptr *s_succs; | |
107 | sbitmap *transp; | |
108 | sbitmap *antloc; | |
109 | sbitmap *redundant; | |
110 | sbitmap *optimal; | |
111 | { | |
112 | sbitmap *antin, *antout, *earlyin, *earlyout, *delayin, *delayout; | |
113 | sbitmap *latein, *isoin, *isoout; | |
114 | ||
115 | /* Compute global anticipatability. ANTOUT is not needed except to | |
116 | compute ANTIN, so free its memory as soon as we return from | |
117 | compute_antinout. */ | |
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); | |
122 | free (antout); | |
123 | antout = NULL; | |
124 | ||
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, | |
131 | earlyin, earlyout); | |
132 | free (earlyout); | |
133 | earlyout = NULL; | |
134 | ||
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); | |
142 | free (delayout); | |
143 | delayout = NULL; | |
144 | free (antin); | |
145 | antin = NULL; | |
146 | free (earlyin); | |
147 | earlyin = NULL; | |
148 | ||
149 | /* Compute latestness. We no longer need DELAYIN after we compute | |
150 | LATEIN. */ | |
151 | latein = sbitmap_vector_alloc (n_blocks, n_exprs); | |
152 | compute_latein (n_blocks, n_exprs, s_succs, antloc, delayin, latein); | |
153 | free (delayin); | |
154 | delayin = NULL; | |
155 | ||
156 | /* Compute isolatedness. ISOIN is not needed except to compute | |
157 | ISOOUT, so free its memory as soon as we return from | |
158 | compute_isoinout. */ | |
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); | |
162 | free (isoin); | |
163 | isoin = NULL; | |
164 | ||
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); | |
168 | free (latein); | |
169 | latein = NULL; | |
170 | free (isoout); | |
171 | isoout = NULL; | |
172 | } | |
173 | ||
174 | /* Given local properties TRANSP, AVLOC, return the redundant and optimal | |
175 | computation points for expressions on the reverse flowgraph. | |
176 | ||
177 | To reduce overall memory consumption, we allocate memory immediately | |
178 | before its needed and deallocate it as soon as possible. */ | |
179 | ||
180 | void | |
181 | pre_rev_lcm (n_blocks, n_exprs, s_preds, s_succs, transp, | |
182 | avloc, redundant, optimal) | |
183 | int n_blocks; | |
184 | int n_exprs; | |
185 | int_list_ptr *s_preds; | |
186 | int_list_ptr *s_succs; | |
187 | sbitmap *transp; | |
188 | sbitmap *avloc; | |
189 | sbitmap *redundant; | |
190 | sbitmap *optimal; | |
191 | { | |
192 | sbitmap *avin, *avout, *fartherin, *fartherout, *earlierin, *earlierout; | |
193 | sbitmap *firstout, *rev_isoin, *rev_isoout; | |
194 | ||
195 | /* Compute global availability. AVIN is not needed except to | |
196 | compute AVOUT, so free its memory as soon as we return from | |
197 | compute_avinout. */ | |
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); | |
201 | free (avin); | |
202 | avin = NULL; | |
203 | ||
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); | |
211 | free (fartherin); | |
212 | fartherin = NULL; | |
213 | ||
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); | |
221 | free (earlierin); | |
222 | earlierin = NULL; | |
223 | free (avout); | |
224 | avout = NULL; | |
225 | free (fartherout); | |
226 | fartherout = NULL; | |
227 | ||
228 | /* Compute firstness. We no longer need EARLIEROUT after we compute | |
229 | FIRSTOUT. */ | |
230 | firstout = sbitmap_vector_alloc (n_blocks, n_exprs); | |
231 | compute_firstout (n_blocks, n_exprs, s_preds, avloc, earlierout, firstout); | |
232 | free (earlierout); | |
233 | earlierout = NULL; | |
234 | ||
235 | /* Compute rev_isolatedness. ISOIN is not needed except to compute | |
236 | ISOOUT, so free its memory as soon as we return from | |
237 | compute_isoinout. */ | |
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); | |
242 | free (rev_isoout); | |
243 | rev_isoout = NULL; | |
244 | ||
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); | |
248 | free (firstout); | |
249 | firstout = NULL; | |
250 | free (rev_isoin); | |
251 | rev_isoin = NULL; | |
252 | } | |
253 | ||
254 | /* Compute expression anticipatability at entrance and exit of each block. */ | |
255 | ||
256 | static void | |
257 | compute_antinout (n_blocks, s_succs, antloc, transp, antin, antout) | |
258 | int n_blocks; | |
259 | int_list_ptr *s_succs; | |
260 | sbitmap *antloc; | |
261 | sbitmap *transp; | |
262 | sbitmap *antin; | |
263 | sbitmap *antout; | |
264 | { | |
265 | int bb, changed, passes; | |
266 | sbitmap old_changed, new_changed; | |
267 | ||
268 | sbitmap_zero (antout[n_blocks - 1]); | |
269 | sbitmap_vector_ones (antin, n_blocks); | |
270 | ||
271 | old_changed = sbitmap_alloc (n_blocks); | |
272 | new_changed = sbitmap_alloc (n_blocks); | |
273 | sbitmap_ones (old_changed); | |
274 | ||
275 | passes = 0; | |
276 | changed = 1; | |
277 | while (changed) | |
278 | { | |
279 | changed = 0; | |
280 | sbitmap_zero (new_changed); | |
281 | /* We scan the blocks in the reverse order to speed up | |
282 | the convergence. */ | |
283 | for (bb = n_blocks - 1; bb >= 0; bb--) | |
284 | { | |
285 | int_list_ptr ps; | |
286 | ||
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) | |
290 | { | |
291 | if (INT_LIST_VAL (ps) == EXIT_BLOCK | |
292 | || INT_LIST_VAL (ps) == ENTRY_BLOCK) | |
293 | break; | |
294 | ||
295 | if (TEST_BIT (old_changed, INT_LIST_VAL (ps)) | |
296 | || TEST_BIT (new_changed, INT_LIST_VAL (ps))) | |
297 | break; | |
298 | } | |
299 | ||
300 | if (!ps) | |
301 | continue; | |
302 | ||
303 | if (bb != n_blocks - 1) | |
304 | sbitmap_intersect_of_successors (antout[bb], antin, | |
305 | bb, s_succs); | |
306 | if (sbitmap_a_or_b_and_c (antin[bb], antloc[bb], | |
307 | transp[bb], antout[bb])) | |
308 | { | |
309 | changed = 1; | |
310 | SET_BIT (new_changed, bb); | |
311 | } | |
312 | } | |
313 | sbitmap_copy (old_changed, new_changed); | |
314 | passes++; | |
315 | } | |
316 | free (old_changed); | |
317 | free (new_changed); | |
318 | } | |
319 | ||
320 | /* Compute expression earliestness at entrance and exit of each block. | |
321 | ||
322 | From Advanced Compiler Design and Implementation pp411. | |
323 | ||
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. */ | |
328 | ||
329 | static void | |
330 | compute_earlyinout (n_blocks, n_exprs, s_preds, transp, antin, | |
331 | earlyin, earlyout) | |
332 | int n_blocks; | |
333 | int n_exprs; | |
334 | int_list_ptr *s_preds; | |
335 | sbitmap *transp; | |
336 | sbitmap *antin; | |
337 | sbitmap *earlyin; | |
338 | sbitmap *earlyout; | |
339 | { | |
340 | int bb, changed, passes; | |
341 | sbitmap temp_bitmap; | |
342 | sbitmap old_changed, new_changed; | |
343 | ||
344 | temp_bitmap = sbitmap_alloc (n_exprs); | |
345 | ||
346 | sbitmap_vector_zero (earlyout, n_blocks); | |
347 | sbitmap_ones (earlyin[0]); | |
348 | ||
349 | old_changed = sbitmap_alloc (n_blocks); | |
350 | new_changed = sbitmap_alloc (n_blocks); | |
351 | sbitmap_ones (old_changed); | |
352 | ||
353 | passes = 0; | |
354 | changed = 1; | |
355 | while (changed) | |
356 | { | |
357 | changed = 0; | |
358 | sbitmap_zero (new_changed); | |
359 | for (bb = 0; bb < n_blocks; bb++) | |
360 | { | |
361 | int_list_ptr ps; | |
362 | ||
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) | |
366 | { | |
367 | if (INT_LIST_VAL (ps) == EXIT_BLOCK | |
368 | || INT_LIST_VAL (ps) == ENTRY_BLOCK) | |
369 | break; | |
370 | ||
371 | if (TEST_BIT (old_changed, INT_LIST_VAL (ps)) | |
372 | || TEST_BIT (new_changed, INT_LIST_VAL (ps))) | |
373 | break; | |
374 | } | |
375 | ||
376 | if (!ps) | |
377 | continue; | |
378 | ||
379 | if (bb != 0) | |
380 | sbitmap_union_of_predecessors (earlyin[bb], earlyout, | |
381 | bb, s_preds); | |
382 | sbitmap_not (temp_bitmap, transp[bb]); | |
383 | if (sbitmap_union_of_diff (earlyout[bb], temp_bitmap, | |
384 | earlyin[bb], antin[bb])) | |
385 | { | |
386 | changed = 1; | |
387 | SET_BIT (new_changed, bb); | |
388 | } | |
389 | } | |
390 | sbitmap_copy (old_changed, new_changed); | |
391 | passes++; | |
392 | } | |
393 | free (old_changed); | |
394 | free (new_changed); | |
395 | free (temp_bitmap); | |
396 | } | |
397 | ||
398 | /* Compute expression delayedness at entrance and exit of each block. | |
399 | ||
400 | From Advanced Compiler Design and Implementation pp411. | |
401 | ||
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. */ | |
405 | ||
406 | static void | |
407 | compute_delayinout (n_blocks, n_exprs, s_preds, antloc, | |
408 | antin, earlyin, delayin, delayout) | |
409 | int n_blocks; | |
410 | int n_exprs; | |
411 | int_list_ptr *s_preds; | |
412 | sbitmap *antloc; | |
413 | sbitmap *antin; | |
414 | sbitmap *earlyin; | |
415 | sbitmap *delayin; | |
416 | sbitmap *delayout; | |
417 | { | |
418 | int bb, changed, passes; | |
419 | sbitmap *anti_and_early; | |
420 | sbitmap temp_bitmap; | |
421 | ||
422 | temp_bitmap = sbitmap_alloc (n_exprs); | |
423 | ||
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]); | |
429 | ||
430 | sbitmap_vector_zero (delayout, n_blocks); | |
431 | sbitmap_copy (delayin[0], anti_and_early[0]); | |
432 | ||
433 | passes = 0; | |
434 | changed = 1; | |
435 | while (changed) | |
436 | { | |
437 | changed = 0; | |
438 | for (bb = 0; bb < n_blocks; bb++) | |
439 | { | |
440 | if (bb != 0) | |
441 | { | |
442 | sbitmap_intersect_of_predecessors (temp_bitmap, delayout, | |
443 | bb, s_preds); | |
444 | changed |= sbitmap_a_or_b (delayin[bb], | |
445 | anti_and_early[bb], | |
446 | temp_bitmap); | |
447 | } | |
448 | sbitmap_not (temp_bitmap, antloc[bb]); | |
449 | changed |= sbitmap_a_and_b (delayout[bb], | |
450 | temp_bitmap, | |
451 | delayin[bb]); | |
452 | } | |
453 | passes++; | |
454 | } | |
455 | ||
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); | |
459 | free (temp_bitmap); | |
460 | } | |
461 | ||
462 | /* Compute latestness. | |
463 | ||
464 | From Advanced Compiler Design and Implementation pp412. | |
465 | ||
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. */ | |
471 | ||
472 | static void | |
473 | compute_latein (n_blocks, n_exprs, s_succs, antloc, delayin, latein) | |
474 | int n_blocks; | |
475 | int n_exprs; | |
476 | int_list_ptr *s_succs; | |
477 | sbitmap *antloc; | |
478 | sbitmap *delayin; | |
479 | sbitmap *latein; | |
480 | { | |
481 | int bb; | |
482 | sbitmap temp_bitmap; | |
483 | ||
484 | temp_bitmap = sbitmap_alloc (n_exprs); | |
485 | ||
486 | for (bb = 0; bb < n_blocks; bb++) | |
487 | { | |
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) | |
491 | { | |
492 | sbitmap_intersect_of_successors (temp_bitmap, delayin, | |
493 | bb, s_succs); | |
494 | sbitmap_not (temp_bitmap, temp_bitmap); | |
495 | } | |
496 | else | |
497 | sbitmap_ones (temp_bitmap); | |
498 | sbitmap_a_and_b_or_c (latein[bb], delayin[bb], | |
499 | antloc[bb], temp_bitmap); | |
500 | } | |
501 | free (temp_bitmap); | |
502 | } | |
503 | ||
504 | /* Compute isolated. | |
505 | ||
506 | From Advanced Compiler Design and Implementation pp413. | |
507 | ||
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. */ | |
512 | ||
513 | static void | |
514 | compute_isoinout (n_blocks, s_succs, antloc, latein, isoin, isoout) | |
515 | int n_blocks; | |
516 | int_list_ptr *s_succs; | |
517 | sbitmap *antloc; | |
518 | sbitmap *latein; | |
519 | sbitmap *isoin; | |
520 | sbitmap *isoout; | |
521 | { | |
522 | int bb, changed, passes; | |
523 | ||
524 | sbitmap_vector_zero (isoin, n_blocks); | |
525 | sbitmap_zero (isoout[n_blocks - 1]); | |
526 | ||
527 | passes = 0; | |
528 | changed = 1; | |
529 | while (changed) | |
530 | { | |
531 | changed = 0; | |
532 | for (bb = n_blocks - 1; bb >= 0; bb--) | |
533 | { | |
534 | if (bb != n_blocks - 1) | |
535 | sbitmap_intersect_of_successors (isoout[bb], isoin, | |
536 | bb, s_succs); | |
537 | changed |= sbitmap_union_of_diff (isoin[bb], latein[bb], | |
538 | isoout[bb], antloc[bb]); | |
539 | } | |
540 | passes++; | |
541 | } | |
542 | } | |
543 | ||
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. */ | |
547 | ||
548 | static void | |
549 | compute_optimal (n_blocks, latein, isoout, optimal) | |
550 | int n_blocks; | |
551 | sbitmap *latein; | |
552 | sbitmap *isoout; | |
553 | sbitmap *optimal; | |
554 | { | |
555 | int bb; | |
556 | ||
557 | for (bb = 0; bb < n_blocks; bb++) | |
558 | sbitmap_difference (optimal[bb], latein[bb], isoout[bb]); | |
559 | } | |
560 | ||
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 | |
563 | or latest. */ | |
564 | ||
565 | static void | |
566 | compute_redundant (n_blocks, n_exprs, antloc, latein, isoout, redundant) | |
567 | int n_blocks; | |
568 | int n_exprs; | |
569 | sbitmap *antloc; | |
570 | sbitmap *latein; | |
571 | sbitmap *isoout; | |
572 | sbitmap *redundant; | |
573 | { | |
574 | int bb; | |
575 | sbitmap temp_bitmap; | |
576 | ||
577 | temp_bitmap = sbitmap_alloc (n_exprs); | |
578 | ||
579 | for (bb = 0; bb < n_blocks; bb++) | |
580 | { | |
581 | sbitmap_a_or_b (temp_bitmap, latein[bb], isoout[bb]); | |
582 | sbitmap_difference (redundant[bb], antloc[bb], temp_bitmap); | |
583 | } | |
584 | free (temp_bitmap); | |
585 | } | |
586 | ||
587 | /* Compute expression availability at entrance and exit of each block. */ | |
588 | ||
589 | static void | |
590 | compute_avinout (n_blocks, s_preds, avloc, transp, avin, avout) | |
591 | int n_blocks; | |
592 | int_list_ptr *s_preds; | |
593 | sbitmap *avloc; | |
594 | sbitmap *transp; | |
595 | sbitmap *avin; | |
596 | sbitmap *avout; | |
597 | { | |
598 | int bb, changed, passes; | |
599 | ||
600 | sbitmap_zero (avin[0]); | |
601 | sbitmap_vector_ones (avout, n_blocks); | |
602 | ||
603 | passes = 0; | |
604 | changed = 1; | |
605 | while (changed) | |
606 | { | |
607 | changed = 0; | |
608 | for (bb = 0; bb < n_blocks; bb++) | |
609 | { | |
610 | if (bb != 0) | |
611 | sbitmap_intersect_of_predecessors (avin[bb], avout, | |
612 | bb, s_preds); | |
613 | changed |= sbitmap_a_or_b_and_c (avout[bb], avloc[bb], | |
614 | transp[bb], avin[bb]); | |
615 | } | |
616 | passes++; | |
617 | } | |
618 | } | |
619 | ||
620 | /* Compute expression latestness. | |
621 | ||
622 | This is effectively the same as earliestness computed on the reverse | |
623 | flow graph. */ | |
624 | ||
625 | static void | |
626 | compute_fartherinout (n_blocks, n_exprs, s_succs, | |
627 | transp, avout, fartherin, fartherout) | |
628 | int n_blocks; | |
629 | int n_exprs; | |
630 | int_list_ptr *s_succs; | |
631 | sbitmap *transp; | |
632 | sbitmap *avout; | |
633 | sbitmap *fartherin; | |
634 | sbitmap *fartherout; | |
635 | { | |
636 | int bb, changed, passes; | |
637 | sbitmap temp_bitmap; | |
638 | ||
639 | temp_bitmap = sbitmap_alloc (n_exprs); | |
640 | ||
641 | sbitmap_vector_zero (fartherin, n_blocks); | |
642 | sbitmap_ones (fartherout[n_blocks - 1]); | |
643 | ||
644 | passes = 0; | |
645 | changed = 1; | |
646 | while (changed) | |
647 | { | |
648 | changed = 0; | |
649 | for (bb = n_blocks - 1; bb >= 0; bb--) | |
650 | { | |
651 | if (bb != n_blocks - 1) | |
652 | sbitmap_union_of_successors (fartherout[bb], fartherin, | |
653 | bb, s_succs); | |
654 | sbitmap_not (temp_bitmap, transp[bb]); | |
655 | changed |= sbitmap_union_of_diff (fartherin[bb], temp_bitmap, | |
656 | fartherout[bb], avout[bb]); | |
657 | } | |
658 | passes++; | |
659 | } | |
660 | ||
661 | free (temp_bitmap); | |
662 | } | |
663 | ||
664 | /* Compute expression earlierness at entrance and exit of each block. | |
665 | ||
666 | This is effectively the same as delayedness computed on the reverse | |
667 | flow graph. */ | |
668 | ||
669 | static void | |
670 | compute_earlierinout (n_blocks, n_exprs, s_succs, avloc, | |
671 | avout, fartherout, earlierin, earlierout) | |
672 | int n_blocks; | |
673 | int n_exprs; | |
674 | int_list_ptr *s_succs; | |
675 | sbitmap *avloc; | |
676 | sbitmap *avout; | |
677 | sbitmap *fartherout; | |
678 | sbitmap *earlierin; | |
679 | sbitmap *earlierout; | |
680 | { | |
681 | int bb, changed, passes; | |
682 | sbitmap *av_and_farther; | |
683 | sbitmap temp_bitmap; | |
684 | ||
685 | temp_bitmap = sbitmap_alloc (n_exprs); | |
686 | ||
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]); | |
692 | ||
693 | sbitmap_vector_zero (earlierin, n_blocks); | |
694 | sbitmap_copy (earlierout[n_blocks - 1], av_and_farther[n_blocks - 1]); | |
695 | ||
696 | passes = 0; | |
697 | changed = 1; | |
698 | while (changed) | |
699 | { | |
700 | changed = 0; | |
701 | for (bb = n_blocks - 1; bb >= 0; bb--) | |
702 | { | |
703 | if (bb != n_blocks - 1) | |
704 | { | |
705 | sbitmap_intersect_of_successors (temp_bitmap, earlierin, | |
706 | bb, s_succs); | |
707 | changed |= sbitmap_a_or_b (earlierout[bb], | |
708 | av_and_farther[bb], | |
709 | temp_bitmap); | |
710 | } | |
711 | sbitmap_not (temp_bitmap, avloc[bb]); | |
712 | changed |= sbitmap_a_and_b (earlierin[bb], | |
713 | temp_bitmap, | |
714 | earlierout[bb]); | |
715 | } | |
716 | passes++; | |
717 | } | |
718 | ||
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); | |
722 | free (temp_bitmap); | |
723 | } | |
724 | ||
725 | /* Compute firstness. | |
726 | ||
727 | This is effectively the same as latestness computed on the reverse | |
728 | flow graph. */ | |
729 | ||
730 | static void | |
731 | compute_firstout (n_blocks, n_exprs, s_preds, avloc, earlierout, firstout) | |
732 | int n_blocks; | |
733 | int n_exprs; | |
734 | int_list_ptr *s_preds; | |
735 | sbitmap *avloc; | |
736 | sbitmap *earlierout; | |
737 | sbitmap *firstout; | |
738 | { | |
739 | int bb; | |
740 | sbitmap temp_bitmap; | |
741 | ||
742 | temp_bitmap = sbitmap_alloc (n_exprs); | |
743 | ||
744 | for (bb = 0; bb < n_blocks; bb++) | |
745 | { | |
746 | /* The first block is preceded only by the entry block; therefore, | |
747 | temp_bitmap will not be set by the following call! */ | |
748 | if (bb != 0) | |
749 | { | |
750 | sbitmap_intersect_of_predecessors (temp_bitmap, earlierout, | |
751 | bb, s_preds); | |
752 | sbitmap_not (temp_bitmap, temp_bitmap); | |
753 | } | |
754 | else | |
755 | { | |
756 | sbitmap_ones (temp_bitmap); | |
757 | } | |
758 | sbitmap_a_and_b_or_c (firstout[bb], earlierout[bb], | |
759 | avloc[bb], temp_bitmap); | |
760 | } | |
761 | free (temp_bitmap); | |
762 | } | |
763 | ||
764 | /* Compute reverse isolated. | |
765 | ||
766 | This is effectively the same as isolatedness computed on the reverse | |
767 | flow graph. */ | |
768 | ||
769 | static void | |
770 | compute_rev_isoinout (n_blocks, s_preds, avloc, firstout, | |
771 | rev_isoin, rev_isoout) | |
772 | int n_blocks; | |
773 | int_list_ptr *s_preds; | |
774 | sbitmap *avloc; | |
775 | sbitmap *firstout; | |
776 | sbitmap *rev_isoin; | |
777 | sbitmap *rev_isoout; | |
778 | { | |
779 | int bb, changed, passes; | |
780 | ||
781 | sbitmap_vector_zero (rev_isoout, n_blocks); | |
782 | sbitmap_zero (rev_isoin[0]); | |
783 | ||
784 | passes = 0; | |
785 | changed = 1; | |
786 | while (changed) | |
787 | { | |
788 | changed = 0; | |
789 | for (bb = 0; bb < n_blocks; bb++) | |
790 | { | |
791 | if (bb != 0) | |
792 | sbitmap_intersect_of_predecessors (rev_isoin[bb], rev_isoout, | |
793 | bb, s_preds); | |
794 | changed |= sbitmap_union_of_diff (rev_isoout[bb], firstout[bb], | |
795 | rev_isoin[bb], avloc[bb]); | |
796 | } | |
797 | passes++; | |
798 | } | |
799 | } |