1/* Generic partial redundancy elimination with lazy code motion support.
2 Copyright (C) 1998-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
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:
23
24 * Traditional partial redundancy elimination.
25
26 * Placement of caller/caller register save/restores.
27
28 * Load/store motion.
29
30 * Copy motion.
31
32 * Conversion of flat register files to a stacked register
33 model.
34
35 * Dead load/store elimination.
36
37 These routines accept as input:
38
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.
43
44 * Bitmaps of local properties (computed, transparent and
45 anticipatable expressions).
46
47 The output of these routines is bitmap of redundant computations
48 and a bitmap of optimal placement points. */
49
50
51#include "config.h"
52#include "system.h"
53#include "coretypes.h"
54#include "backend.h"
55#include "cfganal.h"
56#include "lcm.h"
57
58/* Edge based LCM routines. */
59static void compute_antinout_edge (sbitmap *, sbitmap *, sbitmap *, sbitmap *);
60static void compute_earliest (struct edge_list *, int, sbitmap *, sbitmap *,
61 sbitmap *, sbitmap *, sbitmap *);
62static void compute_laterin (struct edge_list *, sbitmap *, sbitmap *,
63 sbitmap *, sbitmap *);
64static void compute_insert_delete (struct edge_list *edge_list, sbitmap *,
65 sbitmap *, sbitmap *, sbitmap *, sbitmap *);
66
67/* Edge based LCM routines on a reverse flowgraph. */
68static void compute_farthest (struct edge_list *, int, sbitmap *, sbitmap *,
69 sbitmap*, sbitmap *, sbitmap *);
70static void compute_nearerout (struct edge_list *, sbitmap *, sbitmap *,
71 sbitmap *, sbitmap *);
72static void compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *,
73 sbitmap *, sbitmap *, sbitmap *,
74 sbitmap *);
75
76/* Edge based lcm routines. */
77
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. */
81
82static void
83compute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin,
84 sbitmap *antout)
85{
86 basic_block bb;
87 edge e;
88 basic_block *worklist, *qin, *qout, *qend;
89 unsigned int qlen;
90 edge_iterator ei;
91
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));
96
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));
100
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)
106 {
107 bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
108 *qin++ = bb;
109 bb->aux = bb;
110 }
111 free (postorder);
112
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;
116
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);
121
122 /* Iterate until the worklist is empty. */
123 while (qlen)
124 {
125 /* Take the first entry off the worklist. */
126 bb = *qout++;
127 qlen--;
128
129 if (qout >= qend)
130 qout = worklist;
131
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
138 {
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);
143 }
144
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))
152 {
153 *qin++ = e->src;
154 e->src->aux = e;
155 qlen++;
156 if (qin >= qend)
157 qin = worklist;
158 }
159 }
160
161 clear_aux_for_edges ();
162 clear_aux_for_blocks ();
163 free (worklist);
164}
165
166/* Compute the earliest vector for edge based lcm. */
167
168static void
169compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin,
170 sbitmap *antout, sbitmap *avout, sbitmap *kill,
171 sbitmap *earliest)
172{
173 int x, num_edges;
174 basic_block pred, succ;
175
176 num_edges = NUM_EDGES (edge_list);
177
178 auto_sbitmap difference (n_exprs), temp_bitmap (n_exprs);
179 for (x = 0; x < num_edges; x++)
180 {
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
186 {
187 if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun))
188 bitmap_clear (earliest[x]);
189 else
190 {
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);
196 }
197 }
198 }
199}
200
201/* later(p,s) is dependent on the calculation of laterin(p).
202 laterin(p) is dependent on the calculation of later(p2,p).
203
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)).
207
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.
211
212 Boundary conditions:
213
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.
218
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.
223
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. */
229
230static void
231compute_laterin (struct edge_list *edge_list, sbitmap *earliest,
232 sbitmap *antloc, sbitmap *later, sbitmap *laterin)
233{
234 int num_edges, i;
235 edge e;
236 basic_block *worklist, *qin, *qout, *qend, bb;
237 unsigned int qlen;
238 edge_iterator ei;
239
240 num_edges = NUM_EDGES (edge_list);
241
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));
247
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;
251
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.
257
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);
263
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]);
270
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 auto_vec<int, 20> postorder;
274 inverted_post_order_compute (&postorder);
275 for (unsigned int i = 0; i < postorder.length (); ++i)
276 {
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;
283 }
284
285 /* Note that we do not use the last allocated element for our queue,
286 as EXIT_BLOCK is never inserted into it. */
287 qin = worklist;
288 qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
289 qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
290
291 /* Iterate until the worklist is empty. */
292 while (qlen)
293 {
294 /* Take the first entry off the worklist. */
295 bb = *qout++;
296 bb->aux = NULL;
297 qlen--;
298 if (qout >= qend)
299 qout = worklist;
300
301 /* Compute the intersection of LATERIN for each incoming edge to B. */
302 bitmap_ones (laterin[bb->index]);
303 FOR_EACH_EDGE (e, ei, bb->preds)
304 bitmap_and (laterin[bb->index], laterin[bb->index],
305 later[(size_t)e->aux]);
306
307 /* Calculate LATER for all outgoing edges. */
308 FOR_EACH_EDGE (e, ei, bb->succs)
309 if (bitmap_ior_and_compl (later[(size_t) e->aux],
310 earliest[(size_t) e->aux],
311 laterin[bb->index],
312 antloc[bb->index])
313 /* If LATER for an outgoing edge was changed, then we need
314 to add the target of the outgoing edge to the worklist. */
315 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest->aux == 0)
316 {
317 *qin++ = e->dest;
318 e->dest->aux = e;
319 qlen++;
320 if (qin >= qend)
321 qin = worklist;
322 }
323 }
324
325 /* Computation of insertion and deletion points requires computing LATERIN
326 for the EXIT block. We allocated an extra entry in the LATERIN array
327 for just this purpose. */
328 bitmap_ones (laterin[last_basic_block_for_fn (cfun)]);
329 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
330 bitmap_and (laterin[last_basic_block_for_fn (cfun)],
331 laterin[last_basic_block_for_fn (cfun)],
332 later[(size_t) e->aux]);
333
334 clear_aux_for_edges ();
335 free (worklist);
336}
337
338/* Compute the insertion and deletion points for edge based LCM. */
339
340static void
341compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc,
342 sbitmap *later, sbitmap *laterin, sbitmap *insert,
343 sbitmap *del)
344{
345 int x;
346 basic_block bb;
347
348 FOR_EACH_BB_FN (bb, cfun)
349 bitmap_and_compl (del[bb->index], antloc[bb->index],
350 laterin[bb->index]);
351
352 for (x = 0; x < NUM_EDGES (edge_list); x++)
353 {
354 basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
355
356 if (b == EXIT_BLOCK_PTR_FOR_FN (cfun))
357 bitmap_and_compl (insert[x], later[x],
358 laterin[last_basic_block_for_fn (cfun)]);
359 else
360 bitmap_and_compl (insert[x], later[x], laterin[b->index]);
361 }
362}
363
364/* Given local properties TRANSP, ANTLOC, AVLOC, KILL return the insert and
365 delete vectors for edge based LCM and return the AVIN, AVOUT bitmap.
366 map the insert vector to what edge an expression should be inserted on. */
367
368struct edge_list *
369pre_edge_lcm_avs (int n_exprs, sbitmap *transp,
370 sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
371 sbitmap *avin, sbitmap *avout,
372 sbitmap **insert, sbitmap **del)
373{
374 sbitmap *antin, *antout, *earliest;
375 sbitmap *later, *laterin;
376 struct edge_list *edge_list;
377 int num_edges;
378
379 edge_list = create_edge_list ();
380 num_edges = NUM_EDGES (edge_list);
381
382#ifdef LCM_DEBUG_INFO
383 if (dump_file)
384 {
385 fprintf (dump_file, "Edge List:\n");
386 verify_edge_list (dump_file, edge_list);
387 print_edge_list (dump_file, edge_list);
388 dump_bitmap_vector (dump_file, "transp", "", transp,
389 last_basic_block_for_fn (cfun));
390 dump_bitmap_vector (dump_file, "antloc", "", antloc,
391 last_basic_block_for_fn (cfun));
392 dump_bitmap_vector (dump_file, "avloc", "", avloc,
393 last_basic_block_for_fn (cfun));
394 dump_bitmap_vector (dump_file, "kill", "", kill,
395 last_basic_block_for_fn (cfun));
396 }
397#endif
398
399 /* Compute global availability. */
400 compute_available (avloc, kill, avout, avin);
401
402 /* Compute global anticipatability. */
403 antin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
404 antout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
405 compute_antinout_edge (antloc, transp, antin, antout);
406
407#ifdef LCM_DEBUG_INFO
408 if (dump_file)
409 {
410 dump_bitmap_vector (dump_file, "antin", "", antin,
411 last_basic_block_for_fn (cfun));
412 dump_bitmap_vector (dump_file, "antout", "", antout,
413 last_basic_block_for_fn (cfun));
414 }
415#endif
416
417 /* Compute earliestness. */
418 earliest = sbitmap_vector_alloc (num_edges, n_exprs);
419 compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
420
421#ifdef LCM_DEBUG_INFO
422 if (dump_file)
423 dump_bitmap_vector (dump_file, "earliest", "", earliest, num_edges);
424#endif
425
426 sbitmap_vector_free (antout);
427 sbitmap_vector_free (antin);
428
429 later = sbitmap_vector_alloc (num_edges, n_exprs);
430
431 /* Allocate an extra element for the exit block in the laterin vector. */
432 laterin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun) + 1,
433 n_exprs);
434 compute_laterin (edge_list, earliest, antloc, later, laterin);
435
436#ifdef LCM_DEBUG_INFO
437 if (dump_file)
438 {
439 dump_bitmap_vector (dump_file, "laterin", "", laterin,
440 last_basic_block_for_fn (cfun) + 1);
441 dump_bitmap_vector (dump_file, "later", "", later, num_edges);
442 }
443#endif
444
445 sbitmap_vector_free (earliest);
446
447 *insert = sbitmap_vector_alloc (num_edges, n_exprs);
448 *del = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
449 bitmap_vector_clear (*insert, num_edges);
450 bitmap_vector_clear (*del, last_basic_block_for_fn (cfun));
451 compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del);
452
453 sbitmap_vector_free (laterin);
454 sbitmap_vector_free (later);
455
456#ifdef LCM_DEBUG_INFO
457 if (dump_file)
458 {
459 dump_bitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
460 dump_bitmap_vector (dump_file, "pre_delete_map", "", *del,
461 last_basic_block_for_fn (cfun));
462 }
463#endif
464
465 return edge_list;
466}
467
468/* Wrapper to allocate avin/avout and call pre_edge_lcm_avs. */
469
470struct edge_list *
471pre_edge_lcm (int n_exprs, sbitmap *transp,
472 sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
473 sbitmap **insert, sbitmap **del)
474{
475 struct edge_list *edge_list;
476 sbitmap *avin, *avout;
477
478 avin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
479 avout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
480
481 edge_list = pre_edge_lcm_avs (n_exprs, transp, avloc, antloc, kill,
482 avin, avout, insert, del);
483
484 sbitmap_vector_free (avout);
485 sbitmap_vector_free (avin);
486
487 return edge_list;
488}
489
490/* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
491 Return the number of passes we performed to iterate to a solution. */
492
493void
494compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
495 sbitmap *avin)
496{
497 edge e;
498 basic_block *worklist, *qin, *qout, *qend, bb;
499 unsigned int qlen;
500 edge_iterator ei;
501
502 /* Allocate a worklist array/queue. Entries are only added to the
503 list if they were not already on the list. So the size is
504 bounded by the number of basic blocks. */
505 qin = qout = worklist =
506 XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
507
508 /* We want a maximal solution. */
509 bitmap_vector_ones (avout, last_basic_block_for_fn (cfun));
510
511 /* Put every block on the worklist; this is necessary because of the
512 optimistic initialization of AVOUT above. Use inverted postorder
513 to make the dataflow problem require less iterations. */
514 auto_vec<int, 20> postorder;
515 inverted_post_order_compute (&postorder);
516 for (unsigned int i = 0; i < postorder.length (); ++i)
517 {
518 bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
519 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
520 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
521 continue;
522 *qin++ = bb;
523 bb->aux = bb;
524 }
525
526 qin = worklist;
527 qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
528 qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
529
530 /* Mark blocks which are successors of the entry block so that we
531 can easily identify them below. */
532 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
533 e->dest->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun);
534
535 /* Iterate until the worklist is empty. */
536 while (qlen)
537 {
538 /* Take the first entry off the worklist. */
539 bb = *qout++;
540 qlen--;
541
542 if (qout >= qend)
543 qout = worklist;
544
545 /* If one of the predecessor blocks is the ENTRY block, then the
546 intersection of avouts is the null set. We can identify such blocks
547 by the special value in the AUX field in the block structure. */
548 if (bb->aux == ENTRY_BLOCK_PTR_FOR_FN (cfun))
549 /* Do not clear the aux field for blocks which are successors of the
550 ENTRY block. That way we never add then to the worklist again. */
551 bitmap_clear (avin[bb->index]);
552 else
553 {
554 /* Clear the aux field of this block so that it can be added to
555 the worklist again if necessary. */
556 bb->aux = NULL;
557 bitmap_intersection_of_preds (avin[bb->index], avout, bb);
558 }
559
560 if (bitmap_ior_and_compl (avout[bb->index], avloc[bb->index],
561 avin[bb->index], kill[bb->index]))
562 /* If the out state of this block changed, then we need
563 to add the successors of this block to the worklist
564 if they are not already on the worklist. */
565 FOR_EACH_EDGE (e, ei, bb->succs)
566 if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
567 {
568 *qin++ = e->dest;
569 e->dest->aux = e;
570 qlen++;
571
572 if (qin >= qend)
573 qin = worklist;
574 }
575 }
576
577 clear_aux_for_edges ();
578 clear_aux_for_blocks ();
579 free (worklist);
580}
581
582/* Compute the farthest vector for edge based lcm. */
583
584static void
585compute_farthest (struct edge_list *edge_list, int n_exprs,
586 sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin,
587 sbitmap *kill, sbitmap *farthest)
588{
589 int x, num_edges;
590 basic_block pred, succ;
591
592 num_edges = NUM_EDGES (edge_list);
593
594 auto_sbitmap difference (n_exprs), temp_bitmap (n_exprs);
595 for (x = 0; x < num_edges; x++)
596 {
597 pred = INDEX_EDGE_PRED_BB (edge_list, x);
598 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
599 if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun))
600 bitmap_copy (farthest[x], st_avout[pred->index]);
601 else
602 {
603 if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
604 bitmap_clear (farthest[x]);
605 else
606 {
607 bitmap_and_compl (difference, st_avout[pred->index],
608 st_antin[succ->index]);
609 bitmap_not (temp_bitmap, st_avin[succ->index]);
610 bitmap_and_or (farthest[x], difference,
611 kill[succ->index], temp_bitmap);
612 }
613 }
614 }
615}
616
617/* Compute nearer and nearerout vectors for edge based lcm.
618
619 This is the mirror of compute_laterin, additional comments on the
620 implementation can be found before compute_laterin. */
621
622static void
623compute_nearerout (struct edge_list *edge_list, sbitmap *farthest,
624 sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout)
625{
626 int num_edges, i;
627 edge e;
628 basic_block *worklist, *tos, bb;
629 edge_iterator ei;
630
631 num_edges = NUM_EDGES (edge_list);
632
633 /* Allocate a worklist array/queue. Entries are only added to the
634 list if they were not already on the list. So the size is
635 bounded by the number of basic blocks. */
636 tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1);
637
638 /* Initialize NEARER for each edge and build a mapping from an edge to
639 its index. */
640 for (i = 0; i < num_edges; i++)
641 INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
642
643 /* We want a maximal solution. */
644 bitmap_vector_ones (nearer, num_edges);
645
646 /* Note that even though we want an optimistic setting of NEARER, we
647 do not want to be overly optimistic. Consider an incoming edge to
648 the exit block. That edge should always have a NEARER value the
649 same as FARTHEST for that edge. */
650 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
651 bitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]);
652
653 /* Add all the blocks to the worklist. This prevents an early exit
654 from the loop given our optimistic initialization of NEARER. */
655 FOR_EACH_BB_FN (bb, cfun)
656 {
657 *tos++ = bb;
658 bb->aux = bb;
659 }
660
661 /* Iterate until the worklist is empty. */
662 while (tos != worklist)
663 {
664 /* Take the first entry off the worklist. */
665 bb = *--tos;
666 bb->aux = NULL;
667
668 /* Compute the intersection of NEARER for each outgoing edge from B. */
669 bitmap_ones (nearerout[bb->index]);
670 FOR_EACH_EDGE (e, ei, bb->succs)
671 bitmap_and (nearerout[bb->index], nearerout[bb->index],
672 nearer[(size_t) e->aux]);
673
674 /* Calculate NEARER for all incoming edges. */
675 FOR_EACH_EDGE (e, ei, bb->preds)
676 if (bitmap_ior_and_compl (nearer[(size_t) e->aux],
677 farthest[(size_t) e->aux],
678 nearerout[e->dest->index],
679 st_avloc[e->dest->index])
680 /* If NEARER for an incoming edge was changed, then we need
681 to add the source of the incoming edge to the worklist. */
682 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) && e->src->aux == 0)
683 {
684 *tos++ = e->src;
685 e->src->aux = e;
686 }
687 }
688
689 /* Computation of insertion and deletion points requires computing NEAREROUT
690 for the ENTRY block. We allocated an extra entry in the NEAREROUT array
691 for just this purpose. */
692 bitmap_ones (nearerout[last_basic_block_for_fn (cfun)]);
693 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
694 bitmap_and (nearerout[last_basic_block_for_fn (cfun)],
695 nearerout[last_basic_block_for_fn (cfun)],
696 nearer[(size_t) e->aux]);
697
698 clear_aux_for_edges ();
699 free (tos);
700}
701
702/* Compute the insertion and deletion points for edge based LCM. */
703
704static void
705compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc,
706 sbitmap *nearer, sbitmap *nearerout,
707 sbitmap *insert, sbitmap *del)
708{
709 int x;
710 basic_block bb;
711
712 FOR_EACH_BB_FN (bb, cfun)
713 bitmap_and_compl (del[bb->index], st_avloc[bb->index],
714 nearerout[bb->index]);
715
716 for (x = 0; x < NUM_EDGES (edge_list); x++)
717 {
718 basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
719 if (b == ENTRY_BLOCK_PTR_FOR_FN (cfun))
720 bitmap_and_compl (insert[x], nearer[x],
721 nearerout[last_basic_block_for_fn (cfun)]);
722 else
723 bitmap_and_compl (insert[x], nearer[x], nearerout[b->index]);
724 }
725}
726
727/* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
728 insert and delete vectors for edge based reverse LCM. Returns an
729 edgelist which is used to map the insert vector to what edge
730 an expression should be inserted on. */
731
732struct edge_list *
733pre_edge_rev_lcm (int n_exprs, sbitmap *transp,
734 sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill,
735 sbitmap **insert, sbitmap **del)
736{
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;
742
743 edge_list = create_edge_list ();
744 num_edges = NUM_EDGES (edge_list);
745
746 st_antin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
747 st_antout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
748 bitmap_vector_clear (st_antin, last_basic_block_for_fn (cfun));
749 bitmap_vector_clear (st_antout, last_basic_block_for_fn (cfun));
750 compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
751
752 /* Compute global anticipatability. */
753 st_avout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
754 st_avin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
755 compute_available (st_avloc, kill, st_avout, st_avin);
756
757#ifdef LCM_DEBUG_INFO
758 if (dump_file)
759 {
760 fprintf (dump_file, "Edge List:\n");
761 verify_edge_list (dump_file, edge_list);
762 print_edge_list (dump_file, edge_list);
763 dump_bitmap_vector (dump_file, "transp", "", transp,
764 last_basic_block_for_fn (cfun));
765 dump_bitmap_vector (dump_file, "st_avloc", "", st_avloc,
766 last_basic_block_for_fn (cfun));
767 dump_bitmap_vector (dump_file, "st_antloc", "", st_antloc,
768 last_basic_block_for_fn (cfun));
769 dump_bitmap_vector (dump_file, "st_antin", "", st_antin,
770 last_basic_block_for_fn (cfun));
771 dump_bitmap_vector (dump_file, "st_antout", "", st_antout,
772 last_basic_block_for_fn (cfun));
773 dump_bitmap_vector (dump_file, "st_kill", "", kill,
774 last_basic_block_for_fn (cfun));
775 }
776#endif
777
778#ifdef LCM_DEBUG_INFO
779 if (dump_file)
780 {
781 dump_bitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block_for_fn (cfun));
782 dump_bitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block_for_fn (cfun));
783 }
784#endif
785
786 /* Compute farthestness. */
787 farthest = sbitmap_vector_alloc (num_edges, n_exprs);
788 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
789 kill, farthest);
790
791#ifdef LCM_DEBUG_INFO
792 if (dump_file)
793 dump_bitmap_vector (dump_file, "farthest", "", farthest, num_edges);
794#endif
795
796 sbitmap_vector_free (st_antin);
797 sbitmap_vector_free (st_antout);
798
799 sbitmap_vector_free (st_avin);
800 sbitmap_vector_free (st_avout);
801
802 nearer = sbitmap_vector_alloc (num_edges, n_exprs);
803
804 /* Allocate an extra element for the entry block. */
805 nearerout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun) + 1,
806 n_exprs);
807 compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
808
809#ifdef LCM_DEBUG_INFO
810 if (dump_file)
811 {
812 dump_bitmap_vector (dump_file, "nearerout", "", nearerout,
813 last_basic_block_for_fn (cfun) + 1);
814 dump_bitmap_vector (dump_file, "nearer", "", nearer, num_edges);
815 }
816#endif
817
818 sbitmap_vector_free (farthest);
819
820 *insert = sbitmap_vector_alloc (num_edges, n_exprs);
821 *del = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs);
822 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
823 *insert, *del);
824
825 sbitmap_vector_free (nearerout);
826 sbitmap_vector_free (nearer);
827
828#ifdef LCM_DEBUG_INFO
829 if (dump_file)
830 {
831 dump_bitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
832 dump_bitmap_vector (dump_file, "pre_delete_map", "", *del,
833 last_basic_block_for_fn (cfun));
834 }
835#endif
836 return edge_list;
837}
838
839