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   /* Add all the blocks to the worklist.  This prevents an early exit from
 273      the loop given our optimistic initialization of LATER above.  */
 274   for (bb = n_basic_blocks - 1; bb >= 0; bb--)
 275     {
 276       basic_block b = BASIC_BLOCK (bb);
 277       *tos++ = b;
 278       b->aux = b;
 279     }
 280
 281   /* Iterate until the worklist is empty.  */
 282   while (tos != worklist)
 283     {
 284       /* Take the first entry off the worklist.  */
 285       basic_block b = *--tos;
 286       b->aux = NULL;
 287
 288       /* Compute the intersection of LATERIN for each incoming edge to B.  */
 289       bb = b->index;
 290       sbitmap_ones (laterin[bb]);
 291       for (e = b->pred; e != NULL; e = e->pred_next)
 292         sbitmap_a_and_b (laterin[bb], laterin[bb], later[(int)e->aux]);
 293
 294       /* Calculate LATER for all outgoing edges.  */
 295       for (e = b->succ; e != NULL; e = e->succ_next)
 296         {
 297           if (sbitmap_union_of_diff (later[(int)e->aux],
 298                                      earliest[(int)e->aux],
 299                                      laterin[e->src->index],
 300                                      antloc[e->src->index]))
 301             {
 302               /* If LATER for an outgoing edge was changed, then we need
 303                  to add the target of the outgoing edge to the worklist.  */
 304               if (e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0)
 305                 {
 306                   *tos++ = e->dest;
 307                   e->dest->aux = e;
 308                 }
 309             }
 310         }
 311     }
 312
 313   /* Computation of insertion and deletion points requires computing LATERIN
 314      for the EXIT block.  We allocated an extra entry in the LATERIN array
 315      for just this purpose.  */
 316   sbitmap_ones (laterin[n_basic_blocks]);
 317   for (e = EXIT_BLOCK_PTR->pred; e != NULL; e = e->pred_next)
 318     sbitmap_a_and_b (laterin[n_basic_blocks],
 319                      laterin[n_basic_blocks],
 320                      later[(int)e->aux]);
 321
 322   free (tos);
 323 }
 324
 325 /* Compute the insertion and deletion points for edge based LCM.  */
 326 static void
 327 compute_insert_delete (edge_list, antloc, later, laterin,
 328                        insert, delete)
 329      struct edge_list *edge_list;
 330      sbitmap *antloc, *later, *laterin, *insert, *delete;
 331 {
 332   int x;
 333
 334   for (x = 0; x < n_basic_blocks; x++)
 335     sbitmap_difference (delete[x], antloc[x], laterin[x]);
 336
 337   for (x = 0; x < NUM_EDGES (edge_list); x++)
 338     {
 339       basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
 340       if (b == EXIT_BLOCK_PTR)
 341         sbitmap_difference (insert[x], later[x], laterin[n_basic_blocks]);
 342       else
 343         sbitmap_difference (insert[x], later[x], laterin[b->index]);
 344     }
 345 }
 346
 347 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the
 348    insert and delete vectors for edge based LCM.  Returns an
 349    edgelist which is used to map the insert vector to what edge
 350    an expression should be inserted on.  */
 351
 352 struct edge_list *
 353 pre_edge_lcm (file, n_exprs, transp, avloc, antloc, kill, insert, delete)
 354      FILE *file ATTRIBUTE_UNUSED;
 355      int n_exprs;
 356      sbitmap *transp;
 357      sbitmap *avloc;
 358      sbitmap *antloc;
 359      sbitmap *kill;
 360      sbitmap **insert;
 361      sbitmap **delete;
 362 {
 363   sbitmap *antin, *antout, *earliest;
 364   sbitmap *avin, *avout;
 365   sbitmap *later, *laterin;
 366   struct edge_list *edge_list;
 367   int num_edges;
 368
 369   edge_list = create_edge_list ();
 370   num_edges = NUM_EDGES (edge_list);
 371
 372 #ifdef LCM_DEBUG_INFO
 373   if (file)
 374     {
 375       fprintf (file, "Edge List:\n");
 376       verify_edge_list (file, edge_list);
 377       print_edge_list (file, edge_list);
 378       dump_sbitmap_vector (file, "transp", "", transp, n_basic_blocks);
 379       dump_sbitmap_vector (file, "antloc", "", antloc, n_basic_blocks);
 380       dump_sbitmap_vector (file, "avloc", "", avloc, n_basic_blocks);
 381       dump_sbitmap_vector (file, "kill", "", kill, n_basic_blocks);
 382     }
 383 #endif
 384
 385   /* Compute global availability.  */
 386   avin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 387   avout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 388   compute_available (avloc, kill, avout, avin);
 389
 390
 391   free (avin);
 392
 393   /* Compute global anticipatability.  */
 394   antin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 395   antout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 396   compute_antinout_edge (antloc, transp, antin, antout);
 397
 398 #ifdef LCM_DEBUG_INFO
 399   if (file)
 400     {
 401       dump_sbitmap_vector (file, "antin", "", antin, n_basic_blocks);
 402       dump_sbitmap_vector (file, "antout", "", antout, n_basic_blocks);
 403     }
 404 #endif
 405
 406   /* Compute earliestness.  */
 407   earliest = sbitmap_vector_alloc (num_edges, n_exprs);
 408   compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
 409
 410 #ifdef LCM_DEBUG_INFO
 411   if (file)
 412     dump_sbitmap_vector (file, "earliest", "", earliest, num_edges);
 413 #endif
 414
 415   free (antout);
 416   free (antin);
 417   free (avout);
 418
 419   later = sbitmap_vector_alloc (num_edges, n_exprs);
 420   /* Allocate an extra element for the exit block in the laterin vector.  */
 421   laterin = sbitmap_vector_alloc (n_basic_blocks + 1, n_exprs);
 422   compute_laterin (edge_list, earliest, antloc, later, laterin);
 423
 424
 425 #ifdef LCM_DEBUG_INFO
 426   if (file)
 427     {
 428       dump_sbitmap_vector (file, "laterin", "", laterin, n_basic_blocks + 1);
 429       dump_sbitmap_vector (file, "later", "", later, num_edges);
 430     }
 431 #endif
 432
 433   free (earliest);
 434
 435   *insert = sbitmap_vector_alloc (num_edges, n_exprs);
 436   *delete = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 437   compute_insert_delete (edge_list, antloc, later, laterin, *insert, *delete);
 438
 439   free (laterin);
 440   free (later);
 441
 442 #ifdef LCM_DEBUG_INFO
 443   if (file)
 444     {
 445       dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
 446       dump_sbitmap_vector (file, "pre_delete_map", "", *delete, n_basic_blocks);
 447     }
 448 #endif
 449
 450   return edge_list;
 451 }
 452
 453 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
 454    Return the number of passes we performed to iterate to a solution.  */
 455 void
 456 compute_available (avloc, kill, avout, avin)
 457      sbitmap *avloc, *kill, *avout, *avin;
 458 {
 459   int bb;
 460   edge e;
 461   basic_block *worklist, *tos;
 462
 463   /* Allocate a worklist array/queue.  Entries are only added to the
 464      list if they were not already on the list.  So the size is
 465      bounded by the number of basic blocks.  */
 466   tos = worklist = (basic_block *) xmalloc (sizeof (basic_block)
 467                                             * n_basic_blocks);
 468
 469   /* We want a maximal solution.  */
 470   sbitmap_vector_ones (avout, n_basic_blocks);
 471
 472   /* Put every block on the worklist; this is necessary because of the
 473      optimistic initialization of AVOUT above.  */
 474   for (bb = n_basic_blocks - 1; bb >= 0; bb--)
 475     {
 476       *tos++ = BASIC_BLOCK (bb);
 477       BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
 478     }
 479
 480   /* Mark blocks which are successors of the entry block so that we
 481      can easily identify them below.  */
 482   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 483     e->dest->aux = ENTRY_BLOCK_PTR;
 484
 485   /* Iterate until the worklist is empty.  */
 486   while (tos != worklist)
 487     {
 488       /* Take the first entry off the worklist.  */
 489       basic_block b = *--tos;
 490       bb = b->index;
 491
 492       /* If one of the predecessor blocks is the ENTRY block, then the
 493          intersection of avouts is the null set.  We can identify such blocks
 494          by the special value in the AUX field in the block structure.  */
 495       if (b->aux == ENTRY_BLOCK_PTR)
 496         {
 497           /* Do not clear the aux field for blocks which are
 498              successors of the ENTRY block.  That way we never
 499              add then to the worklist again.  */
 500           sbitmap_zero (avin[bb]);
 501         }
 502       else
 503         {
 504           /* Clear the aux field of this block so that it can be added to
 505              the worklist again if necessary.  */
 506           b->aux = NULL;
 507           sbitmap_intersection_of_preds (avin[bb], avout, bb);
 508         }
 509
 510       if (sbitmap_union_of_diff (avout[bb], avloc[bb], avin[bb], kill[bb]))
 511         {
 512           /* If the out state of this block changed, then we need
 513              to add the successors of this block to the worklist
 514              if they are not already on the worklist.  */
 515           for (e = b->succ; e; e = e->succ_next)
 516             {
 517               if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
 518                 {
 519                   *tos++ = e->dest;
 520                   e->dest->aux = e;
 521                 }
 522             }
 523         }
 524     }
 525   free (tos);
 526 }
 527
 528 /* Compute the farthest vector for edge based lcm.  */
 529 static void
 530 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
 531                   kill, farthest)
 532      struct edge_list *edge_list;
 533      int n_exprs;
 534      sbitmap *st_avout, *st_avin, *st_antin, *kill, *farthest;
 535 {
 536   sbitmap difference, temp_bitmap;
 537   int x, num_edges;
 538   basic_block pred, succ;
 539
 540   num_edges = NUM_EDGES (edge_list);
 541
 542   difference = sbitmap_alloc (n_exprs);
 543   temp_bitmap = sbitmap_alloc (n_exprs);
 544
 545   for (x = 0; x < num_edges; x++)
 546     {
 547       pred = INDEX_EDGE_PRED_BB (edge_list, x);
 548       succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 549       if (succ == EXIT_BLOCK_PTR)
 550         sbitmap_copy (farthest[x], st_avout[pred->index]);
 551       else
 552         {
 553           if (pred == ENTRY_BLOCK_PTR)
 554             {
 555               sbitmap_zero (farthest[x]);
 556             }
 557           else
 558             {
 559               sbitmap_difference (difference, st_avout[pred->index],
 560                                   st_antin[succ->index]);
 561               sbitmap_not (temp_bitmap, st_avin[succ->index]);
 562               sbitmap_a_and_b_or_c (farthest[x], difference,
 563                                     kill[succ->index], temp_bitmap);
 564             }
 565         }
 566     }
 567   free (temp_bitmap);
 568   free (difference);
 569 }
 570
 571 /* Compute nearer and nearerout vectors for edge based lcm.
 572
 573    This is the mirror of compute_laterin, additional comments on the
 574    implementation can be found before compute_laterin.  */
 575
 576 static void
 577 compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout)
 578      struct edge_list *edge_list;
 579      sbitmap *farthest, *st_avloc, *nearer, *nearerout;
 580 {
 581   int bb, num_edges, i;
 582   edge e;
 583   basic_block *worklist, *tos;
 584
 585   num_edges = NUM_EDGES (edge_list);
 586
 587   /* Allocate a worklist array/queue.  Entries are only added to the
 588      list if they were not already on the list.  So the size is
 589      bounded by the number of basic blocks.  */
 590   tos = worklist = (basic_block *) xmalloc (sizeof (basic_block)
 591                                             * (n_basic_blocks + 1));
 592
 593   /* Initialize NEARER for each edge and build a mapping from an edge to
 594      its index.  */
 595   for (i = 0; i < num_edges; i++)
 596     INDEX_EDGE (edge_list, i)->aux = (void *)i;
 597
 598   /* We want a maximal solution.  */
 599   sbitmap_vector_ones (nearer, num_edges);
 600
 601   /* Add all the blocks to the worklist.  This prevents an early exit
 602      from the loop given our optimistic initialization of NEARER.  */
 603   for (bb = 0; bb < n_basic_blocks; bb++)
 604     {
 605       basic_block b = BASIC_BLOCK (bb);
 606       *tos++ = b;
 607       b->aux = b;
 608     }
 609
 610   /* Iterate until the worklist is empty.  */
 611   while (tos != worklist)
 612     {
 613       /* Take the first entry off the worklist.  */
 614       basic_block b = *--tos;
 615       b->aux = NULL;
 616
 617       /* Compute the intersection of NEARER for each outgoing edge from B.  */
 618       bb = b->index;
 619       sbitmap_ones (nearerout[bb]);
 620       for (e = b->succ; e != NULL; e = e->succ_next)
 621         sbitmap_a_and_b (nearerout[bb], nearerout[bb], nearer[(int)e->aux]);
 622
 623       /* Calculate NEARER for all incoming edges.  */
 624       for (e = b->pred; e != NULL; e = e->pred_next)
 625         {
 626           if (sbitmap_union_of_diff (nearer[(int)e->aux],
 627                                      farthest[(int)e->aux],
 628                                      nearerout[e->dest->index],
 629                                      st_avloc[e->dest->index]))
 630             {
 631               /* If NEARER for an incoming edge was changed, then we need
 632                  to add the source of the incoming edge to the worklist.  */
 633               if (e->src != ENTRY_BLOCK_PTR && e->src->aux == 0)
 634                 {
 635                   *tos++ = e->src;
 636                   e->src->aux = e;
 637                 }
 638             }
 639         }
 640     }
 641
 642   /* Computation of insertion and deletion points requires computing NEAREROUT
 643      for the ENTRY block.  We allocated an extra entry in the NEAREROUT array
 644      for just this purpose.  */
 645   sbitmap_ones (nearerout[n_basic_blocks]);
 646   for (e = ENTRY_BLOCK_PTR->succ; e != NULL; e = e->succ_next)
 647     sbitmap_a_and_b (nearerout[n_basic_blocks],
 648                      nearerout[n_basic_blocks],
 649                      nearer[(int)e->aux]);
 650
 651   free (tos);
 652 }
 653
 654 /* Compute the insertion and deletion points for edge based LCM.  */
 655 static void
 656 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
 657                            insert, delete)
 658      struct edge_list *edge_list;
 659      sbitmap *st_avloc, *nearer, *nearerout, *insert, *delete;
 660 {
 661   int x;
 662
 663   for (x = 0; x < n_basic_blocks; x++)
 664     sbitmap_difference (delete[x], st_avloc[x], nearerout[x]);
 665
 666   for (x = 0; x < NUM_EDGES (edge_list); x++)
 667     {
 668       basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
 669       if (b == ENTRY_BLOCK_PTR)
 670         sbitmap_difference (insert[x], nearer[x], nearerout[n_basic_blocks]);
 671       else
 672         sbitmap_difference (insert[x], nearer[x], nearerout[b->index]);
 673     }
 674 }
 675
 676 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
 677    insert and delete vectors for edge based reverse LCM.  Returns an
 678    edgelist which is used to map the insert vector to what edge
 679    an expression should be inserted on.  */
 680
 681 struct edge_list *
 682 pre_edge_rev_lcm (file, n_exprs, transp, st_avloc, st_antloc, kill,
 683                   insert, delete)
 684      FILE *file ATTRIBUTE_UNUSED;
 685      int n_exprs;
 686      sbitmap *transp;
 687      sbitmap *st_avloc;
 688      sbitmap *st_antloc;
 689      sbitmap *kill;
 690      sbitmap **insert;
 691      sbitmap **delete;
 692 {
 693   sbitmap *st_antin, *st_antout;
 694   sbitmap *st_avout, *st_avin, *farthest;
 695   sbitmap *nearer, *nearerout;
 696   struct edge_list *edge_list;
 697   int num_edges;
 698
 699   edge_list = create_edge_list ();
 700   num_edges = NUM_EDGES (edge_list);
 701
 702   st_antin = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 703   st_antout = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 704   sbitmap_vector_zero (st_antin, n_basic_blocks);
 705   sbitmap_vector_zero (st_antout, n_basic_blocks);
 706   compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
 707
 708   /* Compute global anticipatability.  */
 709   st_avout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 710   st_avin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 711   compute_available (st_avloc, kill, st_avout, st_avin);
 712
 713 #ifdef LCM_DEBUG_INFO
 714   if (file)
 715     {
 716       fprintf (file, "Edge List:\n");
 717       verify_edge_list (file, edge_list);
 718       print_edge_list (file, edge_list);
 719       dump_sbitmap_vector (file, "transp", "", transp, n_basic_blocks);
 720       dump_sbitmap_vector (file, "st_avloc", "", st_avloc, n_basic_blocks);
 721       dump_sbitmap_vector (file, "st_antloc", "", st_antloc, n_basic_blocks);
 722       dump_sbitmap_vector (file, "st_antin", "", st_antin, n_basic_blocks);
 723       dump_sbitmap_vector (file, "st_antout", "", st_antout, n_basic_blocks);
 724       dump_sbitmap_vector (file, "st_kill", "", kill, n_basic_blocks);
 725     }
 726 #endif
 727
 728 #ifdef LCM_DEBUG_INFO
 729   if (file)
 730     {
 731       dump_sbitmap_vector (file, "st_avout", "", st_avout, n_basic_blocks);
 732       dump_sbitmap_vector (file, "st_avin", "", st_avin, n_basic_blocks);
 733     }
 734 #endif
 735
 736   /* Compute farthestness.  */
 737   farthest = sbitmap_vector_alloc (num_edges, n_exprs);
 738   compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
 739                     kill, farthest);
 740
 741 #ifdef LCM_DEBUG_INFO
 742   if (file)
 743     dump_sbitmap_vector (file, "farthest", "", farthest, num_edges);
 744 #endif
 745
 746   free (st_avin);
 747   free (st_avout);
 748
 749   nearer = sbitmap_vector_alloc (num_edges, n_exprs);
 750   /* Allocate an extra element for the entry block.  */
 751   nearerout = sbitmap_vector_alloc (n_basic_blocks + 1, n_exprs);
 752   compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
 753
 754 #ifdef LCM_DEBUG_INFO
 755   if (file)
 756     {
 757       dump_sbitmap_vector (file, "nearerout", "", nearerout,
 758                            n_basic_blocks + 1);
 759       dump_sbitmap_vector (file, "nearer", "", nearer, num_edges);
 760     }
 761 #endif
 762
 763   free (farthest);
 764
 765   *insert = sbitmap_vector_alloc (num_edges, n_exprs);
 766   *delete = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 767   compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout, *insert, *delete);
 768
 769   free (nearerout);
 770   free (nearer);
 771
 772 #ifdef LCM_DEBUG_INFO
 773   if (file)
 774     {
 775       dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
 776       dump_sbitmap_vector (file, "pre_delete_map", "", *delete, n_basic_blocks);
 777     }
 778 #endif
 779
 780   return edge_list;
 781 }