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 /* Edge based LCM routines. */
66 static void compute_antinout_edge PROTO ((sbitmap *, sbitmap *,
67 sbitmap *, sbitmap *));
68 static void compute_earliest PROTO((struct edge_list *, int, sbitmap *,
69 sbitmap *, sbitmap *, sbitmap *,
71 static void compute_laterin PROTO((struct edge_list *, int, sbitmap *,
72 sbitmap *, sbitmap *, sbitmap *));
73 static void compute_insert_delete PROTO ((struct edge_list *edge_list,
74 sbitmap *, sbitmap *, sbitmap *,
75 sbitmap *, sbitmap *));
77 /* Edge based LCM routines on a reverse flowgraph. */
78 static void compute_farthest PROTO ((struct edge_list *, int, sbitmap *,
79 sbitmap *, sbitmap*, sbitmap *,
81 static void compute_nearerout PROTO((struct edge_list *, int, sbitmap *,
82 sbitmap *, sbitmap *, sbitmap *));
83 static void compute_rev_insert_delete PROTO ((struct edge_list *edge_list,
84 sbitmap *, sbitmap *, sbitmap *,
85 sbitmap *, sbitmap *));
88 /* Edge based lcm routines. */
90 /* Compute expression anticipatability at entrance and exit of each block.
91 This is done based on the flow graph, and not on the pred-succ lists.
92 Other than that, its pretty much identical to compute_antinout. */
95 compute_antinout_edge (antloc, transp, antin, antout)
101 int i, changed, passes;
102 sbitmap old_changed, new_changed;
105 sbitmap_vector_zero (antout, n_basic_blocks);
106 sbitmap_vector_ones (antin, n_basic_blocks);
108 old_changed = sbitmap_alloc (n_basic_blocks);
109 new_changed = sbitmap_alloc (n_basic_blocks);
110 sbitmap_ones (old_changed);
117 sbitmap_zero (new_changed);
119 /* We scan the blocks in the reverse order to speed up
121 for (i = n_basic_blocks - 1; i >= 0; i--)
123 basic_block bb = BASIC_BLOCK (i);
124 /* If none of the successors of this block have changed,
125 then this block is not going to change. */
126 for (e = bb->succ ; e; e = e->succ_next)
128 if (e->dest == EXIT_BLOCK_PTR)
131 if (TEST_BIT (old_changed, e->dest->index)
132 || TEST_BIT (new_changed, e->dest->index))
139 /* If an Exit blocks is the ONLY successor, its has a zero ANTIN,
140 which is the opposite of the default definition for an
141 intersection of succs definition. */
142 if (e->dest == EXIT_BLOCK_PTR && e->succ_next == NULL
143 && e->src->succ == e)
144 sbitmap_zero (antout[bb->index]);
147 sbitmap_intersection_of_succs (antout[bb->index],
152 if (sbitmap_a_or_b_and_c (antin[bb->index], antloc[bb->index],
153 transp[bb->index], antout[bb->index]))
156 SET_BIT (new_changed, bb->index);
159 sbitmap_copy (old_changed, new_changed);
167 /* Compute the earliest vector for edge based lcm. */
169 compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest)
170 struct edge_list *edge_list;
172 sbitmap *antin, *antout, *avout, *kill, *earliest;
174 sbitmap difference, temp_bitmap;
176 basic_block pred, succ;
178 num_edges = NUM_EDGES (edge_list);
180 difference = sbitmap_alloc (n_exprs);
181 temp_bitmap = sbitmap_alloc (n_exprs);
183 for (x = 0; x < num_edges; x++)
185 pred = INDEX_EDGE_PRED_BB (edge_list, x);
186 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
187 if (pred == ENTRY_BLOCK_PTR)
188 sbitmap_copy (earliest[x], antin[succ->index]);
191 if (succ == EXIT_BLOCK_PTR)
193 sbitmap_zero (earliest[x]);
197 sbitmap_difference (difference, antin[succ->index],
199 sbitmap_not (temp_bitmap, antout[pred->index]);
200 sbitmap_a_and_b_or_c (earliest[x], difference, kill[pred->index],
209 /* Compute later and laterin vectors for edge based lcm. */
211 compute_laterin (edge_list, n_exprs,
212 earliest, antloc, later, laterin)
213 struct edge_list *edge_list;
215 sbitmap *earliest, *antloc, *later, *laterin;
219 basic_block pred, succ;
222 num_edges = NUM_EDGES (edge_list);
224 /* Laterin has an extra block allocated for the exit block. */
225 sbitmap_vector_ones (laterin, n_basic_blocks + 1);
226 sbitmap_vector_zero (later, num_edges);
228 /* Initialize laterin to the intersection of EARLIEST for all edges
229 from predecessors to this block. */
231 for (x = 0; x < num_edges; x++)
233 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
234 pred = INDEX_EDGE_PRED_BB (edge_list, x);
235 if (succ != EXIT_BLOCK_PTR)
236 sbitmap_a_and_b (laterin[succ->index], laterin[succ->index],
238 /* We already know the correct value of later for edges from
239 the entry node, so set it now. */
240 if (pred == ENTRY_BLOCK_PTR)
241 sbitmap_copy (later[x], earliest[x]);
244 difference = sbitmap_alloc (n_exprs);
249 for (x = 0; x < num_edges; x++)
251 pred = INDEX_EDGE_PRED_BB (edge_list, x);
252 if (pred != ENTRY_BLOCK_PTR)
254 sbitmap_difference (difference, laterin[pred->index],
255 antloc[pred->index]);
256 if (sbitmap_a_or_b (later[x], difference, earliest[x]))
263 sbitmap_vector_ones (laterin, n_basic_blocks);
265 for (x = 0; x < num_edges; x++)
267 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
268 if (succ != EXIT_BLOCK_PTR)
269 sbitmap_a_and_b (laterin[succ->index], laterin[succ->index],
272 /* We allocated an extra block for the exit node. */
273 sbitmap_a_and_b (laterin[n_basic_blocks], laterin[n_basic_blocks],
281 /* Compute the insertion and deletion points for edge based LCM. */
283 compute_insert_delete (edge_list, antloc, later, laterin,
285 struct edge_list *edge_list;
286 sbitmap *antloc, *later, *laterin, *insert, *delete;
290 for (x = 0; x < n_basic_blocks; x++)
291 sbitmap_difference (delete[x], antloc[x], laterin[x]);
293 for (x = 0; x < NUM_EDGES (edge_list); x++)
295 basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
296 if (b == EXIT_BLOCK_PTR)
297 sbitmap_difference (insert[x], later[x], laterin[n_basic_blocks]);
299 sbitmap_difference (insert[x], later[x], laterin[b->index]);
303 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the
304 insert and delete vectors for edge based LCM. Returns an
305 edgelist which is used to map the insert vector to what edge
306 an expression should be inserted on. */
309 pre_edge_lcm (file, n_exprs, transp, avloc, antloc, kill, insert, delete)
310 FILE *file ATTRIBUTE_UNUSED;
319 sbitmap *antin, *antout, *earliest;
320 sbitmap *avin, *avout;
321 sbitmap *later, *laterin;
322 struct edge_list *edge_list;
325 edge_list = create_edge_list ();
326 num_edges = NUM_EDGES (edge_list);
328 #ifdef LCM_DEBUG_INFO
331 fprintf (file, "Edge List:\n");
332 verify_edge_list (file, edge_list);
333 print_edge_list (file, edge_list);
334 dump_sbitmap_vector (file, "transp", "", transp, n_basic_blocks);
335 dump_sbitmap_vector (file, "antloc", "", antloc, n_basic_blocks);
336 dump_sbitmap_vector (file, "avloc", "", avloc, n_basic_blocks);
337 dump_sbitmap_vector (file, "kill", "", kill, n_basic_blocks);
341 /* Compute global availability. */
342 avin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
343 avout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
344 compute_available (avloc, kill, avout, avin);
348 /* Compute global anticipatability. */
349 antin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
350 antout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
351 compute_antinout_edge (antloc, transp, antin, antout);
353 #ifdef LCM_DEBUG_INFO
356 dump_sbitmap_vector (file, "antin", "", antin, n_basic_blocks);
357 dump_sbitmap_vector (file, "antout", "", antout, n_basic_blocks);
361 /* Compute earliestness. */
362 earliest = sbitmap_vector_alloc (num_edges, n_exprs);
363 compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
365 #ifdef LCM_DEBUG_INFO
367 dump_sbitmap_vector (file, "earliest", "", earliest, num_edges);
374 later = sbitmap_vector_alloc (num_edges, n_exprs);
375 /* Allocate an extra element for the exit block in the laterin vector. */
376 laterin = sbitmap_vector_alloc (n_basic_blocks + 1, n_exprs);
377 compute_laterin (edge_list, n_exprs, earliest, antloc, later, laterin);
379 #ifdef LCM_DEBUG_INFO
382 dump_sbitmap_vector (file, "laterin", "", laterin, n_basic_blocks + 1);
383 dump_sbitmap_vector (file, "later", "", later, num_edges);
389 *insert = sbitmap_vector_alloc (num_edges, n_exprs);
390 *delete = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
391 compute_insert_delete (edge_list, antloc, later, laterin, *insert, *delete);
396 #ifdef LCM_DEBUG_INFO
399 dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
400 dump_sbitmap_vector (file, "pre_delete_map", "", *delete, n_basic_blocks);
407 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
408 Return the number of passes we performed to iterate to a solution. */
410 compute_available (avloc, kill, avout, avin)
411 sbitmap *avloc, *kill, *avout, *avin;
413 int bb, changed, passes;
415 sbitmap_zero (avin[0]);
416 sbitmap_copy (avout[0] /*dst*/, avloc[0] /*src*/);
418 for (bb = 1; bb < n_basic_blocks; bb++)
419 sbitmap_not (avout[bb], kill[bb]);
426 for (bb = 1; bb < n_basic_blocks; bb++)
428 sbitmap_intersection_of_preds (avin[bb], avout, bb);
429 changed |= sbitmap_union_of_diff (avout[bb], avloc[bb],
437 /* Compute the farthest vector for edge based lcm. */
439 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
441 struct edge_list *edge_list;
443 sbitmap *st_avout, *st_avin, *st_antin, *kill, *farthest;
445 sbitmap difference, temp_bitmap;
447 basic_block pred, succ;
449 num_edges = NUM_EDGES (edge_list);
451 difference = sbitmap_alloc (n_exprs);
452 temp_bitmap = sbitmap_alloc (n_exprs);
454 for (x = 0; x < num_edges; x++)
456 pred = INDEX_EDGE_PRED_BB (edge_list, x);
457 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
458 if (succ == EXIT_BLOCK_PTR)
459 sbitmap_copy (farthest[x], st_avout[pred->index]);
462 if (pred == ENTRY_BLOCK_PTR)
464 sbitmap_zero (farthest[x]);
468 sbitmap_difference (difference, st_avout[pred->index],
469 st_antin[succ->index]);
470 sbitmap_not (temp_bitmap, st_avin[succ->index]);
471 sbitmap_a_and_b_or_c (farthest[x], difference,
472 kill[succ->index], temp_bitmap);
480 /* Compute nearer and nearerout vectors for edge based lcm. */
482 compute_nearerout (edge_list, n_exprs,
483 farthest, st_avloc, nearer, nearerout)
484 struct edge_list *edge_list;
486 sbitmap *farthest, *st_avloc, *nearer, *nearerout;
490 basic_block pred, succ;
493 num_edges = NUM_EDGES (edge_list);
495 /* nearout has an extra block allocated for the entry block. */
496 sbitmap_vector_ones (nearerout, n_basic_blocks + 1);
497 sbitmap_vector_zero (nearer, num_edges);
499 /* Initialize nearerout to the intersection of FARTHEST for all edges
500 from predecessors to this block. */
502 for (x = 0; x < num_edges; x++)
504 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
505 pred = INDEX_EDGE_PRED_BB (edge_list, x);
506 if (pred != ENTRY_BLOCK_PTR)
508 sbitmap_a_and_b (nearerout[pred->index], nearerout[pred->index],
511 /* We already know the correct value of nearer for edges to
513 if (succ == EXIT_BLOCK_PTR)
514 sbitmap_copy (nearer[x], farthest[x]);
517 difference = sbitmap_alloc (n_exprs);
522 for (x = 0; x < num_edges; x++)
524 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
525 if (succ != EXIT_BLOCK_PTR)
527 sbitmap_difference (difference, nearerout[succ->index],
528 st_avloc[succ->index]);
529 if (sbitmap_a_or_b (nearer[x], difference, farthest[x]))
537 sbitmap_vector_zero (nearerout, n_basic_blocks);
539 for (x = 0; x < num_edges; x++)
541 pred = INDEX_EDGE_PRED_BB (edge_list, x);
542 if (pred != ENTRY_BLOCK_PTR)
543 sbitmap_a_and_b (nearerout[pred->index],
544 nearerout[pred->index], nearer[x]);
546 sbitmap_a_and_b (nearerout[n_basic_blocks],
547 nearerout[n_basic_blocks], nearer[x]);
554 /* Compute the insertion and deletion points for edge based LCM. */
556 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
558 struct edge_list *edge_list;
559 sbitmap *st_avloc, *nearer, *nearerout, *insert, *delete;
563 for (x = 0; x < n_basic_blocks; x++)
564 sbitmap_difference (delete[x], st_avloc[x], nearerout[x]);
566 for (x = 0; x < NUM_EDGES (edge_list); x++)
568 basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
569 if (b == ENTRY_BLOCK_PTR)
570 sbitmap_difference (insert[x], nearer[x], nearerout[n_basic_blocks]);
572 sbitmap_difference (insert[x], nearer[x], nearerout[b->index]);
576 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
577 insert and delete vectors for edge based reverse LCM. Returns an
578 edgelist which is used to map the insert vector to what edge
579 an expression should be inserted on. */
582 pre_edge_rev_lcm (file, n_exprs, transp, st_avloc, st_antloc, kill,
584 FILE *file ATTRIBUTE_UNUSED;
593 sbitmap *st_antin, *st_antout;
594 sbitmap *st_avout, *st_avin, *farthest;
595 sbitmap *nearer, *nearerout;
596 struct edge_list *edge_list;
599 edge_list = create_edge_list ();
600 num_edges = NUM_EDGES (edge_list);
602 st_antin = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, n_exprs);
603 st_antout = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, n_exprs);
604 sbitmap_vector_zero (st_antin, n_basic_blocks);
605 sbitmap_vector_zero (st_antout, n_basic_blocks);
606 compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
608 /* Compute global anticipatability. */
609 st_avout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
610 st_avin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
611 compute_available (st_avloc, kill, st_avout, st_avin);
613 #ifdef LCM_DEBUG_INFO
616 fprintf (file, "Edge List:\n");
617 verify_edge_list (file, edge_list);
618 print_edge_list (file, edge_list);
619 dump_sbitmap_vector (file, "transp", "", transp, n_basic_blocks);
620 dump_sbitmap_vector (file, "st_avloc", "", st_avloc, n_basic_blocks);
621 dump_sbitmap_vector (file, "st_antloc", "", st_antloc, n_basic_blocks);
622 dump_sbitmap_vector (file, "st_antin", "", st_antin, n_basic_blocks);
623 dump_sbitmap_vector (file, "st_antout", "", st_antout, n_basic_blocks);
624 dump_sbitmap_vector (file, "st_kill", "", kill, n_basic_blocks);
628 #ifdef LCM_DEBUG_INFO
631 dump_sbitmap_vector (file, "st_avout", "", st_avout, n_basic_blocks);
632 dump_sbitmap_vector (file, "st_avin", "", st_avin, n_basic_blocks);
636 /* Compute farthestness. */
637 farthest = sbitmap_vector_alloc (num_edges, n_exprs);
638 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
641 #ifdef LCM_DEBUG_INFO
643 dump_sbitmap_vector (file, "farthest", "", farthest, num_edges);
649 nearer = sbitmap_vector_alloc (num_edges, n_exprs);
650 /* Allocate an extra element for the entry block. */
651 nearerout = sbitmap_vector_alloc (n_basic_blocks + 1, n_exprs);
652 compute_nearerout (edge_list, n_exprs, farthest, st_avloc, nearer, nearerout);
654 #ifdef LCM_DEBUG_INFO
657 dump_sbitmap_vector (file, "nearerout", "", nearerout,
659 dump_sbitmap_vector (file, "nearer", "", nearer, num_edges);
665 *insert = sbitmap_vector_alloc (num_edges, n_exprs);
666 *delete = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
667 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout, *insert, *delete);
672 #ifdef LCM_DEBUG_INFO
675 dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
676 dump_sbitmap_vector (file, "pre_delete_map", "", *delete, n_basic_blocks);