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 *, int, 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 *, int, 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 i, changed, passes;
 102   sbitmap old_changed, new_changed;
 103   edge e;
 104
 105   sbitmap_vector_zero (antout, n_basic_blocks);
 106   sbitmap_vector_ones (antin, n_basic_blocks);
 107
 108   old_changed = sbitmap_alloc (n_basic_blocks);
 109   new_changed = sbitmap_alloc (n_basic_blocks);
 110   sbitmap_ones (old_changed);
 111
 112   passes = 0;
 113   changed = 1;
 114   while (changed)
 115     {
 116       changed = 0;
 117       sbitmap_zero (new_changed);
 118
 119       /* We scan the blocks in the reverse order to speed up
 120          the convergence.  */
 121       for (i = n_basic_blocks - 1; i >= 0; i--)
 122         {
 123           basic_block bb = BASIC_BLOCK (i);
 124           /* If none of the successors of this block have changed,
 125              then this block is not going to change.  */
 126           for (e = bb->succ ; e; e = e->succ_next)
 127             {
 128               if (e->dest == EXIT_BLOCK_PTR)
 129                 break;
 130
 131               if (TEST_BIT (old_changed, e->dest->index)
 132                   || TEST_BIT (new_changed, e->dest->index))
 133                 break;
 134             }
 135
 136           if (!e)
 137             continue;
 138
 139           /* If an Exit blocks is the ONLY successor, its has a zero ANTIN,
 140              which is the opposite of the default definition for an
 141              intersection of succs definition.  */
 142           if (e->dest == EXIT_BLOCK_PTR && e->succ_next == NULL
 143               && e->src->succ == e)
 144             sbitmap_zero (antout[bb->index]);
 145           else
 146             {
 147               sbitmap_intersection_of_succs (antout[bb->index],
 148                                              antin,
 149                                              bb->index);
 150             }
 151
 152           if (sbitmap_a_or_b_and_c (antin[bb->index], antloc[bb->index],
 153                                     transp[bb->index], antout[bb->index]))
 154             {
 155               changed = 1;
 156               SET_BIT (new_changed, bb->index);
 157             }
 158         }
 159       sbitmap_copy (old_changed, new_changed);
 160       passes++;
 161     }
 162
 163   free (old_changed);
 164   free (new_changed);
 165 }
 166
 167 /* Compute the earliest vector for edge based lcm.  */
 168 static void
 169 compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest)
 170      struct edge_list *edge_list;
 171      int n_exprs;
 172      sbitmap *antin, *antout, *avout, *kill, *earliest;
 173 {
 174   sbitmap difference, temp_bitmap;
 175   int x, num_edges;
 176   basic_block pred, succ;
 177
 178   num_edges = NUM_EDGES (edge_list);
 179
 180   difference = sbitmap_alloc (n_exprs);
 181   temp_bitmap = sbitmap_alloc (n_exprs);
 182
 183   for (x = 0; x < num_edges; x++)
 184     {
 185       pred = INDEX_EDGE_PRED_BB (edge_list, x);
 186       succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 187       if (pred == ENTRY_BLOCK_PTR)
 188         sbitmap_copy (earliest[x], antin[succ->index]);
 189       else
 190         {
 191           if (succ == EXIT_BLOCK_PTR)
 192             {
 193               sbitmap_zero (earliest[x]);
 194             }
 195           else
 196             {
 197               sbitmap_difference (difference, antin[succ->index],
 198                                   avout[pred->index]);
 199               sbitmap_not (temp_bitmap, antout[pred->index]);
 200               sbitmap_a_and_b_or_c (earliest[x], difference, kill[pred->index],
 201                                     temp_bitmap);
 202             }
 203         }
 204     }
 205   free (temp_bitmap);
 206   free (difference);
 207 }
 208
 209 /* Compute later and laterin vectors for edge based lcm.  */
 210 static void
 211 compute_laterin (edge_list, n_exprs,
 212                  earliest, antloc, later, laterin)
 213      struct edge_list *edge_list;
 214      int n_exprs;
 215      sbitmap *earliest, *antloc, *later, *laterin;
 216 {
 217   sbitmap difference, temp_bitmap;
 218   int x, num_edges;
 219   basic_block pred, succ;
 220   int done = 0;
 221
 222   num_edges = NUM_EDGES (edge_list);
 223
 224   /* Laterin has an extra block allocated for the exit block.  */
 225   sbitmap_vector_ones (laterin, n_basic_blocks + 1);
 226   sbitmap_vector_zero (later, num_edges);
 227
 228   /* Initialize laterin to the intersection of EARLIEST for all edges
 229      from predecessors to this block. */
 230
 231   for (x = 0; x < num_edges; x++)
 232     {
 233       succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 234       pred = INDEX_EDGE_PRED_BB (edge_list, x);
 235       if (succ != EXIT_BLOCK_PTR)
 236         sbitmap_a_and_b (laterin[succ->index], laterin[succ->index],
 237                          earliest[x]);
 238       /* We already know the correct value of later for edges from
 239          the entry node, so set it now.  */
 240       if (pred == ENTRY_BLOCK_PTR)
 241         sbitmap_copy (later[x], earliest[x]);
 242     }
 243
 244   difference = sbitmap_alloc (n_exprs);
 245
 246   while (!done)
 247     {
 248       done = 1;
 249       for (x = 0; x < num_edges; x++)
 250         {
 251           pred = INDEX_EDGE_PRED_BB (edge_list, x);
 252           if (pred != ENTRY_BLOCK_PTR)
 253             {
 254               sbitmap_difference (difference, laterin[pred->index],
 255                                   antloc[pred->index]);
 256               if (sbitmap_a_or_b (later[x], difference, earliest[x]))
 257                 done = 0;
 258             }
 259         }
 260       if (done)
 261         break;
 262
 263       sbitmap_vector_ones (laterin, n_basic_blocks);
 264
 265       for (x = 0; x < num_edges; x++)
 266         {
 267           succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 268           if (succ != EXIT_BLOCK_PTR)
 269             sbitmap_a_and_b (laterin[succ->index], laterin[succ->index],
 270                              later[x]);
 271           else
 272             /* We allocated an extra block for the exit node.  */
 273             sbitmap_a_and_b (laterin[n_basic_blocks], laterin[n_basic_blocks],
 274                              later[x]);
 275         }
 276     }
 277
 278   free (difference);
 279 }
 280
 281 /* Compute the insertion and deletion points for edge based LCM.  */
 282 static void
 283 compute_insert_delete (edge_list, antloc, later, laterin,
 284                        insert, delete)
 285      struct edge_list *edge_list;
 286      sbitmap *antloc, *later, *laterin, *insert, *delete;
 287 {
 288   int x;
 289
 290   for (x = 0; x < n_basic_blocks; x++)
 291     sbitmap_difference (delete[x], antloc[x], laterin[x]);
 292
 293   for (x = 0; x < NUM_EDGES (edge_list); x++)
 294     {
 295       basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
 296       if (b == EXIT_BLOCK_PTR)
 297         sbitmap_difference (insert[x], later[x], laterin[n_basic_blocks]);
 298       else
 299         sbitmap_difference (insert[x], later[x], laterin[b->index]);
 300     }
 301 }
 302
 303 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the
 304    insert and delete vectors for edge based LCM.  Returns an
 305    edgelist which is used to map the insert vector to what edge
 306    an expression should be inserted on.  */
 307
 308 struct edge_list *
 309 pre_edge_lcm (file, n_exprs, transp, avloc, antloc, kill, insert, delete)
 310      FILE *file;
 311      int n_exprs;
 312      sbitmap *transp;
 313      sbitmap *avloc;
 314      sbitmap *antloc;
 315      sbitmap *kill;
 316      sbitmap **insert;
 317      sbitmap **delete;
 318 {
 319   sbitmap *antin, *antout, *earliest;
 320   sbitmap *avin, *avout;
 321   sbitmap *later, *laterin;
 322   struct edge_list *edge_list;
 323   int num_edges;
 324
 325   edge_list = create_edge_list ();
 326   num_edges = NUM_EDGES (edge_list);
 327
 328 #ifdef LCM_DEBUG_INFO
 329   if (file)
 330     {
 331       fprintf (file, "Edge List:\n");
 332       verify_edge_list (file, edge_list);
 333       print_edge_list (file, edge_list);
 334       dump_sbitmap_vector (file, "transp", "", transp, n_basic_blocks);
 335       dump_sbitmap_vector (file, "antloc", "", antloc, n_basic_blocks);
 336       dump_sbitmap_vector (file, "avloc", "", avloc, n_basic_blocks);
 337       dump_sbitmap_vector (file, "kill", "", kill, n_basic_blocks);
 338     }
 339 #endif
 340
 341   /* Compute global availability.  */
 342   avin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 343   avout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 344   compute_available (avloc, kill, avout, avin);
 345
 346   free (avin);
 347
 348   /* Compute global anticipatability.  */
 349   antin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 350   antout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 351   compute_antinout_edge (antloc, transp, antin, antout);
 352
 353 #ifdef LCM_DEBUG_INFO
 354   if (file)
 355     {
 356       dump_sbitmap_vector (file, "antin", "", antin, n_basic_blocks);
 357       dump_sbitmap_vector (file, "antout", "", antout, n_basic_blocks);
 358     }
 359 #endif
 360
 361   /* Compute earliestness.  */
 362   earliest = sbitmap_vector_alloc (num_edges, n_exprs);
 363   compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
 364
 365 #ifdef LCM_DEBUG_INFO
 366   if (file)
 367     dump_sbitmap_vector (file, "earliest", "", earliest, num_edges);
 368 #endif
 369
 370   free (antout);
 371   free (antin);
 372   free (avout);
 373
 374   later = sbitmap_vector_alloc (num_edges, n_exprs);
 375   /* Allocate an extra element for the exit block in the laterin vector.  */
 376   laterin = sbitmap_vector_alloc (n_basic_blocks + 1, n_exprs);
 377   compute_laterin (edge_list, n_exprs, earliest, antloc, later, laterin);
 378
 379 #ifdef LCM_DEBUG_INFO
 380   if (file)
 381     {
 382       dump_sbitmap_vector (file, "laterin", "", laterin, n_basic_blocks + 1);
 383       dump_sbitmap_vector (file, "later", "", later, num_edges);
 384     }
 385 #endif
 386
 387   free (earliest);
 388
 389   *insert = sbitmap_vector_alloc (num_edges, n_exprs);
 390   *delete = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 391   compute_insert_delete (edge_list, antloc, later, laterin, *insert, *delete);
 392
 393   free (laterin);
 394   free (later);
 395
 396 #ifdef LCM_DEBUG_INFO
 397   if (file)
 398     {
 399       dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
 400       dump_sbitmap_vector (file, "pre_delete_map", "", *delete, n_basic_blocks);
 401     }
 402 #endif
 403
 404   return edge_list;
 405 }
 406
 407 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
 408    Return the number of passes we performed to iterate to a solution.  */
 409 int
 410 compute_available (avloc, kill, avout, avin)
 411      sbitmap *avloc, *kill, *avout, *avin;
 412 {
 413   int bb, changed, passes;
 414   int last = n_basic_blocks - 1;
 415
 416   sbitmap_zero (avin[0]);
 417   sbitmap_copy (avout[0] /*dst*/, avloc[0] /*src*/);
 418
 419   for (bb = 1; bb < n_basic_blocks; bb++)
 420     sbitmap_not (avout[bb], kill[bb]);
 421
 422   passes = 0;
 423   changed = 1;
 424   while (changed)
 425     {
 426       changed = 0;
 427       for (bb = 1; bb < n_basic_blocks; bb++)
 428         {
 429           sbitmap_intersection_of_preds (avin[bb], avout, bb);
 430           changed |= sbitmap_union_of_diff (avout[bb], avloc[bb],
 431                                             avin[bb], kill[bb]);
 432         }
 433       passes++;
 434     }
 435   return passes;
 436 }
 437
 438 /* Compute the farthest vector for edge based lcm.  */
 439 static void
 440 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
 441                   kill, farthest)
 442      struct edge_list *edge_list;
 443      int n_exprs;
 444      sbitmap *st_avout, *st_avin, *st_antin, *kill, *farthest;
 445 {
 446   sbitmap difference, temp_bitmap;
 447   int x, num_edges;
 448   basic_block pred, succ;
 449
 450   num_edges = NUM_EDGES (edge_list);
 451
 452   difference = sbitmap_alloc (n_exprs);
 453   temp_bitmap = sbitmap_alloc (n_exprs);
 454
 455   for (x = 0; x < num_edges; x++)
 456     {
 457       pred = INDEX_EDGE_PRED_BB (edge_list, x);
 458       succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 459       if (succ == EXIT_BLOCK_PTR)
 460         sbitmap_copy (farthest[x], st_avout[pred->index]);
 461       else
 462         {
 463           if (pred == ENTRY_BLOCK_PTR)
 464             {
 465               sbitmap_zero (farthest[x]);
 466             }
 467           else
 468             {
 469               sbitmap_difference (difference, st_avout[pred->index],
 470                                   st_antin[succ->index]);
 471               sbitmap_not (temp_bitmap, st_avin[succ->index]);
 472               sbitmap_a_and_b_or_c (farthest[x], difference,
 473                                     kill[succ->index], temp_bitmap);
 474             }
 475         }
 476     }
 477   free (temp_bitmap);
 478   free (difference);
 479 }
 480
 481 /* Compute nearer and nearerout vectors for edge based lcm.  */
 482 static void
 483 compute_nearerout (edge_list, n_exprs,
 484                    farthest, st_avloc, nearer, nearerout)
 485      struct edge_list *edge_list;
 486      int n_exprs;
 487      sbitmap *farthest, *st_avloc, *nearer, *nearerout;
 488 {
 489   sbitmap difference, temp_bitmap;
 490   int x, num_edges;
 491   basic_block pred, succ;
 492   int done = 0;
 493
 494   num_edges = NUM_EDGES (edge_list);
 495
 496   /* nearout has an extra block allocated for the entry block.  */
 497   sbitmap_vector_ones (nearerout, n_basic_blocks + 1);
 498   sbitmap_vector_zero (nearer, num_edges);
 499
 500   /* Initialize nearerout to the intersection of FARTHEST for all edges
 501      from predecessors to this block. */
 502
 503   for (x = 0; x < num_edges; x++)
 504     {
 505       succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 506       pred = INDEX_EDGE_PRED_BB (edge_list, x);
 507       if (pred != ENTRY_BLOCK_PTR)
 508         {
 509           sbitmap_a_and_b (nearerout[pred->index], nearerout[pred->index],
 510                            farthest[x]);
 511         }
 512       /* We already know the correct value of nearer for edges to
 513          the exit node.  */
 514       if (succ == EXIT_BLOCK_PTR)
 515         sbitmap_copy (nearer[x], farthest[x]);
 516     }
 517
 518   difference = sbitmap_alloc (n_exprs);
 519
 520   while (!done)
 521     {
 522       done = 1;
 523       for (x = 0; x < num_edges; x++)
 524         {
 525           succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 526           if (succ != EXIT_BLOCK_PTR)
 527             {
 528               sbitmap_difference (difference, nearerout[succ->index],
 529                                   st_avloc[succ->index]);
 530               if (sbitmap_a_or_b (nearer[x], difference, farthest[x]))
 531                 done = 0;
 532             }
 533         }
 534
 535       if (done)
 536         break;
 537
 538       sbitmap_vector_zero (nearerout, n_basic_blocks);
 539
 540       for (x = 0; x < num_edges; x++)
 541         {
 542           pred = INDEX_EDGE_PRED_BB (edge_list, x);
 543           if (pred != ENTRY_BLOCK_PTR)
 544               sbitmap_a_and_b (nearerout[pred->index],
 545                                nearerout[pred->index], nearer[x]);
 546             else
 547               sbitmap_a_and_b (nearerout[n_basic_blocks],
 548                                nearerout[n_basic_blocks], nearer[x]);
 549         }
 550     }
 551
 552   free (difference);
 553 }
 554
 555 /* Compute the insertion and deletion points for edge based LCM.  */
 556 static void
 557 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
 558                            insert, delete)
 559      struct edge_list *edge_list;
 560      sbitmap *st_avloc, *nearer, *nearerout, *insert, *delete;
 561 {
 562   int x;
 563
 564   for (x = 0; x < n_basic_blocks; x++)
 565     sbitmap_difference (delete[x], st_avloc[x], nearerout[x]);
 566
 567   for (x = 0; x < NUM_EDGES (edge_list); x++)
 568     {
 569       basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
 570       if (b == ENTRY_BLOCK_PTR)
 571         sbitmap_difference (insert[x], nearer[x], nearerout[n_basic_blocks]);
 572       else
 573         sbitmap_difference (insert[x], nearer[x], nearerout[b->index]);
 574     }
 575 }
 576
 577 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
 578    insert and delete vectors for edge based reverse LCM.  Returns an
 579    edgelist which is used to map the insert vector to what edge
 580    an expression should be inserted on.  */
 581
 582 struct edge_list *
 583 pre_edge_rev_lcm (file, n_exprs, transp, st_avloc, st_antloc, kill,
 584                   insert, delete)
 585      FILE *file;
 586      int n_exprs;
 587      sbitmap *transp;
 588      sbitmap *st_avloc;
 589      sbitmap *st_antloc;
 590      sbitmap *kill;
 591      sbitmap **insert;
 592      sbitmap **delete;
 593 {
 594   sbitmap *st_antin, *st_antout;
 595   sbitmap *st_avout, *st_avin, *farthest;
 596   sbitmap *nearer, *nearerout;
 597   struct edge_list *edge_list;
 598   int x,num_edges;
 599
 600   edge_list = create_edge_list ();
 601   num_edges = NUM_EDGES (edge_list);
 602
 603   st_antin = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 604   st_antout = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 605   sbitmap_vector_zero (st_antin, n_basic_blocks);
 606   sbitmap_vector_zero (st_antout, n_basic_blocks);
 607   compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
 608
 609   /* Compute global anticipatability.  */
 610   st_avout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 611   st_avin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 612   compute_available (st_avloc, kill, st_avout, st_avin);
 613
 614 #ifdef LCM_DEBUG_INFO
 615   if (file)
 616     {
 617       fprintf (file, "Edge List:\n");
 618       verify_edge_list (file, edge_list);
 619       print_edge_list (file, edge_list);
 620       dump_sbitmap_vector (file, "transp", "", transp, n_basic_blocks);
 621       dump_sbitmap_vector (file, "st_avloc", "", st_avloc, n_basic_blocks);
 622       dump_sbitmap_vector (file, "st_antloc", "", st_antloc, n_basic_blocks);
 623       dump_sbitmap_vector (file, "st_antin", "", st_antin, n_basic_blocks);
 624       dump_sbitmap_vector (file, "st_antout", "", st_antout, n_basic_blocks);
 625       dump_sbitmap_vector (file, "st_kill", "", kill, n_basic_blocks);
 626     }
 627 #endif
 628
 629 #ifdef LCM_DEBUG_INFO
 630   if (file)
 631     {
 632       dump_sbitmap_vector (file, "st_avout", "", st_avout, n_basic_blocks);
 633       dump_sbitmap_vector (file, "st_avin", "", st_avin, n_basic_blocks);
 634     }
 635 #endif
 636
 637   /* Compute farthestness.  */
 638   farthest = sbitmap_vector_alloc (num_edges, n_exprs);
 639   compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
 640                     kill, farthest);
 641
 642 #ifdef LCM_DEBUG_INFO
 643   if (file)
 644     dump_sbitmap_vector (file, "farthest", "", farthest, num_edges);
 645 #endif
 646
 647   free (st_avin);
 648   free (st_avout);
 649
 650   nearer = sbitmap_vector_alloc (num_edges, n_exprs);
 651   /* Allocate an extra element for the entry block.  */
 652   nearerout = sbitmap_vector_alloc (n_basic_blocks + 1, n_exprs);
 653   compute_nearerout (edge_list, n_exprs, farthest, st_avloc, nearer, nearerout);
 654
 655 #ifdef LCM_DEBUG_INFO
 656   if (file)
 657     {
 658       dump_sbitmap_vector (file, "nearerout", "", nearerout,
 659                            n_basic_blocks + 1);
 660       dump_sbitmap_vector (file, "nearer", "", nearer, num_edges);
 661     }
 662 #endif
 663
 664   free (farthest);
 665
 666   *insert = sbitmap_vector_alloc (num_edges, n_exprs);
 667   *delete = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 668   compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout, *insert, *delete);
 669
 670   free (nearerout);
 671   free (nearer);
 672
 673 #ifdef LCM_DEBUG_INFO
 674   if (file)
 675     {
 676       dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
 677       dump_sbitmap_vector (file, "pre_delete_map", "", *delete, n_basic_blocks);
 678     }
 679 #endif
 680
 681   return edge_list;
 682 }