1 /* Generic partial redundancy elimination with lazy code motion support.
2 Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
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. */
56 #include "hard-reg-set.h"
59 #include "insn-config.h"
61 #include "basic-block.h"
64 /* We want target macros for the mode switching code to be able to refer
65 to instruction attribute values. */
66 #include "insn-attr.h"
68 /* Edge based LCM routines. */
69 static void compute_antinout_edge
PARAMS ((sbitmap
*, sbitmap
*,
70 sbitmap
*, sbitmap
*));
71 static void compute_earliest
PARAMS ((struct edge_list
*, int,
75 static void compute_laterin
PARAMS ((struct edge_list
*, sbitmap
*,
78 static void compute_insert_delete
PARAMS ((struct edge_list
*edge_list
,
83 /* Edge based LCM routines on a reverse flowgraph. */
84 static void compute_farthest
PARAMS ((struct edge_list
*, int,
88 static void compute_nearerout
PARAMS ((struct edge_list
*, sbitmap
*,
91 static void compute_rev_insert_delete
PARAMS ((struct edge_list
*edge_list
,
96 /* Edge based lcm routines. */
98 /* Compute expression anticipatability at entrance and exit of each block.
99 This is done based on the flow graph, and not on the pred-succ lists.
100 Other than that, its pretty much identical to compute_antinout. */
103 compute_antinout_edge (antloc
, transp
, antin
, antout
)
111 basic_block
*worklist
, *tos
;
113 /* Allocate a worklist array/queue. Entries are only added to the
114 list if they were not already on the list. So the size is
115 bounded by the number of basic blocks. */
117 = (basic_block
*) xmalloc (sizeof (basic_block
) * n_basic_blocks
);
119 /* We want a maximal solution, so make an optimistic initialization of
121 sbitmap_vector_ones (antin
, n_basic_blocks
);
123 /* Put every block on the worklist; this is necessary because of the
124 optimistic initialization of ANTIN above. */
125 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
127 *tos
++ = BASIC_BLOCK (bb
);
128 BASIC_BLOCK (bb
)->aux
= BASIC_BLOCK (bb
);
131 /* Mark blocks which are predecessors of the exit block so that we
132 can easily identify them below. */
133 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
134 e
->src
->aux
= EXIT_BLOCK_PTR
;
136 /* Iterate until the worklist is empty. */
137 while (tos
!= worklist
)
139 /* Take the first entry off the worklist. */
140 basic_block b
= *--tos
;
143 if (b
->aux
== EXIT_BLOCK_PTR
)
144 /* Do not clear the aux field for blocks which are predecessors of
145 the EXIT block. That way we never add then to the worklist
147 sbitmap_zero (antout
[bb
]);
150 /* Clear the aux field of this block so that it can be added to
151 the worklist again if necessary. */
153 sbitmap_intersection_of_succs (antout
[bb
], antin
, bb
);
156 if (sbitmap_a_or_b_and_c (antin
[bb
], antloc
[bb
], transp
[bb
], antout
[bb
]))
157 /* If the in state of this block changed, then we need
158 to add the predecessors of this block to the worklist
159 if they are not already on the worklist. */
160 for (e
= b
->pred
; e
; e
= e
->pred_next
)
161 if (!e
->src
->aux
&& e
->src
!= ENTRY_BLOCK_PTR
)
171 /* Compute the earliest vector for edge based lcm. */
174 compute_earliest (edge_list
, n_exprs
, antin
, antout
, avout
, kill
, earliest
)
175 struct edge_list
*edge_list
;
177 sbitmap
*antin
, *antout
, *avout
, *kill
, *earliest
;
179 sbitmap difference
, temp_bitmap
;
181 basic_block pred
, succ
;
183 num_edges
= NUM_EDGES (edge_list
);
185 difference
= sbitmap_alloc (n_exprs
);
186 temp_bitmap
= sbitmap_alloc (n_exprs
);
188 for (x
= 0; x
< num_edges
; x
++)
190 pred
= INDEX_EDGE_PRED_BB (edge_list
, x
);
191 succ
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
192 if (pred
== ENTRY_BLOCK_PTR
)
193 sbitmap_copy (earliest
[x
], antin
[succ
->index
]);
196 if (succ
== EXIT_BLOCK_PTR
)
197 sbitmap_zero (earliest
[x
]);
200 sbitmap_difference (difference
, antin
[succ
->index
],
202 sbitmap_not (temp_bitmap
, antout
[pred
->index
]);
203 sbitmap_a_and_b_or_c (earliest
[x
], difference
,
204 kill
[pred
->index
], temp_bitmap
);
213 /* later(p,s) is dependent on the calculation of laterin(p).
214 laterin(p) is dependent on the calculation of later(p2,p).
216 laterin(ENTRY) is defined as all 0's
217 later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY)
218 laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)).
220 If we progress in this manner, starting with all basic blocks
221 in the work list, anytime we change later(bb), we need to add
222 succs(bb) to the worklist if they are not already on the worklist.
226 We prime the worklist all the normal basic blocks. The ENTRY block can
227 never be added to the worklist since it is never the successor of any
228 block. We explicitly prevent the EXIT block from being added to the
231 We optimistically initialize LATER. That is the only time this routine
232 will compute LATER for an edge out of the entry block since the entry
233 block is never on the worklist. Thus, LATERIN is neither used nor
234 computed for the ENTRY block.
236 Since the EXIT block is never added to the worklist, we will neither
237 use nor compute LATERIN for the exit block. Edges which reach the
238 EXIT block are handled in the normal fashion inside the loop. However,
239 the insertion/deletion computation needs LATERIN(EXIT), so we have
243 compute_laterin (edge_list
, earliest
, antloc
, later
, laterin
)
244 struct edge_list
*edge_list
;
245 sbitmap
*earliest
, *antloc
, *later
, *laterin
;
247 int bb
, num_edges
, i
;
249 basic_block
*worklist
, *tos
;
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. */
257 = (basic_block
*) xmalloc (sizeof (basic_block
) * (n_basic_blocks
+ 1));
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 sbitmap_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 (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
280 sbitmap_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 (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
286 basic_block b
= BASIC_BLOCK (bb
);
291 /* Iterate until the worklist is empty. */
292 while (tos
!= worklist
)
294 /* Take the first entry off the worklist. */
295 basic_block b
= *--tos
;
298 /* Compute the intersection of LATERIN for each incoming edge to B. */
300 sbitmap_ones (laterin
[bb
]);
301 for (e
= b
->pred
; e
!= NULL
; e
= e
->pred_next
)
302 sbitmap_a_and_b (laterin
[bb
], laterin
[bb
], later
[(size_t)e
->aux
]);
304 /* Calculate LATER for all outgoing edges. */
305 for (e
= b
->succ
; e
!= NULL
; e
= e
->succ_next
)
306 if (sbitmap_union_of_diff (later
[(size_t) e
->aux
],
307 earliest
[(size_t) e
->aux
],
308 laterin
[e
->src
->index
],
309 antloc
[e
->src
->index
])
310 /* If LATER for an outgoing edge was changed, then we need
311 to add the target of the outgoing edge to the worklist. */
312 && e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
->aux
== 0)
319 /* Computation of insertion and deletion points requires computing LATERIN
320 for the EXIT block. We allocated an extra entry in the LATERIN array
321 for just this purpose. */
322 sbitmap_ones (laterin
[n_basic_blocks
]);
323 for (e
= EXIT_BLOCK_PTR
->pred
; e
!= NULL
; e
= e
->pred_next
)
324 sbitmap_a_and_b (laterin
[n_basic_blocks
],
325 laterin
[n_basic_blocks
],
326 later
[(size_t) e
->aux
]);
331 /* 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
);
348 if (b
== EXIT_BLOCK_PTR
)
349 sbitmap_difference (insert
[x
], later
[x
], laterin
[n_basic_blocks
]);
351 sbitmap_difference (insert
[x
], later
[x
], laterin
[b
->index
]);
355 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and
356 delete vectors for edge based LCM. Returns an edgelist which is used to
357 map the insert vector to what edge 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
);
398 /* Compute global anticipatability. */
399 antin
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
400 antout
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
401 compute_antinout_edge (antloc
, transp
, antin
, antout
);
403 #ifdef LCM_DEBUG_INFO
406 dump_sbitmap_vector (file
, "antin", "", antin
, n_basic_blocks
);
407 dump_sbitmap_vector (file
, "antout", "", antout
, n_basic_blocks
);
411 /* Compute earliestness. */
412 earliest
= sbitmap_vector_alloc (num_edges
, n_exprs
);
413 compute_earliest (edge_list
, n_exprs
, antin
, antout
, avout
, kill
, earliest
);
415 #ifdef LCM_DEBUG_INFO
417 dump_sbitmap_vector (file
, "earliest", "", earliest
, num_edges
);
424 later
= sbitmap_vector_alloc (num_edges
, n_exprs
);
426 /* Allocate an extra element for the exit block in the laterin vector. */
427 laterin
= sbitmap_vector_alloc (n_basic_blocks
+ 1, n_exprs
);
428 compute_laterin (edge_list
, earliest
, antloc
, later
, laterin
);
430 #ifdef LCM_DEBUG_INFO
433 dump_sbitmap_vector (file
, "laterin", "", laterin
, n_basic_blocks
+ 1);
434 dump_sbitmap_vector (file
, "later", "", later
, num_edges
);
440 *insert
= sbitmap_vector_alloc (num_edges
, n_exprs
);
441 *delete = sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
442 compute_insert_delete (edge_list
, antloc
, later
, laterin
, *insert
, *delete);
447 #ifdef LCM_DEBUG_INFO
450 dump_sbitmap_vector (file
, "pre_insert_map", "", *insert
, num_edges
);
451 dump_sbitmap_vector (file
, "pre_delete_map", "", *delete,
459 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
460 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. */
474 = (basic_block
*) xmalloc (sizeof (basic_block
) * n_basic_blocks
);
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
)
503 /* Do not clear the aux field for blocks which are successors of the
504 ENTRY block. That way we never add then to the worklist again. */
505 sbitmap_zero (avin
[bb
]);
508 /* Clear the aux field of this block so that it can be added to
509 the worklist again if necessary. */
511 sbitmap_intersection_of_preds (avin
[bb
], avout
, bb
);
514 if (sbitmap_union_of_diff (avout
[bb
], avloc
[bb
], avin
[bb
], kill
[bb
]))
515 /* If the out state of this block changed, then we need
516 to add the successors of this block to the worklist
517 if they are not already on the worklist. */
518 for (e
= b
->succ
; e
; e
= e
->succ_next
)
519 if (!e
->dest
->aux
&& e
->dest
!= EXIT_BLOCK_PTR
)
529 /* Compute the farthest vector for edge based lcm. */
532 compute_farthest (edge_list
, n_exprs
, st_avout
, st_avin
, st_antin
,
534 struct edge_list
*edge_list
;
536 sbitmap
*st_avout
, *st_avin
, *st_antin
, *kill
, *farthest
;
538 sbitmap difference
, temp_bitmap
;
540 basic_block pred
, succ
;
542 num_edges
= NUM_EDGES (edge_list
);
544 difference
= sbitmap_alloc (n_exprs
);
545 temp_bitmap
= sbitmap_alloc (n_exprs
);
547 for (x
= 0; x
< num_edges
; x
++)
549 pred
= INDEX_EDGE_PRED_BB (edge_list
, x
);
550 succ
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
551 if (succ
== EXIT_BLOCK_PTR
)
552 sbitmap_copy (farthest
[x
], st_avout
[pred
->index
]);
555 if (pred
== ENTRY_BLOCK_PTR
)
556 sbitmap_zero (farthest
[x
]);
559 sbitmap_difference (difference
, st_avout
[pred
->index
],
560 st_antin
[succ
->index
]);
561 sbitmap_not (temp_bitmap
, st_avin
[succ
->index
]);
562 sbitmap_a_and_b_or_c (farthest
[x
], difference
,
563 kill
[succ
->index
], temp_bitmap
);
572 /* Compute nearer and nearerout vectors for edge based lcm.
574 This is the mirror of compute_laterin, additional comments on the
575 implementation can be found before compute_laterin. */
578 compute_nearerout (edge_list
, farthest
, st_avloc
, nearer
, nearerout
)
579 struct edge_list
*edge_list
;
580 sbitmap
*farthest
, *st_avloc
, *nearer
, *nearerout
;
582 int bb
, num_edges
, i
;
584 basic_block
*worklist
, *tos
;
586 num_edges
= NUM_EDGES (edge_list
);
588 /* Allocate a worklist array/queue. Entries are only added to the
589 list if they were not already on the list. So the size is
590 bounded by the number of basic blocks. */
592 = (basic_block
*) xmalloc (sizeof (basic_block
) * (n_basic_blocks
+ 1));
594 /* Initialize NEARER for each edge and build a mapping from an edge to
596 for (i
= 0; i
< num_edges
; i
++)
597 INDEX_EDGE (edge_list
, i
)->aux
= (void *) (size_t) i
;
599 /* We want a maximal solution. */
600 sbitmap_vector_ones (nearer
, num_edges
);
602 /* Note that even though we want an optimistic setting of NEARER, we
603 do not want to be overly optimistic. Consider an incoming edge to
604 the exit block. That edge should always have a NEARER value the
605 same as FARTHEST for that edge. */
606 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
607 sbitmap_copy (nearer
[(size_t)e
->aux
], farthest
[(size_t)e
->aux
]);
609 /* Add all the blocks to the worklist. This prevents an early exit
610 from the loop given our optimistic initialization of NEARER. */
611 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
613 basic_block b
= BASIC_BLOCK (bb
);
618 /* Iterate until the worklist is empty. */
619 while (tos
!= worklist
)
621 /* Take the first entry off the worklist. */
622 basic_block b
= *--tos
;
625 /* Compute the intersection of NEARER for each outgoing edge from B. */
627 sbitmap_ones (nearerout
[bb
]);
628 for (e
= b
->succ
; e
!= NULL
; e
= e
->succ_next
)
629 sbitmap_a_and_b (nearerout
[bb
], nearerout
[bb
],
630 nearer
[(size_t) e
->aux
]);
632 /* Calculate NEARER for all incoming edges. */
633 for (e
= b
->pred
; e
!= NULL
; e
= e
->pred_next
)
634 if (sbitmap_union_of_diff (nearer
[(size_t) e
->aux
],
635 farthest
[(size_t) e
->aux
],
636 nearerout
[e
->dest
->index
],
637 st_avloc
[e
->dest
->index
])
638 /* If NEARER for an incoming edge was changed, then we need
639 to add the source of the incoming edge to the worklist. */
640 && e
->src
!= ENTRY_BLOCK_PTR
&& e
->src
->aux
== 0)
647 /* Computation of insertion and deletion points requires computing NEAREROUT
648 for the ENTRY block. We allocated an extra entry in the NEAREROUT array
649 for just this purpose. */
650 sbitmap_ones (nearerout
[n_basic_blocks
]);
651 for (e
= ENTRY_BLOCK_PTR
->succ
; e
!= NULL
; e
= e
->succ_next
)
652 sbitmap_a_and_b (nearerout
[n_basic_blocks
],
653 nearerout
[n_basic_blocks
],
654 nearer
[(size_t) e
->aux
]);
659 /* Compute the insertion and deletion points for edge based LCM. */
662 compute_rev_insert_delete (edge_list
, st_avloc
, nearer
, nearerout
,
664 struct edge_list
*edge_list
;
665 sbitmap
*st_avloc
, *nearer
, *nearerout
, *insert
, *delete;
669 for (x
= 0; x
< n_basic_blocks
; x
++)
670 sbitmap_difference (delete[x
], st_avloc
[x
], nearerout
[x
]);
672 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
674 basic_block b
= INDEX_EDGE_PRED_BB (edge_list
, x
);
675 if (b
== ENTRY_BLOCK_PTR
)
676 sbitmap_difference (insert
[x
], nearer
[x
], nearerout
[n_basic_blocks
]);
678 sbitmap_difference (insert
[x
], nearer
[x
], nearerout
[b
->index
]);
682 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
683 insert and delete vectors for edge based reverse LCM. Returns an
684 edgelist which is used to map the insert vector to what edge
685 an expression should be inserted on. */
688 pre_edge_rev_lcm (file
, n_exprs
, transp
, st_avloc
, st_antloc
, kill
,
690 FILE *file ATTRIBUTE_UNUSED
;
699 sbitmap
*st_antin
, *st_antout
;
700 sbitmap
*st_avout
, *st_avin
, *farthest
;
701 sbitmap
*nearer
, *nearerout
;
702 struct edge_list
*edge_list
;
705 edge_list
= create_edge_list ();
706 num_edges
= NUM_EDGES (edge_list
);
708 st_antin
= (sbitmap
*) sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
709 st_antout
= (sbitmap
*) sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
710 sbitmap_vector_zero (st_antin
, n_basic_blocks
);
711 sbitmap_vector_zero (st_antout
, n_basic_blocks
);
712 compute_antinout_edge (st_antloc
, transp
, st_antin
, st_antout
);
714 /* Compute global anticipatability. */
715 st_avout
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
716 st_avin
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
717 compute_available (st_avloc
, kill
, st_avout
, st_avin
);
719 #ifdef LCM_DEBUG_INFO
722 fprintf (file
, "Edge List:\n");
723 verify_edge_list (file
, edge_list
);
724 print_edge_list (file
, edge_list
);
725 dump_sbitmap_vector (file
, "transp", "", transp
, n_basic_blocks
);
726 dump_sbitmap_vector (file
, "st_avloc", "", st_avloc
, n_basic_blocks
);
727 dump_sbitmap_vector (file
, "st_antloc", "", st_antloc
, n_basic_blocks
);
728 dump_sbitmap_vector (file
, "st_antin", "", st_antin
, n_basic_blocks
);
729 dump_sbitmap_vector (file
, "st_antout", "", st_antout
, n_basic_blocks
);
730 dump_sbitmap_vector (file
, "st_kill", "", kill
, n_basic_blocks
);
734 #ifdef LCM_DEBUG_INFO
737 dump_sbitmap_vector (file
, "st_avout", "", st_avout
, n_basic_blocks
);
738 dump_sbitmap_vector (file
, "st_avin", "", st_avin
, n_basic_blocks
);
742 /* Compute farthestness. */
743 farthest
= sbitmap_vector_alloc (num_edges
, n_exprs
);
744 compute_farthest (edge_list
, n_exprs
, st_avout
, st_avin
, st_antin
,
747 #ifdef LCM_DEBUG_INFO
749 dump_sbitmap_vector (file
, "farthest", "", farthest
, num_edges
);
755 nearer
= sbitmap_vector_alloc (num_edges
, n_exprs
);
757 /* Allocate an extra element for the entry block. */
758 nearerout
= sbitmap_vector_alloc (n_basic_blocks
+ 1, n_exprs
);
759 compute_nearerout (edge_list
, farthest
, st_avloc
, nearer
, nearerout
);
761 #ifdef LCM_DEBUG_INFO
764 dump_sbitmap_vector (file
, "nearerout", "", nearerout
,
766 dump_sbitmap_vector (file
, "nearer", "", nearer
, num_edges
);
772 *insert
= sbitmap_vector_alloc (num_edges
, n_exprs
);
773 *delete = sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
774 compute_rev_insert_delete (edge_list
, st_avloc
, nearer
, nearerout
,
780 #ifdef LCM_DEBUG_INFO
783 dump_sbitmap_vector (file
, "pre_insert_map", "", *insert
, num_edges
);
784 dump_sbitmap_vector (file
, "pre_delete_map", "", *delete,
794 The algorithm for setting the modes consists of scanning the insn list
795 and finding all the insns which require a specific mode. Each insn gets
796 a unique struct seginfo element. These structures are inserted into a list
797 for each basic block. For each entity, there is an array of bb_info over
798 the flow graph basic blocks (local var 'bb_info'), and contains a list
799 of all insns within that basic block, in the order they are encountered.
801 For each entity, any basic block WITHOUT any insns requiring a specific
802 mode are given a single entry, without a mode. (Each basic block
803 in the flow graph must have at least one entry in the segment table.)
805 The LCM algorithm is then run over the flow graph to determine where to
806 place the sets to the highest-priority value in respect of first the first
807 insn in any one block. Any adjustments required to the transparancy
808 vectors are made, then the next iteration starts for the next-lower
809 priority mode, till for each entity all modes are exhasted.
811 More details are located in the code for optimize_mode_switching(). */
813 /* This structure contains the information for each insn which requires
814 either single or double mode to be set.
815 MODE is the mode this insn must be executed in.
816 INSN_PTR is the insn to be executed.
817 BBNUM is the flow graph basic block this insn occurs in.
818 NEXT is the next insn in the same basic block. */
824 struct seginfo
*next
;
825 HARD_REG_SET regs_live
;
830 struct seginfo
*seginfo
;
834 /* These bitmaps are used for the LCM algorithm. */
836 #ifdef OPTIMIZE_MODE_SWITCHING
837 static sbitmap
*antic
;
838 static sbitmap
*transp
;
839 static sbitmap
*comp
;
840 static sbitmap
*delete;
841 static sbitmap
*insert
;
843 static struct seginfo
* new_seginfo
PARAMS ((int, rtx
, int, HARD_REG_SET
));;
844 static void add_seginfo
PARAMS ((struct bb_info
*, struct seginfo
*));
845 static void reg_dies
PARAMS ((rtx
, HARD_REG_SET
));
846 static void reg_becomes_live
PARAMS ((rtx
, rtx
, void *));
847 static void make_preds_opaque
PARAMS ((basic_block
, int));
850 #ifdef OPTIMIZE_MODE_SWITCHING
852 /* This function will allocate a new BBINFO structure, initialized
853 with the FP_MODE, INSN, and basic block BB parameters. */
855 static struct seginfo
*
856 new_seginfo (mode
, insn
, bb
, regs_live
)
860 HARD_REG_SET regs_live
;
863 ptr
= xmalloc (sizeof (struct seginfo
));
865 ptr
->insn_ptr
= insn
;
868 COPY_HARD_REG_SET (ptr
->regs_live
, regs_live
);
872 /* Add a seginfo element to the end of a list.
873 HEAD is a pointer to the list beginning.
874 INFO is the structure to be linked in. */
877 add_seginfo (head
, info
)
878 struct bb_info
*head
;
879 struct seginfo
*info
;
883 if (head
->seginfo
== NULL
)
884 head
->seginfo
= info
;
888 while (ptr
->next
!= NULL
)
894 /* Make all predecessors of basic block B opaque, recursively, till we hit
895 some that are already non-transparent, or an edge where aux is set; that
896 denotes that a mode set is to be done on that edge.
897 J is the bit number in the bitmaps that corresponds to the entity that
898 we are currently handling mode-switching for. */
901 make_preds_opaque (b
, j
)
907 for (e
= b
->pred
; e
; e
= e
->pred_next
)
909 basic_block pb
= e
->src
;
911 if (e
->aux
|| ! TEST_BIT (transp
[pb
->index
], j
))
914 RESET_BIT (transp
[pb
->index
], j
);
915 make_preds_opaque (pb
, j
);
919 /* Record in LIVE that register REG died. */
928 if (GET_CODE (reg
) != REG
)
932 if (regno
< FIRST_PSEUDO_REGISTER
)
933 for (nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
)) - 1; nregs
>= 0;
935 CLEAR_HARD_REG_BIT (live
, regno
+ nregs
);
938 /* Record in LIVE that register REG became live.
939 This is called via note_stores. */
942 reg_becomes_live (reg
, setter
, live
)
944 rtx setter ATTRIBUTE_UNUSED
;
949 if (GET_CODE (reg
) == SUBREG
)
950 reg
= SUBREG_REG (reg
);
952 if (GET_CODE (reg
) != REG
)
956 if (regno
< FIRST_PSEUDO_REGISTER
)
957 for (nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
)) - 1; nregs
>= 0;
959 SET_HARD_REG_BIT (* (HARD_REG_SET
*) live
, regno
+ nregs
);
962 /* Find all insns that need a particular mode setting, and insert the
963 necessary mode switches. Return true if we did work. */
966 optimize_mode_switching (file
)
974 struct edge_list
*edge_list
;
975 static int num_modes
[] = NUM_MODES_FOR_MODE_SWITCHING
;
976 #define N_ENTITIES (sizeof num_modes / sizeof (int))
977 int entity_map
[N_ENTITIES
];
978 struct bb_info
*bb_info
[N_ENTITIES
];
981 int max_num_modes
= 0;
983 for (e
= N_ENTITIES
- 1, n_entities
= 0; e
>= 0; e
--)
984 if (OPTIMIZE_MODE_SWITCHING (e
))
986 /* Create the list of segments within each basic block. */
988 = (struct bb_info
*) xcalloc (n_basic_blocks
, sizeof **bb_info
);
989 entity_map
[n_entities
++] = e
;
990 if (num_modes
[e
] > max_num_modes
)
991 max_num_modes
= num_modes
[e
];
997 #ifdef MODE_USES_IN_EXIT_BLOCK
998 /* For some ABIs a particular mode setting is required at function exit. */
1000 for (eg
= EXIT_BLOCK_PTR
->pred
; eg
; eg
= eg
->pred_next
)
1002 int bb
= eg
->src
->index
;
1003 rtx insn
= BLOCK_END (bb
);
1004 rtx use
= MODE_USES_IN_EXIT_BLOCK
;
1006 /* If the block ends with the use of the return value
1007 and / or a return, insert the new use(s) in front of them. */
1008 while ((GET_CODE (insn
) == INSN
&& GET_CODE (PATTERN (insn
)) == USE
)
1009 || GET_CODE (insn
) == JUMP_INSN
)
1010 insn
= PREV_INSN (insn
);
1012 use
= emit_insn_after (use
, insn
);
1013 if (insn
== BLOCK_END (bb
))
1014 BLOCK_END (bb
) = use
;
1015 else if (NEXT_INSN (use
) == BLOCK_HEAD (bb
))
1016 BLOCK_HEAD (bb
) = NEXT_INSN (insn
);
1018 #endif /* MODE_USES_IN_EXIT_BLOCK */
1020 /* Create the bitmap vectors. */
1022 antic
= sbitmap_vector_alloc (n_basic_blocks
, n_entities
);
1023 transp
= sbitmap_vector_alloc (n_basic_blocks
, n_entities
);
1024 comp
= sbitmap_vector_alloc (n_basic_blocks
, n_entities
);
1026 sbitmap_vector_ones (transp
, n_basic_blocks
);
1028 for (j
= n_entities
- 1; j
>= 0; j
--)
1030 int e
= entity_map
[j
];
1031 int no_mode
= num_modes
[e
];
1032 struct bb_info
*info
= bb_info
[j
];
1034 /* Determine what the first use (if any) need for a mode of entity E is.
1035 This will be the mode that is anticipatable for this block.
1036 Also compute the initial transparency settings. */
1037 for (bb
= 0 ; bb
< n_basic_blocks
; bb
++)
1039 struct seginfo
*ptr
;
1040 int last_mode
= no_mode
;
1041 HARD_REG_SET live_now
;
1043 REG_SET_TO_HARD_REG_SET (live_now
,
1044 BASIC_BLOCK (bb
)->global_live_at_start
);
1045 for (insn
= BLOCK_HEAD (bb
);
1046 insn
!= NULL
&& insn
!= NEXT_INSN (BLOCK_END (bb
));
1047 insn
= NEXT_INSN (insn
))
1049 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
1051 int mode
= MODE_NEEDED (e
, insn
);
1054 if (mode
!= no_mode
&& mode
!= last_mode
)
1057 ptr
= new_seginfo (mode
, insn
, bb
, live_now
);
1058 add_seginfo (info
+ bb
, ptr
);
1059 RESET_BIT (transp
[bb
], j
);
1062 /* Update LIVE_NOW. */
1063 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1064 if (REG_NOTE_KIND (link
) == REG_DEAD
)
1065 reg_dies (XEXP (link
, 0), live_now
);
1067 note_stores (PATTERN (insn
), reg_becomes_live
, &live_now
);
1068 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1069 if (REG_NOTE_KIND (link
) == REG_UNUSED
)
1070 reg_dies (XEXP (link
, 0), live_now
);
1074 info
[bb
].computing
= last_mode
;
1075 /* Check for blocks without ANY mode requirements. */
1076 if (last_mode
== no_mode
)
1078 ptr
= new_seginfo (no_mode
, insn
, bb
, live_now
);
1079 add_seginfo (info
+ bb
, ptr
);
1082 #ifdef MODE_AT_ENTRY
1084 int mode
= MODE_AT_ENTRY (e
);
1086 if (mode
!= no_mode
)
1088 for (eg
= ENTRY_BLOCK_PTR
->succ
; eg
; eg
= eg
->succ_next
)
1090 bb
= eg
->dest
->index
;
1092 /* By always making this nontransparent, we save
1093 an extra check in make_preds_opaque. We also
1094 need this to avoid confusing pre_edge_lcm when
1095 antic is cleared but transp and comp are set. */
1096 RESET_BIT (transp
[bb
], j
);
1098 /* If the block already has MODE, pretend it
1099 has none (because we don't need to set it),
1100 but retain whatever mode it computes. */
1101 if (info
[bb
].seginfo
->mode
== mode
)
1102 info
[bb
].seginfo
->mode
= no_mode
;
1104 /* Insert a fake computing definition of MODE into entry
1105 blocks which compute no mode. This represents the mode on
1107 else if (info
[bb
].computing
== no_mode
)
1109 info
[bb
].computing
= mode
;
1110 info
[bb
].seginfo
->mode
= no_mode
;
1115 #endif /* MODE_AT_ENTRY */
1118 kill
= sbitmap_vector_alloc (n_basic_blocks
, n_entities
);
1119 for (i
= 0; i
< max_num_modes
; i
++)
1121 int current_mode
[N_ENTITIES
];
1123 /* Set the anticipatable and computing arrays. */
1124 sbitmap_vector_zero (antic
, n_basic_blocks
);
1125 sbitmap_vector_zero (comp
, n_basic_blocks
);
1126 for (j
= n_entities
- 1; j
>= 0; j
--)
1128 int m
= current_mode
[j
] = MODE_PRIORITY_TO_MODE (entity_map
[j
], i
);
1129 struct bb_info
*info
= bb_info
[j
];
1131 for (bb
= 0 ; bb
< n_basic_blocks
; bb
++)
1133 if (info
[bb
].seginfo
->mode
== m
)
1134 SET_BIT (antic
[bb
], j
);
1136 if (info
[bb
].computing
== m
)
1137 SET_BIT (comp
[bb
], j
);
1141 /* Calculate the optimal locations for the
1142 placement mode switches to modes with priority I. */
1144 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
1145 sbitmap_not (kill
[bb
], transp
[bb
]);
1146 edge_list
= pre_edge_lcm (file
, 1, transp
, comp
, antic
,
1147 kill
, &insert
, &delete);
1149 for (j
= n_entities
- 1; j
>= 0; j
--)
1151 /* Insert all mode sets that have been inserted by lcm. */
1152 int no_mode
= num_modes
[entity_map
[j
]];
1154 /* Wherever we have moved a mode setting upwards in the flow graph,
1155 the blocks between the new setting site and the now redundant
1156 computation ceases to be transparent for any lower-priority
1157 mode of the same entity. First set the aux field of each
1158 insertion site edge non-transparent, then propagate the new
1159 non-transparency from the redundant computation upwards till
1160 we hit an insertion site or an already non-transparent block. */
1161 for (e
= NUM_EDGES (edge_list
) - 1; e
>= 0; e
--)
1163 edge eg
= INDEX_EDGE (edge_list
, e
);
1166 HARD_REG_SET live_at_edge
;
1171 if (! TEST_BIT (insert
[e
], j
))
1174 eg
->aux
= (void *)1;
1176 mode
= current_mode
[j
];
1179 REG_SET_TO_HARD_REG_SET (live_at_edge
,
1180 src_bb
->global_live_at_end
);
1183 EMIT_MODE_SET (entity_map
[j
], mode
, live_at_edge
);
1184 mode_set
= gen_sequence ();
1187 /* If this is an abnormal edge, we'll insert at the end of the
1189 if (eg
->flags
& EDGE_ABNORMAL
)
1191 src_bb
->end
= emit_insn_after (mode_set
, src_bb
->end
);
1192 bb_info
[j
][src_bb
->index
].computing
= mode
;
1193 RESET_BIT (transp
[src_bb
->index
], j
);
1198 insert_insn_on_edge (mode_set
, eg
);
1202 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
1203 if (TEST_BIT (delete[bb
], j
))
1205 make_preds_opaque (BASIC_BLOCK (bb
), j
);
1206 /* Cancel the 'deleted' mode set. */
1207 bb_info
[j
][bb
].seginfo
->mode
= no_mode
;
1211 free_edge_list (edge_list
);
1214 /* Now output the remaining mode sets in all the segments. */
1215 for (j
= n_entities
- 1; j
>= 0; j
--)
1217 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
1219 struct seginfo
*ptr
, *next
;
1220 for (ptr
= bb_info
[j
][bb
].seginfo
; ptr
; ptr
= next
)
1223 if (ptr
->mode
!= FP_MODE_NONE
)
1228 EMIT_MODE_SET (entity_map
[j
], ptr
->mode
, ptr
->regs_live
);
1229 mode_set
= gen_sequence ();
1232 emit_block_insn_before (mode_set
, ptr
->insn_ptr
,
1233 BASIC_BLOCK (ptr
->bbnum
));
1243 /* Finished. Free up all the things we've allocated. */
1245 sbitmap_vector_free (kill
);
1246 sbitmap_vector_free (antic
);
1247 sbitmap_vector_free (transp
);
1248 sbitmap_vector_free (comp
);
1249 sbitmap_vector_free (delete);
1250 sbitmap_vector_free (insert
);
1253 commit_edge_insertions ();
1255 /* Ideally we'd figure out what blocks were affected and start from
1256 there, but this is enormously complicated by commit_edge_insertions,
1257 which would screw up any indicies we'd collected, and also need to
1258 be involved in the update. Bail and recompute global life info for
1261 allocate_reg_life_data ();
1262 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
1263 (PROP_DEATH_NOTES
| PROP_KILL_DEAD_CODE
1264 | PROP_SCAN_DEAD_CODE
| PROP_REG_INFO
));
1268 #endif /* OPTIMIZE_MODE_SWITCHING */