1 /* Generic partial redundancy elimination with lazy code motion support.
2 Copyright (C) 1998-2016 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>. */
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. */
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 *);
66
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 *);
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
82 static void
compute_antinout_edge(sbitmap * antloc,sbitmap * transp,sbitmap * antin,sbitmap * antout)83 compute_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
168 static void
compute_earliest(struct edge_list * edge_list,int n_exprs,sbitmap * antin,sbitmap * antout,sbitmap * avout,sbitmap * kill,sbitmap * earliest)169 compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin,
170 sbitmap *antout, sbitmap *avout, sbitmap *kill,
171 sbitmap *earliest)
172 {
173 sbitmap difference, temp_bitmap;
174 int x, num_edges;
175 basic_block pred, succ;
176
177 num_edges = NUM_EDGES (edge_list);
178
179 difference = sbitmap_alloc (n_exprs);
180 temp_bitmap = sbitmap_alloc (n_exprs);
181
182 for (x = 0; x < num_edges; x++)
183 {
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
189 {
190 if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun))
191 bitmap_clear (earliest[x]);
192 else
193 {
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);
199 }
200 }
201 }
202
203 sbitmap_free (temp_bitmap);
204 sbitmap_free (difference);
205 }
206
207 /* later(p,s) is dependent on the calculation of laterin(p).
208 laterin(p) is dependent on the calculation of later(p2,p).
209
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)).
213
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.
217
218 Boundary conditions:
219
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.
224
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.
229
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. */
235
236 static void
compute_laterin(struct edge_list * edge_list,sbitmap * earliest,sbitmap * antloc,sbitmap * later,sbitmap * laterin)237 compute_laterin (struct edge_list *edge_list, sbitmap *earliest,
238 sbitmap *antloc, sbitmap *later, sbitmap *laterin)
239 {
240 int num_edges, i;
241 edge e;
242 basic_block *worklist, *qin, *qout, *qend, bb;
243 unsigned int qlen;
244 edge_iterator ei;
245
246 num_edges = NUM_EDGES (edge_list);
247
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));
253
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;
257
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.
263
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);
269
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]);
276
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)
282 {
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;
289 }
290 free (postorder);
291
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;
297
298 /* Iterate until the worklist is empty. */
299 while (qlen)
300 {
301 /* Take the first entry off the worklist. */
302 bb = *qout++;
303 bb->aux = NULL;
304 qlen--;
305 if (qout >= qend)
306 qout = worklist;
307
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]);
313
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)
323 {
324 *qin++ = e->dest;
325 e->dest->aux = e;
326 qlen++;
327 if (qin >= qend)
328 qin = worklist;
329 }
330 }
331
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]);
340
341 clear_aux_for_edges ();
342 free (worklist);
343 }
344
345 /* Compute the insertion and deletion points for edge based LCM. */
346
347 static void
compute_insert_delete(struct edge_list * edge_list,sbitmap * antloc,sbitmap * later,sbitmap * laterin,sbitmap * insert,sbitmap * del)348 compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc,
349 sbitmap *later, sbitmap *laterin, sbitmap *insert,
350 sbitmap *del)
351 {
352 int x;
353 basic_block bb;
354
355 FOR_EACH_BB_FN (bb, cfun)
356 bitmap_and_compl (del[bb->index], antloc[bb->index],
357 laterin[bb->index]);
358
359 for (x = 0; x < NUM_EDGES (edge_list); x++)
360 {
361 basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
362
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]);
368 }
369 }
370
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. */
374
375 struct edge_list *
pre_edge_lcm_avs(int n_exprs,sbitmap * transp,sbitmap * avloc,sbitmap * antloc,sbitmap * kill,sbitmap * avin,sbitmap * avout,sbitmap ** insert,sbitmap ** del)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)
380 {
381 sbitmap *antin, *antout, *earliest;
382 sbitmap *later, *laterin;
383 struct edge_list *edge_list;
384 int num_edges;
385
386 edge_list = create_edge_list ();
387 num_edges = NUM_EDGES (edge_list);
388
389 #ifdef LCM_DEBUG_INFO
390 if (dump_file)
391 {
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));
403 }
404 #endif
405
406 /* Compute global availability. */
407 compute_available (avloc, kill, avout, avin);
408
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);
413
414 #ifdef LCM_DEBUG_INFO
415 if (dump_file)
416 {
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));
421 }
422 #endif
423
424 /* Compute earliestness. */
425 earliest = sbitmap_vector_alloc (num_edges, n_exprs);
426 compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
427
428 #ifdef LCM_DEBUG_INFO
429 if (dump_file)
430 dump_bitmap_vector (dump_file, "earliest", "", earliest, num_edges);
431 #endif
432
433 sbitmap_vector_free (antout);
434 sbitmap_vector_free (antin);
435
436 later = sbitmap_vector_alloc (num_edges, n_exprs);
437
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);
442
443 #ifdef LCM_DEBUG_INFO
444 if (dump_file)
445 {
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);
449 }
450 #endif
451
452 sbitmap_vector_free (earliest);
453
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);
459
460 sbitmap_vector_free (laterin);
461 sbitmap_vector_free (later);
462
463 #ifdef LCM_DEBUG_INFO
464 if (dump_file)
465 {
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));
469 }
470 #endif
471
472 return edge_list;
473 }
474
475 /* Wrapper to allocate avin/avout and call pre_edge_lcm_avs. */
476
477 struct edge_list *
pre_edge_lcm(int n_exprs,sbitmap * transp,sbitmap * avloc,sbitmap * antloc,sbitmap * kill,sbitmap ** insert,sbitmap ** del)478 pre_edge_lcm (int n_exprs, sbitmap *transp,
479 sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
480 sbitmap **insert, sbitmap **del)
481 {
482 struct edge_list *edge_list;
483 sbitmap *avin, *avout;
484
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);
487
488 edge_list = pre_edge_lcm_avs (n_exprs, transp, avloc, antloc, kill,
489 avin, avout, insert, del);
490
491 sbitmap_vector_free (avout);
492 sbitmap_vector_free (avin);
493
494 return edge_list;
495 }
496
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. */
499
500 void
compute_available(sbitmap * avloc,sbitmap * kill,sbitmap * avout,sbitmap * avin)501 compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
502 sbitmap *avin)
503 {
504 edge e;
505 basic_block *worklist, *qin, *qout, *qend, bb;
506 unsigned int qlen;
507 edge_iterator ei;
508
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);
514
515 /* We want a maximal solution. */
516 bitmap_vector_ones (avout, last_basic_block_for_fn (cfun));
517
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)
524 {
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;
531 }
532 free (postorder);
533
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;
537
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);
542
543 /* Iterate until the worklist is empty. */
544 while (qlen)
545 {
546 /* Take the first entry off the worklist. */
547 bb = *qout++;
548 qlen--;
549
550 if (qout >= qend)
551 qout = worklist;
552
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
561 {
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);
566 }
567
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))
575 {
576 *qin++ = e->dest;
577 e->dest->aux = e;
578 qlen++;
579
580 if (qin >= qend)
581 qin = worklist;
582 }
583 }
584
585 clear_aux_for_edges ();
586 clear_aux_for_blocks ();
587 free (worklist);
588 }
589
590 /* Compute the farthest vector for edge based lcm. */
591
592 static void
compute_farthest(struct edge_list * edge_list,int n_exprs,sbitmap * st_avout,sbitmap * st_avin,sbitmap * st_antin,sbitmap * kill,sbitmap * farthest)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)
596 {
597 sbitmap difference, temp_bitmap;
598 int x, num_edges;
599 basic_block pred, succ;
600
601 num_edges = NUM_EDGES (edge_list);
602
603 difference = sbitmap_alloc (n_exprs);
604 temp_bitmap = sbitmap_alloc (n_exprs);
605
606 for (x = 0; x < num_edges; x++)
607 {
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
613 {
614 if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
615 bitmap_clear (farthest[x]);
616 else
617 {
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);
623 }
624 }
625 }
626
627 sbitmap_free (temp_bitmap);
628 sbitmap_free (difference);
629 }
630
631 /* Compute nearer and nearerout vectors for edge based lcm.
632
633 This is the mirror of compute_laterin, additional comments on the
634 implementation can be found before compute_laterin. */
635
636 static void
compute_nearerout(struct edge_list * edge_list,sbitmap * farthest,sbitmap * st_avloc,sbitmap * nearer,sbitmap * nearerout)637 compute_nearerout (struct edge_list *edge_list, sbitmap *farthest,
638 sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout)
639 {
640 int num_edges, i;
641 edge e;
642 basic_block *worklist, *tos, bb;
643 edge_iterator ei;
644
645 num_edges = NUM_EDGES (edge_list);
646
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);
651
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;
656
657 /* We want a maximal solution. */
658 bitmap_vector_ones (nearer, num_edges);
659
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]);
666
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)
670 {
671 *tos++ = bb;
672 bb->aux = bb;
673 }
674
675 /* Iterate until the worklist is empty. */
676 while (tos != worklist)
677 {
678 /* Take the first entry off the worklist. */
679 bb = *--tos;
680 bb->aux = NULL;
681
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]);
687
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)
697 {
698 *tos++ = e->src;
699 e->src->aux = e;
700 }
701 }
702
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]);
711
712 clear_aux_for_edges ();
713 free (tos);
714 }
715
716 /* Compute the insertion and deletion points for edge based LCM. */
717
718 static void
compute_rev_insert_delete(struct edge_list * edge_list,sbitmap * st_avloc,sbitmap * nearer,sbitmap * nearerout,sbitmap * insert,sbitmap * del)719 compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc,
720 sbitmap *nearer, sbitmap *nearerout,
721 sbitmap *insert, sbitmap *del)
722 {
723 int x;
724 basic_block bb;
725
726 FOR_EACH_BB_FN (bb, cfun)
727 bitmap_and_compl (del[bb->index], st_avloc[bb->index],
728 nearerout[bb->index]);
729
730 for (x = 0; x < NUM_EDGES (edge_list); x++)
731 {
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]);
738 }
739 }
740
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. */
745
746 struct edge_list *
pre_edge_rev_lcm(int n_exprs,sbitmap * transp,sbitmap * st_avloc,sbitmap * st_antloc,sbitmap * kill,sbitmap ** insert,sbitmap ** del)747 pre_edge_rev_lcm (int n_exprs, sbitmap *transp,
748 sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill,
749 sbitmap **insert, sbitmap **del)
750 {
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;
756
757 edge_list = create_edge_list ();
758 num_edges = NUM_EDGES (edge_list);
759
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);
765
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);
770
771 #ifdef LCM_DEBUG_INFO
772 if (dump_file)
773 {
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));
789 }
790 #endif
791
792 #ifdef LCM_DEBUG_INFO
793 if (dump_file)
794 {
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));
797 }
798 #endif
799
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);
804
805 #ifdef LCM_DEBUG_INFO
806 if (dump_file)
807 dump_bitmap_vector (dump_file, "farthest", "", farthest, num_edges);
808 #endif
809
810 sbitmap_vector_free (st_antin);
811 sbitmap_vector_free (st_antout);
812
813 sbitmap_vector_free (st_avin);
814 sbitmap_vector_free (st_avout);
815
816 nearer = sbitmap_vector_alloc (num_edges, n_exprs);
817
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);
822
823 #ifdef LCM_DEBUG_INFO
824 if (dump_file)
825 {
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);
829 }
830 #endif
831
832 sbitmap_vector_free (farthest);
833
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);
838
839 sbitmap_vector_free (nearerout);
840 sbitmap_vector_free (nearer);
841
842 #ifdef LCM_DEBUG_INFO
843 if (dump_file)
844 {
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));
848 }
849 #endif
850 return edge_list;
851 }
852
853