gcc/lcm.c

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