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