1 /* Generic partial redundancy elimination with lazy code motion
3 Copyright (C) 1998, 1999, 2000 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 /* We want target macros for the mode switching code to be able to refer
66 to instruction attribute values. */
67 #include "insn-attr.h"
69 /* Edge based LCM routines. */
70 static void compute_antinout_edge
PARAMS ((sbitmap
*, sbitmap
*,
71 sbitmap
*, sbitmap
*));
72 static void compute_earliest
PARAMS ((struct edge_list
*, int, sbitmap
*,
73 sbitmap
*, sbitmap
*, sbitmap
*,
75 static void compute_laterin
PARAMS ((struct edge_list
*, sbitmap
*,
76 sbitmap
*, sbitmap
*, sbitmap
*));
77 static void compute_insert_delete
PARAMS ((struct edge_list
*edge_list
,
78 sbitmap
*, sbitmap
*, sbitmap
*,
79 sbitmap
*, sbitmap
*));
81 /* Edge based LCM routines on a reverse flowgraph. */
82 static void compute_farthest
PARAMS ((struct edge_list
*, int, sbitmap
*,
83 sbitmap
*, sbitmap
*, sbitmap
*,
85 static void compute_nearerout
PARAMS ((struct edge_list
*, sbitmap
*,
86 sbitmap
*, sbitmap
*, sbitmap
*));
87 static void compute_rev_insert_delete
PARAMS ((struct edge_list
*edge_list
,
88 sbitmap
*, sbitmap
*, sbitmap
*,
89 sbitmap
*, sbitmap
*));
92 /* Edge based lcm routines. */
94 /* Compute expression anticipatability at entrance and exit of each block.
95 This is done based on the flow graph, and not on the pred-succ lists.
96 Other than that, its pretty much identical to compute_antinout. */
99 compute_antinout_edge (antloc
, transp
, antin
, antout
)
107 basic_block
*worklist
, *tos
;
109 /* Allocate a worklist array/queue. Entries are only added to the
110 list if they were not already on the list. So the size is
111 bounded by the number of basic blocks. */
112 tos
= worklist
= (basic_block
*) xmalloc (sizeof (basic_block
)
115 /* We want a maximal solution, so make an optimistic initialization of
117 sbitmap_vector_ones (antin
, n_basic_blocks
);
119 /* Put every block on the worklist; this is necessary because of the
120 optimistic initialization of ANTIN above. */
121 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
123 *tos
++ = BASIC_BLOCK (bb
);
124 BASIC_BLOCK (bb
)->aux
= BASIC_BLOCK (bb
);
127 /* Mark blocks which are predecessors of the exit block so that we
128 can easily identify them below. */
129 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
130 e
->src
->aux
= EXIT_BLOCK_PTR
;
132 /* Iterate until the worklist is empty. */
133 while (tos
!= worklist
)
135 /* Take the first entry off the worklist. */
136 basic_block b
= *--tos
;
139 if (b
->aux
== EXIT_BLOCK_PTR
)
141 /* Do not clear the aux field for blocks which are
142 predecessors of the EXIT block. That way we never
143 add then to the worklist again. */
144 sbitmap_zero (antout
[bb
]);
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
], antin
, bb
);
154 if (sbitmap_a_or_b_and_c (antin
[bb
], antloc
[bb
], transp
[bb
], antout
[bb
]))
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 (e
= b
->pred
; e
; e
= e
->pred_next
)
161 if (!e
->src
->aux
&& e
->src
!= ENTRY_BLOCK_PTR
)
172 /* 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
)
198 sbitmap_zero (earliest
[x
]);
202 sbitmap_difference (difference
, antin
[succ
->index
],
204 sbitmap_not (temp_bitmap
, antout
[pred
->index
]);
205 sbitmap_a_and_b_or_c (earliest
[x
], difference
, kill
[pred
->index
],
214 /* later(p,s) is dependent on the calculation of laterin(p).
215 laterin(p) is dependent on the calculation of later(p2,p).
217 laterin(ENTRY) is defined as all 0's
218 later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY)
219 laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)).
221 If we progress in this manner, starting with all basic blocks
222 in the work list, anytime we change later(bb), we need to add
223 succs(bb) to the worklist if they are not already on the worklist.
227 We prime the worklist all the normal basic blocks. The ENTRY block can
228 never be added to the worklist since it is never the successor of any
229 block. We explicitly prevent the EXIT block from being added to the
232 We optimistically initialize LATER. That is the only time this routine
233 will compute LATER for an edge out of the entry block since the entry
234 block is never on the worklist. Thus, LATERIN is neither used nor
235 computed for the ENTRY block.
237 Since the EXIT block is never added to the worklist, we will neither
238 use nor compute LATERIN for the exit block. Edges which reach the
239 EXIT block are handled in the normal fashion inside the loop. However,
240 the insertion/deletion computation needs LATERIN(EXIT), so we have
244 compute_laterin (edge_list
, earliest
, antloc
, later
, laterin
)
245 struct edge_list
*edge_list
;
246 sbitmap
*earliest
, *antloc
, *later
, *laterin
;
248 int bb
, num_edges
, i
;
250 basic_block
*worklist
, *tos
;
252 num_edges
= NUM_EDGES (edge_list
);
254 /* Allocate a worklist array/queue. Entries are only added to the
255 list if they were not already on the list. So the size is
256 bounded by the number of basic blocks. */
257 tos
= worklist
= (basic_block
*) xmalloc (sizeof (basic_block
)
258 * (n_basic_blocks
+ 1));
260 /* Initialize a mapping from each edge to its index. */
261 for (i
= 0; i
< num_edges
; i
++)
262 INDEX_EDGE (edge_list
, i
)->aux
= (void *) (size_t) i
;
264 /* We want a maximal solution, so initially consider LATER true for
265 all edges. This allows propagation through a loop since the incoming
266 loop edge will have LATER set, so if all the other incoming edges
267 to the loop are set, then LATERIN will be set for the head of the
270 If the optimistic setting of LATER on that edge was incorrect (for
271 example the expression is ANTLOC in a block within the loop) then
272 this algorithm will detect it when we process the block at the head
273 of the optimistic edge. That will requeue the affected blocks. */
274 sbitmap_vector_ones (later
, num_edges
);
276 /* Note that even though we want an optimistic setting of LATER, we
277 do not want to be overly optimistic. Consider an outgoing edge from
278 the entry block. That edge should always have a LATER value the
279 same as EARLIEST for that edge. */
280 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
281 sbitmap_copy (later
[(size_t)e
->aux
], earliest
[(size_t)e
->aux
]);
283 /* Add all the blocks to the worklist. This prevents an early exit from
284 the loop given our optimistic initialization of LATER above. */
285 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
287 basic_block b
= BASIC_BLOCK (bb
);
292 /* Iterate until the worklist is empty. */
293 while (tos
!= worklist
)
295 /* Take the first entry off the worklist. */
296 basic_block b
= *--tos
;
299 /* Compute the intersection of LATERIN for each incoming edge to B. */
301 sbitmap_ones (laterin
[bb
]);
302 for (e
= b
->pred
; e
!= NULL
; e
= e
->pred_next
)
303 sbitmap_a_and_b (laterin
[bb
], laterin
[bb
], later
[(size_t)e
->aux
]);
305 /* Calculate LATER for all outgoing edges. */
306 for (e
= b
->succ
; e
!= NULL
; e
= e
->succ_next
)
308 if (sbitmap_union_of_diff (later
[(size_t) e
->aux
],
309 earliest
[(size_t) e
->aux
],
310 laterin
[e
->src
->index
],
311 antloc
[e
->src
->index
]))
313 /* If LATER for an outgoing edge was changed, then we need
314 to add the target of the outgoing edge to the worklist. */
315 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
->aux
== 0)
324 /* Computation of insertion and deletion points requires computing LATERIN
325 for the EXIT block. We allocated an extra entry in the LATERIN array
326 for just this purpose. */
327 sbitmap_ones (laterin
[n_basic_blocks
]);
328 for (e
= EXIT_BLOCK_PTR
->pred
; e
!= NULL
; e
= e
->pred_next
)
329 sbitmap_a_and_b (laterin
[n_basic_blocks
],
330 laterin
[n_basic_blocks
],
331 later
[(size_t) e
->aux
]);
336 /* Compute the insertion and deletion points for edge based LCM. */
338 compute_insert_delete (edge_list
, antloc
, later
, laterin
,
340 struct edge_list
*edge_list
;
341 sbitmap
*antloc
, *later
, *laterin
, *insert
, *delete;
345 for (x
= 0; x
< n_basic_blocks
; x
++)
346 sbitmap_difference (delete[x
], antloc
[x
], laterin
[x
]);
348 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
350 basic_block b
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
351 if (b
== EXIT_BLOCK_PTR
)
352 sbitmap_difference (insert
[x
], later
[x
], laterin
[n_basic_blocks
]);
354 sbitmap_difference (insert
[x
], later
[x
], laterin
[b
->index
]);
358 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the
359 insert and delete vectors for edge based LCM. Returns an
360 edgelist which is used to map the insert vector to what edge
361 an expression should be inserted on. */
364 pre_edge_lcm (file
, n_exprs
, transp
, avloc
, antloc
, kill
, insert
, delete)
365 FILE *file ATTRIBUTE_UNUSED
;
374 sbitmap
*antin
, *antout
, *earliest
;
375 sbitmap
*avin
, *avout
;
376 sbitmap
*later
, *laterin
;
377 struct edge_list
*edge_list
;
380 edge_list
= create_edge_list ();
381 num_edges
= NUM_EDGES (edge_list
);
383 #ifdef LCM_DEBUG_INFO
386 fprintf (file
, "Edge List:\n");
387 verify_edge_list (file
, edge_list
);
388 print_edge_list (file
, edge_list
);
389 dump_sbitmap_vector (file
, "transp", "", transp
, n_basic_blocks
);
390 dump_sbitmap_vector (file
, "antloc", "", antloc
, n_basic_blocks
);
391 dump_sbitmap_vector (file
, "avloc", "", avloc
, n_basic_blocks
);
392 dump_sbitmap_vector (file
, "kill", "", kill
, n_basic_blocks
);
396 /* Compute global availability. */
397 avin
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
398 avout
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
399 compute_available (avloc
, kill
, avout
, avin
);
404 /* Compute global anticipatability. */
405 antin
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
406 antout
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
407 compute_antinout_edge (antloc
, transp
, antin
, antout
);
409 #ifdef LCM_DEBUG_INFO
412 dump_sbitmap_vector (file
, "antin", "", antin
, n_basic_blocks
);
413 dump_sbitmap_vector (file
, "antout", "", antout
, n_basic_blocks
);
417 /* Compute earliestness. */
418 earliest
= sbitmap_vector_alloc (num_edges
, n_exprs
);
419 compute_earliest (edge_list
, n_exprs
, antin
, antout
, avout
, kill
, earliest
);
421 #ifdef LCM_DEBUG_INFO
423 dump_sbitmap_vector (file
, "earliest", "", earliest
, num_edges
);
430 later
= sbitmap_vector_alloc (num_edges
, n_exprs
);
431 /* Allocate an extra element for the exit block in the laterin vector. */
432 laterin
= sbitmap_vector_alloc (n_basic_blocks
+ 1, n_exprs
);
433 compute_laterin (edge_list
, earliest
, antloc
, later
, laterin
);
436 #ifdef LCM_DEBUG_INFO
439 dump_sbitmap_vector (file
, "laterin", "", laterin
, n_basic_blocks
+ 1);
440 dump_sbitmap_vector (file
, "later", "", later
, num_edges
);
446 *insert
= sbitmap_vector_alloc (num_edges
, n_exprs
);
447 *delete = sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
448 compute_insert_delete (edge_list
, antloc
, later
, laterin
, *insert
, *delete);
453 #ifdef LCM_DEBUG_INFO
456 dump_sbitmap_vector (file
, "pre_insert_map", "", *insert
, num_edges
);
457 dump_sbitmap_vector (file
, "pre_delete_map", "", *delete, n_basic_blocks
);
464 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
465 Return the number of passes we performed to iterate to a solution. */
467 compute_available (avloc
, kill
, avout
, avin
)
468 sbitmap
*avloc
, *kill
, *avout
, *avin
;
472 basic_block
*worklist
, *tos
;
474 /* Allocate a worklist array/queue. Entries are only added to the
475 list if they were not already on the list. So the size is
476 bounded by the number of basic blocks. */
477 tos
= worklist
= (basic_block
*) xmalloc (sizeof (basic_block
)
480 /* We want a maximal solution. */
481 sbitmap_vector_ones (avout
, n_basic_blocks
);
483 /* Put every block on the worklist; this is necessary because of the
484 optimistic initialization of AVOUT above. */
485 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
487 *tos
++ = BASIC_BLOCK (bb
);
488 BASIC_BLOCK (bb
)->aux
= BASIC_BLOCK (bb
);
491 /* Mark blocks which are successors of the entry block so that we
492 can easily identify them below. */
493 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
494 e
->dest
->aux
= ENTRY_BLOCK_PTR
;
496 /* Iterate until the worklist is empty. */
497 while (tos
!= worklist
)
499 /* Take the first entry off the worklist. */
500 basic_block b
= *--tos
;
503 /* If one of the predecessor blocks is the ENTRY block, then the
504 intersection of avouts is the null set. We can identify such blocks
505 by the special value in the AUX field in the block structure. */
506 if (b
->aux
== ENTRY_BLOCK_PTR
)
508 /* Do not clear the aux field for blocks which are
509 successors of the ENTRY block. That way we never
510 add then to the worklist again. */
511 sbitmap_zero (avin
[bb
]);
515 /* Clear the aux field of this block so that it can be added to
516 the worklist again if necessary. */
518 sbitmap_intersection_of_preds (avin
[bb
], avout
, bb
);
521 if (sbitmap_union_of_diff (avout
[bb
], avloc
[bb
], avin
[bb
], kill
[bb
]))
523 /* If the out state of this block changed, then we need
524 to add the successors of this block to the worklist
525 if they are not already on the worklist. */
526 for (e
= b
->succ
; e
; e
= e
->succ_next
)
528 if (!e
->dest
->aux
&& e
->dest
!= EXIT_BLOCK_PTR
)
539 /* Compute the farthest vector for edge based lcm. */
541 compute_farthest (edge_list
, n_exprs
, st_avout
, st_avin
, st_antin
,
543 struct edge_list
*edge_list
;
545 sbitmap
*st_avout
, *st_avin
, *st_antin
, *kill
, *farthest
;
547 sbitmap difference
, temp_bitmap
;
549 basic_block pred
, succ
;
551 num_edges
= NUM_EDGES (edge_list
);
553 difference
= sbitmap_alloc (n_exprs
);
554 temp_bitmap
= sbitmap_alloc (n_exprs
);
556 for (x
= 0; x
< num_edges
; x
++)
558 pred
= INDEX_EDGE_PRED_BB (edge_list
, x
);
559 succ
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
560 if (succ
== EXIT_BLOCK_PTR
)
561 sbitmap_copy (farthest
[x
], st_avout
[pred
->index
]);
564 if (pred
== ENTRY_BLOCK_PTR
)
566 sbitmap_zero (farthest
[x
]);
570 sbitmap_difference (difference
, st_avout
[pred
->index
],
571 st_antin
[succ
->index
]);
572 sbitmap_not (temp_bitmap
, st_avin
[succ
->index
]);
573 sbitmap_a_and_b_or_c (farthest
[x
], difference
,
574 kill
[succ
->index
], temp_bitmap
);
582 /* Compute nearer and nearerout vectors for edge based lcm.
584 This is the mirror of compute_laterin, additional comments on the
585 implementation can be found before compute_laterin. */
588 compute_nearerout (edge_list
, farthest
, st_avloc
, nearer
, nearerout
)
589 struct edge_list
*edge_list
;
590 sbitmap
*farthest
, *st_avloc
, *nearer
, *nearerout
;
592 int bb
, num_edges
, i
;
594 basic_block
*worklist
, *tos
;
596 num_edges
= NUM_EDGES (edge_list
);
598 /* Allocate a worklist array/queue. Entries are only added to the
599 list if they were not already on the list. So the size is
600 bounded by the number of basic blocks. */
601 tos
= worklist
= (basic_block
*) xmalloc (sizeof (basic_block
)
602 * (n_basic_blocks
+ 1));
604 /* Initialize NEARER for each edge and build a mapping from an edge to
606 for (i
= 0; i
< num_edges
; i
++)
607 INDEX_EDGE (edge_list
, i
)->aux
= (void *) (size_t) i
;
609 /* We want a maximal solution. */
610 sbitmap_vector_ones (nearer
, num_edges
);
612 /* Note that even though we want an optimistic setting of NEARER, we
613 do not want to be overly optimistic. Consider an incoming edge to
614 the exit block. That edge should always have a NEARER value the
615 same as FARTHEST for that edge. */
616 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
617 sbitmap_copy (nearer
[(size_t)e
->aux
], farthest
[(size_t)e
->aux
]);
619 /* Add all the blocks to the worklist. This prevents an early exit
620 from the loop given our optimistic initialization of NEARER. */
621 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
623 basic_block b
= BASIC_BLOCK (bb
);
628 /* Iterate until the worklist is empty. */
629 while (tos
!= worklist
)
631 /* Take the first entry off the worklist. */
632 basic_block b
= *--tos
;
635 /* Compute the intersection of NEARER for each outgoing edge from B. */
637 sbitmap_ones (nearerout
[bb
]);
638 for (e
= b
->succ
; e
!= NULL
; e
= e
->succ_next
)
639 sbitmap_a_and_b (nearerout
[bb
], nearerout
[bb
],
640 nearer
[(size_t) e
->aux
]);
642 /* Calculate NEARER for all incoming edges. */
643 for (e
= b
->pred
; e
!= NULL
; e
= e
->pred_next
)
645 if (sbitmap_union_of_diff (nearer
[(size_t) e
->aux
],
646 farthest
[(size_t) e
->aux
],
647 nearerout
[e
->dest
->index
],
648 st_avloc
[e
->dest
->index
]))
650 /* If NEARER for an incoming edge was changed, then we need
651 to add the source of the incoming edge to the worklist. */
652 if (e
->src
!= ENTRY_BLOCK_PTR
&& e
->src
->aux
== 0)
661 /* Computation of insertion and deletion points requires computing NEAREROUT
662 for the ENTRY block. We allocated an extra entry in the NEAREROUT array
663 for just this purpose. */
664 sbitmap_ones (nearerout
[n_basic_blocks
]);
665 for (e
= ENTRY_BLOCK_PTR
->succ
; e
!= NULL
; e
= e
->succ_next
)
666 sbitmap_a_and_b (nearerout
[n_basic_blocks
],
667 nearerout
[n_basic_blocks
],
668 nearer
[(size_t) e
->aux
]);
673 /* Compute the insertion and deletion points for edge based LCM. */
675 compute_rev_insert_delete (edge_list
, st_avloc
, nearer
, nearerout
,
677 struct edge_list
*edge_list
;
678 sbitmap
*st_avloc
, *nearer
, *nearerout
, *insert
, *delete;
682 for (x
= 0; x
< n_basic_blocks
; x
++)
683 sbitmap_difference (delete[x
], st_avloc
[x
], nearerout
[x
]);
685 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
687 basic_block b
= INDEX_EDGE_PRED_BB (edge_list
, x
);
688 if (b
== ENTRY_BLOCK_PTR
)
689 sbitmap_difference (insert
[x
], nearer
[x
], nearerout
[n_basic_blocks
]);
691 sbitmap_difference (insert
[x
], nearer
[x
], nearerout
[b
->index
]);
695 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
696 insert and delete vectors for edge based reverse LCM. Returns an
697 edgelist which is used to map the insert vector to what edge
698 an expression should be inserted on. */
701 pre_edge_rev_lcm (file
, n_exprs
, transp
, st_avloc
, st_antloc
, kill
,
703 FILE *file ATTRIBUTE_UNUSED
;
712 sbitmap
*st_antin
, *st_antout
;
713 sbitmap
*st_avout
, *st_avin
, *farthest
;
714 sbitmap
*nearer
, *nearerout
;
715 struct edge_list
*edge_list
;
718 edge_list
= create_edge_list ();
719 num_edges
= NUM_EDGES (edge_list
);
721 st_antin
= (sbitmap
*) sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
722 st_antout
= (sbitmap
*) sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
723 sbitmap_vector_zero (st_antin
, n_basic_blocks
);
724 sbitmap_vector_zero (st_antout
, n_basic_blocks
);
725 compute_antinout_edge (st_antloc
, transp
, st_antin
, st_antout
);
727 /* Compute global anticipatability. */
728 st_avout
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
729 st_avin
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
730 compute_available (st_avloc
, kill
, st_avout
, st_avin
);
732 #ifdef LCM_DEBUG_INFO
735 fprintf (file
, "Edge List:\n");
736 verify_edge_list (file
, edge_list
);
737 print_edge_list (file
, edge_list
);
738 dump_sbitmap_vector (file
, "transp", "", transp
, n_basic_blocks
);
739 dump_sbitmap_vector (file
, "st_avloc", "", st_avloc
, n_basic_blocks
);
740 dump_sbitmap_vector (file
, "st_antloc", "", st_antloc
, n_basic_blocks
);
741 dump_sbitmap_vector (file
, "st_antin", "", st_antin
, n_basic_blocks
);
742 dump_sbitmap_vector (file
, "st_antout", "", st_antout
, n_basic_blocks
);
743 dump_sbitmap_vector (file
, "st_kill", "", kill
, n_basic_blocks
);
747 #ifdef LCM_DEBUG_INFO
750 dump_sbitmap_vector (file
, "st_avout", "", st_avout
, n_basic_blocks
);
751 dump_sbitmap_vector (file
, "st_avin", "", st_avin
, n_basic_blocks
);
755 /* Compute farthestness. */
756 farthest
= sbitmap_vector_alloc (num_edges
, n_exprs
);
757 compute_farthest (edge_list
, n_exprs
, st_avout
, st_avin
, st_antin
,
760 #ifdef LCM_DEBUG_INFO
762 dump_sbitmap_vector (file
, "farthest", "", farthest
, num_edges
);
768 nearer
= sbitmap_vector_alloc (num_edges
, n_exprs
);
769 /* Allocate an extra element for the entry block. */
770 nearerout
= sbitmap_vector_alloc (n_basic_blocks
+ 1, n_exprs
);
771 compute_nearerout (edge_list
, farthest
, st_avloc
, nearer
, nearerout
);
773 #ifdef LCM_DEBUG_INFO
776 dump_sbitmap_vector (file
, "nearerout", "", nearerout
,
778 dump_sbitmap_vector (file
, "nearer", "", nearer
, num_edges
);
784 *insert
= sbitmap_vector_alloc (num_edges
, n_exprs
);
785 *delete = sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
786 compute_rev_insert_delete (edge_list
, st_avloc
, nearer
, nearerout
, *insert
, *delete);
791 #ifdef LCM_DEBUG_INFO
794 dump_sbitmap_vector (file
, "pre_insert_map", "", *insert
, num_edges
);
795 dump_sbitmap_vector (file
, "pre_delete_map", "", *delete, n_basic_blocks
);
803 /* The algorithm for setting the modes consists of scanning the insn list
804 and finding all the insns which require a specific mode. Each insn gets
805 a unique struct seginfo element. These structures are inserted into a list
806 for each basic block. For each entity, there is an array of bb_info over
807 the flow graph basic blocks (local var 'bb_info'), and contains a list
808 of all insns within that basic block, in the order they are encountered.
810 For each entity, any basic block WITHOUT any insns requiring a specific
811 mode are given a single entry, without a mode. (Each basic block
812 in the flow graph must have at least one entry in the segment table.)
814 The LCM algorithm is then run over the flow graph to determine where to
815 place the sets to the highest-priority value in respect of first the first
816 insn in any one block. Any adjustments required to the transparancy
817 vectors are made, then the next iteration starts for the next-lower
818 priority mode, till for each entity all modes are exhasted.
820 More details are located in the code for optimize_mode_switching(). */
822 /* This structure contains the information for each insn which requires
823 either single or double mode to be set.
824 MODE is the mode this insn must be executed in.
825 INSN_PTR is the insn to be executed.
826 BBNUM is the flow graph basic block this insn occurs in.
827 NEXT is the next insn in the same basic block. */
833 struct seginfo
*next
;
834 HARD_REG_SET regs_live
;
839 struct seginfo
*seginfo
;
843 /* These bitmaps are used for the LCM algorithm. */
845 static sbitmap
*antic
;
846 static sbitmap
*transp
;
847 static sbitmap
*comp
;
848 static sbitmap
*delete;
849 static sbitmap
*insert
;
851 static struct seginfo
* new_seginfo
PARAMS ((int, rtx
, int, HARD_REG_SET
));;
852 static void add_seginfo
PARAMS ((struct bb_info
*, struct seginfo
*));
853 static void make_preds_opaque
PARAMS ((basic_block
, int));
854 static void reg_dies
PARAMS ((rtx
, HARD_REG_SET
));
855 static void reg_becomes_live
PARAMS ((rtx
, rtx
, void *));
857 /* This function will allocate a new BBINFO structure, initialized
858 with the FP_MODE, INSN, and basic block BB parameters. */
859 static struct seginfo
*
860 new_seginfo (mode
, insn
, bb
, regs_live
)
864 HARD_REG_SET regs_live
;
867 ptr
= xmalloc (sizeof (struct seginfo
));
869 ptr
->insn_ptr
= insn
;
872 COPY_HARD_REG_SET (ptr
->regs_live
, regs_live
);
876 /* Add a seginfo element to the end of a list.
877 HEAD is a pointer to the list beginning.
878 INFO is the structure to be linked in. */
880 add_seginfo (head
, info
)
881 struct bb_info
*head
;
882 struct seginfo
*info
;
886 if (head
->seginfo
== NULL
)
887 head
->seginfo
= info
;
891 while (ptr
->next
!= NULL
)
897 /* Make all predecessors of basic block B opaque, recursively, till we hit
898 some that are already non-transparent, or an edge where aux is set; that
899 denotes that a mode set is to be done on that edge.
900 J is the bit number in the bitmaps that corresponds to the entity that
901 we are currently handling mode-switching for. */
903 make_preds_opaque (b
, j
)
909 for (e
= b
->pred
; e
; e
= e
->pred_next
)
911 basic_block pb
= e
->src
;
912 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. */
927 if (GET_CODE (reg
) != REG
)
930 if (regno
< FIRST_PSEUDO_REGISTER
)
932 int nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
934 for (; --nregs
>=0; nregs
--, regno
++)
935 CLEAR_HARD_REG_BIT (live
, regno
);
939 /* Record in LIVE that register REG became live.
940 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
)
958 int nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
960 for (; nregs
-- > 0; regno
++)
961 SET_HARD_REG_BIT (* (HARD_REG_SET
*) live
, regno
);
965 /* Find all insns that need a particular mode
966 setting, and insert the necessary mode switches. */
968 optimize_mode_switching (file
)
969 FILE *file ATTRIBUTE_UNUSED
;
971 #ifdef OPTIMIZE_MODE_SWITCHING
977 struct edge_list
*edge_list
;
978 static int num_modes
[] = NUM_MODES_FOR_MODE_SWITCHING
;
979 #define N_ENTITIES (sizeof num_modes / sizeof (int))
980 int entity_map
[N_ENTITIES
];
981 struct bb_info
*bb_info
[N_ENTITIES
];
984 int max_num_modes
= 0;
986 for (e
= N_ENTITIES
- 1, n_entities
= 0; e
>= 0; e
--)
988 if (OPTIMIZE_MODE_SWITCHING (e
))
990 /* Create the list of segments within each basic block. */
992 = (struct bb_info
*) xcalloc (n_basic_blocks
, sizeof **bb_info
);
993 entity_map
[n_entities
++] = e
;
994 if (num_modes
[e
] > max_num_modes
)
995 max_num_modes
= num_modes
[e
];
1001 #ifdef MODE_USES_IN_EXIT_BLOCK
1002 /* For some ABIs a particular mode setting is required at function exit. */
1004 for (eg
= EXIT_BLOCK_PTR
->pred
; eg
; eg
= eg
->pred_next
)
1006 int bb
= eg
->src
->index
;
1008 rtx insn
= BLOCK_END (bb
);
1009 rtx use
= MODE_USES_IN_EXIT_BLOCK
;
1011 /* If the block ends with the use of the return value
1012 and / or a return, insert the new use(s) in front of them. */
1013 while ((GET_CODE (insn
) == INSN
&& GET_CODE (PATTERN (insn
)) == USE
)
1014 || GET_CODE (insn
) == JUMP_INSN
)
1015 insn
= PREV_INSN (insn
);
1016 use
= emit_insn_after (use
, insn
);
1017 if (insn
== BLOCK_END (bb
))
1018 BLOCK_END (bb
) = use
;
1019 else if (NEXT_INSN (use
) == BLOCK_HEAD (bb
))
1020 BLOCK_HEAD (bb
) = NEXT_INSN (insn
);
1024 /* Create the bitmap vectors. */
1026 antic
= sbitmap_vector_alloc (n_basic_blocks
, n_entities
);
1027 transp
= sbitmap_vector_alloc (n_basic_blocks
, n_entities
);
1028 comp
= sbitmap_vector_alloc (n_basic_blocks
, n_entities
);
1030 sbitmap_vector_ones (transp
, n_basic_blocks
);
1032 for (j
= n_entities
- 1; j
>= 0; j
--)
1034 int e
= entity_map
[j
];
1035 int no_mode
= num_modes
[e
];
1036 struct bb_info
*info
= bb_info
[j
];
1038 /* Determine what the first use (if any) need for a mode of entity E is.
1039 This will be th mode that is anticipatable for this block.
1040 Also compute the initial transparency settings. */
1041 for (bb
= 0 ; bb
< n_basic_blocks
; bb
++)
1043 struct seginfo
*ptr
;
1044 int last_mode
= no_mode
;
1045 HARD_REG_SET live_now
;
1047 REG_SET_TO_HARD_REG_SET (live_now
,
1048 BASIC_BLOCK (bb
)->global_live_at_start
);
1049 for (insn
= BLOCK_HEAD (bb
);
1050 insn
!= NULL
&& insn
!= NEXT_INSN (BLOCK_END (bb
));
1051 insn
= NEXT_INSN (insn
))
1053 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
1055 int mode
= MODE_NEEDED (e
, insn
);
1058 if (mode
!= no_mode
&& mode
!= last_mode
)
1061 ptr
= new_seginfo (mode
, insn
, bb
, live_now
);
1062 add_seginfo (info
+ bb
, ptr
);
1063 RESET_BIT (transp
[bb
], j
);
1066 /* Update LIVE_NOW. */
1067 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1068 if (REG_NOTE_KIND (link
) == REG_DEAD
)
1069 reg_dies (XEXP (link
, 0), live_now
);
1070 note_stores (PATTERN (insn
), reg_becomes_live
, &live_now
);
1071 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1072 if (REG_NOTE_KIND (link
) == REG_UNUSED
)
1073 reg_dies (XEXP (link
, 0), live_now
);
1076 info
[bb
].computing
= last_mode
;
1077 /* Check for blocks without ANY mode requirements. */
1078 if (last_mode
== no_mode
)
1080 ptr
= new_seginfo (no_mode
, insn
, bb
, live_now
);
1081 add_seginfo (info
+ bb
, ptr
);
1084 #ifdef MODE_AT_ENTRY
1086 int mode
= MODE_AT_ENTRY (e
);
1087 if (mode
!= no_mode
)
1089 for (eg
= ENTRY_BLOCK_PTR
->succ
; eg
; eg
= eg
->succ_next
)
1091 bb
= eg
->dest
->index
;
1093 /* By always making this nontransparent, we save
1094 an extra check in make_preds_opaque. We also
1095 need this to avoid confusing pre_edge_lcm when
1096 antic is cleared but transp and comp are set. */
1097 RESET_BIT (transp
[bb
], j
);
1099 /* If the block already has MODE, pretend it
1100 has none (because we don't need to set it),
1101 but retain whatever mode it computes. */
1102 if (info
[bb
].seginfo
->mode
== mode
)
1104 info
[bb
].seginfo
->mode
= no_mode
;
1106 /* Insert a fake computing definition of MODE into entry blocks
1107 which compute no mode. This represents the mode on entry. */
1108 else if (info
[bb
].computing
== no_mode
)
1110 info
[bb
].computing
= mode
;
1111 info
[bb
].seginfo
->mode
= no_mode
;
1116 #endif /* MODE_AT_ENTRY */
1119 kill
= sbitmap_vector_alloc (n_basic_blocks
, n_entities
);
1120 for (i
= 0; i
< max_num_modes
; i
++)
1122 int current_mode
[N_ENTITIES
];
1124 /* Set the anticipatable and computing arrays. */
1125 sbitmap_vector_zero (antic
, n_basic_blocks
);
1126 sbitmap_vector_zero (comp
, n_basic_blocks
);
1127 for (j
= n_entities
- 1; j
>= 0; j
--)
1129 int m
= current_mode
[j
] = MODE_PRIORITY_TO_MODE (entity_map
[j
], i
);
1130 struct bb_info
*info
= bb_info
[j
];
1132 for (bb
= 0 ; bb
< n_basic_blocks
; bb
++)
1135 if (info
[bb
].seginfo
->mode
== m
)
1136 SET_BIT (antic
[bb
], j
);
1138 if (info
[bb
].computing
== m
)
1139 SET_BIT (comp
[bb
], j
);
1143 /* Calculate the optimal locations for the
1144 placement mode switches to modes with priority I. */
1146 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
1147 sbitmap_not (kill
[bb
], transp
[bb
]);
1148 edge_list
= pre_edge_lcm (file
, 1, transp
, comp
, antic
,
1149 kill
, &insert
, &delete);
1151 for (j
= n_entities
- 1; j
>=0; j
--)
1153 /* Insert all mode sets that have been inserted by lcm. */
1154 int no_mode
= num_modes
[entity_map
[j
]];
1155 /* Wherever we have moved a mode setting upwards in the flow graph,
1156 the blocks between the new setting site and the now redundant
1157 computation ceases to be transparent for any lower-priority
1158 mode of the same entity. First set the aux field of each
1159 insertion site edge non-transparent, then propagate the new
1160 non-transparency from the redundant computation upwards till
1161 we hit an insertion site or an already non-transparent block. */
1162 for (e
= NUM_EDGES (edge_list
) - 1; e
>= 0; e
--)
1164 edge eg
= INDEX_EDGE (edge_list
, e
);
1167 HARD_REG_SET live_at_edge
;
1172 if (! TEST_BIT (insert
[e
], j
))
1175 eg
->aux
= (void *)1;
1177 mode
= current_mode
[j
];
1180 REG_SET_TO_HARD_REG_SET (live_at_edge
, src_bb
->global_live_at_end
);
1182 EMIT_MODE_SET (entity_map
[j
], mode
, live_at_edge
);
1183 mode_set
= gen_sequence ();
1186 /* If this is an abnormal edge, we'll insert at the end of the
1188 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
);
1203 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
1205 if (TEST_BIT (delete[bb
], j
))
1207 make_preds_opaque (BASIC_BLOCK (bb
), j
);
1208 /* Cancel the 'deleted' mode set. */
1209 bb_info
[j
][bb
].seginfo
->mode
= no_mode
;
1213 free_edge_list (edge_list
);
1216 /* Now output the remaining mode sets in all the segments. */
1217 for (j
= n_entities
- 1; j
>= 0; j
--)
1219 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
1221 struct seginfo
*ptr
, *next
;
1222 for (ptr
= bb_info
[j
][bb
].seginfo
; ptr
; ptr
= next
)
1225 if (ptr
->mode
!= FP_MODE_NONE
)
1230 EMIT_MODE_SET (entity_map
[j
], ptr
->mode
, ptr
->regs_live
);
1231 mode_set
= gen_sequence ();
1234 emit_block_insn_before (mode_set
, ptr
->insn_ptr
,
1235 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 ();
1254 #endif /* OPTIMIZE_MODE_SWITCHING */