1 /* Generic partial redundancy elimination with lazy code motion support.
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
3 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA. */
21
22 /* These routines are meant to be used by various optimization
23 passes which can be modeled as lazy code motion problems.
24 Including, but not limited to:
25
26 * Traditional partial redundancy elimination.
27
28 * Placement of caller/caller register save/restores.
29
30 * Load/store motion.
31
32 * Copy motion.
33
34 * Conversion of flat register files to a stacked register
35 model.
36
37 * Dead load/store elimination.
38
39 These routines accept as input:
40
41 * Basic block information (number of blocks, lists of
42 predecessors and successors). Note the granularity
43 does not need to be basic block, they could be statements
44 or functions.
45
46 * Bitmaps of local properties (computed, transparent and
47 anticipatable expressions).
48
49 The output of these routines is bitmap of redundant computations
50 and a bitmap of optimal placement points. */
51
52
53 #include "config.h"
54 #include "system.h"
55 #include "coretypes.h"
56 #include "tm.h"
57 #include "rtl.h"
58 #include "regs.h"
59 #include "hard-reg-set.h"
60 #include "flags.h"
61 #include "real.h"
62 #include "insn-config.h"
63 #include "recog.h"
64 #include "basic-block.h"
65 #include "output.h"
66 #include "tm_p.h"
67 #include "function.h"
68
69 /* We want target macros for the mode switching code to be able to refer
70 to instruction attribute values. */
71 #include "insn-attr.h"
72
73 /* Edge based LCM routines. */
74 static void compute_antinout_edge (sbitmap *, sbitmap *, sbitmap *, sbitmap *);
75 static void compute_earliest (struct edge_list *, int, sbitmap *, sbitmap *,
76 sbitmap *, sbitmap *, sbitmap *);
77 static void compute_laterin (struct edge_list *, sbitmap *, sbitmap *,
78 sbitmap *, sbitmap *);
79 static void compute_insert_delete (struct edge_list *edge_list, sbitmap *,
80 sbitmap *, sbitmap *, sbitmap *, sbitmap *);
81
82 /* Edge based LCM routines on a reverse flowgraph. */
83 static void compute_farthest (struct edge_list *, int, sbitmap *, sbitmap *,
84 sbitmap*, sbitmap *, sbitmap *);
85 static void compute_nearerout (struct edge_list *, sbitmap *, sbitmap *,
86 sbitmap *, sbitmap *);
87 static void compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *,
88 sbitmap *, sbitmap *, sbitmap *,
89 sbitmap *);
90
91 /* Edge based lcm routines. */
92
93 /* Compute expression anticipatability at entrance and exit of each block.
94 This is done based on the flow graph, and not on the pred-succ lists.
95 Other than that, its pretty much identical to compute_antinout. */
96
97 static void
compute_antinout_edge(sbitmap * antloc,sbitmap * transp,sbitmap * antin,sbitmap * antout)98 compute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin,
99 sbitmap *antout)
100 {
101 basic_block bb;
102 edge e;
103 basic_block *worklist, *qin, *qout, *qend;
104 unsigned int qlen;
105 edge_iterator ei;
106
107 /* Allocate a worklist array/queue. Entries are only added to the
108 list if they were not already on the list. So the size is
109 bounded by the number of basic blocks. */
110 qin = qout = worklist = XNEWVEC (basic_block, n_basic_blocks);
111
112 /* We want a maximal solution, so make an optimistic initialization of
113 ANTIN. */
114 sbitmap_vector_ones (antin, last_basic_block);
115
116 /* Put every block on the worklist; this is necessary because of the
117 optimistic initialization of ANTIN above. */
118 FOR_EACH_BB_REVERSE (bb)
119 {
120 *qin++ = bb;
121 bb->aux = bb;
122 }
123
124 qin = worklist;
125 qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
126 qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
127
128 /* Mark blocks which are predecessors of the exit block so that we
129 can easily identify them below. */
130 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
131 e->src->aux = EXIT_BLOCK_PTR;
132
133 /* Iterate until the worklist is empty. */
134 while (qlen)
135 {
136 /* Take the first entry off the worklist. */
137 bb = *qout++;
138 qlen--;
139
140 if (qout >= qend)
141 qout = worklist;
142
143 if (bb->aux == EXIT_BLOCK_PTR)
144 /* Do not clear the aux field for blocks which are predecessors of
145 the EXIT block. That way we never add then to the worklist
146 again. */
147 sbitmap_zero (antout[bb->index]);
148 else
149 {
150 /* Clear the aux field of this block so that it can be added to
151 the worklist again if necessary. */
152 bb->aux = NULL;
153 sbitmap_intersection_of_succs (antout[bb->index], antin, bb->index);
154 }
155
156 if (sbitmap_a_or_b_and_c_cg (antin[bb->index], antloc[bb->index],
157 transp[bb->index], antout[bb->index]))
158 /* If the in state of this block changed, then we need
159 to add the predecessors of this block to the worklist
160 if they are not already on the worklist. */
161 FOR_EACH_EDGE (e, ei, bb->preds)
162 if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
163 {
164 *qin++ = e->src;
165 e->src->aux = e;
166 qlen++;
167 if (qin >= qend)
168 qin = worklist;
169 }
170 }
171
172 clear_aux_for_edges ();
173 clear_aux_for_blocks ();
174 free (worklist);
175 }
176
177 /* Compute the earliest vector for edge based lcm. */
178
179 static void
compute_earliest(struct edge_list * edge_list,int n_exprs,sbitmap * antin,sbitmap * antout,sbitmap * avout,sbitmap * kill,sbitmap * earliest)180 compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin,
181 sbitmap *antout, sbitmap *avout, sbitmap *kill,
182 sbitmap *earliest)
183 {
184 sbitmap difference, temp_bitmap;
185 int x, num_edges;
186 basic_block pred, succ;
187
188 num_edges = NUM_EDGES (edge_list);
189
190 difference = sbitmap_alloc (n_exprs);
191 temp_bitmap = sbitmap_alloc (n_exprs);
192
193 for (x = 0; x < num_edges; x++)
194 {
195 pred = INDEX_EDGE_PRED_BB (edge_list, x);
196 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
197 if (pred == ENTRY_BLOCK_PTR)
198 sbitmap_copy (earliest[x], antin[succ->index]);
199 else
200 {
201 if (succ == EXIT_BLOCK_PTR)
202 sbitmap_zero (earliest[x]);
203 else
204 {
205 sbitmap_difference (difference, antin[succ->index],
206 avout[pred->index]);
207 sbitmap_not (temp_bitmap, antout[pred->index]);
208 sbitmap_a_and_b_or_c (earliest[x], difference,
209 kill[pred->index], temp_bitmap);
210 }
211 }
212 }
213
214 sbitmap_free (temp_bitmap);
215 sbitmap_free (difference);
216 }
217
218 /* later(p,s) is dependent on the calculation of laterin(p).
219 laterin(p) is dependent on the calculation of later(p2,p).
220
221 laterin(ENTRY) is defined as all 0's
222 later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY)
223 laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)).
224
225 If we progress in this manner, starting with all basic blocks
226 in the work list, anytime we change later(bb), we need to add
227 succs(bb) to the worklist if they are not already on the worklist.
228
229 Boundary conditions:
230
231 We prime the worklist all the normal basic blocks. The ENTRY block can
232 never be added to the worklist since it is never the successor of any
233 block. We explicitly prevent the EXIT block from being added to the
234 worklist.
235
236 We optimistically initialize LATER. That is the only time this routine
237 will compute LATER for an edge out of the entry block since the entry
238 block is never on the worklist. Thus, LATERIN is neither used nor
239 computed for the ENTRY block.
240
241 Since the EXIT block is never added to the worklist, we will neither
242 use nor compute LATERIN for the exit block. Edges which reach the
243 EXIT block are handled in the normal fashion inside the loop. However,
244 the insertion/deletion computation needs LATERIN(EXIT), so we have
245 to compute it. */
246
247 static void
compute_laterin(struct edge_list * edge_list,sbitmap * earliest,sbitmap * antloc,sbitmap * later,sbitmap * laterin)248 compute_laterin (struct edge_list *edge_list, sbitmap *earliest,
249 sbitmap *antloc, sbitmap *later, sbitmap *laterin)
250 {
251 int num_edges, i;
252 edge e;
253 basic_block *worklist, *qin, *qout, *qend, bb;
254 unsigned int qlen;
255 edge_iterator ei;
256
257 num_edges = NUM_EDGES (edge_list);
258
259 /* Allocate a worklist array/queue. Entries are only added to the
260 list if they were not already on the list. So the size is
261 bounded by the number of basic blocks. */
262 qin = qout = worklist
263 = XNEWVEC (basic_block, n_basic_blocks);
264
265 /* Initialize a mapping from each edge to its index. */
266 for (i = 0; i < num_edges; i++)
267 INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
268
269 /* We want a maximal solution, so initially consider LATER true for
270 all edges. This allows propagation through a loop since the incoming
271 loop edge will have LATER set, so if all the other incoming edges
272 to the loop are set, then LATERIN will be set for the head of the
273 loop.
274
275 If the optimistic setting of LATER on that edge was incorrect (for
276 example the expression is ANTLOC in a block within the loop) then
277 this algorithm will detect it when we process the block at the head
278 of the optimistic edge. That will requeue the affected blocks. */
279 sbitmap_vector_ones (later, num_edges);
280
281 /* Note that even though we want an optimistic setting of LATER, we
282 do not want to be overly optimistic. Consider an outgoing edge from
283 the entry block. That edge should always have a LATER value the
284 same as EARLIEST for that edge. */
285 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
286 sbitmap_copy (later[(size_t) e->aux], earliest[(size_t) e->aux]);
287
288 /* Add all the blocks to the worklist. This prevents an early exit from
289 the loop given our optimistic initialization of LATER above. */
290 FOR_EACH_BB (bb)
291 {
292 *qin++ = bb;
293 bb->aux = bb;
294 }
295
296 /* Note that we do not use the last allocated element for our queue,
297 as EXIT_BLOCK is never inserted into it. */
298 qin = worklist;
299 qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
300 qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
301
302 /* Iterate until the worklist is empty. */
303 while (qlen)
304 {
305 /* Take the first entry off the worklist. */
306 bb = *qout++;
307 bb->aux = NULL;
308 qlen--;
309 if (qout >= qend)
310 qout = worklist;
311
312 /* Compute the intersection of LATERIN for each incoming edge to B. */
313 sbitmap_ones (laterin[bb->index]);
314 FOR_EACH_EDGE (e, ei, bb->preds)
315 sbitmap_a_and_b (laterin[bb->index], laterin[bb->index],
316 later[(size_t)e->aux]);
317
318 /* Calculate LATER for all outgoing edges. */
319 FOR_EACH_EDGE (e, ei, bb->succs)
320 if (sbitmap_union_of_diff_cg (later[(size_t) e->aux],
321 earliest[(size_t) e->aux],
322 laterin[e->src->index],
323 antloc[e->src->index])
324 /* If LATER for an outgoing edge was changed, then we need
325 to add the target of the outgoing edge to the worklist. */
326 && e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0)
327 {
328 *qin++ = e->dest;
329 e->dest->aux = e;
330 qlen++;
331 if (qin >= qend)
332 qin = worklist;
333 }
334 }
335
336 /* Computation of insertion and deletion points requires computing LATERIN
337 for the EXIT block. We allocated an extra entry in the LATERIN array
338 for just this purpose. */
339 sbitmap_ones (laterin[last_basic_block]);
340 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
341 sbitmap_a_and_b (laterin[last_basic_block],
342 laterin[last_basic_block],
343 later[(size_t) e->aux]);
344
345 clear_aux_for_edges ();
346 free (worklist);
347 }
348
349 /* Compute the insertion and deletion points for edge based LCM. */
350
351 static void
compute_insert_delete(struct edge_list * edge_list,sbitmap * antloc,sbitmap * later,sbitmap * laterin,sbitmap * insert,sbitmap * delete)352 compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc,
353 sbitmap *later, sbitmap *laterin, sbitmap *insert,
354 sbitmap *delete)
355 {
356 int x;
357 basic_block bb;
358
359 FOR_EACH_BB (bb)
360 sbitmap_difference (delete[bb->index], antloc[bb->index],
361 laterin[bb->index]);
362
363 for (x = 0; x < NUM_EDGES (edge_list); x++)
364 {
365 basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
366
367 if (b == EXIT_BLOCK_PTR)
368 sbitmap_difference (insert[x], later[x], laterin[last_basic_block]);
369 else
370 sbitmap_difference (insert[x], later[x], laterin[b->index]);
371 }
372 }
373
374 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and
375 delete vectors for edge based LCM. Returns an edgelist which is used to
376 map the insert vector to what edge an expression should be inserted on. */
377
378 struct edge_list *
pre_edge_lcm(int n_exprs,sbitmap * transp,sbitmap * avloc,sbitmap * antloc,sbitmap * kill,sbitmap ** insert,sbitmap ** delete)379 pre_edge_lcm (int n_exprs, sbitmap *transp,
380 sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
381 sbitmap **insert, sbitmap **delete)
382 {
383 sbitmap *antin, *antout, *earliest;
384 sbitmap *avin, *avout;
385 sbitmap *later, *laterin;
386 struct edge_list *edge_list;
387 int num_edges;
388
389 edge_list = create_edge_list ();
390 num_edges = NUM_EDGES (edge_list);
391
392 #ifdef LCM_DEBUG_INFO
393 if (dump_file)
394 {
395 fprintf (dump_file, "Edge List:\n");
396 verify_edge_list (dump_file, edge_list);
397 print_edge_list (dump_file, edge_list);
398 dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block);
399 dump_sbitmap_vector (dump_file, "antloc", "", antloc, last_basic_block);
400 dump_sbitmap_vector (dump_file, "avloc", "", avloc, last_basic_block);
401 dump_sbitmap_vector (dump_file, "kill", "", kill, last_basic_block);
402 }
403 #endif
404
405 /* Compute global availability. */
406 avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
407 avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
408 compute_available (avloc, kill, avout, avin);
409 sbitmap_vector_free (avin);
410
411 /* Compute global anticipatability. */
412 antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
413 antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
414 compute_antinout_edge (antloc, transp, antin, antout);
415
416 #ifdef LCM_DEBUG_INFO
417 if (dump_file)
418 {
419 dump_sbitmap_vector (dump_file, "antin", "", antin, last_basic_block);
420 dump_sbitmap_vector (dump_file, "antout", "", antout, last_basic_block);
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_sbitmap_vector (dump_file, "earliest", "", earliest, num_edges);
431 #endif
432
433 sbitmap_vector_free (antout);
434 sbitmap_vector_free (antin);
435 sbitmap_vector_free (avout);
436
437 later = sbitmap_vector_alloc (num_edges, n_exprs);
438
439 /* Allocate an extra element for the exit block in the laterin vector. */
440 laterin = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
441 compute_laterin (edge_list, earliest, antloc, later, laterin);
442
443 #ifdef LCM_DEBUG_INFO
444 if (dump_file)
445 {
446 dump_sbitmap_vector (dump_file, "laterin", "", laterin, last_basic_block + 1);
447 dump_sbitmap_vector (dump_file, "later", "", later, num_edges);
448 }
449 #endif
450
451 sbitmap_vector_free (earliest);
452
453 *insert = sbitmap_vector_alloc (num_edges, n_exprs);
454 *delete = sbitmap_vector_alloc (last_basic_block, n_exprs);
455 compute_insert_delete (edge_list, antloc, later, laterin, *insert, *delete);
456
457 sbitmap_vector_free (laterin);
458 sbitmap_vector_free (later);
459
460 #ifdef LCM_DEBUG_INFO
461 if (dump_file)
462 {
463 dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
464 dump_sbitmap_vector (dump_file, "pre_delete_map", "", *delete,
465 last_basic_block);
466 }
467 #endif
468
469 return edge_list;
470 }
471
472 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
473 Return the number of passes we performed to iterate to a solution. */
474
475 void
compute_available(sbitmap * avloc,sbitmap * kill,sbitmap * avout,sbitmap * avin)476 compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
477 sbitmap *avin)
478 {
479 edge e;
480 basic_block *worklist, *qin, *qout, *qend, bb;
481 unsigned int qlen;
482 edge_iterator ei;
483
484 /* Allocate a worklist array/queue. Entries are only added to the
485 list if they were not already on the list. So the size is
486 bounded by the number of basic blocks. */
487 qin = qout = worklist =
488 XNEWVEC (basic_block, n_basic_blocks - NUM_FIXED_BLOCKS);
489
490 /* We want a maximal solution. */
491 sbitmap_vector_ones (avout, last_basic_block);
492
493 /* Put every block on the worklist; this is necessary because of the
494 optimistic initialization of AVOUT above. */
495 FOR_EACH_BB (bb)
496 {
497 *qin++ = bb;
498 bb->aux = bb;
499 }
500
501 qin = worklist;
502 qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
503 qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
504
505 /* Mark blocks which are successors of the entry block so that we
506 can easily identify them below. */
507 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
508 e->dest->aux = ENTRY_BLOCK_PTR;
509
510 /* Iterate until the worklist is empty. */
511 while (qlen)
512 {
513 /* Take the first entry off the worklist. */
514 bb = *qout++;
515 qlen--;
516
517 if (qout >= qend)
518 qout = worklist;
519
520 /* If one of the predecessor blocks is the ENTRY block, then the
521 intersection of avouts is the null set. We can identify such blocks
522 by the special value in the AUX field in the block structure. */
523 if (bb->aux == ENTRY_BLOCK_PTR)
524 /* Do not clear the aux field for blocks which are successors of the
525 ENTRY block. That way we never add then to the worklist again. */
526 sbitmap_zero (avin[bb->index]);
527 else
528 {
529 /* Clear the aux field of this block so that it can be added to
530 the worklist again if necessary. */
531 bb->aux = NULL;
532 sbitmap_intersection_of_preds (avin[bb->index], avout, bb->index);
533 }
534
535 if (sbitmap_union_of_diff_cg (avout[bb->index], avloc[bb->index],
536 avin[bb->index], kill[bb->index]))
537 /* If the out state of this block changed, then we need
538 to add the successors of this block to the worklist
539 if they are not already on the worklist. */
540 FOR_EACH_EDGE (e, ei, bb->succs)
541 if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
542 {
543 *qin++ = e->dest;
544 e->dest->aux = e;
545 qlen++;
546
547 if (qin >= qend)
548 qin = worklist;
549 }
550 }
551
552 clear_aux_for_edges ();
553 clear_aux_for_blocks ();
554 free (worklist);
555 }
556
557 /* Compute the farthest vector for edge based lcm. */
558
559 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)560 compute_farthest (struct edge_list *edge_list, int n_exprs,
561 sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin,
562 sbitmap *kill, sbitmap *farthest)
563 {
564 sbitmap difference, temp_bitmap;
565 int x, num_edges;
566 basic_block pred, succ;
567
568 num_edges = NUM_EDGES (edge_list);
569
570 difference = sbitmap_alloc (n_exprs);
571 temp_bitmap = sbitmap_alloc (n_exprs);
572
573 for (x = 0; x < num_edges; x++)
574 {
575 pred = INDEX_EDGE_PRED_BB (edge_list, x);
576 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
577 if (succ == EXIT_BLOCK_PTR)
578 sbitmap_copy (farthest[x], st_avout[pred->index]);
579 else
580 {
581 if (pred == ENTRY_BLOCK_PTR)
582 sbitmap_zero (farthest[x]);
583 else
584 {
585 sbitmap_difference (difference, st_avout[pred->index],
586 st_antin[succ->index]);
587 sbitmap_not (temp_bitmap, st_avin[succ->index]);
588 sbitmap_a_and_b_or_c (farthest[x], difference,
589 kill[succ->index], temp_bitmap);
590 }
591 }
592 }
593
594 sbitmap_free (temp_bitmap);
595 sbitmap_free (difference);
596 }
597
598 /* Compute nearer and nearerout vectors for edge based lcm.
599
600 This is the mirror of compute_laterin, additional comments on the
601 implementation can be found before compute_laterin. */
602
603 static void
compute_nearerout(struct edge_list * edge_list,sbitmap * farthest,sbitmap * st_avloc,sbitmap * nearer,sbitmap * nearerout)604 compute_nearerout (struct edge_list *edge_list, sbitmap *farthest,
605 sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout)
606 {
607 int num_edges, i;
608 edge e;
609 basic_block *worklist, *tos, bb;
610 edge_iterator ei;
611
612 num_edges = NUM_EDGES (edge_list);
613
614 /* Allocate a worklist array/queue. Entries are only added to the
615 list if they were not already on the list. So the size is
616 bounded by the number of basic blocks. */
617 tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1);
618
619 /* Initialize NEARER for each edge and build a mapping from an edge to
620 its index. */
621 for (i = 0; i < num_edges; i++)
622 INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
623
624 /* We want a maximal solution. */
625 sbitmap_vector_ones (nearer, num_edges);
626
627 /* Note that even though we want an optimistic setting of NEARER, we
628 do not want to be overly optimistic. Consider an incoming edge to
629 the exit block. That edge should always have a NEARER value the
630 same as FARTHEST for that edge. */
631 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
632 sbitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]);
633
634 /* Add all the blocks to the worklist. This prevents an early exit
635 from the loop given our optimistic initialization of NEARER. */
636 FOR_EACH_BB (bb)
637 {
638 *tos++ = bb;
639 bb->aux = bb;
640 }
641
642 /* Iterate until the worklist is empty. */
643 while (tos != worklist)
644 {
645 /* Take the first entry off the worklist. */
646 bb = *--tos;
647 bb->aux = NULL;
648
649 /* Compute the intersection of NEARER for each outgoing edge from B. */
650 sbitmap_ones (nearerout[bb->index]);
651 FOR_EACH_EDGE (e, ei, bb->succs)
652 sbitmap_a_and_b (nearerout[bb->index], nearerout[bb->index],
653 nearer[(size_t) e->aux]);
654
655 /* Calculate NEARER for all incoming edges. */
656 FOR_EACH_EDGE (e, ei, bb->preds)
657 if (sbitmap_union_of_diff_cg (nearer[(size_t) e->aux],
658 farthest[(size_t) e->aux],
659 nearerout[e->dest->index],
660 st_avloc[e->dest->index])
661 /* If NEARER for an incoming edge was changed, then we need
662 to add the source of the incoming edge to the worklist. */
663 && e->src != ENTRY_BLOCK_PTR && e->src->aux == 0)
664 {
665 *tos++ = e->src;
666 e->src->aux = e;
667 }
668 }
669
670 /* Computation of insertion and deletion points requires computing NEAREROUT
671 for the ENTRY block. We allocated an extra entry in the NEAREROUT array
672 for just this purpose. */
673 sbitmap_ones (nearerout[last_basic_block]);
674 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
675 sbitmap_a_and_b (nearerout[last_basic_block],
676 nearerout[last_basic_block],
677 nearer[(size_t) e->aux]);
678
679 clear_aux_for_edges ();
680 free (tos);
681 }
682
683 /* Compute the insertion and deletion points for edge based LCM. */
684
685 static void
compute_rev_insert_delete(struct edge_list * edge_list,sbitmap * st_avloc,sbitmap * nearer,sbitmap * nearerout,sbitmap * insert,sbitmap * delete)686 compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc,
687 sbitmap *nearer, sbitmap *nearerout,
688 sbitmap *insert, sbitmap *delete)
689 {
690 int x;
691 basic_block bb;
692
693 FOR_EACH_BB (bb)
694 sbitmap_difference (delete[bb->index], st_avloc[bb->index],
695 nearerout[bb->index]);
696
697 for (x = 0; x < NUM_EDGES (edge_list); x++)
698 {
699 basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
700 if (b == ENTRY_BLOCK_PTR)
701 sbitmap_difference (insert[x], nearer[x], nearerout[last_basic_block]);
702 else
703 sbitmap_difference (insert[x], nearer[x], nearerout[b->index]);
704 }
705 }
706
707 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
708 insert and delete vectors for edge based reverse LCM. Returns an
709 edgelist which is used to map the insert vector to what edge
710 an expression should be inserted on. */
711
712 struct edge_list *
pre_edge_rev_lcm(int n_exprs,sbitmap * transp,sbitmap * st_avloc,sbitmap * st_antloc,sbitmap * kill,sbitmap ** insert,sbitmap ** delete)713 pre_edge_rev_lcm (int n_exprs, sbitmap *transp,
714 sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill,
715 sbitmap **insert, sbitmap **delete)
716 {
717 sbitmap *st_antin, *st_antout;
718 sbitmap *st_avout, *st_avin, *farthest;
719 sbitmap *nearer, *nearerout;
720 struct edge_list *edge_list;
721 int num_edges;
722
723 edge_list = create_edge_list ();
724 num_edges = NUM_EDGES (edge_list);
725
726 st_antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
727 st_antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
728 sbitmap_vector_zero (st_antin, last_basic_block);
729 sbitmap_vector_zero (st_antout, last_basic_block);
730 compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
731
732 /* Compute global anticipatability. */
733 st_avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
734 st_avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
735 compute_available (st_avloc, kill, st_avout, st_avin);
736
737 #ifdef LCM_DEBUG_INFO
738 if (dump_file)
739 {
740 fprintf (dump_file, "Edge List:\n");
741 verify_edge_list (dump_file, edge_list);
742 print_edge_list (dump_file, edge_list);
743 dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block);
744 dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
745 dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
746 dump_sbitmap_vector (dump_file, "st_antin", "", st_antin, last_basic_block);
747 dump_sbitmap_vector (dump_file, "st_antout", "", st_antout, last_basic_block);
748 dump_sbitmap_vector (dump_file, "st_kill", "", kill, last_basic_block);
749 }
750 #endif
751
752 #ifdef LCM_DEBUG_INFO
753 if (dump_file)
754 {
755 dump_sbitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block);
756 dump_sbitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block);
757 }
758 #endif
759
760 /* Compute farthestness. */
761 farthest = sbitmap_vector_alloc (num_edges, n_exprs);
762 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
763 kill, farthest);
764
765 #ifdef LCM_DEBUG_INFO
766 if (dump_file)
767 dump_sbitmap_vector (dump_file, "farthest", "", farthest, num_edges);
768 #endif
769
770 sbitmap_vector_free (st_antin);
771 sbitmap_vector_free (st_antout);
772
773 sbitmap_vector_free (st_avin);
774 sbitmap_vector_free (st_avout);
775
776 nearer = sbitmap_vector_alloc (num_edges, n_exprs);
777
778 /* Allocate an extra element for the entry block. */
779 nearerout = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
780 compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
781
782 #ifdef LCM_DEBUG_INFO
783 if (dump_file)
784 {
785 dump_sbitmap_vector (dump_file, "nearerout", "", nearerout,
786 last_basic_block + 1);
787 dump_sbitmap_vector (dump_file, "nearer", "", nearer, num_edges);
788 }
789 #endif
790
791 sbitmap_vector_free (farthest);
792
793 *insert = sbitmap_vector_alloc (num_edges, n_exprs);
794 *delete = sbitmap_vector_alloc (last_basic_block, n_exprs);
795 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
796 *insert, *delete);
797
798 sbitmap_vector_free (nearerout);
799 sbitmap_vector_free (nearer);
800
801 #ifdef LCM_DEBUG_INFO
802 if (dump_file)
803 {
804 dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
805 dump_sbitmap_vector (dump_file, "pre_delete_map", "", *delete,
806 last_basic_block);
807 }
808 #endif
809 return edge_list;
810 }
811
812