contrib/gcc/lcm.c

   1 /* Generic partial redundancy elimination with lazy code motion
   2    support.
   3    Copyright (C) 1998 Free Software Foundation, Inc.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 /* These routines are meant to be used by various optimization
  23    passes which can be modeled as lazy code motion problems.
  24    Including, but not limited to:
  25
  26         * Traditional partial redundancy elimination.
  27
  28         * Placement of caller/caller register save/restores.
  29
  30         * Load/store motion.
  31
  32         * Copy motion.
  33
  34         * Conversion of flat register files to a stacked register
  35         model.
  36
  37         * Dead load/store elimination.
  38
  39   These routines accept as input:
  40
  41         * Basic block information (number of blocks, lists of
  42         predecessors and successors).  Note the granularity
  43         does not need to be basic block, they could be statements
  44         or functions.
  45
  46         * Bitmaps of local properties (computed, transparent and
  47         anticipatable expressions).
  48
  49   The output of these routines is bitmap of redundant computations
  50   and a bitmap of optimal placement points.  */
  51
  52
  53 #include "config.h"
  54 #include "system.h"
  55
  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
  65 static void compute_antinout    PROTO ((int, int_list_ptr *, sbitmap *,
  66                                         sbitmap *, sbitmap *, sbitmap *));
  67 static void compute_earlyinout  PROTO ((int, int, int_list_ptr *, sbitmap *,
  68                                         sbitmap *, sbitmap *, sbitmap *));
  69 static void compute_delayinout  PROTO ((int, int, int_list_ptr *, sbitmap *,
  70                                         sbitmap *, sbitmap *,
  71                                         sbitmap *, sbitmap *));
  72 static void compute_latein      PROTO ((int, int, int_list_ptr *, sbitmap *,
  73                                         sbitmap *, sbitmap *));
  74 static void compute_isoinout    PROTO ((int, int_list_ptr *, sbitmap *,
  75                                         sbitmap *, sbitmap *, sbitmap *));
  76 static void compute_optimal     PROTO ((int, sbitmap *,
  77                                         sbitmap *, sbitmap *));
  78 static void compute_redundant   PROTO ((int, int, sbitmap *,
  79                                         sbitmap *, sbitmap *, sbitmap *));
  80
  81 /* Similarly, but for the reversed flowgraph.  */
  82 static void compute_avinout     PROTO ((int, int_list_ptr *, sbitmap *,
  83                                         sbitmap *, sbitmap *, sbitmap *));
  84 static void compute_fartherinout        PROTO ((int, int, int_list_ptr *,
  85                                                 sbitmap *, sbitmap *,
  86                                                 sbitmap *, sbitmap *));
  87 static void compute_earlierinout  PROTO ((int, int, int_list_ptr *, sbitmap *,
  88                                           sbitmap *, sbitmap *,
  89                                           sbitmap *, sbitmap *));
  90 static void compute_firstout    PROTO ((int, int, int_list_ptr *, sbitmap *,
  91                                         sbitmap *, sbitmap *));
  92 static void compute_rev_isoinout PROTO ((int, int_list_ptr *, sbitmap *,
  93                                          sbitmap *, sbitmap *, sbitmap *));
  94
  95 /* Given local properties TRANSP, ANTLOC, return the redundant and optimal
  96    computation points for expressions.
  97
  98    To reduce overall memory consumption, we allocate memory immediately
  99    before its needed and deallocate it as soon as possible.  */
 100 void
 101 pre_lcm (n_blocks, n_exprs, s_preds, s_succs, transp,
 102          antloc, redundant, optimal)
 103      int n_blocks;
 104      int n_exprs;
 105      int_list_ptr *s_preds;
 106      int_list_ptr *s_succs;
 107      sbitmap *transp;
 108      sbitmap *antloc;
 109      sbitmap *redundant;
 110      sbitmap *optimal;
 111 {
 112   sbitmap *antin, *antout, *earlyin, *earlyout, *delayin, *delayout;
 113   sbitmap *latein, *isoin, *isoout;
 114
 115   /* Compute global anticipatability.  ANTOUT is not needed except to
 116      compute ANTIN, so free its memory as soon as we return from
 117      compute_antinout.  */
 118   antin = sbitmap_vector_alloc (n_blocks, n_exprs);
 119   antout = sbitmap_vector_alloc (n_blocks, n_exprs);
 120   compute_antinout (n_blocks, s_succs, antloc,
 121                     transp, antin, antout);
 122   free (antout);
 123   antout = NULL;
 124
 125   /* Compute earliestness.  EARLYOUT is not needed except to compute
 126      EARLYIN, so free its memory as soon as we return from
 127      compute_earlyinout.  */
 128   earlyin = sbitmap_vector_alloc (n_blocks, n_exprs);
 129   earlyout = sbitmap_vector_alloc (n_blocks, n_exprs);
 130   compute_earlyinout (n_blocks, n_exprs, s_preds, transp, antin,
 131                       earlyin, earlyout);
 132   free (earlyout);
 133   earlyout = NULL;
 134
 135   /* Compute delayedness.  DELAYOUT is not needed except to compute
 136      DELAYIN, so free its memory as soon as we return from
 137      compute_delayinout.  We also no longer need ANTIN and EARLYIN.  */
 138   delayin = sbitmap_vector_alloc (n_blocks, n_exprs);
 139   delayout = sbitmap_vector_alloc (n_blocks, n_exprs);
 140   compute_delayinout (n_blocks, n_exprs, s_preds, antloc,
 141                       antin, earlyin, delayin, delayout);
 142   free (delayout);
 143   delayout = NULL;
 144   free (antin);
 145   antin = NULL;
 146   free (earlyin);
 147   earlyin = NULL;
 148
 149   /* Compute latestness.  We no longer need DELAYIN after we compute
 150      LATEIN.  */
 151   latein = sbitmap_vector_alloc (n_blocks, n_exprs);
 152   compute_latein (n_blocks, n_exprs, s_succs, antloc, delayin, latein);
 153   free (delayin);
 154   delayin = NULL;
 155
 156   /* Compute isolatedness.  ISOIN is not needed except to compute
 157      ISOOUT, so free its memory as soon as we return from
 158      compute_isoinout.  */
 159   isoin = sbitmap_vector_alloc (n_blocks, n_exprs);
 160   isoout = sbitmap_vector_alloc (n_blocks, n_exprs);
 161   compute_isoinout (n_blocks, s_succs, antloc, latein, isoin, isoout);
 162   free (isoin);
 163   isoin = NULL;
 164
 165   /* Now compute optimal placement points and the redundant expressions.  */
 166   compute_optimal (n_blocks, latein, isoout, optimal);
 167   compute_redundant (n_blocks, n_exprs, antloc, latein, isoout, redundant);
 168   free (latein);
 169   latein = NULL;
 170   free (isoout);
 171   isoout = NULL;
 172 }
 173
 174 /* Given local properties TRANSP, AVLOC, return the redundant and optimal
 175    computation points for expressions on the reverse flowgraph.
 176
 177    To reduce overall memory consumption, we allocate memory immediately
 178    before its needed and deallocate it as soon as possible.  */
 179
 180 void
 181 pre_rev_lcm (n_blocks, n_exprs, s_preds, s_succs, transp,
 182              avloc, redundant, optimal)
 183      int n_blocks;
 184      int n_exprs;
 185      int_list_ptr *s_preds;
 186      int_list_ptr *s_succs;
 187      sbitmap *transp;
 188      sbitmap *avloc;
 189      sbitmap *redundant;
 190      sbitmap *optimal;
 191 {
 192   sbitmap *avin, *avout, *fartherin, *fartherout, *earlierin, *earlierout;
 193   sbitmap *firstout, *rev_isoin, *rev_isoout;
 194
 195   /* Compute global availability.  AVIN is not needed except to
 196      compute AVOUT, so free its memory as soon as we return from
 197      compute_avinout.  */
 198   avin = sbitmap_vector_alloc (n_blocks, n_exprs);
 199   avout = sbitmap_vector_alloc (n_blocks, n_exprs);
 200   compute_avinout (n_blocks, s_preds, avloc, transp, avin, avout);
 201   free (avin);
 202   avin = NULL;
 203
 204   /* Compute fartherness.  FARTHERIN is not needed except to compute
 205      FARTHEROUT, so free its memory as soon as we return from
 206      compute_earlyinout.  */
 207   fartherin = sbitmap_vector_alloc (n_blocks, n_exprs);
 208   fartherout = sbitmap_vector_alloc (n_blocks, n_exprs);
 209   compute_fartherinout (n_blocks, n_exprs, s_succs, transp,
 210                         avout, fartherin, fartherout);
 211   free (fartherin);
 212   fartherin = NULL;
 213
 214   /* Compute earlierness.  EARLIERIN is not needed except to compute
 215      EARLIEROUT, so free its memory as soon as we return from
 216      compute_delayinout.  We also no longer need AVOUT and FARTHEROUT.  */
 217   earlierin = sbitmap_vector_alloc (n_blocks, n_exprs);
 218   earlierout = sbitmap_vector_alloc (n_blocks, n_exprs);
 219   compute_earlierinout (n_blocks, n_exprs, s_succs, avloc,
 220                         avout, fartherout, earlierin, earlierout);
 221   free (earlierin);
 222   earlierin = NULL;
 223   free (avout);
 224   avout = NULL;
 225   free (fartherout);
 226   fartherout = NULL;
 227
 228   /* Compute firstness.  We no longer need EARLIEROUT after we compute
 229      FIRSTOUT.  */
 230   firstout = sbitmap_vector_alloc (n_blocks, n_exprs);
 231   compute_firstout (n_blocks, n_exprs, s_preds, avloc, earlierout, firstout);
 232   free (earlierout);
 233   earlierout = NULL;
 234
 235   /* Compute rev_isolatedness.  ISOIN is not needed except to compute
 236      ISOOUT, so free its memory as soon as we return from
 237      compute_isoinout.  */
 238   rev_isoin = sbitmap_vector_alloc (n_blocks, n_exprs);
 239   rev_isoout = sbitmap_vector_alloc (n_blocks, n_exprs);
 240   compute_rev_isoinout (n_blocks, s_preds, avloc, firstout,
 241                         rev_isoin, rev_isoout);
 242   free (rev_isoout);
 243   rev_isoout = NULL;
 244
 245   /* Now compute optimal placement points and the redundant expressions.  */
 246   compute_optimal (n_blocks, firstout, rev_isoin, optimal);
 247   compute_redundant (n_blocks, n_exprs, avloc, firstout, rev_isoin, redundant);
 248   free (firstout);
 249   firstout = NULL;
 250   free (rev_isoin);
 251   rev_isoin = NULL;
 252 }
 253
 254 /* Compute expression anticipatability at entrance and exit of each block.  */
 255
 256 static void
 257 compute_antinout (n_blocks, s_succs, antloc, transp, antin, antout)
 258      int n_blocks;
 259      int_list_ptr *s_succs;
 260      sbitmap *antloc;
 261      sbitmap *transp;
 262      sbitmap *antin;
 263      sbitmap *antout;
 264 {
 265   int bb, changed, passes;
 266   sbitmap old_changed, new_changed;
 267
 268   sbitmap_zero (antout[n_blocks - 1]);
 269   sbitmap_vector_ones (antin, n_blocks);
 270
 271   old_changed = sbitmap_alloc (n_blocks);
 272   new_changed = sbitmap_alloc (n_blocks);
 273   sbitmap_ones (old_changed);
 274
 275   passes = 0;
 276   changed = 1;
 277   while (changed)
 278     {
 279       changed = 0;
 280       sbitmap_zero (new_changed);
 281       /* We scan the blocks in the reverse order to speed up
 282          the convergence.  */
 283       for (bb = n_blocks - 1; bb >= 0; bb--)
 284         {
 285           int_list_ptr ps;
 286
 287           /* If none of the successors of this block have changed,
 288              then this block is not going to change.  */
 289           for (ps = s_succs[bb] ; ps; ps = ps->next)
 290             {
 291               if (INT_LIST_VAL (ps) == EXIT_BLOCK
 292                   || INT_LIST_VAL (ps) == ENTRY_BLOCK)
 293                 break;
 294
 295               if (TEST_BIT (old_changed, INT_LIST_VAL (ps))
 296                   || TEST_BIT (new_changed, INT_LIST_VAL (ps)))
 297                 break;
 298             }
 299
 300           if (!ps)
 301             continue;
 302
 303           if (bb != n_blocks - 1)
 304             sbitmap_intersect_of_successors (antout[bb], antin,
 305                                              bb, s_succs);
 306           if (sbitmap_a_or_b_and_c (antin[bb], antloc[bb],
 307                                     transp[bb], antout[bb]))
 308             {
 309               changed = 1;
 310               SET_BIT (new_changed, bb);
 311             }
 312         }
 313       sbitmap_copy (old_changed, new_changed);
 314       passes++;
 315     }
 316   free (old_changed);
 317   free (new_changed);
 318 }
 319
 320 /* Compute expression earliestness at entrance and exit of each block.
 321
 322    From Advanced Compiler Design and Implementation pp411.
 323
 324    An expression is earliest at the entrance to basic block BB if no
 325    block from entry to block BB both evaluates the expression and
 326    produces the same value as evaluating it at the entry to block BB
 327    does.  Similarly for earlistness at basic block BB exit.  */
 328
 329 static void
 330 compute_earlyinout (n_blocks, n_exprs, s_preds, transp, antin,
 331                     earlyin, earlyout)
 332      int n_blocks;
 333      int n_exprs;
 334      int_list_ptr *s_preds;
 335      sbitmap *transp;
 336      sbitmap *antin;
 337      sbitmap *earlyin;
 338      sbitmap *earlyout;
 339 {
 340   int bb, changed, passes;
 341   sbitmap temp_bitmap;
 342   sbitmap old_changed, new_changed;
 343
 344   temp_bitmap = sbitmap_alloc (n_exprs);
 345
 346   sbitmap_vector_zero (earlyout, n_blocks);
 347   sbitmap_ones (earlyin[0]);
 348
 349   old_changed = sbitmap_alloc (n_blocks);
 350   new_changed = sbitmap_alloc (n_blocks);
 351   sbitmap_ones (old_changed);
 352
 353   passes = 0;
 354   changed = 1;
 355   while (changed)
 356     {
 357       changed = 0;
 358       sbitmap_zero (new_changed);
 359       for (bb = 0; bb < n_blocks; bb++)
 360         {
 361           int_list_ptr ps;
 362
 363           /* If none of the predecessors of this block have changed,
 364              then this block is not going to change.  */
 365           for (ps = s_preds[bb] ; ps; ps = ps->next)
 366             {
 367               if (INT_LIST_VAL (ps) == EXIT_BLOCK
 368                   || INT_LIST_VAL (ps) == ENTRY_BLOCK)
 369                 break;
 370
 371               if (TEST_BIT (old_changed, INT_LIST_VAL (ps))
 372                   || TEST_BIT (new_changed, INT_LIST_VAL (ps)))
 373                 break;
 374             }
 375
 376           if (!ps)
 377             continue;
 378
 379           if (bb != 0)
 380             sbitmap_union_of_predecessors (earlyin[bb], earlyout,
 381                                            bb, s_preds);
 382           sbitmap_not (temp_bitmap, transp[bb]);
 383           if (sbitmap_union_of_diff (earlyout[bb], temp_bitmap,
 384                                      earlyin[bb], antin[bb]))
 385             {
 386               changed = 1;
 387               SET_BIT (new_changed, bb);
 388             }
 389         }
 390       sbitmap_copy (old_changed, new_changed);
 391       passes++;
 392     }
 393   free (old_changed);
 394   free (new_changed);
 395   free (temp_bitmap);
 396 }
 397
 398 /* Compute expression delayedness at entrance and exit of each block.
 399
 400    From Advanced Compiler Design and Implementation pp411.
 401
 402    An expression is delayed at the entrance to BB if it is anticipatable
 403    and earliest at that point and if all subsequent computations of
 404    the expression are in block BB.   */
 405
 406 static void
 407 compute_delayinout (n_blocks, n_exprs, s_preds, antloc,
 408                     antin, earlyin, delayin, delayout)
 409      int n_blocks;
 410      int n_exprs;
 411      int_list_ptr *s_preds;
 412      sbitmap *antloc;
 413      sbitmap *antin;
 414      sbitmap *earlyin;
 415      sbitmap *delayin;
 416      sbitmap *delayout;
 417 {
 418   int bb, changed, passes;
 419   sbitmap *anti_and_early;
 420   sbitmap temp_bitmap;
 421
 422   temp_bitmap = sbitmap_alloc (n_exprs);
 423
 424   /* This is constant throughout the flow equations below, so compute
 425      it once to save time.  */
 426   anti_and_early = sbitmap_vector_alloc (n_blocks, n_exprs);
 427   for (bb = 0; bb < n_blocks; bb++)
 428     sbitmap_a_and_b (anti_and_early[bb], antin[bb], earlyin[bb]);
 429
 430   sbitmap_vector_zero (delayout, n_blocks);
 431   sbitmap_copy (delayin[0], anti_and_early[0]);
 432
 433   passes = 0;
 434   changed = 1;
 435   while (changed)
 436     {
 437       changed = 0;
 438       for (bb = 0; bb < n_blocks; bb++)
 439         {
 440           if (bb != 0)
 441             {
 442               sbitmap_intersect_of_predecessors (temp_bitmap, delayout,
 443                                                  bb, s_preds);
 444               changed |= sbitmap_a_or_b (delayin[bb],
 445                                          anti_and_early[bb],
 446                                          temp_bitmap);
 447             }
 448           sbitmap_not (temp_bitmap, antloc[bb]);
 449           changed |= sbitmap_a_and_b (delayout[bb],
 450                                       temp_bitmap,
 451                                       delayin[bb]);
 452         }
 453       passes++;
 454     }
 455
 456   /* We're done with this, so go ahead and free it's memory now instead
 457      of waiting until the end of pre.  */
 458   free (anti_and_early);
 459   free (temp_bitmap);
 460 }
 461
 462 /* Compute latestness.
 463
 464    From Advanced Compiler Design and Implementation pp412.
 465
 466    An expression is latest at the entrance to block BB if that is an optimal
 467    point for computing the expression and if on every path from block BB's
 468    entrance to the exit block, any optimal computation point for the
 469    expression occurs after one of the points at which the expression was
 470    computed in the original flowgraph.  */
 471
 472 static void
 473 compute_latein (n_blocks, n_exprs, s_succs, antloc, delayin, latein)
 474      int n_blocks;
 475      int n_exprs;
 476      int_list_ptr *s_succs;
 477      sbitmap *antloc;
 478      sbitmap *delayin;
 479      sbitmap *latein;
 480 {
 481   int bb;
 482   sbitmap temp_bitmap;
 483
 484   temp_bitmap = sbitmap_alloc (n_exprs);
 485
 486   for (bb = 0; bb < n_blocks; bb++)
 487     {
 488       /* The last block is succeeded only by the exit block; therefore,
 489          temp_bitmap will not be set by the following call!  */
 490       if (bb == n_blocks - 1)
 491         {
 492           sbitmap_intersect_of_successors (temp_bitmap, delayin,
 493                                            bb, s_succs);
 494           sbitmap_not (temp_bitmap, temp_bitmap);
 495         }
 496       else
 497         sbitmap_ones (temp_bitmap);
 498       sbitmap_a_and_b_or_c (latein[bb], delayin[bb],
 499                             antloc[bb], temp_bitmap);
 500     }
 501   free (temp_bitmap);
 502 }
 503
 504 /* Compute isolated.
 505
 506    From Advanced Compiler Design and Implementation pp413.
 507
 508    A computationally optimal placement for the evaluation of an expression
 509    is defined to be isolated if and only if on every path from a successor
 510    of the block in which it is computed to the exit block, every original
 511    computation of the expression is preceded by the optimal placement point.  */
 512
 513 static void
 514 compute_isoinout (n_blocks, s_succs, antloc, latein, isoin, isoout)
 515      int n_blocks;
 516      int_list_ptr *s_succs;
 517      sbitmap *antloc;
 518      sbitmap *latein;
 519      sbitmap *isoin;
 520      sbitmap *isoout;
 521 {
 522   int bb, changed, passes;
 523
 524   sbitmap_vector_zero (isoin, n_blocks);
 525   sbitmap_zero (isoout[n_blocks - 1]);
 526
 527   passes = 0;
 528   changed = 1;
 529   while (changed)
 530     {
 531       changed = 0;
 532       for (bb = n_blocks - 1; bb >= 0; bb--)
 533         {
 534           if (bb != n_blocks - 1)
 535             sbitmap_intersect_of_successors (isoout[bb], isoin,
 536                                              bb, s_succs);
 537           changed |= sbitmap_union_of_diff (isoin[bb], latein[bb],
 538                                             isoout[bb], antloc[bb]);
 539         }
 540       passes++;
 541     }
 542 }
 543
 544 /* Compute the set of expressions which have optimal computational points
 545    in each basic block.  This is the set of expressions that are latest, but
 546    that are not isolated in the block.  */
 547
 548 static void
 549 compute_optimal (n_blocks, latein, isoout, optimal)
 550      int n_blocks;
 551      sbitmap *latein;
 552      sbitmap *isoout;
 553      sbitmap *optimal;
 554 {
 555   int bb;
 556
 557   for (bb = 0; bb < n_blocks; bb++)
 558     sbitmap_difference (optimal[bb], latein[bb], isoout[bb]);
 559 }
 560
 561 /* Compute the set of expressions that are redundant in a block.  They are
 562    the expressions that are used in the block and that are neither isolated
 563    or latest.  */
 564
 565 static void
 566 compute_redundant (n_blocks, n_exprs, antloc, latein, isoout, redundant)
 567      int n_blocks;
 568      int n_exprs;
 569      sbitmap *antloc;
 570      sbitmap *latein;
 571      sbitmap *isoout;
 572      sbitmap *redundant;
 573 {
 574   int bb;
 575   sbitmap temp_bitmap;
 576
 577   temp_bitmap = sbitmap_alloc (n_exprs);
 578
 579   for (bb = 0; bb < n_blocks; bb++)
 580     {
 581       sbitmap_a_or_b (temp_bitmap, latein[bb], isoout[bb]);
 582       sbitmap_difference (redundant[bb], antloc[bb], temp_bitmap);
 583     }
 584   free (temp_bitmap);
 585 }
 586
 587 /* Compute expression availability at entrance and exit of each block.  */
 588
 589 static void
 590 compute_avinout (n_blocks, s_preds, avloc, transp, avin, avout)
 591      int n_blocks;
 592      int_list_ptr *s_preds;
 593      sbitmap *avloc;
 594      sbitmap *transp;
 595      sbitmap *avin;
 596      sbitmap *avout;
 597 {
 598   int bb, changed, passes;
 599
 600   sbitmap_zero (avin[0]);
 601   sbitmap_vector_ones (avout, n_blocks);
 602
 603   passes = 0;
 604   changed = 1;
 605   while (changed)
 606     {
 607       changed = 0;
 608       for (bb = 0; bb < n_blocks; bb++)
 609         {
 610           if (bb != 0)
 611             sbitmap_intersect_of_predecessors (avin[bb], avout,
 612                                                bb, s_preds);
 613           changed |= sbitmap_a_or_b_and_c (avout[bb], avloc[bb],
 614                                            transp[bb], avin[bb]);
 615         }
 616       passes++;
 617     }
 618 }
 619
 620 /* Compute expression latestness.
 621
 622    This is effectively the same as earliestness computed on the reverse
 623    flow graph.  */
 624
 625 static void
 626 compute_fartherinout (n_blocks, n_exprs, s_succs,
 627                       transp, avout, fartherin, fartherout)
 628      int n_blocks;
 629      int n_exprs;
 630      int_list_ptr *s_succs;
 631      sbitmap *transp;
 632      sbitmap *avout;
 633      sbitmap *fartherin;
 634      sbitmap *fartherout;
 635 {
 636   int bb, changed, passes;
 637   sbitmap temp_bitmap;
 638
 639   temp_bitmap = sbitmap_alloc (n_exprs);
 640
 641   sbitmap_vector_zero (fartherin, n_blocks);
 642   sbitmap_ones (fartherout[n_blocks - 1]);
 643
 644   passes = 0;
 645   changed = 1;
 646   while (changed)
 647     {
 648       changed = 0;
 649       for (bb = n_blocks - 1; bb >= 0; bb--)
 650         {
 651           if (bb != n_blocks - 1)
 652             sbitmap_union_of_successors (fartherout[bb], fartherin,
 653                                          bb, s_succs);
 654           sbitmap_not (temp_bitmap, transp[bb]);
 655           changed |= sbitmap_union_of_diff (fartherin[bb], temp_bitmap,
 656                                             fartherout[bb], avout[bb]);
 657         }
 658       passes++;
 659     }
 660
 661   free (temp_bitmap);
 662 }
 663
 664 /* Compute expression earlierness at entrance and exit of each block.
 665
 666    This is effectively the same as delayedness computed on the reverse
 667    flow graph.  */
 668
 669 static void
 670 compute_earlierinout (n_blocks, n_exprs, s_succs, avloc,
 671                       avout, fartherout, earlierin, earlierout)
 672      int n_blocks;
 673      int n_exprs;
 674      int_list_ptr *s_succs;
 675      sbitmap *avloc;
 676      sbitmap *avout;
 677      sbitmap *fartherout;
 678      sbitmap *earlierin;
 679      sbitmap *earlierout;
 680 {
 681   int bb, changed, passes;
 682   sbitmap *av_and_farther;
 683   sbitmap temp_bitmap;
 684
 685   temp_bitmap = sbitmap_alloc (n_exprs);
 686
 687   /* This is constant throughout the flow equations below, so compute
 688      it once to save time.  */
 689   av_and_farther = sbitmap_vector_alloc (n_blocks, n_exprs);
 690   for (bb = 0; bb < n_blocks; bb++)
 691     sbitmap_a_and_b (av_and_farther[bb], avout[bb], fartherout[bb]);
 692
 693   sbitmap_vector_zero (earlierin, n_blocks);
 694   sbitmap_copy (earlierout[n_blocks - 1], av_and_farther[n_blocks - 1]);
 695
 696   passes = 0;
 697   changed = 1;
 698   while (changed)
 699     {
 700       changed = 0;
 701       for (bb = n_blocks - 1; bb >= 0; bb--)
 702         {
 703           if (bb != n_blocks - 1)
 704             {
 705               sbitmap_intersect_of_successors (temp_bitmap, earlierin,
 706                                                bb, s_succs);
 707               changed |= sbitmap_a_or_b (earlierout[bb],
 708                                          av_and_farther[bb],
 709                                          temp_bitmap);
 710             }
 711           sbitmap_not (temp_bitmap, avloc[bb]);
 712           changed |= sbitmap_a_and_b (earlierin[bb],
 713                                       temp_bitmap,
 714                                       earlierout[bb]);
 715         }
 716       passes++;
 717     }
 718
 719   /* We're done with this, so go ahead and free it's memory now instead
 720      of waiting until the end of pre.  */
 721   free (av_and_farther);
 722   free (temp_bitmap);
 723 }
 724
 725 /* Compute firstness.
 726
 727    This is effectively the same as latestness computed on the reverse
 728    flow graph.  */
 729
 730 static void
 731 compute_firstout (n_blocks, n_exprs, s_preds, avloc, earlierout, firstout)
 732      int n_blocks;
 733      int n_exprs;
 734      int_list_ptr *s_preds;
 735      sbitmap *avloc;
 736      sbitmap *earlierout;
 737      sbitmap *firstout;
 738 {
 739   int bb;
 740   sbitmap temp_bitmap;
 741
 742   temp_bitmap = sbitmap_alloc (n_exprs);
 743
 744   for (bb = 0; bb < n_blocks; bb++)
 745     {
 746       /* The first block is preceded only by the entry block; therefore,
 747          temp_bitmap will not be set by the following call!  */
 748       if (bb != 0)
 749         {
 750           sbitmap_intersect_of_predecessors (temp_bitmap, earlierout,
 751                                              bb, s_preds);
 752           sbitmap_not (temp_bitmap, temp_bitmap);
 753         }
 754       else
 755         {
 756           sbitmap_ones (temp_bitmap);
 757         }
 758       sbitmap_a_and_b_or_c (firstout[bb], earlierout[bb],
 759                             avloc[bb], temp_bitmap);
 760     }
 761   free (temp_bitmap);
 762 }
 763
 764 /* Compute reverse isolated.
 765
 766    This is effectively the same as isolatedness computed on the reverse
 767    flow graph.  */
 768
 769 static void
 770 compute_rev_isoinout (n_blocks, s_preds, avloc, firstout,
 771                       rev_isoin, rev_isoout)
 772      int n_blocks;
 773      int_list_ptr *s_preds;
 774      sbitmap *avloc;
 775      sbitmap *firstout;
 776      sbitmap *rev_isoin;
 777      sbitmap *rev_isoout;
 778 {
 779   int bb, changed, passes;
 780
 781   sbitmap_vector_zero (rev_isoout, n_blocks);
 782   sbitmap_zero (rev_isoin[0]);
 783
 784   passes = 0;
 785   changed = 1;
 786   while (changed)
 787     {
 788       changed = 0;
 789       for (bb = 0; bb < n_blocks; bb++)
 790         {
 791           if (bb != 0)
 792             sbitmap_intersect_of_predecessors (rev_isoin[bb], rev_isoout,
 793                                                bb, s_preds);
 794           changed |= sbitmap_union_of_diff (rev_isoout[bb], firstout[bb],
 795                                             rev_isoin[bb], avloc[bb]);
 796         }
 797       passes++;
 798     }
 799 }