1 /* Thread edges through blocks and update the control flow and SSA graphs. 2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010, 201 3 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "tree.h" 26 #include "flags.h" 27 #include "tm_p.h" 28 #include "basic-block.h" 29 #include "output.h" 30 #include "function.h" 31 #include "tree-flow.h" 32 #include "tree-dump.h" 33 #include "tree-pass.h" 34 #include "cfgloop.h" 35 36 /* Given a block B, update the CFG and SSA graph to reflect redirecting 37 one or more in-edges to B to instead reach the destination of an 38 out-edge from B while preserving any side effects in B. 39 40 i.e., given A->B and B->C, change A->B to be A->C yet still preserve the 41 side effects of executing B. 42 43 1. Make a copy of B (including its outgoing edges and statements). Call 44 the copy B'. Note B' has no incoming edges or PHIs at this time. 45 46 2. Remove the control statement at the end of B' and all outgoing edges 47 except B'->C. 48 49 3. Add a new argument to each PHI in C with the same value as the existing 50 argument associated with edge B->C. Associate the new PHI arguments 51 with the edge B'->C. 52 53 4. For each PHI in B, find or create a PHI in B' with an identical 54 PHI_RESULT. Add an argument to the PHI in B' which has the same 55 value as the PHI in B associated with the edge A->B. Associate 56 the new argument in the PHI in B' with the edge A->B. 57 58 5. Change the edge A->B to A->B'. 59 60 5a. This automatically deletes any PHI arguments associated with the 61 edge A->B in B. 62 63 5b. This automatically associates each new argument added in step 4 64 with the edge A->B'. 65 66 6. Repeat for other incoming edges into B. 67 68 7. Put the duplicated resources in B and all the B' blocks into SSA form. 69 70 Note that block duplication can be minimized by first collecting the 71 set of unique destination blocks that the incoming edges should 72 be threaded to. 73 74 Block duplication can be further minimized by using B instead of 75 creating B' for one destination if all edges into B are going to be 76 threaded to a successor of B. We had code to do this at one time, but 77 I'm not convinced it is correct with the changes to avoid mucking up 78 the loop structure (which may cancel threading requests, thus a block 79 which we thought was going to become unreachable may still be reachable). 80 This code was also going to get ugly with the introduction of the ability 81 for a single jump thread request to bypass multiple blocks. 82 83 We further reduce the number of edges and statements we create by 84 not copying all the outgoing edges and the control statement in 85 step #1. We instead create a template block without the outgoing 86 edges and duplicate the template. */ 87 88 89 /* Steps #5 and #6 of the above algorithm are best implemented by walking 90 all the incoming edges which thread to the same destination edge at 91 the same time. That avoids lots of table lookups to get information 92 for the destination edge. 93 94 To realize that implementation we create a list of incoming edges 95 which thread to the same outgoing edge. Thus to implement steps 96 #5 and #6 we traverse our hash table of outgoing edge information. 97 For each entry we walk the list of incoming edges which thread to 98 the current outgoing edge. */ 99 100 struct el 101 { 102 edge e; 103 struct el *next; 104 }; 105 106 /* Main data structure recording information regarding B's duplicate 107 blocks. */ 108 109 /* We need to efficiently record the unique thread destinations of this 110 block and specific information associated with those destinations. We 111 may have many incoming edges threaded to the same outgoing edge. This 112 can be naturally implemented with a hash table. */ 113 114 struct redirection_data 115 { 116 /* A duplicate of B with the trailing control statement removed and which 117 targets a single successor of B. */ 118 basic_block dup_block; 119 120 /* An outgoing edge from B. DUP_BLOCK will have OUTGOING_EDGE->dest as 121 its single successor. */ 122 edge outgoing_edge; 123 124 edge intermediate_edge; 125 126 /* A list of incoming edges which we want to thread to 127 OUTGOING_EDGE->dest. */ 128 struct el *incoming_edges; 129 }; 130 131 /* Main data structure to hold information for duplicates of BB. */ 132 static htab_t redirection_data; 133 134 /* Data structure of information to pass to hash table traversal routines. */ 135 struct local_info 136 { 137 /* The current block we are working on. */ 138 basic_block bb; 139 140 /* A template copy of BB with no outgoing edges or control statement that 141 we use for creating copies. */ 142 basic_block template_block; 143 144 /* TRUE if we thread one or more jumps, FALSE otherwise. */ 145 bool jumps_threaded; 146 }; 147 148 /* Passes which use the jump threading code register jump threading 149 opportunities as they are discovered. We keep the registered 150 jump threading opportunities in this vector as edge pairs 151 (original_edge, target_edge). */ 152 static VEC(edge,heap) *threaded_edges; 153 154 /* When we start updating the CFG for threading, data necessary for jump 155 threading is attached to the AUX field for the incoming edge. Use these 156 macros to access the underlying structure attached to the AUX field. */ 157 #define THREAD_TARGET(E) ((edge *)(E)->aux)[0] 158 #define THREAD_TARGET2(E) ((edge *)(E)->aux)[1] 159 160 /* Jump threading statistics. */ 161 162 struct thread_stats_d 163 { 164 unsigned long num_threaded_edges; 165 }; 166 167 struct thread_stats_d thread_stats; 168 169 170 /* Remove the last statement in block BB if it is a control statement 171 Also remove all outgoing edges except the edge which reaches DEST_BB. 172 If DEST_BB is NULL, then remove all outgoing edges. */ 173 174 static void 175 remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb) 176 { 177 gimple_stmt_iterator gsi; 178 edge e; 179 edge_iterator ei; 180 181 gsi = gsi_last_bb (bb); 182 183 /* If the duplicate ends with a control statement, then remove it. 184 185 Note that if we are duplicating the template block rather than the 186 original basic block, then the duplicate might not have any real 187 statements in it. */ 188 if (!gsi_end_p (gsi) 189 && gsi_stmt (gsi) 190 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND 191 || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO 192 || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH)) 193 gsi_remove (&gsi, true); 194 195 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 196 { 197 if (e->dest != dest_bb) 198 remove_edge (e); 199 else 200 ei_next (&ei); 201 } 202 } 203 204 /* Create a duplicate of BB. Record the duplicate block in RD. */ 205 206 static void 207 create_block_for_threading (basic_block bb, struct redirection_data *rd) 208 { 209 edge_iterator ei; 210 edge e; 211 212 /* We can use the generic block duplication code and simply remove 213 the stuff we do not need. */ 214 rd->dup_block = duplicate_block (bb, NULL, NULL); 215 216 FOR_EACH_EDGE (e, ei, rd->dup_block->succs) 217 e->aux = NULL; 218 219 /* Zero out the profile, since the block is unreachable for now. */ 220 rd->dup_block->frequency = 0; 221 rd->dup_block->count = 0; 222 } 223 224 /* Hashing and equality routines for our hash table. */ 225 static hashval_t 226 redirection_data_hash (const void *p) 227 { 228 edge e = ((const struct redirection_data *)p)->outgoing_edge; 229 return e->dest->index; 230 } 231 232 static int 233 redirection_data_eq (const void *p1, const void *p2) 234 { 235 edge e1 = ((const struct redirection_data *)p1)->outgoing_edge; 236 edge e2 = ((const struct redirection_data *)p2)->outgoing_edge; 237 edge e3 = ((const struct redirection_data *)p1)->intermediate_edge; 238 edge e4 = ((const struct redirection_data *)p2)->intermediate_edge; 239 240 return e1 == e2 && e3 == e4; 241 } 242 243 /* Given an outgoing edge E lookup and return its entry in our hash table. 244 245 If INSERT is true, then we insert the entry into the hash table if 246 it is not already present. INCOMING_EDGE is added to the list of incoming 247 edges associated with E in the hash table. */ 248 249 static struct redirection_data * 250 lookup_redirection_data (edge e, enum insert_option insert) 251 { 252 void **slot; 253 struct redirection_data *elt; 254 255 /* Build a hash table element so we can see if E is already 256 in the table. */ 257 elt = XNEW (struct redirection_data); 258 elt->intermediate_edge = THREAD_TARGET2 (e) ? THREAD_TARGET (e) : NULL; 259 elt->outgoing_edge = THREAD_TARGET2 (e) ? THREAD_TARGET2 (e) 260 : THREAD_TARGET (e); 261 elt->dup_block = NULL; 262 elt->incoming_edges = NULL; 263 264 slot = htab_find_slot (redirection_data, elt, insert); 265 266 /* This will only happen if INSERT is false and the entry is not 267 in the hash table. */ 268 if (slot == NULL) 269 { 270 free (elt); 271 return NULL; 272 } 273 274 /* This will only happen if E was not in the hash table and 275 INSERT is true. */ 276 if (*slot == NULL) 277 { 278 *slot = (void *)elt; 279 elt->incoming_edges = XNEW (struct el); 280 elt->incoming_edges->e = e; 281 elt->incoming_edges->next = NULL; 282 return elt; 283 } 284 /* E was in the hash table. */ 285 else 286 { 287 /* Free ELT as we do not need it anymore, we will extract the 288 relevant entry from the hash table itself. */ 289 free (elt); 290 291 /* Get the entry stored in the hash table. */ 292 elt = (struct redirection_data *) *slot; 293 294 /* If insertion was requested, then we need to add INCOMING_EDGE 295 to the list of incoming edges associated with E. */ 296 if (insert) 297 { 298 struct el *el = XNEW (struct el); 299 el->next = elt->incoming_edges; 300 el->e = e; 301 elt->incoming_edges = el; 302 } 303 304 return elt; 305 } 306 } 307 308 /* For each PHI in BB, copy the argument associated with SRC_E to TGT_E. */ 309 310 static void 311 copy_phi_args (basic_block bb, edge src_e, edge tgt_e) 312 { 313 gimple_stmt_iterator gsi; 314 int src_indx = src_e->dest_idx; 315 316 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 317 { 318 gimple phi = gsi_stmt (gsi); 319 source_location locus = gimple_phi_arg_location (phi, src_indx); 320 add_phi_arg (phi, gimple_phi_arg_def (phi, src_indx), tgt_e, locus); 321 } 322 } 323 324 /* We have recently made a copy of ORIG_BB, including its outgoing 325 edges. The copy is NEW_BB. Every PHI node in every direct successor of 326 ORIG_BB has a new argument associated with edge from NEW_BB to the 327 successor. Initialize the PHI argument so that it is equal to the PHI 328 argument associated with the edge from ORIG_BB to the successor. */ 329 330 static void 331 update_destination_phis (basic_block orig_bb, basic_block new_bb) 332 { 333 edge_iterator ei; 334 edge e; 335 336 FOR_EACH_EDGE (e, ei, orig_bb->succs) 337 { 338 edge e2 = find_edge (new_bb, e->dest); 339 copy_phi_args (e->dest, e, e2); 340 } 341 } 342 343 /* Given a duplicate block and its single destination (both stored 344 in RD). Create an edge between the duplicate and its single 345 destination. 346 347 Add an additional argument to any PHI nodes at the single 348 destination. */ 349 350 static void 351 create_edge_and_update_destination_phis (struct redirection_data *rd, 352 basic_block bb) 353 { 354 edge e = make_edge (bb, rd->outgoing_edge->dest, EDGE_FALLTHRU); 355 356 rescan_loop_exit (e, true, false); 357 e->probability = REG_BR_PROB_BASE; 358 e->count = bb->count; 359 360 if (rd->outgoing_edge->aux) 361 { 362 e->aux = (edge *) XNEWVEC (edge, 2); 363 THREAD_TARGET(e) = THREAD_TARGET (rd->outgoing_edge); 364 THREAD_TARGET2(e) = THREAD_TARGET2 (rd->outgoing_edge); 365 } 366 else 367 { 368 e->aux = NULL; 369 } 370 371 /* If there are any PHI nodes at the destination of the outgoing edge 372 from the duplicate block, then we will need to add a new argument 373 to them. The argument should have the same value as the argument 374 associated with the outgoing edge stored in RD. */ 375 copy_phi_args (e->dest, rd->outgoing_edge, e); 376 } 377 378 /* Wire up the outgoing edges from the duplicate block and 379 update any PHIs as needed. */ 380 static void 381 fix_duplicate_block_edges (struct redirection_data *rd, 382 struct local_info *local_info) 383 { 384 /* If we were threading through an joiner block, then we want 385 to keep its control statement and redirect an outgoing edge. 386 Else we want to remove the control statement & edges, then create 387 a new outgoing edge. In both cases we may need to update PHIs. */ 388 if (THREAD_TARGET2 (rd->incoming_edges->e)) 389 { 390 edge victim; 391 edge e2; 392 edge e = rd->incoming_edges->e; 393 394 /* This updates the PHIs at the destination of the duplicate 395 block. */ 396 update_destination_phis (local_info->bb, rd->dup_block); 397 398 /* Find the edge from the duplicate block to the block we're 399 threading through. That's the edge we want to redirect. */ 400 victim = find_edge (rd->dup_block, THREAD_TARGET (e)->dest); 401 e2 = redirect_edge_and_branch (victim, THREAD_TARGET2 (e)->dest); 402 403 /* If we redirected the edge, then we need to copy PHI arguments 404 at the target. If the edge already existed (e2 != victim case), 405 then the PHIs in the target already have the correct arguments. */ 406 if (e2 == victim) 407 copy_phi_args (e2->dest, THREAD_TARGET2 (e), e2); 408 } 409 else 410 { 411 remove_ctrl_stmt_and_useless_edges (rd->dup_block, NULL); 412 create_edge_and_update_destination_phis (rd, rd->dup_block); 413 } 414 } 415 /* Hash table traversal callback routine to create duplicate blocks. */ 416 417 static int 418 create_duplicates (void **slot, void *data) 419 { 420 struct redirection_data *rd = (struct redirection_data *) *slot; 421 struct local_info *local_info = (struct local_info *)data; 422 423 /* Create a template block if we have not done so already. Otherwise 424 use the template to create a new block. */ 425 if (local_info->template_block == NULL) 426 { 427 create_block_for_threading (local_info->bb, rd); 428 local_info->template_block = rd->dup_block; 429 430 /* We do not create any outgoing edges for the template. We will 431 take care of that in a later traversal. That way we do not 432 create edges that are going to just be deleted. */ 433 } 434 else 435 { 436 create_block_for_threading (local_info->template_block, rd); 437 438 /* Go ahead and wire up outgoing edges and update PHIs for the duplicate 439 block. */ 440 fix_duplicate_block_edges (rd, local_info); 441 } 442 443 /* Keep walking the hash table. */ 444 return 1; 445 } 446 447 /* We did not create any outgoing edges for the template block during 448 block creation. This hash table traversal callback creates the 449 outgoing edge for the template block. */ 450 451 static int 452 fixup_template_block (void **slot, void *data) 453 { 454 struct redirection_data *rd = (struct redirection_data *) *slot; 455 struct local_info *local_info = (struct local_info *)data; 456 457 /* If this is the template block halt the traversal after updating 458 it appropriately. 459 460 If we were threading through an joiner block, then we want 461 to keep its control statement and redirect an outgoing edge. 462 Else we want to remove the control statement & edges, then create 463 a new outgoing edge. In both cases we may need to update PHIs. */ 464 if (rd->dup_block && rd->dup_block == local_info->template_block) 465 { 466 fix_duplicate_block_edges (rd, local_info); 467 return 0; 468 } 469 470 return 1; 471 } 472 473 /* Hash table traversal callback to redirect each incoming edge 474 associated with this hash table element to its new destination. */ 475 476 static int 477 redirect_edges (void **slot, void *data) 478 { 479 struct redirection_data *rd = (struct redirection_data *) *slot; 480 struct local_info *local_info = (struct local_info *)data; 481 struct el *next, *el; 482 483 /* Walk over all the incoming edges associated associated with this 484 hash table entry. */ 485 for (el = rd->incoming_edges; el; el = next) 486 { 487 edge e = el->e; 488 489 /* Go ahead and free this element from the list. Doing this now 490 avoids the need for another list walk when we destroy the hash 491 table. */ 492 next = el->next; 493 free (el); 494 495 thread_stats.num_threaded_edges++; 496 /* If we are threading through a joiner block, then we have to 497 find the edge we want to redirect and update some PHI nodes. */ 498 if (THREAD_TARGET2 (e)) 499 { 500 edge e2; 501 502 /* We want to redirect the incoming edge to the joiner block (E) 503 to instead reach the duplicate of the joiner block. */ 504 e2 = redirect_edge_and_branch (e, rd->dup_block); 505 flush_pending_stmts (e2); 506 } 507 else if (rd->dup_block) 508 { 509 edge e2; 510 511 if (dump_file && (dump_flags & TDF_DETAILS)) 512 fprintf (dump_file, " Threaded jump %d --> %d to %d\n", 513 e->src->index, e->dest->index, rd->dup_block->index); 514 515 rd->dup_block->count += e->count; 516 517 /* Excessive jump threading may make frequencies large enough so 518 the computation overflows. */ 519 if (rd->dup_block->frequency < BB_FREQ_MAX * 2) 520 rd->dup_block->frequency += EDGE_FREQUENCY (e); 521 EDGE_SUCC (rd->dup_block, 0)->count += e->count; 522 /* Redirect the incoming edge to the appropriate duplicate 523 block. */ 524 e2 = redirect_edge_and_branch (e, rd->dup_block); 525 gcc_assert (e == e2); 526 flush_pending_stmts (e2); 527 } 528 529 /* Go ahead and clear E->aux. It's not needed anymore and failure 530 to clear it will cause all kinds of unpleasant problems later. */ 531 free (e->aux); 532 e->aux = NULL; 533 534 } 535 536 /* Indicate that we actually threaded one or more jumps. */ 537 if (rd->incoming_edges) 538 local_info->jumps_threaded = true; 539 540 return 1; 541 } 542 543 /* Return true if this block has no executable statements other than 544 a simple ctrl flow instruction. When the number of outgoing edges 545 is one, this is equivalent to a "forwarder" block. */ 546 547 static bool 548 redirection_block_p (basic_block bb) 549 { 550 gimple_stmt_iterator gsi; 551 552 /* Advance to the first executable statement. */ 553 gsi = gsi_start_bb (bb); 554 while (!gsi_end_p (gsi) 555 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL 556 || is_gimple_debug (gsi_stmt (gsi)) 557 || gimple_nop_p (gsi_stmt (gsi)))) 558 gsi_next (&gsi); 559 560 /* Check if this is an empty block. */ 561 if (gsi_end_p (gsi)) 562 return true; 563 564 /* Test that we've reached the terminating control statement. */ 565 return gsi_stmt (gsi) 566 && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND 567 || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO 568 || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH); 569 } 570 571 /* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB 572 is reached via one or more specific incoming edges, we know which 573 outgoing edge from BB will be traversed. 574 575 We want to redirect those incoming edges to the target of the 576 appropriate outgoing edge. Doing so avoids a conditional branch 577 and may expose new optimization opportunities. Note that we have 578 to update dominator tree and SSA graph after such changes. 579 580 The key to keeping the SSA graph update manageable is to duplicate 581 the side effects occurring in BB so that those side effects still 582 occur on the paths which bypass BB after redirecting edges. 583 584 We accomplish this by creating duplicates of BB and arranging for 585 the duplicates to unconditionally pass control to one specific 586 successor of BB. We then revector the incoming edges into BB to 587 the appropriate duplicate of BB. 588 589 If NOLOOP_ONLY is true, we only perform the threading as long as it 590 does not affect the structure of the loops in a nontrivial way. */ 591 592 static bool 593 thread_block (basic_block bb, bool noloop_only) 594 { 595 /* E is an incoming edge into BB that we may or may not want to 596 redirect to a duplicate of BB. */ 597 edge e, e2; 598 edge_iterator ei; 599 struct local_info local_info; 600 struct loop *loop = bb->loop_father; 601 602 /* To avoid scanning a linear array for the element we need we instead 603 use a hash table. For normal code there should be no noticeable 604 difference. However, if we have a block with a large number of 605 incoming and outgoing edges such linear searches can get expensive. */ 606 redirection_data = htab_create (EDGE_COUNT (bb->succs), 607 redirection_data_hash, 608 redirection_data_eq, 609 free); 610 611 /* If we thread the latch of the loop to its exit, the loop ceases to 612 exist. Make sure we do not restrict ourselves in order to preserve 613 this loop. */ 614 if (loop->header == bb) 615 { 616 e = loop_latch_edge (loop); 617 618 if (e->aux) 619 e2 = THREAD_TARGET (e); 620 else 621 e2 = NULL; 622 623 if (e2 && loop_exit_edge_p (loop, e2)) 624 { 625 loop->header = NULL; 626 loop->latch = NULL; 627 } 628 } 629 630 /* Record each unique threaded destination into a hash table for 631 efficient lookups. */ 632 FOR_EACH_EDGE (e, ei, bb->preds) 633 { 634 if (e->aux == NULL) 635 continue; 636 637 if (THREAD_TARGET2 (e)) 638 e2 = THREAD_TARGET2 (e); 639 else 640 e2 = THREAD_TARGET (e); 641 642 if (!e2 643 /* If NOLOOP_ONLY is true, we only allow threading through the 644 header of a loop to exit edges. */ 645 || (noloop_only 646 && bb == bb->loop_father->header 647 && (!loop_exit_edge_p (bb->loop_father, e2) 648 || THREAD_TARGET2 (e)))) 649 continue; 650 651 if (e->dest == e2->src) 652 update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e), 653 e->count, THREAD_TARGET (e)); 654 655 /* Insert the outgoing edge into the hash table if it is not 656 already in the hash table. */ 657 lookup_redirection_data (e, INSERT); 658 } 659 660 /* We do not update dominance info. */ 661 free_dominance_info (CDI_DOMINATORS); 662 663 /* Now create duplicates of BB. 664 665 Note that for a block with a high outgoing degree we can waste 666 a lot of time and memory creating and destroying useless edges. 667 668 So we first duplicate BB and remove the control structure at the 669 tail of the duplicate as well as all outgoing edges from the 670 duplicate. We then use that duplicate block as a template for 671 the rest of the duplicates. */ 672 local_info.template_block = NULL; 673 local_info.bb = bb; 674 local_info.jumps_threaded = false; 675 htab_traverse (redirection_data, create_duplicates, &local_info); 676 677 /* The template does not have an outgoing edge. Create that outgoing 678 edge and update PHI nodes as the edge's target as necessary. 679 680 We do this after creating all the duplicates to avoid creating 681 unnecessary edges. */ 682 htab_traverse (redirection_data, fixup_template_block, &local_info); 683 684 /* The hash table traversals above created the duplicate blocks (and the 685 statements within the duplicate blocks). This loop creates PHI nodes for 686 the duplicated blocks and redirects the incoming edges into BB to reach 687 the duplicates of BB. */ 688 htab_traverse (redirection_data, redirect_edges, &local_info); 689 690 /* Done with this block. Clear REDIRECTION_DATA. */ 691 htab_delete (redirection_data); 692 redirection_data = NULL; 693 694 /* Indicate to our caller whether or not any jumps were threaded. */ 695 return local_info.jumps_threaded; 696 } 697 698 /* Threads edge E through E->dest to the edge THREAD_TARGET (E). Returns the 699 copy of E->dest created during threading, or E->dest if it was not necessary 700 to copy it (E is its single predecessor). */ 701 702 static basic_block 703 thread_single_edge (edge e) 704 { 705 basic_block bb = e->dest; 706 edge eto = THREAD_TARGET (e); 707 struct redirection_data rd; 708 709 free (e->aux); 710 e->aux = NULL; 711 712 thread_stats.num_threaded_edges++; 713 714 if (single_pred_p (bb)) 715 { 716 /* If BB has just a single predecessor, we should only remove the 717 control statements at its end, and successors except for ETO. */ 718 remove_ctrl_stmt_and_useless_edges (bb, eto->dest); 719 720 /* And fixup the flags on the single remaining edge. */ 721 eto->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL); 722 eto->flags |= EDGE_FALLTHRU; 723 724 return bb; 725 } 726 727 /* Otherwise, we need to create a copy. */ 728 if (e->dest == eto->src) 729 update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto); 730 731 rd.outgoing_edge = eto; 732 733 create_block_for_threading (bb, &rd); 734 remove_ctrl_stmt_and_useless_edges (rd.dup_block, NULL); 735 create_edge_and_update_destination_phis (&rd, rd.dup_block); 736 737 if (dump_file && (dump_flags & TDF_DETAILS)) 738 fprintf (dump_file, " Threaded jump %d --> %d to %d\n", 739 e->src->index, e->dest->index, rd.dup_block->index); 740 741 rd.dup_block->count = e->count; 742 rd.dup_block->frequency = EDGE_FREQUENCY (e); 743 single_succ_edge (rd.dup_block)->count = e->count; 744 redirect_edge_and_branch (e, rd.dup_block); 745 flush_pending_stmts (e); 746 747 return rd.dup_block; 748 } 749 750 /* Callback for dfs_enumerate_from. Returns true if BB is different 751 from STOP and DBDS_CE_STOP. */ 752 753 static basic_block dbds_ce_stop; 754 static bool 755 dbds_continue_enumeration_p (const_basic_block bb, const void *stop) 756 { 757 return (bb != (const_basic_block) stop 758 && bb != dbds_ce_stop); 759 } 760 761 /* Evaluates the dominance relationship of latch of the LOOP and BB, and 762 returns the state. */ 763 764 enum bb_dom_status 765 { 766 /* BB does not dominate latch of the LOOP. */ 767 DOMST_NONDOMINATING, 768 /* The LOOP is broken (there is no path from the header to its latch. */ 769 DOMST_LOOP_BROKEN, 770 /* BB dominates the latch of the LOOP. */ 771 DOMST_DOMINATING 772 }; 773 774 static enum bb_dom_status 775 determine_bb_domination_status (struct loop *loop, basic_block bb) 776 { 777 basic_block *bblocks; 778 unsigned nblocks, i; 779 bool bb_reachable = false; 780 edge_iterator ei; 781 edge e; 782 783 /* This function assumes BB is a successor of LOOP->header. 784 If that is not the case return DOMST_NONDOMINATING which 785 is always safe. */ 786 { 787 bool ok = false; 788 789 FOR_EACH_EDGE (e, ei, bb->preds) 790 { 791 if (e->src == loop->header) 792 { 793 ok = true; 794 break; 795 } 796 } 797 798 if (!ok) 799 return DOMST_NONDOMINATING; 800 } 801 802 if (bb == loop->latch) 803 return DOMST_DOMINATING; 804 805 /* Check that BB dominates LOOP->latch, and that it is back-reachable 806 from it. */ 807 808 bblocks = XCNEWVEC (basic_block, loop->num_nodes); 809 dbds_ce_stop = loop->header; 810 nblocks = dfs_enumerate_from (loop->latch, 1, dbds_continue_enumeration_p, 811 bblocks, loop->num_nodes, bb); 812 for (i = 0; i < nblocks; i++) 813 FOR_EACH_EDGE (e, ei, bblocks[i]->preds) 814 { 815 if (e->src == loop->header) 816 { 817 free (bblocks); 818 return DOMST_NONDOMINATING; 819 } 820 if (e->src == bb) 821 bb_reachable = true; 822 } 823 824 free (bblocks); 825 return (bb_reachable ? DOMST_DOMINATING : DOMST_LOOP_BROKEN); 826 } 827 828 /* Thread jumps through the header of LOOP. Returns true if cfg changes. 829 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges 830 to the inside of the loop. */ 831 832 static bool 833 thread_through_loop_header (struct loop *loop, bool may_peel_loop_headers) 834 { 835 basic_block header = loop->header; 836 edge e, tgt_edge, latch = loop_latch_edge (loop); 837 edge_iterator ei; 838 basic_block tgt_bb, atgt_bb; 839 enum bb_dom_status domst; 840 841 /* We have already threaded through headers to exits, so all the threading 842 requests now are to the inside of the loop. We need to avoid creating 843 irreducible regions (i.e., loops with more than one entry block), and 844 also loop with several latch edges, or new subloops of the loop (although 845 there are cases where it might be appropriate, it is difficult to decide, 846 and doing it wrongly may confuse other optimizers). 847 848 We could handle more general cases here. However, the intention is to 849 preserve some information about the loop, which is impossible if its 850 structure changes significantly, in a way that is not well understood. 851 Thus we only handle few important special cases, in which also updating 852 of the loop-carried information should be feasible: 853 854 1) Propagation of latch edge to a block that dominates the latch block 855 of a loop. This aims to handle the following idiom: 856 857 first = 1; 858 while (1) 859 { 860 if (first) 861 initialize; 862 first = 0; 863 body; 864 } 865 866 After threading the latch edge, this becomes 867 868 first = 1; 869 if (first) 870 initialize; 871 while (1) 872 { 873 first = 0; 874 body; 875 } 876 877 The original header of the loop is moved out of it, and we may thread 878 the remaining edges through it without further constraints. 879 880 2) All entry edges are propagated to a single basic block that dominates 881 the latch block of the loop. This aims to handle the following idiom 882 (normally created for "for" loops): 883 884 i = 0; 885 while (1) 886 { 887 if (i >= 100) 888 break; 889 body; 890 i++; 891 } 892 893 This becomes 894 895 i = 0; 896 while (1) 897 { 898 body; 899 i++; 900 if (i >= 100) 901 break; 902 } 903 */ 904 905 /* Threading through the header won't improve the code if the header has just 906 one successor. */ 907 if (single_succ_p (header)) 908 goto fail; 909 910 if (latch->aux) 911 { 912 if (THREAD_TARGET2 (latch)) 913 goto fail; 914 tgt_edge = THREAD_TARGET (latch); 915 tgt_bb = tgt_edge->dest; 916 } 917 else if (!may_peel_loop_headers 918 && !redirection_block_p (loop->header)) 919 goto fail; 920 else 921 { 922 tgt_bb = NULL; 923 tgt_edge = NULL; 924 FOR_EACH_EDGE (e, ei, header->preds) 925 { 926 if (!e->aux) 927 { 928 if (e == latch) 929 continue; 930 931 /* If latch is not threaded, and there is a header 932 edge that is not threaded, we would create loop 933 with multiple entries. */ 934 goto fail; 935 } 936 937 if (THREAD_TARGET2 (e)) 938 goto fail; 939 tgt_edge = THREAD_TARGET (e); 940 atgt_bb = tgt_edge->dest; 941 if (!tgt_bb) 942 tgt_bb = atgt_bb; 943 /* Two targets of threading would make us create loop 944 with multiple entries. */ 945 else if (tgt_bb != atgt_bb) 946 goto fail; 947 } 948 949 if (!tgt_bb) 950 { 951 /* There are no threading requests. */ 952 return false; 953 } 954 955 /* Redirecting to empty loop latch is useless. */ 956 if (tgt_bb == loop->latch 957 && empty_block_p (loop->latch)) 958 goto fail; 959 } 960 961 /* The target block must dominate the loop latch, otherwise we would be 962 creating a subloop. */ 963 domst = determine_bb_domination_status (loop, tgt_bb); 964 if (domst == DOMST_NONDOMINATING) 965 goto fail; 966 if (domst == DOMST_LOOP_BROKEN) 967 { 968 /* If the loop ceased to exist, mark it as such, and thread through its 969 original header. */ 970 loop->header = NULL; 971 loop->latch = NULL; 972 return thread_block (header, false); 973 } 974 975 if (tgt_bb->loop_father->header == tgt_bb) 976 { 977 /* If the target of the threading is a header of a subloop, we need 978 to create a preheader for it, so that the headers of the two loops 979 do not merge. */ 980 if (EDGE_COUNT (tgt_bb->preds) > 2) 981 { 982 tgt_bb = create_preheader (tgt_bb->loop_father, 0); 983 gcc_assert (tgt_bb != NULL); 984 } 985 else 986 tgt_bb = split_edge (tgt_edge); 987 } 988 989 if (latch->aux) 990 { 991 /* First handle the case latch edge is redirected. */ 992 loop->latch = thread_single_edge (latch); 993 gcc_assert (single_succ (loop->latch) == tgt_bb); 994 loop->header = tgt_bb; 995 996 /* Thread the remaining edges through the former header. */ 997 thread_block (header, false); 998 } 999 else 1000 { 1001 basic_block new_preheader; 1002 1003 /* Now consider the case entry edges are redirected to the new entry 1004 block. Remember one entry edge, so that we can find the new 1005 preheader (its destination after threading). */ 1006 FOR_EACH_EDGE (e, ei, header->preds) 1007 { 1008 if (e->aux) 1009 break; 1010 } 1011 1012 /* The duplicate of the header is the new preheader of the loop. Ensure 1013 that it is placed correctly in the loop hierarchy. */ 1014 set_loop_copy (loop, loop_outer (loop)); 1015 1016 thread_block (header, false); 1017 set_loop_copy (loop, NULL); 1018 new_preheader = e->dest; 1019 1020 /* Create the new latch block. This is always necessary, as the latch 1021 must have only a single successor, but the original header had at 1022 least two successors. */ 1023 loop->latch = NULL; 1024 mfb_kj_edge = single_succ_edge (new_preheader); 1025 loop->header = mfb_kj_edge->dest; 1026 latch = make_forwarder_block (tgt_bb, mfb_keep_just, NULL); 1027 loop->header = latch->dest; 1028 loop->latch = latch->src; 1029 } 1030 1031 return true; 1032 1033 fail: 1034 /* We failed to thread anything. Cancel the requests. */ 1035 FOR_EACH_EDGE (e, ei, header->preds) 1036 { 1037 free (e->aux); 1038 e->aux = NULL; 1039 } 1040 return false; 1041 } 1042 1043 /* Walk through the registered jump threads and convert them into a 1044 form convenient for this pass. 1045 1046 Any block which has incoming edges threaded to outgoing edges 1047 will have its entry in THREADED_BLOCK set. 1048 1049 Any threaded edge will have its new outgoing edge stored in the 1050 original edge's AUX field. 1051 1052 This form avoids the need to walk all the edges in the CFG to 1053 discover blocks which need processing and avoids unnecessary 1054 hash table lookups to map from threaded edge to new target. */ 1055 1056 static void 1057 mark_threaded_blocks (bitmap threaded_blocks) 1058 { 1059 unsigned int i; 1060 bitmap_iterator bi; 1061 bitmap tmp = BITMAP_ALLOC (NULL); 1062 basic_block bb; 1063 edge e; 1064 edge_iterator ei; 1065 1066 for (i = 0; i < VEC_length (edge, threaded_edges); i += 3) 1067 { 1068 edge e = VEC_index (edge, threaded_edges, i); 1069 edge *x = (edge *) XNEWVEC (edge, 2); 1070 1071 e->aux = x; 1072 THREAD_TARGET (e) = VEC_index (edge, threaded_edges, i + 1); 1073 THREAD_TARGET2 (e) = VEC_index (edge, threaded_edges, i + 2); 1074 bitmap_set_bit (tmp, e->dest->index); 1075 } 1076 1077 /* If optimizing for size, only thread through block if we don't have 1078 to duplicate it or it's an otherwise empty redirection block. */ 1079 if (optimize_function_for_size_p (cfun)) 1080 { 1081 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi) 1082 { 1083 bb = BASIC_BLOCK (i); 1084 if (EDGE_COUNT (bb->preds) > 1 1085 && !redirection_block_p (bb)) 1086 { 1087 FOR_EACH_EDGE (e, ei, bb->preds) 1088 { 1089 free (e->aux); 1090 e->aux = NULL; 1091 } 1092 } 1093 else 1094 bitmap_set_bit (threaded_blocks, i); 1095 } 1096 } 1097 else 1098 bitmap_copy (threaded_blocks, tmp); 1099 1100 BITMAP_FREE(tmp); 1101 } 1102 1103 1104 /* Walk through all blocks and thread incoming edges to the appropriate 1105 outgoing edge for each edge pair recorded in THREADED_EDGES. 1106 1107 It is the caller's responsibility to fix the dominance information 1108 and rewrite duplicated SSA_NAMEs back into SSA form. 1109 1110 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading edges through 1111 loop headers if it does not simplify the loop. 1112 1113 Returns true if one or more edges were threaded, false otherwise. */ 1114 1115 bool 1116 thread_through_all_blocks (bool may_peel_loop_headers) 1117 { 1118 bool retval = false; 1119 unsigned int i; 1120 bitmap_iterator bi; 1121 bitmap threaded_blocks; 1122 struct loop *loop; 1123 loop_iterator li; 1124 1125 /* We must know about loops in order to preserve them. */ 1126 gcc_assert (current_loops != NULL); 1127 1128 if (threaded_edges == NULL) 1129 return false; 1130 1131 threaded_blocks = BITMAP_ALLOC (NULL); 1132 memset (&thread_stats, 0, sizeof (thread_stats)); 1133 1134 mark_threaded_blocks (threaded_blocks); 1135 1136 initialize_original_copy_tables (); 1137 1138 /* First perform the threading requests that do not affect 1139 loop structure. */ 1140 EXECUTE_IF_SET_IN_BITMAP (threaded_blocks, 0, i, bi) 1141 { 1142 basic_block bb = BASIC_BLOCK (i); 1143 1144 if (EDGE_COUNT (bb->preds) > 0) 1145 retval |= thread_block (bb, true); 1146 } 1147 1148 /* Then perform the threading through loop headers. We start with the 1149 innermost loop, so that the changes in cfg we perform won't affect 1150 further threading. */ 1151 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) 1152 { 1153 if (!loop->header 1154 || !bitmap_bit_p (threaded_blocks, loop->header->index)) 1155 continue; 1156 1157 retval |= thread_through_loop_header (loop, may_peel_loop_headers); 1158 } 1159 1160 statistics_counter_event (cfun, "Jumps threaded", 1161 thread_stats.num_threaded_edges); 1162 1163 free_original_copy_tables (); 1164 1165 BITMAP_FREE (threaded_blocks); 1166 threaded_blocks = NULL; 1167 VEC_free (edge, heap, threaded_edges); 1168 threaded_edges = NULL; 1169 1170 if (retval) 1171 loops_state_set (LOOPS_NEED_FIXUP); 1172 1173 return retval; 1174 } 1175 1176 /* Register a jump threading opportunity. We queue up all the jump 1177 threading opportunities discovered by a pass and update the CFG 1178 and SSA form all at once. 1179 1180 E is the edge we can thread, E2 is the new target edge, i.e., we 1181 are effectively recording that E->dest can be changed to E2->dest 1182 after fixing the SSA graph. */ 1183 1184 void 1185 register_jump_thread (edge e, edge e2, edge e3) 1186 { 1187 /* This can occur if we're jumping to a constant address or 1188 or something similar. Just get out now. */ 1189 if (e2 == NULL) 1190 return; 1191 1192 if (threaded_edges == NULL) 1193 threaded_edges = VEC_alloc (edge, heap, 15); 1194 1195 if (dump_file && (dump_flags & TDF_DETAILS) 1196 && e->dest != e2->src) 1197 fprintf (dump_file, 1198 " Registering jump thread around one or more intermediate blocks\n"); 1199 1200 VEC_safe_push (edge, heap, threaded_edges, e); 1201 VEC_safe_push (edge, heap, threaded_edges, e2); 1202 VEC_safe_push (edge, heap, threaded_edges, e3); 1203 } 1204