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 = xmalloc (sizeof (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]; 126 qlen = n_basic_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 = xmalloc (sizeof (basic_block) * (n_basic_blocks + 1)); 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. In fact the above allocation 298 of n_basic_blocks + 1 elements is not necessary. */ 299 qin = worklist; 300 qend = &worklist[n_basic_blocks]; 301 qlen = n_basic_blocks; 302 303 /* Iterate until the worklist is empty. */ 304 while (qlen) 305 { 306 /* Take the first entry off the worklist. */ 307 bb = *qout++; 308 bb->aux = NULL; 309 qlen--; 310 if (qout >= qend) 311 qout = worklist; 312 313 /* Compute the intersection of LATERIN for each incoming edge to B. */ 314 sbitmap_ones (laterin[bb->index]); 315 FOR_EACH_EDGE (e, ei, bb->preds) 316 sbitmap_a_and_b (laterin[bb->index], laterin[bb->index], 317 later[(size_t)e->aux]); 318 319 /* Calculate LATER for all outgoing edges. */ 320 FOR_EACH_EDGE (e, ei, bb->succs) 321 if (sbitmap_union_of_diff_cg (later[(size_t) e->aux], 322 earliest[(size_t) e->aux], 323 laterin[e->src->index], 324 antloc[e->src->index]) 325 /* If LATER for an outgoing edge was changed, then we need 326 to add the target of the outgoing edge to the worklist. */ 327 && e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0) 328 { 329 *qin++ = e->dest; 330 e->dest->aux = e; 331 qlen++; 332 if (qin >= qend) 333 qin = worklist; 334 } 335 } 336 337 /* Computation of insertion and deletion points requires computing LATERIN 338 for the EXIT block. We allocated an extra entry in the LATERIN array 339 for just this purpose. */ 340 sbitmap_ones (laterin[last_basic_block]); 341 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 342 sbitmap_a_and_b (laterin[last_basic_block], 343 laterin[last_basic_block], 344 later[(size_t) e->aux]); 345 346 clear_aux_for_edges (); 347 free (worklist); 348} 349 350/* Compute the insertion and deletion points for edge based LCM. */ 351 352static void 353compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc, 354 sbitmap *later, sbitmap *laterin, sbitmap *insert, 355 sbitmap *delete) 356{ 357 int x; 358 basic_block bb; 359 360 FOR_EACH_BB (bb) 361 sbitmap_difference (delete[bb->index], antloc[bb->index], 362 laterin[bb->index]); 363 364 for (x = 0; x < NUM_EDGES (edge_list); x++) 365 { 366 basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x); 367 368 if (b == EXIT_BLOCK_PTR) 369 sbitmap_difference (insert[x], later[x], laterin[last_basic_block]); 370 else 371 sbitmap_difference (insert[x], later[x], laterin[b->index]); 372 } 373} 374 375/* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and 376 delete vectors for edge based LCM. Returns an edgelist which is used to 377 map the insert vector to what edge an expression should be inserted on. */ 378 379struct edge_list * 380pre_edge_lcm (FILE *file ATTRIBUTE_UNUSED, int n_exprs, sbitmap *transp, 381 sbitmap *avloc, sbitmap *antloc, sbitmap *kill, 382 sbitmap **insert, sbitmap **delete) 383{ 384 sbitmap *antin, *antout, *earliest; 385 sbitmap *avin, *avout; 386 sbitmap *later, *laterin; 387 struct edge_list *edge_list; 388 int num_edges; 389 390 edge_list = create_edge_list (); 391 num_edges = NUM_EDGES (edge_list); 392 393#ifdef LCM_DEBUG_INFO 394 if (file) 395 { 396 fprintf (file, "Edge List:\n"); 397 verify_edge_list (file, edge_list); 398 print_edge_list (file, edge_list); 399 dump_sbitmap_vector (file, "transp", "", transp, last_basic_block); 400 dump_sbitmap_vector (file, "antloc", "", antloc, last_basic_block); 401 dump_sbitmap_vector (file, "avloc", "", avloc, last_basic_block); 402 dump_sbitmap_vector (file, "kill", "", kill, last_basic_block); 403 } 404#endif 405 406 /* Compute global availability. */ 407 avin = sbitmap_vector_alloc (last_basic_block, n_exprs); 408 avout = sbitmap_vector_alloc (last_basic_block, n_exprs); 409 compute_available (avloc, kill, avout, avin); 410 sbitmap_vector_free (avin); 411 412 /* Compute global anticipatability. */ 413 antin = sbitmap_vector_alloc (last_basic_block, n_exprs); 414 antout = sbitmap_vector_alloc (last_basic_block, n_exprs); 415 compute_antinout_edge (antloc, transp, antin, antout); 416 417#ifdef LCM_DEBUG_INFO 418 if (file) 419 { 420 dump_sbitmap_vector (file, "antin", "", antin, last_basic_block); 421 dump_sbitmap_vector (file, "antout", "", antout, last_basic_block); 422 } 423#endif 424 425 /* Compute earliestness. */ 426 earliest = sbitmap_vector_alloc (num_edges, n_exprs); 427 compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest); 428 429#ifdef LCM_DEBUG_INFO 430 if (file) 431 dump_sbitmap_vector (file, "earliest", "", earliest, num_edges); 432#endif 433 434 sbitmap_vector_free (antout); 435 sbitmap_vector_free (antin); 436 sbitmap_vector_free (avout); 437 438 later = sbitmap_vector_alloc (num_edges, n_exprs); 439 440 /* Allocate an extra element for the exit block in the laterin vector. */ 441 laterin = sbitmap_vector_alloc (last_basic_block + 1, n_exprs); 442 compute_laterin (edge_list, earliest, antloc, later, laterin); 443 444#ifdef LCM_DEBUG_INFO 445 if (file) 446 { 447 dump_sbitmap_vector (file, "laterin", "", laterin, last_basic_block + 1); 448 dump_sbitmap_vector (file, "later", "", later, num_edges); 449 } 450#endif 451 452 sbitmap_vector_free (earliest); 453 454 *insert = sbitmap_vector_alloc (num_edges, n_exprs); 455 *delete = sbitmap_vector_alloc (last_basic_block, n_exprs); 456 compute_insert_delete (edge_list, antloc, later, laterin, *insert, *delete); 457 458 sbitmap_vector_free (laterin); 459 sbitmap_vector_free (later); 460 461#ifdef LCM_DEBUG_INFO 462 if (file) 463 { 464 dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges); 465 dump_sbitmap_vector (file, "pre_delete_map", "", *delete, 466 last_basic_block); 467 } 468#endif 469 470 return edge_list; 471} 472 473/* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors. 474 Return the number of passes we performed to iterate to a solution. */ 475 476void 477compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout, 478 sbitmap *avin) 479{ 480 edge e; 481 basic_block *worklist, *qin, *qout, *qend, bb; 482 unsigned int qlen; 483 edge_iterator ei; 484 485 /* Allocate a worklist array/queue. Entries are only added to the 486 list if they were not already on the list. So the size is 487 bounded by the number of basic blocks. */ 488 qin = qout = worklist = xmalloc (sizeof (basic_block) * n_basic_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]; 503 qlen = n_basic_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 = xmalloc (sizeof (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 (FILE *file ATTRIBUTE_UNUSED, 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 (file) 739 { 740 fprintf (file, "Edge List:\n"); 741 verify_edge_list (file, edge_list); 742 print_edge_list (file, edge_list); 743 dump_sbitmap_vector (file, "transp", "", transp, last_basic_block); 744 dump_sbitmap_vector (file, "st_avloc", "", st_avloc, last_basic_block); 745 dump_sbitmap_vector (file, "st_antloc", "", st_antloc, last_basic_block); 746 dump_sbitmap_vector (file, "st_antin", "", st_antin, last_basic_block); 747 dump_sbitmap_vector (file, "st_antout", "", st_antout, last_basic_block); 748 dump_sbitmap_vector (file, "st_kill", "", kill, last_basic_block); 749 } 750#endif 751 752#ifdef LCM_DEBUG_INFO 753 if (file) 754 { 755 dump_sbitmap_vector (file, "st_avout", "", st_avout, last_basic_block); 756 dump_sbitmap_vector (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 (file) 767 dump_sbitmap_vector (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 (file) 784 { 785 dump_sbitmap_vector (file, "nearerout", "", nearerout, 786 last_basic_block + 1); 787 dump_sbitmap_vector (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 (file) 803 { 804 dump_sbitmap_vector (file, "pre_insert_map", "", *insert, num_edges); 805 dump_sbitmap_vector (file, "pre_delete_map", "", *delete, 806 last_basic_block); 807 } 808#endif 809 return edge_list; 810} 811 812