gcc/lcm.c

   1 /* Generic partial redundancy elimination with lazy code motion
   2    support.
   3    Copyright (C) 1998, 1999, 2000 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  PARAMS ((sbitmap *, sbitmap *,
  67                                            sbitmap *, sbitmap *));
  68 static void compute_earliest  PARAMS ((struct edge_list *, int, sbitmap *,
  69                                      sbitmap *, sbitmap *, sbitmap *,
  70                                      sbitmap *));
  71 static void compute_laterin  PARAMS ((struct edge_list *, sbitmap *,
  72                                     sbitmap *, sbitmap *, sbitmap *));
  73 static void compute_insert_delete  PARAMS ((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    PARAMS ((struct edge_list *, int, sbitmap *,
  79                                          sbitmap *, sbitmap*, sbitmap *,
  80                                          sbitmap *));
  81 static void compute_nearerout   PARAMS ((struct edge_list *, sbitmap *,
  82                                        sbitmap *, sbitmap *, sbitmap *));
  83 static void compute_rev_insert_delete  PARAMS ((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 *) (size_t) 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[(size_t)e->aux], earliest[(size_t)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[(size_t)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[(size_t) e->aux],
 305                                      earliest[(size_t) 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[(size_t) 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 *) (size_t) 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[(size_t)e->aux], farthest[(size_t)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],
 636                          nearer[(size_t) e->aux]);
 637
 638       /* Calculate NEARER for all incoming edges.  */
 639       for (e = b->pred; e != NULL; e = e->pred_next)
 640         {
 641           if (sbitmap_union_of_diff (nearer[(size_t) e->aux],
 642                                      farthest[(size_t) e->aux],
 643                                      nearerout[e->dest->index],
 644                                      st_avloc[e->dest->index]))
 645             {
 646               /* If NEARER for an incoming edge was changed, then we need
 647                  to add the source of the incoming edge to the worklist.  */
 648               if (e->src != ENTRY_BLOCK_PTR && e->src->aux == 0)
 649                 {
 650                   *tos++ = e->src;
 651                   e->src->aux = e;
 652                 }
 653             }
 654         }
 655     }
 656
 657   /* Computation of insertion and deletion points requires computing NEAREROUT
 658      for the ENTRY block.  We allocated an extra entry in the NEAREROUT array
 659      for just this purpose.  */
 660   sbitmap_ones (nearerout[n_basic_blocks]);
 661   for (e = ENTRY_BLOCK_PTR->succ; e != NULL; e = e->succ_next)
 662     sbitmap_a_and_b (nearerout[n_basic_blocks],
 663                      nearerout[n_basic_blocks],
 664                      nearer[(size_t) e->aux]);
 665
 666   free (tos);
 667 }
 668
 669 /* Compute the insertion and deletion points for edge based LCM.  */
 670 static void
 671 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
 672                            insert, delete)
 673      struct edge_list *edge_list;
 674      sbitmap *st_avloc, *nearer, *nearerout, *insert, *delete;
 675 {
 676   int x;
 677
 678   for (x = 0; x < n_basic_blocks; x++)
 679     sbitmap_difference (delete[x], st_avloc[x], nearerout[x]);
 680
 681   for (x = 0; x < NUM_EDGES (edge_list); x++)
 682     {
 683       basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
 684       if (b == ENTRY_BLOCK_PTR)
 685         sbitmap_difference (insert[x], nearer[x], nearerout[n_basic_blocks]);
 686       else
 687         sbitmap_difference (insert[x], nearer[x], nearerout[b->index]);
 688     }
 689 }
 690
 691 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
 692    insert and delete vectors for edge based reverse LCM.  Returns an
 693    edgelist which is used to map the insert vector to what edge
 694    an expression should be inserted on.  */
 695
 696 struct edge_list *
 697 pre_edge_rev_lcm (file, n_exprs, transp, st_avloc, st_antloc, kill,
 698                   insert, delete)
 699      FILE *file ATTRIBUTE_UNUSED;
 700      int n_exprs;
 701      sbitmap *transp;
 702      sbitmap *st_avloc;
 703      sbitmap *st_antloc;
 704      sbitmap *kill;
 705      sbitmap **insert;
 706      sbitmap **delete;
 707 {
 708   sbitmap *st_antin, *st_antout;
 709   sbitmap *st_avout, *st_avin, *farthest;
 710   sbitmap *nearer, *nearerout;
 711   struct edge_list *edge_list;
 712   int num_edges;
 713
 714   edge_list = create_edge_list ();
 715   num_edges = NUM_EDGES (edge_list);
 716
 717   st_antin = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 718   st_antout = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 719   sbitmap_vector_zero (st_antin, n_basic_blocks);
 720   sbitmap_vector_zero (st_antout, n_basic_blocks);
 721   compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
 722
 723   /* Compute global anticipatability.  */
 724   st_avout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 725   st_avin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 726   compute_available (st_avloc, kill, st_avout, st_avin);
 727
 728 #ifdef LCM_DEBUG_INFO
 729   if (file)
 730     {
 731       fprintf (file, "Edge List:\n");
 732       verify_edge_list (file, edge_list);
 733       print_edge_list (file, edge_list);
 734       dump_sbitmap_vector (file, "transp", "", transp, n_basic_blocks);
 735       dump_sbitmap_vector (file, "st_avloc", "", st_avloc, n_basic_blocks);
 736       dump_sbitmap_vector (file, "st_antloc", "", st_antloc, n_basic_blocks);
 737       dump_sbitmap_vector (file, "st_antin", "", st_antin, n_basic_blocks);
 738       dump_sbitmap_vector (file, "st_antout", "", st_antout, n_basic_blocks);
 739       dump_sbitmap_vector (file, "st_kill", "", kill, n_basic_blocks);
 740     }
 741 #endif
 742
 743 #ifdef LCM_DEBUG_INFO
 744   if (file)
 745     {
 746       dump_sbitmap_vector (file, "st_avout", "", st_avout, n_basic_blocks);
 747       dump_sbitmap_vector (file, "st_avin", "", st_avin, n_basic_blocks);
 748     }
 749 #endif
 750
 751   /* Compute farthestness.  */
 752   farthest = sbitmap_vector_alloc (num_edges, n_exprs);
 753   compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
 754                     kill, farthest);
 755
 756 #ifdef LCM_DEBUG_INFO
 757   if (file)
 758     dump_sbitmap_vector (file, "farthest", "", farthest, num_edges);
 759 #endif
 760
 761   free (st_avin);
 762   free (st_avout);
 763
 764   nearer = sbitmap_vector_alloc (num_edges, n_exprs);
 765   /* Allocate an extra element for the entry block.  */
 766   nearerout = sbitmap_vector_alloc (n_basic_blocks + 1, n_exprs);
 767   compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
 768
 769 #ifdef LCM_DEBUG_INFO
 770   if (file)
 771     {
 772       dump_sbitmap_vector (file, "nearerout", "", nearerout,
 773                            n_basic_blocks + 1);
 774       dump_sbitmap_vector (file, "nearer", "", nearer, num_edges);
 775     }
 776 #endif
 777
 778   free (farthest);
 779
 780   *insert = sbitmap_vector_alloc (num_edges, n_exprs);
 781   *delete = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 782   compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout, *insert, *delete);
 783
 784   free (nearerout);
 785   free (nearer);
 786
 787 #ifdef LCM_DEBUG_INFO
 788   if (file)
 789     {
 790       dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
 791       dump_sbitmap_vector (file, "pre_delete_map", "", *delete, n_basic_blocks);
 792     }
 793 #endif
 794
 795   return edge_list;
 796 }