Add option for whether ceil etc. can raise "inexact", adjust x86 conditions.
[official-gcc.git] / gcc / lcm.c
blob948e7bc8fc7bdeeee4f70d4f8c52d2c346b6e7b8
1 /* Generic partial redundancy elimination with lazy code motion support.
2 Copyright (C) 1998-2016 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* These routines are meant to be used by various optimization
21 passes which can be modeled as lazy code motion problems.
22 Including, but not limited to:
24 * Traditional partial redundancy elimination.
26 * Placement of caller/caller register save/restores.
28 * Load/store motion.
30 * Copy motion.
32 * Conversion of flat register files to a stacked register
33 model.
35 * Dead load/store elimination.
37 These routines accept as input:
39 * Basic block information (number of blocks, lists of
40 predecessors and successors). Note the granularity
41 does not need to be basic block, they could be statements
42 or functions.
44 * Bitmaps of local properties (computed, transparent and
45 anticipatable expressions).
47 The output of these routines is bitmap of redundant computations
48 and a bitmap of optimal placement points. */
51 #include "config.h"
52 #include "system.h"
53 #include "coretypes.h"
54 #include "backend.h"
55 #include "cfganal.h"
56 #include "lcm.h"
58 /* Edge based LCM routines. */
59 static void compute_antinout_edge (sbitmap *, sbitmap *, sbitmap *, sbitmap *);
60 static void compute_earliest (struct edge_list *, int, sbitmap *, sbitmap *,
61 sbitmap *, sbitmap *, sbitmap *);
62 static void compute_laterin (struct edge_list *, sbitmap *, sbitmap *,
63 sbitmap *, sbitmap *);
64 static void compute_insert_delete (struct edge_list *edge_list, sbitmap *,
65 sbitmap *, sbitmap *, sbitmap *, sbitmap *);
67 /* Edge based LCM routines on a reverse flowgraph. */
68 static void compute_farthest (struct edge_list *, int, sbitmap *, sbitmap *,
69 sbitmap*, sbitmap *, sbitmap *);
70 static void compute_nearerout (struct edge_list *, sbitmap *, sbitmap *,
71 sbitmap *, sbitmap *);
72 static void compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *,
73 sbitmap *, sbitmap *, sbitmap *,
74 sbitmap *);
76 /* Edge based lcm routines. */
78 /* Compute expression anticipatability at entrance and exit of each block.
79 This is done based on the flow graph, and not on the pred-succ lists.
80 Other than that, its pretty much identical to compute_antinout. */
82 static void
83 compute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin,
84 sbitmap *antout)
86 basic_block bb;
87 edge e;
88 basic_block *worklist, *qin, *qout, *qend;
89 unsigned int qlen;
90 edge_iterator ei;
92 /* Allocate a worklist array/queue. Entries are only added to the
93 list if they were not already on the list. So the size is
94 bounded by the number of basic blocks. */
95 qin = qout = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
97 /* We want a maximal solution, so make an optimistic initialization of
98 ANTIN. */
99 bitmap_vector_ones (antin, last_basic_block_for_fn (cfun));
101 /* Put every block on the worklist; this is necessary because of the
102 optimistic initialization of ANTIN above. */
103 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
104 int postorder_num = post_order_compute (postorder, false, false);
105 for (int i = 0; i < postorder_num; ++i)
107 bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
108 *qin++ = bb;
109 bb->aux = bb;
111 free (postorder);
113 qin = worklist;
114 qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
115 qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
117 /* Mark blocks which are predecessors of the exit block so that we
118 can easily identify them below. */
119 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
120 e->src->aux = EXIT_BLOCK_PTR_FOR_FN (cfun);
122 /* Iterate until the worklist is empty. */
123 while (qlen)
125 /* Take the first entry off the worklist. */
126 bb = *qout++;
127 qlen--;
129 if (qout >= qend)
130 qout = worklist;
132 if (bb->aux == EXIT_BLOCK_PTR_FOR_FN (cfun))
133 /* Do not clear the aux field for blocks which are predecessors of
134 the EXIT block. That way we never add then to the worklist
135 again. */
136 bitmap_clear (antout[bb->index]);
137 else
139 /* Clear the aux field of this block so that it can be added to
140 the worklist again if necessary. */
141 bb->aux = NULL;
142 bitmap_intersection_of_succs (antout[bb->index], antin, bb);
145 if (bitmap_or_and (antin[bb->index], antloc[bb->index],
146 transp[bb->index], antout[bb->index]))
147 /* If the in state of this block changed, then we need
148 to add the predecessors of this block to the worklist
149 if they are not already on the worklist. */
150 FOR_EACH_EDGE (e, ei, bb->preds)
151 if (!e->src->aux && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
153 *qin++ = e->src;
154 e->src->aux = e;
155 qlen++;
156 if (qin >= qend)
157 qin = worklist;
161 clear_aux_for_edges ();
162 clear_aux_for_blocks ();
163 free (worklist);
166 /* Compute the earliest vector for edge based lcm. */
168 static void
169 compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin,
170 sbitmap *antout, sbitmap *avout, sbitmap *kill,
171 sbitmap *earliest)
173 sbitmap difference, temp_bitmap;
174 int x, num_edges;
175 basic_block pred, succ;
177 num_edges = NUM_EDGES (edge_list);
179 difference = sbitmap_alloc (n_exprs);
180 temp_bitmap = sbitmap_alloc (n_exprs);
182 for (x = 0; x < num_edges; x++)
184 pred = INDEX_EDGE_PRED_BB (edge_list, x);
185 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
186 if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
187 bitmap_copy (earliest[x], antin[succ->index]);
188 else
190 if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun))
191 bitmap_clear (earliest[x]);
192 else
194 bitmap_and_compl (difference, antin[succ->index],
195 avout[pred->index]);
196 bitmap_not (temp_bitmap, antout[pred->index]);
197 bitmap_and_or (earliest[x], difference,
198 kill[pred->index], temp_bitmap);
203 sbitmap_free (temp_bitmap);
204 sbitmap_free (difference);
207 /* later(p,s) is dependent on the calculation of laterin(p).
208 laterin(p) is dependent on the calculation of later(p2,p).
210 laterin(ENTRY) is defined as all 0's
211 later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY)
212 laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)).
214 If we progress in this manner, starting with all basic blocks
215 in the work list, anytime we change later(bb), we need to add
216 succs(bb) to the worklist if they are not already on the worklist.
218 Boundary conditions:
220 We prime the worklist all the normal basic blocks. The ENTRY block can
221 never be added to the worklist since it is never the successor of any
222 block. We explicitly prevent the EXIT block from being added to the
223 worklist.
225 We optimistically initialize LATER. That is the only time this routine
226 will compute LATER for an edge out of the entry block since the entry
227 block is never on the worklist. Thus, LATERIN is neither used nor
228 computed for the ENTRY block.
230 Since the EXIT block is never added to the worklist, we will neither
231 use nor compute LATERIN for the exit block. Edges which reach the
232 EXIT block are handled in the normal fashion inside the loop. However,
233 the insertion/deletion computation needs LATERIN(EXIT), so we have
234 to compute it. */
236 static void
237 compute_laterin (struct edge_list *edge_list, sbitmap *earliest,
238 sbitmap *antloc, sbitmap *later, sbitmap *laterin)
240 int num_edges, i;
241 edge e;
242 basic_block *worklist, *qin, *qout, *qend, bb;
243 unsigned int qlen;
244 edge_iterator ei;
246 num_edges = NUM_EDGES (edge_list);
248 /* Allocate a worklist array/queue. Entries are only added to the
249 list if they were not already on the list. So the size is
250 bounded by the number of basic blocks. */
251 qin = qout = worklist
252 = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
254 /* Initialize a mapping from each edge to its index. */
255 for (i = 0; i < num_edges; i++)
256 INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
258 /* We want a maximal solution, so initially consider LATER true for
259 all edges. This allows propagation through a loop since the incoming
260 loop edge will have LATER set, so if all the other incoming edges
261 to the loop are set, then LATERIN will be set for the head of the
262 loop.
264 If the optimistic setting of LATER on that edge was incorrect (for
265 example the expression is ANTLOC in a block within the loop) then
266 this algorithm will detect it when we process the block at the head
267 of the optimistic edge. That will requeue the affected blocks. */
268 bitmap_vector_ones (later, num_edges);
270 /* Note that even though we want an optimistic setting of LATER, we
271 do not want to be overly optimistic. Consider an outgoing edge from
272 the entry block. That edge should always have a LATER value the
273 same as EARLIEST for that edge. */
274 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
275 bitmap_copy (later[(size_t) e->aux], earliest[(size_t) e->aux]);
277 /* Add all the blocks to the worklist. This prevents an early exit from
278 the loop given our optimistic initialization of LATER above. */
279 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
280 int postorder_num = inverted_post_order_compute (postorder);
281 for (int i = 0; i < postorder_num; ++i)
283 bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
284 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
285 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
286 continue;
287 *qin++ = bb;
288 bb->aux = bb;
290 free (postorder);
292 /* Note that we do not use the last allocated element for our queue,
293 as EXIT_BLOCK is never inserted into it. */
294 qin = worklist;
295 qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
296 qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
298 /* Iterate until the worklist is empty. */
299 while (qlen)
301 /* Take the first entry off the worklist. */
302 bb = *qout++;
303 bb->aux = NULL;
304 qlen--;
305 if (qout >= qend)
306 qout = worklist;
308 /* Compute the intersection of LATERIN for each incoming edge to B. */
309 bitmap_ones (laterin[bb->index]);
310 FOR_EACH_EDGE (e, ei, bb->preds)
311 bitmap_and (laterin[bb->index], laterin[bb->index],
312 later[(size_t)e->aux]);
314 /* Calculate LATER for all outgoing edges. */
315 FOR_EACH_EDGE (e, ei, bb->succs)
316 if (bitmap_ior_and_compl (later[(size_t) e->aux],
317 earliest[(size_t) e->aux],
318 laterin[bb->index],
319 antloc[bb->index])
320 /* If LATER for an outgoing edge was changed, then we need
321 to add the target of the outgoing edge to the worklist. */
322 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest->aux == 0)
324 *qin++ = e->dest;
325 e->dest->aux = e;
326 qlen++;
327 if (qin >= qend)
328 qin = worklist;
332 /* Computation of insertion and deletion points requires computing LATERIN
333 for the EXIT block. We allocated an extra entry in the LATERIN array
334 for just this purpose. */
335 bitmap_ones (laterin[last_basic_block_for_fn (cfun)]);
336 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
337 bitmap_and (laterin[last_basic_block_for_fn (cfun)],
338 laterin[last_basic_block_for_fn (cfun)],
339 later[(size_t) e->aux]);
341 clear_aux_for_edges ();
342 free (worklist);
345 /* Compute the insertion and deletion points for edge based LCM. */
347 static void
348 compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc,
349 sbitmap *later, sbitmap *laterin, sbitmap *insert,
350 sbitmap *del)
352 int x;
353 basic_block bb;
355 FOR_EACH_BB_FN (bb, cfun)
356 bitmap_and_compl (del[bb->index], antloc[bb->index],
357 laterin[bb->index]);
359 for (x = 0; x < NUM_EDGES (edge_list); x++)
361 basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
363 if (b == EXIT_BLOCK_PTR_FOR_FN (cfun))
364 bitmap_and_compl (insert[x], later[x],
365 laterin[last_basic_block_for_fn (cfun)]);
366 else
367 bitmap_and_compl (insert[x], later[x], laterin[b->index]);
371 /* Given local properties TRANSP, ANTLOC, AVLOC, KILL return the insert and
372 delete vectors for edge based LCM and return the AVIN, AVOUT bitmap.
373 map the insert vector to what edge an expression should be inserted on. */
375 struct edge_list *
376 pre_edge_lcm_avs (int n_exprs, sbitmap *transp,
377 sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
378 sbitmap *avin, sbitmap *avout,
379 sbitmap **insert, sbitmap **del)
381 sbitmap *antin, *antout, *earliest;
382 sbitmap *later, *laterin;
383 struct edge_list *edge_list;
384 int num_edges;
386 edge_list = create_edge_list ();
387 num_edges = NUM_EDGES (edge_list);
389 #ifdef LCM_DEBUG_INFO
390 if (dump_file)
392 fprintf (dump_file, "Edge List:\n");
393 verify_edge_list (dump_file, edge_list);
394 print_edge_list (dump_file, edge_list);
395 dump_bitmap_vector (dump_file, "transp", "", transp,
396 last_basic_block_for_fn (cfun));
397 dump_bitmap_vector (dump_file, "antloc", "", antloc,
398 last_basic_block_for_fn (cfun));
399 dump_bitmap_vector (dump_file, "avloc", "", avloc,
400 last_basic_block_for_fn (cfun));
401 dump_bitmap_vector (dump_file, "kill", "", kill,
402 last_basic_block_for_fn (cfun));
404 #endif
406 /* Compute global availability. */
407 compute_available (avloc, kill, avout, avin);
409 /* Compute global anticipatability. */
410 antin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
411 antout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
412 compute_antinout_edge (antloc, transp, antin, antout);
414 #ifdef LCM_DEBUG_INFO
415 if (dump_file)
417 dump_bitmap_vector (dump_file, "antin", "", antin,
418 last_basic_block_for_fn (cfun));
419 dump_bitmap_vector (dump_file, "antout", "", antout,
420 last_basic_block_for_fn (cfun));
422 #endif
424 /* Compute earliestness. */
425 earliest = sbitmap_vector_alloc (num_edges, n_exprs);
426 compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
428 #ifdef LCM_DEBUG_INFO
429 if (dump_file)
430 dump_bitmap_vector (dump_file, "earliest", "", earliest, num_edges);
431 #endif
433 sbitmap_vector_free (antout);
434 sbitmap_vector_free (antin);
436 later = sbitmap_vector_alloc (num_edges, n_exprs);
438 /* Allocate an extra element for the exit block in the laterin vector. */
439 laterin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun) + 1,
440 n_exprs);
441 compute_laterin (edge_list, earliest, antloc, later, laterin);
443 #ifdef LCM_DEBUG_INFO
444 if (dump_file)
446 dump_bitmap_vector (dump_file, "laterin", "", laterin,
447 last_basic_block_for_fn (cfun) + 1);
448 dump_bitmap_vector (dump_file, "later", "", later, num_edges);
450 #endif
452 sbitmap_vector_free (earliest);
454 *insert = sbitmap_vector_alloc (num_edges, n_exprs);
455 *del = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
456 bitmap_vector_clear (*insert, num_edges);
457 bitmap_vector_clear (*del, last_basic_block_for_fn (cfun));
458 compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del);
460 sbitmap_vector_free (laterin);
461 sbitmap_vector_free (later);
463 #ifdef LCM_DEBUG_INFO
464 if (dump_file)
466 dump_bitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
467 dump_bitmap_vector (dump_file, "pre_delete_map", "", *del,
468 last_basic_block_for_fn (cfun));
470 #endif
472 return edge_list;
475 /* Wrapper to allocate avin/avout and call pre_edge_lcm_avs. */
477 struct edge_list *
478 pre_edge_lcm (int n_exprs, sbitmap *transp,
479 sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
480 sbitmap **insert, sbitmap **del)
482 struct edge_list *edge_list;
483 sbitmap *avin, *avout;
485 avin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
486 avout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
488 edge_list = pre_edge_lcm_avs (n_exprs, transp, avloc, antloc, kill,
489 avin, avout, insert, del);
491 sbitmap_vector_free (avout);
492 sbitmap_vector_free (avin);
494 return edge_list;
497 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
498 Return the number of passes we performed to iterate to a solution. */
500 void
501 compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
502 sbitmap *avin)
504 edge e;
505 basic_block *worklist, *qin, *qout, *qend, bb;
506 unsigned int qlen;
507 edge_iterator ei;
509 /* Allocate a worklist array/queue. Entries are only added to the
510 list if they were not already on the list. So the size is
511 bounded by the number of basic blocks. */
512 qin = qout = worklist =
513 XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
515 /* We want a maximal solution. */
516 bitmap_vector_ones (avout, last_basic_block_for_fn (cfun));
518 /* Put every block on the worklist; this is necessary because of the
519 optimistic initialization of AVOUT above. Use inverted postorder
520 to make the dataflow problem require less iterations. */
521 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
522 int postorder_num = inverted_post_order_compute (postorder);
523 for (int i = 0; i < postorder_num; ++i)
525 bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
526 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
527 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
528 continue;
529 *qin++ = bb;
530 bb->aux = bb;
532 free (postorder);
534 qin = worklist;
535 qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
536 qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
538 /* Mark blocks which are successors of the entry block so that we
539 can easily identify them below. */
540 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
541 e->dest->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun);
543 /* Iterate until the worklist is empty. */
544 while (qlen)
546 /* Take the first entry off the worklist. */
547 bb = *qout++;
548 qlen--;
550 if (qout >= qend)
551 qout = worklist;
553 /* If one of the predecessor blocks is the ENTRY block, then the
554 intersection of avouts is the null set. We can identify such blocks
555 by the special value in the AUX field in the block structure. */
556 if (bb->aux == ENTRY_BLOCK_PTR_FOR_FN (cfun))
557 /* Do not clear the aux field for blocks which are successors of the
558 ENTRY block. That way we never add then to the worklist again. */
559 bitmap_clear (avin[bb->index]);
560 else
562 /* Clear the aux field of this block so that it can be added to
563 the worklist again if necessary. */
564 bb->aux = NULL;
565 bitmap_intersection_of_preds (avin[bb->index], avout, bb);
568 if (bitmap_ior_and_compl (avout[bb->index], avloc[bb->index],
569 avin[bb->index], kill[bb->index]))
570 /* If the out state of this block changed, then we need
571 to add the successors of this block to the worklist
572 if they are not already on the worklist. */
573 FOR_EACH_EDGE (e, ei, bb->succs)
574 if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
576 *qin++ = e->dest;
577 e->dest->aux = e;
578 qlen++;
580 if (qin >= qend)
581 qin = worklist;
585 clear_aux_for_edges ();
586 clear_aux_for_blocks ();
587 free (worklist);
590 /* Compute the farthest vector for edge based lcm. */
592 static void
593 compute_farthest (struct edge_list *edge_list, int n_exprs,
594 sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin,
595 sbitmap *kill, sbitmap *farthest)
597 sbitmap difference, temp_bitmap;
598 int x, num_edges;
599 basic_block pred, succ;
601 num_edges = NUM_EDGES (edge_list);
603 difference = sbitmap_alloc (n_exprs);
604 temp_bitmap = sbitmap_alloc (n_exprs);
606 for (x = 0; x < num_edges; x++)
608 pred = INDEX_EDGE_PRED_BB (edge_list, x);
609 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
610 if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun))
611 bitmap_copy (farthest[x], st_avout[pred->index]);
612 else
614 if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
615 bitmap_clear (farthest[x]);
616 else
618 bitmap_and_compl (difference, st_avout[pred->index],
619 st_antin[succ->index]);
620 bitmap_not (temp_bitmap, st_avin[succ->index]);
621 bitmap_and_or (farthest[x], difference,
622 kill[succ->index], temp_bitmap);
627 sbitmap_free (temp_bitmap);
628 sbitmap_free (difference);
631 /* Compute nearer and nearerout vectors for edge based lcm.
633 This is the mirror of compute_laterin, additional comments on the
634 implementation can be found before compute_laterin. */
636 static void
637 compute_nearerout (struct edge_list *edge_list, sbitmap *farthest,
638 sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout)
640 int num_edges, i;
641 edge e;
642 basic_block *worklist, *tos, bb;
643 edge_iterator ei;
645 num_edges = NUM_EDGES (edge_list);
647 /* Allocate a worklist array/queue. Entries are only added to the
648 list if they were not already on the list. So the size is
649 bounded by the number of basic blocks. */
650 tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1);
652 /* Initialize NEARER for each edge and build a mapping from an edge to
653 its index. */
654 for (i = 0; i < num_edges; i++)
655 INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
657 /* We want a maximal solution. */
658 bitmap_vector_ones (nearer, num_edges);
660 /* Note that even though we want an optimistic setting of NEARER, we
661 do not want to be overly optimistic. Consider an incoming edge to
662 the exit block. That edge should always have a NEARER value the
663 same as FARTHEST for that edge. */
664 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
665 bitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]);
667 /* Add all the blocks to the worklist. This prevents an early exit
668 from the loop given our optimistic initialization of NEARER. */
669 FOR_EACH_BB_FN (bb, cfun)
671 *tos++ = bb;
672 bb->aux = bb;
675 /* Iterate until the worklist is empty. */
676 while (tos != worklist)
678 /* Take the first entry off the worklist. */
679 bb = *--tos;
680 bb->aux = NULL;
682 /* Compute the intersection of NEARER for each outgoing edge from B. */
683 bitmap_ones (nearerout[bb->index]);
684 FOR_EACH_EDGE (e, ei, bb->succs)
685 bitmap_and (nearerout[bb->index], nearerout[bb->index],
686 nearer[(size_t) e->aux]);
688 /* Calculate NEARER for all incoming edges. */
689 FOR_EACH_EDGE (e, ei, bb->preds)
690 if (bitmap_ior_and_compl (nearer[(size_t) e->aux],
691 farthest[(size_t) e->aux],
692 nearerout[e->dest->index],
693 st_avloc[e->dest->index])
694 /* If NEARER for an incoming edge was changed, then we need
695 to add the source of the incoming edge to the worklist. */
696 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) && e->src->aux == 0)
698 *tos++ = e->src;
699 e->src->aux = e;
703 /* Computation of insertion and deletion points requires computing NEAREROUT
704 for the ENTRY block. We allocated an extra entry in the NEAREROUT array
705 for just this purpose. */
706 bitmap_ones (nearerout[last_basic_block_for_fn (cfun)]);
707 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
708 bitmap_and (nearerout[last_basic_block_for_fn (cfun)],
709 nearerout[last_basic_block_for_fn (cfun)],
710 nearer[(size_t) e->aux]);
712 clear_aux_for_edges ();
713 free (tos);
716 /* Compute the insertion and deletion points for edge based LCM. */
718 static void
719 compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc,
720 sbitmap *nearer, sbitmap *nearerout,
721 sbitmap *insert, sbitmap *del)
723 int x;
724 basic_block bb;
726 FOR_EACH_BB_FN (bb, cfun)
727 bitmap_and_compl (del[bb->index], st_avloc[bb->index],
728 nearerout[bb->index]);
730 for (x = 0; x < NUM_EDGES (edge_list); x++)
732 basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
733 if (b == ENTRY_BLOCK_PTR_FOR_FN (cfun))
734 bitmap_and_compl (insert[x], nearer[x],
735 nearerout[last_basic_block_for_fn (cfun)]);
736 else
737 bitmap_and_compl (insert[x], nearer[x], nearerout[b->index]);
741 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
742 insert and delete vectors for edge based reverse LCM. Returns an
743 edgelist which is used to map the insert vector to what edge
744 an expression should be inserted on. */
746 struct edge_list *
747 pre_edge_rev_lcm (int n_exprs, sbitmap *transp,
748 sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill,
749 sbitmap **insert, sbitmap **del)
751 sbitmap *st_antin, *st_antout;
752 sbitmap *st_avout, *st_avin, *farthest;
753 sbitmap *nearer, *nearerout;
754 struct edge_list *edge_list;
755 int num_edges;
757 edge_list = create_edge_list ();
758 num_edges = NUM_EDGES (edge_list);
760 st_antin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
761 st_antout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
762 bitmap_vector_clear (st_antin, last_basic_block_for_fn (cfun));
763 bitmap_vector_clear (st_antout, last_basic_block_for_fn (cfun));
764 compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
766 /* Compute global anticipatability. */
767 st_avout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
768 st_avin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
769 compute_available (st_avloc, kill, st_avout, st_avin);
771 #ifdef LCM_DEBUG_INFO
772 if (dump_file)
774 fprintf (dump_file, "Edge List:\n");
775 verify_edge_list (dump_file, edge_list);
776 print_edge_list (dump_file, edge_list);
777 dump_bitmap_vector (dump_file, "transp", "", transp,
778 last_basic_block_for_fn (cfun));
779 dump_bitmap_vector (dump_file, "st_avloc", "", st_avloc,
780 last_basic_block_for_fn (cfun));
781 dump_bitmap_vector (dump_file, "st_antloc", "", st_antloc,
782 last_basic_block_for_fn (cfun));
783 dump_bitmap_vector (dump_file, "st_antin", "", st_antin,
784 last_basic_block_for_fn (cfun));
785 dump_bitmap_vector (dump_file, "st_antout", "", st_antout,
786 last_basic_block_for_fn (cfun));
787 dump_bitmap_vector (dump_file, "st_kill", "", kill,
788 last_basic_block_for_fn (cfun));
790 #endif
792 #ifdef LCM_DEBUG_INFO
793 if (dump_file)
795 dump_bitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block_for_fn (cfun));
796 dump_bitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block_for_fn (cfun));
798 #endif
800 /* Compute farthestness. */
801 farthest = sbitmap_vector_alloc (num_edges, n_exprs);
802 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
803 kill, farthest);
805 #ifdef LCM_DEBUG_INFO
806 if (dump_file)
807 dump_bitmap_vector (dump_file, "farthest", "", farthest, num_edges);
808 #endif
810 sbitmap_vector_free (st_antin);
811 sbitmap_vector_free (st_antout);
813 sbitmap_vector_free (st_avin);
814 sbitmap_vector_free (st_avout);
816 nearer = sbitmap_vector_alloc (num_edges, n_exprs);
818 /* Allocate an extra element for the entry block. */
819 nearerout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun) + 1,
820 n_exprs);
821 compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
823 #ifdef LCM_DEBUG_INFO
824 if (dump_file)
826 dump_bitmap_vector (dump_file, "nearerout", "", nearerout,
827 last_basic_block_for_fn (cfun) + 1);
828 dump_bitmap_vector (dump_file, "nearer", "", nearer, num_edges);
830 #endif
832 sbitmap_vector_free (farthest);
834 *insert = sbitmap_vector_alloc (num_edges, n_exprs);
835 *del = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
836 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
837 *insert, *del);
839 sbitmap_vector_free (nearerout);
840 sbitmap_vector_free (nearer);
842 #ifdef LCM_DEBUG_INFO
843 if (dump_file)
845 dump_bitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
846 dump_bitmap_vector (dump_file, "pre_delete_map", "", *del,
847 last_basic_block_for_fn (cfun));
849 #endif
850 return edge_list;