1 /* Basic block reordering routines for the GNU compiler. 2 Copyright (C) 2000-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 7 under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 14 License 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 /* This file contains the "reorder blocks" pass, which changes the control 21 flow of a function to encounter fewer branches; the "partition blocks" 22 pass, which divides the basic blocks into "hot" and "cold" partitions, 23 which are kept separate; and the "duplicate computed gotos" pass, which 24 duplicates blocks ending in an indirect jump. 25 26 There are two algorithms for "reorder blocks": the "simple" algorithm, 27 which just rearranges blocks, trying to minimize the number of executed 28 unconditional branches; and the "software trace cache" algorithm, which 29 also copies code, and in general tries a lot harder to have long linear 30 pieces of machine code executed. This algorithm is described next. */ 31 32 /* This (greedy) algorithm constructs traces in several rounds. 33 The construction starts from "seeds". The seed for the first round 34 is the entry point of the function. When there are more than one seed, 35 the one with the lowest key in the heap is selected first (see bb_to_key). 36 Then the algorithm repeatedly adds the most probable successor to the end 37 of a trace. Finally it connects the traces. 38 39 There are two parameters: Branch Threshold and Exec Threshold. 40 If the probability of an edge to a successor of the current basic block is 41 lower than Branch Threshold or its count is lower than Exec Threshold, 42 then the successor will be the seed in one of the next rounds. 43 Each round has these parameters lower than the previous one. 44 The last round has to have these parameters set to zero so that the 45 remaining blocks are picked up. 46 47 The algorithm selects the most probable successor from all unvisited 48 successors and successors that have been added to this trace. 49 The other successors (that has not been "sent" to the next round) will be 50 other seeds for this round and the secondary traces will start from them. 51 If the successor has not been visited in this trace, it is added to the 52 trace (however, there is some heuristic for simple branches). 53 If the successor has been visited in this trace, a loop has been found. 54 If the loop has many iterations, the loop is rotated so that the source 55 block of the most probable edge going out of the loop is the last block 56 of the trace. 57 If the loop has few iterations and there is no edge from the last block of 58 the loop going out of the loop, the loop header is duplicated. 59 60 When connecting traces, the algorithm first checks whether there is an edge 61 from the last block of a trace to the first block of another trace. 62 When there are still some unconnected traces it checks whether there exists 63 a basic block BB such that BB is a successor of the last block of a trace 64 and BB is a predecessor of the first block of another trace. In this case, 65 BB is duplicated, added at the end of the first trace and the traces are 66 connected through it. 67 The rest of traces are simply connected so there will be a jump to the 68 beginning of the rest of traces. 69 70 The above description is for the full algorithm, which is used when the 71 function is optimized for speed. When the function is optimized for size, 72 in order to reduce long jumps and connect more fallthru edges, the 73 algorithm is modified as follows: 74 (1) Break long traces to short ones. A trace is broken at a block that has 75 multiple predecessors/ successors during trace discovery. When connecting 76 traces, only connect Trace n with Trace n + 1. This change reduces most 77 long jumps compared with the above algorithm. 78 (2) Ignore the edge probability and count for fallthru edges. 79 (3) Keep the original order of blocks when there is no chance to fall 80 through. We rely on the results of cfg_cleanup. 81 82 To implement the change for code size optimization, block's index is 83 selected as the key and all traces are found in one round. 84 85 References: 86 87 "Software Trace Cache" 88 A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999 89 http://citeseer.nj.nec.com/15361.html 90 91 */ 92 93 #include "config.h" 94 #define INCLUDE_ALGORITHM /* stable_sort */ 95 #include "system.h" 96 #include "coretypes.h" 97 #include "backend.h" 98 #include "target.h" 99 #include "rtl.h" 100 #include "tree.h" 101 #include "cfghooks.h" 102 #include "df.h" 103 #include "memmodel.h" 104 #include "optabs.h" 105 #include "regs.h" 106 #include "emit-rtl.h" 107 #include "output.h" 108 #include "expr.h" 109 #include "params.h" 110 #include "tree-pass.h" 111 #include "cfgrtl.h" 112 #include "cfganal.h" 113 #include "cfgbuild.h" 114 #include "cfgcleanup.h" 115 #include "bb-reorder.h" 116 #include "except.h" 117 #include "fibonacci_heap.h" 118 #include "stringpool.h" 119 #include "attribs.h" 120 121 /* The number of rounds. In most cases there will only be 4 rounds, but 122 when partitioning hot and cold basic blocks into separate sections of 123 the object file there will be an extra round. */ 124 #define N_ROUNDS 5 125 126 struct target_bb_reorder default_target_bb_reorder; 127 #if SWITCHABLE_TARGET 128 struct target_bb_reorder *this_target_bb_reorder = &default_target_bb_reorder; 129 #endif 130 131 #define uncond_jump_length \ 132 (this_target_bb_reorder->x_uncond_jump_length) 133 134 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */ 135 static const int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0}; 136 137 /* Exec thresholds in thousandths (per mille) of the count of bb 0. */ 138 static const int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0}; 139 140 /* If edge count is lower than DUPLICATION_THRESHOLD per mille of entry 141 block the edge destination is not duplicated while connecting traces. */ 142 #define DUPLICATION_THRESHOLD 100 143 144 typedef fibonacci_heap <long, basic_block_def> bb_heap_t; 145 typedef fibonacci_node <long, basic_block_def> bb_heap_node_t; 146 147 /* Structure to hold needed information for each basic block. */ 148 struct bbro_basic_block_data 149 { 150 /* Which trace is the bb start of (-1 means it is not a start of any). */ 151 int start_of_trace; 152 153 /* Which trace is the bb end of (-1 means it is not an end of any). */ 154 int end_of_trace; 155 156 /* Which trace is the bb in? */ 157 int in_trace; 158 159 /* Which trace was this bb visited in? */ 160 int visited; 161 162 /* Cached maximum frequency of interesting incoming edges. 163 Minus one means not yet computed. */ 164 int priority; 165 166 /* Which heap is BB in (if any)? */ 167 bb_heap_t *heap; 168 169 /* Which heap node is BB in (if any)? */ 170 bb_heap_node_t *node; 171 }; 172 173 /* The current size of the following dynamic array. */ 174 static int array_size; 175 176 /* The array which holds needed information for basic blocks. */ 177 static bbro_basic_block_data *bbd; 178 179 /* To avoid frequent reallocation the size of arrays is greater than needed, 180 the number of elements is (not less than) 1.25 * size_wanted. */ 181 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5) 182 183 /* Free the memory and set the pointer to NULL. */ 184 #define FREE(P) (gcc_assert (P), free (P), P = 0) 185 186 /* Structure for holding information about a trace. */ 187 struct trace 188 { 189 /* First and last basic block of the trace. */ 190 basic_block first, last; 191 192 /* The round of the STC creation which this trace was found in. */ 193 int round; 194 195 /* The length (i.e. the number of basic blocks) of the trace. */ 196 int length; 197 }; 198 199 /* Maximum count of one of the entry blocks. */ 200 static profile_count max_entry_count; 201 202 /* Local function prototypes. */ 203 static void find_traces_1_round (int, profile_count, struct trace *, int *, 204 int, bb_heap_t **, int); 205 static basic_block copy_bb (basic_block, edge, basic_block, int); 206 static long bb_to_key (basic_block); 207 static bool better_edge_p (const_basic_block, const_edge, profile_probability, 208 profile_count, profile_probability, profile_count, 209 const_edge); 210 static bool copy_bb_p (const_basic_block, int); 211 212 /* Return the trace number in which BB was visited. */ 213 214 static int 215 bb_visited_trace (const_basic_block bb) 216 { 217 gcc_assert (bb->index < array_size); 218 return bbd[bb->index].visited; 219 } 220 221 /* This function marks BB that it was visited in trace number TRACE. */ 222 223 static void 224 mark_bb_visited (basic_block bb, int trace) 225 { 226 bbd[bb->index].visited = trace; 227 if (bbd[bb->index].heap) 228 { 229 bbd[bb->index].heap->delete_node (bbd[bb->index].node); 230 bbd[bb->index].heap = NULL; 231 bbd[bb->index].node = NULL; 232 } 233 } 234 235 /* Check to see if bb should be pushed into the next round of trace 236 collections or not. Reasons for pushing the block forward are 1). 237 If the block is cold, we are doing partitioning, and there will be 238 another round (cold partition blocks are not supposed to be 239 collected into traces until the very last round); or 2). There will 240 be another round, and the basic block is not "hot enough" for the 241 current round of trace collection. */ 242 243 static bool 244 push_to_next_round_p (const_basic_block bb, int round, int number_of_rounds, 245 profile_count count_th) 246 { 247 bool there_exists_another_round; 248 bool block_not_hot_enough; 249 250 there_exists_another_round = round < number_of_rounds - 1; 251 252 block_not_hot_enough = (bb->count < count_th 253 || probably_never_executed_bb_p (cfun, bb)); 254 255 if (there_exists_another_round 256 && block_not_hot_enough) 257 return true; 258 else 259 return false; 260 } 261 262 /* Find the traces for Software Trace Cache. Chain each trace through 263 RBI()->next. Store the number of traces to N_TRACES and description of 264 traces to TRACES. */ 265 266 static void 267 find_traces (int *n_traces, struct trace *traces) 268 { 269 int i; 270 int number_of_rounds; 271 edge e; 272 edge_iterator ei; 273 bb_heap_t *heap = new bb_heap_t (LONG_MIN); 274 275 /* Add one extra round of trace collection when partitioning hot/cold 276 basic blocks into separate sections. The last round is for all the 277 cold blocks (and ONLY the cold blocks). */ 278 279 number_of_rounds = N_ROUNDS - 1; 280 281 /* Insert entry points of function into heap. */ 282 max_entry_count = profile_count::zero (); 283 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs) 284 { 285 bbd[e->dest->index].heap = heap; 286 bbd[e->dest->index].node = heap->insert (bb_to_key (e->dest), e->dest); 287 if (e->dest->count > max_entry_count) 288 max_entry_count = e->dest->count; 289 } 290 291 /* Find the traces. */ 292 for (i = 0; i < number_of_rounds; i++) 293 { 294 profile_count count_threshold; 295 296 if (dump_file) 297 fprintf (dump_file, "STC - round %d\n", i + 1); 298 299 count_threshold = max_entry_count.apply_scale (exec_threshold[i], 1000); 300 301 find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000, 302 count_threshold, traces, n_traces, i, &heap, 303 number_of_rounds); 304 } 305 delete heap; 306 307 if (dump_file) 308 { 309 for (i = 0; i < *n_traces; i++) 310 { 311 basic_block bb; 312 fprintf (dump_file, "Trace %d (round %d): ", i + 1, 313 traces[i].round + 1); 314 for (bb = traces[i].first; 315 bb != traces[i].last; 316 bb = (basic_block) bb->aux) 317 { 318 fprintf (dump_file, "%d [", bb->index); 319 bb->count.dump (dump_file); 320 fprintf (dump_file, "] "); 321 } 322 fprintf (dump_file, "%d [", bb->index); 323 bb->count.dump (dump_file); 324 fprintf (dump_file, "]\n"); 325 } 326 fflush (dump_file); 327 } 328 } 329 330 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE 331 (with sequential number TRACE_N). */ 332 333 static basic_block 334 rotate_loop (edge back_edge, struct trace *trace, int trace_n) 335 { 336 basic_block bb; 337 338 /* Information about the best end (end after rotation) of the loop. */ 339 basic_block best_bb = NULL; 340 edge best_edge = NULL; 341 profile_count best_count = profile_count::uninitialized (); 342 /* The best edge is preferred when its destination is not visited yet 343 or is a start block of some trace. */ 344 bool is_preferred = false; 345 346 /* Find the most frequent edge that goes out from current trace. */ 347 bb = back_edge->dest; 348 do 349 { 350 edge e; 351 edge_iterator ei; 352 353 FOR_EACH_EDGE (e, ei, bb->succs) 354 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) 355 && bb_visited_trace (e->dest) != trace_n 356 && (e->flags & EDGE_CAN_FALLTHRU) 357 && !(e->flags & EDGE_COMPLEX)) 358 { 359 if (is_preferred) 360 { 361 /* The best edge is preferred. */ 362 if (!bb_visited_trace (e->dest) 363 || bbd[e->dest->index].start_of_trace >= 0) 364 { 365 /* The current edge E is also preferred. */ 366 if (e->count () > best_count) 367 { 368 best_count = e->count (); 369 best_edge = e; 370 best_bb = bb; 371 } 372 } 373 } 374 else 375 { 376 if (!bb_visited_trace (e->dest) 377 || bbd[e->dest->index].start_of_trace >= 0) 378 { 379 /* The current edge E is preferred. */ 380 is_preferred = true; 381 best_count = e->count (); 382 best_edge = e; 383 best_bb = bb; 384 } 385 else 386 { 387 if (!best_edge || e->count () > best_count) 388 { 389 best_count = e->count (); 390 best_edge = e; 391 best_bb = bb; 392 } 393 } 394 } 395 } 396 bb = (basic_block) bb->aux; 397 } 398 while (bb != back_edge->dest); 399 400 if (best_bb) 401 { 402 /* Rotate the loop so that the BEST_EDGE goes out from the last block of 403 the trace. */ 404 if (back_edge->dest == trace->first) 405 { 406 trace->first = (basic_block) best_bb->aux; 407 } 408 else 409 { 410 basic_block prev_bb; 411 412 for (prev_bb = trace->first; 413 prev_bb->aux != back_edge->dest; 414 prev_bb = (basic_block) prev_bb->aux) 415 ; 416 prev_bb->aux = best_bb->aux; 417 418 /* Try to get rid of uncond jump to cond jump. */ 419 if (single_succ_p (prev_bb)) 420 { 421 basic_block header = single_succ (prev_bb); 422 423 /* Duplicate HEADER if it is a small block containing cond jump 424 in the end. */ 425 if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0) 426 && !CROSSING_JUMP_P (BB_END (header))) 427 copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n); 428 } 429 } 430 } 431 else 432 { 433 /* We have not found suitable loop tail so do no rotation. */ 434 best_bb = back_edge->src; 435 } 436 best_bb->aux = NULL; 437 return best_bb; 438 } 439 440 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do 441 not include basic blocks whose probability is lower than BRANCH_TH or whose 442 count is lower than EXEC_TH into traces (or whose count is lower than 443 COUNT_TH). Store the new traces into TRACES and modify the number of 444 traces *N_TRACES. Set the round (which the trace belongs to) to ROUND. 445 The function expects starting basic blocks to be in *HEAP and will delete 446 *HEAP and store starting points for the next round into new *HEAP. */ 447 448 static void 449 find_traces_1_round (int branch_th, profile_count count_th, 450 struct trace *traces, int *n_traces, int round, 451 bb_heap_t **heap, int number_of_rounds) 452 { 453 /* Heap for discarded basic blocks which are possible starting points for 454 the next round. */ 455 bb_heap_t *new_heap = new bb_heap_t (LONG_MIN); 456 bool for_size = optimize_function_for_size_p (cfun); 457 458 while (!(*heap)->empty ()) 459 { 460 basic_block bb; 461 struct trace *trace; 462 edge best_edge, e; 463 long key; 464 edge_iterator ei; 465 466 bb = (*heap)->extract_min (); 467 bbd[bb->index].heap = NULL; 468 bbd[bb->index].node = NULL; 469 470 if (dump_file) 471 fprintf (dump_file, "Getting bb %d\n", bb->index); 472 473 /* If the BB's count is too low, send BB to the next round. When 474 partitioning hot/cold blocks into separate sections, make sure all 475 the cold blocks (and ONLY the cold blocks) go into the (extra) final 476 round. When optimizing for size, do not push to next round. */ 477 478 if (!for_size 479 && push_to_next_round_p (bb, round, number_of_rounds, 480 count_th)) 481 { 482 int key = bb_to_key (bb); 483 bbd[bb->index].heap = new_heap; 484 bbd[bb->index].node = new_heap->insert (key, bb); 485 486 if (dump_file) 487 fprintf (dump_file, 488 " Possible start point of next round: %d (key: %d)\n", 489 bb->index, key); 490 continue; 491 } 492 493 trace = traces + *n_traces; 494 trace->first = bb; 495 trace->round = round; 496 trace->length = 0; 497 bbd[bb->index].in_trace = *n_traces; 498 (*n_traces)++; 499 500 do 501 { 502 bool ends_in_call; 503 504 /* The probability and count of the best edge. */ 505 profile_probability best_prob = profile_probability::uninitialized (); 506 profile_count best_count = profile_count::uninitialized (); 507 508 best_edge = NULL; 509 mark_bb_visited (bb, *n_traces); 510 trace->length++; 511 512 if (dump_file) 513 fprintf (dump_file, "Basic block %d was visited in trace %d\n", 514 bb->index, *n_traces); 515 516 ends_in_call = block_ends_with_call_p (bb); 517 518 /* Select the successor that will be placed after BB. */ 519 FOR_EACH_EDGE (e, ei, bb->succs) 520 { 521 gcc_assert (!(e->flags & EDGE_FAKE)); 522 523 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) 524 continue; 525 526 if (bb_visited_trace (e->dest) 527 && bb_visited_trace (e->dest) != *n_traces) 528 continue; 529 530 /* If partitioning hot/cold basic blocks, don't consider edges 531 that cross section boundaries. */ 532 if (BB_PARTITION (e->dest) != BB_PARTITION (bb)) 533 continue; 534 535 profile_probability prob = e->probability; 536 profile_count count = e->dest->count; 537 538 /* The only sensible preference for a call instruction is the 539 fallthru edge. Don't bother selecting anything else. */ 540 if (ends_in_call) 541 { 542 if (e->flags & EDGE_CAN_FALLTHRU) 543 { 544 best_edge = e; 545 best_prob = prob; 546 best_count = count; 547 } 548 continue; 549 } 550 551 /* Edge that cannot be fallthru or improbable or infrequent 552 successor (i.e. it is unsuitable successor). When optimizing 553 for size, ignore the probability and count. */ 554 if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX) 555 || !prob.initialized_p () 556 || ((prob.to_reg_br_prob_base () < branch_th 557 || e->count () < count_th) && (!for_size))) 558 continue; 559 560 if (better_edge_p (bb, e, prob, count, best_prob, best_count, 561 best_edge)) 562 { 563 best_edge = e; 564 best_prob = prob; 565 best_count = count; 566 } 567 } 568 569 /* If the best destination has multiple predecessors and can be 570 duplicated cheaper than a jump, don't allow it to be added to 571 a trace; we'll duplicate it when connecting the traces later. 572 However, we need to check that this duplication wouldn't leave 573 the best destination with only crossing predecessors, because 574 this would change its effective partition from hot to cold. */ 575 if (best_edge 576 && EDGE_COUNT (best_edge->dest->preds) >= 2 577 && copy_bb_p (best_edge->dest, 0)) 578 { 579 bool only_crossing_preds = true; 580 edge e; 581 edge_iterator ei; 582 FOR_EACH_EDGE (e, ei, best_edge->dest->preds) 583 if (e != best_edge && !(e->flags & EDGE_CROSSING)) 584 { 585 only_crossing_preds = false; 586 break; 587 } 588 if (!only_crossing_preds) 589 best_edge = NULL; 590 } 591 592 /* If the best destination has multiple successors or predecessors, 593 don't allow it to be added when optimizing for size. This makes 594 sure predecessors with smaller index are handled before the best 595 destinarion. It breaks long trace and reduces long jumps. 596 597 Take if-then-else as an example. 598 A 599 / \ 600 B C 601 \ / 602 D 603 If we do not remove the best edge B->D/C->D, the final order might 604 be A B D ... C. C is at the end of the program. If D's successors 605 and D are complicated, might need long jumps for A->C and C->D. 606 Similar issue for order: A C D ... B. 607 608 After removing the best edge, the final result will be ABCD/ ACBD. 609 It does not add jump compared with the previous order. But it 610 reduces the possibility of long jumps. */ 611 if (best_edge && for_size 612 && (EDGE_COUNT (best_edge->dest->succs) > 1 613 || EDGE_COUNT (best_edge->dest->preds) > 1)) 614 best_edge = NULL; 615 616 /* Add all non-selected successors to the heaps. */ 617 FOR_EACH_EDGE (e, ei, bb->succs) 618 { 619 if (e == best_edge 620 || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) 621 || bb_visited_trace (e->dest)) 622 continue; 623 624 key = bb_to_key (e->dest); 625 626 if (bbd[e->dest->index].heap) 627 { 628 /* E->DEST is already in some heap. */ 629 if (key != bbd[e->dest->index].node->get_key ()) 630 { 631 if (dump_file) 632 { 633 fprintf (dump_file, 634 "Changing key for bb %d from %ld to %ld.\n", 635 e->dest->index, 636 (long) bbd[e->dest->index].node->get_key (), 637 key); 638 } 639 bbd[e->dest->index].heap->replace_key 640 (bbd[e->dest->index].node, key); 641 } 642 } 643 else 644 { 645 bb_heap_t *which_heap = *heap; 646 647 profile_probability prob = e->probability; 648 649 if (!(e->flags & EDGE_CAN_FALLTHRU) 650 || (e->flags & EDGE_COMPLEX) 651 || !prob.initialized_p () 652 || prob.to_reg_br_prob_base () < branch_th 653 || e->count () < count_th) 654 { 655 /* When partitioning hot/cold basic blocks, make sure 656 the cold blocks (and only the cold blocks) all get 657 pushed to the last round of trace collection. When 658 optimizing for size, do not push to next round. */ 659 660 if (!for_size && push_to_next_round_p (e->dest, round, 661 number_of_rounds, 662 count_th)) 663 which_heap = new_heap; 664 } 665 666 bbd[e->dest->index].heap = which_heap; 667 bbd[e->dest->index].node = which_heap->insert (key, e->dest); 668 669 if (dump_file) 670 { 671 fprintf (dump_file, 672 " Possible start of %s round: %d (key: %ld)\n", 673 (which_heap == new_heap) ? "next" : "this", 674 e->dest->index, (long) key); 675 } 676 677 } 678 } 679 680 if (best_edge) /* Suitable successor was found. */ 681 { 682 if (bb_visited_trace (best_edge->dest) == *n_traces) 683 { 684 /* We do nothing with one basic block loops. */ 685 if (best_edge->dest != bb) 686 { 687 if (best_edge->count () 688 > best_edge->dest->count.apply_scale (4, 5)) 689 { 690 /* The loop has at least 4 iterations. If the loop 691 header is not the first block of the function 692 we can rotate the loop. */ 693 694 if (best_edge->dest 695 != ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) 696 { 697 if (dump_file) 698 { 699 fprintf (dump_file, 700 "Rotating loop %d - %d\n", 701 best_edge->dest->index, bb->index); 702 } 703 bb->aux = best_edge->dest; 704 bbd[best_edge->dest->index].in_trace = 705 (*n_traces) - 1; 706 bb = rotate_loop (best_edge, trace, *n_traces); 707 } 708 } 709 else 710 { 711 /* The loop has less than 4 iterations. */ 712 713 if (single_succ_p (bb) 714 && copy_bb_p (best_edge->dest, 715 optimize_edge_for_speed_p 716 (best_edge))) 717 { 718 bb = copy_bb (best_edge->dest, best_edge, bb, 719 *n_traces); 720 trace->length++; 721 } 722 } 723 } 724 725 /* Terminate the trace. */ 726 break; 727 } 728 else 729 { 730 /* Check for a situation 731 732 A 733 /| 734 B | 735 \| 736 C 737 738 where 739 AB->count () + BC->count () >= AC->count (). 740 (i.e. 2 * B->count >= AC->count ) 741 Best ordering is then A B C. 742 743 When optimizing for size, A B C is always the best order. 744 745 This situation is created for example by: 746 747 if (A) B; 748 C; 749 750 */ 751 752 FOR_EACH_EDGE (e, ei, bb->succs) 753 if (e != best_edge 754 && (e->flags & EDGE_CAN_FALLTHRU) 755 && !(e->flags & EDGE_COMPLEX) 756 && !bb_visited_trace (e->dest) 757 && single_pred_p (e->dest) 758 && !(e->flags & EDGE_CROSSING) 759 && single_succ_p (e->dest) 760 && (single_succ_edge (e->dest)->flags 761 & EDGE_CAN_FALLTHRU) 762 && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX) 763 && single_succ (e->dest) == best_edge->dest 764 && (e->dest->count.apply_scale (2, 1) 765 >= best_edge->count () || for_size)) 766 { 767 best_edge = e; 768 if (dump_file) 769 fprintf (dump_file, "Selecting BB %d\n", 770 best_edge->dest->index); 771 break; 772 } 773 774 bb->aux = best_edge->dest; 775 bbd[best_edge->dest->index].in_trace = (*n_traces) - 1; 776 bb = best_edge->dest; 777 } 778 } 779 } 780 while (best_edge); 781 trace->last = bb; 782 bbd[trace->first->index].start_of_trace = *n_traces - 1; 783 if (bbd[trace->last->index].end_of_trace != *n_traces - 1) 784 { 785 bbd[trace->last->index].end_of_trace = *n_traces - 1; 786 /* Update the cached maximum frequency for interesting predecessor 787 edges for successors of the new trace end. */ 788 FOR_EACH_EDGE (e, ei, trace->last->succs) 789 if (EDGE_FREQUENCY (e) > bbd[e->dest->index].priority) 790 bbd[e->dest->index].priority = EDGE_FREQUENCY (e); 791 } 792 793 /* The trace is terminated so we have to recount the keys in heap 794 (some block can have a lower key because now one of its predecessors 795 is an end of the trace). */ 796 FOR_EACH_EDGE (e, ei, bb->succs) 797 { 798 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) 799 || bb_visited_trace (e->dest)) 800 continue; 801 802 if (bbd[e->dest->index].heap) 803 { 804 key = bb_to_key (e->dest); 805 if (key != bbd[e->dest->index].node->get_key ()) 806 { 807 if (dump_file) 808 { 809 fprintf (dump_file, 810 "Changing key for bb %d from %ld to %ld.\n", 811 e->dest->index, 812 (long) bbd[e->dest->index].node->get_key (), key); 813 } 814 bbd[e->dest->index].heap->replace_key 815 (bbd[e->dest->index].node, key); 816 } 817 } 818 } 819 } 820 821 delete (*heap); 822 823 /* "Return" the new heap. */ 824 *heap = new_heap; 825 } 826 827 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add 828 it to trace after BB, mark OLD_BB visited and update pass' data structures 829 (TRACE is a number of trace which OLD_BB is duplicated to). */ 830 831 static basic_block 832 copy_bb (basic_block old_bb, edge e, basic_block bb, int trace) 833 { 834 basic_block new_bb; 835 836 new_bb = duplicate_block (old_bb, e, bb); 837 BB_COPY_PARTITION (new_bb, old_bb); 838 839 gcc_assert (e->dest == new_bb); 840 841 if (dump_file) 842 fprintf (dump_file, 843 "Duplicated bb %d (created bb %d)\n", 844 old_bb->index, new_bb->index); 845 846 if (new_bb->index >= array_size 847 || last_basic_block_for_fn (cfun) > array_size) 848 { 849 int i; 850 int new_size; 851 852 new_size = MAX (last_basic_block_for_fn (cfun), new_bb->index + 1); 853 new_size = GET_ARRAY_SIZE (new_size); 854 bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size); 855 for (i = array_size; i < new_size; i++) 856 { 857 bbd[i].start_of_trace = -1; 858 bbd[i].end_of_trace = -1; 859 bbd[i].in_trace = -1; 860 bbd[i].visited = 0; 861 bbd[i].priority = -1; 862 bbd[i].heap = NULL; 863 bbd[i].node = NULL; 864 } 865 array_size = new_size; 866 867 if (dump_file) 868 { 869 fprintf (dump_file, 870 "Growing the dynamic array to %d elements.\n", 871 array_size); 872 } 873 } 874 875 gcc_assert (!bb_visited_trace (e->dest)); 876 mark_bb_visited (new_bb, trace); 877 new_bb->aux = bb->aux; 878 bb->aux = new_bb; 879 880 bbd[new_bb->index].in_trace = trace; 881 882 return new_bb; 883 } 884 885 /* Compute and return the key (for the heap) of the basic block BB. */ 886 887 static long 888 bb_to_key (basic_block bb) 889 { 890 edge e; 891 edge_iterator ei; 892 893 /* Use index as key to align with its original order. */ 894 if (optimize_function_for_size_p (cfun)) 895 return bb->index; 896 897 /* Do not start in probably never executed blocks. */ 898 899 if (BB_PARTITION (bb) == BB_COLD_PARTITION 900 || probably_never_executed_bb_p (cfun, bb)) 901 return BB_FREQ_MAX; 902 903 /* Prefer blocks whose predecessor is an end of some trace 904 or whose predecessor edge is EDGE_DFS_BACK. */ 905 int priority = bbd[bb->index].priority; 906 if (priority == -1) 907 { 908 priority = 0; 909 FOR_EACH_EDGE (e, ei, bb->preds) 910 { 911 if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) 912 && bbd[e->src->index].end_of_trace >= 0) 913 || (e->flags & EDGE_DFS_BACK)) 914 { 915 int edge_freq = EDGE_FREQUENCY (e); 916 917 if (edge_freq > priority) 918 priority = edge_freq; 919 } 920 } 921 bbd[bb->index].priority = priority; 922 } 923 924 if (priority) 925 /* The block with priority should have significantly lower key. */ 926 return -(100 * BB_FREQ_MAX + 100 * priority + bb->count.to_frequency (cfun)); 927 928 return -bb->count.to_frequency (cfun); 929 } 930 931 /* Return true when the edge E from basic block BB is better than the temporary 932 best edge (details are in function). The probability of edge E is PROB. The 933 count of the successor is COUNT. The current best probability is 934 BEST_PROB, the best count is BEST_COUNT. 935 The edge is considered to be equivalent when PROB does not differ much from 936 BEST_PROB; similarly for count. */ 937 938 static bool 939 better_edge_p (const_basic_block bb, const_edge e, profile_probability prob, 940 profile_count count, profile_probability best_prob, 941 profile_count best_count, const_edge cur_best_edge) 942 { 943 bool is_better_edge; 944 945 /* The BEST_* values do not have to be best, but can be a bit smaller than 946 maximum values. */ 947 profile_probability diff_prob = best_prob.apply_scale (1, 10); 948 949 /* The smaller one is better to keep the original order. */ 950 if (optimize_function_for_size_p (cfun)) 951 return !cur_best_edge 952 || cur_best_edge->dest->index > e->dest->index; 953 954 /* Those edges are so expensive that continuing a trace is not useful 955 performance wise. */ 956 if (e->flags & (EDGE_ABNORMAL | EDGE_EH)) 957 return false; 958 959 if (prob > best_prob + diff_prob 960 || (!best_prob.initialized_p () 961 && prob > profile_probability::guessed_never ())) 962 /* The edge has higher probability than the temporary best edge. */ 963 is_better_edge = true; 964 else if (prob < best_prob - diff_prob) 965 /* The edge has lower probability than the temporary best edge. */ 966 is_better_edge = false; 967 else 968 { 969 profile_count diff_count = best_count.apply_scale (1, 10); 970 if (count < best_count - diff_count 971 || (!best_count.initialized_p () 972 && count.nonzero_p ())) 973 /* The edge and the temporary best edge have almost equivalent 974 probabilities. The higher countuency of a successor now means 975 that there is another edge going into that successor. 976 This successor has lower countuency so it is better. */ 977 is_better_edge = true; 978 else if (count > best_count + diff_count) 979 /* This successor has higher countuency so it is worse. */ 980 is_better_edge = false; 981 else if (e->dest->prev_bb == bb) 982 /* The edges have equivalent probabilities and the successors 983 have equivalent frequencies. Select the previous successor. */ 984 is_better_edge = true; 985 else 986 is_better_edge = false; 987 } 988 989 return is_better_edge; 990 } 991 992 /* Return true when the edge E is better than the temporary best edge 993 CUR_BEST_EDGE. If SRC_INDEX_P is true, the function compares the src bb of 994 E and CUR_BEST_EDGE; otherwise it will compare the dest bb. 995 BEST_LEN is the trace length of src (or dest) bb in CUR_BEST_EDGE. 996 TRACES record the information about traces. 997 When optimizing for size, the edge with smaller index is better. 998 When optimizing for speed, the edge with bigger probability or longer trace 999 is better. */ 1000 1001 static bool 1002 connect_better_edge_p (const_edge e, bool src_index_p, int best_len, 1003 const_edge cur_best_edge, struct trace *traces) 1004 { 1005 int e_index; 1006 int b_index; 1007 bool is_better_edge; 1008 1009 if (!cur_best_edge) 1010 return true; 1011 1012 if (optimize_function_for_size_p (cfun)) 1013 { 1014 e_index = src_index_p ? e->src->index : e->dest->index; 1015 b_index = src_index_p ? cur_best_edge->src->index 1016 : cur_best_edge->dest->index; 1017 /* The smaller one is better to keep the original order. */ 1018 return b_index > e_index; 1019 } 1020 1021 if (src_index_p) 1022 { 1023 e_index = e->src->index; 1024 1025 /* We are looking for predecessor, so probabilities are not that 1026 informative. We do not want to connect A to B becuse A has 1027 only one sucessor (probablity is 100%) while there is edge 1028 A' to B where probability is 90% but which is much more frequent. */ 1029 if (e->count () > cur_best_edge->count ()) 1030 /* The edge has higher probability than the temporary best edge. */ 1031 is_better_edge = true; 1032 else if (e->count () < cur_best_edge->count ()) 1033 /* The edge has lower probability than the temporary best edge. */ 1034 is_better_edge = false; 1035 if (e->probability > cur_best_edge->probability) 1036 /* The edge has higher probability than the temporary best edge. */ 1037 is_better_edge = true; 1038 else if (e->probability < cur_best_edge->probability) 1039 /* The edge has lower probability than the temporary best edge. */ 1040 is_better_edge = false; 1041 else if (traces[bbd[e_index].end_of_trace].length > best_len) 1042 /* The edge and the temporary best edge have equivalent probabilities. 1043 The edge with longer trace is better. */ 1044 is_better_edge = true; 1045 else 1046 is_better_edge = false; 1047 } 1048 else 1049 { 1050 e_index = e->dest->index; 1051 1052 if (e->probability > cur_best_edge->probability) 1053 /* The edge has higher probability than the temporary best edge. */ 1054 is_better_edge = true; 1055 else if (e->probability < cur_best_edge->probability) 1056 /* The edge has lower probability than the temporary best edge. */ 1057 is_better_edge = false; 1058 else if (traces[bbd[e_index].start_of_trace].length > best_len) 1059 /* The edge and the temporary best edge have equivalent probabilities. 1060 The edge with longer trace is better. */ 1061 is_better_edge = true; 1062 else 1063 is_better_edge = false; 1064 } 1065 1066 return is_better_edge; 1067 } 1068 1069 /* Connect traces in array TRACES, N_TRACES is the count of traces. */ 1070 1071 static void 1072 connect_traces (int n_traces, struct trace *traces) 1073 { 1074 int i; 1075 bool *connected; 1076 bool two_passes; 1077 int last_trace; 1078 int current_pass; 1079 int current_partition; 1080 profile_count count_threshold; 1081 bool for_size = optimize_function_for_size_p (cfun); 1082 1083 count_threshold = max_entry_count.apply_scale (DUPLICATION_THRESHOLD, 1000); 1084 1085 connected = XCNEWVEC (bool, n_traces); 1086 last_trace = -1; 1087 current_pass = 1; 1088 current_partition = BB_PARTITION (traces[0].first); 1089 two_passes = false; 1090 1091 if (crtl->has_bb_partition) 1092 for (i = 0; i < n_traces && !two_passes; i++) 1093 if (BB_PARTITION (traces[0].first) 1094 != BB_PARTITION (traces[i].first)) 1095 two_passes = true; 1096 1097 for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++) 1098 { 1099 int t = i; 1100 int t2; 1101 edge e, best; 1102 int best_len; 1103 1104 if (i >= n_traces) 1105 { 1106 gcc_assert (two_passes && current_pass == 1); 1107 i = 0; 1108 t = i; 1109 current_pass = 2; 1110 if (current_partition == BB_HOT_PARTITION) 1111 current_partition = BB_COLD_PARTITION; 1112 else 1113 current_partition = BB_HOT_PARTITION; 1114 } 1115 1116 if (connected[t]) 1117 continue; 1118 1119 if (two_passes 1120 && BB_PARTITION (traces[t].first) != current_partition) 1121 continue; 1122 1123 connected[t] = true; 1124 1125 /* Find the predecessor traces. */ 1126 for (t2 = t; t2 > 0;) 1127 { 1128 edge_iterator ei; 1129 best = NULL; 1130 best_len = 0; 1131 FOR_EACH_EDGE (e, ei, traces[t2].first->preds) 1132 { 1133 int si = e->src->index; 1134 1135 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) 1136 && (e->flags & EDGE_CAN_FALLTHRU) 1137 && !(e->flags & EDGE_COMPLEX) 1138 && bbd[si].end_of_trace >= 0 1139 && !connected[bbd[si].end_of_trace] 1140 && (BB_PARTITION (e->src) == current_partition) 1141 && connect_better_edge_p (e, true, best_len, best, traces)) 1142 { 1143 best = e; 1144 best_len = traces[bbd[si].end_of_trace].length; 1145 } 1146 } 1147 if (best) 1148 { 1149 best->src->aux = best->dest; 1150 t2 = bbd[best->src->index].end_of_trace; 1151 connected[t2] = true; 1152 1153 if (dump_file) 1154 { 1155 fprintf (dump_file, "Connection: %d %d\n", 1156 best->src->index, best->dest->index); 1157 } 1158 } 1159 else 1160 break; 1161 } 1162 1163 if (last_trace >= 0) 1164 traces[last_trace].last->aux = traces[t2].first; 1165 last_trace = t; 1166 1167 /* Find the successor traces. */ 1168 while (1) 1169 { 1170 /* Find the continuation of the chain. */ 1171 edge_iterator ei; 1172 best = NULL; 1173 best_len = 0; 1174 FOR_EACH_EDGE (e, ei, traces[t].last->succs) 1175 { 1176 int di = e->dest->index; 1177 1178 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) 1179 && (e->flags & EDGE_CAN_FALLTHRU) 1180 && !(e->flags & EDGE_COMPLEX) 1181 && bbd[di].start_of_trace >= 0 1182 && !connected[bbd[di].start_of_trace] 1183 && (BB_PARTITION (e->dest) == current_partition) 1184 && connect_better_edge_p (e, false, best_len, best, traces)) 1185 { 1186 best = e; 1187 best_len = traces[bbd[di].start_of_trace].length; 1188 } 1189 } 1190 1191 if (for_size) 1192 { 1193 if (!best) 1194 /* Stop finding the successor traces. */ 1195 break; 1196 1197 /* It is OK to connect block n with block n + 1 or a block 1198 before n. For others, only connect to the loop header. */ 1199 if (best->dest->index > (traces[t].last->index + 1)) 1200 { 1201 int count = EDGE_COUNT (best->dest->preds); 1202 1203 FOR_EACH_EDGE (e, ei, best->dest->preds) 1204 if (e->flags & EDGE_DFS_BACK) 1205 count--; 1206 1207 /* If dest has multiple predecessors, skip it. We expect 1208 that one predecessor with smaller index connects with it 1209 later. */ 1210 if (count != 1) 1211 break; 1212 } 1213 1214 /* Only connect Trace n with Trace n + 1. It is conservative 1215 to keep the order as close as possible to the original order. 1216 It also helps to reduce long jumps. */ 1217 if (last_trace != bbd[best->dest->index].start_of_trace - 1) 1218 break; 1219 1220 if (dump_file) 1221 fprintf (dump_file, "Connection: %d %d\n", 1222 best->src->index, best->dest->index); 1223 1224 t = bbd[best->dest->index].start_of_trace; 1225 traces[last_trace].last->aux = traces[t].first; 1226 connected[t] = true; 1227 last_trace = t; 1228 } 1229 else if (best) 1230 { 1231 if (dump_file) 1232 { 1233 fprintf (dump_file, "Connection: %d %d\n", 1234 best->src->index, best->dest->index); 1235 } 1236 t = bbd[best->dest->index].start_of_trace; 1237 traces[last_trace].last->aux = traces[t].first; 1238 connected[t] = true; 1239 last_trace = t; 1240 } 1241 else 1242 { 1243 /* Try to connect the traces by duplication of 1 block. */ 1244 edge e2; 1245 basic_block next_bb = NULL; 1246 bool try_copy = false; 1247 1248 FOR_EACH_EDGE (e, ei, traces[t].last->succs) 1249 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) 1250 && (e->flags & EDGE_CAN_FALLTHRU) 1251 && !(e->flags & EDGE_COMPLEX) 1252 && (!best || e->probability > best->probability)) 1253 { 1254 edge_iterator ei; 1255 edge best2 = NULL; 1256 int best2_len = 0; 1257 1258 /* If the destination is a start of a trace which is only 1259 one block long, then no need to search the successor 1260 blocks of the trace. Accept it. */ 1261 if (bbd[e->dest->index].start_of_trace >= 0 1262 && traces[bbd[e->dest->index].start_of_trace].length 1263 == 1) 1264 { 1265 best = e; 1266 try_copy = true; 1267 continue; 1268 } 1269 1270 FOR_EACH_EDGE (e2, ei, e->dest->succs) 1271 { 1272 int di = e2->dest->index; 1273 1274 if (e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) 1275 || ((e2->flags & EDGE_CAN_FALLTHRU) 1276 && !(e2->flags & EDGE_COMPLEX) 1277 && bbd[di].start_of_trace >= 0 1278 && !connected[bbd[di].start_of_trace] 1279 && BB_PARTITION (e2->dest) == current_partition 1280 && e2->count () >= count_threshold 1281 && (!best2 1282 || e2->probability > best2->probability 1283 || (e2->probability == best2->probability 1284 && traces[bbd[di].start_of_trace].length 1285 > best2_len)))) 1286 { 1287 best = e; 1288 best2 = e2; 1289 if (e2->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) 1290 best2_len = traces[bbd[di].start_of_trace].length; 1291 else 1292 best2_len = INT_MAX; 1293 next_bb = e2->dest; 1294 try_copy = true; 1295 } 1296 } 1297 } 1298 1299 /* Copy tiny blocks always; copy larger blocks only when the 1300 edge is traversed frequently enough. */ 1301 if (try_copy 1302 && BB_PARTITION (best->src) == BB_PARTITION (best->dest) 1303 && copy_bb_p (best->dest, 1304 optimize_edge_for_speed_p (best) 1305 && (!best->count ().initialized_p () 1306 || best->count () >= count_threshold))) 1307 { 1308 basic_block new_bb; 1309 1310 if (dump_file) 1311 { 1312 fprintf (dump_file, "Connection: %d %d ", 1313 traces[t].last->index, best->dest->index); 1314 if (!next_bb) 1315 fputc ('\n', dump_file); 1316 else if (next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) 1317 fprintf (dump_file, "exit\n"); 1318 else 1319 fprintf (dump_file, "%d\n", next_bb->index); 1320 } 1321 1322 new_bb = copy_bb (best->dest, best, traces[t].last, t); 1323 traces[t].last = new_bb; 1324 if (next_bb && next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun)) 1325 { 1326 t = bbd[next_bb->index].start_of_trace; 1327 traces[last_trace].last->aux = traces[t].first; 1328 connected[t] = true; 1329 last_trace = t; 1330 } 1331 else 1332 break; /* Stop finding the successor traces. */ 1333 } 1334 else 1335 break; /* Stop finding the successor traces. */ 1336 } 1337 } 1338 } 1339 1340 if (dump_file) 1341 { 1342 basic_block bb; 1343 1344 fprintf (dump_file, "Final order:\n"); 1345 for (bb = traces[0].first; bb; bb = (basic_block) bb->aux) 1346 fprintf (dump_file, "%d ", bb->index); 1347 fprintf (dump_file, "\n"); 1348 fflush (dump_file); 1349 } 1350 1351 FREE (connected); 1352 } 1353 1354 /* Return true when BB can and should be copied. CODE_MAY_GROW is true 1355 when code size is allowed to grow by duplication. */ 1356 1357 static bool 1358 copy_bb_p (const_basic_block bb, int code_may_grow) 1359 { 1360 int size = 0; 1361 int max_size = uncond_jump_length; 1362 rtx_insn *insn; 1363 1364 if (EDGE_COUNT (bb->preds) < 2) 1365 return false; 1366 if (!can_duplicate_block_p (bb)) 1367 return false; 1368 1369 /* Avoid duplicating blocks which have many successors (PR/13430). */ 1370 if (EDGE_COUNT (bb->succs) > 8) 1371 return false; 1372 1373 if (code_may_grow && optimize_bb_for_speed_p (bb)) 1374 max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS); 1375 1376 FOR_BB_INSNS (bb, insn) 1377 { 1378 if (INSN_P (insn)) 1379 size += get_attr_min_length (insn); 1380 } 1381 1382 if (size <= max_size) 1383 return true; 1384 1385 if (dump_file) 1386 { 1387 fprintf (dump_file, 1388 "Block %d can't be copied because its size = %d.\n", 1389 bb->index, size); 1390 } 1391 1392 return false; 1393 } 1394 1395 /* Return the length of unconditional jump instruction. */ 1396 1397 int 1398 get_uncond_jump_length (void) 1399 { 1400 int length; 1401 1402 start_sequence (); 1403 rtx_code_label *label = emit_label (gen_label_rtx ()); 1404 rtx_insn *jump = emit_jump_insn (targetm.gen_jump (label)); 1405 length = get_attr_min_length (jump); 1406 end_sequence (); 1407 1408 return length; 1409 } 1410 1411 /* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions. 1412 Add a new landing pad that will just jump to the old one and split the 1413 edges so that no EH edge crosses partitions. */ 1414 1415 static void 1416 fix_up_crossing_landing_pad (eh_landing_pad old_lp, basic_block old_bb) 1417 { 1418 eh_landing_pad new_lp; 1419 basic_block new_bb, last_bb; 1420 rtx_insn *jump; 1421 unsigned new_partition; 1422 edge_iterator ei; 1423 edge e; 1424 1425 /* Generate the new landing-pad structure. */ 1426 new_lp = gen_eh_landing_pad (old_lp->region); 1427 new_lp->post_landing_pad = old_lp->post_landing_pad; 1428 new_lp->landing_pad = gen_label_rtx (); 1429 LABEL_PRESERVE_P (new_lp->landing_pad) = 1; 1430 1431 /* Put appropriate instructions in new bb. */ 1432 rtx_code_label *new_label = emit_label (new_lp->landing_pad); 1433 1434 rtx_code_label *old_label = block_label (old_bb); 1435 jump = emit_jump_insn (targetm.gen_jump (old_label)); 1436 JUMP_LABEL (jump) = old_label; 1437 1438 /* Create new basic block to be dest for lp. */ 1439 last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb; 1440 new_bb = create_basic_block (new_label, jump, last_bb); 1441 new_bb->aux = last_bb->aux; 1442 new_bb->count = old_bb->count; 1443 last_bb->aux = new_bb; 1444 1445 emit_barrier_after_bb (new_bb); 1446 1447 make_single_succ_edge (new_bb, old_bb, 0); 1448 1449 /* Make sure new bb is in the other partition. */ 1450 new_partition = BB_PARTITION (old_bb); 1451 new_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION; 1452 BB_SET_PARTITION (new_bb, new_partition); 1453 1454 /* Fix up the edges. */ 1455 for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; ) 1456 if (e->src != new_bb && BB_PARTITION (e->src) == new_partition) 1457 { 1458 rtx_insn *insn = BB_END (e->src); 1459 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX); 1460 1461 gcc_assert (note != NULL); 1462 gcc_checking_assert (INTVAL (XEXP (note, 0)) == old_lp->index); 1463 XEXP (note, 0) = GEN_INT (new_lp->index); 1464 1465 /* Adjust the edge to the new destination. */ 1466 redirect_edge_succ (e, new_bb); 1467 } 1468 else 1469 ei_next (&ei); 1470 } 1471 1472 1473 /* Ensure that all hot bbs are included in a hot path through the 1474 procedure. This is done by calling this function twice, once 1475 with WALK_UP true (to look for paths from the entry to hot bbs) and 1476 once with WALK_UP false (to look for paths from hot bbs to the exit). 1477 Returns the updated value of COLD_BB_COUNT and adds newly-hot bbs 1478 to BBS_IN_HOT_PARTITION. */ 1479 1480 static unsigned int 1481 sanitize_hot_paths (bool walk_up, unsigned int cold_bb_count, 1482 vec<basic_block> *bbs_in_hot_partition) 1483 { 1484 /* Callers check this. */ 1485 gcc_checking_assert (cold_bb_count); 1486 1487 /* Keep examining hot bbs while we still have some left to check 1488 and there are remaining cold bbs. */ 1489 vec<basic_block> hot_bbs_to_check = bbs_in_hot_partition->copy (); 1490 while (! hot_bbs_to_check.is_empty () 1491 && cold_bb_count) 1492 { 1493 basic_block bb = hot_bbs_to_check.pop (); 1494 vec<edge, va_gc> *edges = walk_up ? bb->preds : bb->succs; 1495 edge e; 1496 edge_iterator ei; 1497 profile_probability highest_probability 1498 = profile_probability::uninitialized (); 1499 profile_count highest_count = profile_count::uninitialized (); 1500 bool found = false; 1501 1502 /* Walk the preds/succs and check if there is at least one already 1503 marked hot. Keep track of the most frequent pred/succ so that we 1504 can mark it hot if we don't find one. */ 1505 FOR_EACH_EDGE (e, ei, edges) 1506 { 1507 basic_block reach_bb = walk_up ? e->src : e->dest; 1508 1509 if (e->flags & EDGE_DFS_BACK) 1510 continue; 1511 1512 /* Do not expect profile insanities when profile was not adjusted. */ 1513 if (e->probability == profile_probability::never () 1514 || e->count () == profile_count::zero ()) 1515 continue; 1516 1517 if (BB_PARTITION (reach_bb) != BB_COLD_PARTITION) 1518 { 1519 found = true; 1520 break; 1521 } 1522 /* The following loop will look for the hottest edge via 1523 the edge count, if it is non-zero, then fallback to 1524 the edge probability. */ 1525 if (!(e->count () > highest_count)) 1526 highest_count = e->count (); 1527 if (!highest_probability.initialized_p () 1528 || e->probability > highest_probability) 1529 highest_probability = e->probability; 1530 } 1531 1532 /* If bb is reached by (or reaches, in the case of !WALK_UP) another hot 1533 block (or unpartitioned, e.g. the entry block) then it is ok. If not, 1534 then the most frequent pred (or succ) needs to be adjusted. In the 1535 case where multiple preds/succs have the same frequency (e.g. a 1536 50-50 branch), then both will be adjusted. */ 1537 if (found) 1538 continue; 1539 1540 FOR_EACH_EDGE (e, ei, edges) 1541 { 1542 if (e->flags & EDGE_DFS_BACK) 1543 continue; 1544 /* Do not expect profile insanities when profile was not adjusted. */ 1545 if (e->probability == profile_probability::never () 1546 || e->count () == profile_count::zero ()) 1547 continue; 1548 /* Select the hottest edge using the edge count, if it is non-zero, 1549 then fallback to the edge probability. */ 1550 if (highest_count.initialized_p ()) 1551 { 1552 if (!(e->count () >= highest_count)) 1553 continue; 1554 } 1555 else if (!(e->probability >= highest_probability)) 1556 continue; 1557 1558 basic_block reach_bb = walk_up ? e->src : e->dest; 1559 1560 /* We have a hot bb with an immediate dominator that is cold. 1561 The dominator needs to be re-marked hot. */ 1562 BB_SET_PARTITION (reach_bb, BB_HOT_PARTITION); 1563 if (dump_file) 1564 fprintf (dump_file, "Promoting bb %i to hot partition to sanitize " 1565 "profile of bb %i in %s walk\n", reach_bb->index, 1566 bb->index, walk_up ? "backward" : "forward"); 1567 cold_bb_count--; 1568 1569 /* Now we need to examine newly-hot reach_bb to see if it is also 1570 dominated by a cold bb. */ 1571 bbs_in_hot_partition->safe_push (reach_bb); 1572 hot_bbs_to_check.safe_push (reach_bb); 1573 } 1574 } 1575 1576 return cold_bb_count; 1577 } 1578 1579 1580 /* Find the basic blocks that are rarely executed and need to be moved to 1581 a separate section of the .o file (to cut down on paging and improve 1582 cache locality). Return a vector of all edges that cross. */ 1583 1584 static vec<edge> 1585 find_rarely_executed_basic_blocks_and_crossing_edges (void) 1586 { 1587 vec<edge> crossing_edges = vNULL; 1588 basic_block bb; 1589 edge e; 1590 edge_iterator ei; 1591 unsigned int cold_bb_count = 0; 1592 auto_vec<basic_block> bbs_in_hot_partition; 1593 1594 propagate_unlikely_bbs_forward (); 1595 1596 /* Mark which partition (hot/cold) each basic block belongs in. */ 1597 FOR_EACH_BB_FN (bb, cfun) 1598 { 1599 bool cold_bb = false; 1600 1601 if (probably_never_executed_bb_p (cfun, bb)) 1602 { 1603 /* Handle profile insanities created by upstream optimizations 1604 by also checking the incoming edge weights. If there is a non-cold 1605 incoming edge, conservatively prevent this block from being split 1606 into the cold section. */ 1607 cold_bb = true; 1608 FOR_EACH_EDGE (e, ei, bb->preds) 1609 if (!probably_never_executed_edge_p (cfun, e)) 1610 { 1611 cold_bb = false; 1612 break; 1613 } 1614 } 1615 if (cold_bb) 1616 { 1617 BB_SET_PARTITION (bb, BB_COLD_PARTITION); 1618 cold_bb_count++; 1619 } 1620 else 1621 { 1622 BB_SET_PARTITION (bb, BB_HOT_PARTITION); 1623 bbs_in_hot_partition.safe_push (bb); 1624 } 1625 } 1626 1627 /* Ensure that hot bbs are included along a hot path from the entry to exit. 1628 Several different possibilities may include cold bbs along all paths 1629 to/from a hot bb. One is that there are edge weight insanities 1630 due to optimization phases that do not properly update basic block profile 1631 counts. The second is that the entry of the function may not be hot, because 1632 it is entered fewer times than the number of profile training runs, but there 1633 is a loop inside the function that causes blocks within the function to be 1634 above the threshold for hotness. This is fixed by walking up from hot bbs 1635 to the entry block, and then down from hot bbs to the exit, performing 1636 partitioning fixups as necessary. */ 1637 if (cold_bb_count) 1638 { 1639 mark_dfs_back_edges (); 1640 cold_bb_count = sanitize_hot_paths (true, cold_bb_count, 1641 &bbs_in_hot_partition); 1642 if (cold_bb_count) 1643 sanitize_hot_paths (false, cold_bb_count, &bbs_in_hot_partition); 1644 1645 hash_set <basic_block> set; 1646 find_bbs_reachable_by_hot_paths (&set); 1647 FOR_EACH_BB_FN (bb, cfun) 1648 if (!set.contains (bb)) 1649 BB_SET_PARTITION (bb, BB_COLD_PARTITION); 1650 } 1651 1652 /* The format of .gcc_except_table does not allow landing pads to 1653 be in a different partition as the throw. Fix this by either 1654 moving or duplicating the landing pads. */ 1655 if (cfun->eh->lp_array) 1656 { 1657 unsigned i; 1658 eh_landing_pad lp; 1659 1660 FOR_EACH_VEC_ELT (*cfun->eh->lp_array, i, lp) 1661 { 1662 bool all_same, all_diff; 1663 1664 if (lp == NULL 1665 || lp->landing_pad == NULL_RTX 1666 || !LABEL_P (lp->landing_pad)) 1667 continue; 1668 1669 all_same = all_diff = true; 1670 bb = BLOCK_FOR_INSN (lp->landing_pad); 1671 FOR_EACH_EDGE (e, ei, bb->preds) 1672 { 1673 gcc_assert (e->flags & EDGE_EH); 1674 if (BB_PARTITION (bb) == BB_PARTITION (e->src)) 1675 all_diff = false; 1676 else 1677 all_same = false; 1678 } 1679 1680 if (all_same) 1681 ; 1682 else if (all_diff) 1683 { 1684 int which = BB_PARTITION (bb); 1685 which ^= BB_HOT_PARTITION | BB_COLD_PARTITION; 1686 BB_SET_PARTITION (bb, which); 1687 } 1688 else 1689 fix_up_crossing_landing_pad (lp, bb); 1690 } 1691 } 1692 1693 /* Mark every edge that crosses between sections. */ 1694 1695 FOR_EACH_BB_FN (bb, cfun) 1696 FOR_EACH_EDGE (e, ei, bb->succs) 1697 { 1698 unsigned int flags = e->flags; 1699 1700 /* We should never have EDGE_CROSSING set yet. */ 1701 gcc_checking_assert ((flags & EDGE_CROSSING) == 0); 1702 1703 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) 1704 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) 1705 && BB_PARTITION (e->src) != BB_PARTITION (e->dest)) 1706 { 1707 crossing_edges.safe_push (e); 1708 flags |= EDGE_CROSSING; 1709 } 1710 1711 /* Now that we've split eh edges as appropriate, allow landing pads 1712 to be merged with the post-landing pads. */ 1713 flags &= ~EDGE_PRESERVE; 1714 1715 e->flags = flags; 1716 } 1717 1718 return crossing_edges; 1719 } 1720 1721 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */ 1722 1723 static void 1724 set_edge_can_fallthru_flag (void) 1725 { 1726 basic_block bb; 1727 1728 FOR_EACH_BB_FN (bb, cfun) 1729 { 1730 edge e; 1731 edge_iterator ei; 1732 1733 FOR_EACH_EDGE (e, ei, bb->succs) 1734 { 1735 e->flags &= ~EDGE_CAN_FALLTHRU; 1736 1737 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */ 1738 if (e->flags & EDGE_FALLTHRU) 1739 e->flags |= EDGE_CAN_FALLTHRU; 1740 } 1741 1742 /* If the BB ends with an invertible condjump all (2) edges are 1743 CAN_FALLTHRU edges. */ 1744 if (EDGE_COUNT (bb->succs) != 2) 1745 continue; 1746 if (!any_condjump_p (BB_END (bb))) 1747 continue; 1748 1749 rtx_jump_insn *bb_end_jump = as_a <rtx_jump_insn *> (BB_END (bb)); 1750 if (!invert_jump (bb_end_jump, JUMP_LABEL (bb_end_jump), 0)) 1751 continue; 1752 invert_jump (bb_end_jump, JUMP_LABEL (bb_end_jump), 0); 1753 EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU; 1754 EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU; 1755 } 1756 } 1757 1758 /* If any destination of a crossing edge does not have a label, add label; 1759 Convert any easy fall-through crossing edges to unconditional jumps. */ 1760 1761 static void 1762 add_labels_and_missing_jumps (vec<edge> crossing_edges) 1763 { 1764 size_t i; 1765 edge e; 1766 1767 FOR_EACH_VEC_ELT (crossing_edges, i, e) 1768 { 1769 basic_block src = e->src; 1770 basic_block dest = e->dest; 1771 rtx_jump_insn *new_jump; 1772 1773 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) 1774 continue; 1775 1776 /* Make sure dest has a label. */ 1777 rtx_code_label *label = block_label (dest); 1778 1779 /* Nothing to do for non-fallthru edges. */ 1780 if (src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) 1781 continue; 1782 if ((e->flags & EDGE_FALLTHRU) == 0) 1783 continue; 1784 1785 /* If the block does not end with a control flow insn, then we 1786 can trivially add a jump to the end to fixup the crossing. 1787 Otherwise the jump will have to go in a new bb, which will 1788 be handled by fix_up_fall_thru_edges function. */ 1789 if (control_flow_insn_p (BB_END (src))) 1790 continue; 1791 1792 /* Make sure there's only one successor. */ 1793 gcc_assert (single_succ_p (src)); 1794 1795 new_jump = emit_jump_insn_after (targetm.gen_jump (label), BB_END (src)); 1796 BB_END (src) = new_jump; 1797 JUMP_LABEL (new_jump) = label; 1798 LABEL_NUSES (label) += 1; 1799 1800 emit_barrier_after_bb (src); 1801 1802 /* Mark edge as non-fallthru. */ 1803 e->flags &= ~EDGE_FALLTHRU; 1804 } 1805 } 1806 1807 /* Find any bb's where the fall-through edge is a crossing edge (note that 1808 these bb's must also contain a conditional jump or end with a call 1809 instruction; we've already dealt with fall-through edges for blocks 1810 that didn't have a conditional jump or didn't end with call instruction 1811 in the call to add_labels_and_missing_jumps). Convert the fall-through 1812 edge to non-crossing edge by inserting a new bb to fall-through into. 1813 The new bb will contain an unconditional jump (crossing edge) to the 1814 original fall through destination. */ 1815 1816 static void 1817 fix_up_fall_thru_edges (void) 1818 { 1819 basic_block cur_bb; 1820 1821 FOR_EACH_BB_FN (cur_bb, cfun) 1822 { 1823 edge succ1; 1824 edge succ2; 1825 edge fall_thru = NULL; 1826 edge cond_jump = NULL; 1827 1828 fall_thru = NULL; 1829 if (EDGE_COUNT (cur_bb->succs) > 0) 1830 succ1 = EDGE_SUCC (cur_bb, 0); 1831 else 1832 succ1 = NULL; 1833 1834 if (EDGE_COUNT (cur_bb->succs) > 1) 1835 succ2 = EDGE_SUCC (cur_bb, 1); 1836 else 1837 succ2 = NULL; 1838 1839 /* Find the fall-through edge. */ 1840 1841 if (succ1 1842 && (succ1->flags & EDGE_FALLTHRU)) 1843 { 1844 fall_thru = succ1; 1845 cond_jump = succ2; 1846 } 1847 else if (succ2 1848 && (succ2->flags & EDGE_FALLTHRU)) 1849 { 1850 fall_thru = succ2; 1851 cond_jump = succ1; 1852 } 1853 else if (succ2 && EDGE_COUNT (cur_bb->succs) > 2) 1854 fall_thru = find_fallthru_edge (cur_bb->succs); 1855 1856 if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))) 1857 { 1858 /* Check to see if the fall-thru edge is a crossing edge. */ 1859 1860 if (fall_thru->flags & EDGE_CROSSING) 1861 { 1862 /* The fall_thru edge crosses; now check the cond jump edge, if 1863 it exists. */ 1864 1865 bool cond_jump_crosses = true; 1866 int invert_worked = 0; 1867 rtx_insn *old_jump = BB_END (cur_bb); 1868 1869 /* Find the jump instruction, if there is one. */ 1870 1871 if (cond_jump) 1872 { 1873 if (!(cond_jump->flags & EDGE_CROSSING)) 1874 cond_jump_crosses = false; 1875 1876 /* We know the fall-thru edge crosses; if the cond 1877 jump edge does NOT cross, and its destination is the 1878 next block in the bb order, invert the jump 1879 (i.e. fix it so the fall through does not cross and 1880 the cond jump does). */ 1881 1882 if (!cond_jump_crosses) 1883 { 1884 /* Find label in fall_thru block. We've already added 1885 any missing labels, so there must be one. */ 1886 1887 rtx_code_label *fall_thru_label 1888 = block_label (fall_thru->dest); 1889 1890 if (old_jump && fall_thru_label) 1891 { 1892 rtx_jump_insn *old_jump_insn 1893 = dyn_cast <rtx_jump_insn *> (old_jump); 1894 if (old_jump_insn) 1895 invert_worked = invert_jump (old_jump_insn, 1896 fall_thru_label, 0); 1897 } 1898 1899 if (invert_worked) 1900 { 1901 fall_thru->flags &= ~EDGE_FALLTHRU; 1902 cond_jump->flags |= EDGE_FALLTHRU; 1903 update_br_prob_note (cur_bb); 1904 std::swap (fall_thru, cond_jump); 1905 cond_jump->flags |= EDGE_CROSSING; 1906 fall_thru->flags &= ~EDGE_CROSSING; 1907 } 1908 } 1909 } 1910 1911 if (cond_jump_crosses || !invert_worked) 1912 { 1913 /* This is the case where both edges out of the basic 1914 block are crossing edges. Here we will fix up the 1915 fall through edge. The jump edge will be taken care 1916 of later. The EDGE_CROSSING flag of fall_thru edge 1917 is unset before the call to force_nonfallthru 1918 function because if a new basic-block is created 1919 this edge remains in the current section boundary 1920 while the edge between new_bb and the fall_thru->dest 1921 becomes EDGE_CROSSING. */ 1922 1923 fall_thru->flags &= ~EDGE_CROSSING; 1924 basic_block new_bb = force_nonfallthru (fall_thru); 1925 1926 if (new_bb) 1927 { 1928 new_bb->aux = cur_bb->aux; 1929 cur_bb->aux = new_bb; 1930 1931 /* This is done by force_nonfallthru_and_redirect. */ 1932 gcc_assert (BB_PARTITION (new_bb) 1933 == BB_PARTITION (cur_bb)); 1934 1935 single_succ_edge (new_bb)->flags |= EDGE_CROSSING; 1936 } 1937 else 1938 { 1939 /* If a new basic-block was not created; restore 1940 the EDGE_CROSSING flag. */ 1941 fall_thru->flags |= EDGE_CROSSING; 1942 } 1943 1944 /* Add barrier after new jump */ 1945 emit_barrier_after_bb (new_bb ? new_bb : cur_bb); 1946 } 1947 } 1948 } 1949 } 1950 } 1951 1952 /* This function checks the destination block of a "crossing jump" to 1953 see if it has any crossing predecessors that begin with a code label 1954 and end with an unconditional jump. If so, it returns that predecessor 1955 block. (This is to avoid creating lots of new basic blocks that all 1956 contain unconditional jumps to the same destination). */ 1957 1958 static basic_block 1959 find_jump_block (basic_block jump_dest) 1960 { 1961 basic_block source_bb = NULL; 1962 edge e; 1963 rtx_insn *insn; 1964 edge_iterator ei; 1965 1966 FOR_EACH_EDGE (e, ei, jump_dest->preds) 1967 if (e->flags & EDGE_CROSSING) 1968 { 1969 basic_block src = e->src; 1970 1971 /* Check each predecessor to see if it has a label, and contains 1972 only one executable instruction, which is an unconditional jump. 1973 If so, we can use it. */ 1974 1975 if (LABEL_P (BB_HEAD (src))) 1976 for (insn = BB_HEAD (src); 1977 !INSN_P (insn) && insn != NEXT_INSN (BB_END (src)); 1978 insn = NEXT_INSN (insn)) 1979 { 1980 if (INSN_P (insn) 1981 && insn == BB_END (src) 1982 && JUMP_P (insn) 1983 && !any_condjump_p (insn)) 1984 { 1985 source_bb = src; 1986 break; 1987 } 1988 } 1989 1990 if (source_bb) 1991 break; 1992 } 1993 1994 return source_bb; 1995 } 1996 1997 /* Find all BB's with conditional jumps that are crossing edges; 1998 insert a new bb and make the conditional jump branch to the new 1999 bb instead (make the new bb same color so conditional branch won't 2000 be a 'crossing' edge). Insert an unconditional jump from the 2001 new bb to the original destination of the conditional jump. */ 2002 2003 static void 2004 fix_crossing_conditional_branches (void) 2005 { 2006 basic_block cur_bb; 2007 basic_block new_bb; 2008 basic_block dest; 2009 edge succ1; 2010 edge succ2; 2011 edge crossing_edge; 2012 edge new_edge; 2013 rtx set_src; 2014 rtx old_label = NULL_RTX; 2015 rtx_code_label *new_label; 2016 2017 FOR_EACH_BB_FN (cur_bb, cfun) 2018 { 2019 crossing_edge = NULL; 2020 if (EDGE_COUNT (cur_bb->succs) > 0) 2021 succ1 = EDGE_SUCC (cur_bb, 0); 2022 else 2023 succ1 = NULL; 2024 2025 if (EDGE_COUNT (cur_bb->succs) > 1) 2026 succ2 = EDGE_SUCC (cur_bb, 1); 2027 else 2028 succ2 = NULL; 2029 2030 /* We already took care of fall-through edges, so only one successor 2031 can be a crossing edge. */ 2032 2033 if (succ1 && (succ1->flags & EDGE_CROSSING)) 2034 crossing_edge = succ1; 2035 else if (succ2 && (succ2->flags & EDGE_CROSSING)) 2036 crossing_edge = succ2; 2037 2038 if (crossing_edge) 2039 { 2040 rtx_insn *old_jump = BB_END (cur_bb); 2041 2042 /* Check to make sure the jump instruction is a 2043 conditional jump. */ 2044 2045 set_src = NULL_RTX; 2046 2047 if (any_condjump_p (old_jump)) 2048 { 2049 if (GET_CODE (PATTERN (old_jump)) == SET) 2050 set_src = SET_SRC (PATTERN (old_jump)); 2051 else if (GET_CODE (PATTERN (old_jump)) == PARALLEL) 2052 { 2053 set_src = XVECEXP (PATTERN (old_jump), 0,0); 2054 if (GET_CODE (set_src) == SET) 2055 set_src = SET_SRC (set_src); 2056 else 2057 set_src = NULL_RTX; 2058 } 2059 } 2060 2061 if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE)) 2062 { 2063 rtx_jump_insn *old_jump_insn = 2064 as_a <rtx_jump_insn *> (old_jump); 2065 2066 if (GET_CODE (XEXP (set_src, 1)) == PC) 2067 old_label = XEXP (set_src, 2); 2068 else if (GET_CODE (XEXP (set_src, 2)) == PC) 2069 old_label = XEXP (set_src, 1); 2070 2071 /* Check to see if new bb for jumping to that dest has 2072 already been created; if so, use it; if not, create 2073 a new one. */ 2074 2075 new_bb = find_jump_block (crossing_edge->dest); 2076 2077 if (new_bb) 2078 new_label = block_label (new_bb); 2079 else 2080 { 2081 basic_block last_bb; 2082 rtx_code_label *old_jump_target; 2083 rtx_jump_insn *new_jump; 2084 2085 /* Create new basic block to be dest for 2086 conditional jump. */ 2087 2088 /* Put appropriate instructions in new bb. */ 2089 2090 new_label = gen_label_rtx (); 2091 emit_label (new_label); 2092 2093 gcc_assert (GET_CODE (old_label) == LABEL_REF); 2094 old_jump_target = old_jump_insn->jump_target (); 2095 new_jump = as_a <rtx_jump_insn *> 2096 (emit_jump_insn (targetm.gen_jump (old_jump_target))); 2097 new_jump->set_jump_target (old_jump_target); 2098 2099 last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb; 2100 new_bb = create_basic_block (new_label, new_jump, last_bb); 2101 new_bb->aux = last_bb->aux; 2102 last_bb->aux = new_bb; 2103 2104 emit_barrier_after_bb (new_bb); 2105 2106 /* Make sure new bb is in same partition as source 2107 of conditional branch. */ 2108 BB_COPY_PARTITION (new_bb, cur_bb); 2109 } 2110 2111 /* Make old jump branch to new bb. */ 2112 2113 redirect_jump (old_jump_insn, new_label, 0); 2114 2115 /* Remove crossing_edge as predecessor of 'dest'. */ 2116 2117 dest = crossing_edge->dest; 2118 2119 redirect_edge_succ (crossing_edge, new_bb); 2120 2121 /* Make a new edge from new_bb to old dest; new edge 2122 will be a successor for new_bb and a predecessor 2123 for 'dest'. */ 2124 2125 if (EDGE_COUNT (new_bb->succs) == 0) 2126 new_edge = make_single_succ_edge (new_bb, dest, 0); 2127 else 2128 new_edge = EDGE_SUCC (new_bb, 0); 2129 2130 crossing_edge->flags &= ~EDGE_CROSSING; 2131 new_edge->flags |= EDGE_CROSSING; 2132 } 2133 } 2134 } 2135 } 2136 2137 /* Find any unconditional branches that cross between hot and cold 2138 sections. Convert them into indirect jumps instead. */ 2139 2140 static void 2141 fix_crossing_unconditional_branches (void) 2142 { 2143 basic_block cur_bb; 2144 rtx_insn *last_insn; 2145 rtx label; 2146 rtx label_addr; 2147 rtx_insn *indirect_jump_sequence; 2148 rtx_insn *jump_insn = NULL; 2149 rtx new_reg; 2150 rtx_insn *cur_insn; 2151 edge succ; 2152 2153 FOR_EACH_BB_FN (cur_bb, cfun) 2154 { 2155 last_insn = BB_END (cur_bb); 2156 2157 if (EDGE_COUNT (cur_bb->succs) < 1) 2158 continue; 2159 2160 succ = EDGE_SUCC (cur_bb, 0); 2161 2162 /* Check to see if bb ends in a crossing (unconditional) jump. At 2163 this point, no crossing jumps should be conditional. */ 2164 2165 if (JUMP_P (last_insn) 2166 && (succ->flags & EDGE_CROSSING)) 2167 { 2168 gcc_assert (!any_condjump_p (last_insn)); 2169 2170 /* Make sure the jump is not already an indirect or table jump. */ 2171 2172 if (!computed_jump_p (last_insn) 2173 && !tablejump_p (last_insn, NULL, NULL)) 2174 { 2175 /* We have found a "crossing" unconditional branch. Now 2176 we must convert it to an indirect jump. First create 2177 reference of label, as target for jump. */ 2178 2179 label = JUMP_LABEL (last_insn); 2180 label_addr = gen_rtx_LABEL_REF (Pmode, label); 2181 LABEL_NUSES (label) += 1; 2182 2183 /* Get a register to use for the indirect jump. */ 2184 2185 new_reg = gen_reg_rtx (Pmode); 2186 2187 /* Generate indirect the jump sequence. */ 2188 2189 start_sequence (); 2190 emit_move_insn (new_reg, label_addr); 2191 emit_indirect_jump (new_reg); 2192 indirect_jump_sequence = get_insns (); 2193 end_sequence (); 2194 2195 /* Make sure every instruction in the new jump sequence has 2196 its basic block set to be cur_bb. */ 2197 2198 for (cur_insn = indirect_jump_sequence; cur_insn; 2199 cur_insn = NEXT_INSN (cur_insn)) 2200 { 2201 if (!BARRIER_P (cur_insn)) 2202 BLOCK_FOR_INSN (cur_insn) = cur_bb; 2203 if (JUMP_P (cur_insn)) 2204 jump_insn = cur_insn; 2205 } 2206 2207 /* Insert the new (indirect) jump sequence immediately before 2208 the unconditional jump, then delete the unconditional jump. */ 2209 2210 emit_insn_before (indirect_jump_sequence, last_insn); 2211 delete_insn (last_insn); 2212 2213 JUMP_LABEL (jump_insn) = label; 2214 LABEL_NUSES (label)++; 2215 2216 /* Make BB_END for cur_bb be the jump instruction (NOT the 2217 barrier instruction at the end of the sequence...). */ 2218 2219 BB_END (cur_bb) = jump_insn; 2220 } 2221 } 2222 } 2223 } 2224 2225 /* Update CROSSING_JUMP_P flags on all jump insns. */ 2226 2227 static void 2228 update_crossing_jump_flags (void) 2229 { 2230 basic_block bb; 2231 edge e; 2232 edge_iterator ei; 2233 2234 FOR_EACH_BB_FN (bb, cfun) 2235 FOR_EACH_EDGE (e, ei, bb->succs) 2236 if (e->flags & EDGE_CROSSING) 2237 { 2238 if (JUMP_P (BB_END (bb))) 2239 CROSSING_JUMP_P (BB_END (bb)) = 1; 2240 break; 2241 } 2242 } 2243 2244 /* Reorder basic blocks using the software trace cache (STC) algorithm. */ 2245 2246 static void 2247 reorder_basic_blocks_software_trace_cache (void) 2248 { 2249 if (dump_file) 2250 fprintf (dump_file, "\nReordering with the STC algorithm.\n\n"); 2251 2252 int n_traces; 2253 int i; 2254 struct trace *traces; 2255 2256 /* We are estimating the length of uncond jump insn only once since the code 2257 for getting the insn length always returns the minimal length now. */ 2258 if (uncond_jump_length == 0) 2259 uncond_jump_length = get_uncond_jump_length (); 2260 2261 /* We need to know some information for each basic block. */ 2262 array_size = GET_ARRAY_SIZE (last_basic_block_for_fn (cfun)); 2263 bbd = XNEWVEC (bbro_basic_block_data, array_size); 2264 for (i = 0; i < array_size; i++) 2265 { 2266 bbd[i].start_of_trace = -1; 2267 bbd[i].end_of_trace = -1; 2268 bbd[i].in_trace = -1; 2269 bbd[i].visited = 0; 2270 bbd[i].priority = -1; 2271 bbd[i].heap = NULL; 2272 bbd[i].node = NULL; 2273 } 2274 2275 traces = XNEWVEC (struct trace, n_basic_blocks_for_fn (cfun)); 2276 n_traces = 0; 2277 find_traces (&n_traces, traces); 2278 connect_traces (n_traces, traces); 2279 FREE (traces); 2280 FREE (bbd); 2281 } 2282 2283 /* Return true if edge E1 is more desirable as a fallthrough edge than 2284 edge E2 is. */ 2285 2286 static bool 2287 edge_order (edge e1, edge e2) 2288 { 2289 return e1->count () > e2->count (); 2290 } 2291 2292 /* Reorder basic blocks using the "simple" algorithm. This tries to 2293 maximize the dynamic number of branches that are fallthrough, without 2294 copying instructions. The algorithm is greedy, looking at the most 2295 frequently executed branch first. */ 2296 2297 static void 2298 reorder_basic_blocks_simple (void) 2299 { 2300 if (dump_file) 2301 fprintf (dump_file, "\nReordering with the \"simple\" algorithm.\n\n"); 2302 2303 edge *edges = new edge[2 * n_basic_blocks_for_fn (cfun)]; 2304 2305 /* First, collect all edges that can be optimized by reordering blocks: 2306 simple jumps and conditional jumps, as well as the function entry edge. */ 2307 2308 int n = 0; 2309 edges[n++] = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0); 2310 2311 basic_block bb; 2312 FOR_EACH_BB_FN (bb, cfun) 2313 { 2314 rtx_insn *end = BB_END (bb); 2315 2316 if (computed_jump_p (end) || tablejump_p (end, NULL, NULL)) 2317 continue; 2318 2319 /* We cannot optimize asm goto. */ 2320 if (JUMP_P (end) && extract_asm_operands (end)) 2321 continue; 2322 2323 if (single_succ_p (bb)) 2324 edges[n++] = EDGE_SUCC (bb, 0); 2325 else if (any_condjump_p (end)) 2326 { 2327 edge e0 = EDGE_SUCC (bb, 0); 2328 edge e1 = EDGE_SUCC (bb, 1); 2329 /* When optimizing for size it is best to keep the original 2330 fallthrough edges. */ 2331 if (e1->flags & EDGE_FALLTHRU) 2332 std::swap (e0, e1); 2333 edges[n++] = e0; 2334 edges[n++] = e1; 2335 } 2336 } 2337 2338 /* Sort the edges, the most desirable first. When optimizing for size 2339 all edges are equally desirable. */ 2340 2341 if (optimize_function_for_speed_p (cfun)) 2342 std::stable_sort (edges, edges + n, edge_order); 2343 2344 /* Now decide which of those edges to make fallthrough edges. We set 2345 BB_VISITED if a block already has a fallthrough successor assigned 2346 to it. We make ->AUX of an endpoint point to the opposite endpoint 2347 of a sequence of blocks that fall through, and ->AUX will be NULL 2348 for a block that is in such a sequence but not an endpoint anymore. 2349 2350 To start with, everything points to itself, nothing is assigned yet. */ 2351 2352 FOR_ALL_BB_FN (bb, cfun) 2353 { 2354 bb->aux = bb; 2355 bb->flags &= ~BB_VISITED; 2356 } 2357 2358 EXIT_BLOCK_PTR_FOR_FN (cfun)->aux = 0; 2359 2360 /* Now for all edges, the most desirable first, see if that edge can 2361 connect two sequences. If it can, update AUX and BB_VISITED; if it 2362 cannot, zero out the edge in the table. */ 2363 2364 for (int j = 0; j < n; j++) 2365 { 2366 edge e = edges[j]; 2367 2368 basic_block tail_a = e->src; 2369 basic_block head_b = e->dest; 2370 basic_block head_a = (basic_block) tail_a->aux; 2371 basic_block tail_b = (basic_block) head_b->aux; 2372 2373 /* An edge cannot connect two sequences if: 2374 - it crosses partitions; 2375 - its src is not a current endpoint; 2376 - its dest is not a current endpoint; 2377 - or, it would create a loop. */ 2378 2379 if (e->flags & EDGE_CROSSING 2380 || tail_a->flags & BB_VISITED 2381 || !tail_b 2382 || (!(head_b->flags & BB_VISITED) && head_b != tail_b) 2383 || tail_a == tail_b) 2384 { 2385 edges[j] = 0; 2386 continue; 2387 } 2388 2389 tail_a->aux = 0; 2390 head_b->aux = 0; 2391 head_a->aux = tail_b; 2392 tail_b->aux = head_a; 2393 tail_a->flags |= BB_VISITED; 2394 } 2395 2396 /* Put the pieces together, in the same order that the start blocks of 2397 the sequences already had. The hot/cold partitioning gives a little 2398 complication: as a first pass only do this for blocks in the same 2399 partition as the start block, and (if there is anything left to do) 2400 in a second pass handle the other partition. */ 2401 2402 basic_block last_tail = (basic_block) ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux; 2403 2404 int current_partition 2405 = BB_PARTITION (last_tail == ENTRY_BLOCK_PTR_FOR_FN (cfun) 2406 ? EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0)->dest 2407 : last_tail); 2408 bool need_another_pass = true; 2409 2410 for (int pass = 0; pass < 2 && need_another_pass; pass++) 2411 { 2412 need_another_pass = false; 2413 2414 FOR_EACH_BB_FN (bb, cfun) 2415 if ((bb->flags & BB_VISITED && bb->aux) || bb->aux == bb) 2416 { 2417 if (BB_PARTITION (bb) != current_partition) 2418 { 2419 need_another_pass = true; 2420 continue; 2421 } 2422 2423 last_tail->aux = bb; 2424 last_tail = (basic_block) bb->aux; 2425 } 2426 2427 current_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION; 2428 } 2429 2430 last_tail->aux = 0; 2431 2432 /* Finally, link all the chosen fallthrough edges. */ 2433 2434 for (int j = 0; j < n; j++) 2435 if (edges[j]) 2436 edges[j]->src->aux = edges[j]->dest; 2437 2438 delete[] edges; 2439 2440 /* If the entry edge no longer falls through we have to make a new 2441 block so it can do so again. */ 2442 2443 edge e = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0); 2444 if (e->dest != ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux) 2445 { 2446 force_nonfallthru (e); 2447 e->src->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux; 2448 } 2449 } 2450 2451 /* Reorder basic blocks. The main entry point to this file. */ 2452 2453 static void 2454 reorder_basic_blocks (void) 2455 { 2456 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT); 2457 2458 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1) 2459 return; 2460 2461 set_edge_can_fallthru_flag (); 2462 mark_dfs_back_edges (); 2463 2464 switch (flag_reorder_blocks_algorithm) 2465 { 2466 case REORDER_BLOCKS_ALGORITHM_SIMPLE: 2467 reorder_basic_blocks_simple (); 2468 break; 2469 2470 case REORDER_BLOCKS_ALGORITHM_STC: 2471 reorder_basic_blocks_software_trace_cache (); 2472 break; 2473 2474 default: 2475 gcc_unreachable (); 2476 } 2477 2478 relink_block_chain (/*stay_in_cfglayout_mode=*/true); 2479 2480 if (dump_file) 2481 { 2482 if (dump_flags & TDF_DETAILS) 2483 dump_reg_info (dump_file); 2484 dump_flow_info (dump_file, dump_flags); 2485 } 2486 2487 /* Signal that rtl_verify_flow_info_1 can now verify that there 2488 is at most one switch between hot/cold sections. */ 2489 crtl->bb_reorder_complete = true; 2490 } 2491 2492 /* Determine which partition the first basic block in the function 2493 belongs to, then find the first basic block in the current function 2494 that belongs to a different section, and insert a 2495 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the 2496 instruction stream. When writing out the assembly code, 2497 encountering this note will make the compiler switch between the 2498 hot and cold text sections. */ 2499 2500 void 2501 insert_section_boundary_note (void) 2502 { 2503 basic_block bb; 2504 bool switched_sections = false; 2505 int current_partition = 0; 2506 2507 if (!crtl->has_bb_partition) 2508 return; 2509 2510 FOR_EACH_BB_FN (bb, cfun) 2511 { 2512 if (!current_partition) 2513 current_partition = BB_PARTITION (bb); 2514 if (BB_PARTITION (bb) != current_partition) 2515 { 2516 gcc_assert (!switched_sections); 2517 switched_sections = true; 2518 emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS, BB_HEAD (bb)); 2519 current_partition = BB_PARTITION (bb); 2520 } 2521 } 2522 2523 /* Make sure crtl->has_bb_partition matches reality even if bbpart finds 2524 some hot and some cold basic blocks, but later one of those kinds is 2525 optimized away. */ 2526 crtl->has_bb_partition = switched_sections; 2527 } 2528 2529 namespace { 2530 2531 const pass_data pass_data_reorder_blocks = 2532 { 2533 RTL_PASS, /* type */ 2534 "bbro", /* name */ 2535 OPTGROUP_NONE, /* optinfo_flags */ 2536 TV_REORDER_BLOCKS, /* tv_id */ 2537 0, /* properties_required */ 2538 0, /* properties_provided */ 2539 0, /* properties_destroyed */ 2540 0, /* todo_flags_start */ 2541 0, /* todo_flags_finish */ 2542 }; 2543 2544 class pass_reorder_blocks : public rtl_opt_pass 2545 { 2546 public: 2547 pass_reorder_blocks (gcc::context *ctxt) 2548 : rtl_opt_pass (pass_data_reorder_blocks, ctxt) 2549 {} 2550 2551 /* opt_pass methods: */ 2552 virtual bool gate (function *) 2553 { 2554 if (targetm.cannot_modify_jumps_p ()) 2555 return false; 2556 return (optimize > 0 2557 && (flag_reorder_blocks || flag_reorder_blocks_and_partition)); 2558 } 2559 2560 virtual unsigned int execute (function *); 2561 2562 }; // class pass_reorder_blocks 2563 2564 unsigned int 2565 pass_reorder_blocks::execute (function *fun) 2566 { 2567 basic_block bb; 2568 2569 /* Last attempt to optimize CFG, as scheduling, peepholing and insn 2570 splitting possibly introduced more crossjumping opportunities. */ 2571 cfg_layout_initialize (CLEANUP_EXPENSIVE); 2572 2573 reorder_basic_blocks (); 2574 cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_NO_PARTITIONING); 2575 2576 FOR_EACH_BB_FN (bb, fun) 2577 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun)) 2578 bb->aux = bb->next_bb; 2579 cfg_layout_finalize (); 2580 2581 return 0; 2582 } 2583 2584 } // anon namespace 2585 2586 rtl_opt_pass * 2587 make_pass_reorder_blocks (gcc::context *ctxt) 2588 { 2589 return new pass_reorder_blocks (ctxt); 2590 } 2591 2592 /* Duplicate a block (that we already know ends in a computed jump) into its 2593 predecessors, where possible. Return whether anything is changed. */ 2594 static bool 2595 maybe_duplicate_computed_goto (basic_block bb, int max_size) 2596 { 2597 if (single_pred_p (bb)) 2598 return false; 2599 2600 /* Make sure that the block is small enough. */ 2601 rtx_insn *insn; 2602 FOR_BB_INSNS (bb, insn) 2603 if (INSN_P (insn)) 2604 { 2605 max_size -= get_attr_min_length (insn); 2606 if (max_size < 0) 2607 return false; 2608 } 2609 2610 bool changed = false; 2611 edge e; 2612 edge_iterator ei; 2613 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) 2614 { 2615 basic_block pred = e->src; 2616 2617 /* Do not duplicate BB into PRED if that is the last predecessor, or if 2618 we cannot merge a copy of BB with PRED. */ 2619 if (single_pred_p (bb) 2620 || !single_succ_p (pred) 2621 || e->flags & EDGE_COMPLEX 2622 || pred->index < NUM_FIXED_BLOCKS 2623 || (JUMP_P (BB_END (pred)) && !simplejump_p (BB_END (pred))) 2624 || (JUMP_P (BB_END (pred)) && CROSSING_JUMP_P (BB_END (pred)))) 2625 { 2626 ei_next (&ei); 2627 continue; 2628 } 2629 2630 if (dump_file) 2631 fprintf (dump_file, "Duplicating computed goto bb %d into bb %d\n", 2632 bb->index, e->src->index); 2633 2634 /* Remember if PRED can be duplicated; if so, the copy of BB merged 2635 with PRED can be duplicated as well. */ 2636 bool can_dup_more = can_duplicate_block_p (pred); 2637 2638 /* Make a copy of BB, merge it into PRED. */ 2639 basic_block copy = duplicate_block (bb, e, NULL); 2640 emit_barrier_after_bb (copy); 2641 reorder_insns_nobb (BB_HEAD (copy), BB_END (copy), BB_END (pred)); 2642 merge_blocks (pred, copy); 2643 2644 changed = true; 2645 2646 /* Try to merge the resulting merged PRED into further predecessors. */ 2647 if (can_dup_more) 2648 maybe_duplicate_computed_goto (pred, max_size); 2649 } 2650 2651 return changed; 2652 } 2653 2654 /* Duplicate the blocks containing computed gotos. This basically unfactors 2655 computed gotos that were factored early on in the compilation process to 2656 speed up edge based data flow. We used to not unfactor them again, which 2657 can seriously pessimize code with many computed jumps in the source code, 2658 such as interpreters. See e.g. PR15242. */ 2659 static void 2660 duplicate_computed_gotos (function *fun) 2661 { 2662 /* We are estimating the length of uncond jump insn only once 2663 since the code for getting the insn length always returns 2664 the minimal length now. */ 2665 if (uncond_jump_length == 0) 2666 uncond_jump_length = get_uncond_jump_length (); 2667 2668 /* Never copy a block larger than this. */ 2669 int max_size 2670 = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS); 2671 2672 bool changed = false; 2673 2674 /* Try to duplicate all blocks that end in a computed jump and that 2675 can be duplicated at all. */ 2676 basic_block bb; 2677 FOR_EACH_BB_FN (bb, fun) 2678 if (computed_jump_p (BB_END (bb)) && can_duplicate_block_p (bb)) 2679 changed |= maybe_duplicate_computed_goto (bb, max_size); 2680 2681 /* Duplicating blocks will redirect edges and may cause hot blocks 2682 previously reached by both hot and cold blocks to become dominated 2683 only by cold blocks. */ 2684 if (changed) 2685 fixup_partitions (); 2686 } 2687 2688 namespace { 2689 2690 const pass_data pass_data_duplicate_computed_gotos = 2691 { 2692 RTL_PASS, /* type */ 2693 "compgotos", /* name */ 2694 OPTGROUP_NONE, /* optinfo_flags */ 2695 TV_REORDER_BLOCKS, /* tv_id */ 2696 0, /* properties_required */ 2697 0, /* properties_provided */ 2698 0, /* properties_destroyed */ 2699 0, /* todo_flags_start */ 2700 0, /* todo_flags_finish */ 2701 }; 2702 2703 class pass_duplicate_computed_gotos : public rtl_opt_pass 2704 { 2705 public: 2706 pass_duplicate_computed_gotos (gcc::context *ctxt) 2707 : rtl_opt_pass (pass_data_duplicate_computed_gotos, ctxt) 2708 {} 2709 2710 /* opt_pass methods: */ 2711 virtual bool gate (function *); 2712 virtual unsigned int execute (function *); 2713 2714 }; // class pass_duplicate_computed_gotos 2715 2716 bool 2717 pass_duplicate_computed_gotos::gate (function *fun) 2718 { 2719 if (targetm.cannot_modify_jumps_p ()) 2720 return false; 2721 return (optimize > 0 2722 && flag_expensive_optimizations 2723 && ! optimize_function_for_size_p (fun)); 2724 } 2725 2726 unsigned int 2727 pass_duplicate_computed_gotos::execute (function *fun) 2728 { 2729 duplicate_computed_gotos (fun); 2730 2731 return 0; 2732 } 2733 2734 } // anon namespace 2735 2736 rtl_opt_pass * 2737 make_pass_duplicate_computed_gotos (gcc::context *ctxt) 2738 { 2739 return new pass_duplicate_computed_gotos (ctxt); 2740 } 2741 2742 /* This function is the main 'entrance' for the optimization that 2743 partitions hot and cold basic blocks into separate sections of the 2744 .o file (to improve performance and cache locality). Ideally it 2745 would be called after all optimizations that rearrange the CFG have 2746 been called. However part of this optimization may introduce new 2747 register usage, so it must be called before register allocation has 2748 occurred. This means that this optimization is actually called 2749 well before the optimization that reorders basic blocks (see 2750 function above). 2751 2752 This optimization checks the feedback information to determine 2753 which basic blocks are hot/cold, updates flags on the basic blocks 2754 to indicate which section they belong in. This information is 2755 later used for writing out sections in the .o file. Because hot 2756 and cold sections can be arbitrarily large (within the bounds of 2757 memory), far beyond the size of a single function, it is necessary 2758 to fix up all edges that cross section boundaries, to make sure the 2759 instructions used can actually span the required distance. The 2760 fixes are described below. 2761 2762 Fall-through edges must be changed into jumps; it is not safe or 2763 legal to fall through across a section boundary. Whenever a 2764 fall-through edge crossing a section boundary is encountered, a new 2765 basic block is inserted (in the same section as the fall-through 2766 source), and the fall through edge is redirected to the new basic 2767 block. The new basic block contains an unconditional jump to the 2768 original fall-through target. (If the unconditional jump is 2769 insufficient to cross section boundaries, that is dealt with a 2770 little later, see below). 2771 2772 In order to deal with architectures that have short conditional 2773 branches (which cannot span all of memory) we take any conditional 2774 jump that attempts to cross a section boundary and add a level of 2775 indirection: it becomes a conditional jump to a new basic block, in 2776 the same section. The new basic block contains an unconditional 2777 jump to the original target, in the other section. 2778 2779 For those architectures whose unconditional branch is also 2780 incapable of reaching all of memory, those unconditional jumps are 2781 converted into indirect jumps, through a register. 2782 2783 IMPORTANT NOTE: This optimization causes some messy interactions 2784 with the cfg cleanup optimizations; those optimizations want to 2785 merge blocks wherever possible, and to collapse indirect jump 2786 sequences (change "A jumps to B jumps to C" directly into "A jumps 2787 to C"). Those optimizations can undo the jump fixes that 2788 partitioning is required to make (see above), in order to ensure 2789 that jumps attempting to cross section boundaries are really able 2790 to cover whatever distance the jump requires (on many architectures 2791 conditional or unconditional jumps are not able to reach all of 2792 memory). Therefore tests have to be inserted into each such 2793 optimization to make sure that it does not undo stuff necessary to 2794 cross partition boundaries. This would be much less of a problem 2795 if we could perform this optimization later in the compilation, but 2796 unfortunately the fact that we may need to create indirect jumps 2797 (through registers) requires that this optimization be performed 2798 before register allocation. 2799 2800 Hot and cold basic blocks are partitioned and put in separate 2801 sections of the .o file, to reduce paging and improve cache 2802 performance (hopefully). This can result in bits of code from the 2803 same function being widely separated in the .o file. However this 2804 is not obvious to the current bb structure. Therefore we must take 2805 care to ensure that: 1). There are no fall_thru edges that cross 2806 between sections; 2). For those architectures which have "short" 2807 conditional branches, all conditional branches that attempt to 2808 cross between sections are converted to unconditional branches; 2809 and, 3). For those architectures which have "short" unconditional 2810 branches, all unconditional branches that attempt to cross between 2811 sections are converted to indirect jumps. 2812 2813 The code for fixing up fall_thru edges that cross between hot and 2814 cold basic blocks does so by creating new basic blocks containing 2815 unconditional branches to the appropriate label in the "other" 2816 section. The new basic block is then put in the same (hot or cold) 2817 section as the original conditional branch, and the fall_thru edge 2818 is modified to fall into the new basic block instead. By adding 2819 this level of indirection we end up with only unconditional branches 2820 crossing between hot and cold sections. 2821 2822 Conditional branches are dealt with by adding a level of indirection. 2823 A new basic block is added in the same (hot/cold) section as the 2824 conditional branch, and the conditional branch is retargeted to the 2825 new basic block. The new basic block contains an unconditional branch 2826 to the original target of the conditional branch (in the other section). 2827 2828 Unconditional branches are dealt with by converting them into 2829 indirect jumps. */ 2830 2831 namespace { 2832 2833 const pass_data pass_data_partition_blocks = 2834 { 2835 RTL_PASS, /* type */ 2836 "bbpart", /* name */ 2837 OPTGROUP_NONE, /* optinfo_flags */ 2838 TV_REORDER_BLOCKS, /* tv_id */ 2839 PROP_cfglayout, /* properties_required */ 2840 0, /* properties_provided */ 2841 0, /* properties_destroyed */ 2842 0, /* todo_flags_start */ 2843 0, /* todo_flags_finish */ 2844 }; 2845 2846 class pass_partition_blocks : public rtl_opt_pass 2847 { 2848 public: 2849 pass_partition_blocks (gcc::context *ctxt) 2850 : rtl_opt_pass (pass_data_partition_blocks, ctxt) 2851 {} 2852 2853 /* opt_pass methods: */ 2854 virtual bool gate (function *); 2855 virtual unsigned int execute (function *); 2856 2857 }; // class pass_partition_blocks 2858 2859 bool 2860 pass_partition_blocks::gate (function *fun) 2861 { 2862 /* The optimization to partition hot/cold basic blocks into separate 2863 sections of the .o file does not work well with linkonce or with 2864 user defined section attributes. Don't call it if either case 2865 arises. */ 2866 return (flag_reorder_blocks_and_partition 2867 && optimize 2868 /* See pass_reorder_blocks::gate. We should not partition if 2869 we are going to omit the reordering. */ 2870 && optimize_function_for_speed_p (fun) 2871 && !DECL_COMDAT_GROUP (current_function_decl) 2872 && !lookup_attribute ("section", DECL_ATTRIBUTES (fun->decl)) 2873 /* Workaround a bug in GDB where read_partial_die doesn't cope 2874 with DIEs with DW_AT_ranges, see PR81115. */ 2875 && !(in_lto_p && MAIN_NAME_P (DECL_NAME (fun->decl)))); 2876 } 2877 2878 unsigned 2879 pass_partition_blocks::execute (function *fun) 2880 { 2881 vec<edge> crossing_edges; 2882 2883 if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1) 2884 return 0; 2885 2886 df_set_flags (DF_DEFER_INSN_RESCAN); 2887 2888 crossing_edges = find_rarely_executed_basic_blocks_and_crossing_edges (); 2889 if (!crossing_edges.exists ()) 2890 /* Make sure to process deferred rescans and clear changeable df flags. */ 2891 return TODO_df_finish; 2892 2893 crtl->has_bb_partition = true; 2894 2895 /* Make sure the source of any crossing edge ends in a jump and the 2896 destination of any crossing edge has a label. */ 2897 add_labels_and_missing_jumps (crossing_edges); 2898 2899 /* Convert all crossing fall_thru edges to non-crossing fall 2900 thrus to unconditional jumps (that jump to the original fall 2901 through dest). */ 2902 fix_up_fall_thru_edges (); 2903 2904 /* If the architecture does not have conditional branches that can 2905 span all of memory, convert crossing conditional branches into 2906 crossing unconditional branches. */ 2907 if (!HAS_LONG_COND_BRANCH) 2908 fix_crossing_conditional_branches (); 2909 2910 /* If the architecture does not have unconditional branches that 2911 can span all of memory, convert crossing unconditional branches 2912 into indirect jumps. Since adding an indirect jump also adds 2913 a new register usage, update the register usage information as 2914 well. */ 2915 if (!HAS_LONG_UNCOND_BRANCH) 2916 fix_crossing_unconditional_branches (); 2917 2918 update_crossing_jump_flags (); 2919 2920 /* Clear bb->aux fields that the above routines were using. */ 2921 clear_aux_for_blocks (); 2922 2923 crossing_edges.release (); 2924 2925 /* ??? FIXME: DF generates the bb info for a block immediately. 2926 And by immediately, I mean *during* creation of the block. 2927 2928 #0 df_bb_refs_collect 2929 #1 in df_bb_refs_record 2930 #2 in create_basic_block_structure 2931 2932 Which means that the bb_has_eh_pred test in df_bb_refs_collect 2933 will *always* fail, because no edges can have been added to the 2934 block yet. Which of course means we don't add the right 2935 artificial refs, which means we fail df_verify (much) later. 2936 2937 Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply 2938 that we also shouldn't grab data from the new blocks those new 2939 insns are in either. In this way one can create the block, link 2940 it up properly, and have everything Just Work later, when deferred 2941 insns are processed. 2942 2943 In the meantime, we have no other option but to throw away all 2944 of the DF data and recompute it all. */ 2945 if (fun->eh->lp_array) 2946 { 2947 df_finish_pass (true); 2948 df_scan_alloc (NULL); 2949 df_scan_blocks (); 2950 /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO 2951 data. We blindly generated all of them when creating the new 2952 landing pad. Delete those assignments we don't use. */ 2953 df_set_flags (DF_LR_RUN_DCE); 2954 df_analyze (); 2955 } 2956 2957 /* Make sure to process deferred rescans and clear changeable df flags. */ 2958 return TODO_df_finish; 2959 } 2960 2961 } // anon namespace 2962 2963 rtl_opt_pass * 2964 make_pass_partition_blocks (gcc::context *ctxt) 2965 { 2966 return new pass_partition_blocks (ctxt); 2967 } 2968