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