Mercurial > hg > CbC > CbC_gcc

comparison gcc/lcm.c @ 0:a06113de4d67

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