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;
 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 ATTRIBUTE_UNUSED;
 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
 415   sbitmap_zero (avin[0]);
 416   sbitmap_copy (avout[0] /*dst*/, avloc[0] /*src*/);
 417
 418   for (bb = 1; bb < n_basic_blocks; bb++)
 419     sbitmap_not (avout[bb], kill[bb]);
 420
 421   passes = 0;
 422   changed = 1;
 423   while (changed)
 424     {
 425       changed = 0;
 426       for (bb = 1; bb < n_basic_blocks; bb++)
 427         {
 428           sbitmap_intersection_of_preds (avin[bb], avout, bb);
 429           changed |= sbitmap_union_of_diff (avout[bb], avloc[bb],
 430                                             avin[bb], kill[bb]);
 431         }
 432       passes++;
 433     }
 434   return passes;
 435 }
 436
 437 /* Compute the farthest vector for edge based lcm.  */
 438 static void
 439 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
 440                   kill, farthest)
 441      struct edge_list *edge_list;
 442      int n_exprs;
 443      sbitmap *st_avout, *st_avin, *st_antin, *kill, *farthest;
 444 {
 445   sbitmap difference, temp_bitmap;
 446   int x, num_edges;
 447   basic_block pred, succ;
 448
 449   num_edges = NUM_EDGES (edge_list);
 450
 451   difference = sbitmap_alloc (n_exprs);
 452   temp_bitmap = sbitmap_alloc (n_exprs);
 453
 454   for (x = 0; x < num_edges; x++)
 455     {
 456       pred = INDEX_EDGE_PRED_BB (edge_list, x);
 457       succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 458       if (succ == EXIT_BLOCK_PTR)
 459         sbitmap_copy (farthest[x], st_avout[pred->index]);
 460       else
 461         {
 462           if (pred == ENTRY_BLOCK_PTR)
 463             {
 464               sbitmap_zero (farthest[x]);
 465             }
 466           else
 467             {
 468               sbitmap_difference (difference, st_avout[pred->index],
 469                                   st_antin[succ->index]);
 470               sbitmap_not (temp_bitmap, st_avin[succ->index]);
 471               sbitmap_a_and_b_or_c (farthest[x], difference,
 472                                     kill[succ->index], temp_bitmap);
 473             }
 474         }
 475     }
 476   free (temp_bitmap);
 477   free (difference);
 478 }
 479
 480 /* Compute nearer and nearerout vectors for edge based lcm.  */
 481 static void
 482 compute_nearerout (edge_list, n_exprs,
 483                    farthest, st_avloc, nearer, nearerout)
 484      struct edge_list *edge_list;
 485      int n_exprs;
 486      sbitmap *farthest, *st_avloc, *nearer, *nearerout;
 487 {
 488   sbitmap difference;
 489   int x, num_edges;
 490   basic_block pred, succ;
 491   int done = 0;
 492
 493   num_edges = NUM_EDGES (edge_list);
 494
 495   /* nearout has an extra block allocated for the entry block.  */
 496   sbitmap_vector_ones (nearerout, n_basic_blocks + 1);
 497   sbitmap_vector_zero (nearer, num_edges);
 498
 499   /* Initialize nearerout to the intersection of FARTHEST for all edges
 500      from predecessors to this block. */
 501
 502   for (x = 0; x < num_edges; x++)
 503     {
 504       succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 505       pred = INDEX_EDGE_PRED_BB (edge_list, x);
 506       if (pred != ENTRY_BLOCK_PTR)
 507         {
 508           sbitmap_a_and_b (nearerout[pred->index], nearerout[pred->index],
 509                            farthest[x]);
 510         }
 511       /* We already know the correct value of nearer for edges to
 512          the exit node.  */
 513       if (succ == EXIT_BLOCK_PTR)
 514         sbitmap_copy (nearer[x], farthest[x]);
 515     }
 516
 517   difference = sbitmap_alloc (n_exprs);
 518
 519   while (!done)
 520     {
 521       done = 1;
 522       for (x = 0; x < num_edges; x++)
 523         {
 524           succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 525           if (succ != EXIT_BLOCK_PTR)
 526             {
 527               sbitmap_difference (difference, nearerout[succ->index],
 528                                   st_avloc[succ->index]);
 529               if (sbitmap_a_or_b (nearer[x], difference, farthest[x]))
 530                 done = 0;
 531             }
 532         }
 533
 534       if (done)
 535         break;
 536
 537       sbitmap_vector_zero (nearerout, n_basic_blocks);
 538
 539       for (x = 0; x < num_edges; x++)
 540         {
 541           pred = INDEX_EDGE_PRED_BB (edge_list, x);
 542           if (pred != ENTRY_BLOCK_PTR)
 543               sbitmap_a_and_b (nearerout[pred->index],
 544                                nearerout[pred->index], nearer[x]);
 545             else
 546               sbitmap_a_and_b (nearerout[n_basic_blocks],
 547                                nearerout[n_basic_blocks], nearer[x]);
 548         }
 549     }
 550
 551   free (difference);
 552 }
 553
 554 /* Compute the insertion and deletion points for edge based LCM.  */
 555 static void
 556 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
 557                            insert, delete)
 558      struct edge_list *edge_list;
 559      sbitmap *st_avloc, *nearer, *nearerout, *insert, *delete;
 560 {
 561   int x;
 562
 563   for (x = 0; x < n_basic_blocks; x++)
 564     sbitmap_difference (delete[x], st_avloc[x], nearerout[x]);
 565
 566   for (x = 0; x < NUM_EDGES (edge_list); x++)
 567     {
 568       basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
 569       if (b == ENTRY_BLOCK_PTR)
 570         sbitmap_difference (insert[x], nearer[x], nearerout[n_basic_blocks]);
 571       else
 572         sbitmap_difference (insert[x], nearer[x], nearerout[b->index]);
 573     }
 574 }
 575
 576 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
 577    insert and delete vectors for edge based reverse LCM.  Returns an
 578    edgelist which is used to map the insert vector to what edge
 579    an expression should be inserted on.  */
 580
 581 struct edge_list *
 582 pre_edge_rev_lcm (file, n_exprs, transp, st_avloc, st_antloc, kill,
 583                   insert, delete)
 584      FILE *file ATTRIBUTE_UNUSED;
 585      int n_exprs;
 586      sbitmap *transp;
 587      sbitmap *st_avloc;
 588      sbitmap *st_antloc;
 589      sbitmap *kill;
 590      sbitmap **insert;
 591      sbitmap **delete;
 592 {
 593   sbitmap *st_antin, *st_antout;
 594   sbitmap *st_avout, *st_avin, *farthest;
 595   sbitmap *nearer, *nearerout;
 596   struct edge_list *edge_list;
 597   int num_edges;
 598
 599   edge_list = create_edge_list ();
 600   num_edges = NUM_EDGES (edge_list);
 601
 602   st_antin = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 603   st_antout = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 604   sbitmap_vector_zero (st_antin, n_basic_blocks);
 605   sbitmap_vector_zero (st_antout, n_basic_blocks);
 606   compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
 607
 608   /* Compute global anticipatability.  */
 609   st_avout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 610   st_avin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 611   compute_available (st_avloc, kill, st_avout, st_avin);
 612
 613 #ifdef LCM_DEBUG_INFO
 614   if (file)
 615     {
 616       fprintf (file, "Edge List:\n");
 617       verify_edge_list (file, edge_list);
 618       print_edge_list (file, edge_list);
 619       dump_sbitmap_vector (file, "transp", "", transp, n_basic_blocks);
 620       dump_sbitmap_vector (file, "st_avloc", "", st_avloc, n_basic_blocks);
 621       dump_sbitmap_vector (file, "st_antloc", "", st_antloc, n_basic_blocks);
 622       dump_sbitmap_vector (file, "st_antin", "", st_antin, n_basic_blocks);
 623       dump_sbitmap_vector (file, "st_antout", "", st_antout, n_basic_blocks);
 624       dump_sbitmap_vector (file, "st_kill", "", kill, n_basic_blocks);
 625     }
 626 #endif
 627
 628 #ifdef LCM_DEBUG_INFO
 629   if (file)
 630     {
 631       dump_sbitmap_vector (file, "st_avout", "", st_avout, n_basic_blocks);
 632       dump_sbitmap_vector (file, "st_avin", "", st_avin, n_basic_blocks);
 633     }
 634 #endif
 635
 636   /* Compute farthestness.  */
 637   farthest = sbitmap_vector_alloc (num_edges, n_exprs);
 638   compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
 639                     kill, farthest);
 640
 641 #ifdef LCM_DEBUG_INFO
 642   if (file)
 643     dump_sbitmap_vector (file, "farthest", "", farthest, num_edges);
 644 #endif
 645
 646   free (st_avin);
 647   free (st_avout);
 648
 649   nearer = sbitmap_vector_alloc (num_edges, n_exprs);
 650   /* Allocate an extra element for the entry block.  */
 651   nearerout = sbitmap_vector_alloc (n_basic_blocks + 1, n_exprs);
 652   compute_nearerout (edge_list, n_exprs, farthest, st_avloc, nearer, nearerout);
 653
 654 #ifdef LCM_DEBUG_INFO
 655   if (file)
 656     {
 657       dump_sbitmap_vector (file, "nearerout", "", nearerout,
 658                            n_basic_blocks + 1);
 659       dump_sbitmap_vector (file, "nearer", "", nearer, num_edges);
 660     }
 661 #endif
 662
 663   free (farthest);
 664
 665   *insert = sbitmap_vector_alloc (num_edges, n_exprs);
 666   *delete = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
 667   compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout, *insert, *delete);
 668
 669   free (nearerout);
 670   free (nearer);
 671
 672 #ifdef LCM_DEBUG_INFO
 673   if (file)
 674     {
 675       dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
 676       dump_sbitmap_vector (file, "pre_delete_map", "", *delete, n_basic_blocks);
 677     }
 678 #endif
 679
 680   return edge_list;
 681 }