OSDN Git Service

* lcm.c: Move all mode-switching related functions from here...
[pf3gnuchains/gcc-fork.git] / gcc / lcm.c
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, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, 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 \f
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
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 = xmalloc (sizeof (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];
126   qlen = n_basic_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
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
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     = xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
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. In fact the above allocation
298      of n_basic_blocks + 1 elements is not necessary.  */
299   qin = worklist;
300   qend = &worklist[n_basic_blocks];
301   qlen = n_basic_blocks;
302
303   /* Iterate until the worklist is empty.  */
304   while (qlen)
305     {
306       /* Take the first entry off the worklist.  */
307       bb = *qout++;
308       bb->aux = NULL;
309       qlen--;
310       if (qout >= qend)
311         qout = worklist;
312
313       /* Compute the intersection of LATERIN for each incoming edge to B.  */
314       sbitmap_ones (laterin[bb->index]);
315       FOR_EACH_EDGE (e, ei, bb->preds)
316         sbitmap_a_and_b (laterin[bb->index], laterin[bb->index],
317                          later[(size_t)e->aux]);
318
319       /* Calculate LATER for all outgoing edges.  */
320       FOR_EACH_EDGE (e, ei, bb->succs)
321         if (sbitmap_union_of_diff_cg (later[(size_t) e->aux],
322                                       earliest[(size_t) e->aux],
323                                       laterin[e->src->index],
324                                       antloc[e->src->index])
325             /* If LATER for an outgoing edge was changed, then we need
326                to add the target of the outgoing edge to the worklist.  */
327             && e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0)
328           {
329             *qin++ = e->dest;
330             e->dest->aux = e;
331             qlen++;
332             if (qin >= qend)
333               qin = worklist;
334           }
335     }
336
337   /* Computation of insertion and deletion points requires computing LATERIN
338      for the EXIT block.  We allocated an extra entry in the LATERIN array
339      for just this purpose.  */
340   sbitmap_ones (laterin[last_basic_block]);
341   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
342     sbitmap_a_and_b (laterin[last_basic_block],
343                      laterin[last_basic_block],
344                      later[(size_t) e->aux]);
345
346   clear_aux_for_edges ();
347   free (worklist);
348 }
349
350 /* Compute the insertion and deletion points for edge based LCM.  */
351
352 static void
353 compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc,
354                        sbitmap *later, sbitmap *laterin, sbitmap *insert,
355                        sbitmap *delete)
356 {
357   int x;
358   basic_block bb;
359
360   FOR_EACH_BB (bb)
361     sbitmap_difference (delete[bb->index], antloc[bb->index],
362                         laterin[bb->index]);
363
364   for (x = 0; x < NUM_EDGES (edge_list); x++)
365     {
366       basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
367
368       if (b == EXIT_BLOCK_PTR)
369         sbitmap_difference (insert[x], later[x], laterin[last_basic_block]);
370       else
371         sbitmap_difference (insert[x], later[x], laterin[b->index]);
372     }
373 }
374
375 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and
376    delete vectors for edge based LCM.  Returns an edgelist which is used to
377    map the insert vector to what edge an expression should be inserted on.  */
378
379 struct edge_list *
380 pre_edge_lcm (FILE *file ATTRIBUTE_UNUSED, int n_exprs, sbitmap *transp,
381               sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
382               sbitmap **insert, sbitmap **delete)
383 {
384   sbitmap *antin, *antout, *earliest;
385   sbitmap *avin, *avout;
386   sbitmap *later, *laterin;
387   struct edge_list *edge_list;
388   int num_edges;
389
390   edge_list = create_edge_list ();
391   num_edges = NUM_EDGES (edge_list);
392
393 #ifdef LCM_DEBUG_INFO
394   if (file)
395     {
396       fprintf (file, "Edge List:\n");
397       verify_edge_list (file, edge_list);
398       print_edge_list (file, edge_list);
399       dump_sbitmap_vector (file, "transp", "", transp, last_basic_block);
400       dump_sbitmap_vector (file, "antloc", "", antloc, last_basic_block);
401       dump_sbitmap_vector (file, "avloc", "", avloc, last_basic_block);
402       dump_sbitmap_vector (file, "kill", "", kill, last_basic_block);
403     }
404 #endif
405
406   /* Compute global availability.  */
407   avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
408   avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
409   compute_available (avloc, kill, avout, avin);
410   sbitmap_vector_free (avin);
411
412   /* Compute global anticipatability.  */
413   antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
414   antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
415   compute_antinout_edge (antloc, transp, antin, antout);
416
417 #ifdef LCM_DEBUG_INFO
418   if (file)
419     {
420       dump_sbitmap_vector (file, "antin", "", antin, last_basic_block);
421       dump_sbitmap_vector (file, "antout", "", antout, last_basic_block);
422     }
423 #endif
424
425   /* Compute earliestness.  */
426   earliest = sbitmap_vector_alloc (num_edges, n_exprs);
427   compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
428
429 #ifdef LCM_DEBUG_INFO
430   if (file)
431     dump_sbitmap_vector (file, "earliest", "", earliest, num_edges);
432 #endif
433
434   sbitmap_vector_free (antout);
435   sbitmap_vector_free (antin);
436   sbitmap_vector_free (avout);
437
438   later = sbitmap_vector_alloc (num_edges, n_exprs);
439
440   /* Allocate an extra element for the exit block in the laterin vector.  */
441   laterin = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
442   compute_laterin (edge_list, earliest, antloc, later, laterin);
443
444 #ifdef LCM_DEBUG_INFO
445   if (file)
446     {
447       dump_sbitmap_vector (file, "laterin", "", laterin, last_basic_block + 1);
448       dump_sbitmap_vector (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   *delete = sbitmap_vector_alloc (last_basic_block, n_exprs);
456   compute_insert_delete (edge_list, antloc, later, laterin, *insert, *delete);
457
458   sbitmap_vector_free (laterin);
459   sbitmap_vector_free (later);
460
461 #ifdef LCM_DEBUG_INFO
462   if (file)
463     {
464       dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
465       dump_sbitmap_vector (file, "pre_delete_map", "", *delete,
466                            last_basic_block);
467     }
468 #endif
469
470   return edge_list;
471 }
472
473 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
474    Return the number of passes we performed to iterate to a solution.  */
475
476 void
477 compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
478                    sbitmap *avin)
479 {
480   edge e;
481   basic_block *worklist, *qin, *qout, *qend, bb;
482   unsigned int qlen;
483   edge_iterator ei;
484
485   /* Allocate a worklist array/queue.  Entries are only added to the
486      list if they were not already on the list.  So the size is
487      bounded by the number of basic blocks.  */
488   qin = qout = worklist = xmalloc (sizeof (basic_block) * n_basic_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];
503   qlen = n_basic_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
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
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 = xmalloc (sizeof (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
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 *
713 pre_edge_rev_lcm (FILE *file ATTRIBUTE_UNUSED, 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 (file)
739     {
740       fprintf (file, "Edge List:\n");
741       verify_edge_list (file, edge_list);
742       print_edge_list (file, edge_list);
743       dump_sbitmap_vector (file, "transp", "", transp, last_basic_block);
744       dump_sbitmap_vector (file, "st_avloc", "", st_avloc, last_basic_block);
745       dump_sbitmap_vector (file, "st_antloc", "", st_antloc, last_basic_block);
746       dump_sbitmap_vector (file, "st_antin", "", st_antin, last_basic_block);
747       dump_sbitmap_vector (file, "st_antout", "", st_antout, last_basic_block);
748       dump_sbitmap_vector (file, "st_kill", "", kill, last_basic_block);
749     }
750 #endif
751
752 #ifdef LCM_DEBUG_INFO
753   if (file)
754     {
755       dump_sbitmap_vector (file, "st_avout", "", st_avout, last_basic_block);
756       dump_sbitmap_vector (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 (file)
767     dump_sbitmap_vector (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 (file)
784     {
785       dump_sbitmap_vector (file, "nearerout", "", nearerout,
786                            last_basic_block + 1);
787       dump_sbitmap_vector (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 (file)
803     {
804       dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
805       dump_sbitmap_vector (file, "pre_delete_map", "", *delete,
806                            last_basic_block);
807     }
808 #endif
809   return edge_list;
810 }
811