1 /* Generic partial redundancy elimination with lazy code motion support.
2 Copyright (C) 1998-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* These routines are meant to be used by various optimization
21 passes which can be modeled as lazy code motion problems.
22 Including, but not limited to:
24 * Traditional partial redundancy elimination.
26 * Placement of caller/caller register save/restores.
32 * Conversion of flat register files to a stacked register
35 * Dead load/store elimination.
37 These routines accept as input:
39 * Basic block information (number of blocks, lists of
40 predecessors and successors). Note the granularity
41 does not need to be basic block, they could be statements
44 * Bitmaps of local properties (computed, transparent and
45 anticipatable expressions).
47 The output of these routines is bitmap of redundant computations
48 and a bitmap of optimal placement points. */
53 #include "coretypes.h"
57 #include "hard-reg-set.h"
59 #include "insn-config.h"
61 #include "basic-block.h"
67 /* Edge based LCM routines. */
68 static void compute_antinout_edge (sbitmap
*, sbitmap
*, sbitmap
*, sbitmap
*);
69 static void compute_earliest (struct edge_list
*, int, sbitmap
*, sbitmap
*,
70 sbitmap
*, sbitmap
*, sbitmap
*);
71 static void compute_laterin (struct edge_list
*, sbitmap
*, sbitmap
*,
72 sbitmap
*, sbitmap
*);
73 static void compute_insert_delete (struct edge_list
*edge_list
, sbitmap
*,
74 sbitmap
*, sbitmap
*, sbitmap
*, sbitmap
*);
76 /* Edge based LCM routines on a reverse flowgraph. */
77 static void compute_farthest (struct edge_list
*, int, sbitmap
*, sbitmap
*,
78 sbitmap
*, sbitmap
*, sbitmap
*);
79 static void compute_nearerout (struct edge_list
*, sbitmap
*, sbitmap
*,
80 sbitmap
*, sbitmap
*);
81 static void compute_rev_insert_delete (struct edge_list
*edge_list
, sbitmap
*,
82 sbitmap
*, sbitmap
*, sbitmap
*,
85 /* Edge based lcm routines. */
87 /* Compute expression anticipatability at entrance and exit of each block.
88 This is done based on the flow graph, and not on the pred-succ lists.
89 Other than that, its pretty much identical to compute_antinout. */
92 compute_antinout_edge (sbitmap
*antloc
, sbitmap
*transp
, sbitmap
*antin
,
97 basic_block
*worklist
, *qin
, *qout
, *qend
;
101 /* Allocate a worklist array/queue. Entries are only added to the
102 list if they were not already on the list. So the size is
103 bounded by the number of basic blocks. */
104 qin
= qout
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
106 /* We want a maximal solution, so make an optimistic initialization of
108 bitmap_vector_ones (antin
, last_basic_block_for_fn (cfun
));
110 /* Put every block on the worklist; this is necessary because of the
111 optimistic initialization of ANTIN above. */
112 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
119 qend
= &worklist
[n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
];
120 qlen
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
122 /* Mark blocks which are predecessors of the exit block so that we
123 can easily identify them below. */
124 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
125 e
->src
->aux
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
127 /* Iterate until the worklist is empty. */
130 /* Take the first entry off the worklist. */
137 if (bb
->aux
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
138 /* Do not clear the aux field for blocks which are predecessors of
139 the EXIT block. That way we never add then to the worklist
141 bitmap_clear (antout
[bb
->index
]);
144 /* Clear the aux field of this block so that it can be added to
145 the worklist again if necessary. */
147 bitmap_intersection_of_succs (antout
[bb
->index
], antin
, bb
);
150 if (bitmap_or_and (antin
[bb
->index
], antloc
[bb
->index
],
151 transp
[bb
->index
], antout
[bb
->index
]))
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_EACH_EDGE (e
, ei
, bb
->preds
)
156 if (!e
->src
->aux
&& e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
166 clear_aux_for_edges ();
167 clear_aux_for_blocks ();
171 /* Compute the earliest vector for edge based lcm. */
174 compute_earliest (struct edge_list
*edge_list
, int n_exprs
, sbitmap
*antin
,
175 sbitmap
*antout
, sbitmap
*avout
, sbitmap
*kill
,
178 sbitmap difference
, temp_bitmap
;
180 basic_block pred
, succ
;
182 num_edges
= NUM_EDGES (edge_list
);
184 difference
= sbitmap_alloc (n_exprs
);
185 temp_bitmap
= sbitmap_alloc (n_exprs
);
187 for (x
= 0; x
< num_edges
; x
++)
189 pred
= INDEX_EDGE_PRED_BB (edge_list
, x
);
190 succ
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
191 if (pred
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
192 bitmap_copy (earliest
[x
], antin
[succ
->index
]);
195 if (succ
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
196 bitmap_clear (earliest
[x
]);
199 bitmap_and_compl (difference
, antin
[succ
->index
],
201 bitmap_not (temp_bitmap
, antout
[pred
->index
]);
202 bitmap_and_or (earliest
[x
], difference
,
203 kill
[pred
->index
], temp_bitmap
);
208 sbitmap_free (temp_bitmap
);
209 sbitmap_free (difference
);
212 /* later(p,s) is dependent on the calculation of laterin(p).
213 laterin(p) is dependent on the calculation of later(p2,p).
215 laterin(ENTRY) is defined as all 0's
216 later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY)
217 laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)).
219 If we progress in this manner, starting with all basic blocks
220 in the work list, anytime we change later(bb), we need to add
221 succs(bb) to the worklist if they are not already on the worklist.
225 We prime the worklist all the normal basic blocks. The ENTRY block can
226 never be added to the worklist since it is never the successor of any
227 block. We explicitly prevent the EXIT block from being added to the
230 We optimistically initialize LATER. That is the only time this routine
231 will compute LATER for an edge out of the entry block since the entry
232 block is never on the worklist. Thus, LATERIN is neither used nor
233 computed for the ENTRY block.
235 Since the EXIT block is never added to the worklist, we will neither
236 use nor compute LATERIN for the exit block. Edges which reach the
237 EXIT block are handled in the normal fashion inside the loop. However,
238 the insertion/deletion computation needs LATERIN(EXIT), so we have
242 compute_laterin (struct edge_list
*edge_list
, sbitmap
*earliest
,
243 sbitmap
*antloc
, sbitmap
*later
, sbitmap
*laterin
)
247 basic_block
*worklist
, *qin
, *qout
, *qend
, bb
;
251 num_edges
= NUM_EDGES (edge_list
);
253 /* Allocate a worklist array/queue. Entries are only added to the
254 list if they were not already on the list. So the size is
255 bounded by the number of basic blocks. */
256 qin
= qout
= worklist
257 = XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
259 /* Initialize a mapping from each edge to its index. */
260 for (i
= 0; i
< num_edges
; i
++)
261 INDEX_EDGE (edge_list
, i
)->aux
= (void *) (size_t) i
;
263 /* We want a maximal solution, so initially consider LATER true for
264 all edges. This allows propagation through a loop since the incoming
265 loop edge will have LATER set, so if all the other incoming edges
266 to the loop are set, then LATERIN will be set for the head of the
269 If the optimistic setting of LATER on that edge was incorrect (for
270 example the expression is ANTLOC in a block within the loop) then
271 this algorithm will detect it when we process the block at the head
272 of the optimistic edge. That will requeue the affected blocks. */
273 bitmap_vector_ones (later
, num_edges
);
275 /* Note that even though we want an optimistic setting of LATER, we
276 do not want to be overly optimistic. Consider an outgoing edge from
277 the entry block. That edge should always have a LATER value the
278 same as EARLIEST for that edge. */
279 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
280 bitmap_copy (later
[(size_t) e
->aux
], earliest
[(size_t) e
->aux
]);
282 /* Add all the blocks to the worklist. This prevents an early exit from
283 the loop given our optimistic initialization of LATER above. */
284 FOR_EACH_BB_FN (bb
, cfun
)
290 /* Note that we do not use the last allocated element for our queue,
291 as EXIT_BLOCK is never inserted into it. */
293 qend
= &worklist
[n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
];
294 qlen
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
296 /* Iterate until the worklist is empty. */
299 /* Take the first entry off the worklist. */
306 /* Compute the intersection of LATERIN for each incoming edge to B. */
307 bitmap_ones (laterin
[bb
->index
]);
308 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
309 bitmap_and (laterin
[bb
->index
], laterin
[bb
->index
],
310 later
[(size_t)e
->aux
]);
312 /* Calculate LATER for all outgoing edges. */
313 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
314 if (bitmap_ior_and_compl (later
[(size_t) e
->aux
],
315 earliest
[(size_t) e
->aux
],
316 laterin
[e
->src
->index
],
317 antloc
[e
->src
->index
])
318 /* If LATER for an outgoing edge was changed, then we need
319 to add the target of the outgoing edge to the worklist. */
320 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
->aux
== 0)
330 /* Computation of insertion and deletion points requires computing LATERIN
331 for the EXIT block. We allocated an extra entry in the LATERIN array
332 for just this purpose. */
333 bitmap_ones (laterin
[last_basic_block_for_fn (cfun
)]);
334 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
335 bitmap_and (laterin
[last_basic_block_for_fn (cfun
)],
336 laterin
[last_basic_block_for_fn (cfun
)],
337 later
[(size_t) e
->aux
]);
339 clear_aux_for_edges ();
343 /* Compute the insertion and deletion points for edge based LCM. */
346 compute_insert_delete (struct edge_list
*edge_list
, sbitmap
*antloc
,
347 sbitmap
*later
, sbitmap
*laterin
, sbitmap
*insert
,
353 FOR_EACH_BB_FN (bb
, cfun
)
354 bitmap_and_compl (del
[bb
->index
], antloc
[bb
->index
],
357 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
359 basic_block b
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
361 if (b
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
362 bitmap_and_compl (insert
[x
], later
[x
],
363 laterin
[last_basic_block_for_fn (cfun
)]);
365 bitmap_and_compl (insert
[x
], later
[x
], laterin
[b
->index
]);
369 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and
370 delete vectors for edge based LCM. Returns an edgelist which is used to
371 map the insert vector to what edge an expression should be inserted on. */
374 pre_edge_lcm (int n_exprs
, sbitmap
*transp
,
375 sbitmap
*avloc
, sbitmap
*antloc
, sbitmap
*kill
,
376 sbitmap
**insert
, sbitmap
**del
)
378 sbitmap
*antin
, *antout
, *earliest
;
379 sbitmap
*avin
, *avout
;
380 sbitmap
*later
, *laterin
;
381 struct edge_list
*edge_list
;
384 edge_list
= create_edge_list ();
385 num_edges
= NUM_EDGES (edge_list
);
387 #ifdef LCM_DEBUG_INFO
390 fprintf (dump_file
, "Edge List:\n");
391 verify_edge_list (dump_file
, edge_list
);
392 print_edge_list (dump_file
, edge_list
);
393 dump_bitmap_vector (dump_file
, "transp", "", transp
,
394 last_basic_block_for_fn (cfun
));
395 dump_bitmap_vector (dump_file
, "antloc", "", antloc
,
396 last_basic_block_for_fn (cfun
));
397 dump_bitmap_vector (dump_file
, "avloc", "", avloc
,
398 last_basic_block_for_fn (cfun
));
399 dump_bitmap_vector (dump_file
, "kill", "", kill
,
400 last_basic_block_for_fn (cfun
));
404 /* Compute global availability. */
405 avin
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), n_exprs
);
406 avout
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), n_exprs
);
407 compute_available (avloc
, kill
, avout
, avin
);
408 sbitmap_vector_free (avin
);
410 /* Compute global anticipatability. */
411 antin
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), n_exprs
);
412 antout
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), n_exprs
);
413 compute_antinout_edge (antloc
, transp
, antin
, antout
);
415 #ifdef LCM_DEBUG_INFO
418 dump_bitmap_vector (dump_file
, "antin", "", antin
,
419 last_basic_block_for_fn (cfun
));
420 dump_bitmap_vector (dump_file
, "antout", "", antout
,
421 last_basic_block_for_fn (cfun
));
425 /* Compute earliestness. */
426 earliest
= sbitmap_vector_alloc (num_edges
, n_exprs
);
427 compute_earliest (edge_list
, n_exprs
, antin
, antout
, avout
, kill
, earliest
);
429 #ifdef LCM_DEBUG_INFO
431 dump_bitmap_vector (dump_file
, "earliest", "", earliest
, num_edges
);
434 sbitmap_vector_free (antout
);
435 sbitmap_vector_free (antin
);
436 sbitmap_vector_free (avout
);
438 later
= sbitmap_vector_alloc (num_edges
, n_exprs
);
440 /* Allocate an extra element for the exit block in the laterin vector. */
441 laterin
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
) + 1,
443 compute_laterin (edge_list
, earliest
, antloc
, later
, laterin
);
445 #ifdef LCM_DEBUG_INFO
448 dump_bitmap_vector (dump_file
, "laterin", "", laterin
,
449 last_basic_block_for_fn (cfun
) + 1);
450 dump_bitmap_vector (dump_file
, "later", "", later
, num_edges
);
454 sbitmap_vector_free (earliest
);
456 *insert
= sbitmap_vector_alloc (num_edges
, n_exprs
);
457 *del
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), n_exprs
);
458 bitmap_vector_clear (*insert
, num_edges
);
459 bitmap_vector_clear (*del
, last_basic_block_for_fn (cfun
));
460 compute_insert_delete (edge_list
, antloc
, later
, laterin
, *insert
, *del
);
462 sbitmap_vector_free (laterin
);
463 sbitmap_vector_free (later
);
465 #ifdef LCM_DEBUG_INFO
468 dump_bitmap_vector (dump_file
, "pre_insert_map", "", *insert
, num_edges
);
469 dump_bitmap_vector (dump_file
, "pre_delete_map", "", *del
,
470 last_basic_block_for_fn (cfun
));
477 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
478 Return the number of passes we performed to iterate to a solution. */
481 compute_available (sbitmap
*avloc
, sbitmap
*kill
, sbitmap
*avout
,
485 basic_block
*worklist
, *qin
, *qout
, *qend
, bb
;
489 /* Allocate a worklist array/queue. Entries are only added to the
490 list if they were not already on the list. So the size is
491 bounded by the number of basic blocks. */
492 qin
= qout
= worklist
=
493 XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
495 /* We want a maximal solution. */
496 bitmap_vector_ones (avout
, last_basic_block_for_fn (cfun
));
498 /* Put every block on the worklist; this is necessary because of the
499 optimistic initialization of AVOUT above. */
500 FOR_EACH_BB_FN (bb
, cfun
)
507 qend
= &worklist
[n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
];
508 qlen
= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
;
510 /* Mark blocks which are successors of the entry block so that we
511 can easily identify them below. */
512 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
513 e
->dest
->aux
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
515 /* Iterate until the worklist is empty. */
518 /* Take the first entry off the worklist. */
525 /* If one of the predecessor blocks is the ENTRY block, then the
526 intersection of avouts is the null set. We can identify such blocks
527 by the special value in the AUX field in the block structure. */
528 if (bb
->aux
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
529 /* Do not clear the aux field for blocks which are successors of the
530 ENTRY block. That way we never add then to the worklist again. */
531 bitmap_clear (avin
[bb
->index
]);
534 /* Clear the aux field of this block so that it can be added to
535 the worklist again if necessary. */
537 bitmap_intersection_of_preds (avin
[bb
->index
], avout
, bb
);
540 if (bitmap_ior_and_compl (avout
[bb
->index
], avloc
[bb
->index
],
541 avin
[bb
->index
], kill
[bb
->index
]))
542 /* If the out state of this block changed, then we need
543 to add the successors of this block to the worklist
544 if they are not already on the worklist. */
545 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
546 if (!e
->dest
->aux
&& e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
557 clear_aux_for_edges ();
558 clear_aux_for_blocks ();
562 /* Compute the farthest vector for edge based lcm. */
565 compute_farthest (struct edge_list
*edge_list
, int n_exprs
,
566 sbitmap
*st_avout
, sbitmap
*st_avin
, sbitmap
*st_antin
,
567 sbitmap
*kill
, sbitmap
*farthest
)
569 sbitmap difference
, temp_bitmap
;
571 basic_block pred
, succ
;
573 num_edges
= NUM_EDGES (edge_list
);
575 difference
= sbitmap_alloc (n_exprs
);
576 temp_bitmap
= sbitmap_alloc (n_exprs
);
578 for (x
= 0; x
< num_edges
; x
++)
580 pred
= INDEX_EDGE_PRED_BB (edge_list
, x
);
581 succ
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
582 if (succ
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
583 bitmap_copy (farthest
[x
], st_avout
[pred
->index
]);
586 if (pred
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
587 bitmap_clear (farthest
[x
]);
590 bitmap_and_compl (difference
, st_avout
[pred
->index
],
591 st_antin
[succ
->index
]);
592 bitmap_not (temp_bitmap
, st_avin
[succ
->index
]);
593 bitmap_and_or (farthest
[x
], difference
,
594 kill
[succ
->index
], temp_bitmap
);
599 sbitmap_free (temp_bitmap
);
600 sbitmap_free (difference
);
603 /* Compute nearer and nearerout vectors for edge based lcm.
605 This is the mirror of compute_laterin, additional comments on the
606 implementation can be found before compute_laterin. */
609 compute_nearerout (struct edge_list
*edge_list
, sbitmap
*farthest
,
610 sbitmap
*st_avloc
, sbitmap
*nearer
, sbitmap
*nearerout
)
614 basic_block
*worklist
, *tos
, bb
;
617 num_edges
= NUM_EDGES (edge_list
);
619 /* Allocate a worklist array/queue. Entries are only added to the
620 list if they were not already on the list. So the size is
621 bounded by the number of basic blocks. */
622 tos
= worklist
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
) + 1);
624 /* Initialize NEARER for each edge and build a mapping from an edge to
626 for (i
= 0; i
< num_edges
; i
++)
627 INDEX_EDGE (edge_list
, i
)->aux
= (void *) (size_t) i
;
629 /* We want a maximal solution. */
630 bitmap_vector_ones (nearer
, num_edges
);
632 /* Note that even though we want an optimistic setting of NEARER, we
633 do not want to be overly optimistic. Consider an incoming edge to
634 the exit block. That edge should always have a NEARER value the
635 same as FARTHEST for that edge. */
636 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
637 bitmap_copy (nearer
[(size_t)e
->aux
], farthest
[(size_t)e
->aux
]);
639 /* Add all the blocks to the worklist. This prevents an early exit
640 from the loop given our optimistic initialization of NEARER. */
641 FOR_EACH_BB_FN (bb
, cfun
)
647 /* Iterate until the worklist is empty. */
648 while (tos
!= worklist
)
650 /* Take the first entry off the worklist. */
654 /* Compute the intersection of NEARER for each outgoing edge from B. */
655 bitmap_ones (nearerout
[bb
->index
]);
656 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
657 bitmap_and (nearerout
[bb
->index
], nearerout
[bb
->index
],
658 nearer
[(size_t) e
->aux
]);
660 /* Calculate NEARER for all incoming edges. */
661 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
662 if (bitmap_ior_and_compl (nearer
[(size_t) e
->aux
],
663 farthest
[(size_t) e
->aux
],
664 nearerout
[e
->dest
->index
],
665 st_avloc
[e
->dest
->index
])
666 /* If NEARER for an incoming edge was changed, then we need
667 to add the source of the incoming edge to the worklist. */
668 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && e
->src
->aux
== 0)
675 /* Computation of insertion and deletion points requires computing NEAREROUT
676 for the ENTRY block. We allocated an extra entry in the NEAREROUT array
677 for just this purpose. */
678 bitmap_ones (nearerout
[last_basic_block_for_fn (cfun
)]);
679 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
680 bitmap_and (nearerout
[last_basic_block_for_fn (cfun
)],
681 nearerout
[last_basic_block_for_fn (cfun
)],
682 nearer
[(size_t) e
->aux
]);
684 clear_aux_for_edges ();
688 /* Compute the insertion and deletion points for edge based LCM. */
691 compute_rev_insert_delete (struct edge_list
*edge_list
, sbitmap
*st_avloc
,
692 sbitmap
*nearer
, sbitmap
*nearerout
,
693 sbitmap
*insert
, sbitmap
*del
)
698 FOR_EACH_BB_FN (bb
, cfun
)
699 bitmap_and_compl (del
[bb
->index
], st_avloc
[bb
->index
],
700 nearerout
[bb
->index
]);
702 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
704 basic_block b
= INDEX_EDGE_PRED_BB (edge_list
, x
);
705 if (b
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
706 bitmap_and_compl (insert
[x
], nearer
[x
],
707 nearerout
[last_basic_block_for_fn (cfun
)]);
709 bitmap_and_compl (insert
[x
], nearer
[x
], nearerout
[b
->index
]);
713 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
714 insert and delete vectors for edge based reverse LCM. Returns an
715 edgelist which is used to map the insert vector to what edge
716 an expression should be inserted on. */
719 pre_edge_rev_lcm (int n_exprs
, sbitmap
*transp
,
720 sbitmap
*st_avloc
, sbitmap
*st_antloc
, sbitmap
*kill
,
721 sbitmap
**insert
, sbitmap
**del
)
723 sbitmap
*st_antin
, *st_antout
;
724 sbitmap
*st_avout
, *st_avin
, *farthest
;
725 sbitmap
*nearer
, *nearerout
;
726 struct edge_list
*edge_list
;
729 edge_list
= create_edge_list ();
730 num_edges
= NUM_EDGES (edge_list
);
732 st_antin
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), n_exprs
);
733 st_antout
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), n_exprs
);
734 bitmap_vector_clear (st_antin
, last_basic_block_for_fn (cfun
));
735 bitmap_vector_clear (st_antout
, last_basic_block_for_fn (cfun
));
736 compute_antinout_edge (st_antloc
, transp
, st_antin
, st_antout
);
738 /* Compute global anticipatability. */
739 st_avout
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), n_exprs
);
740 st_avin
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), n_exprs
);
741 compute_available (st_avloc
, kill
, st_avout
, st_avin
);
743 #ifdef LCM_DEBUG_INFO
746 fprintf (dump_file
, "Edge List:\n");
747 verify_edge_list (dump_file
, edge_list
);
748 print_edge_list (dump_file
, edge_list
);
749 dump_bitmap_vector (dump_file
, "transp", "", transp
,
750 last_basic_block_for_fn (cfun
));
751 dump_bitmap_vector (dump_file
, "st_avloc", "", st_avloc
,
752 last_basic_block_for_fn (cfun
));
753 dump_bitmap_vector (dump_file
, "st_antloc", "", st_antloc
,
754 last_basic_block_for_fn (cfun
));
755 dump_bitmap_vector (dump_file
, "st_antin", "", st_antin
,
756 last_basic_block_for_fn (cfun
));
757 dump_bitmap_vector (dump_file
, "st_antout", "", st_antout
,
758 last_basic_block_for_fn (cfun
));
759 dump_bitmap_vector (dump_file
, "st_kill", "", kill
,
760 last_basic_block_for_fn (cfun
));
764 #ifdef LCM_DEBUG_INFO
767 dump_bitmap_vector (dump_file
, "st_avout", "", st_avout
, last_basic_block_for_fn (cfun
));
768 dump_bitmap_vector (dump_file
, "st_avin", "", st_avin
, last_basic_block_for_fn (cfun
));
772 /* Compute farthestness. */
773 farthest
= sbitmap_vector_alloc (num_edges
, n_exprs
);
774 compute_farthest (edge_list
, n_exprs
, st_avout
, st_avin
, st_antin
,
777 #ifdef LCM_DEBUG_INFO
779 dump_bitmap_vector (dump_file
, "farthest", "", farthest
, num_edges
);
782 sbitmap_vector_free (st_antin
);
783 sbitmap_vector_free (st_antout
);
785 sbitmap_vector_free (st_avin
);
786 sbitmap_vector_free (st_avout
);
788 nearer
= sbitmap_vector_alloc (num_edges
, n_exprs
);
790 /* Allocate an extra element for the entry block. */
791 nearerout
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
) + 1,
793 compute_nearerout (edge_list
, farthest
, st_avloc
, nearer
, nearerout
);
795 #ifdef LCM_DEBUG_INFO
798 dump_bitmap_vector (dump_file
, "nearerout", "", nearerout
,
799 last_basic_block_for_fn (cfun
) + 1);
800 dump_bitmap_vector (dump_file
, "nearer", "", nearer
, num_edges
);
804 sbitmap_vector_free (farthest
);
806 *insert
= sbitmap_vector_alloc (num_edges
, n_exprs
);
807 *del
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), n_exprs
);
808 compute_rev_insert_delete (edge_list
, st_avloc
, nearer
, nearerout
,
811 sbitmap_vector_free (nearerout
);
812 sbitmap_vector_free (nearer
);
814 #ifdef LCM_DEBUG_INFO
817 dump_bitmap_vector (dump_file
, "pre_insert_map", "", *insert
, num_edges
);
818 dump_bitmap_vector (dump_file
, "pre_delete_map", "", *del
,
819 last_basic_block_for_fn (cfun
));