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