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
*, 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
*, 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
)
103 basic_block
*worklist
, *tos
;
105 /* Allocate a worklist array/queue. Entries are only added to the
106 list if they were not already on the list. So the size is
107 bounded by the number of basic blocks. */
108 tos
= worklist
= (basic_block
*) xmalloc (sizeof (basic_block
)
111 /* We want a maximal solution, so make an optimistic initialization of
113 sbitmap_vector_ones (antin
, n_basic_blocks
);
115 /* Put every block on the worklist; this is necessary because of the
116 optimistic initialization of ANTIN above. */
117 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
119 *tos
++ = BASIC_BLOCK (bb
);
120 BASIC_BLOCK (bb
)->aux
= BASIC_BLOCK (bb
);
123 /* Mark blocks which are predecessors of the exit block so that we
124 can easily identify them below. */
125 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
126 e
->src
->aux
= EXIT_BLOCK_PTR
;
128 /* Iterate until the worklist is empty. */
129 while (tos
!= worklist
)
131 /* Take the first entry off the worklist. */
132 basic_block b
= *--tos
;
135 if (b
->aux
== EXIT_BLOCK_PTR
)
137 /* Do not clear the aux field for blocks which are
138 predecessors of the EXIT block. That way we never
139 add then to the worklist again. */
140 sbitmap_zero (antout
[bb
]);
144 /* Clear the aux field of this block so that it can be added to
145 the worklist again if necessary. */
147 sbitmap_intersection_of_succs (antout
[bb
], antin
, bb
);
150 if (sbitmap_a_or_b_and_c (antin
[bb
], antloc
[bb
], transp
[bb
], antout
[bb
]))
152 /* If the in state of this block changed, then we need
153 to add the predecessors of this block to the worklist
154 if they are not already on the worklist. */
155 for (e
= b
->pred
; e
; e
= e
->pred_next
)
157 if (!e
->src
->aux
&& e
->src
!= ENTRY_BLOCK_PTR
)
168 /* Compute the earliest vector for edge based lcm. */
170 compute_earliest (edge_list
, n_exprs
, antin
, antout
, avout
, kill
, earliest
)
171 struct edge_list
*edge_list
;
173 sbitmap
*antin
, *antout
, *avout
, *kill
, *earliest
;
175 sbitmap difference
, temp_bitmap
;
177 basic_block pred
, succ
;
179 num_edges
= NUM_EDGES (edge_list
);
181 difference
= sbitmap_alloc (n_exprs
);
182 temp_bitmap
= sbitmap_alloc (n_exprs
);
184 for (x
= 0; x
< num_edges
; x
++)
186 pred
= INDEX_EDGE_PRED_BB (edge_list
, x
);
187 succ
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
188 if (pred
== ENTRY_BLOCK_PTR
)
189 sbitmap_copy (earliest
[x
], antin
[succ
->index
]);
192 if (succ
== EXIT_BLOCK_PTR
)
194 sbitmap_zero (earliest
[x
]);
198 sbitmap_difference (difference
, antin
[succ
->index
],
200 sbitmap_not (temp_bitmap
, antout
[pred
->index
]);
201 sbitmap_a_and_b_or_c (earliest
[x
], difference
, kill
[pred
->index
],
210 /* later(p,s) is dependent on the calculation of laterin(p).
211 laterin(p) is dependent on the calculation of later(p2,p).
213 laterin(ENTRY) is defined as all 0's
214 later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY)
215 laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)).
217 If we progress in this manner, starting with all basic blocks
218 in the work list, anytime we change later(bb), we need to add
219 succs(bb) to the worklist if they are not already on the worklist.
223 We prime the worklist all the normal basic blocks. The ENTRY block can
224 never be added to the worklist since it is never the successor of any
225 block. We explicitly prevent the EXIT block from being added to the
228 We optimistically initialize LATER. That is the only time this routine
229 will compute LATER for an edge out of the entry block since the entry
230 block is never on the worklist. Thus, LATERIN is neither used nor
231 computed for the ENTRY block.
233 Since the EXIT block is never added to the worklist, we will neither
234 use nor compute LATERIN for the exit block. Edges which reach the
235 EXIT block are handled in the normal fashion inside the loop. However,
236 the insertion/deletion computation needs LATERIN(EXIT), so we have
240 compute_laterin (edge_list
, earliest
, antloc
, later
, laterin
)
241 struct edge_list
*edge_list
;
242 sbitmap
*earliest
, *antloc
, *later
, *laterin
;
244 int bb
, num_edges
, i
;
246 basic_block
*worklist
, *tos
;
248 num_edges
= NUM_EDGES (edge_list
);
250 /* Allocate a worklist array/queue. Entries are only added to the
251 list if they were not already on the list. So the size is
252 bounded by the number of basic blocks. */
253 tos
= worklist
= (basic_block
*) xmalloc (sizeof (basic_block
)
254 * (n_basic_blocks
+ 1));
256 /* Initialize a mapping from each edge to its index. */
257 for (i
= 0; i
< num_edges
; i
++)
258 INDEX_EDGE (edge_list
, i
)->aux
= (void *) (size_t) i
;
260 /* We want a maximal solution, so initially consider LATER true for
261 all edges. This allows propagation through a loop since the incoming
262 loop edge will have LATER set, so if all the other incoming edges
263 to the loop are set, then LATERIN will be set for the head of the
266 If the optimistic setting of LATER on that edge was incorrect (for
267 example the expression is ANTLOC in a block within the loop) then
268 this algorithm will detect it when we process the block at the head
269 of the optimistic edge. That will requeue the affected blocks. */
270 sbitmap_vector_ones (later
, num_edges
);
272 /* Note that even though we want an optimistic setting of LATER, we
273 do not want to be overly optimistic. Consider an outgoing edge from
274 the entry block. That edge should always have a LATER value the
275 same as EARLIEST for that edge. */
276 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
277 sbitmap_copy (later
[(int)e
->aux
], earliest
[(int)e
->aux
]);
279 /* Add all the blocks to the worklist. This prevents an early exit from
280 the loop given our optimistic initialization of LATER above. */
281 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
283 basic_block b
= BASIC_BLOCK (bb
);
288 /* Iterate until the worklist is empty. */
289 while (tos
!= worklist
)
291 /* Take the first entry off the worklist. */
292 basic_block b
= *--tos
;
295 /* Compute the intersection of LATERIN for each incoming edge to B. */
297 sbitmap_ones (laterin
[bb
]);
298 for (e
= b
->pred
; e
!= NULL
; e
= e
->pred_next
)
299 sbitmap_a_and_b (laterin
[bb
], laterin
[bb
], later
[(size_t)e
->aux
]);
301 /* Calculate LATER for all outgoing edges. */
302 for (e
= b
->succ
; e
!= NULL
; e
= e
->succ_next
)
304 if (sbitmap_union_of_diff (later
[(size_t) e
->aux
],
305 earliest
[(size_t) e
->aux
],
306 laterin
[e
->src
->index
],
307 antloc
[e
->src
->index
]))
309 /* If LATER for an outgoing edge was changed, then we need
310 to add the target of the outgoing edge to the worklist. */
311 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
->aux
== 0)
320 /* Computation of insertion and deletion points requires computing LATERIN
321 for the EXIT block. We allocated an extra entry in the LATERIN array
322 for just this purpose. */
323 sbitmap_ones (laterin
[n_basic_blocks
]);
324 for (e
= EXIT_BLOCK_PTR
->pred
; e
!= NULL
; e
= e
->pred_next
)
325 sbitmap_a_and_b (laterin
[n_basic_blocks
],
326 laterin
[n_basic_blocks
],
327 later
[(size_t) e
->aux
]);
332 /* Compute the insertion and deletion points for edge based LCM. */
334 compute_insert_delete (edge_list
, antloc
, later
, laterin
,
336 struct edge_list
*edge_list
;
337 sbitmap
*antloc
, *later
, *laterin
, *insert
, *delete;
341 for (x
= 0; x
< n_basic_blocks
; x
++)
342 sbitmap_difference (delete[x
], antloc
[x
], laterin
[x
]);
344 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
346 basic_block b
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
347 if (b
== EXIT_BLOCK_PTR
)
348 sbitmap_difference (insert
[x
], later
[x
], laterin
[n_basic_blocks
]);
350 sbitmap_difference (insert
[x
], later
[x
], laterin
[b
->index
]);
354 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the
355 insert and delete vectors for edge based LCM. Returns an
356 edgelist which is used to map the insert vector to what edge
357 an expression should be inserted on. */
360 pre_edge_lcm (file
, n_exprs
, transp
, avloc
, antloc
, kill
, insert
, delete)
361 FILE *file ATTRIBUTE_UNUSED
;
370 sbitmap
*antin
, *antout
, *earliest
;
371 sbitmap
*avin
, *avout
;
372 sbitmap
*later
, *laterin
;
373 struct edge_list
*edge_list
;
376 edge_list
= create_edge_list ();
377 num_edges
= NUM_EDGES (edge_list
);
379 #ifdef LCM_DEBUG_INFO
382 fprintf (file
, "Edge List:\n");
383 verify_edge_list (file
, edge_list
);
384 print_edge_list (file
, edge_list
);
385 dump_sbitmap_vector (file
, "transp", "", transp
, n_basic_blocks
);
386 dump_sbitmap_vector (file
, "antloc", "", antloc
, n_basic_blocks
);
387 dump_sbitmap_vector (file
, "avloc", "", avloc
, n_basic_blocks
);
388 dump_sbitmap_vector (file
, "kill", "", kill
, n_basic_blocks
);
392 /* Compute global availability. */
393 avin
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
394 avout
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
395 compute_available (avloc
, kill
, avout
, avin
);
400 /* Compute global anticipatability. */
401 antin
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
402 antout
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
403 compute_antinout_edge (antloc
, transp
, antin
, antout
);
405 #ifdef LCM_DEBUG_INFO
408 dump_sbitmap_vector (file
, "antin", "", antin
, n_basic_blocks
);
409 dump_sbitmap_vector (file
, "antout", "", antout
, n_basic_blocks
);
413 /* Compute earliestness. */
414 earliest
= sbitmap_vector_alloc (num_edges
, n_exprs
);
415 compute_earliest (edge_list
, n_exprs
, antin
, antout
, avout
, kill
, earliest
);
417 #ifdef LCM_DEBUG_INFO
419 dump_sbitmap_vector (file
, "earliest", "", earliest
, num_edges
);
426 later
= sbitmap_vector_alloc (num_edges
, n_exprs
);
427 /* Allocate an extra element for the exit block in the laterin vector. */
428 laterin
= sbitmap_vector_alloc (n_basic_blocks
+ 1, n_exprs
);
429 compute_laterin (edge_list
, earliest
, antloc
, later
, laterin
);
432 #ifdef LCM_DEBUG_INFO
435 dump_sbitmap_vector (file
, "laterin", "", laterin
, n_basic_blocks
+ 1);
436 dump_sbitmap_vector (file
, "later", "", later
, num_edges
);
442 *insert
= sbitmap_vector_alloc (num_edges
, n_exprs
);
443 *delete = sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
444 compute_insert_delete (edge_list
, antloc
, later
, laterin
, *insert
, *delete);
449 #ifdef LCM_DEBUG_INFO
452 dump_sbitmap_vector (file
, "pre_insert_map", "", *insert
, num_edges
);
453 dump_sbitmap_vector (file
, "pre_delete_map", "", *delete, n_basic_blocks
);
460 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
461 Return the number of passes we performed to iterate to a solution. */
463 compute_available (avloc
, kill
, avout
, avin
)
464 sbitmap
*avloc
, *kill
, *avout
, *avin
;
468 basic_block
*worklist
, *tos
;
470 /* Allocate a worklist array/queue. Entries are only added to the
471 list if they were not already on the list. So the size is
472 bounded by the number of basic blocks. */
473 tos
= worklist
= (basic_block
*) xmalloc (sizeof (basic_block
)
476 /* We want a maximal solution. */
477 sbitmap_vector_ones (avout
, n_basic_blocks
);
479 /* Put every block on the worklist; this is necessary because of the
480 optimistic initialization of AVOUT above. */
481 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
483 *tos
++ = BASIC_BLOCK (bb
);
484 BASIC_BLOCK (bb
)->aux
= BASIC_BLOCK (bb
);
487 /* Mark blocks which are successors of the entry block so that we
488 can easily identify them below. */
489 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
490 e
->dest
->aux
= ENTRY_BLOCK_PTR
;
492 /* Iterate until the worklist is empty. */
493 while (tos
!= worklist
)
495 /* Take the first entry off the worklist. */
496 basic_block b
= *--tos
;
499 /* If one of the predecessor blocks is the ENTRY block, then the
500 intersection of avouts is the null set. We can identify such blocks
501 by the special value in the AUX field in the block structure. */
502 if (b
->aux
== ENTRY_BLOCK_PTR
)
504 /* Do not clear the aux field for blocks which are
505 successors of the ENTRY block. That way we never
506 add then to the worklist again. */
507 sbitmap_zero (avin
[bb
]);
511 /* Clear the aux field of this block so that it can be added to
512 the worklist again if necessary. */
514 sbitmap_intersection_of_preds (avin
[bb
], avout
, bb
);
517 if (sbitmap_union_of_diff (avout
[bb
], avloc
[bb
], avin
[bb
], kill
[bb
]))
519 /* If the out state of this block changed, then we need
520 to add the successors of this block to the worklist
521 if they are not already on the worklist. */
522 for (e
= b
->succ
; e
; e
= e
->succ_next
)
524 if (!e
->dest
->aux
&& e
->dest
!= EXIT_BLOCK_PTR
)
535 /* Compute the farthest vector for edge based lcm. */
537 compute_farthest (edge_list
, n_exprs
, st_avout
, st_avin
, st_antin
,
539 struct edge_list
*edge_list
;
541 sbitmap
*st_avout
, *st_avin
, *st_antin
, *kill
, *farthest
;
543 sbitmap difference
, temp_bitmap
;
545 basic_block pred
, succ
;
547 num_edges
= NUM_EDGES (edge_list
);
549 difference
= sbitmap_alloc (n_exprs
);
550 temp_bitmap
= sbitmap_alloc (n_exprs
);
552 for (x
= 0; x
< num_edges
; x
++)
554 pred
= INDEX_EDGE_PRED_BB (edge_list
, x
);
555 succ
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
556 if (succ
== EXIT_BLOCK_PTR
)
557 sbitmap_copy (farthest
[x
], st_avout
[pred
->index
]);
560 if (pred
== ENTRY_BLOCK_PTR
)
562 sbitmap_zero (farthest
[x
]);
566 sbitmap_difference (difference
, st_avout
[pred
->index
],
567 st_antin
[succ
->index
]);
568 sbitmap_not (temp_bitmap
, st_avin
[succ
->index
]);
569 sbitmap_a_and_b_or_c (farthest
[x
], difference
,
570 kill
[succ
->index
], temp_bitmap
);
578 /* Compute nearer and nearerout vectors for edge based lcm.
580 This is the mirror of compute_laterin, additional comments on the
581 implementation can be found before compute_laterin. */
584 compute_nearerout (edge_list
, farthest
, st_avloc
, nearer
, nearerout
)
585 struct edge_list
*edge_list
;
586 sbitmap
*farthest
, *st_avloc
, *nearer
, *nearerout
;
588 int bb
, num_edges
, i
;
590 basic_block
*worklist
, *tos
;
592 num_edges
= NUM_EDGES (edge_list
);
594 /* Allocate a worklist array/queue. Entries are only added to the
595 list if they were not already on the list. So the size is
596 bounded by the number of basic blocks. */
597 tos
= worklist
= (basic_block
*) xmalloc (sizeof (basic_block
)
598 * (n_basic_blocks
+ 1));
600 /* Initialize NEARER for each edge and build a mapping from an edge to
602 for (i
= 0; i
< num_edges
; i
++)
603 INDEX_EDGE (edge_list
, i
)->aux
= (void *) (size_t) i
;
605 /* We want a maximal solution. */
606 sbitmap_vector_ones (nearer
, num_edges
);
608 /* Note that even though we want an optimistic setting of NEARER, we
609 do not want to be overly optimistic. Consider an incoming edge to
610 the exit block. That edge should always have a NEARER value the
611 same as FARTHEST for that edge. */
612 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
613 sbitmap_copy (nearer
[(int)e
->aux
], farthest
[(int)e
->aux
]);
615 /* Add all the blocks to the worklist. This prevents an early exit
616 from the loop given our optimistic initialization of NEARER. */
617 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
619 basic_block b
= BASIC_BLOCK (bb
);
624 /* Iterate until the worklist is empty. */
625 while (tos
!= worklist
)
627 /* Take the first entry off the worklist. */
628 basic_block b
= *--tos
;
631 /* Compute the intersection of NEARER for each outgoing edge from B. */
633 sbitmap_ones (nearerout
[bb
]);
634 for (e
= b
->succ
; e
!= NULL
; e
= e
->succ_next
)
635 sbitmap_a_and_b (nearerout
[bb
], nearerout
[bb
],
636 nearer
[(size_t) e
->aux
]);
638 /* Calculate NEARER for all incoming edges. */
639 for (e
= b
->pred
; e
!= NULL
; e
= e
->pred_next
)
641 if (sbitmap_union_of_diff (nearer
[(size_t) e
->aux
],
642 farthest
[(size_t) e
->aux
],
643 nearerout
[e
->dest
->index
],
644 st_avloc
[e
->dest
->index
]))
646 /* If NEARER for an incoming edge was changed, then we need
647 to add the source of the incoming edge to the worklist. */
648 if (e
->src
!= ENTRY_BLOCK_PTR
&& e
->src
->aux
== 0)
657 /* Computation of insertion and deletion points requires computing NEAREROUT
658 for the ENTRY block. We allocated an extra entry in the NEAREROUT array
659 for just this purpose. */
660 sbitmap_ones (nearerout
[n_basic_blocks
]);
661 for (e
= ENTRY_BLOCK_PTR
->succ
; e
!= NULL
; e
= e
->succ_next
)
662 sbitmap_a_and_b (nearerout
[n_basic_blocks
],
663 nearerout
[n_basic_blocks
],
664 nearer
[(size_t) e
->aux
]);
669 /* Compute the insertion and deletion points for edge based LCM. */
671 compute_rev_insert_delete (edge_list
, st_avloc
, nearer
, nearerout
,
673 struct edge_list
*edge_list
;
674 sbitmap
*st_avloc
, *nearer
, *nearerout
, *insert
, *delete;
678 for (x
= 0; x
< n_basic_blocks
; x
++)
679 sbitmap_difference (delete[x
], st_avloc
[x
], nearerout
[x
]);
681 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
683 basic_block b
= INDEX_EDGE_PRED_BB (edge_list
, x
);
684 if (b
== ENTRY_BLOCK_PTR
)
685 sbitmap_difference (insert
[x
], nearer
[x
], nearerout
[n_basic_blocks
]);
687 sbitmap_difference (insert
[x
], nearer
[x
], nearerout
[b
->index
]);
691 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
692 insert and delete vectors for edge based reverse LCM. Returns an
693 edgelist which is used to map the insert vector to what edge
694 an expression should be inserted on. */
697 pre_edge_rev_lcm (file
, n_exprs
, transp
, st_avloc
, st_antloc
, kill
,
699 FILE *file ATTRIBUTE_UNUSED
;
708 sbitmap
*st_antin
, *st_antout
;
709 sbitmap
*st_avout
, *st_avin
, *farthest
;
710 sbitmap
*nearer
, *nearerout
;
711 struct edge_list
*edge_list
;
714 edge_list
= create_edge_list ();
715 num_edges
= NUM_EDGES (edge_list
);
717 st_antin
= (sbitmap
*) sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
718 st_antout
= (sbitmap
*) sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
719 sbitmap_vector_zero (st_antin
, n_basic_blocks
);
720 sbitmap_vector_zero (st_antout
, n_basic_blocks
);
721 compute_antinout_edge (st_antloc
, transp
, st_antin
, st_antout
);
723 /* Compute global anticipatability. */
724 st_avout
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
725 st_avin
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
726 compute_available (st_avloc
, kill
, st_avout
, st_avin
);
728 #ifdef LCM_DEBUG_INFO
731 fprintf (file
, "Edge List:\n");
732 verify_edge_list (file
, edge_list
);
733 print_edge_list (file
, edge_list
);
734 dump_sbitmap_vector (file
, "transp", "", transp
, n_basic_blocks
);
735 dump_sbitmap_vector (file
, "st_avloc", "", st_avloc
, n_basic_blocks
);
736 dump_sbitmap_vector (file
, "st_antloc", "", st_antloc
, n_basic_blocks
);
737 dump_sbitmap_vector (file
, "st_antin", "", st_antin
, n_basic_blocks
);
738 dump_sbitmap_vector (file
, "st_antout", "", st_antout
, n_basic_blocks
);
739 dump_sbitmap_vector (file
, "st_kill", "", kill
, n_basic_blocks
);
743 #ifdef LCM_DEBUG_INFO
746 dump_sbitmap_vector (file
, "st_avout", "", st_avout
, n_basic_blocks
);
747 dump_sbitmap_vector (file
, "st_avin", "", st_avin
, n_basic_blocks
);
751 /* Compute farthestness. */
752 farthest
= sbitmap_vector_alloc (num_edges
, n_exprs
);
753 compute_farthest (edge_list
, n_exprs
, st_avout
, st_avin
, st_antin
,
756 #ifdef LCM_DEBUG_INFO
758 dump_sbitmap_vector (file
, "farthest", "", farthest
, num_edges
);
764 nearer
= sbitmap_vector_alloc (num_edges
, n_exprs
);
765 /* Allocate an extra element for the entry block. */
766 nearerout
= sbitmap_vector_alloc (n_basic_blocks
+ 1, n_exprs
);
767 compute_nearerout (edge_list
, farthest
, st_avloc
, nearer
, nearerout
);
769 #ifdef LCM_DEBUG_INFO
772 dump_sbitmap_vector (file
, "nearerout", "", nearerout
,
774 dump_sbitmap_vector (file
, "nearer", "", nearer
, num_edges
);
780 *insert
= sbitmap_vector_alloc (num_edges
, n_exprs
);
781 *delete = sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
782 compute_rev_insert_delete (edge_list
, st_avloc
, nearer
, nearerout
, *insert
, *delete);
787 #ifdef LCM_DEBUG_INFO
790 dump_sbitmap_vector (file
, "pre_insert_map", "", *insert
, num_edges
);
791 dump_sbitmap_vector (file
, "pre_delete_map", "", *delete, n_basic_blocks
);