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
, *qin
, *qout
, *qend
;
114 /* Allocate a worklist array/queue. Entries are only added to the
115 list if they were not already on the list. So the size is
116 bounded by the number of basic blocks. */
117 qin
= qout
= worklist
118 = (basic_block
*) xmalloc (sizeof (basic_block
) * n_basic_blocks
);
120 /* We want a maximal solution, so make an optimistic initialization of
122 sbitmap_vector_ones (antin
, n_basic_blocks
);
124 /* Put every block on the worklist; this is necessary because of the
125 optimistic initialization of ANTIN above. */
126 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
128 *qin
++ = BASIC_BLOCK (bb
);
129 BASIC_BLOCK (bb
)->aux
= BASIC_BLOCK (bb
);
133 qend
= &worklist
[n_basic_blocks
];
134 qlen
= n_basic_blocks
;
136 /* Mark blocks which are predecessors of the exit block so that we
137 can easily identify them below. */
138 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
139 e
->src
->aux
= EXIT_BLOCK_PTR
;
141 /* Iterate until the worklist is empty. */
144 /* Take the first entry off the worklist. */
145 basic_block b
= *qout
++;
152 if (b
->aux
== EXIT_BLOCK_PTR
)
153 /* Do not clear the aux field for blocks which are predecessors of
154 the EXIT block. That way we never add then to the worklist
156 sbitmap_zero (antout
[bb
]);
159 /* Clear the aux field of this block so that it can be added to
160 the worklist again if necessary. */
162 sbitmap_intersection_of_succs (antout
[bb
], antin
, bb
);
165 if (sbitmap_a_or_b_and_c (antin
[bb
], antloc
[bb
], transp
[bb
], antout
[bb
]))
166 /* If the in state of this block changed, then we need
167 to add the predecessors of this block to the worklist
168 if they are not already on the worklist. */
169 for (e
= b
->pred
; e
; e
= e
->pred_next
)
170 if (!e
->src
->aux
&& e
->src
!= ENTRY_BLOCK_PTR
)
183 /* Compute the earliest vector for edge based lcm. */
186 compute_earliest (edge_list
, n_exprs
, antin
, antout
, avout
, kill
, earliest
)
187 struct edge_list
*edge_list
;
189 sbitmap
*antin
, *antout
, *avout
, *kill
, *earliest
;
191 sbitmap difference
, temp_bitmap
;
193 basic_block pred
, succ
;
195 num_edges
= NUM_EDGES (edge_list
);
197 difference
= sbitmap_alloc (n_exprs
);
198 temp_bitmap
= sbitmap_alloc (n_exprs
);
200 for (x
= 0; x
< num_edges
; x
++)
202 pred
= INDEX_EDGE_PRED_BB (edge_list
, x
);
203 succ
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
204 if (pred
== ENTRY_BLOCK_PTR
)
205 sbitmap_copy (earliest
[x
], antin
[succ
->index
]);
208 if (succ
== EXIT_BLOCK_PTR
)
209 sbitmap_zero (earliest
[x
]);
212 sbitmap_difference (difference
, antin
[succ
->index
],
214 sbitmap_not (temp_bitmap
, antout
[pred
->index
]);
215 sbitmap_a_and_b_or_c (earliest
[x
], difference
,
216 kill
[pred
->index
], temp_bitmap
);
225 /* later(p,s) is dependent on the calculation of laterin(p).
226 laterin(p) is dependent on the calculation of later(p2,p).
228 laterin(ENTRY) is defined as all 0's
229 later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY)
230 laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)).
232 If we progress in this manner, starting with all basic blocks
233 in the work list, anytime we change later(bb), we need to add
234 succs(bb) to the worklist if they are not already on the worklist.
238 We prime the worklist all the normal basic blocks. The ENTRY block can
239 never be added to the worklist since it is never the successor of any
240 block. We explicitly prevent the EXIT block from being added to the
243 We optimistically initialize LATER. That is the only time this routine
244 will compute LATER for an edge out of the entry block since the entry
245 block is never on the worklist. Thus, LATERIN is neither used nor
246 computed for the ENTRY block.
248 Since the EXIT block is never added to the worklist, we will neither
249 use nor compute LATERIN for the exit block. Edges which reach the
250 EXIT block are handled in the normal fashion inside the loop. However,
251 the insertion/deletion computation needs LATERIN(EXIT), so we have
255 compute_laterin (edge_list
, earliest
, antloc
, later
, laterin
)
256 struct edge_list
*edge_list
;
257 sbitmap
*earliest
, *antloc
, *later
, *laterin
;
259 int bb
, num_edges
, i
;
261 basic_block
*worklist
, *qin
, *qout
, *qend
;
264 num_edges
= NUM_EDGES (edge_list
);
266 /* Allocate a worklist array/queue. Entries are only added to the
267 list if they were not already on the list. So the size is
268 bounded by the number of basic blocks. */
269 qin
= qout
= worklist
270 = (basic_block
*) xmalloc (sizeof (basic_block
) * (n_basic_blocks
+ 1));
272 /* Initialize a mapping from each edge to its index. */
273 for (i
= 0; i
< num_edges
; i
++)
274 INDEX_EDGE (edge_list
, i
)->aux
= (void *) (size_t) i
;
276 /* We want a maximal solution, so initially consider LATER true for
277 all edges. This allows propagation through a loop since the incoming
278 loop edge will have LATER set, so if all the other incoming edges
279 to the loop are set, then LATERIN will be set for the head of the
282 If the optimistic setting of LATER on that edge was incorrect (for
283 example the expression is ANTLOC in a block within the loop) then
284 this algorithm will detect it when we process the block at the head
285 of the optimistic edge. That will requeue the affected blocks. */
286 sbitmap_vector_ones (later
, num_edges
);
288 /* Note that even though we want an optimistic setting of LATER, we
289 do not want to be overly optimistic. Consider an outgoing edge from
290 the entry block. That edge should always have a LATER value the
291 same as EARLIEST for that edge. */
292 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
293 sbitmap_copy (later
[(size_t) e
->aux
], earliest
[(size_t) e
->aux
]);
295 /* Add all the blocks to the worklist. This prevents an early exit from
296 the loop given our optimistic initialization of LATER above. */
297 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
299 basic_block b
= BASIC_BLOCK (bb
);
304 /* Note that we do not use the last allocated element for our queue,
305 as EXIT_BLOCK is never inserted into it. In fact the above allocation
306 of n_basic_blocks + 1 elements is not encessary. */
307 qend
= &worklist
[n_basic_blocks
];
308 qlen
= n_basic_blocks
;
310 /* Iterate until the worklist is empty. */
313 /* Take the first entry off the worklist. */
314 basic_block b
= *qout
++;
320 /* Compute the intersection of LATERIN for each incoming edge to B. */
322 sbitmap_ones (laterin
[bb
]);
323 for (e
= b
->pred
; e
!= NULL
; e
= e
->pred_next
)
324 sbitmap_a_and_b (laterin
[bb
], laterin
[bb
], later
[(size_t)e
->aux
]);
326 /* Calculate LATER for all outgoing edges. */
327 for (e
= b
->succ
; e
!= NULL
; e
= e
->succ_next
)
328 if (sbitmap_union_of_diff (later
[(size_t) e
->aux
],
329 earliest
[(size_t) e
->aux
],
330 laterin
[e
->src
->index
],
331 antloc
[e
->src
->index
])
332 /* If LATER for an outgoing edge was changed, then we need
333 to add the target of the outgoing edge to the worklist. */
334 && e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
->aux
== 0)
344 /* Computation of insertion and deletion points requires computing LATERIN
345 for the EXIT block. We allocated an extra entry in the LATERIN array
346 for just this purpose. */
347 sbitmap_ones (laterin
[n_basic_blocks
]);
348 for (e
= EXIT_BLOCK_PTR
->pred
; e
!= NULL
; e
= e
->pred_next
)
349 sbitmap_a_and_b (laterin
[n_basic_blocks
],
350 laterin
[n_basic_blocks
],
351 later
[(size_t) e
->aux
]);
356 /* Compute the insertion and deletion points for edge based LCM. */
359 compute_insert_delete (edge_list
, antloc
, later
, laterin
,
361 struct edge_list
*edge_list
;
362 sbitmap
*antloc
, *later
, *laterin
, *insert
, *delete;
366 for (x
= 0; x
< n_basic_blocks
; x
++)
367 sbitmap_difference (delete[x
], antloc
[x
], laterin
[x
]);
369 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
371 basic_block b
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
373 if (b
== EXIT_BLOCK_PTR
)
374 sbitmap_difference (insert
[x
], later
[x
], laterin
[n_basic_blocks
]);
376 sbitmap_difference (insert
[x
], later
[x
], laterin
[b
->index
]);
380 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and
381 delete vectors for edge based LCM. Returns an edgelist which is used to
382 map the insert vector to what edge an expression should be inserted on. */
385 pre_edge_lcm (file
, n_exprs
, transp
, avloc
, antloc
, kill
, insert
, delete)
386 FILE *file ATTRIBUTE_UNUSED
;
395 sbitmap
*antin
, *antout
, *earliest
;
396 sbitmap
*avin
, *avout
;
397 sbitmap
*later
, *laterin
;
398 struct edge_list
*edge_list
;
401 edge_list
= create_edge_list ();
402 num_edges
= NUM_EDGES (edge_list
);
404 #ifdef LCM_DEBUG_INFO
407 fprintf (file
, "Edge List:\n");
408 verify_edge_list (file
, edge_list
);
409 print_edge_list (file
, edge_list
);
410 dump_sbitmap_vector (file
, "transp", "", transp
, n_basic_blocks
);
411 dump_sbitmap_vector (file
, "antloc", "", antloc
, n_basic_blocks
);
412 dump_sbitmap_vector (file
, "avloc", "", avloc
, n_basic_blocks
);
413 dump_sbitmap_vector (file
, "kill", "", kill
, n_basic_blocks
);
417 /* Compute global availability. */
418 avin
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
419 avout
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
420 compute_available (avloc
, kill
, avout
, avin
);
423 /* Compute global anticipatability. */
424 antin
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
425 antout
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
426 compute_antinout_edge (antloc
, transp
, antin
, antout
);
428 #ifdef LCM_DEBUG_INFO
431 dump_sbitmap_vector (file
, "antin", "", antin
, n_basic_blocks
);
432 dump_sbitmap_vector (file
, "antout", "", antout
, n_basic_blocks
);
436 /* Compute earliestness. */
437 earliest
= sbitmap_vector_alloc (num_edges
, n_exprs
);
438 compute_earliest (edge_list
, n_exprs
, antin
, antout
, avout
, kill
, earliest
);
440 #ifdef LCM_DEBUG_INFO
442 dump_sbitmap_vector (file
, "earliest", "", earliest
, num_edges
);
449 later
= sbitmap_vector_alloc (num_edges
, n_exprs
);
451 /* Allocate an extra element for the exit block in the laterin vector. */
452 laterin
= sbitmap_vector_alloc (n_basic_blocks
+ 1, n_exprs
);
453 compute_laterin (edge_list
, earliest
, antloc
, later
, laterin
);
455 #ifdef LCM_DEBUG_INFO
458 dump_sbitmap_vector (file
, "laterin", "", laterin
, n_basic_blocks
+ 1);
459 dump_sbitmap_vector (file
, "later", "", later
, num_edges
);
465 *insert
= sbitmap_vector_alloc (num_edges
, n_exprs
);
466 *delete = sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
467 compute_insert_delete (edge_list
, antloc
, later
, laterin
, *insert
, *delete);
472 #ifdef LCM_DEBUG_INFO
475 dump_sbitmap_vector (file
, "pre_insert_map", "", *insert
, num_edges
);
476 dump_sbitmap_vector (file
, "pre_delete_map", "", *delete,
484 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
485 Return the number of passes we performed to iterate to a solution. */
488 compute_available (avloc
, kill
, avout
, avin
)
489 sbitmap
*avloc
, *kill
, *avout
, *avin
;
493 basic_block
*worklist
, *qin
, *qout
, *qend
;
496 /* Allocate a worklist array/queue. Entries are only added to the
497 list if they were not already on the list. So the size is
498 bounded by the number of basic blocks. */
499 qin
= qout
= worklist
500 = (basic_block
*) xmalloc (sizeof (basic_block
) * n_basic_blocks
);
502 /* We want a maximal solution. */
503 sbitmap_vector_ones (avout
, n_basic_blocks
);
505 /* Put every block on the worklist; this is necessary because of the
506 optimistic initialization of AVOUT above. */
507 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
509 *qin
++ = BASIC_BLOCK (bb
);
510 BASIC_BLOCK (bb
)->aux
= BASIC_BLOCK (bb
);
514 qend
= &worklist
[n_basic_blocks
];
515 qlen
= n_basic_blocks
;
517 /* Mark blocks which are successors of the entry block so that we
518 can easily identify them below. */
519 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
520 e
->dest
->aux
= ENTRY_BLOCK_PTR
;
522 /* Iterate until the worklist is empty. */
525 /* Take the first entry off the worklist. */
526 basic_block b
= *qout
++;
533 /* If one of the predecessor blocks is the ENTRY block, then the
534 intersection of avouts is the null set. We can identify such blocks
535 by the special value in the AUX field in the block structure. */
536 if (b
->aux
== ENTRY_BLOCK_PTR
)
537 /* Do not clear the aux field for blocks which are successors of the
538 ENTRY block. That way we never add then to the worklist again. */
539 sbitmap_zero (avin
[bb
]);
542 /* Clear the aux field of this block so that it can be added to
543 the worklist again if necessary. */
545 sbitmap_intersection_of_preds (avin
[bb
], avout
, bb
);
548 if (sbitmap_union_of_diff (avout
[bb
], avloc
[bb
], avin
[bb
], kill
[bb
]))
549 /* If the out state of this block changed, then we need
550 to add the successors of this block to the worklist
551 if they are not already on the worklist. */
552 for (e
= b
->succ
; e
; e
= e
->succ_next
)
553 if (!e
->dest
->aux
&& e
->dest
!= EXIT_BLOCK_PTR
)
567 /* Compute the farthest vector for edge based lcm. */
570 compute_farthest (edge_list
, n_exprs
, st_avout
, st_avin
, st_antin
,
572 struct edge_list
*edge_list
;
574 sbitmap
*st_avout
, *st_avin
, *st_antin
, *kill
, *farthest
;
576 sbitmap difference
, temp_bitmap
;
578 basic_block pred
, succ
;
580 num_edges
= NUM_EDGES (edge_list
);
582 difference
= sbitmap_alloc (n_exprs
);
583 temp_bitmap
= sbitmap_alloc (n_exprs
);
585 for (x
= 0; x
< num_edges
; x
++)
587 pred
= INDEX_EDGE_PRED_BB (edge_list
, x
);
588 succ
= INDEX_EDGE_SUCC_BB (edge_list
, x
);
589 if (succ
== EXIT_BLOCK_PTR
)
590 sbitmap_copy (farthest
[x
], st_avout
[pred
->index
]);
593 if (pred
== ENTRY_BLOCK_PTR
)
594 sbitmap_zero (farthest
[x
]);
597 sbitmap_difference (difference
, st_avout
[pred
->index
],
598 st_antin
[succ
->index
]);
599 sbitmap_not (temp_bitmap
, st_avin
[succ
->index
]);
600 sbitmap_a_and_b_or_c (farthest
[x
], difference
,
601 kill
[succ
->index
], temp_bitmap
);
610 /* Compute nearer and nearerout vectors for edge based lcm.
612 This is the mirror of compute_laterin, additional comments on the
613 implementation can be found before compute_laterin. */
616 compute_nearerout (edge_list
, farthest
, st_avloc
, nearer
, nearerout
)
617 struct edge_list
*edge_list
;
618 sbitmap
*farthest
, *st_avloc
, *nearer
, *nearerout
;
620 int bb
, num_edges
, i
;
622 basic_block
*worklist
, *tos
;
624 num_edges
= NUM_EDGES (edge_list
);
626 /* Allocate a worklist array/queue. Entries are only added to the
627 list if they were not already on the list. So the size is
628 bounded by the number of basic blocks. */
630 = (basic_block
*) xmalloc (sizeof (basic_block
) * (n_basic_blocks
+ 1));
632 /* Initialize NEARER for each edge and build a mapping from an edge to
634 for (i
= 0; i
< num_edges
; i
++)
635 INDEX_EDGE (edge_list
, i
)->aux
= (void *) (size_t) i
;
637 /* We want a maximal solution. */
638 sbitmap_vector_ones (nearer
, num_edges
);
640 /* Note that even though we want an optimistic setting of NEARER, we
641 do not want to be overly optimistic. Consider an incoming edge to
642 the exit block. That edge should always have a NEARER value the
643 same as FARTHEST for that edge. */
644 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
645 sbitmap_copy (nearer
[(size_t)e
->aux
], farthest
[(size_t)e
->aux
]);
647 /* Add all the blocks to the worklist. This prevents an early exit
648 from the loop given our optimistic initialization of NEARER. */
649 for (bb
= 0; bb
< n_basic_blocks
; bb
++)
651 basic_block b
= BASIC_BLOCK (bb
);
656 /* Iterate until the worklist is empty. */
657 while (tos
!= worklist
)
659 /* Take the first entry off the worklist. */
660 basic_block b
= *--tos
;
663 /* Compute the intersection of NEARER for each outgoing edge from B. */
665 sbitmap_ones (nearerout
[bb
]);
666 for (e
= b
->succ
; e
!= NULL
; e
= e
->succ_next
)
667 sbitmap_a_and_b (nearerout
[bb
], nearerout
[bb
],
668 nearer
[(size_t) e
->aux
]);
670 /* Calculate NEARER for all incoming edges. */
671 for (e
= b
->pred
; e
!= NULL
; e
= e
->pred_next
)
672 if (sbitmap_union_of_diff (nearer
[(size_t) e
->aux
],
673 farthest
[(size_t) e
->aux
],
674 nearerout
[e
->dest
->index
],
675 st_avloc
[e
->dest
->index
])
676 /* If NEARER for an incoming edge was changed, then we need
677 to add the source of the incoming edge to the worklist. */
678 && e
->src
!= ENTRY_BLOCK_PTR
&& e
->src
->aux
== 0)
685 /* Computation of insertion and deletion points requires computing NEAREROUT
686 for the ENTRY block. We allocated an extra entry in the NEAREROUT array
687 for just this purpose. */
688 sbitmap_ones (nearerout
[n_basic_blocks
]);
689 for (e
= ENTRY_BLOCK_PTR
->succ
; e
!= NULL
; e
= e
->succ_next
)
690 sbitmap_a_and_b (nearerout
[n_basic_blocks
],
691 nearerout
[n_basic_blocks
],
692 nearer
[(size_t) e
->aux
]);
697 /* Compute the insertion and deletion points for edge based LCM. */
700 compute_rev_insert_delete (edge_list
, st_avloc
, nearer
, nearerout
,
702 struct edge_list
*edge_list
;
703 sbitmap
*st_avloc
, *nearer
, *nearerout
, *insert
, *delete;
707 for (x
= 0; x
< n_basic_blocks
; x
++)
708 sbitmap_difference (delete[x
], st_avloc
[x
], nearerout
[x
]);
710 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
712 basic_block b
= INDEX_EDGE_PRED_BB (edge_list
, x
);
713 if (b
== ENTRY_BLOCK_PTR
)
714 sbitmap_difference (insert
[x
], nearer
[x
], nearerout
[n_basic_blocks
]);
716 sbitmap_difference (insert
[x
], nearer
[x
], nearerout
[b
->index
]);
720 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
721 insert and delete vectors for edge based reverse LCM. Returns an
722 edgelist which is used to map the insert vector to what edge
723 an expression should be inserted on. */
726 pre_edge_rev_lcm (file
, n_exprs
, transp
, st_avloc
, st_antloc
, kill
,
728 FILE *file ATTRIBUTE_UNUSED
;
737 sbitmap
*st_antin
, *st_antout
;
738 sbitmap
*st_avout
, *st_avin
, *farthest
;
739 sbitmap
*nearer
, *nearerout
;
740 struct edge_list
*edge_list
;
743 edge_list
= create_edge_list ();
744 num_edges
= NUM_EDGES (edge_list
);
746 st_antin
= (sbitmap
*) sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
747 st_antout
= (sbitmap
*) sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
748 sbitmap_vector_zero (st_antin
, n_basic_blocks
);
749 sbitmap_vector_zero (st_antout
, n_basic_blocks
);
750 compute_antinout_edge (st_antloc
, transp
, st_antin
, st_antout
);
752 /* Compute global anticipatability. */
753 st_avout
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
754 st_avin
= sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
755 compute_available (st_avloc
, kill
, st_avout
, st_avin
);
757 #ifdef LCM_DEBUG_INFO
760 fprintf (file
, "Edge List:\n");
761 verify_edge_list (file
, edge_list
);
762 print_edge_list (file
, edge_list
);
763 dump_sbitmap_vector (file
, "transp", "", transp
, n_basic_blocks
);
764 dump_sbitmap_vector (file
, "st_avloc", "", st_avloc
, n_basic_blocks
);
765 dump_sbitmap_vector (file
, "st_antloc", "", st_antloc
, n_basic_blocks
);
766 dump_sbitmap_vector (file
, "st_antin", "", st_antin
, n_basic_blocks
);
767 dump_sbitmap_vector (file
, "st_antout", "", st_antout
, n_basic_blocks
);
768 dump_sbitmap_vector (file
, "st_kill", "", kill
, n_basic_blocks
);
772 #ifdef LCM_DEBUG_INFO
775 dump_sbitmap_vector (file
, "st_avout", "", st_avout
, n_basic_blocks
);
776 dump_sbitmap_vector (file
, "st_avin", "", st_avin
, n_basic_blocks
);
780 /* Compute farthestness. */
781 farthest
= sbitmap_vector_alloc (num_edges
, n_exprs
);
782 compute_farthest (edge_list
, n_exprs
, st_avout
, st_avin
, st_antin
,
785 #ifdef LCM_DEBUG_INFO
787 dump_sbitmap_vector (file
, "farthest", "", farthest
, num_edges
);
793 nearer
= sbitmap_vector_alloc (num_edges
, n_exprs
);
795 /* Allocate an extra element for the entry block. */
796 nearerout
= sbitmap_vector_alloc (n_basic_blocks
+ 1, n_exprs
);
797 compute_nearerout (edge_list
, farthest
, st_avloc
, nearer
, nearerout
);
799 #ifdef LCM_DEBUG_INFO
802 dump_sbitmap_vector (file
, "nearerout", "", nearerout
,
804 dump_sbitmap_vector (file
, "nearer", "", nearer
, num_edges
);
810 *insert
= sbitmap_vector_alloc (num_edges
, n_exprs
);
811 *delete = sbitmap_vector_alloc (n_basic_blocks
, n_exprs
);
812 compute_rev_insert_delete (edge_list
, st_avloc
, nearer
, nearerout
,
818 #ifdef LCM_DEBUG_INFO
821 dump_sbitmap_vector (file
, "pre_insert_map", "", *insert
, num_edges
);
822 dump_sbitmap_vector (file
, "pre_delete_map", "", *delete,
832 The algorithm for setting the modes consists of scanning the insn list
833 and finding all the insns which require a specific mode. Each insn gets
834 a unique struct seginfo element. These structures are inserted into a list
835 for each basic block. For each entity, there is an array of bb_info over
836 the flow graph basic blocks (local var 'bb_info'), and contains a list
837 of all insns within that basic block, in the order they are encountered.
839 For each entity, any basic block WITHOUT any insns requiring a specific
840 mode are given a single entry, without a mode. (Each basic block
841 in the flow graph must have at least one entry in the segment table.)
843 The LCM algorithm is then run over the flow graph to determine where to
844 place the sets to the highest-priority value in respect of first the first
845 insn in any one block. Any adjustments required to the transparancy
846 vectors are made, then the next iteration starts for the next-lower
847 priority mode, till for each entity all modes are exhasted.
849 More details are located in the code for optimize_mode_switching(). */
851 /* This structure contains the information for each insn which requires
852 either single or double mode to be set.
853 MODE is the mode this insn must be executed in.
854 INSN_PTR is the insn to be executed.
855 BBNUM is the flow graph basic block this insn occurs in.
856 NEXT is the next insn in the same basic block. */
862 struct seginfo
*next
;
863 HARD_REG_SET regs_live
;
868 struct seginfo
*seginfo
;
872 /* These bitmaps are used for the LCM algorithm. */
874 #ifdef OPTIMIZE_MODE_SWITCHING
875 static sbitmap
*antic
;
876 static sbitmap
*transp
;
877 static sbitmap
*comp
;
878 static sbitmap
*delete;
879 static sbitmap
*insert
;
881 static struct seginfo
* new_seginfo
PARAMS ((int, rtx
, int, HARD_REG_SET
));
882 static void add_seginfo
PARAMS ((struct bb_info
*, struct seginfo
*));
883 static void reg_dies
PARAMS ((rtx
, HARD_REG_SET
));
884 static void reg_becomes_live
PARAMS ((rtx
, rtx
, void *));
885 static void make_preds_opaque
PARAMS ((basic_block
, int));
888 #ifdef OPTIMIZE_MODE_SWITCHING
890 /* This function will allocate a new BBINFO structure, initialized
891 with the MODE, INSN, and basic block BB parameters. */
893 static struct seginfo
*
894 new_seginfo (mode
, insn
, bb
, regs_live
)
898 HARD_REG_SET regs_live
;
901 ptr
= xmalloc (sizeof (struct seginfo
));
903 ptr
->insn_ptr
= insn
;
906 COPY_HARD_REG_SET (ptr
->regs_live
, regs_live
);
910 /* Add a seginfo element to the end of a list.
911 HEAD is a pointer to the list beginning.
912 INFO is the structure to be linked in. */
915 add_seginfo (head
, info
)
916 struct bb_info
*head
;
917 struct seginfo
*info
;
921 if (head
->seginfo
== NULL
)
922 head
->seginfo
= info
;
926 while (ptr
->next
!= NULL
)
932 /* Make all predecessors of basic block B opaque, recursively, till we hit
933 some that are already non-transparent, or an edge where aux is set; that
934 denotes that a mode set is to be done on that edge.
935 J is the bit number in the bitmaps that corresponds to the entity that
936 we are currently handling mode-switching for. */
939 make_preds_opaque (b
, j
)
945 for (e
= b
->pred
; e
; e
= e
->pred_next
)
947 basic_block pb
= e
->src
;
949 if (e
->aux
|| ! TEST_BIT (transp
[pb
->index
], j
))
952 RESET_BIT (transp
[pb
->index
], j
);
953 make_preds_opaque (pb
, j
);
957 /* Record in LIVE that register REG died. */
966 if (GET_CODE (reg
) != REG
)
970 if (regno
< FIRST_PSEUDO_REGISTER
)
971 for (nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
)) - 1; nregs
>= 0;
973 CLEAR_HARD_REG_BIT (live
, regno
+ nregs
);
976 /* Record in LIVE that register REG became live.
977 This is called via note_stores. */
980 reg_becomes_live (reg
, setter
, live
)
982 rtx setter ATTRIBUTE_UNUSED
;
987 if (GET_CODE (reg
) == SUBREG
)
988 reg
= SUBREG_REG (reg
);
990 if (GET_CODE (reg
) != REG
)
994 if (regno
< FIRST_PSEUDO_REGISTER
)
995 for (nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
)) - 1; nregs
>= 0;
997 SET_HARD_REG_BIT (* (HARD_REG_SET
*) live
, regno
+ nregs
);
1000 /* Find all insns that need a particular mode setting, and insert the
1001 necessary mode switches. Return true if we did work. */
1004 optimize_mode_switching (file
)
1010 int need_commit
= 0;
1012 struct edge_list
*edge_list
;
1013 static int num_modes
[] = NUM_MODES_FOR_MODE_SWITCHING
;
1014 #define N_ENTITIES (sizeof num_modes / sizeof (int))
1015 int entity_map
[N_ENTITIES
];
1016 struct bb_info
*bb_info
[N_ENTITIES
];
1019 int max_num_modes
= 0;
1021 for (e
= N_ENTITIES
- 1, n_entities
= 0; e
>= 0; e
--)
1022 if (OPTIMIZE_MODE_SWITCHING (e
))
1024 /* Create the list of segments within each basic block. */
1026 = (struct bb_info
*) xcalloc (n_basic_blocks
, sizeof **bb_info
);
1027 entity_map
[n_entities
++] = e
;
1028 if (num_modes
[e
] > max_num_modes
)
1029 max_num_modes
= num_modes
[e
];
1035 /* Create the bitmap vectors. */
1037 antic
= sbitmap_vector_alloc (n_basic_blocks
, n_entities
);
1038 transp
= sbitmap_vector_alloc (n_basic_blocks
, n_entities
);
1039 comp
= sbitmap_vector_alloc (n_basic_blocks
, n_entities
);
1041 sbitmap_vector_ones (transp
, n_basic_blocks
);
1043 for (j
= n_entities
- 1; j
>= 0; j
--)
1045 int e
= entity_map
[j
];
1046 int no_mode
= num_modes
[e
];
1047 struct bb_info
*info
= bb_info
[j
];
1049 /* Determine what the first use (if any) need for a mode of entity E is.
1050 This will be the mode that is anticipatable for this block.
1051 Also compute the initial transparency settings. */
1052 for (bb
= 0 ; bb
< n_basic_blocks
; bb
++)
1054 struct seginfo
*ptr
;
1055 int last_mode
= no_mode
;
1056 HARD_REG_SET live_now
;
1058 REG_SET_TO_HARD_REG_SET (live_now
,
1059 BASIC_BLOCK (bb
)->global_live_at_start
);
1060 for (insn
= BLOCK_HEAD (bb
);
1061 insn
!= NULL
&& insn
!= NEXT_INSN (BLOCK_END (bb
));
1062 insn
= NEXT_INSN (insn
))
1064 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
1066 int mode
= MODE_NEEDED (e
, insn
);
1069 if (mode
!= no_mode
&& mode
!= last_mode
)
1072 ptr
= new_seginfo (mode
, insn
, bb
, live_now
);
1073 add_seginfo (info
+ bb
, ptr
);
1074 RESET_BIT (transp
[bb
], j
);
1077 /* Update LIVE_NOW. */
1078 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1079 if (REG_NOTE_KIND (link
) == REG_DEAD
)
1080 reg_dies (XEXP (link
, 0), live_now
);
1082 note_stores (PATTERN (insn
), reg_becomes_live
, &live_now
);
1083 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1084 if (REG_NOTE_KIND (link
) == REG_UNUSED
)
1085 reg_dies (XEXP (link
, 0), live_now
);
1089 /* If this is a predecessor of the exit block, and we must
1090 force a mode on exit, make note of that. */
1092 if (NORMAL_MODE (e
) != no_mode
&& last_mode
!= NORMAL_MODE (e
))
1093 for (eg
= BASIC_BLOCK (bb
)->succ
; eg
; eg
= eg
->succ_next
)
1094 if (eg
->dest
== EXIT_BLOCK_PTR
)
1096 rtx insn
= BLOCK_END (bb
);
1098 /* Find the last insn before a USE and/or JUMP. */
1099 while ((GET_CODE (insn
) == INSN
1100 && GET_CODE (PATTERN (insn
)) == USE
)
1101 || GET_CODE (insn
) == JUMP_INSN
)
1102 insn
= PREV_INSN (insn
);
1103 if (insn
!= BLOCK_END (bb
) && NEXT_INSN (insn
))
1104 insn
= NEXT_INSN (insn
);
1105 last_mode
= NORMAL_MODE (e
);
1106 add_seginfo (info
+ bb
,
1107 new_seginfo (last_mode
, insn
, bb
, live_now
));
1108 RESET_BIT (transp
[bb
], j
);
1112 info
[bb
].computing
= last_mode
;
1113 /* Check for blocks without ANY mode requirements. */
1114 if (last_mode
== no_mode
)
1116 ptr
= new_seginfo (no_mode
, insn
, bb
, live_now
);
1117 add_seginfo (info
+ bb
, ptr
);
1122 int mode
= NORMAL_MODE (e
);
1124 if (mode
!= no_mode
)
1126 for (eg
= ENTRY_BLOCK_PTR
->succ
; eg
; eg
= eg
->succ_next
)
1128 bb
= eg
->dest
->index
;
1130 /* By always making this nontransparent, we save
1131 an extra check in make_preds_opaque. We also
1132 need this to avoid confusing pre_edge_lcm when
1133 antic is cleared but transp and comp are set. */
1134 RESET_BIT (transp
[bb
], j
);
1136 /* If the block already has MODE, pretend it
1137 has none (because we don't need to set it),
1138 but retain whatever mode it computes. */
1139 if (info
[bb
].seginfo
->mode
== mode
)
1140 info
[bb
].seginfo
->mode
= no_mode
;
1142 /* Insert a fake computing definition of MODE into entry
1143 blocks which compute no mode. This represents the mode on
1145 else if (info
[bb
].computing
== no_mode
)
1147 info
[bb
].computing
= mode
;
1148 info
[bb
].seginfo
->mode
= no_mode
;
1153 #endif /* NORMAL_MODE */
1156 kill
= sbitmap_vector_alloc (n_basic_blocks
, n_entities
);
1157 for (i
= 0; i
< max_num_modes
; i
++)
1159 int current_mode
[N_ENTITIES
];
1161 /* Set the anticipatable and computing arrays. */
1162 sbitmap_vector_zero (antic
, n_basic_blocks
);
1163 sbitmap_vector_zero (comp
, n_basic_blocks
);
1164 for (j
= n_entities
- 1; j
>= 0; j
--)
1166 int m
= current_mode
[j
] = MODE_PRIORITY_TO_MODE (entity_map
[j
], i
);
1167 struct bb_info
*info
= bb_info
[j
];
1169 for (bb
= 0 ; bb
< n_basic_blocks
; bb
++)
1171 if (info
[bb
].seginfo
->mode
== m
)
1172 SET_BIT (antic
[bb
], j
);
1174 if (info
[bb
].computing
== m
)
1175 SET_BIT (comp
[bb
], j
);
1179 /* Calculate the optimal locations for the
1180 placement mode switches to modes with priority I. */
1182 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
1183 sbitmap_not (kill
[bb
], transp
[bb
]);
1184 edge_list
= pre_edge_lcm (file
, 1, transp
, comp
, antic
,
1185 kill
, &insert
, &delete);
1187 for (j
= n_entities
- 1; j
>= 0; j
--)
1189 /* Insert all mode sets that have been inserted by lcm. */
1190 int no_mode
= num_modes
[entity_map
[j
]];
1192 /* Wherever we have moved a mode setting upwards in the flow graph,
1193 the blocks between the new setting site and the now redundant
1194 computation ceases to be transparent for any lower-priority
1195 mode of the same entity. First set the aux field of each
1196 insertion site edge non-transparent, then propagate the new
1197 non-transparency from the redundant computation upwards till
1198 we hit an insertion site or an already non-transparent block. */
1199 for (e
= NUM_EDGES (edge_list
) - 1; e
>= 0; e
--)
1201 edge eg
= INDEX_EDGE (edge_list
, e
);
1204 HARD_REG_SET live_at_edge
;
1209 if (! TEST_BIT (insert
[e
], j
))
1212 eg
->aux
= (void *)1;
1214 mode
= current_mode
[j
];
1217 REG_SET_TO_HARD_REG_SET (live_at_edge
,
1218 src_bb
->global_live_at_end
);
1221 EMIT_MODE_SET (entity_map
[j
], mode
, live_at_edge
);
1222 mode_set
= gen_sequence ();
1225 /* If this is an abnormal edge, we'll insert at the end of the
1227 if (eg
->flags
& EDGE_ABNORMAL
)
1229 src_bb
->end
= emit_insn_after (mode_set
, src_bb
->end
);
1230 bb_info
[j
][src_bb
->index
].computing
= mode
;
1231 RESET_BIT (transp
[src_bb
->index
], j
);
1236 insert_insn_on_edge (mode_set
, eg
);
1240 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
1241 if (TEST_BIT (delete[bb
], j
))
1243 make_preds_opaque (BASIC_BLOCK (bb
), j
);
1244 /* Cancel the 'deleted' mode set. */
1245 bb_info
[j
][bb
].seginfo
->mode
= no_mode
;
1249 free_edge_list (edge_list
);
1252 /* Now output the remaining mode sets in all the segments. */
1253 for (j
= n_entities
- 1; j
>= 0; j
--)
1255 int no_mode
= num_modes
[entity_map
[j
]];
1257 for (bb
= n_basic_blocks
- 1; bb
>= 0; bb
--)
1259 struct seginfo
*ptr
, *next
;
1260 for (ptr
= bb_info
[j
][bb
].seginfo
; ptr
; ptr
= next
)
1263 if (ptr
->mode
!= no_mode
)
1268 EMIT_MODE_SET (entity_map
[j
], ptr
->mode
, ptr
->regs_live
);
1269 mode_set
= gen_sequence ();
1272 if (NOTE_LINE_NUMBER (ptr
->insn_ptr
) == NOTE_INSN_BASIC_BLOCK
)
1273 emit_block_insn_after (mode_set
, ptr
->insn_ptr
,
1274 BASIC_BLOCK (ptr
->bbnum
));
1276 emit_block_insn_before (mode_set
, ptr
->insn_ptr
,
1277 BASIC_BLOCK (ptr
->bbnum
));
1287 /* Finished. Free up all the things we've allocated. */
1289 sbitmap_vector_free (kill
);
1290 sbitmap_vector_free (antic
);
1291 sbitmap_vector_free (transp
);
1292 sbitmap_vector_free (comp
);
1293 sbitmap_vector_free (delete);
1294 sbitmap_vector_free (insert
);
1297 commit_edge_insertions ();
1299 /* Ideally we'd figure out what blocks were affected and start from
1300 there, but this is enormously complicated by commit_edge_insertions,
1301 which would screw up any indicies we'd collected, and also need to
1302 be involved in the update. Bail and recompute global life info for
1305 allocate_reg_life_data ();
1306 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
1307 (PROP_DEATH_NOTES
| PROP_KILL_DEAD_CODE
1308 | PROP_SCAN_DEAD_CODE
| PROP_REG_INFO
));
1312 #endif /* OPTIMIZE_MODE_SWITCHING */