gcc/lcm.c

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