1/* Generic partial redundancy elimination with lazy code motion 2 support. 3 Copyright (C) 1998 Free Software Foundation, Inc. 4 5This file is part of GNU CC. 6 7GNU CC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GNU CC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GNU CC; see the file COPYING. If not, write to 19the Free Software Foundation, 59 Temple Place - Suite 330, 20Boston, 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 65static void compute_antinout PROTO ((int, int_list_ptr *, sbitmap *, 66 sbitmap *, sbitmap *, sbitmap *)); 67static void compute_earlyinout PROTO ((int, int, int_list_ptr *, sbitmap *, 68 sbitmap *, sbitmap *, sbitmap *)); 69static void compute_delayinout PROTO ((int, int, int_list_ptr *, sbitmap *, 70 sbitmap *, sbitmap *, 71 sbitmap *, sbitmap *)); 72static void compute_latein PROTO ((int, int, int_list_ptr *, sbitmap *, 73 sbitmap *, sbitmap *)); 74static void compute_isoinout PROTO ((int, int_list_ptr *, sbitmap *, 75 sbitmap *, sbitmap *, sbitmap *)); 76static void compute_optimal PROTO ((int, sbitmap *, 77 sbitmap *, sbitmap *)); 78static void compute_redundant PROTO ((int, int, sbitmap *, 79 sbitmap *, sbitmap *, sbitmap *)); 80 81/* Similarly, but for the reversed flowgraph. */ 82static void compute_avinout PROTO ((int, int_list_ptr *, sbitmap *, 83 sbitmap *, sbitmap *, sbitmap *)); 84static void compute_fartherinout PROTO ((int, int, int_list_ptr *, 85 sbitmap *, sbitmap *, 86 sbitmap *, sbitmap *)); 87static void compute_earlierinout PROTO ((int, int, int_list_ptr *, sbitmap *, 88 sbitmap *, sbitmap *, 89 sbitmap *, sbitmap *)); 90static void compute_firstout PROTO ((int, int, int_list_ptr *, sbitmap *, 91 sbitmap *, sbitmap *)); 92static 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. */ 100void 101pre_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 180void 181pre_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 256static void 257compute_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 329static void 330compute_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 406static void 407compute_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 472static void 473compute_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 513static void 514compute_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 548static void 549compute_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 565static void 566compute_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 589static void 590compute_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 625static void 626compute_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 669static void 670compute_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 730static void 731compute_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 769static void 770compute_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} 800