1 /* Generic partial redundancy elimination with lazy code motion support.
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008,
3 2010, 2011 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* These routines are meant to be used by various optimization
22 passes which can be modeled as lazy code motion problems.
23 Including, but not limited to:
25 * Traditional partial redundancy elimination.
27 * Placement of caller/caller register save/restores.
33 * Conversion of flat register files to a stacked register
36 * Dead load/store elimination.
38 These routines accept as input:
40 * Basic block information (number of blocks, lists of
41 predecessors and successors). Note the granularity
42 does not need to be basic block, they could be statements
45 * Bitmaps of local properties (computed, transparent and
46 anticipatable expressions).
48 The output of these routines is bitmap of redundant computations
49 and a bitmap of optimal placement points. */
54 #include "coretypes.h"
58 #include "hard-reg-set.h"
60 #include "insn-config.h"
62 #include "basic-block.h"
67 /* We want target macros for the mode switching code to be able to refer
68 to instruction attribute values. */
69 #include "insn-attr.h"
71 /* Edge based LCM routines. */
72 static void compute_antinout_edge (sbitmap
*, sbitmap
*, sbitmap
*, sbitmap
*);
73 static void compute_earliest (struct edge_list
*, int, sbitmap
*, sbitmap
*,
74 sbitmap
*, sbitmap
*, sbitmap
*);
75 static void compute_laterin (struct edge_list
*, sbitmap
*, sbitmap
*,
76 sbitmap
*, sbitmap
*);
77 static void compute_insert_delete (struct edge_list
*edge_list
, sbitmap
*,
78 sbitmap
*, sbitmap
*, sbitmap
*, sbitmap
*);
80 /* Edge based LCM routines on a reverse flowgraph. */
81 static void compute_farthest (struct edge_list
*, int, sbitmap
*, sbitmap
*,
82 sbitmap
*, sbitmap
*, sbitmap
*);
83 static void compute_nearerout (struct edge_list
*, sbitmap
*, sbitmap
*,
84 sbitmap
*, sbitmap
*);
85 static void compute_rev_insert_delete (struct edge_list
*edge_list
, sbitmap
*,
86 sbitmap
*, sbitmap
*, sbitmap
*,
89 /* Edge based lcm routines. */
91 /* Compute expression anticipatability at entrance and exit of each block.
92 This is done based on the flow graph, and not on the pred-succ lists.
93 Other than that, its pretty much identical to compute_antinout. */
96 compute_antinout_edge (sbitmap
*antloc
, sbitmap
*transp
, sbitmap
*antin
,
101 basic_block
*worklist
, *qin
, *qout
, *qend
;
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 qin
= qout
= worklist
= XNEWVEC (basic_block
, n_basic_blocks
);
110 /* We want a maximal solution, so make an optimistic initialization of
112 sbitmap_vector_ones (antin
, last_basic_block
);
114 /* Put every block on the worklist; this is necessary because of the
115 optimistic initialization of ANTIN above. */
116 FOR_EACH_BB_REVERSE (bb
)
123 qend
= &worklist
[n_basic_blocks
- NUM_FIXED_BLOCKS
];
124 qlen
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
126 /* Mark blocks which are predecessors of the exit block so that we
127 can easily identify them below. */
128 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
129 e
->src
->aux
= EXIT_BLOCK_PTR
;
131 /* Iterate until the worklist is empty. */
134 /* Take the first entry off the worklist. */
141 if (bb
->aux
== EXIT_BLOCK_PTR
)
142 /* Do not clear the aux field for blocks which are predecessors of
143 the EXIT block. That way we never add then to the worklist
145 sbitmap_zero (antout
[bb
->index
]);
148 /* Clear the aux field of this block so that it can be added to
149 the worklist again if necessary. */
151 sbitmap_intersection_of_succs (antout
[bb
->index
], antin
, bb
->index
);
154 if (sbitmap_a_or_b_and_c_cg (antin
[bb
->index
], antloc
[bb
->index
],
155 transp
[bb
->index
], antout
[bb
->index
]))
156 /* If the in state of this block changed, then we need
157 to add the predecessors of this block to the worklist
158 if they are not already on the worklist. */
159 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
160 if (!e
->src
->aux
&& e
->src
!= ENTRY_BLOCK_PTR
)
170 clear_aux_for_edges ();
171 clear_aux_for_blocks ();
175 /* Compute the earliest vector for edge based lcm. */
178 compute_earliest (struct edge_list
*edge_list
, int n_exprs
, sbitmap
*antin
,
179 sbitmap
*antout
, sbitmap
*avout
, sbitmap
*kill
,
182 sbitmap difference
, temp_bitmap
;
184 basic_block pred
, succ
;
186 num_edges
= NUM_EDGES (edge_list
);
188 difference
= sbitmap_alloc (n_exprs
);
189 temp_bitmap
= sbitmap_alloc (n_exprs
);
191 for (x
= 0; x
< num_edges
; x
++)
193 pred
= INDEX_EDGE_PRED_BB (edge_list
, x
);
194 succ
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
195 if (pred
== ENTRY_BLOCK_PTR
)
196 sbitmap_copy (earliest
[x
], antin
[succ
->index
]);
199 if (succ
== EXIT_BLOCK_PTR
)
200 sbitmap_zero (earliest
[x
]);
203 sbitmap_difference (difference
, antin
[succ
->index
],
205 sbitmap_not (temp_bitmap
, antout
[pred
->index
]);
206 sbitmap_a_and_b_or_c (earliest
[x
], difference
,
207 kill
[pred
->index
], temp_bitmap
);
212 sbitmap_free (temp_bitmap
);
213 sbitmap_free (difference
);
216 /* later(p,s) is dependent on the calculation of laterin(p).
217 laterin(p) is dependent on the calculation of later(p2,p).
219 laterin(ENTRY) is defined as all 0's
220 later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY)
221 laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)).
223 If we progress in this manner, starting with all basic blocks
224 in the work list, anytime we change later(bb), we need to add
225 succs(bb) to the worklist if they are not already on the worklist.
229 We prime the worklist all the normal basic blocks. The ENTRY block can
230 never be added to the worklist since it is never the successor of any
231 block. We explicitly prevent the EXIT block from being added to the
234 We optimistically initialize LATER. That is the only time this routine
235 will compute LATER for an edge out of the entry block since the entry
236 block is never on the worklist. Thus, LATERIN is neither used nor
237 computed for the ENTRY block.
239 Since the EXIT block is never added to the worklist, we will neither
240 use nor compute LATERIN for the exit block. Edges which reach the
241 EXIT block are handled in the normal fashion inside the loop. However,
242 the insertion/deletion computation needs LATERIN(EXIT), so we have
246 compute_laterin (struct edge_list
*edge_list
, sbitmap
*earliest
,
247 sbitmap
*antloc
, sbitmap
*later
, sbitmap
*laterin
)
251 basic_block
*worklist
, *qin
, *qout
, *qend
, bb
;
255 num_edges
= NUM_EDGES (edge_list
);
257 /* Allocate a worklist array/queue. Entries are only added to the
258 list if they were not already on the list. So the size is
259 bounded by the number of basic blocks. */
260 qin
= qout
= worklist
261 = XNEWVEC (basic_block
, n_basic_blocks
);
263 /* Initialize a mapping from each edge to its index. */
264 for (i
= 0; i
< num_edges
; i
++)
265 INDEX_EDGE (edge_list
, i
)->aux
= (void *) (size_t) i
;
267 /* We want a maximal solution, so initially consider LATER true for
268 all edges. This allows propagation through a loop since the incoming
269 loop edge will have LATER set, so if all the other incoming edges
270 to the loop are set, then LATERIN will be set for the head of the
273 If the optimistic setting of LATER on that edge was incorrect (for
274 example the expression is ANTLOC in a block within the loop) then
275 this algorithm will detect it when we process the block at the head
276 of the optimistic edge. That will requeue the affected blocks. */
277 sbitmap_vector_ones (later
, num_edges
);
279 /* Note that even though we want an optimistic setting of LATER, we
280 do not want to be overly optimistic. Consider an outgoing edge from
281 the entry block. That edge should always have a LATER value the
282 same as EARLIEST for that edge. */
283 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
284 sbitmap_copy (later
[(size_t) e
->aux
], earliest
[(size_t) e
->aux
]);
286 /* Add all the blocks to the worklist. This prevents an early exit from
287 the loop given our optimistic initialization of LATER above. */
294 /* Note that we do not use the last allocated element for our queue,
295 as EXIT_BLOCK is never inserted into it. */
297 qend
= &worklist
[n_basic_blocks
- NUM_FIXED_BLOCKS
];
298 qlen
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
300 /* Iterate until the worklist is empty. */
303 /* Take the first entry off the worklist. */
310 /* Compute the intersection of LATERIN for each incoming edge to B. */
311 sbitmap_ones (laterin
[bb
->index
]);
312 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
313 sbitmap_a_and_b (laterin
[bb
->index
], laterin
[bb
->index
],
314 later
[(size_t)e
->aux
]);
316 /* Calculate LATER for all outgoing edges. */
317 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
318 if (sbitmap_union_of_diff_cg (later
[(size_t) e
->aux
],
319 earliest
[(size_t) e
->aux
],
320 laterin
[e
->src
->index
],
321 antloc
[e
->src
->index
])
322 /* If LATER for an outgoing edge was changed, then we need
323 to add the target of the outgoing edge to the worklist. */
324 && e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
->aux
== 0)
334 /* Computation of insertion and deletion points requires computing LATERIN
335 for the EXIT block. We allocated an extra entry in the LATERIN array
336 for just this purpose. */
337 sbitmap_ones (laterin
[last_basic_block
]);
338 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
339 sbitmap_a_and_b (laterin
[last_basic_block
],
340 laterin
[last_basic_block
],
341 later
[(size_t) e
->aux
]);
343 clear_aux_for_edges ();
347 /* Compute the insertion and deletion points for edge based LCM. */
350 compute_insert_delete (struct edge_list
*edge_list
, sbitmap
*antloc
,
351 sbitmap
*later
, sbitmap
*laterin
, sbitmap
*insert
,
358 sbitmap_difference (del
[bb
->index
], antloc
[bb
->index
],
361 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
363 basic_block b
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
365 if (b
== EXIT_BLOCK_PTR
)
366 sbitmap_difference (insert
[x
], later
[x
], laterin
[last_basic_block
]);
368 sbitmap_difference (insert
[x
], later
[x
], laterin
[b
->index
]);
372 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and
373 delete vectors for edge based LCM. Returns an edgelist which is used to
374 map the insert vector to what edge an expression should be inserted on. */
377 pre_edge_lcm (int n_exprs
, sbitmap
*transp
,
378 sbitmap
*avloc
, sbitmap
*antloc
, sbitmap
*kill
,
379 sbitmap
**insert
, sbitmap
**del
)
381 sbitmap
*antin
, *antout
, *earliest
;
382 sbitmap
*avin
, *avout
;
383 sbitmap
*later
, *laterin
;
384 struct edge_list
*edge_list
;
387 edge_list
= create_edge_list ();
388 num_edges
= NUM_EDGES (edge_list
);
390 #ifdef LCM_DEBUG_INFO
393 fprintf (dump_file
, "Edge List:\n");
394 verify_edge_list (dump_file
, edge_list
);
395 print_edge_list (dump_file
, edge_list
);
396 dump_sbitmap_vector (dump_file
, "transp", "", transp
, last_basic_block
);
397 dump_sbitmap_vector (dump_file
, "antloc", "", antloc
, last_basic_block
);
398 dump_sbitmap_vector (dump_file
, "avloc", "", avloc
, last_basic_block
);
399 dump_sbitmap_vector (dump_file
, "kill", "", kill
, last_basic_block
);
403 /* Compute global availability. */
404 avin
= sbitmap_vector_alloc (last_basic_block
, n_exprs
);
405 avout
= sbitmap_vector_alloc (last_basic_block
, n_exprs
);
406 compute_available (avloc
, kill
, avout
, avin
);
407 sbitmap_vector_free (avin
);
409 /* Compute global anticipatability. */
410 antin
= sbitmap_vector_alloc (last_basic_block
, n_exprs
);
411 antout
= sbitmap_vector_alloc (last_basic_block
, n_exprs
);
412 compute_antinout_edge (antloc
, transp
, antin
, antout
);
414 #ifdef LCM_DEBUG_INFO
417 dump_sbitmap_vector (dump_file
, "antin", "", antin
, last_basic_block
);
418 dump_sbitmap_vector (dump_file
, "antout", "", antout
, last_basic_block
);
422 /* Compute earliestness. */
423 earliest
= sbitmap_vector_alloc (num_edges
, n_exprs
);
424 compute_earliest (edge_list
, n_exprs
, antin
, antout
, avout
, kill
, earliest
);
426 #ifdef LCM_DEBUG_INFO
428 dump_sbitmap_vector (dump_file
, "earliest", "", earliest
, num_edges
);
431 sbitmap_vector_free (antout
);
432 sbitmap_vector_free (antin
);
433 sbitmap_vector_free (avout
);
435 later
= sbitmap_vector_alloc (num_edges
, n_exprs
);
437 /* Allocate an extra element for the exit block in the laterin vector. */
438 laterin
= sbitmap_vector_alloc (last_basic_block
+ 1, n_exprs
);
439 compute_laterin (edge_list
, earliest
, antloc
, later
, laterin
);
441 #ifdef LCM_DEBUG_INFO
444 dump_sbitmap_vector (dump_file
, "laterin", "", laterin
, last_basic_block
+ 1);
445 dump_sbitmap_vector (dump_file
, "later", "", later
, num_edges
);
449 sbitmap_vector_free (earliest
);
451 *insert
= sbitmap_vector_alloc (num_edges
, n_exprs
);
452 *del
= sbitmap_vector_alloc (last_basic_block
, n_exprs
);
453 sbitmap_vector_zero (*insert
, num_edges
);
454 sbitmap_vector_zero (*del
, last_basic_block
);
455 compute_insert_delete (edge_list
, antloc
, later
, laterin
, *insert
, *del
);
457 sbitmap_vector_free (laterin
);
458 sbitmap_vector_free (later
);
460 #ifdef LCM_DEBUG_INFO
463 dump_sbitmap_vector (dump_file
, "pre_insert_map", "", *insert
, num_edges
);
464 dump_sbitmap_vector (dump_file
, "pre_delete_map", "", *del
,
472 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
473 Return the number of passes we performed to iterate to a solution. */
476 compute_available (sbitmap
*avloc
, sbitmap
*kill
, sbitmap
*avout
,
480 basic_block
*worklist
, *qin
, *qout
, *qend
, bb
;
484 /* Allocate a worklist array/queue. Entries are only added to the
485 list if they were not already on the list. So the size is
486 bounded by the number of basic blocks. */
487 qin
= qout
= worklist
=
488 XNEWVEC (basic_block
, n_basic_blocks
- NUM_FIXED_BLOCKS
);
490 /* We want a maximal solution. */
491 sbitmap_vector_ones (avout
, last_basic_block
);
493 /* Put every block on the worklist; this is necessary because of the
494 optimistic initialization of AVOUT above. */
502 qend
= &worklist
[n_basic_blocks
- NUM_FIXED_BLOCKS
];
503 qlen
= n_basic_blocks
- NUM_FIXED_BLOCKS
;
505 /* Mark blocks which are successors of the entry block so that we
506 can easily identify them below. */
507 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
508 e
->dest
->aux
= ENTRY_BLOCK_PTR
;
510 /* Iterate until the worklist is empty. */
513 /* Take the first entry off the worklist. */
520 /* If one of the predecessor blocks is the ENTRY block, then the
521 intersection of avouts is the null set. We can identify such blocks
522 by the special value in the AUX field in the block structure. */
523 if (bb
->aux
== ENTRY_BLOCK_PTR
)
524 /* Do not clear the aux field for blocks which are successors of the
525 ENTRY block. That way we never add then to the worklist again. */
526 sbitmap_zero (avin
[bb
->index
]);
529 /* Clear the aux field of this block so that it can be added to
530 the worklist again if necessary. */
532 sbitmap_intersection_of_preds (avin
[bb
->index
], avout
, bb
->index
);
535 if (sbitmap_union_of_diff_cg (avout
[bb
->index
], avloc
[bb
->index
],
536 avin
[bb
->index
], kill
[bb
->index
]))
537 /* If the out state of this block changed, then we need
538 to add the successors of this block to the worklist
539 if they are not already on the worklist. */
540 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
541 if (!e
->dest
->aux
&& e
->dest
!= EXIT_BLOCK_PTR
)
552 clear_aux_for_edges ();
553 clear_aux_for_blocks ();
557 /* Compute the farthest vector for edge based lcm. */
560 compute_farthest (struct edge_list
*edge_list
, int n_exprs
,
561 sbitmap
*st_avout
, sbitmap
*st_avin
, sbitmap
*st_antin
,
562 sbitmap
*kill
, sbitmap
*farthest
)
564 sbitmap difference
, temp_bitmap
;
566 basic_block pred
, succ
;
568 num_edges
= NUM_EDGES (edge_list
);
570 difference
= sbitmap_alloc (n_exprs
);
571 temp_bitmap
= sbitmap_alloc (n_exprs
);
573 for (x
= 0; x
< num_edges
; x
++)
575 pred
= INDEX_EDGE_PRED_BB (edge_list
, x
);
576 succ
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
577 if (succ
== EXIT_BLOCK_PTR
)
578 sbitmap_copy (farthest
[x
], st_avout
[pred
->index
]);
581 if (pred
== ENTRY_BLOCK_PTR
)
582 sbitmap_zero (farthest
[x
]);
585 sbitmap_difference (difference
, st_avout
[pred
->index
],
586 st_antin
[succ
->index
]);
587 sbitmap_not (temp_bitmap
, st_avin
[succ
->index
]);
588 sbitmap_a_and_b_or_c (farthest
[x
], difference
,
589 kill
[succ
->index
], temp_bitmap
);
594 sbitmap_free (temp_bitmap
);
595 sbitmap_free (difference
);
598 /* Compute nearer and nearerout vectors for edge based lcm.
600 This is the mirror of compute_laterin, additional comments on the
601 implementation can be found before compute_laterin. */
604 compute_nearerout (struct edge_list
*edge_list
, sbitmap
*farthest
,
605 sbitmap
*st_avloc
, sbitmap
*nearer
, sbitmap
*nearerout
)
609 basic_block
*worklist
, *tos
, bb
;
612 num_edges
= NUM_EDGES (edge_list
);
614 /* Allocate a worklist array/queue. Entries are only added to the
615 list if they were not already on the list. So the size is
616 bounded by the number of basic blocks. */
617 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks
+ 1);
619 /* Initialize NEARER for each edge and build a mapping from an edge to
621 for (i
= 0; i
< num_edges
; i
++)
622 INDEX_EDGE (edge_list
, i
)->aux
= (void *) (size_t) i
;
624 /* We want a maximal solution. */
625 sbitmap_vector_ones (nearer
, num_edges
);
627 /* Note that even though we want an optimistic setting of NEARER, we
628 do not want to be overly optimistic. Consider an incoming edge to
629 the exit block. That edge should always have a NEARER value the
630 same as FARTHEST for that edge. */
631 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
632 sbitmap_copy (nearer
[(size_t)e
->aux
], farthest
[(size_t)e
->aux
]);
634 /* Add all the blocks to the worklist. This prevents an early exit
635 from the loop given our optimistic initialization of NEARER. */
642 /* Iterate until the worklist is empty. */
643 while (tos
!= worklist
)
645 /* Take the first entry off the worklist. */
649 /* Compute the intersection of NEARER for each outgoing edge from B. */
650 sbitmap_ones (nearerout
[bb
->index
]);
651 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
652 sbitmap_a_and_b (nearerout
[bb
->index
], nearerout
[bb
->index
],
653 nearer
[(size_t) e
->aux
]);
655 /* Calculate NEARER for all incoming edges. */
656 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
657 if (sbitmap_union_of_diff_cg (nearer
[(size_t) e
->aux
],
658 farthest
[(size_t) e
->aux
],
659 nearerout
[e
->dest
->index
],
660 st_avloc
[e
->dest
->index
])
661 /* If NEARER for an incoming edge was changed, then we need
662 to add the source of the incoming edge to the worklist. */
663 && e
->src
!= ENTRY_BLOCK_PTR
&& e
->src
->aux
== 0)
670 /* Computation of insertion and deletion points requires computing NEAREROUT
671 for the ENTRY block. We allocated an extra entry in the NEAREROUT array
672 for just this purpose. */
673 sbitmap_ones (nearerout
[last_basic_block
]);
674 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
675 sbitmap_a_and_b (nearerout
[last_basic_block
],
676 nearerout
[last_basic_block
],
677 nearer
[(size_t) e
->aux
]);
679 clear_aux_for_edges ();
683 /* Compute the insertion and deletion points for edge based LCM. */
686 compute_rev_insert_delete (struct edge_list
*edge_list
, sbitmap
*st_avloc
,
687 sbitmap
*nearer
, sbitmap
*nearerout
,
688 sbitmap
*insert
, sbitmap
*del
)
694 sbitmap_difference (del
[bb
->index
], st_avloc
[bb
->index
],
695 nearerout
[bb
->index
]);
697 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
699 basic_block b
= INDEX_EDGE_PRED_BB (edge_list
, x
);
700 if (b
== ENTRY_BLOCK_PTR
)
701 sbitmap_difference (insert
[x
], nearer
[x
], nearerout
[last_basic_block
]);
703 sbitmap_difference (insert
[x
], nearer
[x
], nearerout
[b
->index
]);
707 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
708 insert and delete vectors for edge based reverse LCM. Returns an
709 edgelist which is used to map the insert vector to what edge
710 an expression should be inserted on. */
713 pre_edge_rev_lcm (int n_exprs
, sbitmap
*transp
,
714 sbitmap
*st_avloc
, sbitmap
*st_antloc
, sbitmap
*kill
,
715 sbitmap
**insert
, sbitmap
**del
)
717 sbitmap
*st_antin
, *st_antout
;
718 sbitmap
*st_avout
, *st_avin
, *farthest
;
719 sbitmap
*nearer
, *nearerout
;
720 struct edge_list
*edge_list
;
723 edge_list
= create_edge_list ();
724 num_edges
= NUM_EDGES (edge_list
);
726 st_antin
= sbitmap_vector_alloc (last_basic_block
, n_exprs
);
727 st_antout
= sbitmap_vector_alloc (last_basic_block
, n_exprs
);
728 sbitmap_vector_zero (st_antin
, last_basic_block
);
729 sbitmap_vector_zero (st_antout
, last_basic_block
);
730 compute_antinout_edge (st_antloc
, transp
, st_antin
, st_antout
);
732 /* Compute global anticipatability. */
733 st_avout
= sbitmap_vector_alloc (last_basic_block
, n_exprs
);
734 st_avin
= sbitmap_vector_alloc (last_basic_block
, n_exprs
);
735 compute_available (st_avloc
, kill
, st_avout
, st_avin
);
737 #ifdef LCM_DEBUG_INFO
740 fprintf (dump_file
, "Edge List:\n");
741 verify_edge_list (dump_file
, edge_list
);
742 print_edge_list (dump_file
, edge_list
);
743 dump_sbitmap_vector (dump_file
, "transp", "", transp
, last_basic_block
);
744 dump_sbitmap_vector (dump_file
, "st_avloc", "", st_avloc
, last_basic_block
);
745 dump_sbitmap_vector (dump_file
, "st_antloc", "", st_antloc
, last_basic_block
);
746 dump_sbitmap_vector (dump_file
, "st_antin", "", st_antin
, last_basic_block
);
747 dump_sbitmap_vector (dump_file
, "st_antout", "", st_antout
, last_basic_block
);
748 dump_sbitmap_vector (dump_file
, "st_kill", "", kill
, last_basic_block
);
752 #ifdef LCM_DEBUG_INFO
755 dump_sbitmap_vector (dump_file
, "st_avout", "", st_avout
, last_basic_block
);
756 dump_sbitmap_vector (dump_file
, "st_avin", "", st_avin
, last_basic_block
);
760 /* Compute farthestness. */
761 farthest
= sbitmap_vector_alloc (num_edges
, n_exprs
);
762 compute_farthest (edge_list
, n_exprs
, st_avout
, st_avin
, st_antin
,
765 #ifdef LCM_DEBUG_INFO
767 dump_sbitmap_vector (dump_file
, "farthest", "", farthest
, num_edges
);
770 sbitmap_vector_free (st_antin
);
771 sbitmap_vector_free (st_antout
);
773 sbitmap_vector_free (st_avin
);
774 sbitmap_vector_free (st_avout
);
776 nearer
= sbitmap_vector_alloc (num_edges
, n_exprs
);
778 /* Allocate an extra element for the entry block. */
779 nearerout
= sbitmap_vector_alloc (last_basic_block
+ 1, n_exprs
);
780 compute_nearerout (edge_list
, farthest
, st_avloc
, nearer
, nearerout
);
782 #ifdef LCM_DEBUG_INFO
785 dump_sbitmap_vector (dump_file
, "nearerout", "", nearerout
,
786 last_basic_block
+ 1);
787 dump_sbitmap_vector (dump_file
, "nearer", "", nearer
, num_edges
);
791 sbitmap_vector_free (farthest
);
793 *insert
= sbitmap_vector_alloc (num_edges
, n_exprs
);
794 *del
= sbitmap_vector_alloc (last_basic_block
, n_exprs
);
795 compute_rev_insert_delete (edge_list
, st_avloc
, nearer
, nearerout
,
798 sbitmap_vector_free (nearerout
);
799 sbitmap_vector_free (nearer
);
801 #ifdef LCM_DEBUG_INFO
804 dump_sbitmap_vector (dump_file
, "pre_insert_map", "", *insert
, num_edges
);
805 dump_sbitmap_vector (dump_file
, "pre_delete_map", "", *del
,