Only create gcc/configargs.h if gcc build directory is present
[official-gcc.git] / gcc / lcm.c
blobdc037970f64df95ffae432e11f90d509c19ea8be
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)
9 any later version.
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.
29 * Load/store motion.
31 * Copy motion.
33 * Conversion of flat register files to a stacked register
34 model.
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
43 or functions.
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. */
52 #include "config.h"
53 #include "system.h"
54 #include "rtl.h"
55 #include "regs.h"
56 #include "hard-reg-set.h"
57 #include "flags.h"
58 #include "real.h"
59 #include "insn-config.h"
60 #include "recog.h"
61 #include "basic-block.h"
62 #include "tm_p.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,
72 sbitmap *, sbitmap *,
73 sbitmap *, sbitmap *,
74 sbitmap *));
75 static void compute_laterin PARAMS ((struct edge_list *, sbitmap *,
76 sbitmap *, sbitmap *,
77 sbitmap *));
78 static void compute_insert_delete PARAMS ((struct edge_list *edge_list,
79 sbitmap *, sbitmap *,
80 sbitmap *, sbitmap *,
81 sbitmap *));
83 /* Edge based LCM routines on a reverse flowgraph. */
84 static void compute_farthest PARAMS ((struct edge_list *, int,
85 sbitmap *, sbitmap *,
86 sbitmap*, sbitmap *,
87 sbitmap *));
88 static void compute_nearerout PARAMS ((struct edge_list *, sbitmap *,
89 sbitmap *, sbitmap *,
90 sbitmap *));
91 static void compute_rev_insert_delete PARAMS ((struct edge_list *edge_list,
92 sbitmap *, sbitmap *,
93 sbitmap *, sbitmap *,
94 sbitmap *));
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. */
102 static void
103 compute_antinout_edge (antloc, transp, antin, antout)
104 sbitmap *antloc;
105 sbitmap *transp;
106 sbitmap *antin;
107 sbitmap *antout;
109 int bb;
110 edge e;
111 basic_block *worklist, *qin, *qout, *qend;
112 unsigned int qlen;
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
121 ANTIN. */
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);
132 qin = worklist;
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. */
142 while (qlen)
144 /* Take the first entry off the worklist. */
145 basic_block b = *qout++;
146 bb = b->index;
147 qlen--;
149 if (qout >= qend)
150 qout = worklist;
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
155 again. */
156 sbitmap_zero (antout[bb]);
157 else
159 /* Clear the aux field of this block so that it can be added to
160 the worklist again if necessary. */
161 b->aux = NULL;
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)
172 *qin++ = e->src;
173 e->src->aux = e;
174 qlen++;
175 if (qin >= qend)
176 qin = worklist;
180 free (worklist);
183 /* Compute the earliest vector for edge based lcm. */
185 static void
186 compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest)
187 struct edge_list *edge_list;
188 int n_exprs;
189 sbitmap *antin, *antout, *avout, *kill, *earliest;
191 sbitmap difference, temp_bitmap;
192 int x, num_edges;
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]);
206 else
208 if (succ == EXIT_BLOCK_PTR)
209 sbitmap_zero (earliest[x]);
210 else
212 sbitmap_difference (difference, antin[succ->index],
213 avout[pred->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);
221 free (temp_bitmap);
222 free (difference);
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.
236 Boundary conditions:
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
241 worklist.
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
252 to compute it. */
254 static void
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;
260 edge e;
261 basic_block *worklist, *qin, *qout, *qend;
262 unsigned int qlen;
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
280 loop.
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);
300 *qin++ = b;
301 b->aux = b;
303 qin = worklist;
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. */
311 while (qlen)
313 /* Take the first entry off the worklist. */
314 basic_block b = *qout++;
315 b->aux = NULL;
316 qlen--;
317 if (qout >= qend)
318 qout = worklist;
320 /* Compute the intersection of LATERIN for each incoming edge to B. */
321 bb = b->index;
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)
336 *qin++ = e->dest;
337 e->dest->aux = e;
338 qlen++;
339 if (qin >= qend)
340 qin = worklist;
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]);
353 free (worklist);
356 /* Compute the insertion and deletion points for edge based LCM. */
358 static void
359 compute_insert_delete (edge_list, antloc, later, laterin,
360 insert, delete)
361 struct edge_list *edge_list;
362 sbitmap *antloc, *later, *laterin, *insert, *delete;
364 int x;
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]);
375 else
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. */
384 struct edge_list *
385 pre_edge_lcm (file, n_exprs, transp, avloc, antloc, kill, insert, delete)
386 FILE *file ATTRIBUTE_UNUSED;
387 int n_exprs;
388 sbitmap *transp;
389 sbitmap *avloc;
390 sbitmap *antloc;
391 sbitmap *kill;
392 sbitmap **insert;
393 sbitmap **delete;
395 sbitmap *antin, *antout, *earliest;
396 sbitmap *avin, *avout;
397 sbitmap *later, *laterin;
398 struct edge_list *edge_list;
399 int num_edges;
401 edge_list = create_edge_list ();
402 num_edges = NUM_EDGES (edge_list);
404 #ifdef LCM_DEBUG_INFO
405 if (file)
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);
415 #endif
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);
421 free (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
429 if (file)
431 dump_sbitmap_vector (file, "antin", "", antin, n_basic_blocks);
432 dump_sbitmap_vector (file, "antout", "", antout, n_basic_blocks);
434 #endif
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
441 if (file)
442 dump_sbitmap_vector (file, "earliest", "", earliest, num_edges);
443 #endif
445 free (antout);
446 free (antin);
447 free (avout);
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
456 if (file)
458 dump_sbitmap_vector (file, "laterin", "", laterin, n_basic_blocks + 1);
459 dump_sbitmap_vector (file, "later", "", later, num_edges);
461 #endif
463 free (earliest);
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);
469 free (laterin);
470 free (later);
472 #ifdef LCM_DEBUG_INFO
473 if (file)
475 dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
476 dump_sbitmap_vector (file, "pre_delete_map", "", *delete,
477 n_basic_blocks);
479 #endif
481 return edge_list;
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. */
487 void
488 compute_available (avloc, kill, avout, avin)
489 sbitmap *avloc, *kill, *avout, *avin;
491 int bb;
492 edge e;
493 basic_block *worklist, *qin, *qout, *qend;
494 unsigned int qlen;
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);
513 qin = worklist;
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. */
523 while (qlen)
525 /* Take the first entry off the worklist. */
526 basic_block b = *qout++;
527 bb = b->index;
528 qlen--;
530 if (qout >= qend)
531 qout = worklist;
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]);
540 else
542 /* Clear the aux field of this block so that it can be added to
543 the worklist again if necessary. */
544 b->aux = NULL;
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)
555 *qin++ = e->dest;
556 e->dest->aux = e;
557 qlen++;
559 if (qin >= qend)
560 qin = worklist;
564 free (worklist);
567 /* Compute the farthest vector for edge based lcm. */
569 static void
570 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
571 kill, farthest)
572 struct edge_list *edge_list;
573 int n_exprs;
574 sbitmap *st_avout, *st_avin, *st_antin, *kill, *farthest;
576 sbitmap difference, temp_bitmap;
577 int x, num_edges;
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]);
591 else
593 if (pred == ENTRY_BLOCK_PTR)
594 sbitmap_zero (farthest[x]);
595 else
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);
606 free (temp_bitmap);
607 free (difference);
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. */
615 static void
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;
621 edge e;
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. */
629 tos = worklist
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
633 its index. */
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);
652 *tos++ = b;
653 b->aux = b;
656 /* Iterate until the worklist is empty. */
657 while (tos != worklist)
659 /* Take the first entry off the worklist. */
660 basic_block b = *--tos;
661 b->aux = NULL;
663 /* Compute the intersection of NEARER for each outgoing edge from B. */
664 bb = b->index;
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)
680 *tos++ = e->src;
681 e->src->aux = e;
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]);
694 free (tos);
697 /* Compute the insertion and deletion points for edge based LCM. */
699 static void
700 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
701 insert, delete)
702 struct edge_list *edge_list;
703 sbitmap *st_avloc, *nearer, *nearerout, *insert, *delete;
705 int x;
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]);
715 else
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. */
725 struct edge_list *
726 pre_edge_rev_lcm (file, n_exprs, transp, st_avloc, st_antloc, kill,
727 insert, delete)
728 FILE *file ATTRIBUTE_UNUSED;
729 int n_exprs;
730 sbitmap *transp;
731 sbitmap *st_avloc;
732 sbitmap *st_antloc;
733 sbitmap *kill;
734 sbitmap **insert;
735 sbitmap **delete;
737 sbitmap *st_antin, *st_antout;
738 sbitmap *st_avout, *st_avin, *farthest;
739 sbitmap *nearer, *nearerout;
740 struct edge_list *edge_list;
741 int num_edges;
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
758 if (file)
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);
770 #endif
772 #ifdef LCM_DEBUG_INFO
773 if (file)
775 dump_sbitmap_vector (file, "st_avout", "", st_avout, n_basic_blocks);
776 dump_sbitmap_vector (file, "st_avin", "", st_avin, n_basic_blocks);
778 #endif
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,
783 kill, farthest);
785 #ifdef LCM_DEBUG_INFO
786 if (file)
787 dump_sbitmap_vector (file, "farthest", "", farthest, num_edges);
788 #endif
790 free (st_avin);
791 free (st_avout);
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
800 if (file)
802 dump_sbitmap_vector (file, "nearerout", "", nearerout,
803 n_basic_blocks + 1);
804 dump_sbitmap_vector (file, "nearer", "", nearer, num_edges);
806 #endif
808 free (farthest);
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,
813 *insert, *delete);
815 free (nearerout);
816 free (nearer);
818 #ifdef LCM_DEBUG_INFO
819 if (file)
821 dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
822 dump_sbitmap_vector (file, "pre_delete_map", "", *delete,
823 n_basic_blocks);
825 #endif
827 return edge_list;
830 /* Mode switching:
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. */
857 struct seginfo
859 int mode;
860 rtx insn_ptr;
861 int bbnum;
862 struct seginfo *next;
863 HARD_REG_SET regs_live;
866 struct bb_info
868 struct seginfo *seginfo;
869 int computing;
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));
886 #endif
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)
895 int mode;
896 rtx insn;
897 int bb;
898 HARD_REG_SET regs_live;
900 struct seginfo *ptr;
901 ptr = xmalloc (sizeof (struct seginfo));
902 ptr->mode = mode;
903 ptr->insn_ptr = insn;
904 ptr->bbnum = bb;
905 ptr->next = NULL;
906 COPY_HARD_REG_SET (ptr->regs_live, regs_live);
907 return ptr;
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. */
914 static void
915 add_seginfo (head, info)
916 struct bb_info *head;
917 struct seginfo *info;
919 struct seginfo *ptr;
921 if (head->seginfo == NULL)
922 head->seginfo = info;
923 else
925 ptr = head->seginfo;
926 while (ptr->next != NULL)
927 ptr = ptr->next;
928 ptr->next = info;
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. */
938 static void
939 make_preds_opaque (b, j)
940 basic_block b;
941 int j;
943 edge e;
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))
950 continue;
952 RESET_BIT (transp[pb->index], j);
953 make_preds_opaque (pb, j);
957 /* Record in LIVE that register REG died. */
959 static void
960 reg_dies (reg, live)
961 rtx reg;
962 HARD_REG_SET live;
964 int regno, nregs;
966 if (GET_CODE (reg) != REG)
967 return;
969 regno = REGNO (reg);
970 if (regno < FIRST_PSEUDO_REGISTER)
971 for (nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1; nregs >= 0;
972 nregs--)
973 CLEAR_HARD_REG_BIT (live, regno + nregs);
976 /* Record in LIVE that register REG became live.
977 This is called via note_stores. */
979 static void
980 reg_becomes_live (reg, setter, live)
981 rtx reg;
982 rtx setter ATTRIBUTE_UNUSED;
983 void *live;
985 int regno, nregs;
987 if (GET_CODE (reg) == SUBREG)
988 reg = SUBREG_REG (reg);
990 if (GET_CODE (reg) != REG)
991 return;
993 regno = REGNO (reg);
994 if (regno < FIRST_PSEUDO_REGISTER)
995 for (nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg)) - 1; nregs >= 0;
996 nregs--)
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)
1005 FILE *file;
1007 rtx insn;
1008 int bb, e;
1009 edge eg;
1010 int need_commit = 0;
1011 sbitmap *kill;
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];
1017 int i, j;
1018 int 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. */
1025 bb_info[n_entities]
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];
1032 if (! n_entities)
1033 return 0;
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 (INSN_P (insn))
1066 int mode = MODE_NEEDED (e, insn);
1067 rtx link;
1069 if (mode != no_mode && mode != last_mode)
1071 last_mode = 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. */
1091 #ifdef NORMAL_MODE
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);
1110 #endif
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);
1120 #ifdef NORMAL_MODE
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
1144 entry. */
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);
1202 int mode;
1203 basic_block src_bb;
1204 HARD_REG_SET live_at_edge;
1205 rtx mode_set;
1207 eg->aux = 0;
1209 if (! TEST_BIT (insert[e], j))
1210 continue;
1212 eg->aux = (void *)1;
1214 mode = current_mode[j];
1215 src_bb = eg->src;
1217 REG_SET_TO_HARD_REG_SET (live_at_edge,
1218 src_bb->global_live_at_end);
1220 start_sequence ();
1221 EMIT_MODE_SET (entity_map[j], mode, live_at_edge);
1222 mode_set = gen_sequence ();
1223 end_sequence ();
1225 /* If this is an abnormal edge, we'll insert at the end of the
1226 previous block. */
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);
1233 else
1235 need_commit = 1;
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)
1262 next = ptr->next;
1263 if (ptr->mode != no_mode)
1265 rtx mode_set;
1267 start_sequence ();
1268 EMIT_MODE_SET (entity_map[j], ptr->mode, ptr->regs_live);
1269 mode_set = gen_sequence ();
1270 end_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));
1275 else
1276 emit_block_insn_before (mode_set, ptr->insn_ptr,
1277 BASIC_BLOCK (ptr->bbnum));
1280 free (ptr);
1284 free (bb_info[j]);
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);
1296 if (need_commit)
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
1303 everything. */
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));
1310 return 1;
1312 #endif /* OPTIMIZE_MODE_SWITCHING */