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 - NUM_FIXED_BLOCKS];
 126   qlen = n_basic_blocks - NUM_FIXED_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);
 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. */
 298   qin = worklist;
 299   qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
 300   qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
 301
 302   /* Iterate until the worklist is empty.  */
 303   while (qlen)
 304     {
 305       /* Take the first entry off the worklist.  */
 306       bb = *qout++;
 307       bb->aux = NULL;
 308       qlen--;
 309       if (qout >= qend)
 310         qout = worklist;
 311
 312       /* Compute the intersection of LATERIN for each incoming edge to B.  */
 313       sbitmap_ones (laterin[bb->index]);
 314       FOR_EACH_EDGE (e, ei, bb->preds)
 315         sbitmap_a_and_b (laterin[bb->index], laterin[bb->index],
 316                          later[(size_t)e->aux]);
 317
 318       /* Calculate LATER for all outgoing edges.  */
 319       FOR_EACH_EDGE (e, ei, bb->succs)
 320         if (sbitmap_union_of_diff_cg (later[(size_t) e->aux],
 321                                       earliest[(size_t) e->aux],
 322                                       laterin[e->src->index],
 323                                       antloc[e->src->index])
 324             /* If LATER for an outgoing edge was changed, then we need
 325                to add the target of the outgoing edge to the worklist.  */
 326             && e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0)
 327           {
 328             *qin++ = e->dest;
 329             e->dest->aux = e;
 330             qlen++;
 331             if (qin >= qend)
 332               qin = worklist;
 333           }
 334     }
 335
 336   /* Computation of insertion and deletion points requires computing LATERIN
 337      for the EXIT block.  We allocated an extra entry in the LATERIN array
 338      for just this purpose.  */
 339   sbitmap_ones (laterin[last_basic_block]);
 340   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 341     sbitmap_a_and_b (laterin[last_basic_block],
 342                      laterin[last_basic_block],
 343                      later[(size_t) e->aux]);
 344
 345   clear_aux_for_edges ();
 346   free (worklist);
 347 }
 348
 349 /* Compute the insertion and deletion points for edge based LCM.  */
 350
 351 static void
 352 compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc,
 353                        sbitmap *later, sbitmap *laterin, sbitmap *insert,
 354                        sbitmap *delete)
 355 {
 356   int x;
 357   basic_block bb;
 358
 359   FOR_EACH_BB (bb)
 360     sbitmap_difference (delete[bb->index], antloc[bb->index],
 361                         laterin[bb->index]);
 362
 363   for (x = 0; x < NUM_EDGES (edge_list); x++)
 364     {
 365       basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
 366
 367       if (b == EXIT_BLOCK_PTR)
 368         sbitmap_difference (insert[x], later[x], laterin[last_basic_block]);
 369       else
 370         sbitmap_difference (insert[x], later[x], laterin[b->index]);
 371     }
 372 }
 373
 374 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and
 375    delete vectors for edge based LCM.  Returns an edgelist which is used to
 376    map the insert vector to what edge an expression should be inserted on.  */
 377
 378 struct edge_list *
 379 pre_edge_lcm (FILE *file ATTRIBUTE_UNUSED, int n_exprs, sbitmap *transp,
 380               sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
 381               sbitmap **insert, sbitmap **delete)
 382 {
 383   sbitmap *antin, *antout, *earliest;
 384   sbitmap *avin, *avout;
 385   sbitmap *later, *laterin;
 386   struct edge_list *edge_list;
 387   int num_edges;
 388
 389   edge_list = create_edge_list ();
 390   num_edges = NUM_EDGES (edge_list);
 391
 392 #ifdef LCM_DEBUG_INFO
 393   if (file)
 394     {
 395       fprintf (file, "Edge List:\n");
 396       verify_edge_list (file, edge_list);
 397       print_edge_list (file, edge_list);
 398       dump_sbitmap_vector (file, "transp", "", transp, last_basic_block);
 399       dump_sbitmap_vector (file, "antloc", "", antloc, last_basic_block);
 400       dump_sbitmap_vector (file, "avloc", "", avloc, last_basic_block);
 401       dump_sbitmap_vector (file, "kill", "", kill, last_basic_block);
 402     }
 403 #endif
 404
 405   /* Compute global availability.  */
 406   avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
 407   avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
 408   compute_available (avloc, kill, avout, avin);
 409   sbitmap_vector_free (avin);
 410
 411   /* Compute global anticipatability.  */
 412   antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
 413   antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
 414   compute_antinout_edge (antloc, transp, antin, antout);
 415
 416 #ifdef LCM_DEBUG_INFO
 417   if (file)
 418     {
 419       dump_sbitmap_vector (file, "antin", "", antin, last_basic_block);
 420       dump_sbitmap_vector (file, "antout", "", antout, last_basic_block);
 421     }
 422 #endif
 423
 424   /* Compute earliestness.  */
 425   earliest = sbitmap_vector_alloc (num_edges, n_exprs);
 426   compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
 427
 428 #ifdef LCM_DEBUG_INFO
 429   if (file)
 430     dump_sbitmap_vector (file, "earliest", "", earliest, num_edges);
 431 #endif
 432
 433   sbitmap_vector_free (antout);
 434   sbitmap_vector_free (antin);
 435   sbitmap_vector_free (avout);
 436
 437   later = sbitmap_vector_alloc (num_edges, n_exprs);
 438
 439   /* Allocate an extra element for the exit block in the laterin vector.  */
 440   laterin = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
 441   compute_laterin (edge_list, earliest, antloc, later, laterin);
 442
 443 #ifdef LCM_DEBUG_INFO
 444   if (file)
 445     {
 446       dump_sbitmap_vector (file, "laterin", "", laterin, last_basic_block + 1);
 447       dump_sbitmap_vector (file, "later", "", later, num_edges);
 448     }
 449 #endif
 450
 451   sbitmap_vector_free (earliest);
 452
 453   *insert = sbitmap_vector_alloc (num_edges, n_exprs);
 454   *delete = sbitmap_vector_alloc (last_basic_block, n_exprs);
 455   compute_insert_delete (edge_list, antloc, later, laterin, *insert, *delete);
 456
 457   sbitmap_vector_free (laterin);
 458   sbitmap_vector_free (later);
 459
 460 #ifdef LCM_DEBUG_INFO
 461   if (file)
 462     {
 463       dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges);
 464       dump_sbitmap_vector (file, "pre_delete_map", "", *delete,
 465                            last_basic_block);
 466     }
 467 #endif
 468
 469   return edge_list;
 470 }
 471
 472 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
 473    Return the number of passes we performed to iterate to a solution.  */
 474
 475 void
 476 compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
 477                    sbitmap *avin)
 478 {
 479   edge e;
 480   basic_block *worklist, *qin, *qout, *qend, bb;
 481   unsigned int qlen;
 482   edge_iterator ei;
 483
 484   /* Allocate a worklist array/queue.  Entries are only added to the
 485      list if they were not already on the list.  So the size is
 486      bounded by the number of basic blocks.  */
 487   qin = qout = worklist =
 488     xmalloc (sizeof (basic_block) * (n_basic_blocks - NUM_FIXED_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 - NUM_FIXED_BLOCKS];
 503   qlen = n_basic_blocks - NUM_FIXED_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