gcc/lcm.c

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