gcc/lcm.c

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