Daily bump.
[official-gcc.git] / gcc / lcm.c
blobedc86b5700999a703e4d06ed1ffd169604cbeb25
1 /* Generic partial redundancy elimination with lazy code motion support.
2 Copyright (C) 1998-2017 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 int x, num_edges;
174 basic_block pred, succ;
176 num_edges = NUM_EDGES (edge_list);
178 auto_sbitmap difference (n_exprs), temp_bitmap (n_exprs);
179 for (x = 0; x < num_edges; x++)
181 pred = INDEX_EDGE_PRED_BB (edge_list, x);
182 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
183 if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
184 bitmap_copy (earliest[x], antin[succ->index]);
185 else
187 if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun))
188 bitmap_clear (earliest[x]);
189 else
191 bitmap_and_compl (difference, antin[succ->index],
192 avout[pred->index]);
193 bitmap_not (temp_bitmap, antout[pred->index]);
194 bitmap_and_or (earliest[x], difference,
195 kill[pred->index], temp_bitmap);
201 /* later(p,s) is dependent on the calculation of laterin(p).
202 laterin(p) is dependent on the calculation of later(p2,p).
204 laterin(ENTRY) is defined as all 0's
205 later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY)
206 laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)).
208 If we progress in this manner, starting with all basic blocks
209 in the work list, anytime we change later(bb), we need to add
210 succs(bb) to the worklist if they are not already on the worklist.
212 Boundary conditions:
214 We prime the worklist all the normal basic blocks. The ENTRY block can
215 never be added to the worklist since it is never the successor of any
216 block. We explicitly prevent the EXIT block from being added to the
217 worklist.
219 We optimistically initialize LATER. That is the only time this routine
220 will compute LATER for an edge out of the entry block since the entry
221 block is never on the worklist. Thus, LATERIN is neither used nor
222 computed for the ENTRY block.
224 Since the EXIT block is never added to the worklist, we will neither
225 use nor compute LATERIN for the exit block. Edges which reach the
226 EXIT block are handled in the normal fashion inside the loop. However,
227 the insertion/deletion computation needs LATERIN(EXIT), so we have
228 to compute it. */
230 static void
231 compute_laterin (struct edge_list *edge_list, sbitmap *earliest,
232 sbitmap *antloc, sbitmap *later, sbitmap *laterin)
234 int num_edges, i;
235 edge e;
236 basic_block *worklist, *qin, *qout, *qend, bb;
237 unsigned int qlen;
238 edge_iterator ei;
240 num_edges = NUM_EDGES (edge_list);
242 /* Allocate a worklist array/queue. Entries are only added to the
243 list if they were not already on the list. So the size is
244 bounded by the number of basic blocks. */
245 qin = qout = worklist
246 = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
248 /* Initialize a mapping from each edge to its index. */
249 for (i = 0; i < num_edges; i++)
250 INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
252 /* We want a maximal solution, so initially consider LATER true for
253 all edges. This allows propagation through a loop since the incoming
254 loop edge will have LATER set, so if all the other incoming edges
255 to the loop are set, then LATERIN will be set for the head of the
256 loop.
258 If the optimistic setting of LATER on that edge was incorrect (for
259 example the expression is ANTLOC in a block within the loop) then
260 this algorithm will detect it when we process the block at the head
261 of the optimistic edge. That will requeue the affected blocks. */
262 bitmap_vector_ones (later, num_edges);
264 /* Note that even though we want an optimistic setting of LATER, we
265 do not want to be overly optimistic. Consider an outgoing edge from
266 the entry block. That edge should always have a LATER value the
267 same as EARLIEST for that edge. */
268 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
269 bitmap_copy (later[(size_t) e->aux], earliest[(size_t) e->aux]);
271 /* Add all the blocks to the worklist. This prevents an early exit from
272 the loop given our optimistic initialization of LATER above. */
273 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
274 int postorder_num = inverted_post_order_compute (postorder);
275 for (int i = 0; i < postorder_num; ++i)
277 bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
278 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
279 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
280 continue;
281 *qin++ = bb;
282 bb->aux = bb;
284 free (postorder);
286 /* Note that we do not use the last allocated element for our queue,
287 as EXIT_BLOCK is never inserted into it. */
288 qin = worklist;
289 qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
290 qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
292 /* Iterate until the worklist is empty. */
293 while (qlen)
295 /* Take the first entry off the worklist. */
296 bb = *qout++;
297 bb->aux = NULL;
298 qlen--;
299 if (qout >= qend)
300 qout = worklist;
302 /* Compute the intersection of LATERIN for each incoming edge to B. */
303 bitmap_ones (laterin[bb->index]);
304 FOR_EACH_EDGE (e, ei, bb->preds)
305 bitmap_and (laterin[bb->index], laterin[bb->index],
306 later[(size_t)e->aux]);
308 /* Calculate LATER for all outgoing edges. */
309 FOR_EACH_EDGE (e, ei, bb->succs)
310 if (bitmap_ior_and_compl (later[(size_t) e->aux],
311 earliest[(size_t) e->aux],
312 laterin[bb->index],
313 antloc[bb->index])
314 /* If LATER for an outgoing edge was changed, then we need
315 to add the target of the outgoing edge to the worklist. */
316 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest->aux == 0)
318 *qin++ = e->dest;
319 e->dest->aux = e;
320 qlen++;
321 if (qin >= qend)
322 qin = worklist;
326 /* Computation of insertion and deletion points requires computing LATERIN
327 for the EXIT block. We allocated an extra entry in the LATERIN array
328 for just this purpose. */
329 bitmap_ones (laterin[last_basic_block_for_fn (cfun)]);
330 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
331 bitmap_and (laterin[last_basic_block_for_fn (cfun)],
332 laterin[last_basic_block_for_fn (cfun)],
333 later[(size_t) e->aux]);
335 clear_aux_for_edges ();
336 free (worklist);
339 /* Compute the insertion and deletion points for edge based LCM. */
341 static void
342 compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc,
343 sbitmap *later, sbitmap *laterin, sbitmap *insert,
344 sbitmap *del)
346 int x;
347 basic_block bb;
349 FOR_EACH_BB_FN (bb, cfun)
350 bitmap_and_compl (del[bb->index], antloc[bb->index],
351 laterin[bb->index]);
353 for (x = 0; x < NUM_EDGES (edge_list); x++)
355 basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
357 if (b == EXIT_BLOCK_PTR_FOR_FN (cfun))
358 bitmap_and_compl (insert[x], later[x],
359 laterin[last_basic_block_for_fn (cfun)]);
360 else
361 bitmap_and_compl (insert[x], later[x], laterin[b->index]);
365 /* Given local properties TRANSP, ANTLOC, AVLOC, KILL return the insert and
366 delete vectors for edge based LCM and return the AVIN, AVOUT bitmap.
367 map the insert vector to what edge an expression should be inserted on. */
369 struct edge_list *
370 pre_edge_lcm_avs (int n_exprs, sbitmap *transp,
371 sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
372 sbitmap *avin, sbitmap *avout,
373 sbitmap **insert, sbitmap **del)
375 sbitmap *antin, *antout, *earliest;
376 sbitmap *later, *laterin;
377 struct edge_list *edge_list;
378 int num_edges;
380 edge_list = create_edge_list ();
381 num_edges = NUM_EDGES (edge_list);
383 #ifdef LCM_DEBUG_INFO
384 if (dump_file)
386 fprintf (dump_file, "Edge List:\n");
387 verify_edge_list (dump_file, edge_list);
388 print_edge_list (dump_file, edge_list);
389 dump_bitmap_vector (dump_file, "transp", "", transp,
390 last_basic_block_for_fn (cfun));
391 dump_bitmap_vector (dump_file, "antloc", "", antloc,
392 last_basic_block_for_fn (cfun));
393 dump_bitmap_vector (dump_file, "avloc", "", avloc,
394 last_basic_block_for_fn (cfun));
395 dump_bitmap_vector (dump_file, "kill", "", kill,
396 last_basic_block_for_fn (cfun));
398 #endif
400 /* Compute global availability. */
401 compute_available (avloc, kill, avout, avin);
403 /* Compute global anticipatability. */
404 antin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
405 antout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
406 compute_antinout_edge (antloc, transp, antin, antout);
408 #ifdef LCM_DEBUG_INFO
409 if (dump_file)
411 dump_bitmap_vector (dump_file, "antin", "", antin,
412 last_basic_block_for_fn (cfun));
413 dump_bitmap_vector (dump_file, "antout", "", antout,
414 last_basic_block_for_fn (cfun));
416 #endif
418 /* Compute earliestness. */
419 earliest = sbitmap_vector_alloc (num_edges, n_exprs);
420 compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
422 #ifdef LCM_DEBUG_INFO
423 if (dump_file)
424 dump_bitmap_vector (dump_file, "earliest", "", earliest, num_edges);
425 #endif
427 sbitmap_vector_free (antout);
428 sbitmap_vector_free (antin);
430 later = sbitmap_vector_alloc (num_edges, n_exprs);
432 /* Allocate an extra element for the exit block in the laterin vector. */
433 laterin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun) + 1,
434 n_exprs);
435 compute_laterin (edge_list, earliest, antloc, later, laterin);
437 #ifdef LCM_DEBUG_INFO
438 if (dump_file)
440 dump_bitmap_vector (dump_file, "laterin", "", laterin,
441 last_basic_block_for_fn (cfun) + 1);
442 dump_bitmap_vector (dump_file, "later", "", later, num_edges);
444 #endif
446 sbitmap_vector_free (earliest);
448 *insert = sbitmap_vector_alloc (num_edges, n_exprs);
449 *del = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
450 bitmap_vector_clear (*insert, num_edges);
451 bitmap_vector_clear (*del, last_basic_block_for_fn (cfun));
452 compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del);
454 sbitmap_vector_free (laterin);
455 sbitmap_vector_free (later);
457 #ifdef LCM_DEBUG_INFO
458 if (dump_file)
460 dump_bitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
461 dump_bitmap_vector (dump_file, "pre_delete_map", "", *del,
462 last_basic_block_for_fn (cfun));
464 #endif
466 return edge_list;
469 /* Wrapper to allocate avin/avout and call pre_edge_lcm_avs. */
471 struct edge_list *
472 pre_edge_lcm (int n_exprs, sbitmap *transp,
473 sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
474 sbitmap **insert, sbitmap **del)
476 struct edge_list *edge_list;
477 sbitmap *avin, *avout;
479 avin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
480 avout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
482 edge_list = pre_edge_lcm_avs (n_exprs, transp, avloc, antloc, kill,
483 avin, avout, insert, del);
485 sbitmap_vector_free (avout);
486 sbitmap_vector_free (avin);
488 return edge_list;
491 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
492 Return the number of passes we performed to iterate to a solution. */
494 void
495 compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
496 sbitmap *avin)
498 edge e;
499 basic_block *worklist, *qin, *qout, *qend, bb;
500 unsigned int qlen;
501 edge_iterator ei;
503 /* Allocate a worklist array/queue. Entries are only added to the
504 list if they were not already on the list. So the size is
505 bounded by the number of basic blocks. */
506 qin = qout = worklist =
507 XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
509 /* We want a maximal solution. */
510 bitmap_vector_ones (avout, last_basic_block_for_fn (cfun));
512 /* Put every block on the worklist; this is necessary because of the
513 optimistic initialization of AVOUT above. Use inverted postorder
514 to make the dataflow problem require less iterations. */
515 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
516 int postorder_num = inverted_post_order_compute (postorder);
517 for (int i = 0; i < postorder_num; ++i)
519 bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
520 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
521 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
522 continue;
523 *qin++ = bb;
524 bb->aux = bb;
526 free (postorder);
528 qin = worklist;
529 qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
530 qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
532 /* Mark blocks which are successors of the entry block so that we
533 can easily identify them below. */
534 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
535 e->dest->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun);
537 /* Iterate until the worklist is empty. */
538 while (qlen)
540 /* Take the first entry off the worklist. */
541 bb = *qout++;
542 qlen--;
544 if (qout >= qend)
545 qout = worklist;
547 /* If one of the predecessor blocks is the ENTRY block, then the
548 intersection of avouts is the null set. We can identify such blocks
549 by the special value in the AUX field in the block structure. */
550 if (bb->aux == ENTRY_BLOCK_PTR_FOR_FN (cfun))
551 /* Do not clear the aux field for blocks which are successors of the
552 ENTRY block. That way we never add then to the worklist again. */
553 bitmap_clear (avin[bb->index]);
554 else
556 /* Clear the aux field of this block so that it can be added to
557 the worklist again if necessary. */
558 bb->aux = NULL;
559 bitmap_intersection_of_preds (avin[bb->index], avout, bb);
562 if (bitmap_ior_and_compl (avout[bb->index], avloc[bb->index],
563 avin[bb->index], kill[bb->index]))
564 /* If the out state of this block changed, then we need
565 to add the successors of this block to the worklist
566 if they are not already on the worklist. */
567 FOR_EACH_EDGE (e, ei, bb->succs)
568 if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
570 *qin++ = e->dest;
571 e->dest->aux = e;
572 qlen++;
574 if (qin >= qend)
575 qin = worklist;
579 clear_aux_for_edges ();
580 clear_aux_for_blocks ();
581 free (worklist);
584 /* Compute the farthest vector for edge based lcm. */
586 static void
587 compute_farthest (struct edge_list *edge_list, int n_exprs,
588 sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin,
589 sbitmap *kill, sbitmap *farthest)
591 int x, num_edges;
592 basic_block pred, succ;
594 num_edges = NUM_EDGES (edge_list);
596 auto_sbitmap difference (n_exprs), temp_bitmap (n_exprs);
597 for (x = 0; x < num_edges; x++)
599 pred = INDEX_EDGE_PRED_BB (edge_list, x);
600 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
601 if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun))
602 bitmap_copy (farthest[x], st_avout[pred->index]);
603 else
605 if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
606 bitmap_clear (farthest[x]);
607 else
609 bitmap_and_compl (difference, st_avout[pred->index],
610 st_antin[succ->index]);
611 bitmap_not (temp_bitmap, st_avin[succ->index]);
612 bitmap_and_or (farthest[x], difference,
613 kill[succ->index], temp_bitmap);
619 /* Compute nearer and nearerout vectors for edge based lcm.
621 This is the mirror of compute_laterin, additional comments on the
622 implementation can be found before compute_laterin. */
624 static void
625 compute_nearerout (struct edge_list *edge_list, sbitmap *farthest,
626 sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout)
628 int num_edges, i;
629 edge e;
630 basic_block *worklist, *tos, bb;
631 edge_iterator ei;
633 num_edges = NUM_EDGES (edge_list);
635 /* Allocate a worklist array/queue. Entries are only added to the
636 list if they were not already on the list. So the size is
637 bounded by the number of basic blocks. */
638 tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1);
640 /* Initialize NEARER for each edge and build a mapping from an edge to
641 its index. */
642 for (i = 0; i < num_edges; i++)
643 INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
645 /* We want a maximal solution. */
646 bitmap_vector_ones (nearer, num_edges);
648 /* Note that even though we want an optimistic setting of NEARER, we
649 do not want to be overly optimistic. Consider an incoming edge to
650 the exit block. That edge should always have a NEARER value the
651 same as FARTHEST for that edge. */
652 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
653 bitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]);
655 /* Add all the blocks to the worklist. This prevents an early exit
656 from the loop given our optimistic initialization of NEARER. */
657 FOR_EACH_BB_FN (bb, cfun)
659 *tos++ = bb;
660 bb->aux = bb;
663 /* Iterate until the worklist is empty. */
664 while (tos != worklist)
666 /* Take the first entry off the worklist. */
667 bb = *--tos;
668 bb->aux = NULL;
670 /* Compute the intersection of NEARER for each outgoing edge from B. */
671 bitmap_ones (nearerout[bb->index]);
672 FOR_EACH_EDGE (e, ei, bb->succs)
673 bitmap_and (nearerout[bb->index], nearerout[bb->index],
674 nearer[(size_t) e->aux]);
676 /* Calculate NEARER for all incoming edges. */
677 FOR_EACH_EDGE (e, ei, bb->preds)
678 if (bitmap_ior_and_compl (nearer[(size_t) e->aux],
679 farthest[(size_t) e->aux],
680 nearerout[e->dest->index],
681 st_avloc[e->dest->index])
682 /* If NEARER for an incoming edge was changed, then we need
683 to add the source of the incoming edge to the worklist. */
684 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) && e->src->aux == 0)
686 *tos++ = e->src;
687 e->src->aux = e;
691 /* Computation of insertion and deletion points requires computing NEAREROUT
692 for the ENTRY block. We allocated an extra entry in the NEAREROUT array
693 for just this purpose. */
694 bitmap_ones (nearerout[last_basic_block_for_fn (cfun)]);
695 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
696 bitmap_and (nearerout[last_basic_block_for_fn (cfun)],
697 nearerout[last_basic_block_for_fn (cfun)],
698 nearer[(size_t) e->aux]);
700 clear_aux_for_edges ();
701 free (tos);
704 /* Compute the insertion and deletion points for edge based LCM. */
706 static void
707 compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc,
708 sbitmap *nearer, sbitmap *nearerout,
709 sbitmap *insert, sbitmap *del)
711 int x;
712 basic_block bb;
714 FOR_EACH_BB_FN (bb, cfun)
715 bitmap_and_compl (del[bb->index], st_avloc[bb->index],
716 nearerout[bb->index]);
718 for (x = 0; x < NUM_EDGES (edge_list); x++)
720 basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
721 if (b == ENTRY_BLOCK_PTR_FOR_FN (cfun))
722 bitmap_and_compl (insert[x], nearer[x],
723 nearerout[last_basic_block_for_fn (cfun)]);
724 else
725 bitmap_and_compl (insert[x], nearer[x], nearerout[b->index]);
729 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
730 insert and delete vectors for edge based reverse LCM. Returns an
731 edgelist which is used to map the insert vector to what edge
732 an expression should be inserted on. */
734 struct edge_list *
735 pre_edge_rev_lcm (int n_exprs, sbitmap *transp,
736 sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill,
737 sbitmap **insert, sbitmap **del)
739 sbitmap *st_antin, *st_antout;
740 sbitmap *st_avout, *st_avin, *farthest;
741 sbitmap *nearer, *nearerout;
742 struct edge_list *edge_list;
743 int num_edges;
745 edge_list = create_edge_list ();
746 num_edges = NUM_EDGES (edge_list);
748 st_antin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
749 st_antout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
750 bitmap_vector_clear (st_antin, last_basic_block_for_fn (cfun));
751 bitmap_vector_clear (st_antout, last_basic_block_for_fn (cfun));
752 compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
754 /* Compute global anticipatability. */
755 st_avout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
756 st_avin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
757 compute_available (st_avloc, kill, st_avout, st_avin);
759 #ifdef LCM_DEBUG_INFO
760 if (dump_file)
762 fprintf (dump_file, "Edge List:\n");
763 verify_edge_list (dump_file, edge_list);
764 print_edge_list (dump_file, edge_list);
765 dump_bitmap_vector (dump_file, "transp", "", transp,
766 last_basic_block_for_fn (cfun));
767 dump_bitmap_vector (dump_file, "st_avloc", "", st_avloc,
768 last_basic_block_for_fn (cfun));
769 dump_bitmap_vector (dump_file, "st_antloc", "", st_antloc,
770 last_basic_block_for_fn (cfun));
771 dump_bitmap_vector (dump_file, "st_antin", "", st_antin,
772 last_basic_block_for_fn (cfun));
773 dump_bitmap_vector (dump_file, "st_antout", "", st_antout,
774 last_basic_block_for_fn (cfun));
775 dump_bitmap_vector (dump_file, "st_kill", "", kill,
776 last_basic_block_for_fn (cfun));
778 #endif
780 #ifdef LCM_DEBUG_INFO
781 if (dump_file)
783 dump_bitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block_for_fn (cfun));
784 dump_bitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block_for_fn (cfun));
786 #endif
788 /* Compute farthestness. */
789 farthest = sbitmap_vector_alloc (num_edges, n_exprs);
790 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
791 kill, farthest);
793 #ifdef LCM_DEBUG_INFO
794 if (dump_file)
795 dump_bitmap_vector (dump_file, "farthest", "", farthest, num_edges);
796 #endif
798 sbitmap_vector_free (st_antin);
799 sbitmap_vector_free (st_antout);
801 sbitmap_vector_free (st_avin);
802 sbitmap_vector_free (st_avout);
804 nearer = sbitmap_vector_alloc (num_edges, n_exprs);
806 /* Allocate an extra element for the entry block. */
807 nearerout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun) + 1,
808 n_exprs);
809 compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
811 #ifdef LCM_DEBUG_INFO
812 if (dump_file)
814 dump_bitmap_vector (dump_file, "nearerout", "", nearerout,
815 last_basic_block_for_fn (cfun) + 1);
816 dump_bitmap_vector (dump_file, "nearer", "", nearer, num_edges);
818 #endif
820 sbitmap_vector_free (farthest);
822 *insert = sbitmap_vector_alloc (num_edges, n_exprs);
823 *del = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
824 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
825 *insert, *del);
827 sbitmap_vector_free (nearerout);
828 sbitmap_vector_free (nearer);
830 #ifdef LCM_DEBUG_INFO
831 if (dump_file)
833 dump_bitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
834 dump_bitmap_vector (dump_file, "pre_delete_map", "", *del,
835 last_basic_block_for_fn (cfun));
837 #endif
838 return edge_list;