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, 2008,
   3    2010, 2011 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 "insn-config.h"
  61 #include "recog.h"
  62 #include "basic-block.h"
  63 #include "output.h"
  64 #include "tm_p.h"
  65 #include "function.h"
  66 #include "sbitmap.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 *del)
 354 {
 355   int x;
 356   basic_block bb;
 357
 358   FOR_EACH_BB (bb)
 359     sbitmap_difference (del[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 **del)
 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   *del = sbitmap_vector_alloc (last_basic_block, n_exprs);
 454   sbitmap_vector_zero (*insert, num_edges);
 455   sbitmap_vector_zero (*del, last_basic_block);
 456   compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del);
 457
 458   sbitmap_vector_free (laterin);
 459   sbitmap_vector_free (later);
 460
 461 #ifdef LCM_DEBUG_INFO
 462   if (dump_file)
 463     {
 464       dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
 465       dump_sbitmap_vector (dump_file, "pre_delete_map", "", *del,
 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 =
 489     XNEWVEC (basic_block, n_basic_blocks - NUM_FIXED_BLOCKS);
 490
 491   /* We want a maximal solution.  */
 492   sbitmap_vector_ones (avout, last_basic_block);
 493
 494   /* Put every block on the worklist; this is necessary because of the
 495      optimistic initialization of AVOUT above.  */
 496   FOR_EACH_BB (bb)
 497     {
 498       *qin++ = bb;
 499       bb->aux = bb;
 500     }
 501
 502   qin = worklist;
 503   qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
 504   qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
 505
 506   /* Mark blocks which are successors of the entry block so that we
 507      can easily identify them below.  */
 508   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 509     e->dest->aux = ENTRY_BLOCK_PTR;
 510
 511   /* Iterate until the worklist is empty.  */
 512   while (qlen)
 513     {
 514       /* Take the first entry off the worklist.  */
 515       bb = *qout++;
 516       qlen--;
 517
 518       if (qout >= qend)
 519         qout = worklist;
 520
 521       /* If one of the predecessor blocks is the ENTRY block, then the
 522          intersection of avouts is the null set.  We can identify such blocks
 523          by the special value in the AUX field in the block structure.  */
 524       if (bb->aux == ENTRY_BLOCK_PTR)
 525         /* Do not clear the aux field for blocks which are successors of the
 526            ENTRY block.  That way we never add then to the worklist again.  */
 527         sbitmap_zero (avin[bb->index]);
 528       else
 529         {
 530           /* Clear the aux field of this block so that it can be added to
 531              the worklist again if necessary.  */
 532           bb->aux = NULL;
 533           sbitmap_intersection_of_preds (avin[bb->index], avout, bb->index);
 534         }
 535
 536       if (sbitmap_union_of_diff_cg (avout[bb->index], avloc[bb->index],
 537                                     avin[bb->index], kill[bb->index]))
 538         /* If the out state of this block changed, then we need
 539            to add the successors of this block to the worklist
 540            if they are not already on the worklist.  */
 541         FOR_EACH_EDGE (e, ei, bb->succs)
 542           if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
 543             {
 544               *qin++ = e->dest;
 545               e->dest->aux = e;
 546               qlen++;
 547
 548               if (qin >= qend)
 549                 qin = worklist;
 550             }
 551     }
 552
 553   clear_aux_for_edges ();
 554   clear_aux_for_blocks ();
 555   free (worklist);
 556 }
 557
 558 /* Compute the farthest vector for edge based lcm.  */
 559
 560 static void
 561 compute_farthest (struct edge_list *edge_list, int n_exprs,
 562                   sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin,
 563                   sbitmap *kill, sbitmap *farthest)
 564 {
 565   sbitmap difference, temp_bitmap;
 566   int x, num_edges;
 567   basic_block pred, succ;
 568
 569   num_edges = NUM_EDGES (edge_list);
 570
 571   difference = sbitmap_alloc (n_exprs);
 572   temp_bitmap = sbitmap_alloc (n_exprs);
 573
 574   for (x = 0; x < num_edges; x++)
 575     {
 576       pred = INDEX_EDGE_PRED_BB (edge_list, x);
 577       succ = INDEX_EDGE_SUCC_BB (edge_list, x);
 578       if (succ == EXIT_BLOCK_PTR)
 579         sbitmap_copy (farthest[x], st_avout[pred->index]);
 580       else
 581         {
 582           if (pred == ENTRY_BLOCK_PTR)
 583             sbitmap_zero (farthest[x]);
 584           else
 585             {
 586               sbitmap_difference (difference, st_avout[pred->index],
 587                                   st_antin[succ->index]);
 588               sbitmap_not (temp_bitmap, st_avin[succ->index]);
 589               sbitmap_a_and_b_or_c (farthest[x], difference,
 590                                     kill[succ->index], temp_bitmap);
 591             }
 592         }
 593     }
 594
 595   sbitmap_free (temp_bitmap);
 596   sbitmap_free (difference);
 597 }
 598
 599 /* Compute nearer and nearerout vectors for edge based lcm.
 600
 601    This is the mirror of compute_laterin, additional comments on the
 602    implementation can be found before compute_laterin.  */
 603
 604 static void
 605 compute_nearerout (struct edge_list *edge_list, sbitmap *farthest,
 606                    sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout)
 607 {
 608   int num_edges, i;
 609   edge e;
 610   basic_block *worklist, *tos, bb;
 611   edge_iterator ei;
 612
 613   num_edges = NUM_EDGES (edge_list);
 614
 615   /* Allocate a worklist array/queue.  Entries are only added to the
 616      list if they were not already on the list.  So the size is
 617      bounded by the number of basic blocks.  */
 618   tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1);
 619
 620   /* Initialize NEARER for each edge and build a mapping from an edge to
 621      its index.  */
 622   for (i = 0; i < num_edges; i++)
 623     INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
 624
 625   /* We want a maximal solution.  */
 626   sbitmap_vector_ones (nearer, num_edges);
 627
 628   /* Note that even though we want an optimistic setting of NEARER, we
 629      do not want to be overly optimistic.  Consider an incoming edge to
 630      the exit block.  That edge should always have a NEARER value the
 631      same as FARTHEST for that edge.  */
 632   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 633     sbitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]);
 634
 635   /* Add all the blocks to the worklist.  This prevents an early exit
 636      from the loop given our optimistic initialization of NEARER.  */
 637   FOR_EACH_BB (bb)
 638     {
 639       *tos++ = bb;
 640       bb->aux = bb;
 641     }
 642
 643   /* Iterate until the worklist is empty.  */
 644   while (tos != worklist)
 645     {
 646       /* Take the first entry off the worklist.  */
 647       bb = *--tos;
 648       bb->aux = NULL;
 649
 650       /* Compute the intersection of NEARER for each outgoing edge from B.  */
 651       sbitmap_ones (nearerout[bb->index]);
 652       FOR_EACH_EDGE (e, ei, bb->succs)
 653         sbitmap_a_and_b (nearerout[bb->index], nearerout[bb->index],
 654                          nearer[(size_t) e->aux]);
 655
 656       /* Calculate NEARER for all incoming edges.  */
 657       FOR_EACH_EDGE (e, ei, bb->preds)
 658         if (sbitmap_union_of_diff_cg (nearer[(size_t) e->aux],
 659                                       farthest[(size_t) e->aux],
 660                                       nearerout[e->dest->index],
 661                                       st_avloc[e->dest->index])
 662             /* If NEARER for an incoming edge was changed, then we need
 663                to add the source of the incoming edge to the worklist.  */
 664             && e->src != ENTRY_BLOCK_PTR && e->src->aux == 0)
 665           {
 666             *tos++ = e->src;
 667             e->src->aux = e;
 668           }
 669     }
 670
 671   /* Computation of insertion and deletion points requires computing NEAREROUT
 672      for the ENTRY block.  We allocated an extra entry in the NEAREROUT array
 673      for just this purpose.  */
 674   sbitmap_ones (nearerout[last_basic_block]);
 675   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 676     sbitmap_a_and_b (nearerout[last_basic_block],
 677                      nearerout[last_basic_block],
 678                      nearer[(size_t) e->aux]);
 679
 680   clear_aux_for_edges ();
 681   free (tos);
 682 }
 683
 684 /* Compute the insertion and deletion points for edge based LCM.  */
 685
 686 static void
 687 compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc,
 688                            sbitmap *nearer, sbitmap *nearerout,
 689                            sbitmap *insert, sbitmap *del)
 690 {
 691   int x;
 692   basic_block bb;
 693
 694   FOR_EACH_BB (bb)
 695     sbitmap_difference (del[bb->index], st_avloc[bb->index],
 696                         nearerout[bb->index]);
 697
 698   for (x = 0; x < NUM_EDGES (edge_list); x++)
 699     {
 700       basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
 701       if (b == ENTRY_BLOCK_PTR)
 702         sbitmap_difference (insert[x], nearer[x], nearerout[last_basic_block]);
 703       else
 704         sbitmap_difference (insert[x], nearer[x], nearerout[b->index]);
 705     }
 706 }
 707
 708 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
 709    insert and delete vectors for edge based reverse LCM.  Returns an
 710    edgelist which is used to map the insert vector to what edge
 711    an expression should be inserted on.  */
 712
 713 struct edge_list *
 714 pre_edge_rev_lcm (int n_exprs, sbitmap *transp,
 715                   sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill,
 716                   sbitmap **insert, sbitmap **del)
 717 {
 718   sbitmap *st_antin, *st_antout;
 719   sbitmap *st_avout, *st_avin, *farthest;
 720   sbitmap *nearer, *nearerout;
 721   struct edge_list *edge_list;
 722   int num_edges;
 723
 724   edge_list = create_edge_list ();
 725   num_edges = NUM_EDGES (edge_list);
 726
 727   st_antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
 728   st_antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
 729   sbitmap_vector_zero (st_antin, last_basic_block);
 730   sbitmap_vector_zero (st_antout, last_basic_block);
 731   compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
 732
 733   /* Compute global anticipatability.  */
 734   st_avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
 735   st_avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
 736   compute_available (st_avloc, kill, st_avout, st_avin);
 737
 738 #ifdef LCM_DEBUG_INFO
 739   if (dump_file)
 740     {
 741       fprintf (dump_file, "Edge List:\n");
 742       verify_edge_list (dump_file, edge_list);
 743       print_edge_list (dump_file, edge_list);
 744       dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block);
 745       dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
 746       dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
 747       dump_sbitmap_vector (dump_file, "st_antin", "", st_antin, last_basic_block);
 748       dump_sbitmap_vector (dump_file, "st_antout", "", st_antout, last_basic_block);
 749       dump_sbitmap_vector (dump_file, "st_kill", "", kill, last_basic_block);
 750     }
 751 #endif
 752
 753 #ifdef LCM_DEBUG_INFO
 754   if (dump_file)
 755     {
 756       dump_sbitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block);
 757       dump_sbitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block);
 758     }
 759 #endif
 760
 761   /* Compute farthestness.  */
 762   farthest = sbitmap_vector_alloc (num_edges, n_exprs);
 763   compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
 764                     kill, farthest);
 765
 766 #ifdef LCM_DEBUG_INFO
 767   if (dump_file)
 768     dump_sbitmap_vector (dump_file, "farthest", "", farthest, num_edges);
 769 #endif
 770
 771   sbitmap_vector_free (st_antin);
 772   sbitmap_vector_free (st_antout);
 773
 774   sbitmap_vector_free (st_avin);
 775   sbitmap_vector_free (st_avout);
 776
 777   nearer = sbitmap_vector_alloc (num_edges, n_exprs);
 778
 779   /* Allocate an extra element for the entry block.  */
 780   nearerout = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
 781   compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
 782
 783 #ifdef LCM_DEBUG_INFO
 784   if (dump_file)
 785     {
 786       dump_sbitmap_vector (dump_file, "nearerout", "", nearerout,
 787                            last_basic_block + 1);
 788       dump_sbitmap_vector (dump_file, "nearer", "", nearer, num_edges);
 789     }
 790 #endif
 791
 792   sbitmap_vector_free (farthest);
 793
 794   *insert = sbitmap_vector_alloc (num_edges, n_exprs);
 795   *del = sbitmap_vector_alloc (last_basic_block, n_exprs);
 796   compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
 797                              *insert, *del);
 798
 799   sbitmap_vector_free (nearerout);
 800   sbitmap_vector_free (nearer);
 801
 802 #ifdef LCM_DEBUG_INFO
 803   if (dump_file)
 804     {
 805       dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
 806       dump_sbitmap_vector (dump_file, "pre_delete_map", "", *del,
 807                            last_basic_block);
 808     }
 809 #endif
 810   return edge_list;
 811 }
 812